基于功效散度和成對約束的半監(jiān)督聚類算法

向思源，金應(yīng)華，徐圣兵

（廣東工業(yè)大學(xué)應(yīng)用數(shù)學(xué)學(xué)院，廣東廣州510520）

在當(dāng)今大數(shù)據(jù)時(shí)代,信息技術(shù)迅猛發(fā)展，極大地提高了數(shù)據(jù)收集和存儲(chǔ)能力，各個(gè)領(lǐng)域都積累了海量的數(shù)據(jù)，促使數(shù)據(jù)處理技術(shù)得到廣泛應(yīng)用。聚類分析屬于機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域的經(jīng)典課題，是數(shù)據(jù)處理的主要工具之一。傳統(tǒng)的聚類算法是一種典型的無監(jiān)督學(xué)習(xí)，例如K-均值（K-means）算法［1］、模糊 C 均值（Fuzzy C-means，F(xiàn)CM）算法［2］和極大熵聚類（Maximum Entropy Clustering，MEC）算法［3］等。MEC算法是在FCM算法的目標(biāo)函數(shù)中加入信息熵懲罰項(xiàng)，利用最大熵原理，使得聚類結(jié)果更符合實(shí)際。針對各類背景復(fù)雜的實(shí)際應(yīng)用問題，已有多種MEC算法的變種［4-10］。相對于無監(jiān)督學(xué)習(xí)，有監(jiān)督學(xué)習(xí)也是數(shù)據(jù)處理常用方法之一，兩種方法的本質(zhì)區(qū)別是后者已有訓(xùn)練集，對訓(xùn)練集進(jìn)行建模的方法有很多，例如支持向量機(jī)、線性判別分析、K-近鄰、神經(jīng)網(wǎng)絡(luò)和決策樹等［11］。

一般地，實(shí)際數(shù)據(jù)既含有大量未標(biāo)記的樣本，也含有少量已標(biāo)記樣本或少量樣本的類關(guān)系信息。無監(jiān)督學(xué)習(xí)和有監(jiān)督學(xué)習(xí)分別利用未標(biāo)記樣本和已標(biāo)記樣本（訓(xùn)練集）進(jìn)行建模，但兩者都不能有效分析包含類關(guān)系信息的聚類分析問題。針對這一缺陷，半監(jiān)督學(xué)習(xí)方法應(yīng)運(yùn)而生，并得到快速發(fā)展。半監(jiān)督學(xué)習(xí)能有效利用少量已知樣本的類關(guān)系監(jiān)督信息，提高聚類算法的性能。根據(jù)監(jiān)督信息形式，半監(jiān)督聚類方法可分為以下兩類。

（1）監(jiān)督信息為少量已標(biāo)記類別樣本。聚類算法利用這部分標(biāo)簽信息來引導(dǎo)聚類過程，以期得到更好的聚類結(jié)果［12-15］。近年來，此類半監(jiān)督聚類有向高維數(shù)據(jù)發(fā)展的趨勢［16］。另，此類基于少量已標(biāo)記類別樣本半監(jiān)督聚類方法與本文的研究內(nèi)容聯(lián)系甚少。

（2）監(jiān)督信息為成對約束，即樣本對之間的類關(guān)系信息。成對約束是一種普遍存在且應(yīng)用廣泛的數(shù)據(jù)信息，因此基于成對約束的半監(jiān)督聚類研究具有十分重要的實(shí)際意義［17-29］。該類研究的基本框架是以MEC算法為基礎(chǔ)，加入成對約束對應(yīng)隸屬度的懲罰項(xiàng)，用它表示成對約束的信息?，F(xiàn)有文獻(xiàn)中，已有多種基于成對約束的半監(jiān)督聚類方法，例如競爭凝聚態(tài)算法［17］、基于貝葉斯先驗(yàn)理論的概率方法［18-19］、基于譜分解的聚類方法［26-29］等。

在聚類分析領(lǐng)域，可以利用交叉熵刻畫樣本對之間的成對約束信息，并且以此來構(gòu)造聚類分析方法［30-34］。李晁銘等［34］用樣本交叉熵描述樣本自信息與成對約束信息，提出了基于成對約束的交叉熵半監(jiān)督聚類算法（Cross-Entropy Semi-supervised Clustering Based on Pairwise Constraints，CE-sSC）。CE-sSC算法是MEC算法在半監(jiān)督學(xué)習(xí)領(lǐng)域中的一種推廣形式。

