《机器学习实战》学习（1）—— kNN算法

一些碎碎念：失踪人口回归（虽然也没人fo我，一个人自娱自乐啦）。新学期开始好久了，感觉需要系统性地学习一些东西，扫了一眼书架发现之前买的《机器学习实战》这本书还没看完，于是从这本书开始搭建自己的机器学习基础体系啦，顺便学习一下python。如果正文有什么描述不对的地方，麻烦给与指正啦...争取周更，不能拖拉。

star了一个github项目（本书配套代码） https://github.com/pbharrin/machinelearninginaction

kNN算法是分类算法，主要是通过测量比较 输入测试数据 与 分类过的训练数据 的（特征）距离 进行分类的。当输入一个新的未分类（没有标签）的数据时，与样本集中的数据特征进行比较，选出与新数据最接近的k个数据，将出现频率最高的分类作为新数据的分类。

首先需要对数据进行处理，数据清洗和归一化，数据清洗是为了剔除异常数据，归一化是为了使各个特征不受数据取值大小的影响，当然也可以根据数据的重要性定权重。

以下是kNN的核心代码：

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()
    classCout = {}
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCout[voteIlabel] = classCout.get(voteIlabel, 0) + 1
    sortedClassCout = sorted(classCout.items(),
                             key = operator.itemgetter(1), reverse = True)
    return sortedClassCout[0][0]

其中inX是输入数据（向量形式），dataSet和labels分别是样本数据和标签（分类），k是参与评价的点数。

代码首先求了输入数据与样本数据的距离，然后对距离排序，选出距离最近的k个点，返回k点内出现频率最高的标签作为分类结果。

此处距离的求解方法是欧式距离，还可以选用其他距离公式，视具体数据情况为定。

kNN简单有效但是当数据集较大时，所需内存和计算量也较大，也不能体现出各个数据特征之间的区别，这种分类方法还是十分硬核的，适用于简单的情况。