一種可靠信任推薦文本分類特征權重算法

摘 要:從可信計算角度，提出一種可靠信任推薦文本分類特征權重算法，分析了特征在文檔中的特性，基于Beta分布函數研究了特征與文檔類之間的信任關系，建立特征權重計算模型，并實現簡單高效的線性文本分類器。在比較實驗中采用20newsgroup和復旦中文語料集。與TFIDF算法進行性能比較，實驗結果顯示該算法性能較TFIDF顯著提高，并對非平衡語料具有良好的適應性。

關鍵詞:文本分類; 特征權重; 可信計算; 概率確定性密度; 自然語言處理

中圖分類號:TP181

文獻標志碼:A

文章編號:1001-3695(2010)02-0472-03

doi:10.3969/j.issn.1001-3695.2010.02.0018

Reliable trust recommendation model for feature weighting in text categorization

JIAO Qing-zheng1，2， WEI Cheng-jian1

(1. College of Information Science Engineering， Nanjing University of Technology， Nanjing 210009， China; 2. Information Management Center， Anhui Normal University， Wuhu Anhui 241000， China)

Abstract:By reliable trust recommendation， used a feature weighting approach to construct the simplest linear weighting classifier in the procedure of which characteristics of feature were explored， while the trust relationship between features and categories was developed based on Beta distribution function. Experiments with 20newsgroup and Fudan Chinese evaluation data collection reported shows that this new algorithm generally outperformed TFIDF， and has good adaptability to non-equilibrium corpus.

Key words:text categorization(TC); feature weighting; trust computing; probability certainty density; natural language processing

0 引言

自動文本分類是一種有監(jiān)督的學習任務[1]，即根據已分類的訓練文檔集合，對未分類文檔分配類標簽。文本分類(TC)的最大困難之一是特征空間的高維性，選擇合適的特征及權值來表示文檔是提高文本分類準確性的關鍵。目前，文本特征表示的主要模型有布爾模型、向量空間、概率三種，這些模型又可以歸結為特征選擇和特征權重計算兩類。特征選擇是通過選擇算法過濾掉對分類性能無益或引起性能下降的噪聲特征。特征選擇方法有文檔頻率法(document frequency， DF)、信息增益法(information gain， IG)、KL距離法(Kullback-Leibler divergence， KL)、X2統計法、互信息法(mutual information， MI)等。特征權重計算方法主要有TFIDF[2]權重、基于熵概念的權重。TFIDF是一種用于評估詞(或特征)對于一個訓練語料重要程度的統計方法，是文本分類中最常用的特征權重算法。TFIDF 的主要核心思想是:TF表示詞在類文檔中出現的頻率，如果某個詞在一類文章中出現的頻率TF高，而且在其他類文章中低，則認為此詞具有很好的類別區(qū)分能力，適合用于分類。IDF(inverse document frequency)是反文檔頻率:

IDF=log (N/DF)

其中:N為訓練文檔總數;DF為包含某詞的文檔數量。IDF的思想是:如果包含某詞的文檔越少，IDF越大，則說明該詞具有很好的類別區(qū)分能力。通常在文本分類中TFIDF權重計算如下:

aij=log (TFij+1.0)×log (N/DFi)∑k[log (TFkj+1.0)×log (N/DFk)]2

其中:i是文檔類，j是詞。

雖然TFIDF權重在文本分類中十分常用，但其假設并沒有嚴格的理論證明，且在不同語料上的表現有很大差異，很多研究者提出了各種TFIDF算法改進，提高了TFIDF文本分類性能。

本文對文檔中詞匯特征進行了分析，從特征信任角度分析，引入特征可靠性評估，提出一種可靠信任推薦特征權重算法。在比較實驗中以TFIDF權重算法為參照算法進行比較，取得了良好效果。

2 可靠信任推薦文本分類特征權重算法

2.1 信任評估途徑

本文從信任推薦角度分析認為[3~5]，文檔分類是詞對文檔類推薦的結果，文檔類別測試是詞以往推薦經驗的運用。就某一詞i來說，詞頻反映了詞i對文檔類的推薦力度，詞i如果在文檔類j中相對其他文檔類越高，說明詞i對文檔類j的推薦力度越大。對于文檔出現頻率，本文并不直接引用，而引入詞在文檔中出現的平均詞頻。詞的平均詞頻反映了詞在文檔分類中的平均參與程度。如果詞i的平均詞頻相對其他詞越高，則說明詞i在文檔分類中的平均參與程度越高，那么它的推薦經驗就越可信。在特征權重的計算過程中要綜合考慮詞的推薦度與參與度。

