knn算法的优化之手肘法

‘壹’ 01 KNN算法 - 概述

KNN算法 全称是K近邻算法 （K-nearst neighbors，KNN）

KNN是一种基本的机器学习算法，所谓K近邻，就是k个最近的邻居。即每个样本都可以用和它 最接近的k个邻近位置的样本 来代替。

KNN是个相对比较简单的算法，比起之前提过的回归算法和分类算法更容易。如果一个人从来没有接触过机器学习的算法，拿到数据后最容易想到的分类方式就是K近邻。打个比方：你们想了解我是个怎样的人，然后你们发现我的身边关系最密切的朋友是一群逗逼，所以你们可以默认我也是一个逗逼。

KNN算法即可以应用于 分类算法 中，也可以应用于 回归算法 中。

KNN在做回归和分类的主要区别，在于最后做预测时候的决策不同。在分类预测时，一般采用 多数表决法 。在做回归预测时，一般使用 平均值法 。

多数表决法： 分类时，哪些样本离我的目标样本比较近，即目标样本离哪个分类的样本更接近。

平均值法： 预测一个样本的平均身高，观察目标样本周围的其他样本的平均身高，我们认为平均身高是目标样本的身高。

再举个例子：
分别根据甜度和脆度两个特征来判断食物的种类。
根据样本我们普遍发现：
比较甜，比较脆的食物都是水果。
不甜，不太脆的食物是蛋白质。
不甜，比较脆的食物是蔬菜。
于是根据目标的样本甜度和脆度两个特征，我们可以对其进行分类了。

k值的选择:
先选一个较小的值，然后通过交叉验证选择一个合适的最终值。
k越小，即使用较小的领域中的样本进行预测，训练误差会减小，但模型会很复杂，以至于过拟合。
k越大，即使用交大的领域中的样本进行预测，训练误差会增大，模型会变得简单，容易导致欠拟合。

距离的度量:
使用欧几里得距离：欧几里得度量（euclidean metric）（也称欧氏距离）是一个通常采用的距离定义，指在m维空间中两个点之间的真实距离，或者向量的自然长度（即该点到原点的距离）。在二维和三维空间中的欧氏距离就是两点之间的实际距离。

决策规划:
分类：多数表决法、加权多数表决法。
回归：平均值法、加权平均值法。

加权多数表决法：

平均值法和加权平均值法：
同样看上面的图，上方的三个样本值为3，下面两个样本值为2，预测？的值。
如果不考虑加权，直接计算平均值：
(3 * 3 + 2 * 2) / 5 = 2.6

加权平均值：权重分别为1/7和2/7。计算加权平均值：
(3 * 3* 1/7 + 2 * 2 * 2/7) / 5 = 2.43

1、蛮力实现(brute)：
计算预测样本到所有训练集样本的距离，然后选择最小的k个距离，即可得到k个最邻近点。
缺点：当特征数多、样本数多时，算法的效率比较低。

2、KD树 (kd_tree)：
首先对训练数据进行建模，构建KD树，然后根据建好的模型来获取邻近样本数据。
后续内容会介绍KD树搜索最小值的方式，让大家直观感受到KD树比蛮力实现要少检索多少数据。

‘贰’ 邻近算法的改进策略

kNN算法因其提出时间较早，随着其他技术的不断更新和完善，kNN算法的诸多不足之处也逐渐显露，因此许多kNN算法的改进算法也应运而生。
针对以上算法的不足，算法的改进方向主要分成了分类效率和分类效果两方面。
分类效率：事先对样本属性进行约简，删除对分类结果影响较小的属性，快速的得出待分类样本的类别。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。
分类效果：采用权值的方法（和该样本距离小的邻居权值大）来改进，Han等人于2002年尝试利用贪心法，针对文件分类实做可调整权重的k最近邻居法WAkNN (weighted adjusted k nearest neighbor)，以促进分类效果；而Li等人于2004年提出由于不同分类的文件本身有数量上有差异，因此也应该依照训练集合中各种分类的文件数量，选取不同数目的最近邻居，来参与分类。

