邻近分割算法

❶ 图像分割算法总结

       图像处理的很多任务都离不开图像分割。因为图像分割在cv中实在太重要(有用)了，就先把图像分割的常用算法做个总结。

        接触机器学习和深度学习时间已经不短了。期间看过各种相关知识但从未总结过。本文过后我会尽可能详细的从工程角度来总结，从传统机器学习算法，传统计算机视觉库算法到深度学习目前常用算法和论文，以及模型在各平台的转化，量化，服务化部署等相关知识总结。

        图像分割常用算法大致分为下面几类。由于图像的能量范函，边缘追踪等方法的效果往往只能解决特定问题，效果并不理想，这里不再阐述。当然二值化本身也可以分割一些简单图像的。但是二值化算法较多，我会专门做一个文章来总结。这里不再赘述。

        1.基于边缘的图像分割算法：

            有利用图像梯度的传统算法算子的sobel，roberts，prewitt,拉普拉斯以及canny等。

            这些算法的基本思想都是采用合适的卷积算子，对图像做卷积。从而求出图像对应的梯度图像。(至于为什么通过如图1这样的算子卷积，即可得到图像的梯度图像，请读者复习下卷积和倒数的概念自行推导)由于图像的边缘处往往是图像像素差异较大，梯度较大地方。因此我们通过合适的卷积核得到图像的梯度图像，即得到了图像的边缘图像。至于二阶算子的推导，与一阶类似。优点：传统算子梯度检测，只需要用合适的卷积核做卷积，即可快速得出对应的边缘图像。缺点：图像边缘不一定准确，复杂图像的梯度不仅仅出现在图像边缘，可以能出现在图像内部的色彩和纹理上。

             也有基于深度学习方法hed，rcf等。由于这类网络都有同一个比较严重的缺陷，这里只举例hed网络。hed是基于FCN和VGG改进，同时引出6个loss进行优化训练，通过多个层输出不同scale的粒度的边缘，然后通过一个训练权重融合各个层的边缘结果。hed网络结构如下：

可以得到一个比较完整的梯度图像，可参考github的hed实现。优点：图像的梯度细节和边缘完整性，相比传统的边缘算子要好很多。但是hed对于边缘的图像内部的边缘并不能很好的区分。当然我们可以自行更改loss来尝试只拟合外部的图像边缘。但最致命的问题在于，基于vgg的hed的网络表达能力有限，对于图像和背景接近，或者图像和背景部分相融的图片，hed似乎就有点无能为力了。

        2.基于区域分割的算法：

            区域分割比较常用的如传统的算法结合遗传算法，区域生长算法，区域分裂合并，分水岭算法等。这里传统算法的思路是比较简单易懂的，如果有无法理解的地方，欢迎大家一起讨论学习。这里不再做过多的分析。

            基于区域和语意的深度学习分割算法，是目前图像分割成果较多和研究的主要方向。例如FCN系列的全卷积网络，以及经典的医学图像分割常用的unet系列，以及rcnn系列发展下的maskrcnn，以及18年底的PAnet。基于语意的图像分割技术，无疑会成为图像分割技术的主流。

            其中，基于深度学习语意的其他相关算法也可以间接或直接的应用到图像分割。如经典的图像matting问题。18年又出现了许多非常优秀的算法和论文。如Deep-Image-Matting，以及效果非常优秀的MIT的 semantic soft segmentation(sss).

            基于语意的图像分割效果明显要好于其他的传统算法。我在解决图像分割的问题时，首先尝试用了hed网络。最后的效果并不理想。虽然也参考github，做了hed的一些fine-tune,但是还是上面提到的原因，在我多次尝试后，最终放弃。转而适用FCN系列的网络。但是fcn也无法解决图像和背景相融的问题。图片相融的分割，感觉即需要大的感受野，又需要未相融部分原图像细节，所以单原FCN的网络，很难做出准确的分割。中间还测试过很多其他相关的网络，但都效果不佳。考虑到感受野和原图像细节，尝试了resnet和densenet作为图像特征提取的底层。最终我测试了unet系列的网络：

                unet的原始模型如图所示。在自己拍照爬虫等手段采集了将近1000张图片。去掉了图片质量太差的，图片内容太过类似的。爬虫最终收集160多张，自己拍照收集200张图片后，又用ps手动p了边缘图像，采用图像增强变换，大约有300*24张图片。原生unet网络的表现比较一般。在将unet普通的卷积层改为resnet后，网络的表达能力明显提升。在将resnet改为resnet101，此时，即使对于部分相融的图像，也能较好的分割了。但是unet的模型体积已经不能接受。

                在最后阶段，看到maskrcnn的实例分割。maskrcnn一路由rcnn,fasterrcnn发展过来。于是用maskrcnn来加入自己的训练数据和label图像进行训练。maskrcnn的结果表现并不令人满意，对于边缘的定位，相比于其他算法，略显粗糙。在产品应用中，明显还不合适。                

        3.基于图的分割算法

            基于深度学习的deepgrab,效果表现并不是十分理想。deepgrab的git作者backbone采用了deeplabv2的网络结构。并没有完全安装原论文来做。

