張俊溪，吳曉軍，蔣江紅

1.西安航空學(xué)院 車輛工程學(xué)院，西安 710077 2.西北工業(yè)大學(xué) 自動(dòng)化學(xué)院，西安 710047 3.陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，西安 710062

復(fù)雜分布數(shù)據(jù)的半監(jiān)督階段聚類*

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

1.西安航空學(xué)院 車輛工程學(xué)院，西安 710077 2.西北工業(yè)大學(xué) 自動(dòng)化學(xué)院，西安 710047 3.陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，西安 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.

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

元胞自動(dòng)機(jī)；半監(jiān)督聚類；K-means聚類算法；CA-K-means二階段聚類；復(fù)雜分布

1　引言

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

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

2　元胞自動(dòng)機(jī)距離變換算法

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

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

本文采用的摩爾鄰居將元胞的狀態(tài)定義為3種：原狀態(tài)、擴(kuò)展?fàn)顟B(tài)和空狀態(tài)。以待聚類對(duì)象的約束規(guī)則作為目標(biāo)函數(shù)在離散的演化周期上進(jìn)行擴(kuò)散，一個(gè)周期后原狀態(tài)元胞經(jīng)過(guò)擴(kuò)展后如圖1所示。

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

3　CA-K-means二階段聚類

3.1CA層次聚類

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

其中，vix、viy表示鄰居元胞的行列坐標(biāo)值；vox、voy表示中心元胞的行列坐標(biāo)值，對(duì)于Moore型鄰居來(lái)說(shuō)，維數(shù)為d時(shí)，鄰居個(gè)數(shù)為3d-1。

元胞狀態(tài)定義為：

其中，以S=0標(biāo)記為元胞的空狀態(tài)；S>0標(biāo)記為元胞的源狀態(tài)，其狀態(tài)記錄了當(dāng)前元胞的索引；S<0標(biāo)記為擴(kuò)展?fàn)顟B(tài)，其絕對(duì)值表明了擴(kuò)展到該位置的源元胞索引，如式（3）所示：

元胞自動(dòng)機(jī)根據(jù)以上規(guī)則進(jìn)行演化，直到所有元胞合并為一個(gè)簇。

規(guī)則中元胞自動(dòng)機(jī)的層次聚類情況如圖2（a）所示，原始對(duì)象為526個(gè)，初始狀態(tài)，，在時(shí)間和空間上進(jìn)行演化迭代，迭代步長(zhǎng)為t，經(jīng)過(guò)98步，元胞狀態(tài)從初始狀態(tài)演化為，且，中心元胞和鄰居元胞狀態(tài)都不再發(fā)生改變，迭代過(guò)程如圖3所示。

待聚類對(duì)象從C=526經(jīng)過(guò)98步演化為C=2，并且在相當(dāng)長(zhǎng)一段時(shí)間內(nèi)不再發(fā)生變化，在t=98～ 150演化周期內(nèi)C均未發(fā)生改變，表明C=2即為該樣本的最佳聚類簇。將兩類數(shù)據(jù)C1和C2作為標(biāo)記數(shù)據(jù)，為第二階段聚類提供先驗(yàn)信息。

Fig.2　State evolution of CA圖2　元胞自動(dòng)機(jī)狀態(tài)演化示意圖

3.2K-means劃分聚類

經(jīng)過(guò)第一階段的層次聚類后，獲得了基本先驗(yàn)知識(shí)，將成對(duì)約束先驗(yàn)信息加入到K-means聚類過(guò)程中。成對(duì)約束信息表述為樣本點(diǎn)之間的相似性，規(guī)定樣本之間為強(qiáng)相似性must-link和強(qiáng)差異性connotlink[18]。算法步驟如下：

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

初始中心的計(jì)算：

其中，規(guī)定樣本個(gè)數(shù)為n，聚類簇為k,i=0,1,…,n,j=1,2,…,k。

（2）根據(jù)樣本的成對(duì)約束信息，以及每個(gè)聚類對(duì)象的均值計(jì)算這些對(duì)象與聚類中心的距離，并根據(jù)目標(biāo)函數(shù)進(jìn)行劃分。

目標(biāo)函數(shù)仍然使用K-means算法的距離最短原則：

（3）計(jì)算目標(biāo)函數(shù)，當(dāng)滿足收斂條件時(shí)算法終止，否則轉(zhuǎn)第（2）步。

3.3算法復(fù)雜度分析

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

4　仿真實(shí)驗(yàn)與結(jié)果對(duì)比

為了驗(yàn)證算法的可行性，分別選用3組具有典型結(jié)構(gòu)和分布特征的人工數(shù)據(jù)集和3組標(biāo)準(zhǔn)UCI數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，所有計(jì)算均在PC機(jī)上采用Visio Studio 6.0編譯環(huán)境，使用C語(yǔ)言編程實(shí)現(xiàn)。聚類結(jié)果通過(guò)圖形的方式顯示，并將聚類結(jié)果的準(zhǔn)確率（correct rate，CR）作為評(píng)價(jià)算法有效性的主要指標(biāo)。準(zhǔn)確率CR定義為：

其中，ρ為正確聚類的對(duì)象個(gè)數(shù)；n為待聚類對(duì)象總數(shù)。

4.1人工數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

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

