结合弱监督信息的凸聚类研究

权祯臻 陈松灿

(南京航空航天大学计算机科学与技术学院 南京 211106) (zz.quan@nuaa.edu.cn)

结合弱监督信息的凸聚类研究

权祯臻 陈松灿

(南京航空航天大学计算机科学与技术学院 南京 211106) (zz.quan@nuaa.edu.cn)

基于目标函数的聚类是一类重要的聚类分析技术，其中几乎所有算法均是经非凸目标的优化建立，因而难以保证全局最优并对初始值敏感.近年提出的凸聚类通过优化凸目标函数克服了上述不足，同时获得了相对更稳定的解.当现实中存在辅助信息(典型的如必连和或不连约束)可资利用时，通过将其结合到相应目标所得优化模型已证明能有效提高聚类性能，然而，现有通过在目标函数中添加约束惩罚项的常用结合方式往往会破坏其原有凸目标的凸性.鉴于此，提出了一种新的结合此类弱监督辅助信息的凸聚类算法.其实现关键是代替在目标函数中添加约束，而是通过对目标函数中距离度量的改造以保持凸性，由此既保持了原凸聚类的优势同时有效提高了聚类性能.

基于目标函数的聚类；凸聚类；弱监督信息；约束；距离度量；半监督聚类

聚类算法是多元数据分析的重要工具，是知识发现和数据挖掘的关键技术，已广泛用于生物信息学[1]、图像处理[2]、信息检索[3]等领域.聚类是依据给定的相似性度量，将数据集样本划分成若干个通常不相交的子集或簇，使得簇内相似度和簇间相异度最大[4].目前已有众多聚类算法被提出[5]，其中，基于目标函数的聚类是一类重要的聚类方法，其通过最小化或最大化一个全局目标函数实现对无标记数据的最优划分[6]，常见此类算法有k均值算法、模糊k均值算法、最大期望聚类算法等.然而，几乎所有基于目标函数的聚类算法都难以保证解及性能的稳定性，归咎于通过非凸目标的优化建立，易陷入局部最优解且对初始值敏感.为克服上述不足，2011年，Lindsten等人[7]和Hocking等人[8]分别将k均值算法和层次聚类凸松弛化，通过促使簇中心的融合获取全局最优解.鉴于凸聚类具有可求取全局最优解、对数据扰动相对不敏感及自动获取簇数的优势，近年已备受关注，相关研究集中在优化方面(如文献[9])和数据结构信息的结合方面(如文献[10-13]).

聚类本身是一种典型的无监督学习任务，然而当有一些额外的监督信息可资利用时，利用这些监督信息能获得更优的聚类效果[14].常用的监督信息大致有2种：1)个体的样本标记或类别；2)样本必连(must-link)和不连(cannot-link)约束，前者是指2个样本必须属于同一簇，后者则指2个样本必不属于同一簇.由于这种成对约束给出的先验信息弱于数据标记给出的先验信息[15]，故又被称为弱监督信息或辅助信息.本文主要关注第2种辅助型监督信息.将辅助信息结合到聚类目标所得优化模型已被证明能够有效提高聚类性能，如文献[15-20].现有的此类半监督聚类算法都基于非凸目标建模和优化，故按上述方式添加约束后目标函数的性质未改变，遗传了非凸优化对初始值敏感、难以保证全局最优的缺点.

依据上述在基于非凸目标函数的聚类中添加辅助信息可提高性能的经验，我们猜测凸聚类结合此类信息也可提高其性能.然而此方面研究尚未出现，故本文尝试弥补这一缺漏.在凸聚类中添加约束看似容易，然而研究中发现将必连约束作为惩罚项添加到目标函数中仍能保持其凸性，但将不连约束作为惩罚项添加到目标函数则会破坏其凸性，从而失去凸聚类的优势并退化为一个基于非凸目标函数的聚类任务.因此本文尝试通过对凸聚类目标函数中距离度量的改造以保持凸性.对于容易处理的必连约束，借鉴Klein等人[15]的方法改造距离矩阵，再恢复样本空间；对于较难处理的不连约束，受到Asafi等人[19]工作的启发，将不连约束转化为特征空间的增广.由此处理辅助信息后，对改变了距离度量的数据集进行凸聚类.最后，在模拟数据集和UCI数据集上的实验结果显示本文所提模型能够有效提高凸聚类的性能.

