[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.

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

<!–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]