網(wǎng)頁模糊歸類算法的應(yīng)用與實現(xiàn)

1、網(wǎng)頁模糊歸類算法的應(yīng)用與實現(xiàn) 05-12-23 13:21:00 作者：佚名編輯：studa9ngns摘要：本文運用以模糊綜合評判為核心的理論實現(xiàn)對網(wǎng)頁的模糊自動歸類，詳細(xì)闡述了網(wǎng)頁模糊歸類算法(FWCA)，并且通過一個實例闡明了實現(xiàn)過程。作者利用此算法親自設(shè)計實現(xiàn)了一個“網(wǎng)頁模糊歸類測試系統(tǒng)”，通過分析大量實驗數(shù)據(jù)證明了利用此算法得歸類效果非常穩(wěn)定和準(zhǔn)確。關(guān)鍵詞：FWCA 模糊綜合評判 網(wǎng)頁歸類 分類瀏覽 搜索引擎自有文字和書籍以來，人類就開始注意文章的分門別類和編撰目錄。那些目錄事實上就將文章按照內(nèi)容的類別進行了分類。九十年代以來，Internet 以驚人的速度發(fā)展起來，Web的容量增長迅

2、速，平均每天增加100萬個頁面。計算技術(shù)發(fā)展到今天，靠人來閱讀互聯(lián)網(wǎng)上信息和對網(wǎng)上信息做分門別類和總結(jié)已經(jīng)不可能。搜索引擎的分類瀏覽模式由此應(yīng)運而生。它的目錄分類的質(zhì)量較高，檢索效果好；但是需要人工維護，因此存在成本高、信息更新慢、維護的工作量大的缺點。而基于模糊技術(shù)的網(wǎng)頁自動歸類能依據(jù)網(wǎng)頁中所包含的文本的語義將大量的網(wǎng)頁自動分門別類，從而更好地幫助人們把握網(wǎng)絡(luò)信息。網(wǎng)頁模糊歸類步驟與算法簡單地說，網(wǎng)頁自動歸類所要完成的任務(wù)就是在給定的分類體系下，根據(jù)網(wǎng)頁的內(nèi)容自動地確定網(wǎng)頁關(guān)聯(lián)的類別。如果從純數(shù)學(xué)角度來看，網(wǎng)頁分類的過程實際上就是一個多對多的映射過程。依據(jù)“貝葉斯假設(shè)”的內(nèi)容，可以假定組成網(wǎng)

3、頁的元素在確定網(wǎng)頁類別的作用上相互獨立。這樣，可以使用網(wǎng)頁中出現(xiàn)的字或詞的集合來代替網(wǎng)頁，即用一個向量來表示文本：D（W1,W2,W3Wn），其中 Wi 為第 i 個元素（以下均稱為“特征項”）的數(shù)值。當(dāng)然，這將丟失大量關(guān)于網(wǎng)頁內(nèi)容的信息，但是這種假設(shè)可以使網(wǎng)頁的表示和處理形式化，從而讓計算機可以處理網(wǎng)頁。構(gòu)成網(wǎng)頁中的文本的詞匯，數(shù)量是相當(dāng)大的，因此，表示網(wǎng)頁的向量空間的維數(shù)也相當(dāng)大，可以達到幾萬維，所有幾萬個詞匯對網(wǎng)頁分類的意義是不同的。首先，需要考慮詞語的性質(zhì)。一些通用的、各個類別都普遍存在的詞匯對分類的貢獻是很小的，因此特征提取過程需要去掉對表達網(wǎng)頁類別不太重要的詞匯。例如“的”、“地”

4、、“得”、“著”、“了”等等。其次，在某特定類中出現(xiàn)比重大而在其他類中出現(xiàn)比重小的詞匯對文本分類的貢獻大，為了提高分類精度，可以利用詞語的互信息量篩選出針對該類的特征項集合。具體操作方法是算出每個詞語的互信息量并排序，然后抽取前個詞語作為該類別的特征項，抽取的原則是反復(fù)試驗使得網(wǎng)頁歸類效果最優(yōu)。互信息量(I)計算公式由下式給出：為了讓計算機為我們進行網(wǎng)頁的自動歸類，必須先對計算機進行訓(xùn)練。只要訓(xùn)練網(wǎng)頁足夠多，那么由計算機進行的歸類活動也將是準(zhǔn)確的。所有的訓(xùn)練樣本都需表示為向量 。并使用每個詞的相對詞頻（TF-IDF 公式）對網(wǎng)頁樣本的特征項進行量化。然后，將每個類別中的所有訓(xùn)練樣本數(shù)據(jù)合成為一

5、個平均參照樣本，計算方法就是將每個特征項的值求算術(shù)平均。相對詞頻計算公式由下式給出：在歸類過程中，采用三級模糊綜合評判。一級指標(biāo)因素集（網(wǎng)頁中出現(xiàn)位置）包括：網(wǎng)頁題名、文章標(biāo)題、第一段首句、第一段尾句、第二段首句、第二段尾句、第三段首句、第三段尾句、首段、尾段、HTML標(biāo)記。二級指標(biāo)因素集（詞性）包括：名詞, 動詞, 形容詞, 副詞, 介詞, 連詞, 助詞, 數(shù)字, 符號。三級指標(biāo)因素集：待分類網(wǎng)頁中所包含的全部詞語的頻數(shù)。評價集確定為V=V1(不屬于0), V2(不太可能屬于0.25), V3(可能屬于0.5), V4(很可能屬于0.75), V5(屬于1)。 專家隨機抽取了300篇網(wǎng)頁，對

