基于信息融合的網(wǎng)頁(yè)文本聚類距離選擇方法

張少宏，李繼巧，羅嘉怡，謝冬青，王 婧

（1.廣州大學(xué)計(jì)算機(jī)科學(xué)與教育軟件學(xué)院，廣東 廣州 510006；2.廣州圖書館，廣東 廣州 510623）

基于信息融合的網(wǎng)頁(yè)文本聚類距離選擇方法

張少宏1，李繼巧1，羅嘉怡1，謝冬青1，王 婧2

（1.廣州大學(xué)計(jì)算機(jī)科學(xué)與教育軟件學(xué)院，廣東 廣州 510006；2.廣州圖書館，廣東 廣州 510623）

在當(dāng)前信息化的年代里，文本數(shù)據(jù)在高速的增長(zhǎng)，人們獲取有用的信息猶如大海撈針.文本聚類作為文本挖掘的基礎(chǔ)技術(shù)，發(fā)揮了很重要的作用.由于缺乏預(yù)先定義的類和類標(biāo)號(hào)的訓(xùn)練實(shí)例，如何選擇合適的數(shù)據(jù)相似度是文本聚類的關(guān)鍵問(wèn)題.文章為此提出一種新的衡量文本相似度的方法Adaptive Metric Selection（AMS）.文章通過(guò)抓取網(wǎng)頁(yè)內(nèi)容，為聚類提供數(shù)據(jù)來(lái)源，分詞和向量化是必要的轉(zhuǎn)化，利用特征提取的方法獲取特征項(xiàng)，并用Isomap進(jìn)行降維，最后利用自適應(yīng)選擇方法AMS對(duì)數(shù)據(jù)進(jìn)行相似度衡量再進(jìn)行聚類分析.實(shí)驗(yàn)結(jié)果表明，AMS明顯優(yōu)于從多種相似度獨(dú)立進(jìn)行聚類的平均結(jié)果.

數(shù)據(jù)挖掘；特征提??；聚類融合

本文針對(duì)聚類知識(shí)提取和聚類評(píng)價(jià)的若干問(wèn)題進(jìn)行研究，討論如何在盡可能包含聚類先驗(yàn)知識(shí)的情況下抽象出聚類知識(shí)，并從知識(shí)中尋找盡可能多的聚類結(jié)構(gòu)信息，用一種自適應(yīng)度量方法

在無(wú)監(jiān)督學(xué)習(xí)中，由于缺乏已知類別的樣本數(shù)據(jù)，數(shù)據(jù)的相似度衡量方法歷來(lái)備受重視并得到深入的研究.在監(jiān)督學(xué)習(xí)中，學(xué)習(xí)的目標(biāo)是學(xué)習(xí)者從輸入到輸出的映射關(guān)系，其中輸出的正確值已經(jīng)由指導(dǎo)者提供.然而，在無(wú)監(jiān)督學(xué)習(xí)中，卻沒(méi)有這樣的指導(dǎo)者.另一方面，在無(wú)監(jiān)督聚類應(yīng)用中基于集成的技術(shù)已經(jīng)吸引許多計(jì)算機(jī)領(lǐng)域的精英團(tuán)體的高度興趣［1-18］.

具體而言，無(wú)監(jiān)督集成框架，通常被稱為聚類融合或一致聚類［1，4］，能根據(jù)多個(gè)不同的獨(dú)立聚類結(jié)果生成一個(gè)一致的結(jié)果.獨(dú)立聚類結(jié)果能通過(guò)不同的透視方法，例如，通過(guò)不同的數(shù)據(jù)樣本子集［3-4］，不同的數(shù)據(jù)特征子集［2-3］或不同的聚類算法［1，19］得到.一旦獨(dú)立分區(qū)創(chuàng)建，可以用于互協(xié)矩陣的方法［1，3，5］或者以圖分割方法［1-2］推導(dǎo)出一致聚類結(jié)果.在第一類聚類融合的方法，重組矩陣是根據(jù)各個(gè)獨(dú)立的分區(qū)，這些獨(dú)立分區(qū)的第（i，J）個(gè)矩陣標(biāo)志項(xiàng)中，第i個(gè)數(shù)據(jù)點(diǎn)和第J個(gè)數(shù)據(jù)點(diǎn)是否屬于分區(qū)內(nèi)的同一集合來(lái)生成的.然后，把所有的重組矩陣總結(jié)起來(lái)得出一個(gè)一致矩陣.這樣一來(lái)這個(gè)矩陣能充當(dāng)一個(gè)成對(duì)的相似矩陣，一個(gè)一致的結(jié)果能用恰當(dāng)?shù)木垲愃惴ɑ驁D像分割算法被提取.特別地，每一個(gè)一致矩陣的項(xiàng)都是所有重組矩陣的相應(yīng)的項(xiàng)的均值.這樣一個(gè)一致矩陣能被看對(duì)比其他相似度度量方法獨(dú)立進(jìn)行聚類的平均結(jié)果，進(jìn)而評(píng)價(jià)聚類的好壞.

