快速近似最近邻算法介绍

⑴ 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。

⑵ 大数据挖掘的算法有哪些

大数据挖掘的算法：
1.朴素贝叶斯，超级简单，就像做一些数数的工作。如果条件独立假设成立的话，NB将比鉴别模型收敛的更快，所以你只需要少量的训练数据。即使条件独立假设不成立，NB在实际中仍然表现出惊人的好。
2. Logistic回归，LR有很多方法来对模型正则化。比起NB的条件独立性假设，LR不需要考虑样本是否是相关的。与决策树与支持向量机不同，NB有很好的概率解释，且很容易利用新的训练数据来更新模型。如果你想要一些概率信息或者希望将来有更多数据时能方便的更新改进模型，LR是值得使用的。
3.决策树，DT容易理解与解释。DT是非参数的，所以你不需要担心野点（或离群点）和数据是否线性可分的问题，DT的主要缺点是容易过拟合，这也正是随机森林等集成学习算法被提出来的原因。
4.支持向量机，很高的分类正确率，对过拟合有很好的理论保证，选取合适的核函数，面对特征线性不可分的问题也可以表现得很好。SVM在维数通常很高的文本分类中非常的流行。

如果想要或许更多更详细的讯息，建议您去参加CDA数据分析课程。大数据分析师现在有专业的国际认证证书了，CDA，即“CDA 数据分析师”，是在数字经济大背景和人工智能时代趋势下，面向全行业的专业权威国际资格认证， 旨在提升全民数字技能，助力企业数字化转型，推动行业数字化发展。 “CDA 数据分析师”具体指在互联网、金融、零售、咨询、电信、医疗、旅游等行业专门从事数据的采集、清洗、处理、分析并能制作业务报告、 提供决策的新型数据分析人才。点击预约免费试听课。

⑶ k近邻算法的案例介绍

如 上图所示，有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。也就是说，现在， 我们不知道中间那个绿色的数据是从属于哪一类（蓝色小正方形or红色小三角形），下面，我们就要解决这个问题：给这个绿色的圆分类。我们常说，物以类聚，人以群分，判别一个人是一个什么样品质特征的人，常常可以从他/她身边的朋友入手，所谓观其友，而识其人。我们不是要判别上图中那个绿色的圆是属于哪一类数据么，好说，从它的邻居下手。但一次性看多少个邻居呢？从上图中，你还能看到：
如果K=3，绿色圆点的最近的3个邻居是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。 如果K=5，绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。 于此我们看到，当无法判定当前待分类点是从属于已知分类中的哪一类时，我们可以依据统计学的理论看它所处的位置特征，衡量它周围邻居的权重，而把它归为(或分配)到权重更大的那一类。这就是K近邻算法的核心思想。
KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。
KNN 算法本身简单有效，它是一种 lazy-learning 算法，分类器不需要使用训练集进行训练，训练时间复杂度为0。KNN 分类的计算复杂度和训练集中的文档数目成正比，也就是说，如果训练集中文档总数为 n，那么 KNN 的分类时间复杂度为O(n)。
KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。
K 近邻算法使用的模型实际上对应于对特征空间的划分。K 值的选择，距离度量和分类决策规则是该算法的三个基本要素： K 值的选择会对算法的结果产生重大影响。K值较小意味着只有与输入实例较近的训练实例才会对预测结果起作用，但容易发生过拟合；如果 K 值较大，优点是可以减少学习的估计误差，但缺点是学习的近似误差增大，这时与输入实例较远的训练实例也会对预测起作用，是预测发生错误。在实际应用中，K 值一般选择一个较小的数值，通常采用交叉验证的方法来选择最优的 K 值。随着训练实例数目趋向于无穷和 K=1 时，误差率不会超过贝叶斯误差率的2倍，如果K也趋向于无穷，则误差率趋向于贝叶斯误差率。 该算法中的分类决策规则往往是多数表决，即由输入实例的 K 个最临近的训练实例中的多数类决定输入实例的类别 距离度量一般采用 Lp 距离，当p=2时，即为欧氏距离，在度量之前，应该将每个属性的值规范化，这样有助于防止具有较大初始值域的属性比具有较小初始值域的属性的权重过大。 KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成反比。该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。 该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。可以采用权值的方法（和该样本距离小的邻居权值大）来改进。
该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。
实现 K 近邻算法时，主要考虑的问题是如何对训练数据进行快速 K 近邻搜索，这在特征空间维数大及训练数据容量大时非常必要。

⑷ K-近邻算法 KNN

K值选择问题 ，李航博士的一书“统计学习方法”上所说：

近似误差（train loss）：

估计误差（test loss）：

 在实际应用中，K值一般取一个比较小的数值，例如采用交叉验证法（简单来说，就是把训练数据在分成两组:训练集和验证集）来选择最优的K值。

 例如：将数据分成4份，其中一份作为验证集。然后经过4次(组)的测试，每次都更换不同的验证集。即得到4组模型的结果，取平均值作为最终结果。又称4折交叉验证。

 据KNN每次需要预测一个点时，我们都需要计算训练数据集里每个点到这个点的距离，然后选出距离最近的k个点进行投票。当数据集很大时，这个计算成本非常高，针对N个样本，D个特征的数据集，其算法复杂度为O(DN ² )。

