K最近鄰算法

2019-11-14 17:49:17

字體：大中小

供稿：網(wǎng)友

K最近鄰（K-Nearest-Neighbour,KNN）算法是機器學習里簡單易掌握的一個算法。通過你的鄰居判斷你的類型，“近朱者赤，近墨者黑”表達了K近鄰的算法思想。

一．算法描述：

1.1 KNN算法的原理

KNN算法的前提是存在一個樣本的數(shù)據(jù)集，每一個樣本都有自己的標簽，表明自己的類型。現(xiàn)在有一個新的未知的數(shù)據(jù)，需要判斷它的類型。那么通過計算新未知數(shù)據(jù)與已有的數(shù)據(jù)集中每一個樣本的距離，然后按照從近到遠排序。取前K個最近距離的樣本，來判斷新數(shù)據(jù)的類型。

通過兩個例子來說明KNN算法的原理

（1）下圖中，綠色圓要被決定賦予哪個類，是紅色三角形還是藍色四方形？如果K=3，由于紅色三角形所占比例為2/3，綠色圓將被賦予紅色三角形那個類，如果K=5，由于藍色四方形比例為3/5，因此綠色圓被賦予藍色四方形類。

從該圖中可以看出K值的選取對類別的判斷具有較大的影響，K的選擇目前沒有很好的辦法，經(jīng)驗規(guī)則K值一般低于訓練樣本的開平方。

（2）有六部已知類型的電影，有人統(tǒng)計了電影場景中打斗次數(shù)和接吻次數(shù)，如下表。最后一行表示有一部新的電影，統(tǒng)計了其中打斗和接吻的次數(shù)，那么如何判斷這部電影是愛情片還是動作片。

電影名稱	打斗次數(shù)	接吻次數(shù)	電影類型
California Man	3	104	Romance
He’s Not Really into Dudes	2	100	Romance
Beautiful Woman	1	81	Romance
Kevin Longblade	101	10	Action
Robo Slayer 3000	99	5	Action
Amped II	98	2	Action
未知	18	90	Unknown

將打斗次數(shù)和接吻次數(shù)分別作為x,y軸，得到下圖

？表示未知電影的未知，然后計算該位置到其他點的距離，假定K=3，可知，距離最近都是愛情片，因此判定該電影也是愛情片。

1.2 KNN算法的優(yōu)缺點

該算法在分類時有個主要的不足是，當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本占多數(shù)。因此可以采用權(quán)值的方法（和該樣本距離小的鄰居權(quán)值大）來改進。

該方法的另一個不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。該算法比較適用于樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。

1.3 算法執(zhí)行步驟：

（1）生成向量位置

（2）計算樣本集到新數(shù)據(jù)的距離

（3）對樣本集按距離進行排序

（4）根據(jù)K選取樣本，判定類型

二．Python實現(xiàn)

1.簡單實現(xiàn)

創(chuàng)建數(shù)據(jù)集并實現(xiàn)knn算法

#knn agorithm***#2014-1-28   ***from numpy import import Operatordef createDataSet():    group=array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])    labels=['A','A','B','B']    return group,labelsdef classify0(inX,dataSet,labels,k):    dataSetSize=dataSet.shape[0]    diffMat=tile(inX,(dataSetSize,1))-dataSet    ddMat=diffMat**2    dsumMat=sum(ddMat,axis=1)    deqrMat=dsumMat**0.5    sortMat=deqrMat.argsort()    dic={}    for i in range(k):        lab=labels[sortMat[i]]        dic[lab]=dic.get(lab,0)+1    maxlabelcout=sorted(dic.iteritems(),key=operator.itemgetter(1),reverse=True)    return maxlabelcout[0][0]

對測試數(shù)據(jù)進行類型判斷

#knn               *********#run the knn1 with [0,0]****#2014-1-28         *********#zhen              *********import knn1group,labels=knn1.createDataSet()PRint groupprint labelsg=knn1.classify0([0,0],group,labels,3)print g

2.實際應(yīng)用-約會網(wǎng)站

###knn agorithm###2014-1-28   from numpy import *import operator#knn def classify0(inX,dataSet,labels,k):    dataSetSize=dataSet.shape[0]    diffMat=tile(inX,(dataSetSize,1))-dataSet    ddMat=diffMat**2    dsumMat=sum(ddMat,axis=1)    deqrMat=dsumMat**0.5    sortMat=deqrMat.argsort()    dic={}    for i in range(k):        lab=labels[sortMat[i]]        dic[lab]=dic.get(lab,0)+1    maxlabelcout=sorted(dic.iteritems(),key=operator.itemgetter(1),reverse=True)    return maxlabelcout[0][0]    def fileopen(filename):    f=open(filename)    flines=f.readlines()    fsize=len(flines)    index=0    mat=zeros((fsize,3))    labels=[]    for line in flines:        line=line.strip()        list=line.split('/t')        mat[index,:]=list[0:3]        labels.append(int(list[-1]))        index+=1    return mat,labelsdef autonorm(Dataset):    dmin=Dataset.min(0)    dmax=Dataset.max(0)    ranges=dmax-dmin    datanorm=zeros(shape(Dataset))    m=Dataset.shape[0]    datanorm=Dataset-tile(dmin,(m,1))    datanorm=datanorm/tile(ranges,(m,1))    return datanorm,ranges,dmindef classTest():    hoRatio=0.1    mat,lables=fileopen('datingTestSet2.txt')    dataNorm,ranges,dmin=autonorm(mat)    m=mat.shape[0]    numTest=int(m*hoRatio)    errorCount=0.0    for i in range(numTest):        lablesTest=classify0(dataNorm[i,:],dataNorm[numTest:m,:],/            lables[numTest:m],3)        if (lablesTest!=lables[i]):            errorCount+=1.0        print "the classifier came back with:%d,the real answer is:%d"/            %(lablesTest,lables[i])    print "the total error rate is: %f" % (errorCount/numTest)def classifyperson():    resultTypeList=['not at all','in small doses','in large doses']    percentGame=float(raw_input(/        "percentage of time spent playing video games?"))    miles=float(raw_input("miles earned per year?"))    iceCream=float(raw_input("liters of ice cream per year?"))    mat,lables=fileopen('datingTestSet2.txt')    dataNorm,ranges,dmin=autonorm(mat)    arr=array([miles,percentGame,iceCream])    result=classify0((arr-dmin)/ranges,dataNorm,lables,3)    print "You will probably like this person: ",/        resultTypeList[result-1]