基于分組模型的引力搜索智能大數據聚類方法

胡曉東，高嘉偉

(1.山西經濟管理干部學院 電子信息工程系，山西 太原 030024； 2.山西大學 計算機學院，山西 太原 030024)

0 引 言

數據聚簇是目前最為流行也最為重要的一種數據分析手段[1]，其目標是以數據對象集合分組的方式將其聚類成簇，使同一聚簇內的數據對象具有最大的相似性，即同質數據，而不同聚簇內的數據對象間具有最大的差異性，即異質數據[2]。數據聚簇廣泛應用于諸多領域，如機器學習[3]、模式識別[4]、圖像處理[5]、數據挖掘[6]等。

目前，受萬有引力定理和物體運動規律的啟發，一種基于隨機種群的元啟發式算法被提出，即引力搜索算法GSA[7]。GSA的設計初衷是求解連續最優化問題，與多數元啟發式算法相似，該算法擁有較好靈活性，且在加強搜索和開發能力的均衡性上表現突出。GSA的搜索策略是利用萬有引力定理將種群成員向著種群中最優的K個解移動。受該算法在變體最優化問題中的啟發，本文提出一種基于分組的GSA算法GGSA實現大數據的聚簇求解。提出的GGSA算法與標準的GSA具有兩個方面的不同。首先，算法設計一種分組編碼策略，將數據聚簇問題的相關結構映射為解的部分；其次，對于給定的聚簇編碼，適合于分組編碼的解的位置更新與速度更新公式在GGSA算法中被重新定義。為了評估GGSA算法在數據聚簇上的性能，選取了13種經典的數據集進行了測試。對于給定的D個聚簇的數據集，GGSA試圖通過隨機選擇的給定數據集的75%來尋找D個聚簇中心，這75%的數據集稱為GGSA的訓練數據集。而剩余的25%數據集則用于評估GGSA算法的性能，稱之為測試集，而分類失誤比率CEP則用于評估算法在測試集中的聚簇性能。

1 相關研究

數據聚簇方法已有很多研究，傳統的數據聚簇算法的分類主要以分層和分割的方式進行區分[8]。分層的聚簇算法主要以凝聚式模式或群集式模式遞歸尋找數據聚簇。凝聚式方法以單個數據對象作為一個分離聚簇，然后連續地合并最具最似性的聚簇直到滿足聚簇終止條件。群集式方法初始將所有數據對象視為一個聚簇，然后重復地分割每個聚簇為更小的聚簇，直到滿足終止條件。另一方面，分割式聚簇算法試圖在不構建分層結構的情況下同步尋找所有的聚簇。事實上，分割聚簇算法初始獲得的是不相交的聚簇集合，然后逐步提煉使其滿足最小化的預定義目標函數，其目標是在最小化聚簇間的聯系的同時最大化聚簇內的聯系性，從而實現最大化的數據緊密度，該方法也是本文的研究方法背景。

除了傳統的數據聚類方法以外，基于算法聚類標準的不同還有幾種聚類方法[9]。第一種是基于鄰居共享相同聚類的聚類算法，這類方法主要有基于密度的算法[10]和最近鄰鄰居方法[11]，前者根據對象密度進行聚類，后者則將近鄰對象歸屬于相同聚類中。雙聚類算法[12]同步通過行和列進行數據聚類，多目標聚類算法[13]則同步優化了數據集的不同特征進行聚類。重疊聚類算法[14]不同于多數的聚類算法，傳統算法中每個對象僅屬于一個聚類，而重疊聚類中每個對象可分屬于不同的聚類中，最具代表性的重疊聚類即為模糊C均值聚類算法[15]。

近年來，元啟發式方法廣泛應用在數據聚類問題中。從優化角度上看，聚類問題可建立模型為一類NP難的群組劃分問題[16]。這類算法需要搜索一個聚類的最優解，可以降低搜索過程陷入局部最優的風險。具體包括遺傳算法GA[17]、模擬退火算法SA[18]、禁忌搜索算法Tabu[19]、智能蜂群算法ABC[20]、貪婪隨機自適應搜索算法GRASP[21]、迭代局部搜索算法ILS[22]、可變鄰居搜索算法VNS[23]、蟻群算法ACO[24]、粒子群優化算法PSO[25]等。