特征詞(以下稱為特征)對文檔類的推薦可理解為事件模型，特征i在文檔類j的詞頻TFij為肯定事件數目，在其他文檔類的詞頻為否定事件數目，特征i對文檔類j的事件(event[i，j])概率為Tij=TFij/TFi(TFi為特征i的總詞頻)，但Tij特征i詞頻大小分布簡單、直觀的計算方式，消除了詞頻大小分布的細節(jié)特征，因此使用Tij來表達特征i對文檔類j的信任存在風險。

Jsang等人[3，4]提出二項事件的信任評估模型，實體產生的事件被簡單地劃分為肯定事件(positive event)和否定事件(negative event)。Jsang基于Beta分布函數描述二項事件(binary event)后驗概率的思想，給出了一個由觀察到的肯定事件數和否定事件數決定的概率確定性密度函數pcdf，并以此來計算實體產生某個事件的概率的可信度。設概率變量為θ，r和s分別表示觀測到的實體所產生某個事件的概率及產生的肯定事件和否定事件數，則pcdf公式表述為

f(θ|r，s)=Γ(r+s+2)Γ(r+1)Γ(s+1)θr(1-θ)s(1)

將Tfij、TFi-Tfij、Tij分別替換式(1)中的r、s、θ，即得到event[i，j]事件概率在Tij時的確定性密度，它可用于衡量Tij在r、s事件條件下的確定性。為了找到在特征權重計算中運用Jsang信任評估模型的方法，本文構建了一種文本分類中特征權重計算的可靠信任推薦模型。

1.2 可靠信任推薦模型(RTRM)

RTRM(reliable trust recommendation model)將特征i對文檔類j的事件(event[i，j])概率分為微觀經驗概率和宏觀經驗概率。

微觀經驗概率(mipij):將非j類文檔數平衡到與j類文檔數(Nj)相同時，事件event[i，j]發(fā)生的概率。

宏觀經驗概率(mapij):在原始j類與非j類文檔數分布下，事件event[i，j]發(fā)生的概率。

根據定義，特征mipij和mapij的計算式可分別表示為式(2)和(3)。如果分類語料為平衡語料，mipij的計算公式可簡化為式(4)。

mipij=TFijTFij+TFi-TFijN-Nj×Nj(2)

mapij=TFijTFj(3)

mipij=TFijTFij+TFi-TFijk-1(4)

mipij肯定事件的特征詞頻為TFij，類文檔數為Nj，否定事件的特征詞頻為(TFi-TFij)×Nj/(N-Nj)，文檔數與肯定事件相同;mipij肯定事件的特征詞頻為TFij，類文檔數為Nj，否定事件的特征詞頻為TFi-TFij，文檔數為N-Nj。

可以分析微觀經驗概率mipij和宏觀經驗概率mapij事件的確定性。mipij中將非j類文檔數平衡到與j類文檔數相同，相比mapij充分暴露了經驗概率的風險特征。在mapij否定事件數偏大，TFij的增減對確定性密度影響較小，使mapij趨于可靠，掩蓋了TFij的分布特征，特征詞頻在各文檔類分布相對均勻及文檔類偏多時尤為明顯;微觀經驗概率mipij以特征i在文檔類j與非文檔類j中關于文檔類j的平均詞頻概率(只要在式(2)中將其分子分母同除以Nj即可得出)代替詞頻概率，還原了TFij分布對經驗概率風險的影響，或者說對確定性密度的影響。

根據Jsang信任評估模型，可以求出mipij和mapij關于詞頻與文檔數的確定性密度。確定性密度反映了相應詞頻與文檔數下mipij和mapij的確定性，以mapij的確定性為基線，mipij和mapij確定性密度的比值表征了mipij的可靠度。可以分別求出mipij分別關于詞頻與文檔數的可靠度。將兩個可靠度作為平衡因子與mipij相乘即得到特征對文檔類推薦的信任值或推薦度。

Rij=mipij×f(mipij|TFij，(TFi-TFij)×Nj/(N-Nj))f(mapij|TFij，TFi-TFij)×f(0.5|Nj，Nj)f(Nj/(N-Nj)|Nj，N-Nj)(5)

