機(jī)器學(xué)習(xí)之KNN算法

1 KNN算法

1.1 KNN算法簡介

　　KNN（K-Nearest Neighbor）工作原理：存在一個(gè)樣本數(shù)據(jù)集合，也稱為訓(xùn)練樣本集，并且樣本集中每個(gè)數(shù)據(jù)都存在標(biāo)簽，即我們知道樣本集中每一數(shù)據(jù)與所屬分類對應(yīng)的關(guān)系。輸入沒有標(biāo)簽的數(shù)據(jù)后，將新數(shù)據(jù)中的每個(gè)特征與樣本集中數(shù)據(jù)對應(yīng)的特征進(jìn)行比較，提取出樣本集中特征最相似數(shù)據(jù)（最近鄰）的分類標(biāo)簽。一般來說，我們只選擇樣本數(shù)據(jù)集中前k個(gè)最相似的數(shù)據(jù)，這就是k近鄰算法中k的出處，通常k是不大于20的整數(shù)。最后選擇k個(gè)最相似數(shù)據(jù)中出現(xiàn)次數(shù)最多的分類作為新數(shù)據(jù)的分類。

　　說明：KNN沒有顯示的訓(xùn)練過程，它是“懶惰學(xué)習(xí)”的代表，它在訓(xùn)練階段只是把數(shù)據(jù)保存下來，訓(xùn)練時(shí)間開銷為0，等收到測試樣本后進(jìn)行處理。

　　舉例：以電影分類作為例子，電影題材可分為愛情片，動作片等，那么愛情片有哪些特征？動作片有哪些特征呢？也就是說給定一部電影，怎么進(jìn)行分類？這里假定將電影分為愛情片和動作片兩類，如果一部電影中接吻鏡頭很多，打斗鏡頭較少，顯然是屬于愛情片，反之為動作片。有人曾根據(jù)電影中打斗動作和接吻動作數(shù)量進(jìn)行評估，數(shù)據(jù)如下：

電影名稱	打斗鏡頭	接吻鏡頭	電影類別
Califoria Man	3	104	愛情片
Beautigul Woman	1	81	愛情片
Kevin Longblade	101	10	動作片
Amped II	98	2	動作片

　　給定一部電影數(shù)據(jù)（18，90）打斗鏡頭18個(gè)，接吻鏡頭90個(gè)，如何知道它是什么類型的呢？KNN是這樣做的，首先計(jì)算未知電影與樣本集中其他電影的距離（這里使用曼哈頓距離），數(shù)據(jù)如下：

電影名稱	與未知分類電影的距離
Califoria Man	20.5
Beautigul Woman	19.2
Kevin Longblade	115.3
Amped II	118.9

　　現(xiàn)在我們按照距離的遞增順序排序，可以找到k個(gè)距離最近的電影，加入k=3,那么來看排序的前3個(gè)電影的類別，愛情片，愛情片，動作片，下面來進(jìn)行投票，這部未知的電影愛情片2票，動作片1票，那么我們就認(rèn)為這部電影屬于愛情片。

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

　　優(yōu)點(diǎn)：精度高，對異常值不敏感、無數(shù)據(jù)輸入假定

　　缺點(diǎn)：計(jì)算復(fù)雜度高、空間復(fù)雜度高

1.3 KNN算法python代碼實(shí)現(xiàn)

　　實(shí)現(xiàn)步驟：

　　　　（1）計(jì)算距離

　　　?。?）選擇距離最小的k個(gè)點(diǎn)

　　　　（3）排序

　　Python 3代碼：

 1 import numpy as np
 2 import operator
 3 
 4 def classify(intX,dataSet,labels,k):
 5     '''
 6     KNN算法
 7     '''
 8     #numpy中shape[0]返回?cái)?shù)組的行數(shù)，shape[1]返回列數(shù)
 9     dataSetSize = dataSet.shape[0]
