復雜分布數據的半監督階段聚類*

張俊溪，吳曉軍，蔣江紅

1.西安航空學院 車輛工程學院，西安 710077 2.西北工業大學 自動化學院，西安 710047 3.陜西師范大學 計算機科學學院，西安 710062

復雜分布數據的半監督階段聚類*

張俊溪1+，吳曉軍2，蔣江紅3

1.西安航空學院 車輛工程學院，西安 710077 2.西北工業大學 自動化學院，西安 710047 3.陜西師范大學 計算機科學學院，西安 710062

ZHANG Junxi,WU Xiaojun,JIANG Jianghong.Semi-supervised clustering algorithm for complex distributed data.Journal of Frontiers of Computer Science and Technology,2016,10(7)：1003-1009.

半監督聚類是一種用先驗信息完善聚類過程的機器學習方法。通過將元胞自動機（cellular automata，CA）距離變換算法引入到半監督聚類過程中，采用平面距離變換算法將數據集劃分為若干子類，獲得聚類數和約束信息，并作為下一階段聚類的先驗信息。利用半監督K-means聚類算法對第一階段的聚類結果做進一步劃分，可以獲得完整的聚類中心和聚類數，并由此提出CA-K-means二階段聚類算法。采用3組人工數據集和3組標準UCI數據集進行對比仿真實驗，將CA-K-means二階段聚類算法與半監督K-means聚類算法、遺傳K-means聚類算法和單純的CA層次聚類算法進行對比，結果顯示，該算法對復雜分布數據的聚類準確率較高，聚類性能更加優良。

元胞自動機；半監督聚類；K-means聚類算法；CA-K-means二階段聚類；復雜分布

1　引言

聚類是數據挖掘領域最重要的技術之一，也是一種重要的數據分析方法。目前已經應用到模式識別、機器學習及圖像處理等多個領域[1]。聚類的任務是通過相似性度量矩陣找到樣本之間的相似程度，使得類內的相似度最大，類間的相似度最小，是一種典型的無監督聚類。半監督聚類則是通過將部分先驗知識加入到無監督聚類過程中以改善聚類特性[2-3]。由于半監督聚類結合了無監督聚類和監督聚類的特點，近年來在各個領域也成為研究熱點[4-5]。Basu等人提出一個基于K-means的半監督算法，將約束信息和距離信息引入作為監督信息[6]；Xing等人通過定義兩個樣本之間的距離，并構造優化函數，求解度量矩陣使得類內的樣本點距離較近，類間的樣本點距離較遠[7]；高瑩等人提出一種半監督K-means多關系數據聚類算法，在K-means聚類算法的基礎上擴展了初始聚類中心的選擇方法及相似性度量方法[8]；李巖波等人提出一種人工免疫半監督聚類，采用流行距離度量樣本間距，采用克隆選擇算法求得最優類心[9]。對半監督聚類改進的共同特點是加入不同的約束信息使得監督信息更加完善，以此提高聚類的效率，而K-means算法本身僅適用于凸狀數據的聚類，對于復雜的非凸數據集聚類效果較差，因此對于半監督聚類的改進需要更多地關注數據集的多樣性和算法的泛化性。

傳統的半監督聚類多針對常規數據集的分析，通過增加先驗知識提高收斂效率和收斂精度，但針對復雜分布數據的半監督聚類仍需進一步研究。復雜分布數據往往表現為復雜的非凸特性，需要注重其聚類形狀及空間、屬性的鄰接性以及數據分布密度等特性，傳統的聚類算法難以得出滿意的結果。為了提高聚類結果的準確率和效率，數據之間的關聯特性以及數據的多關系特性都需要進行有效的處理，或者通過多階段聚類[10]以得到滿意的聚類結果。本文針對復雜分布數據的特性，提出將元胞自動機距離變換算法應用于聚類過程，并將其得到的類別數和約束信息作為半監督K-means聚類算法的先驗知識，通過半監督K-means聚類對結果做進一步劃分，得到新的聚類中心。最后通過3組人工數據集和3組標準UCI數據集，分別從聚類性能和準確度兩個方面驗證了算法的性能。

2　元胞自動機距離變換算法