本文在文獻(xiàn)［34］研究結(jié)果的基礎(chǔ)上，提出了一類半監(jiān)督聚類算法。該算法剔除了CE-sSC算法中交叉熵之間的重復(fù)部分，避免了各熵項(xiàng)之間的相互干擾，使得懲罰項(xiàng)系數(shù)的選擇簡單明了。新算法推廣了懲罰項(xiàng)的形式，提供了一族選擇，包含相對熵特例。實(shí)證分析表明，在成對約束較少時(shí)，新算法具備良好的聚類性能；與CE-sSC算法相比，懲罰系數(shù)的選擇更簡潔高效。

1 算法

1.1 原理

MEC算法有收斂速度快、數(shù)值穩(wěn)定性好、容易實(shí)現(xiàn)等優(yōu)點(diǎn)，缺點(diǎn)是其中的懲罰項(xiàng)（信息熵）僅能表達(dá)樣本點(diǎn)屬于同類的自身性的自信息（Self-information），即各樣本自身的內(nèi)部信息。信息熵定義如下。

定義1設(shè)樣本點(diǎn)xj的隸屬度向量為μjT（μ1j，…，μcj），其中T為轉(zhuǎn)置符號(hào)，c為聚類數(shù)。稱

為樣本點(diǎn)xj的信息熵。

信息熵僅含有各樣本自身的內(nèi)部信息［34］。當(dāng)數(shù)據(jù)帶成對約束時(shí)，就需要構(gòu)造新的懲罰項(xiàng)。成對約束是不同樣本之間的類關(guān)系信息，要求新的懲罰項(xiàng)能夠充分利用此類信息。一般采用的成對約束為must-link約束類和cannot-link約束類，具體定義如下。

定義 2 must-link 集合 ML=｛（xj，xk）│j＜k｝，若（xj，xk）∈ML，則表明xj和xk必須屬于同類，也稱xj和xk存在正關(guān)聯(lián)約束關(guān)系。

存在正關(guān)聯(lián)約束關(guān)系的樣本對xj和xk包含信息如圖1所示，其中實(shí)線圈代表類簇，小三角形代表樣本點(diǎn)，同一實(shí)線圈中的樣本點(diǎn)屬于同一類簇，灰色小三角形代表樣本點(diǎn)xj，黑色小三角形代表樣本點(diǎn)xk·xj和xk屬于同一類簇cluster1，即存在正關(guān)聯(lián)約束關(guān)系。

定義 3 cannot-link 集合 CL=｛（xj，xk）│j＜k｝，若（xj，xk）∈CL，則表明xj和xk必須屬于不同類簇，也稱xj和xk存在負(fù)關(guān)聯(lián)約束關(guān)系。

存在負(fù)關(guān)聯(lián)約束關(guān)系樣本對xj和xk包含信息如圖2所示，其中實(shí)線圈和小三角形的含義同圖1，不同實(shí)線圈中樣本點(diǎn)屬于不同類簇，灰色小三角形代表樣本點(diǎn)xj，黑色小三角形代表樣本點(diǎn)xk·xj和xk分別屬于類簇cluster1和類簇cluster2，即存在負(fù)關(guān)聯(lián)約束關(guān)系。

在正關(guān)聯(lián)約束和負(fù)關(guān)聯(lián)約束的直觀意義下，李晁銘等［34］借用交叉熵，構(gòu)造了CE-sSC半監(jiān)督聚類算法。該算法推廣了傳統(tǒng)MEC算法中的懲罰項(xiàng)（信息熵），使其能充分利用成對約束信息。

圖1 正關(guān)聯(lián)約束關(guān)系樣本點(diǎn)示意圖

圖2 負(fù)關(guān)聯(lián)約束關(guān)系樣本點(diǎn)示意圖

定義4 定義樣本點(diǎn)對（xj，xk）的交叉熵為

式（2）給出了交叉熵的具體數(shù)學(xué)表達(dá)式，該表達(dá)式與信息熵（1）的數(shù)學(xué)表達(dá)式相似。從結(jié)構(gòu)上看，可把信息熵H（xj）看成是樣本點(diǎn)xj對其自身的樣本交叉熵H（xj，xj），是交叉熵的一種特殊情形。式（2）交叉熵有如下分解

