優(yōu)化加權(quán)多視角K-means聚類算法

賀艷芳，梁書田

(1.廣東理工學(xué)院 信息工程學(xué)院，廣東 肇慶 526100；2.河南理工大學(xué) 電氣工程與自動(dòng)化學(xué)院，河南 焦作 454000)

1 概 述

傳統(tǒng)的聚類算法根據(jù)數(shù)據(jù)集中存在的特征將未知的數(shù)據(jù)樣本進(jìn)行劃分，它根據(jù)這些特征按照某種相似性度量，使同一類的數(shù)據(jù)集具有相似性，而不同類的數(shù)據(jù)集盡可能不相似。目前較為傳統(tǒng)的聚類算法包括基于劃分的方法[1]、基于層次的方法[2]、基于網(wǎng)格的方法[3]和基于密度的方法[4]等。這些常見的聚類算法均是圍繞單一視角的聚類分析。然而當(dāng)前信息技術(shù)的發(fā)展越來越快，人們?cè)诂F(xiàn)實(shí)世界會(huì)遇到越來越多具有重要意義的多特征數(shù)據(jù)，即又稱為多視角數(shù)據(jù)。多視角數(shù)據(jù)存在于社會(huì)、經(jīng)濟(jì)和科學(xué)等方面。例如在醫(yī)學(xué)上，通過不同的視角來描述紅核細(xì)胞的密度、顏色、紋理、幾何特征等不同的特征，其中每個(gè)視角表示數(shù)據(jù)集的一種不同的度量值。多視角聚類通過分析同一數(shù)據(jù)簇的不同特征，利用特征之間的相似性成分，協(xié)調(diào)處理這些關(guān)系，讓多視角中的多特征形成互補(bǔ)，得到盡可能一致的聚類結(jié)果[5]。

經(jīng)過對(duì)傳統(tǒng)聚類分析方法的研究，挖掘出更有效的多視角聚類技術(shù)，該技術(shù)在聚類過程中使得具有多特征的多視角數(shù)據(jù)在聚類過程中協(xié)同學(xué)習(xí)，解決了復(fù)雜數(shù)據(jù)多特征問題。傳統(tǒng)聚類算法可能僅僅能處理復(fù)雜數(shù)據(jù)的一個(gè)特征，而早期的多視角聚類技術(shù)是考慮數(shù)據(jù)的每個(gè)視角，將每個(gè)視角作為獨(dú)立的聚類任務(wù)進(jìn)行處理，在得到每個(gè)視角對(duì)應(yīng)的聚類結(jié)果后，再利用集成學(xué)習(xí)機(jī)制選擇一個(gè)合適的集成學(xué)習(xí)策略將多個(gè)視角結(jié)果進(jìn)行集成，進(jìn)而得到最終的聚類結(jié)果[6-7]。

當(dāng)前，多視角聚類技術(shù)得到了迅速發(fā)展，越來越多的人對(duì)該技術(shù)感興趣，并建立了各種數(shù)學(xué)模型解決當(dāng)前面臨的問題。例如，Wang等[8]利用數(shù)據(jù)間的聯(lián)系進(jìn)行聚類，增加了各個(gè)數(shù)據(jù)屬性的關(guān)聯(lián)性；Bickel等[9]提出的多視角聚類算法，將每個(gè)視角作為獨(dú)立的數(shù)據(jù)集進(jìn)行K-means聚類，再將每個(gè)視角的聚類結(jié)果提供給其他視角使用，完成多視角聚類；Bickel等[10]提出的基于EM算法適用于多視角應(yīng)用場(chǎng)景的協(xié)同聚類算法Co-EM，文獻(xiàn)[11]將高維數(shù)據(jù)映射到不同低維空間，在低維空間對(duì)這些數(shù)據(jù)進(jìn)行多視角聚類；Cleuziou等[12]等提出了協(xié)同多視角模糊聚類算法Co-FKM。

通過研究多視角聚類算法，學(xué)習(xí)多視角算法的各種模型，發(fā)現(xiàn)多視角學(xué)習(xí)是利用數(shù)據(jù)集中的各種特征之間的聯(lián)系，充分利用各構(gòu)成視角的差異性和關(guān)聯(lián)性，使最終的學(xué)習(xí)結(jié)果趨于一致。多視角學(xué)習(xí)模型如圖1所示。

