基于引力搜索機制的數據聚類及特征選擇算法

張雪峰，杜孝平，王曉健，王 哲

(1.北京賽迪工業和信息化工程監理中心有限公司 信息化管理與咨詢部，北京 100048；2.北京航空航天大學 軟件學院，北京 100191；3.湘潭大學 信息工程學院，湖南 湘潭 411105)

0 引 言

數據聚類是將未標記數據集分割為相似數據點群組，每個群組為一個聚類，其內的數據點具有最大相似性，而不同聚類間數據點差異較大[1]。數據聚類在圖像分割[2]、機器學習[3]、文本分析、模式識別[4]等方面得到了廣泛應用。目前數據聚類方法有兩類：分層式方法和分割式方法。分層式方法的主要不足是：①靜態屬性，即數據點的移動受限于分配的所屬聚類內；②重疊聚類無法分離。分割式方法旨在將數據劃分為不相交聚類集，該方法也是本文采用的聚類方法。

多數分割聚類方法在聚類過程中給予所有特征相同重要性。但部分特征實際是不相關或冗余的，這在處理高維度數據集聚類時尤其無法得到較好聚類結果[5]。因此，有必要選擇使數據聚類更適宜的相關特征。此外，獲得最優聚類數量也是分割聚類的另一挑戰。求解數據聚類問題必須同步選擇相關特征和最優聚類數量[6]。為解決該問題，本文利用引力搜索機制設計一種自動式聚類和特征選擇算法。算法試圖在沒有聚類數量先驗知識前提下，同步決策聚類數量和相關特征。設計了一種復合代理表示方法，用于分別對聚類和特征進行編碼。同時，設計了一種臨界值概念用于尋找最優聚類數量和特征。最后通過9種數據示例集測試驗證了算法的有效性和可行性。

1 相關工作

本小節同時對特征選擇和聚類問題的相關工作做概述性研究。K-means算法是最早的一種經典數據聚類算法[7]，由于其最終解過多依賴于初始的質心選擇，因此較容易存在嚴重的局部最優情況。文獻[8]提出一種基于改進和聲搜索的聚類算法，將狀態反饋機制引入到和聲搜索算法中，通過判斷和聲記憶庫中最優和聲和最差和聲之間的差異來動態調整和聲記憶庫考慮概率和移動步長，使算法能夠快速地收斂到全局最優解。文獻[9]提出一種基于蟻群優化思想的聚類和特征選擇算法FS_ACO。算法使用了基于包裝的思路，并利用連續回溯選擇技術實現特征提取。文獻[10]提出基于粒子群優化的數據聚類和特征選擇算法CFS_PSO。文獻通過隨機化特征選擇機制改進了粒子群的搜索行為，以此選擇相關特征，而聚類解則在所選特征的基礎上進行迭代求解。文獻[11]提出一種模因算法NMA_CFS尋找數據聚類和特征選擇解，利用了局部搜索機制在編碼染色體中提煉數據聚類，但種群多樣性的不足使得算法會出現早熟，從而收斂在局部最優解上。文獻[12]設計了一種自冶的和聲搜索聚類算法HS_CFS，算法針對模糊聚類對初值和聚類中心的依賴性，采用和聲搜索尋找最佳聚類質心，并且改進了和聲搜索的調音概率和隨機帶寬，加速了算法收斂。文獻[13]則提出改進文化基因聚類算法INMA_CFS，首先，基于特征與標記間的依賴將特征按照適應度進行排名，使用遺傳搜索建立多標記類；然后使用局部優化方案向被選的特征集中增加精英樣本或刪除較弱樣本。對部分基因進行改良，且在搜索過程中逐漸改變優化操作的次數，從而降低了整體計算成本。以上算法并沒有考慮到數據集的變異特征，該特征是一種統計屬性，且極大取決于數據點及其特征的數量。而數據聚類數量又直接或間接地取決于特征數量，給定數據集,其冗余特征可能影響聚類性能。因此，識別和尋找相關特征對于數據聚類過程具有關鍵影響。

以上研究概述表明元啟發式方法是選擇數據特征和同步數據聚類的有效手段，但以上方法并沒有考慮到數據集的變化特點(統計屬性)，該屬性直接取決于特征選擇的數量和數據點。而聚類數量直接或間接取決于特征數量，在給定數據集中的冗余特征可能一定程度上會影響聚類算法的性能。因此，盡可能選擇相關特征剔除冗余特征是至關重要的。鑒于引力搜索算法所依賴的初始參數數量較其它智能群體算法更少，選擇該算法作為特征選擇和聚類的優化手段將具有一定可行性。