元胞自動機（cellular automata，CA），也稱細胞自動機，是一種時間、空間和狀態都離散，可用于模擬復雜系統時空演化過程的動力學模型[11]。采用元胞自動機距離變換算法模擬聚類過程可將元胞自動機描述為一個四元組A=(Ld,S,N,f)，其中Ld表示待聚類對象的維度是d時對應的網格空間；S表示待聚類對象中元胞在變換過程中的狀態；N表示待聚類對象的所有數據點（包含聚類中心點），即包含有n個不同元胞狀態的空間向量；f則表示中心元胞與鄰居元胞間的轉換規則，即按照預定的目標函數進行轉換的模型[11]。

CA模型由Von Neumann于20世紀中葉[12]提出,具有與傳統數學模型截然不同的建模思路，可以模擬生態、環境、自然災害等多種高度復雜的地理現象，具有模擬非線性復雜系統的突現、混沌、進化等特征，在地理研究領域取得了豐碩的研究成果。元胞自動機在柵格空間上的距離變換是一種空間擴散運動，其距離分為外距離變換、內距離變換和條件距離變換3種[13]。鄰居分為多種類型，常見的有一維鄰居、馮諾依曼鄰居和摩爾鄰居等。鑒于本文采用CA進行層次聚類時采用的為自下而上合并聚類，而摩爾鄰居能夠涵蓋聚類對象的全部鄰居信息，故本文采用摩爾鄰居。元胞自動機應用于聚類的研究已有學者進行了有效的嘗試[14-15]，元胞自動機并行計算以及易于向高維空間擴散的性能也成為其應用于聚類的極大優勢。

本文采用的摩爾鄰居將元胞的狀態定義為3種：原狀態、擴展狀態和空狀態。以待聚類對象的約束規則作為目標函數在離散的演化周期上進行擴散，一個周期后原狀態元胞經過擴展后如圖1所示。

Fig.1　Clustering result after one cycle圖1　一個周期后生成的聚類效果

3　CA-K-means二階段聚類

3.1CA層次聚類

假設聚類對象分布于w×h的d維柵格空間，w為空間的橫向長度，h為縱向長度，以二維空間為例，構造元胞自動機 A=(Ld,S,N,f)，其中元胞空間L={ci,j|0≤i≤w,0≤j≤h}，采用狀態為空的定值邊界[16]，Moore鄰居，設共有n個柵格，即n=w×h，則鄰居定義如式（1）：

其中，vix、viy表示鄰居元胞的行列坐標值；vox、voy表示中心元胞的行列坐標值，對于Moore型鄰居來說，維數為d時，鄰居個數為3d-1。

元胞狀態定義為：

其中，以S=0標記為元胞的空狀態；S>0標記為元胞的源狀態，其狀態記錄了當前元胞的索引；S<0標記為擴展狀態，其絕對值表明了擴展到該位置的源元胞索引，如式（3）所示：

元胞自動機根據以上規則進行演化，直到所有元胞合并為一個簇。

規則中元胞自動機的層次聚類情況如圖2（a）所示，原始對象為526個，初始狀態，，在時間和空間上進行演化迭代，迭代步長為t，經過98步，元胞狀態從初始狀態演化為，且，中心元胞和鄰居元胞狀態都不再發生改變，迭代過程如圖3所示。

待聚類對象從C=526經過98步演化為C=2，并且在相當長一段時間內不再發生變化，在t=98～ 150演化周期內C均未發生改變，表明C=2即為該樣本的最佳聚類簇。將兩類數據C1和C2作為標記數據，為第二階段聚類提供先驗信息。

Fig.2　State evolution of CA圖2　元胞自動機狀態演化示意圖

3.2K-means劃分聚類

經過第一階段的層次聚類后，獲得了基本先驗知識，將成對約束先驗信息加入到K-means聚類過程中。成對約束信息表述為樣本點之間的相似性，規定樣本之間為強相似性must-link和強差異性connotlink[18]。算法步驟如下：

（1）選擇C1和C2兩個簇中的任意兩個對象xo1和xo2作為初始聚類中心，并將這個初始聚類中心視為所在類別的所有樣本。

初始中心的計算：

其中，規定樣本個數為n，聚類簇為k,i=0,1,…,n,j=1,2,…,k。

（2）根據樣本的成對約束信息，以及每個聚類對象的均值計算這些對象與聚類中心的距離，并根據目標函數進行劃分。

目標函數仍然使用K-means算法的距離最短原則：

（3）計算目標函數，當滿足收斂條件時算法終止，否則轉第（2）步。

3.3算法復雜度分析

