基于Seeds集和成對(duì)約束的半監(jiān)督三支聚類集成

姜春茂，吳 鵬，李志聰*

（1.福建工程學(xué)院 計(jì)算機(jī)科學(xué)與數(shù)學(xué)學(xué)院，福州 350118；2.哈爾濱師范大學(xué) 計(jì)算機(jī)科學(xué)與信息工程學(xué)院，哈爾濱 150025）

0 引言

聚類分析是一種典型的無(wú)監(jiān)督機(jī)器學(xué)習(xí)方法。聚類分析因?yàn)椴恍枰o定樣本的標(biāo)簽信息，僅通過(guò)衡量數(shù)據(jù)之間的關(guān)系就能識(shí)別數(shù)據(jù)中潛在的結(jié)構(gòu)特征而受到廣泛的關(guān)注。但單一的聚類算法往往采用某種理想化的數(shù)據(jù)分布假設(shè)，如K-means 算法假設(shè)樣本均勻分布在球形的樣本空間中，當(dāng)樣本分布不均勻或存在較多的噪點(diǎn)時(shí)，聚類效果不佳。不同的聚類算法往往存在較大的差異性，即使相同的聚類算法在參數(shù)不同時(shí)，聚類結(jié)果也往往存在差異。這限制了聚類分析的適用性。

聚類集成旨在融合多個(gè)不同的基聚類成員，從而獲得一個(gè)統(tǒng)一的數(shù)據(jù)劃分。研究表明，相較于單一的聚類算法，聚類集成能夠有效提高聚類結(jié)果的穩(wěn)定性、魯棒性和準(zhǔn)確率。Strehl 等［1］將集成學(xué)習(xí)引入聚類分析中，提出了聚類集成的概念。由于缺乏先驗(yàn)的標(biāo)簽信息，聚類集成的研究要比分類集成更加困難，其中的關(guān)鍵問(wèn)題是如何生成多個(gè)具有差異性的基聚類，以及如何對(duì)多個(gè)基聚類結(jié)果進(jìn)行融合，獲得更好的聚類集成結(jié)果。Strehl 等將超圖劃分引入聚類集成，提出了三種基于超圖劃分的聚類集成算法，分別是基于類簇的相似分區(qū)算法（Cluster-based Similarity Partitioning Algorithm，CSPA）、元類簇算法（Meta-CLustering Algorithm，MCLA）和超圖分區(qū)算法（HyperGraph Partitioning Algorithm，HGPA）。Zhou 等［2］提出了基于投票的聚類集成方法。Fred 等［3］提出了證據(jù)積累的概念，通過(guò)在基聚類結(jié)果中構(gòu)建共協(xié)關(guān)系矩陣，分析對(duì)象間的相似性，并利用層次聚類得到了聚類結(jié)果。Wang 等［4］將傳統(tǒng)的成對(duì)約束（即必須鏈接或不能鏈接）擴(kuò)展為模糊成對(duì)約束，進(jìn)而提出了一種帶有模糊配對(duì)約束的半監(jiān)督模糊聚類（Semi-Supervised Fuzzy clustering with Pairwise Constraints，SSFPC）。

當(dāng)前聚類集成的研究以非監(jiān)督聚類集成為主，未能充分利用已知的先驗(yàn)信息，導(dǎo)致難以得到更加優(yōu)質(zhì)的聚類集成結(jié)果。半監(jiān)督聚類集成利用少量已知的先驗(yàn)信息，如少量標(biāo)簽信息或成對(duì)約束信息等提高聚類集成的質(zhì)量。Ma 等［5］利用共識(shí)函數(shù)中的約束信息，提出了基于Chameleon 的半監(jiān)督選擇性聚類集成（Semi-supervised Selective Clustering Ensemble based on Chameleon，SSCEC）和基于Ncut 的半監(jiān)督選擇性聚類合集（Semi-supervised Selective Clustering Ensemble based on Ncut，SSCEN）方法。SSCEC 使用Chameleon 算法作為共識(shí)函數(shù)，并在子圖分割和子圖組合中處理約束信息；SSCEN使用歸一化切割算法作為共識(shí)函數(shù)，并在圖的二分法過(guò)程中處理約束信息。實(shí)驗(yàn)結(jié)果表明，這兩種半監(jiān)督成員選擇聚類組合算法優(yōu)于其他半監(jiān)督算法。Xiao 等［6］設(shè)計(jì)了一種基于貝葉斯網(wǎng)絡(luò)的半監(jiān)督聚類集成模型，并通過(guò)變分法對(duì)模型進(jìn)行了推理和求解。這些研究推動(dòng)了半監(jiān)督聚類集成的發(fā)展，但有一個(gè)值得注意的問(wèn)題是：當(dāng)前關(guān)于半監(jiān)督聚類集成的研究依然以硬聚類為主。在硬聚類的結(jié)果中，對(duì)象與類簇之間存在明確的歸屬關(guān)系，即對(duì)象確定屬于該類簇或?qū)ο蟠_定不屬于該類簇。在現(xiàn)實(shí)的復(fù)雜數(shù)據(jù)中，對(duì)象與類簇之間的關(guān)系通常是模糊和不確定性的，對(duì)象與類簇之間缺乏明確的歸屬關(guān)系。當(dāng)可用信息不足時(shí)，強(qiáng)制將對(duì)象劃分到某一類簇容易引起較高的誤分類代價(jià)。因此現(xiàn)有的聚類集成算法難以精確地刻畫類簇的結(jié)構(gòu)特征。

