WEb頁面自動分類系統(tǒng)的設(shè)計與實現(xiàn) 計算機專業(yè)

1、WEb頁面自動分類系統(tǒng)的設(shè)計與實現(xiàn)摘要：隨著科學(xué)技術(shù)的飛速發(fā)展，我們進入了數(shù)字信息時代。互聯(lián)網(wǎng)作為世界上最大的信息銀行，已成為人們獲取信息的最重要手段。由于網(wǎng)絡(luò)上的信息資源有巨大的、動態(tài)的、異構(gòu)的、半結(jié)構(gòu)化的特點,缺乏統(tǒng)一的組織和管理,所以如何快速、準(zhǔn)確地從大量的信息資源找到你所需的信息已經(jīng)成為了網(wǎng)絡(luò)用戶急需解決一個大問題。因此，網(wǎng)絡(luò)信息的收集和分類已經(jīng)成為一個熱門話題。傳統(tǒng)的Web信息獲取目標(biāo)是盡可能多地收集信息頁面，甚至是Web上的全部資源，在這個過程中，它并不太關(guān)注抽樣順序，而是頁面的主題。這使得收集的頁面的內(nèi)容過于雜亂，大部分的利用率都很低，這極大地消耗了系統(tǒng)資源和網(wǎng)絡(luò)資源。這需要有效

2、的收集方法來減少收集的混亂和重復(fù)。同時，有必要對所收集的網(wǎng)頁進行自動分類，以創(chuàng)建一個更高效、更高效的搜索引擎。網(wǎng)絡(luò)分類是組織和管理信息的有效手段。它能在很大程度上解決信息雜亂的問題，方便用戶準(zhǔn)確定位所需信息。傳統(tǒng)的操作模式是組織和管理人工分類。隨著互聯(lián)網(wǎng)上各種信息的快速增長，手工處理信息是不現(xiàn)實的。因此，web頁面的自動分類是一種具有重要實用價值的方法，是組織和管理數(shù)據(jù)的有效手段。這也是本研究的一個重要部分。關(guān)鍵詞：網(wǎng)頁內(nèi)容提取，文本自動分類，自動分類算法1. 引言目前，中國互聯(lián)網(wǎng)上的網(wǎng)站數(shù)量巨大，增長迅速。這些網(wǎng)站需要分類以便更好更快的查詢信息。雖然也有谷歌等目錄,雅虎、搜狐和其他類別的中國

3、網(wǎng)站分類,但由于使用人工方法進行分類,低效率,更新速度慢,無法完成當(dāng)前巨大的大型中文網(wǎng)站報道,所以中文網(wǎng)頁自動分類技術(shù)已經(jīng)成為了在線文本數(shù)據(jù)組織和管理的關(guān)鍵技術(shù)。在本研究的背景下，雖然網(wǎng)頁自動分類精度不高，但基于信息檢索內(nèi)容的網(wǎng)頁自動分類研究，Web數(shù)據(jù)挖掘應(yīng)用仍具有深遠的意義。2. 文本自動分類的研究現(xiàn)狀在我國，自動文本分類研究始于80年代，由于中文文本之間沒有間隔，需要專門的文本分割算法，因此國內(nèi)很多學(xué)者將中文文本分割作為文本自動分類研究的重點和研究特征。作為電子工程的秘密，清華大學(xué)在1995年以語料庫相關(guān)系數(shù)作為分類依據(jù)、詞頻和詞頻及其常見搭配作為補充，使用了“停止列表”、“人工指導(dǎo)文本

4、分類”。1997年，山西大學(xué)計算機系劉凱英等人采用了三維加權(quán)算法，采用了最長匹配算法、分類詞加權(quán)、語料庫中提取詞的自動分類。隨著網(wǎng)絡(luò)信息的快速增長，網(wǎng)頁作為語料庫的自動分類已經(jīng)成為一個新的研究熱點。自動文本分類有兩類:一種是基于規(guī)則的分類方法;二是基于統(tǒng)計的分類方法?；谝?guī)則的分類方法應(yīng)用于特定的領(lǐng)域，它需要該領(lǐng)域的知識和規(guī)則庫。然而，知識和規(guī)則的制定、更新、維護和自我學(xué)習(xí)等方面存在著諸多問題，使得應(yīng)用面臨的問題越來越小?；诮y(tǒng)計方法，采用純數(shù)學(xué)運算，不要求復(fù)雜的語言知識和領(lǐng)域知識，也具有較高的準(zhǔn)確性，因此越來越受到人們的重視。自動文本分類的統(tǒng)計模型包括向量空間模型、概率模型、線性模型、非線性