單純的合并層次聚類算法復雜度為O(N)，其中N為待聚類對象個數。單純的K-means算法復雜度為O(NKT)，其中N為待聚類對象個數，K為聚類類別數，T為迭代時間。將兩者合并為二階段聚類，那么算法復雜度有所增加，會達到O(N2KT)。對整體算法的時間復雜度來講，影響因素主要在于待聚類對象的規模以及進行二階段運算，由于二階段運算耗費時間，并且第二階段需要第一階段的先驗知識作為監督信息，故運算過程略有復雜化。

4　仿真實驗與結果對比

為了驗證算法的可行性，分別選用3組具有典型結構和分布特征的人工數據集和3組標準UCI數據集進行實驗，所有計算均在PC機上采用Visio Studio 6.0編譯環境，使用C語言編程實現。聚類結果通過圖形的方式顯示，并將聚類結果的準確率（correct rate，CR）作為評價算法有效性的主要指標。準確率CR定義為：

其中，ρ為正確聚類的對象個數；n為待聚類對象總數。

4.1人工數據集實驗結果

通過3組具有典型分布特征的人工數據集分析，分別采用半監督K-means聚類算法和本文提出的CA-K-means聚類算法進行運算比較，聚類結果如圖4所示。

圖4中相同顏色的樣本點被分為同一類中，人工數據集1為凸狀數據集，聚類結果較為理想，準確率CR約為95%，人工數據集2和3為非凸狀數據集，數據集2聚類的準確率CR約為50%，數據集3聚類的準確率約為30%。然后用本文提出的CA-K-means算法進行聚類，3組人工數據集的聚類結果如圖5所示，聚類的準確率CR均為100%。

K-means算法本身是基于劃分的聚類方法，對于非凸數據集聚類準確率低，且無法事先確定聚類數。本文提出的CA-K-means聚類算法能夠很好地解決非凸數據集的聚類問題，并能夠提供聚類數和類別的成對約束信息，通過二階段聚類較好地解決了數據集形狀的局限，同時聚類結果準確率較高。

Fig.4　Artificial datasets and K-means clustering results圖4　人工數據集及其K-means聚類結果

Fig.5　Clustering results of 3 artificial datasets by CA-K-means圖5　3組人工數據集經過CA-K-means算法聚類結果

4.2UCI數據集實驗結果

為了驗證算法的泛化性能，同時選取了3組標準UCI數據集進行相同的仿真實驗，具體數據集信息如表1所示。

分別采用K-means算法、遺傳K-means聚類算法、單純CA層次聚類算法和CA-K-means聚類算法進行運算比較，以本文定義的聚類準確率CR作為評判標準，得到3組UCI數據集的聚類準確率比較如表2所示。

Table 2　Comparison of CR for 3 UCI datasets表2　3組UCI數據集CR比較　%

由表2可以看出，單純K-means算法對3組數據集的聚類算法準確率均低于CA層次聚類和CA-K-means聚類，而CA層次聚類對Iris和Zoo的聚類準確率均低于CA-K-means聚類。

為了更充分地說明CA-K-means二階段聚類的優越特性，本文將3組UCI數據Iris、Wine和Zoo的聚類過程收斂特性進行了對比分析，分別采用半監督K-means聚類算法、遺傳K-means聚類算法、單純的CA聚類算法以及CA-K-means聚類算法進行聚類，采用3.2節定義的適應度函數值作為目標函數，3組曲線圖如圖6所示，橫坐標為迭代步數，縱坐標為適應度函數值。從3組收斂特性曲線可以看出，CA-K-means對3組數據的收斂效率均為最優，遺傳K-means優于半監督K-means聚類算法，而CA聚類的收斂特性則介于遺傳K-means和半監督K-means之間。這是因為遺傳K-means采用全局搜索，可以一定程度克服單純K-means容易獲得局部最優解的缺點。單純的CA聚類可以得出最終的聚類結果，但是收斂效率較低，計算復雜度高。

因此本文提出的元胞自動機距離變換與半監督K-means算法相結合的二階段聚類算法性能較為優良，聚類準確率高，收斂效率高，適用范圍較廣，對復雜分布數據的聚類效果尤其明顯。

Fig.6　Convergence curves of 3 UCI datasets圖6　3組UCI數據集的算法收斂特性對比圖

5　結論

本文通過引入元胞自動機距離變換算法，將CA層次聚類結果作為先驗信息為半監督K-means聚類算法提供約束信息，提出了一種基于約束和距離融合的半監督聚類算法——CA-K-means聚類算法。該算法分為兩個階段，第一階段用CA層次聚類獲得類別數和簇的標記信息，并將其作為第二階段聚類的先驗信息，通過在K-means聚類過程中加入約束信息得到了完整的聚類結果。最后通過多組具有不同分布特征的數據集聚類實驗，驗證了本文算法聚類準確率較高，尤其針對復雜分布數據聚類性能較好。