1 數(shù)據(jù)預(yù)處理

1.1 網(wǎng)頁(yè)抓取

筆者使用網(wǎng)絡(luò)爬蟲技術(shù)抓取5種類型的網(wǎng)頁(yè)，分別是教育類（edu）、財(cái)經(jīng)類（finance）、健康類（health）、體育類（sports）和軍事類（war），每個(gè)類別300篇文章，存到.txt文件中.因?yàn)橛?jì)算機(jī)并不具備人腦的理解能力.在對(duì)文本進(jìn)行預(yù)處理時(shí)，需要對(duì)文本內(nèi)容進(jìn)行分詞處理，去除停用詞，將其表示成計(jì)算機(jī)能夠理解和計(jì)算的模型.

1.2 分詞處理

與英文不同，在中文文本中，詞與詞之間沒(méi)有用空格來(lái)分隔，界限不明顯，導(dǎo)致計(jì)算機(jī)的處理存在較大難度.因此，需要將中文句子拆分為一個(gè)個(gè)單獨(dú)的詞.

筆者使用ICTCLAS分詞系統(tǒng)（又名NLPIR漢語(yǔ)分詞系統(tǒng)）對(duì)文本進(jìn)行處理.其基本思想是：對(duì)句子進(jìn)行原子切分，然后進(jìn)行較為粗糙的N-最短路徑切分，找到前N個(gè)較為符合要求的切分結(jié)果，生成二元分詞表，最后得到分詞結(jié)果［20］.

分詞前后的對(duì)照見(jiàn)圖1和圖2.

圖1 分詞前的例子Fig.1 Example before the split

1.3 去除停用詞

停用詞是指詞頻過(guò)高且沒(méi)有實(shí)質(zhì)意義的詞，或詞頻很低且不能代表文本主題的詞［21］.一般地，過(guò)濾停用詞可以構(gòu)造停用詞表，通過(guò)跟讀入的文本分詞進(jìn)行對(duì)比，若該詞在停用詞表出現(xiàn)就去除.而且，為了后續(xù)程序容易處理，詞與詞之間采用空行來(lái)分隔.

1.4 計(jì)算TF-IDF

傳統(tǒng)的數(shù)據(jù)均以結(jié)構(gòu)化的形式而被處理，因此，在滿足復(fù)雜性能夠接受的情況下，需要合理的標(biāo)示文本.

TF-IDF是在1988年由SALTON提出的實(shí)現(xiàn)單詞權(quán)重最為有效的方法.其中，TF稱為詞頻；IDF是逆文檔頻率，其大小與一個(gè)詞的常見(jiàn)程度成反比：如果一個(gè)詞越常見(jiàn)，則權(quán)重越?。?2］.將這2個(gè)值相乘，就得到了一個(gè)詞的TF-IDF值.

（1）計(jì)算詞頻（TF）

（2）計(jì)算逆文檔頻率（IDF）

逆文檔頻率（IDF）＝

（3）計(jì)算TF-IDF

IF-IDF＝詞頻（IF）×逆文檔頻率（IDF）.

1.5 特征選擇方法

對(duì)特征集中的所有特征計(jì)算評(píng)分值，得到一個(gè)評(píng)估分值（又稱權(quán)值），對(duì)其從大到小排序，提取預(yù)定數(shù)目的最優(yōu)特征作為提取結(jié)果的特征子集，稱為特征提取［23］.在文本聚類中幾種常見(jiàn)的文本監(jiān)督特征算法包括MI、IG、CHI和WLLR.

假設(shè)整個(gè)文檔集中有N篇文檔，其中M篇是教育類的，以下有4個(gè)觀察值可以使用，即類別和文檔數(shù)的4種組合（見(jiàn)表1）.

表1 類別和文檔的組合Table 1 The combination of categories and document

1.5.1 互信息法MI（Mutual Information）

互信息法用于衡量特征詞與文檔類別直接的信息量.它是根據(jù)特征詞條t與類別C之間的相關(guān)程度來(lái)度量特征詞條與類別的相關(guān)度的，在某個(gè)特定的類別中出現(xiàn)的頻率高，而在其他的類別中出現(xiàn)的頻率較低的詞條與該類別的互信息值較大［24］.

計(jì)算公式：

它不僅能夠反映2個(gè)變量之間的線性相關(guān)性，而且能夠反映變量之間的非線性相關(guān)性［24］.