Yu 等［7］將三支決策的思想引入聚類分析，并提出了三支聚類算法。不同于傳統(tǒng)的硬聚類結(jié)果，三支聚類通過(guò)一對(duì)集合呈現(xiàn)一個(gè)類簇，即核心域和邊界域。核心域中的數(shù)據(jù)表示確定屬于該類簇，邊界域中的數(shù)據(jù)表示可能屬于該類簇。瑣碎域表示核心域和邊界域并集的補(bǔ)集，用來(lái)描述確定不屬于該類簇的對(duì)象。三支聚類能夠更加精確地刻畫類簇邊界模糊的現(xiàn)象，能夠有效描述對(duì)象與類簇之間的不確定性關(guān)系。自三支聚類提出以來(lái)，多種研究成果已經(jīng)涌現(xiàn)。如Wang等［8］借鑒數(shù)學(xué)形態(tài)學(xué)中的收縮和擴(kuò)張思想，提出了一種基于數(shù)學(xué)形態(tài)學(xué)的三支聚類算法；Yu 等［9］將證據(jù)理論引入聚類分析中，提出了一種基于證據(jù)理論的密度峰值三支聚類算法；Afridi 等［10］針對(duì)含有缺失值的數(shù)據(jù)，提出了一種基于博弈粗糙集的三支聚類算法；Yu 等［11］將低秩矩陣和主動(dòng)學(xué)習(xí)引入多視圖聚類中，提出了一種基于低秩表示的多視圖主動(dòng)三支聚類算法；Jiang 等［12］利用陰影集和多粒度粗糙集的思想提出了一種三支聚類集成方法，在眾多UCI（University of California，Irvine）數(shù)據(jù)集上的實(shí)驗(yàn)效果良好。

在聚類集成中，標(biāo)簽信息和成對(duì)約束信息有助于改善集成效果，然而，很少有人考慮或同時(shí)考慮這兩種類型的先驗(yàn)知識(shí)。此外，傳統(tǒng)的基聚類結(jié)果是二支聚類，難以精確地刻畫類簇的結(jié)構(gòu)特征，使得在集成階段可能丟失一些重要信息。為了解決上述問(wèn)題，本文提出了一種基于Seeds 集和成對(duì)約束的半監(jiān)督三支聚類集成（Seeds-set based Three-Way Clustering Ensemble，STWCE）方法。首先，基于標(biāo)簽傳播算法（Label Propagation Algorithm，LPA），STWCE 方法利用標(biāo)簽信息構(gòu)建具有差異性的基聚類成員集合；然后提出一種新的方法來(lái)構(gòu)建一致性相似矩陣，并利用成對(duì)約束信息對(duì)相似矩陣進(jìn)行調(diào)整；最后，使用三支譜聚類對(duì)相似矩陣聚類，得到最終集成后的聚類結(jié)果。本文主要工作總結(jié)如下：

1）將三支決策理論引入半監(jiān)督聚類集成，利用不同類型的先驗(yàn)信息設(shè)計(jì)了一種三支標(biāo)簽傳播算法來(lái)生成基聚類成員。

2）通過(guò)在均勻的成對(duì)空間中比較不同區(qū)域的對(duì)象來(lái)區(qū)別基聚類成員所做出的貢獻(xiàn)，即采用一種新的規(guī)則對(duì)基聚類成員進(jìn)行不同的權(quán)重表示；并通過(guò)將不同基聚類成員結(jié)果進(jìn)行統(tǒng)一表示，有效解決了未對(duì)齊的問(wèn)題。

3）使用基于三支決策思想的譜聚類方法對(duì)一致性相似矩陣進(jìn)行聚類，使集成結(jié)果收斂于全局最優(yōu)解。每個(gè)類簇由一對(duì)集合進(jìn)行表示，更好地表現(xiàn)出對(duì)象與類簇之間的歸屬關(guān)系。

1 相關(guān)工作

1.1 聚類集成

