基于成对约束的半监督凝聚层次聚类算法

盛俊杰，谢丽聪

(福州大学 数学与计算机学院，福建 福州350108)

聚类即根据数据集中数据的不同特征将其划分为不同簇的过程，使得同一个簇中的样本之间具有较高的相似度，而不同簇中的样本之间具有高度相异度。聚类过程中通常没有类别标签等监督信息，因而是一种无监督的学习。传统的无监督学习通常只利用无标签样本进行学习，而监督学习只利用有标签样本进行学习，半监督学习的优越性体现在其同时利用无标签样本和有标签样本进行学习。半监督聚类算法研究如何利用少量的监督信息来提升聚类性能[1]，使用的监督信息既可以是类标签，也可以是一对样本是否属于同一类的约束信息。半监督聚类算法对聚类性能的提高主要依赖于监督信息，监督信息的选取非常关键。

对于现实世界的无监督学习算法，例如人的语音识别、GPS道路检测等，以成对约束形式出现的监督信息更实际。对用户而言，要确定样本类标签比较困难，但是获得关于两个样本是否属于同一类的约束信息则较为容易[2]。其中涉及两类成对点约束，分别是must-link和cannot-link。

与监督学习相比，无监督聚类过程缺少用户或分类器(如类标签信息)的指导，因此不能产生理想的聚类结果。使用某种监督形式，例如成对约束，可以显著提高无监督聚类的质量。本文将监督信息的信息含量应用到聚类中，提出一种基于成对约束的半监督凝聚层次聚类算法。

1 成对约束概念

半监督聚类使用的成对约束表示两个样本一定被分到同一个簇或者一定被分到不同的簇。两个广泛使用的成对约束方法是must-link约束和cannot-link约束，其中，must-link约束表示两个样本一定被分配到同一个簇，cannot-link约束代表两个样本一定被分到不同的簇[3]。令 Con(i，j)表示样本 xi和样本 xj之间的成对约束，如下表示：

很明显地可以看出，如果 Con(i，j)＝1，则 Con(j，i)＝1；如果 Con(i，j)＝-1，则 Con(j，i)＝-1。

2 凝聚层次聚类算法(AHC)

层次聚类方法是根据给定的簇间距离度量准则，构造和维护一棵由簇和子簇形成的聚类树，直至满足某个终结条件为止。根据层次分解是自底向上还是自顶向下形成，层次聚类方法可以分为凝聚的(Agglomerative)和分裂的(Divisive)两种[4]。一个纯粹的层次聚类方法的聚类质量受限于如下的特点：一旦一个合并或分裂被执行，就不能修正。

凝聚层次聚类AHC(Agglomerative Hierarchical Clustering)采用自底向上的策略，首先将每个样本作为一个簇，然后合并这些原子簇为越来越大的簇，直至所有的样本都在一个簇中，或者满足某个终结条件。绝大多数层次聚类方法都属于这一类，它们只是在簇间距离的定义上有所不同。图1是凝聚层次聚类的一个简单例子。

聚类簇C1和聚类簇C2的距离为：

AHC算法的步骤如下：

输入：未知分布的样本集 S＝{x1，x2，…，xN}

输出：最优的聚类分组{C1，C2，…，CK}

(1)假设初始聚类分组为：g＝{C1，C2，…，CN}，初始的聚类簇个数为 Y＝N，计算所有的距离 d(C，C′)，其中 C、C′∈g。

本文凝聚层次聚类的簇间距离的度量采用了中心点的方法。设C是一个聚类簇，xk是C中的样本，则C的中心点为：止，输出结果；如果 Y＞K，算法跳转到步骤(3)。

(3)计算所有的距离 d(Cr，C″)，其中 C″∈g。 跳转到步骤(2)。

3 基于成对约束的半监督凝聚层次聚类算法

在PS-AHC中，P代表成对约束 Pairwise Constraints，S代表半监督Semi-supervised。

3.1 近邻度的定义

本文提出了近邻度这个新的概念，其思想是基于k近邻分类算法的。k近邻分类算法的思想是：找出距离待分类样本最近的k个有标记样本，在这k个有标记样本中，哪个类别的样本占的数目最多，待分类样本就属于哪个类别。在KNN算法中，待分类样本的类别由它附近最近的k个样本决定。

对于每一个样本 xi，都有一个近邻度 αi，αi≥0，αi的定义如下：

其中，k是给定的参数，xm是距离样本xi最近的k个样本。

