Cycoe@Home

[python機器學習-1] K 近鄰算法實現驗證碼識別

A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.

b8e80b83eb2b7e31.jpg
Figure 1: image1

機器學習在最近幾年有越來越火熱的趨勢。正巧打算做一個爬取教務網成績的爬蟲,碰到驗 證碼識別的問題。於是通過各方瞭解後買了《機器學習實戰》這本書,開坑機器學習。機器 學習的內容其實很廣,涉及的知識也非常的雜,包括概率論、統計學、逼近論、凸分析、算 法複雜度理論和編程等等。因爲不是本科涉及的內容,只能一點一點的補。

<!–more–>

1 分類

機器學習分爲監督學習和無監督學習兩種,監督學習是指算法知道要預測的目標,即目標變 量的分類信息;而無監督學習時,數據沒有類別信息,也不會給定目標值。

監督學習 無監督學習
k-近鄰算法 K-均值
樸素貝葉斯算法 DBSCAN
支持向量機 \
決策樹 \

2 核心思想

k-近鄰算法的原理很簡單,即選取 m 個已分類的樣本作爲訓練集,每個樣本擁有 n 個特徵。 待測試樣本與每個訓練樣本求歐式距離,對得到的距離順序排序。根據預設的 k 值(k 一 般取一個比較小的數)取出前 k 個距離。最後統計每個類別出現的次數,取出現次數最多 的類別作爲待測樣本的類別標籤。

此處說明 KNN 算法的兩個特徵:

  • 各個特徵等權重,不考慮各個特徵對類別的貢獻大小
  • 最終的分類方法其實是投票表決的方法

3 代碼

爲了提高代碼的運行效率及編碼效率,import 了 Numpy 庫,具體的函數看官方文檔 ,或者 Numpy 教程

3.1 分類函數

def classify0(inX, dataSet, labels, k): #輸入(待測樣本向量,訓練樣本矩陣,標籤向量,k)
    dataSetSize = dataSet.shape[0] #shape函數用來讀取矩陣的維的長度,返回值爲(4L,2L)
    diffMat = tile(inX, (dataSetSize, 1)) - dataSet #tile函數用來重複 A=[1,2] tile(A,(2,3)) -> [[1,2,1,2,1,2], [1,2,1,2,1,2]]
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances**0.5

    sortedDistIndicies = distances.argsort()
    classCount = {}
    for i in range(k):
        votedLabel = labels[sortedDistIndicies[i]]
        classCount[votedLabel] = classCount.get(votedLabel, 0) + 1 #dict.get(key, default_value)函數用來取鍵對應的值,若鍵不存在則值爲defalut_vlaue
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True) #operator.itemgetter(1)表示根據多級列表的第二個元素進行排序
    return sortedClassCount[0][0]
Author: Cycoe (cycoejoo@163.com)
Date: <2017-03-12 Sun>
Generator: Emacs 28.0.50 (Org mode 9.3)
Built: <2020-05-21 Thu 20:09>