一種可重疊子空間K-Means聚類算法

劉宇航,馬慧芳,2,劉海姣,余 麗

(1.西北師范大學(xué) 計算機(jī)科學(xué)與工程學(xué)院,蘭州 730070;2.桂林電子科技大學(xué) 廣西可信軟件重點(diǎn)實(shí)驗(yàn)室,廣西 桂林 541004)

0 概述

隨著計算機(jī)技術(shù)的不斷發(fā)展,聚類應(yīng)用領(lǐng)域產(chǎn)生了大量的高維稀疏數(shù)據(jù),如文檔數(shù)據(jù)、基因表達(dá)數(shù)據(jù)等維度可達(dá)到上千維甚至更高[1]。聚類是數(shù)據(jù)挖掘、模式識別等研究方向的重要內(nèi)容之一,目標(biāo)是將數(shù)據(jù)或者一組對象分為若干個類簇,使同類簇中的數(shù)據(jù)具有較大的相似性,不同簇之間數(shù)據(jù)盡可能有較大的相異性。在現(xiàn)實(shí)世界的數(shù)據(jù)中,針對特定類簇而言,類簇中的大多數(shù)成員更聚焦于數(shù)據(jù)所具有的少數(shù)屬性信息。此外,數(shù)據(jù)中還往往存在類簇間重疊和離群點(diǎn)情況。如在一組文檔集中,由于單詞可能屬于多個主題使得簇與簇之間是重疊的,且可能會出現(xiàn)一些不屬于任何主題的詞匯而產(chǎn)生離群點(diǎn);在社交網(wǎng)絡(luò)中,社交關(guān)系往往非常稀疏,并且個體扮演的多重角色使得聚類后得到某些用戶不屬于任何類簇。考慮到高維數(shù)據(jù)的復(fù)雜性、稀疏性和多樣性等特點(diǎn)會制約聚類算法的有效性,必須對高維數(shù)據(jù)進(jìn)行特殊的處理[2]。因此,針對高維稀疏的數(shù)據(jù)進(jìn)行屬性子空間劃分[3],并利用特定屬性子空間進(jìn)行聚類分析具有一定的研究意義。

經(jīng)典的K-Means[4]聚類算法將數(shù)據(jù)對象劃入某個特定簇且在低維數(shù)據(jù)上表現(xiàn)良好。然而,現(xiàn)實(shí)數(shù)據(jù)往往存在重疊和離群點(diǎn),利用K-Means算法聚類此類數(shù)據(jù)效果欠佳。目前對此進(jìn)行改進(jìn)的代表性算法主要有:文獻(xiàn)[5]提出的OKM算法,該算法是K-Means方法的擴(kuò)展,考慮了類簇間的重疊性,但忽略了數(shù)據(jù)中離群點(diǎn)情況;文獻(xiàn)[6]提出了NEO-K-Means算法,該方法既考慮了類簇之間的重疊性,也考慮了存在離群數(shù)據(jù)的情況,但忽略了類簇中的屬性子空間信息。此外,作為傳統(tǒng)聚類算法在高維空間中的延伸,基于子空間聚類算法認(rèn)為每個類簇是由屬性子集標(biāo)識的一組數(shù)據(jù),且不同類簇可以用不同屬性子集表示。子空間確定方式通常有兩種基本技術(shù),即自下而上搜索策略和自上向下搜索策略[7]。基于這兩個搜索方向,研究人員設(shè)計了不同的子空間聚類算法[8-9],如文獻(xiàn)[10]提出的EWKM算法,該算法基于熵加權(quán)屬性子空間聚類,針對K-Means算法在屬性子空間上修正,文獻(xiàn)[11]提出結(jié)合屬性子空間和子圖聚類方法,可以自動選擇屬性特征,然后根據(jù)選擇后的結(jié)果進(jìn)行聚類分析。