在构建kd树时，有2个关键问题：
（1）选择向量的哪一维进行划分? 随机选择某一维或按顺序选择，但是更好的方法应该是在数据比较分散的那一维进行划分（分散的程度可以根据方差来衡量）。
（2）如何划分数据? 好的划分方法可以使构建的树比较平衡，可以每次选择中位数来进行划分。
构造方法

  给定一个二维空间数据集：T={(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}，构造一个平衡kd树。

 优点：

 缺点：

⑸ 什么叫做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值的方法是自助法。

⑹ 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近邻搜索及指定半径的范围搜索。多维空间的检索，调用方式与此例相差无多。

⑺ 2021-01-21

摘要

人脸聚类最近吸引了越来越多的研究兴趣，以利用网络上的大量人脸图像。图卷积网络（GCN）由于其强大的表示能力而实现了最先进的性能。然而，现有的基于 GCN 的方法主要根据特征空间中的 kNN 关系构建人脸图，这可能导致连接不同类别的两个人脸的大量噪声边缘。当消息通过这些噪声边缘时，面部特征将被污染，从而降低 GCN 的性能。在本文中，提出了一种名为 Ada-NETS 的新算法，通过为 GCN 构建干净的图来聚类人脸。在 Ada-NETS 中，每个人脸都被转换到一个新的结构空间，通过考虑相手租邻图像的人脸特征来获得鲁棒的特征。然后，提出了一种自适应邻居发现策略来确定连接到每个人脸图像的适当数量的边。它显着减少了噪声边缘，同时保持了良好的边缘，从而为 GCN 构建具有干净而丰富边缘的图形来聚类人脸。在多个公共聚类数据集上的实验表明，Ada-NETS 显着优于当前最先进的方法，证明了其优越性和泛化性。

1.引言

近年来，网络上的图像数量迅速增加，其中很大一部分是以人为中心的照片。在几乎没有人为参与的情况下理解和管理这些照片是一项艰巨的任务，例如将来自某个人的照片关联在一起。面对这些需求的一个基本问题是人脸聚类（Manning et al., 2008）。

近年来，人脸聚类得到了彻底的研究。使用图卷积网络获得了显着的性能改进（Wang 等人，2019b；Yang 等人，2019；2020；Guo 等人，2020；Shen 等人，2021）由于其强大的特征传播能力.代表性的 DA-Net (Guo et al., 2020) 和 STAR-FC (Shen et al., 2021) 使用 GCN 通过顶点或边分类任务来学习增强的特征嵌入，以辅助聚类。

然而，限制现有基于 GCN 的人脸聚类算法能力的主要问题是人脸图中存在噪声边缘。如图1（b）所示，噪声边缘是指不同类别的两个面之间的连接。与 Citeseer、Cora 和 Pubmed 等以显式链接关系作为边的常见图形数据集不同（Kipf & Welling, 2017），人脸图像不包含明确的结构信息，而仅包含从经过训练的 CNN 模型中提取的深层特征。因此，人脸图像被视为顶点，人脸图像之间的边缘通常在构建图时基于 kNN (Cover & Hart, 1967) 关系构建：每个人脸作为一个探针，通过以下方式检索其 k 个最近邻居深度特征（Wang 等人，2019b；Yang 等人，2019；2020；Guo 等人，2020；Shen 等人，2021）。 kNN 关系并不总是可靠的，因为深度特征不够准确。因此，噪声边缘与 kNN 一起被引入到图中。噪声边缘问题在人脸聚类中很常见，但很少受到研究关注。例如，(Yang et al., 2020; Shen et al., 2021) 中使用的图在测试中包含约 38.23% 的噪声边缘。噪声边缘会在顶点之间传播噪声信息，在聚合时会损害它们的特征，从而导致性能下降。在图 1 (b) 中，三角形顶点 v1 与三个不同类别的顶点相连，它会被图中传递的消息污染。因此，基于 GCN 的链接预测无法有效解决相关工作中的噪声边缘问题（Wang 等人，2019b；Yang 等人，2020；Shen 等人，2021）。

图 1：基于 GCN 的人脸聚类中的噪声边缘问题。图中不同的形状代表不同的类别。 (a) 要聚类的人脸图像。 (b) 在基于 na ̈ıve kNN 构建图时引入了噪声边缘。 (c) 通过特征距离连接边缘可能会导致噪声边缘。 (d) 现有的“一刀切”的解决方案对每个顶点使用固定数量的邻居会引入许多噪声边缘。

如图 1 (c) (d) 所示，去除人脸图中的噪声边缘的挑战是双重的。首先，深度特征的表示能力在现实世界的数据中是有限的。仅根据深度特征很难判断两个顶点是否属于同一类，因此连接不同类的两个顶点不可避免地会带来噪声边缘。其次侍薯消，在构建图时很难确定每个顶点连接多少条边：连接的边太少会导致图中的信息聚合不足。连接的边太多会增加噪声边的数量，并且顶点特征会被错误连接的顶点老知污染。虽然 Clusformer (Nguyen et al., 2021) 和 GAT (Velickovic et al., 2018) 试图通过注意力机制减少噪声边缘的影响，但各个顶点之间的连接非常复杂，因此很难找到注意力权重学习的常见模式（Yang et al., 2020）。

为了克服这些严峻的挑战，每个顶点周围的特征都被考虑在内，因为它们可以提供更多信息。具体来说，当考虑附近的其他顶点时，可以改进每个顶点特征表示。这有利于解决图 1 (c) 中的表示挑战。然后，一个顶点与其他顶点之间的边数可以从它周围的特征模式中学习，而不是为所有顶点手动设计参数。这种学习方法可以有效地减少噪声边缘的连接，这对于解决图 1 (d) 中的第二个挑战至关重要。基于上述思想，提出了一种新的聚类算法，称为结构空间中的自适应邻居发现（Ada-NETS），用于处理聚类中的噪声边缘问题。在 Ada-NETS 中，首先提出了一个结构空间，其中顶点在感知数据分布后，可以通过编码更多的纹理信息来获得鲁棒的特征。然后，仔细设计候选邻居质量标准以指导构建噪声较小但丰富的边缘，以及可学习的自适应滤波器来学习该标准。通过这种方式，自适应地发现每个顶点的邻居，以构建具有干净和丰富边缘的图。最后，GCN 将此图作为输入来聚类人脸。

本文的主要贡献总结如下：

• 据我们所知，这是第一篇在人脸图像上为 GCN 构建图时解决噪声边缘问题的论文。同时，本文阐述了其成因、重大影响、现有解决方案的弱点以及解决该问题的挑战。

• 所提出的 Ada-NETS 可以缓解在人脸图像上构建图形时的噪声边缘问题，从而极大地改进 GCN 以提高聚类性能。

• Ada-NETS 在聚类任务上取得了最先进的性能，在人脸、人物和衣服数据集上大大超过了之前的表现。

2 相关工作

FaceClustering 人脸聚类任务软化人脸大规模样本和复杂数据分布，因此引起了特别的研究关注。经典的无监督方法速度很慢，并且由于其简单的分布假设无法实现良好的性能，例如 K-Means 中的凸形数据（Lloyd，1982）和 DBSCAN 中相似的数据密度（Ester et al.，1996））。近年来，基于 GCN 的监督方法被证明对人脸聚类有效且高效。 L-GCN (Wang et al., 2019b) 部署了一个 GCN 用于子图的链接预测。 DS-GCN (Yang et al., 2019) 和 VE-GCN (Yang et al., 2020) 都提出了基于大 kNN 图的两阶段 GCN 聚类。 DA-Net (Guo et al., 2020) 通过基于密度的图利用非本地上下文信息进行聚类。 Clusformer (Nguyen et al., 2021) 将人脸与变压器进行聚类。 STAR-FC (Shen et al., 2021) 开发了一种结构保留的采样策略来训练边缘分类 GCN。这些成就展示了 GCN 在表示和聚类方面的强大功能。然而，现有方法大多基于kNN构建人脸图，其中包含大量噪声边缘。在构建这些图时，仅根据并不总是准确的深度特征来获得顶点之间的相似度，并且每个顶点的边数是固定的或由相似度阈值确定。

Graph Convolutional Networks GCN 被提出来处理非欧几里得数据，并在学习图模式方面展示了它们的能力。它最初用于转导式半监督学习 (Kipf & Welling, 2017)，并由学习特征聚合原理的 GraphSAGE (Hamilton et al., 2017) 扩展到归纳任务。为了进一步扩展 GCN 的表示能力，可学习的边权重被引入到图注意网络 (GAT) 中的图聚合中 (Velickovic et al., 2018)。除了人脸聚类，GCN 还用于许多任务，例如基于骨架的动作识别 (Yan et al., 2018)、知识图谱 (Schlichtkrull et al., 2018) 和推荐系统 (Ying et al., 2018) .然而，这些方法是在结构数据上提出的，其中明确给出了边缘。如果图形是由大量噪声边缘构成的，则 GCN 在人脸图像数据集上可能表现不佳。

图 2：Ada-NETS 的框架。 （一世）。将特征转换到结构空间以获得更好的相似度度量。 (二)。每个顶点的邻居由自适应滤波器发现。 （三）。使用 (II) 发现的邻居关系构建图，GCN 模型使用该图对顶点对进行分类。最终的聚类结果是使用来自 GCN 的嵌入来链接具有高相似性的顶点对获得的。

3 方法论

人脸聚类旨在将一组人脸样本进行分组，使一个组中的样本属于一个身份，不同组中的任意两个样本属于不同的身份。给定一组特征向量 V = {v1,v2,...,vi,...,vN | vi ∈ RD} 由经过训练的 CNN 模型从人脸图像中提取，聚类任务为每个向量 vi 分配一个组标签。 N是样本总数，D是每个特征的维度。提出了如图 2 所示的 Ada-NETS 算法，通过处理人脸图中的噪声边缘来对人脸进行聚类。首先，将特征转换为提出的结构空间以获得准确的相似度度量。然后使用自适应邻居发现策略为每个顶点查找邻居。根据发现结果，构建一个具有干净和丰富边缘的图作为 GCN 的输入图，用于最终聚类。

3.1 结构空间

噪声边缘问题会导致顶点特征的污染，降低基于 GCN 的聚类的性能。仅仅根据它们的深度特征很难确定两个顶点是否属于同一类，因为不同类的两个顶点也可以具有很高的相似性，从而引入噪声边缘。不幸的是，据我们所知，几乎所有现有方法（Wang 等人，2019b；Yang 等人，2020；Guo 等人，2020；Shen 等人，2021）仅基于成对余弦构建图使用深度特征的顶点之间的相似性。实际上，可以通过考虑结构信息来改进相似度度量，即数据集图像之间的邻域关系。基于这一思想，提出了结构空间的概念来应对这一挑战。在结构空间中，特征可以通过感知数据分布来编码更多的纹理信息，从而更加稳健（Zhang et al., 2020）。一个转换函数 φ 被部署来将一个特征 vi 转换为结构空间，记为 vis：

vis = φ(vi|V),∀i ∈ {1,2,··· ,N}。 (1)

如图2（I）所示，在结构空间的帮助下，对于一个顶点vi，它与其他顶点的相似度通过以下步骤计算：首先，通过近似最近邻（Approximate Nearest-neighbour）获得vi的kNN（ ANN) 算法基于 vi 与其他顶点之间的余弦相似度，记为 N (vi, k) = {vi1 , vi2 , ···, vik }。其次，通过核方法 (Shawe-Taylor & Cristianini, 2004) 进行激励，我们不是直接求解 φ 的形式，而是通过以下方式定义 vi 与其在结构空间中的每个候选者的相似性

