距离度量学习算法的精确性研究

许小媛，黄 黎，2

（1.江苏开放大学信息工程学院，江苏南京 210017；2.南京航空航天大学计算机科学与技术学院，江苏南京 210016）

0 引 言

距离度量学习或者称为相似度学习，是指在给定的训练样本集上，通过学习得到一个能够有效反映数据样本间的距离或者相似度的度量矩阵，目的是使在新的样本空间中，相同类别的样本相似度更大，也就是分布更紧密；不同类别的样本相似度更小，也就是分布更松散。距离度量学习算法[1-5]在计算机视觉及模式识别等领域应用非常广泛，对距离度量学习算法的研究已成为近年比较活跃的研究热点之一，因此，该项研究具有重要的意义和价值。

距离度量学习算法依据不同分类标准，有多种分类方法。例如，依据学习方式的不同，可以将度量学习算法分为有监督的距离度量学习算法[6-7]和无监督的距离度量学习算法[7]两类。有监督的距离度量学习算法的主要思想是对于训练集的样本信息建立优化函数，获得能够合理反映样本空间特性的度量矩阵，然后利用算法进行训练。文献[7]提出最大化互信息熵的思想，通过此方法进行距离度量学习。无监督的距离度量学习算法倾向于通过寻找集群来分散数据，对数据进行标记。其基本思想是将原始数据集通过降维映射到一个低维子空间中，从而得到关于原始数据集更紧密的低维表示。文献[8]提出基于AML 算法，结合核学习技术，提出非线性自适应距离度量学习算法。文献[9]提出自适应距离度量学习（Adaptive Metric Learning，AML）算法，该算法将距离度量学习和聚类结合，将原始数据集进行降维，形成新的更紧密的低维子空间后，再进行距离度量学习。

本文研究主要是基于无监督的距离度量学习算法。选择单位矩阵、邢氏算法、信息论度量学习算法和编码相似度算法，在选取的不同数据库上进行比较，对提高距离度量学习算法的精确性提供研究基础，对于实际应用中度量学习算法的选择提供依据。

1 算 法

基于约束条件（未标记的数据和相似集）选择四种算法对距离矩阵进行比较。这四种算法分别是：单位矩阵或欧几里得距离；邢氏算法[10（]一种迭代算法）；信息论的度量学习[11（]一种迭代算法）；编码相似度算法[12]。

四种算法可以用不同的方式确定相似性问题。

1.1 邢氏算法

邢氏算法是可以考虑用来解决问题的最简单的算法。 一般的思路是最小化相似点与相异点之间的距离。为此考虑一个距离矩阵，并进行优化：

该算法的主要缺点是集合的收敛性不确定。有时根据数据集或初始条件可能无法计算出一个很好的结果，并被卡在一个循环中，每个迭代步骤产生的新矩阵都远离了前一个矩阵。在某些数据集上，还可能出现A=0，这是不应该的。

在本文中，该算法仅运用于学习全矩阵[13]。

1.2 信息论的度量学习算法

Kullback-Leibler 距离[14-15（]或称作KL 分歧）是指两个分布之间的统计距离，公式是：

式中：ξ0是描述相似性与差异性之间临界值的集合；ξi,j是S或D中(i,j)的临界值；γ控制着对任意矩阵A0进行学习的矩阵与对预计算的阈值进行调整之间的平衡问题，这个问题可以有很多参数，用来获得更好的计算结果，但是在算法开始时，必须设定好A0，ξ和γ的初始值，因为它们很难进行预先估算。

1.3 编码相似度

编码相似度指的是一个数据包含了另外一个数据的信息量的多少。相似度codsim(x,x′)表示x传递了x′的信息量，这是一个基于分布的方法。信息量的大小通过两个分布之间编码长度的差异进行评估：一个分布认为x和x′之间并不存在真正的联系，另一个分布则认为有。需要注意，这个算法只使用相似的数据对。编码长度为最终计算公式为：

该算法通过降低维度避免了过拟合[9]。虽然它不需要进行迭代，但是计算过程很复杂（逆矩阵），而且在求解逆矩阵的过程中容易出现一些问题。为了避免这种情况，将零特征值尽量减少。在本文的实验中，没有计算出任何维度的减少。

2 实验方法

