網(wǎng)頁(yè)去重的改進(jìn)算法

王 靜 ,劉觀寧 ，張鈺輝

(1.西安電子科技大學(xué) 計(jì)算機(jī)學(xué)院,陜西 西安 710071;2.安徽省技術(shù)創(chuàng)新服務(wù)中心,安徽 合肥 230001)

隨著互聯(lián)網(wǎng)的高速發(fā)展，Web已經(jīng)成為最大的信息來(lái)源。但是如何獲取這些Web信息為我所用則是大家面臨的共同問(wèn)題。網(wǎng)頁(yè)去重是Web網(wǎng)頁(yè)信息處理的重要環(huán)節(jié)，只有在對(duì)網(wǎng)頁(yè)的去重基礎(chǔ)上才可以準(zhǔn)確處理網(wǎng)頁(yè)中的信息。本文介紹網(wǎng)頁(yè)的去重算法。

提取出來(lái)的網(wǎng)頁(yè)，有些內(nèi)容可能很相似，對(duì)于這些內(nèi)容相似的網(wǎng)頁(yè)沒(méi)必要保存。針對(duì)系統(tǒng)中的人才招聘網(wǎng)頁(yè)更是必要：一個(gè)公司的招聘信息很可能會(huì)在數(shù)十家招聘網(wǎng)站以及自己公司主頁(yè)同時(shí)發(fā)布，所以有必要對(duì)這些網(wǎng)頁(yè)去重。

1 網(wǎng)頁(yè)的特征表示

詞、詞組和短語(yǔ)是組成文檔的基本元素，在不同內(nèi)容的文檔中各詞條出現(xiàn)頻率有一定的規(guī)律性，不同的特征詞條可以區(qū)分不同內(nèi)容的文本。因此可以抽取一些特征詞條構(gòu)成特征矢量，在VSM[1]模型中把 t1,t2,…,tn看成一個(gè)N維的坐標(biāo)系 w1(d),w2(d),…,wn(d)為相應(yīng)的坐標(biāo)值,因而文本d被看成是N維空間中的一個(gè)規(guī)范化特征矢量：V(d)=(t1,w1(d);…;ti,wi(d);…;tn,wn(d);)

對(duì)于網(wǎng)頁(yè)，ti就表示特征詞條，wi(d)就是文本d中ti的權(quán)值。用這個(gè)特征矢量來(lái)表示網(wǎng)頁(yè)文本。在網(wǎng)頁(yè)表示中，對(duì)任一特征而言有兩個(gè)因素影響特征的權(quán)值。一是詞在HTML文檔中出現(xiàn)的詞頻，另一個(gè)是該詞在該文檔中出現(xiàn)的位置。詞頻指的是某一詞條在文檔中出現(xiàn)的頻率，頻率越高 (當(dāng)然不包括那些停用詞)則說(shuō)明該詞越重要,越能代表該網(wǎng)頁(yè)的內(nèi)容。對(duì)于網(wǎng)頁(yè)的主題包含在之間的詞組比在之間的詞組更具有代表性。因此本文提出了一種把該詞出現(xiàn)的頻率以及該詞出現(xiàn)的位置相結(jié)合的權(quán)重計(jì)算方法，能夠更有效地表示網(wǎng)頁(yè)。公式如下：

這里α=2,α=3,α=4和α=6都是經(jīng)過(guò)實(shí)驗(yàn)得到的。實(shí)驗(yàn)結(jié)果也證明了此改進(jìn)算法對(duì)網(wǎng)頁(yè)分類正確率的有效性。

2 網(wǎng)頁(yè)的特征提取