本文提出一種可重疊子空間K-Means聚類算法(OS-K-Means)。設(shè)計類簇子空間計算策略,在每輪迭代過程中動態(tài)更新各類簇的屬性子空間。通過定義合理的目標(biāo)函數(shù)約束條件對傳統(tǒng)的K-Means聚類算法進(jìn)行修正,從而計算每個類簇中各個維度的權(quán)重,使用權(quán)重值來標(biāo)識不同類簇中維度的相對重要性,同時通過加入特定參數(shù)用來控制類簇的重疊程度以及數(shù)據(jù)中離群點(diǎn)的數(shù)量。

1 準(zhǔn)備工作

(0≤βn≤n),意味著最多βn數(shù)據(jù)點(diǎn)可以被認(rèn)為是離群點(diǎn)。當(dāng)βn?n時,使得多數(shù)據(jù)點(diǎn)可以被分配給類簇。

現(xiàn)有的多數(shù)維度加權(quán)的聚類算法可以執(zhí)行子空間聚類的任務(wù)[12-13]。與在整個數(shù)據(jù)集的維度上分配權(quán)重不同,子空間聚類為每個類簇中的每個維度分配權(quán)重,因此,不同的類簇具有不同的權(quán)重值集合,為了保持可擴(kuò)展性,在這些新的子空間聚類算法中采用了K-Means聚類過程。在每次迭代中,添加一個步驟來計算權(quán)重值。作為對K-Means聚類的一個直接擴(kuò)展,利用維度加權(quán)算法[14]最小化以下目標(biāo)函數(shù)[15-16]:

(1)

約束條件:

2 可重疊子空間K-Means聚類算法

2.1 OS-K-Means目標(biāo)函數(shù)

(2)

約束條件:

目標(biāo)函數(shù)式(2)中的第一項是簇內(nèi)分散程度的總和,第二項是負(fù)權(quán)重熵,正參數(shù)γ可用于控制多維度子空間聚類的激勵強(qiáng)度。

2.2 OS-K-Means算法

本節(jié)提出OS-K-Means算法用于優(yōu)化2.1節(jié)中的目標(biāo)函數(shù)。對式(2)中帶有約束的目標(biāo)函數(shù)進(jìn)行最小化時,形成一類約束非線性優(yōu)化問題,使得目標(biāo)函數(shù)的解是未知的。因此優(yōu)化目標(biāo)函數(shù)的常用方法是對指示矩陣U、簇中心矩陣C和簇權(quán)重矩陣W進(jìn)行部分優(yōu)化。首先固定U和W,根據(jù)U對目標(biāo)函數(shù)進(jìn)行最小化。然后,固定U和C,根據(jù)W對目標(biāo)函數(shù)進(jìn)行最小化。最后,固定U和W,根據(jù)C對目標(biāo)函數(shù)進(jìn)行最小化。通過迭代方法使得目標(biāo)函數(shù)趨于局部極小值。

對于固定U和C,根據(jù)W在對目標(biāo)函數(shù)進(jìn)行最小化時,使用如下的函數(shù)進(jìn)行更新目標(biāo)函數(shù)。wlt的計算公式由下列定理給出:

定理1目標(biāo)函數(shù)最小,當(dāng)且僅當(dāng)給定U和C,下式成立:

(3)

證明使用拉格朗日乘數(shù)技術(shù)來獲得以下無約束最小化問題:

minF1({wli},{δl})=

(4)

其中,[δ1,δ2,…,δk]是一個含有對應(yīng)約束的拉格朗日乘數(shù)的向量,δl代表對應(yīng)第l個約束的拉格朗日乘數(shù)。上述優(yōu)化問題可以分解為k個獨(dú)立的最小化問題:

(5)

對于l=1,2,…,k,F1l分別對δl和wli求偏導(dǎo),可得:

(6)

(7)

由此可以得到:

(8)

(9)

因此,有:

(10)

將式(10)代入式(8),得:

(11)

