蔡 帥，朱 磊，曾維軍，魏克峰，孫 靜

(1.陸軍工程大學 通信工程學院，江蘇 南京 210001；2.戰(zhàn)略支援部隊61623部隊，北京 100093；3.空軍通信士官學校，遼寧 大連 116000)

0 引言

K-means聚類算法[1]最近被認為是過去50年中十大數(shù)據(jù)挖掘工具之一[2]。同時，隨機投影(Random Projection，RP)或所謂的Johnson-Lindenstrausstype嵌入[3]開始流行，并在理論計算機科學[4]和數(shù)據(jù)分析[5]中得到應(yīng)用。K-means聚類的目標是為數(shù)據(jù)集找到一組K個聚類中心，使得每個點到其最近聚類中心的距離的平方和最小化。雖然已知即使對于K=2，K-means聚類也是NP難問題[6]，但實際上，由Lloyd提出的局部搜索啟發(fā)式方法被廣泛用于求解K-means聚類問題。Lloyd的迭代算法以K個任意“聚類中心”開始，并且在每次迭代中，每個點被分配到最近的聚類中心，并且每個聚類中心被重新計算為分配給它的所有點的質(zhì)心，重復這最后兩個步驟，直到過程穩(wěn)定。

1 相關(guān)理論

1.1 近似K-means算法

K-means聚類的目的是將數(shù)據(jù)集A=[a1,a2,…，an]T∈Rn×d中的所有樣本點劃分到k個互不重疊的簇C={C1,C2,…，Ck}中，同一個簇中的每一個樣本點與其他點之間的距離都比較近，而與其他簇中的樣本點的距離都比較遠?，F(xiàn)在令μi代表第i個簇的質(zhì)心，對于每一個樣本點ai，它的簇標記可以表示為C(ai)，K-means聚類的目標就是最小化下式：

(1)

(2)

(3)

1.2 隨機投影

隨機投影(或者稱為Johnson-Lindenstrauss嵌入)定理的一個重要結(jié)論是：對于任意矩陣A∈Rn×d，可以將其中的n個d維向量線性投影到t=Ω(k/ε2)維空間中，這種投影使用隨機標準正交矩陣，并以因子1+ε保存了原始空間中任意兩點之間的距離。

(1-ε)‖A(i)-A(j)‖2≤‖A(i)R-A(j)R‖2≤(1+ε)‖A(i)-A(j)‖2

(4)

2 基于隨機投影的K-means算法

2.1 基于隨機投影的K-means算法

基于隨機投影的K-means算法描述如下：

輸入:數(shù)據(jù)集A∈Rn×d,簇個數(shù)k,誤差0 <ε< 1/3輸出:質(zhì)心集C∈Rn×t步驟1:定義t=Ωk/ε2(),初始化t0;步驟2:生成隨機矩陣R∈Rd×t,對于i=1,...,d,j=1,...,t,Rij=-1t,1t{},概率分布為1/2;步驟3:計算矩陣C=AR;步驟4:返回C∈Rn×t;步驟5:對矩陣C∈Rn×t使用K-means算法進行聚類。

2.2 K-means聚類近似算法證明

尋找XCopt是一個NP-hard問題，因此這里引出K-means問題的“γ-近似”定義：對于任何數(shù)據(jù)矩陣A的K-means問題，如果矩陣Xγ滿足

(5)

那么就稱矩陣Xγ是該問題的“γ-近似”，其中γ≥1。

定理：令n×d矩陣A和正整數(shù)k

(6)

定理簡要證明：

A=Ak+Aρ-k

令:

證畢。

2.3 算法分析

3 實驗與分析

在MATLAB中實現(xiàn)了所提出的算法，并將它們與其他一些顯著的降維技術(shù)(如SVD)進行了比較。SVD是用于聚類的流行特征提取方法。本文在具有雙核2.8 GHz處理器和8 GB RAM的機器上進行了所有實驗。

3.1 實驗數(shù)據(jù)