給定一組數(shù)據(jù)U={x1，x2，…，xn}，n表示數(shù)據(jù)樣本的個(gè)數(shù)。聚類集成通過(guò)在數(shù)據(jù)U上重復(fù)執(zhí)行m次聚類得到一組基聚類結(jié)果Π={π1，π2，…，πm}，式中πi=是第i次基聚類的結(jié)果表示第i次基聚類的第j個(gè)類簇。聚類集成主要包括兩個(gè)步驟：基聚類Π的生成和一致性函數(shù)Γ的設(shè)計(jì)。在第一步中，主要工作是使用不同的生成機(jī)制生成一組不同的聚類結(jié)果，例如不同參數(shù)下的同一算法［12］、選擇不同算法［13］和選擇不同的對(duì)象子集［14-15］等；第二步是聚類集成的關(guān)鍵步驟，對(duì)得到的基聚類成員進(jìn)行集成來(lái)得到最終的聚類結(jié)果?，F(xiàn)有的聚類集成方法主要分為三類：基于圖的方法［16］、基于數(shù)據(jù)點(diǎn)間相似度的方法［17］和基于特征的方法［18］?；趫D的方法將聚類集成問(wèn)題表示成超圖的形式，并調(diào)用圖劃分算法求解；基于數(shù)據(jù)點(diǎn)間相似度的方法通過(guò)建立樣本間的相似矩陣，再基于相似度聚類的方法來(lái)得到聚類結(jié)果；基于特征的方法則使用每個(gè)基聚類成員內(nèi)各樣本的聚類標(biāo)簽作為新的特征來(lái)得到最后的聚類結(jié)果。

1.2 三支聚類的基本形式

傳統(tǒng)的聚類算法是一種硬聚類或者說(shuō)二支聚類的結(jié)果，即對(duì)象和類簇之間的關(guān)系是明確的，對(duì)象確定屬于該類簇或?qū)ο蟠_定不屬于該類簇。給定一組數(shù)據(jù)U={x1，x2，…，xn}，二支聚類通過(guò)單個(gè)集合Ci表示一個(gè)類簇。所劃分的類簇內(nèi)具有較高的相似性，而類簇間具有較高的相異性。給定一組類簇集合C={C1，C2，…，Ck}，將U中所有的對(duì)象劃分到k個(gè)類簇中，并且k個(gè)類簇滿足如下條件：

1）類簇不能為空，即每個(gè)類簇至少包含一個(gè)對(duì)象：Ci≠?(i=1，2，…，k)；

3）每一個(gè)對(duì)象只能屬于一個(gè)類簇，即類簇之間的交集為空：Ci∩Cj=?(i≠j)。

不同于二支聚類，三支聚類將每個(gè)類簇用一對(duì)集合進(jìn)行表示：Ci={Co(Ci)，F(xiàn)r(Ci)}，即類簇Ci由核心域Co(Ci)和邊界域Fr(Ci)兩個(gè)子集組成。類簇Ci的瑣碎域表示為Tr(Ci)=U-Co(Ci) -Fr(Ci)，表示由確定不屬于類簇Ci的對(duì)象組成的集合。類簇Ci的三個(gè)域滿足如下條件：

上述4 個(gè)條件說(shuō)明任何一個(gè)類簇的核心域、邊界域和瑣碎域之間的并集為論域OB，且核心域、邊界域和瑣碎域兩兩互不相交。三支聚類的k個(gè)類簇滿足如下條件：

上述三個(gè)條件說(shuō)明任意一個(gè)類簇的核心域不為空，所有類簇的核心域和邊界域的并集為論域OB，任意兩個(gè)類簇的核心域的交集為空。

1.3 半監(jiān)督聚類

按照不同的監(jiān)督信息，半監(jiān)督聚類可分為基于成對(duì)約束信息的半監(jiān)督聚類和基于標(biāo)簽信息的半監(jiān)督聚類。

成對(duì)約束信息有must-link 和cannot-link：must-link 指兩個(gè)對(duì)象屬于同一個(gè)類別；cannot-link 指兩個(gè)對(duì)象不屬于同一個(gè)類別。Wagstaff 等［19］將成對(duì)約束的思想運(yùn)用到傳統(tǒng)K-means 算法中，提出了Cop-Kmeans 算法；Zheng 等［20］將成對(duì)約束思想引入層次聚類算法，在層次聚類中也可以使用成對(duì)約束；Yang 等［21］通過(guò)對(duì)cannot-link 進(jìn)行廣度搜索來(lái)解決Cop-Kmeans 中的約束沖突問(wèn)題，并通過(guò)MapReduce 降低計(jì)算復(fù)雜度。