1.5.2 信息增益法IG（Information Gain）

在信息增益中，衡量標(biāo)準(zhǔn)是看特征能夠?yàn)榉诸愊到y(tǒng)帶來(lái)多少信息，帶來(lái)的信息越多，特征就越重要［25］.假如有一個(gè)特征t，整個(gè)系統(tǒng)中某些文本有t和整個(gè)系統(tǒng)中沒(méi)有t時(shí)的信息量是不同的，而前后的相差部分就是特征t的信息量，即信息增益.

它表示的是包含所有特征時(shí)系統(tǒng)的信息量，也叫熵.計(jì)算公式：

其中，N1表示正類文檔數(shù)，數(shù)值等于A+C，N2表示負(fù)類文檔數(shù)，數(shù)值等于B+D.N1+N2表示總文檔數(shù)N.

系統(tǒng)中不包含t的信息量，叫做條件熵.

歸納起來(lái)，每個(gè)詞的信息增益計(jì)算為

信息增益的缺點(diǎn)在于，它只考慮到特征對(duì)系統(tǒng)的貢獻(xiàn)，而沒(méi)有關(guān)注到具體的類別［26］.雖然能夠獲得整個(gè)文檔集中的特征詞，但是不能區(qū)分不同類別間的特征詞的權(quán)重.

1.5.3 卡方檢驗(yàn)CHI（Chi-square）

卡方檢驗(yàn)的主要思想：根據(jù)實(shí)際值與理論值的偏差來(lái)確定理論是否正確［27］.偏離程度決定卡方值的大小，卡方值越大，越不符合，偏差越小，卡方值就越小，越趨于符合，若量值完全相等時(shí)，卡方值就為0，表明理論值完全符合.計(jì)算公式：

而不足在于“低頻詞缺陷”，即不管在文檔中出現(xiàn)的次數(shù)，而單純考慮是否出現(xiàn).

1.5.4 加權(quán)對(duì)數(shù)概率比WLLR（Weighted Log Likelihood Ration）WLLR特征選擇方法的定義如下：

其中，p（t|C）表示文檔中出現(xiàn)特征詞t時(shí)屬于類C的概率，p（t|Cˉ）表示特征詞t不屬于C類的概率.

計(jì)算公式：

總之，這些特征選擇方法各有優(yōu)缺.一般而言，CHI、IG的性能明顯優(yōu)于MI；而CHI、IG 2者之間的性能大體相當(dāng)，都能夠過(guò)濾掉80%以上的特征項(xiàng).

2 基于一致近似性的聚類自適應(yīng)評(píng)價(jià)指標(biāo)選擇

2.1 傳統(tǒng)的聚類分析方法

聚類就是給出一堆原始數(shù)據(jù)，根據(jù)數(shù)據(jù)對(duì)象之間的相似度將數(shù)據(jù)分成相應(yīng)的類或簇，類或簇是數(shù)據(jù)對(duì)象的集合.同一個(gè)類或簇中的對(duì)象應(yīng)該具有很高的相似度，而不同簇中的對(duì)象則高度相異［28］.

傳統(tǒng)的聚類方法主要分成5大類：劃分方法、層次方法、基于密度的方法、基于網(wǎng)格的方法和基于模型的方法［29］.

劃分方法中，最著名和最常用的劃分方法是k均值（又叫k-means算法），k中心點(diǎn)和它們的變種［30］.

層次聚類方法將數(shù)據(jù)對(duì)象組成一棵聚類樹(shù)，將這棵樹(shù)進(jìn)行層次的分解.根據(jù)層次分解是以自底向上（合并）還是自頂向下（分裂）方式，層次聚類方法可以進(jìn)一步分為凝聚的和分裂的.一般分為2種類型：凝聚層次聚類和分裂層次聚類［30］.

基于密度的聚類方法以數(shù)據(jù)集在空間分布上的稠密程度為依據(jù)進(jìn)行聚類，無(wú)需預(yù)先設(shè)定簇的數(shù)量，因此，特別適合于對(duì)未知內(nèi)容的數(shù)據(jù)集進(jìn)行聚類.密度聚類方法可以發(fā)現(xiàn)任意形狀的簇，克服了那些基于對(duì)象之間距離的聚類算法只能發(fā)現(xiàn)球狀簇的缺點(diǎn)，并且可以過(guò)濾孤立點(diǎn)數(shù)據(jù)或離群點(diǎn)這些“噪聲”［30］.

2.2 文本相似度衡量

與分類不同的是，聚類是根據(jù)一定的相似性定義來(lái)劃分?jǐn)?shù)據(jù)的，因此，需要考慮到聚類時(shí)所采用的相似性度量.

