哇，这是我回家之前的最后一篇文章喔~~~我19号就放假啦！这几天闲着无聊，最后一个考试在18号然而中间有13天没有任何事情，所以我就决定买几本书看看机器学习什么的毕竟以后还要学，这篇文章是基于对《Machine Learning in Action》的理解而写，因为书中给出的代码并不完整所以我对书中有些代码进行了修改和补全供大家参考。

K-近邻算法(k-Nearest Neighbors)

简单的说K-近邻算法是一种分类算法，它通过测量不同特征值之间的距离来进行分类。

我感觉书上给的使用例子非常生动：电影可以按照题材分类，然而题材本身是如何定义的?由谁来判定某部电影属于哪个题材?也就是说同一题材的电影具有哪些公共特征？这些都是在进行电影分类时必须要考虑的问题。没有哪个电影人会说自己制作的电影和以前的某部电影类似，但我们确实知道每部电影在风格上的确有可能会和同题材的电影相近。那么动作片具有哪些共有特征，使得动作片之间非常类似，而与爱情片存在着明显的差别呢?动作片中也会存在接吻镜头，爱情片中也会存在打斗场景，我们不能单纯依靠是否存在打斗或者亲吻来判断影片的类型。但是爱情片中的亲吻镜头更多，动作片中的打斗场景也更频繁，基于此类场景在某部电影中出现的次数可以用来进行电影分类。基于电影中出现的亲吻、打斗出现的次数，使用-近邻算法构造程序，自动划分电影的题材类型。

 

K近邻算法属性

K近邻算法属性
优点：精度高，对异常值不敏感，无数据输入假定。
缺点：计算复杂度高，空间复杂度高。
使用数据范围：数值型和标称型。

 

该算法核心基于欧氏距离公式(Euclidian distance)计算两个向量点xA和xB之间的公式如下图所示：

当然这里只给出了两个特征值时的距离算法，多个特征值时只是对应项作差求平凡然后加和开根号。

一、解析数据

在这个算法中我们用如下一个例子来讲如何

我的朋友海伦一直使用在线约会网站寻找适合自己的约会对象。尽管约会网站会推荐不同的
人选，但她没有从中找到喜欢的人。经过一番总结，她发现曾交往过三种类型的人：
(1)不喜欢的人

(2)魅力一般的人

(3)极具魅力的人
尽管发现了上述规律，但海伦依然无法将约会网站推荐的匹配对象归入恰当的分类。她觉得可以在周一到周五约会那些魅力一般的人，而周末则更喜欢与那些极具魅力的人为伴。海伦希望我们的分类软件可以更好地帮助她将匹配对象划分到确切的分类中。

海伦的样本主要包含以下3种特征；

(1)每年获得的飞行常客里程数

(2)玩视频游戏所耗时间百分比

(3)每周消费的冰淇淋公升数

数据源如下图:

第一列：每年获得的飞行里程数

第二列：玩视频游戏所耗时间百分比

第三列：每周消费的冰淇淋公升数

第四列：魅力程度

我们首先需要让程序读入数据，因此第一步我们需要从文本中解析数据，函数如下

def file2matrix(filename):
    '''
    该函数负责从文本文件中读取文件并解析内容
    :param filename: 文件名
    :return: 解析后生成的数据矩阵，分类向量
    '''
    fr = open(filename)
    #获取文件行数
    numberOfLines = len(fr.readlines())
    #创建m行n列的零矩阵
    returnMat = zeros((numberOfLines,3))
    #分类标签向量的数组
    classLabelVector = []
    fr = open(filename)
    index = 0
    for line in fr.readlines():
        line = line.strip()
        #去除空格
        listFromLine = line.split('\t')
        #每一行数据作为矩阵的每一行，[0:3]表示从第0列到第3列，0也可以省略
        returnMat[index,:] = listFromLine[0:3]
        #从数据源可以看出listFromLine中最后一列为分类标签
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
    return returnMat,classLabelVector
file2matrix

需要注意的是我代码中使用的数组均为NumPy数组而非Python数组，因此需要下载NumPy库并导入

