基于隨機(jī)投影的K-means算法研究

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

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

0 引言

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

1 相關(guān)理論

1.1 近似K-means算法

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

(1)

(2)

(3)

1.2 隨機(jī)投影

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

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

(4)

2 基于隨機(jī)投影的K-means算法

2.1 基于隨機(jī)投影的K-means算法

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

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

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

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

(5)

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

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

(6)

定理簡(jiǎn)要證明：

A=Ak+Aρ-k

令:

證畢。

2.3 算法分析

3 實(shí)驗(yàn)與分析

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

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

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

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

3.2 評(píng)估方法

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

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

圖1 算法運(yùn)行時(shí)間比較曲線

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

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

圖3 聚類精度比較曲線

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

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

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

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

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

4 結(jié)論

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