基于Seeds集和成對約束的半監督三支聚類集成

姜春茂，吳 鵬，李志聰*

（1.福建工程學院 計算機科學與數學學院，福州 350118；2.哈爾濱師范大學 計算機科學與信息工程學院，哈爾濱 150025）

0 引言

聚類分析是一種典型的無監督機器學習方法。聚類分析因為不需要給定樣本的標簽信息，僅通過衡量數據之間的關系就能識別數據中潛在的結構特征而受到廣泛的關注。但單一的聚類算法往往采用某種理想化的數據分布假設，如K-means 算法假設樣本均勻分布在球形的樣本空間中，當樣本分布不均勻或存在較多的噪點時，聚類效果不佳。不同的聚類算法往往存在較大的差異性，即使相同的聚類算法在參數不同時，聚類結果也往往存在差異。這限制了聚類分析的適用性。

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

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

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

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

1）將三支決策理論引入半監督聚類集成，利用不同類型的先驗信息設計了一種三支標簽傳播算法來生成基聚類成員。

2）通過在均勻的成對空間中比較不同區域的對象來區別基聚類成員所做出的貢獻，即采用一種新的規則對基聚類成員進行不同的權重表示；并通過將不同基聚類成員結果進行統一表示，有效解決了未對齊的問題。

3）使用基于三支決策思想的譜聚類方法對一致性相似矩陣進行聚類，使集成結果收斂于全局最優解。每個類簇由一對集合進行表示，更好地表現出對象與類簇之間的歸屬關系。

1 相關工作

1.1 聚類集成

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

1.2 三支聚類的基本形式

傳統的聚類算法是一種硬聚類或者說二支聚類的結果，即對象和類簇之間的關系是明確的，對象確定屬于該類簇或對象確定不屬于該類簇。給定一組數據U={x1，x2，…，xn}，二支聚類通過單個集合Ci表示一個類簇。所劃分的類簇內具有較高的相似性，而類簇間具有較高的相異性。給定一組類簇集合C={C1，C2，…，Ck}，將U中所有的對象劃分到k個類簇中，并且k個類簇滿足如下條件：

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

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

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

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

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

1.3 半監督聚類

按照不同的監督信息，半監督聚類可分為基于成對約束信息的半監督聚類和基于標簽信息的半監督聚類。

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

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

半監督聚類算法在很多領域等都有著廣泛的應用。在以上研究中，只使用了單一的監督信息來輔助聚類。然而，先驗信息不僅有成對約束，還存在標簽信息，不同類型的先驗信息具有不同的意義，因此，如何融合不同類型的先驗信息達到聚類結果的目的有著重要的研究意義。

2 基于Seeds 集和成對約束的半監督三支聚類集成方法

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

2.1 STWCE的基本思想

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

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

在得到基聚類集合后，共協關系矩陣可能只得到了部分點的相似關系，例如，對象x在不同基聚類結果中可能有不同的歸屬關系。另外，不同的基聚類成員聚類后的標簽可能并不對應，因此，定義一組規則來統一表示不同基聚類成員的結果，并針對不同區域的對象采用不同的策略進行集成，以更好地描述對象間的相似關系，并利用成對約束信息優化調整一致性相似矩陣。最后通過三支譜聚類方法對一致性相似矩陣聚類，得到最終的集成結果。

2.2 基聚類成員生成

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

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

給定原始數據集U={x1，x2，…，xn}，用Π={π1，π2，…，πK}表示基聚類成員集合，πi表示第i個基聚類的結果。數據集中前l個對象帶有數據類標簽，后n-l個對象不帶數據類標簽。給定已知對象的標簽集合Y={y1，y2，…，yl}，集合U的前l個對象在Y中一一對應。給定圖結構G=(U，W)，其中：U為數據集合在圖G中的節點；W代表節點之間的相似性關系，即節點間的權重。計算節點間權重Wij：

定義一個n×n的概率傳播矩陣P，節點i的標簽傳遞給節點j的概率Pij為：

其中：Pij表示節點i的標簽傳遞給節點j的概率。

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

