徐圣兵，林上鈞，鐘國(guó)祥

1. 廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣東 廣州 510006

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

在大數(shù)據(jù)時(shí)代，對(duì)數(shù)據(jù)進(jìn)行人工標(biāo)注往往需要耗費(fèi)大量的人工成本，從而使得研究如何有效利用少量帶標(biāo)注對(duì)象開(kāi)展知識(shí)學(xué)習(xí)成為機(jī)器學(xué)習(xí)中的一個(gè)重要課題。因此，如何在只有少量指導(dǎo)信息的情況下去學(xué)習(xí)知識(shí)是目前一個(gè)很重要的研究議題。常見(jiàn)的半監(jiān)督信息[1-4]有2類：一類是少部分對(duì)象帶類標(biāo)簽信息；另一類是少量對(duì)象間的成對(duì)約束信息。其中，成對(duì)約束信息因其標(biāo)注成本低且有效，而被眾多半監(jiān)督核聚類[5-8]所采用。但是，成對(duì)約束信息的測(cè)度目前還沒(méi)有一個(gè)統(tǒng)一標(biāo)準(zhǔn)，進(jìn)而限制了成對(duì)約束指導(dǎo)信息的有效利用。因此，如何有效測(cè)度和利用成對(duì)約束指導(dǎo)信息成為半監(jiān)督學(xué)習(xí)算法研究領(lǐng)域的一個(gè)亟待解決的新議題。

Wang[9]引入對(duì)象間隸屬度交互效應(yīng)測(cè)度，基于模糊數(shù)學(xué)理論將軟聚類思想推廣應(yīng)用到非球形數(shù)據(jù)，提出了基于成對(duì)約束的半監(jiān)督模糊核聚類算法（semi-supervised kernel-based fuzzy c-means with pairwise constraints，PCKFCM）。目前基于成對(duì)約束的核聚類算法研究主要集中在以下兩方面：1）對(duì)象方面。Wang[10]利用動(dòng)態(tài)加權(quán)給對(duì)象空間上每個(gè)對(duì)象分配一個(gè)動(dòng)態(tài)權(quán)值，以解決對(duì)象對(duì)類簇貢獻(xiàn)不均衡的問(wèn)題，形成了基于成對(duì)約束的動(dòng)態(tài)加權(quán)半監(jiān)督模糊核聚類算法(DKFCM)。王勇臻等[11]提出了利用主動(dòng)學(xué)習(xí)的方法選擇對(duì)象，以解決初始化對(duì)象不具代表性的問(wèn)題。王小玉[12]利用成對(duì)約束調(diào)整對(duì)象間的關(guān)系，以解決密度相差比較大的簇進(jìn)行有效聚類的問(wèn)題，提出了基于共享近鄰的成對(duì)約束譜聚類算法。2）核函數(shù)方面。Wang[13]提出了面向成對(duì)約束半監(jiān)督模糊核聚類的核參數(shù)優(yōu)化算法，以解決核函數(shù)參數(shù)影響聚類性能的問(wèn)題。Kusunoki[14]提出利用Boolean核函數(shù)解決類簇可解釋性的問(wèn)題。Zhang等[15]利用自適應(yīng)核方法指導(dǎo)標(biāo)注傳播，實(shí)現(xiàn)高維數(shù)據(jù)分類。但目前對(duì)于成對(duì)約束核聚類的研究中，還缺少對(duì)成對(duì)約束指導(dǎo)信息的有效測(cè)度方面的關(guān)注。

為了解決上述問(wèn)題，本文提出基于交叉熵測(cè)度的成對(duì)約束核函數(shù)聚類算法。交叉熵作為成對(duì)約束對(duì)象隸屬度選擇的信息度量工具，以此為基礎(chǔ)而提出了本文的最小-最大交叉熵隸屬度學(xué)習(xí)準(zhǔn)則。以此準(zhǔn)則為基礎(chǔ)，形成基于交叉熵測(cè)度的成對(duì)約束核函數(shù)聚類算法。與其他算法的性能對(duì)比實(shí)驗(yàn)表明：本算法的對(duì)象類簇劃分更加有效，同時(shí)也說(shuō)明本算法能更加有效利用成對(duì)約束指導(dǎo)信息提升聚類性能。

1 成對(duì)約束及核聚類算法

成對(duì)約束[16]一般可以分為正關(guān)聯(lián)約束（mustlink）和負(fù)關(guān)聯(lián)約{束（cannot-link）2種}約束。設(shè)mustlink集合則表示與屬于同一類{，記這種關(guān)系為}；設(shè)cannot-link集合，若則表示與屬于不同類，記這種關(guān)系為；成對(duì)約束關(guān)系示意如圖1所示。

圖1 成對(duì)約束示意