这时我们已经有初始数据了，我们可以将获得的数据集制作原始数据散点图，由于原文对图像输出的代码写的并不完善，因此我对原文的代码进行了一些小小的封装和修改，如下是用来输出图像的函数

def showImage(datingDataMat,datingLabels,xlabelStr,ylabelStr,index1,index2):
    '''
    为简化图像输出而定义的专门用于输出图像的函数
    :param datingDataMat: 数据集矩阵
    :param datingLabels: 数据集标签
    :param xlabelStr: X轴描述
    :param ylabelStr: Y轴描述
    :param index1: 指定数据列1
    :param index2: 指定数据列2
    :return: 
    '''
    fig = plt.figure()
    # 111表示把绘图区域分成1行*1列共1个区域，然后在区域1上创建一个轴对象
    ax = fig.add_subplot(111)

    type1_x = []
    type1_y = []
    type2_x = []
    type2_y = []
    type3_x = []
    type3_y = []

    #按照标签分类
    for i in range(len(datingLabels)):
        if datingLabels[i] == 1:
            type1_x.append(datingDataMat[i][index1])
            type1_y.append(datingDataMat[i][index2])

        if datingLabels[i] == 2:
            type2_x.append(datingDataMat[i][index1])
            type2_y.append(datingDataMat[i][index2])

        if datingLabels[i] == 3:
            #print i, '：', datingLabels[i], ':', type(datingLabels[i])
            type3_x.append(datingDataMat[i][index1])
            type3_y.append(datingDataMat[i][index2])

    type1 = ax.scatter(type1_x, type1_y, s=20, c='red')
    type2 = ax.scatter(type2_x, type2_y, s=40, c='green')
    type3 = ax.scatter(type3_x, type3_y, s=50, c='blue')

    ax.legend((type1, type2, type3), (u'不喜欢', u'魅力一般', u'极具魅力'), loc=2)

    plt.xlabel(xlabelStr)
    plt.ylabel(ylabelStr)
    plt.show()
showImage

需要注意的是我使用的是Matplotlib来绘制图像，因此也需要单独下载该库并导入到项目中

使用datingDataMat矩阵的第二列和第三列的数据绘制散点图

datingDataMat,datingLabels=file2matrix('datingTestSet2.txt')
xlabelStr=u"玩视频游戏所耗时百分百"
ylabelStr=u"每周消耗的冰淇淋公升数"
showImage(datingDataMat,datingLabels,xlabelStr,ylabelStr,1,2)

会输出这样的一张散点图：

当然我们也可以使用第0列和第1列绘制散点图只需将代码改为：

datingDataMat,datingLabels=file2matrix('datingTestSet2.txt')
xlabelStr=u"每年的飞行公里数"
ylabelStr=u"玩视频游戏所耗时百分百"
showImage(datingDataMat,datingLabels,xlabelStr,ylabelStr,0,1)

就可以得到如下的散点图：

二、数据归一化

我们来看这样的一个等式：

不难发现在这个距离公式中数值差值最大的属性对计算的结果影响最大，也就是对应我们数据源中“每年获得的飞行里程数”这一特征对计算结果的影响要远远大于其他两个特征——“玩视频游戏所耗时间百分比”和“每周消费的冰淇淋公升数”的影响，产生这种情况的原因是因为“每年获得的飞行里程数”这一特征值远大于其他两个特征值，然而海伦人为这三个因素同等重要，因此作为等权重的特征之一“每年获得的飞行里程数”这一特征不应该如此严重的影响计算结果，因此我们需要将数值归一化，通常采用的方法是将取值范围处理为0到1或-1到1之间。

下面的公式可以将任意取值范围的特征转化为0到1之间：

实现函数如下：

def autoNorm(dataSet):
    '''
    该函数用于数据归一化，用于处理不同取值范围的特征值相差较大时消除对计算结果的影响，
    将取值范围处理为0到1或-1到-1之间的数值
    :param dataSet: 
    :return: 
    '''
    #参数为0则从列中选择最小值，而不是选取当前行的最小值
    minVals=dataSet.min(0)
    maxVals=dataSet.max(0)
    ranges=maxVals-minVals
    normDataSet=zeros(shape(dataSet))
    m=dataSet.shape[0]
    #tile函数将变量内容复制成输入矩阵相同大小的矩阵
    normDataSet=dataSet-tile(minVals,(m,1))
    normDataSet=normDataSet/tile(ranges,(m,1))
    return normDataSet,ranges,minVals
