基于高性能特征選擇函數(shù)的Ｗｅｂ文檔聚類算法
2009-01-01 00:00:00楊炳儒邵闊義宋澤鋒張克君
計(jì)算機(jī)應(yīng)用研究 2009年2期
(1.北京科技大學(xué) 知識(shí)工程研究所， 北京 100083;2.北京銀聯(lián)商務(wù)有限公司， 北京 100048)
摘 要：目前常用向量空間模型 VSM(vector spacemodel)表示文檔，造成的高維問(wèn)題制約了其實(shí)際應(yīng)用的效果。采用了一種高性能特征選擇函數(shù)，在構(gòu)建VSM時(shí)選取對(duì)區(qū)分類別貢獻(xiàn)較大的特征詞，因此有效地降低了特征空間的緯度，大大提高了系統(tǒng)的效率，改善了聚類的效果。通過(guò)真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)，證明其性能優(yōu)于傳統(tǒng)方法。
關(guān)鍵詞：文檔聚類；Web挖掘；特征選擇；降維
中圖分類號(hào)：TP391.9 文獻(xiàn)標(biāo)志碼：A
文章編號(hào)：10013695(2009)02054603
Web document clustering algorithmbased on heigh performance feature selecting function
YANG Bingru1，SHAO Kuoyi2，SONG Zefeng1，ZHANG Kejun1
(1.Instrtute of Knowledge Engineering， University of Science Technology Beijing， Beijing 100083， China;2.Beijing Unionpay Merchant Services Co.，Ltd.， Beijing 100048， China)
Abstract:Vector space model(VSM) is the mainly way to represent text， but， “heighly dimension” restricts the application of VSM. This paper constructed a heigh performance feature selecting function. Based on category resolve power，selected most valuble feature when constructed vector space. Based on the experiments on an real corpus， this Web document clustering algorithm has better efficiency than traditional algorithms.
Key words:document clustering;Web mining;feature selection;dimension reduction
隨著WWW的飛速發(fā)展，Internet上的資源和服務(wù)均呈現(xiàn)出爆炸性增長(zhǎng)的趨勢(shì)。為了幫助人們有效地使用這些資源和服務(wù)，陸續(xù)地有一些功能強(qiáng)大的搜索引擎問(wèn)世了。這些搜索引擎在給人們帶來(lái)很大便利的同時(shí)也暴露出搜索結(jié)果不能很好地滿足用戶需求的問(wèn)題。因此，Web文檔聚類技術(shù)以其縮減搜索空間、加快檢索速度、提高查詢精度的特點(diǎn)而受到了人們的廣泛關(guān)注[1，2]。
由于Web文檔長(zhǎng)度不同或各個(gè)文檔間關(guān)鍵詞出現(xiàn)的頻度各異而產(chǎn)生的畸變，特別是當(dāng)數(shù)據(jù)維數(shù)較高時(shí)，聚類的質(zhì)量和算法的性能都明顯下降。為了提高其運(yùn)行效率，一般有兩種途徑，即高效的降維方法和較好的聚類算法。目前的降維方法主要有TFIDF、信息增益(information gain，IG)、互信息(mutual information，MI)等，它們都是基于詞頻的統(tǒng)計(jì)信息。文獻(xiàn)[1]中提出利用潛在語(yǔ)義索引（latent semantic index，LSI）壓縮維數(shù)，但其時(shí)間開(kāi)銷較大，影響了在實(shí)際應(yīng)用中的推廣。聚類算法方面，目前效率最好的常用聚類算法是Kmeans算法，該算法復(fù)雜度為O(tkmn)。其中：t為迭代次數(shù)；k為聚類數(shù)；m為特征屬性數(shù)；n為待分類的對(duì)象數(shù)，通常k，m，t< 1 聚類概念及常用的特征選擇算法 1.1 聚類概念 迄今為止，聚類還沒(méi)有一個(gè)學(xué)術(shù)界公認(rèn)的定義。這里給出Everitt在1974年關(guān)于聚類所下的定義[3]：一個(gè)類簇內(nèi)的實(shí)體是相似的，不同類簇的實(shí)體是不相似的；一個(gè)類簇是測(cè)試空間中點(diǎn)的會(huì)聚，同一類簇的任意兩個(gè)點(diǎn)間的距離小于不同類簇的任意兩個(gè)點(diǎn)間的距離；類簇可以描述為一個(gè)包含密度相對(duì)較高的點(diǎn)集的多維空間中的連通區(qū)域，它們借助包含密度相對(duì)較低的點(diǎn)集的區(qū)域與其他區(qū)域(類簇)相分離。 事實(shí)上，聚類是一個(gè)無(wú)監(jiān)督的分類，它沒(méi)有任何先驗(yàn)知識(shí)可用。聚類的形式描述如下：令U={p1，p2，…，pn}表示一個(gè)模式(實(shí)體)集合，pi表示第i個(gè)模式i={1，2，…，n}；CtU，t=1，2，…，k，Ct={pt1，pt2，…，ptw}；proximity(pms，pir)，其中第一個(gè)下標(biāo)表示模式所屬的類，第二個(gè)下標(biāo)表示某類中某一模式，函數(shù)proximity用來(lái)刻畫模式的相似性距離。若諸類Ct為聚類的結(jié)果，則諸Ct需滿足如下條件： a）∪kt=1Ct=U b）對(duì)于Cm，CrU，Cm≠Cr，有Cm∩Cr=（剛性聚類） min(proximity(pms，pir))＞max(proximity(pms，pir)) 1.2 常用的特征選擇算法 已有的實(shí)驗(yàn)結(jié)果[4~6]表明：IG 是最有效的特征選擇方法之一，DF 的效果稍差，但與IG基本相似，而MI相對(duì)較差。 1.2.1 TFIDF 下面是比較常見(jiàn)的一種公式： W(t，d)=tf(t，d)×log(N/nt+0.01)/ t∈d[tf(t，d)×log(N/nt+0.01)]2 其中：W(t，d)為詞t在文本d中的權(quán)重，而tf(t，d)為詞t在文本d中的詞頻；N為訓(xùn)練文本的總數(shù)；nt為訓(xùn)練文本集中出現(xiàn)t的文本數(shù)，分母為歸一化因子。 1.2.2 信息增益 信息增益被廣泛應(yīng)用在機(jī)器學(xué)習(xí)領(lǐng)域，它通過(guò)一個(gè)詞條在一篇文章中出現(xiàn)與否來(lái)計(jì)算對(duì)類別的信息增益。設(shè){ci}mi=1為目標(biāo)空間中的類別的集合，那么詞條t對(duì)類別的信息增益為 IG(t)=-mi=1p(ci)log p(ci)+p(t)mi=1p(ci|t)log p(ci|t)+p()mi=1p(ci|) log p(ci|) 1.2.3 互信息 互信息廣泛應(yīng)用于統(tǒng)計(jì)語(yǔ)言模型，對(duì)于類別c和詞條t，它們之間的互信息定義為 MI（t，c）=log2[ p(t∧c)/（p(t)×p(c)）] 這是單個(gè)類別的互信息，將互信息應(yīng)用于多個(gè)類別有兩種常用的方法：設(shè){ci}mi=1為目標(biāo)空間的類的集合，則平均和最大互信息分別為 MIavg(t)=mi=1p(ci)I(t，ci)， MImax(t)=maxmi=1{I(t，ci)} 2 高性能特征選擇函數(shù) 特征選擇是根據(jù)某種準(zhǔn)則從原始特征中選擇部分最有區(qū)分類別能力的特征。所謂特征區(qū)分類別的能力，直觀上說(shuō)，是通過(guò)一個(gè)特征在文檔中出現(xiàn)與否來(lái)判定該文檔的類別屬性的能力。換言之，類別的集合C={ci}mi=1對(duì)詞條集合的T={t，}依賴（其中：t表示一個(gè)詞條在文檔中出現(xiàn)；表示一個(gè)詞條在文檔中不出現(xiàn)），可通過(guò)c的類別分布和詞條t出現(xiàn)或不出現(xiàn)時(shí)的類別分布的變化來(lái)刻畫。該變化是一個(gè)模糊的概念，需要進(jìn)一步細(xì)化，通過(guò)一個(gè)關(guān)于類別分布的函數(shù)g(C)來(lái)刻畫變化。 定義1 文檔的類別分布函數(shù)。若文檔集的類別分布為p(C)={p(c1)，p(c2)，…，p(cm)}，g(C)為p(c1)，p(c2)，…，p(cm)的一個(gè)函數(shù)，則稱g(C)為一個(gè)關(guān)于類別分布的函數(shù)。 定義2 稱p(t)g(C|t)+p(）g(C|)為文檔集在給定T時(shí)的一個(gè)條件類別分布值(條件類別分布)。 定義3 一個(gè)類別分布值與給定T時(shí)的條件類別分布值之差為g(C)-p(t)g(C|t)+p(）g(C|)，稱其為t的區(qū)分類別的能力，記為f(C，t)，即f表示特征選擇函數(shù)。 性質(zhì)1 f(C，t)不惟一，它依賴于類別分布的函數(shù)g(C)。 按照上述的定義和性質(zhì)，選擇g(C)=1≤i＜j≤m(p(ci)+p(cj))，并以此為基礎(chǔ)構(gòu)造f(C，t)=g(C)-p(t)g(C|t)+p()g(C|)。 f(C，t)=1≤i＜j≤m(p(ci)+p(cj))-p(t)1≤i＜j≤m(p(ci|t)+p(cj|t))+p()1≤i＜j≤m(p(ci|)+p(cj|)) 上式滿足如下兩條性質(zhì)：a)如果T和C獨(dú)立，當(dāng)且僅當(dāng)t的類別區(qū)分能力最小，即f(C，t)的值最小;b)如果C的值完全取決于T，當(dāng)且僅當(dāng)t的區(qū)分類別能力最大，即f(C，t)的值最大。 3 基于高性能特征選擇方法的Web文檔聚類算法 Web文檔聚類的另一個(gè)重要組成是聚類算法，其基本思想是在樣品之間定義距離、在變量之間定義相似系數(shù)，距離或相似系數(shù)代表樣品或變量之間的相似程度。按相似程度的大小，將樣品（或變量）逐一歸類，關(guān)系密切的類聚到一個(gè)小的分類單位，然后逐步擴(kuò)大，使得關(guān)系疏遠(yuǎn)的聚合到一個(gè)大的分類單位，直到所有的樣品（或變量）都聚集完畢。沒(méi)有任何一種聚類技術(shù)(聚類算法)可以普遍適用于揭示各種多維數(shù)據(jù)集所呈現(xiàn)出來(lái)的多種多樣的結(jié)構(gòu)。根據(jù)數(shù)據(jù)在聚類中的積聚規(guī)則以及應(yīng)用這些規(guī)則的方法，聚類算法大致分成劃分式聚類算法、層次化聚類算法。典型的劃分式方法是MacQueen提出的K均值聚類算法(Kmeans算法)，它能對(duì)大型數(shù)據(jù)集進(jìn)行高效分類，其計(jì)算復(fù)雜性為O(tKmn)。在對(duì)大型數(shù)據(jù)集聚類時(shí)，Kmeans算法比層次聚類算法快得多，比較適用于Web文檔聚類任務(wù)。層次化聚類算法使用數(shù)據(jù)的連接規(guī)則，透過(guò)一種層次架構(gòu)方式，反復(fù)將數(shù)據(jù)進(jìn)行分裂或聚合，以形成一個(gè)層次序列的聚類問(wèn)題解，其計(jì)算復(fù)雜性為O(n2)，適合于小型數(shù)據(jù)集的分類。 因此在構(gòu)造本文的Web文檔聚類算法時(shí)，采用Kmeans算法作為核心的聚類算法。將其與上述基于區(qū)分類別能力的特征選擇方法結(jié)合起來(lái)，形成結(jié)構(gòu)如圖1所示的高性能Web文檔聚類算法。 4 實(shí)驗(yàn)分析 4.1 測(cè)試語(yǔ)料庫(kù) 為了測(cè)試本文提出的Web文檔聚類算法，采用的測(cè)試數(shù)據(jù)集是一個(gè)含有約2 300篇語(yǔ)料的新聞?wù)Z料庫(kù)，該新聞?wù)Z料庫(kù)中的文本都是新聞電信稿件。語(yǔ)料庫(kù)測(cè)試數(shù)據(jù)類別的構(gòu)成如表1所示。 4.2 評(píng)價(jià)方法 文本分類算法中使用的性能評(píng)價(jià)指標(biāo)為：文檔的查全率（recall）、查準(zhǔn)率（precision）及綜合分類率F1值（F1 value）。但是在文本聚類過(guò)程中并不存在自動(dòng)分類類別與手工分類類別確定的一一對(duì)應(yīng)關(guān)系，因而無(wú)法像文本分類一樣直接以查全率和查準(zhǔn)率作為評(píng)價(jià)標(biāo)準(zhǔn)。為此，本文將選擇平均準(zhǔn)確率θ作為評(píng)價(jià)的指標(biāo)。平均準(zhǔn)確率通過(guò)考察任意兩篇文章之間類屬關(guān)系是否一致來(lái)評(píng)價(jià)聚類的效果。任意兩篇文章之間的關(guān)系，按照人工分類的標(biāo)準(zhǔn)和自動(dòng)聚類分析的標(biāo)準(zhǔn)可以有四種情況，如表2所示。 平均準(zhǔn)確率θ定義為積極準(zhǔn)確率θ1與消極準(zhǔn)確率θ2的算術(shù)平均值，即θ=(θ1+θ2)/2。其中：積極準(zhǔn)確率θ1定義為θ1=a/(a+c)；消極準(zhǔn)確率θ2定義為θ2=d/(b+d)。 表1 測(cè)試語(yǔ)料庫(kù)的類別構(gòu)成表 主題類別文本篇數(shù)主題類別文本篇數(shù) 政治與社會(huì)607教育147 軍事407航空航天130 計(jì)算機(jī)354法律81 體育242醫(yī)療衛(wèi)生70 經(jīng)濟(jì)198旅游服務(wù)56 表2 文本之間的關(guān)系情況表 人工分類時(shí)屬于同一類別 聚類分析時(shí)屬于同一類別標(biāo)志 YesYesa YesNob NoYesc NoNod 4.3 評(píng)價(jià)結(jié)果 為了考察本文算法的實(shí)際性能，采用了基于詞頻的Kmeans算法、基于信息熵的Kmeans算法和基于信息增益的Kmeans算法與本文基于區(qū)分類別能力的聚類算法在測(cè)試語(yǔ)料庫(kù)中進(jìn)行了實(shí)際運(yùn)行分析，算法聚類結(jié)果如圖2所示。圖3為本文聚類算法聚類結(jié)果的網(wǎng)格結(jié)構(gòu)信息導(dǎo)航圖。網(wǎng)格結(jié)構(gòu)顯示窗口分成左右兩個(gè)部分，左半部分使用樹(shù)型結(jié)構(gòu)顯示聚類自動(dòng)形成的主題類別及每類中包含的文章名稱；右半部分使用網(wǎng)格結(jié)構(gòu)表示文本聚類的結(jié)果，它用所有帶顏色的網(wǎng)絡(luò)數(shù)目表示待聚類的文本集合。對(duì)屬于同一個(gè)主題類別的文本集則染上同樣的顏色，不同主題類別文本集的顏色不同。 從以上的實(shí)驗(yàn)運(yùn)行結(jié)果中可以看出，基于區(qū)分類別能力的聚類算法的平均準(zhǔn)確率比其他三種聚類分析算法要高；同時(shí)在實(shí)驗(yàn)觀察結(jié)果中發(fā)現(xiàn)，基于區(qū)分類別能力的聚類算法得到的集簇具有相當(dāng)鮮明的類別特征，即與一個(gè)主題類別相關(guān)的文本較集中地聚為一類。因此，平均準(zhǔn)確率θ只是從一個(gè)方面說(shuō)明了該算法具有良好的聚類特征。 5 結(jié)束語(yǔ) Web文檔聚類分析是文本挖掘中的一種重要手段，而文檔標(biāo)引和特征選擇是其基礎(chǔ)和關(guān)鍵工作。本文提出一種新的基于區(qū)別類別能力的特征選擇方法，并將其與聚類算法整合，形成一套高性能的Web文檔聚類算法。該方法能降低特征空間維度，同時(shí)可有效改善傳統(tǒng)以詞為特征的聚類算法的性能。通過(guò)實(shí)驗(yàn)驗(yàn)證發(fā)現(xiàn)，其效果優(yōu)于傳統(tǒng)算法。 參考文獻(xiàn)： [1]HOW B C，NARAYANAN K.An empirical study of feature selection for text categorization based on term weightage[C]//Proc of the IEEE/WIC/ACM Int’l Conference on Web Intelligence.Washington DC:IEEE Computer Society Press，2004:599602. [2]LI S S，ZONG C Q.A new approach to feature selection for text categorization[C]//Proc of IEEE Int’l Conference on Natural Language Processing and Knowledge Engineering.Piscataway:IEEE Press， 2005:626630. [3]ACKERMAN M，BILLSUS D，GAFFNEY S，et al.Learning probabilistic user profiles[J].AI Magazine，1997，18(2):4756. ［4］CHANG C H，HSU C C.Customizable multiengine search tool with clustering[J].Computer Network and ISDN Systems，1997，29(813):12171224. [5]CHEN L，KATYA S.Webmate:a personal agent browsing and searching[C]//Proc of the 2nd International Conference on Autonomous Agents. New York: ACM Press， 1998:132139. [6]RON W，BIENVENIDO V，MARK A S，et al.Hypursuit:a hierarchical network search engine that exploits contentlink hypertext clustering[C]//Proc of the 7th ACM Conference on Hypertext. New York: ACM Press， 1996:180193. [7]ZHAO S Q，ZHANG Y，LIU T，et al.A feature selection method based on class feature domains for text categorization[J].Journal of Chinese Information Processing，2005，19(6):2127 .