κ􏰅v,v =􏰈vs,vs􏰉 iij iij

(2) 其中 η 加权余弦相似度 scos 􏰅v ,v 􏰆 = vi·vij 和 Jaccard 相似度

􏰎(1−η)sJac􏰅v,v 􏰆+ηscosv,v , ∀j∈{1,2,···,k}, i ij i ij

i ij ∥vi∥∥vij ∥

sJac 􏰅v , v 􏰆 受到基于公共邻居的度量的启发（Zhong et al., 2017）。和

我

上面的定义， κ 􏰅v , v 测量 v 和 v 在结构空间中的相似性。

iij i ij 3.2 自适应邻居发现

现有方法通过深度特征（Wang 等人，2019b；Yang 等人，2020；Shen 等人，2021）或使用固定的相似度阈值（Guo 等人，2020）从朴素的 kNN 关系中连接边缘。这些方法都是一刀切的解决方案，超参数对性能有很大影响。为了解决这个问题，提出了自适应邻居发现模块来学习每个顶点周围的特征模式，如图2（II）所示。

对于顶点vi，其大小为j的候选邻居是基于深度特征相似度的j个最近邻居顶点，其中j = 1, 2,····,k。它的邻居是指一个特定大小的候选邻居，满足如下所述的某些特定标准。 vi 与其所有邻居之间的边被构造。

