一种基于少量标签的改进迁移模糊聚类

王跃，杨燕，王红军

(西南交通大学 信息科学与技术学院，四川 成都 610031)



一种基于少量标签的改进迁移模糊聚类

王跃，杨燕，王红军

(西南交通大学 信息科学与技术学院，四川 成都 610031)

摘要：传统聚类算法难以利用已有的历史信息，尤其是数据被污染的情况下聚类结果不理想；半监督聚类常用于数据中有部分标签的情况。在源数据有少量标签的情况下，提出半监督混合C均值聚类算法(SS-FPCM)；基于迁移学习框架，针对负迁移问题对算法进行修正，提出了防止负迁移的半监督迁移算法(TSS-FPCM)；最后，为了充分借鉴源数据的信息，利用“代表点”来代替源数据类信息，融入算法中再次迁移得到改善的半监督迁移算法(ITSS-FPCM)。实验表明，3个算法能够有效的利用源数据提高聚类性能。SS-FPCM与TSS-FPCM可以利用源数据的少量标签数据，而ITSS-FPCM算法结合了标签数据与“代表点”两个有效信息，在数据信息匮乏、数据被污染的情况下得到较好的聚类结果。

关键词：聚类；迁移学习；半监督；可能性C均值；模糊C均值

传统的聚类算法在拥有大量数据的情况下能够在不同的场景下发挥各自的作用，当数据匮乏、噪声污染的情况，传统的聚类算法存在着不足。

近年来，迁移学习的成果逐渐丰富，研究表明，迁移学习能够有效地解决数据量不足、数据受污染和信息丢失等问题。文献[1]根据迁移学习中源领域和目标领域中是否含有标签，可以将迁移学习划分为3类：归纳迁移学习、直推式迁移学习和无监督迁移学习。现有的迁移学习在分类领域已有较多研究成果[2-10]，而在聚类领域迁移学习理论和方法相对则要少很多。文献[11-12]在聚类领域利用了迁移学习的理论。

半监督聚类是半监督学习与聚类分析相结合的研究领域，文献[13]提出了不同情况下的半监督聚类算法，并取得了不错的效果。

文献[14]将经典的模糊C均值算法[15](FCM)与可能性C均值[16](PCM)算法进行改进，提出了模糊可能性聚类算法(FPCM)。本文探讨在源领域有少量标签的情况下，如何指导目标域进行聚类，提出半监督模糊可能性C均值聚类算法(SS-FPCM)，并针对负迁移问题对算法进行改进，提出了防止负迁移的半监督迁移算法(TSS-FPCM)，同时，用代表点代替源领域的数据进行数据迁移，得到改善的半监督迁移算法(ITSS-FPCM)，并进行了实验验证。

1相关算法介绍

1.1PCM聚类算法

(1)

(2)

(3)

最小化目标函数可以得到可能性矩阵和聚类中心的迭代式(4)和式(5):

(4)

(5)

1.2PFCM聚类算法

FPCM是建立在FCM和PCM基础上的算法，它将两者结合在一起 ，FPCM的目标函数定义为

(6)

式中：m>1,η>1,0≤ik,tik≤1，约束条件为

(7)

(8)

通过最小化目标函数，可以得到以下迭代优化公式：

(9)

(10)

(11)

1.3半监督聚类算法

对于一些有着一部分标签的数据集，在文献[17]中，Pedrycz提出了基于部分标签的模糊聚类算法(SS-FCM)，算法的核心思想是利用现有的分类信息，并把它作为优化程序的一部分。

(12)

2半监督迁移模糊聚类算法

2.1半监督模糊可能性C均值聚类算法

对半监督FCM算法进行研究可以发现，上文中的B和F的功能相似，保留下F并对FPCM的目标函数做如下改进：

(13)

最小化目标函数，可以得到迭代表达式：

(14)

(15)

(16)

通过不断迭代优化隶属度矩阵最终获得我们需要的划分。改进的半监督模糊可能性C均值算法(SS-FPCM)能够通过α、β控制FPCM中FCM和PCM的权重，通过参数ω的变化控制已知标签在算法中所占的比重。

2.2历史标签数据的迁移

