盛俊杰，謝麗聰

(福州大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，福建 福州350108)

聚類即根據(jù)數(shù)據(jù)集中數(shù)據(jù)的不同特征將其劃分為不同簇的過程，使得同一個(gè)簇中的樣本之間具有較高的相似度，而不同簇中的樣本之間具有高度相異度。聚類過程中通常沒有類別標(biāo)簽等監(jiān)督信息，因而是一種無監(jiān)督的學(xué)習(xí)。傳統(tǒng)的無監(jiān)督學(xué)習(xí)通常只利用無標(biāo)簽樣本進(jìn)行學(xué)習(xí)，而監(jiān)督學(xué)習(xí)只利用有標(biāo)簽樣本進(jìn)行學(xué)習(xí)，半監(jiān)督學(xué)習(xí)的優(yōu)越性體現(xiàn)在其同時(shí)利用無標(biāo)簽樣本和有標(biāo)簽樣本進(jìn)行學(xué)習(xí)。半監(jiān)督聚類算法研究如何利用少量的監(jiān)督信息來提升聚類性能[1]，使用的監(jiān)督信息既可以是類標(biāo)簽，也可以是一對(duì)樣本是否屬于同一類的約束信息。半監(jiān)督聚類算法對(duì)聚類性能的提高主要依賴于監(jiān)督信息，監(jiān)督信息的選取非常關(guān)鍵。

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

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

1 成對(duì)約束概念

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

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

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

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

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

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

AHC算法的步驟如下：

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

輸出：最優(yōu)的聚類分組{C1，C2，…，CK}

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

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

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

3 基于成對(duì)約束的半監(jiān)督凝聚層次聚類算法

在PS-AHC中，P代表成對(duì)約束 Pairwise Constraints，S代表半監(jiān)督Semi-supervised。

3.1 近鄰度的定義

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

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

其中，k是給定的參數(shù)，xm是距離樣本xi最近的k個(gè)樣本。

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

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

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

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

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

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

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

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

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

PS-AHC算法的步驟如下：

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

輸出：最優(yōu)的聚類分組 C＝{C1，C2，…，CK}

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

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

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

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

表1 AHC和PS-AHC的聚類準(zhǔn)確率比較

從實(shí)驗(yàn)結(jié)果可以看出，PS-AHC表現(xiàn)出了比AHC更優(yōu)越的性能。這是因?yàn)镻S-AHC引進(jìn)了樣本的成對(duì)約束信息。PS-AHC利用成對(duì)約束信息改變聚類簇之間的距離，使有must-link約束的兩個(gè)聚類簇的距離變得更近，而有cannot-link約束的兩個(gè)聚類簇的距離變得更遠(yuǎn)，從而改變層次聚類的樹結(jié)構(gòu)。實(shí)驗(yàn)結(jié)果同時(shí)表明，本文所提出的近鄰度概念是有效的。

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

[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]李昆侖，曹崢，曹麗蘋，等.半監(jiān)督聚類的若干新進(jìn)展[J].模式識(shí)別與人工智能，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.數(shù)據(jù)挖掘概念與技術(shù)[M].范明，孟小峰，譯.北京：機(jī)械工業(yè)出版社，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.