使用VSM模型表示法時(shí)，表示文檔的特征向量的維數(shù)會(huì)達(dá)到成百上千。同時(shí)，具有代表性的特征以及詞匯特征也會(huì)很大，并且是冗余的。這種未經(jīng)處理的文本矢量會(huì)給后繼的處理工作帶來(lái)巨大的計(jì)算開(kāi)銷。特征提取主要用于排除那些被認(rèn)為無(wú)關(guān)或關(guān)聯(lián)性不大的特征。基于VSM常用的特征項(xiàng)提取算法有：詞頻、信息增益、互信息量[2]及X2統(tǒng)計(jì)量[3]等。在中文文本分類中使用較多的是互信息量和X2統(tǒng)計(jì)量。

(1)互信息量

互信息是信息論中的概念，它用于度量一個(gè)消息中兩個(gè)信號(hào)之間的相互依賴程度。在特征選擇領(lǐng)域中人們經(jīng)常利用它來(lái)計(jì)算特征t與類別c之間的依賴程度，將特征t與各個(gè)類的互信息融合起來(lái)作為特征的權(quán)重。特征t與第i類的互信息計(jì)算公式如下（兩個(gè)公式等價(jià)）：

其中：tk表示任意特征項(xiàng) (特征詞)；ci表示任意類別；g為訓(xùn)練集中所有文本數(shù)；P(tk,ci)為tk和ci同時(shí)出現(xiàn)的概率（即對(duì)于任意一篇文章X,含有特征項(xiàng)tk且文章X屬于類別 ci的概率)；P(tk)為文章中出現(xiàn)特征項(xiàng) tk的概率；P(ci)為文章屬于類別ci的概率，類似地不難理解

(3)聯(lián)合特征提取方法

雖然X2統(tǒng)計(jì)量法是目前常用的特征提取方法之一，但該方法仍存在一些缺點(diǎn)，如它提高了在指定類中出現(xiàn)少而在其他類中出現(xiàn)較高的特征的權(quán)重以及降低了低頻詞的權(quán)重等。根據(jù)公式(3)～(5)，對(duì)于指定類中出現(xiàn)頻率低而其他類中出現(xiàn)頻率高的詞語(yǔ)，當(dāng)P(t，ci)→0，而 P(t)和 P(ci)均不趨向于零，則 P(t，ci)/(P(t)P(ci))→0，于是I(t,c)將趨向于負(fù)無(wú)窮，故這些詞語(yǔ)會(huì)被過(guò)濾掉。根據(jù)式(6),對(duì)于有相同 logPr(t|c)的詞語(yǔ)來(lái)說(shuō)，低頻詞的權(quán)重將更高，即在多類中普遍出現(xiàn)的高頻詞的權(quán)重將比只在特定類中出現(xiàn)的低頻詞的權(quán)重低。這樣就很好地解決了上述問(wèn)題，所以本文提出一種聯(lián)合特征提取的方法，該方法綜合了X2統(tǒng)計(jì)量法和互信息量法,可以獲得較好的結(jié)果。該方法可以描述為：

其中E1(t,c)是使用X2統(tǒng)計(jì)量法得到的特征權(quán)重；E2(t,c)為使用互信息量法得到的特征權(quán)重。

3 SOM神經(jīng)網(wǎng)絡(luò)算法

3.1 向量歸一化

向量的歸一化是對(duì)輸入向量進(jìn)行預(yù)處理的第一步。其目的是把所有不同長(zhǎng)短和方向的向量變成方向不變、長(zhǎng)度為1的單位向量。設(shè)：