2 數據聚類與引力搜索模型

2.1 數據聚類模型

(1)每個聚類擁有至少一個數據點，即Cg≠?,g=1,2,…,K；

(2)兩個不相似的聚類不存在共同的數據點，即Cg∩Ch=?,g,h=1,2,…,K，且g≠h；

數據點是否屬于某一個特定聚類內取決于其相似性，該相似性通常以數據點與聚類中心的歐氏距離度量。數據點xl與聚類Cg的聚類中心mg的歐氏距離定義為

(1)

2.2 引力搜索算法模型

引力搜索算法GSA[14]是基于萬有引力和物體質量間的相互影響發展來的一種元啟發式算法。GSA中，給定問題的可能解考慮為代理集合，代理的質量決定代理的性能。由于引力的影響，代理之間會相互吸引，導致代理會朝著擁有更大質量的代理進行全局移動。問題的解即對應于代理在空間中的位置，適應度函數則決定了代理的慣性質量。GSA的執行步驟如下：

步驟1 代理初始化。隨機初始化P個代理位置為

(2)

步驟2 適應度評估，計算最優適應度。對于所有代理，計算每次迭代中的適應度。最優和最差適應度的計算方法為(對于最大化問題)

(3)

(4)

其中，fitnessi(T)表示代理i時刻T的適應度，Best(T)和Worst(T)分別表示時刻T所有代理中的最優適應度和最差適應度。

步驟3 計算引力常量。時間t時的引力常量表示為Gc(t)，定義為

(5)

式中：G0和α為常量，Tmax為最大迭代次數。

步驟4 計算代理的引力質量。時間T時代理i的引力質量表示為Massi(T)，基于當前種群的適應度進行計算

(6)

其中

(7)

步驟5 計算代理引力和加速度。時間T時在維度D上代理i受到代理j的引力定義為

(8)

(9)

步驟6 代理位置和速度更新。下一迭代T+1時代理的位置和速度可計算為

(10)

(11)

步驟7 終止條件。重復步驟2～步驟6，直接迭代過程達到最大迭代次數為止。

3 算法詳細設計

本節的主要工作是設計一種基于引力搜索機制的數據聚類與特征選擇算法。首先，提出一種變量合成代理表示策略使得算法可以同步尋找最優的聚類和特征數量，然后，為每個聚類中心和特征選擇設計了一種臨界值機制，代理通過相應的臨界值可以對聚類中心和特征進行編碼，最后通過引力搜索的迭代過程，不斷評估代理的適應度，最終得到最優的聚類和特征選擇。

3.1 基于引力搜索的數據聚類與特征選擇算法GSA_CFS

GSA_CFS算法步驟如下：

步驟1 初始化算法參數，包括代理(種群)數量、最大聚類數量Kmax(由式(12)計算)以及最大迭代次數；

步驟2 生成每個代理，使其包括Kmax個聚類中心數、Kmax+D個主動臨界值，其中，D代表每個數據點的維度(見3.1.1節)。初始時，聚類中心和主動臨界值隨機產生。

步驟3 重復以下步驟，直到滿足終止條件：

(1)通過評估選擇臨界值(見3.1.4節)，尋找每個代理的主動聚類中心和特征；

(2)對于每個數據點，計算其與代理i的每個主動聚類中心的歐氏距離；

(3)分配數據點至距離最小的聚類中；

(4)如果沒有數據點分配至一個聚類中，則通過3.1.5節中的方法重新計算聚類中心；

(5)利用GSA算法修改代理，通過代理的適應度值指導代理搜索過程；

(6)分配選擇臨界值至每個聚類及聚類中的每個特征，選擇臨界值基于修改的代理進行計算，見3.1.2節；

(7)基于部署(3)～(6)計算的選擇臨界值計算聚類中心和特征的截止臨界值；

步驟4 在最后一次迭代中，最優代理將提供最優的特征子集和聚類中心以及聚類數量。

3.1.1 代理表示及初始化

算法利用一種變量合成代理表示策略對擁有不同聚類數量的特征和聚類中心進行編碼。算法中，對于N個數據點，一個代理由維度為(Kmax+D)+(Kmax×D)的實數矢量組成，每個數據點擁有D個維度，最大聚類數量為Kmax。此時，聚類數量的上限值為Kmax，等于給定數據集中數據點的數量的開方

