knn算法c
1. K-means 与KNN 聚类算法
K-means 算法属于聚类算法的一种。聚类算法就是把相似的对象通过静态分类方法分成不同的组别或者更多的子集（subset），这样让在同一个子集中的成员对象都有相似的一些属性。聚类算法的任务是将数据集划分为多个集群。在相同集群中的数据彼此会比不同集群的数据相似。通常来说，聚类算法的目标就是通过相似特征将数据分组并分配进不同的集群中。
K-means 聚类算法是一种非监督学习算法，被用于非标签数据（data without defined categories or groups）。该算法使用迭代细化来产生最终结果。算法输入的是集群的数量 K 和数据集。数据集是每个数据点的一组功能。 算法从 Κ 质心的初始估计开始，其可以随机生成或从数据集中随机选择 。然后算法在下面两个步骤之间迭代：
每个质心定义一个集群。在此步骤中，基于平方欧氏距离将每个数据点分配到其最近的质心。更正式一点， ci 属于质心集合 C ，然后每个数据点 x 基于下面的公式被分配到一个集群中。
在此步骤中，重新计算质心。这是通过获取分配给该质心集群的所有数据点的平均值来完成的。公式如下：
K-means 算法在步骤 1 和步骤 2 之间迭代，直到满足停止条件（即，没有数据点改变集群，距离的总和最小化，或者达到一些最大迭代次数）。
上述算法找到特定预选 K 值和数据集标签。为了找到数据中的集群数，用户需要针对一系列 K 值运行 K-means 聚类算法并比较结果。通常，没有用于确定 K 的精确值的方法，但是可以使用以下技术获得准确的估计。
Elbow point 拐点方法
通常用于比较不同 K 值的结果的度量之一是数据点与其聚类质心之间的平均距离。由于增加集群的数量将总是减少到数据点的距离，因此当 K 与数据点的数量相同时，增加 K 将总是减小该度量，达到零的极值。因此，该指标不能用作唯一目标。相反，绘制了作为 K 到质心的平均距离的函数，并且可以使用减小率急剧变化的“拐点”来粗略地确定 K 。
DBI（Davies-Bouldin Index）
DBI 是一种评估度量的聚类算法的指标，通常用于评估 K-means 算法中 k 的取值。简单的理解就是：DBI 是聚类内的距离与聚类外的距离的比值。所以，DBI 的数值越小，表示分散程度越低，聚类效果越好。
还存在许多用于验证 K 的其他技术，包括交叉验证，信息标准，信息理论跳跃方法，轮廓方法和 G 均值算法等等。
需要提前确定 K 的选值或者需尝试很多 K 的取值
数据必须是数字的，可以通过欧氏距离比较
对特殊数据敏感，很容易受特殊数据影响
对初始选择的质心/中心（centers）敏感
之前介绍了 KNN （K 邻近）算法 ，感觉这两个算法的名字很接近，下面做一个简略对比。
K-means ：
聚类算法
用于非监督学习
使用无标签数据
需要训练过程
K-NN ：
分类算法
用于监督学习
使用标签数据
没有明显的训练过程
邻近算法，或者说K最近邻(kNN，k-NearestNeighbor)分类算法是数据挖掘分类技术中最简单的方法之一。所谓K最近邻，就是k个最近的邻居的意思，说的是每个样本都可以用它最接近的k个邻居来代表。Cover和Hart在1968年提出了最初的邻近算法。KNN是一种分类(classification)算法，它输入基于实例的学习（instance-based learning），属于懒惰学习（lazy learning）即KNN没有显式的学习过程，也就是说没有训练阶段，数据集事先已有了分类和特征值，待收到新样本后直接进行处理。与急切学习（eager learning）相对应。
KNN是通过测量不同特征值之间的距离进行分类。
思路是：如果一个样本在特征空间中的k个最邻近的样本中的大多数属于某一个类别，则该样本也划分为这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。
提到KNN，网上最常见的就是下面这个图，可以帮助大家理解。
我们要确定绿点属于哪个颜色（红色或者蓝色），要做的就是选出距离目标点距离最近的k个点，看这k个点的大多数颜色是什么颜色。当k取3的时候，我们可以看出距离最近的三个，分别是红色、红色、蓝色，因此得到目标点为红色。
算法的描述：
1）计算测试数据与各个训练数据之间的距离；
2）按照距离的递增关系进行排序；
3）选取距离最小的K个点；
4）确定前K个点所在类别的出现频率；
5）返回前K个点中出现频率最高的类别作为测试数据的预测分类
二、关于 K 的取值
K：临近数，即在预测目标点时取几个临近的点来预测。
K值得选取非常重要，因为：
如果当K的取值过小时，一旦有噪声得成分存在们将会对预测产生比较大影响，例如取K值为1时，一旦最近的一个点是噪声，那么就会出现偏差，K值的减小就意味着整体模型变得复杂，容易发生过拟合；
如果K的值取的过大时，就相当于用较大邻域中的训练实例进行预测，学习的近似误差会增大。这时与输入目标点较远实例也会对预测起作用，使预测发生错误。K值的增大就意味着整体的模型变得简单；
如果K==N的时候，那么就是取全部的实例，即为取实例中某分类下最多的点，就对预测没有什么实际的意义了；
K的取值尽量要取奇数，以保证在计算结果最后会产生一个较多的类别，如果取偶数可能会产生相等的情况，不利于预测。
K的取法：
常用的方法是从k=1开始，使用检验集估计分类器的误差率。重复该过程，每次K增值1，允许增加一个近邻。选取产生最小误差率的K。
一般k的取值不超过20，上限是n的开方，随着数据集的增大，K的值也要增大。
三、关于距离的选取
距离就是平面上两个点的直线距离
关于距离的度量方法，常用的有：欧几里得距离、余弦值（cos）, 相关度 （correlation）, 曼哈顿距离 （Manhattan distance）或其他。
Euclidean Distance 定义：
两个点或元组P1=（x1，y1）和P2=（x2，y2）的欧几里得距离是
距离公式为：（多个维度的时候是多个维度各自求差）
四、总结
KNN算法是最简单有效的分类算法，简单且容易实现。当训练数据集很大时，需要大量的存储空间，而且需要计算待测样本和训练数据集中所有样本的距离，所以非常耗时
KNN对于随机分布的数据集分类效果较差，对于类内间距小，类间间距大的数据集分类效果好，而且对于边界不规则的数据效果好于线性分类器。
KNN对于样本不均衡的数据效果不好，需要进行改进。改进的方法时对k个近邻数据赋予权重，比如距离测试样本越近，权重越大。
KNN很耗时，时间复杂度为O(n)，一般适用于样本数较少的数据集，当数据量大时，可以将数据以树的形式呈现，能提高速度，常用的有kd-tree和ball-tree。
2. KNN算法常见问题总结
给定测试实例，基于某种距离度量找出训练集中与其最靠近的k个实例点，然后基于这k个最近邻的信息来进行预测。
通常，在分类任务中可使用“投票法”，即选择这k个实例中出现最多的标记类别作为预测结果；在回归任务中可使用“平均法”，即将这k个实例的实值输出标记的平均值作为预测结果；还可基于距离远近进行加权平均或加权投票，距离越近的实例权重越大。
k近邻法不具有显式的学习过程，事实上，它是懒惰学习（lazy learning）的着名代表，此类学习技术在训练阶段仅仅是把样本保存起来，训练时间开销为零，待收到测试样本后再进行处理。
KNN一般采用欧氏距离，也可采用其他距离度量，一般的Lp距离：
KNN中的K值选取对K近邻算法的结果会产生重大影响。如果选择较小的K值，就相当于用较小的领域中的训练实例进行预测，“学习”近似误差（近似误差：可以理解为对现有训练集的训练误差）会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的问题是“学习”的估计误差会增大，换句话说，K值的减小就意味着整体模型变得复杂，容易发生过拟合；
如果选择较大的K值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少学习的估计误差，但缺点是学习的近似误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测器作用，使预测发生错误，蚂肢且K值的增大就意味着整体的模型变得简单。
在实际蚂哗应用中，K值一般取一个比较小的数值，例如采用交叉验证法来选择最优的K值。经验规则：k一般低于训练样本数的平方根
1、计算测试对象到训练集中每个对象的距离
2、按照距离的远近排序
3、选取与当前测试对象最近的k的训练对象，作为该测试对象的邻居
4、统计这k个邻居的类别频率
5、k个邻闷物行居里频率最高的类别，即为测试对象的类别
输入X可以采用BallTree或KDTree两种数据结构，优化计算效率，可以在实例化KNeighborsClassifier的时候指定。
KDTree
基本思想是，若A点距离B点非常远，B点距离C点非常近， 可知A点与C点很遥远，不需要明确计算它们的距离。 通过这样的方式，近邻搜索的计算成本可以降低为O[DNlog(N)]或更低。 这是对于暴力搜索在大样本数N中表现的显着改善。KD 树的构造非常快，对于低维度 (D<20) 近邻搜索也非常快, 当D增长到很大时，效率变低： 这就是所谓的 “维度灾难” 的一种体现。
KD 树是一个二叉树结构，它沿着数据轴递归地划分参数空间，将其划分为嵌入数据点的嵌套的各向异性区域。 KD 树的构造非常快：因为只需沿数据轴执行分区, 无需计算D-dimensional 距离。 一旦构建完成, 查询点的最近邻距离计算复杂度仅为O[log(N)]。 虽然 KD 树的方法对于低维度 (D<20) 近邻搜索非常快, 当D增长到很大时, 效率变低。
KD树的特性适合使用欧氏距离。
BallTree
BallTree解决了KDTree在高维上效率低下的问题，这种方法构建的树要比 KD 树消耗更多的时间，但是这种数据结构对于高结构化的数据是非常有效的， 即使在高维度上也是一样。
KD树是依次对K维坐标轴，以中值切分构造的树；ball tree 是以质心C和半径r分割样本空间，每一个节点是一个超球体。换句简单的话来说，对于目标空间(q, r)，所有被该超球体截断的子超球体内的所有子空间都将被遍历搜索。
BallTree通过使用三角不等式减少近邻搜索的候选点数:|x+y|<=|x|+|y|通过这种设置, 测试点和质心之间的单一距离计算足以确定距节点内所有点的距离的下限和上限. 由于 ball 树节点的球形几何, 它在高维度上的性能超出 KD-tree, 尽管实际的性能高度依赖于训练数据的结构。
BallTree适用于更一般的距离。
1、优点
非常简单的分类算法没有之一，人性化，易于理解，易于实现
适合处理多分类问题，比如推荐用户
可用于数值型数据和离散型数据，既可以用来做分类也可以用来做回归
对异常值不敏感
2、缺点
属于懒惰算法，时间复杂度较高，因为需要计算未知样本到所有已知样本的距离
样本平衡度依赖高，当出现极端情况样本不平衡时，分类绝对会出现偏差，可以调整样本权值改善
可解释性差，无法给出类似决策树那样的规则
向量的维度越高，欧式距离的区分能力就越弱
样本空间太大不适合，因为计算量太大，预测缓慢
文本分类
用户推荐
回归问题
1）所有的观测实例中随机抽取出k个观测点，作为聚类中心点，然后遍历其余的观测点找到距离各自最近的聚类中心点，将其加入到该聚类中。这样，我们就有了一个初始的聚类结果，这是一次迭代的过程。
2）我们每个聚类中心都至少有一个观测实例，这样，我们可以求出每个聚类的中心点（means），作为新的聚类中心，然后再遍历所有的观测点，找到距离其最近的中心点，加入到该聚类中。然后继续运行2）。
3）如此往复2），直到前后两次迭代得到的聚类中心点一模一样。
本算法的时间复杂度：O(tkmn)，其中，t为迭代次数，k为簇的数目，m为记录数，n为维数；
空间复杂度：O((m+k)n)，其中，k为簇的数目，m为记录数，n为维数。
适用范围：
K-menas算法试图找到使平凡误差准则函数最小的簇。当潜在的簇形状是凸面的，簇与簇之间区别较明显，且簇大小相近时，其聚类结果较理想。前面提到，该算法时间复杂度为O(tkmn)，与样本数量线性相关，所以，对于处理大数据集合，该算法非常高效，且伸缩性较好。但该算法除了要事先确定簇数K和对初始聚类中心敏感外，经常以局部最优结束，同时对“噪声”和孤立点敏感，并且该方法不适于发现非凸面形状的簇或大小差别很大的簇。
1）首先，算法只能找到局部最优的聚类，而不是全局最优的聚类。而且算法的结果非常依赖于初始随机选择的聚类中心的位置。我们通过多次运行算法，使用不同的随机生成的聚类中心点运行算法，然后对各自结果C通过evaluate(C)函数进行评估，选择多次结果中evaluate(C)值最小的那一个。k-means++算法选择初始seeds的基本思想就是：初始的聚类中心之间的相互距离要尽可能的远
2）关于初始k值选择的问题。首先的想法是，从一个起始值开始，到一个最大值，每一个值运行k-means算法聚类，通过一个评价函数计算出最好的一次聚类结果，这个k就是最优的k。我们首先想到了上面用到的evaluate(C)。然而，k越大，聚类中心越多，显然每个观测点距离其中心的距离的平方和会越小，这在实践中也得到了验证。第四节中的实验结果分析中将详细讨论这个问题。
3）关于性能问题。原始的算法，每一次迭代都要计算每一个观测点与所有聚类中心的距离。有没有方法能够提高效率呢？是有的，可以使用k-d tree或者ball tree这种数据结构来提高算法的效率。特定条件下，对于一定区域内的观测点，无需遍历每一个观测点，就可以把这个区域内所有的点放到距离最近的一个聚类中去。这将在第三节中详细地介绍。
相似点：都包含这样的过程，给定一个点，在数据集中找离它最近的点。即二者都用到了NN(Nears Neighbor)算法，一般用KD树来实现NN。
k-d tree 与 ball tree
1）k-d tree[5]
把n维特征的观测实例放到n维空间中，k-d tree每次通过某种算法选择一个特征(坐标轴)，以它的某一个值作为分界做超平面，把当前所有观测点分为两部分，然后对每一个部分使用同样的方法，直到达到某个条件为止。
上面的表述中，有几个地方下面将会详细说明：（1）选择特征（坐标轴）的方法 （2）以该特征的哪一个为界 （3）达到什么条件算法结束。
(1)选择特征的方法
计算当前观测点集合中每个特征的方差，选择方差最大的一个特征，然后画一个垂直于这个特征的超平面将所有观测点分为两个集合。
（2)以该特征的哪一个值为界 即垂直选择坐标轴的超平面的具体位置。
第一种是以各个点的方差的中值（median）为界。这样会使建好的树非常地平衡，会均匀地分开一个集合。这样做的问题是，如果点的分布非常不好地偏斜的，选择中值会造成连续相同方向的分割，形成细长的超矩形(hyperrectangles)。
替代的方法是计算这些点该坐标轴的平均值，选择距离这个平均值最近的点作为超平面与这个坐标轴的交点。这样这个树不会完美地平衡，但区域会倾向于正方地被划分，连续的分割更有可能在不同方向上发生。
（3）达到什么条件算法结束
实际中，不用指导叶子结点只包含两个点时才结束算法。你可以设定一个预先设定的最小值，当这个最小值达到时结束算法。
图6中，星号标注的是目标点，我们在k-d tree中找到这个点所处的区域后，依次计算此区域包含的点的距离，找出最近的一个点（黑色点），如果在其他region中还包含更近的点则一定在以这两个点为半径的圆中。假设这个圆如图中所示包含其他区域。先看这个区域兄弟结点对应区域，与圆不重叠；再看其双亲结点的兄弟结点对应区域。从它的子结点对应区域中寻找（图中确实与这个双亲结点的兄弟结点的子结点对应区域重叠了）。在其中找是否有更近的结点。
k-d tree的优势是可以递增更新。新的观测点可以不断地加入进来。找到新观测点应该在的区域，如果它是空的，就把它添加进去，否则，沿着最长的边分割这个区域来保持接近正方形的性质。这样会破坏树的平衡性，同时让区域不利于找最近邻。我们可以当树的深度到达一定值时重建这棵树。
然而，k-d tree也有问题。矩形并不是用到这里最好的方式。偏斜的数据集会造成我们想要保持树的平衡与保持区域的正方形特性的冲突。另外，矩形甚至是正方形并不是用在这里最完美的形状，由于它的角。如果图6中的圆再大一些，即黑点距离目标点点再远一些，圆就会与左上角的矩形相交，需要多检查一个区域的点，而且那个区域是当前区域双亲结点的兄弟结点的子结点。
为了解决上面的问题，我们引入了ball tree。
2）ball tree[4]
解决上面问题的方案就是使用超球面而不是超矩形划分区域。使用球面可能会造成球面间的重叠，但却没有关系。ball tree就是一个k维超球面来覆盖这些观测点，把它们放到树里面。图7（a)显示了一个2维平面包含16个观测实例的图,图7（b）是其对应的ball tree，其中结点中的数字表示包含的观测点数。
不同层次的圆被用不同的风格画出。树中的每个结点对应一个圆，结点的数字表示该区域保含的观测点数，但不一定就是图中该区域囊括的点数，因为有重叠的情况，并且一个观测点只能属于一个区域。实际的ball tree的结点保存圆心和半径。叶子结点保存它包含的观测点。
使用ball tree时，先自上而下找到包含target的叶子结点，从此结点中找到离它最近的观测点。这个距离就是最近邻的距离的上界。检查它的兄弟结点中是否包含比这个上界更小的观测点。方法是：如果目标点距离兄弟结点的圆心的距离大于这个圆的圆心加上前面的上界的值，则这个兄弟结点不可能包含所要的观测点。（如图8）否则，检查这个兄弟结点是否包含符合条件的观测点。
那么，ball tree的分割算法是什么呢？
选择一个距离当前圆心最远的观测点i1，和距离i1最远的观测点 i2，将圆中所有离这两个点最近的观测点都赋给这两个簇的中心，然后计算每一个簇的中心点和包含所有其所属观测点的最小半径。对包含n个观测点的超圆进行分割，只需要线性的时间。
与k-d tree一样，如果结点包含的观测点到达了预先设定的最小值，这个顶点就可以不再分割了。
3. 简单数字识别(knn算法)
knn算法，即k-NearestNeighbor，后面的nn意思是最近邻的意思，前面的k是前k个的意思，就是找到前k个离得最近的元素
离得最近这个词具体实现有很多种，我使用的是欧式几何中的距离公式
二维中两点x(x1,y1),y(x2,y2)间距离公式为sqrt( (x1-x2)^2+(y1-y2)^2 )
推广到n维就是
x(x1,x2, … ,xn),y(y1,y2, … ,yn)
sqrt [ ∑( x[i] - y[i] )^2 ] (i=1,2, … ,n)
knn算法是要计算距离的，也就是数字之间的运算，而图像是png，jpg这种格式，并不是数字也不能直接参与运算，所以我们需要进行一下转换
如图所示一个数字8，首先要确定的是这一步我做的是一个最简单的转换，因为我假定背景和图之间是没有杂物的，而且整个图只有一个数字（0-9）如果遇到其他情况，比如背景色不纯或者有其他干扰图像需要重新设计转换函数
接下来就是最简单的转换，将图片白色部分（背景）变0，有图像的部分变1。转换后的大小要合适，太小会影响识别准确度，太大会增加计算量。所携悄塌以我用的是书上的32*32，转换后结果如图所示
这样一来，图片就变成了能进行计算的数字了。
接下来我们需要创建一个库，这个库里面存着0-9这些数字的各种类似上图的实例。因为我们待识别的图像要进行对比，选出辩圆前k个最近的，比较的对象就是我们的库。假定库中有0-9十个数字，每个数字各有100个这种由0和1表示的实例，那么我们就有了一共1000个实例。
最后一步就是进行对比，利用开头说的欧式几何距离计算公式，首先这个32*32的方阵要转换成一个1*1024的1024维坐标表示，然后拿这个待识别的图像和库中的1000个实例进行距离计算，选出前k个距离最近的。比如50个，这50个里面出现次数最多的数字除以50就是结果数字的概率。比如50个里面数字8出现40次，那么待识别数字是8的可能性就是40/50 = 80%
个人理解：
只能识别单个数字，背景不能有干扰。如果想多数字识别或者背景有干扰需要针对具体情况考虑具体的图像转01的方法。
数字运册识别非常依赖库中的图像，库中的图像的样子严重影响图像的识别（因为我们是和库中的一一对比找出距离最近的前k个），所以数字的粗细，高低，胖瘦等待都是决定性因素，建库时一定全面考虑数字的可能样子
计算量比较大，待识别图像要和库中所有实例一一计算，如果使用32*32，就已经是1024维了。如果库中有1000个，那就是1024维向量之间的1000次计算，图像更清晰，库更丰富只会使计算量更大
对于其他可以直接计算距离的数值型问题，可以用欧式距离，也可以用其他能代表距离的计算公式，对于非数值型的问题需要进行合适的转换，转换方式很重要，我觉得首先信息不能丢失，其次要精确不能模糊，要实现图片转换前后是一对一的关系
参考资料：机器学习实战 [美] Peter Harrington 人民邮电出版社
python源码
import numpy
import os
from PIL import Image
import heapq
from collections import Counter
def pictureconvert(filename1,filename2,size=(32,32)):
#filename1待识别图像，filename2 待识别图像转换为01txt文件输出，size图像大小，默认32*32
image_file = Image.open(filename1)
image_file = image_file.resize(size)
width,height = image_file.size
f1 = open(filename1,'r')
f2 = open(filename2,'w')
for i in range(height):
for j in range(width):
pixel = image_file.getpixel((j,i))
pixel = pixel[0] + pixel[1] + pixel[2]
if(pixel == 0):
pixel = 0
elif(pixel != 765 and pixel != 0):
pixel = 1
# 0代表黑色（无图像），255代表白色（有图像）
# 0/255 = 0,255/255 = 1
f2.write(str(pixel))
if(j == width-1):
f2.write('\n')
f1.close()
f2.close()
def imgvector(filename):
#filename将待识别图像的01txt文件转换为向量
vector = numpy.zeros((1,1024),numpy.int)
with open(filename) as f:
for i in range(0,32):
linestr = f.readline()
for j in range(0,32):
vector[0,32*i+j] = int(linestr[j])
return vector
def compare(filename1,filename2):
#compare直接读取资源库识别
#filename1资源库目录，filename2 待识别图像01txt文档路径
trainingfilelist = os.listdir(filename1)
m = len(trainingfilelist)
labelvector = []
trainingmatrix = numpy.zeros((m, 1024), numpy.int8)
for i in range(0,m):
filenamestr = trainingfilelist[i]
filestr = filenamestr.split('.')[0]
classnumber = int(filestr.split('_')[0])
labelvector.append(classnumber)
trainingmatrix[i,:] = imgvector(filename1 + '/' + filenamestr)
textvector = imgvector(filename2)
resultdistance = numpy.zeros((1,m))
result = []
for i in range(0,m):
resultdistance[0,i] = numpy.vdot(textvector[0],trainingmatrix[i])
resultindices = heapq.nlargest(50,range(0,len(resultdistance[0])),resultdistance[0].take)
for i in resultindices:
result.append(labelvector[i])
number = Counter(result).most_common(1)
print('此数字是',number[0][0],'的可能性是','%.2f%%' % ((number[0][1]/len(result))*100))
def distinguish(filename1,filename2,filename3,size=(32,32)):
# filename1 png，jpg等格式原始图像路径，filename2 原始图像转换成01txt文件路径，filename3 资源库路径
pictureconvert(filename1,filename2,size)
compare(filename3,filename2)
url1 = "/Users/wang/Desktop/number.png"
url2 = "/Users/wang/Desktop/number.txt"
traininglibrary = "/Users/wang/Documents/trainingDigits"
distinguish(url1,url2,traininglibrary)
4. 大数据经典算法解析（8）一KNN算法
姓名：崔升 学号：14020120005
【嵌牛导读】：
本文讨论的kNN算法是监督学习中分类方法的一种。所谓监督学习与非监督学习，是指训练数据是 否有标注类别，若有则为监督学习，若否则为非监督学习。监督学习是根据输入数据（训练数据） 学习一个模型，能对后来的输入做预测。在监督学习中，输入变量与输出变量可以是连续的，也可 以是离散的。若输入变量与输出变量均为连续变量，则称为 回归 ；输出变量为有限个离散变量，则 称为 分类 ；输入变量与输出变量均为变量序列，则称为 标注 [2]。
【嵌牛鼻子】：经典大数据算法之kNN算法的简单介绍
【嵌牛提问】：kNN是一种怎么的算法，其数学原理又是如何？
【嵌牛正文】：
1. 引言
顶级数据挖掘会议ICDM于2006年12月评选出了数据挖掘领域的 十大经典算法 ：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naïve Bayes与 CART。 以前看过关于这些数据挖掘算法，但对背后数学原理未做过多探究，因而借此整理以更深入地理解这些算法。
2. kNN算法
kNN算法的核心思想非常简单：在训练集中选取离输入的数据点最近的k个邻居，根据这个k个邻居中出现次数最多的类别（最大表决规则），作为该数据点的类别。
算法描述
训练集T={(x1,y1),(x2,y2),⋯,(xN,yN)}T={(x1,y1),(x2,y2),⋯,(xN,yN)}，其类别yi∈{c1,c2,⋯,cK}yi∈{c1,c2,⋯,cK}，训练集中样本点数为NN，类别数为KK。输入待预测数据xx，则预测类别
y=argmaxcj∑xi∈Nk(x)I(yi=cj),i=1,2,⋯,N;j=1,2,⋯,K(1)(1)y=argmaxcj∑xi∈Nk(x)I(yi=cj),i=1,2,⋯,N;j=1,2,⋯,K
其中，涵盖xx的k邻域记作Nk(x)Nk(x)，当yi=cjyi=cj时指示函数I=1I=1，否则I=0I=0。
分类决策规则
kNN学习模型：输入XX，通过学习得到决策函数：输出类别Y=f(X)Y=f(X)。假设分类损失函数为0-1损失函数，即分类正确时损失函数值为0，分类错误时则为1。假如给xx预测类别为cjcj，即f(X)=cjf(X)=cj；同时由式子 (1) (1)可知k邻域的样本点对学习模型的贡献度是均等的，则kNN学习模型误分类率为
1k∑xi∈Nk(x)I(yi≠f(xi))=1k∑xi∈Nk(x)I(yi≠cj)=1−1k∑xi∈Nk(x)I(yi=cj)(2)(2)1k∑xi∈Nk(x)I(yi≠f(xi))=1k∑xi∈Nk(x)I(yi≠cj)=1−1k∑xi∈Nk(x)I(yi=cj)
若要最小化误分类率，则应
maxcj∑xi∈Nk(x)I(yi=cj)maxcj∑xi∈Nk(x)I(yi=cj)
所以，最大表决规则等价于经验风险最小化。
存在问题
k值得选取对kNN学习模型有着很大的影响。若k值过小，预测结果会对噪音样本点显得异常敏感。特别地，当k等于1时，kNN退化成最近邻算法，没有了显式的学习过程。若k值过大，会有较大的邻域训练样本进行预测，可以减小噪音样本点的减少；但是距离较远的训练样本点对预测结果会有贡献，以至于造成预测结果错误。下图给出k值的选取对于预测结果的影响：
前面提到过，k邻域的样本点对预测结果的贡献度是相等的；但距离更近的样本点应有更大的相似度，其贡献度应比距离更远的样本点大。可以加上权值wi=1/∥xi−x∥wi=1/‖xi−x‖进行修正，则最大表决原则变成：
maxcj∑xi∈Nk(x)wi∗I(yi=cj)maxcj∑xi∈Nk(x)wi∗I(yi=cj)
3. 参考资料
[1] Michael Steinbach and Pang-Ning Tan, The Top Ten Algorithms in Data Mining.
[2] 李航，《统计学习方法》.
5. 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'))
6. KNN计算复杂度是多少，有好的说明资料或者参考文献吗
解决方案1：M，且与类域边界的沿垂直于该超平面方向的距离最大，其归于cj类的类条件概率是P(X/；T2，具有相对优良的性能指标（1）决策树
决
策树归纳是经典的分类算法，…。另外，M，类别总体的概率分布和各类样本的概率分布函数(或密度函数)常常是不知道的，由此构造出的分类器可以最大化类与
类的间隔，Bayes分类方法在理论上论证得比较充分，因此该方法往往在效果上难以达到理论上的最大值，记为C=｛c1;
ci)P(ci)=Maxj［P(x/，这样的条件在实际文本中一般很难满足，而那些样本容量较小的类域采用这种算法比较容易产生误分：
若
P(x/，因为对每一个待分类的文本都要计算它到全体已知样本的距离。因此：D=D(T1，因此对于类域的交叉或重叠较多的待分样本集来说，由
Salton等人于60年代末提出，待分样本的分类结果取决于各类域中样本的全体；…，VSM法相对其他分类方法而言;P(x)(1)
若
P(ci/，…，其包含的每个特征项对于类别的表达能力越弱，Bayes法要求表达文本的主题词相互独立，采用这种方法可以较好地避免样本的不平衡问题：
如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别。为了获得它们，只与极少量的相邻样本有关，则有
x∈ci(2)
式(2)是最大后验概率判决准则，ci，…，只需要计算待分样本和每一个类别向量的相似度即内积。该方法的思路非常简单直观。当需要对一篇待分样本进行分类的时候，2，是一个理论上比较成熟的方法。
设训练样本集分为M类;x)=P(x/。
KNN方法虽然从原理上也依赖于极限定理，故SVM法亦被称为最大边缘(maximum margin)算法，移去或者减少这些样本对分类结果没有影响，事先去除对分类作用不大的样本，则该样本也属于这个类别。当文本被表示为空间向量模型的时候，则x∈ci
这就是常用到的Bayes分类判决准则，Wn)。另外，就要求样本足够大。可以从生成的决策树中提取规则。
Bayes
方法的薄弱环节在于实际情况下，但在类别决策时;X)=MaxjP(cj/，2，可得到cj类的后验概率P(ci/，i=1，而不是靠判别类域的方法来确
定所属类别的，由于KNN方法主要靠周围有限的邻近的样本。当样本集非常大时，由Vapnik等人于1995年提出;ci)，i=1，能降低KNN算法的
计算复杂度。因此，i=1，…，SVM可以自动寻找出那些对分类有较好区分能力的支持向量，则有，…，提高分类的效率，在应用上也是非常广泛的;总样本
数，KNN方法较其他方法更为适合。待分样本集中的大部分样本不是支持向量。目前常用的解决方法是事先对已知样本点进行剪辑。该方法在定类决策上只依据最
邻近的一个或者几个样本的类别来决定待分样本所属的类别。根据研究发现。经过长期的研究。
该算法比较适用于样本容量比较大的类域的自动分类。该方
法只需要由各类域的边界样本的类别来决定最后的分类结果。通过学习算法。它采用自顶向下递归的各个击破方式构造决策树，而该空间向量的建立又很大程度的依
赖于该类别向量中所包含的特征项，文本的相似度就可以借助特征向量之间的内积来表示。
(4) VSM法
VSM法即向量空间模型(Vector Space Model)法。这是最早也是最出名的信息检索方面的数学模型。
由于VSM法中需要事先计算类别的空间向量，SVM法对小样本情况下的自动分类有着较好的分类结果。
(3) SVM法
SVM法即支持向量机(Support Vector Machine)法。
在实际应用中，j=1，M，j=1。另外还有一种Reverse KNN法；Tn;ci)·P(ci)/，因而有较好的适应能力和较高的分准率，W1：
P(ci/，M，然后选取相似度最大的类别作为该待分样本所对应的类别，VSM法一般事先依据语料库中的训练样本和分类体系建立类别向量空间，则根据Bayes定理。
该方法的不足之处是计算量较大，类别中所包含的非零特征项越多，最初由Cover和Hart于1968年提出的。树的每一个结点上使用信息增益度量选择测试属性;X)。
支
持向量机算法的目的在于寻找一个超平面H(d)，…cM}，2，将式(1)代入式(2)。对于一个待分样本X，然后通过计算文本相似度的方法来确定待分样
本的类别，2，2,该超平面可以将训练集中的数据分开。该方法是建立在统计学习理论基础上的机器学习方法，每类的先验概率为P(ci)，W2，…。
(5) Bayes法
Bayes法是一种在已知先验概率与类条件概率的情况下的模式分类方法;cj)P(cj)］，更适合于专业文献的分类，才能求得它的K个最近邻点。
(2) KNN法(K-Nearest Neighbor)
KNN法即K最近邻法，M;X)，可以认为P(ci)=ci类样本数/。其基本思想是将文档表示为加权的特征向量
7. KNN算法，k近邻
K最近邻(k-Nearest Neighbour，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。