本文表示文本的形式是基于向量空間模型的，即一個(gè)向量代表一個(gè)文檔，特征詞的權(quán)重作為向量的元素.將文檔表示成向量空間模型的形式，有利于對(duì)文本進(jìn)行相似度的衡量.

首先，本文的對(duì)象是一篇篇.txt文檔，也就是比較1 500*1 500個(gè)對(duì)象的相似度.相似度的衡量通常有2種度量方式：距離度量和相似度度量.

假設(shè)要比較數(shù)據(jù)點(diǎn)集x和y的差異，它們都包含了D個(gè)維的特征，即

距離度量用于衡量個(gè)體在空間上存在的距離，越遠(yuǎn)說(shuō)明個(gè)體間的差異越大.常用方法是歐幾里得距離和曼哈頓距離.

（1）歐幾里得距離.它衡量的是多維空間中各個(gè)點(diǎn)之間的絕對(duì)距離［31］，公式為

（2）曼哈頓距離.是將多個(gè)維度上的距離進(jìn)行求和后的結(jié)果［31］.

相似度度量，不同于距離度量，它的值越小代表個(gè)體間差異越大，越不相似［32］.常用的是向量空間余弦相似度和相關(guān)距離.

（3）向量空間余弦相似度.它利用向量空間中2個(gè)向量夾角的余弦值作為衡量2個(gè)個(gè)體間的差異大小，相比于距離度量，它更加注重2個(gè)向量在方向上的差異，而不是在距離或長(zhǎng)度上［33］.

（4）相關(guān)距離.相關(guān)系數(shù)ρxy是衡量x與y相關(guān)程度的一種方法.相關(guān)系數(shù)的絕對(duì)值越大，表明x與y相關(guān)度越高.相關(guān)距離的定義則為

2.3 自適應(yīng)選擇方法文本相似度衡量

筆者利用了一種新的相似度衡量方法，叫做Adaptive Metric Selection（AMS），來(lái)比較文本的相似度.它是基于劃分方法k均值算法的基礎(chǔ)上的，采用了一致密切關(guān)系來(lái)衡量聚類算法的自適應(yīng)指標(biāo)選擇問(wèn)題.

k均值算法的基本步驟：給出n個(gè)數(shù)據(jù)對(duì)象，從中任意選取k個(gè)對(duì)象，每個(gè)對(duì)象都作為一個(gè)簇的初始聚類中心.對(duì)剩余的n-k個(gè)對(duì)象，分配到離它最近（最相似）的簇中.然后重新計(jì)算每個(gè)（有變化）簇的均值（中心對(duì)象），更新聚類中心.這個(gè)過(guò)程不斷重復(fù)，直到準(zhǔn)則函數(shù)收斂或者到達(dá)某個(gè)終止條件［34］.

以下給出k均值過(guò)程的概述：

算法：k均值

輸入：①k：簇的數(shù)目；②D：包含n個(gè)對(duì)象的數(shù)據(jù)集

輸出：k個(gè)簇的集合方法：①?gòu)腄中任意選擇k個(gè)對(duì)象作為初始

簇中心；

②repeat根據(jù)簇中對(duì)象的均值，將每個(gè)對(duì)象（再）指派到最相似的簇；

更新簇均值，計(jì)算每個(gè)簇中對(duì)象的均值；

③until簇中心不再發(fā)生變化對(duì)于各種不同的數(shù)據(jù)集都使用統(tǒng)一的度量指標(biāo)是不太合理的.因此在本文中使用一種稱為自適應(yīng)指標(biāo)的聚類融合方法AMS.

給出一個(gè)擁有N個(gè)數(shù)據(jù)點(diǎn)｛x1，x2，…，xN｝的數(shù)據(jù)集X，把數(shù)據(jù)集X分成K個(gè)互不相交的簇｛A1，A2，…，Ak｝，一個(gè)N×N的Co-association Matrix（M），即互協(xié)矩陣，它的構(gòu)造公式如下所示：

利用多個(gè)已經(jīng)被計(jì)算出來(lái)的N×N的互協(xié)矩陣M，求出它們的均值，構(gòu)造出相應(yīng)的Consensus Matrix（M），即一致矩陣.

圖3 一致矩陣的構(gòu)造流程圖Fig.3 The flow chart of the structure of the consistent matrix

利用降維后的數(shù)據(jù)，經(jīng)過(guò)k均值算法得到5個(gè)簇，使得1 500篇文章都被分到5個(gè)類別中的任意一個(gè).利用這些聚類類別，通過(guò)轉(zhuǎn)化把向量矢量轉(zhuǎn)變?yōu)榫仃嚨男问剑玫交f(xié)矩陣Mv，最后求出互協(xié)矩陣的均值融合成一個(gè)一致矩陣這個(gè)Μ在整個(gè)實(shí)驗(yàn)中起到一個(gè)參考矩陣的作用.

