結(jié)合文本語義圖和詞頻統(tǒng)計的網(wǎng)頁分類算法研究*

周文文 韓 斌 黃樹成

（江蘇科技大學(xué)計算機學(xué)院 鎮(zhèn)江 212003）

1 引言

互聯(lián)網(wǎng)的快速發(fā)展帶給人數(shù)不盡的網(wǎng)頁，面對如此爆炸式豐富的內(nèi)容，如何精準(zhǔn)快速地查詢到自己所需要的信息成了計算機領(lǐng)域近些年來研究的熱點，在這種情況下，網(wǎng)頁分類技術(shù)應(yīng)運而生并一直處在發(fā)展進步中。

簡單來講，網(wǎng)頁分類就是一個依照不同的種類、等級或性質(zhì)研究網(wǎng)頁相似性，然后將網(wǎng)頁分別歸類的過程。現(xiàn)在主要發(fā)展有兩個方向，一個是占主流的依照文本內(nèi)容分類［1］，即分類實現(xiàn)依托于各種詞頻統(tǒng)計權(quán)值算法。另一個是依照文本語義［2］分類，但由于中文語義的錯綜復(fù)雜，這一方向還有待發(fā)展。前者的思路是將網(wǎng)頁文本在預(yù)處理分詞后根據(jù)詞條在文本出現(xiàn)的頻次和在其他網(wǎng)頁中出現(xiàn)的頻次［3］為基礎(chǔ)發(fā)展改進的，重點在于詞語出現(xiàn)與否以及出現(xiàn)的次數(shù)，缺乏了對詞語語義語法結(jié)構(gòu)和句法的考慮，忽略了詞語本身自帶的信息。后者則側(cè)重于詞義本身和文本結(jié)構(gòu)性［4］信息，以詞義以及詞語和詞語間關(guān)系為依托進行網(wǎng)頁間的相似性判別，但也忽略了文本自身詞語的比例組成。

為了提高網(wǎng)頁分類效率，本文提出一種通過分析網(wǎng)頁詞義，以詞語組合代替單獨的詞語作為特征項構(gòu)建文本語義圖為基礎(chǔ)的網(wǎng)頁分類，兼顧詞語間的相似性和詞語相關(guān)性，然后融入對于詞語組成詞頻統(tǒng)計的研究，結(jié)合文本語義圖和內(nèi)容共同進行網(wǎng)頁分類，并作出相應(yīng)改進。

2 詞匯網(wǎng)絡(luò)構(gòu)建

2.1 語義圖節(jié)點獲取

獲取網(wǎng)頁內(nèi)容，經(jīng)過源網(wǎng)頁解析［5］和文本預(yù)處理，網(wǎng)頁文本內(nèi)容以一系列詞的形式存在。要選取合適的詞語作為特征詞組成特征詞空間，考慮詞頻對詞語重要性的影響，且為了減少詞語冗余，增加計算工作量，從中選取頻次 f＞fmin（給定最小詞頻）的詞語作為特征詞語義圖節(jié)點空間。

2.2 詞語相似性

2.2.1 同義詞詞林

同義詞詞林［6～7］是梅家駒先生于1983年編纂而成的一部同義詞辭典，哈爾濱工業(yè)大學(xué)信息檢索實驗室又對其中詞語進行了更新，完成了擴展板部分的改良。擴展版共含有7萬多個詞語，這些詞語又被分為12個大類，94個中類，1428個小類，再細化小類為詞群和原子詞群。整部辭典呈五層樹狀構(gòu)架存在，遵循從具體到抽象的準(zhǔn)則，隨級別逐層細分，第五層即為不可再細分的原子詞群。值得一提的是，在第五級詞群中，不僅分有同義詞，例如東南西北和四方同屬一個編碼，這類詞明顯相似性最強，還有相關(guān)詞，例如液體、流體是為同類相關(guān)詞，同屬一個編碼，但這種詞相似性比前者要弱。同時還存在有獨立詞，即該詞既沒有同義詞也沒有相關(guān)詞，顯然這類詞相關(guān)性最低。對這三類詞，編者分別用“=”“#”“@”三種符號在編碼末加以標(biāo)注區(qū)分。

2.2.2 詞語相似性計算

詞語相似性［8］是一個取值范圍在0～1之間的數(shù)值，次遇見相似性越高，相似度越接近1，詞語和其本身相似度即為1。根據(jù)詞語在詞林中距離的遠近，又考慮到詞語所在詞林樹的密度及分支數(shù)，若兩詞語在第 i層分支，定義詞語相似度［9］sim(x，y)為

