基于特征向量的文本信息過濾算法研究

摘 要:隨著信息技術的迅速發展，網絡已經逐步成為人們生活當中不可或缺的信息傳播工具。由于網絡資源的大量使用和信息的大量傳輸，導致信息過載及安全等問題日益突出。為了解決信息過濾的過濾精度和效率瓶頸等問題，這里詳細地對文本信息過濾的主要過程、文本表示方法、特征向量獲取、相似度計算等技術進行研究，提出一個基于特征向量的文本信息過濾算法。該過濾算法有效地平衡了計算負載，具有較高的信息過濾性能。

關鍵詞:文本信息;特征向量;相似度;信息過濾

中圖分類號:TP391文獻標識碼:A

文章編號:1004-373X(2010)04-145-03

Algorithm of Text Information Filtering Based on Feature Vector

RUAN Bing

(Wuhan Polytechnic University，Wuhan，430023，China)

Abstract:With its rapid development and widely applied，network has become an important tool to transmit information now.So it's important for us to filtrate the information spreading through the network.To help the network information safe guarders control the bad information and identify the bad websites，an algorithm based on the feature vector，and the documents expression and the similar computational are introduced.The work has confirmed the methods which can improve the precision of information filtering.

Keywords:text information;feature vector;similarity;information filtering

0 引 言

作為面向Internet的個性化主動信息服務的一個重要中間環節，近年來信息過濾(Information Filtering，IF )技術近年來在信息的處理體系中應用越來越廣泛。IF系統的作用與傳統的信息檢索(Information Retrieval，IR)系統類似，用于幫助用戶選擇感興趣的文本。但傳統的信息過濾技術難以適應這種動態環境的需求。個性化文本信息過濾就是基于這一要求，根據用戶過濾需求，建立基于樣本的信息特征過濾模型，在詞頻和詞長的基礎上，結合文本中詞的屬性特征和局部語法結構分析，從統計特性和知識兩方面建立特征模型，實現對文本的分析過濾，獲得了較好的特定信息過濾準確性和快速性[1-3]。采用計算機能夠理解的形式表示文本是信息過濾系統所必須解決的問題。之后，系統可以采用類似于人的工作方式從文本中抽取一些反映文本內容的特征詞，并以適當的方式表示這些特征。

1 文本表示

文檔的表示方法有許多種，如向量空間模型(Vector Space Model，VSM)、N-Grams表示法和文檔概念分類表示法等[4]。向量空間模型于20世紀60年代末由Gerard Salton等人提出，因其簡單及有效性，是近幾年來應用最為廣泛的模型，檢索效果較為顯著[5，6]。在VSM模型中，每一個文本都可以用一個向量來表示。向量的元素是由項(詞條)及其權重組成的，該向量稱之為文本的特征向量。特征向量是文本的一個特征表示，在某種意義上可以完全代表文本的特性。在VSM中，每一篇文本都被映射成多維向量空間中的一個點，對于所有的文本類和未知文本，都可用此空間中的向量(T1，W1;T2，W2;…;Tm，Wm)來表示(其中Ti為詞，Wi為詞對應的權重，用以刻畫該詞在描述此文本內容時的重要程度)，從而將文本信息的表示和匹配問題轉化為向量空間中向量的表示和匹配問題來處理。

2 特征向量獲取

人們用以辨識或區分該事物的標志就是特征。特征向量就是整個文本的標志，它在后續處理中直接代表原文本，特征向量的優劣將直接影響到整個文本處理結果的好壞。因此，文本的特征向量獲取是文本信息處理中的一個重要處理步驟。為了提高特征詞條獲取的精度和速度，需要對分詞得到的詞條進行預處理，包括無用詞條過濾、詞頻加權、位置加權、同(近)義詞合并[7，8]。圖1為特征向量的獲取過程。

圖1 特征向量獲取流程

2.1 無用詞條過濾

無用詞條過濾指與Web文本挖掘無關或相關性甚小的詞條。它們在各個文本中均可以出現，不代表文本的特點。這些詞條的存在不僅不為挖掘操作提供任何信息量，而且將導致距離的計算不準確，同時還將增加存儲與計算的額外開銷，必須予以刪除。另外，從自然語言理解的角度來看，名詞和動詞構成了一個文本的核心。它們的簡單組合可以作為整個文本的簡單表示。所以，無用詞條主要包括:停用(Stop-list)詞典中的詞條，如“the”，“is”等詞條;名詞、動詞以外的詞條，這些詞條不提供信息量或提供很小的信息量;在各個類別中都出現的詞條。

2.2 詞頻加權

在VSM中，TF-IDF是一種最常見的確定詞權重的方法。對于詞權重的計算，經典的TF-IDF方法考慮詞條頻率(Term Frequency，TF)和詞條倒排文本頻率(Inverse Document Frequency，IDF)兩個因素。

