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

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

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

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

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

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

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

1 算法

1.1 原理

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

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

為樣本點xj的信息熵。

信息熵僅含有各樣本自身的內(nèi)部信息［34］。當數(shù)據(jù)帶成對約束時，就需要構(gòu)造新的懲罰項。成對約束是不同樣本之間的類關(guān)系信息，要求新的懲罰項能夠充分利用此類信息。一般采用的成對約束為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所示，其中實線圈代表類簇，小三角形代表樣本點，同一實線圈中的樣本點屬于同一類簇，灰色小三角形代表樣本點xj，黑色小三角形代表樣本點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存在負關(guān)聯(lián)約束關(guān)系。

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

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

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

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

定義4 定義樣本點對（xj，xk）的交叉熵為

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

在式（3）中，H（xj，xj）即為信息熵H（xj），表示樣本xj的自信息（Self-information），D（xj‖xk）為樣本點對（xj，xk）的相對熵（外部信息）。下文中的信息熵，皆用符號H（xj，xj）表示。在CE-sSC算法中，每對成對約束的交叉熵皆可分解成信息熵和相對熵，經(jīng)分析發(fā)現(xiàn)某些熵項之間存在互相干擾，這會使得懲罰項系數(shù)的調(diào)整復雜化。假設(shè)有兩對正/負關(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）。此時，在CE-sSC算法的懲罰項中，H（xj，xk），H（xj，xk'）和H（xj，xj）三項之間存在相互干擾。正關(guān)聯(lián)約束和負關(guān)聯(lián)約束的懲罰項系數(shù)的符號相反，兩者之間一旦存在干擾，會使干擾交叉化和復雜化。一般地，成對約束越多，干擾越復雜。

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

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

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

由定義5可知，PD散度是一族，當指標p=0時PD散度也為KL散度，即樣本對之間的相對熵。PD散度隨著指標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 目標函數(shù)

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

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

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

CE-sSC算法的懲罰項為

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

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

式（7）中的符號含義如表1所示。

表1 PD-sSC算法目標函數(shù)符號含義表

1.3 算法步驟

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

當 L（U，V，Λ）取極小值時，應(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散度指標p，算法迭代終止條件ε，最大迭代次數(shù)T。

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

迭代過程：

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

S2 利用式（8）和 U(t)計算出 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當算法收斂后，輸出隸屬度矩陣U和中心矩陣V。

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

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

2 實驗分析

2.1 實驗數(shù)據(jù)與評價準則

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

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

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

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

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

實驗過程中對每個數(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 對。對各個數(shù)據(jù)集中每個固定數(shù)目成對約束都進行1 000次的重復實驗，每次實驗都從數(shù)據(jù)集中隨機抽取相應(yīng)數(shù)目的成對約束，用于指導各算法對數(shù)據(jù)集的聚類學習。把1 000次重復實驗結(jié)果的平均值作為該固定數(shù)目成對約束的最終實驗結(jié)果。本文PD-sSC算法的PD指標p選擇了區(qū)間［-2，2］中的等距格子點，間距為0.05，對應(yīng)的實驗結(jié)果有好有壞，羅列出來的是表現(xiàn)較好的PD指標p的實驗結(jié)果；不同數(shù)據(jù)的PD指標p 的結(jié)果有區(qū)別，例如 iris、wine、seeds、breast數(shù)據(jù) p=-1，X1數(shù)據(jù) p=0.25，X2數(shù)據(jù) p=-1.75；實驗結(jié)果表明，在實際的數(shù)據(jù)分析中，通過調(diào)整PD指標p來選擇PD-sSC算法具有一定的意義。算法迭代終止條件為ε=le-5，最大迭代次數(shù)T=100。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表3 各聚類算法的時間復雜度

3 結(jié)語

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