基于增強(qiáng)重引力搜索的高維數(shù)據(jù)協(xié)同聚類算法

桑 遙 尹 君 王 迪 王 皓 景 康

1(國網(wǎng)新疆電力有限公司烏魯木齊供電公司 新疆 烏魯木齊 830002) 2(新疆電力有限公司信息通信公司 新疆 烏魯木齊 830018)

0 引 言

聚類處理將物理或抽象的數(shù)據(jù)對象按指定的相似性度量歸納，是沒有先驗知識情況下的一種重要數(shù)據(jù)挖掘技術(shù)[1]?，F(xiàn)有的聚類技術(shù)按采用的基本思想主要可分為4類[2]，即層次聚類算法、分割聚類算法、機(jī)器學(xué)習(xí)的聚類算法和高維數(shù)據(jù)聚類算法。層次聚類算法將數(shù)據(jù)組織成若干類構(gòu)成一個樹狀結(jié)構(gòu)來進(jìn)行聚類處理。分割聚類算法首先將數(shù)據(jù)點集劃分為若干個子集，再通過控制策略對各個子集分別做聚類優(yōu)化處理。機(jī)器學(xué)習(xí)的聚類算法[3]主要采用人工神經(jīng)網(wǎng)絡(luò)、進(jìn)化學(xué)習(xí)等理論處理聚類問題，通過機(jī)器學(xué)習(xí)的自學(xué)習(xí)能力對聚類準(zhǔn)則進(jìn)行優(yōu)化處理。高維數(shù)據(jù)的特征空間中存在大量的不相關(guān)屬性[4]，且高維數(shù)據(jù)間的分界較為模糊，因此高維數(shù)據(jù)的聚類處理需要結(jié)合降維處理[5]、子空間聚類[6]或協(xié)同聚類處理[7]等。

協(xié)同聚類[8-9]處理是高維數(shù)據(jù)聚類領(lǐng)域的一種有效方案，協(xié)同聚類對數(shù)據(jù)點和特征集同時進(jìn)行聚類，以特征子集引導(dǎo)數(shù)據(jù)點的聚類過程，能提高聚類的效率和準(zhǔn)確率。協(xié)同聚類技術(shù)能夠提高對高維數(shù)據(jù)的聚類效果[10-11]，因此本文采用協(xié)同聚類技術(shù)解決高維數(shù)據(jù)聚類的問題。重引力搜索能夠高效地解決某些特定情況下的優(yōu)化問題，尤其對于高維優(yōu)化問題具有獨特的優(yōu)勢[12]，因此本文采用重引力搜索解決高維數(shù)據(jù)的聚類問題。針對重引力搜索存在局部開發(fā)能力不足的問題，本文設(shè)計擬牛頓法的局部開發(fā)策略，提高重引力搜索的求解質(zhì)量。

1 協(xié)同相似性的問題模型

首先以一個實例介紹協(xié)同相似性的問題模型。表1是一個矩陣實例，圖1是表1對應(yīng)的二部圖。理想情況下，d1-d3為第1行，d4-d5為第2行，c1-c3為第1列，c4-c6為第2列。假設(shè)一個文檔為d1，且d1與d2相似，但與d3不相似，而d2與d3關(guān)于c3相似。列c1和c3均存在于d2中，因此c1與c3相似。根據(jù)二部圖可推導(dǎo)出d1和d3間的相似性路徑：d1→c1→d2→c3→d3。設(shè)Rij和Cij分別表示目標(biāo)i、j間的相似性和列i、j間的相似性，相似性路徑改寫為d1→Cij→d3。因此協(xié)同相似性矩陣具有以下屬性：如果列相似，那么包含該列的行也相似；如果行相似，那么該行的列也相似。

表1 一個矩陣的實例

圖1 表1實例的二部圖結(jié)構(gòu)

采用Chi-Sim[13]度量相似性。設(shè)n×n的矩陣R和m×m的矩陣C分別表示行間相似性和列間相似性。開始階段樣本或特征的相似性為未知信息，因此將R和C初始化為單位矩陣，即R=In×n和C=Im×m。算法迭代更新R和C，設(shè)R(i)和C(i)分別表示迭代i次的矩陣R和C，更新R(i)和C(i)的方法分別為：

(1)

(2)

