基于文本過濾的Ｗｅｂ頁面檢索研究

摘要：文本過濾是信息過濾的一個研究分支，信息過濾隨著信息檢索的發(fā)展而受到關(guān)注，它是一個尋找人們感興趣的信息的處理過程。為了提高檢索web頁面的效率，把原型web頁面集合預(yù)處理為有結(jié)構(gòu)的頁面集，然后再進(jìn)行快速分類處理。

關(guān)鍵詞：web頁面檢索；相似性；文本過濾

中圖分類號：TP393文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044(2008)26-1642-03

The Research on Web searching Based on Text Filtering

ZHANG Xia

(Software College， Nanjing College of Information Technology， Nanjing 210046， China)

Abstract: Text Filtering is a research branch of Message Filtering， which is attracting more attention with development of Information Retrieval. It is a treatment process of finding information to user's interest. In order to improve efficiency of searching， Preprocess the web pages to structured， and then speed up the classification for the pages.

Key words: web page retrieval; similarity; text filtering

1 引言

文本過濾（Text Filtering）是信息過濾（Information Filtering）的一個研究分支，就是從大量的動態(tài)信息中找出最滿足用戶需求，并濾除無用信息和非法信息的過程。為了提高檢索web頁面的效率，把原型web頁面集合預(yù)處理為有組織的結(jié)構(gòu)，然后再進(jìn)行快速分類處理。

2 Web頁面檢索

Web信息檢索是指從大量Web文檔的集合C中找到與給定的查詢請求q相關(guān)的、恰當(dāng)數(shù)目的文檔子集S[1]。為了盡可能多地找出與用戶查詢請求相關(guān)的文檔信息，研究者提出了很多檢索策略：基于內(nèi)容的檢索、基于超鏈接分析的檢索和基于融合的檢索。

在頁面檢索時，一般是把用戶輸入的查詢關(guān)鍵詞或短語作為主題，來檢索頁面并進(jìn)行相關(guān)的排序，而實(shí)際上這種檢索的結(jié)果往往會有偏差。因此，提出的檢索策略把關(guān)鍵詞->文本模型轉(zhuǎn)變?yōu)殛P(guān)鍵詞->文本->文本模型，即在粗糙的檢索結(jié)果基礎(chǔ)上根據(jù)模版庫再次檢索，用以提高檢索精度。鏈接信息由通用搜索引擎的結(jié)果隱含覆蓋，主要考慮內(nèi)容上的檢索與排序情況。由原來的詞-文檔查詢分為了兩步：首先詞-文檔，然后是文檔-文檔來達(dá)到對結(jié)果提煉的目的，與此同時，在計(jì)算相似性之前利用了文本過濾的思想來減少計(jì)算復(fù)雜度。

3 基于文本過濾的頁面檢索研究與實(shí)現(xiàn)

3.1 基于ABT的快速檢索

快速檢索算法有兩大主流：有損和無損檢索算法。關(guān)于減少計(jì)算負(fù)擔(dān)的算法技術(shù)主要有三種：計(jì)算部分距離，結(jié)構(gòu)預(yù)處理以及編輯存儲原型[2]。

在查找近鄰的任務(wù)中，比較樣本向量的每一個維度是很花費(fèi)時間的，一般復(fù)雜度為nd（n為相關(guān)集合中樣本的個數(shù)，d為特征數(shù)或者維度），因此，文獻(xiàn)[3]提出一種快速的排除大部分樣本來求近鄰的方法，算法針對特征維度很高以及特征值的類型是二元的特別有效。同時，此方法在圖像識別系統(tǒng)OCR系統(tǒng)[3]中得到有效驗(yàn)證。