迁移学习可以将历史场景(也叫源数据)中获取需要的数据或者信息，用于指导当前场景(又成为目标数据)，当历史场景的信息与当前场景的相关性足够大时，可以从中得到潜藏的信息。在当历史场景没有任何指导信的数据(无任何标签信息)时，文献[11-12]针对这种情况分别做出了自己的研究。

当源数据有少量的标签时候，可以很直观地想到，将这些数据提取出来，加入到当前场景，一起进行聚类，以期待能够指导当前场景。前面提到了半监督FPCM聚类算法能够有效利用标签进行聚类，便可以直接引用式(13)的目标函数。但是，在迁移学习中负迁移是难以避免的一个问题，如果历史场景与当前场景相关性并不大。那么历史数据的标签很可能对当前场景产生不良影响，造成负迁移现象。针对这个问题，对式(13)进行改造，提出避免负迁移的半监督迁移聚类算法(TSS-FPCM)。

(17)

不直接使用式(13)的目标函数而改用式(17)的目标函数，当参数ω趋于0的时候，前者相当于将M个源数据当作未知标签加入到目标领域中进行无监督混合C均值聚类，而后者则等于认为这些数据没有用处而舍弃。可以发现前者无法控制加入源数据后所可能造成的负迁移现象影响聚类结果，而后者则可以有效避免该情况。

最小化目标函数可以得到：

(18)

(19)

(20)

2.3改进的半监督迁移算法

在历史场景中，除了少量的标签信息，还有大量的未标记数据，这些数据量远远大于已标记数据，同样可以从中获取需要的信息来帮助当前场景。直接将大量未标记数据加入当前场景中进行聚类大大增加了计算量。

在历史场景中，为了减少计算量，可以使用一个“代表点”来表示一个类，而不仅仅是文献[11]中的聚类中心；这个点既可以是聚类中心，也可以是数据中的真实样本点，将庞大的数据变为有限的几个点。

(21)

式中γ1和γ2为权重因子，用于调节历史中心的重要程度，将代表点作为有效信息迁移到当前场景中来。新的目标函数如式(22)：

式中：α≥0，β≥0，ω>0， 0≤uik,tik≤1，

(23)

式中λk与θi为Lagrange乘子。

令∂Q/∂Vi=0,解得：

(24)

令∂Q/∂λk=0,可以得到：

(25)

令∂Q/∂uik=0，对于0

(26)

将式(26)代入式(25)，解得：

(27)

再将λ代回式(26)，得到：

(28)

同理，对于N

(29)

合并式(28)和(29)可以得到最终表达式：

(30)

使用同样得方法，可以求得tik的迭代表达式：

(31)

2.4改进的半监督迁移算法描述

根据上一节的公式，ITSS-FPCM的表述如下： 算法1ITSS-FPCM算法

输出聚类中心vi，隶属度矩阵uik和概率矩阵tik。

1)初始化聚类中心vi，根据已知标签构造矩阵F，初始化目标函数J(l)=0。

2)根据表达式(30)更新vik。

3)根据表达式(31)更新vik。

4)根据表达式(24)更新vi。

5)l=l+1，计算新的目标函数J(l)，如果J(l)-J(l-1)<ε，或者l>L跳到第6)，否则，跳到2)。

6)聚类中心vi，隶属度矩阵vik和概率矩阵vik。

3实验结果

为了验证算法的有效性，实验使用了人工数据集、UCI真实数据集以及文本数据集进行相关的实验验证。

在进行聚类结果评价时，选取了相关的4种聚类评价指标：正确率AC(Accuracy)[18]、归一化互信息NMI(normalized mutual information)[11,18]、芮氏指标RI(Rand Index)[11,19]和F-measure[19]。 4个指标的值域均在0到1，值越大表示聚类质量越好。

实验中选取了LSSMTC[18]、Co-Clustering[20]、FPCM、TSC[12]、T-GIFP-FCM[11]算法进行对比实实验；评价结果将进行10次计算取平均值。

3.1人工数据集

为了模拟源场景和当前目标场景，实验使用文献[11]的方法：首先利用高斯函数生成相关的数据集，随机生成类别数为3，每类250个样本点，每个样本点为两微的源场景数据，如图1所示。

图1　源数据Fig.1　Source Dataset