將成對(duì)約束指導(dǎo)信息引入到核聚類算法是一種提升聚類性能的有效途徑。核聚類算法利用Mercer核[17]將原始空間上的對(duì)象映射到高維特征空間上，從而實(shí)現(xiàn)對(duì)象線性可分。如圖2所示，在二維空間上呈環(huán)狀分布的非球形數(shù)據(jù)難以被有效劃分，但通過(guò)核方法映射到三維空間上便可實(shí)現(xiàn)線性可分。

圖2 核函數(shù)映射

在FCM算法[18]基礎(chǔ)上，模糊核聚類算法[19]（KFCM）的目標(biāo)函數(shù)如下：

在此基礎(chǔ)上，一種用對(duì)象間隸屬度二次項(xiàng)測(cè)度方法[9]來(lái)表示成對(duì)約束的核模糊算法PCKFCM被提出。PCKFCM算法的目標(biāo)函數(shù)如下:

式中的第1部分繼承FKC算法處理非球形數(shù)據(jù)的方法；第2部分是成對(duì)約束違反的懲罰項(xiàng)；為平衡參數(shù)。PCKFCM算法用對(duì)象隸屬度交互相乘的測(cè)度來(lái)指導(dǎo)學(xué)習(xí)過(guò)程。

2 基于交叉熵測(cè)度的成對(duì)約束核聚類算法(CEM-FKCPC)

2.1 交叉熵

1948年，Shannon[20]借鑒熱力學(xué)中熵的概念，將其引入到信息論中，提出了信息熵（也稱為香農(nóng)熵）。信息熵量化了對(duì)象包含的不確定性，而交叉熵作為信息熵的拓展，量化了對(duì)象間不確定性的差異程度，也是信息論研究中的重要領(lǐng)域，在機(jī)器學(xué)習(xí)、模式識(shí)別等眾多領(lǐng)域有著廣泛的應(yīng)用。尤其在深度學(xué)習(xí)領(lǐng)域中，交叉熵可以作為一種損失函數(shù)用來(lái)評(píng)判學(xué)習(xí)效果。因此在CEMFKCPC（cross-entropy-measure based fuzzy kernel clusting algorithm with pairwise constraints）算法中，我們將交叉熵引入到成對(duì)約束指導(dǎo)信息度量中。

從對(duì)象交叉熵定義的數(shù)學(xué)表達(dá)式中可以推出如下關(guān)系式[21]：

為便于討論，式(2)右邊2項(xiàng)依次記為：

定義3 最小-最大交叉熵隸屬度學(xué)習(xí)準(zhǔn)則

圖3 最小-最大交叉熵隸屬度學(xué)習(xí)準(zhǔn)則示意

圖4 交叉熵指導(dǎo)算法學(xué)習(xí)過(guò)程

2.2 CEM-FKCPC動(dòng)機(jī)

CE-sSC（cross-entropy semi-supervised clusting based on pairwise constraints）算法[21]是在極大熵聚類算法的基礎(chǔ)上，利用成對(duì)約束的一種交叉熵的信息表達(dá)方法，擴(kuò)展得到了一種基于成對(duì)約束的交叉熵半監(jiān)督聚類算法。該方法能有效利用少量的成對(duì)約束監(jiān)督信息在線性可分的類簇上提高聚類性能，但對(duì)于非線性可分的類簇難以得到較好的效果（如圖5中的左圖）。在實(shí)際生產(chǎn)環(huán)境中，大多數(shù)情況的類簇都是非線性可分的，因此，在CE-sSC基礎(chǔ)上，本文引入核函數(shù)處理非線性可分?jǐn)?shù)據(jù)。

圖5 核函數(shù)實(shí)現(xiàn)示意

如圖5，結(jié)合成對(duì)約束信息，利用核函數(shù)將原本非線性可分的類簇映射到另一個(gè)空間后實(shí)現(xiàn)線性可分。

2.3 算法設(shè)計(jì)

根據(jù)以上定義和分析，構(gòu)造CEM-FKCPC算法的目標(biāo)函數(shù)如下：式中目標(biāo)函數(shù)的符號(hào)說(shuō)明如表1。

表1 符號(hào)說(shuō)明

由此得到聚類中心更新公式：

同理，由以下式子：

可以得到隸屬度迭代公式：

2.4 算法步驟及復(fù)雜度分析

據(jù)上述CEM-FKCPC算法推導(dǎo)過(guò)程和迭代公式，給出CEM-FKCPC算法具體步驟如下：