在式（3）中，H（xj，xj）即為信息熵H（xj），表示樣本xj的自信息（Self-information），D（xj‖xk）為樣本點(diǎn)對（xj，xk）的相對熵（外部信息）。下文中的信息熵，皆用符號(hào)H（xj，xj）表示。在CE-sSC算法中，每對成對約束的交叉熵皆可分解成信息熵和相對熵，經(jīng)分析發(fā)現(xiàn)某些熵項(xiàng)之間存在互相干擾，這會(huì)使得懲罰項(xiàng)系數(shù)的調(diào)整復(fù)雜化。假設(shè)有兩對正/負(fù)關(guān)聯(lián)約束（xj，xk）和（xj，xk'），其中k≠k'；分解對應(yīng)的交叉熵得到

從式（4）可得，兩對關(guān)聯(lián)約束（xj，xk）和（xj，xk'）對應(yīng)的交叉熵H（xj，xk）和H（xj，xk'）中皆包含樣本xj的信息熵H（xj，xj）。此時(shí)，在CE-sSC算法的懲罰項(xiàng)中，H（xj，xk），H（xj，xk'）和H（xj，xj）三項(xiàng)之間存在相互干擾。正關(guān)聯(lián)約束和負(fù)關(guān)聯(lián)約束的懲罰項(xiàng)系數(shù)的符號(hào)相反，兩者之間一旦存在干擾，會(huì)使干擾交叉化和復(fù)雜化。一般地，成對約束越多，干擾越復(fù)雜。

定義2和定義3強(qiáng)調(diào)了成對約束樣本對的順序；而在文獻(xiàn)［34］中給出的must-link約束類和cannot-link約束類并沒有強(qiáng)調(diào)順序；這進(jìn)一步強(qiáng)化了CE-sSC算法中各熵項(xiàng)之間的互相干擾。鑒于熵項(xiàng)之間的相互干擾，本文將對CE-sSC算法做相應(yīng)的改進(jìn)。

賀楊成等［35］研究了成對約束屬性對半監(jiān)督聚類效果所產(chǎn)生的影響；尹學(xué)松等［36］通過對正關(guān)聯(lián)約束進(jìn)行打包，提出基于成對約束的K均值算法（PCBKM），并結(jié)合線性判別分析處理高維數(shù)據(jù)的半監(jiān)督聚類問題；蔣偉進(jìn)等［37］提出了一種主動(dòng)學(xué)習(xí)更新成對約束的半監(jiān)督譜聚類算法（SSC）；肖宇等［38］研究了基于近鄰傳播的半監(jiān)督聚類算法（SAP）。

相對熵D（xj‖xk）又被稱為Kullback-Leibler（KL）散度［39］，可度量兩個(gè)概率向量之間的距離。概率向量之間相似度越高，對應(yīng)的KL散度越小。Cressie等［39］將KL散度推廣到功效散度（power-divergence，PD），用于研究多項(xiàng)概率模型的擬合優(yōu)度檢驗(yàn)。在數(shù)據(jù)樣本量很大時(shí)，基于PD散度的擬合優(yōu)度檢驗(yàn)與基于KL散度的擬合優(yōu)度檢驗(yàn)結(jié)果差別不大；但當(dāng)樣本量不大時(shí)，差別很明顯，模擬實(shí)驗(yàn)表明，基于PD散度的擬合優(yōu)度檢驗(yàn)比基于KL散度的擬合優(yōu)度檢驗(yàn)結(jié)果更好。

由定義5可知，PD散度是一族，當(dāng)指標(biāo)p=0時(shí)PD散度也為KL散度，即樣本對之間的相對熵。PD散度隨著指標(biāo)p的改變而改變。還可將PD散度推廣到更一般的形式，例如?散度［40］。類似于KL散度，概率向量之間相似度越高，則對應(yīng)的PD散度越小。基于PD散度和相對熵之間的關(guān)系，本文將在下一小節(jié)提出一種基于PD散度的半監(jiān)督聚類算法（Power-divergence Semi-supervised Clustering Based on Pairwise Constraints，PD-sSC）。