‘叁’ KNN算法-4-算法优化-KD树

KNN算法的重要步骤是对所有的实例点进行快速k近邻搜索。如果采用线性扫描（linear scan），要计算输入点与每一个点的距离，时间复杂度非常高。因此在查询操作时，可以使用kd树对查询操作进行优化。

Kd-树是K-dimension tree的缩写，是对数据点在k维空间（如二维(x，y)，三维(x，y，z)，k维(x1，y，z..)）中划分的一种数据结构，主要应用于多维空间关键数据的搜索（如：范围搜索和最近邻搜索）。本质上说，Kd-树就是一种平衡二叉树。

k-d tree是每个节点均为k维样本点的二叉树，其上的每个样本点代表一个超平面，该超平面垂直于当前划分维度的坐标轴，并在该维度上将空间划分为两部分，一部分在其左子树，另一部分在其右子树。即若当前节点的划分维度为d，其左子树上所有点在d维的坐标值均小于当前值，右子树上所有点在d维的坐标值均大于等于当前值，本定义对其任意子节点均成立。

必须搞清楚的是，k-d树是一种空间划分树，说白了，就是把整个空间划分为特定的几个部分，然后在特定空间的部分内进行相关搜索操作。想象一个三维(多维有点为难你的想象力了)空间，kd树按照一定的划分规则把这个三维空间划分了多个空间，如下图所示：

首先，边框为红色的竖直平面将整个空间划分为两部分，此两部分又分别被边框为绿色的水平平面划分为上下两部分。最后此4个子空间又分别被边框为蓝色的竖直平面分割为两部分，变为8个子空间，此8个子空间即为叶子节点。

常规的k-d tree的构建过程为：

对于构建过程，有两个优化点：

例子：采用常规的构建方式，以二维平面点(x,y)的集合(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2) 为例结合下图来说明k-d tree的构建过程：

如上算法所述，kd树的构建是一个递归过程，我们对左子空间和右子空间内的数据重复根节点的过程就可以得到一级子节点（5,4）和（9,6），同时将空间和数据集进一步细分，如此往复直到空间中只包含一个数据点。

如之前所述，kd树中，kd代表k-dimension，每个节点即为一个k维的点。每个非叶节点可以想象为一个分割超平面，用垂直于坐标轴的超平面将空间分为两个部分，这样递归的从根节点不停的划分，直到没有实例为止。经典的构造k-d tree的规则如下：

kd树的检索是KNN算法至关重要的一步，给定点p，查询数据集中与其距离最近点的过程即为最近邻搜索。

如在构建好的k-d tree上搜索(3,5)的最近邻时，对二维空间的最近邻搜索过程作分析。

首先从根节点(7,2)出发，将当前最近邻设为(7,2)，对该k-d tree作深度优先遍历。

以(3,5)为圆心，其到(7,2)的距离为半径画圆（多维空间为超球面），可以看出(8,1)右侧的区域与该圆不相交，所以(8,1)的右子树全部忽略。

接着走到(7,2)左子树根节点(5,4)，与原最近邻对比距离后，更新当前最近邻为(5,4)。

以(3,5)为圆心，其到(5,4)的距离为半径画圆，发现(7,2)右侧的区域与该圆不相交，忽略该侧所有节点，这样(7,2)的整个右子树被标记为已忽略。

遍历完(5,4)的左右叶子节点，发现与当前最优距离相等，不更新最近邻。所以(3,5)的最近邻为(5,4)。

举例：查询点（2.1,3.1）

星号表示要查询的点（2.1,3.1）。通过二叉搜索，顺着搜索路径很快就能找到最邻近的近似点，也就是叶子节点（2,3）。而找到的叶子节点并不一定就是最邻近的，最邻近肯定距离查询点更近，应该位于以查询点为圆心且通过叶子节点的圆域内。为了找到真正的最近邻，还需要进行相关的‘回溯'操作。也就是说，算法首先沿搜索路径反向查找是否有距离查询点更近的数据点。

