基于成對約束的半監督凝聚層次聚類算法

盛俊杰，謝麗聰

(福州大學 數學與計算機學院，福建 福州350108)

聚類即根據數據集中數據的不同特征將其劃分為不同簇的過程，使得同一個簇中的樣本之間具有較高的相似度，而不同簇中的樣本之間具有高度相異度。聚類過程中通常沒有類別標簽等監督信息，因而是一種無監督的學習。傳統的無監督學習通常只利用無標簽樣本進行學習，而監督學習只利用有標簽樣本進行學習，半監督學習的優越性體現在其同時利用無標簽樣本和有標簽樣本進行學習。半監督聚類算法研究如何利用少量的監督信息來提升聚類性能[1]，使用的監督信息既可以是類標簽，也可以是一對樣本是否屬于同一類的約束信息。半監督聚類算法對聚類性能的提高主要依賴于監督信息，監督信息的選取非常關鍵。

對于現實世界的無監督學習算法，例如人的語音識別、GPS道路檢測等，以成對約束形式出現的監督信息更實際。對用戶而言，要確定樣本類標簽比較困難，但是獲得關于兩個樣本是否屬于同一類的約束信息則較為容易[2]。其中涉及兩類成對點約束，分別是must-link和cannot-link。

與監督學習相比，無監督聚類過程缺少用戶或分類器(如類標簽信息)的指導，因此不能產生理想的聚類結果。使用某種監督形式，例如成對約束，可以顯著提高無監督聚類的質量。本文將監督信息的信息含量應用到聚類中，提出一種基于成對約束的半監督凝聚層次聚類算法。

1 成對約束概念

半監督聚類使用的成對約束表示兩個樣本一定被分到同一個簇或者一定被分到不同的簇。兩個廣泛使用的成對約束方法是must-link約束和cannot-link約束，其中，must-link約束表示兩個樣本一定被分配到同一個簇，cannot-link約束代表兩個樣本一定被分到不同的簇[3]。令 Con(i，j)表示樣本 xi和樣本 xj之間的成對約束，如下表示：

很明顯地可以看出，如果 Con(i，j)＝1，則 Con(j，i)＝1；如果 Con(i，j)＝-1，則 Con(j，i)＝-1。

2 凝聚層次聚類算法(AHC)

層次聚類方法是根據給定的簇間距離度量準則，構造和維護一棵由簇和子簇形成的聚類樹，直至滿足某個終結條件為止。根據層次分解是自底向上還是自頂向下形成，層次聚類方法可以分為凝聚的(Agglomerative)和分裂的(Divisive)兩種[4]。一個純粹的層次聚類方法的聚類質量受限于如下的特點：一旦一個合并或分裂被執行，就不能修正。

凝聚層次聚類AHC(Agglomerative Hierarchical Clustering)采用自底向上的策略，首先將每個樣本作為一個簇，然后合并這些原子簇為越來越大的簇，直至所有的樣本都在一個簇中，或者滿足某個終結條件。絕大多數層次聚類方法都屬于這一類，它們只是在簇間距離的定義上有所不同。圖1是凝聚層次聚類的一個簡單例子。

聚類簇C1和聚類簇C2的距離為：

AHC算法的步驟如下：

輸入：未知分布的樣本集 S＝{x1，x2，…，xN}

輸出：最優的聚類分組{C1，C2，…，CK}

(1)假設初始聚類分組為：g＝{C1，C2，…，CN}，初始的聚類簇個數為 Y＝N，計算所有的距離 d(C，C′)，其中 C、C′∈g。

本文凝聚層次聚類的簇間距離的度量采用了中心點的方法。設C是一個聚類簇，xk是C中的樣本，則C的中心點為：止，輸出結果；如果 Y＞K，算法跳轉到步驟(3)。

(3)計算所有的距離 d(Cr，C″)，其中 C″∈g。 跳轉到步驟(2)。

3 基于成對約束的半監督凝聚層次聚類算法

在PS-AHC中，P代表成對約束 Pairwise Constraints，S代表半監督Semi-supervised。

3.1 近鄰度的定義

本文提出了近鄰度這個新的概念，其思想是基于k近鄰分類算法的。k近鄰分類算法的思想是：找出距離待分類樣本最近的k個有標記樣本，在這k個有標記樣本中，哪個類別的樣本占的數目最多，待分類樣本就屬于哪個類別。在KNN算法中，待分類樣本的類別由它附近最近的k個樣本決定。

對于每一個樣本 xi，都有一個近鄰度 αi，αi≥0，αi的定義如下：

其中，k是給定的參數，xm是距離樣本xi最近的k個樣本。