3.2.1 候选邻居质量标准

受顶点置信度估计方法 (Yang et al., 2020) 的启发，设计了一种启发式标准来评估每个探测顶点的候选邻居的质量。好邻居应该是干净的，即大多数邻居应该与探测顶点具有相同的类标签，这样在构建图时就不会大量包含噪声边缘。邻居也应该是丰富的，这样消息才能在图中完全传递。为了满足这两个原则，在信息检索中根据Fβ-score（Rijsbergen，1979）提出了标准。与视觉语法类似（Nguyen et al., 2021），所有候选邻居都按照与序列中探测顶点的相似度排序。给定由顶点 vi 探测到的大小为 j 的候选邻居，其质量标准 Q (j) 定义为：

其中 P rj 和 Rcj 是前 j 个候选邻居相对于 vi 的标签的精度和召回率。 β 是权重平衡精度和召回率。较高的 Q 值表示更好的候选邻居质量。

3.2.2 自适应滤波器

使用上述标准，koff 被定义为要选择的邻居数量的启发式真实值：

3.3 用于人脸聚类的 ADA-NETS

为了有效解决人脸聚类中的噪声边缘问题，Ada-NETS 首先利用所提出的结构空间和自适应邻居发现来构建具有干净和丰富边缘的图。然后使用 GCN 模型完成该图中的聚类，如图 2（III）所示。使用上述结构空间中的相似度度量和自适应邻居发现方法，顶点vi的发现邻居表示为N s(vi, k)：

