王留洋，俞揚(yáng)信，陳伯倫，章 慧

（淮陰工學(xué)院計算機(jī)與軟件工程學(xué)院，江蘇淮安223003）

（?通信作者電子郵箱wangly@hyit.edu.cn）

0 引言

目前，大量數(shù)據(jù)通過不同的渠道源源不斷地匯集到互聯(lián)網(wǎng)數(shù)據(jù)庫中，并有針對性地作為互聯(lián)網(wǎng)的副產(chǎn)品進(jìn)入社會。網(wǎng)絡(luò)信息的巨大容量對搜索引擎的信息檢索效率造成了巨大威脅。在搜索引擎返回數(shù)千個搜索結(jié)果中，只有極少部分與用戶感興趣的話題有關(guān)［1］。對無標(biāo)記數(shù)據(jù)可進(jìn)行無監(jiān)督數(shù)據(jù)分析。數(shù)據(jù)聚類是一種無監(jiān)督學(xué)習(xí)技術(shù)，聚類利用數(shù)據(jù)中的非結(jié)構(gòu)化信息揭示數(shù)據(jù)間潛在的關(guān)系［2］。

個人資料庫和公共論壇中的信息通常以文本形式出現(xiàn)，這樣的數(shù)據(jù)無法用傳統(tǒng)數(shù)據(jù)庫工具進(jìn)行抓取、管理和處理。文本數(shù)據(jù)一般屬于未標(biāo)記數(shù)據(jù)類別，可通過數(shù)據(jù)聚類技術(shù)進(jìn)行分析。數(shù)據(jù)聚類技術(shù)在計算機(jī)中的應(yīng)用已超過50 年，現(xiàn)有的技術(shù)有共識聚類、多視圖聚類、集合聚類和累積聚類等。

近年來，不同的聚類算法用于設(shè)計各自的策略，然而，每種技術(shù)在執(zhí)行特定數(shù)據(jù)集時都有一定的局限性。因此，缺少一種通用的數(shù)據(jù)聚類方法，支持不同技術(shù)的混合聚類，即共識聚類。共識聚類可通過以下幾步實(shí)現(xiàn):首先，劃分訓(xùn)練數(shù)據(jù)，并使用不同聚類方法對每個數(shù)據(jù)進(jìn)行分區(qū)，以便獲得基本結(jié)果；其次，使用相同的算法，進(jìn)行不同的初始化或使用不同的參數(shù)，通過聚類技術(shù)間的關(guān)系建立共識；最后，使用不同的特征空間給共識分配新標(biāo)簽，并在第一時間通過聚類更改基礎(chǔ)分區(qū)，設(shè)計最終的聚類方案［3］。本文提出了一種使用監(jiān)督學(xué)習(xí)方法集成文檔聚類的共識構(gòu)建方法，該共識構(gòu)建方法是現(xiàn)有文檔聚類的共識聚類技術(shù)的新補(bǔ)充，共識功能使用了一種基礎(chǔ)聚類生成的標(biāo)簽訓(xùn)練分類器，且訓(xùn)練分類器通過預(yù)測標(biāo)簽生成最后的分區(qū)。

1 相關(guān)研究

數(shù)據(jù)聚類是開發(fā)未標(biāo)記數(shù)據(jù)的底層結(jié)構(gòu)的基本工具之一。文本數(shù)據(jù)種類繁多，數(shù)據(jù)聚類技術(shù)需不斷發(fā)展，以適應(yīng)未來的挑戰(zhàn)。目前，大多數(shù)設(shè)計的數(shù)據(jù)聚類方法都具有已知的潛力，但在大多數(shù)情況下，沒有一種通用的技術(shù)能夠保持良好的性能。可靠的解決方案是將不同的聚類技術(shù)融合成一個單一策略。