论文原地址参考： https://arxiv.org/pdf/1707.00243.pdf

整体结构类似于encode和decoder。并没有太仔细的研究，因为基于resent101的结构，在模型体积，速度以及deeplab的分割精度上，都不能满足当前的需求。之前大致总结过计算机视觉的相关知识点，既然目前在讨论移动端模型，那后面就分模块总结下移动端模型的应用落地吧。

由于时间实在有限。这里并没有针对每个算法进行详细的讲解。后续我会从基础的机器学习算法开始总结。

❷ 最邻近规则分类（K-Nearest Neighbor）KNN算法（七）

1.1 Cover和Hart在1968年提出了最初的邻近算法。
1.2 分类(classification)算法。
1.3 输入基于实例的学习(instance-based learning),或则是懒惰学习(lazy learning)。-----（为什么叫懒惰学习了？因为在处理大量的训练集的时候并没有建立大量的模型，而是刚开始的时候对于一个未知的实例进行归类的时候我们会根据已知类型实例的比较来进行归类）

目的：求未知的电影属于什么类型？ ----可以根据实例的特征值来进行归类（分类）。

3.1 步骤：

3.3 举例:

4.1 算法优点

4.2 算法缺点

注意：在选择k的时候，一般k为奇数，因为保证了结果相等的出现情况被排除了，如果选择偶数，可能会出现结果相等