相較于成對(duì)約束信息，標(biāo)簽信息可以直接判斷數(shù)據(jù)點(diǎn)的類別。Qin 等［22］系統(tǒng)性回顧了半監(jiān)督聚類，尤其是對(duì)基于約束信息的半監(jiān)督聚類方法；Zhou 等［23］提出了標(biāo)簽傳播算法，該算法是基于圖的半監(jiān)督聚類的代表性算法；Yu 等［24］同時(shí)考慮特征空間和樣本空間的漸進(jìn)式子空間的方法以獲得更準(zhǔn)確的半監(jiān)督聚類結(jié)果；Fang 等［25］提出了一種基于低秩表示的半監(jiān)督子空間聚類方法，將低秩表示框架與高斯場(chǎng)和諧函數(shù)結(jié)合，通過(guò)融合標(biāo)簽信息完成相似矩陣的構(gòu)造和子空間聚類。

半監(jiān)督聚類算法在很多領(lǐng)域等都有著廣泛的應(yīng)用。在以上研究中，只使用了單一的監(jiān)督信息來(lái)輔助聚類。然而，先驗(yàn)信息不僅有成對(duì)約束，還存在標(biāo)簽信息，不同類型的先驗(yàn)信息具有不同的意義，因此，如何融合不同類型的先驗(yàn)信息達(dá)到聚類結(jié)果的目的有著重要的研究意義。

2 基于Seeds 集和成對(duì)約束的半監(jiān)督三支聚類集成方法

本章首先闡述了基于Seeds 集和成對(duì)約束的半監(jiān)督三支聚類集成（STWCE）方法的基本思想，然后詳細(xì)介紹了該方法的關(guān)鍵步驟。

2.1 STWCE的基本思想

圖1 給出了STWCE 方法的基本框架，其中：p為打標(biāo)問(wèn)詢次數(shù)，P為最大問(wèn)詢次數(shù)。由圖1 可知，該方法首先采用LPA 生成多個(gè)具有差異性的基聚類集合，即Π={π1，π2，…，πm}。每個(gè)節(jié)點(diǎn)的標(biāo)簽更新取決于其鄰居節(jié)點(diǎn)，更新效果受節(jié)點(diǎn)初始輸入和標(biāo)簽更新順序的影響，因此每次結(jié)果存在不確定性，強(qiáng)制將不確定的對(duì)象分配到某一類可能會(huì)降低聚類的結(jié)果，而三支決策思想正是解決聚類算法結(jié)果不穩(wěn)定和不精確問(wèn)題的重要方法之一。通過(guò)將每個(gè)類由兩個(gè)集合進(jìn)行表示，減少由于強(qiáng)制分類而帶來(lái)的聚類效果的降低，更好地呈現(xiàn)出對(duì)象與類簇之間的關(guān)系。

圖1 STWCE方法的框架Fig.1 Framework of STWCE method

在得到基聚類集合后，共協(xié)關(guān)系矩陣可能只得到了部分點(diǎn)的相似關(guān)系，例如，對(duì)象x在不同基聚類結(jié)果中可能有不同的歸屬關(guān)系。另外，不同的基聚類成員聚類后的標(biāo)簽可能并不對(duì)應(yīng)，因此，定義一組規(guī)則來(lái)統(tǒng)一表示不同基聚類成員的結(jié)果，并針對(duì)不同區(qū)域的對(duì)象采用不同的策略進(jìn)行集成，以更好地描述對(duì)象間的相似關(guān)系，并利用成對(duì)約束信息優(yōu)化調(diào)整一致性相似矩陣。最后通過(guò)三支譜聚類方法對(duì)一致性相似矩陣聚類，得到最終的集成結(jié)果。

2.2 基聚類成員生成

基聚類成員的產(chǎn)生方法多種多樣，如采用不同的聚類算法、采用不同參數(shù)下同一聚類算法、在特征子空間進(jìn)行聚類和在數(shù)據(jù)子空間進(jìn)行聚類等。然而，這些成員生成方法未考慮到數(shù)據(jù)集中已有的標(biāo)簽信息，本文設(shè)計(jì)了一種三支標(biāo)簽傳播算法（TW-LPA），利用已有標(biāo)簽信息構(gòu)成的Seeds 集對(duì)原始數(shù)據(jù)集進(jìn)行聚類。

LPA 只需利用少量的標(biāo)簽信息指導(dǎo)就可以發(fā)現(xiàn)未標(biāo)記數(shù)據(jù)的內(nèi)在特性、分布規(guī)律，進(jìn)而預(yù)測(cè)和傳播未標(biāo)記數(shù)據(jù)的標(biāo)簽，合并到標(biāo)記的數(shù)據(jù)集中。LPA 通過(guò)相似節(jié)點(diǎn)之間的標(biāo)簽的傳遞來(lái)學(xué)習(xí)如何進(jìn)行聚類，所以它不受數(shù)據(jù)分布的限制。算法具有線性時(shí)間復(fù)雜度，廣泛應(yīng)用于大規(guī)模數(shù)據(jù)處理和挖掘。然而，該算法每個(gè)節(jié)點(diǎn)的標(biāo)簽更新取決于其鄰居節(jié)點(diǎn)，更新效果受節(jié)點(diǎn)初始輸入和標(biāo)簽更新順序的影響。因此，LPA 的每次結(jié)果存在不確定性，而三支決策思想正是解決聚類算法結(jié)果不穩(wěn)定和不精確的重要方法之一。為此，將多次運(yùn)行的LPA 的結(jié)果作為基聚類的結(jié)果。

