最近邻分类

1. 模型背景

一般的分类器，比如决策树和支撑向量机，只要有训练数据可用，它们就开始学习从输入属性到类标号的映射模型，这类学习策略被称为积极学习方法（eager learner）。我们可以认为学习后的模型已经就绪，并急于对先前未见过的元组进行分类。与之相对的是消极学习算法（lazy learner），它的策略是推迟对训练数据的建模，在需要分类测试样例时再进行。学习程序直到对给定的检验元组分类之前的一刻才构造模型。也就是说，当给定一个训练元组时，消极学习算法简单的存储它（或只是稍加处理），并且一直等待，直到给定一个检验元组。仅当看到检验元组时，它才进行泛化。

最近邻方法是20世纪50年代早期首次引进的。当给定大量数据集时，该方法是计算密集的，直到20世纪60年代计算能力大大增强之后才流行起来。此后它广泛用于模式识别领域。

在做分类或数值预测时，惰性学习法的计算开销可能相当大。它们需要有效的存储技术，并且非常适合在并行硬件上实现。它们不提供多少解释或对数据结构的洞察。然而，消极学习算法天生地支持增量学习。它们也能对具有超多边形形状的复杂决策空间建模，这些可能不太容易其他学习算法描述（如被决策树建模的超矩形形状）。本节考察消极学习中的k-最近邻分类。

2. 模型原理

最近邻分类法是基于类比学习，即通过将给定的检验元组与和它相似的训练元组进行比较来学习。训练元组用n个属性描述。每个元组代表n维空间的一个点。这样，所有的训练元组都存放在n维模式空间中。当给定一个未知元组时，最近邻分类法（nearest-neighbor classifier）搜索空间。

其中，目前应用较广泛的为k-最近邻分类法（k-nearest-neighbor classifier），搜索过程中，找出最接近未知元组的k个训练元组。找出最接近未知元组的k个训练元组。这k个训练元组是未知减组的k个“最近邻”。

“邻近性”用距离度量，如欧几里得距离。两个点或元组和的欧几里得距离是：

换言之，对于每个数值属性，我们取元组和该属性对应值的差，取差的平方和，并取其平方根。通常，在使用上式之前，我们把每个属性的值规范化。这有助于防止有较大初始值域的属性（如收人）比具有较小初始值域的属性(如二元属性)的权重过大。例如，可以通过计算下式，使用最小-最大规范化把数值属性A的值v变换到[0，1]区间中的v^’:

其中，min_A和max_A分别是属性A的最小值和最大值。

对于k-最近邻分类，未知元组被指派到它的k个最近邻中的多数类。当k=1时，未知元组被指派到模式空间中最接近它的训练元组所在的类。最近邻分类也可以用于数值预测，即返回给定未知元组的实数值预测。在这种情况下，分类器返回未知元组的k个最近邻的实数值标号的平均值。

3. 实施分析步骤

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

4. 输入输出参数设置

• K值

对于k-最近邻分类，未知元组被指派到它的k个最近邻中的多数类。K值的选取非常重要：

• 若K取值过小，一旦有噪声得成分存在们将会对预测产生比较大影响，例如取K值为1时，一旦最近的一个点是噪声，那么就会出现偏差，K值的减小就意味着整体模型变得复杂，容易发生过拟合；
• 若K取值过大，就相当于用较大邻域中的训练实例进行预测，学习的近似误差会增大。这时与输入目标点较远实例也会对预测起作用，使预测发生错误。K值的增大就意味着整体的模型变得简单；
• 若K==N，那么就是取全部的实例，即为取实例中某分类下最多的点；
• K的取值尽量要取奇数，以保证在计算结果最后会产生一个较多的类别，如果取偶数可能会产生相等的情况，不利于预测。

常用的方法是从k=1开始，使用检验集估计分类器的误差率。重复该过程，每次K增值1，允许增加一个近邻。选取产生最小误差率的K。一般k的取值不超过20，上限是n的开方，随着数据集的增大，K的值也要增大。

• 属性

对于标称属性，一种简单的方法是比较元组和中对应属性的值。如果二者相同（例如，元组和均为蓝色），则二者之间的差为0。如果二者不同（例如，元组是蓝色，而元组是红色），则二者之间的差为1。其他方法可能采用更复杂的方案（例如，对蓝色和白色赋予比蓝色和黑色更大的差值）。

• 缺失值

通常，如果元组和/或元组在给定属性A上的值缺失，则我们假定取最大的可能差。假设每个属性都已经映射到[0，1]区间。对于标称属性，如果A的一个或两个对应值缺失，则我们取差值为1。如果A是数值属性，并且在元组和上都缺失，则差值也取1。如果只有一个值缺失，而另一个存在并且已经规范化（记作），则取差为和中的最大者。

• 近邻数值

通过实验来确定，从k=1开始，使用检验集估计分类器的错误率。重复该过程，每次k增值1，允许增加一个近邻。可以选取产生最小错误率的k。一般而言，训练元组越多，k的值越大（使得分类和数值预测决策可以基于存储元组的较大比例）。随着训练元组数趋向于无穷并且k=1，错误率不会超过贝叶斯错误率的2倍（后者是理论最小错误率）。如果k也趋向于无穷，则错误率趋向于贝叶斯错误率。

• 距离度量

最近邻分类法使用基于距离的比较，本质上赋予每个属性相等的权重。因此，当数据存在噪声或不相关属性时，它们的准确率可能受到影响。然而这种方法已经被改进，结合属性加权和噪声数据元组的剪枝。距离度量的选择距离可能是至关重要的，也可以使用曼哈顿距离或其他距离度量。

最近邻分类往往需要对训练集进行预处理才能使用，并且每一次分类需耗费较大时长。针对算法的不足，算法的改进方向主要分成了分类效率和分类效果两方面。分类效率指事先对样本属性进行约简，删除对分类结果影响较小的属性，快速的得出待分类样本的类别。分类效果指采用权值的方法（和该样本距离小的邻居权值大）来改进以促进分类效果。

5. 运行效果评价

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

该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。 该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。

该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点；且可理解性差，无法给出像决策树那样的规则。

针对以上算法的不足，算法的改进方向主要分成了分类效率和分类效果两方面：

• 分类效率

事先对样本属性进行约简，删除对分类结果影响较小的属性，快速的得出待分类样本的类别。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。

• 分类效果

采用权值的方法（和该样本距离小的邻居权值大）来改进，Han等人于2002年尝试利用贪心法，针对文件分类实做可调整权重的k最近邻居法WAkNN (weighted adjusted k nearest neighbor)，以促进分类效果；而Li等人于2004年提出由于不同分类的文件本身有数量上有差异，因此也应该依照训练集合中各种分类的文件数量，选取不同数目的最近邻居，来参与分类。

6. 模型应用

图1 例题图

如上图所示，有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。这也就是我们的目的，来了一个新的数据点，要得到它的类别是什么。那么下面我们根据k近邻的思想来给绿色圆点进行分类。

• 如果K=3，绿色圆点的最邻近的3个点是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。
• 如果K=5，绿色圆点的最邻近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。

以上即为最近邻分类的最基本用法。