王鴻菲 杜洪波* 林凱迪 姚云飛 朱立軍

1(沈陽工業(yè)大學(xué)理學(xué)院 遼寧 沈陽 110870)

2(天津大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 天津 300050)

3(北方民族大學(xué)信息與計(jì)算科學(xué)學(xué)院 寧夏 銀川 750021)

0 引 言

隨著信息技術(shù)、移動(dòng)互聯(lián)網(wǎng)的快速發(fā)展，數(shù)據(jù)呈爆炸式增長。聚類算法作為數(shù)據(jù)挖掘中一種無監(jiān)督學(xué)習(xí)方法，在圖像識(shí)別、生物學(xué)和統(tǒng)計(jì)學(xué)等領(lǐng)域中贏得廣泛應(yīng)用[1]。譜聚類是聚類算法中研究熱點(diǎn)之一。一般算法只能解決凸優(yōu)化問題，在非凸優(yōu)化問題中容易陷入局部最優(yōu)，而譜聚類能在任意形狀分布的數(shù)據(jù)中正確聚類。譜聚類是基于譜圖劃分理論[2]，構(gòu)造相似矩陣，從而構(gòu)造拉普拉斯矩陣，進(jìn)而求特征值和特征向量，根據(jù)特征向量內(nèi)在的關(guān)系進(jìn)行重聚類。

譜聚類中一般利用高斯核函數(shù)度量相似性。高斯核參數(shù)σ和聚類個(gè)數(shù)需要人工確定。何家玉[3]提出利用局部尺度高斯核函數(shù)替代傳統(tǒng)的高斯核函數(shù)，避免尺度參數(shù)的人為確定；王超[4]提出用和第k近鄰的距離代替σ。對(duì)于聚類個(gè)數(shù)的確定，李金澤等[5]提出基于本征間隙自動(dòng)確定聚類個(gè)數(shù)，在本征間隙序列中第一極大值對(duì)應(yīng)下標(biāo)即為聚類數(shù)。本文擬對(duì)高斯核函數(shù)中的σ參數(shù)及聚類個(gè)數(shù)進(jìn)行優(yōu)化，建立自適應(yīng)譜聚類算法。

近年以來，許多學(xué)者對(duì)非線性高維聚類算法進(jìn)行研究。傳統(tǒng)的非線性高維聚類問題一般是先通過非線性降維約簡方法將非線性高維數(shù)據(jù)映射到線性低維空間中，在低維空間進(jìn)行聚類。對(duì)于非線性數(shù)據(jù)，文獻(xiàn)[6]提出了一種新的無監(jiān)督非參數(shù)型的聚類算法支持向量聚類；文獻(xiàn)[7]將支持向量機(jī)方法用于數(shù)據(jù)域描述即單一分類中,提出了基于Gaussion核的支持向量維數(shù)描述(SVDD)算法;對(duì)于高維數(shù)據(jù)，張蓉等[8]提出了一種基于超網(wǎng)絡(luò)模型的聚類方法，使用關(guān)聯(lián)規(guī)則中的相關(guān)概念度量多個(gè)對(duì)象之間的相似度，實(shí)質(zhì)上是把高維聚類問題轉(zhuǎn)化成了超網(wǎng)絡(luò)模型劃分尋優(yōu)的問題；對(duì)于非線性高維數(shù)據(jù)，姜洪權(quán)等[9]提出了一種基于核主元分析(KPCA)與密度聚類(DBSCAN)的高維非線性特征數(shù)據(jù)聚類分析技術(shù)；本文擬將非線性高維數(shù)據(jù)通過顯式構(gòu)造，構(gòu)造顯式隨機(jī)特征空間[10]。在隨機(jī)特征空間中使用自適應(yīng)譜聚類進(jìn)行聚類，解決非線性高維數(shù)據(jù)的聚類分析。

1 譜聚類

數(shù)據(jù)集X={x1,x2,…,xn}為n個(gè)數(shù)據(jù)的集合，相似矩陣W={wij}n×n，wij為數(shù)據(jù)點(diǎn)xi和xj的相似度，其中wij=wji。構(gòu)造相似圖G=(X,W)。譜聚類就是在圖G的基礎(chǔ)上，找到一個(gè)分割圖，不同簇的邊權(quán)值很小，相同簇的邊權(quán)值很大。NJW算法是譜聚類中比較常用的算法之一。

NJW算法主要步驟如下[5]：