給定原始數(shù)據(jù)集U={x1，x2，…，xn}，用Π={π1，π2，…，πK}表示基聚類成員集合，πi表示第i個(gè)基聚類的結(jié)果。數(shù)據(jù)集中前l(fā)個(gè)對(duì)象帶有數(shù)據(jù)類標(biāo)簽，后n-l個(gè)對(duì)象不帶數(shù)據(jù)類標(biāo)簽。給定已知對(duì)象的標(biāo)簽集合Y={y1，y2，…，yl}，集合U的前l(fā)個(gè)對(duì)象在Y中一一對(duì)應(yīng)。給定圖結(jié)構(gòu)G=(U，W)，其中：U為數(shù)據(jù)集合在圖G中的節(jié)點(diǎn)；W代表節(jié)點(diǎn)之間的相似性關(guān)系，即節(jié)點(diǎn)間的權(quán)重。計(jì)算節(jié)點(diǎn)間權(quán)重Wij：

定義一個(gè)n×n的概率傳播矩陣P，節(jié)點(diǎn)i的標(biāo)簽傳遞給節(jié)點(diǎn)j的概率Pij為：

其中：Pij表示節(jié)點(diǎn)i的標(biāo)簽傳遞給節(jié)點(diǎn)j的概率。

通過(guò)概率傳遞，使概率分布集中于給定類別，然后通過(guò)邊的權(quán)重值來(lái)傳遞節(jié)點(diǎn)標(biāo)簽。在通過(guò)LPA 得到C={C1，C2，…，Ck}時(shí)，可能會(huì)得到如圖2 的結(jié)果：將每個(gè)類簇用一個(gè)集合進(jìn)行表示，x1與x2分別被聚類到C1和C2中，但從圖2 中可以看到強(qiáng)制性劃分到一個(gè)類中可能是錯(cuò)誤的。因此，引入三支聚類，并借鑒k近鄰的思想，設(shè)計(jì)一種三支標(biāo)簽傳播算法（TW-LPA），將LPA 的結(jié)果進(jìn)行再次劃分，采用Dist(x)（距離該點(diǎn)最近的t個(gè)點(diǎn)組成的集合）對(duì)每個(gè)類別的對(duì)象進(jìn)行劃分，將每個(gè)類簇進(jìn)一步劃分為核心域Co(Ci)和邊界域Fr(Ci)兩個(gè)子集，更好地展現(xiàn)對(duì)象與類簇的歸屬關(guān)系，從而減少在基聚類階段由于強(qiáng)制劃分某些對(duì)象帶來(lái)的信息丟失導(dǎo)致聚類效果的降低。

圖2 對(duì)象與類簇的歸屬關(guān)系Fig.2 Belonging relationships between objects and class clusters

首先，考慮對(duì)象xi的Dist(xi)，xi∈Ci，設(shè)arg maxDist(xi)代表距離該點(diǎn)最近的t個(gè)對(duì)象中數(shù)量最多的集合，若arg maxDist(xi) ∩Ci≥t，將xi分配到 該類的 核心域，即xi∈Co(Ci)，否則，xi∈Fr(Ci)。此外，對(duì)于對(duì)象xj?Ci，如果arg maxDist(xj) ∩Ci=?，將xi分配到邊界域，即xj∈Fr(Ci)。在進(jìn)行n次之后，得到了新的標(biāo)簽傳播結(jié)果。運(yùn)行TW-LPA獲得集合Π={π1，π2，…，πK}。具體流程見算法1。

算法1 基于TW-LPA 的基聚類成員生成。

2.3 半監(jiān)督三支聚類集成

在得到由TW-LPA 產(chǎn)生的具有不同差異的基聚類成員集合Π={π1，π2，…，πK}后，將構(gòu)建一致性相似矩陣，并利用成對(duì)約束信息對(duì)一致性相似矩陣進(jìn)行優(yōu)化調(diào)整。最后利用三支譜聚類對(duì)調(diào)整后的相似矩陣聚類，得到最終的集成結(jié)果。

2.3.1 半監(jiān)督三支聚類集成

利用無(wú)類屬數(shù)據(jù)內(nèi)部存在的結(jié)構(gòu)先驗(yàn)信息，同時(shí)結(jié)合成對(duì)約束信息匯總來(lái)自基聚類成員集合Π的信息構(gòu)造相似矩陣。

