kNN算法python實(shí)現(xiàn)和簡(jiǎn)單數(shù)字識(shí)別

2019-11-14 17:30:31

字體：大中小

供稿：網(wǎng)友

kNN算法

算法優(yōu)缺點(diǎn)：

優(yōu)點(diǎn)：精度高、對(duì)異常值不敏感、無(wú)輸入數(shù)據(jù)假定
缺點(diǎn)：時(shí)間復(fù)雜度和空間復(fù)雜度都很高
適用數(shù)據(jù)范圍:數(shù)值型和標(biāo)稱型

算法的思路：

KNN算法（全稱K最近鄰算法），算法的思想很簡(jiǎn)單，簡(jiǎn)單的說(shuō)就是物以類聚，也就是說(shuō)我們從一堆已知的訓(xùn)練集中找出k個(gè)與目標(biāo)最靠近的，然后看他們中最多的分類是哪個(gè)，就以這個(gè)為依據(jù)分類。

函數(shù)解析：

庫(kù)函數(shù)

tile()
如tile(A,n)就是將A重復(fù)n次

a = np.array([0, 1, 2])np.tile(a, 2)array([0, 1, 2, 0, 1, 2])np.tile(a, (2, 2))array([[0, 1, 2, 0, 1, 2],[0, 1, 2, 0, 1, 2]])np.tile(a, (2, 1, 2))array([[[0, 1, 2, 0, 1, 2]],[[0, 1, 2, 0, 1, 2]]])b = np.array([[1, 2], [3, 4]])np.tile(b, 2)array([[1, 2, 1, 2],[3, 4, 3, 4]])np.tile(b, (2, 1))array([[1, 2],[3, 4],[1, 2],[3, 4]])`

自己實(shí)現(xiàn)的函數(shù)

createDataSet()生成測(cè)試數(shù)組
kNNclassify(inputX, dataSet, labels, k)分類函數(shù)

inputX 輸入的參數(shù)
dataSet 訓(xùn)練集
labels 訓(xùn)練集的標(biāo)號(hào)

k 最近鄰的數(shù)目

 1 #coding=utf-8 2 from numpy import * 3 import Operator 4  5 def createDataSet(): 6     group = array([[1.0, 0.9], [1.0, 1.0], [0.1, 0.2], [0.0, 0.1]]) 7     labels = ['A','A','B','B'] 8     return group,labels 9 #inputX表示輸入向量（也就是我們要判斷它屬于哪一類的）10 #dataSet表示訓(xùn)練樣本11 #label表示訓(xùn)練樣本的標(biāo)簽12 #k是最近鄰的參數(shù)，選最近k個(gè)13 def kNNclassify(inputX, dataSet, labels, k):14     dataSetSize = dataSet.shape[0]#計(jì)算有幾個(gè)訓(xùn)練數(shù)據(jù)15     #開(kāi)始計(jì)算歐幾里得距離16     diffMat = tile(inputX, (dataSetSize,1)) - dataSet17     18     sqDiffMat = diffMat ** 219     sqDistances = sqDiffMat.sum(axis=1)#矩陣每一行向量相加20     distances = sqDistances ** 0.521     #歐幾里得距離計(jì)算完畢22     sortedDistance = distances.argsort()23     classCount = {}24     for i in xrange(k):25         voteLabel = labels[sortedDistance[i]]26         classCount[voteLabel] = classCount.get(voteLabel,0) + 127     res = max(classCount)28     return res29 30 def main():31     group,labels = createDataSet()32     t = kNNclassify([0,0],group,labels,3)33     PRint t34     35 if __name__=='__main__':36     main()37

kNN應(yīng)用實(shí)例

手寫(xiě)識(shí)別系統(tǒng)的實(shí)現(xiàn)

數(shù)據(jù)集：

兩個(gè)數(shù)據(jù)集：training和test。分類的標(biāo)號(hào)在文件名中。像素32*32的。數(shù)據(jù)大概這個(gè)樣子：

方法：

kNN的使用，不過(guò)這個(gè)距離算起來(lái)比較復(fù)雜（1024個(gè)特征），主要是要處理如何讀取數(shù)據(jù)這個(gè)問(wèn)題的，比較方面直接調(diào)用就可以了。

速度：

速度還是比較慢的，這里數(shù)據(jù)集是：training 2000+，test 900+（i5的CPU）
k=3的時(shí)候要32s+

 1 #coding=utf-8 2 from numpy import * 3 import operator 4 import os 5 import time 6  7 def createDataSet(): 8     group = array([[1.0, 0.9], [1.0, 1.0], [0.1, 0.2], [0.0, 0.1]]) 9     labels = ['A','A','B','B']10     return group,labels11 #inputX表示輸入向量（也就是我們要判斷它屬于哪一類的）12 #dataSet表示訓(xùn)練樣本13 #label表示訓(xùn)練樣本的標(biāo)簽14 #k是最近鄰的參數(shù)，選最近k個(gè)15 def kNNclassify(inputX, dataSet, labels, k):16     dataSetSize = dataSet.shape[0]#計(jì)算有幾個(gè)訓(xùn)練數(shù)據(jù)17     #開(kāi)始計(jì)算歐幾里得距離18     diffMat = tile(inputX, (dataSetSize,1)) - dataSet19     #diffMat = inputX.repeat(dataSetSize, aixs=1) - dataSet20     sqDiffMat = diffMat ** 221     sqDistances = sqDiffMat.sum(axis=1)#矩陣每一行向量相加22     distances = sqDistances ** 0.523     #歐幾里得距離計(jì)算完畢24     sortedDistance = distances.argsort()25     classCount = {}26     for i in xrange(k):27         voteLabel = labels[sortedDistance[i]]28         classCount[voteLabel] = classCount.get(voteLabel,0) + 129     res = max(classCount)30     return res31 32 def img2vec(filename):33     returnVec = zeros((1,1024))34     fr = open(filename)35     for i in range(32):36         lineStr = fr.readline()37         for j in range(32):38             returnVec[0,32*i+j] = int(lineStr[j])39     return returnVec40     41 def handwritingClassTest(trainingFloder,testFloder,K):42     hwLabels = []43     trainingFileList = os.listdir(trainingFloder)44     m = len(trainingFileList)45     trainingMat = zeros((m,1024))46     for i in range(m):47         fileName = trainingFileList[i]48         fileStr = fileName.split('.')[0]49         classNumStr = int(fileStr.split('_')[0])50         hwLabels.append(classNumStr)51         trainingMat[i,:] = img2vec(trainingFloder+'/'+fileName)52     testFileList = os.listdir(testFloder)53     errorCount = 0.054     mTest = len(testFileList)55     for i in range(mTest):56         fileName = testFileList[i]57         fileStr = fileName.split('.')[0]58         classNumStr = int(fileStr.split('_')[0])59         vectorUnderTest = img2vec(testFloder+'/'+fileName)60         classifierResult = kNNclassify(vectorUnderTest, trainingMat, hwLabels, K)61         #print classifierResult,' ',classNumStr62         if classifierResult != classNumStr:63             errorCount +=164     print 'tatal error ',errorCount65     print 'error rate',errorCount/mTest66         67 def main():68     t1 = time.clock()69     handwritingClassTest('trainingDigits','testDigits',3)70     t2 = time.clock()71     print 'execute ',t2-t172 if __name__=='__main__':73     main()74