簡單的說k-近鄰算法是通過測(cè)量不同特征值之間的距離進(jìn)行分類.
優(yōu)點(diǎn):精度高,對(duì)異常值不敏感 無數(shù)據(jù)輸入假定.
缺點(diǎn):計(jì)算復(fù)雜度高,空間復(fù)雜度高.
適用數(shù)據(jù)范圍:數(shù)值型和標(biāo)稱型.
它的工作原理:需要有一個(gè)樣本數(shù)據(jù)集,也成為訓(xùn)練樣本集,并且樣本集中每個(gè)數(shù)據(jù)都有標(biāo)簽(有明確的分類信息).輸入沒有標(biāo)簽的新數(shù)據(jù)后,將新數(shù)據(jù)的每個(gè)特征和樣本集中每個(gè)數(shù)據(jù)對(duì)應(yīng)的特征進(jìn)行比較,然后算法提取樣本集中特征最相似數(shù)據(jù)(最近鄰)的分類標(biāo)簽.一般來說我們只選取樣本數(shù)據(jù)集中前k個(gè)最相似的數(shù)據(jù),這就是k-近鄰算法中k的出處,通常k是不大于20的正整數(shù).最后,選擇k個(gè)最相似數(shù)據(jù)中出現(xiàn)最多的分類作為新數(shù)據(jù)的分類.
實(shí)施分類算法
fromnumpyimport*
importoperator
#《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》k—近鄰算法實(shí)現(xiàn)
# numpy是科學(xué)計(jì)算包署恍，operator是運(yùn)算符包
#創(chuàng)建數(shù)據(jù)集和標(biāo)簽
defcreateDataSet():
group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
labels = ['A','A','B','B']
returngroup,labels
#實(shí)施kNN分類算法
# 1.計(jì)算已知類別數(shù)據(jù)集中的點(diǎn)與當(dāng)前點(diǎn)之間的距離
# 2.按照距離遞增次序排序
# 3.選取與當(dāng)前點(diǎn)距離最近的k個(gè)點(diǎn)
# 4.確定k個(gè)點(diǎn)所在類別的出現(xiàn)頻率
# 5.返回k個(gè)點(diǎn)中出現(xiàn)頻率最高的類別作為當(dāng)前點(diǎn)的預(yù)測(cè)分類
defclassify0(inX,dataSet,labels,k):
#獲取訓(xùn)練樣本集的行數(shù)
dataSetSize = dataSet.shape[0]
#距離計(jì)算? 使用歐式計(jì)算√(a0 - b0)^2 + (a1 - b1)^2
diffMat = tile(inX,(dataSetSize,1)) - dataSet
sqDiffMat = diffMat **2
sqDistances = sqDiffMat.sum(axis=1)
#選擇距離最小的k個(gè)點(diǎn)
distances = sqDistances **0.5
sortedDistIndicies = distances.argsort()
classCount = {}
foriinrange(k):
voteIlabel = labels[sortedDistIndicies[i]]
classCount[voteIlabel] = classCount.get(voteIlabel,0) +1
#排序
# Python3.5中：iteritems變?yōu)閕tems
sortedClassCount =sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
returnsortedClassCount[0][0]
這是用Python實(shí)現(xiàn)的k-近鄰算法 ,windows下在cmd命令窗下可以執(zhí)行.
把路徑切換到該.py文件路徑下,cmd中輸入python進(jìn)入Python交互模式,然后輸入下面的命令導(dǎo)入編輯的程序模塊(kNN是上面模塊的文件名):
import kNN
然后創(chuàng)建訓(xùn)練樣本集:
group,labels = kNN.createDataSet()
預(yù)測(cè)數(shù)據(jù)所在分類:
kNN.classify0([0,0], group, labels, 3)
輸出結(jié)果應(yīng)該是'B',也可以改變輸入[0,0]為其他值來測(cè)試.