定理2目標(biāo)函數(shù)最小,當(dāng)且僅當(dāng)給定固定U和W,C被更新,可得:

(12)

從圖1可以看出,首先對待處理數(shù)據(jù)預(yù)處理得到數(shù)據(jù)矩陣X。其次得到數(shù)據(jù)矩陣后隨機(jī)初始化簇中心,根據(jù)式(2)中的第一項可以得到數(shù)據(jù)點(diǎn)與簇中心的加權(quán)距離矩陣WD,將數(shù)據(jù)點(diǎn)分別給距離最近的簇,得到指示矩陣U。再次利用U與X對每個簇中的數(shù)據(jù)每一維度求其平均值,更新簇中心矩陣C。然后根據(jù)式(3)對簇中心權(quán)重矩陣W更新。最后得到矩陣C、U和X計算目標(biāo)函數(shù)的值,查看目標(biāo)函數(shù)值是否收斂,若已收斂,則結(jié)束算法;若仍未收斂,則迭代上述過程,直到目標(biāo)函數(shù)收斂或者達(dá)到最大迭代次數(shù),結(jié)束算法。

圖1 可重疊的子空間K-Means聚類算法流程Fig.1 Procedure of overlapping subspace K-Meansclustering algorithm

本文使用文獻(xiàn)[17]提出的K-Means++初始類簇中心。如算法1所示,第4行是計算得到每一個數(shù)據(jù)點(diǎn)與所有簇中心的加權(quán)距離矩陣。第5行、第6行初始化一些參數(shù)。第8行～第11行用來判斷非離群點(diǎn)個數(shù)是否已經(jīng)滿足要求,若仍未滿足,需將非離群點(diǎn)放入簇中。第12行用來判斷重疊度是否達(dá)到要求,若重疊度仍未達(dá)到要求,將數(shù)據(jù)仍舊分配,否則停止分配數(shù)據(jù)。第17行用來更新簇中心。第18行使用式(3)進(jìn)行更新權(quán)重矩陣。第19行用來計算目標(biāo)函數(shù)的值,判斷目標(biāo)函數(shù)是否收斂。

算法1OS-K-Means(U,C,W)

輸入數(shù)據(jù)點(diǎn)X={x1,x2,…,xn},簇的個數(shù)k,控制重疊的參數(shù)α,控制離群點(diǎn)數(shù)量的參數(shù)β,正參數(shù)γ

輸出指示矩陣U

2.初始化權(quán)重矩陣[wli]k×m

3.while 目標(biāo)函數(shù)沒有收斂 and t

4.計算每一個數(shù)據(jù)點(diǎn)與所有簇中心的加權(quán)距離矩陣[djl]n×k

5.初始化全為0指示矩陣U

6.初始化 T=φ,S=?,p=0

7.while p<(n+αn) do

8.if p

10.S=S∪{j*}

11.else

13.end if

14.T=T∪{(j*,l*)}

15.p=p+1

16.end while

17.根據(jù)式(12)更新簇中心

18.根據(jù)式(3)更新權(quán)重矩陣

19.根據(jù)式(2)計算目標(biāo)函數(shù)值

20.t=t+1

21.end while

2.3 收斂性與復(fù)雜度分析

2.3.1 收斂性分析

OS-K-Means算法在有限次迭代后收斂,將把數(shù)據(jù)劃分成k個類簇,可能的劃分?jǐn)?shù)是有限的。設(shè)Ut1表示第t1次迭代后的類簇劃分情況。給定Ut,根據(jù)式(12)可得到Ct,根據(jù)式(3)計算可得到Wt。設(shè)Ut1=Ut2,則Ct1=Ct2與Wt1=Wt2,故:

F(Ut1,Ct1,Wt1)=F(Ut2,Ct2,Wt2)

而OS-K-Means算法產(chǎn)生的上述序列是嚴(yán)格減少的。因此,OS-K-Means算法在有限次數(shù)的迭代后收斂。

