曾令偉, 伍振興, 杜文才

(1. 瓊州學(xué)院 電子信息工程學(xué)院, 海南 三亞 572022; 2. 海南大學(xué) 信息科學(xué)技術(shù)學(xué)院, 海南 ?？?570228)

?

基于改進(jìn)自監(jiān)督學(xué)習(xí)群體智能(ISLCI)的高性能聚類算法

曾令偉1, 伍振興1, 杜文才2

(1. 瓊州學(xué)院 電子信息工程學(xué)院, 海南 三亞 572022; 2. 海南大學(xué) 信息科學(xué)技術(shù)學(xué)院, 海南 海口 570228)

摘要：針對(duì)現(xiàn)有數(shù)據(jù)聚類算法(如K-means)易陷入局部最優(yōu)和聚類質(zhì)量不佳的問(wèn)題，提出一種結(jié)合改進(jìn)自監(jiān)督學(xué)習(xí)群體智能(improved self supervised learning collection intelligence，ISLCI)和K均值(K-means)的高性能聚類算法。已有的自監(jiān)督學(xué)習(xí)群體智能演化方案具有計(jì)算效率和聚類質(zhì)量高的優(yōu)點(diǎn)，但當(dāng)應(yīng)用于數(shù)據(jù)聚類時(shí)，收斂速度較慢且極易陷入局部最優(yōu)。為ISLCI加入突變操作，增加其樣本多樣性來(lái)降低早熟的概率,提高最優(yōu)解的求解質(zhì)量；計(jì)算每個(gè)樣本的行為方程，獲得其行為結(jié)果；通過(guò)輪盤(pán)賭方案來(lái)選擇群體智能學(xué)習(xí)的對(duì)象和群體中其他樣本學(xué)習(xí)目標(biāo)對(duì)象的屬性來(lái)提高自己。同時(shí)，利用K-means操作提高其收斂速度，提高算法計(jì)算效率。對(duì)比試驗(yàn)結(jié)果表明，本算法具有收斂速度快、聚類質(zhì)量高、不易陷入局部最優(yōu)的特點(diǎn)。

關(guān)鍵詞：自監(jiān)督學(xué)習(xí)群體智能；數(shù)據(jù)聚類；突變操作；簇內(nèi)距離；函數(shù)評(píng)價(jià)次數(shù)

0引言

將數(shù)據(jù)集合按照相似性進(jìn)行分類，相似性高的數(shù)據(jù)歸為一簇，此為數(shù)據(jù)挖掘中的聚類技術(shù)[1]，聚類技術(shù)是數(shù)據(jù)挖掘的核心技術(shù)之一。聚類通常分為基于密度聚類[2]、分割聚類[3]、分層聚類[4]等。

已有大量針對(duì)數(shù)據(jù)挖掘聚類的研究，文獻(xiàn)[5]提出一種基于圖劃分的高階聯(lián)合聚類算法(based on gragh partitioning of high order combined clustering algorithm,GPHCC)，該算法將網(wǎng)狀高階異構(gòu)數(shù)據(jù)的聚類問(wèn)題轉(zhuǎn)化為多對(duì)二部圖的最小正則割劃分問(wèn)題。通過(guò)將優(yōu)化問(wèn)題轉(zhuǎn)化為半正定問(wèn)題求解，降低了計(jì)算復(fù)雜度，然而收斂速度依然不夠理想。文獻(xiàn)[6]提出了基于多子群粒子群偽均值(PK-means)聚類算法，而該算法的收斂速度不佳。文獻(xiàn)[7]提出了一種基于混合差分進(jìn)化的滑動(dòng)窗口數(shù)據(jù)流聚類算法。該算法在對(duì)數(shù)據(jù)流執(zhí)行聚類時(shí)具有較高的執(zhí)行效率，但對(duì)于非數(shù)據(jù)對(duì)象時(shí)，分類質(zhì)量不夠理想。文獻(xiàn)[8]提出一種由在頂點(diǎn)上的低層隨機(jī)游走和在組件上的高層隨機(jī)游走2部分構(gòu)成的雙層隨機(jī)游走半監(jiān)督聚類算法，其算法僅優(yōu)于其他半監(jiān)督聚類算法，而其他高質(zhì)量聚類算法并無(wú)明顯優(yōu)勢(shì)。文獻(xiàn)[9]提出了1種基于2個(gè)最小生成樹(shù)命中時(shí)間的高維數(shù)據(jù)聚類算法，該算法收斂速度快，然而容易陷入局部最優(yōu)。文獻(xiàn)[10]提出一種基于人工蟻群算法的數(shù)據(jù)挖掘聚類優(yōu)化算法，而其同樣具有收斂速度不佳及容易陷入局部最優(yōu)的不足。文獻(xiàn)[11]基于遺傳算法與混沌理論提出了一種優(yōu)化聚類算法，該算法具有收斂速度快、計(jì)算復(fù)雜度低的優(yōu)點(diǎn)，但其較容易陷入局部最優(yōu)。文獻(xiàn)[12]針對(duì)數(shù)據(jù)流提出了一種收斂速度優(yōu)化的算法，而其具有收斂早熟概率大的缺點(diǎn)。