先算出4個(gè)待用參數(shù)a，b，c，d.

然后利用4個(gè)參數(shù)計(jì)算出SS.

自適應(yīng)度量選擇AMS權(quán)值是由以下所有實(shí)驗(yàn)各指標(biāo)中的一致矩陣和互協(xié)矩陣Mv之間計(jì)算出一致性的.如下所示：

根據(jù)自適應(yīng)度量選擇權(quán)值從高到低排序出一個(gè)指標(biāo)列表.用公式（3）選出AMS的最好結(jié)果并保存下來(lái).

式中表示A（t*）是SS函數(shù)中，會(huì)產(chǎn)生最大輸出的那個(gè)參數(shù)t.比如有一個(gè)函數(shù)f（t），t可能的取值范圍是｛0，1，2｝，f（t＝0）＝29，f（t＝1）＝31，f（t＝3）＝2.那么y＝argmax f（t）＝1，也就是t等于1時(shí)，f（t）有最大的值.

3 AMS算法的實(shí)驗(yàn)開(kāi)展

3.1 AMS實(shí)驗(yàn)前期準(zhǔn)備工作

實(shí)驗(yàn)環(huán)境在MyEclipse10，Matlab7.0環(huán)境下進(jìn)行，實(shí)驗(yàn)語(yǔ)料位抓取1 500篇網(wǎng)頁(yè)正文文本.

（1）數(shù)據(jù)集：5個(gè)特征方法分別經(jīng)過(guò)Isomap降維算法降維后，分別得到1 500*20的矩陣.

（3）k均值的評(píng)價(jià)指標(biāo)：4種相似度衡量方法，即①歐幾里得距離；②曼哈頓（或城市塊）距離；③向量空間余弦相似度；④相關(guān)距離.

（4）評(píng)估方法：在聚類中，常用作為聚類效果評(píng)估的2種指標(biāo)：①調(diào)整后的芮氏指標(biāo)Adjusted Rand Index（ARI）；②標(biāo)準(zhǔn)化互信息Normalized Mutual Information（NMI）.

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

3.2.1 文本樣本數(shù)據(jù)在5種不同文本特征衡量方法下的相似度

對(duì)5種文本特征選擇方法畫出對(duì)應(yīng)的1 500 *1 500的相似矩陣（見(jiàn)圖4），以觀察它們的聚類性能.第i行第J列的交叉點(diǎn)表示第i個(gè)網(wǎng)頁(yè)和第J個(gè)網(wǎng)頁(yè)的相似程度，而每個(gè)方格代表一個(gè)類別.比如第1行第4個(gè)方格表示第1類（教育類）和第4類（體育類）的相似度.

圖4 文本樣本數(shù)據(jù)在5種不同文本特征衡量方法下的相似度矩陣Fig.4 The similarity matrix of text sample data in 5 different text features

通常，相同的類別之間應(yīng)該盡可能相似（灰度越深），而不同類別之間則越不相似越好（灰度越淡）.反映在上面幾幅圖中就是，相同類別對(duì)應(yīng)的是大矩陣中向下對(duì)角線的5個(gè)小矩陣；不同的類別對(duì)應(yīng)的是非向下對(duì)角線的其它20個(gè)小矩陣.理想情況是，相同類別下的小矩陣越黑越好，表示類別間文本越相似.然而事實(shí)并沒(méi)有達(dá)到預(yù)期的結(jié)果.圖4中，WLLR中的第4類明顯和所有5個(gè)類的相似度很低（包括自身）.這表明，單一的特征選擇方法還是存在較大的缺陷.

3.2.2 文本樣本數(shù)據(jù)在5種不同文本特征衡量方法下的相似度