10     #將intX在橫向重復(fù)dataSetSize次，縱向重復(fù)1次
11     #例如intX=([1,2])--->([[1,2],[1,2],[1,2],[1,2]])便于后面計(jì)算
12     diffMat = np.tile(intX,(dataSetSize,1))-dataSet
13     #二維特征相減后乘方
14     sqdifMax = diffMat**2
15     #計(jì)算距離
16     seqDistances = sqdifMax.sum(axis=1)
17     distances = seqDistances**0.5
18     print ("distances:",distances)
19     #返回distance中元素從小到大排序后的索引
20     sortDistance = distances.argsort()
21     print ("sortDistance:",sortDistance)
22     classCount = {}
23     for i in range(k):
24         #取出前k個(gè)元素的類別
25         voteLabel = labels[sortDistance[i]]
26         print ("第%d個(gè)voteLabel=%s",i,voteLabel)
27         classCount[voteLabel] = classCount.get(voteLabel,0)+1
28     #dict.get(key,default=None),字典的get()方法,返回指定鍵的值,如果值不在字典中返回默認(rèn)值。
29     #計(jì)算類別次數(shù)
30 
31     #key=operator.itemgetter(1)根據(jù)字典的值進(jìn)行排序
32     #key=operator.itemgetter(0)根據(jù)字典的鍵進(jìn)行排序
33     #reverse降序排序字典
34     sortedClassCount = sorted(classCount.items(),key = operator.itemgetter(1),reverse = True)
35     #結(jié)果sortedClassCount = [('動作片', 2), ('愛情片', 1)]
36     print ("sortedClassCount:",sortedClassCount)
37     return sortedClassCount[0][0]

View Code

2 KNN算法實(shí)例

2.1 KNN實(shí)現(xiàn)電影分類

 1 import numpy as np
 2 import operator
 3 
 4 def createDataset():
 5     #四組二維特征
 6     group = np.array([[5,115],[7,106],[56,11],[66,9]])
 7     #四組對應(yīng)標(biāo)簽
 8     labels = ('動作片','動作片','愛情片','愛情片')
 9     return group,labels
10 
11 def classify(intX,dataSet,labels,k):
12     '''
13     KNN算法
14     '''
15     #numpy中shape[0]返回?cái)?shù)組的行數(shù)，shape[1]返回列數(shù)
16     dataSetSize = dataSet.shape[0]
17     #將intX在橫向重復(fù)dataSetSize次，縱向重復(fù)1次
18     #例如intX=([1,2])--->([[1,2],[1,2],[1,2],[1,2]])便于后面計(jì)算
19     diffMat = np.tile(intX,(dataSetSize,1))-dataSet
20     #二維特征相減后乘方
21     sqdifMax = diffMat**2
22     #計(jì)算距離
23     seqDistances = sqdifMax.sum(axis=1)
24     distances = seqDistances**0.5
25     print ("distances:",distances)
26     #返回distance中元素從小到大排序后的索引
27     sortDistance = distances.argsort()
28     print ("sortDistance:",sortDistance)
29     classCount = {}
30     for i in range(k):
31         #取出前k個(gè)元素的類別
32         voteLabel = labels[sortDistance[i]]
33         print ("第%d個(gè)voteLabel=%s",i,voteLabel)
34         classCount[voteLabel] = classCount.get(voteLabel,0)+1
35     #dict.get(key,default=None),字典的get()方法,返回指定鍵的值,如果值不在字典中返回默認(rèn)值。
36     #計(jì)算類別次數(shù)
37 
38     #key=operator.itemgetter(1)根據(jù)字典的值進(jìn)行排序
39     #key=operator.itemgetter(0)根據(jù)字典的鍵進(jìn)行排序
40     #reverse降序排序字典
41     sortedClassCount = sorted(classCount.items(),key = operator.itemgetter(1),reverse = True)
42     #結(jié)果sortedClassCount = [('動作片', 2), ('愛情片', 1)]
43     print ("sortedClassCount:",sortedClassCount)
44     return sortedClassCount[0][0]
45 
46 
47 
48 if __name__ == '__main__':
49     group,labels = createDataset()
50     test = [20,101]
51     test_class = classify(test,group,labels,3)
52     print (test_class)

View Code

2.2 改進(jìn)約會網(wǎng)站匹配

　　這個(gè)例子簡單說就是通過KNN找到你喜歡的人，首先數(shù)據(jù)樣本包含三個(gè)特征，（a）每年獲得的飛行?？屠锍虜?shù)（b）玩游戲消耗的時(shí)間（c）每周消耗的冰激淋公升數(shù)，樣本數(shù)據(jù)放在txt中，如下，前三列為三個(gè)特征值，最后一列為標(biāo)簽