將多種聚類技術(shù)結(jié)合起來進(jìn)行最終數(shù)據(jù)劃分的想法啟發(fā)于分類器和信息融合中使用的類似策略啟發(fā)。與此類似，K 均值（K-means）方法先從n 個數(shù)據(jù)對象任意選擇k 個對象作為初始聚類中心，然后計算每個所獲新聚類的聚類中心，進(jìn)行多次K均值聚類分區(qū)，最后直到每個聚類不再發(fā)生變化為止，以找出結(jié)果中的任何關(guān)聯(lián)。然而，已有文獻(xiàn)尚未意識到數(shù)據(jù)分布對K 均值算法的影響，并未理解算法與數(shù)據(jù)具有很強(qiáng)的耦合關(guān)系。文獻(xiàn)［4］提出了一種使用共同關(guān)聯(lián)樣本矩陣映射相關(guān)聯(lián)的方法，通過在最終分區(qū)的關(guān)聯(lián)矩陣上應(yīng)用基于最小生成樹（Minimum Spanning Tree，MST）的聚類，對任意形狀的聚類進(jìn)行擴(kuò)展。Fred 等［5］利用相似矩陣上的單鏈路和平均鏈路方法對EAC（Evidence Accumulation Clustering）的計算缺陷進(jìn)行分類。和一般的集成聚類不同，EAC 并不直接組合不同的劃分，而是由這些不同的劃分得到一個鄰近度矩陣。之后便可在這個鄰近度矩陣上運(yùn)用層次聚類中的單連接算法得到最終的劃分，即從多個分區(qū)中獲得的公共信息，進(jìn)行最終聚類。

聚類融合結(jié)合了多種數(shù)據(jù)集群技術(shù)，可以生成初始標(biāo)簽并形成最終統(tǒng)一的群聚解決方案。據(jù)了解，在早期的劃分步驟中，在構(gòu)造和積累知識時會丟失一些有價值的信息，如關(guān)聯(lián)矩陣這樣的中間表征特征缺少一些參與聚類技術(shù)的數(shù)據(jù)條目。文獻(xiàn)［6］研究了丟失信息對融合聚類結(jié)果的影響，并提出了一種通過聚集間的相似性鏈接方法，通過揭示集群之間的相似性來猜測未知條目。最后，利用圖分割技術(shù)得到最終的聚類結(jié)果。投影聚類集合結(jié)合了輸入數(shù)據(jù)子空間聚類和集合聚類本身，利用集合聚類的知識對數(shù)據(jù)子空間進(jìn)行優(yōu)化。文獻(xiàn)［7］提出了自適應(yīng)集成聚類，并設(shè)計了一種輸入數(shù)據(jù)子采樣的自適應(yīng)集成策略。子樣本利用了以往的聚類結(jié)果，并強(qiáng)調(diào)在共識過程中存在不良?xì)v史的樣本。聚類可以利用分類技術(shù)，通過比較基本聚類方法的比例結(jié)果來達(dá)成共識。

多視圖聚類的靈感來自多視角學(xué)習(xí)的概念。多視圖聚類通過對多維數(shù)據(jù)進(jìn)行預(yù)處理和對處理后的數(shù)據(jù)進(jìn)行聚類投影、分類解決聚類時所涉及的技術(shù)［8］。其中一個技術(shù)是描述無監(jiān)督學(xué)習(xí)問題的共正則化，文獻(xiàn)［9］提出了一個光譜聚類目標(biāo)函數(shù)，該函數(shù)隱式地將來自多個數(shù)據(jù)視圖的圖結(jié)合起來，以獲得更好的聚類。多視圖聚類的另一個技術(shù)是使用標(biāo)準(zhǔn)化來解決共識的非負(fù)矩陣分解（Non-negative Matrix Factorization，NMF）。它從多個視圖中學(xué)習(xí)到的集群結(jié)構(gòu)的表示應(yīng)該規(guī)范化，以達(dá)成共識。類似的想法將多流形正則化納入NMF，從而保留了數(shù)據(jù)空間的局部幾何結(jié)構(gòu)。