對(duì)于每個(gè)基聚類成員πd(1 ≤d≤K)的結(jié)果，將它的每個(gè)類利用核心域Co(Ci)和邊界域Fr(Ci)兩個(gè)集合進(jìn)行表示。相較于傳統(tǒng)的硬聚類和軟聚類表示方法，三支聚類的表示更加直觀地展示了對(duì)象與類簇之間的歸屬關(guān)系，位于核心域中的對(duì)象比邊界域的對(duì)象更具有可信度。此外，不同基聚類通過(guò)聚類得到的結(jié)果可能是不對(duì)齊的，與監(jiān)督學(xué)習(xí)不同，聚類后的結(jié)果僅表示數(shù)據(jù)的聚類特征，將不同的聚類結(jié)果直接進(jìn)行比較并不可行。例如，如圖3 所示，對(duì)象x在不同的基聚類成員中可能有不同的歸屬關(guān)系。

圖3 對(duì)象x在不同的基聚類成員中的歸屬關(guān)系Fig.3 Belonging relationships of object x in different base cluster members

定義以下規(guī)則用來(lái)統(tǒng)一表示不同基聚類成員的結(jié)果。設(shè)P=[P(i，j)]是一個(gè)n×n的矩陣，其中，P(i，j)是xi和xj之間的相似度。

1）如果對(duì)象xi和對(duì)象xj屬于同一個(gè)類Ci，同時(shí)有xi∈Co(Ci)和xj∈Co(Ci)，則P(i，j)=λ+；

2）如果對(duì)象xi和對(duì)象xj屬于同一個(gè)類Ci，同時(shí)有xi∈Co(Ci)和xj∈Fr(Ci)，則P(i，j)=λ；

3）如果對(duì)象xi和對(duì)象xj屬于同一個(gè)類Ci，同時(shí)有xi∈Fr(Ci)和xj∈Fr(Ci)，則P(i，j)=λ-。

其中，0 ＜λ-＜λ＜λ+＜1。

根據(jù)式（3），將不同的基聚類成員結(jié)果進(jìn)行統(tǒng)一表示。

根據(jù)所提出的表示方法，當(dāng)有K個(gè)基聚類成員進(jìn)行集成時(shí)，可以將每個(gè)基聚類成員的結(jié)果保存到一個(gè)n×n的成對(duì)矩陣中。設(shè)P=是來(lái)自K個(gè)基聚類成員的一組成對(duì)矩陣，其中，Pt=[Pt(i，j)]是用來(lái)保存來(lái)自第t個(gè)基聚類成員的n×n的成對(duì)矩陣。在給定基聚類成員集合Π={π1，π2，…，πK}的情況下，可以找到所有基聚類成員間的一致性相似矩陣S的元素S(i，j)如下：

得到相似矩陣S后，利用成對(duì)約束信息優(yōu)化調(diào)整相似矩陣S，使對(duì)象xi和xj在一個(gè)類簇中更緊湊，在不同類簇中更離散。對(duì)象xi和xj的相似性由Sij和Sji表示，Sij和Sji是相似矩陣S中的元素。如果對(duì)象xi和xj標(biāo)記在同一個(gè)類簇中，滿足must-link 關(guān)系，即(xi，xj) ∈ML，相似矩陣S中相應(yīng)的元素更新為1；相反，如果xi和xj不屬于同一個(gè)類簇，滿足cannot-link關(guān)系，即(xi，xj) ∈CL，相似矩陣S中相應(yīng)的元素更新為0。

采用以下的策略進(jìn)行對(duì)S(i，j)進(jìn)行調(diào)整：

算法2 相似矩陣構(gòu)造算法。

根據(jù)式（3）計(jì)算Pt(i，j)

2.3.2 三支譜聚類

在上一步處理中得到了一致性相似矩陣，現(xiàn)在將定義一個(gè)劃分準(zhǔn)則，目的是使同一類簇的對(duì)象更緊湊，不同類簇的對(duì)象更分散。由于求圖劃分的最優(yōu)解是一個(gè)NP 難的問(wèn)題，一個(gè)很好的解決方法是考慮問(wèn)題的連續(xù)放松形式，將原問(wèn)題轉(zhuǎn)換為求圖的Laplacian 矩陣的譜分解。

譜聚類是一種基于圖劃分理論的方法，能對(duì)任意形狀的數(shù)據(jù)進(jìn)行劃分且收斂于全局最優(yōu)解。三支譜聚類是將三支決策思想和譜聚類方法相結(jié)合，將每個(gè)類簇由一對(duì)集合進(jìn)行表示Ci={Co(Ci)，F(xiàn)r(Ci)}，核心域Co(Ci)和邊界域Fr(Ci)兩個(gè)子集構(gòu)成該類簇的上界。

三支譜聚類算法主要過(guò)程分為兩步：1）對(duì)一致性相似度矩陣通過(guò)譜聚類方法獲得每個(gè)類簇的上界；2）借助于三支決策思想，基于q鄰域?qū)⒚總€(gè)類簇的上界進(jìn)一步劃分為核心域Co(Ci)和邊界域Fr(Ci)兩個(gè)子集。基本流程如算法3 所示。