如圖2所示，有 x1、x2和 x3三個樣本，圓的半徑代表相應樣本的近鄰度。近鄰度大，說明該樣本附近的樣本分布比較稀疏，樣本之間的距離比較遠；反之，近鄰度小，說明該樣本附近的樣本分布比較密集，樣本之間的距離比較近。

3.2 利用成對約束改變聚類簇之間的距離

首先，定義兩個集合 ML(C；x)和 CL(C；x)。 ML(C；x)指在聚類簇C中與樣本x具有must-link約束關系的樣本的集合，CL(C；x)指在聚類簇C中與樣本x具有cannotlink約束關系的樣本的集合，表示如下：

其次，在 ML(C；x)和 CL(C；x)的基礎上定義集合的并 ML(C；C′)和 CL(C；C′)：

最后，用 K(C；C′)表示所有 ML(C；C′)和 CL(C；C′)的近鄰度之差：

例 如，C＝{x1，x2，x3}和 C′＝{x4，x5，x6}是 兩 個 聚 類 簇，(x1，x4)和 (x3，x5)是 must-link 約 束， (x2，x6)是 cannot-link約束。 那么，ML(C；C′)、CL(C；C′)和 K(C；C′)的計算結果如下：

同樣，ML(C′；C)、CL(C′；C)和 K(C′；C)的計算結果如下：

有了 K(C；C′)的定義，聚類簇 C1和聚類簇 C2的距離被調整為：

其中，｜C1｜和｜C2｜分別表示 C1的樣本數和 C2的樣本數。

PS-AHC算法的步驟如下：

輸入：未知分布的樣本集 S＝{x1，x2，…，xN}和樣本的成對約束信息 Con(i，j)

輸出：最優的聚類分組 C＝{C1，C2，…，CK}

(1)假設初始聚類分組為：g＝{C1，C2，…，CN}，初始的聚類簇個數為 Y＝N，利用式(5)計算所有的 K(C；C′)，C、C′∈g，再利用式(6)計算所有的距離 d(C，C′)，C、C′∈g。

(3)利用式(5)計算所有的 K(C；C′)，C、C′∈g，再利用式(6)計算所有的距離 d(C，C′)，C、C′∈g。 跳轉到步驟(2)。

4 實驗結果與分析

為了驗證本文提出的PS-AHC算法的有效性，對AHC和PS-AHC這兩個算法進行了對比實驗。從UCI數據集[5]上選擇了 5個完整的數據集，分別是 haberman、balance-scale、iris、tae（teaching assistant evaluation）和 pid（pima indians diabetes）。在每個數據集S中，隨機地選擇一些樣本對，對這些樣本對生成must-link約束和cannotlink約束。成對約束的數量設置為總樣本集數量的3倍，即為3×｜S｜。所有算法各運行 30次，取平均的聚類準確率，實驗結果對比如表1所示。

表1 AHC和PS-AHC的聚類準確率比較

從實驗結果可以看出，PS-AHC表現出了比AHC更優越的性能。這是因為PS-AHC引進了樣本的成對約束信息。PS-AHC利用成對約束信息改變聚類簇之間的距離，使有must-link約束的兩個聚類簇的距離變得更近，而有cannot-link約束的兩個聚類簇的距離變得更遠，從而改變層次聚類的樹結構。實驗結果同時表明，本文所提出的近鄰度概念是有效的。

成對約束是樣本的一種監督信息。本文利用成對約束來指導聚類過程，提出了一種基于成對約束的半監督凝聚層次聚類算法（PS-AHC）。PS-AHC利用成對約束來改變聚類簇之間的距離，使聚類簇之間的距離更真實。在UCI數據集上的實驗表明，PS-AHC能有效地提高聚類的準確率，是一種有前景的半監督聚類算法。

[1]BILENKO M，BASU S，MOONEY R J.Integrating constraints and metric learning in semi-supervised clustering[C].Brodley CE，ed.Proc.of the 21st Int’l Conf.on Machine Learning.New York：ACM Press，2004：81-88.

[2]李昆侖，曹崢，曹麗蘋，等.半監督聚類的若干新進展[J].模式識別與人工智能，2009，22(5)：735-742.

[3]BASU S，BANERJEE A，MOONEY R J.Active semi-supervision for pairwise constrained clustering[C].Proc.of the SIAM Int’l Conf.on Data Mining.Cambridge：MIT Press，2004：333-344.

[4]Han Jiawei，KAMBER M.數據挖掘概念與技術[M].范明，孟小峰，譯.北京：機械工業出版社，2004：1-262.

[5]NEWMAN D J，HETTICH S，BLAKE C L，et al.UCI repository of machine learning databases[EB/OL].http：//www.ics.uci.edu/～mlearn/MLRepository.htm l,1998.