Machine Learning in Action:KNN Algorithm

概述

对于分类问题，最主要的任务就是找到对应数据合适的分类。而机器学习的另一项任务就是回归，比如CTR预测之类的。ml算法按照有无label可以分为有监督学习和无监督学习，对于无监督学习的算法比较经典的有聚类算法，有监督的相对来说较多，回归类算法基本都是的。按照参数有可以划分成有参数模型和无参数模型和半参数模型，有参数模型有两个特征，一个是用参数代表从训练数据中获得的信息，只有当target function包含在了hypothesis set里面才会收敛。无参数模型是没有参数的，直接存储所以的训练数据，也就是不再用参数代表训练数据，比如KNN，无训练过程，而且一定收敛。对于半参数模型，参数一定有，但是一定收敛，最经典的就是神经网络模型，神经网络模型在理论上是可以拟合所有的target function，所有只要训练数据够多，一定可以收敛，因为他的hypothesis set包含了所以的target function。 如何选择算法，需要考虑两个方面：首先是使用这个算法的目的是什么，想要完成什么任务，其次就是数据怎么来，规模多大。开放ml程序一般要经历一下步骤，首先是收集数据，准备输入数据，也就是数据预处理，分析输入数据，训练算法。

KNN Algorithm

KNN算法是属于近邻算法的一种，之前的Chapter 6一章就有专门提到。KNN的VC维是无穷的，但是效果缺不会差过最优分类器的两倍，Chapter 6博客中有证明。这个算法优点很明显，没有training cost，因为他根本没有训练过程，所以很简单，拿到直接上手预测，所以需要存储完整的训练数据来预测测试数据；预测精度高，对异常值不敏感，偶尔有几个值超出预期对于预测不会有太大影响；另外也没有数据的假定输入。 没有十全十美的事物，training cost其实不是没有了，而是转换到了预测阶段，而且空间复杂度高，需要每一次都计算distance然后sort by order。 工作原理就很简单了，首先找到一个样本数据集合，也称作训练样本集，并且样本中每一个数据都存在label，也就是知道每一个样本和分类之间的对应关系。输入新的数据后，会计算与当前新数据点最近的k个数据，最后选择k个样本中classification最多的组合，通常对于k的选择是不能被类数所整除，避免有两个类的voting是相同的，事实上就是相当于一个poll，投票选举。 计算前就涉及到了相似度的衡量，前面的文章也提到了。

伪代码

首先要计算已知类别数据集中的点与当前点之间的距离。 然后就是排序， 选取最近的K个点， 确定k个点钟类别出现的频率， 频率最高的类别就是当前新数据点的类别。 当然，K的选择一搬就是3，越高，其实越好，但是，你的回报是无法和计算代价所平衡。比如k = 3，accuracy = 97%，k = 5，accuracy = 97.1%，这样就很不值得了，不应该为百分之一的提升增加这么多的计算机消耗。

from numpy import *
import operator


class KNN(object):
    @staticmethod
    def classify(inX, dataSet, labels, k):
        datasetsize = dataSet.shape[0]
        diffmat = tile(inX, (datasetsize, 1)) - dataSet
        sqdiffMat = diffmat ** 2
        sqdistance = sqdiffMat.sum(axis=1)
        distance = sqdistance ** 0.5
        sortDistance = distance.argsort()
        classcount = {}
        for i in range(k):
            voteLabel = labels[sortDistance[i]]
            classcount[voteLabel] = classcount.get(voteLabel, 0) + 1
        sortclasscount = sorted(classcount.iteritems(), key=operator.itemgetter(1), reverse=True)
        return sortclasscount[0][0]

这就是具体实现。比较烦的就是上面的numpy.tile，这个方法是复制数组方法，第二个参数有两个(a,b)，意思是把第一个参数先纵向复制a次，再横向复制b次，这么做是因为要用一个数据点减去所以的训练集，这么多相同的直接复制就好了。

使用KNN改进约会网站配对效果

约会网站会提供三种类型的人选，不喜欢的人，魅力一般的人，极具魅力的人。

实现步骤 收集数据，拿到提供的文本数据 准备数据，使用Python来解析文本文件 分析数据，画图 训练算法，KNN是没有training的，所以可以忽略，也正因为如此，KNN算法的Ein永远是0 测试算法，用给出的数据做测试 使用算法，投入工程使用

准备数据

数据类似于这样，包含了三种特征，每年获得飞行常客的里程数，玩游戏视频所消耗时间百分比，每周冰淇淋公升数。 显示数据

    @staticmethod
    def drawDataSet(X, Y):
        fig = plt.figure()
        ax = fig.add_subplot(111)
        ax.scatter(X[:, 1], X[:, 2])
        plt.show()

这里只是使用了第一和第二个特征，加上类别颜色：

最后试一下之后会发现，23，13，12列得到的分布差不多一样的，只有12列是不同：

数据归一化

不同数据的大小算出来的距离是不一样的，第一个特征都是以千为单位，而后面两个feature相对较小，所以需要归一化把特征都转换成同一大小单位。

    @staticmethod
    def autoNorm(dataSet):
        minVals = dataSet.min(0)
        maxVals = dataSet.max(0)
        ranges = maxVals - minVals
        normDataset = np.zeros(shape(dataSet))
        m = dataSet.shape[0]
        normDataset = dataSet - tile(minVals, (m, 1))
        normDataset = normDataset / tile(ranges, (m, 1))
        return normDataset, ranges, minVals

测试数据

还是可以的

手写数字识别

所有的手写数字都是这个样子。预测效果，代码就不贴了，很普通。

还是可以的。但是KNN算法如果作用于对图片相似度的话可能不太好，因为图片相等的地方很大程度上是背景相同，有可能导致误识别。比如两张图片，一张是汽车，一张是飞机，两张图片都是大片的天空做背景的话可能就会出现问题。KNN算法是对于实例的学习，使用算法的时候必须接近实际数据的训练样本数据，而且要保存所有的数据，在数据过多的情况下可能导致computational cost，计算开销会很大。而且，他无法给出任何数据的基础结构信息，也无法知道平均实力样本和典例样本有什么特征。

最后附上所有GitHub代码：https://github.com/GreenArrow2017/MachineLeariningnAction