·848. 智能系统学报 第10卷 数(m=2,e=10-5,T=100,C=10-5)。实验将重 算法一样应用于FCM聚类算法中以评价。 复每个聚类过程20次，实验结果取其均值。 3.3实验结果与分析 为了评估聚类效果，采用一种类似F,-measure 对于各个数据集，本文所提出算法与其他算法 的成对约束评价方法，评价参数包括：pairwise Preci- 在8个数据集上的实验结果对比如图1所示，其中 sion,pairwise Recall和pairwise F,定义为[ 每一个子图的纵坐标表示了各个算法在相同参数下 #TruePositive 在该数据集上的聚类效果的评价指标均值，横坐标 Precision #TruePositive +#FalsePositive 上的柱形分为3组，每一组分别表示F,、precsion和 #TruePositive Recall = recall。每个颜色代表一个算法，从左至右分别为 #TruePositive #FalseNegative FCM算法[a,C-Euc算法[)，PGDM-Ad算法[)， 2 X Precision×Recall F1= PGDM-Af算法[]和HDFCM算法，数据集名称标注 Precision Recall 在图标题上。表2展示了本文算法相对于传统 式中：#TruePositive为将正约束对预测为正约束对 FCM算法聚类效果的提升率，提升率使用如下公式 的个数，#FalsePositive为将负约束对预测为正约束 计算得到： 对的个数，#FalseNegative为将正约束对预测为负 HDFCM_F FCM_F 约束对的个数。由于该评价方法的对象为约束对， 提升率= -×100% FCM_F 因此不仅可以应用于二分类的评价，也可应用于多 从图1可以看出，本文提出的算法在大部分数 类分类的评价。 据集上获得了最好的表现。相对于其他距离学习算 3.2对比算法 法而言，本文算法在sonar数据集和cmc数据集中 本文使用了若干经典距离学习算法进行对比， 虽未获得最好的表现，但是结合表2可以发现本文 包括：使用欧式距离的传统FCM算法(FCM),使用 算法的聚类效果相对于传统CM算法仍有一定的 欧氏距离但含有约束条件的K-均值聚类算法(C- 提升。由于本文使用的距离分量有限，因此对于不 Ec)【2),基于凸优化的全局距离学习算法(PG 同的数据集不一定能拟合出最适合于该数据集的距 DM)[3] 离度量。此外，从表2可以观察到，本文算法在 与本文提出的算法类似，C-Euc算法也是一种利 breast数据集和wine数据集上有相当卓越的表现。 用边信息进行距离学习的半监督聚类算法，它在传统 结合图1和表1可以得出，本文算法不仅适用 K-均值算法的基础上加上成对约束，在这些约束的监 于2类数据集，对于多类数据集也有较好的聚类效 督下进行聚类。C-Euc算法在聚类的过程中要求每 果。比如，2类数据集breast,3类数据集wine,7类 一次划分都满足已知的约束条件，每个样本在没有违 数据集segment在聚类效果上均取得了30%以上的 反约束条件的情况下，被划分给最近的类，最终得到 提升。 的聚类结果将满足所有的约束对信息[]。 1.0 PGDM算法由Xing等提出，是一种基于凸优化 0.8 的全局距离度量学习算法。它将正约束对构成的集 合记为S,负约束对构成的集合记为D。通过以下 凸优化问题对距离矩阵A进行求解： FCM min∑Ix-x,I C-Euc (xi》eS 0.2 PGDM-Ad GDM-Af st.∑‖x-xI4≥1，A≥0 HDFCM ()eD F precision recall (a)breast 式中：Ⅱ：，‖A=√(x,)A(,x)表示2个 1.0 样本点x,和x之间的距离。根据预期得到的矩阵 0.8 A的不同将有不同的解法。如果期望得到对角形式 的距离矩阵，可以通过牛顿法进行求解，本文将此算 0.6 法记为PGDM-Ad。如果期待得到全矩阵形式的距 0.4 IFCM 离矩阵，则可以通过梯度下降和逐次映射的方法进 C-Euc 0.2 PGDM-Ad 行求解，本文将此算法记为PGDM-Af。为了保证对 PGDM-AF HDFCM 比性，在实验中本文将学习得到的距离矩阵和本文 precision recall (b)sonar数（ ｍ ＝ ２，ε ＝ １０ －５ ，Ｔ ＝ １００，Ｃ ＝ １０ －５ ）。 实验将重 复每个聚类过程 ２０ 次，实验结果取其均值。 为了评估聚类效果，采用一种类似 Ｆ１ ⁃ｍｅａｓｕｒｅ 的成对约束评价方法，评价参数包括：ｐａｉｒｗｉｓｅ Ｐｒｅｃｉ⁃ ｓｉｏｎ，ｐａｉｒｗｉｓｅ Ｒｅｃａｌｌ 和 ｐａｉｒｗｉｓｅ Ｆ１ ， 定义为［２］ Ｐｒｅｃｉｓｉｏｎ ＝ ＃ＴｒｕｅＰｏｓｉｔｉｖｅ ＃ＴｒｕｅＰｏｓｉｔｉｖｅ ＋ ＃ＦａｌｓｅＰｏｓｉｔｉｖｅ Ｒｅｃａｌｌ ＝ ＃ＴｒｕｅＰｏｓｉｔｉｖｅ ＃ＴｒｕｅＰｏｓｉｔｉｖｅ ＋ ＃ＦａｌｓｅＮｅｇａｔｉｖｅ Ｆ１ ＝ ２ × Ｐｒｅｃｉｓｉｏｎ × Ｒｅｃａｌｌ Ｐｒｅｃｉｓｉｏｎ ＋ Ｒｅｃａｌｌ 式中： ＃ＴｒｕｅＰｏｓｉｔｉｖｅ 为将正约束对预测为正约束对 的个数， ＃ＦａｌｓｅＰｏｓｉｔｉｖｅ 为将负约束对预测为正约束 对的个数， ＃ＦａｌｓｅＮｅｇａｔｉｖｅ 为将正约束对预测为负 约束对的个数。 由于该评价方法的对象为约束对， 因此不仅可以应用于二分类的评价，也可应用于多 类分类的评价。 ３．２ 对比算法 本文使用了若干经典距离学习算法进行对比， 包括：使用欧式距离的传统 ＦＣＭ 算法（ＦＣＭ），使用 欧氏距离但含有约束条件的 Ｋ⁃均值聚类算法（Ｃ⁃ Ｅｕｃ） ［１２ ］ ，基于凸优化的全局距离学习算法 （ ＰＧ⁃ ＤＭ） ［３］ 。 与本文提出的算法类似，Ｃ⁃Ｅｕｃ 算法也是一种利 用边信息进行距离学习的半监督聚类算法，它在传统 Ｋ⁃均值算法的基础上加上成对约束，在这些约束的监 督下进行聚类。 Ｃ⁃Ｅｕｃ 算法在聚类的过程中要求每 一次划分都满足已知的约束条件，每个样本在没有违 反约束条件的情况下，被划分给最近的类，最终得到 的聚类结果将满足所有的约束对信息［１３ ］ 。 ＰＧＤＭ 算法由 Ｘｉｎｇ 等提出，是一种基于凸优化 的全局距离度量学习算法。 它将正约束对构成的集 合记为 Ｓ ，负约束对构成的集合记为 Ｄ 。 通过以下 凸优化问题对距离矩阵 Ａ 进行求解： ｍｉｎ Ａ （ｘ∑ｉ ，ｘｊ ）∈Ｓ ‖ ｘｉ － ｘｊ‖２ Ａ ｓ．ｔ． （ｘ∑ｉ ，ｘｊ ）∈Ｄ ‖ ｘｉ － ｘｊ‖Ａ ≥ １，Ａ ≥ ０ 式中： ‖ ｘｉ，ｘｊ‖Ａ ＝ （ｘｉ，ｘｊ） ＴＡ（ｘｉ，ｘｊ） 表示 ２ 个 样本点 ｘｉ 和 ｘｊ 之间的距离。 根据预期得到的矩阵 Ａ 的不同将有不同的解法。 如果期望得到对角形式 的距离矩阵，可以通过牛顿法进行求解，本文将此算 法记为 ＰＧＤＭ⁃Ａｄ。 如果期待得到全矩阵形式的距 离矩阵，则可以通过梯度下降和逐次映射的方法进 行求解，本文将此算法记为 ＰＧＤＭ⁃Ａｆ。 为了保证对 比性，在实验中本文将学习得到的距离矩阵和本文 算法一样应用于 ＦＣＭ 聚类算法中以评价。 ３．３ 实验结果与分析 对于各个数据集，本文所提出算法与其他算法 在 ８ 个数据集上的实验结果对比如图 １ 所示，其中 每一个子图的纵坐标表示了各个算法在相同参数下 在该数据集上的聚类效果的评价指标均值，横坐标 上的柱形分为 ３ 组，每一组分别表示 Ｆ１ 、ｐｒｅｃｓｉｏｎ 和 ｒｅｃａｌｌ。 每个颜色代表一个算法，从左至右分别为 ＦＣＭ 算法［ １４ ］ ， Ｃ⁃Ｅｕｃ 算法［１２］ ， ＰＧＤＭ⁃Ａｄ 算法［３］ ， ＰＧＤＭ⁃Ａｆ 算法［３］和 ＨＤＦＣＭ 算法，数据集名称标注 在图标题上。 表 ２ 展示了本文算法相对于传统 ＦＣＭ 算法聚类效果的提升率，提升率使用如下公式 计算得到： 提升率 ＝ ＨＤＦＣＭ＿Ｆ１ － ＦＣＭ＿Ｆ１ ＦＣＭ＿Ｆ１ × １００％ 从图 １ 可以看出，本文提出的算法在大部分数 据集上获得了最好的表现。 相对于其他距离学习算 法而言，本文算法在 ｓｏｎａｒ 数据集和 ｃｍｃ 数据集中 虽未获得最好的表现，但是结合表 ２ 可以发现本文 算法的聚类效果相对于传统 ＦＣＭ 算法仍有一定的 提升。 由于本文使用的距离分量有限，因此对于不 同的数据集不一定能拟合出最适合于该数据集的距 离度量。 此外，从表 ２ 可以观察到， 本文算法在 ｂｒｅａｓｔ 数据集和 ｗｉｎｅ 数据集上有相当卓越的表现。 结合图 １ 和表 １ 可以得出，本文算法不仅适用 于 ２ 类数据集，对于多类数据集也有较好的聚类效 果。 比如，２ 类数据集 ｂｒｅａｓｔ，３ 类数据集 ｗｉｎｅ，７ 类 数据集 ｓｅｇｍｅｎｔ 在聚类效果上均取得了 ３０％以上的 提升。 ·８４８· 智 能 系 统 学 报 第 １０ 卷