基于成對約束的半監(jiān)督聚類方法

陶性留，俞 璐，王曉瑩

(1.陸軍工程大學(xué) 通信工程學(xué)院，江蘇 南京 210007；2.陸軍工程大學(xué) 指揮控制工程學(xué)院，江蘇 南京 210007)

0 引言

現(xiàn)實社會中，面臨的數(shù)據(jù)越來越多，越來越寬泛，越來越復(fù)雜，同樣數(shù)據(jù)特征的維度也越來越高。如何去挖掘有價值的信息一直是廣受關(guān)注的熱點。聚類是數(shù)據(jù)挖掘和模式識別的重要工具，它是將數(shù)據(jù)樣本劃分為不同的簇，使同一簇的數(shù)據(jù)樣本具有較高的相似性，常見的方法有K-means[1-2]、FCM[3-4]等。而半監(jiān)督聚類[5]作為半監(jiān)督學(xué)習(xí)的一個重要分支，它以無監(jiān)督的聚類算法為基礎(chǔ)，通過利用少量的監(jiān)督信息來提高聚類的性能。目前，半監(jiān)督聚類中常見的先驗知識表現(xiàn)為部分樣本的類標(biāo)簽信息或是反映兩樣本是否歸于同一簇的成對約束信息。所謂成對約束關(guān)系具體分為兩種：

(1)兩個樣本同屬于一個簇團(必須鏈接集Must-link，ML);

(2)兩個樣本屬于不同簇團(不能鏈接集Cannot-link，CL)。很顯然，這是一種相對較弱的指導(dǎo)信息，因為判斷兩個樣本是否屬于同一簇團要比判斷它們分屬于哪個簇團更加容易。通?？梢酝ㄟ^生活經(jīng)驗或者常識來判斷。

基于成對約束的半監(jiān)督聚類方法的基本思想是利用先驗監(jiān)督信息來調(diào)整樣本數(shù)據(jù)之間的作用力，根據(jù)少量被正確劃分的樣本數(shù)據(jù)，促使其近鄰能被正確地劃分，進而實現(xiàn)整個數(shù)據(jù)集的劃分。該聚類算法通常在經(jīng)典的算法框架下，合理設(shè)計出目標(biāo)函數(shù)再進行一定程度的優(yōu)化之后得到更加符合實際，更加令人滿意的聚類算法。本文考慮在之前研究的FCM-NMF[6]算法上添加成對約束條件，以使聚類性能得到進一步的提高。

1 相關(guān)工作

1.1 NMF算法[7]

(1)

(2)

其中⊙是Hadamard積運算符，代表矩陣對應(yīng)元素相乘。這時用系數(shù)矩陣HT代替原始矩陣，就可以實現(xiàn)對原始矩陣進行降維，從而減少存儲空間，減少計算資源。

1.2 基于非負矩陣分解和模糊C均值的聚類方法(FCM-NMF)

通過利用非負矩陣分解獨特的優(yōu)勢，不僅可以進行降維，而且物理意義明確。但也有可能破壞數(shù)據(jù)樣本之間的本質(zhì)結(jié)構(gòu)，影響聚類效果。為了減少負面影響，希望在NMF壓縮樣本數(shù)據(jù)的過程中進行模糊聚類。對于大量高維數(shù)據(jù)，通過NMF提取樣本的本質(zhì)特征，同時保留作FCM模糊分析聚類，提出了新的聚類算法FCM-NMF。它將NMF分解對原始數(shù)據(jù)樣本的影響加入到FCM的目標(biāo)函數(shù)中，由交替迭代產(chǎn)生的新的低維表示矩陣可以用來描述樣本之間的本質(zhì)關(guān)系。改進目標(biāo)函數(shù)如下：

(3)

式(3)中，λ≥0是平衡系數(shù);第一項表示模糊C均值聚類框架，第二項表示利用NMF算法處理原始數(shù)據(jù)的過程對聚類的影響程度。

使用梯度下降法和交替迭代法解得各變量的更新公式如下：

(4)

i=1,2,···,c;j=1,2,···,n

(5)

i=1,2,···,c;j=1,2,···,n

(6)

(7)

H=H⊙[1×sum(Uf)]T

1.3 基于非負矩陣分解的約束聚類[8]