(12)

第一部分(Kmax+D)由兩個記錄Kmax和D組成，所分配的值為[0,1]間的正實數值。第一個記錄Kmax的值用于對聚類過程中對應的聚類是否被激活進行決策，第二個記錄D的值表明是否對應的特征被激活。第二部分(Kmax×D)表示維度D中每個維度上的Kmax個聚類中心。在特定時間t時代理i的矢量表示為圖1所示，此時，i代表種群規模，i=1,2,…,P。

圖1 代理編碼表示

其中，mcij為代理i的第j個聚類中心，TCij為聚類中心mcij對應的臨界值，TFij為代理i的每個聚類中第j個特征的臨界值，TCij和TFij分別表示選擇活躍聚類中心和特征時的選擇臨界值。以下以一個實例對其說明：

實例1：令Kmax=4，D=3，即最大聚類數量為4，空間為3維。代理編碼如圖2所示。

圖2 實例1

矢量中的前4個記錄(0.6,0.7,0.4,0.3)代表對應4個聚類的聚類選擇臨界值，后面的3個記錄(0.7,0.3,0.8)表示特征選擇臨界值(由于每個聚類擁有3個特征)。剩余的記錄表示4個聚類中心，即(4.9,3.2,1.6)、(5.7,4.4,1.0)、(6.9,3.0,4.9)和(7.7,3.1,2.4)。

3.1.2 臨界值計算

聚類數量本質上對應于給定數據集的變化。因此，對于聚類中心的選擇臨界值定義為

(13)

對應于每個聚類的相同特征與所有聚類間的關聯通過以下公式計算

(14)

式中：TFq表示數據集中第q個特征的臨界值，Vrq表示數據集中第q個特征的方差，Vrq,i表示第i個聚類中特征q的方差，K代表數據集的聚類數量。

TFq描述聚類結構中特征q的重要性均值，該值接近于1，表明當前解中的所有聚類在該特征下相互遠離，使其可用于決定聚類結構。

3.1.3 截止臨界值計算

聚類選擇的截止臨界值定義為

(15)

類似地，特征選擇的截止臨界值定義為

(16)

算法開始時，截止臨界值Tcutoff_center和Tcutoff_feature均設置為0.5。

實例2：實例1中代理的聚類中心和特征選擇分別為(0.6,0.7,0.4,0.3)和(0.7,0.3,0.8)，基于以上截止臨界值概念，Tcutoff_center和Tcutoff_feature分別為0.5和0.6。

3.1.4 活躍聚類中心及特征提取

代理中的聚類中心和特征選擇是基于相應的截止臨界值的，即Tcutoff_center和Tcutoff_feature。若聚類中心的臨界值TCij大于Tcutoff_center，則相應的聚類中心mij被選擇分割數據集合；否則，不被選擇。活躍聚類中心提取規則如下：

若TCij>Tcutoff_center，則代理i的聚類中心j是活躍的，即mij是活躍的，否則，聚類中心j不活躍；此時，TCij代表代理i的第j個聚類中心，Tcutoff_center為聚類中心的截止臨界值。

類似地，活躍特征提取規則如下：

若TFij>Tcutoff_feature，則代理i的每個聚類中心的特征j是活躍的，否則，特征j不活躍。此時，TFij代表代理i的第j個特征，Tcutoff_feature為特征的截止臨界值。

若在GSA算法執行過程中，不存在任一臨界值大于截止臨界值，則隨機選擇兩個臨界值并初始化至大于截止臨界值。

實例3：實例1中代理的聚類中心和特征選擇臨界值分別為(0.6,0.7,0.4,0.3)和(0.7,0.3,0.8)，實例2中的聚類中心截止臨界值Tcutoff_center和特征截止臨界值Tcutoff_feature分別為0.5和0.6。首先，聚類中心臨界值用于選擇給定數據集的聚類數量，根據以上提出的規則，僅有兩個聚類中心的臨界值(0.6和0.7)大于0.5，且對應的活躍聚類中心為(4.9,3.2,1.6)和(5.7,4.4,1.0)。活躍聚類中心圓形區域部分，如圖3所示。然后，特征選擇臨界值用于從對應的活躍聚類中選擇重要的特征形式，此時，兩個特征選擇的臨界值(0.7和0.8)大于截止臨界值0.6，則在每個活躍聚類中心中的第一個和第三個特征被選擇，即粗體部分。