共識聚類有助于確定最佳的聚類集。文獻(xiàn)［10］提出了一種在分布式環(huán)境下實(shí)現(xiàn)冪迭代聚類的方法。利用某種相似性度量方法，將原始數(shù)據(jù)轉(zhuǎn)換成一個可以視為圖的親和矩陣。通過頂點(diǎn)切割，把行歸一化后的親和矩陣切分成若干個小圖，圖的每一個劃分子圖對應(yīng)一個類簇。通過從多個聚類算法形成共識矩陣來猜測聚類的數(shù)量，根據(jù)關(guān)聯(lián)圖的近似非耦合結(jié)構(gòu)受益的有效性，確定最佳聚類集。

上下文中最新想法是將不同數(shù)據(jù)分區(qū)視圖結(jié)果與來自不同集合技術(shù)的相似矩陣結(jié)合起來，為共識決策計算出最終的相似矩陣［11］。計算機(jī)矩陣的相似性度量方法有:基于聚類的相似性矩陣、相似性矩陣和成對相異性矩陣。相似矩陣中分配的權(quán)重用于聚集。共識聚類的基本原理是通過幾種策略得出的:使用具有相似參數(shù)的不同聚類技術(shù)、使用具有不同聚類參數(shù)的單一策略或兩者的組合。另一個想法是對訓(xùn)練數(shù)據(jù)進(jìn)行分區(qū)，并使用不同聚類方法對數(shù)據(jù)進(jìn)行分區(qū)，以獲得基本結(jié)果。聚類的結(jié)果來自于早期的基礎(chǔ)階段。共識可以使用投票公式分配新的標(biāo)簽［12］。著名的共識策略有:層次凝聚-聚類共識、最遠(yuǎn)共識、基于聚類的共識、期望最大化共識、迭代投票共識和基于片段的聚類共識［13］。

近年來，共識聚類在文檔聚類中得到了廣泛的應(yīng)用和有效 的 使 用。Topchy 于2003 年 使 用QMI（Quadratic Mutual Information）作為效用函數(shù)，提出利用K 均值算法來解決共識聚類的問題，即將共識聚類問題在QMI 下轉(zhuǎn)化成經(jīng)典的K 均值優(yōu)化問題［14］，如何種效用函數(shù)的效果比較優(yōu)越、如何處理樣本不一致問題以及其收斂性等，都亟待解決。共識聚類相比單一聚類算法的優(yōu)勢體現(xiàn)在魯棒性、新穎性、穩(wěn)定性、并行性和擴(kuò)展性等［15］。然而，共識聚類是一個具有挑戰(zhàn)性的工作，其主要難點(diǎn)在于從不同聚類結(jié)果中求出一個共識劃分，使得共識效用函數(shù)最大。學(xué)者從不同角度解釋基礎(chǔ)聚類器產(chǎn)生聚類結(jié)果的共性，從而找出共識聚類結(jié)果。

本文提出一種基于共識和分類的文檔聚類（Document Clustering by Consensus and Classification，DCCC）策略，實(shí)現(xiàn)共識和分類文檔自適應(yīng)集成聚類。利用基于關(guān)鍵詞DIM（Discrimination Information Method）的不同文檔聚類算法的優(yōu)勢，揭示它們之間的潛在關(guān)系。從有關(guān)文獻(xiàn)中可明顯地看出，每個DIM 都利用來自不同潛在客戶的數(shù)據(jù)，因此會發(fā)現(xiàn)不同的聚類解決方案［16］。然而，簇重疊最有可能出現(xiàn)在每個解決方案中，并且有一些文檔與其聚類解決方案相符。簇解決方案可以將這些文檔保持在相似的簇中。這些帶有簇標(biāo)簽的融合文檔有助于訓(xùn)練共識分類器［17］。分類器使用從早期聚類解決方案中發(fā)現(xiàn)的知識來預(yù)測與初始聚集簇標(biāo)簽信息不一致的文檔，從而確定最終的聚類解決方案。聚類利用分類技術(shù)是本文研究的主要焦點(diǎn)。