CEM-FKCPC算法的時(shí)間復(fù)雜度主要由兩部分組成：1)聚類中心矩陣，由于類簇?cái)?shù)遠(yuǎn)遠(yuǎn)小于對(duì)象數(shù)據(jù)個(gè)數(shù)所以其時(shí)間復(fù)雜度為；2)隸屬度矩陣，其時(shí)間復(fù)雜度為。其中為對(duì)象數(shù)據(jù)集對(duì)象個(gè)數(shù)，為對(duì)象數(shù)據(jù)集的維度，表示成對(duì)約束關(guān)系的對(duì)象個(gè)數(shù)。當(dāng)算法迭代t次時(shí)，算法的時(shí)間復(fù)雜度為。在實(shí)際算法的應(yīng)用過(guò)程中，由于信息獲取成本限制，監(jiān)督信息難以獲取或只能獲取少部分，則有。因此，算法的時(shí)間復(fù)雜近似線性的。

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

為了檢驗(yàn)CEM-FKCPC算法的聚類性能，實(shí)驗(yàn)用基于交叉熵的CE-sSC算法[21]、二次項(xiàng)測(cè)度的PCKFCM算法[9]、DKFCM算法[10]和傳統(tǒng)的kmeans算法、KFCM算法[19]作為對(duì)比實(shí)驗(yàn)。在所有的實(shí)驗(yàn)中，使用高斯作為核函數(shù)，設(shè)置算法迭代終止條件閾值為，最大迭代次數(shù)。實(shí)驗(yàn)過(guò)程中，對(duì)每個(gè)數(shù)據(jù)集分別固定成對(duì)約束數(shù)目，選擇 0、10、20、30、40、50對(duì)進(jìn)行實(shí)驗(yàn)。對(duì)各數(shù)據(jù)集中每個(gè)固定數(shù)目的成對(duì)約束都進(jìn)行10次重復(fù)實(shí)驗(yàn)，每次實(shí)驗(yàn)從數(shù)據(jù)集中隨機(jī)抽取相應(yīng)數(shù)目的成對(duì)約束，用于指導(dǎo)各算法對(duì)數(shù)據(jù)集的聚類學(xué)習(xí)。由于上述部分算法可能受初值選擇的影響，為此在每次實(shí)驗(yàn)過(guò)程中算法運(yùn)行100次后取平均作為該次實(shí)驗(yàn)結(jié)果，最后對(duì)10次重復(fù)實(shí)驗(yàn)的結(jié)果取平均作為該固定數(shù)目成對(duì)約束實(shí)驗(yàn)的最終結(jié)果。

3.1 實(shí)驗(yàn)設(shè)置

1) 性能指標(biāo)

對(duì)于采用的各種聚類算法，實(shí)驗(yàn)將采用如下性能指標(biāo)評(píng)估聚類算法性能。

Rand Index[22]度量定義為

式中：TP：同一類的對(duì)象被分到同一個(gè)簇；FP：不同類的對(duì)象被分到同一個(gè)簇；TN：不同類的對(duì)象被分到不同簇；FN：同一類的對(duì)象被分到不同簇。1，算法性能越好；數(shù)值越接近0，算法性能越差。

2) 標(biāo)準(zhǔn)數(shù)據(jù)集

實(shí)驗(yàn)標(biāo)準(zhǔn)數(shù)據(jù)集分別選用UCI常用的數(shù)據(jù)集和人工合成的非球型數(shù)據(jù)集[23]（見(jiàn)表2）。其中，Iris數(shù)據(jù)集和Wine數(shù)據(jù)集廣泛應(yīng)用于各類算法性能測(cè)試，具有較高的直觀性和可靠性。人工合成的非球型數(shù)據(jù)可以檢驗(yàn)核方法對(duì)線性不可分?jǐn)?shù)據(jù)的聚類性能。X型、拋物線型數(shù)據(jù)如圖6所示。

表2 標(biāo)準(zhǔn)數(shù)據(jù)集信息

除此之外，為了更能體現(xiàn)上述聚類算法在實(shí)際應(yīng)用中的聚類性能，本文從文獻(xiàn)[24]當(dāng)中選取基于基站定位數(shù)據(jù)的商圈分析和基于多污染因素的區(qū)域空氣質(zhì)量評(píng)價(jià)等實(shí)際應(yīng)用案例。其中，基站定位數(shù)據(jù)的商圈分析案例根據(jù)手機(jī)運(yùn)營(yíng)商的用戶的歷史定位數(shù)據(jù)進(jìn)行數(shù)據(jù)分析，歸納出商圈的人流特征和規(guī)律，識(shí)別出不同的商圈，從而達(dá)到為合適區(qū)域進(jìn)行運(yùn)營(yíng)商促銷活動(dòng)的目的。而空氣質(zhì)量評(píng)價(jià)案例則是關(guān)于環(huán)境質(zhì)量評(píng)價(jià)方面的相關(guān)應(yīng)用，空氣質(zhì)量評(píng)價(jià)是環(huán)境質(zhì)量評(píng)價(jià)中的一個(gè)重要組成部分，空氣質(zhì)量一般受多個(gè)污染因素相互作用影響，從多污染因素角度出發(fā)更能客觀準(zhǔn)確地反映環(huán)境質(zhì)量狀況，考慮SO2、NO、NO2等多個(gè)相關(guān)污染因素，通過(guò)采集和預(yù)處理得到空氣質(zhì)量數(shù)據(jù)，用以對(duì)空氣質(zhì)量進(jìn)行評(píng)價(jià)。因此，本文采用商圈用戶特征數(shù)據(jù)集Y1和空氣質(zhì)量數(shù)據(jù)集Y2這兩個(gè)工業(yè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)數(shù)據(jù)均已標(biāo)準(zhǔn)化，其中以文獻(xiàn)[24]的劃分結(jié)果作為數(shù)據(jù)集Y1和Y2的標(biāo)簽，便于進(jìn)行聚類性能對(duì)比，數(shù)據(jù)如表3和表4。