1 相关工作

首先回顾凸聚类及相关工作.Lindsten等人[7]和Hocking等人[8]将聚类任务改造为一个凸优化问题，对于由n个无标记样本构成的数据集X={x1,x2,…,xn}(xi∈M)，优化严格凸的目标函数：

(1)

其中，第1项是损失函数，第2项是正则化项且一般取1,2范数，取1范数时式(1)与fused拉索[21]具有相似性.权重wij非负且wij=wji，ui是样本xi的簇中心.对于任意参数γ，式(1)存在唯一的最小值，参数γ控制簇数：若γ=0，则ui=xi时式(1)取最小值，每个簇仅有一个样本；随着γ的增大，簇中心逐渐融合，ui=uj时将xi与xj归为同一簇；若γ过大，则将所有样本聚为一个簇.

对凸聚类的研究主要在2方面展开.1)优化方面.鉴于交替迭代乘子方法(alternating direction method of multipliers, ADMM)适用于解决统计学、机器学习等领域的分布式的凸优化问题[22]，Chi等人[9]提出用ADMM方法[22]加速式(1)的求解过程，并提出了运行效率更高的交替最小化方法(alternating minimization algorithm, AMA)[23]，这2种方法现已成为凸聚类相关算法的常用优化方法.2)数据结构信息的结合方面.其包括2个子方向：①改造凸聚类使其适用于特定情形：Hallac等人[10]提出了具有较强扩展性的network拉索，其是group拉索的泛化形式，适用于大规模图网络的聚类和优化；Wang等人[11]提出了适用于高维数据的稀疏凸聚类，该算法能够在凸聚类的同时进行特征选择，不仅提高凸聚类的性能而且极大地降低了算法时间复杂度；②将已有聚类算法凸松弛化：Lu等人[12]将谱聚类改造为凸稀疏谱聚类，并将该算法拓展为成对的稀疏谱聚类以利用数据的多视图信息提高聚类性能；Chi等人[13]将凸聚类拓展到凸双聚类，其目标函数的正则化项由行、列簇中心的fused拉索惩罚项共同构成，通过迭代地对行、列进行凸聚类实现算法.

将辅助信息与非凸目标结合的聚类算法，大致有3种:

1) 贪婪迭代搜索方法[1]，如Wagstaff等人[16-17]提出的COP-COBWEB算法和约束k均值(COP-Kmeans)算法，前者基于Fisher等人[24]提出的COBWEB算法，后者基于传统的k-means算法.每次都会检查数据分配是否符合约束条件，若整个聚类过程都不违反约束，则得到的簇符合要求.其主要缺点是不能将成对约束给出的信息扩散到整个样本空间，即不能充分利用约束以反映样本空间的分布[15]，导致聚类结果失真.

2) 将约束作为惩罚项[18]添加到相应目标函数中，而后优化出模型.这是一种较为常用的半监督聚类方法，如文献[18]，但此方法可能改变原目标函数的性质.

3) 改造距离度量，此方法可弥补前2种方法的不足.必连关系具有传递性且具有明显的几何特征，容易处理，然而，寻找满足不连约束的距离度量是一个NP完全的问题[15]，故改造距离度量的难点在于不连约束的处理.Klein等人[15]提出了基于层次聚类的CCL(constrained complete-link)算法，其处理不连关系的巧妙之处在于代替直接恢复样本空间的距离度量，而是在每次合并簇时获取一个新的距离度量，间接地将不连约束提供的信息扩散到样本空间.Asafi等人[19]提出了一种有趣的方法处理不连约束：若向特征空间为M维的数据集添加N个不连约束，则每个不连约束对应一个新的特征维度，利用扩散映射(diffusion map)[25]将特征空间增广到M+N维，具体参考3.2节.鉴于相对约束衡量了3个样本之间的相似关系，能够较好地反映样本分布的局部区域信息从而指导聚类，Lesek等人[20]在文献[19]的基础上将相对约束转化为特征空间的增广.