基于非負矩陣分解的約束聚類的主要思想在于：當(dāng)給定數(shù)據(jù)集X、必須鏈接集ML和不能鏈接集CL時，希望通過借助非負矩陣分解的手段，在FCM-NMF的聚類框架中去尋找?guī)в邢闰炛R信息的系數(shù)表示矩陣H。可以構(gòu)造以下目標(biāo)函數(shù)：

(8)

其中定義了監(jiān)督矩陣R，它是由先驗知識構(gòu)成的，反映了樣本i與樣本j之間的成對約束關(guān)系。

(9)

Must-link上兩點之間的相似性被強制近似為1，CL上兩點之間的相似性被強制近似為0。同時定義了價值系數(shù)矩陣A，其元數(shù)α與β表示所確定的ML與CL的重要性，其數(shù)值在0～1之間。

(10)

HHT是可以近似監(jiān)督矩陣R，從而解決了利用系數(shù)表示矩陣來表示約束就成了問題，使得模型物理意義得以明確。然后，進行優(yōu)化目標(biāo)函數(shù)，利用交替迭代法求解出基矩陣W和系數(shù)表示矩陣H的更新公式：

(11)

(12)

2 基于成對約束的半監(jiān)督聚類方法

2.1 模型建立

由相關(guān)知識可知，基于非負矩陣分解和模糊C均值的聚類方法(FCM-NMF算法)，其核心思想利用NMF作為特征提取的手段，為了盡可能不破壞樣本之間的本質(zhì)聯(lián)系，將特征提取手段與聚類過程加以結(jié)合，融合NMF和FCM算法改變目標(biāo)函數(shù)的形式，生成新的低維表示矩陣。該算法物理意義較為清晰，同時在實驗中證明了其正確性和有效性。本節(jié)考慮將成對約束條件加入FCM-NMF的目標(biāo)函數(shù)框架中，通過少量監(jiān)督信息的引入，進一步改善聚類性能。改進的目標(biāo)函數(shù)如下所示：

(13)

在公式(13)中，λ≥0是平衡系數(shù)，f是模糊系數(shù)，其值介于1～2.5之間。第一項表示模糊C均值聚類框架，hj到vi的歐幾里得距離用dij表示。第二項表示加入了成對約束監(jiān)督信息的NMF算法處理原始數(shù)據(jù)的過程對聚類的影響程度。當(dāng)約束數(shù)量為0時，該算法退化為FCM-NMF算法。

2.2 模型求解

很明顯，公式(13)的目標(biāo)函數(shù)是非凸的，解出它的全局最優(yōu)是不實際的。因此，利用交替迭代法則去探索非凸函數(shù)的局部最優(yōu)解是一個可行的辦法。通過迭代以下步驟來解決優(yōu)化問題，直到目標(biāo)函數(shù)收斂或超出閾值條件:

(14)

i=1,2,…,c;j=1,2,…,n

(2)固定W,H，U，通過V最優(yōu)化J。V的更新準(zhǔn)則為:

(15)

i=1,2,…,c;j=1,2,…,n

(3)固定V，H，U，通過W最優(yōu)化J。W的更新規(guī)則與NMF算法一致，為:

(16)

(4)固定W，V，U，通過H最優(yōu)化J。

(17)

其中，H=H⊙[1×sum(Uf)]T。1 代表具有c行的全1向量，Uf是指U矩陣的對應(yīng)每個元素的f次冪。利用梯度下降法得到以下附加的更新規(guī)則:

(18)

δ是控制梯度下降步長的參數(shù)矩陣。令

(19)

然后，能得到：

由于會展旅游業(yè)相關(guān)制度的不完善，也導(dǎo)致了成都市會展業(yè)和旅游業(yè)的融合不暢，由此導(dǎo)致會展旅游業(yè)的整體營銷模式不成體系，發(fā)展滯后。目前成都市會展旅游業(yè)的營銷模式主要還是以承辦單位為主，很多會展雖然主辦方為政府和行業(yè)協(xié)會，但是這些單位往往不會參與對展會的營銷，而是由承辦單位來進行營銷宣傳，但是其作用肯定是不如主辦單位的影響力大。旅游管理部門很少關(guān)注會展旅游這一方面，在營銷上也很少配合承辦單位，常常出現(xiàn)會展旅游業(yè)中旅游業(yè)管理缺位的局面。承辦單位在會展?fàn)I銷模式上也較為傳統(tǒng)，缺乏創(chuàng)新。

