K近隣アルゴリズムのpython実装

9494 ワード

前言
K近傍の元のアルゴリズムでは,K近傍の方法を最適化していないのか,それとも訓練セットを巡回して入力インスタンスに最も近いK個の訓練インスタンスを見つけ,それらのカテゴリを統計して入力インスタンスカテゴリの判断とする.具体的なモデル理論は:統計学習方法——K近隣法(原始方法)を見る
1.K近隣アルゴリズムの実現
アルゴリズム実装の過程で,点と点間の距離メトリックをオーステナイト距離で行う.データ演算を行う場合はnumpyではなくPythonに付属のlistでデータの計算を行う.
def knn(x,dataSet,labels,k):
    distanceMemories = {}  #          
    for i in range(len(dataSet)):
        distance = euDis(x,dataSet[i])
        distanceMemories[i] = distance
    sortResult = sorted(distanceMemories.items(),key = lambda  x:x[1])
    distance_min_k = sortResult[:k]
    classCount = {}  #      k          
    for i in range(len(distance_min_k)):
        if labels[distance_min_k[i][0]] not in classCount:
            classCount[labels[distance_min_k[i][0]]] = 0
        classCount[labels[distance_min_k[i][0]]] += 1
    result = sorted(classCount.items(),key = lambda x:x[1],reverse = True)
    #      ,         ,      
    return result[0][0]

def euDis(x,y): #        
    dim = len(x)
    temp = 0
    for i in range(dim):
        temp += (x[i] - y[i]) ** 2
    return temp ** 0.5

dataSet = [[3,104],[2,100],[1,81],[101,10],[99,5],[98,2]]  
#                
labels = ["   ","   ","   ","   ","   ","   "]
print(knn([18,90],dataSet,labels,3))
#     :