(1) 詞條頻率:詞條在文本中出現的次數;

(2) 詞條倒排文本頻率:該詞條在文本集合中分布情況的一種量化，常用的計算方法是log2(N/nk+0.01)。其中:N為文本集合中的文本數目;nk為出現該詞條的文章數。

各個系統中TF-IDF的實現不盡相同，但它們的詞權重與詞頻率成正比，與文本頻率成反比。

根據以上兩個因素，可以得出:

Wik=TFik×log2(N/nk+0.01)(1)

式中:TFik為詞條Tk在文本Di中出現的次數;N表示全部樣本的總數;nk表示詞條Tk的文本頻率，即包含詞條Tk的文本個數;Wik為詞條Tk在文本Di中的權重，k=1，2，…，m(m為詞的個數)。

為了計算方便，通常要對向量進行歸一化，最后有:

Wik=TFik×log2(N/nk+0.01)∑mk=1[TFik×log2(N/nk+0.01)]2(2)

2.3 位置加權

與普通文本不同，Web文本數據是一種半結構化的數據，文本中包含了由各種標記指明的格式信息。據統計，

2.4 同(近)義詞合并

在傳統的向量空間模型中，最基本的假設是各個分量間正交。而在真實文檔中，作為分量的詞匯往往具有很大的相關性[9]。這是因為在自然語言理解的過程中，語境中經常出現多詞同(近)義以及詞條之間相互蘊含等現象。如果不考慮詞條的這種語義關系，而將它們分別作為單獨的詞條來對待，那么詞條權重的計算會存在很大的問題。

在進行文本表示時，考慮到把具有語義聯系的詞條轉化為同一個核心詞匯，將它們統一起來，并相應地調整詞條的權重。詞條在文本中的出現頻數是由中心關鍵詞、蘊含詞詞條、近義詞詞條三部分的詞頻數累計得到的，其詞條權重統計公式為:

TF=TMF+∑TIFi×ai+∑TJFi×wi(3)

式中:TMF為中心詞詞條的詞頻數;TIFi為蘊含詞詞條的詞頻數;ai為蘊含詞與中心詞之間的蘊含度;TJFi為近義詞詞條詞頻數;wi為近義詞與中心詞之間的近似度。

3 文本相似度計算

若想判斷一篇文本是否真正符合用戶興趣，一種常見的方法是衡量文本與主題特征間的相似程度，即需要計算文本與主題間的相似度。在信息過濾過程中，相似度是十分重要的概念[10]。文本的一切特性通過由較為重要的特征詞匯構成的特征向量來表示。所以，文本相似度借助于其特征向量的相似度計算方法。

3.1 詞語相似度計算

相似度這個概念，涉及到詞語的詞法、句法、語義，甚至語用等方方面面的特點。其中，對詞語相似度影響最大的應該是詞的語義。

度量兩個詞語關系的另一個重要指標是詞語的距離。一般而言，詞語距離是在[0，∞)之間的實數。一個詞語與其本身的距離為0。詞語距離與詞語相似度之間有著密切的關系。兩個詞語的距離越大，其相似度越低;反之，兩個詞語的距離越小，其相似度越大。二者之間可以建立一種簡單的對應關系。這種對應關系需要滿足以下幾個條件:

(1) 兩個詞語距離為0時，其相似度為1;

(2) 兩個詞語距離為無窮大時，其相似度為0;

(3) 兩個詞語距離越大，其相似度越小(單調下降)。

對于兩個詞語W1和W2，將其相似度記為Sim(W1，W2)，其詞語距離為Dis(W1，W2)，那么可以定義一個滿足以上條件的簡單的轉換關系為:

Sim(W1，W2)=αDis(W1，W)+α(4)

式中:α是相似度為0.5時的詞語距離值，它是一個可調節的參數。

對于兩個漢語詞語W1和W2，如果W1有n個義項(概念)，則S11，S12，…，S1n;如果W2有m個義項(概念)，則S21，S22，…，S2m，那么，W1和W2的相似度就是各個概念的相似度之最大值，也就是說:

Sim(W1，W2)=maxi=1…n，j=1…mSim(S1i，S2j)(5)

3.2 義原相似度計算

由于所有的義原根據上下位關系構成了一個樹狀的義原層次體系，所以這里采用簡單的通過語義距離計算相似度的辦法。假設兩個義原在這個層次體系中的路徑距離為d，根據式(4)可以得到這兩個義原之間的語義距離為:

Sim(P1，P2)=α/(d+α)(6)

式中:P1和P2為兩個義原(Primitive);d為P1和P2在義原層次體系中的路徑長度，是一個正整數。