文獻(xiàn)[13]提出了一種基于自監(jiān)督學(xué)習(xí)的啟發(fā)式優(yōu)化算法(self supervised learning collection intelligence,SLCI)，該研究針對(duì)一些經(jīng)典問(wèn)題做了試驗(yàn)驗(yàn)證并與部分經(jīng)典優(yōu)化算法進(jìn)行了比較，結(jié)果表明其具有計(jì)算效率高、聚類質(zhì)量高的優(yōu)點(diǎn)。本文將該優(yōu)化算法引入數(shù)據(jù)挖掘的聚類算法中，并結(jié)合經(jīng)典的K-means算法[14]，提出了一種收斂速度快、求解質(zhì)量高及不易早熟收斂的聚類算法，并通過(guò)對(duì)比試驗(yàn)驗(yàn)證了以上特點(diǎn)。

1K-means聚類算法

設(shè)R=[Y1,Y2,…,YN](其中Yi∈RD)表示含N個(gè)數(shù)據(jù)對(duì)象的集合，S=[X1,X2,…,XK]表示該集合的K個(gè)簇。聚類過(guò)程即為將R中數(shù)據(jù)全部分配至K個(gè)簇中。簇內(nèi)方差定義為簇內(nèi)各Yi與質(zhì)心Xj的歐氏距離平方和，該目標(biāo)方程如下表示

(1)

假設(shè)預(yù)知簇?cái)?shù)量，K-means算法的目標(biāo)是計(jì)算并確定各簇的質(zhì)心。K-means算法的主要步驟如下。

1)從數(shù)據(jù)集R=[Y1,Y2,…,YN]中隨機(jī)選取K個(gè)樣本作為初始化質(zhì)心S=[X1,X2,…,XK]。

2)將R中各樣本分配至距離最近的質(zhì)心。

3)重新計(jì)算各簇質(zhì)心位置。

4)重復(fù)2)—3)步，直至滿足預(yù)設(shè)的結(jié)束條件。

文獻(xiàn)[15]提出了K-means的優(yōu)化算法，稱為K-means++算法，其步驟如下。

1)從R中均勻隨機(jī)的選取一個(gè)中心X1。

2)對(duì)每個(gè)樣本Yi，計(jì)算其與最近中心的距離D(Yi)。

4)重復(fù)2)—3)步，直至質(zhì)心數(shù)量達(dá)到K。

5)至此，選取了全部的初始化質(zhì)心，然后使用標(biāo)準(zhǔn)K-means算法進(jìn)行聚類處理。

2SLCI優(yōu)化算法