举例：查询点（2，4.5）

一个复杂点了例子如查找点为（2，4.5），具体步骤依次如下：

上述两次实例表明，当查询点的邻域与分割超平面两侧空间交割时，需要查找另一侧子空间，导致检索过程复杂，效率下降。

一般来讲，最临近搜索只需要检测几个叶子结点即可，如下图所示：

但是，如果当实例点的分布比较糟糕时，几乎要遍历所有的结点，如下所示：

研究表明N个节点的K维k-d树搜索过程时间复杂度为： 。

同时，以上为了介绍方便，讨论的是二维或三维情形。但在实际的应用中，如SIFT特征矢量128维，SURF特征矢量64维，维度都比较大，直接利用k-d树快速检索（维数不超过20）的性能急剧下降，几乎接近贪婪线性扫描。假设数据集的维数为D，一般来说要求数据的规模N满足N»2D，才能达到高效的搜索。

Sklearn中有KDTree的实现，仅构建了一个二维空间的k-d tree，然后对其作k近邻搜索及指定半径的范围搜索。多维空间的检索，调用方式与此例相差无多。

‘肆’ 什么叫做knn算法

在模式识别领域中，最近邻居法（KNN算法，又译K-近邻算法）是一种用于分类和回归的非参数统计方法。

在这两种情况下，输入包含特征空间（Feature Space）中的k个最接近的训练样本。

1、在k-NN分类中，输出是一个分类族群。一个对象的分类是由其邻居的“多数表决”确定的，k个最近邻居（k为正整数，通常较小）中最常见的分类决定了赋予该对象的类别。若k=1，则该对象的类别直接由最近的一个节点赋予。

2、在k-NN回归中，输出是该对象的属性值。该值是其k个最近邻居的值的平均值。

最近邻居法采用向量空间模型来分类，概念为相同类别的案例，彼此的相似度高，而可以借由计算与已知类别案例之相似度，来评估未知类别案例可能的分类。

K-NN是一种基于实例的学习，或者是局部近似和将所有计算推迟到分类之后的惰性学习。k-近邻算法是所有的机器学习算法中最简单的之一。

无论是分类还是回归，衡量邻居的权重都非常有用，使较近邻居的权重比较远邻居的权重大。例如，一种常见的加权方案是给每个邻居权重赋值为1/ d，其中d是到邻居的距离。

邻居都取自一组已经正确分类（在回归的情况下，指属性值正确）的对象。虽然没要求明确的训练步骤，但这也可以当作是此算法的一个训练样本集。

k-近邻算法的缺点是对数据的局部结构非常敏感。

K-均值算法也是流行的机器学习技术，其名称和k-近邻算法相近，但两者没有关系。数据标准化可以大大提高该算法的准确性。

参数选择

如何选择一个最佳的K值取决于数据。一般情况下，在分类时较大的K值能够减小噪声的影响，但会使类别之间的界限变得模糊。一个较好的K值能通过各种启发式技术（见超参数优化）来获取。

噪声和非相关性特征的存在，或特征尺度与它们的重要性不一致会使K近邻算法的准确性严重降低。对于选取和缩放特征来改善分类已经作了很多研究。一个普遍的做法是利用进化算法优化功能扩展，还有一种较普遍的方法是利用训练样本的互信息进行选择特征。

在二元（两类）分类问题中，选取k为奇数有助于避免两个分类平票的情形。在此问题下，选取最佳经验k值的方法是自助法。

‘伍’ 聚类算法--KMeans

    与分类、序列标注等任务不同，聚类是在事先并不知道任何样本标签的情况下，通过数据之间的内在关系把样本划分为若干类别，使得同类别样本之间的相似度高，不同类别之间的样本相似度低(即增大类内聚，减少类间距)。    

    聚类属于非监督学习，K均值聚类是最基础常用的聚类算法。它的基本思想是，通过迭代寻找K个簇(Cluster)的一种划分方案，使得聚类结果对应的损失函数最小。其中，损失函数可以定义为各个样本距离所属簇中心点的误差平方和。

