如何表示2点之间的距离是模式识别中的基础问题。一个好的距离度量能够根据数据的结构与分布适用于不同的应用。欧氏距离是众多数据挖掘应用中使用最多的距离度量，但是欧氏距离仅适用于特征空间中超球结构的数据集，对于超立方体结构、超椭球结构的数据集效果不太理想^[1]。除了欧氏距离，余弦距离是另一个应用广泛的距离度量。尽管余弦距离在文本检索中有优秀的表现，但是其预先假设了数据集每一维度都是等权重的^[2]，这一特性显然限制了余弦距离的应用范围。因此，欧式距离和余弦距离在实际应用中都不是最理想的选择。

从训练样本中学习出合适的距离度量是近年来的研究热点，它对于提高聚类和分类效果有着重要的影响。一般的距离学习方法都是首先假定一个距离函数模型并进行求解，其中大部分的距离函数假定在马氏距离定义的框架之下，即对于2点 x、y ，使用距离公式 d(x,y)=(x-y)^TA(x-y) ，其中 A 为所要学习的距离矩阵。比如文献[3]中通过使相似样本之间距离减小学习了一个全局距离度量;区分成分分析(DCA)^[4]通过最小化相似样本之间距离的同时最大化不相似样本之间的距离来学习距离矩阵;近邻成分分析(NCA)^[5]通过最优化最近邻分类器的精度去学习马氏距离度量;最大边界近邻分类方法(LMNN)^[6]在NCA的框架下拓展了最大边界的目标，但是学习的目标仍然是得到一个马氏距离。当马氏距离中的矩阵 A 取单位矩阵 I 时，则马氏距离表示欧氏距离。因此，本质上来说，以马氏距离为目标学习得到的新距离是欧式距离的线性变换，其无法准确地度量所有样本之间的距离。

有别于传统的距离学习方法，本文提出的距离学习方法并没有将学习目标单纯设定为马氏距离，而是学习由若干候选距离线性组合而成的新距离。基于最大间隔理论建立目标函数，利用数据的边信息通过对目标函数进行优化从而得到组合距离中的权重进而得到新的距离度量。对于候选距离的选择也不仅仅局限于马氏距离，本文选择了其他形式的距离度量进行组合，以扩大距离度量的适用范围。

为了更好地表示数据点之间的距离，在距离函数中引入权重来强化有积极作用的部分，削减冗余的部分，已经成为一种常用的方法。在之前的方法中，研究者往往使用特征加权距离的方法^[7]来改进聚类算法，特征加权距离的计算表达式为

式中： x=[x₁ x₂ … x_d]^T,y=[y₁y₂…y_d]^T 为特征空间 R^d 中的任意2点，ω_h 为特征权重且满足。

受特征加权距离的启发，引入权值将距离函数改写为若干候选距离的线性组合，将特征加权改为距离加权，从而强化对某一数据集有更好度量效果的距离分量。

本文通过以下线性组合来表示数据集中的距离度量：

式中： D(x_a,x_b) 表示数据点 x_a 到数据点 x_b 之间的距离，它由 p 个距离分量组成，d_i(x_a,x_b) 是其第 i 个距离分量， ω_i 是第 i 个距离分量所对应的权值。 ω_i 需要满足各个分量权值均为正且和为1的条件。

在距离分量的选择上，除了经典的欧式距离之外，本文选择了若干含有数据维度方差的距离分量(如：，其中 β 为常数，I 为单位矩阵，σ 为数据点之间的标准差)以保留数据各特征分量上的特征。但是这些距离均为马氏距离定义框架下的距离度量，对其进行线性组合后，得到的距离函数仍为马氏距离形式。因此，根据Wu等提出的新距离^[8]，本文给出了若干形如的距离分量进行组合，其中 β 为常数，这些距离均为非线性的距离度量，通过组合可以形成非线性的距离函数以克服马氏距离的缺点。