下面

首先讀取數(shù)據(jù)，獲取數(shù)據(jù)集和標(biāo)簽

 1 def file2matrix(filename):
 2     fr = open(filename)
 3     arraylines = fr.readlines()
 4     #獲取行數(shù)
 5     numberoflines = len(arraylines)
 6     #返回numpy的數(shù)據(jù)矩陣,目前矩陣數(shù)據(jù)為0
 7     returnMat = np.zeros([numberoflines,3])
 8     #返回的分類標(biāo)簽
 9     classLabelVector = []
10     #行的索引
11     index = 0
12     for line in arraylines:
13         #str.strip(rm) 刪除str頭和尾指定的字符 rm為空時(shí)，默認(rèn)刪除空白符(包括'\n','\r','\t',' ')
14         line = line.strip()
15         #每行數(shù)據(jù)是\t劃分的，將每行數(shù)據(jù)按照\t進(jìn)行切片劃分
16         listFromLine = line.split('\t')
17         #取出前三列數(shù)據(jù)存放到returnMat
18         returnMat[index,:] = listFromLine[0:3]
19         #根據(jù)文本中標(biāo)記的喜歡程度進(jìn)行分類
20         if listFromLine[-1] == "didntLike":
21             classLabelVector.append(1)
22         elif listFromLine[-1] == "smallDoses":
23             classLabelVector.append(2)
24         else:
25             classLabelVector.append(3)
26         index += 1
27     return returnMat,classLabelVector

View Code

數(shù)據(jù)和標(biāo)簽我們可以打印一下：

下面