圖3 實例3

3.1.5 聚類中心確認

有可能一個特定聚類不存在任一數據點，即可能出現空聚類。在一個聚類中心超過分布點的邊界時會出現這種情況。該問題可以通過重新對特定代理的聚類中心進行重新初始化解決。現在分配n/K個數據點至每個聚類中心，使得每個數據點被分配至離其最近的特定聚類中。

實例4：考慮三維特征空間中擁有150個數據點的數據集，活躍聚類數量為3。假設一個特定代理的聚類中心為((1.9,0.52,-0.02),(5.0,4.1,0.9),(7.1,2.2,1.8))。沒有任一數據點分配至聚類中心(1.9,0.52,-0.02)，由于該中心處于數據點分布的邊界以外。基于以上提到的平均計算公式n/K，即30個數據點被分配至最近的聚類中心。因此，最新形成的聚類中心為(4.128,3.269,1.601),(3.900,2.832,1.266)和(5.789,3.456,0.976)。

3.1.6 適應度計算

聚類算法的性能取決于聚類標準。本文選擇I-index指標對聚類算法性能做出評估，定義為

(17)

(18)

(19)

其中，K為分割數據集所選的聚類數量，P值取2。I-index取值越高，聚類解的質量越好。

本文研究了與聚類和特定數量相關的兩個優化問題，并將其合并至I-index中。

問題1：尋找最優的聚類數量。本文通過考慮Kmax的影響，設計了以下懲罰函數

Penality1=Kmax-K

(20)

該懲罰函數偏好更少的聚類數量，它與(Kmax-K)成比例。

問題2：尋找最優的特征數量。多數的聚類指標沒有考慮合適的特征數量。特征選擇即從所有特征量中選擇d個特征D。保留重要特征有助于確保聚類性能，為了降低特征數量對性能的影響，引入另一懲罰函數

(21)

結合以上定義，聚類評估指標可定義為

fitness=I(K)×Penality1×Penality2

(22)

(23)

3.2 復雜度分析

(1)算法的初始化時間復雜度為O(agentsize×stringlength)，agentsize為代理數量，stringlength為每個編碼代理的長度，而stringlength則為O((Kmax+D)+(Kmax×D))，D為數據集的維度，Kmax為最大聚類數量。

(2)算法的活躍聚類和特征提取時間復雜度為O(agentsize×Kmax×D)。

(3)適應度計算包括3步：數據點至不同聚類的分配對于每個代理的時間為O(n2×Kmax)，聚類中心更新時間為O(Kmax)，適應度計算的時間為O(n×Kmax)。算法的步驟3需要在所有代理上遞歸，即3個子步驟乘以agentsize次。因此，步驟3的總體時間要求(計算適應度)為agentsize×(n2×Kmax+Kmax+n×Kmax)=O(agentsize×n2×Kmax)。

(4)算法的代理質量計算時間為O(agentsize×stringlength)。

(5)算法的加速度計算時間為O(agentsize×stringlength)。

(6)算法的代理速度和位置更新計算時間為O(agentsize×stringlength)。

綜上，若stringlength遠小于n，則每次迭代的時間復雜度為O(agentsize×n2×Kmax)，算法的總體時間復雜度則為O(agentsize×n2×Kmax×Maxgen)，Maxgen即為最大代數。

4 仿真實驗

4.1 環境搭建

GSA_CFS算法的運行與多個不同的控制參數相關，包括：代理數量P、最大迭代次數Maxgen和引力常量G0。實驗中設置P=30，Maxgen=100，G0=100。參數固定后，算法運行20次并取結果的平均值進行性能評估。引用UCI數據庫中8種實際的測試數據集對算法性能進行仿真測試，所選取的測試數據集涵蓋了低、中和高維度的數據實例，表1描述了所選的8種經典數據集的特征，然后同其它數據聚類算法進行仿真測試。

表1 測試數據集相關描述

4.2 特征選擇的相關性

所選特征的價值可以通過特征選擇的頻率和調和分值LS確定。特征選擇的頻率定義為

(24)

式中：分子表示特定特征在算法運行中被選擇的次數，分母表示算法實施聚類獨立運行的次數。表2是GAS_CFS算法得到的不同數據集中特征選擇的頻率和LS情況。可以看到，對于Iris數據集，GAS_CFS算法非常頻繁地選擇了特征量3和4，該特征也擁有較高的LS值。對于Wine數據集，GAS_CFS算法頻繁選擇了特征量1、6、7和13。類似地，對于Glass，1、3、4、7是最頻繁的特征選擇。對于Haberman，最頻繁的特征選擇是1和3。其它數據集的特征量選擇結果也可以依次看出。