圖4中相同顏色的樣本點(diǎn)被分為同一類中，人工數(shù)據(jù)集1為凸?fàn)顢?shù)據(jù)集，聚類結(jié)果較為理想，準(zhǔn)確率CR約為95%，人工數(shù)據(jù)集2和3為非凸?fàn)顢?shù)據(jù)集，數(shù)據(jù)集2聚類的準(zhǔn)確率CR約為50%，數(shù)據(jù)集3聚類的準(zhǔn)確率約為30%。然后用本文提出的CA-K-means算法進(jìn)行聚類，3組人工數(shù)據(jù)集的聚類結(jié)果如圖5所示，聚類的準(zhǔn)確率CR均為100%。

K-means算法本身是基于劃分的聚類方法，對(duì)于非凸數(shù)據(jù)集聚類準(zhǔn)確率低，且無(wú)法事先確定聚類數(shù)。本文提出的CA-K-means聚類算法能夠很好地解決非凸數(shù)據(jù)集的聚類問(wèn)題，并能夠提供聚類數(shù)和類別的成對(duì)約束信息，通過(guò)二階段聚類較好地解決了數(shù)據(jù)集形狀的局限，同時(shí)聚類結(jié)果準(zhǔn)確率較高。

Fig.4　Artificial datasets and K-means clustering results圖4　人工數(shù)據(jù)集及其K-means聚類結(jié)果

Fig.5　Clustering results of 3 artificial datasets by CA-K-means圖5　3組人工數(shù)據(jù)集經(jīng)過(guò)CA-K-means算法聚類結(jié)果

4.2UCI數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

為了驗(yàn)證算法的泛化性能，同時(shí)選取了3組標(biāo)準(zhǔn)UCI數(shù)據(jù)集進(jìn)行相同的仿真實(shí)驗(yàn)，具體數(shù)據(jù)集信息如表1所示。

分別采用K-means算法、遺傳K-means聚類算法、單純CA層次聚類算法和CA-K-means聚類算法進(jìn)行運(yùn)算比較，以本文定義的聚類準(zhǔn)確率CR作為評(píng)判標(biāo)準(zhǔn)，得到3組UCI數(shù)據(jù)集的聚類準(zhǔn)確率比較如表2所示。

Table 2　Comparison of CR for 3 UCI datasets表2　3組UCI數(shù)據(jù)集CR比較　%

由表2可以看出，單純K-means算法對(duì)3組數(shù)據(jù)集的聚類算法準(zhǔn)確率均低于CA層次聚類和CA-K-means聚類，而CA層次聚類對(duì)Iris和Zoo的聚類準(zhǔn)確率均低于CA-K-means聚類。

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

因此本文提出的元胞自動(dòng)機(jī)距離變換與半監(jiān)督K-means算法相結(jié)合的二階段聚類算法性能較為優(yōu)良，聚類準(zhǔn)確率高，收斂效率高，適用范圍較廣，對(duì)復(fù)雜分布數(shù)據(jù)的聚類效果尤其明顯。

Fig.6　Convergence curves of 3 UCI datasets圖6　3組UCI數(shù)據(jù)集的算法收斂特性對(duì)比圖

5　結(jié)論

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

但是本文算法仍然有不足之處和需要改進(jìn)的地方，如二階段聚類的時(shí)間復(fù)雜度問(wèn)題及半監(jiān)督聚類的約束信息簡(jiǎn)化問(wèn)題等。分階段聚類往往導(dǎo)致增加時(shí)間復(fù)雜度來(lái)優(yōu)化聚類性能，同時(shí)約束信息過(guò)多導(dǎo)致聚類問(wèn)題變成有監(jiān)督分類，達(dá)不到預(yù)期效果，這些都是需要進(jìn)一步研究的問(wèn)題。

[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.

附中文參考文獻(xiàn)：

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

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

[3]趙衛(wèi)中,馬慧芳,李志清,等.一種結(jié)合主動(dòng)學(xué)習(xí)的半監(jiān)督文檔聚類算法[J].軟件學(xué)報(bào),2015,23(6):1486-1497.

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

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

[8]高瑩,劉大有,齊紅,等.一種半監(jiān)督K均值多關(guān)系數(shù)據(jù)聚類算法[J].軟件學(xué)報(bào),2008,19(11):2814-2821.

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

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

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

[13]聞凱.元胞自動(dòng)機(jī)的進(jìn)化與計(jì)算研究[D].南京:南京航空航天大學(xué),2008:6-12.

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

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

[16]周成虎,孫戰(zhàn)利,謝一春.地理元胞自動(dòng)機(jī)研究[M].北京:科學(xué)出版社,2001:23-36.

[18]張震,汪斌強(qiáng),伊鵬.一種分層組合的半監(jiān)督近鄰傳播聚類算法[J].電子與信息學(xué),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—），女，河南新鄉(xiāng)人，2009年于西北工業(yè)大學(xué)獲得碩士學(xué)位，現(xiàn)為西安航空學(xué)院講師，主要研究領(lǐng)域?yàn)槟Ｊ阶R(shí)別，人工智能等。

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—），男，陜西鳳翔人，博士，西北工業(yè)大學(xué)、陜西師范大學(xué)教授、博士生導(dǎo)師，CCF高級(jí)會(huì)員，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)，復(fù)雜系統(tǒng)等。

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—），陜西師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)，數(shù)據(jù)挖掘等。

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(陜西省自然科學(xué)基金).

CNKI網(wǎng)絡(luò)優(yōu)先出版:2015-10-28,http://www.cnki.net/kcms/detail/11.5602.TP.20151028.1045.004.html