其中，θi為詞林第i層分支下的分支系數(shù)，m為i層總分類數(shù)，k為兩分支間距離。分別計算不同節(jié)點間的相似度，給定最小相似度值 simmin，當(dāng)時，在兩節(jié)點間建立一條邊，形成初步語義網(wǎng)絡(luò)。

2.3 詞語相關(guān)性

2.3.1 頻繁項集

研究語義的過程中，不僅要考慮詞義自身所含的特性，還需要考慮該詞語在整個文本中發(fā)揮的作用，查看在特定文本中詞語間的相關(guān)性，即當(dāng)多個詞語同時出現(xiàn)在同一個文本類中，可以推斷這些詞語間有很強的相關(guān)性。首先給出頻繁項集［10］的概念，記文本中詞匯集合 D={wordi，wordj，…，wordn}為數(shù)據(jù)集，有 X={wordi，wordj…} ，若 wordi∈D ，則稱X為項集。而對于項集X，若X的支持度滿（最小支持度）時，則稱 X是數(shù)據(jù)集 D 上的頻繁項項集［11］，wordi，wordj… 具有詞語相關(guān)性。

2.3.2 頻繁項集挖掘

在頻繁項集的基礎(chǔ)上找出關(guān)聯(lián)規(guī)則的過程即為頻繁項集挖掘。以X是頻繁項集為基礎(chǔ)，對于則 X就被稱為數(shù)據(jù)集D上的最大頻繁集［12］。又因為最大頻繁集的非空子集一定是頻繁項集，所以只需要保留最大頻繁集即可，由所有最大頻繁集組成而成相關(guān)詞集。遍歷最終的相關(guān)詞集，在相關(guān)詞集中的每一個相關(guān)詞組合之間建立一條邊，將新的邊添加到語義網(wǎng)絡(luò)中，得到最終完整的詞匯語義網(wǎng)絡(luò)。

3 詞頻統(tǒng)計方法

3.1 IDF算法

在形成詞匯網(wǎng)絡(luò)的過程中，算法僅對詞語出現(xiàn)的總體詞頻做出考慮，缺少對類內(nèi)詞頻分布的考慮，也對特征詞所在的文本在全部文本中的分布信息沒有關(guān)注，顯然這種考慮并不充分的。對于這種缺失，首先引入 IDF算法［13～14］。IDF算法是逆文檔頻率權(quán)重法，它認為在少數(shù)文本中出現(xiàn)的特征詞更具有代表性，故出現(xiàn)文本數(shù)量越小的詞語給予的IDF值越大，顯示該詞語區(qū)別能力越強。這種算法很好地考慮到了特征詞所在的文本在整個語料庫的分布信息。在結(jié)合詞語類內(nèi)的分布，有詞頻權(quán)重值wfi：

其中，wfi是特征詞ti的詞頻權(quán)重值，idf(ti)是逆文檔頻率權(quán)重值，mi是特征詞在該類中出現(xiàn)的文本數(shù)，Mi為該類文本總數(shù)，當(dāng)詞語在該類中文本占比越多，則該詞語越能代表該類網(wǎng)頁，權(quán)重值越大。

3.2 IDF改進算法

在上述分析中，對于詞語出現(xiàn)的文本占比，逆文檔頻率算法僅從宏觀角度去度量，但對于每類樣本空間，有一種詞語屬于網(wǎng)頁常見詞，在多個類別中都有不均衡出現(xiàn)，這種詞語詞頻偏高，文本總占比不高，但攜帶的類別特征信息卻仍然很少，區(qū)分度并不高，易引發(fā)混淆，影響網(wǎng)頁分類的效率，為減少這類詞語的影響，對逆文檔頻率算法做出改進，有

其中，N為總文本數(shù)，ni為詞語ti所在文本數(shù)，Ci為詞語ti所在的類別的類別數(shù)，當(dāng)Ci越大即詞語所在種類越多時，詞語ti所攜帶的分類信息越少，給予較低權(quán)重。綜合上述分析，詞頻權(quán)重wfi更新為

4 特征向量

4.1 PageRank算法應(yīng)用

