KNN（K-Nearest Neighbor）是一個監(jiān)督學習方法微饥，它的工作機制非常簡單逗扒，無需訓練訓練集，是較為簡單的經(jīng)典機器學習算法之一欠橘【丶纾可以處理回歸問題和分類問題。
KNN工作原理：存在一個樣本數(shù)據(jù)集合肃续，也稱為訓練樣本集黍檩，并且樣本集中每個數(shù)據(jù)都存在標簽，即我們知道樣本集中每一數(shù)據(jù)與所屬分類對應(yīng)的關(guān)系始锚。輸入沒有標簽的數(shù)據(jù)后刽酱，將新數(shù)據(jù)中的每個特征與樣本集中數(shù)據(jù)對應(yīng)的特征進行比較，提取出樣本集中特征最相似數(shù)據(jù)（最近鄰）的分類標簽瞧捌。一般來說棵里，我們只選擇樣本數(shù)據(jù)集中前k個最相似的數(shù)據(jù)，這就是k近鄰算法中k的出處姐呐，通常k是不大于20的整數(shù)殿怜。最后選擇k個最相似數(shù)據(jù)中出現(xiàn)次數(shù)最多的分類作為新數(shù)據(jù)的分類。
SVM和KNN算法區(qū)別
SVM算法樣本需要固定曙砂，屬于急切性學習头谜，即在存在訓練階段，在學習模型中訓練好后鸠澈，與驗證集比較柱告，將低維度問題上升到高緯度
KNN算法不需要固定樣本數(shù)量，屬于懶惰學習款侵，沒有顯示的訓練過程末荐，它在訓練階段只是把數(shù)據(jù)保存下來，訓練時間開銷為0新锈，等收到測試樣本后進行處理
KNN優(yōu)點缺點：
優(yōu)點：
1）用法靈活
2）對于小樣本預測方便
3）精度高甲脏，對異常值不敏感、無數(shù)據(jù)輸入假定
缺點：
1） 缺少訓練階段，無法應(yīng)對多樣本
2）計算復雜度高块请、空間復雜度高
KNN實現(xiàn)步驟：
1）計算距離
歐氏距離（Euclidean distance）娜氏，即
2）按照距離的遞增關(guān)系進行排序；
3）選取距離最小的K個點（一般不大于20個）墩新；
4）確定前K個點所在類別的出現(xiàn)頻率贸弥；
出現(xiàn)頻率 =某個類別 / k
5）返回前K個點中出現(xiàn)頻率最高的類別作為測試數(shù)據(jù)的預測分類。
舉個例子海渊，根據(jù)下圖绵疲，測試樣本m在圖中央，若k=1時臣疑，樣本m的近鄰點為“+”盔憨，則判斷樣本m為“+”。當k=3時讯沈，近鄰點有1個+郁岩、2個-，則判斷為“-”缺狠。當k=5時问慎，近鄰點有3個+、2個-挤茄，則判斷為“+”如叼。
KNN優(yōu)缺點
優(yōu)點：（1）簡單，易于理解驮樊，易于實現(xiàn)薇正，無需參數(shù)估計，無需訓練;（2） 精度高囚衔，對異常值不敏感（3）適合對稀有事件進行分類; （4） 適合于多分類問題(multi-modal,對象具有多個類別標簽)挖腰，KNN要比SVM表現(xiàn)要好;
缺點：（1）計算復雜度高、空間復雜度高练湿，對大量測試樣本計算量大猴仑，資源開銷大。（2）K值的選擇：最大的缺點是當樣本不平衡時肥哎，如一個類的樣本容量很大辽俗，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時篡诽，該樣本的K個鄰居中大容量類的樣本占多數(shù)崖飘。（3） KNN是一種消極學習方法、懶惰算法杈女。
KNN代碼與MDS多維標度法代碼一同實現(xiàn)朱浴，在最下方吊圾。
MDS多維標度法
因為KNN算法需要用到距離計算，但是在實際任務(wù)中翰蠢，樣本空間的維度都可能會比較高项乒，在高維的情況下，可能會出現(xiàn)距離樣本稀釋梁沧、距離計算困難等問題檀何。所以我們緩解高維空間帶來的問題的重要途徑是降維，即通過某種數(shù)學變化將原始空降的高維屬性空間轉(zhuǎn)化為一個低緯“子空間”
降維的經(jīng)典方法：MDS“多維縮放”算法
算法實現(xiàn)：
import numpy as np
import operator
def createDataset():
#四組二維特征
group = np.array([[5,115],[7,106],[56,11],[66,9]])
#四組對應(yīng)標簽
labels = ('動作片','動作片','愛情片','愛情片')
return group,labels
def classify(intX,dataSet,labels,k):
'''
KNN算法
'''
#numpy中shape[0]返回數(shù)組的行數(shù)廷支，shape[1]返回列數(shù)
#MDS降維操作
dataSetSize = dataSet.shape[0]
#去逆矩陣
diffMat = np.tile(intX,(dataSetSize,1))-dataSet
#二維特征相減后乘方
sqdifMax = diffMat**2
#計算距離
seqDistances = sqdifMax.sum(axis=1)
distances = seqDistances**0.5
print ("distances:",distances)
#返回distance中元素從小到大排序后的索引
sortDistance = distances.argsort()
print ("sortDistance:",sortDistance)
classCount = {}
for i in range(k):
#取出前k個元素的類別
voteLabel = labels[sortDistance[i]]
print ("第%d個voteLabel=%s",i,voteLabel)
classCount[voteLabel] = classCount.get(voteLabel,0)+1
#dict.get(key,default=None),字典的get()方法,返回指定鍵的值,如果值不在字典中返回默認值频鉴。
#計算類別次數(shù)
#key=operator.itemgetter(1)根據(jù)字典的值進行排序
#key=operator.itemgetter(0)根據(jù)字典的鍵進行排序
#reverse降序排序字典
sortedClassCount = sorted(classCount.items(),key = operator.itemgetter(1),reverse = True)
#結(jié)果sortedClassCount = [('動作片', 2), ('愛情片', 1)]
print ("sortedClassCount:",sortedClassCount)
return sortedClassCount[0][0]
if __name__ == '__main__':
group,labels = createDataset()
test = [20,101]
test_class = classify(test,group,labels,3)
print (test_class)
完整文件查看碼云
