最近邻分类中的距离度量学习算法实现与验证(3)
聚类算法获得更好的结果。
1．3kNN的缺陷及改进
kNN算法的一个很大的优势在于它的判定边缘是非线性的，并且只有一个整型参
数（通过交叉验证很容易得到），分类的质量也随着训练集中样本数的增加而自动地提高。
然而，kNN却有两个严重的缺陷：一个是计算量过于庞大，由于为每一个样本分
类时，都需要搜索整个训练集，并且计算和存储与训练集中每个样本的距离，导致过
多的计算和存储开销。另一个是模型问题：如何定义kNN算法所使用距离度量标准。
理想情况下，kNN分类中的距离度量应该适用于任何问题，但显然，欧式距离无法做
到这一点。事实上，正如许多研究人员的研究成果[6,10,11]
所示,使用通过训练集学习得到的距离度量方法可以显著地提高kNN算法的性能。甚至即使是一个简单输入空间的
线性变换都可以改善kNN算法。
针对以上问题，NCA算法利用了概率性的近邻样本选择规则，通过在训练集上最
优化留一分类错误率，学习了一种二次的距离度量标准，在保存大部分信息的前提下
降低输入样本的文数，有效的减少了存储空间的开销，在低文的输入空间，也可以通
过使用特殊的数据结构（例如KD-trees，ball-trees）降低搜索的时间开销。当然，
低文的输入数据也大大减小了样本间的距离计算量。
LMNN算法是以马氏距离度量为基础的，并通过优化这种度量标准使得近邻样本尽
量属于同一个类别，而不同类别样本间的距离尽可能的大。以往的研究中，距离度量
学习算法的主要目标是尽量减少同类别样本间的距离，这样的目标是很难实现的，它
并不会促使kNN算法的性能产生改变，因为kNN的准确性并不要求所有同类别样本都
是紧密集群的。LMNN算法与支持向量机[12]
有相似之处，但不同的是LMNN算法不需要
更改和扩展就能完成多类（相对于二类）分类问题。在NCA和基于能量模型的算法研
究上的突破很大程度启发了LMNN算法，虽然基于同一目标，但在方法上却有着很大
的不同，LMNN算法利用半定规划解决优化问题，凸优化的全局最小值可以有效的计算
得到。2弱监督距离度量学习算法
2．1学习距离度量标准假设有一些点集
，并且给定特定的点对之间是“相似的”：
S：（）∊S如果和是“相似的”（1）
弱监督学习算法试图学习一种距离度量标准d(x,y),使得“相似”点更加靠近彼此。
我们可以考虑从以下形式学习一种距离度量标准：.（2）
为了保证满足非负性和三角不等式，要求A是半正定的，A⪰0。令A=I，得到的就是
欧式距离度量标准；如果将A对角化，那么A对角线上的数字就是输入样本每个分量
对应的“权重”；更多情况下，A将作为Rn空间上的马氏距离度量的参数，这也就等同于利用A1/2
x代替x，然后利用欧式距离进行计算。
获得A的一个简单的方法是使得点对（xi，xj）∊S距离平方和尽可能小：A⪰0.（5）
对于（4）式中大于号右边常数1的选择并不是很重要，若用其他常数c代替1，所产
生的结果将会是c2
A。这个问题在参数矩阵A中的目标函数是线性的，并且（4）和（5）
很容易被证明是两个凸约束，因此，这是一个凸优化问题，可以得到有效的解决。同
时也必须注意到，尽管式（4）是一个简单的线性约束，但它有可能导致矩阵A1/2成为
行矩阵（这样就会将所有的样本投影到一条直线上），所以我们试图用其他的约束代替式（4）。