圖2 對象與類簇的歸屬關系Fig.2 Belonging relationships between objects and class clusters

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

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

2.3 半監督三支聚類集成

在得到由TW-LPA 產生的具有不同差異的基聚類成員集合Π={π1，π2，…，πK}后，將構建一致性相似矩陣，并利用成對約束信息對一致性相似矩陣進行優化調整。最后利用三支譜聚類對調整后的相似矩陣聚類，得到最終的集成結果。

2.3.1 半監督三支聚類集成

利用無類屬數據內部存在的結構先驗信息，同時結合成對約束信息匯總來自基聚類成員集合Π的信息構造相似矩陣。

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

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

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

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

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

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

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

根據式（3），將不同的基聚類成員結果進行統一表示。

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

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

采用以下的策略進行對S(i，j)進行調整：

算法2 相似矩陣構造算法。

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

2.3.2 三支譜聚類

在上一步處理中得到了一致性相似矩陣，現在將定義一個劃分準則，目的是使同一類簇的對象更緊湊，不同類簇的對象更分散。由于求圖劃分的最優解是一個NP 難的問題，一個很好的解決方法是考慮問題的連續放松形式，將原問題轉換為求圖的Laplacian 矩陣的譜分解。

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

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

算法3 三支譜聚類。

2.4 復雜性分析

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

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

譜聚類階段：進行譜聚類的時間復雜度為O(n3)，構造核心域和邊界域的時間復雜度為O(n2k)。

所以，STWCE 算法的復雜度約為：

3 實驗與結果分析

3.1 實驗數據與評價標準

采用UCI 數據中的7 個數據集進行實驗。其中3 個是二類的，4 個是多類的，維度分布有高有低。表1 給出了這些數據集的相關信息描述。

表1 實驗數據集相關信息描述Tab.1 Information description of experimental datasets

實驗采用目前三種廣泛使用的聚類性能評價指標：

1）歸一化互信息（Normalized Mutual Information，NMI）。NMI 用于評價對數據集聚類后的結果與數據集的真實結果之間的相似程度。設C為對數據集聚類后的結果，Y為數據集的真實結果，NMI 計算公式如下：

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

2）調整蘭德系數（Adjusted Rand Index，ARI）。ARI 衡量的是兩個數據分布的相似性。ARI 計算公式如下：

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

3）F 測度（F-Measure）。該指標綜合了精確率和召回率評估標準，反映了任意一對樣本的正確歸類的準確性。F-Measure 的值越高越好，它的計算公式如下：

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

3.2 實驗結果與分析

3.2.1 算法性能比較

實驗首先選取LPA 作為基聚類器，運行20 次。由于LPA 的不穩定性，將會得到20 個有差異性的基聚類結果；然后通過本文方法構造一致性相似矩陣，利用成對約束信息對一致性相似矩陣進行調整，再經過三支譜聚類得到集成后的結果C。

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

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

表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 一致性相似矩陣分析

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

圖4 不同先驗信息下數據集Segment的ARI、NMI和F-Measure對比Fig.4 Comparison of ARI，NMI and F-Measure of dataset Segment under different priori information

此外，在大部分的數據集上，在先驗信息不足的情況下，可以看出本文方法相較于另外兩個算法有更好的集成效果。這說明相對于傳統方法，三支聚類更加直觀地展示了對象與類簇之間的歸屬關系，經過不同的規則處理后的基聚類集合采用不同的規則進行集成，充分考慮了不同成員的不同貢獻，在大部分數據集上相對于傳統的CO 矩陣算法和CTS 矩陣方法擁有更優的聚類性能。

4 結語

本文提出了半監督的三支聚類集成方法，它能有效利用有限的先驗知識，同時融合標簽信息和成對約束信息。使用連接三元組構造相似矩陣，并利用成對約束信息對相似矩陣進行調整，通過三支譜聚類進行聚類，最后得到聚類集成結果。

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

在未來的工作將從兩個方面進行考慮：一是考慮基聚類的質量，去除一些低質量的基聚類；二是引入主動學習，進一步提高成對約束的質量。