本文所提出的距离学习算法将利用数据集的边信息进行学习，而边信息通常以成对约束的形式表现。因此，本文以成对约束的集合作为训练集并表示为，其中 n 为成对约束的对数。 D 中每一对成对约束 (x_a^k,x_b^k,y_k) 都是一个包含三个元素的元组，其中 x_a^k 和 x_b^k 是被表示为 d 维向量的样本点，y_k 是表示样本点 x_a^k 和 x_b^k 之间关系的类标。当 x_a^k 和 x_b^k 为同一类的样本点时， y_k 为正(如： y_k=+1 )；反之，y_k 为负(如： y_k=-1 )。使用 X=(x₁,x₂,…,x_N) 来表示 D 中出现的所有的训练样本点，其中 N 表示样本点的个数。

统计学习中常用的经验风险最小化并不能保证良好的泛化性能，因此间隔理论^[9]就伴随着过拟合的问题研究被提出，并逐渐成为机器学习领域中的一个重要评价标准。本文依据最大间隔理论并受L2-SVM方法^[10]和文献[2]的启发，构建目标函数如式(2)：

式中： d_i(x_a^k,x_b^k) 表示第 k 对成对约束的第 i 个距离分量，为了便于表示，本文在后续的介绍中将使用符号 d_i.k 来代替 d_i(x_a^k,x_b^k) 。此外，y_k 为该约束对的类标，C 为惩罚因子，C 值大时对训练错误的惩罚增大，θ 为已知参数，β 为阈值，最大间隔为。在优化的过程中最大化 ρ ，最小化 ‖ω‖² ，并使训练误差 ξ_k 最小化，其中 ξ_k≥0 。

本文的目标是通过优化该目标函数求得距离分量的权值 ω_i，下面将具体介绍求解 ω_i的方法。 为了求解上述优化问题，将它作为原始最优化问题，应用拉格朗日对偶性，通过求解对偶问题得到原始问题的最优解。接下来将介绍具体求解过程。

首先，构建拉格朗日函数如式(3)：

式中： α=[α₁ α₂ … α_n]^T 、 λ 均为拉格朗日乘子。

如果此时考虑式(2)中 ω_i≥0 的约束条件，并将该条件加入拉格朗日函数，则得到

将该拉格朗日函数分别对 ω_i、β、ρ、ξ_k、λ 求偏导，并令其等于0得到

显然由方程组(4)无法求得 ω_i ，因此本文先暂时不考虑 ω_i≥0 的约束条件，使用式(3)进行后续的求解。

根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题：

所以，需要先求 L(ω,β,ξ,α,λ) 对于 ω、λ 的极小值。

将拉格朗日函数式(5)分别对 ω_i、β、ρ、ξ_k、λ 求偏导，并令其等于0得到

进而得到

将式(6)代入式(10)得到

进而，将式(11)代入式(6)得到

将式(7)~(10)、(12)代入拉格朗日函数(3)中，即得

即

求对 α 的极大，即得对偶问题：

将式(13)的目标函数由求极大转换为求极小，就得到下面与之等价的对偶最优化问题：

如此，可以通过二次规划的求解方法得到最优解 ，进而代入式(12)得到 ω_i 的最优解：

可以明显地观察到，即使成功的优化得到最优解，也不能保证 ω_i 完全满足式(2)中 ω_i≥0 的约束条件，受PFC算法^[11]的启发，在之前的基础上对 ω_i 做如下修改：

式中：

p⁺ 表示所有使得 ω_i 取正值的 i 的集合，相对应的 p^- 表示无法使 ω_i 取正值的 i 的集合，2个集合 p⁺ 和 p^- 的大小分别使用 |p⁺| 和 |p^-| 来表示。

至此完成求解距离分量权值 ω_i 的目标，求解集合 p⁺ 和 p^- 的算法描述将在下一小节给出。

最大几何间隔中的 ρ 亦可在求解权值 ω_i 的过程中求得。与原始SVM类似，目标函数(3)的分离超平面为，即可得最大函数间隔 。在求得最优解后由式(9)可得 β 的最优解 进而可得最大函数间隔 。

本节将给出求解距离分量权值 ω_i 的具体算法步骤。

为了便于表示，将式(14)简化：

式中：