5、模型和組合模型。簡而言之，在現(xiàn)有文本分類的基礎(chǔ)上，要找出分類器的文本類別(或規(guī)則、假設(shè)、模型)的描述和區(qū)分，然后使用分類器對新的非分類文本進行分類。分類方法是文本分類的核心問題，是分類器的設(shè)計?，F(xiàn)在,研究人員已經(jīng)提出了很多有效的從不同角度的文本分類方法,這些方法大多是基于機器學(xué)習(xí)的方法,分為線性分類器根據(jù)其分類的原則,統(tǒng)計學(xué)習(xí)分類器,基于分類器和決策樹方法的例子,神經(jīng)網(wǎng)絡(luò)和支持向量機(SVM)方法,等。如Rocchio方法屬于線性分類器,樸素貝葉斯分類器是一個典型的統(tǒng)計學(xué)習(xí)分類器,K最近鄰分類器的算法是基于實例,ID3算法是決策樹的一種基本方法,支持向量機和神經(jīng)網(wǎng)絡(luò)從經(jīng)驗中學(xué)習(xí)的數(shù)據(jù)集,但神經(jīng)

6、網(wǎng)絡(luò)在某種意義上是一種啟發(fā)式的學(xué)習(xí)機器,本身有很多的經(jīng)驗,和支持向量機有嚴(yán)格的數(shù)學(xué)理論基礎(chǔ),是一個通用的知識發(fā)現(xiàn)方法,已成為一個研究熱點領(lǐng)域的文本分類。3. 網(wǎng)頁分類難點及突出問題Web頁面分類是在文本分類技術(shù)中發(fā)展起來的，但是相對于文本分類的網(wǎng)頁分類問題比較困難，需要考慮更多的因素，這一特點主要是由Web特性決定的。網(wǎng)頁分類所面臨的突出問題主要包括以下幾個方面:1頁格式多樣化:多種格式,和相同的web頁面的格式有多種標(biāo)準(zhǔn),同時因為網(wǎng)頁和內(nèi)容的寫作風(fēng)格變化很大,所以如何解析不同格式、不同網(wǎng)絡(luò)的網(wǎng)頁預(yù)處理的困難。2 .模糊分類和主題:網(wǎng)絡(luò)知識體系的異常發(fā)展迅速，各種新的知識結(jié)構(gòu)，如果培訓(xùn)語料庫沒

7、有更新，導(dǎo)致網(wǎng)頁無法分類。3網(wǎng)頁去噪:有很多與網(wǎng)頁主題無關(guān)的噪聲信息，如何提高去噪算法的性能是一個有待研究的問題。web頁面結(jié)構(gòu)信息:網(wǎng)頁包含豐富的結(jié)構(gòu)信息，除了純文本之外，還有其他一些內(nèi)容有助于分類。如Hn與頁面的標(biāo)題和標(biāo)題和移動后標(biāo)題、元標(biāo)簽名稱屬性和屬性值的內(nèi)容是一個描述web頁面上的頁面的鏈接指向的內(nèi)容可能與網(wǎng)頁相關(guān)內(nèi)容,網(wǎng)頁上的信息分類有貢獻,有可能是噪音,綜合利用上述特性設(shè)計的分類算法是一個網(wǎng)頁分類的關(guān)鍵也是困難的。5。缺乏評價標(biāo)準(zhǔn):web分類系統(tǒng)沒有統(tǒng)一的評價標(biāo)準(zhǔn)，常用的評價指標(biāo)具有準(zhǔn)確性和召回率。網(wǎng)頁的數(shù)量非常大，簡單的召回率沒有真正的價值，而準(zhǔn)確性的含義也應(yīng)該相應(yīng)調(diào)整;數(shù)據(jù)庫