表2 特征選擇頻率及其LS值

4.3 聚類選擇的相關性

為了區分不同聚類的重要性，需要計算所選聚類數量的頻率及其對應的聚類準確率Ac。聚類頻率計算為

(25)

式中：分子表示特定聚類在算法運行中被選擇的次數，分母表示算法實施聚類獨立運行的次數。表3是GAS_CFS算法得到的不同數據集中聚類選擇的頻率及其聚類準確率Ac的情況。對于Iris數據集，算法生成了3個聚類，對應的聚類準確率較高。對于Wine，算法也生成了3個聚類。對于Glass，生成聚類數量較為頻繁的是5和6個。對于Haberman則最為頻繁的聚類數是2。其它數據集的聚類量選擇結果及聚類準確率也可以依次看出。

表3 聚類選擇頻率及聚類準確率

4.4 同類型算法的性能對比

選擇7種典型的數據聚類算法進行性能對比，包括：K均值算法K-means[7]、改進的和聲搜索聚類算法MHSC[8]、基于蟻群優化的特征選擇與聚類算法FS_ACO[9]、基于粒子群優化的特征選擇與聚類算法CFS_PSO[10]、基于文化基因算法的聚類算法NMA_CFS[11]、自冶和聲搜索聚類算法HS_CFS[12]以及改進文化基因聚類算法INMA_CFS[13]。算法的最大迭代次數和種群規模分別設置為500和30，每個數據集按序運行20次，聚類質量的度量根據平均值和標準方差進行衡量，以展示算法的魯棒性。表4是相關對比算法的主要參數設置。

表4 對比算法的相關參數設置

表5給出所有測試數據集中算法得到的聚類數量、特征數量及聚類準確率的均值結果。

表5 性能比較結果

對于Iris，GSA_CFS擁有最優的聚類準確率，然后依次是HS_CFS、NMA_CFS、CFS_PSO、INMA_CFS、FS_ACO、MHSC、K-Means。GSA_CFS、INMA_CFS、NMA_CFS、CFS_PSO、FS_ACO和HS_CFS都可以正確聚類數量和特征，而本文算法則在每次運行過程均選擇了特征量3和4。

對于Wine，GSA_CFS獲得了比其它算法更高的聚類準確率，其聚類數量為3，NMA_CFS、CFS_PSO、FS_ACO和HS_CFS選擇的特征數量為6，而INMA_CFS生成了7個特征，而本文算法找到的最佳特征量為4。

對于Glass數據集，所有聚類算法產生的聚類數量均為6，INMA_CFS、NMA_CFS、CFS_PSO、FS_ACO和GSA_CFS得到的特征數量均為4。然而，HS_CFS的特征數量為3，本文算法則比其它算法提供了改進效果更好的聚類準確率。

對于Haberman數據集，本文算法的聚類準確率為62.5%，HS_CFS和NMA_CFS分別為56.9%和55.8%。FS_ACO、CFS_PSO和HS_CFS生成的特征數量為2。INMA_CFS、NMA_CFS與本文算法在聚類和特征數量上得到相似的結果。

對于Bupa數據集，GSA_CFS算法得到的聚類量和特征量均為2，而NMA_CFS、FS_ACO、CFS_PSO和HS_CFS提供了不同準確的聚類量。HS_CFS得到的特征量為2。顯然，本文算法在聚類和特征量的聚類準確率要高于其它算法。

對于Cancer數據集，所有算法均得到了準確的聚類和特征，但聚類準確率上本文算法是高于其它算法的。對于Vowel和CMC數據集，GSA_CFS得到了最佳的聚類準確率，其它依次是HS_CFS、FS_ACO、CFS_PSO、NMA_CFS、INMA_CFS、MHSC以及K-Means算法。

5 結束語

設計了一種基于引力搜索機制的數據聚類與特征選擇算法。首先，提出一種變量合成代理表示策略使得算法可以同步尋找最優的聚類和特征數量，然后，為每個聚類中心和特征選擇設計了一種臨界值機制，代理通過相應的臨界值可以對聚類中心和特征進行編碼，最后通過引力搜索的迭代過程，不斷評估代理的適應度，最終得到最優的聚類和特征選擇。