式中:DR和DC分別為矩陣D歸一化的行和列，DR和DC均采用“L1范數(shù)”做歸一化處理?？紤]稀疏數(shù)據(jù)行向量和列向量不等的情況，觀察式(1)和式(2)，根據(jù)列(特征)相似性矩陣更新行(樣本)相似性矩陣，樣本間的相似性以特征相似性為參考，所以該矩陣為協(xié)同相似性矩陣。文中計算R和C的迭代次數(shù)設(shè)為3。

2 增強(qiáng)的重引力搜索算法(GSA)

GSA的廣義目標(biāo)問題為：

(3)

式中:x∈Rm為決策變量的向量；l和u均為m維的向量，分別為問題的下界和上界；f(x)為連續(xù)的目標(biāo)函數(shù)。

2.1 重引力搜索算法

(4)

式中：N為種群規(guī)模。

GSA每次迭代更新粒子的位置和速度以提高目標(biāo)函數(shù)的值，最終獲得全局最優(yōu)的適應(yīng)度。最優(yōu)函數(shù)定義如下：

(5)

最差函數(shù)定義為：

(6)

每個粒子具有引力質(zhì)量和慣性質(zhì)量Mi，引力質(zhì)量包括主動引力質(zhì)量Ma和被動引力質(zhì)量Mp。粒子質(zhì)量間的關(guān)系如下：

Mai=Mpi=Mii=Mii=1,2，…,N

(7)

引力質(zhì)量和慣性質(zhì)量分別定義為：

(8)

(9)

每次迭代個體i和j間的作用力定義如下：

(10)

式中：Fij為j對i的引力；Mpi為對i的被動引力；Maj為對j的主動引力；Rij為i和j的歐氏距離；參數(shù)ε為一個極小的常量，作用是防止分母為0；Gt為引力常量。引力常量隨著迭代遞減：

(11)

式中：G0為初值；α為學(xué)習(xí)速度；T為最大迭代次數(shù)。式(11)的作用是平衡搜索和開發(fā)的關(guān)系，開始階段增強(qiáng)搜索能力，結(jié)束階段增強(qiáng)開發(fā)能力。

粒子i受到的總作用力為所有其他個體的作用力之和，定義如下：

(12)

式中：randj為區(qū)間(0,1)的均勻隨機(jī)數(shù)。為了平衡局部開發(fā)和全局搜索，僅考慮Kopt粒子的力作用于其他的粒子，Kopt關(guān)于t的函數(shù)記為Koptt=Kopt(t)。

計算每個粒子對其他粒子的總作用力，然后根據(jù)牛頓第二引力計算每個粒子的加速度，根據(jù)總作用力更新粒子的位置和速度。粒子i的加速度定義為：

(13)

更新后的速度和位置分別計算為：

(14)

(15)

GSA中粒子向高質(zhì)量的粒子移動，Gt和Koptt控制局部開發(fā)和全局搜索的平衡。

2.2 基于擬牛頓法的局部開發(fā)機(jī)制

(16)

(17)

設(shè)計以下兩條優(yōu)質(zhì)區(qū)域的判斷規(guī)則：

圖2 R1規(guī)則和R2規(guī)則的處理示意圖

擬牛頓法[14]的起點設(shè)為yk，建立二次模型目標(biāo)函數(shù)：

mk(x)=f(yk)+▽f(yk)T(x-yk)+

(18)

(19)

(20)

在dk方向遠(yuǎn)離yk會導(dǎo)致目標(biāo)函數(shù)降低，因此采用以下的線性搜索方法：

(21)

為了確定合適的步長，計算式(21)的近似解，獲得新點yk+1=yk+αkdk，然后從點yk+1重復(fù)程序。

引力搜索中Bk=▽2f(yk)，▽2f(yk)為f對yk的Hessian矩陣，牛頓法的收斂速度為二次方，但計算▽2f(yk)的復(fù)雜度較高，擬牛頓法能夠加快計算速度。通過觀察f(y)和▽f(y)的行為近似Hessian矩陣，擬牛頓法通過更新公式(Broyden Fletcher Goldfarb Shanno,BFGS)近似Hessian矩陣，BFGS逼近逆Hessian矩陣[▽2f(yk+1)]-1的方法為：

(22)

sk=yk+1-yk

(23)

qk=▽f(yk+1)-▽f(yk)

(24)

