基金項(xiàng)目:國(guó)家自然科學(xué)基金(the National Natural Science Foundation of China under Grant No.10671045)

[摘 要] 針對(duì)Html網(wǎng)頁結(jié)構(gòu)的特點(diǎn)，網(wǎng)頁的不同標(biāo)記信息所轄的特征項(xiàng)包含不同的類別信息，通過抽取網(wǎng)頁不同標(biāo)記信息內(nèi)的特征項(xiàng)并賦予不同權(quán)重來表明其重要程度。實(shí)驗(yàn)證明該方法比單獨(dú)依賴網(wǎng)頁內(nèi)容信息的分類在效果上有所提高。

[關(guān)鍵詞] 網(wǎng)頁分類 特征項(xiàng) 權(quán)重計(jì)算

一、引言

隨著互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，web網(wǎng)已經(jīng)成為一個(gè)巨大的信息源，成為人們獲取信息的重要來源。由于Web網(wǎng)頁中蘊(yùn)藏的信息資源內(nèi)容廣泛，形式各異，有效組織和管理這些資源尤為重要，通過網(wǎng)頁的自動(dòng)分類可以更好地對(duì)其進(jìn)行組織和管理，加快信息檢索的速度。然而，web頁面中存在著大量的HTML格式的無結(jié)構(gòu)數(shù)據(jù)和少量XML格式的半結(jié)構(gòu)數(shù)據(jù)。一方面，這些結(jié)構(gòu)性信息常是頁面中包含的非主題信息的內(nèi)容，網(wǎng)頁必須剔除這些無用的信息后才能形成有用的文本信息。另一方面，這些結(jié)構(gòu)性信息又包含著重要的分類信息，利用好這些信息能有效提高分類效果。

本文對(duì)網(wǎng)頁的標(biāo)記進(jìn)行了分類，對(duì)位于不同標(biāo)記內(nèi)的特征項(xiàng)賦予不同的權(quán)重系數(shù)，在分類過程中重新調(diào)整其權(quán)值，以期改善分類器的性能。

二、網(wǎng)頁特征分析

與純文本數(shù)據(jù)不同，網(wǎng)頁數(shù)據(jù)是一種半結(jié)構(gòu)化的數(shù)據(jù)。在HTML文檔中，正文信息是嵌入在HTML標(biāo)記中的，HTML文檔的標(biāo)記具有嵌套結(jié)構(gòu)。仔細(xì)分析HTML文件的格式，可以發(fā)現(xiàn)其中有一些標(biāo)記信息對(duì)分類是有益的。(1)頁面的標(biāo)題，無論哪種類型的文本，一般都會(huì)有標(biāo)題，通常標(biāo)題部分特征信息的量都比文章其余部分要大，標(biāo)題一般是網(wǎng)頁內(nèi)容的精煉概括，字?jǐn)?shù)較少，除很少的一些虛詞外基本上都是網(wǎng)頁的特征詞;(2)分級(jí)標(biāo)題，分級(jí)標(biāo)題是網(wǎng)頁內(nèi)容的基本框架，是網(wǎng)頁局部?jī)?nèi)容的概括和提煉，在一定程序上強(qiáng)調(diào)了網(wǎng)頁內(nèi)容;(3)字體格式，在一些網(wǎng)頁上，常對(duì)重要的文本加以修飾，突出其重要性，如將關(guān)鍵詞句的字號(hào)加大，對(duì)其加粗、加下劃線及加斜，或者附以不同的顏色。

為了精確表示網(wǎng)頁的結(jié)構(gòu)，定義標(biāo)記集S={TL，HD，F(xiàn)S，F(xiàn)L，F(xiàn)C，UR}。

TL:標(biāo)記為TL的特征項(xiàng)是文中的標(biāo)題部分;

HDi:標(biāo)記為HD的特征項(xiàng)是文中的分級(jí)標(biāo)題;

FSi:標(biāo)記為FS的特征項(xiàng)為非基準(zhǔn)字號(hào);

FL:標(biāo)記為FL的特征項(xiàng)被字體格式化處理;

FC:標(biāo)記為FC的特征項(xiàng)為非基準(zhǔn)顏色。

