k-近邻算法采用测量不同特征值之间的距离方法进行分类。

优点：精度高、对异常值不敏感、无数据输入假定。

缺点：计算复杂度高、空间复杂度高。

适用范围：数值型、标称型。

工作原理：存在一个样本数据集合（训练样本集），并且样本集中每个数据都存在标签。输入没有标签的新数据后，将数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相近数据的分类标签。

python实现简单的KNN算法如下：

 

KNN

from numpy import *

import operator

def getDataSet():

group=array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])

labels=['A','A','B','B']

return group,labels

def classfy0(inX,dataSet,labels,k):

dataSetSize=dataSet.shape[0]

diffMat=tile(inX,(dataSetSize,1))-dataSet

sqdiffMat=diffMat**2

sqDistances=sqdiffMat.sum(1)

distances=sqDistances**0.5

sortedDistIndicies=distances.argsort()

classCount={}

for i in range(k):

voteIlabel=labels[sortedDistIndicies[i]]

classCount[voteIlabel]=classCount.get(voteIlabel,0)+1

sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)

return sortedClassCount[0][0]

group,labels=getDataSet()

print(classfy0([0,0],group,labels,3))

 

 

该算法用到的距离计算为欧式距离公式。