Step1構(gòu)造相似矩陣W∈Rn×n。矩陣中的元素一般為高斯核函數(shù)，表示為：

式中：當(dāng)i=j時(shí)，wij=0。其中d(xi,xj)為數(shù)據(jù)xi和xj的距離，一般為歐氏距離。σ為決定樣本間的衰減速度的尺度參數(shù)。

Step2構(gòu)造度矩陣D∈Rn×n：

式中：di為W第i行的和,其他元素為0。

Step3構(gòu)造拉普拉斯矩陣L∈Rn×n：

L=D-W

規(guī)范化為：

式中：I為n×n單位矩陣。

Step4計(jì)算L的特征值和特征向量：選擇k個(gè)最小特征值。對(duì)應(yīng)的特征值為：

0≤t1≤t2≤…≤tk

構(gòu)成矩陣：

T=[t1,t2,…,tk]∈Rn×k。

Step5對(duì)T進(jìn)行歸一化：

Step6對(duì)Y使用K-means進(jìn)行聚類。Yi所在的類及為原始數(shù)據(jù)xi的類。

相似矩陣是實(shí)現(xiàn)譜聚類算法的關(guān)鍵，合理的度量數(shù)據(jù)之間的相似度可以提高算法的準(zhǔn)確率。傳統(tǒng)的NJW在Step 1構(gòu)造相似矩陣時(shí)，σ參數(shù)的變化會(huì)直接影響算法的效率，并且效果比較明顯。圖1顯示σ的不同時(shí)，聚類效果有很大差別。

Spirl(σ=0.1) Spirl(σ=0.4) Spirl(σ=0.8)

在圖1中，分別對(duì)可分為三類數(shù)據(jù)Spirl、Twomoon和Ring進(jìn)行聚類。分別令σ為0.1、0.4和0.8。對(duì)于Spirl數(shù)據(jù)，σ為0.1和0.4時(shí)，兩類中一類完全聚類，另一類沒有完全聚類，部分?jǐn)?shù)據(jù)錯(cuò)誤。σ為0.8時(shí)，兩類都沒有完全聚類，混作一起。同理，對(duì)于Twomoon數(shù)據(jù)，σ為0.2時(shí)部分聚類成功，另一部分部分錯(cuò)誤。σ為0.4和0.8時(shí)混作一起。Ring數(shù)據(jù)，σ為0.1時(shí)，將兩類分為一類，另一類完全錯(cuò)誤。σ為0.4和0.7時(shí)，部分聚類成功，另一部分錯(cuò)誤。

通過上面對(duì)σ進(jìn)行不同值得改變，對(duì)三個(gè)數(shù)據(jù)進(jìn)行聚類，結(jié)論得出σ的不同對(duì)聚類效果的影響比較明顯。

2 自適應(yīng)譜聚類

2.1 參數(shù)和聚類個(gè)數(shù)的自適應(yīng)確定

Step 1中σ一般是人工設(shè)定，需要反復(fù)調(diào)試，工作量比較大，同時(shí)σ應(yīng)該隨數(shù)據(jù)分布的不同需要做經(jīng)常性的調(diào)整。另外，Step 4中k值一般也為人為設(shè)定。本文就σ和k的取值進(jìn)行研究，提出一種自適應(yīng)譜聚類算法，根據(jù)數(shù)據(jù)分布特點(diǎn)自動(dòng)計(jì)算σ和k的值。

將Step 1中的wij改進(jìn)為:

(1)

式中：σ=cos(xi,xj)∈[0,1]。cos(xi,xj)反映了xi、xj的夾角大小，夾角越小余弦越大，對(duì)應(yīng)的wij值越大，即相似度越大。對(duì)于Step 4 中k的確定，在實(shí)驗(yàn)中發(fā)現(xiàn)，在Step 4中求出來的特征值中，部分特征值會(huì)發(fā)生非常明顯的跳躍[4]。本文對(duì)UCI的iris、wine數(shù)據(jù)和人工數(shù)據(jù)Three_circle、Spiral、Ring和Twomoon數(shù)據(jù)進(jìn)行分析畫散點(diǎn)圖，如圖2所示。

Iris Wine Three_circle

