文本分類中基于位置和類別信息的一種特征降維方法

摘 要：從文本特征項所處的位置角度提出了特征項基于位置的降維方法；同時結合特征的類別分布進行了二次特征降維。這種基于位置和類別相結合的特征降維方法在最大程度減少信息損失的條件下，實現了特征維數的有效壓縮。實驗表明，該方法有較高的文本分類效率。

關鍵詞：文本分類； 特征選擇； 特征降維； 位置加權； 類別分布

中圖分類號：TP391 文獻標志碼：A 文章編號：1001-3695(2008)08-2292-03

Method of feature reduction in text classification

based on position and sort information

LIU Hai-fenga，b， WANG Yuan-yuana， ZHANG Xue-renb， YAO Ze-qingb

(a. Institute of Command Automation， b.Institute of Sciences， PLA University of Science Technology， Nanjing 210007， China)

Abstract:From the position of the terms， this paper put forward a method to reduce the dimensionality. Meanwhile， combined with the sorts distributing， it once more reduced the feature dimension. Therefore，in precondition of the information loss least， connecting with the two aspects， used this method to complete the text feature decrease smartly. The test shows that this method has better precision in the text categorization.

Key words：text categorization; feature selection; feature reduce; positionweight; sort distribution

Internet的迅猛發展改變了人們的生活方式，人類社會步入了以網絡為信息載體的全新信息時代。伴隨著Web信息量的指數形式增長，在享受著信息“海洋”所提供的便利的同時，“信息迷航”的困境使得人們對如何獲取有效信息提出了更高的要求。作為信息處理技術的重要內容之一，文本自動分類技術已成為文本挖掘的研究熱點之一。文本分類是指在給定的分類體系下，根據文本內容自動確定文本所屬類別的過程。將文本分類技術與搜索引擎、信息過濾等信息處理技術相結合，能夠有效地提高信息服務的質量，它是文本挖掘的一個重要組成部分，在情報檢索、信息過濾等許多方面有重要現實意義和廣闊的應用前景。

1 文本分類的主要問題及其處理方法

總的說來，文本分類方法可分為基于知識和基于距離兩種。基于知識的方法是指借助專家的經驗知識，構建分類專家系統作為分類器進行分類。由于這種模式費時費力，并且擴展性差，難以適用于大規模的文本分類，特別是基于Web的文本分類要求。目前普遍采用的是基于距離分類的方法，如樸素貝葉斯方法、決策樹方法、k-近鄰方法、回歸模型方法、神經網絡方法以及支持向量機方法等^[1]。文本自動分類的關鍵問題是文本的合理表示、特征降維以及分類器的構造。

1.1 向量空間模型及其主要問題

在文本表示方法上基于向量空間模型的分類模式具有概念簡單、應用方便等優點，是主流的文本分類模型之一。在向量空間算法模型中，文本dj被映射為一個特征向量：

 ，需分類的文本為dj，兩者的相似度可用向量之間的夾角來度量，夾角越小說明相似度越高。相似度計算可以使用常用的向量夾角余弦公式:

sim(di，dj)=∑nk=1wikwjk/∑nk=1w2ik∑nk=1w2ik（3）

向量空間模型的優點在于將非結構化的文本表示為向量形式，使得各種數學處理成為可能。但是其不足之處也很明顯:

a）該模型假定特征項之間相互獨立，然而實際情況是一詞多義和多詞同義現象在文本中非常普遍。這種詞語之間關系相互獨立的基本假設在實際應用中很難得到滿足，因此影響了該模式對文本表示的準確性。

b）文本的向量表示帶來的另一個困難是文本向量維數太高，這給基于自動分類模式下機器的存儲及運算帶來了很大開銷。從矩陣A的列向量看，每個列向量的構成元素為文本的特征項（通常為詞或詞組），而文本中對表達其所屬類別有比較強說服力的詞匯是非常多的。目前漢語的常用詞有幾萬個，還有不少專業名詞和技術名詞，也就是說一個普通的文本經過分詞處理（包括去除停用詞、特高頻詞、特低頻詞等）后會有幾千甚至上萬個詞，一個篇幅較長的文本其特征空間維數通常是幾千甚至上萬維。再從行向量看，文本來自于文本集，一般說來，用于文本自動分類的訓練集中的文本不能太少，通常也要有1 000~3 000篇，否則類別信息不足。這樣行的維數也很高。分類器的算法和實現的復雜度都會隨著矩陣維數的增加而增加，而A的維數之高使得大多數機器學習算法無法承受。

c)訓練文本類別分布的傾斜現象在文本分類中也是一個突出的問題。即使是著名的文本分類語料Reuters-21578的ApteMod版本^[3]，其類別分布也非常不均。最大類含有2 877個文本，但是82%的類中文本數低于100個，并且33%的類中甚至低于10個。在特征降維時一些小類的樣本常常會作為噪聲而被刪除。這種條件下其模式識別的復雜度較高，以至于難以取得非常理想的分類效果。