筆者使用2個(gè)評(píng)價(jià)指標(biāo)NMI和ARI比較自適應(yīng)選擇度量方法AMS和單獨(dú)使用4種不同相似度衡量方法（歐幾里得距離、曼哈頓距離、向量空間余弦相似度和相關(guān)距離）進(jìn)行聚類后的性能，如圖5所示.圖5中的2個(gè)子圖中，縱坐標(biāo)分別表示對(duì)應(yīng)的2種不同聚類性能衡量標(biāo)準(zhǔn)NMI和ARI.從圖5可見(jiàn)，使用AMS選擇自適應(yīng)的文本相似度衡量后的聚類效果明顯優(yōu)于單獨(dú)使用4種不同的相似度衡量方法.筆者也使用實(shí)驗(yàn)驗(yàn)證參數(shù)選擇對(duì)AMS算法的影響.AMS只依賴一個(gè)參數(shù)，即聚類個(gè)數(shù)T.驗(yàn)證T在不同選擇情況下AMS的性能：T＝40，80，120，160，200.在圖6中比較使用AMS選擇自適應(yīng)的文本相似度衡量方法和單獨(dú)使用4種不同相似度衡量方法的平均結(jié)果的性能.圖6中的2個(gè)子圖中，橫坐標(biāo)表示選擇不同的聚類個(gè)數(shù)T＝40，80，120，160，200，縱坐標(biāo)分別表示對(duì)應(yīng)的2種不同聚類性能衡量標(biāo)準(zhǔn)NMI和ARI.從圖6可見(jiàn)，AMS選擇的自適應(yīng)文本相似度衡量方法在不同T的情況下都優(yōu)于比較對(duì)象.

圖5 AMS和4種相似度衡量方法的平均值在文本相似度衡量方面的差異Fig.5 Performance comparison between AMS and the average of four individual similarity measures

圖6 在不同聚類個(gè)數(shù)T下基于AMS選擇的相似度和單獨(dú)選擇相似度衡量方法的平均值的聚類性能比較Fig.6 Performance comparison between AMS and the average of four individual similarity measures with different numbers of clustering solutions t

結(jié)合圖5和圖6發(fā)現(xiàn)，不論是整體結(jié)果分析，還是細(xì)分T，自適應(yīng)選擇度量方法AMS的聚類效果都超過(guò)了4種相似度衡量方法的平均值.這也從側(cè)面反映了使用不同的評(píng)估方法對(duì)判定結(jié)果的重要性.

筆者提出的方法是把多個(gè)聚類解決方案作為參考信息并且使用SS方法來(lái)進(jìn)行評(píng)估以達(dá)成一致性.得益于從一個(gè)聚類融合的一致密切關(guān)系，自適應(yīng)選擇方法AMS獲得顯著的改進(jìn)，明顯高于4種相似度衡量方法的平均水平.而且，AMS只需要依賴一個(gè)參數(shù)——聚類融合解決方案數(shù)T.這也大大簡(jiǎn)化實(shí)驗(yàn)的工作量.另外，通過(guò)圖6可以觀察到，對(duì)于不同的聚類融合解決方案數(shù)T，本文提出的方法均明顯高于4種相似度衡量方法的平均水平，這說(shuō)明本文的方法有較好的魯棒性，并不依賴于具體參數(shù).

4 結(jié) 論

對(duì)網(wǎng)頁(yè)文本聚類問(wèn)題，本文提出基于信息融合的自適應(yīng)指標(biāo)選擇方法Adaptive Metric Selection（AMS），并對(duì)比了4種距離/相似度方法和AMS在衡量文本相似度方面的差異.在衡量文本相似度中，自適應(yīng)指標(biāo)選擇AMS相對(duì)于4種距離/相似度度量有著比較好的聚類效果.

［1］ STREHL A，GHOSH J.Cluster ensembles-a knowledge reuse framework for combining multiple partitions［J］.J Mach Learn Res，2002，3：583-617.

［2］ FERN X Z，BRODLEY C E.Solving cluster ensemble problems by bipartite graph partitioning［C］∥Proceed 21 Intern Conf Mach Learn，2004：69.

［3］ FERN X，LIN W.Cluster ensemble selection［C］∥Proc SIAM Int Conf Data Min（SDM），2008：787-797.

［4］ MONTI S，TAMAYO P，MESIROV J，et al.Consensus clustering：a resampling-based method for class discovery and visualization of gene expression microarray data［J］.Mach Learn，2003，52（1）：91-118.

［5］ FRED A，JAIN A K.Combining multiple clusterings using evidence accumulation［J］.IEEE Trans Pattern Anal Mach Intell，2005，27（6）：835-850.

［6］ KUNCHEVA L I，VETROV D.Evaluation of stability of k-means cluster ensembles with respect to random initialization［J］.IEEE Trans Pattern Anal Mach Intell，2006，28（11）：1798-1808.

［7］ AYAD H，KAMEL M S.Cumulative voting consensus method for partitions with variable number of clusters［J］.IEEE Trans Pattern Anal Mach Intell，2008，30（1）：160-173.

［8］ AZIMI J，F(xiàn)ERN X.Adaptive cluster ensemble selection［C］//Proceed 21st Intern Jont Confer Artif Intell，2009：992-997.

［9］ WU O，HU W，MAYBANK S J，et al.Efficient clustering aggregation based on data fragments［J］.IEEE Trans Syst，Man，Cybern B，Cybern，2012，42（3）：913-926.

