1、基本概念
K近鄰法(K-nearest neighbors,KNN)既可以分類，也可以回歸，
KNN做回歸和分類的區別在于最后預測時的決策方式，
KNN做分類時，一般用多數表決法: 采用車輛不同特征值之間的距離方法進行分類
KNN做回歸時，一般用平均法，
基本概念如下：存在一個樣本資料集合，所有特征屬性已知，并且樣本集中每個物件都已知所屬分類，對不知道分類的待測物件，將待測物件的每個特征屬性與樣本集中資料對應的特征屬性進行比較，然后演算法提取樣本最相似物件(最近鄰)的分類標簽，一般來說，我們只選擇樣本資料集中前k個最相似的物件資料，這就是k-近鄰演算法中k的出處，通常k是不大于20的整數，最后根據這k個資料的特征和屬性，判斷待測資料的分類
2. KNN演算法三要素
KNN演算法主要考慮：k值的選取，距離度量方式，分類決策規則，
1） k值的選取，在應用中，k值一般選擇一個比較小的值，一般選用交叉驗證來取最優的k值
當K值較小，訓練誤差減小，泛化誤差增大，模型復雜容易過擬合；
當K值較大，泛化誤差減小，訓練誤差增大，模型簡單使預測發生錯誤（一個極端，K等于樣本數m，則完全沒有分類，此時無論測驗集是什么，結果都屬于訓練集中最多的類）
2）距離度量，Lp距離：誤差絕對值p次方求和再求p次根，歐式距離：p=2的Lp距離，曼哈頓距離：p=1的Lp距離，p為無窮大時，Lp距離為各個維度上距離的最大值
3）分類決策規則，也就是如何根據k個最近鄰決定待測物件的分類，k最近鄰的分類決策規則一般選用多數表決
3. KNN基本執行步驟
1）計算待測物件和訓練集中每個樣本點的歐式距離 2）對上面的所有距離值排序 3）選出k個最小距離的樣本作為“選民” 4）根據“選民”預測待測樣本的分類或值4. KNN特點
1）原理簡單 2）保存模型需要保存所有樣本集 3）訓練程序很快，預測速度很慢 · 優點： 簡單好用，容易理解，精度高，理論成熟，既可以用來做分類也可以用來做回歸； 可用于非線性分類； 可用于數值型資料和離散型資料（既可以用來估值，又可以用來分類） 訓練時間復雜度為O(n)；無資料輸入假定； 對例外值不敏感， 準確度高，對資料沒有假設，對outlier不敏感； · 缺點： 計算復雜性高；空間復雜性高；需要大量的記憶體 樣本不平衡問題（即有些類別的樣本數量很多，而其它樣本的數量很少）； 一般數值很大的時候不用這個，計算量太大，但是單個樣本又不能太少，否則容易發生誤分， 最大的缺點是無法給出資料的內在含義， 需要思考的問題： 樣本屬性如何選擇？如何計算兩個物件間距離？當樣本各屬性的型別和尺度不同時如何處理？各屬性不同重要程度如何處理？模型的好壞如何評估？5.代碼實作
K近鄰演算法的一般流程：收集資料- 準備資料- 分析資料- 測驗演算法- 使用演算法5.1 python3代碼實作
5.1.1 首先以電影分類為例，了解kNN作業流程，主要包括創建資料，迭代計算兩點公式，代碼如下
# -*- coding: UTF-8 -*- import numpy as np import operator import collections """ 函式說明:創建資料集 Parameters: 無 Returns: group - 資料集 labels - 分類標簽 """ def createDataSet(): #四組二維特征 group = np.array([[1,101],[5,89],[108,5],[115,8]]) #四組特征的標簽 labels = ['愛情片','愛情片','動作片','動作片'] return group, labels """ 函式說明:kNN演算法,分類器 Parameters: inX - 用于分類的資料(測驗集) dataSet - 用于訓練的資料(訓練集) labes - 分類標簽 k - kNN演算法引數,選擇距離最小的k個點 Returns: sortedClassCount[0][0] - 分類結果 """ def classify0(inx, dataset, labels, k): # 計算距離 dist = np.sum((inx - dataset)**2, axis=1)**0.5 # k個最近的標簽 k_labels = [labels[index] for index in dist.argsort()[0 : k]] # 出現次數最多的標簽即為最終類別 label = collections.Counter(k_labels).most_common(1)[0][0] return label if __name__ == '__main__': #創建資料集 group, labels = createDataSet() #測驗集 test = [101,20] #kNN分類 test_class = classify0(test, group, labels, 3) #列印分類結果 print(test_class)View Code 5.1.2 以K近鄰演算法實作約會網站配對效果判定， 1）下載資料集 datingTestSet.txt 2）準備資料：資料決議 將資料分為特征矩陣和對應的分類標簽矩陣，
# -*- coding: UTF-8 -*- import numpy as np """ 函式說明:打開并決議檔案，對資料進行分類：1代表不喜歡,2代表魅力一般,3代表極具魅力 Parameters: filename - 檔案名 Returns: returnMat - 特征矩陣 classLabelVector - 分類Label向量 """ def file2matrix(filename): #打開檔案 fr = open(filename) #讀取檔案所有內容 arrayOLines = fr.readlines() #得到檔案行數 numberOfLines = len(arrayOLines) #回傳的NumPy矩陣,決議完成的資料:numberOfLines行,3列 returnMat = np.zeros((numberOfLines,3)) #回傳的分類標簽向量 classLabelVector = [] #行的索引值 index = 0 for line in arrayOLines: #s.strip(rm)，當rm空時,默認洗掉空白符(包括'\n','\r','\t',' ') line = line.strip() #使用s.split(str="",num=string,cout(str))將字串根據'\t'分隔符進行切片， listFromLine = line.split('\t') #將資料前三列提取出來,存放到returnMat的NumPy矩陣中,也就是特征矩陣 returnMat[index,:] = listFromLine[0:3] #根據文本中標記的喜歡的程度進行分類,1代表不喜歡,2代表魅力一般,3代表極具魅力 if listFromLine[-1] == 'didntLike': classLabelVector.append(1) elif listFromLine[-1] == 'smallDoses': classLabelVector.append(2) elif listFromLine[-1] == 'largeDoses': classLabelVector.append(3) index += 1 return returnMat, classLabelVector """ 函式說明:main函式 Parameters: 無 Returns: 無 """ if __name__ == '__main__': #打開的檔案名 filename = "datingTestSet.txt" #打開并處理資料 datingDataMat, datingLabels = file2matrix(filename) print(datingDataMat) print(datingLabels)View Code 3）分析資料：資料可視化 直觀的發現資料的規律
""" 函式說明:可視化資料 Parameters: datingDataMat - 特征矩陣 datingLabels - 分類Label Returns: 無 """ def showdatas(datingDataMat, datingLabels): #設定漢字格式 font = FontProperties(fname=r"c:\windows\fonts\simsun.ttc", size=14) #將fig畫布分隔成1行1列,不共享x軸和y軸,fig畫布的大小為(13,8) #當nrow=2,nclos=2時,代表fig畫布被分為四個區域,axs[0][0]表示第一行第一個區域 fig, axs = plt.subplots(nrows=2, ncols=2,sharex=False, sharey=False, figsize=(13,8)) numberOfLabels = len(datingLabels) LabelsColors = [] for i in datingLabels: if i == 1: LabelsColors.append('black') if i == 2: LabelsColors.append('orange') if i == 3: LabelsColors.append('red') #畫出散點圖,以datingDataMat矩陣的第一(飛行常客例程)、第二列(玩游戲)資料畫散點資料,散點大小為15,透明度為0.5 axs[0][0].scatter(x=datingDataMat[:,0], y=datingDataMat[:,1], color=LabelsColors,s=15, alpha=.5) #設定標題,x軸label,y軸label axs0_title_text = axs[0][0].set_title(u'每年獲得的飛行常客里程數與玩視頻游戲所消耗時間占比',FontProperties=font) axs0_xlabel_text = axs[0][0].set_xlabel(u'每年獲得的飛行常客里程數',FontProperties=font) axs0_ylabel_text = axs[0][0].set_ylabel(u'玩視頻游戲所消耗時間占',FontProperties=font) plt.setp(axs0_title_text, size=9, weight='bold', color='red') plt.setp(axs0_xlabel_text, size=7, weight='bold', color='black') plt.setp(axs0_ylabel_text, size=7, weight='bold', color='black') #畫出散點圖,以datingDataMat矩陣的第一(飛行常客例程)、第三列(冰激凌)資料畫散點資料,散點大小為15,透明度為0.5 axs[0][1].scatter(x=datingDataMat[:,0], y=datingDataMat[:,2], color=LabelsColors,s=15, alpha=.5) #設定標題,x軸label,y軸label axs1_title_text = axs[0][1].set_title(u'每年獲得的飛行常客里程數與每周消費的冰激淋公升數',FontProperties=font) axs1_xlabel_text = axs[0][1].set_xlabel(u'每年獲得的飛行常客里程數',FontProperties=font) axs1_ylabel_text = axs[0][1].set_ylabel(u'每周消費的冰激淋公升數',FontProperties=font) plt.setp(axs1_title_text, size=9, weight='bold', color='red') plt.setp(axs1_xlabel_text, size=7, weight='bold', color='black') plt.setp(axs1_ylabel_text, size=7, weight='bold', color='black') #畫出散點圖,以datingDataMat矩陣的第二(玩游戲)、第三列(冰激凌)資料畫散點資料,散點大小為15,透明度為0.5 axs[1][0].scatter(x=datingDataMat[:,1], y=datingDataMat[:,2], color=LabelsColors,s=15, alpha=.5) #設定標題,x軸label,y軸label axs2_title_text = axs[1][0].set_title(u'玩視頻游戲所消耗時間占比與每周消費的冰激淋公升數',FontProperties=font) axs2_xlabel_text = axs[1][0].set_xlabel(u'玩視頻游戲所消耗時間占比',FontProperties=font) axs2_ylabel_text = axs[1][0].set_ylabel(u'每周消費的冰激淋公升數',FontProperties=font) plt.setp(axs2_title_text, size=9, weight='bold', color='red') plt.setp(axs2_xlabel_text, size=7, weight='bold', color='black') plt.setp(axs2_ylabel_text, size=7, weight='bold', color='black') #設定圖例 didntLike = mlines.Line2D([], [], color='black', marker='.', markersize=6, label='didntLike') smallDoses = mlines.Line2D([], [], color='orange', marker='.', markersize=6, label='smallDoses') largeDoses = mlines.Line2D([], [], color='red', marker='.', markersize=6, label='largeDoses') #添加圖例 axs[0][0].legend(handles=[didntLike,smallDoses,largeDoses]) axs[0][1].legend(handles=[didntLike,smallDoses,largeDoses]) axs[1][0].legend(handles=[didntLike,smallDoses,largeDoses]) #顯示圖片 plt.show()View Code 4）資料準備：資料歸一化 使用autoNorm函式自動將資料歸一化
""" 函式說明:對資料進行歸一化 Parameters: dataSet - 特征矩陣 Returns: normDataSet - 歸一化后的特征矩陣 ranges - 資料范圍 minVals - 資料最小值 """ def autoNorm(dataSet): #獲得資料的最小值 minVals = dataSet.min(0) maxVals = dataSet.max(0) #最大值和最小值的范圍 ranges = maxVals - minVals #shape(dataSet)回傳dataSet的矩陣行列數 normDataSet = np.zeros(np.shape(dataSet)) #回傳dataSet的行數 m = dataSet.shape[0] #原始值減去最小值 normDataSet = dataSet - np.tile(minVals, (m, 1)) #除以最大和最小值的差,得到歸一化資料 normDataSet = normDataSet / np.tile(ranges, (m, 1)) #回傳歸一化資料結果,資料范圍,最小值 return normDataSet, ranges, minValsView Code 5）構建、驗證分類器 將資料分為90%樣本集和10%的測驗機（可以調整）
# -*- coding: UTF-8 -*- import numpy as np import operator """ 函式說明:kNN演算法,分類器 Parameters: inX - 用于分類的資料(測驗集) dataSet - 用于訓練的資料(訓練集) labes - 分類標簽 k - kNN演算法引數,選擇距離最小的k個點 Returns: sortedClassCount[0][0] - 分類結果 """ def classify0(inX, dataSet, labels, k): #numpy函式shape[0]回傳dataSet的行數 dataSetSize = dataSet.shape[0] #在列向量方向上重復inX共1次(橫向),行向量方向上重復inX共dataSetSize次(縱向) diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet #二維特征相減后平方 sqDiffMat = diffMat**2 #sum()所有元素相加,sum(0)列相加,sum(1)行相加 sqDistances = sqDiffMat.sum(axis=1) #開方,計算出距離 distances = sqDistances**0.5 #回傳distances中元素從小到大排序后的索引值 sortedDistIndices = distances.argsort() #定一個記錄類別次數的字典 classCount = {} for i in range(k): #取出前k個元素的類別 voteIlabel = labels[sortedDistIndices[i]] #dict.get(key,default=None),字典的get()方法,回傳指定鍵的值,如果值不在字典中回傳默認值， #計算類別次數 classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1 #python3中用items()替換python2中的iteritems() #key=operator.itemgetter(1)根據字典的值進行排序 #key=operator.itemgetter(0)根據字典的鍵進行排序 #reverse降序排序字典 sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True) #回傳次數最多的類別,即所要分類的類別 return sortedClassCount[0][0] """ 函式說明:分類器測驗函式 Parameters: 無 Returns: normDataSet - 歸一化后的特征矩陣 ranges - 資料范圍 minVals - 資料最小值 """ def datingClassTest(): #打開的檔案名 filename = "datingTestSet.txt" #將回傳的特征矩陣和分類向量分別存盤到datingDataMat和datingLabels中 datingDataMat, datingLabels = file2matrix(filename) #取所有資料的百分之十 hoRatio = 0.10 #資料歸一化,回傳歸一化后的矩陣,資料范圍,資料最小值 normMat, ranges, minVals = autoNorm(datingDataMat) #獲得normMat的行數 m = normMat.shape[0] #百分之十的測驗資料的個數 numTestVecs = int(m * hoRatio) #分類錯誤計數 errorCount = 0.0 for i in range(numTestVecs): #前numTestVecs個資料作為測驗集,后m-numTestVecs個資料作為訓練集 classifierResult = classify0(normMat[i,:], normMat[numTestVecs:m,:], datingLabels[numTestVecs:m], 4) print("分類結果:%d\t真實類別:%d" % (classifierResult, datingLabels[i])) if classifierResult != datingLabels[i]: errorCount += 1.0 print("錯誤率:%f%%" %(errorCount/float(numTestVecs)*100))View Code 6）使用演算法：構建完整可用系統
""" 函式說明:通過輸入一個人的三維特征,進行分類輸出 Parameters: 無 Returns: 無 """ def classifyPerson(): #輸出結果 resultList = ['討厭','有些喜歡','非常喜歡'] #三維特征用戶輸入 precentTats = float(input("玩視頻游戲所耗時間百分比:")) ffMiles = float(input("每年獲得的飛行常客里程數:")) iceCream = float(input("每周消費的冰激淋公升數:")) #打開的檔案名 filename = "datingTestSet.txt" #打開并處理資料 datingDataMat, datingLabels = file2matrix(filename) #訓練集歸一化 normMat, ranges, minVals = autoNorm(datingDataMat) #生成NumPy陣列,測驗集 inArr = np.array([ffMiles, precentTats, iceCream]) #測驗集歸一化 norminArr = (inArr - minVals) / ranges #回傳分類結果 classifierResult = classify0(norminArr, normMat, datingLabels, 3) #列印結果 print("你可能%s這個人" % (resultList[classifierResult-1]))View Code 在cmd中，運行程式，并輸入資料(12,44000,0.5)，預測結果是"你可能有些喜歡這個人"，也就是這個人魅力一般，一共有三個檔次：討厭、有些喜歡、非常喜歡，對應著不喜歡的人、魅力一般的人、極具魅力的人， 本部分完整代碼請見：
5.2 sklearn包實作
關于sklearn的詳細介紹，請見之前的博客 https://www.cnblogs.com/aitree/p/14331551.html5.2.1
sklearn實作k-近鄰演算法簡介 官方檔案5.2.2 KNeighborsClassifier函式8個引數
- n_neighbors：k值，選取最近的k個點，默認為5， - weights：默認是uniform，引數可以是uniform（均等權重）、distance（按距離分配權重），也可以是用戶自己定義的函式，uniform是均等的權重，就說所有的鄰近點的權重都是相等的， - algorithm：快速k近鄰搜索演算法，默認引數為auto，除此之外，用戶也可以自己指定搜索演算法ball_tree、kd_tree、brute方法進行搜索， - leaf_size：默認是30，這個是構造的kd樹和ball樹的大小，這個值的設定會影響樹構建的速度和搜索速度，同樣也影響著存盤樹所需的記憶體大小，需要根據問題的性質選擇最優的大小， - metric：用于距離度量，默認度量是minkowski，也就是p=2的歐氏距離(歐幾里德度量)， - p：距離度量公式，歐氏距離和曼哈頓距離，這個引數默認為2，也可以設定為1， - metric_params：距離公式的其他關鍵引數，這個可以不管，使用默認的None即可， - n_jobs：并行處理設定，默認為1，臨近點搜索并行作業數，如果為-1，那么CPU的所有cores都用于并行作業，5.2.3 實體
基于sklearn實作手寫數字識別系統
# -*- coding: UTF-8 -*- import numpy as np import operator from os import listdir from sklearn.neighbors import KNeighborsClassifier as kNN """ 函式說明:將32x32的二進制影像轉換為1x1024向量， Parameters: filename - 檔案名 Returns: returnVect - 回傳的二進制影像的1x1024向量 """ def img2vector(filename): #創建1x1024零向量 returnVect = np.zeros((1, 1024)) #打開檔案 fr = open(filename) #按行讀取 for i in range(32): #讀一行資料 lineStr = fr.readline() #每一行的前32個元素依次添加到returnVect中 for j in range(32): returnVect[0, 32*i+j] = int(lineStr[j]) #回傳轉換后的1x1024向量 return returnVect """ 函式說明:手寫數字分類測驗 Parameters: 無 Returns: 無 """ def handwritingClassTest(): #測驗集的Labels hwLabels = [] #回傳trainingDigits目錄下的檔案名 trainingFileList = listdir('trainingDigits') #回傳檔案夾下檔案的個數 m = len(trainingFileList) #初始化訓練的Mat矩陣,測驗集 trainingMat = np.zeros((m, 1024)) #從檔案名中決議出訓練集的類別 for i in range(m): #獲得檔案的名字 fileNameStr = trainingFileList[i] #獲得分類的數字 classNumber = int(fileNameStr.split('_')[0]) #將獲得的類別添加到hwLabels中 hwLabels.append(classNumber) #將每一個檔案的1x1024資料存盤到trainingMat矩陣中 trainingMat[i,:] = img2vector('trainingDigits/%s' % (fileNameStr)) #構建kNN分類器 neigh = kNN(n_neighbors = 3, algorithm = 'auto') #擬合模型, trainingMat為訓練矩陣,hwLabels為對應的標簽 neigh.fit(trainingMat, hwLabels) #回傳testDigits目錄下的檔案串列 testFileList = listdir('testDigits') #錯誤檢測計數 errorCount = 0.0 #測驗資料的數量 mTest = len(testFileList) #從檔案中決議出測驗集的類別并進行分類測驗 for i in range(mTest): #獲得檔案的名字 fileNameStr = testFileList[i] #獲得分類的數字 classNumber = int(fileNameStr.split('_')[0]) #獲得測驗集的1x1024向量,用于訓練 vectorUnderTest = img2vector('testDigits/%s' % (fileNameStr)) #獲得預測結果 # classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3) classifierResult = neigh.predict(vectorUnderTest) print("分類回傳結果為%d\t真實結果為%d" % (classifierResult, classNumber)) if(classifierResult != classNumber): errorCount += 1.0 print("總共錯了%d個資料\n錯誤率為%f%%" % (errorCount, errorCount/mTest * 100)) """ 函式說明:main函式 Parameters: 無 Returns: 無 """ if __name__ == '__main__': handwritingClassTest()View Code 可以嘗試更改這些引數的設定，加深對其函式的理解， 參考： https://blog.csdn.net/luanpeng825485697/article/details/78796773 http://cuijiahua.com/blog/2017/11/ml_1_knn.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/252905.html
標籤：Python
下一篇：Python爬蟲學習筆記(二)