8、大小、索引方法、用戶界面、響應(yīng)時間等應(yīng)納入評價指標(biāo)體系中。此外，文本分類中的一些問題，如特征選擇和分類效率，也會影響到網(wǎng)頁的分類。4. 自動分類算法目前，在web頁面的自動分類中已經(jīng)提出了許多有效的文本分類方法，并介紹了一些典型的分類算法。4.1 線性分類器線性分類器的原理是將分類系統(tǒng)中的每個類別映射為一個特征向量，向量和表示屬于同一向量空間的向量，將分類問題劃分為更多的網(wǎng)頁和類別向量相似度。某一網(wǎng)頁向量與某一類別的相似度越高，該頁屬于該類的概率就越大。最常用的度量相似度的方法是向量之間的夾角余弦。線性分類器的原理是將類別體系中每一個類別都映射為一個特征向量，該向量與表示網(wǎng)頁的向量屬于同一個向

9、量空間，則分類問題轉(zhuǎn)化為比較網(wǎng)頁向量與類別向量的相似度問題。某一個網(wǎng)頁向量與某個類別的向量相似度越高，則網(wǎng)頁屬于該類別的概率越大。最常用于相似度度量的方法是向量之間的夾角余弦。假設(shè)某一類別 cj 的特征向量表示為：V(cj)(wj1, wj2, wjn)，任一網(wǎng)頁的向量表示為：V(di)(wi1, wi2, win)，V(cj)與 V(di)屬于同一向量空間 Rn，用夾角余弦法表示 V(di)與 V(cj)的相似度如下式所示：nSim ( di , cj) =Wik ×Wjkk =1nn( W 2 ik )( W 2 jk )k =1k =1線性分類器學(xué)習(xí)算法的主要任務(wù)是建立類的特征

10、向量。根據(jù)特征向量法的不同，將線性分類器分為批量學(xué)習(xí)法和在線學(xué)習(xí)法。小組學(xué)習(xí)方法通過初始學(xué)習(xí)過程建立分類器，然后逐個測試每個新樣本來調(diào)整分類器，這種方法適合開始時我找不到足夠的樣本。4.2 統(tǒng)計學(xué)習(xí)分類器基于統(tǒng)計學(xué)習(xí)方法的分類器被稱為統(tǒng)計學(xué)習(xí)分類器，最典型的統(tǒng)計學(xué)習(xí)分類器是樸素貝葉斯分類器。樸素貝葉斯分類器的原理是在假設(shè)文本中詞的分布相互獨立的的前提下使用類別的先驗概率和詞的類別的條件概率分布來計算未知文本屬于一種概率。設(shè)某一待分類網(wǎng)頁向量 d=( d1, dM)，訓(xùn)練網(wǎng)頁集 D:d1, dN，類別集合 C:c1, c1,ck，類別 cj 的樣本數(shù)目為 Nj，則根據(jù)貝葉斯公式，網(wǎng)頁 d 屬于

