基于交叉熵測度的成對約束模糊核聚類算法

徐圣兵，林上鈞，鐘國祥

1. 廣東工業大學 計算機學院，廣東 廣州 510006

2. 廣東工業大學 應用數學學院，廣東 廣州 510520

在大數據時代，對數據進行人工標注往往需要耗費大量的人工成本，從而使得研究如何有效利用少量帶標注對象開展知識學習成為機器學習中的一個重要課題。因此，如何在只有少量指導信息的情況下去學習知識是目前一個很重要的研究議題。常見的半監督信息[1-4]有2類：一類是少部分對象帶類標簽信息；另一類是少量對象間的成對約束信息。其中，成對約束信息因其標注成本低且有效，而被眾多半監督核聚類[5-8]所采用。但是，成對約束信息的測度目前還沒有一個統一標準，進而限制了成對約束指導信息的有效利用。因此，如何有效測度和利用成對約束指導信息成為半監督學習算法研究領域的一個亟待解決的新議題。

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

為了解決上述問題，本文提出基于交叉熵測度的成對約束核函數聚類算法。交叉熵作為成對約束對象隸屬度選擇的信息度量工具，以此為基礎而提出了本文的最小-最大交叉熵隸屬度學習準則。以此準則為基礎，形成基于交叉熵測度的成對約束核函數聚類算法。與其他算法的性能對比實驗表明：本算法的對象類簇劃分更加有效，同時也說明本算法能更加有效利用成對約束指導信息提升聚類性能。

1 成對約束及核聚類算法

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

圖1 成對約束示意

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

圖2 核函數映射

在FCM算法[18]基礎上，模糊核聚類算法[19]（KFCM）的目標函數如下：

在此基礎上，一種用對象間隸屬度二次項測度方法[9]來表示成對約束的核模糊算法PCKFCM被提出。PCKFCM算法的目標函數如下:

式中的第1部分繼承FKC算法處理非球形數據的方法；第2部分是成對約束違反的懲罰項；為平衡參數。PCKFCM算法用對象隸屬度交互相乘的測度來指導學習過程。

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

2.1 交叉熵

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

從對象交叉熵定義的數學表達式中可以推出如下關系式[21]：

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

定義3 最小-最大交叉熵隸屬度學習準則

圖3 最小-最大交叉熵隸屬度學習準則示意

圖4 交叉熵指導算法學習過程

2.2 CEM-FKCPC動機

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

圖5 核函數實現示意

如圖5，結合成對約束信息，利用核函數將原本非線性可分的類簇映射到另一個空間后實現線性可分。

2.3 算法設計

根據以上定義和分析，構造CEM-FKCPC算法的目標函數如下：式中目標函數的符號說明如表1。

表1 符號說明

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

同理，由以下式子：

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

2.4 算法步驟及復雜度分析

據上述CEM-FKCPC算法推導過程和迭代公式，給出CEM-FKCPC算法具體步驟如下：

CEM-FKCPC算法的時間復雜度主要由兩部分組成：1)聚類中心矩陣，由于類簇數遠遠小于對象數據個數所以其時間復雜度為；2)隸屬度矩陣，其時間復雜度為。其中為對象數據集對象個數，為對象數據集的維度，表示成對約束關系的對象個數。當算法迭代t次時，算法的時間復雜度為。在實際算法的應用過程中，由于信息獲取成本限制，監督信息難以獲取或只能獲取少部分，則有。因此，算法的時間復雜近似線性的。

3 實驗及結果分析

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

3.1 實驗設置

1) 性能指標

對于采用的各種聚類算法，實驗將采用如下性能指標評估聚類算法性能。

Rand Index[22]度量定義為

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

2) 標準數據集

實驗標準數據集分別選用UCI常用的數據集和人工合成的非球型數據集[23]（見表2）。其中，Iris數據集和Wine數據集廣泛應用于各類算法性能測試，具有較高的直觀性和可靠性。人工合成的非球型數據可以檢驗核方法對線性不可分數據的聚類性能。X型、拋物線型數據如圖6所示。

表2 標準數據集信息

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

圖6 人工合成數據集

表3 Y1數據集部分數據

表4 Y2數據集部分數據

3.2 實驗結果分析

根據實驗設置與上述的實驗方案，通過隨機抽取已知的成對約束監督信息指導算法聚類學習，實驗結果如下：

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

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

圖7 聚類結果

4 結論

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

2）相比于已有的成對約束度量，交叉熵度量方法更能表達整體的不確定性信息。通過UCI經典數據集、合成的非球形數據集和實際工業數據集的實驗表明，CEM-FKCPC算法能有效地利用少量的成對約束監督信息提高聚類性能。

3）對比CE-sSC、PCKFCM、DKFCM算法，基于成對約束的核聚類算法CEM-FKCPC對于線性不可分數據有更好的聚類效果。