參考資料

《機器學習實戰》，Machine Learning in Action，本文中簡稱MLiA
《機器學習》周志華，本文簡稱西瓜書
《Web安全之機器學習》劉焱著，本文中簡稱WSML(Web Security in Machine Learning，該英文翻譯只為記錄方便，是本人杜撰的，僅限本系列文章使用)

轉載請注明出處：http://blog.csdn.net/rosetta/article/details/79179004

前言

因為之前不知道怎么把機器學習的知識用起來，所以心理很沒底，看了近一年的數學基礎，感覺也沒有什么長進，而看了《機器學習實戰》第2章k-近鄰算法后發現，原來機器學習也可以這么簡單。
本算法真不需要什么高深的數學公式，只要會一些基礎的矩陣知識就可以了。代碼里Numpy ndarray相關的東西看起來挺復雜的，但打出來調試后也就不會覺得難了。
另外我發現了自己學習的方法（其實原來也發現了，只是沒總結），先跟著書把代碼敲一遍（或者直接復制粘貼），這個時候不要去看書上關于代碼的解釋，因為看不懂，看不懂會影響學習心情，所以不要看。先把代碼運行一遍看結果，運行成功后再看不理解的代碼，邊看邊調試，比看書本上關于代碼的解釋效果好多了。

本次學習以實踐為主，理論為輔。為了加深對KNN算法的理解，我學了以下內容，雖然很多，但我相信如果大家對以下內容都理解了，那么KNN算法也就掌握了。主要內容有以下五，我會分五篇文章完成學習記錄。

使用KNN算法對約會對象魅力程度分類

使用sklearn庫中的KNN算法對約會對象魅力程度分類

使用KNN算法完成手寫識別系統

使用KNN算法完成西瓜分類

使用KNN算法檢測Linux系統異常操作

本篇文章先描述K-近鄰算法核心思想，再記錄使用KNN算法對約會對象魅力程度分類的代碼的理解。

K-近鄰算法

所謂的k-近鄰算法（K-Nearest Neighbor，簡稱KNN）是這樣的，首先要有一批已知的樣本數據的特征（比如MLiA舉的交友例子，交友對象的年飛行里程、玩游戲占的時間比和周消費的冰淇淋公升數），并且知道這些數據的標簽（不喜歡的人、魅力一般的人和極具魅力的人），然后輸入不帶標簽的新數據（知道這個人的年飛行里程、玩游戲占的時間比和周消費的冰淇淋公升數，但不知道它屬于哪一類），拿這個新數據和樣本數據比較，算出和新數據最相似的k個數據（k可自定義），然后看這k個數據中出現最多的類型，新數據就屬于這一類。
所以整體思想是很簡單的，但這里面會延伸出三個問題：
1. 新數據和樣本數據距離計算公式是怎樣的？
2. 如果某一項屬性數據太大，這樣在計算距離時其它屬性就不起作用了，但是其它屬性也是一樣重要的，那怎么辦?這就需要做歸一化處理。
3. 如何測試算法的準確性。這里會拿樣本數據的前x%用于作為直接的樣本（因為k-近鄰算法沒有訓練數據概念，這里姑且叫它訓練數據），后面的1-x%數據拿來測試（叫測試數據）。

相關概念

本節內容可先跳過，如后續看的不明白可回來查看相關概念。
KNN算法中的訓練數據和一般意義上的訓練數據不太一樣。因為在KNN中實際上是不需要訓練數據的，只需要知道一些已知的帶標簽的數據就可以了，后續新來的數據只要和這些已知標簽的數據做運算就可以了。

所以這里的相關解釋如下：

• 樣本數據

  所有帶標簽的數據。其中一部分拿來用做訓練數據（比如80%），一部分拿來當測試數據（比如剩下的20%）。

• 訓練數據

  帶標簽的標本數據，實際上是給KNN算法本身使用的。當測試數據或待預測數據來了時和這些數據做運算使用。