初始矩陣H0設(shè)為對稱正定矩陣。BFGS的流程如算法1所示，每次迭代的計算成本為O(m2)，m為決策變量的數(shù)量，存儲復(fù)雜度和計算復(fù)雜度與m2成正比例。

算法1基于擬牛頓法的局部開發(fā)

Step1初始化：設(shè)k=0，選擇一個初始點y0，設(shè)H0為y0的近似逆Hessian矩陣。

Step2如果不滿足結(jié)束條件，運行Step 2.1，否則運行Step 3。

Step2.1計算搜索方向：

dk=-Hk▽f(yk)

(25)

Step2.2根據(jù)式(21)計算步長αk。

Step2.3計算yk+1=yk+αkdk。

Step2.4使用式(22)-式(24)更新逆Hessian矩陣Hk+1。

Step2.5k=k+1，返回Step 2。

Step3結(jié)束迭代程序。

2.3 算法實現(xiàn)

將GSA的主迭代程序描述為一個映射關(guān)系：給定一個種群Xt及其速度集Vt，映射為一個新種群Xt+1及其速度集Vt+1，映射公式為：

(Xt+1,Vt+1)=A(Xt,Vt)

(26)

式中：A為映射函數(shù)。給定一個點y0，映射為新向量y*：

y*=AqN(y0)

(27)

式中：Aq為粒子q的映射函數(shù)。

算法2為采用上述新元素的EGSA算法，算法中Step 2.2如果觸發(fā)規(guī)則，則進(jìn)行局部搜索。Step 2.3每次迭代結(jié)束，運行擬牛頓法。參數(shù)tol控制局部開發(fā)的強(qiáng)度。

算法2EGSA算法的流程

Step2如果不滿足結(jié)束條件，運行Step 2.1，否則運行Step 3。

Step2.1運行一次GSA迭代：

(Xt,Vt)=A(Xt-1,Vt-1)

(28)

Step2.5t=t+1。

Step3結(jié)束迭代程序。

3 基于增強(qiáng)重引力搜索的特征選擇算法

3.1 EGSA的解格式

將EGSA的完全解建模為向量格式。設(shè)一個矩陣共有n個目標(biāo)和m個特征，目標(biāo)是為m個對象和n個特征分配一個類標(biāo)簽。給定一個n+m長度的向量，前n個元素為n個樣本的類標(biāo)簽，剩余m個元素為m個特征的類標(biāo)簽。圖3是一個解的例子，該例子包括10個樣本和8個特征，設(shè)樣本的分類數(shù)k1為3，特征的分類數(shù)k2為2。行標(biāo)簽表示為xi∈{1，2，…，k1}，特征標(biāo)簽為yi∈{1，2，…，k2}。

圖3 EGSA解的例子

3.2 種群初始化

設(shè)計混合初始化方案，一半種群為隨機(jī)初始化，另一半使用K-means++算法[15]處理，K-means++算法處理數(shù)據(jù)矩陣獲得n行和m列的類標(biāo)簽。圖4所示是混合種群初始化的示意圖，P為種群總規(guī)模，M為每個粒子的列數(shù)。

圖4 混合種群初始化的示意圖

3.3 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)評估解的質(zhì)量，采用Chi-Sim[13]度量樣本和特征間的距離。矩陣R和C為L1范數(shù)歸一化的相似性值，直接將這些元素轉(zhuǎn)化為不相似值。本文的適應(yīng)度函數(shù)定義為：

(29)

式中：pi為第i個粒子；δjk為距離的歸一化因子。適應(yīng)度值越高表示解質(zhì)量越高。第1項對應(yīng)行聚類，第2項對應(yīng)列聚類，使用該目標(biāo)函數(shù)計算解的適應(yīng)度。

3.4 算法流程

圖5為協(xié)同聚類算法的總體流程圖。初始化階段一半種群為隨機(jī)初始化，另外一半種群采用K-means++聚類處理。之后每次GSA迭代檢查是否滿足R1和R2，如果滿足則執(zhí)行局部開發(fā)，如果不滿足則繼續(xù)GSA迭代進(jìn)行全局搜索程序。

圖5 算法的總體流程圖

4 實 驗

4.1 實驗數(shù)據(jù)集

