基于共識和分類改善文檔聚類的識別信息方法

王留洋，俞揚信，陳伯倫，章 慧

（淮陰工學院計算機與軟件工程學院，江蘇淮安223003）

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

0 引言

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

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

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

1 相關研究

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

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

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

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

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

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

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

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

2 文檔聚類識別信息方法

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

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

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

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

2.1 使用CDIM初始聚類

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

2.1.1 CDIM-RR

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

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

2.1.2 CDIM-MDI

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

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

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

2.2 尋找共識

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

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

2.3 使用分類器進行改進

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

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

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

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

算法1 DCCC。

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

3 實驗與結果分析

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

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

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

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

3.2 聚類驗證方法

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

3.3 實驗結果與分析

通過CDIM 進行聚類可獲得高質量結果，但需在方法RR和MDI之間進行選擇。

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

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

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

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

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

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

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

4 結語

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

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