一種適合于非線性高維數據的譜聚類算法

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

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

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

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

0 引 言

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

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

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

1 譜聚類

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

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

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

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

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

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

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

L=D-W

規范化為：

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

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

0≤t1≤t2≤…≤tk

構成矩陣：

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

Step5對T進行歸一化：

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

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

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

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

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

2 自適應譜聚類

2.1 參數和聚類個數的自適應確定

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

將Step 1中的wij改進為:

(1)

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

Iris Wine Three_circle

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

表1 實際聚類數和跳躍點的對比

2.2 聚類結果分析

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

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

Five_cluster Three_circle Spiral

3 大規模隨機特征空間

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

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

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

(2)

(3)

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

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

4.1 算法介紹

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

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

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

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

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

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

Step5利用傳統的K-means進行聚類。

4.2 實驗環境

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

表2 TS10K集群詳細信息

4.3 實驗結果分析

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

(4)

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

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

表3 數據集屬性

表4 三種算法RI比較

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

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

5 結 語

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