1.2 目標(biāo)函數(shù)

由定義1和定義2可知，同一個(gè)數(shù)據(jù)的must-link約束類和cannot-link約束類沒有交集，即ML∩CL=?。基于集合ML、CL，下面定義懲罰系數(shù)矩陣。

定義 6 懲罰系數(shù)矩陣 Γ＝（Γjk）n×n，其中

顯然，Γ為上三角形矩陣，其中所有γjk元素皆為正數(shù)。

CE-sSC算法的懲罰項(xiàng)為

由對式（4）的分析可得，CE-sSC算法的懲罰項(xiàng)Θ0內(nèi)部之間存在相互干擾，且成對約束越多干擾越復(fù)雜。為克服此缺點(diǎn)，我們用PD散度構(gòu)造如下新的懲罰項(xiàng)

構(gòu)造如下PD-sSC算法的目標(biāo)函數(shù)

式（7）中的符號(hào)含義如表1所示。

表1 PD-sSC算法目標(biāo)函數(shù)符號(hào)含義表

1.3 算法步驟

聚類的過程就是最小化目標(biāo)函數(shù)，得出合適的隸屬度矩陣和中心矩陣，本文采用極小值。設(shè)拉格朗日函數(shù)為 L（U，V，Λ），其中 Λ=（λ1，…，λn）T為拉格朗日乘子，則有

當(dāng) L（U，V，Λ）取極小值時(shí)，應(yīng)滿足

可得

由迭代式（8）和（10），可得PD-sSC算法的流程如下：

輸入 數(shù)據(jù)樣本集 X=｛xj│xj∈Rd，j=1，…，n｝，懲罰系數(shù)矩陣 Γ＝（Γjk）n×n，初始隸屬度矩陣 U(0)，聚類數(shù)c（2≤c≤n），PD散度指標(biāo)p，算法迭代終止條件ε，最大迭代次數(shù)T。

輸出 隸屬度矩陣U和中心矩陣V。

迭代過程：

S1設(shè)置迭代計(jì)數(shù)器t=0。

S2 利用式（8）和 U(t)計(jì)算出 V(t)。

S3 利用式（10）和 V(t)更新 U(t)為 U(t+1)。

S4若滿足‖U(t)-U(t+1)‖F(xiàn)≤ε或t=T，則終止；否則令t=t+1，并返回S2。此處，‖·‖F(xiàn)表示Frobenius范數(shù)。

S5當(dāng)算法收斂后，輸出隸屬度矩陣U和中心矩陣V。

聚類中心矩陣與隸屬度矩陣的交替迭代更新是PD-sSC算法流程的主要思想。聚類中心矩陣和隸屬度矩陣更新迭代計(jì)算的時(shí)間復(fù)雜度分別為

其中，c，n的含義見表1，d為數(shù)據(jù)樣本集X的維數(shù)，r表示X中有成對約束關(guān)系的數(shù)據(jù)樣本個(gè)數(shù)。若算法迭代t次，算法的時(shí)間復(fù)雜度為O（tcdn+tcn（d+r+1））。若僅考慮樣本量n，PD-sSC算法的時(shí)間復(fù)雜度是樣本量n線性函數(shù)。

2 實(shí)驗(yàn)分析

2.1 實(shí)驗(yàn)數(shù)據(jù)與評價(jià)準(zhǔn)則

選用UCI數(shù)據(jù)庫中常用的iris、wine、seeds、breast數(shù)據(jù)以及用于池塘水質(zhì)評價(jià)水色圖像特征數(shù)據(jù)集X1和用于區(qū)域環(huán)境質(zhì)量狀況評價(jià)的空氣質(zhì)量數(shù)據(jù)集X2作為實(shí)驗(yàn)數(shù)據(jù)，特征見表2。表2中breast數(shù)據(jù)有16個(gè)缺失值，在實(shí)驗(yàn)過程中將包含缺失值的行做刪除處理。實(shí)驗(yàn)前，對數(shù)據(jù)進(jìn)行中心化與標(biāo)準(zhǔn)化處理，以消除指標(biāo)的量綱差異。