2.3.2 復(fù)雜度分析

OS-K-Means算法涉及到主要的計算步驟有以下3步:

1)劃分。將數(shù)據(jù)分類為k個可重疊的類簇,計算加權(quán)距離矩陣,復(fù)雜性為O(nk);再根據(jù)加權(quán)距離矩陣將數(shù)據(jù)點(diǎn)進(jìn)行劃分時,時間復(fù)雜性為O((n+αn)×nk),由于α經(jīng)常比較小,因此復(fù)雜度為O(n2k)。

2)更新簇中心。給定指示矩陣U,更新簇中心就是在同一個類簇中找到數(shù)據(jù)對象的均值。因此,對于k個類簇,計算復(fù)雜度是O(mnk)。

3)更新權(quán)重矩陣。給定U與C,根據(jù)式(3)進(jìn)行更新權(quán)重矩陣,只需遍歷整個數(shù)據(jù)集一次來更新權(quán)重矩陣,因此復(fù)雜度為O(mnk)。

如果聚類過程需要t次迭代才收斂,則該算法的總計算復(fù)雜度為max(O(tmnk),O(tn2k))。

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

為了驗(yàn)證OS-K-Means算法的有效性,本文在真實(shí)數(shù)據(jù)集和人工數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)驗(yàn)證。首先對實(shí)驗(yàn)數(shù)據(jù)進(jìn)行描述,然后設(shè)計兩組實(shí)驗(yàn)對本文方法進(jìn)行驗(yàn)證,并對實(shí)驗(yàn)結(jié)果作進(jìn)一步分析。

3.1 實(shí)驗(yàn)數(shù)據(jù)集與評價指標(biāo)

第1組數(shù)據(jù)集是公開可用的20-Newsgroups數(shù)據(jù)集。該數(shù)據(jù)集均勻分布著不同主題的新聞組集合,其中一些新聞組的主題非常類似,同時新聞數(shù)據(jù)中存在不屬于任何主題的單詞。表1為選取新聞組數(shù)據(jù)集,其中,name是文件夾名字,nd為選擇文件數(shù)。對原始文本數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)預(yù)處理,并用TF-IDF加權(quán)得到數(shù)據(jù)矩陣。

表1 20-Newsgroups數(shù)據(jù)集Table 1 20-Newsgroups datasets

表2 人工數(shù)據(jù)集Table 2 Manual datasets

作為K-Means聚類算法的一種擴(kuò)展,本文使用歸一化互信息(NMI)[18]和F1分?jǐn)?shù)(F1 Score)[19]作為聚類結(jié)果的評價指標(biāo)。

3.2 結(jié)果分析

3.2.1 參數(shù)設(shè)置

OS-K-Means方法包括3個重要參數(shù)α、β和γ,本節(jié)討論如何在實(shí)驗(yàn)中設(shè)置這3個參數(shù)。參數(shù)α和β的取值可通過使用下面討論的啟發(fā)式規(guī)則進(jìn)行估計。參數(shù)γ的取值通過其對聚類結(jié)果的影響實(shí)驗(yàn)進(jìn)行估計。

對估計參數(shù)β,先運(yùn)行EWKM算法得到數(shù)據(jù)點(diǎn)與其最近簇中心的距離向量D=[d1,d2,…,dn]T,其中di(1≤i≤n)表示數(shù)據(jù)點(diǎn)i與其最近的簇的簇中心之間的距離。計算di(i=1,2,…,n)的平均值(用μ表示)和標(biāo)準(zhǔn)差(用σ表示)。如果距離di大于μ+3σ,則本文將數(shù)據(jù)點(diǎn)i視為離群點(diǎn),即通過遵循統(tǒng)計學(xué)中的3σ法則,距離其最近的簇的簇中心距離大于平均值的3個標(biāo)準(zhǔn)差,便認(rèn)為數(shù)據(jù)點(diǎn)是離群點(diǎn)。通過這種方式,可以估計離群點(diǎn)的數(shù)量,從而得到β值。

