一種基于少量標簽的改進遷移模糊聚類

王躍，楊燕，王紅軍

(西南交通大學 信息科學與技術學院，四川 成都 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