如图2所示，同样利用高斯分布函数产生当前数据集Set1和Set2 两个数据集；其中Set1每类样本数目为20，如图2(a)所示；Set2每类样本数目为100，再向其中加入高斯噪声构成，如图2(b)所示。

(a)数据集 Set1

(b)数据集Set2图2　目标数据集Fig.2　Target dataset

两个数据集分别模拟当前的数据样本信息匮乏(数据不足)、充足(数据足够)但是受污染(有噪声)的不同情况下进行聚类。

实验时，SS-FPCM,TSS-FPCM,ITSS-FPCM算法需要已知部分源标签，随机从源数据中抽取3%的样本作为已知标签数据进行实验，实验结果如表1所示，表格中“—”表示该数据集不满足算法运行的基本条件。

表1　8个算法在人工数据集的对比

从表1可以看出:

1)在Set1数据集中样本量很少，少量的源标签数据样本和其他信息都能够对目标数据产生正向的推动作用，从而达到较好的结果，SS-FPCM与TSS-FPCM的结果验证了这一点；T-GITP-FCM算法也可以得到很好的结果；

2)在有噪声的数据集Set2上，少量的标签不足以取得令人满意的效果，仍需要源数据的其他帮助，SS-FPCM与TSS-FPCM算法的结果不如T-GIFP-FCM算法；说明SS-FPCM与TSS-FPCM算法在抗干扰方面存在不足；

3)改进后的ITSS-FPCM算法则在Set1和Set2上均取得了良好的聚类效果。说明当在数据信息不足，数据样本有限，数据受污染的时候，在有大量历史数据的帮助下迁移算法可以取得不错的效果，改进的ITSS-FPCM算法在抗噪声和干扰方面优于其他算法。

3.2UCI真实数据集

UCI中的Image Segment Data Set是一个图片数据集，它由7个室外图像数据库中随机抽取，组成7个不同的类别，共2 100个样本数据，其中每个类别含有300个样本点。 实验从数据中抽取70%的数据作为源数据，剩下的构成目标数据进行实验，数据构成如表2。

表2　Image Segment数据集构成情况

算法在数据集的聚类结果如图3所示，从图中可以发现本文所提出的ITSS-FPCM算法在4个指标均取得了不错的结果，在准确率与NMI指标上有相对较大的优势，进一步验证了算法得有效性。

图3　8个算法在Image Segment数据集上的对比Fig.3　Comparison of 8 algorithms on image segment data set

3.3文本真实数据集

20NG(20Newsgroups)[12]是一个真实的新闻文本数据集，数据集收集了大约2万条新闻组，均匀地分布到20个不同的集合中，20个小集合又可以分为4个大的类别，该数据集在大量迁移学习分类算法中被使用。

TDT2[21](NIST话题检测与跟踪的语料库)共收集1998年上半年6个来源的数据，包含2个通讯社(APW，NYT)，2个电台节目(VOA,PRI)和2个电视节目(CNN,ABC)，共1万多个样本数据。

Reuters-21578[21]语料库包含21 578个文件，放在135个文件夹下。

实验时分别对3个文本数据集抽取其中一部分类别，利用工具进行降维处理后构成新的数据集样本，数据具体构成如表3所示。

表3　数据集构成情况

聚类的结果如表4所示，结果中可以看到：

1) 利用迁移学习的TSC、T-GIFP-FCM、TSS-FCM、ITSS-FCM算法在效果上均优于非迁移学习型算法，表明迁移学习能够有效地提升聚类的性能；

2)仅对源数据少量标签数据直接使用的SS-FPCM算法和TSS-FPCM算法对当前场景的作用有限，不及能够利用更多信息的TSC迁移聚类和T-GIFP-FCM算法，但还是能够有效地提高聚类性能；

3) 本论文的ITSS-FPCM算法在大部分指标都优于其他算法，但是当源数据与目标数据相关性不大时，基于标签与代表点的直接迁移对当前场景帮助有限，不及STC算法的聚类效果，存在着局限性和适用范围的问题。

表4　8个算法在人工数据集的对比

4结束语