2 模型建立

结合弱监督信息的凸聚类算法具体分为2个阶段：1)通过距离度量的改造添加约束；2)对改造距离度量后的数据集进行凸聚类.本节将分别对其详细地介绍.

2.1添加约束

(2)

φ(xi,xj)=|Ψt(xi)-Ψt(xj)|，

(3)

(4)

(5)

(6)

2.2凸聚类

2.2.1 权重

(7)

2.2.2 正则化项参数的选择

Lange等人[29]提出用聚类稳定性理论评价模型的有效性：从同一数据源抽取若干组样本进行聚类时，结果应具有可重现性、对于抽取的样本不敏感.Wang等人[30]用此理论选择簇数：每次将包含n个样本的数据集划分成2组训练集和1组验证集，用验证集衡量训练得到的2个模型的稳定性.这种方法的缺点是训练样本数量缩减为n3，所得模型不可靠.为提高训练模型的可靠性，Fang和Wang等人[31]对上述方法做出改进：每次用Bootstrap方法抽取2组各包含n个样本的训练集，得到2个训练模型并计算其聚类距离，如式(8).推广上述理论：一个好的正则化参数也应对于微小的数据扰动不敏感，故将Bootstrap方法用于式中正则化参数的选取，具体如算法1所示：

算法1. 选取正则化参数γ.

输出：最优正则化参数γ.

/*第1阶段：抽样*/

① forb=1,2,…,Bdo

② forj=1,2 do

④ end for

⑤ end for

/*第2阶段：计算各正则化参数对应的聚类不稳定性*/

⑥ forg=1,2,…,Gdo

⑦ forb=1,2,…,Bdo

(8)

⑨ end for

⑩ end for

(9)

/*第3阶段：获取最优正则化参数*/

2.2.3 AMA算法

本文涉及的凸聚类均用AMA算法优化.首先，给出式(1)的增广拉格朗日形式：

(10)

再用对偶上升方法迭代地更新各变量，第m次迭代过程如下：

(11)

AMA算法的具体推导过程可参考文献[9].由于其实际迭代过程中只需更新U,Λ，且更新Λ的复杂度取决于权重集合W的稀疏性，故相比式(11)极大地减少了算法运行时间.具体如算法2所示：

算法2. AMA.

输入：数据集X、权重集合W、正则化参数γ；

输出：变量V.

① 初始化Λ0;

② repeat

③ fori=1,2,…,n

(12)

⑤ end for

(13)

⑧ end for

⑨ until满足收敛条件.

(14)

优化结束后进行簇的分配.首先，由X构造包含n个顶点的图，并将满足v=0的第对样本用一条边连接；再对该图进行广度优先搜索，得到若干连通分量，每个联通分量对应一个簇.

3 实验与结果

3.1实验设置

(15)

为方便叙述，将必连约束记为ML，不连约束记为CL.弱监督信息可通过2种方法获取:1)随机获取.从同一/不同类中随机抽取的2个样本构成一个ML/CL.2)由样本真实分布获取.用L(xi)表示xi的真实类号，设定k1，k2且k1>k2.对于每个样本xi，若k1NN(xi)中满足L(xi)=L(xj)(xj∈k1NN(xi))的样本数目小于k2，则选取距xi较近且满足L(xi)≠L(xj)的样本xj构成CL，记为(xi,xj).若(xi,xj)、(xi,xt)都是与xi相关的CL，且Di,j

对X′进行3种实验：仅添加ML、仅添加CL、同时添加2种约束(ML与CL各 占12).逐渐增加约束数目，并针对每个约束数目随机选取4～5组不同的约束进行实验.每次实验等同于将X′按照第2节进行建模与优化，其凸聚类阶段的相关设置具体如下：正则化项取2范数；结合高斯核(用局部尺度化方法改造)与k近邻计算权重集合W，且k=

实验均在配置为英特尔i5-3470 CPU，16 GB内存的计算机上执行，由R语言实现，且用R的多线程实现正则化参数选择模块的加速.