(20)

H最終的更新公式為：

(21)

Ω=XTW+2(A⊙R⊙AT)H

+4(A⊙A)(H⊙H⊙H)

Λ=HWTW+2(A⊙(HHT)⊙AT)H

+4(A⊙A)(H⊙H⊙H)

2.3 聚類算法

基于成對約束的半監(jiān)督聚類算法具體流程如表1所示。通過上述推導(dǎo)求解，可以獲得基矩陣W，系數(shù)矩陣H，隸屬度矩陣U，聚類中心矩陣V的更新表達公式。W是降維后的低秩空間的表現(xiàn)形式，H是原始數(shù)據(jù)X經(jīng)降維后的低維表達方式，V是該聚類過程中所形成的簇中心向量的組合形式，而隸屬度矩陣U是對所有樣本進行軟聚類的模糊隸屬度的呈現(xiàn)方式，Uij越大，則反映樣本j屬于簇i的概率越大，可根據(jù)其獲取樣本的標(biāo)簽向量Y∈R1×n。

表1 基于成對約束的半監(jiān)督聚類算法

3 實驗結(jié)果與分析

3.1 實驗環(huán)境與方法

在本節(jié)中，通過在wdbc數(shù)據(jù)集和wine數(shù)據(jù)集兩個UCI驗證集上的實驗驗證基于成對約束的半監(jiān)督聚類算法的性能，包含在不同數(shù)量的監(jiān)督信息的指導(dǎo)下其算法性能的變化情況和價值系數(shù)的變動對聚類準(zhǔn)確率的影響。所有這些算法都是在MATLAB R2014a中實現(xiàn)的。將這些算法的最大迭代次數(shù)設(shè)置為10 000，并在接下來的所有實驗中保持不變。針對每種算法實驗，分別進行20次，并將實驗數(shù)據(jù)結(jié)果平均值予以記錄。表2顯示了驗證數(shù)據(jù)集的統(tǒng)計信息。并且選取了3種半監(jiān)督聚類算法與之對比，分別是PMF[9]、SS-NMF[10]和CCSR[5]。

表2 驗證數(shù)據(jù)集的統(tǒng)計信息

PMF算法分別將樣本之間的約束關(guān)系ML和CL抽象為樣本數(shù)據(jù)結(jié)構(gòu)關(guān)系的正邊和負邊，而利用先驗監(jiān)督信息構(gòu)造的鄰接矩陣則是通過圖正則化進行處理。SS-NMF是一種基于Symmetric NMF的約束聚類算法，它對滿足ML的樣本進行獎勵，對違反CL的樣本進行懲罰，同時修改樣本的鄰接矩陣。CCSR算法將數(shù)據(jù)點映射到一個新的特征空間，同時讓其滿足約束條件，它是圖聚類的一種方式，支持非線性可分數(shù)據(jù)。

3.2 評價標(biāo)準(zhǔn)

對于每個數(shù)據(jù)集，選取準(zhǔn)確率(ACC)、歸一化互信息(NMI)和F度量(F-score)作為聚類效果的評價指標(biāo)。下面的公式是本實驗聚類的評價指標(biāo)。

(22)

式中，TP是指在同一個類中聚集的兩個文檔是正確分類的，TN是指在同一個類中聚集的兩個文檔是正確分開的。FP表示不應(yīng)該屬于一個類別的文檔應(yīng)該屬于錯誤的類別，F(xiàn)N表示不應(yīng)該被分開的文檔應(yīng)該屬于錯誤的類別。

(23)

聚類中常用NMI來衡量兩種聚類結(jié)果的接近程度。PAB(a,b)表示A和B的聯(lián)合概率分布，H(A,B)表示兩類結(jié)果的聯(lián)合熵。

(24)

(25)

(26)

F-score是一種考慮到信息檢索的精度和召回程度，以便于不同技術(shù)或系統(tǒng)之間進行結(jié)果比較的測量方法。在上面的公式中，P和R分別表示信息的精度和召回率。上述三個聚類評價指標(biāo)的取值均在0～1之間，指標(biāo)值越大，聚類效果越好。

