机器学习之分类算法一：K-近邻算法

一、K-近邻算法

    K-近邻算法是一种分类算法，分类算法是监督学习算法，监督学习算法和无监督学习算法的最大区别就是监督学习需要告诉机器一些正确的事物，也就是训练数据集，而无监督学习算法则不需要事先准备这些，比如聚类算法。

    所谓的分类，就是要求数据都是离散型（标称型）的，且是数值型的。一下子 说这么多概念术语很绕弯哈，数据从大的分类来说分为离散型（标称型）和连续型。离散的就是数据只能在有限的数据集中（比如：是/否，1/2/3，a/b /c，红/白/黑）,连续型的属于无限集（比如:全体实数集），对于离散型的适合采用分类器方式也就是分类算法解决，而连续型适合使用线性回归算法解决， 但这也不是绝对的。

    K-近邻算法的优点：精度高、对异常值不敏感（个别噪音数据对结果的影响不是很大）；缺点是：计算复杂度高、空间复杂度高（当数据维度变大，矩阵求距离运算相当耗时耗资源）；适用数据范围：数值型和标称型（求距离需要要求数据是数值类型）。

    我们就用教材中的例子 简单说一下该算法的工作原理，假设我有六部电影A（3,104，爱情片）、B（2,100，爱情片）、C（1,81，爱情片）、D（101,10，动作 片）、E（99,5，动作片）、F（98,2.动作片），其中第一个数字代表电影中打斗镜头次数、第二个数字代表亲吻镜头次数，那么现在有一个新电影 G（18,90，？），它属于爱情片还是动作片呢？其实我们一眼就能判断出来属于爱情片！理由呢？

    K-近邻算法采用的是求距离方式。A(x1,y1,z1)、B(x2,y2,z2)，则d=√(x2-x1)2+(y2-y1)2+(z2-z1)2

    计算结 果为（20.5,18.7,19.2,115.3,117.4,118.9），按距离由小到大排序，所谓的K-近邻就是选取最相近的K个，比如K=3，也 就是（18.7,19.2,20.5）对应的电影是B、C、A，他们中绝大多数都是爱情片（这里其实全部都是爱情片）。所以我们认为G就是爱情片。

    这就是K-近邻算法的工作原理。

    下面再把书中给出的一个示例结合代码给大家说一下怎么去编程。

    假 设我在坐标系中有四个点，分别是（1.0,1.1）、（1.0,1.0）、（0，0）、（0,0.1），这四个点分别是属于A、A、B、B类别。我们需要 预测（0,0）这个点属于什么类别，实际上（0,0）已经在已知的训练数据集中，这没关系，我们仅仅是做个小测试而已。

    给出的代码与教材中代码一致，不过初学者很难看懂每一步都是什么含义，所以我把一些注释加了上去。具体的运行流程可以参考教材中的步骤。当最终结果返回了“B”，证明我们是对的。