11、Cj 的概率表示為：p(C j | d ) = p (C j )iM=1 p (di | Cj)在訓(xùn)練樣本集的基礎(chǔ)上，大多數(shù)學(xué)習(xí)方法建立了目標(biāo)函數(shù)的清晰的泛化描述?；趯嵗膶W(xué)習(xí)方法只是存儲訓(xùn)練樣本。將工作的泛化從這些實例中延遲到必須對新實例進行分類，每當(dāng)我遇到一個新的學(xué)習(xí)機器進行分類時，它會用先前存儲的實例分析新的實例，目標(biāo)類之間的關(guān)系，并將一個值分配給一個新實例?；趯嵗膶W(xué)習(xí)方法包括k近鄰法(KNN)和局部加權(quán)回歸法。K-近鄰法是基于實例的學(xué)習(xí)中最基本的一種方法。該算法假定所有的實例對應(yīng)于 n 維空間 Rn 中的點。一個實例的最近鄰是根據(jù)距離定義的。令任意的實例 x 表示為(t1 (x)

12、,t2 (x),，tn(x)，其中 tk(x)表示實例 x 的第 k 個權(quán)值，兩個實例 xi 和 xj 間的距離定義為 d(xi,xj),常用的距離有海明距離、余弦距離，歐氏距離等，其中，最常用的是歐氏距離，用下式表示：nd (xi , xj ) =(t k (xi ) t k (xj)2k =1K-近鄰法可以看作是在單一的實例上逼近目標(biāo)函數(shù) f(x)，局部加權(quán)回歸就是這種方法的推廣。它在環(huán)繞新實例 x 的局部區(qū)域內(nèi)為目標(biāo)函數(shù)建立明確的逼近，具體地說局部加權(quán)回歸的一般方法是建立一個逼近 f ,使 f 擬合環(huán)繞 x 的鄰域內(nèi)的訓(xùn)練樣本，并用這個逼近來計x 的類別值?；趯嵗膶W(xué)習(xí)方法也被稱為負(fù)面

13、學(xué)習(xí)方法，因為這種方法的所有處理都經(jīng)常被延遲。這種方法的缺點是缺乏必要的訓(xùn)練，降低了分類速度。這種方法的優(yōu)點是，這種方法不是對整個實例空間中目標(biāo)函數(shù)的一次性估計，而是對每個新實例進行局部和不同的估計。當(dāng)目標(biāo)函數(shù)是復(fù)雜的，但可以用不太復(fù)雜的局部逼近來描述，它有一個顯著的優(yōu)勢。5. 設(shè)計一個 Rocchio 與 KNN 相結(jié)合的分類器不同的分類方法有其優(yōu)點和局限性，因此通常需要根據(jù)具體的應(yīng)用背景選擇方法。在本文中,我們研究了分類系統(tǒng)是面向大型跨學(xué)科組web頁面,實時要求高,所以為了確保一定,分類精度的基礎(chǔ)上,盡可能提高速度的分類系統(tǒng)的研究重點。基于向量空間模型，KNN方法通常被認(rèn)為是分類精度最好的

14、方法之一，但KNN方法存在計算時間復(fù)雜度的分類問題，特別是當(dāng)訓(xùn)練樣本容量較大時，其分類速度是無法承受的。Rocchio方法在向量空間模型框架中是最簡單、最有效的分類方法，因為方法簡單，分類速度快，在許多實時處理能力中要求較高的字段用于它，但其分類精度不高。本文采用了羅基奧法和KNN法的優(yōu)點，設(shè)計了一種羅喬和KNN的分類器，或Rocchio-KNN分類器。5.1 分類器的分析與設(shè)計分類器的主要功能是訓(xùn)練學(xué)習(xí)和自動分類，從訓(xùn)練學(xué)習(xí)和自動分類兩個方面進行了討論。Rocchio-KNN分類器的具體設(shè)計方法。KNN方法沒有訓(xùn)練學(xué)習(xí)階段，在訓(xùn)練學(xué)習(xí)階段采用了Rocchio方法。Rocchio方法的關(guān)鍵問題

15、是構(gòu)建一個所謂的類中心向量，它可以更好地描述類的特征。類別中心向量的權(quán)重由三個部分組成，即初始權(quán)值、正樣本的平均權(quán)重和反例的平均權(quán)重。由于本文采用了類別獨立性的特征選擇方案，網(wǎng)頁的表示也與類別無關(guān)，因此可以忽略反例平均權(quán)重的影響。在自動分類階段，降低KNN的時間復(fù)雜度是一個關(guān)鍵問題。為了解決這個問題，我們可以從兩個方面著手，減少矢量比較的冗余計算，縮小測試樣本的比較。減少冗余計算向量比較基礎(chǔ)的測試web頁面的權(quán)重向量是基于訓(xùn)練集的關(guān)鍵建筑,所以一定有很多的重量值為0,與培訓(xùn)頁面相比,這些東西,沒有實際意義,因此不能參與操作?？s小測試樣本比較的范圍是一個困難的問題，其中包括兩個選擇，一個是分類抽

16、樣方法，以縮小事實的范圍，證明它難以操作，因為不確定抽樣標(biāo)準(zhǔn)。第二種是將訓(xùn)練樣本與有限類別進行比較，以減少比較，這顯然是一種更可行的方法，問題是如何獲得可比較的類別。訓(xùn)練學(xué)習(xí)階段生成的類特征向量是一種很明顯的思維方式，因此可以首先對測試樣本進行測試。類特征向量在相似度上進行比較，然后根據(jù)比較結(jié)果過濾出一些類別，然后在其余分類中進行篩選。KNN方法用于分類。這種方法的主要問題是分類的過濾原則。這是一個簡單的方法。通過一組測試樣本向量和類別特征向量相似閾值篩選，低于閾值類別篩選，并對測試樣本繼續(xù)和高于訓(xùn)練樣本類別的閾值進行比較?本文設(shè)計了一種多閥值方案，計算每個類別的類相似閾值，計算方法為。找出某

17、一類別中所有訓(xùn)練樣本的平均值和類別特征向量的相似性，作為類相似閾值的參考值。顯然，這項工作應(yīng)該在訓(xùn)練階段完成。為了保證分類的準(zhǔn)確性，需要對KNN方法進行適當(dāng)?shù)恼{(diào)整。篩選器類別的范圍，因此引入了一個中介因子，并且類引用值減去中介因子，成為該類的閥門值。可調(diào)對于解因子和K值的確定，沒有好的方法來使用預(yù)先確定的初始值的初始值，然后通過試錯。確定了調(diào)整的方法。5.2分類器的具體實現(xiàn)。根據(jù)以上分析和設(shè)計，Rocchio-KNN分類器的具體實現(xiàn)步驟如下:在訓(xùn)練階段，計算每個類別的特征向量，并根據(jù)特征向量計算出各種其他相似閥。價值。2。該測試頁面被分類表示為一個向量形式，而余弦距離公式被用來計算相似度。3保

18、持以上類別相似性閾值類別的訓(xùn)練樣本,形成新的訓(xùn)練樣本集。4初始化集合為空集,每個相應(yīng)的測試頁面與培訓(xùn)網(wǎng)絡(luò)距離和網(wǎng)頁標(biāo)志。5簡化測試樣本向量,只保留重量值和項不為零的位置,計算所有樣本的測試樣品和這個距離,計算的結(jié)果和培訓(xùn)頁面標(biāo)識插入。6項目根據(jù)距離升序排序,前K計算,確定測試的類型的網(wǎng)站。5.3 多分類問題的解決使用上述分類算法構(gòu)造分類器，計算網(wǎng)頁的相關(guān)性和所有類別，并將頁面劃分為相關(guān)。在最大的類別中，這樣的分類器被稱為單一分類器。事實上，分類系統(tǒng)中的類別并不是完全對等的。例如，“文化”和“教育”類是相互重疊的，所以一定有什么東西不是。其中一個類別，也屬于其他類別的網(wǎng)頁，稱為多分類。本文利用相

19、關(guān)閾值來解決多分類問題。在實際進行分類時，計算web頁面與各種類別之間的相關(guān)性。將頁面分配給關(guān)聯(lián)大于類別相關(guān)閾值的類別。相關(guān)性的計算方法是去掉最大值。值的符號。在此基礎(chǔ)上，關(guān)鍵問題是確定類閾值，閾值的確定是困難的。理論上，它只能通過反復(fù)實驗來確定。以c類為例，本文確定了類別階段。閾值的解決方法是選擇一定數(shù)量的c樣本，并分別計算每個樣本和c之間的相關(guān)性。并計算所有相關(guān)度的平均值 p，如果設(shè)類別相關(guān)度閥值為 y，則 y = p + 。通過反復(fù)實驗不斷調(diào)整 的值，從而取得較優(yōu)的類別閥值。5.4 實驗與分析為了驗證Rocchio- knn方法的有效性，本文采用了Rocchio- knn方法和Rocchio。該方法和KNN方法實現(xiàn)了分類，從而進行了比較分析，在此基