蟻群聚類在民族突發事件應急決策中的應用

(1.大連民族學院 計算機科學與工程學院， 遼寧 大連 116600；2.上海師范大學 人文與傳播學院， 上海 200234；3.國家民族事務委員會 信息中心， 北京 100080；4.青海師范大學 民族師范學院， 西寧 810008) 

摘 要：首先使用混合屬性數據集表示民族突發事件中的數值信息和類屬信息；然后，考慮到每個屬性擁有不同權重因子，改進了蟻群聚類算法中相似度密度的計算方法；在此基礎上，給出了一種混合屬性數據集蟻群聚類算法。聚類分析結果表明，應用該算法能得出民族突發事件的發生規律，因此該算法可用于民族突發事件的應急智能輔助決策。該算法是應急預案自動生成等工作的基礎，明確給出了未來工作的內容、方法和步驟，為維護國家安全提供了智能化支持。 

關鍵詞：蟻群聚類算法；混合屬性數據；民族突發事件；智能輔助決策

中圖分類號：TP391 文獻標志碼：A

文章編號：10013695(2009)02050904



Application of ant colony clustering algorithm in aided intelligent decisionmaking for emergency related to ethnic groups 

YUN Jian1，2，LIU Yongkui1，HE Lijun1，CHEN Hua3，WANG Shuangcheng2，4

(1.College of Computer Science Technology， Dalian Nationalities University， Dalian Liaoning 116600， China;2.College of Humanities Communications， Shanghai Normal University， Shanghai 200234， China;3.Information Center， State Ethnic Affairs Commission， Beijing 100080， China;4.Minorities Normal College， Qinghai Normal University， Xining 810008， China)

Abstract:First，this paper denoted the numerical feature and categorical feature of emergencies related to ethnic groups by mixture data sets with mixed numerical and categorical values. Then， taking account of the particular contribution of different feature for cluster analysis，improved the calculation method of similarity function.Sequentially，proposed an ant colony clustering algorithm for mixture data sets.Cluster analysis result indicates that it can obtain the rules of emergencies related to ethnic groups by using this clustering algorithm. Therefore， this algorithm can be applied in aided intelligent decisionmaking for emergencies related to ethnic groups. This algorithm provides the groundwork for automatic generation for emergency response plan，and gives the content， method and steps of future research issues.The above work offers some effective intelligent supports for defending national security.

Key words:ant colony clustering algorithm; mixture data sets; emergency related to ethnic groups; aided intelligent decisionmaking 

0 引言

我國擁有56個民族，其中少數民族55個，少數民族人口數量超過1億，占全國人口的8.4%，分布在64%的國土面積上。所謂民族突發事件，即指涉及民族因素的群體性突發事件。近年來，我國民族突發事件的頻發度及危害性均呈上升趨勢。2007年2月27日，國務院正式發布了1949年以來首個專門就少數民族事業發展制定的《少數民族事業“十一五”規劃》。該規劃[1]在關于“繼續營造各民族和諧發展社會環境”主要任務的論述中明確指出，建立民族關系監測系統，制定處置涉及民族因素突發性事件應急預案；在關于“民族事務管理信息化建設工程”的論述中明確指出，建立以信息資源集成為基礎的統計、分析、評價、監測、預警和決策咨詢系統。2007年3月29日我國各大門戶網站均在顯著位置報道：中國將制定處置涉及民族因素突發性事件應急預案。綜合以上可見：民族突發事件的應急管理已經得到國家的高度重視，同時我國民族突發事件應急智能輔助決策的研究工作尚處在起步階段。民族突發事件復雜程度高、涉及因素多、應急決策難度大，加之我國民族地區與其他地區相比危機應對能力更差、危機承受能力更脆弱[2]。因此針對民族突發事件的智能輔助決策更加必要，其任務也日益緊迫。本文采用混合屬性數據集（即數值屬性和類屬性混合）表示民族突發事件，給出了一種可用于民族突發事件應急決策的混合屬性數據集蟻群自然聚類（不需要事先決定聚類數目）算法。通過聚類分析，可以得出民族突發事件的發生規律，進而提高決策效率和質量。同時，該算法也是應急預案自動生成的基礎。

1 民族突發事件的數據表示