其中 Ind 表示按 κ 􏰅v , v 􏰆 降序排列的 v 的索引。基于这些邻居关系，如果其中任何一个是另一个已发现的邻居，则通过链接两个顶点之间的边来生成无向图 G (F, A)。 F = [v1 , v2 , ··· , vN ]T 为顶点特征矩阵，A 为邻接矩阵：

通过构建的图 G(F,A)，使用 GCN 模型来学习两个顶点是否属于同一类。一个 GCN 层定义为：

其中 A ̃ = A + I, I ∈ RN ×N 是单位矩阵，D ̃ 是对角度矩阵 D ̃ ii = 􏰊Nj=1 A ̃ i,j , Fl 和 Wl 分别是输入特征矩阵和第 l 层的权重矩阵，和

σ(·) 是一个激活函数。本文使用了两个 GCN 层，然后是一个具有 PReLU (He et al., 2015) 激活和一个归一化的 FC 层。对于一批随机采样的顶点 Bv，训练损失定义为铰链损失的变体版本（Rosasco et al., 2004）：

其中 yvi,vj 是批次 Bv 中两个顶点 vi 和 vj 的 GCN 输出特征 v′i 和 v′j 的余弦相似度，[·]+ = max(0,·)，∥li = lj∥ 是正对的数量，即vi的ground-truth标签li和vj的ground-truth标签lj相同； β1 和 β2 是正负损失的边际，λ 是平衡这两个损失的权重。

在推理过程中，将测试数据的整个图输入到 GCN 中，得到所有顶点的增强特征 F′ = [v′1, v′2, ···, v′N ]T ∈ RN×D′，其中 D′是每个新特征的维度。

当顶点对的相似度分数大于预定义的阈值 θ 时，它们将被链接。最后，聚类是通过使用联合查找算法传递合并所有链接来完成的，即无等待并行算法（Anderson & Woll，1991）。

4 项实验

4.1 评估指标、数据集和实验设置

Signal-Noise Rate (SNR) 和 Q-value 用于直接评估图构建的质量，其中 SNR 是图中正确边数与噪声边数之比。 BCubed F-score FB (Bagga & Baldwin, 1998; Amigo ́ et al., 2009) 和 Pairwise F-score FP (Shi et al., 2018) 用于评估最终的聚类性能。

实验中使用了三个数据集：MS-Celeb-1M (Guo et al., 2016; Deng et al., 2019) 是一个大规模的人脸数据集，经过数据清洗后包含 86K 身份的约 580 万张人脸图像。为了公平比较，我们遵循与 VE-GCN (Yang et al., 2019) 相同的协议和特征，将数据集按身份平均分为十部分，并将第 0 部分作为训练集，将第 1 部分到第 9 部分作为训练集测试集。除了人脸数据，Ada-NETS 还被评估为在聚类其他对象方面的潜力。服装数据集 DeepFashion (Liu et al., 2016) 使用与 VE-GCN (Yang et al., 2020) 相同的子集、分割设置和特征，其中有 3,997 个类别的 25,752 张图像用于训练，26,960 张图像用于测试的 3,984 个类别。 MSMT17 (Wei et al., 2018) 是目前最大的 ReID 数据集。它的图像是在不同的天气、光照条件和时间段下从 15 个摄像机捕获的，这对聚类具有挑战性。有 1,041 个人的 32,621 张图像用于训练，3,060 个人的 93,820 张图像用于测试。特征是从在训练集上训练的模型中获得的（He et al., 2020）。

学习率最初是 0.01 用于训练自适应滤波器，0.1 用于训练具有余弦退火的 GCN。对于 Huberloss，δ=1，β1 =0.9，β2 =1.0，对于 Hingleloss，λ=1，对于 Q 值，β=0.5。使用动量为 0.9 且权重衰减为 1e-5 的 SGD 优化器。 k 在 MS-Celeb-1M、DeepFashion 和 MSMT17 上设置为 80、5、40。实验是使用 PyTorch (Paszke et al., 2019) 和 DGL (Wang et al., 2019a) 进行的。

4.2 方法比较