3.3 實詞概念的相似度的計算

因為整體相似要建立在部分相似的基礎上，所以把一個復雜的整體分解成部分，通過計算部分之間的相似度得到整體的相似度。在比較兩個整體的相似性時，首先要做的工作是在這兩個整體的各個部分之間建立起一一對應的關系，然后在這些對應的部分之間進行比較。如果某一部分對應物為空，則:

將任何義原(或具體詞)與空值的相似度定義為一個比較小的常數(δ);整體的相似度通過部分相似度加權平均得到。

實詞概念的語義表達式主要分成四個部分:

(1) 第一獨立義原描述式:兩個概念的這一部分相似度記為Sim1(S1，S2);

(2) 其他獨立義原描述式:語義表達式中除第一獨立義原以外的所有其他獨立義原(或具體詞)，兩個概念的這一部分相似度記為Sim2(S1，S2);

(3) 關系義原描述式:語義表達式中所有的用關系義原描述式，兩個概念的這一部分相似度記為Sim3(S1，S2);

(4) 符號義原描述式:語義表達式中所有的用符號義原描述式，兩個概念的這一部分的相似度記為Sim4(S1，S2)。

但是，主要部分的相似度值應該對次要部分的相似度值起到制約作用，如果Sim1非常小，但Sim3或者Sim4比較大，將導致整體的相似度仍然比較大的不合理現象，于是，最后得到兩個概念語義表達式的整體相似度記為:

Sim(S1，S2)=∑4i=1βi∏ij=1Simj(S1，S2)(7)

式中:βi(1≤i≤4)是可調節的參數，且有:β1+β2+β3+β4=1，β1≥β2≥β3≥β4。后者反映了Sim1到Sim4對于總體相似度所起到的作用依次遞減。由于第一獨立義原描述式反映了一個概念最主要的特征，所以其權重定義得比較大，一般在0.5以上。

各個部分的相似度的計算方法如下:

(1) 第一獨立義原描述式:就是兩個義原的相似度，按照式(6)計算即可;

(2) 其他獨立義原描述式:按照如下步驟對這些獨立義原描述式分組:

① 先把兩個表達式的所有獨立義原(第一個除外)任意配對，計算出所有可能配對的義原相似度;

②取相似度最大的一對，并將它們歸為一組;

③在剩下的獨立義原的配對相似度中，取最大的一對，并歸為一組，如此反復，直到所有獨立義原都完成分組。

(3) 關系義原描述式:把關系義原相同的描述式分為一組，并計算其相似度;

(4) 符號義原描述式:把關系符號相同的描述式分為一組，并計算其相似度。

在以上步驟(2)~(4)的計算中，最后求加權平均時，各部分取相等的權重。

4 結 語

在過濾技術中，文檔特征向量的獲取和相似度的計算方法對過濾的正確性起著關鍵的作用。本文理論研究中的一些文本分析所要求的步驟比如:詞干的提取，同義詞的合并算法等在實際的編程實現中有一定的困難，就算勉強實現，對文本的分析速度也有很大的影響，因此需要在過濾正確性和速度上找到一個平衡點，提出更好的過濾技術來。

參考文獻

[1]曹海.基于文本內容分析的過濾技術研究[J].四川大學學報:自然科學版，2006，43(6):1 248-1 252.

[2]胡娟麗，姚勇，劉志鏡.基于典型反饋的個性化文本信息過濾[J].計算機應用，2007，27(10):2 607-2 609.

[3]劉海峰，劉守生，姚澤清，等.基于Web的信息過濾技術研究[J].情報科學，2008，26(12):1 869-1 872.

[4]Chris H Q Ding.A Sinilarity-based Probability Model for Latent Semantic Indexing[A].Proceeding of 22nd Intemratonal Conference on Research and Development in Information Retrieval[C]，1999:59-65.

[5]費洪曉，穆珺，鞏艷玲，等.基于Agent的個性化信息過濾系統的設計與實現[J].計算機技術與發展，2006(12):1-2.

[6]何建英，陳蓉，徐淼，等.基于類別特征向量表示的中文文本分類算法[J].計算機應用研究，2008，25(2):337-338，344.

[7]趙豐年，劉林，商建云.基于概念的文本過濾模型[J].計算機工程與應用，2006，42(4):186-188.

[8]汪琴，安賀意，秦穎.網絡信息過濾和個性化信息服務[J].情報科學，2007，25(6):858-863.

[9]管玉娟.基于智能Agent的個性化信息檢索技術研究[D].西安:西安建筑科技大學，2005.

[10]曾毅，賀衛紅.基于向量空間模型的信息安全過濾系統[J].計算機工程與設計，2006，27(2):224-227.