ABT[3]是模式識別領(lǐng)域提出來的一個預(yù)結(jié)構(gòu)的檢索算法，ABT即為加法二叉樹（additive binary tree），即對每個樣本的向量表示建一棵加法二叉樹并存儲以備查詢使用。主要思想是：利用閾值減少計(jì)算時間，在檢測所有屬性之前就能給出兩個向量匹配程度的決策。首先，粗略看一下相關(guān)集合以及匹配侯選集；接著，分析上一步過濾后的侯選集，從中選出更小的一個候選集合，然后繼續(xù)。在經(jīng)過若干步過濾之后，定下最終的侯選集。

圖1是基于ABT的快速檢索的一個例子：

對于某個向量：0101110011111011，依據(jù)建樹算法我們可以得到它的樹形結(jié)構(gòu)如下（其中，每個節(jié)點(diǎn)的值都是它孩子節(jié)點(diǎn)值的和）：

考慮一個樣本集合個數(shù)為3（n＝3）的集合，維度d＝8，以及閾值t＝2，樣本集合R={r1，r2，r3}以及查詢向量q的向量表示如下：

一般的相似檢索情況下，查詢向量與樣本集合向量的每一維都要比較，故總共需要比較24次；如果采用ABT預(yù)結(jié)構(gòu)之后，只需比較18次，其正確性證明見參考文獻(xiàn)[3]。

3.2 基于文本過濾的頁面檢索的實(shí)現(xiàn)

3.2.1 設(shè)計(jì)思想

上文中，向量的每個維度上只采用0或者1表示，即只表示某個單詞出現(xiàn)或者不出現(xiàn)，此種表示會損失一部分精度。但換個角度來想，快速檢索若不用來最終產(chǎn)生匹配集，而是用來產(chǎn)生侯選集，然后再精確計(jì)算，這不但可以減少計(jì)算量，而且又不損失精度，故本文尋求了在文本相似檢索之前用該種粗略檢索達(dá)到過濾的目的。實(shí)驗(yàn)證明，這條思路確實(shí)可行。

搜索引擎中元搜索或者主題搜索返回的結(jié)果的頁面數(shù)往往是大量的，用戶要從這些結(jié)果中找到自己需要的信息通常需要查看好幾頁或者好多條頁面，因此，本文結(jié)合了文本過濾思想，把近鄰查找分為兩步（具體的頁面檢索流程見圖2）：1）先通過文本過濾來粗略篩選頁面，用到預(yù)結(jié)構(gòu)的方法來減少計(jì)算量；2）再用余弦相似度來精確計(jì)算k個近鄰文檔。

3.2.2 文本過濾的實(shí)現(xiàn)

對于用元搜索或者歷史庫搜索得到的中間結(jié)果，根據(jù)模板庫進(jìn)行文本過濾去除一些與主題域不太相關(guān)的文檔，其中對文本建樹在檢索之前完成，過濾在檢索時完成。

1）對文本建樹：采用ABT預(yù)結(jié)構(gòu)的方法進(jìn)行文本過濾，首先是對所有的文本建立樹型結(jié)構(gòu)并存儲。文獻(xiàn)[3]的建樹算法中為建立平衡二叉樹，采取固定維度且指定是2的N次方，如維度d=256=216，考慮到文本的維度不一定是2的N次方，因此實(shí)現(xiàn)過程中采取浪費(fèi)部分空間的方案，例如：若維度256

2）過濾：對所有文本建成樹性結(jié)構(gòu)之后，就可以對此加法二叉樹一層一層的、用過濾閾值方法進(jìn)行過濾，得到大于或者等于指定數(shù)目的文檔集合。

3.2.3 精確計(jì)算實(shí)現(xiàn)

對于初步過濾后剩下的文檔集合（數(shù)目為KNum）可以采用余弦相似度精確計(jì)算，求得與查詢向量最相似的K個文檔。數(shù)據(jù)庫中存有文本的樹性結(jié)構(gòu)等信息，用戶等待的時間就是過濾和精確計(jì)算花費(fèi)的時間，由3.1的實(shí)例說明計(jì)算量減少了，花費(fèi)的時間也少了。