為了提高對民族突發事件的應急處置能力，對民族突發事件進行準確的描述是非常必要的。根據能夠準確表達民族突發事件發生規律的各類涉及因素，對民族突發事件進行數據表示，為將民族突發事件的數據處理提升為對民族突發事件的知識發現做好準備工作。目前，民族突發事件的數據表示還沒有形成有價值并可以再利用的時空序列數據庫。因此，本文的研究屬于先期探索性工作。民族突發事件的數據表示需要民族問題領域專家的參與。在本文的研究過程中，筆者邀請了民族問題領域專家參與工作。經過對民族突發事件的分析，最終確定使用事件發生日期與時間、事件發生地點、事件民族特征、事件參與人數、事件人員傷亡人數、事件財產損失情況、事件緊急程度評估、事件誘因、事件處置效果評估九個對民族突發事件發生規律具有顯著刻畫作用的屬性作為聚類分析的基礎。這里，事件發生日期與時間可以轉換為數值屬性數據；事件發生地點可通過GIS系統支持轉換為橫縱坐標x，y的數值屬性數據；事件民族特征、事件緊急程度評估、事件誘因及事件處置效果評估均屬于類屬性數據。需要說明的是，與事件民族特征一定是在我國56個民族中取值一樣，筆者對事件緊急程度評估、事件誘因及事件處置效果評估等屬性都在民族問題領域專家的幫助下建立了詳盡的、互不交叉的、無二義性的類型屬性取值范圍。比如將事件緊急程度評估分為一般、較大、重大、特別重大。但這項工作政策性很強，為了維護我國民族政策的嚴肅性，同時又要保證可以準確表述研究結果，將實際表示結果作了如下處理：對數值屬性數據均以變量或變量＋數字或0表達；對類屬性數據以屬性英文名稱＋數字表達為主，如事件誘因中可使用cause31（以上兩處數字在本文表述中沒有排序或民族指示意義）。特別地，事件緊急程度評估的屬性為一般（普通）、較大、重大、特別重大，依次以class4、class3、class2、class1表達，該序號有排序意義；事件處置效果評估屬性為對民族突發事件處理中評估結論為“應急響應及時、措施得當、效果好，所采取的措施有借鑒意義”的等級記為evaluate1，其他等級依次記為evaluate2、evaluate3等，以上特殊處理沒有影響問題的本質。民族突發事件數據表示樣本表如表1所示（以三條記錄為例）。

表1 民族突發事件數據表示樣本表

日期時間地點x坐標地點y坐標民族特征參與人數

傷亡人數財產損失緊急程度事件誘因處置評估

樣本表中第一條記錄含義：該突發事件發生于d3（月日結合已經進行了數值化處理），具體發生時間是t2，發生地點的坐標為(x4，y4)，事件主要涉及民族ethnic1，共有p1人參與事件，沒有人員傷亡，財產損失w20，事件的誘因為cause31。該事件是一起普通的民族突發事件，處置結果評估結論是：應急響應及時、措施得當、效果好，所采取的措施有借鑒意義。2 蟻群聚類算法

在民族突發事件數據表示的基礎上，應用某種聚類算法進行聚類分析，可為民族突發事件發生規律的發現提供依據和定量支持。

2.1 蟻群聚類在分析民族突發事件時的優點

民族突發事件的數據集具有混合數據屬性，既包含數值也包含類屬值。由于類屬域的無序性，使得大多數聚類算法不能處理混合數據集，其原因是這些算法通過計算聚類的平均值來使代價函數最小化。只有少數聚類算法可以較好地解決該問題，如Kmode算法、Kprototypes算法[3，4]等，但這些算法假設聚類的數目已知，然而這一假設由于民族突發事件的高復雜度而實際難以滿足。

自然界中的螞蟻群體能夠完成單個螞蟻所無法勝任的工作。螞蟻群體的這種能力與它們的協同作用有關，人們受螞蟻等社會性昆蟲的啟發，已經設計了一系列蟻群算法[5]，蟻群聚類算法就是其中之一。蟻群聚類能夠自動確定聚類數目，避免了人工確定聚類數目的主觀性?；谙伻核惴ǖ木垲惙椒◤脑砩峡梢苑譃閮煞N：a）運用螞蟻覓食的原理，利用信息素來實現聚類[6]；b)基于蟻堆的形成原理實現數據聚類[7]。其中，基于蟻堆原理的蟻群聚類算法無須計算聚類的平均值，為處理混合數據集提供了可能。綜合以上分析，本文的研究認為基于蟻堆原理的蟻群聚類算法是處理民族突發事件混合屬性數據集的有效方法。

2.2 基于蟻堆原理的蟻群聚類算法