3.2实验结果

本文在模拟数据集和真实数据集上实验：模拟生成的2个圆圈数据集和2个半月数据集，如图1所示，4个真实数据集取自UCI[36](Iris选取了难分的2类数据)，具体如表1所示：

Table 1 Data Sets表1 数据集

Fig. 1 Simulated data sets图1 模拟数据集

Fig. 2 Evaluation on clustering performance图2 聚类性能评价结果

聚类性能的比较结果如图2所示，横坐标为约束数目，纵坐标为聚类性能评价结果，由图和实验数据可获得5种信息：

1) 结合弱监督信息的凸聚类性能优于无约束的凸聚类.随着约束的增多，聚类效果更优，这与直觉吻合.部分数据集在添加少量约束时就已获得较高性能，反映了约束的稀疏性.

2) 具体比较3种实验的性能.仅添加ML时，性能的提高幅度较明显并趋于最优；仅添加CL时，性能相对稳定；同时添加ML和CL时，性能的提高幅度也较明显，有时优于仅添加ML或CL时的情形.整体而言，性能在约束较少时波动较大，随约束的增多趋于稳定，ARI的波动比RI大.

3) 比较聚类所得簇数与真实类数.表2为部分数据集在不同约束下的平均簇数，可见：仅添加ML的实验在约束较少时簇数偏多，约束增多时簇数趋于真实类数；只添加CL时簇数相对稳定，约束过多时簇数相对较多；同时添加ML和CL时簇数稳定，约束较多时更逼近真实类数.

4) 比较聚类结果的约束符合率，即符合约束条件的样本对的数目与所添约束总数的比值.表3为Banknote在3种实验中的平均约束符合率，可见：仅添加ML的实验在约束较少时符合率较低，另外2种实验的约束符合率一直保持较高水平；在约束较少时，同时添加ML和CL使得ML的约束符合率也很高，故联合使用CL可提高约束符合率.

Table 2 Average Number of Clusters表2 平均簇数

Table 3 Average Coincidence of Constraints in Banknote表3 Banknote的平均约束符合率

5) 比较约束的重要性对聚类性能的影响.表4为将Iris数据集依照样本分布获取的约束按重要性降序排序后，相同约束数目下前3组实验的RI值.可见：约束数目相同时，聚类性能与约束的重要性呈正相关关系，约束数目增多时性能趋于稳定，故弱监督信息的质量对聚类结果有重要影响.

Table 4 RI of Iris with Constraints Sorted表4 Iris的芮氏指标(约束依重要性排序)

4 总结与展望

本文鉴于凸聚类的优势及基于非凸目标函数的半监督聚类算法可获取更优聚类效果的经验，提出了一种结合必连与不连辅助信息的凸聚类算法，通过对凸聚类目标函数中距离度量的改造保持了其凸性，并通过实验证明了此算法能够有效提高聚类性能.此算法存在2个缺点：1)不连约束过多时算法运行时间较长，影响算法效率；2)遗传了凸聚类不允许聚簇重叠的缺点.针对缺点1，可考虑2个层面：1)实验结果反映了约束的稀疏性，即添加相对少的约束就可获得较高的聚类性能，故实际应用中毋须添加过多约束以避免冗余；2)结合聚类集成[37]方法，将约束集合划分为若干允许重叠的子集，并行地运行凸聚类再集成聚类结果.针对缺点2，可将模糊C均值算法与凸聚类结合，进行建模与优化.故下一步工作是聚类集成以及模糊C均值算法与凸聚类的结合.

[1] Madeira S C, Oliveira A L. Biclustering algorithms for biological data analysis: A survey[J]. IEEE/ACM Trans on Computational Biology and Bioinformatics, 2004, 1(1): 24-45

[2] Oliveira D, Valente J, Pedrycz W, et al. Advances in fuzzy clustering and its applications[M]. New York: John Wiley & Sons, 2007: 285-311