其中，KNum為過濾后剩下的文本數(shù)，K為精確檢索時所需要返回的文本數(shù)；條件判斷KNum>2*K而不是KNum>K是為了減少篩選率，提供更多的文本傳送給精確計(jì)算。

3.3 實(shí)驗(yàn)及結(jié)果分析

1) 首先是對ABT預(yù)結(jié)構(gòu)的正確性的實(shí)驗(yàn)驗(yàn)證，實(shí)驗(yàn)分別對文本向量用單詞表示和用ngram（n＝5）表示而展開[4]。其中數(shù)字表示文檔ID號，共取了30篇文檔，其中編號為4，5，6的文檔屬于相同子類，查詢向量query＝document 4；層次閾值取Maxlay/2。

因?yàn)椴樵兾臋n直接取的是document 4，由表1發(fā)現(xiàn)無論閾值FilterT如何選取，document 4始終都沒有被過濾掉；由表2發(fā)現(xiàn)當(dāng)采用合適的FilterT之后，ngram表示的實(shí)驗(yàn)結(jié)果并不比單詞表示的實(shí)驗(yàn)結(jié)果遜色，而實(shí)際上上文已經(jīng)證明了采用ABT預(yù)結(jié)構(gòu)的方法本身沒有精度的損失，唯有可能帶來精度損失的是由文檔的表示引起的；同時，采用ABT預(yù)結(jié)構(gòu)的方法比采用余弦相似度計(jì)算花費(fèi)的時間少得多，實(shí)驗(yàn)過程中得到以下的觀察結(jié)果：

觀察一：閾值FilterT越小，ABT算法越快但是過濾掉的文本增加；

觀察二：維度d越大，ABT算法執(zhí)行時間的優(yōu)越性越明顯；

觀察三：一般說來，ABT技術(shù)優(yōu)于順序決策技術(shù)，但在最壞的情況下，每個條目都是一個匹配項(xiàng)，兩者都不能提高速度，ABT所花費(fèi)的時間甚至是普通的方法兩倍。

2）采用先過濾再計(jì)算的方法：

①對于單詞表示的情況：先由樹形結(jié)構(gòu)篩選出的文本：17，18，20，25，3，4，5，6，8，9（其中FilterT＝170），然后用TFIDF精確計(jì)算得到最終的檢索結(jié)果是3，4，5；②對于ngram的情況：先用樹形結(jié)構(gòu)篩選出的文本：2，3，4，5，6，7（FilterT＝900），然后用TFIDF精確計(jì)算得到的檢索結(jié)果是3，4，5。

由于查詢文檔是document 4，而document 5是和document 4同類的，若選擇檢索個數(shù)為3的話，那么采用先過濾再精確計(jì)算的方法所得結(jié)果和直接計(jì)算相仿，而節(jié)省的是采用過濾之后減少的計(jì)算量。因此，不管采用單詞表示還是ngram表示，采用先過濾再精確計(jì)算的方法有效可行。

4 結(jié)論

通過把通用搜索引擎檢出的web頁面集合進(jìn)行預(yù)處理，然后再進(jìn)行快速分類，提高web頁面檢索的效率；預(yù)處理方法采用ABT預(yù)結(jié)構(gòu)方法。

參考文獻(xiàn)：

[1] 王繼成，潘金貴，張福炎.Web文本挖掘技術(shù)研究.計(jì)算機(jī)研究與發(fā)展[J].2000，37(5):513-520.

[2] Broder A J. Strategies for efficient incremental nearest neighbor search[J]. Pattern Recognition ，1990，23(12):171-178.

[3] Sung-Hyuk C， Sargur N. A fast nearest neighbor search algorithm by filtration[J]. Pattern Recognition，2002，(11):515-525.

[4] Cavnar W B. Using an n-gram-based document representation with a vector processing retrieval model[J]. In TREC-3，1994269-278.