算法3 三支譜聚類。

2.4 復(fù)雜性分析

基聚類算法階段：設(shè)基聚類算法的個(gè)數(shù)為ε(ε≥2)，第i(i∈[1，ε])個(gè)基聚類算法的復(fù)雜度為φi，則所有的基聚類算法的復(fù)雜度為

集成階段：計(jì)算一個(gè)基聚類成員n×n的成對(duì)關(guān)系矩陣復(fù)雜度為O(n2)，那么計(jì)算整個(gè)基聚類成員集合的復(fù)雜度是O(n2k)。構(gòu)建基于成對(duì)約束信息監(jiān)督矩陣對(duì)CTS（Connected-Triple-based Similarity）矩陣進(jìn)行修改的復(fù)雜度為O(n2)。

譜聚類階段：進(jìn)行譜聚類的時(shí)間復(fù)雜度為O(n3)，構(gòu)造核心域和邊界域的時(shí)間復(fù)雜度為O(n2k)。

所以，STWCE 算法的復(fù)雜度約為：

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

3.1 實(shí)驗(yàn)數(shù)據(jù)與評(píng)價(jià)標(biāo)準(zhǔn)

采用UCI 數(shù)據(jù)中的7 個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。其中3 個(gè)是二類的，4 個(gè)是多類的，維度分布有高有低。表1 給出了這些數(shù)據(jù)集的相關(guān)信息描述。

表1 實(shí)驗(yàn)數(shù)據(jù)集相關(guān)信息描述Tab.1 Information description of experimental datasets

實(shí)驗(yàn)采用目前三種廣泛使用的聚類性能評(píng)價(jià)指標(biāo)：

1）歸一化互信息（Normalized Mutual Information，NMI）。NMI 用于評(píng)價(jià)對(duì)數(shù)據(jù)集聚類后的結(jié)果與數(shù)據(jù)集的真實(shí)結(jié)果之間的相似程度。設(shè)C為對(duì)數(shù)據(jù)集聚類后的結(jié)果，Y為數(shù)據(jù)集的真實(shí)結(jié)果，NMI 計(jì)算公式如下：

式中：I(X；Y)=H(X) -H(X|Y)，反映了兩個(gè)變量X和Y之間的互信息；H(X)表示變量X的香農(nóng)熵；H(X|Y)表示基于給定Y的情況下X的條件熵。RNMI∈[0，1]，值越大代表聚類效果越好。

2）調(diào)整蘭德系數(shù)（Adjusted Rand Index，ARI）。ARI 衡量的是兩個(gè)數(shù)據(jù)分布的相似性。ARI 計(jì)算公式如下：

其中：a表示在C與Y中都是同類別的元素對(duì)數(shù)，b表示在C與Y中都是不同類別的元素對(duì)數(shù)表示數(shù)據(jù)集中可以組成的對(duì)數(shù)。RARI∈[ -1，1]，值越大意味著聚類結(jié)果與真實(shí)情況越吻合。

3）F 測(cè)度（F-Measure）。該指標(biāo)綜合了精確率和召回率評(píng)估標(biāo)準(zhǔn)，反映了任意一對(duì)樣本的正確歸類的準(zhǔn)確性。F-Measure 的值越高越好，它的計(jì)算公式如下：

其中：P表示精確率，R表示召回率。

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

3.2.1 算法性能比較

實(shí)驗(yàn)首先選取LPA 作為基聚類器，運(yùn)行20 次。由于LPA 的不穩(wěn)定性，將會(huì)得到20 個(gè)有差異性的基聚類結(jié)果；然后通過(guò)本文方法構(gòu)造一致性相似矩陣，利用成對(duì)約束信息對(duì)一致性相似矩陣進(jìn)行調(diào)整，再經(jīng)過(guò)三支譜聚類得到集成后的結(jié)果C。

實(shí)驗(yàn)中采取的對(duì)比算法有CSPA［1］、HGPA［1］、MCLA［1］、LPA［23］、Cop-Kmeans 算法［19］、限制性投射半監(jiān)督的譜聚類集成（Constraint Projections for Semi-Supervised Spectral Clustering Ensemble，CPSSSCE）算法［25］。為了公平對(duì)比，從每一類數(shù)據(jù)集中抽取5%的標(biāo)簽樣本，標(biāo)簽樣本作為基聚類算法的Seeds 集；同時(shí)從每一類Ground-Truth 的成對(duì)約束信息中選出20%的必連信息和20%的不連信息，作為成對(duì)約束的先驗(yàn)知識(shí)。本文中的λ-、λ和λ+分別設(shè)置為0.3、0.5和0.7。