引力搜索算法GSA是受牛頓的萬有引力定理的啟發而提出的一種元啟發式優化算法。算法中，搜索空間中的一個對象因為質量和重力的關系相互吸引，其吸引力與對象的質量成正比，而與距離的平方成反比。GSA已經被證明可應用于不同類型的優化方法中，包括數據聚類[26]、模糊系統識別[27]、分類問題[28]、排放負載分配[29]、風力渦輪控制[30]以及供電系統[31]中。然而，傳統的引力搜索算法直接應用于數據聚類問題時，在問題解的編碼機制和解的迭代更新機制上依然存在不足，會導致最優解的搜索過程過早收斂，本文將從這兩個方面進行改進，并驗證改進后的聚類算法性能。

2 數據聚簇問題

數據對象距離的度量是數據聚簇問題的關鍵，兩個不同的數據對象Oi和Oj間的相似性與特征空間S中的距離是密切相關的，而空間S中的距離度量常用方式是Euclidean歐氏距離。衡量聚簇結果質量的常用目標函數為考慮聚簇內聚度的二次誤差之和，可以評價一個給定數據分割的質量，定義為

(1)

(2)

式中：|Ci|代表聚簇Ci的基數，即聚簇i中數據對象的數目。

數據聚簇過程可以分為兩類：無監督聚簇和監督聚簇。無監督聚簇即自動式的聚簇，訓練數據集無需描述聚簇數目。而監督聚簇中訓練數據集合需要描述訓練目標和聚簇數目。本文所處理的數據集包括聚簇信息，因此，其優化目標是通過最小化目標函數尋找D個聚簇的中心，即最小化數據對象與其聚簇中心的距離之和。本文中，在訓練集OTrain上的一個聚簇C={C1,C2,…,CD}的適應度定義為

(3)

3 引力算法GSA

標準的引力搜索算法GSA是受牛頓萬有引力定理的啟發發展而來的，這種群體優化技術提供了一種模擬對象在多維空間中由于萬有引力影響帶來的相互關連的迭代方法。GSA的基本模型中，其初始目標是解決連續優化問題，即一個對象(代理agent)被引入D維解空間中，需要尋找最優解。GSA中的每個代理的位置代表問題的一個候選解，因此，每個代理可表示為問題解空間中的矢量Xi。擁有越好性能的代理將擁有更大的質量，由于更重的代理擁有更大的吸引半徑，因此擁有更大的吸引強度。在GSA的運行周期中，每個代理會連續調整其位置Xi，向著種群中最優的K個代理的位置移動。

為了詳細描述GSA，考慮一個擁有s個搜索代理的D維空間，空間中第i個代理的位置可定義為

(4)

(5)

(6)

其中，Mi(t)和fiti(t)分別代表時間t時代理i的質量值和適應度值，worst(t)和best(t)分別定義為

(7)

(8)

利用運行定律計算代理i的加速度為

(9)

其中：randj代表區間[0,1]內的均勻分布的隨機數；Rij(t)代表D維歐氏空間中兩個代理i與j間的歐氏距離；ε代表一個極小值，避免公式中的分母為0，即兩個代理i與j間的歐氏距離可能為0，但分母不能為0；Kbest代表擁有最優適應度值和最大質量值的最初的K個代理的集合，K代表時間的函數，算法開始時初始化為Kinitial，其值將隨著時間遞減；G(t)代表重力系數，擁有初始值Ginitial，其值也將隨著時間遞減至Gend，且

G(t)=G(Ginitial,Gend,t)

(10)

由此，代理i的速率更新可計算為當前速率的部分與其加速度之和，如式(11)，而代理i的位置更新可計算為式(12)

(11)

(12)

其中，rand代表區域[0,1]間的均勻分布的隨機值。

標準的GSA算法的過程如算法1所示。

算法1:GSA(1)generate the initial population(2)evaluate the fitness value for each agent(3)calculate the mass value for each agent(4)while stopping criteria is not satisfied do(5) update G, K and Kbest(6) calculate the acceleration of each agent(7) calculate the velocity of each agent(8) update the position of each agent(9) evaluate the fitness for each agent(10)calculate the mass value for each agent(11)end while(12)return best solution found

算法說明：步驟(1)進行種群初始化操作，生成約定數量部署于空間中的代理粒子，每個粒子代表求解問題的一個解；步驟(2)根據適應度函數(利用式(3)計算)對空間中的每個代理的適應度進行評估；步驟(3)利用式(6)計算每個代理的質量；步驟(4)～步驟(11)為算法的迭代求解過程，其中，步驟(5)利用式(10)更新相關參數，步驟(6)利用式(9)計算每個代理的加速度，步驟(7)利用式(11)計算每個代理的速率，步驟(8)利用式(12)更新每個代理在解空間中的位置，步驟(9)再次利用式(3)評估更新代理位置后代理的適應度，步驟(10)利用式(6)計算新的代理質量；最后，在經過約定次數的迭代操作后，在步驟(12)返回找到的最優代理，即問題的最優解。