圖1 多視角學(xué)習(xí)模型

該模型的多視角聚類算法同時(shí)把每個(gè)視角的聚類結(jié)果融合在一起，在互補(bǔ)性和一致性原則下讓它們相互作用，實(shí)現(xiàn)各個(gè)視角間的協(xié)同學(xué)習(xí)，提高聚類的精確度，使得多視角聚類算法優(yōu)于傳統(tǒng)的單視角聚類，具有更有效的聚類性能。

在上述研究基礎(chǔ)上，文中提出了一種多視角K-means聚類算法，利用權(quán)重值分配各個(gè)視角的重要程度，引入常數(shù)確保權(quán)重值不為零，從而確保受噪聲干擾視角或異常視角不被忽視，所有視角協(xié)同學(xué)習(xí)，從而得到好的聚類結(jié)果。

2 單視角聚類算法

給定數(shù)據(jù)樣本(N為樣本總量，D為樣本維數(shù))，z為樣本的類中心，目標(biāo)函數(shù)為：

(1)

其中，zi為第i類的中心點(diǎn)；ε0為一個(gè)標(biāo)量，當(dāng)ε0屬于第j個(gè)樣本點(diǎn)，ε0等于1，否則等于0。根據(jù)拉格朗日求解法得到的聚類中心迭代表達(dá)式為：

(2)

K-means算法的思想是首先從一簇?cái)?shù)據(jù)集中隨機(jī)選取若干個(gè)合適的對(duì)象作為初始簇類中心，其次讓其他對(duì)象根據(jù)它們與簇類中心的距離加入到該類，讓一個(gè)類中的所有對(duì)象具有相似性，最后再根據(jù)距離重新計(jì)算每個(gè)簇的聚類中心，不斷重復(fù)這一過程直到收斂為止。

3 多視角K-means聚類算法

為了把具有多特征的數(shù)據(jù)用K-means表示，給每個(gè)視角的聚類分配一個(gè)權(quán)重向量W，滿足以下條件：

(3)

(4)

給每個(gè)視角分配一個(gè)權(quán)重值，用來衡量視角的重要程度。當(dāng)某個(gè)視角的數(shù)據(jù)較分散時(shí)，某個(gè)視角受噪聲干擾較大時(shí)，該視角容易被忽略，造成該視角的權(quán)重為0。文中通過引入了常數(shù)ε0，構(gòu)造新的目標(biāo)函數(shù)，如下：

(5)

利用拉格朗日乘子最優(yōu)化方法最小化式5，得到了MKSC算法聚類中心vk，權(quán)重向量wv的迭代表達(dá)式為：

(7)

MKSC的算法流程如下：

輸入：多視角樣本集view={view1,view2,…,viewv}(共v個(gè)視角)，而任意視角對(duì)應(yīng)的樣本集為viewk={x1,x2,…,xN},聚類數(shù)C(2≤C≤N),權(quán)重指數(shù)p,協(xié)同學(xué)習(xí)參數(shù)ε0，迭代閾值τ。

輸出：劃分聚類δ,聚類中心矩陣Z,權(quán)重矩陣W

Step2:通過式6更新計(jì)算聚類中心矩陣Z;

Step3:通過式7更新計(jì)算權(quán)重值矩陣W;

Step4:通過式5更新計(jì)算目標(biāo)函數(shù)JH;

Step5:如果‖Jk+1-Jk‖<τ，則算法結(jié)束，跳出循環(huán)，返回Step2。

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

4.1 實(shí)驗(yàn)結(jié)果的評(píng)價(jià)標(biāo)準(zhǔn)

為了評(píng)價(jià)MKSC算法的性能，應(yīng)用normalized mutual information (NMI)[12]和芮氏指標(biāo)rand index[13]作為評(píng)價(jià)聚類質(zhì)量的測(cè)量標(biāo)準(zhǔn)。它們的取值范圍在0到1之間。值越高，算法中得到的聚類結(jié)果越接近真實(shí)的聚類結(jié)果。

(8)