說明:標(biāo)題部分可以看成是零級(jí)標(biāo)題，因此TL和HDi的權(quán)重系數(shù)可統(tǒng)一處理;FSi的權(quán)重系數(shù)為字號(hào)減去基準(zhǔn)字號(hào)的絕對(duì)值，其中，基準(zhǔn)字號(hào)l是文本長(zhǎng)度最長(zhǎng)的標(biāo)簽部分所用的字號(hào);FL權(quán)重系數(shù)為3;FC的顏色值為非基準(zhǔn)值u時(shí)取2，其中，基準(zhǔn)值u為文本長(zhǎng)度最長(zhǎng)的標(biāo)簽部分所用的顏色值。

三、關(guān)鍵技術(shù)

1.特征項(xiàng)抽取

本文的特征提取分兩步進(jìn)行，第一步按常規(guī)方法去除結(jié)構(gòu)性標(biāo)簽，獲取純文本內(nèi)容，用成熟的特征選擇方法互信息MI得到一個(gè)初始特征集合T?；バ畔I公式為:(1)

其中:A為t和c同時(shí)出現(xiàn)的次數(shù);B為t出現(xiàn)而c沒有出現(xiàn)的次數(shù);C為c出現(xiàn)而t沒有出現(xiàn)的次數(shù)。N為所有文檔數(shù)。如果t和c不相關(guān)，則MI(t，c)值為0。如果有m個(gè)類，于是對(duì)于每個(gè)t會(huì)有m 個(gè)值，取它們的平均，就可得到特征選取所需的一個(gè)線性序。互信息值大的特征被選取的可能性大。

第二步對(duì)格式化文本進(jìn)行提取，抽取格式特征項(xiàng)集合，并按表1模板對(duì)特征項(xiàng)進(jìn)行標(biāo)記，以備后續(xù)處理。

2.特征權(quán)重計(jì)算

(1)特征表示

文本分類中的文本表示主要采用向量空間模型(vector space mode，VSM)。向量空間模型的基本思想是以(W1，W2，W3，…，Wm)向量來表示文本，其中Wi為第i個(gè)特征項(xiàng)的權(quán)重 。n個(gè)文本組成的文本集合D={d1，d2，…，dn}被m個(gè)特征項(xiàng)W1，W2，W3，…，Wm索引，可表示成一個(gè)m×n的特征項(xiàng)文本矩陣A，A={d1，d2，…，dn}，其中di=(W1，W2，W3，…，Wm)，如下所示: (2)

其中:每一列di代表一個(gè)文本;一行Yj 代表特征項(xiàng)在各個(gè)文本中的權(quán)值.特征項(xiàng)權(quán)重的計(jì)算方法主要運(yùn)用TF-IDF公式: (3)

式中:W(t，d)表示特征詞t在文本d中的權(quán)重，tf(t，d)為特征詞t在文本d中的詞頻，N為訓(xùn)練集中文本的總數(shù)，nt為訓(xùn)練文本集中出現(xiàn)詞t的文本數(shù)，分母為歸一化因子。

(2)特征加權(quán)

考慮Web網(wǎng)頁的描述信息中出現(xiàn)的關(guān)鍵字包含網(wǎng)頁的重要信息，對(duì)分類有較大的作用。因此，對(duì)這部分特征項(xiàng)進(jìn)行加權(quán)處理。依此權(quán)值信息表，我們對(duì)特征詞t在文檔d的權(quán)重計(jì)算公式(1)做如下改進(jìn)。

(4)

其中，表示特征項(xiàng)t被k個(gè)HTML標(biāo)記修飾權(quán)重之和。

3.特征選擇算法描述

Step One:對(duì)網(wǎng)頁預(yù)處理，進(jìn)行分詞及分詞后的預(yù)處理，獲取初始特征集;對(duì)網(wǎng)頁進(jìn)行格式特征抽取，獲取格式特征集合;

Step Two:對(duì)于初始特征集中的每個(gè)詞，利用式(6)計(jì)算特征項(xiàng)和類別的互信息值;

