一種適合于非線性高維數(shù)據(jù)的譜聚類算法

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

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

2(天津大學計算機科學與技術學院 天津 300050)

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

0 引 言

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

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

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

1 譜聚類

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

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

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

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

Step2構造度矩陣D∈Rn×n：

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

Step3構造拉普拉斯矩陣L∈Rn×n：

L=D-W

規(guī)范化為：

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

Step4計算L的特征值和特征向量：選擇k個最小特征值。對應的特征值為：

0≤t1≤t2≤…≤tk

構成矩陣：

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

Step5對T進行歸一化：

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

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

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

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

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

2 自適應譜聚類

2.1 參數(shù)和聚類個數(shù)的自適應確定

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

將Step 1中的wij改進為:

(1)

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

Iris Wine Three_circle

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

表1 實際聚類數(shù)和跳躍點的對比

2.2 聚類結果分析

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

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

Five_cluster Three_circle Spiral

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

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

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

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

(2)

(3)

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

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

4.1 算法介紹

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

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

Step2構造相似矩陣。相似矩陣表示為：

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

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

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

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

4.2 實驗環(huán)境

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

表2 TS10K集群詳細信息

4.3 實驗結果分析

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

(4)

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

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

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

表4 三種算法RI比較

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

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

5 結 語

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