[3] Liu Ming, Liu Bingquan, Liu Yuanchao. A fast clustering algorithm for information retrieval[J]. Journal of Computer Research and Development, 2013, 50(7): 1452-1463 (in Chinese)(刘铭, 刘秉权, 刘远超. 面向信息检索的快速聚类算法[J]. 计算机研究与发展, 2013, 50(7): 1452-1463)

[4] Wong K C. A short survey on data clustering algorithms[C] //Proc of the 2nd Int Conf on Soft Computing and Machine Intelligence (ISCMI). Piscataway, NJ: IEEE, 2015: 64-68

[5] Xu Rui, Wunsch D. Survey of clustering algorithms[J]. IEEE Trans on Neural Networks, 2005, 16(3): 645-678

[6] Hall L O. Objective function-based clustering[J]. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2012, 2(4): 326-339

[7] Lindsten F, Ohlsson H, Ljung L. Just Relax and Come Clustering!: A Convexification ofk-means Clustering[M]. Linköping: Linköping University Electronic Press, 2011

[8] Hocking T D, Joulin A, Bach F, et al. Clusterpath an algorithm for clustering using convex fusion penalties[C] //Proc of the 28th Int Conf on Machine Learning. New York: ACM, 2011: 1

[9] Chi E C, Lange K. Splitting methods for convex clustering[J]. Journal of Computational and Graphical Statistics, 2015, 24(4): 994-1013

[10] Hallac D, Leskovec J, Boyd S. Network lasso: Clustering and optimization in large graphs[C] //Proc of the 21st ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2015: 387-396

[11] Wang Binhuan, Zhang Yilong, Sun Wei, et al. Sparse Convex Clustering[OL]. arXiv preprint arXiv: 1601.04586, 2016 [2016-05-01]. http: / /arxiv.org /abs /1601.04586

[12] Lu Canyi, Yan Shuicheng, Lin Zhouchen. Convex sparse spectral clustering: Single-view to multi-view[J]. IEEE Trans on Image Processing, 2016, 25(6): 2833-2843

[13] Chi E C, Allen G I, Baraniuk R G. Convex biclustering[J]. Biometrics, 2016, 73(1): 10-19

[14] Zhou Zhihua. Machine Learning[M]. Beijing: Tsing University Press, 2016: 293-312 (in Chinese)(周志华. 机器学习[M]. 北京: 清华大学出版社, 2016: 293-312 )

[15] Klein D, Kamvar S D, Manning C D. From instance-level constraints to space-level constraints: Making the most of prior knowledge in data clustering [R]. Stanford, CA: Stanford University InfoLab, 2002

[16] Wagstaff K, Cardie C, Rogers S, et al. Constrainedk-means clustering with background knowledge[C] //Proc of the 18th Int Conf on Machine Learning. New York: ACM, 2001: 577-584

[17] Wagstaff K, Cardie C. Clustering with instance-level constraints[C] //Proc of the 17th Int Conf on Machine Learning, New York: ACM, 2000: 1103-1110

[18] Fang Ling, Chen Songcan. Semi-supervised clustering learning combined with feature preferences[J]. Journal of Frontiers of Computer Science and Technology, 2015, 9(1): 105-111 (in Chinese)(方玲, 陈松灿. 结合特征偏好的半监督聚类学习[J]. 计算机科学与探索, 2015, 9(1): 105-111)

[19] Asafi S, Cohen-Or D. Constraints as features[C] //Proc of the 31st IEEE Conf on Computer Vision and Pattern Recognition (CVPR). Piscataway, NJ: IEEE, 2013: 1634-1641

[20] Lasek P, Lasek K. Relative constraints as features[C] //Proc of the 23rd Int Workshop on Concurrency, Specification and Programming. Berlin: Humboldt University, 2014: 121-125

[21] Tibshirani R, Saunders M, Rosset S, et al. Sparsity and smoothness via the fused lasso[J]. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 2005, 67(1): 91-108

[22] Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. Foundations and Trends®in Machine Learning, 2011, 3(1): 1-122

[23] Tseng P. Applications of a splitting algorithm to decomposition in convex programming and variational inequalities[J]. SIAM Journal on Control and Optimization, 1991, 29(1): 119-138

