利用Python实现kNN算法的代码
邻近算法（k-NearestNeighbor)是机器学习中的一种分类（classification）算法，也是机器学习中最简单的算法之一了。虽然很简单，但在解决特定问题时却能发挥很好的效果。因此，学习kNN算法是机器学习入门的一个很好的途径。
kNN算法的思想非常的朴素，它选取k个离测试点最近的样本点，输出在这k个样本点中数量最多的标签（label）。我们假设每一个样本有m个特征值（property），则一个样本的可以用一个m维向量表示:X=（x1，x2，...,xm), 同样地，测试点的特征值也可表示成：Y=（y1，y2，...,ym)。那我们怎么定义这两者之间的“距离”呢？
在二维空间中，有：d2=(x1-y1)2+(x2-y2)2, 在三维空间中，两点的距离被定义为：d2=(x1-y1)2+(x2-y2)2 +(x3-y3)2。我们可以据此推广到m维空间中，定义m维空间的距离：d2=(x1-y1)2+(x2-y2)2 +......+(xm-ym)2。要实现kNN算法，我们只需要计算出每一个样本点与测试点的距离，选取距离最近的k个样本，获取他们的标签（label)，然后找出k个样本中数量最多的标签，返回该标签。
在开始实现算法之前，我们要考虑一个问题，不同特征的特征值范围可能有很大的差别，例如，我们要分辨一个人的性别，一个女生的身高是1.70m，体重是60kg，一个男生的身高是1.80m，体重是70kg，而一个未知性别的人的身高是1.81m,体重是64kg，这个人与女生数据点的“距离”的平方d2=(1.70-1.81)2+(60-64)2=0.0121+16.0=16.0121，而与男生数据点的“距离”的平方d2=(1.80-1.81)2+(70-64)2=0.0001+36.0=36.0001。可见，在这种情况下，身高差的平方相对于体重差的平方基本可以忽略不计，但是身高对于辨别性别来说是十分重要的。为了解决这个问题，就需要将数据标准化（normalize），把每一个特征值除以该特征的范围，保证标准化后每一个特征值都在0~1之间。我们写一个normData函数来执行标准化数据集的工作：
defnormData(dataSet): maxVals=dataSet.max(axis=0) minVals=dataSet.min(axis=0) ranges=maxVals-minVals retData=(dataSet-minVals)/ranges returnretData,ranges,minVals
然后开始实现kNN算法：
defkNN(dataSet,labels,testData,k):
distSquareMat=(dataSet-testData)**2#计算差值的平方
distSquareSums=distSquareMat.sum(axis=1)#求每一行的差值平方和
distances=distSquareSums**0.5#开根号，得出每个样本到测试点的距离
sortedIndices=distances.argsort()#排序，得到排序后的下标
indices=sortedIndices[:k]#取最小的k个
labelCount={}#存储每个label的出现次数
foriinindices:
label=labels[i]
labelCount[label]=labelCount.get(label,0)+1#次数加一
sortedCount=sorted(labelCount.items(),key=opt.itemgetter(1),reverse=True)
#对label出现的次数从大到小进行排序
returnsortedCount[0][0]#返回出现次数最大的label
注意，在testData作为参数传入kNN函数之前，需要经过标准化。
我们用几个小数据验证一下kNN函数是否能正常工作：
if__name__=="__main__": dataSet=np.array([[2,3],[6,8]]) normDataSet,ranges,minVals=normData(dataSet) labels=['a','b'] testData=np.array([3.9,5.5]) normTestData=(testData-minVals)/ranges result=kNN(normDataSet,labels,normTestData,1) print(result)
结果输出a，与预期结果一致。
完整代码：
importnumpyasnp
frommathimportsqrt
importoperatorasopt
defnormData(dataSet):
maxVals=dataSet.max(axis=0)
minVals=dataSet.min(axis=0)
ranges=maxVals-minVals
retData=(dataSet-minVals)/ranges
returnretData,ranges,minVals
defkNN(dataSet,labels,testData,k):
distSquareMat=(dataSet-testData)**2#计算差值的平方
distSquareSums=distSquareMat.sum(axis=1)#求每一行的差值平方和
distances=distSquareSums**0.5#开根号，得出每个样本到测试点的距离
sortedIndices=distances.argsort()#排序，得到排序后的下标
indices=sortedIndices[:k]#取最小的k个
labelCount={}#存储每个label的出现次数
foriinindices:
label=labels[i]
labelCount[label]=labelCount.get(label,0)+1#次数加一
sortedCount=sorted(labelCount.items(),key=opt.itemgetter(1),reverse=True)#对label出现的次数从大到小进行排序
returnsortedCount[0][0]#返回出现次数最大的label
if__name__=="__main__":
dataSet=np.array([[2,3],[6,8]])
normDataSet,ranges,minVals=normData(dataSet)
labels=['a','b']
testData=np.array([3.9,5.5])
normTestData=(testData-minVals)/ranges
result=kNN(normDataSet,labels,normTestData,1)
print(result)
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。