［10］IAM-ON N，BOONGOEN T，GARRETT S.Lce：A link-based cluster ensemble method for improved gene expression data analysis［J］.Bioin-Format，2010，26（12）：1513-1519.

［11］IAM-ON N，BOONGOEN T，GARRETT S，et al.A link-based approach to the cluster ensemble problem［J］.IEEE Trans Pattern Anal Mach Intell，2011，33（12）：2396-2409.

［12］WANG T.Ca-tree：A hierarchical structure for efficient and scalable coassociation-based cluster ensembles［J］.IEEE Trans Syst Man Cybern B Cybern，2011，41（3）：686-698.

［13］ZHANG S，WONG H S.Arimp：A generalized adjusted rand index for cluster ensembles［C］∥Istanbul，Turkey 20th Internat Conf Pattern Recog（ICPR 2010），2010：778-781.

［14］ZHANG S，WONG H S，SHEN Y.Generalized adjusted rand indices for cluster ensembles［J］.Pattern Recog，2012，45（6）：2214-2226.

［15］ZHANG S，WONG H，SHEN Y，et al.A new unsupervised feature ranking method for gene expression data based on consensus affinity［J］.IEEE/ACM Trans Comput Biol Bioinf，2012，9（4）：1257-1263.

［16］ZHANG S，WONG H S，SHEN W J，et al.Aors：Affinity-based outlier ranking score［C］∥Neural Netw（IJCNN），2014 Intern Joint Conf IEEE，2014：1020-1027.

［17］TOPCHY A P，JAIN A K，PUNCH W F.Clustering ensembles：Models of consensus and weak partitions［J］.IEEE Trans Pattern Anal Mach Intell，2005，27（12）：1866-1881.

［18］YU Z，WONG H，WANG H.Graph-based consensus clustering for class discovery from gene expression data［J］.Bioinformatics，2007，23（21）：2888.

［19］GIONIS A，MANNILA H，TSAPARAS P.Clustering aggregation［J］.ACM Trans Knowl Disc Data（TKDD），2007，1（1）：4.

［20］劉群，張華平，俞鴻魁，等.基于層疊隱馬模型的漢語(yǔ)詞法分析［J］.計(jì)算機(jī)研究與發(fā)展，2004（8）：1421-1429.LIU Q，ZHANG H P，YU H K，et al.Based on layered hidden Markov model of Chinese lexical analysis［J］.Comput Res Devel，2004（8）：1421-1429.

［21］劉七.基于Web文本內(nèi)容的信息過(guò)濾系統(tǒng)的研究與設(shè)計(jì)［D］.南京：南京理工大學(xué)，2004.LIU Q.Research and design of information filtering system based on Web text content［D］.Nanjing：Nanjing University of Science and Technology，2004.

［22］盧志翔，蒙麗莉.文本分類中特征項(xiàng)權(quán)重算法的改進(jìn)［J］.柳州師專學(xué)報(bào)，2011（4）：128-131.LU Z X，MENG L L.The improvement of feature weight algorithm in text classification［J］.J Liuzhou Teach Coll，2011（4）：128-131.

［23］楊帆，孫強(qiáng).從Web網(wǎng)頁(yè)上獲取一價(jià)事件常識(shí)的方法［J］.科學(xué)技術(shù)與工程，2010（25）：6300-6304.YANG F，SUN Q.A method for obtaining knowledge from the Web Webpage event［J］.Sci Tech Eng，2010（25）：6300-6304.

［24］鄧彩鳳.中文文本分類中互信息特征選擇方法研究［D］.重慶：西南大學(xué)，2011.DENG C F.Research on feature selection method in Chinese Text Categorization［D］.Chongqing：Southwestern University，2011.

［25］彭湘華.基于相關(guān)性的癌癥特征選擇及分類算法研究［D］.長(zhǎng)沙：湖南大學(xué)，2012.PENG X H.Research on correlation based feature selection and classification algorithm for cancer［D］.Changsha：Hunan University，2012.

［26］田偉.XML文檔分類方法的研究及其應(yīng)用［D］.沈陽(yáng)：大連理工大學(xué)，2009.TIAN W.Research and application of XML document classification method［D］.Shenyang：Dalian University of Technology，2009.

［27］王垚堯.基于機(jī)器學(xué)習(xí)的經(jīng)濟(jì)行業(yè)分類方法研究［D］.哈爾濱：哈爾濱工業(yè)大學(xué)，2011.WANG Y Y.Research based on classification method of economic sectors based on machine learning［D］.Harbin：Harbin Institute of Technology，2011.