文獻(xiàn)[13]提出了一種基于自監(jiān)督學(xué)習(xí)的群體智能優(yōu)化算法，該算法源自社會(huì)中同類人群具有互相學(xué)習(xí)的趨勢(shì)，同類人群指該人群具有內(nèi)在共通的目標(biāo)，其中每個(gè)人學(xué)習(xí)其他同類人群來(lái)提高自己。最終每個(gè)人學(xué)習(xí)其他同類人并經(jīng)過(guò)數(shù)次迭代后提高了群體的總性能。如果數(shù)次迭代后，群體并無(wú)改善，該群體則稱為飽和狀。

一般無(wú)約束最小值問(wèn)題表示為

Minimizef(X)=f(x1,x2,…,xi,…,xN)

步驟1初始化以下參數(shù)：樣本C的數(shù)量、屬性的采樣間隔ψi、采樣間隔縮減系數(shù)r∈[0,1]、收斂參數(shù)ε、迭代次數(shù)n和變化次數(shù)t。

步驟2每個(gè)樣本c選擇行為f*(Xc)的概率計(jì)算為

(2)

(3)

(3)式中，ψi=(‖ψi‖)×r。

步驟5在縮短后的采樣周期內(nèi)采樣t個(gè)行為并組成集合，即Fc,t=[f(Xc)1,f(Xc)2,…,f(Xc)t]，從中選擇最佳行為f*(Xc)。其他樣本學(xué)習(xí)該最優(yōu)行為，表示為

步驟6如f*(Xc)較之前無(wú)明顯改善，該群體則視作飽和，即多次迭代后，行為間差異不大于閾值ε，表示為

(4)

(5)

(6)

步驟7滿足以下2個(gè)條件之一即結(jié)束，否則跳至步驟2。

1)達(dá)到迭代最大次數(shù)限制。

2)如果該群體飽和，即滿足方程(4)—(6)。

3SLCI的改進(jìn)算法ISLCI

本文對(duì)文獻(xiàn)[13]算法進(jìn)行改進(jìn)，提出了ISLCI(improvedselfsupervisedlearningcollectionintelligence)算法，提高其正確率與收斂速度，SLCI算法當(dāng)收斂于局部最優(yōu)或搜索速度過(guò)慢時(shí)，易早熟收斂。本文提出一種突變機(jī)制擴(kuò)大其搜索范圍以及增加解的多樣性來(lái)防止早熟。

(7)

(7)式中，變量m1，m2，m3是隨機(jī)選擇的3個(gè)樣本，所以m1≠m2≠m3≠c。

(8)

所選樣本則為

(9)

(10)

(10)式中：z=1,2,…,b；rand(.)表示[0,1]間的隨機(jī)數(shù)；γ表示小于1的隨機(jī)數(shù)；D表示數(shù)據(jù)對(duì)象的維度。因此，基于如下方程選擇第i次迭代時(shí)c的新增屬性

(11)

圖1　樣本聚類方案舉例Fig.1　Individuality clustering approach sample

4融合K-means與ISLCI的聚類算法K-ISLCI

ISLCI具有分類質(zhì)量高和不易早熟的優(yōu)點(diǎn)，結(jié)合K-means提高收斂速度，提出了一種高性能的數(shù)據(jù)挖掘聚類算法K-ISLCI。首先利用K-means算法處理樣本，然后運(yùn)行ISLCI算法處理。本算法具有收斂速度快，不易陷入局部最優(yōu)和分類準(zhǔn)確率高的優(yōu)點(diǎn)。算法步驟如下。

步驟1產(chǎn)生初始化樣本，利用(12)式隨機(jī)產(chǎn)生C個(gè)初始樣本

(12)

(13)

(14)

(15)

步驟2使用第1節(jié)的K-means算法處理每個(gè)樣本。

步驟3使用第3節(jié)的ISLCI算法處理每個(gè)樣本。

步驟4使用(1)式計(jì)算每個(gè)樣本的行為方程f(Sc)。

步驟5使用(2)式計(jì)算每個(gè)樣本選擇行為f*(Sc)的概率。

步驟8如f*(Xc)較之前無(wú)明顯改善，該群體則視作飽和，即多次迭代后，行為間差異不大于閾值ε。

