基于图的半监督学习的距离度量改进

兰远东　高蕾

摘 要：基于图的半监督学习的一个关键问题是：图上顶点之间的距离度量的有效性问题。为了解决这个问题，提出了基于图的半监督学习的距离度量改进方法。通过在现有密度敏感的距离度量方案中添加补偿参数的方法，使得改进的距离度量方案不但能够有效的扩大不同类别的高密度区域样本间的距离，同时还能缩小相同类别中样本之间的距离。将改进的距离度量方案应用到聚类算法中，来验证改进的距离度量方案的有效性。实验结果表明：改进的距离度量方法能够有效的扩大不同类别间距离，增强类内聚合度。

关键词：半监督学习；距离度量；聚类；机器学习

中图分类号：TP319.4 文献标识号：A 文章编号：2095-2163（2014）02-

Improved Distance Measure for Graph Based Semi Supervised Learning

LAN Yuandong， GAO Lei

（Department of Computer Science， Huizhou University， Huizhou Guangdong 516007， China）

Abstract： A key problem in graph-based semi supervised learning is the effectiveness of distance measurement between the vertices of graph. In view of this， an improved distance measure method is proposed for semi-supervised learning. The method cans effective amplification the distance between data points in different high density region and reduces the distance between data points in the same high density region by adding an offset parameter. Then， a graph based semi supervised clustering algorithm is presented based on this improved distance measurement. Experimental results shows that the improved method can effectively increase the scatter of inter classes and reduce the scatter of intra-class.

Keyword： semi supervised learning； distance measurement； clustering； machine learning

0 引 言

半监督学习的目的是利用无标记数据来改进机器学习的性能[1]。聚类假设认为决策边界应该存在于数据的低密度区域，而不是存在于高密度区域[2]。几乎所有有效的半监督学习方法都是基于聚类假设，或者间接使用了聚类假设。基于图的半监督学习方法通过利用所有数据来构建一个图，图上的节点就是数据集中的样本点（包含标记数据和未标记数据），连接图上任意两个顶点之间的边则是两个样本点之间相似性的表征[3]。学习方法通常并不需要数据点本身，而是需要两个点之间的距离。这样的学习方法都假定样本点的标记在图上平滑分布，而图则是基于图的半监督学习方法的核心所在[4-8]。通常将要构建的图需要能够反映数据的真实分布，但是图的构建方法却并未取得卓有成效的研究成果[9]。大多数基于图的半监督学习算法都是通过高斯函数来计算两个顶点之间的连接边的权值，即[10]：

（1）

学习算法的性能对参数 比较敏感[11]，并且在处理复杂的现实问题时，这种简答的基于欧几里德距离的相似性度量方法，并不能真实全面地反映复杂空间数据的分布，可以通过图1来说明这个问题。

图1 距离度量示例

Fig. 1 Example for distance measurement

在图1中，点B和点C之间的欧几里德距离相对较近，但是根据聚类假设，点A与点B则属于同一个类别，也就是A与B更加相似，意即更加接近。公式（1）的距离计算方法，并不能反映图1中的这种情况。

为了解决这个问题，文献[12，13]中提出了两个版本的密度敏感的距离度量方法。两个版本的距离方法都能够度量流行上的最短路径，并且能够反映数据集的内在的流行结构。通过使用短边来连接高密度同类样本中的样本点，而用长边来连接不同的高密度区域之间的样本点。在对这两个版本的密度敏感的距离度量进行了深入分析之后，本文提出了一种改进的密度敏感的距离度量方法。并且基于改进的密度敏感的距离度量方法，更进一步地提出了一种新的密度敏感的半监督聚类（a new density-sensitive semi-supervised clustering， NDS-SSC） 算法。

1 密度敏感的距离度量

通过聚类假设可以知道，同类样本趋向于聚集在一个相同的高密度区域内，在不同的聚类之间存在相对稀疏的数据分布区域，这就能够推知决策边界应该存在于低密度区域。研究中，需要找到一种距离度量方法，能够刻画数据的局部一致性和全局一致性。由于密度敏感的距离度量方法能够反映数据聚类的空间分布，由此即获得了机器学习界的广泛关注。在本小节中，介绍两个版本的密度敏感的距离度量方法。每个方法都包含两个步骤，通过这两个步骤，不同类别的样本之间的距离得到拉伸，而同类样本之间的距离得到压缩。文献[12]即使用下面的两个步骤来执行密度敏感的距离度量，具体论述如下：