由式(16)观察可得，若想满足 ω_i 为正值，则 V_i 需要足够大，且当 V_i 越大，ω_i 为正值的几率就越大。因此，求解集合 p⁺ 和 p^- 的算法总结如下。

算法 1 求解集合 p⁺ 和 p^-。

1)初始化：

2) ，其中，；

3)通过式(14)计算 ω_g 并判断其是否大于0。其中， 。如果 ω_g>0 则回到2)，否则设置 p⁺=p_h-1⁺,p^-=p_h-1^- 并终止。

下面将介绍学习距离函数中权值 ω_i 的算法，其中 ω_i 将采用如下方法初始化：在式(1)中 ω_i 的约束条件下，令 ω₁⁽⁰⁾=ω₂⁽⁰⁾=…=ω_p ⁽⁰⁾，因此有 ω⁽⁰⁾_i=1/p。

算法 2 学习距离函数。

输入：

1)数据矩阵： X∈R^d×N ；

2)成对约束： x_a^k,x_a^k,y_k 其中，y_k={+1,-1}；

3)参数： C、θ ；

输出：距离权值： ω ；

方法：

1)初始化： ω=ω⁽⁰⁾ ；

2)计算距离矩阵： D(i,k) ；

3)计算二次规划参数 H 和 f ：

4)利用二次规划优化算法求解得到最优解： α^*=[α^*₁ α^*₂ … α^*_n]^T ；

5)计算集合 p⁺ 和 p^- ：算法1；

6)利用式(15)计算 ω 。

为了与传统FCM算法之间有可比性，本文将简单的以学习得到的距离函数替换传统FCM算法中的欧式距离。根据传统FCM算法的实现方法，本文将通过以下步骤实现聚类：

1)初始化隶属度矩阵 U ，使得 。

2)计算聚类中心：

3)计算价值函数：

当其相对于上次价值函数值的改变量小于某个阈值时，算法停止。

4)更新隶属度矩阵：

其中对于样本点 x_j ，它与聚类中心 c_i 之间的距离使用如下公式计算：

将上述聚类算法记为基于组合距离(hybrid distance)的FCM聚类算法(HDFCM)。

本节将上述HDFCM算法与已有的经典距离学习算法进行对比与分析。

本文使用了8个来自UCI机器学习数据库的真实数据集。其中4个为二类数据集，其余4个为多类数据集。各个数据集的信息如表 1所示。

在数据集的选择上基于以下考虑：首先，这些数据集的特征数和类别数都各不相同。另外，这些数据集是机器学习研究中被广泛使用的基准数据集，因而具有代表性。最后，由于数据集均为真实数据集，因此可以检验算法在真实应用中是否可行。

文中所有实验均在MATLAB平台下进行，所有训练数据集和测试数据集均先归一化至 [0,1]内。带有边信息的训练集将通过如下方法产生：首先，随机选取数据集的10%组成一个子集。然后，根据子集中样本点带有的类标是否相同来生成约束对 x_a^k,x_b^k,y_k 集合。其中，类标相同的成对约束为正约束对，反之为负约束对。将取个数相同的正负约束对组成训练集。

在组合距离分量的选择上，本文依据第2节的理论，在实验中选取如下10个距离度量进行组合：

在使用组合距离进行聚类的算法中，本文将依据数据集的类别数给定聚类数目，初始隶属度矩阵随机生成。为了保证可比性，实验中所有的对比算法将使用相同的初始隶属度矩阵，训练集和其他参数( m=2,ε=10^-5,T=100,C=10^-5 )。实验将重复每个聚类过程20次，实验结果取其均值。

为了评估聚类效果，采用一种类似F₁-measure的成对约束评价方法，评价参数包括：pairwise Precision，pairwise Recall和pairwise F₁，定义为^[2]

式中： #TruePositive 为将正约束对预测为正约束对的个数，#FalsePositive 为将负约束对预测为正约束对的个数，#FalseNegative 为将正约束对预测为负约束对的个数。由于该评价方法的对象为约束对，因此不仅可以应用于二分类的评价，也可应用于多类分类的评价。