步驟9滿足以下2個(gè)條件之一即結(jié)束，否則跳至步驟2。

1)達(dá)到迭代最大次數(shù)限制。

2)如果該群體飽和，即滿足方程(4)—(6)。

5試驗(yàn)結(jié)果與分析

選擇6個(gè)真實(shí)、經(jīng)典數(shù)據(jù)集驗(yàn)證本算法，介紹如下。

1)Irisdataset(N=150,D=4,K=3)：以鳶尾花特征作為數(shù)據(jù)源，共150個(gè)數(shù)據(jù)，分為3類(setosa，versicolor，virginica)，每類50個(gè)數(shù)據(jù)，每個(gè)數(shù)據(jù)含4個(gè)屬性。

2)Winedataset(N=178,D=13,K=3)：以酒的化學(xué)成分作數(shù)據(jù)源，共178個(gè)數(shù)據(jù)，分為3類，樣本個(gè)數(shù)分別為59，71，48，每個(gè)數(shù)據(jù)含13個(gè)屬性。

3)Glassdataset(N=214,D=9,K=6)：以玻璃的特征作為數(shù)據(jù)源，共214個(gè)數(shù)據(jù)，分為6類，樣本個(gè)數(shù)分別為70，76，17，13，9，29，每個(gè)數(shù)據(jù)含9個(gè)屬性。

4)BreastCancerWisconsindataset(N=683,D=9,K=2)：共683個(gè)數(shù)據(jù)集，分為2類，樣本數(shù)量分別為444，239，各數(shù)據(jù)含9個(gè)屬性。

5)Voweldataset(N=871,D=3,K=6)：共871個(gè)數(shù)據(jù)集，分為6類，樣本數(shù)量分別為72，89，172，151，207，180，各數(shù)據(jù)含3個(gè)屬性。

6)ContraceptiveMethodChoicedataset(N=1 473,D=9,K=3)：共1473個(gè)數(shù)據(jù)集，分為3類，樣本數(shù)量分別為629，334，510，各數(shù)據(jù)含9個(gè)屬性。

采用2個(gè)參數(shù)評(píng)價(jià)聚類算法的性能，分別為i)簇內(nèi)距離，如(1)式定義；ii)目標(biāo)函數(shù)評(píng)價(jià)次數(shù)適應(yīng)度函數(shù)評(píng)估( fitness function evaluation, NFE)。簇內(nèi)距離越小表示聚類質(zhì)量越高；NFE表示搜索最優(yōu)值過(guò)程中，聚類算法計(jì)算目標(biāo)方程(1)式的次數(shù)，NFE值越小表示收斂速度越快。

試驗(yàn)環(huán)境為PC(Intel Core i7-3770, 3.4 GHz, 4 GByte內(nèi)存)，操作系統(tǒng)為Windows 7專業(yè)版，編程環(huán)境為Matlab 2007。K-ISLCI，ISLCI和SLCI的參數(shù)如表1所示。將本算法與以下各聚類算法進(jìn)行對(duì)比試驗(yàn)：K-means，K-means++[15]，一般的蜂群算法(general artificial bee colony, GA)[10]，遺傳算法案例 (sample of a genetic algorithm, SAA)[11]，快速聚類算法 ( data speedup clustering, DS)[12]滑動(dòng)窗口優(yōu)化的聚類算法(clustering algorithm optimized for sliding window, COS)[7]，基于樹(shù)結(jié)構(gòu)優(yōu)化的混合算法 (hybrid tree based optimized algorithm , HBOA)[9]。將以上各聚類算法分別對(duì)6個(gè)數(shù)據(jù)庫(kù)進(jìn)行聚類實(shí)驗(yàn)，每個(gè)實(shí)驗(yàn)均運(yùn)行20次，將所得20個(gè)聚類實(shí)驗(yàn)結(jié)果(簇內(nèi)距離)中最優(yōu)值、平均值、最差值、標(biāo)準(zhǔn)差和NFE值統(tǒng)計(jì)于表2中。