2 文檔聚類識別信息方法

近年來，利用文檔的K 簇識別信息的文檔聚類算法的高性能已得到有效的證明。這些聚類算法迭代地將文檔投影到K 維識別信息空間上，并將有最大值的簇分配給一個文檔。在每次迭代中，關(guān)鍵詞識別信息定義了識別信息空間，其中關(guān)鍵詞識別信息是根據(jù)上一次迭代中生成的標(biāo)記文檔集進(jìn)行估計的。該聚類方法作為優(yōu)化問題被提出，目標(biāo)函數(shù)可以使用各種可用的統(tǒng)計和信息理論度量［18］。人們經(jīng)常使用以下方法發(fā)布目標(biāo)函數(shù)的結(jié)果:相對危險度（Relative Risk，RR）、識別信息方法（Method of Discrimination Information，MDI）、域相關(guān)性（Domain Relevance，DR）和 域 識 別（Domain Consensus，DC）。

使用發(fā)布函數(shù)方法可能帶來另一個風(fēng)險，即在相同數(shù)據(jù)的不同解決方案之間如何選擇最佳方案。雖然不同的聚類解決方案可選擇不同的方法來計算最終簇數(shù)，但可計算的簇數(shù)之間存在顯著的相似性。因此，對來自不同聚類方法的同一簇中的文檔須有統(tǒng)一的簇標(biāo)簽。文本分類器使用這些同義文檔的簇標(biāo)簽進(jìn)行訓(xùn)練，隨后該分類器再用于預(yù)測不同文檔的簇標(biāo)簽，使用共識和分類改善文檔聚類的工作流程如圖1 所示，圖2是DCCC過程總結(jié)的可視化。

圖1 本文方法的簡單工作流程Fig.1 Simple flowchart of the method proposed in this paper

圖2 DCCC過程總結(jié)的可視化Fig.2 Visualization of DCCC process summary

2.1 使用CDIM初始聚類

本文選擇CDIM 作為數(shù)據(jù)集生成初始聚類的解決方法。CDIM是一種迭代分區(qū)文檔聚類方法，在從M維輸入空間轉(zhuǎn)換的K 維識別信息空間中找到K 組文檔，其中M 表示詞匯表中不同關(guān)鍵詞的總數(shù)。通過有效的文擋投影和分配可實(shí)現(xiàn)這一目標(biāo)，最大限度地提高文檔的識別數(shù)總和。CDIM-RR 和CDIM-MDI 是CDIM 的兩種變體，用來尋找初始聚集ERR和EMDI。第一類使用RR，第二類使用MDI、CDIM-RR 和CDIMMDI看作是CDIM識別項(xiàng)加權(quán)策略。

2.1.1 CDIM-RR

用CDIM-RR 時，關(guān)鍵詞xj在簇Ck中的RR 高于剩余簇-Ck的。簇Ck中的關(guān)鍵詞xj的識別信息（如wjk）和剩余簇-Ck中的關(guān)鍵詞xj的識別信息（如-wjk）由式（1）～（2）給出。

其中:p(xj|Ck)是簇Ck中的關(guān)鍵詞xj的條件概率。關(guān)鍵詞識別信息要么為0（無識別信息），要么大于1，較大值表示有較強(qiáng)的識別能力。

2.1.2 CDIM-MDI

用CDIM-MDI 時，MDI 用于計算關(guān)鍵詞的識別信息，量化關(guān)鍵詞間的語義相關(guān)性。類別1 和類別2 分別定義為:ifdI1和ifdI2。在文檔聚類中，ifdI1和ifdI2分別對應(yīng)于簇Ck和簇-Ck。方法定義如下:

其中:λ1和λ2分別是Ck和的已有概率。關(guān)鍵詞xj的識別具有以下不平等特征:

如果滿足不等式（5），則關(guān)鍵詞xj支持ifdI1超過ifdI2；當(dāng)滿足不等式（6），則關(guān)鍵詞xj支持ifdI2超過ifdI1。根據(jù)不等式（5）～（6），CDIM的wjk和-wjk的識別項(xiàng)權(quán)重如下:

2.2 尋找共識

在分別使用CDIM-RR 和CDIM-MDI 獲得兩個簇集ERR和EMDI后，下一步就是將這兩簇集結(jié)合起來，尋找相符的文檔。由于無監(jiān)督特性的原因，導(dǎo)致CDIM-RR 和CDIM-MDI 分配給文檔的簇標(biāo)簽不同。為了解決這一問題，需將每個簇Ci∈ERR和Cj∈EMDI進(jìn)行比較，將ERR和EMDI中最相似的兩個聚類分配相同的簇標(biāo)簽，依次共產(chǎn)生K 個簇標(biāo)簽，并使用Jaccard 指數(shù)計算兩簇集的相似度。Jaccard 相似度為:Ci和Cj交集的大小與并集大小的比值，即

相似度值越大說明兩聚類集共識文檔數(shù)越多。當(dāng)Ci和Cj都為空時，J(Ci，Cj)= 1。

2.3 使用分類器進(jìn)行改進(jìn)

位于CDIM-RR和CDIM-MDI同一簇中的文檔很可能正好聚集在一起，將這些文檔與它們的簇標(biāo)簽信息一起生成文本分類器的訓(xùn)練集。

其中:Xi是數(shù)據(jù)集X中第i個文檔。

對于沒有在CDIM-RR和CDIM-MDI同一簇中的剩余文檔則生成文本分類器的測試集。

本文選擇DTWC 文本分類器。DTWC 是一種基于識別式加權(quán)的線性識別方法，可用于文本分類，而且實(shí)踐表明具有良好的分類結(jié)果［19］。盡管可以使用任何文本分類器，但除了其效率和良好結(jié)果外，選擇DTWC 的另一個原因是該方法的識別特性與初始聚類方法CDIM 相匹配。是簇標(biāo)簽的最終列表，融合了訓(xùn)練集中文檔的共識簇標(biāo)簽和測試集中被DTWC預(yù)測的文檔簇標(biāo)簽。算法1為本文算法的流程。

算法1 DCCC。

輸出 X（關(guān)鍵詞-文檔數(shù)據(jù)集），K（簇編號）。

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

3.1 數(shù)據(jù)集

在8個網(wǎng)絡(luò)數(shù)據(jù)集上評估了本文的聚類方法DCCC。表1給出了這些網(wǎng)絡(luò)數(shù)據(jù)集的關(guān)鍵特征。數(shù)據(jù)集1、3 到8 進(jìn)行預(yù)處理，同時對數(shù)據(jù)集2進(jìn)行了停用詞的刪除和封堵。

表1 數(shù)據(jù)集及其特征Tab.1 Datasets and their characteristics

數(shù)據(jù)集pu 是從Internet Content Filtering Group 的網(wǎng)站獲得，包含標(biāo)記為垃圾郵件或非垃圾郵件的特定用戶收到的電子郵件；數(shù)據(jù)集movie 來自Internet 電影數(shù)據(jù)庫（Internet Movie DataBase，IMDB）的電影評論，每個電影文檔都有正面或負(fù)面評論；hitech、tr31、re0 和wap 數(shù)據(jù)集來自明尼蘇達(dá)大學(xué)的Karypis實(shí)驗(yàn)室；數(shù)據(jù)集hitech 來源于圣何塞水星報，這些文章作為TREC（Text Retrieval Conference）系列的一部分發(fā)布；數(shù)據(jù)集tr31 來自TREC-6，此數(shù)據(jù)集中的查詢類別與其最相關(guān)的文檔對應(yīng)；數(shù)據(jù)集re0 來自Reuters-21578 文本分類測試集分發(fā)版1.0；數(shù)據(jù)集wap 是從WebACE 項(xiàng)目中獲得的，每個文檔對應(yīng)于Yahoo！主題層結(jié)構(gòu)中列出的網(wǎng)頁；數(shù)據(jù)集cora是一個指標(biāo)矩陣，表示文檔中某個關(guān)鍵詞的存在或不存在；citeseer是出現(xiàn)在網(wǎng)站上的文章的集合，這些文章的視圖與關(guān)鍵詞-文檔矩陣相對應(yīng)。