根據之前的分析，綜合考慮特征的推薦度和平均參與度(degree of participation， DOP)即特征平均詞頻(TFi/DFi)，即可得到特征權重的計算式:

aij=Rij×TFiDFi=mipij×f(mipij|TFij，(TFi-TFij)×Nj/(N-Nj))f(mapij|TFij，TFi-TFij)×f(0.5|Nj，Nj)f(Nj/(N-Nj)|Nj，N-Nj)×TFiDFi(6)

式(6)中DFi為特征i的文檔出現頻率。對于平衡語料，式(6)可簡化為式(7)，省略關于文檔數的可靠度是因為對于所有特征它是一個固定常量，因此可以略去。

aij=mipij×f(mipij|TFij，(TFi-TFij)/(k-1))f(mapij|TFij，TFi-TFij)×TFiDFi(7)

2 性能分析

2.1 數據集和實驗環(huán)境

實驗數據來自兩個語料集:a)分類研究中廣為使用的Reuters-20newsgroup，數據來自LibSVM網站數據集(http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/multiclass.html#news20)，下載的數據已是經過預處理后的數據集，省去了本文對數據集的預處理過程;b)復旦大學計算機信息與技術系國際數據庫中心提供的中文語料集(http://www.nlp.org.cn/docs/doclist.php? cat_id=16type=15)。兩個語料集涵蓋了中、英文兩個語種及平衡與不平衡兩種語料類別，使實驗可以從兩個方面測試算法的性能。本文使用了兩個數據集中的所有訓練文檔和測試文檔。Reuters-20newsgroup為平衡語料集，分20個類別，共2萬篇文檔，訓練集16 000篇文檔，每個類800篇，測試集4 000篇。復旦大學計算機信息與技術系國際數據庫中心提供的中文語料集共有19 637篇文檔，訓練集9 804篇，測試集9 833篇，分20個類，各類別中的文檔數分別為740， 33， 59， 44， 466， 640， 32， 27， 25， 1 357， 33， 57， 1 217， 1 021， 1 600， 51， 51， 74， 1 024， 1 253，是個文檔數嚴重不均勻的語料。

Reuters-20newsgroup預處理后共有60 346個特征詞匯。對于中文語料集，本文采用Standford自然語言處理實驗室的中文分詞系統進行分詞，去除停用詞及在文檔中只出現一次的詞匯，共獲得120 190個特征詞匯。

本文的編程環(huán)境為Java， 采用關系數據庫(MySQL)作為數據持久存儲。

2.2 特征選擇和分類器設計

為了評估TFIDF、RTRM算法在選取不同特征數目時分類的性能表現[6，7]，本文使用同一算法標準分別對TFIDF與RTRM計算其特征的全局判別能力并排序，選擇全局判別能力強的特征。

兩個文檔類特征權重距離反映了特征的判別能力，本文采用特征權重距離實現特征判別能力評價。特征的全局判別能力可以采用最大法、平均法、最小法[7]。本文通過反復測試發(fā)現平均法優(yōu)于最大法，驗證了文獻[7]中的結論。權重距離和平均法計算特征的全局判別能力式如式(8)和(9)。

Djl(i)=aij-ail(8)

Dave(i)=2k(k-1)∑kj=1∑l>1Djl(i)(9)

為了嚴格意義上比較TFIDF與RTRM算法的性能，本文構建簡單的分類器。分類器僅根據測試文檔特征詞頻及特征權重計算各文檔類分類值，見式(10)，分類值最大類即為測試文檔的類別，見式(11)。

DCi=∑jaijTFj(10)

DC=arg max DCi1≤i≤k(11)

2.3 實驗分析

本文分別采用微平均F1指標和宏平均F1指標評價算法的性能[8]。20newsgroup語料分類實驗結果如表1所示。

表1 20newsgroup文本分類結果

feature size

TFIDF

Micro F1Macro F1

RTRM

Micro F1Macro F1

2 00040.67 41.3947.62 49.39

4 00055.99 56.7461.81 63.51

6 00065.01 65.4572.54 73.24

8 00071.23 71.4977.41 77.85

10 00075.28 75.3780.66 80.87

20 00081.70 81.6585.30 85.29

30 00084.02 83.9186.30 86.28

40 00085.20 85.0786.93 86.90

50 00086.10 85.9987.03 87.01

60 33786.80 86.6787.08 87.06

從表1可以看出，在所有特征規(guī)模下，RTRM的微平均F1指標和宏平均F1指標明顯好于TFIDF，其中微平均F1指標平均高出4.07，宏平均F1指標平均高出4.00。這表明在平衡語料下RTRM特征權重比TFIDF特征權重的判別能力強。

中文語料分類實驗結果如圖1所示。

從圖1中可以看出，RTRM在中文非平衡語料集中相比于TFIDF表現出更多的性能優(yōu)勢:a)在整體分類性能上顯著高于TFIDF，微平均F1指標平均高出17.32，宏平均F1指標平均高出28.41;b)RTRM選取較少的特征數目即可獲得較好的分類性能，而TFIDF在較少特征規(guī)模時表現出來的性能較差;c)RTRM從較小特征規(guī)模直到最大特征規(guī)模，微平均F1指標和宏平均F1指標曲線相對平穩(wěn)。