表1為實(shí)際聚類數(shù)和跳躍點(diǎn)的對(duì)比。從圖2和表1可得出，部分特征值有明顯的跳躍，其中Iris、Spiral、Ring和Twomoon實(shí)際聚類數(shù)和特征值得跳躍點(diǎn)個(gè)數(shù)相同，并且相對(duì)比較明顯。Wine數(shù)據(jù)和ThreeCircle數(shù)據(jù)特征值跳躍點(diǎn)和實(shí)際聚類數(shù)有出入，但是Wine數(shù)據(jù)和ThreeCircle特征值跳躍點(diǎn)和實(shí)際聚類相差不大，僅相差1。充分顯示特征值的跳躍點(diǎn)數(shù)和聚類數(shù)基本相同。

表1 實(shí)際聚類數(shù)和跳躍點(diǎn)的對(duì)比

2.2 聚類結(jié)果分析

自適應(yīng)譜聚類對(duì)低維數(shù)據(jù)聚類效果比較好，通過對(duì)Five_cluster、Three_circle、Spiral、Spiral_unbalance、Twomoon和Ring進(jìn)行聚類，結(jié)果如圖3所示。

這些數(shù)據(jù)大致可以分為：線性數(shù)據(jù)和非線性數(shù)據(jù)、對(duì)稱數(shù)據(jù)和非對(duì)稱數(shù)據(jù)、有無噪聲數(shù)據(jù)、圓類數(shù)據(jù)和非圓類數(shù)據(jù)。其中Five_cluster是線性數(shù)據(jù)，將數(shù)據(jù)分為5類，其他如Three_circle等是非線性的數(shù)據(jù)；Spiral等平衡數(shù)據(jù)，所分的兩類都是對(duì)稱均勻的，但Spiral_unbalance數(shù)據(jù)，所分的兩類為非對(duì)稱，非對(duì)稱數(shù)據(jù)聚類比較難；Three_circle和Twomoon都有很大的噪聲；Three_circle、Ring、Spiral都屬于圓類數(shù)據(jù)，Twomoon和Five_cluster為非圓類數(shù)據(jù)。通過圖3可得，不管是非線性還是線性、對(duì)稱還是非對(duì)稱、有無噪聲、是否為圓形數(shù)據(jù)，都能進(jìn)行準(zhǔn)確聚類，聚類效果比較好。

Five_cluster Three_circle Spiral

3 大規(guī)模隨機(jī)特征空間

核函數(shù)[11]是解決非線性的關(guān)鍵因素，被應(yīng)用到許多方面，并取得較好的效果。在非線性數(shù)據(jù)映射到線性空間時(shí)，χ為原數(shù)據(jù)集，H為映射后的希爾伯特空間，φ:χ→H，φ為映射函數(shù)。但實(shí)際中映射函數(shù)是很難找到，并且一般也不需要找到對(duì)應(yīng)的映射函數(shù)。核函數(shù)是不用明確知道映射函數(shù)就可以計(jì)算映射向量的內(nèi)積，即k(x,y)=(φ(x)·φ(y))。但核函數(shù)學(xué)習(xí)時(shí)間和空間復(fù)雜度較高，至少是平方級(jí)，不適合進(jìn)行大規(guī)模學(xué)習(xí)。

馮昌等[10]提出一種通過近似核函數(shù)顯式構(gòu)造隨機(jī)特征空間的方法。核函數(shù)近似表示為：

k(x,y)≈(φ(x)·φ(y))

(2)

(3)

式中：P∈RD×d為高斯隨機(jī)矩陣。每個(gè)位置上的元素均服從N(0,1/σ2)，b的每個(gè)元素均服從μ[-π,π]。將原始再生核希爾伯特空間中的學(xué)習(xí)問題轉(zhuǎn)化成顯式隨機(jī)特征空間中的學(xué)習(xí)問題。時(shí)間復(fù)雜度為O(n×D)，n為數(shù)據(jù)個(gè)數(shù)。

4 非線性高維自適應(yīng)譜聚類算法(NHASC)

4.1 算法介紹

本文將改進(jìn)的自適應(yīng)譜聚類和顯式隨機(jī)特征空間進(jìn)行結(jié)合，實(shí)現(xiàn)大規(guī)模的譜聚類算法實(shí)現(xiàn)。算法步驟：

Step1變換空間。將數(shù)據(jù)集X={x1,x2,…,xn}通過以下顯式構(gòu)造映射到顯式隨機(jī)特征空間φRKS(X)={z1,z2,…,zn}：

Step2構(gòu)造相似矩陣。相似矩陣表示為：

由于W需為對(duì)稱矩陣，所以令W=W+WT；其中k的值隨著數(shù)據(jù)的不同有所差別，但比較好確定。