3.2 聚類驗(yàn)證方法

圖3 計算一個文檔的BP和BR示例Fig.3 Example of calculating BP and BR for a Document

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

通過CDIM 進(jìn)行聚類可獲得高質(zhì)量結(jié)果，但需在方法RR和MDI之間進(jìn)行選擇。

盡管CDIM-RR 和CDIM-MDI 的性能不同沒有統(tǒng)計學(xué)意義，但從結(jié)果中可以看到一個簡單的模式，如圖4 所示。對于較小的種類數(shù)，RR 較強(qiáng)；而對于較大的種類數(shù)，MDI較強(qiáng)。這種模式促進(jìn)了共識聚類方法的融合發(fā)展。

圖4 不同數(shù)據(jù)集的RR和MDI的比較Fig.4 Comparison of RR and MDI of different datasets

表2 是本文提出的DCCC 方法與CDIM-RR、CDIM-MDI 和HierLink方法進(jìn)行的比較。

表2 DCCC方法與CDIM-RR、CDIM-MDI和HierLink方法的比較Tab.2 Comparison of DCCC with CDIM-RR，CDIM-MDI and HierLink methods

表2 中最后一列顯示的是DCCC 方法比單個聚類方法的平均值提高的百分比。在HierLink 方法中，首先，通過基于相同的簇成員計算所有對象的成對相似度矩陣來實(shí)現(xiàn)基礎(chǔ)的共識聚類。然后，利用“區(qū)”鏈接進(jìn)行分層聚類，最終達(dá)到聚類的目的。利用CDIM-RR和CDIM-MDI的兩種初始聚類方法計算相似矩陣。與CDIM-RR、CDIM-MDI 和HierLink 相比，DCCC的結(jié)果都有顯著改善。

表3 是DCCC 方法與其他共識聚類方法［8］的比較，表中顯示的是精度值，本文提出的DCCC方法明顯優(yōu)于其他方法。

表3 DCCC與其他共識聚類方法的精度對比Tab.3 Comparison accuracy of DCCC and other consensus clustering methods

4 結(jié)語

本文提出了一種文檔聚類的共識構(gòu)建方法。在不同的數(shù)據(jù)聚類工具生成的簇解決方法中，DCCC 使用分類工具進(jìn)行共識度量。本文選擇CDIM 尋找初始簇:CDIM 使用識別信息最大化進(jìn)行文檔聚類。起始階段，使用不同聚類的解決方法尋找共識文檔，即哪些文檔應(yīng)該屬于最相似的簇。同時，識別文本分類器DTWC 接受共識文檔的培訓(xùn)。而后，DTWC 文本分類器預(yù)報與初始聚集簇標(biāo)簽信息不一致的文檔。為了獲得不同的初始視圖，本文采用了RR 和MDI 兩種識別方法。RR和MDI 具有不同的優(yōu)勢，在DCCC 中進(jìn)行融合可達(dá)到提升性能的效果。利用8 種標(biāo)準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集驗(yàn)證了本文方法的有效性。

本文方法是一種通用的共識方法，可應(yīng)用于文檔聚類之外的其他領(lǐng)域，并可測試不同的初始聚類方法和不同的分類方法。目前，只有兩種方法用于初始聚類。在未來，本文的目標(biāo)是測試其他識別方法的融合、聚類和分類。