什么是Ｋ近邻算法
众所周知，电影可以按照题材分类，然而题材本身是如何定义？同一题材的电影有哪些公共特征？这是电影分类的时候必须要考虑的。而Ｋ近邻算法就是解决这个问题的。Ｋ近邻算法通过分析电影中的特征，比如打斗场景、亲吻次数等来划分测试的影片跟哪个题材相关。
Ｋ近邻算法概述
ｋ近邻算法就是采用测量不同的特征值之间的距离方法进行分类。它的优点是精度高、对异常值不敏感、无数据输入假定。它的缺点是计算复杂度高、空间复杂度高、仅适用于数值型和标称型数据。
Ｋ近邻算法的一般流程
(1)收集数据：数据还要数值型或者是标称型数据
(2)准备数据：将数据转化成距离计算所需要的数值
(3)分析数据：使用Ｋ近邻算法对数据进行分析
(4)测试算法：计算该算法的错误率
(5)使用算法：输入想要测试的数据，运行Ｋ近邻算法，得出结果
Ｋ近邻算法代码实现
首先导入数据，添加一个组矩阵和一个标签矩阵。
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
这两个东西有什么用呢？这四组值加上四组标签一一对应在x,y轴上的话就是
这时候输入一个坐标，例如(1,1)这个点，计算这个点与这四个点的欧氏距离，得出与Ａ标签的点距离近，所以(1,1)这个点就属于类型Ａ。这就是Ｋ近邻算法。算法伪代码如下：
对未知类别属性的数据集中的点依次执行以下操作：
１．计算已知类别数据集中的点与当前点之间的距离
２．按照距离递增次序排序
３．选取与当前点距离最小的ｋ个点
４．确定前ｋ个点所在类别的出现频率
５．返回前ｋ个点出现频率最高的类别作为当前点的预测分类
程序代码如下所示：
def classify0(inX, dataSet, labels, k):
dataSetSize = dataSet.shape[0]
diffMat = tile(inX, (dataSetSize,1)) - dataSet
sqDiffMat = diffMat**2
sqDistances = sqDiffMat.sum(axis=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=lambda v: v[1], reverse=True)
return sortedClassCount[0][0]
其中函数的输入有四个，inX是输入向量，也就是要分类的对象。dataSet是训练样本集。labels是训练样本集对应的标签。最后的参数ｋ表示选择最近邻的数目。其中计算两个点之间的距离用的是欧氏距离，公式如下：
如果不是二维空间，而是多维空间，那么计算距离公式为：
计算完所有距离之后，可以对数据按照从小到大的次序排列。然后确定前ｋ个距离最小元素所在的分类，返回出现频率最高的元素标签。
运行上述程序，输出的结果应该是Ｂ。
测试Ｋ近邻算法
对于测试分类器，我们可以用已知的数据来进行测试，首先将已知数据使用Ｋ近邻算法进行分类，然后将已知数据的标签与测试结果作对比，来得到我们的误差率。我们使用《机器学习实战》这本书上海伦对约会网站上的哪类人感兴趣的数据集来进行测试。算法伪代码如下：
１．准备数据：使用python解析文件数据
２．分析数据：使用matplotlib画出二维扩散图
３．测试数据：使用文件中部分数据集作为测试样本进行测试
４．得出结果：将样本测得的标签与实际标签作对比，记录错误标签的数目
def file2matrix(filename):#准备数据
fr = open(filename,'r',encoding='UTF-8')
numberOfLines = len(fr.readlines()) #get the number of lines in the file
returnMat = zeros((numberOfLines,3)) #prepare matrix to return
classLabelVector = [] #prepare labels return
fr = open(filename,'r',encoding='UTF-8')
index = 0
for line in fr.readlines():
line = line.strip()
listFromLine = line.split('\t')
returnMat[index,:] = listFromLine[0:3]
classLabelVector.append(int(listFromLine[-1]))
index +=1
return returnMat,classLabelVector
#画出散点图
fig = plt.figure()
ax = fig.add_subplot(111)
datingDataMat,datingLabels = kNN.file2matrix('EXTRAS/datingTestSet2.txt')
ax.scatter(datingDataMat[:,0], datingDataMat[:,1], 35, 1.0*array(datingLabels))
ax.axis([-2,100000,-0.2,25])
plt.xlabel('Percentage of Time Spent Playing Video Games')
plt.ylabel('Liters of Ice Cream Consumed Per Week')
plt.show()
def autoNorm(dataSet): #数据归一化
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals - minVals
normDataSet = zeros(shape(dataSet))
m = dataSet.shape[0]
normDataSet = dataSet - tile(minVals, (m,1))
normDataSet = normDataSet/tile(ranges, (m,1)) #element wise divide
return normDataSet, ranges, minVals
def datingClassTest(): #测试误差率
hoRatio = 0.5 #hold out 10%
datingDataMat,datingLabels = file2matrix('./datingTestSet2.txt') #load data setfrom file
normMat, ranges, minVals = autoNorm(datingDataMat)
m = normMat.shape[0]
numTestVecs = int(m*hoRatio)
errorCount = 0.0
for i in range(numTestVecs):
classifierResult = classify0(normMat[i,:],normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],3)
print ("the classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i]))
if (classifierResult != datingLabels[i]): errorCount += 1.0
print( "the total error rate is: %f" % (errorCount/float(numTestVecs)))
print ('errorCount')
其中散点图如下所示：
图中清晰地表示了这两个类别对结果的影响。这时候从图中就可以看出，x,y轴的度量单位差异较大，所以对于结果来说，x轴的数据所占的权重较大，这明显是不符合常规的。所以我们在这儿需要将特征值进行归一化处理，将每个特征都归一化有助于平均所有特征的权重。归一化代码如上图所示。最后测试ｋ近邻算法，随机抽取前５０％数据来测试，结果得出误差率为6.4%，这个结果还比较不错。这个例子表明我们可以正确地预测分类，现在可以调用ｋ近邻算法来对输入的特征值进行分类，从而确定结果是属于哪一类！
预测函数代码如下：
def classifyPersion():
resultlist =['not at all','in small doses','in large doses']
percenttats = float(input("percentage of time spent playing video game:"))
ffmile = float(input('frequent filer miles earned per year:'))
icecream = float(input('liters of ice cream consumed per year:'))
datingDateMat,datingLabels = file2matrix('EXTRAS/datingTestSet2.txt')
normMat,ranges,minVals = autoNorm(datingDateMat)
inArr = array ([ffmile,percenttats,icecream])
classifierResult = classify0((inArr-minVals)/ranges,normMat,datingLabels,3)
print("You will probably like this person: ",resultlist[classifierResult-1])
现在运行这段代码，并输入测试人的信息，就能得出对这个人感兴趣的程度，如下图所示：
现在只要输入某个人的这三项特征，就能得出对他感不感兴趣，极大地提高了配对速率。
了解更多请关注作者微信公众号：