• 測試數據

  測試數據也是帶標簽的，是在樣本數據中預留出來的，用以檢測算法正確率的。當算法已經設計好后，給算法傳入這些測試數據，然后取得算法返回的預測結果，并把這些預測結果和已知的標簽做對比，從而計算出算法的正確率。

使用KNN算法對約會對象魅力程度分類

先來看下最終效果，有一個直觀的認識。

最終效果

最終效果如下。輸入年飛行里程、玩游戲占的時間比和周消費的冰淇淋公升數，程序輸出這個人的魅力程度。

代碼分析

代碼分析請直接看注釋。

def classifyPerson():resultList = ['沒有魅力', '魅力一般', '極具魅力']ffMiles = float(input("每年飛行公里數？"))percentTats=float(input("打游戲耗費時間的百分比？"))iceCream = float(input("每周消費的冰激凌?"))datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')normMat, ranges, minVals = autoNorm(datingDataMat)inArr = np.array([ffMiles,percentTats,iceCream])classifierResult = classify0((inArr-minVals)/ranges, normMat, datingLabels, 3)print("這個人：", resultList[classifierResult-1])#從文件中獲取數據，并格式化成Numpy數組。 #returnMat[]數組用于存放樣本的屬性。 #classLabelVector[]用于存放樣本的類別 def file2matrix(filename):fr = open(filename)numberOfLines = len(fr.readlines()) #1000returnMat = np.zeros((numberOfLines,3)) #創建numberOfLines行，3列矩陣，初始化為0.classLabelVector = [] #用于存放第四列的的值。fr = open(filename)index = 0for line in fr.readlines():line = line.strip()listFromLine = line.split('\t')returnMat[index,:] = listFromLine[0:3] #因為index是會自增的，所以數據會往returnMat上增。classLabelVector.append(int(listFromLine[-1]))index += 1return returnMat,classLabelVector # returnMat={ndarray} [[ 4.09200000e+04 8.32697600e+00 9.53952000e-01] # [ 1.44880000e+04 7.15346900e+00 1.67390400e+00] # [ 2.60520000e+04 1.44187100e+00 8.05124000e-01] # ..., # [ 2.65750000e+04 1.06501020e+01 8.66627000e-01] # [ 4.81110000e+04 9.13452800e+00 7.28045000e-01] # [ 4.37570000e+04 7.88260100e+00 1.33244600e+00]] #classLabelVector={list}[3, 2, 1, 1, 1, 1, 3, 3, 1, 3, 1, 1, 2, 1, 1,……]#歸一化處理公式：newValue=(oldValue-min)/(max-min) def autoNorm(dataSet):#dataSet是1000行3列的數據。minVals = dataSet.min(0)maxVals = dataSet.max(0)ranges = maxVals - minValsnormDataSet = np.zeros(np.shape(dataSet))#shape取ndarray dataSet的大小（維度），然后創建一個一樣大小的ndarray,并以0初始化。m = dataSet.shape[0]#取0維大小，1000行。normDataSet = dataSet - np.tile(minVals, (m,1))#做(oldValue-min)操作normDataSet = normDataSet/np.tile(ranges, (m,1)) #element wise dividereturn normDataSet, ranges, minVals # normDataSet={ndarray}[[ 0.44832535 0.39805139 0.56233353] # [ 0.15873259 0.34195467 0.98724416] # [ 0.28542943 0.06892523 0.47449629] # ..., # [ 0.29115949 0.50910294 0.51079493] # [ 0.52711097 0.43665451 0.4290048 ] # [ 0.47940793 0.3768091 0.78571804]]# ranges={ndarray}[ 9.12730000e+04 2.09193490e+01 1.69436100e+00] # minVals={ndarray}[ 0. 0. 0.001156]#classify0的作用： #給定一個輸入List inX，可以是n維，這個inX一般存放待分類的條目的屬性值，然后和已知數據集（因為是已知的，所以標簽類別也是已知的）相比（通過兩點差的平方和再開根號），算出最近的k個，這k個數據中出現次數就是最多的類別就是新數據的類別。 #輸出即是該條目的類別。#這個分類函數是支持多維的，而該函數里的注釋是基于2維寫的。 #2維情況的輸入值： #inX=[0, 0] #dataSet= #這個即是已知的數據屬性（這里有4條數據，每條數據有兩個屬性） # [[ 1. 1.1] # [ 1. 1. ] # [ 0. 0. ] # [ 0. 0.1]] #labels=['A', 'A', 'B', 'B'] #這個就是已知的數據的類別 #k=3 表示只取最近的3個做比較， #輸出A或B。 def classify0(inX, dataSet, labels, k):dataSetSize = dataSet.shape[0] #計算dataSet有多少行，這里的0維指x行diffMat = np.tile(inX, (dataSetSize,1)) - dataSet#生成和dataSet一樣大小的數組，其每行的成員(x,y)都是inX的x,y減dataSet對應行的x,y。sqDiffMat = diffMat**2 #對每個成員做平方操作。sqDistances = sqDiffMat.sum(axis=1) #把每行的兩個值相加distances = sqDistances**0.5 #再把相加的值開方，就算出了距離sortedDistIndicies = distances.argsort() #然后再從小到大排序，并記下相應的下標。classCount={}for i in range(k):#這里是字典相關的操作，即統計'A','B'的次數（前3名中），其中'A','B’為key,次數為value。voteIlabel = labels[sortedDistIndicies[i]]classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1 #這種都是字典操作，先從字典中取出'A'的次數，然后加1，再賦值給'A'對應的值。#上述代碼結束后，classCount字典的值為：{'B': 2, 'A': 1}sortedClassCount = sorted(iter(classCount.items()), key=op.itemgetter(1), reverse=True)#sorted可對迭代類型排序#operator是python的一個模塊，其中itemgetter函數可以獲得對象不同維度的數據，參數為維度的索引值#比如[('B', 2), ('A', 1)]，那么op.itemgetter(1)就是以第2維來排序，即以后面的數字來排序。#reverse是否反轉，默認排序結果是從小到大，這里想要的是從大到小。return sortedClassCount[0][0]#這里取第0行第0列。

