基于詞出現和信息增益的連續屬性離散化方法
2009-01-01 00:00:00孫挺耿國華周明全
計算機應用研究 2009年2期
(1.西北大學 可視化研究所， 西安 710127;2.周口師范學院 計算機系， 河南 周口 466000；3.北京師范大學 信息科學與技術學院， 北京 100875)
摘 要：連續屬性的離散化是文本分類任務中數據預處理階段的一項重要技術。針對機器學習領域中的諸多優秀算法只能處理離散屬性的特點，提出一種基于詞出現和信息增益相結合的多區間連續屬性離散化方法（multiinterval discretization based on term presence and information gain，MTPIG）。并將MTPIG算法應用到了分類算法AdaBoost.MH中，給出實驗結果及分析。實驗結果表明，使用MTPIG算法處理文本分類中的數據，其過程簡單高效，預測精度高，可理解性強。采用該算法離散化數據集后，分類算法的分類性能有所提高。
關鍵詞：連續屬性的離散化；信息增益；文本分類
中圖分類號：TP31 文獻標志碼：A
文章編號：10013695(2009)02048503
Method of continuous attribute discretizationbased on term presence and information gain
SUN Ting1，2，GENG Guohua1，ZHOU Mingquan3
（1．Institute of Visualization Technology， Northwest University， Xi’an 710127， China；2.Dept. of Computer Science， Zhoukou Normal University， Zhoukou Henan 466000， China；3.College of Information Science Technology， Beijing Normal University， Beijing 100875， China）
Abstract:Discretization of continuous attributes is an important technology in data preprocessing stage of the text classification. On the issue that many algorithms with outstanding features could only deal with discrete attributes in the field of machine learning，this paper proposed a method of multiinterval discretization based on term presence and information gain(MTPIG). MTPIG was applied to AdaBoost.MH， a classification algorithm.Gave the experimental results and analysis.The results de-monstrate that the process，using MTPIG algorithm to preprocess the data in the text classification， is simple and efficient， accurate， strongly understandable， and the AdaBoost.MH performance has been improved by preprocessing.
Key words:continuous attribute discretization; information gain; text classification
在分類學習任務中，樣本的屬性主要有兩種類型：a)連續（定量）屬性。它們表示了對象的某種可測性質，連續屬性的取值一般為某個數域內的點，如整數或實數域內的點，并且取值之間具有一定的線性順序關系。例如，年齡、身高。b)離散（定性）屬性。使用語言或少量離散值來表示，取值之間沒有明確的順序關系。例如，性別、顏色等，均屬于離散屬性。比如，性別屬性的取值，男、女之間沒有一定的順序關系。在絕大多數文本分類任務中，既包含連續屬性，又包含離
散屬性。
研究發現，決策樹方法（ID3，C4.5）、關聯規則方法和Boosting方法等諸多優秀的學習算法都是以離散值為處理對象[1~5]。這些算法共同的特點是：都要求文本表示采用二值向量，以表示某特征詞在該文本中出現還是不出現，忽略了對特征詞重要程度的衡量，丟失了很多權值中所包含的分類信息。然而，不同特征詞在分類中的重要程度不同，僅依賴是否出現不能很好地描述其對分類的作用，考慮特征詞的權重往往比單純用二值表示包含更加豐富的分類信息。連續屬性的離散化問題解決如何將連續屬性值離散化，以適于這些優秀學習方法。采用好的離散化方法可以提高監督分類器的預測精度和效率，同時能夠獲得易于理解的規則表示[6]。因此，對連續屬性進行離散化是文本分類任務中的一個重要問題。
本文提出了基于詞出現和信息增益相結合的的離散化方法MTPIG（multiinterval discretization based on term presence and information gain）。該算法定義一個離散化過程（discretization procedure），離散化過程采用傳統信息檢索的加權技術（如詞頻、TF*IDF等）生成的非二值特征詞空間，判斷原特征空間中每個特征詞屬于或不屬于某給定子區間，將問題轉換成二值表示方式，以使得這些分類算法適用于連續屬性值。實驗結果表明，該算法過程簡單高效，預測精度高，可理解性強。
1 算法思想
離散化的任務是在特定連續屬性的取值范圍內，根據某種評價規則，設定若干個分割點，用這些分割點將屬性的取值范圍劃分成若干個子區間，這些子區間即為該離散屬性的取值，最后用特定的符號或整數值代表每個子區間，從而將連續屬性作為離散屬性來處理。因而，連續屬性值離散化問題涉及如何合理地設定分割點、評價分割點以及在每個連續屬性的取值范圍內設定多少個分割點等多個問題。
Tri={s∈Tr|sA≤a1} if i=1
{s∈Tr|ai-1＜sA≤ai}if 1＜i＜k
{s∈Tr|ak-1＜sA}if i=k（1）
MTPIG算法離散化過程的基本思想是：針對特征空間中的每一個特征詞tk（連續屬性A），采用遞歸二分法的離散化方法，將屬性A所屬的連續區間[LT，LD]進行劃分，形成一個不連續子區間的有序序列：
I={[LT=a0，a1]，(a1，a2]，…，(a|I|-1，a|I|=LD]}
然后，判斷A在劃分后的子區間中出現或不出現，用1或0替換A在文檔中的原權重值，從而將樣本空間的連續屬性值轉換為離散化屬性值。
在文本分類問題中，每一個特征項和一個屬性對應，僅考慮特征值是連續屬性的情況。MTPIG算法主要包括了區間的劃分、分割的評估、閾值的選擇以及向量表示的轉換等步驟。
1.1 區間劃分
定義1 連續屬性的屬性值序列。在樣本集Tr中，特征屬性集合為T，A是屬于T的一個連續屬性，A的取值范圍是[LT，LD]。在樣本集中將連續屬性A在[LT，LD]的取值上進行有序排序，得到v1＜v2＜…＜v|Tr|，則序列VA={v1，v2，…，v|Tr|}稱為連續屬性A上的有序屬性序列。其中，LT＞0，LD分別被稱為A取值范圍的上界和下界。
在離散化方法中，對某個連續屬性A的離散化結果對應著當前樣本集Tr的一個劃分。下面給出劃分的定義[7]。
定義2 劃分。對于樣本集Tr，s∈Tr表示一個樣本， sA表示樣本s在屬性A上的取值。若對于連續屬性A，其連續屬性的屬性值序列為VA={v1，v2，…，v|Tr|}，分割點集合{a1，a2，…，ak-1}將A的取值范圍離散為k個區間，則這一離散化過程定義了樣本集Tr的一個劃分，該劃分將樣本集Tr分為k個樣本子集。其中第i個樣本子集Tri的表示如式(1)。
該劃分應滿足如下四個約束條件：
a） 子集不為空。對于任意i∈{1…，k}，Tri≥1。
b） 完全性。∪ki=1Tri=Tr。
c） 互斥性。對于任意i≠j，Tri∩Trj=。其中1≤i，j≤k。
d） 有序性。對于任意i＜j，若有si∈Tri，sj∈Trj，則siA＜sjA。
1.2 評估函數
對于每一個連續值屬性A，通過評估其取值范圍中的每一個候選分割點，以便在它的取值范圍中選擇最好的分割點aA。常用的評估函數有x2統計量[8]、信息增益[9]、增益比[10]、最短描述長度原理[11]、訓練樣本集出錯率[12]等。本文采用信息增益來評價分割點的優劣。信息增益的基本思想：給定一個連續屬性A，其取值范圍是[LT，LD]，尋找一個值aA（被稱為分割值或分割），將[LT，LD]分成兩個子區間[LT，aA]和[aA，LD]，從而將訓練樣本集分成兩個子集，即A∈[LT，aA]和A∈（aA，LD]兩部分。當使用分割aA時，信息增益可以量化分類的容易性，也就是衡量新產生的兩個樣本子集區分正例和反例的性能好壞的能力。選擇使信息增益最大的分割aA也就是選擇使正例和反例距離最大的分割。
在算法中遞歸地使用二分法的離散化方法，即在劃分后的[LT，aA]和[aA，LD]兩個子區間中繼續二分法分割，分別尋找使其信息增益最大的分割，直到遞歸得到的子區間數目大于或等于某預先設定的閾值Ts，分割過程停止，從而在屬性A上創建了多區間。
下面引入信息增益的定義。
定義3 分割的信息熵。假設屬性A的候選分割點集合為{a1，a2，…，ak-1}，ai將樣本集合Tr劃分成兩個子集Tr1i={s∈Tr|sA≤ai}和Tr2i={s∈Tr|sA＞ai}且Tr=Tr1i∪Tr2i，由屬性A而來的分割的類別信息熵，用E(A，ai，Tr)表示，計算公式如式(2)：
E(A，ai，Tr)=[|Tr1i|/|Tr|]Ent(Tr1i)+[|Tr2i|/|Tr|]Ent(Tr2i)(2)
A屬性的二分離散化由如下決定：在所有分割中選擇使其信息熵最小的分割點ai。
定義4 樣本集的信息熵。對于連續屬性A，假設其分割ai將樣本集合Tr中的樣本分成兩個子集Tr1i和Tr2i，m個類別C1，…，Cm，那么Ent(Tr2i)和Ent(Tr2i)由式(3)計算：
Ent(Tr1i)=-mj=1P(Cj，Tr1i)log (P(Cj，Tr1i))=-mj=1[|TrCj1i|/|Tr1i|]log2 [|TrCj1i|/|Tr1i|](3)
其中：P(Cj，Tr1i)是所有Tr1i中屬于類別Cj的樣本的比例；P(Cj，Tr1i)=|TrCj1i|/|Tr1i|，TrCj1i表示樣本集中所有的屬于類別Cj的樣本的集合。Ent(Tr2i)的確定方法和Ent(Tr2i)的確定方法相同。
定義5 信息增益。選擇ai作為分割點劃分Tr后，其信息熵增益IG(Tr，ai)的定義如式(4)：
IG(Tr，ai)=E(A，ai，Tr)-[|Tr1i|/|Tr|E(A，ai，Tr1i)]-
[|Tr2i|/|Tr|E(A，ai，Tr2i)]（4）
選擇分割ai，使在原訓練集上Tr的信息增益IG(Tr，ai)最大，正例和反例的距離就越大，那么ai就是經過評估得到的最優分割。
1.3 閾值設定
在MTPIG算法中，遞歸地使用二分離散化方法。針對每一個連續屬性A，尋找信息增益最大的最優分割aA，經過一次劃分后，使得屬性A的取值范圍[LT，LD]被劃分為[LT，LA]和[aA，LD]兩個子區間；接著在劃分后的子區間中繼續使用二分法分割，分別尋找使其信息增益最大的分割，直到得到的子區間數目大于或等于某個預先給定的閾值，分割過程停止，從而在特征A上創建了多區間。
閾值的確定非常困難，理論上至今還沒有完美的解決方法。算法中所采用的閾值確定方法是根據實驗而來，即采用預設初始值，然后使用分類器對測試文本進行分類，根據分類的準確程度不斷地調整初始值，直到達到滿意的分類準確率。
1.4 向量表示轉換
給定訓練樣本集Tr={d1，d2，…，d|Tr|}，采用向量空間模型將每一個文本表示為一個向量dj=(w1j，w2j，…，wnj)。其中wkj為第k個特征項tk在文檔dj中的權重，以確定該特征項的重要程度。特征項的作用越重要，其相應的權值wkj就越高。權重的確定方法有很多種，常用的有詞頻，TF*IDF等。采用上述的特征加權方法，每個文本就用一組連續屬性表征。
針對特征空間中的每一個特征詞tk（連續屬性A），采用上述的離散化方法，將屬性A所屬的連續區間[LT，LD]進行劃分，形成一個不連續子區間的有序序列
I={[LT=a0，a1]，(a1，a2]，…，(a|I|-1，a|I|=LD]}
接著判斷原特征空間中每個特征詞出現或不出現在某給定子區間，從而將文本加權向量表示方式轉換成布爾表示方式。轉換的公式如式（5）：
wkj=1 if wkj∈(ai-1，ai）(i=1，…，|I|)
0 其他（5）
2 算法描述
完整的MTPIG算法描述如下：
輸入：訓練樣本集合、特征向量集合以及類別標號。
Tr={〈d1，C1〉，…，〈d|Tr|，C|Tr|〉}：訓練樣本集合；
T={t1，…，t|T|}：特征向量集合；
α＞0和β分別是T中所有特征項可取值范圍的上界和下界；
C={c1，…，cm}：類別標號集合。
輸出：最優分割集合。
第一步：Optimal_splits={}；//最優分割點集合置空；
第二步：for k=1 to |T|//針對每一個連續屬性tk∈T：
a）按照tk在樣本集Tr中的取值進行升序排序得到有序序列：
Vk={vk1，vk2，…，vk|Tr|}
b）Candidate_splits={}；//候選分割點集合置空；
c）for i=1 to |Tr|。
(a)計算aki=[vki+vk(i+1)]/2；//計算序列Vk中的相鄰連續樣本對的中點，將其作為連續屬性tk的潛在候選分割點；
（b）Candidate_splits=Candidate_splits∪aki//生成連續屬性tk的候選分割點集合Candidate_splits，其中的每個點是屬于不同類的相鄰屬性值的中點；
（c）在[α，β]上依照式（4）計算候選分割點aki的信息增益；
d）選擇使信息熵增益最大的候選分割點：
ak=arg maxaki∈Candidate_splitsIG(Tr，aki)
e）將ak加入最優分割點集合Optimal_splits中，即
Optimal_splits=Optimal_splits∪{ak}
f）在分割形成的子區間中重復進行a）～e）步驟，直到得到的子區間數目大于或等于預先設定的值Ts，劃分停止。
3 實驗結果及分析
為了驗證MTPIG算法的有效性，筆者選取了UCI（university of california，irine，repository of machine learning database）機器學習數據庫中5個包含連續屬性的數據集[13]。所有實驗結果均為采用10次交叉驗證對算法進行測試的平均值。
實驗任務：設定離散化區間數目的初始值，對數據集分別進行離散化處理，再使用AdaBoost.MH算法對離散化后的數據集進行分類[14]，比較分類精度。AdaBoost.MH算法迭代次數選用50次。
表1是實驗選取的數據集特性。實驗結果見表2和圖1。表2 是設定不同分割子區間數目Ts時的分類精度。表中最后一行是在五個數據集上分類精度的平均值。圖1是不同閾值時七個數據集的平均分類精度的示意圖。分析該算法可以得出，該離散化方法對每個特征詞的離散將使該特征詞的數量增加Ts倍。當訓練文檔的個數|Tr|和表示文本的特征詞個數|T|的比值|Tr|/|T|較小時，易產生過配。也就是說這種情況下是完全根據訓練數據調整訓練模型的參數，使得該模型完全地匹配訓練數據，過分地擬合了訓練數據。因而，容易訓練出一個過于專門化的分類器，這個分類器在訓練集中表現出較好的分類性能，而對訓練集之外數據分類性能不理想。因此，在算法中應該限制分割區間的數量。雖然該算法在初始區間劃分時有較多的小區間，但是針對每個特征詞一次劃分只挑選出一個最優的分割點，在區間數目的限制條件下，遞歸次數大量減少，因而區間的總數也隨之大量減少。實驗結果表明，Ts取[10，20]之間的整數時，分類性能較理想。
表1 數據集特性
4 結束語
本文討論了文本分類任務中數據預處理階段的一項重要技術——連續屬性離散化。在對連續屬性離散化的相關理論和典型離散化方法進行分析研究的基礎上，提出了一種基于詞出現和信息增益相結合的多區間連續屬性離散化方法MTPIG，該算法定義了一個離散化過程，離散化用傳統信息檢索的加權技術（如詞頻、TF*IDF等）生成的非二值特征詞空間，判斷原特征空間中每個特征詞屬于或不屬于某給定子區間，將問題轉換成二值表示方式。實驗結果表明，使用MTPIG算法處理文本分類中的數據，其過程簡單，預測精度高，可理解性強。采用該算法離散化數據集后，分類算法的分類性能有所提高。
參考文獻：
[1]李榮陸.文本分類及其相關技術研究[D].上海：復旦大學，2005.
[2]FABRIZIO S，ALESSANDRO S，NICOLA V.An improved boosting algorithm and its application to text categorization[C]//Proc of ACM CIKM International Conference on Information and Knowledge Management.New York:ACMPress，2000:7885.
[3]姚望舒，商琳，陳兆乾.一種基于進化算法的連續屬性離散化方法[J].計算機應用與軟件，2005，22（3）:3739.
[4]FAYYAD U M，IRANI K B.Multiinterval discretization of conti-nuousvalued attributes for classification learning[C]//Proc ofthe 13th International Joint Conference on Artifical Intelligence.1993:10221027.
[5]FRIEDMAN N，GOLDSIMIDT M.Discretizing continuous attributes while learning Bayesian networks[C]//Proc of the 13th International Conference on Machine Learning.[S.l.]:Morgan Kaufmann，1996:157165.
［6］DAUGHERTY J，KOHAVI R，SAHAMI M.Supervised and unsupervised discretization of continuous feature[C]//Proc of the 20th International Conference on Machine Learning.San Francisco:Morgan Kaufmann，1995:194202.
[7]蔣艷凰.遙感圖像高精度并行監督分類技術研究[D].長沙：國防科學技術大學，2004.
[8]KERBER R.ChiMerge:discretization of numeric attributes[C]//Proc of the 10th Conference of the American Association for Articial Intelligence.1992:123128.
[9]QUINLAN J R.Induction of decision trees[J].Machine Learning，1986，1:81106.
[10]QUINLAN J R.Improved use of continuous attributes in C4.5[J].Journal of Articial Intelligence Research，1996，4:7790.
[11]WALLACE C S，PATRICK J D.Coding decision trees[J].Machine Learning，1993，11(1):722.
[12]AUER P，HOLTE R C，MAASS W.Theory and application of agnostic PAClearning with small decision trees[C]//Proc of the 12th PRIEDITIS A，RUSSELL S.International Conference on Machine Learning. San Francisco: Morgan Kaufmann Publishers，1995:2129.
[13][EB/OL].http://www.ics.uci.edu/mlearn/MLRepository.html.
[14]SCHAPIRE R E，SINGER Y.Boostexter:a boostingbased system for text categorization [J]. Maching Learning，2000，39(2/3):135168.