在每个数据集中，给定每个数据的分类，通过相似或相异的数据对，对每个可能的数据对进行标记，作为算法的输入。在此基础上，进行双重交叉验证，另外还需要一个阈值来评估其相似度。本文使用的算法并没有给出这个阈值，因此在评估过程中要筛选出一个阈值。在给定的距离矩阵和几个阈值中，计算几个混合矩阵。选择阈值，以便描述有用值的整个范围：从对相异数据的所有映射中，再到相似数据的所有映射中进行选择，然后计算接受者操作特征曲线（ROC），并且模型的精度由ROC 曲线下半部分的面积（AUC）给出，ROC 曲线如图1 所示。

图1 ROC 曲线Figure 1 ROC Curve

对于信息论度量学习算法（ITML），需要初始化ξ0。按照经验对它进行初始值设定，尽管这种选择是完全随机的：所有数据对的距离分布中，5%为相似性，95%表现为相异。然后研究不连续的数据对整体结果的影响。这些集合表现出了精确的相似度，但人造的数据不具备这个属性。因此，选择通过“翻转”一些数据对的相似度来添加一些矛盾数据。该方法不是添加新对，而是修改现有的对，因此数据集不具有矛盾对，但包含相似性评估错误。

由于可能产生不一致性，在一个真正的数据集中选择将它们从测试集中排除。人造的编码不能选择，这只会降低结果准确性，并且对算法的比较也没有帮助。

3 实验结果

3.1 电离层

电离层结果如表1 所示。由表1 可知，运用欧几里得定理得到的结果不理想；邢氏算法结果较好，但是当内部关联数据出现时，健壮性较差；编码相似度算法给出了基本一致的稳定性。

表1 电离层结果Table 1 Ionosphere results

3.2 虹膜（IRIS）

虹膜层结果如表2 所示。由表2 可知，小规模的IRIS 数据集的尺寸解释了相似性准确度上的急速下降。根据欧几里得定理得出的结果，使用学习过的距离函数效果不好。

表2 虹膜层结果Table 2 Iris results

3.3 酒 类

酒类结果如表3 所示。由表3 可知，编码相似度算法在正确的数据集上效果很好。但意外的是，邢氏算法针对错误的数据却得出最好的结果。而且这些精确度与欧几里得距离得出的结果非常接近。

表3 酒类结果Table 3 Wine results

3.4 WDBC（美国威斯康星乳腺癌数据库）

WDBC 结果如表4 所示，欧几里得和距离学习都没有得到好的结果，因此这个数据集看上去似乎是无效的，在这种情况下，选择欧几里得距离来评价相似度是最安全的方法。

表4 WDBC 结果Table 4 WDBC Results

3.5 大豆类（小样本Soybean-small）

大豆类（小样本）结果如表5 所示。由表5 可知，欧几里得距离可以得出很好的结果，使用其他算法的表现都很差。

表5 大豆类（小样本）结果Table 5 Soybean（small sample）results

3.6 平衡量表

平衡量表结果如表6 所示。由表6 数据可得出，邢氏算法出现很多错误数据，因此至少在某一时间段或某些迭代的情况下是不能收敛的，就如同信息论度量学习算法一样。这可能是由数据集尺寸导致的。

表6 平衡量表结果Table 6 Balance-scale results

4 结 论

本文研究的主要结论是基于数据驱动算法的准确性中，算法并不处于主导地位的。此外，明确定义的集合的结果并不能代表随机产生的数据集合的结果。当没有明确分类时，相似性的区别和分类问题值得研究。

由于真实数据集中可能存在错误，可以选择一种具有良好稳固性的算法。实验证明，数据的不同特性影响到算法的结果。虽然加入非相关数据的方法是模拟部分坏数据集的一种快速而有效的方法，但无法评估相似性。相似性不能理解为二元评估（相似/不相似），也不能被视为二次函数。相似性评价的误差可以遵循一定的模式，而不是完全随机地分布。这些“选择”也可以是个人的。如果测试集由某一用户创建，那么距离矩阵就反映了对相似度的描述。数据可以是近距离的，也可以是连续的。此外，本文研究仅限于Mahanalobis 距离[3-10]。

某些算法的结果不理想，但并不应该受到限制。比如，如果编码相似性算法很好，就可以用来学习一个很好的距离函数，并且可以通过在线捕获的数据（如ITML的在线版本）来调整矩阵。关于人造数据集和非二元距离的领域，在未来的实际应用中还有很多值得研究的地方。