最近邻分类中的距离度量学习算法实现与验证(2)
的类别中。待聚类完成之后重新计算每个聚类中心，重复聚类，直到新聚类中心与原
聚类中心相等或者距离小于指定的阀值。
最近邻分类算法[2]
是最古老和最简单的模式分类[3]
方法之一，但却拥有很好的分
类效果，在机器学习领域[4,5]
有着重要的地位。NCA[6]和LMNN[7]
算法都是以最近邻分类
为基础的，它的主要思想是：在训练集里一个输入样本的最终类别归属取决于k个最
近邻已分类样本的数量，样本数最多的类别即输入样本的类别。因此，其性能很大程
度上取决于样本间距离的度量标准。
1．1关于距离度量
对于很多的分类和聚类算法，已经有很成熟的算法模型，所以提升算法性能的关
键就在于输入样本间距离的度量上，一种简单而有效的距离度量学习算法能够大幅度
的提高分类和聚类的速度和正确率。样本通常以向量的形式输入，大多数情况下会使
用简单的欧式距离度量样本间的距离。然而，对于具有大量样本的训练集总结出的统
计规律，欧式距离度量并未加以利用。这将严重影响样本间距离计算的速度和准确性。
针对欧式距离度量的这一缺陷，研究人员提出了许多更为高效的距离度量学习算法，
它们基本上都利用或是依赖于训练集中样本分布的统计规律。
对于不同的应用领域，数据集的数据分布特点存在的差异，所以很难有一种度量
标准适合所有的分类和聚类问题。每一种距离度量学习算法的思想都是在一定的背景
之下产生的，所以很多距离度量标准都是在各自的一些特定的领域内对分类或者聚类
的效果改善非常明显。总而言之，距离度量学习算法的不断革新和进步，对模式识别
和人工智能领域的发展有着巨大的推动作用。
1．2弱监督距离度量学习的特性
很多聚类算法的性能对给定的距离度量标准的依赖性很强。它们要求距离度量标
准能够合理的反映输入数据间的关系，这个问题在无监督聚类算法上表现的尤为突出。
甚至会使得聚类算法无法得到一个“正确的”结果，例如三种算法作用于一文本集，
分别根据“作者”，“主题”和“写作风格”进行聚类，这很难判断哪一种聚类结果是
“正确的”。并且，对于根据“作者”进行聚类的算法，如果试图用“主题”代替，
就会缺少一种系统的机制将这个信息以参数化的形式传递给算法，取而代之的只能是
手动修改距离度量标准。
弱监督距离度量学习算法在以上问题上取得了重要的突破。用户向算法提供一个
“相似”集合（如果需要，也可以是“不相似”集合）：输入空间内属于相同类别的
“点对”，亦即S={（xi，xj）|xi，xj属于同一个类别}。弱监督距离度量学习算法根
据这些相似信息，学习一种距离度量标准有效的反映相似样本间的“小距离”信息。
作为距离度量学习算法的重要组成部分，无监督学习算法（如MDS[8],LLE[9]）只得
到训练样本集在某些空间的一个嵌入。弱监督学习算法区别于此的一个很大的特点是
它得出的度量标准是针对于这个输入空间的，而不是仅仅关注训练样本集，因此，弱
监督学习算法可以很容易的推广到多文的样本空间。LLE和MDS算法有时甚至无法得
到“正确的”分类结果，例如，如果MDS算法无法获得数据的分布结构，算法就无法
继续运行。而弱监督聚类算法同样可以用于数据的预处理，处理的结果有助于无监督