在具有不同数量未标记图像的 MS-Celeb-1M 数据集上评估人脸聚类性能。比较方法包括经典的聚类方法 K-Means (Lloyd, 1982)、HAC (Sibson, 1973)、DBSCAN (Ester et al., 1996) 和基于图的方法 L-GCN (Wang et al., 2019b)、DS -GCN (Yang et al., 2019)、VE-GCN (Yang et al., 2020)、DA-Net (Guo et al., 2020)、Clusformer (Nguyen et al., 2021) 和 STAR-FC (Shen等人，2021）。在本节中，为了进一步增强 GCN 的聚类性能，在训练图中添加了一些噪声。表 1 中的结果表明，所提出的 Ada-NETS 在所有测试中都达到了最佳性能（θ = 0.96），在 584K 未标记数据上的 BCubed F-score 比 STAR-FC 高 1.19%，达到 91.40%。随着未标记图像数量的增加，所提出的 Ada-NETS 保持了优越的性能，揭示了图构建在大规模聚类中的重要性。

为了进一步评估我们的方法在非人脸聚类任务中的泛化能力，还对 DeepFashion 和 MSMT17 进行了比较。如表 2 所示，Ada-NETS 在衣服和人物聚类任务中取得了最佳性能。与 STAR-FC 相比，衣服聚类的 Pairwise F-score 为 37.07%，达到了惊人的 39.30%，人物聚类的 Pairwise F-score 为 58.80%，达到了 64.05%。

4.3 消融研究

结构空间和自适应邻居发现的研究 表 3 评估了结构空间和自适应邻居发现的贡献。将构建图的 SNR 与 BCubed 和 Pairwise F 分数进行比较。可以观察到，结构空间和自适应邻居发现都有助于性能提升，其中自适应邻居发现贡献更大。使用这两个组件，图的 SNR 大大提高了 13.38 倍，聚类性能也大大提高。图 4 中的每一行显示了以第一张图像作为探针的发现结果，按结构空间中的相似性排序。带有蓝色圆圈的图像与探针具有相同的身份。它们都成功地在结构空间中获得了比代表不同身份的红色三角形更大的相似性。在自适应滤波器的帮助下，黄色垂直线之后的图像被过滤掉，保持干净和丰富的邻居。如果没有自适应滤波器，带有红色三角形的图像将与其探头连接，导致探头污染。

质量标准研究 根据等式3，该标准包含一个超参数β。较小的 β 更强调精确度，更大的 β 更强调召回。我们选择三个最常用的值 β ∈ {0.5, 1.0, 2.0} 来研究它如何影响邻居发现和聚类。表 4 显示了 Ada-NETS 在原始（表示为 Ori.）和结构空间（表示为 Str.）中不同 β 下的性能。 Qbefore 和 Qafter 是大小为 k 和 koff 的候选邻居的 Q 值。 FP和FB是koff下对应的聚类性能。可以观察到，在所有情况下，Qafter 与 Qbefore 相比都有明显的提高。对于相同的β，结构空间比原始空间的改进更明显。如上所述，较高的 Q 值表示更好的候选邻居质量，例如，更多的噪声边缘将被消除（干净）或更多正确的边缘将在图中保留（丰富）。因此，结构空间中的聚类性能也如预期的那样高于原始空间。此外，β = 0.5 在两个空间中均实现了最佳聚类性能，而在结构空间中的敏感度要低得多，达到 95.51% Pairwise F-score 和 94.93% BCubed F-score。这表明了特征表示在结构空间中的鲁棒性。

学习头自适应过滤器

建议使用自适应过滤器从候选邻居中选择邻居。与直接在自适应滤波器中回归 koff 的估计方法（称为 Ekreg）相比，还研究了其他一些估计方法： Ekcls 将 koff 估计表示为 k-

分类任务； EQseq 直接回归所有 j 的 Q 值； EQparam 用二次曲线拟合关于 j 的 Q 值，并估计该曲线的参数。表 5 中的结果表明，估计 koff 的 Ekreg 和 Ekcls 获得的性能明显高于估计 koff 的 EQseq 和 EQparam

估计 Q 值。与 Ekcls 相比，Ekreg 取得了接近的结果，但需要学习的参数更少。 GAT 也通过注意力机制进行了比较以消除噪声边缘，但由于复杂的特征模式而没有获得有竞争力的结果（Yang et al., 2020）。

对 k 的敏感性研究 图 5 (a) 显示了具有 k 方差的聚类性能。 “kNN”表示直接选择最近的k个邻居来构建图，就像现有方法（Yang et al., 2020; Shen et al., 2021）一样，“Structure kNN”表示在N（v）的结构空间中选择kNN , 256)。尽管在结构空间中有所帮助，但两种 kNN 方法都对 k 敏感，因为当 k 增加时会包含更多的噪声边缘。然而，所提出的 Ada-NETS 可以相对稳定地获得良好的性能，表明我们的方法可以有效地提供干净和丰富的邻居来为 GCNs 构建图。

图嵌入的研究 在 Ada-NETS 中，GCN 模块用于生成分布更紧凑的特征，因此更适合聚类。十亿个随机选择的对的 ROC 曲线如图 5 (b) 所示。观察到原始特征嵌入 (OFE) 获得了最差的 ROC 性能，而所提出的 GCN 输出的图嵌入 (GE) 得到了大幅增强。在自适应邻居发现（GE + AND）的帮助下，输出特征更具辨别力。当发现应用在结构空间（GE + AND + SS）时，GCN 可以输出最具区分性的特征。通过 PCA (Pearson, 1901) 对 10 个随机选择的身份进行降维后嵌入的分布如图 5 (c) 所示。可以观察到，在图 5（b）中，一种特征嵌入的 ROC 性能越好，它的嵌入对于某个身份就越紧凑。有了更好的特征嵌入，聚类可以重新开始。这些“GE + AND + SS”的判别图嵌入被用作Ada-NETS的输入，以获得最终的聚类结果进行增强（θ = 0.99）。在表 6 中，将 MS-Celeb-1M 上的聚类结果与使用原始特征嵌入的聚类结果进行了比较。据观察，图嵌入进一步将 Ada-NETS 从最先进的水平提高到了显着的 93.74% 的 Pairwise F-score，在 584K 未标记数据上再次实现了近 1% 的改进。