對比算法選擇了 CE-sSC［34］算法、PCBKM［36］算法和 SSC 算法［37］。本文沒有考慮文獻(xiàn)[34]選中的 SAP算法［38］，是因?yàn)镾AP算法沒有事先固定聚類數(shù)c，而是通過偏向系數(shù)來自動(dòng)控制聚類數(shù)。實(shí)際的數(shù)據(jù)分析表明，通過調(diào)節(jié)偏向系數(shù)而把最終聚類數(shù)恰好控制為c，此過程并不容易實(shí)現(xiàn)。

表2 數(shù)據(jù)集的特征

為了準(zhǔn)確評價(jià)聚類算法的性能，本文選擇了三類常見的聚類評價(jià)指標(biāo)：1）準(zhǔn)確率（Accuracy Cluster，AC）指標(biāo)：描述聚類正確的百分比；2）標(biāo)準(zhǔn)互信息（Normalized Mutual Information，NMI）指標(biāo)：衡量兩個(gè)數(shù)據(jù)分布的吻合程度；3）蘭德指數(shù)（Rand Index，RI）指標(biāo)：用來表現(xiàn)聚類結(jié)果與真實(shí)情況的吻合程度。三類指標(biāo)取值都在0到1之間，越大說明聚類效果越好。

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

實(shí)驗(yàn)過程中對每個(gè)數(shù)據(jù)集分別固定成對約束數(shù)目，其中iris選擇的固定成對約束數(shù)目依次為10，15，20，25，30，35，40，45，50，55 對；wine 選擇的固定成對約束數(shù)目依次為 8，16，24，32，40，48，56，64，72，80 對；seeds、X1、X2選擇的固定成對約束數(shù)目依次為 10，20，30，40，50，60，70，80，90，100 對；breast選擇的固定成對約束數(shù)目依次為 20，40，60，80，100，120，140，160，180，200 對。對各個(gè)數(shù)據(jù)集中每個(gè)固定數(shù)目成對約束都進(jìn)行1 000次的重復(fù)實(shí)驗(yàn)，每次實(shí)驗(yàn)都從數(shù)據(jù)集中隨機(jī)抽取相應(yīng)數(shù)目的成對約束，用于指導(dǎo)各算法對數(shù)據(jù)集的聚類學(xué)習(xí)。把1 000次重復(fù)實(shí)驗(yàn)結(jié)果的平均值作為該固定數(shù)目成對約束的最終實(shí)驗(yàn)結(jié)果。本文PD-sSC算法的PD指標(biāo)p選擇了區(qū)間［-2，2］中的等距格子點(diǎn)，間距為0.05，對應(yīng)的實(shí)驗(yàn)結(jié)果有好有壞，羅列出來的是表現(xiàn)較好的PD指標(biāo)p的實(shí)驗(yàn)結(jié)果；不同數(shù)據(jù)的PD指標(biāo)p 的結(jié)果有區(qū)別，例如 iris、wine、seeds、breast數(shù)據(jù) p=-1，X1數(shù)據(jù) p=0.25，X2數(shù)據(jù) p=-1.75；實(shí)驗(yàn)結(jié)果表明，在實(shí)際的數(shù)據(jù)分析中，通過調(diào)整PD指標(biāo)p來選擇PD-sSC算法具有一定的意義。算法迭代終止條件為ε=le-5，最大迭代次數(shù)T=100。

圖3～10分別為6個(gè)數(shù)據(jù)集的3個(gè)指標(biāo)值實(shí)驗(yàn)結(jié)果。其中，橫坐標(biāo)為成對約束數(shù)目，縱坐標(biāo)分別為AC指標(biāo)的值、NMI指標(biāo)的值、RI指標(biāo)的值。

圖3顯示當(dāng)成對約束數(shù)目不大于45時(shí)，PD-sSC算法的AC與RI指標(biāo)值高于3個(gè)對比算法，NMI指標(biāo)值比CE-sSC和PCBKM高。PD-sSC和CE-sSC算法的3個(gè)指標(biāo)值都在緩慢下降；在約束數(shù)目為50時(shí)，PD-sSC和CE-sSC的指標(biāo)值下降較為明顯。雖然SSC算法的NMI值遠(yuǎn)超PD-sSC算法和CE-sSC算法，但SSC算法中含有兩個(gè)對算法效果影響很大的超參數(shù)，計(jì)算速度相較其他三種算法十分緩慢，SSC算法復(fù)雜度高。