6、這些網(wǎng)頁進行人工自由標(biāo)引、人工打分、詞頻統(tǒng)計，并進行統(tǒng)計數(shù)據(jù)的分析、研究，將一級指標(biāo)因素權(quán)重集確定為A=0.128, 0.128, 0.128, 0.104, 0.104, 0.104, 0.06, 0.06, 0.06, 0.06, 0.05, 0.05；根據(jù)語言學(xué)專家對各類別中不同詞性的詞語對標(biāo)志一個類別（以中圖分類法為標(biāo)準(zhǔn)）重要性程度統(tǒng)計和評分，將二級指標(biāo)因素權(quán)重集確定為An=0.28, 0.18, 0.24, 0.06, 0.05, 0.04, 0.04, 0.06, 0.05；根據(jù)詞語的互信息量確定出三級指標(biāo)因素權(quán)重為Anm=Anm1, Anm2 Anmx 其中，Anmx即為對應(yīng)詞語

7、的互信息量隸屬函數(shù)采用卡夫曼教授提出的隸屬函數(shù)確定方法（正態(tài)分布模型）確定如下： 詞頻針對“不屬于”的隸屬函數(shù) 詞頻針對“不太可能屬于”的隸屬函數(shù) 詞頻針對“不可能屬于”的隸屬函數(shù) 詞頻針對“很可能屬于”的隸屬函數(shù) 頻針對“屬于”的隸屬函數(shù)其中，axyz是訓(xùn)練樣本中詞語的相對詞頻；x為樣本網(wǎng)頁中對應(yīng)詞的統(tǒng)計詞頻；系數(shù)是通過人工評判得到一些特殊點，由待定系數(shù)法求出的。下面就要根據(jù)多級模糊綜合評判的計算方法與步驟將待歸類網(wǎng)頁與所有類別的平均參照樣本進行一遍計算，得出一組表示該網(wǎng)頁與各個類別貼近度的數(shù)值。然后按照“最大隸屬原則”，將網(wǎng)頁劃到Vn值最大的對應(yīng)的類別中；或者用“域值法”，事先確定一個不大

8、于1的域值，若Vn則認(rèn)為網(wǎng)頁屬于此類別，因此，一個網(wǎng)頁可能同時屬于多個類別。網(wǎng)頁模糊歸類實例（1）前期工作簡化的分類的標(biāo)準(zhǔn)：經(jīng)濟類，體育類，科教類訓(xùn)練樣本數(shù)目：48篇（三類各16篇）待歸類網(wǎng)頁：一級指標(biāo)因素及權(quán)重：U=U1=0.5, U2=0.5二級指標(biāo)因素及權(quán)重：U1=U11=1.0 U2=U21=0.4, U22=0.26), U23=0.34 三級指標(biāo)因素及權(quán)重：U11=U111=0.86, U112=0.14) U21=U211=0.11, U212=0.35, U213=0.21, U214=0.06, U215=0.10, U216=0.17 U22=U221=0.26, U222

9、=0.38, U223=0.36 U23=U231=0.46, U232=0.54經(jīng)濟類訓(xùn)練網(wǎng)頁樣本相對詞頻：a11=a111(經(jīng)濟1.2), a112(快訊1.2) a21=a211(我國1.1), a212(經(jīng)濟2.2), a213(水平1.8), a214(三年0.5), a215(人民0.9), a216(生活1.3) a22=a221(實現(xiàn)1.3), a222(翻番1.8), a223(提高1.7) a23=a231(連續(xù)1.6), a232(日益1.7)（2）模糊綜合評判首先統(tǒng)計待分類網(wǎng)頁的各個詞語的絕對詞頻如下： U11=U111(經(jīng)濟1), U112(快訊1)U21=U211(

10、我國1), U212(經(jīng)濟2), U213(水平1), U214(三年1), U215(人民1), U216(生活1)U22=U221(實現(xiàn)1), U222(翻番1), U223(提高1)U23=U231(連續(xù)1), U232(日益1)總共可以得到4個一級模糊綜合評判矩陣如下：構(gòu)造二級模糊綜合評判矩陣采用M(,)算子的運算結(jié)果 采用M(, )算子的運算結(jié)果構(gòu)造三級模糊綜合評判矩陣采用M(,)算子的運算結(jié)果采用M(, )算子的運算結(jié)果多因素綜合評判采用M(,)算子的運算結(jié)果采用M(, )算子的運算結(jié)果網(wǎng)頁歸類決策通過三輪計算得出下表：樣本與類別貼近度 經(jīng)濟類 體育類 科教類采用M(,)算子 06

11、8 031 042采用M(, )算子080 016 027不管采用哪一種算子，如果用“最大隸屬原則”判斷，顯然都應(yīng)該屬于“經(jīng)濟類”；如果用“域值法”（=0.6）判斷，也應(yīng)該都屬于“經(jīng)濟類”。結(jié)果分析由上述算例可以看出，若用“最大隸屬原則”判斷，取=0.68，采用M(,)算子的算法就無法對此網(wǎng)頁歸類了，而采用M(, )算子卻可以對網(wǎng)頁正確歸類。另外，采用M(, )算子的結(jié)果區(qū)分效果比較明顯，與人工歸類的結(jié)果比較接近。由此可見，采用M(, )算子的算法明顯優(yōu)于采用M(,)算子的算法。本文的實例網(wǎng)頁最后得出的與“經(jīng)濟類”網(wǎng)頁的貼近值僅0.8，比理想值（人工估計為0.9）偏低了了一些，與其他類別的貼近值也存在一些偏差。這是因為本文中舉的例子為了簡單起見，訓(xùn)練文本才48篇，導(dǎo)致計算機訓(xùn)練不足；另外，待歸類網(wǎng)頁過于簡單。這些都導(dǎo)致了歸類結(jié)果與理想值的偏差,在實際情況下，這些問題都可以避免。