(2)芮氏指標(biāo)(rand index，RI)。

RI=2(d00+d11)/N(N-1)

(9)

其中,d00為數(shù)據(jù)點(diǎn)具有不同的類標(biāo)簽并且屬于不同類的配對(duì)數(shù)目；d11為數(shù)據(jù)點(diǎn)具有相同的類標(biāo)簽并且屬于同一類的配對(duì)點(diǎn)數(shù)目；N為數(shù)據(jù)集所有的對(duì)象數(shù)目。

4.2 實(shí)驗(yàn)結(jié)果對(duì)比

為了驗(yàn)證算法的有效性，將MKSC算法和多視角模糊聚類算法Co-FKM[14]、基于多任務(wù)的組合K-means算法CombKM[15]和在特征空間進(jìn)行協(xié)同聚類算法Co-clustering[16]在性能上進(jìn)行比較。

使用人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集(MF)驗(yàn)證MKSC算法的有效性。其中人工數(shù)據(jù)集中含有兩個(gè)視角，每個(gè)視角中包含700個(gè)數(shù)據(jù)樣本，每個(gè)數(shù)據(jù)樣本維度為2，每個(gè)視角中含有三個(gè)數(shù)據(jù)類簇，其中第二個(gè)視角數(shù)據(jù)存在噪聲點(diǎn)的干擾，這兩個(gè)視角如圖2所示。

(a)View_1

(b)View_2

表1為人工數(shù)據(jù)集在MKSC算法中的應(yīng)用。實(shí)驗(yàn)中選取ε0=0.000 4，通過p值的大小來對(duì)比聚類結(jié)果和權(quán)重值。其中View_1和View_2表示兩個(gè)視角的權(quán)重值。

表1 MKSC算法取不同p值的NMI值和權(quán)值

從實(shí)驗(yàn)結(jié)果可以看出，MKSC算法得到的聚類結(jié)果受p值的影響，p值越大，權(quán)重值分配越均勻。p值在[1.2,1.5]之間時(shí)，NMI值為最大。從圖2可以看出，視角2受噪聲干擾較嚴(yán)重，該視角的權(quán)重較小。視角1權(quán)重值大，對(duì)聚類結(jié)果的劃分較明顯。

為了進(jìn)一步分析MKSC算法在處理真實(shí)數(shù)據(jù)時(shí)的有效性，在UCI數(shù)據(jù)集中的multiple features dataset (MF)，即數(shù)字手寫體多特征數(shù)據(jù)集，進(jìn)行實(shí)驗(yàn)驗(yàn)證。該數(shù)據(jù)集包含6個(gè)視角，分別為Mfeat-fou(Mfo)、Mfeat-fac (Mfa)、Mfeat-kar(Mfk)、Mfeat-pix (Mfp)、Mfeat-zer (Mfz)、Mfeat-mor(Mfm)。結(jié)果如表2和圖3所示。

表2 各種算法在手寫體多特征數(shù)據(jù)集上的 聚類結(jié)果

圖3 算法MKSC在數(shù)據(jù)集MF的權(quán)重值

從實(shí)驗(yàn)結(jié)果可以看出，與算法CombKM、Co-clustering和Co-FKM相比，MKSC算法聚類效果更好，更接近于真實(shí)數(shù)據(jù)的分布，說明該算法的各視角協(xié)作能力更強(qiáng)。從權(quán)重值上看各視角的重要程度較均衡，上述原因使得Co-FKM算法的結(jié)果更接近于文中算法，但是對(duì)比下Mfa和Mfm視角權(quán)重值較大，說明該視角具有更好的劃分。

5 結(jié)束語

通過研究多視角聚類算法的各種模型，發(fā)現(xiàn)多視角聚類算法聚類結(jié)果更優(yōu)，精度更精確，在解決多視角任務(wù)時(shí)提出了一種優(yōu)化加權(quán)多視角K-means聚類算法。該算法利用權(quán)重的策略，為每個(gè)視角分配權(quán)重，通過引入常數(shù)優(yōu)化權(quán)重來解決受噪聲干擾視角和較分散的視角容易丟失的問題。實(shí)驗(yàn)結(jié)果表明，該算法具有較好的聚類效果。