下面用Matplotlib作圖看一下數(shù)據(jù)信息：

 1 from matplotlib.font_manager import FontProperties
 2 import numpy as np
 3 import matplotlib.pyplot as plt
 4 from prepareData_1 import file2matrix
 5 import matplotlib.lines as mlines
 6 # from matplotlib.font_manage import FontProperties
 7 '''
 8 函數(shù)說明：數(shù)據(jù)可視化
 9 Parameters:
10     datingDataMat - 特征矩陣
11     datingLabels - 分類標(biāo)簽向量
12 Returns:
13     無
14 '''
15 def showDatas(datingDataMat,datingLabels):
16     #設(shè)置漢子格式
17     font = FontProperties(fname=r"c:\windows\fonts\simsun.ttc", size=14)
18     #函數(shù)返回一個(gè)figure圖像和一個(gè)子圖ax的array列表。
19     fig,axs = plt.subplots(nrows=2,ncols=2,sharex=False,sharey=False,figsize=(13,8))
20 
21     numberofLabels = len(datingLabels)
22     LabelColors = []
23     for i in datingLabels:
24         if i==1:
25             LabelColors.append('black')
26         if i ==2:
27             LabelColors.append('orange')
28         if i==3:
29             LabelColors.append("red")
30     #畫散點(diǎn)圖，以數(shù)據(jù)矩陣的第一列（飛行?？蜌v程）、第二列（玩游戲）數(shù)據(jù)話散點(diǎn)圖
31     #散點(diǎn)大小為15 透明度為0.5
32     axs[0][0].scatter(x=datingDataMat[:,0],y=datingDataMat[:,1],color=LabelColors,
33         s=15,alpha=0.5)
34     axs0_title_text=axs[0][0].set_title(u"每年獲得的飛行里程數(shù)與玩視頻游戲消耗時(shí)間占比",
35         FontProperties=font)
36     axs0_xlabel_text=axs[0][0].set_xlabel("每年獲得的飛行?？屠锍虜?shù)",FontProperties=font)
37     axs0_ylabel_text=axs[0][0].set_ylabel("玩游戲消耗的時(shí)間",FontProperties=font)
38     plt.setp(axs0_title_text,size=9,weight='bold',color='red')
39     #畫散點(diǎn)圖，以數(shù)據(jù)矩陣的第一列（飛行?？蜌v程）、第三列（冰激淋公斤數(shù)）數(shù)據(jù)話散點(diǎn)圖
40     #散點(diǎn)大小為15 透明度為0.5
41     axs[0][1].scatter(x=datingDataMat[:,0],y=datingDataMat[:,2],color=LabelColors,
42         s=15,alpha=0.5)
43     axs0_title_text=axs[0][0].set_title("每年獲得的飛行里程數(shù)與冰激淋公斤數(shù)占比",
44         FontProperties=font)
45     axs0_xlabel_text=axs[0][0].set_xlabel("每年獲得的飛行常客里程數(shù)",FontProperties=font)
46     axs0_ylabel_text=axs[0][0].set_ylabel("所吃冰激淋公斤數(shù)",FontProperties=font)
47     plt.setp(axs0_title_text,size=9,weight='bold',color='red')
48     #畫散點(diǎn)圖，以數(shù)據(jù)矩陣的第二列（玩游戲）、第三列（冰激淋公斤數(shù)）數(shù)據(jù)話散點(diǎn)圖
49     #散點(diǎn)大小為15 透明度為0.5
50     axs[1][0].scatter(x=datingDataMat[:,1],y=datingDataMat[:,2],color=LabelColors,
51         s=15,alpha=0.5)
52     axs0_title_text=axs[0][0].set_title("玩游戲時(shí)間與冰激淋公斤數(shù)占比",
53         FontProperties=font)
54     axs0_xlabel_text=axs[0][0].set_xlabel("每年獲得的飛行常客里程數(shù)",FontProperties=font)
55     axs0_ylabel_text=axs[0][0].set_ylabel("所吃冰激淋公斤數(shù)",FontProperties=font)
56     plt.setp(axs0_title_text,size=9,weight='bold',color='red')
57 
58     #設(shè)置圖例
59     didntLike = mlines.Line2D([],[],color='black',marker='.',markersize=6,label='didntlike')
60     smallDose = mlines.Line2D([],[],color='orange',marker='.',markersize=6,label='smallDose')
61     largeDose = mlines.Line2D([],[],color='red',marker='.',markersize=6,label='largeDose')
62 
63     #添加圖例
64     axs[0][0].legend(handles=[didntLike,smallDose,largeDose])
65     axs[0][1].legend(handles=[didntLike,smallDose,largeDose])
66     axs[1][0].legend(handles=[didntLike,smallDose,largeDose])
67 
68     plt.show()
69 
70 if __name__ == '__main__':
71     filename = "datingTestSet.txt"
72     returnMat,classLabelVector = file2matrix(filename)
73     showDatas(returnMat,classLabelVector)
74             
75

View Code

這里我把py文件分開寫了，還要注意txt數(shù)據(jù)的路徑，高大上的圖：

樣本數(shù)據(jù)中的到底喜歡什么樣子的人？自己去分析一下吧。下面要對數(shù)據(jù)進(jìn)行歸一化，歸一化的原因就不多說了，

 1 from prepareData_1 import file2matrix
 2 import numpy as np
 3 '''
 4 函數(shù)說明：數(shù)據(jù)歸一化
 5 Parameters:
 6     dataSet - 特征矩陣
 7 Returns:
 8     normDataSet - 歸一化后的特征矩陣
 9     ranges - 數(shù)據(jù)范圍
10     minVals - 數(shù)據(jù)最小值
11 '''
12 
13 def autoNorm(dataSet):
14     #獲得數(shù)據(jù)的最大最小值
15     print (dataSet)
16     print ("**********************")
17     minVals = dataSet.min(0)
18     maxVals = dataSet.max(0)
19     print ("minValues:",minVals)
20     print ("maxValuse:",maxVals)
21     #計(jì)算最大最小值的差
22     ranges = maxVals - minVals
23     print ()
24     #shape(dataSet)返回dataSet的矩陣行列數(shù)
25     normDataSet=np.zeros(np.shape(dataSet))
26     #返回dataSet的行數(shù)
27     m = dataSet.shape[0]
28     #原始值減去最小值
29     normDataSet=dataSet-np.tile(minVals,(m,1))
30     #除以最大值和最小值的差，得到的歸一化的數(shù)據(jù)
31     normDataSet = normDataSet/np.tile(ranges,(m,1))
32     return normDataSet,ranges,minVals