Step Three:對(duì)互信息值進(jìn)行排序， 根據(jù)設(shè)定閾值T對(duì)每個(gè)類別提取若干個(gè)貢獻(xiàn)最大的特征項(xiàng)，刪除大部分對(duì)分類意義不大的特征項(xiàng)，得到特征項(xiàng)的最終集合T=(t1，t2，……，tm)(m

Step Four:根據(jù)式(4)計(jì)算每個(gè)特征項(xiàng)的權(quán)值wi;

Step Five:生成特征向量表，每篇文檔表示為向量(tl，wl;t2，w2;……;tn，wn)，ti為特征項(xiàng)，wi為對(duì)應(yīng)的權(quán)值。

四、試驗(yàn)分析與結(jié)果

1.分類算法

本文采用KNN分類算法進(jìn)行實(shí)驗(yàn)，該算法的是在給定新文本后，考慮在訓(xùn)練文本集中與該新文本距離最相近的K篇文本，根據(jù)這K篇文本所屬文本所屬的類別判定新文本所屬的類別。計(jì)算公式為: (5)

其中，相似度計(jì)算公式為:(6)

為類別屬性函數(shù)，定義為:(7)

2.實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)數(shù)據(jù)是從新浪網(wǎng)、雅虎網(wǎng)等多個(gè)網(wǎng)站上采集的中文網(wǎng)頁數(shù)據(jù)集，從中選取了政治、交通、環(huán)境、經(jīng)濟(jì)、藝術(shù)、娛樂等六個(gè)類別共1800篇文章，其中每個(gè)類別300篇文章;每類選取200個(gè)網(wǎng)頁作為訓(xùn)練集，其余100個(gè)網(wǎng)頁作為測(cè)試集。

在相同環(huán)境下，我們分別對(duì)兩種特征選擇方法進(jìn)行了對(duì)比實(shí)驗(yàn)，結(jié)果見表1。其一是采用傳統(tǒng)TF-IDF特征選擇方法直接進(jìn)行訓(xùn)練，計(jì)算權(quán)重;其二是考慮網(wǎng)頁結(jié)構(gòu)特征的重要性，將位于網(wǎng)頁某些結(jié)構(gòu)標(biāo)簽的特征項(xiàng)進(jìn)行加權(quán)，并將加權(quán)處理融合到TF-IDF方法中。實(shí)驗(yàn)結(jié)果表明，第二種方法能取得良好的分類效果。

五、結(jié)束語

網(wǎng)頁的自動(dòng)分類在信息檢索領(lǐng)域中均占有十分重要的意義。然而，網(wǎng)頁分類不同于普通文本的分類，網(wǎng)頁中包含大量的網(wǎng)頁標(biāo)記信息，這些標(biāo)記信息包含重要的分類信息，充分挖掘這些信息有利于提高網(wǎng)頁的可分性。本文正是在對(duì)這些標(biāo)記對(duì)信息研究的基礎(chǔ)上實(shí)現(xiàn)正文信息的選取和表示的。實(shí)驗(yàn)已表明所用方法的有效性和可用性。在后續(xù)的研究中，將對(duì)網(wǎng)頁特殊描述信息中的特征項(xiàng)權(quán)值系數(shù)確定方法進(jìn)行研究，以求更加合理的加權(quán)方法。

參考文獻(xiàn):

[1]Wang Lian，David Wai-lok Cheung.An efficient and scalable algorithm for clustering XML documents by structure [J].IEEE Trans on Knowledge and Data Engineering，2004，16(1):82～96

[2]初建崇 劉培衛(wèi) 王衛(wèi)玲:Web文檔中詞語權(quán)重計(jì)算方法的改進(jìn)[J].計(jì)算機(jī)工程與應(yīng)用，2007，43(19): 192～194，198

[3]呼聲波 劉希玉:網(wǎng)頁分類中特征提取方法的比較與改進(jìn)[J].山東師范大學(xué)學(xué)報(bào)(自然科學(xué)版)，2008，23(3): 35～37

[4]胡 健 陸一嗚 馬范援:基于HTML文檔結(jié)構(gòu)的向量空間模型的改進(jìn)[J].情報(bào)學(xué)報(bào)，2005(4):433～437

[5]何中市 劉 里:基于上下文關(guān)系的文本分類特征描述方法[J].計(jì)算機(jī)科學(xué)，2007，34(5):183～186