但是本文算法仍然有不足之處和需要改進的地方，如二階段聚類的時間復雜度問題及半監督聚類的約束信息簡化問題等。分階段聚類往往導致增加時間復雜度來優化聚類性能，同時約束信息過多導致聚類問題變成有監督分類，達不到預期效果，這些都是需要進一步研究的問題。

[1]Yuan Liyong,Wang Jiyi.An improved semi-supervised K-means clustering algorithm[J].Computer Engineering and Science,2011,33(6):138-143.

[2]Li Kunlun,Cao Zheng,Cao Liping,et al.Some developments on semi-supervised clustering[J].Pattern Recognition andArtificial Intelligence,2009,22(5):735-742.

[3]Zhao Weizhong,Ma Huifang,Li Zhiqing,et al.Efficiently active learning for semi-supervised document clustering[J]. Journal of Software,2015,23(6):1486-1497.

[4]Yin Xuesong,Hu Enliang,Chen Songcan.Discriminative semi-supervised clustering analysis with pairwise constraints [J].Journal of Software,2008,19(11):2791-2802.

[5]Tao Xinmin,Xu Jing,Yang Libiao.Improved cluster algorithm based on K-means and particle swarm optimization[J]. Journal of Electronics&Information Technology,2010,32 (1):92-97.

[6]Bilenko M,Basu S,Mooney R J.Integrating constraints and metric learning in semi-supervised clustering[C]//Proceedings of the 21st International Conference on Machine Learning, Banff,Canada,Jul 2004.New York,USA:ACM,2004:81-88.

[7]Xing E P,Ng A Y,Jordan M.Distance metric learning,with application to clustering with side information[C]//Proceedings of the 16th Annual Conference on Neural Information Processing Systems,Vancouver,Canada,Dec 8-13,2003.Cambridge,USA:MIT Press,2003:505-512.

[8]Gao Ying,Liu Dayou,Qi Hong,et al.Semi-supervised K-means clustering algorithm for multi-type relational data[J]. Journal of Software,2008,19(11):2814-2821.

[9]Li Yanbo,Song Qiong,Guo Xinchen.Artificial immune clustering semi-supervised algorithm based on manifold distance[J].Computer Science,2012,39(11):204-207.

[10]Gong Maoguo,Wang Shuang,Ma Meng,et al.Two-phase clustering algorithm for complex distributed data[J].Journal of Software,2011,22(11):2760-2770.

[11]Chen Shupeng.Urbanization and urban geographic information system[M].Beijing:Science Press,1999:171-197.

[12]Von Neumann J.Theory of self-reproducing automata[M]. Illinois,USA:University of Illinois Press,1966.

[13]Wen Kai.Research on evolution and computation with cellular automata[D].Nanjing:Nanjing University of Aeronautics andAstronautics,2008:6-12.

[14]Zhang Junxi,Xue Huifeng,Su Jinqi.Agglomerative clusteringalgorithm based on CA[J].Computer Engineering and Applications,2008,44(23):151-153.

[15]Liu Yong,Xu Qiuyan,Wang Honggang,et al.Intelligent optimizations algorithm for clustering analysis[J].Computer Engineering andApplications,2009,45(19):123-124.

[16]Zhou Chenghu,Sun Zhanli,Xie Yichun.Study of geographical elements of automaton[M].Beijing:Science Press,2001:23-36.

[17]Conway J.Game of life[J].Scientific American,1970,223: 120-123.

[18]Zhang Zhen,Wang Binqiang,Yi Peng.Semi-supervised affinity propagation clustering algorithm based on stratified combination[J].Journal of Electronics&Information Technology,2013,35(3):645-651.

附中文參考文獻：

[1]袁利永,王基一.一種改進的半監督K-means聚類算法[J].計算機工程與科學,2011,33(6):138-143.

[2]李昆侖,曹錚,曹麗蘋,等.半監督聚類的若干新進展[J].模式識別與人工智能,2009,22(5):735-742.

[3]趙衛中,馬慧芳,李志清,等.一種結合主動學習的半監督文檔聚類算法[J].軟件學報,2015,23(6):1486-1497.