圖6 人工合成數(shù)據(jù)集

表3 Y1數(shù)據(jù)集部分?jǐn)?shù)據(jù)

表4 Y2數(shù)據(jù)集部分?jǐn)?shù)據(jù)

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

根據(jù)實(shí)驗(yàn)設(shè)置與上述的實(shí)驗(yàn)方案，通過(guò)隨機(jī)抽取已知的成對(duì)約束監(jiān)督信息指導(dǎo)算法聚類學(xué)習(xí)，實(shí)驗(yàn)結(jié)果如下：

由圖7(a)、(b)可以看出，在Iris和Wine數(shù)據(jù)集上，基于交叉熵測(cè)度的CEM-FKCPC算法在不同的成對(duì)約束數(shù)量均優(yōu)于其余算法，在實(shí)驗(yàn)中，控制成對(duì)約束數(shù)量在50對(duì)以內(nèi)，證明了利用交叉熵表達(dá)成對(duì)約束的CEM-FKCPC算法只需利用少量的監(jiān)督信息就能達(dá)到較好的聚類性能。對(duì)于X型（如圖7(c)），4種半監(jiān)督算法在少量的成對(duì)約束條件下，整體聚類性能都不高，但CEM-FKCPC算法的聚類性能依然高于其余算法。對(duì)于拋物線型數(shù)據(jù)（如圖7(d)），CEM-FKCPC算法隨著成對(duì)約束數(shù)量的增加，聚類性能逐漸超越PCKFCM算法和CE-sSC算法。同時(shí)，CEM-FKCPC算法的成對(duì)約束對(duì)聚類性能的提升效果優(yōu)于CE-sSC等算法。由結(jié)果分析知道，對(duì)于非球形數(shù)據(jù)，CEM-FKCPC算法合理利用成對(duì)約束監(jiān)督信息的核聚類算法能更好地處理非球形數(shù)據(jù)，提高聚類性能。

由圖7(e)可以看出，在Y1數(shù)據(jù)集上，CEMFKCPC算法的RI值一直都優(yōu)于其他4種算法。對(duì)于Y2數(shù)據(jù)集(圖7(f))，在成對(duì)約束數(shù)量在0～15時(shí)，CE-sSC算法RI值要高于CEM-FKCPC算法，但成對(duì)約束數(shù)量在20～50時(shí)，CEM-FKCPC算法RI值上升趨勢(shì)明顯，逐步趕超其余算法。因此，根據(jù)RI值的比較可以看出，基于交叉熵測(cè)度的CEM-FKCPC算法能更有效地利用成對(duì)約束信息。此外，從圖7總體上看，與傳統(tǒng)的k-means和FKCM算法比較可以看出，CEM-FKCPC算法優(yōu)于這類傳統(tǒng)算法。

圖7 聚類結(jié)果

4 結(jié)論

1）針對(duì)基于成對(duì)約束的核聚類中，如何合理高效地利用成對(duì)約束監(jiān)督信息，同時(shí)更好地表達(dá)成對(duì)約束信息并作出明確解析等問(wèn)題，本文引入交叉熵作為成對(duì)約束信息度量，提出新的成對(duì)約束框架CEM-FKCPC。

2）相比于已有的成對(duì)約束度量，交叉熵度量方法更能表達(dá)整體的不確定性信息。通過(guò)UCI經(jīng)典數(shù)據(jù)集、合成的非球形數(shù)據(jù)集和實(shí)際工業(yè)數(shù)據(jù)集的實(shí)驗(yàn)表明，CEM-FKCPC算法能有效地利用少量的成對(duì)約束監(jiān)督信息提高聚類性能。

3）對(duì)比CE-sSC、PCKFCM、DKFCM算法，基于成對(duì)約束的核聚類算法CEM-FKCPC對(duì)于線性不可分?jǐn)?shù)據(jù)有更好的聚類效果。