在GSA中，參數K和G可以均衡算法在局部開發和全局搜索間的性能。為避免陷入局部最優，算法需要在初期迭代中利用搜索機制，而GSA算法可在初期利用較大的參數K值和G值完成搜索操作，即Kinitial和Ginitial必須較高。越大的參數K值可基于更多代理的位置加速代理在解空間中的移動，進而提升算法的搜索性能。同樣地，越大的G值也可以增加代理在解空間的移動能力，增加其搜索性能。Kinitial和Ginitial值越高，解空間中更好的區域可在算法迭代中更可能被識別。因此，隨著算法的迭代進行，GSA的搜索能力將減弱，開發能力將逐漸顯現。而降低參數K和G值可以提升其開發能力。越小的K值可基于更少的代理位置使代理在解空間中移動，進而提升其開發能力。同樣地，越小的G值則可以降低每個代理在解空間中的移動性能，增強其開發能力。因此，解空間中更好的區域在迭代中更有可能被開發出來。

4 基于分組模型的引力搜索算法GGSA

為求解大數據的聚簇問題，本文提出了一種基于分組的引力算法GGSA，算法考慮數據的聚簇結構設計了一種特定的聚簇編碼方式。在給定的編碼下，重新設計了代理的位置和速度更新公式。

4.1 解的編碼

問題解的表達必須適合且與處理的優化問題具有很好的關聯性，這樣易于搜索操作符的控制，從而降低對解的搜索中的時間和空間復雜度。GGSA算法中解的編碼利用一種分組表達方式，由兩個不同的部分構成：物品item部分和分組group部分。item部分由大小為n的數組構成(n代表數據對象的數目)，group部分由D個分組(聚簇)標簽的排列構成。item部分中的每個成員可以對應D個分組標簽中的任意一個，代表對應的物品可屬于給定標簽聚簇中。圖1描述了GGSA中一種基于分組的解的編碼示例，其中，數據聚簇問題O={O1,O2,O3,O4,O5}的一個解可表示為C={C1={O1,O3},C2={O2,O4,O5}}。

圖1 5個數據對象聚簇中由兩個聚簇構成的侯選解

利用標準的GSA優化一個連續函數時，通常每個解可表示為實值長度為D的矢量(D為空間中的搜索維度)，而每個值則對應一個變量。類似地，利用GGSA算法解決數據聚簇問題，由D個聚簇構成的一個解也可以表示為長度為聚簇數目的結構。換言之，GGSA算法中的分組group即為標準GSA中的變量，在第d個維度上對象的位置即代表第d個參數的值，它決定了該數據對象屬于第d個聚簇。本文中，在可行解X中聚簇數目以D表示。

分組編碼的屬性可以使解具有較低的冗余度。若問題的一個解擁有多個不同的編碼，則認為該編碼具有冗余度。在這種情況下，問題的解空間與算法的編碼空間之間的映射關系是一對多的關系。算法編碼冗余會擴大搜索空間，且無法適應搜索操作符的搜索過程，從而降低算法效率。

4.2 GGSA的公式更新

給定解的分組表達，本節的目標是重新定義式(9)、式(11)和式(12)，使得算法可以數據聚簇方式替代標準GSA中的標量方式。重定義等式的主要特征是使其可以在連續空間內運行。

為識別GSA的主要搜索操作符，假設代理構成的種群被初始化在問題的解空間中。若應用GSA求解優化問題，則算法會試圖在問題解空間中移動代理的位置，進而尋優?；谑?12)，這種代理位置的移動是通過典型的加“+”操作符實現的，它需要兩個輸入參數，即代理i的當前位置和代理的移動長度。然后，返回解空間的新位置作為輸出。代理i的移動長度即為其速度?；谑?11)，代理i的移動長度由兩類移動長度構成：獨立移動長度IML和依賴移動長度DML。IML為代理對其它代理位置未知僅對自身位置已知的情況下得到的移動長度，該移動長度僅取決于它先前的移動長度(或先前的速度)，本質上是先前移動長度的一部分。另外，DML是代理通過考慮Kbest集合中所有成員位置的情況下得到的移動長度。式(9)顯示了代理的DML的計算方式。根據式(9)，代理的DML取決于多個因素，包括：代理j的位置(j∈Kbest)，代理i與j間在第d個維度上的線性距離，代理i與j間的歐氏距離，代理j的質量值以及引力系數值。為了重新定義式(9)、式(11)和式(12)，使其可以分組的形式操作替代標量操作，需要重新定義3個操作符：線性距離操作符“-”、歐氏距離操作符以及移動操作符“+”。