能否進行有效的降維處理對文本分類的訓練時間、分類準確性都有顯著的影響，所以降維過程是提高文本分類準確率和有效率的關鍵。

1.2 文本特征降維常用的方法

特征選擇和特征抽取(feature extraction) 是文本特征降維中的主要方法。特征選擇一般是指依據某個準則從眾多原始特征中選擇部分最能反映模式類別統計特性的相關特征，即要找到能反映文本內容的特征集的最優解子集，本質上是對特征集合的約簡。目前用于特征選擇的方法大致有文檔頻度、特征頻度、特征熵、互信息、信息增益、χ2統計量、特征權、期望交叉熵、文本證據權、幾率比等，這些模型由于構造相對簡單、易于理解而得到廣泛應用。

特征抽取就是基于特征項之間的語義相關性、類別特征集對類內文本聚合程度、類間離散程度的影響力等方面考量而對文本特征集的一種壓縮。在中文文本分類中，這種模式著眼于解決特征選擇方法所遇到的文本特征項之間的一詞多義、多詞同義、近義等現象所引起的特征壓縮瓶頸。常用的特征抽取方法可以分為主成分分析、潛在語義標引、非負矩陣分解等^[4]。這些方法從不同的角度度量特征對文本分類所起的作用，但多數還是以文本特征項矩陣A為基礎而進行的一系列降維模式研究。但是這些模式的一個顯著問題是沒有利用特征項的位置信息，使得不同位置的特征項在文本中的不同作用沒有顯現出來。

本文從文本類和特征項的位置因素結合方面對文本分類方法進行探討。2 類別—特征項向量模型的相關概念及文本分類算法

2.1 使用類別—特征項模型進行矩陣維數壓縮

與文本—特征項矩陣A的構成相似，筆者考慮建立類別—特征項矩陣體系用于文本分類。具體說來，類似于構建文本—特征項矩陣A用來表示文本，現在建立的矩陣可以設為^[5]

2.2 使用特征選擇方法對矩陣維數進行二次壓縮

本文將特征項在文本中的位置作為考量因素再從行的角度進行降維。如前所述，一個普通的文本經過分詞處理后有幾千甚至上萬個詞可以作為特征項，一個篇幅較長的文本的特征空間維數是幾千甚至幾萬維是常有的現象。對于分類器來說，仍然很難處理以這種模式構成的類別—特征項矩陣B。但是，特征詞對文本分類的作用是不同的，文本的不同部位對文本的主題表達能力是有區別的。從針對文獻整體的檢準率的角度看，文獻題名中的詞最有用，其次為文獻中的小標題或章節名或文獻的摘要，最后為文獻正文中的詞^[8]。將特征項在文本中的位置作為確定其權重的因素之一，再結合詞頻進行權值的確定，就是通常所說的位置加權法。無論哪種類型的文本，其標題部分所含有的特征信息都多于文章其余部分。但是，單純從標題中抽取特征信息對文本進行分類是不夠的，還應該考慮摘要部分;而對沒有摘要的文章，從正文的標題和子標題中抽取特征信息的效果也要優于單純從正文標題中抽取^[9]。文獻[10]通過對涉及經濟、教育、文學和心理學四個領域的1 800篇文本進行分析、實驗，對Web文本所含有的12個信息分布位置——網頁題名(title 項)、文章標題(bt)、第一段首句(ds1)、第一段尾句(dw1)、第二段首句(ds2) 、第二段尾句(dw2)、 第三段首句(ds3)、 第三段尾句(dw3)、首段(sd)、尾段(wd)、其他段(qt，即除去sd、wd，并且不包括ds2、dw2、ds3、dw3 之外的文本其他部分)、html 標記(html)等對文本的表達能力進行了詳細的統計分析，得到各個位置對主題表達能力的先后順序并建議位置權重方案為^[10]

bt ∶html ∶sd ∶ds1 ∶title ∶dw1 ∶qt ∶wd ∶ds2 ∶dw2 ∶ds3 ∶dw3 =

5∶5∶5∶4∶4∶4∶2∶2∶2∶2∶2∶2（7）

本文考慮用文本中較為重要的部分，即文章標題、html 標記（如果文本為Web上的html文本）、關鍵詞、摘要、首段；第一段首句、網頁題名、第一段尾句等所含有的特征項為矩陣B中的特征項來表示文本。相比較整篇文本中的特征項個數，這部分內容所含有的特征項個數要少得多。具體的基于位置加權處理方法是：

H1={Ti|Ti為文章標題、html標記、關鍵詞中特征項}

H2={Ti|Ti為摘要、第一段首句、網頁題名中特征項}（8）

定義矩陣B中的元素為

w＾ij=6wij 若Ti∈H1∩Sj

4wij 若Ti∈H2∩Sj

5wij 若Ti∈H1∩H2∩Sj(9)

