KNN(python実装)

kNNアルゴリズムフロー
一般的にkNNは,(1)データ収集:トレーニングサンプル集合テストデータの決定;(2)試験データと訓練サンプルセットの各サンプルデータの距離を計算する.
一般的な距離計算式:ヨーロッパ式距離式:d(x,y)=Σni=1(xi−yi)2−−−−−−−−−−−−−−−−√d(x,y)=Σi=1 n(xi−yi)2マンハッタン距離式:d(x,y)=Σni=1|xi−yi|d(x,y)=Σi=1 n|xi−yi|(3)は照射距離が増加する順に並べ替えられる.(4)最も近いk個の点を選択する.(5)このk点における分類情報の頻度を決定する.(6)前k点で最も頻度の高い分類を返し,現在のテストデータの分類とする.
 
主なコード:

from numpy import *
import operator

#  KNN       
#      ：(    ，    ，  ,k )
def classify(inX,dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    diffMat = tile(inX,(dataSetSize,1))-dataSet
    sqDiffMat=diffMat**2
    sqDistances=sqDiffMat.sum(axis=1)
    distances=sqDistances**0.5 #      
    sortedDistIndicies=distances.argsort() #     index
    #       k  
    classCount={}
    for i in range(k):
        voteIlabel=labels[sortedDistIndicies[i]]
        #D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None.
        classCount[voteIlabel]=classCount.get(voteIlabel,0)+1
    #  ，  
    sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0]

注意:

ここではマトリクス演算を用いて、試験サンプルと各訓練サンプルとの間のL 2距離

を計算する.

KNNの不足は、1つのサンプルを予測するたびに、訓練サンプル全体に対して距離測定を行い、時間がかかることである.

したがって,対応するKD−Treeはこの問題をうまく解決し,すべてのサンプルを遍歴することなくcoor点に最も近いK個点のシーケンス番号を求めることができる.詳細手順は、前述の「KD-TreeのC++実装」

を参照してください.
 
参考資料:https://blog.csdn.net/moxigandashu/article/details/71169991