資訊專欄INFORMATION COLUMN
摘要：背景近鄰算法的概述近鄰算法的簡介近鄰算法是屬于一個非常有效且易于掌握的機器學習算法，簡單的說就是采用測量不同特征值之間距離的方法對數據進行分類的一個算法。完美的分類器的錯誤率為，而最差的分類器的錯誤率則為。
（1）k近鄰算法的簡介
k-近鄰算法是屬于一個非常有效且易于掌握的機器學習算法，簡單的說就是采用測量不同特征值之間距離的方法對數據進行分類的一個算法。
（2）k近鄰算法的工作原理
給定一個樣本的集合，這里稱為訓練集，并且樣本中每個數據都包含標簽。對于新輸入的一個不包含標簽的數據，通過計算這個新的數據與每一個樣本之間的距離，選取前k個，通常k小于20，以k個劇里最近的數據的標簽中出現次數最多的標簽作為該新加入的數據標簽。
（3）k近鄰算法的案例
當前統計了6部電影的接吻和打斗的鏡頭數，假設有一部未看過的電影，如何確定它是愛情片還是動作片呢？
| 電影名稱 | 打斗鏡頭 | 接吻鏡頭 | 電影類型 |
| California Man | 3 | 104 | 愛情片 |
| He‘s Not Really into Dudes | 2 | 100 | 愛情片 |
| Beautiful Woman | 1 | 81 | 愛情片 |
| Kevin Longblade | 101 | 10 | 動作片 |
| Robo Slayer 3000 | 99 | 5 | 動作片 |
| Amped II | 98 | 2 | 動作片 |
| ？ | 18 | 90 | 未知 |
根據knn算法的原理，我們可以求出，未知電影與每部電影之間的距離(這里采用歐式距離）
以California Man為例
>>>((3-18)**2+(104-90)**2)**(1/2)20.518284528683193| 電影名稱 | 與未知i電影之間的距離 |
| California Man | 20.5 |
| He‘s Not Really into Dudes | 18.7 |
| Beautiful Woman | 19.2 |
| Kevin Longblade | 115.3 |
| Robo Slayer 3000 | 117.4 |
| Amped II | 118.9 |
因此我們可以找到樣本中前k個距離最近的電影，假設k=3，前三部電影均為愛情片，因此我們判定未知電影屬于愛情片。
（1）計算已知類別數據集中的每個點與當前點之間的距離
（2）按照距離遞增次序排序
（3）選取與當前點距離最小的k個點
（4）確定前k個點所在類別出現的頻率
（5）返回前k個點出現頻率最高的類別作為當前點的預測分類
import numpy as npimport operatordef classify0(inX, dataSet, labels, k): dataSetSize = dataSet.shape[0] diffMat = np.tile(inX, (dataSetSize,1)) - dataSet sqDiffMat = diffMat**2 sqDistances = sqDiffMat.sum(axis=1) distances = sqDistances**0.5 sortedDistIndicies = distances.argsort() classCount={} for i in range(k): voteIlabel = labels[sortedDistIndicies[i]] classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1 sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True) return sortedClassCount[0][0]（6）案例
>>>group = np.array([[1, 1.1],... [1, 1],... [0, 0],... [0, 0.1]])>>>labels = ["A", "A", "B", "B"]>>>classify0([0,0], group, labels, 3)"B"正常來說為了測試分類器給出來的分類效果，我們通常采用計算分類器的錯誤率對分類器的效果進行評判。也就是采用分類出錯的次數除以分類的總次數。完美的分類器的錯誤率為0，而最差的分類器的錯誤率則為1。
朋友海倫在使用約會軟件尋找約會對象的時候，盡管網站會推薦不同的人選，但并不是每一個人她都喜歡，具體可以分為以下三類：不喜歡的人，魅力一般的人，極具魅力的人。盡管發現了以上的規律，但是海倫依舊無法將網站推薦的人歸到恰當的類別，因此海倫希望我們的分類軟件能更好的幫助她將匹配到的對象分配到確切的分類中。
以下提供兩種下載數據集的渠道：
數據存放在datingTestSet2.txt中，每個樣本占一行，共1000行數據，主要包括了以下三個特征：
每年獲得的飛行常客里程數，玩視頻游戲所耗時間百分比，每周消費冰淇淋公升數
在數據輸入到分類器之前，需要把數據轉換成分類器可以識別的樣式
def file2matrix(filename): fr = open(filename) numberOfLines = len(fr.readlines()) #get the number of lines in the file returnMat = np.zeros((numberOfLines,3)) #prepare matrix to return classLabelVector = [] #prepare labels return fr = open(filename) index = 0 for line in fr.readlines(): line = line.strip() listFromLine = line.split("/t") returnMat[index,:] = listFromLine[0:3] classLabelVector.append(int(listFromLine[-1])) index += 1 return returnMat,classLabelVector使用file2matix讀取到的特征數據(datingDataMat)如下
array([[4.0920000e+04, 8.3269760e+00, 9.5395200e-01], [1.4488000e+04, 7.1534690e+00, 1.6739040e+00], [2.6052000e+04, 1.4418710e+00, 8.0512400e-01], ..., [2.6575000e+04, 1.0650102e+01, 8.6662700e-01], [4.8111000e+04, 9.1345280e+00, 7.2804500e-01], [4.3757000e+04, 7.8826010e+00, 1.3324460e+00]]標簽數據(datingLabels)如下
[3,2,1,1,1,1,3,3,...,3,3,3]（1）玩視頻游戲所耗時間百分比與每周消費冰淇淋公升數之間的相關關系圖
import matplotlibimport matplotlib.pyplot as pltfig = plt.figure()ax = fig.add_subplot(111)ax.scatter(datingDataMat[:,0], datingDataMat[:,1], 15.0*np.array(datingDLabels), 15.0*np.array(datingDLabels))plt.show()其中，y軸為每周消費冰淇淋公升數，x軸為玩視頻游戲所耗時間百分比
紫色為不喜歡，綠色為魅力一般，黃色為極具魅力
（2）飛行常客里程數與玩視頻游戲所耗時間百分比之間的相關關系圖
import matplotlibimport matplotlib.pyplot as pltfig = plt.figure()ax = fig.add_subplot(111)ax.scatter(datingDataMat[:,0], datingDataMat[:,1], 15.0*np.array(datingDLabels), 15.0*np.array(datingDLabels))plt.show()其中，y軸為玩視頻游戲所耗時間百分比，x軸為飛行常客里程數
紫色為不喜歡，綠色為魅力一般，黃色為極具魅力
（3）飛行常客里程數與每周消費冰淇淋公升數之間的相關關系圖
import matplotlibimport matplotlib.pyplot as pltfig = plt.figure()ax = fig.add_subplot(111)ax.scatter(datingDataMat[:,0], datingDataMat[:,2], 15.0*np.array(datingDLabels), 15.0*np.array(datingDLabels))plt.show()其中，y軸為每周消費冰淇淋公升數，x軸為飛行常客里程數
紫色為不喜歡，綠色為魅力一般，黃色為極具魅力
?由于通過歐式距離計算樣本之間的距離時，對于飛行常客里程數來說，數量值巨大，會對結果影響的權重也會較大，而且遠遠大于其他兩個特征，但是作為三個等權重之一，飛行常客里程數并不應該如此嚴重影響結果，例子如下
((0-67)**2+(20000-32000)**2+(1.1-0.1)**2)**1/2| 玩視頻游戲所耗時間百分比 | 飛行常客里程數 | 每周消費冰淇淋公升數 | 樣本分類 | |
| 1 | 0.8 | 400 | 0.5 | 1 |
| 2 | 12 | 134000 | 0.9 | 3 |
| 3 | 0 | 20000 | 1.1 | 2 |
| 4 | 67 | 32000 | 0.1 | 2 |
通常我們在處理不同取值范圍的特征時，常常采用歸一化進行處理，將特征值映射到0-1或者-1到1之間，通過對（列中所有值-列中最小值）/（列中最大值-列中最小值）進行歸一化特征
def autoNorm(dataSet): minVals = dataSet.min(0) maxVals = dataSet.max(0) ranges = maxVals - minVals normDataSet = np.zeros(np.shape(dataSet)) m = dataSet.shape[0] normDataSet = dataSet - np.tile(minVals, (m,1)) normDataSet = normDataSet/np.tile(ranges, (m,1)) #element wise divide return normDataSet, ranges, minVals評估正確率是機器學習算法中非常重要的一個步驟，通常我們會只使用訓練樣本的90%用來訓練分類器，剩下的10%用于測試分類器的正確率。為了不影響數據的隨機性，我們需要隨機選擇10%數據。
（1）使用file2matrix函數導入數據樣本
（2）使用autoNorm對數據進行歸一化處理
（3）使用classify0對90%的數據進行訓練，對10%的數據進行測試
（4）輸出測試集中的錯誤率
def datingClassTest(): hoRatio = 0.50 #hold out 10% datingDataMat,datingLabels = file2matrix("datingTestSet2.txt") #load data setfrom file normMat, ranges, minVals = autoNorm(datingDataMat) m = normMat.shape[0] numTestVecs = int(m*hoRatio) errorCount = 0.0 for i in range(numTestVecs): classifierResult = classify0(normMat[i,:],normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],3) 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)最后得到分類器處理的約會數據集的錯誤率為2.4%，這是一個相當不錯的結果，同樣我們可以改變hoRatio的值，和k的值，檢測錯誤率是否隨著變量的變化而增加
通過上面的學習，我們嘗試給海倫開發一套程序，通過在約會網站找到某個人的信息，輸入到程序中，程序會給出海倫對對方的喜歡程度的預測值：不喜歡，魅力一般，極具魅力
import numpy as npimport operatordef file2matrix(filename): fr = open(filename) numberOfLines = len(fr.readlines()) #get the number of lines in the file returnMat = np.zeros((numberOfLines,3)) #prepare matrix to return classLabelVector = [] #prepare labels return fr = open(filename) index = 0 for line in fr.readlines(): line = line.strip() listFromLine = line.split("/t") returnMat[index,:] = listFromLine[0:3] classLabelVector.append(int(listFromLine[-1])) index += 1 return returnMat,classLabelVectordef autoNorm(dataSet): minVals = dataSet.min(0) maxVals = dataSet.max(0) ranges = maxVals - minVals normDataSet = np.zeros(np.shape(dataSet)) m = dataSet.shape[0] normDataSet = dataSet - np.tile(minVals, (m,1)) normDataSet = normDataSet/np.tile(ranges, (m,1)) #element wise divide return normDataSet, ranges, minValsdef classify0(inX, dataSet, labels, k): dataSetSize = dataSet.shape[0] diffMat = np.tile(inX, (dataSetSize,1)) - dataSet sqDiffMat = diffMat**2 sqDistances = sqDiffMat.sum(axis=1) distances = sqDistances**0.5 sortedDistIndicies = distances.argsort() classCount={} for i in range(k): voteIlabel = labels[sortedDistIndicies[i]] classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1 sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True) return sortedClassCount[0][0]def classifyPerson(): resultList = ["not at all", "in small doses", "in large doses"] percentTats = float(input("percentage of time spent playing video games?")) ffMiles = float(input("ferquent fiter miles earned per year?")) iceCream = float(input("liters of ice ice crean consumed per year?")) datingDataMat,datingLabels = file2matrix("knn/datingTestSet2.txt") #load data setfrom file normMat, ranges, minVals = autoNorm(datingDataMat) inArr = np.array([percentTats, ffMiles, iceCream]) classifierResult = classify0((inArr-minVals)/ranges, normMat, datingLabels,3) print ("You will probably like this person:", resultList[classifierResult-1])if __name__ == "__main__": classifyPerson()#10 10000 0.5輸入測試數據：
percentage of time spent playing video games?10ferquent fiter miles earned per year?10000liters of ice ice crean consumed per year?0.5You will probably like this person: not at all以下案例以數字0-9的分類為例，簡述如何采用k近鄰算法對手寫數字進行識別。
?通常手寫輸入的數字都是圖片格式，我們需要將圖片轉換成knn算法可以識別的結構化數據，簡單來說就是讀取圖片中的像素點，像素點值通常在0-255之間，0為黑色，255為白色，因此可以將值大于250的像素點標記為1，其余標記為0，手寫數字1可以用以下數據集表示：
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
?以下提供兩種下載數據集的渠道：
數據集存放在digits.zip中，其中用1代表手寫的區域，用0代表空白區域
（大佬們，中秋快樂！！！）?
?通過img2vector函數對數據進行讀取，并且返回數組
def img2vector(filename): returnVect = np.zeros((1,1024)) fr = open(filename) for i in range(32): lineStr = fr.readline() for j in range(32): returnVect[0,32*i+j] = int(lineStr[j]) return returnVect（1）使用listdir讀取trainingDigits目錄下所有文件作為訓練數據
（2）使用listdir讀取testDigits目錄下所有文件作為測試數據
（3）將訓練數據與測試數據喂入knn算法中
def handwritingClassTest(): hwLabels = [] trainingFileList = listdir("trainingDigits") #load the training set m = len(trainingFileList) trainingMat = np.zeros((m,1024)) for i in range(m): fileNameStr = trainingFileList[i] fileStr = fileNameStr.split(".")[0] #take off .txt classNumStr = int(fileStr.split("_")[0]) hwLabels.append(classNumStr) trainingMat[i,:] = img2vector("trainingDigits/%s" % fileNameStr) testFileList = listdir("testDigits") #iterate through the test set errorCount = 0.0 mTest = len(testFileList) for i in range(mTest): fileNameStr = testFileList[i] fileStr = fileNameStr.split(".")[0] #take off .txt classNumStr = int(fileStr.split("_")[0]) vectorUnderTest = img2vector("testDigits/%s" % fileNameStr) classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3) print ("the classifier came back with: %d, the real answer is: %d"% (classifierResult, classNumStr)) if (classifierResult != classNumStr): errorCount += 1.0 print ("/nthe total number of errors is: %d" % errorCount) print ("/nthe total error rate is: %f" % (errorCount/float(mTest)))輸出訓練結果，錯誤率為1.1628%，通過改變k值與訓練樣本都會使得錯誤率發生變化。
the classifier came back with: 7, the real answer is: 7the classifier came back with: 7, the real answer is: 7the classifier came back with: 9, the real answer is: 9the classifier came back with: 0, the real answer is: 0the classifier came back with: 0, the real answer is: 0the classifier came back with: 4, the real answer is: 4the classifier came back with: 9, the real answer is: 9the classifier came back with: 7, the real answer is: 7the classifier came back with: 7, the real answer is: 7the classifier came back with: 1, the real answer is: 1the classifier came back with: 5, the real answer is: 5the classifier came back with: 4, the real answer is: 4the classifier came back with: 3, the real answer is: 3the classifier came back with: 3, the real answer is: 3the total number of errors is: 11the total error rate is: 0.011628（1）優點：精度高，對異常值不敏感，無數據輸入假定
（2）缺點：計算復雜度高，空間復雜度高
適用數據范圍：數值型和標稱型
（1）收集數據：可以使用任何方法
（2）準備數據：距離計算所需的數值，最好是結構化的數據格式
（3）分析數據L：可以使用任何方法
（4）訓練算法：此步驟不適合與k近鄰算法
（5）測試算法：計算錯誤率
（6）使用算法：首先需要輸入樣本數據和結構化的輸出結果，然后運行k-近鄰算法判定輸入數據分別屬于哪個分類，最后應用對計算出的分類執行后續的處理。
（1）數據特征之間量綱不統一時，需要對數據進行歸一化處理，否則會出現大數吃小數的問題
（2）數據之間的距離計算通常采用歐式距離
（3）kNN算法中K值的選取會對結果產生較大的影響，一般k值要小于訓練樣本數據的平方根
（4）通常采用交叉驗證法來選擇最優的K值
《機器學習實戰》
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.hztianpu.com/yun/120005.html
k近鄰(k-Nearest Neighbor，kNN)算法是經典的帶監督的分類算法，核心思想是如果一個樣本在特征空間中的k個最相鄰的樣本中的大多數屬于某一個類別，則針對該樣本的劃分結果也屬于這個類別。 1. 算法步驟 準備訓練數據和測試數據； 確定參數 k； 計算測試數據與各個訓練數據之間的距離，距離的遞增關系進行排序； 選取距離最小的 k 個點； 確定前 k 個點所在類別的出現頻率； 返回前 ...
摘要：是一種非參數的懶惰的監督學習算法非參數的意思是，模型不會對基礎數據分布做出任何假設。電腦端查看源碼參考資料網址是一個支持的人工智能建模平臺，能幫助你快速開發訓練并部署應用。 KNN 是一種非參數的懶惰的監督學習算法. 非參數的意思是，模型不會對基礎數據分布做出任何假設。換句話說，模型的結構是根據數據確定的。懶惰的意思是沒有或者只有很少的訓練過程. KNN 算法既可以處理分類問題,測試數...
摘要：算法及工作原理近鄰算法采用測量不同特征值之間的距離方法進行分類。最后選擇個最相似數據中出現次數最多的分類作為新數據的分類。 1 分類算法引言 眾所周知,電影可以按照題材分類,然而題材本身是如何定義的?由誰來判定某部電影屬于哪個題材?也就是說同一題材的電影具有哪些公共特征?這些都是在進行電影分類時必須要考慮的問題。 動作片中也會存在接吻鏡頭,愛情片中也會存在打斗場景,我們不能單純依靠是...
閱讀 3355·2021-11-23 09:51
閱讀 3874·2021-09-22 15:35
閱讀 3842·2021-09-22 10:02
閱讀 3147·2021-08-30 09:49
閱讀 775·2021-08-05 10:01
閱讀 3631·2019-08-30 15:54
閱讀 1855·2019-08-30 15:53
閱讀 3776·2019-08-29 16:27