View Code

歸一化后的數(shù)據(jù)如下：

有了以上步驟，下面就可以構(gòu)建完整的約會分類，去找你喜歡的人了：

 1 from prepareData_1 import file2matrix
 2 from dataNormal_3 import autoNorm
 3 import operator
 4 import numpy as np
 5 '''
 6 函數(shù)說明：knn算法，分類器
 7 Parameters:
 8     inX - 用于分類的數(shù)據(jù)（測試集）
 9     dataset - 用于訓(xùn)練的數(shù)據(jù)（訓(xùn)練集）
10     labes - 分類標(biāo)簽
11     k - knn算法參數(shù)，選擇距離最小的k個(gè)點(diǎn)
12 Returns:
13     sortedClassCount[0][0] - 分類結(jié)果
14 '''
15 def classify0(inX,dataset,labes,k):
16     dataSetSize = dataset.shape[0]  #返回行數(shù)
17     diffMat = np.tile(inX,(dataSetSize,1))-dataset
18     sqDiffMat = diffMat**2
19     sqDistances = sqDiffMat.sum(axis=1)
20     distances = sqDistances**0.5
21     sortedDistIndices  =distances.argsort()
22     classCount = {}
23     for i in range(k):
24         voteLabel = labes[sortedDistIndices[i]]
25         classCount[voteLabel] = classCount.get(voteLabel,0)+1
26     sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
27     return sortedClassCount[0][0]
28 def datingClassTest():
29     #filename="test.txt"
30     filename = "datingTestSet.txt"
31     datingDataMat,datingLabels = file2matrix(filename)
32     #取所有數(shù)據(jù)的10%
33     hoRatio = 0.1
34     #數(shù)據(jù)歸一化，返回歸一化后的矩陣，數(shù)據(jù)范圍，數(shù)據(jù)最小值
35     normMat,ranges,minVals = autoNorm(datingDataMat)
36     #獲得nornMat的行數(shù)
37     m = normMat.shape[0]
38     #百分之十的測試數(shù)據(jù)的個(gè)數(shù)
39     numTestVecs = int(m*hoRatio)
40     #分類錯(cuò)誤計(jì)數(shù)
41     errorCount = 0.0
42 
43     for i in range(numTestVecs):
44         #前numTestVecs個(gè)數(shù)據(jù)作為測試集，后m-numTestVecs個(gè)數(shù)據(jù)作為訓(xùn)練集
45         classifierResult = classify0(normMat[i,:],normMat[numTestVecs:m,:],
46             datingLabels[numTestVecs:m],10)
47         print ("分類結(jié)果：%d \t真實(shí)類別：%d"%(classifierResult,datingLabels[i]))
48         if classifierResult != datingLabels[i]:
49             errorCount += 1.0
50     print ("錯(cuò)誤率：%f"%(errorCount/float(numTestVecs)*100))
51 
52 if __name__ == '__main__':
53     datingClassTest()

View Code

都是上面的步驟，這里就不解釋了，結(jié)果如下所示：

2.3 手寫數(shù)字識別

　　數(shù)據(jù)可以樣例可以打開文本文件進(jìn)行查看，其中txt文件名的第一個(gè)數(shù)字為本txt中的數(shù)字，目錄trainingDigits中包含了大約2000個(gè)例子，每個(gè)數(shù)字大約有200個(gè)樣本，testDigits中包含900個(gè)測試數(shù)據(jù)，我們使用trainingDigits中的數(shù)據(jù)訓(xùn)練分類器，testDigits中的數(shù)據(jù)作為測試，兩組數(shù)據(jù)沒有重合。

數(shù)據(jù)在這里：https://github.com/Jenny0611/Ml_Learning01