實驗表明：工蟻能在幾小時內將分散在蟻穴各處的大小不同的螞蟻尸體聚成幾類，小的蟻堆通過吸引螞蟻積攢更多的尸體來逐漸變大，這種正反饋會導致蟻堆逐漸越積越大，以達到聚類數據的目的。Deneubourg等人[7，8]提出了一種基本模型（basic model，BM），用來解釋螞蟻尸體堆積成螞蟻墓的行為，并模擬實現了蟻群的聚類過程?；灸Ｐ偷闹饕枷胧欠稚⒌膶ο蟊晃浵伿捌穑╬ickedup）并隨機移動，然后在與被拾起對象相似的對象附近放下（dropped）。Lumer等人[9]對Deneubourg的基本模型進行泛化，并應用于數據分析，提出了LF算法。LF算法不必預先指定簇的數目，并能構造任意形狀的簇。算法的主要思想是：先將所有多維屬性空間中的數據對象隨機地投影到二維網格平面上，然后在這個平面上產生一些虛擬螞蟻，每只螞蟻在二維平面上隨機選擇一個數據對象，隨即螞蟻計算該數據對象與鄰域半徑內其他數據對象之間在屬性空間中的相似性。如果不相似，螞蟻將數據對象拾起并隨機移往別處，然后再計算，直到移到與周圍對象相似的地方被放下，再隨機選擇下一個數據對象；如果相似，螞蟻不會拾起該數據對象，將隨機選擇下一個數據對象。這樣，數據對象被逐漸聚類。LF算法中對象之間在屬性空間中的相似度密度測量公式為

f(oi)=max{0，1/s2oj∈Neighs×s(r)[1-d(oi，oj)/α]}(1)

其中：Neighs×s（r）表示地點r周圍的以s為邊長的正方形局部區域；α為相似系數，它是相似度測量的關鍵系數，直接影響聚類中心的個數，同時也影響聚類算法的收斂速度[10]；d(oi，oj)表示對象oi和oj在屬性空間中的距離，用歐氏距離計算：

d(oi，oj)=tk=1(oik-ojk)2(2)

其中：t表示屬性個數。

LF算法給出了一種概率轉換函數的定義。一只無負載螞蟻拾起一個物體的概率為

pp(oi)=k1/[k1+f(oi)]2(3)

一只有負載的螞蟻，放下一個物體的概率為

pd(oi)=2f(oi)， f(oi)＜k2

1， f(oi)≥k2(4)

式(3)和(4)中k1，k2為閾值常量。LF算法中的k1，k2兩個參數意義不直觀，且沒有明確的取值范圍，給參數的選取帶來困難。文獻[11]進行了改進，選取對稱式sigmoid函數作為概率轉換函數。該函數具有非線性，運算中只需調整一個參數，且收斂性更快。概率轉換函數的定義為

pp(oi)=1-sigmoid(f(oi))(5)

pd(oi)=sigmoid(f(oi))(6)

式(5)和(6)中:

sigmoid(x)=（1-e-cx）/（1+e-cx）(7)

為自然指數形式，參數c越大，曲線飽和越快，算法收斂速度也越快。基于以上分析，本文的研究選取sigmoid函數作為概率轉換函數。

2.3 處理民族突發事件的混合屬性數據集蟻群聚類

民族突發事件數據集不僅包含數值屬性數據，還有類型屬性數據。傳統的基于歐氏距離計算d(oi，oj)的方法，難以滿足民族突發事件混合屬性數據集聚類要求。文獻[12，13]對d(oi，oj)的計算方法進行了改進。本文的研究在其基礎上給出了蟻群聚類中可滿足混合屬性數據集聚類要求的d(oi，oj)計算方法。設對象共有t個屬性，不失一般性，設其前m個屬性為數值屬性，其余為類型屬性。d(oi，oj)的改進計算公式如下：

d(oi，oj)=mk=1λk(oik-ojk)2+{1-[mk=1λk(oik×ojk)/

mk=1λk(oik)2×mk=1λk(ojk)2)]}+tk=m+1λkδ(oik，ojk)(8)