步骤（1）：通过给定的拉伸函数来计算图上顶点之间的距离长度，并且可以通过该步骤调节样本的密度；计算公式为：

（2）

其中， 是样本 和 之间的欧几里德距离， 是拉伸因子。

步骤（2）：定义 是图G=（V，E，W）上的长度为 的路径，如果 且 ，则 。路径 指的是连接节点 到 之间的路径， 表示所有连接 和 的路径的集合，可以得到：

（3）

其中， 是图上 到 之间的最短路径。

除此之外，文献[12]中还给出了另外一种距离度量公式：

（4）

文献[13]和文献[12]使用相同的聚类假设和前提条件，但是在两个步骤中却使用了不同的公式来度量距离，具体如下：

步骤（1）：采用的公式为：

（5）

步骤（2）：采用的公式为：

（6）

其中， 表示 到 之间的路径长度。

2 改进的距离度量与算法

聚类假设表明，决策边界不应穿过数据空间的高密度区域，而应存在于低密度区域。回顾一下Chapelle的密度敏感的距离度量方法[12]，其计算公式为：

（4）

该方法使用拉伸函数 来拉伸距离 ，其后寻找拉伸后的 与 之间的最短距离。问题主要在于：经过特征归一化的处理，距离 通常存在于区间[0，1]中，在这个区间中 变化缓慢，也就是对距离的拉伸效果不明显。在此借助图2来说明该问题。拉伸函数的拉伸效果如图2所示。

图2 拉伸函数的拉伸效果示例

Fig. 2 Example for the effect of strench function

在图2中，可以看到拉伸函数改变缓慢，拉伸效果并不明显。为了改善这个问题，本文在公式中加入一个补偿参数 ，具体如下：

（7）

其中， 是拉伸因子， 是补偿参数。可以选择合适的 值，来达到最佳的拉伸效果。基于此，可以按照下面的方法重新定义密度敏感的距离度量。

定义 是图G=（V，E，W）上的长度为 的路径，如果 其中 ，则 。路径 指的是连接节点 到 之间的路径， 表示所有连接 和 的路径的集合，密度敏感的距离度量定义如下：

（8）

当 时， 是图上 和 之间的最短的欧几里德距离；当 时，结果即与公式（4）相同。

综上所述，通过密度敏感的距离度量，可以得到密度敏感的相似矩阵如下：

（9）

接下来，使用与文献[14]中相似的方法，采用公式（10）所示的正则化框架来解决标记数据不足的情况。

（10）

公式（10）的封闭解是：

（11）

求解公式（11）将具有很高的时间复杂度，因此本文使用迭代防范来求解公式（11），即：

（12）

根据公式（12），得到下面的聚类算法。方法步骤为：

步骤（1）：根据数据空间中的样本，建立一个全连图G=（V，E，W），V是所有样本（包含有标记和无标记数据）的集合，E是边的集合，W是权值集合，W中的 ，在W中的每一行保留K个最小的值；

步骤（2）：通过公式（8）计算密度敏感的距离度量矩阵 ；

步骤（3）：通过公式（9）构建密度敏感的相似矩阵W；

步骤（4）：使用迭代方法求解公式（12），得到 ；

步骤（5）：使用聚类算法来聚类数据集FU。

3 实验结果与分析

3.1 实验数据集

为了评估算法的聚类性能，实验采用机器学习领域中比较流行的基准数据集：UCI（UC Irvine machine learning repository）数据集（http：//archive.ics.uci.edu/ml/）。主要采用UCI数据集中的Iris，Ionosphere，Glass和Image segmentation数据集，表1列出了4个数据集的主要信息。

在实验中，首先验证参数 和 对聚能性能的影响；然后在将本文的算法与基于公式（1）的GB-SSC（Gaussian-Based Semi-Supervised Clustering， GB-SSC）算法以及基于公式（4）的DS-SSC（Density-Sensitive Semi-supervised Clustering， DS-SSC）算法进行对比。在上述4个数据集上单独进行实验，最后给出平均测试错误。

3.2 参数选择

由于参数 能够改善对数据空间中的样本间距离的拉伸效果，为了验证 对聚类性能的影响，从每个数据集中随机选择20个样本作为标记数据，实验结果如图3所示。

图3 补偿参数 对聚类性能的影响

Fig. 3 Impact of the offset parameter to clustering performance

从图3可以看出：当 时，参数 对公式（8）没有影响，所以性能曲线是一条水平线。总体来说，在 =5的附近，测试错误率最小。但是，当 时， =8的性能曲线最优。这是因为当 ，拉伸函数改变缓慢，就需要更大的补偿参数 才能获得较好的聚类结果。