[4]尹學松,胡恩良,陳松燦.基于成對約束的判別型半監督聚類分析[J].軟件學報,2008,19(11):2791-2802.

[5]陶新民,徐晶,楊立標.一種改進的粒子群和K均值混合聚類算法[J].電子與信息學報,2010,32(1):92-97.

[8]高瑩,劉大有,齊紅,等.一種半監督K均值多關系數據聚類算法[J].軟件學報,2008,19(11):2814-2821.

[9]李巖波,宋瓊,郭新辰.基于流形距離的人工免疫半監督聚類算法[J].計算機科學,2012,39(11):204-207.

[10]公茂果,王爽,馬萌,等.復雜分布數據的二階段聚類算法[J].軟件學報,2011,22(11):2760-2770.

[11]陳述彭.城市化與城市地理信息系統[M].北京:科學出版社,1999:171-197.

[13]聞凱.元胞自動機的進化與計算研究[D].南京:南京航空航天大學,2008:6-12.

[14]張俊溪,薛惠鋒,蘇錦旗.基于CA模型的凝固聚類算法[J].計算機工程與應用,2008,44(23):151-153.

[15]劉勇,許秋艷,王洪剛,等.智能優化算法在聚類分析中的應用[J].計算機工程與應用,2009,45(19):123-124.

[16]周成虎,孫戰利,謝一春.地理元胞自動機研究[M].北京:科學出版社,2001:23-36.

[18]張震,汪斌強,伊鵬.一種分層組合的半監督近鄰傳播聚類算法[J].電子與信息學,2013,35(3):645-651.

ZHANG Junxi was born in 1983.She received the M.S.degree in automation from Northwestern Polytechnical University in 2009.Now she is a lecturer at Xi?an Aeronautical University.Her research interests include pattern recognition and artificial intelligence,etc.

張俊溪（1983—），女，河南新鄉人，2009年于西北工業大學獲得碩士學位，現為西安航空學院講師，主要研究領域為模式識別，人工智能等。

WU Xiaojun was born in 1970.He received the Ph.D.degree in automation from Northwestern Polytechnical University.Now he is a professor and Ph.D.supervisor at Northwestern Polytechnical University and Shaanxi Normal University,and the senior member of CCF.His research interests include machine learning and complex system,etc.

吳曉軍（1970—），男，陜西鳳翔人，博士，西北工業大學、陜西師范大學教授、博士生導師，CCF高級會員，主要研究領域為機器學習，復雜系統等。

JIANG Jianghong was born in 1990.He is an M.S candidate at Shaanxi Normal University.His research interests include machine learning and data mining,etc.

蔣江紅（1990—），陜西師范大學計算機科學學院碩士研究生，主要研究領域為機器學習，數據挖掘等。

Semi-supervised ClusteringAlgorithm for Complex Distributed Data?

ZHANG Junxi1+,WU Xiaojun2,JIANG Jianghong3
1.College of Vehicle Engineering,Xi’anAeronautical University,Xi’an 710077,China 2.College ofAutomation,Northwestern Polytechnical University,Xi’an 710047,China 3.School of Computer Science,Shaanxi Normal University,Xi’an 710062,China +Corresponding author:E-mail:zhang_junxi@126.com

Semi-supervised clustering algorithm is a machine learning method which uses the priori information to improve the clustering process.Cellular automata(CA)distance transform algorithm is induced into the process of semi-supervised clustering.The dataset is divided into several clusters by distance transform of cellular automata, and then the number of clusters and the constraint information are obtained,which can be used as priori information of the next phase of clustering.In the second phase of clustering,the semi-supervised K-means clustering algorithm is used to further divide the results of the first phase and the final clustering results are got.Based on that,this paper proposes the CA-K-means clustering algorithm.By comparing the proposed algorithm with K-means algorithm,GAK-means and pure CA clustering algorithm,the experimental results on three artificial data sets and three UCI data sets with different structures show that the novel algorithm has higher clustering accuracy for complex distributed data and more optimal clustering feature.

cellular automata;semi-supervised clustering algorithm;K-means clustering algorithm;CA-K-meanstwo phases clustering algorithm;complex distribution

2015-07,Accepted 2015-10.

10.3778/j.issn.1673-9418.1507102

A

TP181

*The Natural Science Foundation of Shaanxi Province under Grant No.2014JM8353(陜西省自然科學基金).

CNKI網絡優先出版:2015-10-28,http://www.cnki.net/kcms/detail/11.5602.TP.20151028.1045.004.html