K近接アルゴリズム

略称kNN、動作原理は:1つの訓練サンプルセットが存在し、対応する各データにラベルがある.新しいデータを入力すると、新しいデータの各特徴をサンプルセットデータに対応する特徴と比較し、K近傍アルゴリズムは、サンプルセットの特徴が最も類似しているデータの分類ラベルを新しいデータの分類として抽出する.言い換えれば、各サンプルと測定対象データとの距離を計算し、得られた距離を並べ替えて上位K名を取り出し、K名の中でサンプルデータが属する分類タイプが最も多いタイプが新しいデータ型である.

#coding=utf-8
from numpy import *
import operator
def createDataSet():
    group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
    labels = ['A','A','B','B']
    return group,labels

print createDataSet()

def KNNClassify(inX,dataSet,labels,k):
    dataSetSize = dataSet.shape[0]#dataSet      
    diffMat = tile(inX,(dataSetSize,1)) - dataSet
    sqDiffMat = diffMat ** 2
    '''     (   axis=0        ,
        axis=1                 )'''
    sqDistances = sqDiffMat.sum(axis = 1)
    distances = sqDistances ** 0.5
    sortedDistIndicies = distances.argsort()
    classCount = {}
    for i in range(k):
        votelabel = labels[sortedDistIndicies[i]]
        classCount[votelabel] = classCount.get(votelabel,0) + 1
    sortedClassCount = sorted(classCount.iteritems(),key = operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0]#sortedClassCount:[('A', 2), ('B', 1)])

dataSet, labels = createDataSet()
 
testX = array([1.2, 1.0])
k = 3
outputLabel = KNNClassify(testX, dataSet, labels, 3)
 
print("Your input is:", testX, "and classified to class: ", outputLabel)
 
 
testX = array([0.1, 0.3])
k = 3
outputLabel = KNNClassify(testX, dataSet, labels, 3)
 
print("Your input is:", testX, "and classified to class: ", outputLabel)

結果:

(array([[ 1. ,  1.1],
       [ 1. ,  1. ],
       [ 0. ,  0. ],
       [ 0. ,  0.1]]), ['A', 'A', 'B', 'B'])
('Your input is:', array([ 1.2,  1. ]), 'and classified to class: ', 'A')
('Your input is:', array([ 0.1,  0.3]), 'and classified to class: ', 'B')