同样，实验还给出了参数 对聚类性能的影响结果，图4是在不同的 值时的测试错误率即如图4所示。

图4 参数 对聚类性能的影响

Fig. 4 Impact of parameter on the clustering performance

由图4可以清楚地看到，NDS-SSC的测试错误率要明显低于算法DS-SSC的错误率，特别是在 时，聚类性能最优。当 时，两个算法具有相同的测试错误率，这是因为当 时，补偿参数 对聚类性能没有任何影响。

最后，从每个数据集中随机选择20个样本作为标记样本，建立K近邻图（K-nearest neighbors graph），并设定K=30。然后通过聚类算法来判别余下样本的所属的类别，分别进行10次实验，最后计算每个算法的平均错误率，结果如表2所示。

从实验结果可以看出密度敏感的半监督聚类算法的错误率，要明显低于GB-SSC。这表明保持原始数据的空间信息一致性，对于聚类效果起着至关重要的作用。随着训练数据的增加，错误率也随之下降，这就表明要真实地反映数据空间的结构，单独使用少量的标记样本是很难做到的，还需要充分利用未标记的样本来认识数据的分布结构，这正是半监督学习得以发展的原因所在。另外，本文算法的聚类效果要优于DS-SSC和GB-SSC，这也说明补偿参数 能够有效地扩大不同样本之间的距离，并缩小同类样本之间的距离。

4 结束语

本文通过构建一个图来反映数据的真实分布，确保聚类假设的有效性。通过对两种密度敏感的距离度量方法的研究与分析，提出了一种改进的密度敏感的距离度量方法。该方法能够有效扩大不同密度区域之间样本的距离，同时还能缩小同一密度区域中样本之间的距离。另外，本文还给出了基于改进的密度敏感的距离度量方法的聚类算法，并在UCI基准数据集上进行实验，验证了本文算法的有效性。

参考文献：

[1] 俞亚君， 霍静， 史颖欢， 等. SSXCS： 半监督学习分类系统[J]. 南京大学学报： 自然科学版， 2013， 49（005）： 611-618.

[2] 吴烨， 钟志农， 熊伟， 等. 一种高效的属性图聚类方法[J]. 计算机学报， 2013， 36（8）： 1704-1713.

[3] 郭涛， 李贵洋， 兰霞. 基于图的半监督协同训练算法[J]. 计算机工程， 2012， 38（13）： 163-168.

[4] TEICHMAN A， THRUN S. Tracking-based semi-supervised learning[J]. The International Journal of Robotics Research， 2012， 31（7）： 804-818.

[5] BUNKE H， RIESEN K. Towards the unification of structural and statistical pattern recognition[J]. Pattern Recognition Letters， 2012， 33（7）： 811-825.

[6] XU X， LU L， HE P， et al. Protein Classification Using Random Walk on Graph[M]//Emerging Intelligent Computing Technology and Applications. Springer Berlin Heidelberg， 2012： 180-184.

[7] LUO D， DING C H Q， HUANG H， et al. Forging the graphs： a low rank and positive semidefinite graph learning approach[C]//BARTLETT P， PEREIRA F C N， BRUGES C J C， et al. NIPS， 2012： 2969-2977.

[8] PLESS N M， MAAK T， STAHL G K. Developing responsible global leaders through international service-learning programs： The Ulysses experience[J]. Academy of Management Learning & Education， 2011， 10（2）： 237-260.

[9] ZHANG C， WANG F. Graph-based semi-supervised learning[J]. Frontiers of Electrical and Electronic Engineering in China， 2011， 6（1）： 17-26.

[10] 兰远东. 基于图的半监督学习理论， 算法及应用研究[D]. 广州：华南理工大学， 2012.

[11] 陈诗国， 张道强. 半监督降维方法的实验比较[J]. 软件学报， 2011， 22（1）： 28-43.

[12] CHAPELLE O， ZIEN A. Semi-supervised classification by low density separation[C]//Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics， pp. 57-64， 2005.

[13] WANG L， BO L F， JIAO L C. Jiao. Density-sensitive semi-supervised spectral clustering. [J]. Journal of Software，2007，18（10）.

[14] CAI D， WANG X， HE X. Probabilistic dyadic data analysis with local and global consistency[C]//Proceedings of the 26th Annual International Conference on Machine Learning. ACM， 2009：105-112.