采用6個常用的公開數(shù)據(jù)集作為實驗的benchmark數(shù)據(jù)集，前2個數(shù)據(jù)集是UCI的低維小數(shù)據(jù)集，然后從20Newsgroup語料庫選出3個不同復(fù)雜度和分類數(shù)量的數(shù)據(jù)集，最終選擇典型的高維數(shù)據(jù)Reuters。表2是6個benchmark數(shù)據(jù)集的簡單介紹，Iris數(shù)據(jù)集和Wine數(shù)據(jù)集均具有正定標(biāo)簽，據(jù)此評估聚類的結(jié)果。20Newsgroup數(shù)據(jù)集包含約20 000個新聞報道，共有20個分類，每個分類約有1 000個文檔，采用該語料庫的3個子集：M2、M5、M10，分別包含2、5和10個分類。RT數(shù)據(jù)集來自于Reuters集合。

表2 benchmark數(shù)據(jù)集的屬性

4.2 性能評價指標(biāo)

使用準(zhǔn)確率作為性能評價指標(biāo)，準(zhǔn)確率將聚類算法的預(yù)測結(jié)果和正定值比較來觀察算法的準(zhǔn)確率。TPi表示分類i的正定值，F(xiàn)Pi表示其他類樣本被錯誤分類為i類的樣本數(shù)量。平均準(zhǔn)確率定義如下：

(30)

式中:分母為數(shù)據(jù)集中樣本總數(shù)量n。acc值越高表示分類器的準(zhǔn)確率越高，每組實驗獨立運行10次，將10次的平均值作為實驗的最終結(jié)果。

4.3 參數(shù)設(shè)置

算法的參數(shù)ε=0，γ=1。算法中擬牛頓法局部開發(fā)的結(jié)束條件設(shè)為：

|f(yk+1)-f(yk)|

(31)

式中:tol參數(shù)控制局部開發(fā)的強(qiáng)度，將tol設(shè)為0.01。

(1)迭代次數(shù)對于準(zhǔn)確率的影響。通過實驗評估最大迭代次數(shù)對于聚類準(zhǔn)確率的影響。將算法的其他參數(shù)設(shè)為定值：種群規(guī)模固定為50，迭代次數(shù)從50遞增至500。實驗結(jié)果如圖6所示，觀察圖中結(jié)果，對于高維數(shù)據(jù)集和低維數(shù)據(jù)集，聚類準(zhǔn)確率均隨著迭代次數(shù)的增加而提高，當(dāng)?shù)螖?shù)超過400時，曲線逐漸收斂，因此將最大迭代次數(shù)設(shè)為400。

圖6 迭代次數(shù)對于準(zhǔn)確率的影響

(2)種群規(guī)模對于準(zhǔn)確率的影響。通過實驗評估重引力搜索算法種群規(guī)模對于聚類準(zhǔn)確率的影響。將算法的其他參數(shù)設(shè)為定值：種群規(guī)模設(shè)為50～300，迭代次數(shù)定為400，每組參數(shù)獨立運行10次。實驗結(jié)果如圖7所示，對于高維數(shù)據(jù)集和低維數(shù)據(jù)集，聚類準(zhǔn)確率與種群規(guī)模的關(guān)系較為穩(wěn)定，為了保持較高的計算效率，實驗中將種群規(guī)模設(shè)為50。

圖7 種群規(guī)模對于準(zhǔn)確率的影響

4.4 局部開發(fā)機(jī)制的效果

本文算法的一個關(guān)鍵創(chuàng)新是為GSA引入基于逆牛頓法的局部開發(fā)機(jī)制，因此首先測試本文局部開發(fā)機(jī)制的效果。選擇幾個常見的GSA局部開發(fā)機(jī)制與本文算法對比，分別為基于遺傳算法的局部開發(fā)機(jī)制(簡稱GSA_GA)[16]、基于混沌置亂的局部開發(fā)機(jī)制(簡稱GSA_C)[17]、基于神經(jīng)網(wǎng)絡(luò)和模糊系統(tǒng)的局部開發(fā)機(jī)制(簡稱GSA_NNF)[18]。

圖8為不同GSA對于高維數(shù)據(jù)集和低維數(shù)據(jù)集的平均聚類準(zhǔn)確率結(jié)果?？梢钥闯?，GSA_GA、GSA_C、GSA_NNF及本文算法的性能均明顯高于原GSA，GSA_GA和GSA_NNF的結(jié)果低于GSA_C和本文算法。本文算法采用兩條規(guī)則選擇GSA的優(yōu)質(zhì)區(qū)域，再通過擬牛頓法對優(yōu)質(zhì)區(qū)域進(jìn)行深入開發(fā)，實現(xiàn)了較好的總體性能。