測試分類算法的正確性

上一步已經實現了算法的核心功能。其實在這分類算法出來之前，應該對分類算法做一個測試，看其正確率有多少。

#用來測試分類算法的正確性 def datingClassTest():hoRatio = 0.10 #預留的數據百分比用來測試分類器。datingDataMat,datingLabels = file2matrix('datingTestSet2.txt') normMat, ranges, minVals = autoNorm(datingDataMat)m = normMat.shape[0] #算出0維大小，一共1000條numTestVecs = int(m*hoRatio) #預留數據的后面數據用來訓練樣本，這里算這些數據的起始位置。預留數據用來和這些訓練樣本比較，計算距離。errorCount = 0.0for i in range(numTestVecs):classifierResult = classify0(normMat[i,:],normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],3)#classifierResult是使用分類器測出來的結果，拿此結果和真實結果（datingLabels[i]）對比，如果一樣表示預測正確。#normMat[i,:]，表示norMat的第i行，第i取所有（：冒號表示所有），具體可看my_4_1_intro.py二維數組切片。#normMat[numTestVecs:m,:]表示從訓練數據位置numTestVecs開始到最后一條數據m為止。print("the classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i]))if (classifierResult != datingLabels[i]): errorCount += 1.0 #統計錯誤數。print("the total error rate is: %f" % (errorCount/float(numTestVecs))) #統計錯誤率。print(errorCount)

運行結果如下圖所示，可知錯誤率為5%，可以調整預留數據hoRatio的比例再試錯誤率。

如何畫圖直觀展示數據

這里展示的程序沒對數據做歸一化處理，展示的時候只取飛行公里數和玩游戲時間，即datingDataMat第0列和第1列數據。當然也可取其它組合試試，但是分類效果不好。