圖2為本文算法在3個人工數(shù)據(jù)集上關(guān)于不同γ值的聚類結(jié)果。圖2(a)展示了γ值對F1的影響,圖2(b)展示了γ值對NMI的影響。由圖2可以看出,當(dāng)γ從0.1增長至0.5時,熵權(quán)約束重要性增加導(dǎo)致聚類性能較小幅度的增長,F1值與NMI值會有較小幅度的增加;當(dāng)γ從0.5增長至6時,聚類精度對γ不敏感。結(jié)果表明,OS-K-Means算法的聚類結(jié)果對參數(shù)γ具有魯棒性。

圖2 3個人工數(shù)據(jù)集上γ值的聚類結(jié)果Fig.2 Clustering results of γ values on three artificial datasets

3.2.2 算法性能分析

為評估本文所提出算法的有效性,選取EWKM[10]、NEO-K-Means[6]、OKM[5]、MOC[20]等典型聚類算法與OS-K-Means與進(jìn)行比較,其中,EWKM算法基于屬性子空間聚類,然而未涉及類簇間重疊與離群點(diǎn),NEO-K-Means算法考慮了可重疊與離群點(diǎn)卻未考慮屬性子空間聚類,MOC與OKM算法研究了可重疊情況,但忽略了屬性子空間以及離群點(diǎn)。在MOC算法中,本文使用文獻(xiàn)中提供的默認(rèn)參數(shù)。關(guān)于本文算法和NEO-K-Means方法,通過3.2.1節(jié)中描述的策略估計β參數(shù),由于簇的個數(shù)相對較小,將α設(shè)置為一個小程度的重疊α=0.1。對于EWKM和本文的γ參數(shù),根據(jù)3.2.1節(jié)的策略使γ=0.5。為評估每種方法得到的聚類結(jié)果,對每個算法進(jìn)行5次實(shí)驗(yàn),分別計算每次實(shí)驗(yàn)結(jié)果的F1值和NMI值,并記錄實(shí)驗(yàn)中每個方法的最好、最壞和平均結(jié)果。如表3所示,NMI指標(biāo)和F1指標(biāo)的算法排名略有不同,如在20-Newsgroups數(shù)據(jù)集上,EWKM的F1分?jǐn)?shù)略低,但是NMI分?jǐn)?shù)相對較好。本文算法在F1和NMI指標(biāo)方面始終優(yōu)于其他算法。值得注意的是,對于相對較低維度的數(shù)據(jù),NEO聚類算法的F1分?jǐn)?shù)和NMI分?jǐn)?shù)會有一定的提升,表明NEO對于處理低維數(shù)據(jù)有一定的優(yōu)勢。同時,當(dāng)在維度相對較高、類簇重疊程度較低的情況下,EWKM算法性能也會提高。可以看出,對于高維數(shù)據(jù),本文算法可以將數(shù)據(jù)較好地分配到數(shù)據(jù)模型中,有助于識別真實(shí)的類簇。

表3 不同算法的聚類結(jié)果Table 3 Clustering results of different algorithm %

4 結(jié)束語

本文提出一種可重疊子空間K-Means算法,該算法考慮高維數(shù)據(jù)中的可重疊屬性和可能出現(xiàn)的離群點(diǎn)情況,解決了對高維稀疏數(shù)據(jù)進(jìn)行聚類時效果欠佳的問題。通過在兩種不同數(shù)據(jù)集上的驗(yàn)證結(jié)果表明,與NED-K-Means等算法相比,本文算法對高維稀疏數(shù)據(jù)可以進(jìn)行更好的聚類。下一步考慮將數(shù)據(jù)本身與屬性相結(jié)合,來整體衡量聯(lián)合聚類與子空間的應(yīng)用。