圖8 不同GSA對于數(shù)據(jù)集的聚類結(jié)果

4.5 與其他聚類算法的比較

本文算法首次將協(xié)同過濾技術(shù)與GSA算法結(jié)合，重點研究本算法對于高維數(shù)據(jù)集的聚類效果。上文顯示本文的重引力搜索算法有效地增強(qiáng)了原重引力搜素算法的性能，此處將本文算法與其他聚類算法比較，評估本文算法的總體性能。對比方法分別為經(jīng)典的DBSCAN[19]、GA聚類算法[20]，以及兩個高維數(shù)據(jù)的聚類算法。FSEC[21]是一種基于特征優(yōu)化分組的集成式高維大數(shù)據(jù)聚類算法，該算法也利用協(xié)同聚類的思想，并且構(gòu)建集成式聚類算法的框架，對高維大數(shù)據(jù)實現(xiàn)理想的聚類結(jié)果。HDTDC是一種基于改進(jìn)布谷鳥搜索的和語義索引的高維數(shù)據(jù)聚類算法，該算法也利用協(xié)同聚類算法的思想，并且首次利用布谷鳥搜索算法對高維文檔數(shù)據(jù)集進(jìn)行聚類處理。

圖9為5個聚類算法對于6個數(shù)據(jù)集的聚類準(zhǔn)確率結(jié)果?？梢钥闯觯現(xiàn)SEC對于Wine和Iris數(shù)據(jù)集的準(zhǔn)確率較低，遠(yuǎn)低于其他4種算法，而FSEC對于M2、M5、M10和RT 4個高維數(shù)據(jù)集的準(zhǔn)確率較高。DBSCAN則對Wine和Iris數(shù)據(jù)集的準(zhǔn)確率較為理想，但對于M2、M5、M10和RT 4個高維數(shù)據(jù)集的準(zhǔn)確率處于明顯的劣勢。FSEC和HDTDC兩個近期的算法實現(xiàn)較為理想的聚類準(zhǔn)確率，并且具有良好的穩(wěn)定性。本文算法對于6個不同數(shù)據(jù)集均實現(xiàn)最佳的聚類結(jié)果，對于高維數(shù)據(jù)集的性能優(yōu)勢更加明顯。

4.6 算法的時間效率

高維數(shù)據(jù)中包含大量的噪聲信息和冗余信息，給算法的處理時間帶來了極大的挑戰(zhàn)。圖10為5種算法對于6個不同數(shù)據(jù)集的平均聚類處理時間?？梢钥闯觯現(xiàn)SEC將特征優(yōu)化分組，采用并行處理框架獲得了最低的計算時間。GAC的種群規(guī)模較大，每次迭代包含交叉算子、變異算子和選擇算子的處理，算法的計算時間較長。DBSCAN對于低維數(shù)據(jù)集的處理速度較快，但對于M2、M5、M10和RT 4個高維數(shù)據(jù)集的速度較慢。本文算法對于高維小樣本數(shù)據(jù)集的處理效率較為理想，但對于高維大樣本數(shù)據(jù)集的效率較為一般。

圖10 5種算法對于6個不同數(shù)據(jù)集的平均聚類處理時間

5 結(jié) 語

本文設(shè)計協(xié)同相似性矩陣度量數(shù)據(jù)集的樣本相似性和特征相似性，以二部圖形式建模特征和數(shù)據(jù)點的關(guān)系；設(shè)計擬牛頓法的局部開發(fā)策略，提高重引力搜索的求解質(zhì)量?；诟呔S數(shù)據(jù)集和低維數(shù)據(jù)集進(jìn)行仿真實驗，結(jié)果表明，本文算法對于不同維度的數(shù)據(jù)集均實現(xiàn)理想的聚類準(zhǔn)確率，并且對高維小樣本數(shù)據(jù)實現(xiàn)較高的計算效率。但本文算法對于高維大樣本數(shù)據(jù)的時間效率較為一般，未來將專注于本文算法應(yīng)用于高維大樣本數(shù)據(jù)集的研究，在提高聚類準(zhǔn)確率的前提下，保持較快的處理速度。