在網(wǎng)絡(luò)訓(xùn)練過(guò)程開(kāi)始時(shí)，定義獲勝節(jié)點(diǎn)的鄰域節(jié)點(diǎn)是為了能使二維輸出平面上相鄰輸出節(jié)點(diǎn)對(duì)相近的輸入模式類做出特別反應(yīng)。假設(shè)本次獲勝節(jié)點(diǎn)為Nj,它在t時(shí)刻的鄰域節(jié)點(diǎn)用 NEj表示，NEj(t)是包含以 Nj中心而距離不超過(guò)某一半徑的所有節(jié)點(diǎn)。隨著訓(xùn)練過(guò)程的進(jìn)行，NEj(t)的半徑逐漸減小，最后只包含獲勝節(jié)點(diǎn) Nj本身，也就是說(shuō)在訓(xùn)練的起始階段不僅對(duì)獲勝節(jié)點(diǎn)做權(quán)值調(diào)整，而且也對(duì)其較大范圍內(nèi)的幾何鄰節(jié)點(diǎn)做相應(yīng)的調(diào)整，隨著訓(xùn)練過(guò)程的繼續(xù)進(jìn)行，與輸出節(jié)點(diǎn)相連的權(quán)向量也越來(lái)越接近其代表的模式類。這時(shí)，在對(duì)獲勝節(jié)點(diǎn)的權(quán)值進(jìn)行比較細(xì)微的調(diào)整時(shí)，只對(duì)其幾何鄰節(jié)點(diǎn)比較近的節(jié)點(diǎn)進(jìn)行相應(yīng)的調(diào)整，直到最后只對(duì)獲勝節(jié)點(diǎn)本身做細(xì)微的調(diào)整。在訓(xùn)練過(guò)程結(jié)束后，幾何上相近的輸出節(jié)點(diǎn)所連接的權(quán)向量既有聯(lián)系又有區(qū)別，這樣，保證了對(duì)某一類輸入模式獲勝節(jié)點(diǎn)能夠做出最大“響應(yīng)”，而相鄰節(jié)點(diǎn)做出“較大”響應(yīng)。幾何上相鄰節(jié)點(diǎn)代表特征上相近的模式類別。

自組織特征映射學(xué)習(xí)過(guò)程包括描述最佳匹配神經(jīng)元的選擇和描述權(quán)矢量的自適應(yīng)變化過(guò)程兩部分。SOM輸出層通常由兩維m×m的網(wǎng)格節(jié)點(diǎn)組成，從輸入向量到網(wǎng)絡(luò)輸出層的每個(gè)節(jié)點(diǎn)j的權(quán)值向量定義為w，w和xi的維數(shù)是相同的，設(shè)為d，影射節(jié)點(diǎn)的數(shù)量從數(shù)十個(gè)到數(shù)千個(gè)決定SOM正確性和概化能力。

3.2 Kohonen網(wǎng)絡(luò)訓(xùn)練算法[4～5]

其算法步聚如下：

(1)權(quán)連接初始化：初始化輸出層節(jié)點(diǎn)j的權(quán)值矢量wij時(shí)可選隨機(jī)值，初始值通常要選擇小一點(diǎn)。初始化學(xué)習(xí)率和領(lǐng)域函數(shù)時(shí)要盡量大一些，對(duì)連接輸入神經(jīng)元和輸出神經(jīng)元之間的權(quán)系數(shù)設(shè)定為小的隨機(jī)數(shù)a，一般有0

(2)網(wǎng)絡(luò)輸入模式為:

(3)在SOM迭代訓(xùn)練的每一步，從輸入數(shù)據(jù)集中隨機(jī)地選擇文本向量xi屬于實(shí)數(shù)集,計(jì)算xi和som輸出層所有節(jié)點(diǎn)j的權(quán)值向量wij的距離,最匹配的點(diǎn)用d表示,權(quán)值向量用wij表示,它是輸出層節(jié)點(diǎn)中最接近xi的。

(5)在每一步學(xué)習(xí)中CN的神經(jīng)元自適應(yīng)變化而CN外的神經(jīng)元保持不變，調(diào)整輸出節(jié)點(diǎn)所連接的權(quán)值以及幾何鄰域內(nèi)節(jié)點(diǎn)所連權(quán)值為：

式中 η(t)為標(biāo)量自適應(yīng)增益，0<η(t)<1,η(t)是單調(diào)降函數(shù),它可以是線性指數(shù)的或者是與其成反比的形式等，通常選擇η(t)=0.9(1-t/1 000)，它與 N(t)都是經(jīng)驗(yàn)函數(shù)。