在此基礎上，將待分類的文本d在每個類別Sj中表示成由上述特征項的相應權值構成的向量Sj=(w＾1j，w＾2j，…，w＾mj)T（j=1，2，…，n）；按照類別將Sj各分量相加，其和作為文本d在Sj中的類屬權重，權重最大者所對應的類別即為文本d所屬類別。 綜上所述，本文提出一種基于類別和位置的特征降維方法。

2.3 基于類別—特征項模型的文本分類算法及其特點

類別—特征項模型對文本進行分類的主要步驟為：

a）對待分類文本d進行分詞、過濾；按照式（8）抽取特征項。

b）根據式（6）、（10）計算類別—特征項矩陣B中的元素w＾ij，構造矩陣B。

c）將矩陣B的每個列向量Sj=(w＾1j，w＾2j，…，w＾mj)T(j=1，2，…，n)的各分量相加求和：

vj=∑mi=1w＾ij; j=1，2，…，n(10)

d）判別類屬，若vk=max{v1，v2，…，vn}，則將d劃歸到類別Sk中。

相比傳統的向量空間模型，類別—特征項向量模型具有以下兩個顯著特點：

a）類別—特征項矩陣B相比較文本—特征項矩陣A來說，其維數的下降幅度非常大，易于各種分類器的處理。

b）在傳統的向量空間模型中，就某一文本而言，特征項出現與否具有偶然性，使得矩陣A中的數據呈現稀疏現象；而在類別—特征項矩陣B中，對于特定的一個具體類別而言，其具有代表性的特征項非常穩定，一些名詞特別是一些類別的專有名詞、技術名詞等常常用于描述該類別的特征，而文本的作者也往往傾向于使用類別中頻率較高的詞語^[6]。也就是說，大量的同類文本中，其代表性詞語是相對固定的。

3 實驗結果及其分析

本文對上述方法的分類效果進行了實驗。實驗數據為新浪網上下載的3 376篇文本，分為房地產（550篇）、金融（512篇）、體育（530篇）、計算機（602篇）、音樂（495篇）以及旅游（687篇）。實驗時采用四分交叉實驗法，將3 580篇文本平均分為四份，三份為訓練集，一份為測試集；每份輪流作為測試集循環測試四次，取平均值為測試結果。剔除特高頻詞、低頻詞以及停用詞等對文本進行預處理，效果評估函數使用常用的查準率、查全率和F1測試值：

查準率=分類的正確文本數/實際分類文本數

查全率=分類的正確文本數/應有文本數

F1=（查準率×查全率×2）/（查準率+查全率）

分類結果統計如表1所示。

表1 文本分類實驗結果統計%類別房地產金融體育計算機音樂旅游查準率84.3 87.292.387.484.288.2查全率85.2 80.485.292.183.790.4F1值84.783.788.689.783.989.3從表1中可以得到，平均查準率為87.3%，查全率為86.2%;測試值為86.7 %。使用本文提到的特征降維方法對文本進行分類，分類效果還是令人滿意的。

4 結束語

本文提出的類別—特征項文本分類模型，從類別和特征位置兩個方面先后兩次對文本矩陣維數進行壓縮，在盡量保留分類信息的同時解決了文本分類中最困難的特征降維問題。其高效的降維效率使得各種文本分類器能有效工作，有效地解決了數據存儲、分類開銷等傳統的向量空間模型很難解決的問題。今后的工作重點是在本系統的基礎上，更深入地結合機器學習、自然語言處理等理論知識，嘗試其他分類算法，進一步提高分類查全率和查準率。

參考文獻：

[1]蘇金樹，張博鋒，徐昕.基于機器學習的文本分類技術研究進展[J].軟件學報，2006，17（9）：1848-1859.

[2]劉海峰，王元元.基于向量模型的文本檢索若干問題研究[J].情報雜志，2006，25(10):57-62.

[3]YANG Yi-ming， LIU Xin. A re-examination of text categorization methods[C]//Proc of ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM Press，1999:42-49.

[4]陳濤，謝陽群.文本分類中的特征降維方法綜述[J].情報學報，2005，24(6):690-695.

[5]黃冉.郭嵩山.基于類別空間模型的文本分類系統的設計與實現[J].計算機應用研究，2005，22(8):60-63.

[6]劉海峰，王元元，王倩.基于分類的VSM模式下文本檢索若干問題研究[J]. 情報科學，2006，24(11):1700-1703.

[7]寇莎莎，魏振軍.自動文本分類中權值公式的改進[J].計算機工程與設計，2005，26(6):1616-1618.

[8]張琪玉.情報語言學基礎[M]. 武漢:武漢大學出版社，1997.

[9]劉海峰，王倩，王元元.基于Web的文本檢索位置加權模型研究[J]. 情報科學，2007，25（3）：451-455.

[10]侯漢清，章成志.Web概念挖掘中標引源加權方案初探[J].情報學報，2005，24(1):87-92.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文