標準GSA中，線性距離操作符量化的是兩個標量間的線性距離，該操作符需要重新定義使其能夠量化兩個數據聚簇間的距離。聚簇距離度量方式有多種，一種是聚簇間的最小距離，即兩個最鄰近成員間的距離；另一種是聚簇間的最大距離，即兩個相距最遠的成員間的距離。而k均值距離度量方式則是以成員與聚簇中心的距離來度量。本文設計一種基于杰卡德距離(Jaccard distance)的聚簇間距度量方法。令C1和C2為基數為|C1|和|C2|的兩個數據聚簇，聚簇C1和C2間的杰卡德距離定義為

(13)

式中：DistJ(C1,C2)代表兩個分組C1和C2間的差異度，它決定了兩個聚簇分離的遠近。如果有C1=C2，則差異度為0；如果有C1∩C2=?，則差異度為1。通常情況下，有0≤DistJ(C1,C2)≤1。

為重新定義歐氏距離操作符，GGSA算法將以聚簇操作代替標準GSA算法中的標量操作。換言之，類似于GSA，其代理在第d個維度上的位置代表d維變量的值，GGSA中代理的位置將決定數據屬于第d個聚簇。令C={C1,C2,…,CD}，C’={C’1,C’2,…,C’D}，表示數據對象的兩個候選聚簇，定義聚簇C和C’間的歐氏距離為

(14)

利用以上公式計算DistJ(.,.)時，距離計算之前需要適當對聚簇進行配對。為降低隨機聚簇配對的負面影響，算法需要重新對C和C’聚簇進行索引分配，使得最為相似的聚簇總能完成配對。本文使用一種最大權重雙向配對MWM方法進行聚簇的配對操作，MWM排序規則以一個擁有兩種結點的完全雙向相似圖開始進行聚簇配對，一種為源結點，一種為目標結點。每個源結點對應于C中的一個聚簇，每個目標結點對應于C’中的一個聚簇。兩個結點間的邊以結點間的相似度賦予一個權重值，該相似度即為杰卡德系數，為(|C1∩C2|/|C1∪C2|)。令Gb表示一個加權完全雙向相似圖，Gb中的配對即尋找未入射至任一普通結點的邊的子集。若屬于匹配的結點是一條邊的入射結點，則該匹配會覆蓋該結點。通過這種方式，尋找Gb中的具有最大權重和的匹配(即最大權重匹配)以及對C’中的聚簇重新進行索引分配(重新排序)，使得參與匹配的邊的雙方終止結點(聚簇)將擁有相同的索引，并且滿足C和C’中具有最相似的聚簇進行配對的目標。

(15)

(16)

4.3 GGSA的新解生成方法

GGSA算法利用兩階段生成新的解。第一個階段為繼承階段，即解Xi(t+1)可以繼承解Xi(t)的部分基因，這使得解Xi(t+1)可能會丟失部分物品Item。第二個階段為重新插入階段，該階段可以使得丟失的item可以重新插入已有的聚簇中。

(17)

算法2是GGSA中代理i在迭代t+1時生成新解的過程。

算法2：

(1)//MWM ordering rule (2)ford=1 to Ddo (3) pair cluster d of Xi(t) with the most similar cluster in Xj(t)(for all Xj(t)∈Kbest) by MWM pairing procedure (4)//Inheritance phase繼承階段 (5)calculate the value of EuclidianJ(Xi(t),Xj(t))(for all Xj(t) ∈Kbest) using Eq.(14) (6)for d=1 to Ddo (7) calculate the value of DistJ(xdj(t),xdi(t))(for all Xj(t)∈Kbest) using Eq.(13) (8) compute vdi(t+1) using Eq.(15) (9) calculate the value of ndi(t+1) by Eq.(17) (10) randomly select ndi(t+1) items fromcluster xdi(t) and allocate them to new cluster xdi(t+1) (11)end for (12)//Reinsertion phase重新插入階段 (13)for each data Oj that have not been selected in the inheritance phase do (14) allocate data Oj to an existing cluster with the closest center (15)output: solution Xi(t+1)

5 仿真實驗

5.1 實驗環境配置

本節利用UCI數據庫[32]中13種實際的測試數據集對算法性能進行仿真測試，所選取的測試數據集涵蓋了低、中和高維度的數據實例，后文中首先描述了所選的13種經典數據集的特征，然后同另外4種啟發式數據聚簇算法進行仿真測試。

