k近鄰(k-Nearest Neighbor,kNN)算法是經典的帶監督的分類算法,核心思想是如果一個樣本在特征空間中的k個最相鄰的樣本中的大多數屬于某一個類別,則針對該樣本的劃分結果也屬于這個類別。1. 算法步驟
準備訓練數據和測試數據;
確定參數 k;
計算測試數據與各個訓練數據之間的距離,距離的遞增關系進行排序;
選取距離最小的 k 個點;
確定前 k 個點所在類別的出現頻率;
返回前 k 個點中出現頻率最高的類別作為測試數據的預測分類。
2. Python代碼實現kNN 2.1 算法實現# python 3.7.2 from numpy import * import operator def kNNClassify(testData, trainData, labels, k): dataSize = trainData.shape[0] # 測試數據矩陣的行數,4 diffMat = tile(testData, (dataSize, 1)) - trainData # numpy中的tile用于重復矩陣中的元素,構造和dataSize規格一樣 sqDiffMat = diffMat ** 2 sqDistances = sqDiffMat.sum(axis=1) # 計算矩陣的行和 distances = sqDistances ** 0.5 # 采用歐式距離計算 sortedDisindexes = distances.argsort() # 返回排序后對應的索引數據 classCount = {} for i in range(k): voteLabel = labels[sortedDisindexes[i]] classCount[voteLabel] = classCount.get(voteLabel, 0) + 1 sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True) # 根據第2維進行排序 return sortedClassCount[0][0]
假設訓練數據為:
trainData= [[1, 1.1], [1, 1], [0, 0], [0, 0.1]] labels = ["A", "A", "B", "B"]
測試數據為:
testData = [[1.1 , 1], [0.1, 0]]2.2 實戰:約會網站對象匹配
小明在某約會網站上瀏覽妹子,對看到的每一個妹子進行評價:largeDoses,smallDoses,didntLike,評價的依據有3條:
每年旅行里程數
玩游戲占一天時間比重
每周吃的甜品數量
收集了1000條相關數據,存儲在datingTestSet.txt文件中
40920 8.326976 0.953952 largeDoses 14488 7.153469 1.673904 smallDoses 26052 1.441871 0.805124 didntLike 75136 13.147394 0.428964 didntLike 38344 1.669788 0.134296 didntLike 72993 10.141740 1.032955 didntLike 35948 6.830792 1.213192 largeDoses 42666 13.276369 0.543880 largeDoses 67497 8.631577 0.749278 didntLike 35483 12.273169 1.508053 largeDoses 50242 3.723498 0.831917 didntLike 63275 8.385879 1.669485 didntLike 5569 4.875435 0.728658 smallDoses 51052 4.680098 0.625224 didntLike ...
def file2Matrix(filename): love_dictionary = {"largeDoses": 1, "smallDoses": 0, "didntLike": -1} fr = open("datingTestSet.txt") arrayOfLines = fr.readlines() numOfLines = len(arrayOfLines) dataMatrix = zeros((numOfLines, 3)) # 數據矩陣 classLabels = [] # 標簽數組 index = 0 for line in arrayOfLines: line = line.strip() listFromLine = line.split(" ") dataMatrix [index, :] = listFromLine[0:3] classLabels.append(love_dictionary.get(listFromLine[-1])) index += 1 return returnMat, classLabels
各個維度的數值差異較大,直接使用會嚴重影響分類效果,因此需要進行歸一化處理:
newValue = (oldVlue -min) / (max - min)
def autoNorm(dataSet): minVals = dataSet.min(0) # min(0)返回列的最小值, min(1)返回行的最小值 maxVals = dataSet.max(0) # max(0)返回列的最大值, max(1)返回行的最大值 ranges = maxVals - minVals normDataSet = zeros(shape(dataSet)) m = normDataSet.shape[0] normDataSet = dataSet - tile(minVals, (m, 1)) normDataSet = normDataSet / tile(ranges, (m, 1)) return normDataSet
最后調用kNNClassify函數進行測試。此處省略
3. 算法優缺點 3.1 優點簡單,易于理解,易于實現;
適合數值型屬性分類;
適合于多分類問題(multi-modal,對象具有多個類別標簽), kNN比SVM的表現要好。
3.2 缺點當樣本不平衡時,如一個類的樣本容量很大,而其他類樣本容量很小時,有可能導致當輸入一個新樣本時,該樣本的k個鄰居中大容量類的樣本占多數,分類出現偏差。
計算量較大,每一個待分類的文本都要計算它到全體已知樣本的距離。
4. 改進策略改進策略主要分成了分類效率和分類效果兩個方向:
分類效率:事先對樣本屬性進行約簡,刪除對分類結果影響較小的屬性。該算法比較適用于樣本容量比較大的類域的自動分類,而那些樣本容量較小的類域采用這種算法比較容易產生誤分。
分類效果:① 采用權值的方法(和該樣本距離小的鄰居權值大)來改進,如可調整權重的k最近鄰居法WAkNN (weighted adjusted k nearest neighbor);② 依照訓練集合中各種分類的文件數量,選取不同數目的最近鄰居,來參與分類;③ 類中心算法,求出各個樣本的類中心到測試數據的距離,劃分到最近的類。
參考資料《機器學習實戰》
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/43672.html
摘要:電影分析近鄰算法周末,小迪與女朋友小西走出電影院,回味著剛剛看過的電影。近鄰分類電影類型小迪回到家,打開電腦,想實現一個分類電影的案例。分類器并不會得到百分百正確的結果,我們可以使用很多種方法來驗證分類器的準確率。 電影分析——K近鄰算法 周末,小迪與女朋友小西走出電影院,回味著剛剛看過的電影。 小迪:剛剛的電影很精彩,打斗場景非常真實,又是一部優秀的動作片! 小西:是嗎?我怎么感覺這...
摘要:背景近鄰算法的概述近鄰算法的簡介近鄰算法是屬于一個非常有效且易于掌握的機器學習算法,簡單的說就是采用測量不同特征值之間距離的方法對數據進行分類的一個算法。完美的分類器的錯誤率為,而最差的分類器的錯誤率則為。 1 背景 1.1 k近鄰算法的概述 (1)k近鄰算法的簡介 k-近鄰算法是屬于一個非...
摘要:算法及工作原理近鄰算法采用測量不同特征值之間的距離方法進行分類。最后選擇個最相似數據中出現次數最多的分類作為新數據的分類。 1 分類算法引言 眾所周知,電影可以按照題材分類,然而題材本身是如何定義的?由誰來判定某部電影屬于哪個題材?也就是說同一題材的電影具有哪些公共特征?這些都是在進行電影分類時必須要考慮的問題。 動作片中也會存在接吻鏡頭,愛情片中也會存在打斗場景,我們不能單純依靠是...
閱讀 654·2019-08-30 15:44
閱讀 1379·2019-08-30 11:02
閱讀 2980·2019-08-29 18:42
閱讀 3506·2019-08-29 16:16
閱讀 1719·2019-08-26 13:55
閱讀 1768·2019-08-26 13:45
閱讀 2384·2019-08-26 11:43
閱讀 3246·2019-08-26 10:32