表2中可看出，對(duì)于Iris數(shù)集，K-ISLCI和ISLCI算法每次運(yùn)行均可收斂于全局最優(yōu)值96.555 4，而SLCI，K-Means，K-means++，GA，SAA，DS，COS和HBOA的最優(yōu)值分別為96.655 7，97.325 9，97.325 9，113.986 5，97.457 3，97.365 9，97.100 7和96.752；同時(shí)K-ISLCI的標(biāo)準(zhǔn)差是0，遠(yuǎn)低于其他算法，可見(jiàn)本算法的聚類質(zhì)量和魯棒性均明顯優(yōu)于其他聚類算法。對(duì)于Wine數(shù)據(jù)集，K-ISLCI的最優(yōu)值同樣最佳，同時(shí)平均值、最差值均優(yōu)于其他算法。對(duì)于UCI的一個(gè)數(shù)據(jù)集(contraceptive method choice, CMC)，K-ISLCI獲得最優(yōu)簇內(nèi)距離5 693.73，而SLCI，ISLCI，K-Means，K-means++，GA，SAA，DS，COS，HBOA的最優(yōu)值分別為5 695.33， 5 694.28， 5 703.20，5 703.20，5 705.63，5 849.03，5 885.06，5 701.92，5 699.26，此外，K-ISLCI的標(biāo)準(zhǔn)差也明顯優(yōu)于其他算法。對(duì)于vowel數(shù)據(jù)集，本算法的最優(yōu)、平均、最差簇內(nèi)距離和標(biāo)準(zhǔn)差分別為48 967.24，148 987.55，149 048.58，36.086，同樣明顯小于其他算法。

比較表2中的ISLCI和SLCI的試驗(yàn)結(jié)果：對(duì)于Wine數(shù)據(jù)集，ISLCI的最優(yōu)、平均、最差值分別為16 295.16，16 296.51，16 297.98，標(biāo)準(zhǔn)差為0.907；而SLCI的最優(yōu)、平均、最差結(jié)果分別為16 298.01，16 300.98，16 305.60，標(biāo)準(zhǔn)差為2.118。可見(jiàn)本文的突變操作提高了SLCI的聚類性能。

比較表2中K-ISLCI，ISLCI，SLCI，可看出將K-means加入ISLCI，具有明顯效果。對(duì)Wine數(shù)據(jù)集，K-ISLCI，ISLCI，SLCI的全局最優(yōu)值分別為16 292.44，16 295.16，16 298.01。結(jié)果證明K-ISLCI比ISLCI和SLCI具有更好的聚類性能。此外，結(jié)合K-means增強(qiáng)了算法收斂速度。對(duì)于Wine數(shù)據(jù)集，SLCI和ISLCI獲得最優(yōu)解分別需17 500和16 500次計(jì)算，而K-ISLCI僅需6 250次計(jì)算即可獲得最優(yōu)解，因此K-ISLCI收斂速度較快。盡管K-means和K-means++算法收斂快于其他算法，但其較容易早熟，例如，對(duì)于Wine數(shù)據(jù)集，K-means++算法僅需261次計(jì)算即可獲得最優(yōu)解，但其收斂結(jié)果明顯比K-ISLCI差。

綜上所述，表2的試驗(yàn)結(jié)果證明了，相較于其他算法，本算法可在較低的標(biāo)準(zhǔn)差及較少的計(jì)算次數(shù)下獲得了更佳的聚類效果。表3—5所示為K-ISLCI獲取的各數(shù)據(jù)集質(zhì)心，可看出本聚類算法成功獲得所有數(shù)據(jù)集的質(zhì)心，可看出本算法的有效性，所獲得質(zhì)心供參考。

表1　SLCI，ISLCI，K-ISLCI算法參數(shù)(c(每個(gè)隊(duì)列中樣本數(shù)量)、t(樣本屬性的數(shù)量)、r(采樣周期的折減系數(shù)))

表2　各聚類算法實(shí)驗(yàn)結(jié)果