改進計算公式中對對象的數值屬性相似度計算使用了歐氏距離和余弦距離的線性組合，它們可以相互補償，保證d(oi，oj)中數值屬性成分始終起作用。式(8)中第三項是類屬性的相異匹配測度，δ(#8226;)定義為

δ（a，b）=0，a=b1，a≠b(9)

在Kprototypes算法中，雖然引入了權值λ來控制數值特征和類屬特征的比例，但是沒有考慮到每個屬性特征的重要程度，即數值特征集中每一個數值特征對分類的貢獻仍然被假設是均勻的；同樣，每一個類屬特征的貢獻也被假設是相同的。本文研究在式(8)中引入了屬性個體權重因子λk，以區分每個屬性特征對民族突發事件聚類的不同貢獻。λk的計算使用ReliefF算法，具體方法按文獻[14~16]給出的方案和計算公式。下面證明|mk=1λk(oik×ojk)/mk=1λk(oik)2×mk=1λk(ojk)2|≤1。

證明 令U=（λ1oi1，λ2oi2，…，λmoim），V=λ1oj1，λ2oj2，…，λmojm)，設sim(oi，oj)=

mk=1(oik×ojk)/

mk=1(oik)2×mk=1(ojk)2，顯然，|sim(oi，oj)|∈[0，1]，則

sim′(oi，oj)=[mk=1λk(oik×ojk)]/

mk=1λkoik2×mk=1λkojk2=

[mk=1(λkoik×λkojk)]/

mk=1(λkoik)2×mk=1(λkojk)2=sim(U，V)

而|sim(U，V)|∈[0，1]，因此有|sim′(oi，oj)|∈[0，1]。證畢。

3 蟻群聚類在民族突發事件應急決策中的應用

3.1 聚類算法流程與參數設定

3.1.1 聚類算法流程

應用于民族突發事件應急決策的聚類算法流程如圖1所示。

3.1.2 參數設定

蟻群聚類算法需要初始化許多參數，這些參數對算法的性能影響較大，但其選取的方法和原則目前尚無理論上的依據[17]。因此本文大部分的實驗參數是根據經驗并結合多次具體的仿真實驗調優確定的。主要參數設定列舉如下：螞蟻個數n=8；二維平面邊長L=80；迭代次數M=100 000；局部區域邊長s=4；相似性參數α=5；c的初值為1，每次迭代增加0.001，以利于加快識別離群點并使算法盡快收斂。

3.2 聚類在民族突發事件應急決策中的應用分析

3.2.1 具體聚類分析方法

使用本文提出的算法可以對民族突發事件的全部屬性進行聚類，但由于因素較多（即維數較高），基于全屬性聚類結果的規律分析不容易直觀表達。為了更直觀地表現算法對民族突發事件發生規律的有效挖掘，選取了民族突發事件中容易直觀表達的若干屬性進行聚類。在民族問題專家的幫助下，生成了具有普遍意義的包含500條記錄的民族突發事件樣本數據集。對該數據集的聚類分析以發生時間地點、誘發因素、緊急程度以及處置評估聚類分析為例進行。聚類結果如表2~5所示。

表2民族突發事件時間地點聚類分析表

以表2為例：d11、x11、y11分別表示在對民族突發事件時間地點聚類分析中第一類所有聚類點的時間中心值、地點橫縱坐標的中心值。另外，可以觀察到表中的聚類個數總和小于500，原因是在聚類過程中出現了離群點。離群點也很有研究價值，它可以發現民族突發事件中的特殊現象。民族突發事件的誘發因素十分復雜，有時一個民族突發事件在發生初期卻被當做普通的突發公共事件來處理，這往往會貽誤解決問題的最好時機。離群點分析也可以推廣到在普通的突發公共事件中實現對民族突發事件的挖掘。以上內容筆者將另文研究。

3.2.2 民族突發事件發生規律的得出

根據表2的聚類結果，可以得出以下結論：某地區民族突發事件多發生于d13、d12兩個時段，并相對集中發生在以(x13，y13)、(x12，y12)為中心的兩個地理區域。因此，有關部門應在上述時段、上述區域加強工作力度。根據表3的聚類結果可以得出以下結論：在(x28，y28)附近地理區域易發生誘因為cause16的民族突發事件；在(x22，y22)附近地理區域易發生誘因為cause50的民族突發事件，且以上區域事件頻發度明顯高于其他區域。因此，有關部門可以很快找到不同原因，在上述區域有針對性地開展工作，盡力解決cause16、cause50等誘發因素，力求事件頻發度的下降。根據表4的聚類結果可以得出以下結論：某地區總體民族關系狀況是好的，沒有大的糾紛，但在(x33，y33)附近區域發生了重大的民族突發事件，今后在(x33，y33)附近區域要大力加強民族突發事件的預警工作，有效防止突發事件的蔓延和擴大。根據表5的聚類結果可以得出以下結論：某地區的大部分區域對民族突發事件應急響應及時、措施得當、效果好，所采取的措施有借鑒意義，但(x44，y44)附近區域的民族突發事件處置措施還不完善，需要進一步改進；同時可以深入研究那些評估等級為evaluate1的應急預案，優中選優，作為應急預案的范本，為今后自動匹配生成初步的應急預案提供案例基礎。