Step3構(gòu)造度矩陣和拉普拉斯矩陣(同傳統(tǒng)的NJW算法)。

Step4估計(jì)聚類個(gè)數(shù),確定特征值和特征向量。計(jì)算拉普拉斯矩陣特征值，對(duì)特征值進(jìn)行畫散點(diǎn)圖分析，估計(jì)聚類個(gè)數(shù)k。確定前k個(gè)最小的特征向量作為新的數(shù)據(jù)。

Step5利用傳統(tǒng)的K-means進(jìn)行聚類。

4.2 實(shí)驗(yàn)環(huán)境

本實(shí)驗(yàn)使用浪潮TS10K集群作為實(shí)驗(yàn)環(huán)境，其中,管理節(jié)點(diǎn)為MU01，計(jì)算節(jié)點(diǎn)為CU01-CU05，配置信息見表2。

表2 TS10K集群詳細(xì)信息

4.3 實(shí)驗(yàn)結(jié)果分析

本文通過一系列實(shí)驗(yàn)來驗(yàn)證本文算法NHASC的聚類效果。通過使用UCI數(shù)據(jù)進(jìn)行聚類分析，和傳統(tǒng)的NJW、K-means進(jìn)行比較，采用RI準(zhǔn)確率來衡量聚類的準(zhǔn)確率。RI[12]評(píng)價(jià)指標(biāo)計(jì)算式為：

(4)

式中：a表示原來是同一類，被聚類后還在同一類的個(gè)數(shù)；b表示原來不是一類，聚類后也不是一類的個(gè)數(shù)；n為數(shù)據(jù)個(gè)數(shù)。RI∈[0,1]，RI越大代表準(zhǔn)確率越高，當(dāng)RI為1是表示完全正確。

實(shí)驗(yàn)用UCI數(shù)據(jù)集屬性如表3所示。通過對(duì)Iris、Wine、cmc、seeds和CNAE-9數(shù)據(jù)用NHASC算法聚類。實(shí)驗(yàn)結(jié)果如表4所示，本文算法 NHASC較傳統(tǒng)NJW算法和K-means效果更好。例如，Iris數(shù)據(jù)上K-means算法的準(zhǔn)確率為0.879 7，傳統(tǒng)NJW算法準(zhǔn)確率為0.934 1，NHASC算法的準(zhǔn)確率能達(dá)到0.973 9，在150個(gè)數(shù)據(jù)中有3個(gè)數(shù)據(jù)聚類錯(cuò)誤。同樣，其他數(shù)據(jù)上NHASC算法準(zhǔn)確率也相對(duì)其他算法更好，如表4所示。

表3 數(shù)據(jù)集屬性

表4 三種算法RI比較

在時(shí)間效率上，在相同的數(shù)據(jù)上，NHASC算法消耗的時(shí)間較少，如表5所示。Iris數(shù)據(jù)聚類在傳統(tǒng)NJW中消耗時(shí)間為3 375.8 ms，NHASC算法消耗時(shí)間為3 339.7 ms。并且對(duì)數(shù)據(jù)量較大、維度較高的聚類時(shí)間差別較明顯。在CNAE-9上傳統(tǒng)NJW消耗時(shí)間為252 000.55，而NHASC算法則為192 000.43 ms，NHASC算法明顯快于傳統(tǒng)的NJW算法。其中NHASC算法時(shí)間復(fù)雜度為O(n2×D)，D為映射后的維度。

表5 NJW 和NHASC算法時(shí)間消耗比較 單位：ms

5 結(jié) 語

本文在傳統(tǒng)譜聚類算法的基礎(chǔ)上，對(duì)高斯核函數(shù)的尺度參數(shù)和聚類個(gè)數(shù)進(jìn)行優(yōu)化，提出根據(jù)數(shù)據(jù)分布特點(diǎn)自動(dòng)計(jì)算尺度參數(shù)和聚類個(gè)數(shù)的自適應(yīng)譜聚類算法，使其與隨機(jī)特征空間結(jié)合，將數(shù)據(jù)通過顯式構(gòu)造映射到隨機(jī)特征空間后，在隨機(jī)特征空間中使用自適應(yīng)譜聚類算法進(jìn)行聚類，以解決非線性高維數(shù)據(jù)的聚類問題。在UCI數(shù)據(jù)集上的測(cè)試結(jié)果表明，與NJW、K-means算法相比較，本文提出的算法聚類效果更好，且時(shí)間復(fù)雜度更低。