圖3 iris數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

圖4 wine數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

圖5 seeds 數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

圖4中wine數(shù)據(jù)集實(shí)驗(yàn)結(jié)果表明，PD-sSC算法的AC、NMI和RI指標(biāo)值都明顯高于其他3個(gè)算法，PD-sSC算法和CE-sSC算法曲線都呈下降趨勢，且AC和RI指標(biāo)值都高于0.85。PD-sSC算法的聚類效果最好。

在圖5中，PD-sSC算法成對約束數(shù)目小于20時(shí)，3個(gè)指標(biāo)值比對比算法高。PD-sSC算法聚類效果優(yōu)于CE-sSC算法，且AC和RI指標(biāo)值都高于0.80。隨著成對約束數(shù)目的增加，PD-sSC算法和CE-sSC算法聚類效果隨之下降，但PD-sSC算法的下降速度稍緩于CE-sSC算法的下降速度。

圖6 breast數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

圖7 X1數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

圖8 X2數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

圖6表明PD-sSC算法對breast數(shù)據(jù)集聚類效果最好。由于breast數(shù)據(jù)集樣本量相對較大，SSC算法速度極慢，因此在計(jì)算時(shí)沒有考慮SSC算法中主動(dòng)學(xué)習(xí)部分，只考慮了半監(jiān)督譜聚類算法。隨著成對約束數(shù)目的增加，除SSC算法的指標(biāo)值基本固定不變外，其他3個(gè)算法的指標(biāo)都有下降趨勢，其中PCBKM算法降幅最大，PD-sSC算法降幅最小，且AC和RI值都大于0.85。

由圖7可知，當(dāng)成對約束數(shù)目小于30時(shí)，PD-sSC算法與CE-sSC算法的AC、NMI和RI指標(biāo)值相差不大，但明顯優(yōu)于其他兩個(gè)算法。隨著成對約束數(shù)目的增多，PD-sSC算法的AC和NMI指標(biāo)值高于CE-sSC算法，當(dāng)成對約束數(shù)目大于80時(shí)，PD-sSC算法的RI指標(biāo)值略高于CE-sSC算法。從整體看，PD-sSC算法的AC、NMI指標(biāo)值是波動(dòng)上升的，且聚類效果優(yōu)于其他三個(gè)算法。圖8給出的X2數(shù)據(jù)集實(shí)驗(yàn)結(jié)果表明，PCBKM算法的聚類效果最好，PD-sSC算法的AC指標(biāo)值與RI指標(biāo)值一直高于CE-sSC算法。

一般而言，成對約束數(shù)量越多，聚類效果應(yīng)該會(huì)越好，但根據(jù)上述分析，PD-sSC算法和CE-sSC算法的聚類效果都隨著成對約束數(shù)目的增多呈下降趨勢。此現(xiàn)象的可能原因是，為簡化實(shí)驗(yàn)過程，選擇了固定的懲罰系數(shù)，當(dāng)成對約束數(shù)目增加時(shí)，目標(biāo)函數(shù)JPD-sSC（U，V）中的懲罰項(xiàng)比重會(huì)增加，從而影響了聚類效果。此時(shí)，可選擇隨成對約束數(shù)目增加而減小的懲罰項(xiàng)系數(shù)，降低懲罰項(xiàng)的比重，以期獲得更好的聚類效果。以iris、wine數(shù)據(jù)集為例，隨著成對約束數(shù)目的增加，適當(dāng)減小懲罰系數(shù)的值，對CE-sSC算法懲罰系數(shù)分別取為（10/N）3，（10/N）4.5，對 PD-sSC 算法懲罰項(xiàng)系數(shù)分別取為（10/N）4，（10/N）5.5，其中 N為成對約束數(shù)目。

圖9 iris數(shù)據(jù)集調(diào)整懲罰項(xiàng)系數(shù)后實(shí)驗(yàn)結(jié)果

圖10 wine數(shù)據(jù)集調(diào)整懲罰項(xiàng)系數(shù)后實(shí)驗(yàn)結(jié)果