［28］韓家煒.數(shù)據(jù)挖掘概念與技術(shù)［M］.北京：機(jī)械工業(yè)出版社，2001.HAN J W.Concept and technology of data mining［M］.Beijing：Machinery Industry Press，2001.

［29］毛國(guó)君.數(shù)據(jù)挖掘原理與算法［M］.北京：清華大學(xué)出版社，2005.MAO G J.Principle and algorithm of data mining［M］.Beijing：Tsinghua University Press，2005.

［30］TENENBAUM J B，DE SILVA V，LANGFORD J C.A global geometric framework for nonlinear dimensionality reduction［J］.Science，2000，290（5500）：2319-2323.

［31］馬永軍，方廷健.基于支持向量機(jī)和距離度量的紋理分類［J］.中國(guó)圖像圖形學(xué)報(bào)，2002，7（11）：1151-1155.MA Y J，F(xiàn)ANG T J.Texture classification based on support vector machine and distance measurement［J］.Chin J Imag Graph，2002，7（11）：1151-1155.

［32］劉寶生，閆莉萍，周東華.幾種經(jīng)典相似性度量的比較研究［J］.計(jì)算機(jī)應(yīng)用技術(shù)，2006（11）：1-3.LIU B S，YAN L P，ZHOU D H.Comparison of several classical similarity measures［J］.Comput Appl Tech，2006（11）：1-3.

［33］MONTI S，TAMAYO P，MESIROV J，et al.Consensus clustering：A resampling-based method for class discovery and visualization of gene expression microarray data［J］.Mach Learn，2003，52（1）：91-118.

［34］FERN X，LIN W.Cluster ensemble selection［C］∥Proc SIAM Int Conf Data Min（SDM），2008：787-797.

M etric selection for web text clustering based on information ensembles

ZHANG Shao-hong1，LI Ji-qiao1，LUO Jia-yi1，XIE Dong-qing1，WANG Jing2
（1.School of Computer Science and Educational Software，Guangzhou University，Guangzhou 510006，China；2.Guangzhou Library，Guangzhou 510623，China）

In the current information age，text data grows at a high speed，and it is very hard for people to get useful information from huge data，which is like looking for a needle in a haystack.As the basic method in text mining，text clustering plays a very important role.Without predefined training set，it is one of the most important questions in text mining to select the suitable metric for different text data.Thus，in this thesis，we propose one novel Adaptive Metric Selection（AMS）method.The pipeline of our working includes：①crawling the webpage content to prepare the data source for clustering；②transforming the content to separate words and then to a vector form；③Extracting features；④Reducing dimension using Isomap；and⑤Using an adaptive selection method AMS to evaluate data similarity.K means is used as the basic clustering algorithm，and we use two popular clustering quality measures to evaluate the final results：①Adjusted Rand Index（ARI），and②Normalized Mutual Information（NMI）.Simulation results show the effectiveness of our proposed methods compared to the averaged results of different metrics.

data mining；feature extraction；clustering ensembles

TP 181

A

1671-4229（2016）01-0080-10做是一個(gè)相似矩陣，并且，這樣一個(gè)最終的聚類結(jié)果能用任意能直接在距離矩陣或相似矩陣上運(yùn)算的聚類算法獲得.基于包含Single Link（SL），Average Link（AL）or Complete Link（CL）的凝聚層次聚類算法的聚類融合方法就是有代表性熱門方法.第二類聚類融合方法生成一種基于樣本、集合、分區(qū)之間的關(guān)聯(lián)的代表性圖像，其中這種關(guān)聯(lián)是源于獨(dú)立聚類結(jié)果.在這一類方法中，典型的結(jié)果包括Cluster-based Similarity Partitioning Algorithm（CSPA）［19］，Meta-CLustering Algorithm（MCLA）［19］和Hybrid Bipartite Graph Formulation algorithm（HBGF）［19］.聚類融合方法生成更多較獨(dú)立聚類結(jié)果更穩(wěn)定且精確的結(jié)果.一般需要處理2種相似度衡量：①樣本數(shù)據(jù)之間的相似度衡量方法，通常稱為相似度或者距離.樣本相似度或距離的選擇，會(huì)直接影響無(wú)監(jiān)督學(xué)習(xí)算法的學(xué)習(xí)結(jié)果.②無(wú)監(jiān)督學(xué)習(xí)得到的樣本類別和樣本類別參考值之間的相似度，通常成為聚類質(zhì)量的衡量方法.聚類質(zhì)量衡量方法的選擇，是正確衡量聚類結(jié)果的基礎(chǔ).

【責(zé)任編輯：陳 鋼】

2015-12-21；

2015-12-30

張少宏（1969-），男，副教授，博士.E-mail：zimzsh＠qq.com