續(xù)表2

表3　Glass與Vowel各類的質(zhì)心

表4　Iris各類的質(zhì)心

續(xù)表4

表5　Cancer各類的質(zhì)心

6結(jié)束語(yǔ)

SLCI是一種新型的高性能優(yōu)化算法，對(duì)于數(shù)據(jù)挖掘聚類算法具有極大的潛力。然而，SLCI的收斂速度不佳，當(dāng)數(shù)據(jù)維度增加或簇?cái)?shù)量增加時(shí)，容易產(chǎn)生陷入局部最優(yōu)。針對(duì)此類缺點(diǎn)，結(jié)合突變操作提出了一種改進(jìn)的ISLCI算法，擴(kuò)大其搜索范圍來(lái)降低早熟收斂的概率，此外，結(jié)合K-means算法提高其收斂速度。試驗(yàn)結(jié)果表明，本算法具有收斂速度快、聚類質(zhì)量高、不易陷入局部最優(yōu)的特點(diǎn)。

本算法需預(yù)知數(shù)據(jù)集部分參數(shù)，未來(lái)將對(duì)此開(kāi)發(fā)新的自適應(yīng)聚類算法，提高算法的實(shí)用性。

參考文獻(xiàn)：

[1]畢志升, 王甲海, 印鑒. 基于差分演化算法的軟子空間聚類[J]. 計(jì)算機(jī)學(xué)報(bào), 2012, 35(10): 2116-2128.

BI Zhisheng , WANG Jiahai , YIN Jian. Subspace Clustering Based on Differential Evolution[J].Chinese Journal of Computers,2012,35(10): 2116-2128.

[2]馬素琴, 施化吉. 閾值優(yōu)化的文本密度聚類算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2011, 47(17): 134-136.

MA Suqin,SHI Huaji. Text density clustering algorithm with optimized threshold values[J].Computer Engineering and Applications,2011,47(17):134-136.

[3]張薇,劉加.電話語(yǔ)音的多說(shuō)話人分割聚類研究[J].清華大學(xué)學(xué)報(bào)：自然科學(xué)版,2008,48(4):574-577.ZHANG Wei,LIU Jia. Multi-speaker segmentation and clustering of telephone speech[J].Journal of Tsinghua University:Science and Technology,2008,48(4):574-577.

[4]許寧,張毅坤.基于正交分層聚類算法軟件可靠性模型的預(yù)測(cè)分析[J].計(jì)算機(jī)應(yīng)用,2007,27(3):635-637.XU Ning,ZHANG Yikun. Research on reliability prediction model based on orthogonal layer-clustering algorithm[J].Journal of Computer Applications,2007,27(3):635-637.

[5]楊欣欣,黃少濱.基于圖劃分的網(wǎng)狀高階異構(gòu)數(shù)據(jù)聯(lián)合聚類算法[J].四川大學(xué)學(xué)報(bào):工程科學(xué)版,2014,46(2):105-110.

YANG Xinxin， HUANG Shaobin. A Net-structure High-order Heterogeneous Data Co-clustering[J].Journal of Sichuan University:Engineering Science Edition,2014,46(2):105-110.

[6]沈艷, 余冬華, 王昊雷. 粒子群 K-means 聚類算法的改進(jìn)[J]. Computer Engineering and Applications, 2014, 50(21): 125-128.SHEN Yan,YU Donghua,WANG Haolei. Improvement of K-means based on particle swarm clustering algorithm[J].Computer Engineering and Applications,2014(21):125-128.

[7]任永功,胡志冬,楊雪.基于混合差分進(jìn)化的滑動(dòng)窗口數(shù)據(jù)流聚類算法研究[J].計(jì)算機(jī)應(yīng)用研究,2014,31(4):1009-1012.

REN Yonggong;HU Zhidong;YANG Xue.Research on sliding window data stream clustering algorithm based on hybrid differential evolution[J].Application Research of Computers,2014,31(4):1009-1012.