由圖9～10可知，懲罰系數(shù)被調(diào)整以后，PD-sSC算法的3個(gè)指標(biāo)值都有波動(dòng)上升趨勢，聚類效果有明顯提升。在圖9中，當(dāng)成對約束數(shù)目為大于35時(shí)，CE-sSC算法指標(biāo)值持續(xù)上升；PD-sSC算法的指標(biāo)值在成對約束數(shù)目大于15時(shí)小幅波動(dòng)上升。在圖10中，CE-sSC算法在成對約束數(shù)目為20～80時(shí)指標(biāo)值都持續(xù)下降，而后小幅上升，成對約束數(shù)目取100時(shí)，3個(gè)指標(biāo)值都比成對約束數(shù)目取10時(shí)低；PD-sSC算法的指標(biāo)值在成對約束數(shù)目為20時(shí)達(dá)到最高，但總體呈小幅上升之勢。試驗(yàn)中對CE-sSC算法的懲罰系數(shù)進(jìn)行調(diào)整比PD-sSC算法難，因?yàn)镃E-sSC算法的懲罰項(xiàng)內(nèi)部之間互相干擾，影響了懲罰系數(shù)的調(diào)整效果，這也是本文引進(jìn)PD-sSC算法的原因之一。

綜合圖3～10的實(shí)驗(yàn)結(jié)果得出，對成對約束數(shù)目較少的數(shù)據(jù)集，PD-sSC算法的聚類效果優(yōu)于其他對比聚類算法。生活中獲取帶成對約束的數(shù)據(jù)比較困難，因此本文所提出的算法是有意義的。PCBKM算法是利用Must-link約束對數(shù)據(jù)進(jìn)行打包，然后再進(jìn)行聚類分析，因此可預(yù)計(jì)，在成對約束數(shù)目較大時(shí)，該算法的聚類效果可能會(huì)很理想，圖3～5以及圖8證實(shí)了這種猜想。

表3列出了各算法計(jì)算時(shí)間的復(fù)雜度?？煽闯觯琒SC算法的時(shí)間復(fù)雜度為立方階，相較其他3個(gè)算法，在實(shí)際運(yùn)用時(shí)耗費(fèi)的時(shí)間成本更高。雖然在PD-sSC算法中式（11）形式上較復(fù)雜，但程序?qū)崿F(xiàn)并不復(fù)雜；PD-sSC算法和CE-sSC算法具有相同的時(shí)間復(fù)雜度，這在實(shí)驗(yàn)過程中就有體現(xiàn)。

表3 各聚類算法的時(shí)間復(fù)雜度

3 結(jié)語

為克服CE-sSC算法的懲罰項(xiàng)中各熵項(xiàng)之間的相互干擾，本文基于相對熵提出了PD-sSC算法，并把表示成對約束樣本信息（外部信息）的KL散度（即相對熵）項(xiàng)推廣到了PD散度。PD指標(biāo)p可取任意的實(shí)數(shù)，當(dāng)成對約束數(shù)較少時(shí)，可通過調(diào)整PD指標(biāo)來選擇比CE-sSC算法表現(xiàn)更好的PD-sSC算法。選擇了CE-sSC算法、PCBKM算法和SSC算法作為對比算法，PD指標(biāo)選擇了區(qū)間［-2，2］中的等距格子點(diǎn)進(jìn)行比較，挑選了表現(xiàn)較好的PD指標(biāo)進(jìn)行展示，不同數(shù)據(jù)的PD指標(biāo)有可能不同。實(shí)驗(yàn)結(jié)果表明，在成對約束數(shù)目較少時(shí)，PD-sSC算法聚類效果比對比算法更好，在處理樣本量較大的數(shù)據(jù)集（例如breast）時(shí)，PD-sSC算法明顯優(yōu)于其他對比算法。如果設(shè)定懲罰系數(shù)隨成對約束數(shù)目的增多而減小，此時(shí)PD-sSC算法聚類效果會(huì)得到進(jìn)一步提升。PD-sSC算法的懲罰系數(shù)調(diào)整比CE-sSC算法簡單且高效。在分析iris、wine和seeds數(shù)據(jù)時(shí)，當(dāng)成對約束數(shù)目相對較大時(shí)，PCBKM算法表現(xiàn)較好，這與該算法直接對must-link成對約束樣本進(jìn)行打包處理有關(guān)。未來的研究，將參照PCBKM算法的這個(gè)特點(diǎn)，對PD-sSC算法做進(jìn)一步的優(yōu)化處理。