其中 代表第i个样本， 是 所属的簇，  代表簇对应的中心点，M是样本总数。

相关概念：

    K值： 要得到的簇的个数。

    质心： 每个簇的均值向量。即向量各维取平均即可。

    距离量度： 常用欧几里得距离和余弦相似度(先标准化)。

    KMeans的主要思想是：在给定K值和K个初始类簇中心点的情况下，把每个点(亦即数据记录)分到离其最近的类簇中心点所代表的类簇中，所有点分配完毕之后，根据一个类簇内的所有点重新计算该类簇的中心点(取平均值)，然后再迭代的进行分配点和更新类簇中心点的步骤，直至类簇中心点的变化很小，或者达到指定的迭代次数。

    KMeans的核心目标是将给定的数据集划分成K个簇(K是超餐)，并给出每个样本数据对应的中心点。具体步骤非常简单：

    （1）首先确定一个K值，即我们希望将数据集经过聚类得到k个集合。

    （2）从数据集中随机选择K个数据点作为质心。

    （3）对数据集中每一个点，计算其与每一个质心的距离(如欧式距离)，离哪个质心近，就划分到哪个质心所属的集合。

    （4）把所有数据归好集合后，一共有K个集合。然后重新计算每个集合的质心。

    （5）如果新计算出来的质心和原来的质心之间的距离小于某一个设置的阈值(表示重新计算的质心的位置变化不大，趋于稳定，或者说收敛)，我们可以认为聚类已经达到期望的结果，算法终止。

    （6）如果新质心和原质心距离变化很大，需要迭代3-5步骤。

KMeans最核心的部分是先固定中心点，调整每个样本所属的类别来减少J；再固定每个样本的类别，调整中心点继续减小J。两个过程交替循环，J单调递减直到极小值，中心点和样本划分的类别同时收敛。

KMeans的优点 ：

 高效可伸缩，计算复杂度为O(NKt)接近于线性(N是数据量，K是聚类总数，t是迭代轮数)。

 收敛速度快，原理相对通俗易懂，可解释性强。

当结果簇是密集的，而簇与簇之间区别是明显时，他的效果较好。主要需要调参的参数仅仅是簇数K。

缺点 ：

 受初始值和异常点影响，聚类结果可能不是全局最优而是局部最优。K-Means算法对初始选取的质心点是敏感的，不同的随机种子点得到的聚类结果完全不同，对结果影响很大。

 K是超参数，一般需要按经验选择。

 对噪音和异常点比较的敏感，用来检测异常值。

 只能发现球状的簇。在K-Means中，我们用单个点对cluster进行建模，这实际上假设各个cluster的数据是呈高维球型分布的，但是在生活中出现这种情况的概率并不算高。例如，每一个cluster是一个一个的长条状的，K-Means的则根本识别不出来这种类别( 这种情况可以用GMM )。实际上，K-Means是在做凸优化，因此处理不了非凸的分布。

根据以上特点，我们可以从下面几个角度对算法做调优。

（1）数据预处理：归一化和异常点过滤

    KMeans本质是一种基于欧式距离度量的数据划分方法，均值和方差大的维度将对数据的聚类结果产生决定性影响 。所以在聚类前对数据( 具体的说是每一个维度的特征 )做归一化和单位统一至关重要。此外，异常值会对均值计算产生较大影响，导致 中心偏移 ，这些噪声点最好能提前过滤。

（2）合理选择K值

    K值的选择一般基于实验和多次实验结果。例如采用 手肘法 ，尝试不同K值并将对应的损失函数画成折线。手肘法认为图上的 拐点就是K的最佳值 (k=3)。