在真實數(shù)據(jù)集和合成數(shù)據(jù)集上進行了實驗。對于合成數(shù)據(jù)集，在n= 2 000維度中生成m= 1 000個點的數(shù)據(jù)集。從邊長2 000的n維超立方體中隨機均勻地選擇k= 5個點作為中心點，然后，以每個中心點為中心，以方差為1的高斯分布生成其他點。對于5個中心點，生成了200個點(此處沒有在數(shù)據(jù)集中包含該中心點)。因此，獲得了許多分離良好的高斯，其真實中心提供了對最佳聚類的良好近似。將此數(shù)據(jù)集稱為Synth。

對于面部圖像集合，下載了與ORL數(shù)據(jù)庫相對應(yīng)的圖像。此系列包含400個面部圖像，尺寸為64×64，對應(yīng)40個不同的人。這些圖像形成40個組，每個組包含同一個人的10個不同圖像。在對每個二維圖像進行矢量化并將其作為行向量放入適當?shù)木仃囍?，可以?gòu)建一個400×4 096的逐像素矩陣A。在該矩陣中，對象是ORL集合的面部圖像，而特征是圖像的像素值。為了在矩陣A上應(yīng)用Lloyd的啟發(fā)式，使用MATLAB的函數(shù)K-means，其中參數(shù)確定最大重復次數(shù)設(shè)置為30。

3.2 評估方法

3.3 實驗結(jié)果分析

圖1主要描述了在數(shù)據(jù)集Synth中，標準K-means算法、隨機投影、SVD降準方法的運行時間與不同投影維數(shù)的關(guān)系曲線。

圖1 算法運行時間比較曲線

圖2主要描述了在數(shù)據(jù)集Synth中，標準K-means算法、隨機投影、SVD降準方法的聚類目標函數(shù)與不同投影維數(shù)的關(guān)系曲線。

圖2 目標函數(shù)比較曲線

圖3 聚類精度比較曲線

圖3主要描述了在數(shù)據(jù)集Synth中，標準K-means算法、隨機投影、SVD降準方法的聚類精度與不同投影維數(shù)的關(guān)系曲線。

在綜合數(shù)據(jù)集中可以觀察到，與標準K-means算法相比，K-means算法的降維方法(RP和SVD)明顯更有效。更重要的是，圖3的準確度曲線表明，在這種情況下，維數(shù)降低方法也是準確的，即使相對(相對于k)小的r值。在這種情況下，數(shù)據(jù)集的聚類結(jié)果之間是完全分開的。因此，這些觀察結(jié)果表明，當應(yīng)用于分離良好的數(shù)據(jù)點時，K均值聚類的維數(shù)降低是有效的。實驗表明，使用較小的r值運行本文算法，例如r=20或r=30，實現(xiàn)了高斯混合的幾乎最佳分離，并且在幾個真實的聚類問題中表現(xiàn)良好。雖然對該算法進行更全面的實驗評估會提供更多信息，但初步實驗結(jié)果對于該算法在實踐中的表現(xiàn)而言是相當令人鼓舞的。

表1描述了在不同維度t下，K-means、RP和SVD在面部圖像數(shù)據(jù)集的聚類精度。

對于面部圖像數(shù)據(jù)集，首先通過運行2.1節(jié)算法來執(zhí)行實驗，其中所有內(nèi)容都是固定的，t表示投影數(shù)據(jù)的維度。然后，對于t的4個代表值，將算法與SVD降維方法以及在原始高維數(shù)據(jù)上運行Lloyd啟發(fā)式的方法進行比較，通過分析可以看出，在t=60時，對真實數(shù)據(jù)集的聚類效果與K-means算法聚類基本一樣。

表1 算法精度比較(實際數(shù)據(jù)集)

4 結(jié)論

本文研究了K-means聚類的降維問題。盡管專注于所提算法的理論基礎(chǔ)，但在實踐中測試了所提出的方法并得出結(jié)論，實驗結(jié)果非常令人滿意。使用所提出的方法降低了K-means算法的維數(shù)，降維后的聚類結(jié)果幾乎與運行K-means算法一樣準確?？偠灾?，本文描述了K-means聚類的一個可證明有效的特征提取算法。未來研究的一個方向是為K-means設(shè)計可證明有效的(1 +ε)誤差降維方法。