[24] Fisher D H. Knowledge acquisition via incremental conceptual clustering[J]. Machine Learning, 1987, 2(2): 139-172

[25] Lafon S, Lee A B. Diffusion maps and coarse-graining: A unified framework for dimensionality reduction, graph partitioning, and data set parameterization[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2006, 28(9): 1393-1403

[26] Wickelmaier F. An introduction to MDS[M]. Denmark: Aalborg University, 2003

[27] Von Luxburg U. A tutorial on spectral clustering[J]. Statistics and Computing, 2007, 17(4): 395-416

[28] Zelnik-Manor L, Perona P. Self-tuning spectral clustering[C] //Advances in Neural Information Processing System. Berlin: Springer, 2005: 1601-1608

[29] Lange T, Roth V, Braun M L, et al. Stability-based validation of clustering solutions[J]. Neural Computation, 2004, 16(6): 1299-1323

[30] Wang Junhui. Consistent selection of the number of clusters via crossvalidation[J]. Biometrika, 2010, 97(4): 893-904

[31] Fang Yixin, Wang Junhui. Selection of the number of clusters via the bootstrap method[J]. Computational Statistics and Data Analysis, 2012, 56(3): 468-477

[32] Parikh N, Boyd S. Proximal algorithms[J]. Foundations and Trends®in Optimization, 2014, 1(3): 127-239

[33] Donoho D L. De-noising by soft-thresholding[J]. IEEE Trans on Information Theory, 1995, 41(3): 613-627

[34] Al Shalabi L, Shaaban Z, Kasasbeh B. Data mining: A preprocessing engine[J]. Journal of Computer Science, 2006, 2(9): 735-739

[35] Hubert L, Arabie P. Comparing partitions[J]. Journal of Classification, 1985, 2(1): 193-218

[36] Asuncion A, Newman D. UCI machine learning repository[DB].

[37] Strehl A, Ghosh J. Cluster ensembles-a knowledge reuse framework for combining partitionings[C] //Proc of the 18th National Conf on Artificial Intelligence. New York: ACM, 2002: 93-99

ConvexClusteringCombinedwithWeakly-SupervisedInformation

Quan Zhenzhen and Chen Songcan

(CollegeofComputerScienceandTechnology,NanjingUniversityofAeronauticsandAstronautics,Nanjing211106)

Objective function-based clustering is a class of important clustering analysis techniques, of which almost all the algorithms are built by optimization of non-convex objective. Thus, these algorithms can hardly get global optimal solution and are sensitive to the provided initialization. Recently, convex clustering has been proposed by optimizing a convex objective function, not only does it overcome the insufficiency illustrated above, but it also obtains a relatively stable solution. It has been proven that clustering performance can be improved effectively by combining useful auxiliary information (typically must-links andor cannot-links) obtained from reality with the corresponding objective. To the best of our knowledge, all such semi-supervised objective function-based clustering algorithms are based on non-convex objective, semi-supervised convex clustering has not been proposed yet. Thus, we attempt to combine pairwise constraints with convex clustering. However, the existing methods usually make the original convex objectives lose their convexity, which add constraint penalty terms to the objective function. In order to deal with such problem, we introduce a novel semi-supervised convex clustering model by using the weakly-supervised information. In particular, the key idea is to change distance metric instead of adding constraint penalty terms to the objective function. As a result, the proposed method not only maintains the advantages of convex clustering, but also improves the performance of convex clustering.

objective function-based clustering; convex clustering; weakly-supervised information; constraints; distance metric; semi-supervised clustering

Quan Zhenzhen, born in 1991. Master candidate. Student member of CCF. Her main research interests include machine learning and pattern recognition.

Chen Songcan, born in 1962. Professor and PhD supervisor of pattern recognition and artificial intelligence. Senior member of CCF. His main research interests include pattern recognition, machine learning and neural computing.

2017-05-23；

：2017-06-19

国家自然科学基金项目(61672281) This work was supported by the National Natural Science Foundation of China (61672281).

陈松灿(s.chen@nuaa.edu.cn)

TP391.4