#從文本文件中解析數據，并使用Matplotlib畫圖展示。 def file2matrix_test():#2.2.1節代碼，從文本文件中解析數據。datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')print(datingDataMat) #數據前三列的矩陣print(datingLabels) #第四列值存放在list中。#2.2.2使用Matplotlib創建散點圖。fig = plt.figure()ax = fig.add_subplot(111)num_show=0#需要從矩陣的第幾行數據開始展示，0為展示所有ax.scatter(datingDataMat[num_show:,0], datingDataMat[num_show:,1], 15.0*np.array(datingLabels[num_show:]), 15.0*np.array(datingLabels[num_show:]))#用datingLabels類型標注不同的顏色，scatter的具體用法再學。plt.show()#這里還有一個小問題沒有解決，就是顯示在圖上的顏色沒有標注到底是屬于哪一類的，這個可在后續學Matplotlib時再完善。

運行結果：

完整代碼

以下代碼是本實例完成代碼，使用python3.6可直接運行，當然需要安裝相應的庫了，不會的話可上網找下。

#coding:utf-8 #autho:pan_limin #date:2018.1.22 #python3.6 #說明：本程序參考《機器學習實踐》第2章KNN相關教程，源碼幾乎是一樣的，主要加入自己的一些學習備注。import numpy as np #這里和書上導入的方式不太一樣，使用我這種方式更容易理解。 import operator as opimport matplotlib import matplotlib.pyplot as plt#classify0的作用： #給定一個輸入List inX，可以是n維，這個inX一般存放待分類的條目的屬性值，然后和已知數據集（因為是已知的，所以標簽類別也是已知的）相比（通過兩點差的平方和再開根號），和哪幾個近就屬于哪類。 #輸出即是該條目的類別。#這個分類函數是支持多維的，而該函數里的注釋是基于2維寫的。 #2維情況的輸入值： #inX=[0, 0] #dataSet= # [[ 1. 1.1] # [ 1. 1. ] # [ 0. 0. ] # [ 0. 0.1]] #labels=['A', 'A', 'B', 'B'] #k=3 表示只取最近的3個做比較， #輸出A或B。 def classify0(inX, dataSet, labels, k):dataSetSize = dataSet.shape[0] #計算dataSet有多少行，這里的0維指x行diffMat = np.tile(inX, (dataSetSize,1)) - dataSet#生成和dataSet一樣大小的數組，其每行的成員(x,y)都是inX的x,y減dataSet對應行的x,y。sqDiffMat = diffMat**2 #對每個成員做平方操作。sqDistances = sqDiffMat.sum(axis=1) #把每行的兩個值相加distances = sqDistances**0.5 #再把相加的值開方，就算出了距離sortedDistIndicies = distances.argsort() #然后再從小到大排序，并記下相應的下標。classCount={}for i in range(k):#這里是字典相關的操作，即統計'A','B'的次數（前3名中），其中'A','B’為key,次數為value。voteIlabel = labels[sortedDistIndicies[i]]classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1 #這種都是字典操作，先從字典中取出'A'的次數，然后加1，再賦值給'A'對應的值。#上述代碼結束后，classCount字典的值為：{'B': 2, 'A': 1}sortedClassCount = sorted(iter(classCount.items()), key=op.itemgetter(1), reverse=True)#sorted可對迭代類型排序#operator是python的一個模塊，其中itemgetter函數可以獲得對象不同維度的數據，參數為維度的索引值#比如[('B', 2), ('A', 1)]，那么op.itemgetter(1)就是以第2維來排序，即以后面的數字來排序。#reverse是否反轉，默認排序結果是從小到大，這里想要的是從大到小。return sortedClassCount[0][0]#這里取第0行第0列。def createDataSet():group = np.array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])# print(group)lables = ['A', 'A', 'B', 'B']return group, lablesdef createDataSet_test():group, labels = createDataSet()#2.1.1導入數據到ndarray中。result = classify0([0,0], group, labels, 3)#2.1.2 實現分類算法，并給定一個條目，判斷此條目屬于哪類。print(result)#為了理解以上內容，做的單獨測試，和正式代碼沒有任何關系。 def createDataSet_temp_test():inX = [0,0]k=3group, labels = createDataSet()print(group)dataSetSize = group.shape[0]#group 0維方向大小，group因為是4行3列，0維的值即為4.print(group.shape[0]) #4dataSet = groupprint(np.tile(inX, (4,1))) #tile表示在給定的數組，在行方向重復4次，列方向重復1次。diffMat = np.tile(inX, (dataSetSize,1)) - dataSetprint(diffMat)sqDiffMat = diffMat**2print(sqDiffMat)sqDistances=sqDiffMat.sum(axis=1)print(sqDistances)distances = sqDistances**0.5print(distances)sortedDistIndicies = distances.argsort()print(sortedDistIndicies)classCount={}# aa = 'B'# print(classCount.get('B',0))for i in range(k):#voteIlabel = labels[sortedDistIndicies[i]]classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1print(classCount)#classCount字典的值為：{'B': 2, 'A': 1}print(iter(classCount.items()))for item in iter(classCount.items()):print(item)sortedClassCount = sorted(iter(classCount.items()), key=op.itemgetter(1), reverse=True)#sorted可對迭代類型排序#operator是python的一個模塊，其中itemgetter函數可以獲得對象不同維度的數據，參數為維度的索引值#比如[('B', 2), ('A', 1)]，那么op.itemgetter(1)就是以第2維來排序，即以后面的數字來排序。#reverse是否反轉，默認排序結果是從小到大，這里想要的是從大到小。print(sortedClassCount)#從文件中獲取數據，并格式化成Numpy數組。 #returnMat[]數組用于存放樣本的屬性。 #classLabelVector[]用于存放樣本的類別 def file2matrix(filename):fr = open(filename)numberOfLines = len(fr.readlines()) #1000returnMat = np.zeros((numberOfLines,3)) #創建numberOfLines行，3列矩陣，初始化為0.classLabelVector = [] #用于存放第四列的的值。fr = open(filename)index = 0for line in fr.readlines():line = line.strip()listFromLine = line.split('\t')returnMat[index,:] = listFromLine[0:3] #因為index是會自增的，所以數據會往returnMat上增。classLabelVector.append(int(listFromLine[-1]))index += 1return returnMat,classLabelVector # returnMat={ndarray} [[ 4.09200000e+04 8.32697600e+00 9.53952000e-01] # [ 1.44880000e+04 7.15346900e+00 1.67390400e+00] # [ 2.60520000e+04 1.44187100e+00 8.05124000e-01] # ..., # [ 2.65750000e+04 1.06501020e+01 8.66627000e-01] # [ 4.81110000e+04 9.13452800e+00 7.28045000e-01] # [ 4.37570000e+04 7.88260100e+00 1.33244600e+00]] #classLabelVector={list}[3, 2, 1, 1, 1, 1, 3, 3, 1, 3, 1, 1, 2, 1, 1,……]#歸一化處理公式：newValue=(oldValue-min)/(max-min) def autoNorm(dataSet):#dataSet是1000行3列的數據。minVals = dataSet.min(0)maxVals = dataSet.max(0)ranges = maxVals - minValsnormDataSet = np.zeros(np.shape(dataSet))#shape取ndarray dataSet的大小（維度），然后創建一個一樣大小的ndarray,并以0初始化。m = dataSet.shape[0]#取0維大小，1000行。normDataSet = dataSet - np.tile(minVals, (m,1))#做(oldValue-min)操作normDataSet = normDataSet/np.tile(ranges, (m,1)) #element wise dividereturn normDataSet, ranges, minVals # normDataSet={ndarray}[[ 0.44832535 0.39805139 0.56233353] # [ 0.15873259 0.34195467 0.98724416] # [ 0.28542943 0.06892523 0.47449629] # ..., # [ 0.29115949 0.50910294 0.51079493] # [ 0.52711097 0.43665451 0.4290048 ] # [ 0.47940793 0.3768091 0.78571804]]# ranges={ndarray}[ 9.12730000e+04 2.09193490e+01 1.69436100e+00] # minVals={ndarray}[ 0. 0. 0.001156]#從文本文件中解析數據，并使用Matplotlib畫圖展示。 def file2matrix_test():#2.2.1節代碼，從文本文件中解析數據。datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')print(datingDataMat) #數據前三列的矩陣print(datingLabels) #第四列值存放在list中。#2.2.2使用Matplotlib創建散點圖。fig = plt.figure()ax = fig.add_subplot(111)num_show=0#需要從矩陣的第幾行數據開始展示，0為展示所有ax.scatter(datingDataMat[num_show:,0], datingDataMat[num_show:,1], 15.0*np.array(datingLabels[num_show:]), 15.0*np.array(datingLabels[num_show:]))#用datingLabels類型標注不同的顏色，scatter的具體用法再學。plt.show()#這里還有一個小問題沒有解決，就是顯示在圖上的顏色沒有標注到底是屬于哪一類的，這個可在后續學Matplotlib時再完善。#歸一化處理,因為有一項屬性數據太大，這樣在算距離時其它屬性就不起作用了，但是其它屬性也是一樣重要的，需要要做歸一化處理。 def autoNorm_test():datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')normMat, ranges, minVals = autoNorm(datingDataMat)print(normMat,'\n', ranges,'\n',minVals,'\n')#用來測試分類算法的正確性 def datingClassTest():hoRatio = 0.10 #預留的數據用來測試分類器。datingDataMat,datingLabels = file2matrix('datingTestSet2.txt') #load data setfrom filenormMat, ranges, minVals = autoNorm(datingDataMat)m = normMat.shape[0] #算出0維大小，一共1000條numTestVecs = int(m*hoRatio) #預留數據的后面數據用來訓練樣本。預留數據用來和這些訓練樣本比較，計算距離。errorCount = 0.0for i in range(numTestVecs):classifierResult = classify0(normMat[i,:],normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],3)#classifierResult是使用分類器測出來的結果，拿此結果和真實結果（datingLabels[i]）對比，如果一樣表示預測正確。#normMat[i,:]，表示norMat的第i行，第i取所有（：冒號表示所有），具體可看my_4_1_intro.py二維數組切片。#normMat[numTestVecs:m,:]表示從訓練數據位置numTestVecs開始到最后一條數據m為止print("the classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i]))if (classifierResult != datingLabels[i]): errorCount += 1.0 #統計錯誤數。print("the total error rate is: %f" % (errorCount/float(numTestVecs))) #統計錯誤率。print(errorCount)#這個代碼在原書自帶的源碼中沒找到，自己敲一遍吧。 def classifyPerson():resultList = ['沒有魅力', '魅力一般', '極具魅力']ffMiles = float(input("每年飛行公里數？"))percentTats=float(input("打游戲耗費時間的百分比？"))iceCream = float(input("每周消費的冰激凌?"))datingDataMat, datingLabels = file2matrix('datingTestSet2.txt')normMat, ranges, minVals = autoNorm(datingDataMat)inArr = np.array([ffMiles,percentTats,iceCream])classifierResult = classify0((inArr-minVals)/ranges, normMat, datingLabels, 3)print("這個人：", resultList[classifierResult-1])if __name__ == '__main__':#1、2.1節代碼# createDataSet_test()#用于學習k近領核心算法classify0()# createDataSet_temp_test()#2、演示2.2.1和2.2.2。 2.2.1從文本文件中解析數據，2.2.2使用Matplotlib創建散點圖。file2matrix_test()#3、測試2.2.3# autoNorm_test()#4、測試2.2.4節#有了以上知識做鋪墊后，現在開始測試算法。測試算法# datingClassTest()#5、2.2.5完整可用系統。輸入一個條目屬性特征，返回這個人屬于哪類。# classifyPerson()

如有疑問之處歡迎加我微信交流，共同進步！請備注“CSDN博客”

總結

以上是生活随笔為你收集整理的机器学习笔记(3)---K-近邻算法(1)---约会对象魅力程度分类的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。