本文将半监督学习思想应用到FPCM算法上，提出半监督SS-FPCM算法；迁移学习方面对算法进行非负迁移改进，得到TSS-FPCM算法，再利用“代表点”代替原始数据提出了改进的半监督的迁移聚类算法ITSS-FPCM。在多种数据集上的实验验证表明，ITSS-FPCM算法在性能上要好于SS-FPCM算法与TSS-FPCM算法。在数据量不足、数据被污染的情况下，ITSS-FPCM算法能够提升聚类的性能；算法在源数据与目标数据相关不大时效果一般，下一步研究将会提取其他相关信息改善聚类性能，同时考虑参数的优化问题。

参考文献:

[1]庄福振, 罗平, 何清, 等. 迁移学习研究进展[J]. 软件学报, 2015, 26(1): 26-39.

ZHUANG Fuzhen, LUO Ping, HE Qing, et al. Survey on transfer learning research[J]. Journal of software, 2015, 26(1): 26-39.

[2]WEI Fengmei, ZHANG Jianpei, CHU Yan, et al. FSFP: transfer learning from long texts to the short[J]. Applied mathematics and information sciences, 2014, 8(4): 2033-2040.

[3]DAI Wenyuan, XUE Guirong, YANG Qiang, et al. Co-clustering based classification for out-of-domain documents[C]//Proceedings of the 13th ACM SIGKDD Tinternational Conference on Knowledge Discovery and Data Mining. San Jose, California, USA, 2007: 210-219.

[4]DAI Wenyuan, YANG Qiang, XUE Guirong, et al. Self-taught clustering[C]//Proceedings of the 25th International Conference on Machine Learning. Helsinki, Finland,, 2008: 200-207.

[5]SAMANTA S, SELVAN A T, DAS S. Cross-domain clustering performed by transfer of knowledge across domains[C]//Proceedings of the 4th National Conference on Pattern Recognition, Image Processing and Graphics (NCVPRIPG). Jodhpur, India, 2013: 1-4.

[6]DAI Wenyuan, XUE Guirong, YANG Qiang, et al. Transferring naive Bayes classifiers for text classification[C]//Proceedings of the 22nd National Conference on Artificial Intelligence. Vancourver, British Columbia, Canada, 2007, 1: 540-545.

[7]LIAO Xuejun, XUE Ya, CARIN L. Logistic regression with an auxiliary data source[C]//Proceedings of the 22nd International Conference on Machine Learning. New York, NY, USA, 2005: 505-512.

[8]DAI Wenyuan, YANG Qiang, XUE Guirong, et al. Boosting for transfer learning[C]//Proceedings of the 24th International Conference on Machine Learning. Corvallis, Oregon, USA, 2007: 193-200.

[9]LUO Ping, ZHUANG Fuzhen, XIONG Hui, et al. Transfer learning from multiple source domains via consensus regularization[C]//Proceedings of the 17th ACM Conference on Information and Knowledge Management. Napa Valley, California, USA, 2008: 103-112.

[10]DUAN Lixin, TSANG I W, XU Dong, et al. Domain adaptation from multiple sources via auxiliary classifiers[C]//Proceedings of the 26th Annual International Conference on Machine Learning. Montreal, Canada,, 2009: 289-296.

[11]蒋亦樟, 邓赵红, 王骏, 等. 基于知识利用的迁移学习一般化增强模糊划分聚类算法[J]. 模式识别与人工智能, 2013, 26(10): 975-984.

JIANG Yizhang, DENG Zhaohong, WANG Jun, et al. Transfer generalized fuzzy c-means clustering algorithm with improved fuzzy partitions by leveraging knowledge[J]. Pattern recognition and artificial intelligence, 2013, 26(10): 975-984.

[12]JIANG Wenhao, CHUNG F L. Transfer spectral clustering[M]//FLACH P A, DE BIE T, CRISTIANINI N. Machine learning and knowledge discovery in databases: lecture notes in computer science. Berlin Heidelberg: Springer, 2012, 7524: 789-803.

[13]李昆仑, 曹铮, 曹丽苹, 等. 半监督聚类的若干新进展[J]. 模式识别与人工智能, 2009, 22(5): 735-742. LI Kunlun, CAO Zheng, CAO Liping, et al. Some developments on semi-supervised clustering[J]. Pattern recognition and artificial intelligence, 2009, 22(5): 735-742.

[14]PAL N R, PAL K, BEZDEK J C. A mixed c-means clustering model[C]//Proceedings of the 6th IEEE International Conference on Fuzzy Systems. Barcelona, Spain, 1997, 1: 11-21.

