桑 遙 尹 君 王 迪 王 皓 景 康

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

0 引 言

聚類處理將物理或抽象的數(shù)據(jù)對(duì)象按指定的相似性度量歸納，是沒有先驗(yàn)知識(shí)情況下的一種重要數(shù)據(jù)挖掘技術(shù)[1]。現(xiàn)有的聚類技術(shù)按采用的基本思想主要可分為4類[2]，即層次聚類算法、分割聚類算法、機(jī)器學(xué)習(xí)的聚類算法和高維數(shù)據(jù)聚類算法。層次聚類算法將數(shù)據(jù)組織成若干類構(gòu)成一個(gè)樹狀結(jié)構(gòu)來進(jìn)行聚類處理。分割聚類算法首先將數(shù)據(jù)點(diǎn)集劃分為若干個(gè)子集，再通過控制策略對(duì)各個(gè)子集分別做聚類優(yōu)化處理。機(jī)器學(xué)習(xí)的聚類算法[3]主要采用人工神經(jīng)網(wǎng)絡(luò)、進(jìn)化學(xué)習(xí)等理論處理聚類問題，通過機(jī)器學(xué)習(xí)的自學(xué)習(xí)能力對(duì)聚類準(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é)同聚類對(duì)數(shù)據(jù)點(diǎn)和特征集同時(shí)進(jìn)行聚類，以特征子集引導(dǎo)數(shù)據(jù)點(diǎn)的聚類過程，能提高聚類的效率和準(zhǔn)確率。協(xié)同聚類技術(shù)能夠提高對(duì)高維數(shù)據(jù)的聚類效果[10-11]，因此本文采用協(xié)同聚類技術(shù)解決高維數(shù)據(jù)聚類的問題。重引力搜索能夠高效地解決某些特定情況下的優(yōu)化問題，尤其對(duì)于高維優(yōu)化問題具有獨(dú)特的優(yōu)勢[12]，因此本文采用重引力搜索解決高維數(shù)據(jù)的聚類問題。針對(duì)重引力搜索存在局部開發(fā)能力不足的問題，本文設(shè)計(jì)擬牛頓法的局部開發(fā)策略，提高重引力搜索的求解質(zhì)量。

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

首先以一個(gè)實(shí)例介紹協(xié)同相似性的問題模型。表1是一個(gè)矩陣實(shí)例，圖1是表1對(duì)應(yīng)的二部圖。理想情況下，d1-d3為第1行，d4-d5為第2行，c1-c3為第1列，c4-c6為第2列。假設(shè)一個(gè)文檔為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 一個(gè)矩陣的實(shí)例

圖1 表1實(shí)例的二部圖結(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é)同相似性矩陣。文中計(jì)算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)

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

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

(7)

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

(8)

(9)

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

(10)

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

(11)

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

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

(12)

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

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

(13)

更新后的速度和位置分別計(jì)算為：

(14)

(15)

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

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

(16)

(17)

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

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

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

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

(18)

(19)

(20)

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

(21)

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

引力搜索中Bk=▽2f(yk)，▽2f(yk)為f對(duì)yk的Hessian矩陣，牛頓法的收斂速度為二次方，但計(jì)算▽2f(yk)的復(fù)雜度較高，擬牛頓法能夠加快計(jì)算速度。通過觀察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è)為對(duì)稱正定矩陣。BFGS的流程如算法1所示，每次迭代的計(jì)算成本為O(m2)，m為決策變量的數(shù)量，存儲(chǔ)復(fù)雜度和計(jì)算復(fù)雜度與m2成正比例。

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

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

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

Step2.1計(jì)算搜索方向：

dk=-Hk▽f(yk)

(25)

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

Step2.3計(jì)算yk+1=yk+αkdk。

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

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

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

2.3 算法實(shí)現(xiàn)

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

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

(26)

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

y*=AqN(y0)

(27)

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

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

算法2EGSA算法的流程

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

Step2.1運(yùn)行一次GSA迭代：

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

(28)

Step2.5t=t+1。

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

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

3.1 EGSA的解格式

將EGSA的完全解建模為向量格式。設(shè)一個(gè)矩陣共有n個(gè)目標(biāo)和m個(gè)特征，目標(biāo)是為m個(gè)對(duì)象和n個(gè)特征分配一個(gè)類標(biāo)簽。給定一個(gè)n+m長度的向量，前n個(gè)元素為n個(gè)樣本的類標(biāo)簽，剩余m個(gè)元素為m個(gè)特征的類標(biāo)簽。圖3是一個(gè)解的例子，該例子包括10個(gè)樣本和8個(gè)特征，設(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ì)混合初始化方案，一半種群為隨機(jī)初始化，另一半使用K-means++算法[15]處理，K-means++算法處理數(shù)據(jù)矩陣獲得n行和m列的類標(biāo)簽。圖4所示是混合種群初始化的示意圖，P為種群總規(guī)模，M為每個(gè)粒子的列數(shù)。

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

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

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

(29)

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

3.4 算法流程

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

圖5 算法的總體流程圖

4 實(shí) 驗(yàn)

4.1 實(shí)驗(yàn)數(shù)據(jù)集

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

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

4.2 性能評(píng)價(jià)指標(biāo)

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

(30)

式中:分母為數(shù)據(jù)集中樣本總數(shù)量n。acc值越高表示分類器的準(zhǔn)確率越高，每組實(shí)驗(yàn)獨(dú)立運(yùn)行10次，將10次的平均值作為實(shí)驗(yàn)的最終結(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ù)對(duì)于準(zhǔn)確率的影響。通過實(shí)驗(yàn)評(píng)估最大迭代次數(shù)對(duì)于聚類準(zhǔn)確率的影響。將算法的其他參數(shù)設(shè)為定值：種群規(guī)模固定為50，迭代次數(shù)從50遞增至500。實(shí)驗(yàn)結(jié)果如圖6所示，觀察圖中結(jié)果，對(duì)于高維數(shù)據(jù)集和低維數(shù)據(jù)集，聚類準(zhǔn)確率均隨著迭代次數(shù)的增加而提高，當(dāng)?shù)螖?shù)超過400時(shí)，曲線逐漸收斂，因此將最大迭代次數(shù)設(shè)為400。

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

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

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

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

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

圖8為不同GSA對(duì)于高維數(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ū)域，再通過擬牛頓法對(duì)優(yōu)質(zhì)區(qū)域進(jìn)行深入開發(fā)，實(shí)現(xiàn)了較好的總體性能。

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

4.5 與其他聚類算法的比較

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

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

4.6 算法的時(shí)間效率

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

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

5 結(jié) 語

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