本文使用了若干经典距离学习算法进行对比，包括：使用欧式距离的传统FCM算法(FCM)，使用欧氏距离但含有约束条件的K-均值聚类算法(C-Euc)^[12]，基于凸优化的全局距离学习算法(PGDM)^[3]。

与本文提出的算法类似，C-Euc算法也是一种利用边信息进行距离学习的半监督聚类算法，它在传统K-均值算法的基础上加上成对约束，在这些约束的监督下进行聚类。C-Euc算法在聚类的过程中要求每一次划分都满足已知的约束条件，每个样本在没有违反约束条件的情况下，被划分给最近的类，最终得到的聚类结果将满足所有的约束对信息^[13]。

PGDM算法由Xing等提出，是一种基于凸优化的全局距离度量学习算法。它将正约束对构成的集合记为 S ，负约束对构成的集合记为 D 。通过以下凸优化问题对距离矩阵 A 进行求解：

式中：表示2个样本点 x_i 和 x_j 之间的距离。根据预期得到的矩阵 A 的不同将有不同的解法。如果期望得到对角形式的距离矩阵，可以通过牛顿法进行求解，本文将此算法记为PGDM-Ad。如果期待得到全矩阵形式的距离矩阵，则可以通过梯度下降和逐次映射的方法进行求解，本文将此算法记为PGDM-Af。为了保证对比性，在实验中本文将学习得到的距离矩阵和本文算法一样应用于FCM聚类算法中以评价。

对于各个数据集，本文所提出算法与其他算法在8个数据集上的实验结果对比如图 1所示，其中每一个子图的纵坐标表示了各个算法在相同参数下在该数据集上的聚类效果的评价指标均值，横坐标上的柱形分为3组，每一组分别表示 F₁ 、precsion和recall。每个颜色代表一个算法，从左至右分别为FCM算法^[14]，C-Euc算法^[12]，PGDM-Ad算法^[3]，PGDM-Af算法^[3]和HDFCM算法，数据集名称标注在图标题上。表 2展示了本文算法相对于传统FCM算法聚类效果的提升率，提升率使用如下公式计算得到：

图 1 算法对比图 Fig. 1 Clustering performance comparison

图选项

从图 1可以看出，本文提出的算法在大部分数据集上获得了最好的表现。相对于其他距离学习算法而言，本文算法在sonar数据集和cmc数据集中虽未获得最好的表现，但是结合表 2可以发现本文算法的聚类效果相对于传统FCM算法仍有一定的提升。由于本文使用的距离分量有限，因此对于不同的数据集不一定能拟合出最适合于该数据集的距离度量。此外，从表 2可以观察到，本文算法在breast数据集和wine数据集上有相当卓越的表现。

结合图 1和表 1可以得出，本文算法不仅适用于2类数据集，对于多类数据集也有较好的聚类效果。比如，2类数据集breast，3类数据集wine，7类数据集segment在聚类效果上均取得了30%以上的提升。

由于传统FCM算法使用的是欧式距离，且其为无监督聚类算法，因此在应用的过程中不一定适合所有类型的数据集。而C-Euc算法虽然引入了数据集的边信息，但是其使用的距离度量仍然为欧氏距离，因此在使用的时候也具有局限性。PGDM在引入了边信息的基础上学习出了新的距离度量，但是该距离函数仍是在马氏距离定义框架下的距离度量，属于线性的距离学习方法。本文提出的算法不仅引入了数据集的边信息，而且组合了预设的多种形式的距离度量，学习得到一个非线性的距离度量，使其对于数据集有较好的适应性。上述实验可以证明本文算法的有效性。

本文提出了一种基于线性组合的混合距离学习算法。该算法构建了一个由若干候选距离线性组合而成的距离目标函数，利用数据集的边信息学习得到各候选距离对应权值，从而得到新的距离函数。本文将学习得到的距离函数应用于模糊C均值算法中以构成一个半监督聚类算法。通过使用UCI真实数据集将该半监督聚类算法的聚类效果与其他距离学习算法进行对比，证明了本文算法的有效性。