autoNorm(dataSet)

三、K-近邻算法实现

该算法主要是对未知类别属性的数据集中的每个点依次执行以下操作：
（1）计算已知类别数据集中的点与当前点之间的距离；
（2）按照距离递增次序排序；
（3）选取与当前点距离最小的k个点；
（4）确定前k个点所在类别的出现频率；
（5）返回前k个点出现频率最高的类别作为当前点的预测分类。

函数实现如下：

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

    '''
    计算距离
    :param inX: 用于分类的输入向量
    :param dataSet: 输入的训练样本集
    :param labels: 标签向量
    :param k: 用于选择最近邻居的数目
    :return: 排序好的结果集
    '''
    '''
    shape读取矩阵的长度，比如shape[0]就是读取矩阵第一维度的长度。
    它的输入参数可以使一个整数表示维度，也可以是一个矩阵。
    '''
    dataSetSize=dataSet.shape[0]
    #输入向量inX循环与输入数据集作差
    diffMat=tile(inX,(dataSetSize,1))-dataSet
    sqDiffMat=diffMat**2
    #axis=1是将一个矩阵的每一行向量相加
    sqDistances=sqDiffMat.sum(axis=1)
    #开根号才是距离
    distances=sqDistances**0.5
    #选择距离最小的k个点
    #argsort函数返回的是数组值从小到大的索引值
    sortedDistIndicies=distances.argsort()
    classCount={}
    #range(x)函数通常结合for循环一起使用,使得循环终止于x-1的位置
    for i in range(k):
        voteIlabel=labels[sortedDistIndicies[i]]
        classCount[voteIlabel]=classCount.get(voteIlabel,0)+1
    '''
        排序
        iteritems()返回iterator 他是迭代器是访问集合元素的一种方式。
        迭代器对象从集合的第一个元素开始访问，直到所有的元素被访问完结束。
        迭代器只能往前不会后退。
        key用列表元素的某个属性或函数进行作为关键字，有默认值，迭代集合中的一项
        reverse = True 降序 或者 reverse = False 升序

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

    return sortedClassCount[0][0]
classify0

四、测试算法

机器学习算法一个很重要的工作就是评估算法的正确率，通常我们只提供已有数据的90%作为训练样本来训练分类器，而使用其余的10%数据去测试分类器，检测分类器的正确率。本书后续章节还会介绍一些高级方法完成同样的任务，这里我们还是采用最原始的做法。需要注意的是，10%的测试数据应该是随机选择的，由于海伦提供的数据并没有按照特定目的来排序，所以我们可以随意选择10%数据而不影响其随机性。

测试方法实现：

def datingClassTest():
    '''
    该函数用于测试算法的正确性
    :return:
    '''
    #通常提供90%的数据作为样本进行训练，其余10%的数据去测试分类器，要注意10%的测试数据需要随机选择
    hoRatio = 0.10
    datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')
    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
    pass
datingClassTest

我们可以查看测试结果如下图所示：

错误率为5%，这是一个相当不错的结果。我们可以改变函数datingclassTest内变量hoRatio和变量k的值，检测错误率是否随着变量值的变化而增加。依赖于分类算法、数据集和程序设置，分类器的输出结果可能有很大的不同。

五、使用算法构建完整可用的系统

至此我们可以针对用户输入的一些数据来进行有效的预测了,输入如下数据可以得到一个预测结果为 in small doses：

六、算法总结

K-近邻算法是分类数据最简单有效的算法，但是如果训练的数据量很大时必须消耗大量的存储空间，而且由于必须对数据集中的每一个数据计算距离值实际使用时可能非常耗时。

点我开启源码传送门！

如有问题请与我联系喔~请发送邮件到如下邮箱，我看到后会及时回复。

bubblyyi@outlook.com

欢迎转载，转载时请标明出。

查看更多文章请访问我的个人博客 www.bubblyyi.com

请喝咖啡☕️

 

打赏

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注