一種利用信息熵的群體智能聚類算法

1、一種利用信息熵的群體智能聚類算法!#$%計算機(jī)工程與應(yīng)用前言數(shù)據(jù)挖掘是一個多學(xué)科交叉的研究 領(lǐng)域，涉及數(shù)據(jù)庫技術(shù)、 人工智能、 機(jī)器學(xué)習(xí)、統(tǒng)計學(xué)、知識 獲取、生物計算等學(xué)科。這些學(xué)科的發(fā)展為數(shù)據(jù)挖掘的研究提供了新的機(jī)遇與挑戰(zhàn)。聚類是數(shù)據(jù)挖掘的重要任務(wù)之一，目前主要的聚類算法可以劃分為如下幾類()：劃分方法， 層次方法，基于密度的方法，基于網(wǎng)格的方法和基于模型的方法等。這些方法大多數(shù)需要一些參數(shù)限制，設(shè)定聚的數(shù)目，而且聚類結(jié)果對初始狀態(tài)及參數(shù)非常敏感。近年來，一些學(xué)者開始應(yīng)用 群體智 能(*+,-./01233452062)(!)的思想研究聚類問題。因為群體智能源于對簡單個體組成的群落社會系統(tǒng)的

2、模擬，如蟻群、蜂群，在沒有任何先驗知識和無統(tǒng)一指揮的分布環(huán)境下，它們具有自 我組織、合作、通信等特點。在文獻(xiàn)(%)中，720289:8-5等首次模擬幼蟻自 動分類(即較小 的幼蟲在中心， 較大的幼蟲在外圍)及蟻尸聚積現(xiàn)象， 提出了聚 類基本模型。隨后;8.2- 和,421,在文獻(xiàn)(#)中改進(jìn)了 720289:8-5 的基本 模型，提出了 ；算法并應(yīng)用于數(shù)據(jù)分析中雖然以上方法可以獲得較好的聚類結(jié)果，但是需較長的計算時 間，還需設(shè)置較多的參數(shù)。文獻(xiàn)（,=）采用 群體智能與 均值算法相結(jié)合的方法加快聚類速 度。論文在；算法中利用信息熵來控制螞蟻拾起和放下對象動作， 既可以減少參數(shù)的個數(shù)，又可以加快聚

3、類的進(jìn)程。!蟻群聚類的基本模型和；算法在自 然界中， 一些螞蟻可以將 蟻尸 聚成 公墓，也可將幼蟲按大小分類。720289:8-5 等根據(jù)這兩種現(xiàn)象提出 了兩種模型（），兩者的 原理是一致的，即一群螞蟻在一個二維區(qū)域內(nèi)任意移動，允許按 規(guī)則拾起和放下物體。一個任意移動的未載物體的螞蟻拾起一個物體的可能性！按公式（）計算；一個任意移動的載有物體的螞蟻放下一個物體的可 能性!#按公式（?。┯嬎悖渲?是螞蟻周圍物體的個數(shù)，唏口 %! 均為常數(shù)。!?%$!（）#?$%!$!（!）;8.2- 和,421, 在文獻(xiàn)（#）中，基 于720289:8-5的 基本 模型，提出了以下算法：A B/0414,34

4、C,14:0 B A:- 2D2-E 412. F:G3,62 -,0F:.3E :05-4FH0F :-:- ,33 ,5201I F:G3,62 ,5201 ,1 -,0F:.3E I232612FI412H0F :-A B J,40 3:G B A:- （? 1: （.,K F:- ,33 ,52011 F:/L（,5201 803,F20）,0F（ I412 :668G42F 9E 412. ）1M20N:.G812$（）,0F（）7-,+ -,0F:. -2,3 08.92- ） 921+220 ,0F /L（）!()1M20 AA 拾起規(guī)則 O46P 8G 412. HOF /LH

5、3I2 /L (,52016,-E405 412.) ,0F(I412 2.G1E ) 1M20N:.G812 $() ,0F #()7-,+ -,0F:. -2,3 08.92- ) 921+220 ,0F /L()!# () 1M20AA放下規(guī)則7-:G 412. 一種利用信息熵的群體智能聚類算法劉波(暨南大學(xué)計算機(jī)科學(xué)系，廣州二!) HQ.,43 :39K3FFRI:M8$6:.摘要論文采用群體智能(*+,-. /01233452062)的思想研究聚類問題。在;8.2- 和,421,基于蟻群的聚類算法中， 通過信息熵的計 算與比較，改變了拾起和放下對象的規(guī)則， 增加了兩區(qū)域?qū)ο蟮?合并操

6、作，從而加快了 聚類速度并減少了 參數(shù)設(shè)置數(shù)目。該方法能夠有效地聚集數(shù)據(jù)庫的記錄對象，具有一定的實際應(yīng)用價值。關(guān)鍵詞信息熵群體智能聚類文章編號！QS%Q (!# ) %QSQ%獻(xiàn)標(biāo) 識碼 T 中 圖分類號 UO%!#$%()*+ !#+,()-. /%)*+ 0*(,12 3*4 563(. 7*#)+*89)$:,( 72G,-1.201:L N:.G812-*642062，V40,0W04D2-I41E, X8,05CM:8 =%!) UM2 G,G2- 6,-42I-2I2,-6M:0638I12-405 8I405 I+,-.401233452062$/1 ,.20FIG46P405

7、,0FF-:GG405 -832I 40!;%(38:,01 Y9,I2F 638I12-405 ,35:-41M.G-:G:I2F 9E ;8.2- ,0F ,421,1M-:85M 6:.G81405,0F6:.G,-40540L:-.,14:0201-:GE$TI,-2I831 ， 41 IG22FI 8G 638I12-405,0F -2F862I08.92-:LG,-,.212-I$UM2.21M:F6,0638112-26:-FI40,F,1,9,I22LL2614D23E,0F 4I :L G-,6146,3,GG346,14:0D,382$26,(4% :40L:-.,14:0

8、201-:GE , I+,-.401233452062, 638I12-作者簡介：劉波，女，副教授，主要研究方向：數(shù)據(jù)挖掘，數(shù)據(jù)倉庫，智能信息處理。S 計算機(jī)工程與應(yīng)用!#$%() *+() ,+-./0 1.23().456 7050810)(0*9:;.2*(97*10 (.1 .88=*0);6.1:02390(1() .2() .2?2*(15.831*.( .+ *1047以上算法考慮的是：在一個!的網(wǎng)格中，螞蟻在地點#可以觀察到周圍$的區(qū)域中的物體(下面稱對象)。對象在地點2與周 圍對象的相似度按公式 (% 計算，其 中！是一個衡量相異度的參數(shù)，(% %0是兩個對象%和 %(的距離

9、。)(%A$!%(! *+,-( $)(#)AB( % %0 !# *+ ) ( %C%.-+#/$%+(% 00( % 1A1AD)(% (*)!(#)0( % !) (% *+ )( %E1!A*+ )(% 1!$()在F算法中，螞蟻拾起和放下一個對象的可能性按公式(#)和公式()計算。拾起或放下的規(guī)則是：將一個隨機(jī)數(shù)與計算所得的拾起或放下可能性值比較，若隨機(jī)數(shù)小則執(zhí)行拾起或放下操作。這種規(guī)則會導(dǎo)致一個對象多次被拾起或放下，從而聚類較慢。%基于信息熵的蟻群聚類方法（12.=6GH（1GI57102）在文獻(xiàn)JKL中，闡 述了 M:3（.（ 提出 的 信息 熵定義：假設(shè)2是一個隨機(jī)變量，3是其

10、可能的取值集合（連續(xù)型數(shù)據(jù)需離散化），0 （2）是取2值的可能性函數(shù)，信息熵4（2）定義為公式（N）:4（ 2）B23! 0 （2）5.90 （ 2）（ N） 個多變量向 量 2O2A2!，25P的 信息熵按公式 （K）計算，其中：0（ 2）60 （2A，2!，25） 是多變量可能分布函數(shù)，3A，3!，35是相應(yīng)向 量項的可能取值集合（連續(xù)型數(shù)據(jù)需離散化）。4（2）B2A!3A25!35! 0 （2A，2!， ，25）5.90 （2A，2!，25）（ K）文獻(xiàn)JK，QL已提出了基于信息熵的聚類算法，這些方法均依據(jù)這樣一個事實：包含聚的子空間的信息熵比不包含聚的信息熵小。借鑒這一思想，下面在（1

11、2.=6GH（1GI57102算法中，將信息熵引 入F算法中，改變了拾起和放下判斷規(guī)則。R S 初始化S R.2每一對象% ）.將%隨機(jī)地放在一網(wǎng)格中；（）.2.2每一螞蟻）.隨機(jī)地選擇網(wǎng)格中一地方；（）.2R S主循環(huán)SR.2 .A1. .43T ）.2 每一螞蟻）.,+ （螞蟻未負(fù)載）3（）（在 % 之處）1:0（計算信息熵4A和4! ；，+（4AC4!） 1:0（拾起% RR拾起規(guī)則（）,+570，+ （螞蟻負(fù)載%）3（）（所在之處為空）1:0（計 算信息熵4A和4! ； ，+（ 4AC4!）1:0（放下% RR放下規(guī)則（）*+（），+螞蟻隨機(jī)移到某地方；（）.2（） .2一個未負(fù)載的螞

12、蟻移到對象之處，計算周圍$的區(qū)域中的對象信息熵，假設(shè)未拾起對象前的信息熵為4A，拾起對象后該區(qū)域的信息熵變?yōu)?!，拾 起規(guī)則為：，+ 4AC4!，則拾起對象。一個負(fù)載對象的螞蟻移到空白 之處，計算周圍$的區(qū)域中 的對象信息熵，假設(shè)未放下對象前的信息熵為4A，放下對象% 后該區(qū)域的信息熵變?yōu)?!，放下規(guī)則為：，+ 4AC4!，則放下對象。假設(shè)每一對象包括5個互為獨立的 屬性7A ,7!75,各屬性的 可能取值集合為3A ,3!，35 , #區(qū)域中的對象信息熵可按公式 （Q 計算，0 （2）按公式 （U）計算， 其中589:+#;%）;2 是$區(qū) 域中滿足762的對象個數(shù)，589:+#;%）;=$

13、+是$區(qū)域中的對象總 數(shù)。4（ $!）B5 6 A!2! 35! 0（ 2）5.90（ 2）（ Q） 0（ 2）589:+#;%）;2589:+#;%）;=$+ （ U #兩種方法的比較分析蟻群聚類方 法最大的特點是：不需設(shè)定最終產(chǎn)生的聚的數(shù)目，聚中心是動態(tài)變化的，可以發(fā)現(xiàn)任意形狀的聚。以上兩種方法均以 390（1的任意選擇的地方作為變化的聚中 心，并考察周圍一小塊區(qū)域中的對象，通過拾起或放下操作改變此一小塊區(qū)域的對象相似度。在F算法中，影響拾起或放下動作的因素有對象間的距離、1A、 1!、！、$等參數(shù)，還有隨機(jī)數(shù)，因此，每次放下的對象不一定 與小塊區(qū)域中存在的對象相似；每次拾起的對象不一定與

14、小塊區(qū)域中存在的對象不相似，聚類過程很慢。在(12.=6GH(1GI57102的方法中， 影響拾起或放下動作的因素 只有$參數(shù)，每次放下對象能減少小塊區(qū)域的信息熵；每次拾起能增加小塊區(qū)域的信息熵。根據(jù)文獻(xiàn)JK, QL 包含聚的子空間的信息熵比不包含聚的信息 熵小，因此同類型的對象能夠較快地聚集在一起，但產(chǎn)生的結(jié)果是局部最優(yōu)。通過調(diào)整觀察區(qū)域的大小$，可減少小塊聚的產(chǎn)生。兩種方法的時間復(fù)雜度均為？(.43T*=5. ), *=5.為螞蟻個數(shù)，但 實驗結(jié)果表明(12.=6GH(1GI57102算法經(jīng)過較少次循環(huán)就能達(dá)到較 好的聚類結(jié)果。實驗結(jié)果從VI,J#L公共數(shù)據(jù)庫中選取一組數(shù)據(jù)集 (W*8G1

15、38G1.Q)9340)，該數(shù)據(jù)集包括UQ個對象， 可分為兩類。分別用F算法和(12.=6GH(1GI57102方法對這一數(shù)據(jù)集進(jìn)行 聚類。在F算法中，設(shè)置N個參數(shù)：1A$A，1!$A !$, $!NXN .43T% =,+5.;589:+# (螞蟻數(shù) 目)； 在(12.=6GH(1GI57102AQA!#$%算機(jī)工程與應(yīng)用(上接56/-78456/-7839;*8,878; ,-./0=;后面輸出 所有的拓?fù)湫蛄校创娣旁诙S數(shù)組 嚴(yán) 中的元素，略去；$?AB算 法的實例用ABC算法，可以求出 一個可行的CDE網(wǎng)的所有可行 的拓?fù)湫蛄?，該算法的調(diào)用是以判斷CDE網(wǎng)不存在有向環(huán)為前提的 + 1

16、。對于圖 所示的CDE網(wǎng)，調(diào)用ABC算法可求得！個并行拓?fù)?序列如下：（）! % # ； （!） ! % # ； （% ! # % ；（#） % !# ；（）% ! #；（?）!%#；（F）!% # ；（G）!# % ；（H）% ! #；（） % !# ；（） %! #；（!）% !#。而用非并行算法只能求得一種拓?fù)湫蛄校? ! # 。兩種結(jié)果相 比，ABC算法的優(yōu)勢是很顯然的。因為一個實際活動很有可能不能按%!#這樣的唯一順序安排，那么有了 ABC的結(jié)果，則還有 種可能的串行安排選擇。更為重要的是，從所有的拓?fù)湫蛄兄校?可以得到并行信息，如 上例，可按（）！ （! %）! （ #）的順序安排

17、子工程，若每個 子工程耗費一個單位時間，則并行安排只需三個單位時間，而串行安排卻需六個單位的時間?？梢?，AB（算法提升了拓?fù)渑判蛩惴ǖ膶嵱脙r值。F結(jié)束語若一個CDE網(wǎng)有！個頂點，最多有!#個拓?fù)湫蛄?則AB（算法的 時間 復(fù)雜度和空間 復(fù)雜度均為$（!#%!）,算法效率較高，但仍需要進(jìn)一步優(yōu)化。拓?fù)渑判蛩惴ㄔ诠こ痰挠媱澒芾怼⑾到y(tǒng)的統(tǒng)籌調(diào)度、工藝決策過程+#1、生產(chǎn)流程控制及軟件開發(fā)+1等領(lǐng)域得到了 廣泛的應(yīng)用， 但是以往用程序只能求得一種拓?fù)湫蛄惺沟盟惴▽嵱眯韵陆?。ABC算法根據(jù)拓?fù)渑判蛩枷耄?引 入層次的概念，并基于一種 以十字隊列為主的混合數(shù)據(jù)結(jié)構(gòu)，采用分層求解的方法得到了一個CDE中頂點

18、的所有可行拓?fù)湫蛄?。該算法的并行性就體現(xiàn)在：ABC算法在求解過程中是分層的，同一層次的子序列均求出以 后才能求下一層次的子序列， 即并行地向前推進(jìn)； 同時，從多個 拓?fù)湫蛄兄心艿玫酵粫r刻可并行執(zhí)行的子工程名 。結(jié)合工程安排的實際情況及一些特定的約束條件，利 用ABC算法可以得到真正可行的串 行或并行子工程安排表， 從而真正做到 管理統(tǒng)籌的自 動化、高效化，因 此ABC算法具有非常高的實用 價值。（收稿日期：!# 年 月）參考文獻(xiàn)$陳慧南$數(shù)據(jù)結(jié)構(gòu)（使用1=語言描述）+J1$南京：東南大學(xué)出版社，！!$王曉瑛，魏正軍$關(guān)于拓?fù)渑判蛩惴ǖ挠?論+K1$西北大學(xué)學(xué)報 （自 然科學(xué)版），！!3# :

19、%#L%#?%王順鳳$種有向權(quán)圖的拓?fù)渑判蛩惴捌鋺?yīng)用 +K1晡京氣象學(xué)院學(xué)報（自 然科學(xué)版），！!3#$趙學(xué)軍，喬紅兵等$IC系 統(tǒng)工藝決策過程的CDE3網(wǎng)表示法及拓?fù)渑判蚍治?K1$機(jī)電一體化， HHG3#丁明亮，陳仁全$用有限自 動機(jī)和拓?fù)渑判蚶碚撎岣逬MB開 發(fā)效率+K1$微計算機(jī)信息，！3F方法中，僅設(shè)置三個參數(shù)：!4N ，:）04%, （）*!+!#,*-（螞蟻數(shù)目）4!。在實驗中， 首先使AP,Q0）,Q0-8 R/7S）:8 數(shù)據(jù)集的對象均勻分 布在N的區(qū)域中， 不同類型的對象分別用不同符號表示?？梢缘贸鲆韵陆Y(jié)論：（）TU算法在4%時，不能將同一類型的對象聚在一起， 不同 類型

20、的對象混合集中分布在幾個區(qū)域中； （!）R/0*-;VQC/0QIW.X08* 方法在4%時，基本上可以將不同類型的對象分開， 并且同一類型 的對象集中分布在幾個區(qū)域范圍內(nèi) 。顯然，R/0*-;VQC/0QIW.X08*方法與TU算法相比， 聚類速度較 快，而且準(zhǔn)確率高。?結(jié)論群體智能是人工智能領(lǐng)域一個新穎的研究分支，其模擬一些自然界中具有自 治、合作、通信等特點社會群體的行為， 已 解決旅行推銷員， 作業(yè)調(diào)度， 路由 選擇等優(yōu)化問題。Y8/8.Z-.*S、T.:8* 和U）P80）等在文獻(xiàn)+% #1中，借鑒蟻群可以將蟻尸聚成公墓以及可將幼蟲按大小分類的行為，提出了聚類模型和算法，但是存在聚類

21、速度慢并且需要設(shè)置較多參數(shù)等 問題。論文利用 信息熵修改了 TU算法中的拾起和放下對象規(guī)則，減少了參數(shù)數(shù)目，力口 DO6-*7 d/Pe8*XP0V*8XX HHH%$Y8/8.Z-.*S K T, B a-XX，b U*)/2X 80 )W$A8 YV/):P,X -6 l-WW8,0Pe8B-*0P/S: f-Z-03TP28 C/0 )/7 C/03TP28 f-Z-0+l1$M/K C J8V8*，B ggPWX-/ 87X$*-,887P/SX UP*X0 I-/68*8/,8 -/BP:.W)0P-/ -6 C7);0Pe8_8)eP-*U*-: C/P:)WX 0- C/P:)0

22、X，I):Z*P7S8，JC：JMA *8XX，HH%?L%?#$T.:8* R， _ U)P80)$YPe8*XP0V )/7C7);0)0P-/ P/-;.W)0P-/X -6 ,W.X308*P/S )/0X+I1$M/:*-,887P/SX AP*7 M/08*/)0P-/)W I-/68*8/,8 -/ BP:.3W)0P-/-6 C7);0Pe8 _8)eP-*:P，HHH3?吳斌，傅偉鵬，鄭毅等$種基于群體智能的g8Z文 檔聚類算法+K1$計算機(jī)研究與發(fā)展，! ； %H():#!HL#%F$Y)/P8W _)*Z)*i，K.WP) I-.0- ，cP TP$IDDTICAC/8/0*-;V3Z)X87)WS-3*P0:6-* ,)08S-*P,)W ,W.X08*P/S+I1$M/:;*-,887P/SX-6088W8e8/0P/308*/)0P-/)W ,-/68*8/,8，-e8*V )/77)0) :P/P/S，HHHG