機械学習アルゴリズムのKNNアルゴリズム

説明:KNNアルゴリズムは単純で暴力的な機械学習アルゴリズムであり、分類回帰でもよい.分類問題では,彼が線形に分けられるか線形に分けられないかにかかわらず,乾であり,分類するたびに,テストベクトルはすべての訓練データと距離を計算し,計算量は非常に大きい.データセットが非常に膨大である場合、困難であるが、k−dツリーまたはball−treeによってk近隣の検索を加速させることができる.k値の決定も問題であり,一般的には交差検証を用いて決定され,k=1,2,3,4…はそれぞれ計算され,誤り率が最も小さいkを探し出し,暴力計算である.
アルゴリズム原理:テストサンプルが知られており、そのサンプルとトレーニングデータセットのすべての距離を計算し、距離が最も小さいk個のサンプルを選択し、このk個のサンプルのラベルの出現回数を統計し、出現回数が最も多いラベルはテストサンプルの予測結果である.
Python実装KNNコード:

#knn ， ， ， 
def KnnClassify(testvec,trainset,labels,k):
    m=trainset.shape[0]# 
    diffmat=tile(testvec,(m,1))-trainset# 
    sqdiff=diffmat**2
    diffsum=sqdiff.sum(axis=1)# 
    distance=diffsum**0.5
    sortindex=distance.argsort()# ， ， 
    classcount={}# ， k 
    for i in range(k):
        tmpclass=labels[sortindex[i]]
        if classcount.has_key(tmpclass):
            classcount[tmpclass]+=1
        else:
            classcount[tmpclass]=1
    sortclass=sorted(classcount.iteritems(),key=lambda d:d[1],reverse=True)# value 
    return sortclass[0][0]