算法簡(jiǎn)介
KNN（k-NearestNeighbor ）算法是數(shù)據(jù)挖掘算法中最簡(jiǎn)單的算法之一，K代表最鄰近的鄰居，一個(gè)樣本的列表可以根據(jù)最鄰近的K個(gè)鄰居的分類決定。KNN的核心思想就是一個(gè)樣本在特征向量空間中k個(gè)最相鄰的樣本中大多數(shù)屬于哪個(gè)類別，那我們就說這個(gè)樣本屬于哪個(gè)類別。
算法優(yōu)點(diǎn)
1.簡(jiǎn)單，易于理解，易于實(shí)現(xiàn)，無需估計(jì)參數(shù)，無需訓(xùn)練；
- 適合對(duì)稀有事件進(jìn)行分類；
3.特別適合于多分類問題(multi-modal,對(duì)象具有多個(gè)類別標(biāo)簽)， kNN比SVM的表現(xiàn)要好。
算法缺點(diǎn)
1.當(dāng)樣本數(shù)量不平衡時(shí)，一個(gè)類的樣本容量特別大，其他類的樣本容量特別小，影響分類效果。
2.計(jì)算量大，需要計(jì)算待分類樣本與全部已知的所有分類樣本的距離，才能得到與待分類樣本最近的K個(gè)樣本。
3.可理解性查。
算法改進(jìn)
kNN計(jì)算量大，非常占用內(nèi)存的問題，對(duì)于大規(guī)模的數(shù)據(jù)，效率慘不忍睹。
就樣本數(shù)據(jù)本身來改進(jìn)，由于kNN善于處理稀有事件和多類別問題（MLkNN）所以適合類域的交叉或重疊較多的。樣本容量比較大的數(shù)據(jù)集。另外可以考慮壓縮訓(xùn)練樣本量，像濃縮技術(shù)(condensing)和編輯技術(shù)(editing)等都能大幅減少訓(xùn)練樣本量，同時(shí)又能很好的保持分類精度。
4.算法實(shí)現(xiàn)：
from numpy import *
import operator
import KNN
def createDataSet():
# 創(chuàng)建訓(xùn)練集
group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
labels = ['A', 'A', 'B', 'B']
return group, labels
def classify0(inX, dataSet, labels, k):
dataSetSize = dataSet.shape[0]
print("dataSetSize=",dataSetSize)
# 根據(jù)歐式距離計(jì)算訓(xùn)練集中每個(gè)樣本到測(cè)試點(diǎn)的距離
# Numpy的 tile() 函數(shù)，就是將原矩陣橫向、縱向地復(fù)制
diffMat = tile(inX, (dataSetSize, 1)) - dataSet
sqDiffMat = diffMat ** 2
sqDistances = sqDiffMat.sum(axis=1)#按行求和
print("sqDistances=",sqDistances)
distances = sqDistances ** 0.5#再開方
print("distances=",distances)
# 計(jì)算完所有點(diǎn)的距離后，對(duì)數(shù)據(jù)按照從小到大的次序排序 argsort返回的是索引值
sortedDistIndicies = distances.argsort()
print("sortedDistIndicies=",sortedDistIndicies)
# 確定前k個(gè)距離最小的元素所在的主要分類，最后返回發(fā)生頻率最高的元素類別
classCount = {}
for i in range(k):
voteIlabel = labels[sortedDistIndicies[i]]
classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
# operator.itemgetter(1)根據(jù)數(shù)據(jù)的第1維排序，第1維的為分類出現(xiàn)的次數(shù)
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
if __name__ == '__main__':
group,labes = KNN.createDataSet()
print("group=",group)
print("labels",labes)
print(KNN.classify0([0,0],group,labes,3))
輸出：
group=
[[1. 1.1]
[1. 1. ]
[0. 0. ]
[0. 0.1]]
labels ['A', 'A', 'B', 'B']
dataSetSize= 4
sqDistances= [2.21 2. 0. 0.01]
distances= [1.48660687 1.41421356 0. 0.1 ]
sortedDistIndicies= [2 3 1 0]
B