如图2所示，有 x1、x2和 x3三个样本，圆的半径代表相应样本的近邻度。近邻度大，说明该样本附近的样本分布比较稀疏，样本之间的距离比较远；反之，近邻度小，说明该样本附近的样本分布比较密集，样本之间的距离比较近。

3.2 利用成对约束改变聚类簇之间的距离

首先，定义两个集合 ML(C；x)和 CL(C；x)。 ML(C；x)指在聚类簇C中与样本x具有must-link约束关系的样本的集合，CL(C；x)指在聚类簇C中与样本x具有cannotlink约束关系的样本的集合，表示如下：

其次，在 ML(C；x)和 CL(C；x)的基础上定义集合的并 ML(C；C′)和 CL(C；C′)：

最后，用 K(C；C′)表示所有 ML(C；C′)和 CL(C；C′)的近邻度之差：

例 如，C＝{x1，x2，x3}和 C′＝{x4，x5，x6}是 两 个 聚 类 簇，(x1，x4)和 (x3，x5)是 must-link 约 束， (x2，x6)是 cannot-link约束。 那么，ML(C；C′)、CL(C；C′)和 K(C；C′)的计算结果如下：

同样，ML(C′；C)、CL(C′；C)和 K(C′；C)的计算结果如下：

有了 K(C；C′)的定义，聚类簇 C1和聚类簇 C2的距离被调整为：

其中，｜C1｜和｜C2｜分别表示 C1的样本数和 C2的样本数。

PS-AHC算法的步骤如下：

输入：未知分布的样本集 S＝{x1，x2，…，xN}和样本的成对约束信息 Con(i，j)

输出：最优的聚类分组 C＝{C1，C2，…，CK}

(1)假设初始聚类分组为：g＝{C1，C2，…，CN}，初始的聚类簇个数为 Y＝N，利用式(5)计算所有的 K(C；C′)，C、C′∈g，再利用式(6)计算所有的距离 d(C，C′)，C、C′∈g。

(3)利用式(5)计算所有的 K(C；C′)，C、C′∈g，再利用式(6)计算所有的距离 d(C，C′)，C、C′∈g。 跳转到步骤(2)。

4 实验结果与分析

为了验证本文提出的PS-AHC算法的有效性，对AHC和PS-AHC这两个算法进行了对比实验。从UCI数据集[5]上选择了 5个完整的数据集，分别是 haberman、balance-scale、iris、tae（teaching assistant evaluation）和 pid（pima indians diabetes）。在每个数据集S中，随机地选择一些样本对，对这些样本对生成must-link约束和cannotlink约束。成对约束的数量设置为总样本集数量的3倍，即为3×｜S｜。所有算法各运行 30次，取平均的聚类准确率，实验结果对比如表1所示。

表1 AHC和PS-AHC的聚类准确率比较

从实验结果可以看出，PS-AHC表现出了比AHC更优越的性能。这是因为PS-AHC引进了样本的成对约束信息。PS-AHC利用成对约束信息改变聚类簇之间的距离，使有must-link约束的两个聚类簇的距离变得更近，而有cannot-link约束的两个聚类簇的距离变得更远，从而改变层次聚类的树结构。实验结果同时表明，本文所提出的近邻度概念是有效的。

成对约束是样本的一种监督信息。本文利用成对约束来指导聚类过程，提出了一种基于成对约束的半监督凝聚层次聚类算法（PS-AHC）。PS-AHC利用成对约束来改变聚类簇之间的距离，使聚类簇之间的距离更真实。在UCI数据集上的实验表明，PS-AHC能有效地提高聚类的准确率，是一种有前景的半监督聚类算法。

[1]BILENKO M，BASU S，MOONEY R J.Integrating constraints and metric learning in semi-supervised clustering[C].Brodley CE，ed.Proc.of the 21st Int’l Conf.on Machine Learning.New York：ACM Press，2004：81-88.

[2]李昆仑，曹峥，曹丽苹，等.半监督聚类的若干新进展[J].模式识别与人工智能，2009，22(5)：735-742.

[3]BASU S，BANERJEE A，MOONEY R J.Active semi-supervision for pairwise constrained clustering[C].Proc.of the SIAM Int’l Conf.on Data Mining.Cambridge：MIT Press，2004：333-344.

[4]Han Jiawei，KAMBER M.数据挖掘概念与技术[M].范明，孟小峰，译.北京：机械工业出版社，2004：1-262.

[5]NEWMAN D J，HETTICH S，BLAKE C L，et al.UCI repository of machine learning databases[EB/OL].http：//www.ics.uci.edu/～mlearn/MLRepository.htm l,1998.