本文利用提出的算法求解了不同測試數據集的聚簇問題，算法利用C語言編程實現，硬件環境為2.2 GHz的Intel CPU。算法運行中的固定參數設置如下：數據對象數量s設置為20，K的初始值Kinitial設置為10，G的初始值Ginitial設置為1，G的終止值Gend設置為0.5，算法的最大迭代次數設置為200。同時，兩種基于時間的線性函數用于降低參數G和K的值。

5.2 性能評價指標

對于每一個數據集，實驗首先記錄了算法聚簇后的分類失誤比率指標CEP，該指標表示測試集中錯誤分類的數據比率，其計算方法如下：首先，對全部測試數據進行分類，并統計錯誤分類的數據量。由于對于特定的測試數據集，每個數據實例的實際分類標簽是可以提前知道的。然后，錯誤分類的數據量與測試集中總的數據實例數量相除，并乘以100即可得到百分比，即計算方式為

除此之外，進一步引入聚類內的距離之和度量聚類算法的性能，該指標表示一個聚類內的數據矢量與聚類質心間的距離。聚類內距離之和越小，表明數據聚類結果的質量越高。定義為

其中，zj表示聚類j的質心質量，xp表示第p個數據矢量，d表示每個質心矢量的特征量，nj表示聚類j的數據矢量數量，Cj表示形成聚類j的數據矢量的子集。

5.3 數據集描述

本文所選取的13種測試數據集為機器學習領域最為常用的測試數據，表1顯示了測試數據集的特征，包括數據實例數量、數據特征數量以及分類數量。每一個數據集中，隨機選擇75%的數據用于訓練集的訓練過程，剩余25%的數據用于算法的測試過程。表1同時給出了訓練和測試集的數量。訓練階段后，可以獲得聚簇中心作為從訓練集中提煉出來的知識而用于分類測試集。

表1 13種測試數據集的特征

5.4 結果分析

算法在13種經典的測試數據集中進行了測試，其生成的計算結果與以下幾種典型的元啟發式算法進行了性能對比，包括：標準引力搜索算法GSA[33]、智能蜂群算法ABC[34]、粒子群算法PSO[35]以及螢火蟲算法FA[36]，對比結果見表2。

表2 算法的分類失誤比率

表2表明，在所有測試數據集，本文算法GGSA優于PSO和標準GSA，在其中10個數據集，GGSA優于ABC，而在其它3種數據集中，ABC和GGSA幾乎表現出相同的性能。對比FA算法，GGSA也得到了可接受的結果，僅在數據集Cancer、Heart和Thyriod中，FA要優于GGSA。而且，對于所有測試集，GGSA的平均CEP為8.9%，而FA為11.36%，標準GSA為11.41%，ABC為13.13%，PSO為15.99%。由表2的最后一行的平均值可以看到，本文的GGSA算法是5種元啟發式算法中排序第一的算法。

表3為5種數據聚類算法在所有數據集中的聚類內距離測試結果。所記錄的值為20次仿真實驗測試得到的平均值。可以看到，本文基于分組模型的引力搜索機制下的數據聚類算法得到的聚類內距離的均值是小于其它4種算法的，且在不同的測試數據集中得到的結果均體現出了一定的優勢，這說明算法在處理不同屬性和不同分類量的數據集時具有很好的適應性和魯棒性。其它4種算法之間，并沒有體現出在不同測試數據集下的絕對性能優勢，即在不同數據集上得到的聚類距離的差距是不一致的。如FA算法在Balance、Cancer-Int、Thyroid等數據集中是除了GGSA算法之外表現最好的一種算法，但它在其它數據集中得到的測試結果不是最優的，這說明算法在處理具有不同特征的數據時并不能保證性能的穩定性。

表3 算法的聚類內距離度量

6 結束語

為求解數據聚簇問題，提出一種基于分組的引力搜索算法GGSA。該算法在解決數據聚簇上的優勢在于：首先，基于分組模型的解的編碼方式最大限度降低的編碼的冗余度，使數據聚簇問題的相關結構與引力搜索空間中解間映射關系得到了最好的表達；其次，算法中搜索代理的位置與速度更新機制與標準GSA是類似的，但利用了基于差異的分組因子替換了標準GSA中的算術操作符。聚簇差異性度量的使用允許算法以聚簇操作代替原始的標量操作。通過仿真實驗的評估，驗證了基于分組的GSA算法在分類失誤比率指標上要優于同類型的幾種數據聚簇算法。