特征權重的全局判別能力體現在文檔類之間特征權重距離和特征之間權重距離，文檔類之間的特征權重距離分配越合理，則特征對文檔類的判別能力就越強，特征之間權重距離分配越合理，則在特征選取時越能選出全局判別能力強的特征。

圖1中RTRM的整體性能優(yōu)勢說明RTRM的特征權重在文檔類之間的分配合理，證明RTRM推薦度有效地映射了特征對文檔類的貢獻。

同時RTRM在較少特征數目下表現出的分類性能優(yōu)勢說明RTRM的特征之間權重距離分配合理，證明利用參與度調節(jié)推薦度的有效性，參與度越高，推薦度就越可信，參與度的引入既保留和強化了參與度高的強分類特征，又避免了對稀有特征過度擬合，使算法更加健壯。本文比較了RTRM在參與度出現與缺失時的分類性能，如圖2所示。

宏平均F1指標相對微平均F1指標而言更受小類的影響[1]。從圖1中還可以看出，即使在TFIDF達到最佳分類性能時，RTRM的宏平均F1指標仍然顯著領先于TFIDF，主要原因是RTRM定義微觀經驗概率時平衡了文檔類的數目，使非平衡語料下，小類得到了應有重視。

3 結束語

本文將文本分類理解為特征詞匯對文檔類別的信任推薦，建立基于可靠信任推薦特征權重算法，并與TFIDF算法進行性能對比測試分析。本文的主要結論包括:a) RTRM特征權重判別能力顯著優(yōu)于TFIDF;b) RTRM算法健壯穩(wěn)定，在平衡語料和非平衡語料中均表現出良好的分類性能;c)RTRM算法對非平衡語料有良好的適應性。

未來將嘗試RTRM算法與其他文本分類算法結合，以期提高文本分類的整體性能，同時也將嘗試RTRM算法思想運用到其他自然語言處理問題。

參考文獻:

[1]YANG Yi-ming， LIU X. A re-examination of text categorization methods[C]//Proc of the 22nd Annual International ACM SIGIR Confe-rence on Research and Development in Information Retrieval. 1999:42-49.

[2]JOACHIMS T. A probabilistic analysis of the Rocchio algorithm with TFIDF for text categorization[C]//Proc of the 14th International Conference on Machine Learning. 1997:143-151.

[3]JSANG A， KNAPSKOG S J. A metric for trusted systems[C]//Proc of the 21st National Security Conference. 1998:16-29.

[4]JSANG A， ISMAIL R. The beta reputation system[C]//Proc of the 15th Bled Conference on Electronic Commerce. Bled， Slovenia:[s.n.]， 2002.

[5]林鴻飛，楊志豪，趙晶. 基于內容和合作模式的信息推薦機制[J]. 中文信息學報，2005，19(1):48-55.

[6]YANG Yi-ming， PEDERSEN J O. A comparative study on feature selection in text categorization[C]//Proc of the 14th International Conference on Machine Learning.1997:412-420.

[7]朱靖波，王會珍，張希娟. 面向文本分類的混淆類判別技術[J]. 軟件學報，2008，19(3):630-639.

[8]YANG Yi-ming. An evaluation of statistical approaches to text categorization[J]. Information Retrieval，1999，1(1-2):76-82.