7.2k-最邻近分类算法
k-最邻近分类算法
[P1] 上一节我们说到，分类算法第一步就是分类学习，通过对已知的训练数据学习，从而拟合出一个数据模型函数，我们用这个函数来计算后续数据的分类结果。但问题是，数据模型函数到底应该怎么样呢? 我们这里就给大家介绍一种简单的数据分类方法，K最近邻分类算法。
[P2] 我们这节主要是给大家介绍 K最近邻分类算法 的原理，以及它对应的计算过程。
[P3] 假设数据集中的每一个数据，有n个属性，我们把这个n个属性想象为空间坐标，那么数据集中的每一个数据都是n维空间中的一个数据点。整个数据集其实就是一批数据点，分布在这个n维空间中。大家可以想象围棋的棋盘上分布了很多的棋子，这些棋子都是二维属性，分别是X轴和Y轴。现在，来了一个新的未知数据，我们把它按属性放到这个n维空间中去，然后，在n维空间中，我们找出离它最近的k个点，看看最近的这 k 个点分别是属于什么分类的，最多的那个分类我们就赋予这个新的未知数据，这个数据因而就有了自己的分类。这其实就和我们说的，近朱者赤，近墨者黑，是一个意思，它离谁最近，我们就认为它们是一样的分类。
[P4] K最近邻，是一种常用于分类的算法，是较为简单的经典机器学习算法之一。这个算法的基本原理，就是近朱者赤，近墨者黑，我们只要知道一个新的点离谁最近，我们就知道这个点是属于什么分类。在这里我们也可以看到，K近邻算法 要能够执行，前提是，你已经有一批已知分类的数据点存在了，然后才能把新的数据和这些已知数据去比较分类，最终得到新数据的分类。
[P5] 这个图比较好的演示了K近邻算法的原理。蓝色方形样本和红色三角形样本为已知分类样本。若使用K近邻算法对图中绿色圆形未知分类样本进行分类，当K=3时，其最近的3个点中，有2个红色三角形和1个蓝色方形，因此预测该待分类样本为红色三角形；当K=5时，其最近的5个点中，有3个红色三角形和2个蓝色方形，因此预测该待分类样本为蓝色方形。从这个例子我们也可以看到，K的选值不同，可能得到完全不同的结果。
[P6] 上面的例子，我们可以看出K近邻算法是需要一些条件才能运行的。首先，我们要有一个数据集，这个数据集我们一般称作训练集，样本数据集。这种数据集中每个样本都是有标签的，即我们知道样本数据集中每一个样本的分类。当一个没有标签的待分类样本出现时，算法将待分类样本与样本数据集中的每一个样本进行比较，找到与当前样本最为相近的K个样本，并获取这K个样本的标签，最后，选择这K个样本标签中中出现次数最多的分类，作为待分类样本的分类。因此，K近邻算法可行的基础是，存在数据集，并且数据集中的数据都是有分类的。
[P7] 样本的向量表示：即不管是当前已知的样本数据集，还是将来可能出现的待分类样本，都必须可以用向量的形式加以表征。样本的向量表现形式，构筑了问题的解空间，即囊括了样本所有可能出现的情况。向量的每一个维度，刻画样本的一个特征，必须是量化的，可比较的。有了向量的表示，我们才能描述样本在空间的位置，也就才能计算两个样本的距离，从而得到谁和样本距离最近。
[P8] 样本间距离的计算方法：既然要找到待分类样本在当前样本数据集中与自己距离最近的K个邻居，必然就要确定样本间的距离计算方法。样本间距离的计算方法的构建，与样本的向量表示方法有关，当建立样本的向量表示方法时，必须考虑其是否便于样本间距离的计算。因此，样本的向量表示与样本间距离的计算方法，两者相辅相成。常用的距离计算方法有：欧氏距离、余弦距离、汉明距离、曼哈顿距离等等。欧式距离就是我们在几何数学中学过的，两个点都有坐标，然后利用它们的坐标计算它们的物理距离。总结来说，K近邻算法需要的条件，第一是 有一组已知结果的样本数据，第二是 每个数据都可以用向量表示，第三是 通过每个数据的向量，确定一种计算两个数据距离的方法，从而可以挑选出最近距离的相似点。
[P9] K近邻模型 有三个基本要素，分别是 距离度量、K值的选择、和分类决策规则。距离度量前面我们说了，目前主流的计算距离的方法有
欧氏距离、余弦距离、汉明距离、曼哈顿距离等。针对不同的数据场景和数据特性，我们需要选择对应的距离计算方法。比如，如果是线性数据，那一般选择欧式距离比较好，但如果做文本分类时一般使用余弦相似性会比较好，具体场景需要具体分析和选择。
[P10] K近邻模型 三个基本要素的第二个，就是 K值如何选择。前面的蓝色方块和红色三角形例子，我们也看到了，不同的K值选择会直接导致结果完全不一样。k 值的选择不是一个平凡的问题，而且对于分类的精确度影响很大：k 值选取过小，算法容易受到一些噪音点的影响；k 值选取过大，则在数量上占优的类别会具有统治性的优势。例如，以“守信–失信”分类问题为例。如果训练集中守信者有 4 万名，失信者只有 1219 名，那么如果选择一个比较大的 k 值，新对象可能几乎都会被判断为守信者，因为与守信者成为近邻的概率太大了。
[P11] K近邻模型 三个基本要素的第三个，就是分类决策规则。就是我们得到了一批近邻，那我们用什么策略来确定当前数据的分类呢，大部分时候，我们采用少数服从多数的策略，也就是这一批近邻中，多数近邻属于哪个分类，那我们的当前数据就被分配到这个分类。
[P12] 这是算法的描述。给定一个训练数据集 S，里面有 t1 到 ts 个数据，再给定这些数据对应的分类，从 C1 到 Cm 。这些给的数据，构造了一个空间，每一个数据都是这个空间的一个点。现在，新来了一个数据样本 Ti，如果存在一个分类 Cj，使得数据点 Ti 在分类 Cj 上的相似度比 Ti 和另外别的分类的相似度都高，那么我们就把 Ti 分配到 Cj 这个分类上。
[P13] 其中 sim(Ti, Cj) 被称为相似性。在实际的计算中往往用距离来表征相似性，距离越近，相似性越大，距离越远，相似性越小。距离的计算方法有多种，最常用的是欧几里德距离。对于一个样本 ti，若 Cj 类的特征样本为 tj，则 ti 与 Cj 的欧几里德距离定义为：他们所有属性的差值的平方累加，然后开根号，这就是我们在几何数学上学过的坐标系中两点的距离公式。通过计算 Ti 和任意已知点的距离，我们就能得到一组K个最近的点，然后根据这批点已知的分类就能确定 Ti 的分类。
[P14] k最邻近分类算法的基本过程是，对于含有 s 个元组的训练数据库 S，要对新样本 t 进行分类。第一步，先求出 t 与 S 中所有训练样本 ti 的距离 ，也就是 t 到每一个训练节点的距离，并对所有求出的距离递增排序。第二步，选取前 k 个样本集合 N，统计 N 中每个类别出现的次数，其中最大类别的 C 作为新样本 t 的分类类别。
[P15] 这里是一个具体的例子。以表中所示的人员信息作为样本数据。假设 k=5，并只用 身高 属性作为距离计算属性。采用 k邻近分类算法对 Pat，女，1.6 进行分类的过程如下，我们逐个扫描表中的数据，计算身高距离，例如 Jim 男 的身高是 2米，和我们的样本数据 1.6米，距离是 0.4 米。所有数据按照这样进行计算。
[P16] 以身高作为距离，按照前面的计算过程，我们取距离最近的 5 个点，如表中所示。现在有了距离最近的 5 个点，我们对这 5 个点的分类做统计，5个人中，有4个人的分类是矮，1个人的分类是中等，按照少数服从多数的决策原则，我们定义新的这个样本分类为 矮。到这里，我们就完成了这个新样本的 K近邻分类。
[P17] 这里是算法的具体代码实现，大家可以自己具体看一下这里的代码描述，我们就不再细说了。
[P18] 最后总结一下，K近邻算法 首先要求有一组训练数据，这组数据有 N 个属性构成 N 维空间，并且这写数据我们已经知道它们的具体分类。现在对新的数据做分类，我们只需要计算新数据在 N 维空间中距离最近的 K 个点，对这 K 个距离最近的点统计它们的 分类，把其中分类占比最高的作为新数据的分类即可。