首先我們要將圖像數(shù)據(jù)處理為一個(gè)向量，將32*32的二進(jìn)制圖像信息轉(zhuǎn)化為1*1024的向量，再使用前面的分類器，代碼如下：

 1 import numpy as np
 2 import operator
 3 from os import listdir
 4 from sklearn.neighbors import KNeighborsClassifier as kNN
 5 
 6 '''
 7 函數(shù)說明：將32*32的二進(jìn)制圖片轉(zhuǎn)換為1*1024向量
 8 Parameters:
 9     filename - 文件名
10 Returns:
11     returnVect - 返回的二進(jìn)制圖像的1*1024向量
12 '''
13 def img2vector(filename):
14     #創(chuàng)建1*1024的0向量
15     returnVect = np.zeros((1,1024))
16     fr = open(filename)
17     #按行讀取
18     for i in range(32):
19         #讀一行數(shù)據(jù)
20         lineStr=fr.readline()
21         #每一行的前32個(gè)數(shù)據(jù)依次添加到returnVect
22         for j in range(32):
23             returnVect[0,32*i+j]=int(lineStr[j])
24     return returnVect
25 
26 '''
27 函數(shù)說明：手寫數(shù)字分類測試
28 Parameters:
29     filename - 無
30 Returns:
31     returnVect - 無
32 '''
33 def handwritingClassTest():
34     #測試集的labels
35     hwLabels=[]
36     #返回trainingDigits目錄下的文件名
37     trainingFileList=listdir('trainingDigits')
38     #返回文件夾下文件的個(gè)數(shù)
39     m=len(trainingFileList)
40     #初始化訓(xùn)練的Mat矩陣的測試集
41     trainingMat=np.zeros((m,1024))
42     #從文件名中解析出訓(xùn)練集的類別
43     for i in range(m):
44         fileNameStr=trainingFileList[i]
45         classNumber = int(fileNameStr.split('_')[0])
46         #將獲取的類別添加到hwLabels中
47         hwLabels.append(classNumber)
48         #將每一個(gè)文件的1*1024數(shù)據(jù)存儲到trainingMat矩陣中
49         trainingMat[i,:]=img2vector('trainingDigits/%s'%(fileNameStr))
50     #構(gòu)建KNN分類器
51     neigh = kNN(n_neighbors=3,algorithm='auto')
52     #擬合模型，trainingMat為測試矩陣,hwLabels為對應(yīng)的標(biāo)簽
53     neigh.fit(trainingMat,hwLabels)
54     #返回testDigits目錄下的文件列表
55     testFileList=listdir('testDigits')
56     errorCount=0.0
57     mTest=len(testFileList)
58     #從文件中解析出測試集的類別并進(jìn)行分類測試
59     for i in range(mTest):
60         fileNameStr=testFileList[i]
61         classNumber=int(fileNameStr.split('_')[0])
62         #獲得測試集的1*1024向量用于訓(xùn)練
63         vectorUnderTest=img2vector('testDigits/%s'%(fileNameStr))
64         #獲得預(yù)測結(jié)果
65         classifierResult=neigh.predict(vectorUnderTest)
66         print ("分類返回結(jié)果%d\t真實(shí)結(jié)果%d"%(classifierResult,classNumber))
67         if (classNumber != classifierResult):
68             errorCount += 1.0
69     print ("總共錯(cuò)了%d個(gè)\t錯(cuò)誤率為%f%%"%(errorCount,errorCount/mTest*100))
70 
71 if __name__ == '__main__':
72     handwritingClassTest()

View Code

2.4 小結(jié)

　　KNN是簡單有效的分類數(shù)據(jù)算法，在使用時(shí)必須有訓(xùn)練樣本數(shù)據(jù)，還要計(jì)算距離，如果數(shù)據(jù)量非常大會非常消耗空間和時(shí)間。它的另一個(gè)缺陷是無法給出任何數(shù)據(jù)的基礎(chǔ)結(jié)構(gòu)信息，因此我們無法平均實(shí)例樣本和典型實(shí)例樣本具體特征，而決策樹將使用概率測量方法處理分類問題，以后章節(jié)會介紹。

本文參考：http://blog.csdn.net/c406495762/article/details/75172850

　　　　　《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》

posted @ 2017-09-24 22:20 知其然，知其所以然。閱讀(50505) 評論(5) 收藏舉報(bào)

刷新頁面返回頂部

知其然，知其所以然。

用簡單的話和栗子來學(xué)習(xí)

機(jī)器學(xué)習(xí)之KNN算法

公告

知其然，知其所以然。

用簡單的話和栗子來學(xué)習(xí)

機(jī)器學(xué)習(xí)之KNN算法

公告

知其然，知其所以然。