5 结论

本文提出了一种新的 Ada-NETS 算法来处理在基于 GCN 的人脸聚类中构建图时的噪声边缘问题。在 Ada-NETS 中，首先将特征转换为结构空间以提高相似度度量的准确性。然后使用自适应邻居发现方法在启发式质量标准的指导下自适应地为所有样本寻找邻居。基于发现的邻居关系，构建具有干净和丰富边缘的图作为 GCN 的输入，以获得人脸、衣服和人物聚类任务的最新技术。

⑻ 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）距离测量标准的选择。
距离测量的标准一般选择 欧几里得距离 或者 曼哈顿距离 。

简单例子

⑼ 12 - SVM, KNN，LR, RF简要介绍

这里接 第11篇 的介绍。

支持向量机是可对类别进行分类的有监督的学习算法。其在样本的特征空间中找出间隔最大的超平面对样本进行分类。SVM根据其学习算法不同可划分为线性可分SVM、线性近似可分SVM与非线性SVM。实现上述三种SVM主要依靠核函数—线性核函数、高斯核函数、多项式核函数与Sigmoid核函数，后三种核函数为非线性，一般建议使用高斯核函数。

如上图，对于二分类，SVM需要确定一条最优直线使两类样本分开，在图1-4中A可以看到有多条直线可将两组分开，但最优的是图1-4中B的w*x+b=0直线。对于最优直线的确定，需要使最优直线到最近点的距离最大，最近点被称为支持向量（如图1-4中B的红点/圈），这里的距离是求出点到直线的距离最大，这是在二维空间，当在三维及其以上的空间时，直线变为超平面，距离则需要求点到超平面的几何距离（Westreich et al 2010）。

SVM的优点：（1）适用各种形式的数据，如文本、图像等；（2）泛化能力较好，即其过拟合的风险小；（3）相对较好地处理高维度数据；（4）核函数的应用使其能很好的适应各种情况。其缺点：（1）对大规模数据难以处理；（2）只依靠少数支持向量决定最终结果，如有异常值，则结果容易出现较大偏差；（3）对缺失值敏感（Westreich et al 2010）。

K最近邻算法是通过计算样本特征之间的距离，根据距离k进行分类，属于无参数分类和回归方法（Altman 1992）。距离k的度量可以使用闵可夫斯基距离、欧氏距离与曼哈顿距离等距离公式进行计算，一般其取20以内的正整数，较大的k取值会降低噪音对分析的影响，且一般对于二分类问题，取k为奇数将有利于判别。

闵可夫斯基距离公式为：

上述公式中，当p=2时，变为欧氏距离，当p=1时，变为曼哈顿距离（Hechenbichler and Schliep 2004）。
KNN属于“懒惰学习”，即只是将训练集数据储存起来，再来新样本时进行距离计算，根据投票结果判别新样本属于哪一类。例如图1-6，蓝色方框与红色三角为已知的训练集，当有绿色圆圈新样本进行判别时，假设k为1，则有两个红色三角与一个为蓝色方框参与判别，这样投票结果为2:1，故绿色圆圈属于红色三角形一类；假如k为2，则有两个红色三角与三个为蓝色方框参与判别，这样投票结果为2:3，故绿色圆圈属于蓝色方框。所以k值需要选择，一般是根据经验进行设置，并且每个样本（如红三角）对判别决策所占的比重也可以进行设定即为权重KNN（Hechenbichler and Schliep 2004）。

逻辑回归是一种有监督的学习方法，其函数基本的公式：

上述公式为Sigmoid函数，图为1-7，其输出值在[0, 1]之间，需要选择一个阈值，通常是0.5，当p(x) > 0.5时，x为A类，如果p(x) < 0.5时，x为B类。阈值可以调整，其代表对于这个事情的把握度，如上述的阈值为0.5，如计算的p(x1)=0.3，则有50%的把握认为x1属于B类（Press 2013）。
LR的运算基本过程：（1）假设p(x)=1，构造sigmoid函数，即利用最大似然取对数作为误差函数，用梯度下降求最小的误差函数值，求出a与b；（2）根据训练数据集多组数据，重复循环（1）n次，计算数据集梯度，更新sigmoid参数，确定最终的sigmoid函数；（3）输入预测集数据；（4）运用最终sigmoid函数求解分类（Dreiseitl and Ohno-Machado 2002）。
LR的优点：（1）容易接收新数据，对模型更新；（2）能够容易解决变量间的共线性问题；（3）运算速度快，适合二分类问题。其缺点：（1）适用的数据和具体场景较少；（2）不适用于样本具有很大的特征值（即变量过多）；（3）容易欠拟合，分类准确性较低；（4）使用前提是应变量和自变量有线性关系，只是广义线性模型，不能处理非线性问题。

