机器学习之Ｋ近邻算法

什么是Ｋ近邻算法

众所周知，电影可以按照题材分类，然而题材本身是如何定义？同一题材的电影有哪些公共特征？这是电影分类的时候必须要考虑的。而Ｋ近邻算法就是解决这个问题的。Ｋ近邻算法通过分析电影中的特征，比如打斗场景、亲吻次数等来划分测试的影片跟哪个题材相关。

Ｋ近邻算法概述

ｋ近邻算法就是采用测量不同的特征值之间的距离方法进行分类。它的优点是精度高、对异常值不敏感、无数据输入假定。它的缺点是计算复杂度高、空间复杂度高、仅适用于数值型和标称型数据。

Ｋ近邻算法的一般流程

(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])

现在运行这段代码，并输入测试人的信息，就能得出对这个人感兴趣的程度，如下图所示：

运行结果

现在只要输入某个人的这三项特征，就能得出对他感不感兴趣，极大地提高了配对速率。

了解更多请关注作者微信公众号：

一技破万法