基于詞匯網(wǎng)絡(luò)圖的特征權(quán)重計算，這里引入PageRank 算法［15～16］。PageRank 是 Google創(chuàng)始人提出用來計算網(wǎng)頁排序的經(jīng)典算法，用網(wǎng)頁間的互相鏈接表現(xiàn)網(wǎng)頁的重要程度。若一個網(wǎng)頁被很多其他網(wǎng)頁鏈接到則認為該網(wǎng)頁很重要，給予大的PageRank值，而當(dāng)一個網(wǎng)頁被一個高PR值網(wǎng)頁鏈接時，它也將相應(yīng)提高自身的PR值。PageRank以此為基礎(chǔ)對網(wǎng)頁進行排序，同樣的思想借鑒到詞匯網(wǎng)絡(luò)為節(jié)點重要程度排序中。在詞匯網(wǎng)絡(luò)中，當(dāng)一個節(jié)點被其他很多節(jié)點指向時，認為這個節(jié)點較為重要。同樣地，當(dāng)一個比較重要的節(jié)點指向其他節(jié)點時，被指向的節(jié)點重要程度也將提高。這里節(jié)點更重要就是指這個節(jié)點攜帶信息量多，區(qū)分度高，因而具有較強的分類能力，對分類效果會產(chǎn)生較大影響。一個節(jié)點的PR值［17］為

其中，F(xiàn)Vi為指向節(jié)點Vi的節(jié)點合集，LVj是從節(jié)點Vi出發(fā)指向其他節(jié)點的邊的條數(shù)，N為網(wǎng)絡(luò)中的節(jié)點總數(shù)，d為阻尼系數(shù)，幫助節(jié)點的PR值實現(xiàn)收斂，通常d取0.85。為提高PR值的收斂速度，指定計算PR初值為

根據(jù)公式可以計算每個節(jié)點的PR值，當(dāng)節(jié)點PR值經(jīng)過不斷迭代趨于平穩(wěn)時，得到最終PR值，記每個節(jié)點的語義權(quán)重值Wi=PRi。

4.2 特征向量計算

由PageRank算法，可以得到特征詞的語義權(quán)重值，結(jié)合改進的詞頻權(quán)重算法得出的詞頻權(quán)重值，得到最終權(quán)重值Wi：

5 實驗結(jié)果與分析

網(wǎng)絡(luò)上公開的中文網(wǎng)頁文本庫并不多，故通過人工抓取獲得4028個網(wǎng)頁，分別有游戲、旅游、醫(yī)療、招聘、金融五個類別，其中2754個網(wǎng)頁作為訓(xùn)練集，剩下1274個網(wǎng)頁作為測試集。具體類別分布如表1。

表1 文本語料庫分布表

實驗選用K最近鄰算法（KNN）［18］訓(xùn)練分類器。

實驗一：對比基于文本語義圖網(wǎng)頁分類算法、基于詞頻統(tǒng)計網(wǎng)頁分類算法和結(jié)合文本語義圖和詞頻統(tǒng)計的算法分類效率，結(jié)果如表2。

表2 三種算法效率對比表

由實驗結(jié)果表明，僅基于詞匯網(wǎng)絡(luò)和僅基于詞頻統(tǒng)計的網(wǎng)頁分類效果明顯差于融合兩種算法的網(wǎng)頁分類算法，說明這種結(jié)合是行之有效的。

實驗二：對比算法改進前后網(wǎng)頁算法的分類效率，結(jié)果如圖1所示。

圖1 權(quán)值改進前后效率對比圖

由圖1可以清晰看出，對特征權(quán)值改進后，網(wǎng)頁分類效率明顯優(yōu)于改進前。實驗結(jié)果表明，改進方法可以有效地進一步提高分類器分類能力。

6 結(jié)語

本文針對傳統(tǒng)網(wǎng)頁分類算法進行分析，在構(gòu)建文本語義圖的基礎(chǔ)上實現(xiàn)PageRank算法，并結(jié)合詞頻統(tǒng)計算法實現(xiàn)兩種分類方法的融合，另外對算法做出一定改進，通過添加詞頻權(quán)值的方式將詞語的重要性區(qū)分開來，提高詞語區(qū)分度，提高分類效率。實驗結(jié)果表明這種改進算法在準(zhǔn)確率，召回率和Fl均值三種評價方式中均有明顯的提高，相較于其他網(wǎng)頁分類方法具有很大的優(yōu)勢。接下來，如何讓這兩種方式結(jié)合的更加完美以取得網(wǎng)頁分類效率的進一步提高將是研究重點。