[15]BEZDEK J C, EHRLICH R, FULL W. FCM: The fuzzy c-means clustering algorithm[J]. Computers and geosciences, 1984, 10(2-3): 191-203.

[16]KRISHNAPURAM R, KELLER J M. The possibilistic C-means algorithm: insights and recommendations[J]. IEEE transactions on fuzzy systems, 1996, 4(3): 385-393.

[17]PEDRYCZ W. Algorithms of fuzzy clustering with partial supervision[J]. Pattern recognition letters, 1985, 3(1): 13-20.

[18]GU Quanquan, ZHOU Jie. Learning the shared subspace for multi-task clustering and transductive transfer classification[C]//Proceedings of the 2009 9th IEEE international conference on data mining. Miami, Florida, USA, 2009: 159-168.

[19]杨燕, 靳蕃, KAME M. 聚类有效性评价综述[J]. 计算机应用研究, 2008, 25(6): 1630-1632, 1638.

YANG Yan, JIN Fan, KAME M. Survey of clustering validity evaluation[J]. Application research of computers, 2008, 25(6): 1630-1632, 1638.

[20]GU Quanquan, ZHOU Jie. Co-clustering on manifolds[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Paris, France, 2009: 359-368.

[21]CAI Deng, HE Xiaofei, HAN Jiawei. Locally consistent concept factorization for document clustering[J]. IEEE transactions on knowledge and data engineering, 2011, 23(6): 902-913.

王跃，男，1990年生，硕士研究生，主要研究方向为数据挖掘、计算智能。

杨燕，女，1964年生，教授，博士生导师，主要研究方向为计算智能、数据挖掘、集成学习。主持国家自然科学基金项目3项，国家科技支撑计划项目1项，发表学术论文130余篇。

王红军，男，1977年生，副研究员，主要研究方向为机器学习、深度学习、半监督学习。主持完成国家自然科学青年基金项目1项，主持国家自然科学基金项目2项，发表学术论文30余篇。

中文引用格式：王跃，杨燕，王红军.一种基于少量标签的改进迁移模糊聚类[J]. 智能系统学报， 2016, 11(3): 310-317.

英文引用格式：WANG Yue， YANG Yan， WANG Hongjun.An improved transfer fuzzy clustering with few labels[J]. CAAI transactions on intelligent systems, 2016,11(3): 310-317.

An improved transfer fuzzy clustering with few labels

WANG Yue， YANG Yan， WANG Hongjun

(School of Information Science and Technology, Southwest Jiaotong University， Chengdu 610031， China)

Abstract：In the traditional clustering algorithm, it is difficult to utilize existing historical information, which tends to be less effective in cases in which the data is contaminated. The semi-supervised clustering algorithm is often used in such circumstances, wherein the target data has some labeled examples. For situations in which the source data has partially labeled samples, in this paper, we propose a semi-supervised fuzzy possibilistic C-means algorithm (SS-FPCM). Based on the transfer learning framework, we use a transfer semi-supervised fuzzy possibilistic C-means algorithm (TSS-FPCM) to avoid the negative transfer learning problem. Finally, in order to make full use of source data information, we use representative points to replace the source data class. Thus, we have developed an improved transfer semi-supervised fuzzy possibilistic C-means algorithm (ITSS-FPCM). The experimental results demonstrate that these three algorithms may be used to improve the clustering performance by using source data effectively, as compared with other clustering algorithms. Moreover, the SS-FPCM and TSS-FPCM algorithms exploit partially labeled data from the source, while the ITSS-FPCM algorithm combines the labeled data and "representative points," for cases having insufficient data information or contaminated data, and an excellent clustering result is attained.

Keywords：clustering; transfer learning; semi-supervised; possibilistic C-means; fuzzy C-means

作者简介：

中图分类号：TP301

文献标志码：A

文章编号：1673-4785(2016)03-0310-08

通信作者：杨燕. E-mail： yyang@swjtu.edu.cn.

基金项目：国家自然科学基金项目(61170111, 61572407, 61134002);四川省科技支撑计划项目(2014SZ0207).

收稿日期：2016-03-19.网络出版日期：2016-05-13.

DOI:10.11992/tis.201603046

网络出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20160513.0957.034.html