表2～4 分別概括了7 個(gè)數(shù)據(jù)集上給予不同類別相同比例的監(jiān)督信息下，本文方法STWCE 以及對(duì)比的6 種方法的ARI值、NMI 值和F-Measure 值，加粗表示最優(yōu)值。從實(shí)驗(yàn)結(jié)果可以看出，這7 種方法在不同的數(shù)據(jù)集上都獲得了不同程度的聚類效果，而STWCE 的三個(gè)評(píng)價(jià)指標(biāo)在絕大多數(shù)據(jù)集上都獲得了相對(duì)較好的聚類集成效果，說(shuō)明綜合考慮標(biāo)簽信息和成對(duì)約束信息的融合以及本文所提出的集成策略能夠改善聚類效果。

表2 不同算法的ARI值Tab.2 ARI values of different algorithms

表3 不同算法的NMI值Tab.3 NMI values of different algorithms

表4 不同算法的F-Measure值Tab.4 F-measure values of different algorithms

3.2.2 一致性相似矩陣分析

為了更好地說(shuō)明本文提出的半監(jiān)督三支聚類集成方法構(gòu)成一致性相似矩陣的效果，在不同的數(shù)據(jù)集上使用不同比例的先驗(yàn)信息，采用三種指標(biāo)與傳統(tǒng)的CO-association（CO）矩陣和CTS 矩陣算法進(jìn)行對(duì)比。不同算法采用相同的基聚類算法并在給予相同比例的先驗(yàn)信息下進(jìn)行實(shí)驗(yàn)，部分結(jié)果如圖4 所示。從圖4 可以看出：隨著給予的先驗(yàn)信息的比例增大，三種評(píng)價(jià)指標(biāo)都有逐漸增加的趨勢(shì)；但是當(dāng)提供的先驗(yàn)信息達(dá)到一定值之后，這些指標(biāo)的增長(zhǎng)趨勢(shì)都略顯減緩。

圖4 不同先驗(yàn)信息下數(shù)據(jù)集Segment的ARI、NMI和F-Measure對(duì)比Fig.4 Comparison of ARI，NMI and F-Measure of dataset Segment under different priori information

此外，在大部分的數(shù)據(jù)集上，在先驗(yàn)信息不足的情況下，可以看出本文方法相較于另外兩個(gè)算法有更好的集成效果。這說(shuō)明相對(duì)于傳統(tǒng)方法，三支聚類更加直觀地展示了對(duì)象與類簇之間的歸屬關(guān)系，經(jīng)過(guò)不同的規(guī)則處理后的基聚類集合采用不同的規(guī)則進(jìn)行集成，充分考慮了不同成員的不同貢獻(xiàn)，在大部分?jǐn)?shù)據(jù)集上相對(duì)于傳統(tǒng)的CO 矩陣算法和CTS 矩陣方法擁有更優(yōu)的聚類性能。

4 結(jié)語(yǔ)

本文提出了半監(jiān)督的三支聚類集成方法，它能有效利用有限的先驗(yàn)知識(shí)，同時(shí)融合標(biāo)簽信息和成對(duì)約束信息。使用連接三元組構(gòu)造相似矩陣，并利用成對(duì)約束信息對(duì)相似矩陣進(jìn)行調(diào)整，通過(guò)三支譜聚類進(jìn)行聚類，最后得到聚類集成結(jié)果。

在多個(gè)數(shù)據(jù)集上評(píng)估了該方法，得出以下結(jié)論：1）使用標(biāo)簽傳播算法作為基聚類算法，不僅可以利用標(biāo)簽傳播算法的優(yōu)勢(shì)，同時(shí)又能避免標(biāo)簽傳播算法不穩(wěn)定的問(wèn)題；2）使用基于三支聚類的方法來(lái)集成基聚類成員構(gòu)建相似矩陣，并使用成對(duì)約束信息進(jìn)行修改，在獲得了優(yōu)質(zhì)的相似矩陣的同時(shí)避免了基聚類成員非對(duì)齊的問(wèn)題，同時(shí)考慮了不同基聚類成員之間的貢獻(xiàn)不同的問(wèn)題；3）通過(guò)結(jié)合不同類型先驗(yàn)信息，可以有效提高聚類集成的性能；4）使用三支譜聚類對(duì)相似矩陣進(jìn)行聚類得到集成后的結(jié)果，不僅能對(duì)任意形狀的數(shù)據(jù)進(jìn)行劃分，且收斂于全局最優(yōu)解，同時(shí)將每個(gè)類簇用核心域和邊界域進(jìn)行表示，更加直觀地展示了數(shù)據(jù)對(duì)象確定屬于或可能屬于某個(gè)類簇。

在未來(lái)的工作將從兩個(gè)方面進(jìn)行考慮：一是考慮基聚類的質(zhì)量，去除一些低質(zhì)量的基聚類；二是引入主動(dòng)學(xué)習(xí)，進(jìn)一步提高成對(duì)約束的質(zhì)量。