4 結束語

給出的聚類算法較好地實現了對民族突發事件發生規律的知識發現，可為民族突發事件應急響應提供輔助決策支持。同時，該算法也是應急預案自動生成的基礎。為解決高度緊急的情況下，要求指揮人員迅速作出正確的應急決策難度大的問題，今后更深入的研究工作包括：a)形成真正意義上的大規模、有價值并可以再利用的民族突發事件時空序列數據庫；b)在聚類的基礎上，根據對已發生事件處置措施及效果的評估，為每類民族突發事件設立應急預案模板；c)實現對新發生事件的自動分類，使得指揮人員能夠快速、準確地得到新發生事件的隸屬關系；d)實現應急預案自動生成系統。系統根據對新發生事件的分類結果以及預先設立的應急預案模板，自動匹配生成初步的應急預案，經指揮人員調整后快速形成更完善的應急預案，以實現實時應急響應。實現對民族突發事件應急響應的智能化，已經成為一個事關國家長治久安、13億各族人民安居樂業的帶有全局性、戰略性和緊迫性的重大課題。本文的研究屬于先期探索性工作，旨在為維護民族團結、社會穩定和國家安全提供智能化支持。

參考文獻：

［1］

國務院辦公廳.少數民族事業“十一五”規劃［K］. 北京:人民出版社，2007.

［2］楊安華.民族地區突發事件與危機管理機制研究［J］.公共管理學報，2005，2(3):4248.

［3］HUANG Zhexue.Extensions to the Kmeans algorithm for clustering large data sets with categorical values[J].Data Mining and Know-ledge Discovery，1998，2(3):283304.

［4］BARBARA D，CHEN Ping.Using selfsimilarity to cluster large data sets[J].Data Mining and Knowledge Discovery，2003，7(2):123152.

［5］徐曉華， 陳崚.一種自適應的螞蟻聚類算法［J］.軟件學報，2006，17(9):18841889.

［6］楊新斌，孫京誥，黃道.一種進化聚類學習新方法［J］.計算機工程與應用，2003，39(15):6062.

［7］DENEUBOURG J L，GOSS S，FRANKS N，et al.The dynamics of collective sorting:robotlike ant and antlike robot[C]//Proc of the 1st Conference on Simulation of Adaptive Behavior:From Animals to Animats.Cambridge，MA:MIT Press，1991:356365.

［8］DORIGO M， BONABEAU E， THERAULAZ G. Ant algorithms and stigmergy[J].Future Generation Computer Systems，2000，16(8):851871.

［9］LUMER E， FAIETA B.Diversity and adaptation in populations of clustering ants[C]//Proc of the 3rd International Conference on Simu-lation of Adaptive Behavior: From Animals to a Nimats.Cambridge，MA:MIT Press，1994:501508.

［10］WU Bin， ZHENG Yi，LIU Shaohui，et al.CSIM:a document clustering algorithm based on swarm intelligence[C]//Proc of Congress on Evolutionary Computation.[S.l.]:IEEE Press，2002:477482. 

［11］YANG Yan，KAMEL M.Clustering ensemble using swarm intelligence[C]//Proc ofIEEE Swarm Intelligence Symposium.Piscataway，NJ:IEEE Service Center，2003:6571.

［12］段海濱.蟻群算法原理及其應用［M］. 北京:科學出版社，2005.

［13］李潔，高新波，焦李成.一種基于GA的混合屬性特征大數據集聚類算法［J］.電子與信息學報，2004，26(8):12031209.

［14］KONONENKO I.Estimating attributes:analysis and extensions of relief[C]//Proc of the 7th European Conference on Machine Learning.Berlin:Springer，1994:171182.

［15］KIRA K，RENDELL L A.A practical approach to feature selection[C]//Proc of the 9th International Workshop on Machine Learning.San Francisco，CA:Morgan Kaufmann，1992:249256.

［16］李潔，高新波，焦李成.基于特征加權的模糊聚類新算法[J].電子學報，2006，34(1):8992.

［17］DORIGO M，BLUM C. Ant colony optimization theory : a survey[J].Theoretical Computer Science，2005，344(2/3):243278.