[8]何萍,徐曉華,陸林,等.雙層隨機(jī)游走半監(jiān)督聚類[J].軟件學(xué)報(bào),2014,25(5):997-1013.

HE Ping,XU Xiaohu,LU Lin, et al.Semi-Supervised Clustering via Two-Level Random Walk[J].Journal of Software,2014,25(5):997-1013.

[9]GALLUCCIO L, MICHEL O, COMON P, et al. Clustering with a new distance measure based on a dual-rooted tree[J]. Information Sciences, 2013(251): 96-113.

[10] KARABOGA D, OZTURK C. A novel clustering approach: Artificial Bee Colony (ABC) algorithm[J]. Applied Soft Computing, 2011, 11(1): 652-657.

[11] LEE J, LEE D. An Improved Cluster Labeling Method for Support Vector Clustering[J]. IEEE Transactions on pattern analysis and machine intelligence, 2005, 27(3): 461-464.

[12] FU L, NIU B, ZHU Z, et al. CD-HIT: accelerated for clustering the next-generation sequencing data[J]. Bioinformatics, 2012, 28(23): 3150-3152.

[13] TIAN Zheng, LI Xiaobin, JU Yanwei. Disturbing Analysis on Spectrum Clustering[J]. Science in China: Series E, 2007, 37(4): 527-543.

[14] JAIN A K. Data clustering: 50 years beyond K-means[J]. Pattern Recognition Letters, 2010, 31(8): 651-666.

[15] DOMINGOS P. Prospects and challenges for multi-relational data mining[J]. ACM SIGKDD Explorations Newsletter, 2003, 5(1): 80-83.

Improved self supervised learning collection intelligence based high performance data clustering approach

ZENG Lingwei1, WU Zhenxing1, DU Wencai2

(1. College of Information and Electronic, Qiongzhou University, Sanya 572022 P.R. China;2. College of Information Science & Technology, Hainan University, Haikou 570228 P.R. china)

Abstract:For the problems that traditional data clustering approaches easily converge to local optima and the quality of the solution is not good, a high performance clustering approach which combines the improved self supervised learning collection intelligence and K-means is proposed. The existing self supervised learning approach has the advantage of computation efficiency and quality of clustering, but has the problem of low speed of convergence and trapping in local optimal easily. Firstly, a mutation mechanism is added to ISLCI that aims to reduce the probability of optima and the quality of optimal solution is improved; Secondly, the action function of each candidate is computed. Lastly, the object of the collection intelligence learning is selected by roulette approach, and the others in the population learn from the object to improve themselves. The converge speed is speeded up with K-means approach and the computation efficiency is improved. The compared experiment result demonstrated that the proposed approach has the characteristic of converge quickly, good quality of clustering solution and low probability to fall to local optima.

Keywords：self supervised learning collection intelligence; data clustering; mutation operation; intra-cluster distance; fitness function evaluation

DOI：10.3979/j.issn.1673-825X.2016.01.020

收稿日期：2014-12-10

修訂日期：2015-10-09通訊作者：曾令偉sanyazenglingwei@126.com

基金項(xiàng)目：2014年海南省高等學(xué)校科學(xué)研究項(xiàng)目(HNKY2014-65)

Foundation Item：The Higher School Science Foundation Project of Hainan(HNKY2014-65)

中圖分類號(hào)：TP181

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1673-825X(2016)01-0131-07

作者簡(jiǎn)介：

曾令偉(1978-)，男，湖南衡陽(yáng)人，副教授，碩士，主要研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘，人工智能。E-mail：sanyazenglingwei@126.com。

伍振興(1985-)，男，湖南婁底人，講師,碩士，主要研究領(lǐng)域?yàn)檐浖こ?，?jì)算機(jī)網(wǎng)絡(luò)。

杜文才(1953-)，男，江蘇南通人，教授，博士，主要研究領(lǐng)域?yàn)楹Ｑ笸ㄐ拧⒂?jì)算機(jī)網(wǎng)絡(luò)、物聯(lián)網(wǎng)。

(編輯：張誠(chéng))