随机森林是将多个决策树集合在一起的一种算法，基本单元为决策树，并且可以用于回归和分类（Breiman 2001, Liaw and Wiener 2002）。其名字由“随机”与“森林”组成，“随机”有两个含义，一指在训练集中随机且有放回的抽取n个样本进行建模，二指每个节点在特征值M中随机抽取k（k<M）个进行建模，且每个节点处的k应相同，这两个随机使该算法不容易过拟合（Ho 1998）。“森林”即为多个决策树组成，其要求基本同上述的决策树，但这里的决策树没有剪枝的过程，让其尽量生长（Cutler et al 2012）。其将多个决策树组合在一起是采用集成学习方法，该算法的中心思想是让每个决策树产生一个结果，再对这些结果进行统计，哪种结果数量最多，即为最终结果。

RF实现的过程（1）随机有放回的从样本N中选出n个子样本；（2）每个节点在特征值M中随机选出k个特征值；（3）重复第一与第二步s次，创建s个决策树；（4）对s个决策树结果分析，哪一类决策树最多，则最终判别为哪一类。

RF算法主要有两个参数，第一个为抽取每个样本的特征值k，第二个为决策树的数量。特征值k一般建议为全部特征值的开方（Geurts et al 2006）。在确定较优的k后，一般取决策树数为500进行尝试，查看随着决策树的数量增多，袋外错误率是否会稳定在一个定值，取能达到这个定值的最小决策树数的数量。

随机森林算法优点：（1）能够有效处理大数据；（2）能处理高维度变量的样本，不需要降维；（3）能较好处理缺失值问题。其缺点：（1）不能直观进行解释（2）过度拟合某些具有噪声分类。
上述的八种算法，一般多用于二分类问题，如“有或无”与“好或坏”等，但在实际应用中也有较多的多分类问题，如彩虹可以划分7种颜色，当判别一个新的颜色属于这7种颜色的哪一种时，这就需要解决一个七分类问题。多分类是二分类的一个拓展，解决办法有两种，第一种是一对多，即先从K类中选出一种，剩余K-1类归为一种，这样需要建立K个判别模型，当有新数据进行判别时，新样本需在K个判别模型中，同时进行判别，看被判别为哪一类的可能性最大，就判别为哪类；

⑽ 机器学习中算法的优缺点之最近邻算法

机器学习中有个算法是十分重要的，那就是最近邻算法，这种算法被大家称为KNN。我们在学习机器学习知识的时候一定要学习这种算法，其实不管是什么算法都是有自己的优缺点的，KNN算法也不例外，在这篇文章中我们就详细的给大家介绍一下KNN算法的优缺点，大家一定要好好学起来哟。
说到KNN算法我们有必要说一下KNN算法的主要过程，KNN算法的主要过程有四种，第一就是计算训练样本和测试样本中每个样本点的距离，第二个步骤就是对上面所有的距离值进行排序(升序)。第三个步骤就是选前k个最小距离的样本。第四个步骤就是根据这k个样本的标签进行投票，得到最后的分类类别。
那么大家是否知道如何选择一个最佳的K值，这取决于数据。一般情况下，在分类时较大的K值能够减小噪声的影响，但会使类别之间的界限变得模糊。一般来说，一个较好的K值可通过各种启发式技术来获取，比如说交叉验证。另外噪声和非相关性特征向量的存在会使K近邻算法的准确性减小。近邻算法具有较强的一致性结果，随着数据趋于无限，算法保证错误率不会超过贝叶斯算法错误率的两倍。对于一些好的K值，K近邻保证错误率不会超过贝叶斯理论误差率。
那么KNN算法的优点是什么呢？KNN算法的优点具体体现在六点，第一就是对数据没有假设，准确度高，对outlier不敏感。第二就是KNN是一种在线技术，新数据可以直接加入数据集而不必进行重新训练。第三就是KNN理论简单，容易实现。第四就是理论成熟，思想简单，既可以用来做分类也可以用来做回归。第五就是可用于非线性分类。第六就是训练时间复杂度为O(n)。由此可见，KNN算法的优点是有很多的。
那么KNN算法的缺点是什么呢？这种算法的缺点具体体现在六点，第一就是样本不平衡时，预测偏差比较大。第二就是KNN每一次分类都会重新进行一次全局运算。第三就是k值大小的选择没有理论选择最优，往往是结合K-折交叉验证得到最优k值选择。第四就是样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）效果差。第五就是需要大量内存。第六就是对于样本容量大的数据集计算量比较大。
正是由于这些优点和缺点，KNN算法应用领域比较广泛，在文本分类、模式识别、聚类分析，多分类领域中处处有KNN算法的身影。
在这篇文章中我们给大家介绍了很多关于KNN算法的相关知识，通过对这些知识的理解相信大家已经知道该算法的特点了吧，希望这篇文章能够帮助大家更好的理解KNN算法。