考虑距离，根据距离加上权重（ 比如: 1/d (d: 距离）---表示加权重来计算大小）

❸ 邻近算法

k-Nearest Neighbor algorithm K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。因此，采用这种方法可以较好地避免样本的不平衡问题。另外，由于 KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。该方法的不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。

❹ 邻近算法的缺点

该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。 该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。
该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。
可理解性差，无法给出像决策树那样的规则。

❺ 图像分割

图像阈值化分割是一种传统的最常用的图像分割方法，因其实现简单、计算量小、性能较稳定而成为图像分割中最基本和应用最广泛的分割技术。它特别适用于目标和背景占据不同灰度级范围的图像。它不仅可以极大的压缩数据量，而且也大大简化了分析和处理步骤，因此在很多情况下，是进行图像分析、特征提取与模式识别之前的必要的图像预处理过程。

图像阈值化的目的是要按照灰度级，对像素集合进行一个划分，得到的每个子集形成一个与现实景物相对应的区域，各个区域内部具有一致的属性，而相邻区域不具有这种一致属性。这样的划分可以通过从灰度级出发选取一个或多个阈值来实现。

基本原理是：通过设定不同的特征阈值，把图像象素点分为若干类。
常用的特征包括：直接来自原始图像的灰度或彩色特征；由原始灰度或彩色值变换得到的特征。
设原始图像为f(x，y)，按照一定的准则f(x，y)中找到特征值T，将图像分割为两个部分，分割后的图像为：
若取：b0=0(黑)，b1=1(白)，即为我们通常所说的图像二值化。

阈值分割方法实际上是输入图像f到输出图像g的如下变换：

其中，T为阈值，对于物体的图像元素g(i,j)=1，对于背景的图像元素g(i,j)=0。

由此可见，阈值分割算法的关键是确定阈值，如果能确定一个合适的阈值就可准确地将图像分割开来。阈值确定后，将阈值与像素点的灰度值逐个进行比较，而且像素分割可对各像素并行地进行，分割的结果直接给出图像区域。
阈值分割的优点是计算简单、运算效率较高、速度快。有着各种各样的阈值处理技术，包括全局阈值、自适应阈值、最佳阈值等等。

阈值处理技术参看：

区域分割是讲图像按照相似性准则分成不同的区域，主要包括区域增长，区域分裂合并和分水岭等几种类型。

区域生长是一种串行区域分割的图像分割方法。区域生长是指从某个像素出发，按照一定的准则，逐步加入邻近像素，当满足一定的条件时，区域生长终止。区域生长的好坏决定于1. 初始点（种子点）的选取。 2. 生长准则。 3. 终止条件 。区域生长是从某个或者某些像素点出发，最后得到整个区域，进而实现目标的提取。

区域生长的基本思想是将具有相似性质的像素集合起来构成区域。具体先对每个需要分割的区域找一个种子像素作为生长的起点，然后将种子像素周围邻域中与种子像素有相同或相似性质的像素(根据某种事先确定的生长或相似准则来判定)合并到种子像素所在的区域中。将这些新像素当作新的种子像素继续进行上面的过程，直到再没有满足条件的像素可被包括进来。这样一个区域就长成了。

区域生长需要选择一组能正确代表所需区域的种子像素，确定在生长过程中的相似性准则，制定让生长停止的条件或准则。相似性准则可以是灰度级、彩色、纹理、梯度等特性。选取的种子像素可以是单个像素，也可以是包含若干个像素的小区域。大部分区域生长准则使用图像的局部性质。生长准则可根据不同原则制定，而使用不同的生长准则会影响区域生长的过程。

图1是区域增长的示例。

区域生长是一种古老的图像分割方法，最早的区域生长图像分割方法是由Levine等人提出的。该方法一般有两种方式，一种是先给定图像中要分割的目标物体内的一个小块或者说种子区域(seed point)，再在种子区域基础上不断将其周围的像素点以一定的规则加入其中，达到最终将代表该物体的所有像素点结合成一个区域的目的；另一种是先将图像分割成很多的一致性较强，如区域内像素灰度值相同的小区域，再按一定的规则将小区域融合成大区域，达到分割图像的目的，典型的区域生长法如T. C. Pong等人提出的基于小面（facet）模型的区域生长法，区域生长法固有的缺点是往往会造成过度分割，即将图像分割成过多的区域

区域生长实现的步骤如下:

区域分裂合并算法的基本思想是先确定一个分裂合并的准则，即区域特征一致性的测度，当图像中某个区域的特征不一致时就将该区域分裂成4个相等的子区域，当相邻的子区域满足一致性特征时则将它们合成一个大区域，直至所有区域不再满足分裂合并的条件为止。当分裂到不能再分的情况时，分裂结束，然后它将查找相邻区域有没有相似的特征，如果有就将相似区域进行合并，最后达到分割的作用。在一定程度上区域生长和区域分裂合并算法有异曲同工之妙，互相促进相辅相成的，区域分裂到极致就是分割成单一像素点，然后按照一定的测量准则进行合并，在一定程度上可以认为是单一像素点的区域生长方法。区域生长比区域分裂合并的方法节省了分裂的过程，而区域分裂合并的方法可以在较大的一个相似区域基础上再进行相似合并，而区域生长只能从单一像素点出发进行生长（合并）。

反复进行拆分和聚合以满足限制条件的算法。

令R表示整幅图像区域并选择一个谓词P。对R进行分割的一种方法是反复将分割得到的结果图像再次分为四个区域，直到对任何区域Ri，有P(Ri)=TRUE。这里是从整幅图像开始。如果P(R)=FALSE，就将图像分割为4个区域。对任何区域如果P的值是FALSE．就将这4个区域的每个区域再次分别分为4个区域，如此不断继续下去。这种特殊的分割技术用所谓的四叉树形式表示最为方便(就是说，每个非叶子节点正好有4个子树)，这正如图10.42中说明的树那样。注意，树的根对应于整幅图像，每个节点对应于划分的子部分。此时，只有R4进行了进一步的再细分。

如果只使用拆分，最后的分区可能会包含具有相同性质的相邻区域。这种缺陷可以通过进行拆分的同时也允许进行区域聚合来得到矫正。就是说，只有在P(Rj∪Rk)=TRUE时，两个相邻的区域Rj和Rk才能聚合。
前面的讨论可以总结为如下过程。在反复操作的每一步，我们需要做：

可以对前面讲述的基本思想进行几种变化。例如，一种可能的变化是开始时将图像拆分为一组图象块。然后对每个块进一步进行上述拆分，但聚合操作开始时受只能将4个块并为一组的限制。这4个块是四叉树表示法中节点的后代且都满足谓词P。当不能再进行此类聚合时，这个过程终止于满足步骤2的最后的区域聚合。在这种情况下，聚合的区域可能会大小不同。这种方法的主要优点是对于拆分和聚合都使用同样的四叉树，直到聚合的最后一步。

分水岭分割方法，是一种基于拓扑理论的数学形态学的分割方法，其基本思想是把图像看作是测地学上的拓扑地貌，图像中每一点像素的灰度值表示该点的海拔高度，每一个局部极小值及其影响区域称为集水盆，而集水盆的边界则形成分水岭。分水岭的概念和形成可以通过模拟浸入过程来说明。在每一个局部极小值表面，刺穿一个小孔，然后把整个模型慢慢浸入水中，随着浸入的加深，每一个局部极小值的影响域慢慢向外扩展，在两个集水盆汇合处构筑大坝，即形成分水岭。

分水岭的计算过程是一个迭代标注过程。分水岭比较经典的计算方法是L. Vincent提出的。在该算法中，分水岭计算分两个步骤，一个是排序过程，一个是淹没过程。首先对每个像素的灰度级进行从低到高排序，然后在从低到高实现淹没过程中，对每一个局部极小值在h阶高度的影响域采用先进先出(FIFO)结构进行判断及标注。

分水岭变换得到的是输入图像的集水盆图像，集水盆之间的边界点，即为分水岭。显然，分水岭表示的是输入图像极大值点。因此，为得到图像的边缘信息，通常把梯度图像作为输入图像，即

分水岭算法对微弱边缘具有良好的响应，图像中的噪声、物体表面细微的灰度变化，都会产生过度分割的现象。但同时应当看出，分水岭算法对微弱边缘具有良好的响应，是得到封闭连续边缘的保证的。另外，分水岭算法所得到的封闭的集水盆，为分析图像的区域特征提供了可能。
为消除分水岭算法产生的过度分割，通常可以采用两种处理方法，一是利用先验知识去除无关边缘信息。二是修改梯度函数使得集水盆只响应想要探测的目标。

为降低分水岭算法产生的过度分割，通常要对梯度函数进行修改，一个简单的方法是对梯度图像进行阈值处理，以消除灰度的微小变化产生的过度分割。即

程序可采用方法：用阈值限制梯度图像以达到消除灰度值的微小变化产生的过度分割，获得适量的区域，再对这些区域的边缘点的灰度级进行从低到高排序，然后在从低到高实现淹没的过程，梯度图像用Sobel算子计算获得。对梯度图像进行阈值处理时，选取合适的阈值对最终分割的图像有很大影响，因此阈值的选取是图像分割效果好坏的一个关键。缺点：实际图像中可能含有微弱的边缘，灰度变化的数值差别不是特别明显，选取阈值过大可能会消去这些微弱边缘。

参考文章：

图像分割的一种重要途径是通过边缘检测，即检测灰度级或者结构具有突变的地方，表明一个区域的终结，也是另一个区域开始的地方。这种不连续性称为边缘。不同的图像灰度不同，边界处一般有明显的边缘，利用此特征可以分割图像。

图像中边缘处像素的灰度值不连续，这种不连续性可通过求导数来检测到。对于阶跃状边缘，其位置对应一阶导数的极值点，对应二阶导数的过零点(零交叉点)。因此常用微分算子进行边缘检测。常用的一阶微分算子有Roberts算子、Prewitt算子和Sobel算子，二阶微分算子有Laplace算子和Kirsh算子等。在实际中各种微分算子常用小区域模板来表示，微分运算是利用模板和图像卷积来实现。这些算子对噪声敏感，只适合于噪声较小不太复杂的图像。

由于边缘和噪声都是灰度不连续点，在频域均为高频分量，直接采用微分运算难以克服噪声的影响。因此用微分算子检测边缘前要对图像进行平滑滤波。LoG算子和Canny算子是具有平滑功能的二阶和一阶微分算子，边缘检测效果较好，

在边缘检测算法中，前三个步骤用得十分普遍。这是因为大多数场合下，仅仅需要边缘检测器指出边缘出现在图像某一像素点的附近，而没有必要指出边缘的精确位置或方向．边缘检测误差通常是指边缘误分类误差，即把假边缘判别成边缘而保留，而把真边缘判别成假边缘而去掉．边缘估计误差是用概率统计模型来描述边缘的位置和方向误差的．我们将边缘检测误差和边缘估计误差区分开，是因为它们的计算方法完全不同，其误差模型也完全不同．

Roberts算子 ：边缘定位准，但是对噪声敏感。适用于边缘明显且噪声较少的图像分割。Roberts边缘检测算子是一种利用局部差分算子寻找边缘的算子,Robert算子图像处理后结果边缘不是很平滑。经分析，由于Robert算子通常会在图像边缘附近的区域内产生较宽的响应，故采用上述算子检测的边缘图像常需做细化处理，边缘定位的精度不是很高。

Prewitt算子 ：对噪声有抑制作用，抑制噪声的原理是通过像素平均，但是像素平均相当于对图像的低通滤波，所以Prewitt算子对边缘的定位不如Roberts算子。

Sobel算子 ：Sobel算子和Prewitt算子都是加权平均，但是Sobel算子认为，邻域的像素对当前像素产生的影响不是等价的，所以距离不同的像素具有不同的权值，对算子结果产生的影响也不同。一般来说，距离越远，产生的影响越小。

Isotropic Sobel算子 ：加权平均算子，权值反比于邻点与中心点的距离，当沿不同方向检测边缘时梯度幅度一致，就是通常所说的各向同性。
在边沿检测中，常用的一种模板是Sobel 算子。Sobel 算子有两个，一个是检测水平边沿的；另一个是检测垂直平边沿的 。Sobel算子另一种形式是各向同性Sobel(Isotropic Sobel)算子，也有两个，一个是检测水平边沿的，另一个是检测垂直平边沿的 。各向同性Sobel算子和普通Sobel算子相比，它的位置加权系数更为准确，在检测不同方向的边沿时梯度的幅度一致。由于建筑物图像的特殊性，我们可以发现，处理该类型图像轮廓时，并不需要对梯度方向进行运算，所以程序并没有给出各向同性Sobel算子的处理方法。

1971年，R.Kirsch[34]提出了一种能检测边缘方向的Kirsch算子新方法：它使用了8个模板来确定梯度幅度值和梯度的方向。

图像中的每个点都用8个掩模进行卷积，每个掩模对某个特定边缘方向作出最大响应。所有8个方向中的最大值作为边缘幅度图像的输出。最大响应掩模的序号构成了对边缘方向的编码。
Kirsch算子的梯度幅度值用如下公式：

不同检测算子的对比：

参考文章：

文章引用于 木夜溯
编辑 Lornatang
校准 Lornatang

❻ 邻近算法的算法流程

1. 准备数据，对数据进行预处理
2. 选用合适的数据结构存储训练数据和测试元组
3. 设定参数，如k
4.维护一个大小为k的的按距离由大到小的优先级队列，用于存储最近邻训练元组。随机从训练元组中选取k个元组作为初始的最近邻元组，分别计算测试元组到这k个元组的距离，将训练元组标号和距离存入优先级队列
5. 遍历训练元组集，计算当前训练元组与测试元组的距离，将所得距离L 与优先级队列中的最大距离Lmax
6. 进行比较。若L>=Lmax，则舍弃该元组，遍历下一个元组。若L < Lmax，删除优先级队列中最大距离的元组，将当前训练元组存入优先级队列。
7. 遍历完毕，计算优先级队列中k 个元组的多数类，并将其作为测试元组的类别。
8. 测试元组集测试完毕后计算误差率，继续设定不同的k值重新进行训练，最后取误差率最小的k 值。

❼ 邻近算法的优点

1.简单，易于理解，易于实现，无需估计参数，无需训练；
2. 适合对稀有事件进行分类；
3.特别适合于多分类问题(multi-modal,对象具有多个类别标签)， kNN比SVM的表现要好。

❽ 邻近图算法基本思想是什么为何说该算法能够节省能量

邻近图的功率控制算法的基本思想。如果一个样本在特征空间中的K个最相似（即特征空间中最邻近）的样本中的大多数属于某一个类别，则该样本也属于这个类别。它的整体思想简单，效果强大。

❾ knn算法是什么

KNN（K- Nearest Neighbor）法即K最邻近法，最初由Cover和Hart于1968年提出，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。

作为一种非参数的分类算法，K-近邻（KNN）算法是非常有效和容易实现的。它已经广泛应用于分类、回归和模式识别等。

介绍

KNN算法本身简单有效，它是一种lazy-learning算法，分类器不需要使用训练集进行训练，训练时间复杂度为0。KNN分类的计算复杂度和训练集中的文档数目成正比，也就是说，如果训练集中文档总数为n，那么KNN的分类时间复杂度为O(n)。

KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。

❿ 使用Node.js如何实现K最近邻分类算法

源于数据挖掘的一个作业， 这里用Node.js技术来实现一下这个机器学习中最简单的算法之一k-nearest-neighbor算法(k最近邻分类法)。
k-nearest-neighbor-classifier
还是先严谨的介绍下。急切学习法（eager learner）是在接受待分类的新元组之前就构造了分类模型，学习后的模型已经就绪，急着对未知的元组进行分类，所以称为急切学习法，诸如决策树归纳，贝叶斯分类等都是急切学习法的例子。惰性学习法（lazy learner）正好与其相反，直到给定一个待接受分类的新元组之后，才开始根据训练元组构建分类模型，在此之前只是存储着训练元组，所以称为惰性学习法，惰性学习法在分类进行时做更多的工作。
本文的knn算法就是一种惰性学习法，它被广泛应用于模式识别。knn基于类比学习，将未知的新元组与训练元组进行对比，搜索模式空间，找出最接近未知元组的k个训练元组，这里的k即是knn中的k。这k个训练元祖就是待预测元组的k个最近邻。
balabala了这么多，是不是某些同学想大喊一声..speak Chinese! 还是来通俗的解释下，然后再来看上面的理论应该会明白很多。小时候妈妈会指着各种各样的东西教我们，这是小鸭子，这个红的是苹果等等，那我们哼哧哼哧的看着应答着，多次被教后再看到的时候我们自己就能认出来这些事物了。主要是因为我们在脑海像给这个苹果贴了很多标签一样，不只是颜色这一个标签，可能还有苹果的形状大小等等。这些标签让我们看到苹果的时候不会误认为是橘子。其实这些标签就对应于机器学习中的特征这一重要概念，而训练我们识别的过程就对应于泛化这一概念。一台iphone戴了一个壳或者屏幕上有一道划痕，我们还是能认得出来它，这对于我们人来说非常简单，但蠢计算机就不知道怎么做了，需要我们好好调教它，当然也不能过度调教2333，过度调教它要把其他手机也认成iphone那就不好了，其实这就叫过度泛化。
所以特征就是提取对象的信息，泛化就是学习到隐含在这些特征背后的规律，并对新的输入给出合理的判断。
我们可以看上图，绿色的圆代表未知样本，我们选取距离其最近的k个几何图形，这k个几何图形就是未知类型样本的邻居，如果k=3，我们可以看到有两个红色的三角形，有一个蓝色的三正方形，由于红色三角形所占比例高，所以我们可以判断未知样本类型为红色三角形。扩展到一般情况时，这里的距离就是我们根据样本的特征所计算出来的数值，再找出距离未知类型样本最近的K个样本，即可预测样本类型。那么求距离其实不同情况适合不同的方法，我们这里采用欧式距离。
综上所述knn分类的关键点就是k的选取和距离的计算。
2. 实现
我的数据是一个xls文件，那么我去npm搜了一下选了一个叫node-xlrd的包直接拿来用。
// node.js用来读取xls文件的包
var xls = require('node-xlrd');
然后直接看文档实例即可，把数据解析后插入到自己的数据结构里。
var data = [];// 将文件中的数据映射到样本的属性var map = ['a','b','c','d','e','f','g','h','i','j','k'];// 读取文件
xls.open('data.xls', function(err,bk){
if(err) {console.log(err.name, err.message); return;}
var shtCount = bk.sheet.count;
for(var sIdx = 0; sIdx < shtCount; sIdx++ ){
var sht = bk.sheets[sIdx],
rCount = sht.row.count,
cCount = sht.column.count;
for(var rIdx = 0; rIdx < rCount; rIdx++){
var item = {};
for(var cIdx = 0; cIdx < cCount; cIdx++){
item[map[cIdx]] = sht.cell(rIdx,cIdx);
}
data.push(item);
}
}
// 等文件读取完毕后 执行测试
run();
});
然后定义一个构造函数Sample表示一个样本，这里是把刚生成的数据结构里的对象传入，生成一个新的样本。
// Sample表示一个样本
var Sample = function (object) {
// 把传过来的对象上的属性克隆到新创建的样本上
for (var key in object)
{
// 检验属性是否属于对象自身
if (object.hasOwnProperty(key)) {
this[key] = object[key];
}
}
}
再定义一个样本集的构造函数
// SampleSet管理所有样本 参数k表示KNN中的kvar SampleSet = function(k) {
this.samples = [];
this.k = k;
};
// 将样本加入样本数组
SampleSet.prototype.add = function(sample) {
this.samples.push(sample);
}
然后我们会在样本的原型上定义很多方法，这样每个样本都可以用这些方法。
// 计算样本间距离 采用欧式距离
Sample.prototype.measureDistances = function(a, b, c, d, e, f, g, h, i, j, k) {
for (var i in this.neighbors)
{
var neighbor = this.neighbors[i];
var a = neighbor.a - this.a;
var b = neighbor.b - this.b;
var c = neighbor.c - this.c;
var d = neighbor.d - this.d;
var e = neighbor.e - this.e;
var f = neighbor.f - this.f;
var g = neighbor.g - this.g;
var h = neighbor.h - this.h;
var i = neighbor.i - this.i;
var j = neighbor.j - this.j;
var k = neighbor.k - this.k;
// 计算欧式距离
neighbor.distance = Math.sqrt(a*a + b*b + c*c + d*d + e*e + f*f + g*g + h*h + i*i + j*j + k*k);
}
};
// 将邻居样本根据与预测样本间距离排序
Sample.prototype.sortByDistance = function() {
this.neighbors.sort(function (a, b) {
return a.distance - b.distance;
});
};
// 判断被预测样本类别
Sample.prototype.guessType = function(k) {
// 有两种类别 1和-1
var types = { '1': 0, '-1': 0 };
// 根据k值截取邻居里面前k个
for (var i in this.neighbors.slice(0, k))
{
var neighbor = this.neighbors[i];
types[neighbor.trueType] += 1;
}
// 判断邻居里哪个样本类型多
if(types['1']>types['-1']){
this.type = '1';
} else {
this.type = '-1';
}
}
注意到我这里的数据有a-k共11个属性，样本有1和-1两种类型，使用truetype和type来预测样本类型和对比判断是否分类成功。
最后是样本集的原型上定义一个方法，该方法可以在整个样本集里寻找未知类型的样本，并生成他们的邻居集，调用未知样本原型上的方法来计算邻居到它的距离，把所有邻居按距离排序，最后猜测类型。
// 构建总样本数组，包含未知类型样本
SampleSet.prototype.determineUnknown = function() {

for (var i in this.samples)
{
// 如果发现没有类型的样本
if ( ! this.samples[i].type)
{
// 初始化未知样本的邻居
this.samples[i].neighbors = [];
// 生成邻居集
for (var j in this.samples)
{
// 如果碰到未知样本 跳过
if ( ! this.samples[j].type)
continue;
this.samples[i].neighbors.push( new Sample(this.samples[j]) );
}
// 计算所有邻居与预测样本的距离
this.samples[i].measureDistances(this.a, this.b, this.c, this.d, this.e, this.f, this.g, this.h, this.k);
// 把所有邻居按距离排序
this.samples[i].sortByDistance();
// 猜测预测样本类型
this.samples[i].guessType(this.k);
}
}
};
最后分别计算10倍交叉验证和留一法交叉验证的精度。
留一法就是每次只留下一个样本做测试集，其它样本做训练集。
K倍交叉验证将所有样本分成K份，一般均分。取一份作为测试样本，剩余K-1份作为训练样本。这个过程重复K次，最后的平均测试结果可以衡量模型的性能。
k倍验证时定义了个方法先把数组打乱随机摆放。
// helper函数 将数组里的元素随机摆放
function ruffle(array) {
array.sort(function (a, b) {
return Math.random() - 0.5;
})
}
剩余测试代码好写，这里就不贴了。
测试结果为
用余弦距离等计算方式可能精度会更高。
3. 总结
knn算法非常简单，但却能在很多关键的地方发挥作用并且效果非常好。缺点就是进行分类时要扫描所有训练样本得到距离，训练集大的话会很慢。
可以用这个最简单的分类算法来入高大上的ML的门，会有点小小的成就感。