3.3 實驗結(jié)果與分析

通過觀察圖1，從總體來看，隨著約束對的增加，兩個數(shù)據(jù)集上的聚類性能趨勢上均朝著好的方向發(fā)展，在wdbc數(shù)據(jù)集和wine數(shù)據(jù)集上實驗中其準(zhǔn)確率最好可達95.86%和93.10%，較沒有約束的聚類算法性能有著極大的改善，說明了成對約束信息確實可以指導(dǎo)聚類過程，同時也說明該算法優(yōu)于FCM-NMF算法，驗證了該算法的正確性和有效性。從細節(jié)上來說，在隨著約束信息增加的有些過程，其算法性能不但沒有提高，反而降低了。這也是一種合理的現(xiàn)象，原因在于，首先是約束信息是通過隨機方式獲取的，有些樣本之間的關(guān)系對這個數(shù)據(jù)集結(jié)構(gòu)刻畫得更深入，而有些關(guān)系早已在FCM-NMF算法基礎(chǔ)上明確，其指導(dǎo)聚類的過程意義不大。再者由于成對約束是一種弱指導(dǎo)信息，模型的輸出樣本也許不一定滿足成對約束關(guān)系，有可能會衍生出輸出模型與監(jiān)督信息不一致的性能平衡問題。

圖1 wdbc和wine數(shù)據(jù)集上聚類性能

圖2顯示了wdbc和wine數(shù)據(jù)集上價值系數(shù)α和β的變動對聚類準(zhǔn)確率的影響。在兩個數(shù)據(jù)集上分別加入九組和五組的約束信息，通過調(diào)節(jié)價值系數(shù)的數(shù)值觀察其聚類準(zhǔn)確率的變化情況。通過大量實驗可以看出價值系數(shù)α與β設(shè)定對聚類性能的影響匪淺，它們反映了的半監(jiān)督信息ML與CL對聚類的重要性。該參數(shù)的設(shè)定與數(shù)據(jù)集本身有著密切的關(guān)系。在本實驗中，將wdbc數(shù)據(jù)集中α設(shè)為0.7，β設(shè)為0.5可以尋求到準(zhǔn)確率的局部最優(yōu)解。而在wine數(shù)據(jù)集中α設(shè)為0.8，β設(shè)為0.9可以尋求到局部最優(yōu)解。

圖2 wdbc和wine數(shù)據(jù)集上價值系數(shù)α和β的變動對聚類準(zhǔn)確率的影響

圖3顯示了wdbc和wine數(shù)據(jù)集上各半監(jiān)督聚類算法性能對比圖。首先可以看到，在兩個數(shù)據(jù)集上，隨著成對約束數(shù)目增加，各算法均呈現(xiàn)上升趨勢。再者，CCSR在wdbc數(shù)據(jù)集上的性能表現(xiàn)很好，但在wine數(shù)據(jù)集上性能很差，或許因為在wine數(shù)據(jù)集上的監(jiān)督信息不夠，不足以支持其達到最佳效果。相反SS-NMF在wine數(shù)據(jù)集上性能非常好，但是在wdbc數(shù)據(jù)集上其劣勢卻很明顯。因為SS-NMF修改的是鄰接矩陣，而不是直接改變目標(biāo)函數(shù)。PMF算法總體性能良好，在驗證集上，比無監(jiān)督聚類準(zhǔn)確率最佳分別改善可以接近10%和8%。相較于本算法差距比較明顯，因為PMT在獎勵ML時約束的提供了一個負項，這對于整體聚類意義不大。通過驗證集的實驗驗證了所提的基于成對約束的半監(jiān)督聚類方法的有效性和穩(wěn)定性。

圖3 wdbc和wine數(shù)據(jù)集上各半監(jiān)督聚類算法性能對比

4 結(jié)論

本文提出了基于成對約束的半監(jiān)督聚類方法。其核心思想是在FCM-NMF算法的基礎(chǔ)上，依靠少量的成對約束監(jiān)督信息的加入，改善整體聚類性能。但也有可能衍生出輸出模型與監(jiān)督信息不一致的性能平衡問題，有待作深入探討。下一步考慮將成對約束條件作為監(jiān)督信息應(yīng)用于多視角聚類任務(wù)，并針對這個問題展開研究。