为了将寻找最佳K值的过程自动化，研究人员提出了Gap Statistic方法。不需要人们用肉眼判断，只需要找到最大的Gap Statistic对应的K即可。

       损失函数记为  ，当分为K类时，Gap Statistic定义为：  。 是 的期望 ，一般由蒙特卡洛模拟产生。我们在样本所在的区域内按照均匀分布随机地产生和原始样本数一样多的随机样本，并对这个随机样本做KMeans，得到一个 ，重复多次就可以计算出 的近似值。

       的物理含义是随机样本的损失与实际样本的损失之差。Gap越大说明聚类的效果越好 。一种极端情况是，随着K的变化 几乎维持一条直线保持不变。说明这些样本间没有明显的类别关系，数据分布几乎和均匀分布一致，近似随机。此时做聚类没有意义。

（3）改进初始值的选择

    之前我们采用随机选择K个中心的做法，可能导致不同的中心点距离很近，就需要更多的迭代次数才能收敛。如果在选择初始中心点时能 让不同的中心尽可能远离 ，效果往往更好。这类算法中，以K-Means++算法最具影响力。

（4）采用核函数

    主要思想是通过一个非线性映射，将输入空间中的数据点映射到高维的特征空间中，并在新的空间进行聚类。非线性映射增加了数据点线性可分的概率(与SVM中使用核函数思想类似)对于非凸的数据分布可以达到更为准确的聚类结果。

 (1）初始的K个质心怎么选？

    最常用的方法是随机选，初始质心的选取对最终聚类结果有影响，因此算法一定要多执行几次，哪个结果更合理，就用哪个结果。当然也有一些优化的方法，第一种是选择彼此距离最远的点，具体来说就是先选第一个点，然后选离第一个点最远的当第二个点，然后选第三个点，第三个点到第一、第二两点的距离之和最小，以此类推。第二种是先根据其他聚类算法(如层次聚类)得到聚类结果，从结果中每个分类选一个点

（2）关于离群值？

    离群值就是远离整体的，非常异常、非常特殊的数据点，在聚类之前应该将这些"极大""极小"之类的离群数据都去掉，否则会对于聚类的结果有影响。但是，离散值往往自身就很有分析的价值，可以把离群值单独作为一类来分析。

（3）单位要一致！

（4）标准化

    数据中X整体都比较小，比如都是1到10之间的数，Y很大，比如都是1000以上的数，那么在计算距离的时候Y起到的作用就比X大很多，X对于距离的影响几乎可以忽略，这也有问题。因此，如果K-Means聚类中选择欧几里得距离计算距离，数据集又出现了上面所述的情况，就一定要进行数据的标准化(normalization)，即将数据按比例缩放，使之落入一个小的特定区间。

    K-Means是无监督学习的聚类算法，没有样本输出；而KNN是监督学习的分类算法，有对应的类别输出 。KNN基本不需要训练，对测试集里面的点，只需要找到在训练集中最近的K个点，用这最近的K个点的类别来决定测试点的类别。而K-Means则有明显的训练过程，找到K个类别的最佳质心，从而决定样本的簇类别。当然，两者也有一些相似点，两个算法都包含一个过程，即找出和某一个点最近的点。 两周都利用了最近邻的思想 。

‘陆’ R语言-KNN算法

1、K最近邻(k-NearestNeighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。

2、KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。

3、KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。

简言之，就是将未标记的案例归类为与它们最近相似的、带有标记的案例所在的类 。

原理及举例

工作原理：我们知道样本集中每一个数据与所属分类的对应关系，输入没有标签的新数据后，将新数据与训练集的数据对应特征进行比较，找出“距离”最近的k（通常k<20）数据，选择这k个数据中出现最多的分类作为新数据的分类。

算法描述

1、计算已知数据集中的点与当前点的距离

2、按距离递增次序排序

3、选取与当前数据点距离最近的K个点

4、确定前K个点所在类别出现的频率

5、返回频率最高的类别作为当前类别的预测

距离计算方法有"euclidean"（欧氏距离）,”minkowski”（明科夫斯基距离）, "maximum"（切比雪夫距离）, "manhattan"（绝对值距离）,"canberra"（兰式距离）, 或 "minkowski"（马氏距离）等

Usage

knn(train, test, cl, k = 1, l = 0, prob =FALSE, use.all = TRUE)

Arguments

train

matrix or data frame of training set cases.

test

matrix or data frame of test set cases. A vector will  be interpreted as a row vector for a single case.

cl

factor of true classifications of training set

k

number of neighbours considered.

l

minimum vote for definite decision, otherwisedoubt. (More precisely, less thank-ldissenting votes are allowed, even

ifkis  increased by ties.)

prob

If this is true, the proportion of the votes for the

winning class are returned as attributeprob.

use.all

controls handling of ties. If true, all distances equal

to thekth largest are

included. If false, a random selection of distances equal to thekth is chosen to use exactlykneighbours.

kknn(formula = formula(train), train, test, na.action = na.omit(), k = 7, distance = 2, kernel = "optimal", ykernel = NULL, scale=TRUE, contrasts = c('unordered' = "contr.mmy", ordered = "contr.ordinal"))

参数：

formula                            A formula object.

train                                 Matrix or data frame of training set cases.

test                                   Matrix or data frame of test set cases.

na.action                         A function which indicates what should happen when the data contain ’NA’s.

k                                       Number of neighbors considered.

distance                          Parameter of Minkowski distance.

kernel                              Kernel to use. Possible choices are "rectangular" (which is standard unweighted knn), "triangular", "epanechnikov" (or beta(2,2)), "biweight" (or beta(3,3)), "triweight" (or beta(4,4)), "cos", "inv", "gaussian", "rank" and "optimal".

ykernel                            Window width of an y-kernel, especially for prediction of ordinal classes.

scale                                Logical, scale variable to have equal sd.

contrasts                         A vector containing the ’unordered’ and ’ordered’ contrasts to use

kknn的返回值如下：

fitted.values              Vector of predictions.

CL                              Matrix of classes of the k nearest neighbors.

W                                Matrix of weights of the k nearest neighbors.

D                                 Matrix of distances of the k nearest neighbors.

C                                 Matrix of indices of the k nearest neighbors.

prob                            Matrix of predicted class probabilities.

response                   Type of response variable, one of continuous, nominal or ordinal.

distance                     Parameter of Minkowski distance.

call                              The matched call.

terms                          The ’terms’ object used.

iris%>%ggvis(~Length,~Sepal.Width,fill=~Species)

library（kknn）
data（iris）

dim(iris)

m<-(dim(iris))[1]
val<-sample(1:m,size=round(m/3）,replace=FALSE,prob=rep(1/m,m))

建立训练数据集

data.train<-iris[-val,]

建立测试数据集

data.test<-iris[val,]

调用kknn  之前首先定义公式

formula ： Species ~ Sepal.Length + Sepal.Width + Petal.Length + Petal.Width

iris.kknn<-kknn(Species~.,iris.train,iris.test,distance=1,kernel="triangular")

summary(iris.kknn)

# 获取fitted.values

fit <- fitted(iris.kknn)

# 建立表格检验判类准确性

table(iris.valid$Species, fit)
# 绘画散点图，k-nearest neighbor用红色高亮显示

pcol <- as.character(as.numeric(iris.valid$Species))

pairs(iris.valid[1:4], pch = pcol, col = c("green3", "red")[(iris.valid$Species != fit)+1]

二、R语言knn算法

install.packages("class")

library(class)

对于新的测试样例基于距离相似度的法则，确定其K个最近的邻居，在K个邻居中少数服从多数

确定新测试样例的类别

1、获得数据

2、理解数据

对数据进行探索性分析，散点图

如上例

3、确定问题类型，分类数据分析

4、机器学习算法knn

5、数据处理，归一化数据处理

normalize <- function(x){

num <- x - min(x)

denom <- max(x) - min(x)

return(num/denom)

}

iris_norm <-as.data.frame(lapply(iris[,1:4], normalize))

summary(iris_norm)

6、训练集与测试集选取

一般按照3:1的比例选取

方法一、set.seed(1234)

ind <- sample(2,nrow(iris), replace=TRUE, prob=c(0.67, 0.33))

iris_train <-iris[ind==1, 1:4]

iris_test <-iris[ind==2, 1:4]

train_label <-iris[ind==1, 5]

test_label <-iris[ind==2, 5]

方法二、

ind<-sample(1:150,50)

iris_train<-iris[-ind,]

iris_test<-iris[ind,1:4]

iris_train<-iris[-ind,1:4]

train_label<-iris[-ind,5]

test_label<-iris[ind,5]

7、构建KNN模型

iris_pred<-knn(train=iris_train,test=iris_test,cl=train_label,k=3)

8、模型评价

交叉列联表法

table（test_label,iris_pred)

实例二

数据集

http://archive.ics.uci.e/ml/machine-learning-databases/breast-cancer-wisconsin/wdbc.data

导入数据

dir <-'http://archive.ics.uci.e/ml/machine-learning-databases/breast-cancer-wisconsin/wdbc.data'wdbc.data <-read.csv(dir,header = F)

names(wdbc.data) <- c('ID','Diagnosis','radius_mean','texture_mean','perimeter_mean','area_mean','smoothness_mean','compactness_mean','concavity_mean','concave points_mean','symmetry_mean','fractal dimension_mean','radius_sd','texture_sd','perimeter_sd','area_sd','smoothness_sd','compactness_sd','concavity_sd','concave points_sd','symmetry_sd','fractal dimension_sd','radius_max_mean','texture_max_mean','perimeter_max_mean','area_max_mean','smoothness_max_mean','compactness_max_mean','concavity_max_mean','concave points_max_mean','symmetry_max_mean','fractal dimension_max_mean')

table(wdbc.data$Diagnosis)## M = malignant, B = benign

wdbc.data$Diagnosis <- factor(wdbc.data$Diagnosis,levels =c('B','M'),labels = c(B ='benign',M ='malignant'))

‘柒’ kNN（k-NearestNeighbor）算法

参考《数据挖掘10大算法》对kNN算法进行基本总结，附有一个Python3的简例。

基本思想
从训练集中找出 k 个最接近测试对象的训练对象，再从这 k 个对象中找出居于主导的类别，将其赋给测试对象。

定位
由于这种总体占优的决策模式，对于类域的交叉、重叠较多的或者多模型、多标签的待分样本集来说，kNN方法较其他方法更为适合。kNN算法属于有监督学习的分类算法。

避开了两个问题
（1）分类时对象之间不可能完全匹配（kNN方法计算的是对象之间的距离）；
（2）具有相同属性的对象有不同的类别（kNN方法依据总体占优的类别进行决策，而不是单一对象的类别进行决策）。

需要考虑几个关键要素
（1）训练集；
（2）用于计算对象之间临近的程度或者其他相似的指标；
（3）最近邻的个数 k；
（4）基于 k 个最近邻及其类别对目标对象类别进行判定的方法。

kNN方法很容易理解和实现，在一定条件下，其分类错误率不会超过最优贝叶斯错误率的两倍。一般情况下，kNN方法的错误率会逐渐收敛到最优贝叶斯错误率，可以用作后者的近似。

基本算法

算法的存储复杂度为O(n)，时间复杂度为O(n)，其中 n 为训练对象的数量。

影响kNN算法性能的几个关键因素
（1）k 值的选择；
如果 k 值选得过小，结果就会对噪声点特别敏感；k 值选得过大就会使得近邻中包含太多别的类的点。最佳 k 值的估计可以使用交叉验证的方法。通常，使用 k=1会有一个比较好的结果（特别是对于小数据集的情况）。但是，在样本很充足的情况下，选择较大的 k 值可以提高抗噪能力。

（2）类别决策时的综合方法；
对目标对象的类别进行决策，最简单的就是使用总体占优方法（简单投票，票数最多的一类胜出）。稍微复杂一点，考虑近邻中每个点与目标对象的距离不同，对决策的份量进行加权考虑。

（3）距离测量标准的选择。
距离测量的标准一般选择 欧几里得距离 或者 曼哈顿距离 。

简单例子