(6)若還有輸入樣本數(shù)據(jù)則t=t+1轉(zhuǎn)到步驟(2)。

網(wǎng)絡(luò)輸出與權(quán)值調(diào)整競(jìng)爭(zhēng)學(xué)習(xí)算法規(guī)定，獲勝神經(jīng)元輸出為1，其余輸出為零。只有獲勝神經(jīng)元才有權(quán)調(diào)整其權(quán)向量j×w，調(diào)整后權(quán)向量為：

其中，α∈(0,1]為學(xué)習(xí)率，一般其值隨著學(xué)習(xí)的進(jìn)展而減小。可以看出，當(dāng) j≠j*時(shí)，對(duì)應(yīng)神經(jīng)元的權(quán)值得不到調(diào)整，其實(shí)質(zhì)是“勝者”對(duì)它們進(jìn)行了抑制，不允許它們興奮。另外，調(diào)整后得到的新向量不再是單位向量，因此需要對(duì)調(diào)整后的向量重新歸一化。步驟（3）完成后回到步驟(1)繼續(xù)訓(xùn)練，直到學(xué)習(xí)率α衰減到0。

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

采用以上介紹的算法,對(duì)一批數(shù)量在50～100之間的網(wǎng)頁(yè)集合進(jìn)行去重處理，集合中包含了一與此內(nèi)容完全相同或部分相同的網(wǎng)頁(yè)，將實(shí)驗(yàn)結(jié)果與人工判別的結(jié)果進(jìn)了比較，發(fā)現(xiàn)重復(fù)網(wǎng)頁(yè)的正確率達(dá)到95%以上，出現(xiàn)錯(cuò)誤的判斷的是由于網(wǎng)頁(yè)轉(zhuǎn)載時(shí)出現(xiàn)錯(cuò)碼等現(xiàn)象，有的是兩個(gè)重復(fù)網(wǎng)頁(yè)的段落排列差異太大。測(cè)試結(jié)果如圖1所示。

本文將SOM的思想和方法引入中文Web文檔的聚類問(wèn)題.探索向用戶提供高質(zhì)量的網(wǎng)頁(yè)信息具有很強(qiáng)的理論意義和實(shí)際價(jià)值。但是，這種方法的不足之處是當(dāng)網(wǎng)絡(luò)的連接過(guò)多、節(jié)點(diǎn)數(shù)目龐大時(shí)其計(jì)算量大，需要較長(zhǎng)的學(xué)習(xí)時(shí)間。所以對(duì)于上述問(wèn)題，筆者正在研究通過(guò)網(wǎng)絡(luò)剪枝技術(shù)，在不增加聚類錯(cuò)誤的前提下，剪去多余的連接和節(jié)點(diǎn)，降低特征向量空間的維數(shù)從而減少計(jì)算工作量。

[1]LINSKER R.An application of the principle of maximum information preservation to linear systems[Z].Adv.Neural Inform.Process Systems,1989,1.

[2]JUTTEN C,HERAULT J.Blind separation of sources,Part 1:An adaptive algorithm based on neuromimetic architecture[J].Signal Processing,1991,24:10.

[3]COMMON P.Independent component analysis,a new concept[J].Signal Processing,1994,36:287-314.

[4]TONAZZINI A,BEDINI L,KURUOGLU E E.Blind separation of auto-correlated images from noisy images using mrf models,.in 4th Int.Symp.on ICA and Blind Source Separation,Nara,Japan,2003.

[5]SHULMAN D,HERVE J Y.Regularization of discontinuous flow fields.in Proc.Workshop on Visual Motion,1989:81.86.

[6]BOUMAN C,SAUER K.A generalised gaussian image model for edge-preserving MAP estimation,.IEEE Trans.Image Processing,vol.2,pp.296-310,1993.2704.