基于改進(jìn)χ2統(tǒng)計的數(shù)據(jù)離散化算法

桑 雨， 李 克 秋＊， 閆 德 勤

(1.大連理工大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，遼寧 大連 116024；2.遼寧師范大學(xué) 計算機與信息技術(shù)學(xué)院，遼寧 大連 116029)

0 引 言

隨著數(shù)據(jù)庫中信息量的增加以及信息管理水平的不斷提高，涌現(xiàn)了各種類型的數(shù)據(jù)來描述客觀世界.在應(yīng)用機器學(xué)習(xí)從數(shù)據(jù)中提取知識時，涉及的數(shù)據(jù)通常包括離散值(如男、女)和連續(xù)值(如身高、溫度等).然而，大多數(shù)的數(shù)據(jù)挖掘、歸納學(xué)習(xí)等算法僅僅適用于使用離散化方法描述的樣本，如 C4.5[1]和 AQ 算法[2]等.因此，連續(xù)屬性必須進(jìn)行離散化，其實質(zhì)是分割連續(xù)屬性的值域，轉(zhuǎn)化成若干個有意義的區(qū)間，簡化數(shù)據(jù)，提高分類器的學(xué)習(xí)精度.

離散化算法的類型有[3]考慮類信息的有監(jiān)督類型和不考慮類信息的無監(jiān)督類型；考慮整體樣本的全局型和考慮部分樣本的局部型；相鄰區(qū)間合并的自底向上型(bottom－up)和區(qū)間分割的自頂向下型(top－down).EQW 和 EQF[3]是實現(xiàn)簡單且計算消耗低的自頂向下無監(jiān)督離散化算法.著名的自頂向下有監(jiān)督離散化算法包括基于信息熵理論的算法，如Ent－MDLP[4]；基于類屬性相互依賴的算法，如 CACC[5].Ent－MDLP通過定義信息熵標(biāo)準(zhǔn)來最小化模型總的信息量，同時利用MDLP來決定合適的離散區(qū)間數(shù).CACC是目前最新的基于類－屬性相互依賴的離散化算法，它提出了一個啟發(fā)式斷點選擇標(biāo)準(zhǔn)，考慮了所有樣本的分布信息，并且避免了過擬合現(xiàn)象，產(chǎn)生了理想的離散化方案.著名的自底向上有監(jiān)督離散化算法包括基于統(tǒng)計學(xué)理論的Chi2－based相關(guān)算法[6～9]，如 ChiMerge[6]和 Extended Chi2[9]等.它們首先初始化區(qū)間，采用χ2統(tǒng)計來判斷當(dāng)前相鄰區(qū)間是否被合并，并且通過不一致衡量標(biāo)準(zhǔn)來判斷離散化進(jìn)程是否結(jié)束.

基于χ2統(tǒng)計的方法是目前最有效的離散化算法之一.自由度與期望頻數(shù)的選取直接影響χ2計算的準(zhǔn)確性，從而影響離散化的性能.本文提出一種基于改進(jìn)χ2統(tǒng)計的數(shù)據(jù)離散化算法，該算法考慮相鄰區(qū)間數(shù)對自由度的影響.此外，對于沒有在相鄰區(qū)間中出現(xiàn)的類，期望頻數(shù)均取一個預(yù)先給定的常數(shù)，忽視了自身的內(nèi)在信息對期望頻數(shù)的影響，導(dǎo)致計算χ2不準(zhǔn)確，區(qū)間合并順序不合理，從而降低了學(xué)習(xí)精度.因此，本文給出自由度與期望頻數(shù)的合理改進(jìn)方案.

1 基礎(chǔ)知識

1.1 粗糙集[10]

設(shè)S＝ (U，A，V，F(xiàn))是一個信息系統(tǒng)，其中U＝｛x1，x2，…，xn｝是論域，A是屬性集合，V是屬性取值集合，F(xiàn)是U×A→V的映射.A由條件屬性集合C與一個決策類屬性d來決定，即A＝C∪d，C∩d＝，則此信息系統(tǒng)被定義為決策表.

對于x，y∈U，PA是U上的一個子集(等價關(guān)系)，如果滿足xPy(p∈P)(fp(x)＝fp(y))，則x和y是在等價關(guān)系P下所構(gòu)成等價類集合中的元素.

定義1 假設(shè)論域U的一個子集為X，條件屬性集合C的一個子集為P，則X關(guān)于P的下近似被定義為

P－X＝ ｛x∈U｜[x]PX｝

其中[x]P是P所產(chǎn)生等價類的元素構(gòu)成的集合.

定義2 等價關(guān)系P關(guān)于決策類屬性所劃分的等價類｛Y1，Y2，…，Yk｝的一致性水平為其中card(·)是集合的基數(shù).

1.2 χ2統(tǒng)計

離散化任務(wù)要求訓(xùn)練集包含N個樣本，每個樣本屬于k個類中的其中一類，且包含m個連續(xù)屬性(條件屬性).基于χ2統(tǒng)計的自底向上離散化算法的實質(zhì)是在所有相鄰區(qū)間對中決定哪一對相鄰區(qū)間首先被選擇合并.

χ2統(tǒng)計可評價被離散區(qū)間與類屬性之間的獨立性.在離散化過程中，需要計算所有相鄰區(qū)間的χ2來判斷當(dāng)前哪對區(qū)間先被合并，計算方法如下:

式中:k為數(shù)據(jù)集總的決策類別數(shù)；Aij為i區(qū)間j類樣本數(shù)；Eij＝Ri×Cj／M，為Aij的期望頻數(shù)，其中為i區(qū)間樣本數(shù)為相鄰兩區(qū)間中j類樣本數(shù)為相鄰兩區(qū)間的樣本總數(shù).如果Cj＝0，則Eij＝0.1.

2 改進(jìn)χ2統(tǒng)計的離散化算法

有效的離散化標(biāo)準(zhǔn)(區(qū)間合并標(biāo)準(zhǔn))可以產(chǎn)生好的離散化結(jié)果.在基于χ2統(tǒng)計的離散化算法中，χ2統(tǒng)計的合理性直接影響離散化的性能.然而，χ2統(tǒng)計中在自由度的選取上僅僅考慮了相鄰區(qū)間的類別數(shù)，忽視了相鄰區(qū)間數(shù)的作用；另外，對于沒有在相鄰區(qū)間中出現(xiàn)的類，其期望頻數(shù)取一個預(yù)先給定的常數(shù)，忽視了數(shù)據(jù)類分布對期望頻數(shù)取值的影響.這些缺陷導(dǎo)致計算χ2不準(zhǔn)確，區(qū)間合并順序不合理，從而降低學(xué)習(xí)精度.基于上面兩點不足，本文提出一種基于改進(jìn)χ2統(tǒng)計的數(shù)據(jù)離散化算法，該算法考慮了相鄰區(qū)間數(shù)對自由度的影響，并依據(jù)數(shù)據(jù)類分布給出了合理的期望頻數(shù)，能夠合理準(zhǔn)確地進(jìn)行離散化.下面，具體分析這兩點不足并且提出有效的改進(jìn)方案.

2.1 χ2分布中自由度選取的不足及改進(jìn)

在Chi2算法[7]中，χ2分布的自由度選取為v＝k－1，k為數(shù)據(jù)總的決策類別數(shù).改進(jìn)的Chi2算法[8]認(rèn)為自由度的選擇應(yīng)該根據(jù)劃分?jǐn)帱c兩邊區(qū)間的類別數(shù)來確定，即v＝k′－1，k′為相鄰區(qū)間對中的類別數(shù)，2≤k′≤k.

一般來說，χ2分布的隨機變量為W＝＋，其中Zi服從標(biāo)準(zhǔn)正態(tài)分布，i＝1，2，…，n.也就是說，W服從自由度為n－1的χ2分布，即分布.這樣，式(2)中的χ2相當(dāng)于χ2分布的隨機變量，由2k′項的加和獲得，即服從自由度為2k′－1的χ2分布.在自由度的選取上，χ2統(tǒng)計僅僅考慮了相鄰區(qū)間的類別數(shù)，忽視了相鄰區(qū)間數(shù)的作用；換句話說，自由度選取不僅僅與相鄰區(qū)間的類別數(shù)有關(guān)，還與相鄰區(qū)間數(shù)有關(guān).因此，應(yīng)該選取v＝2k′－1作為χ2統(tǒng)計顯著性檢驗的自由度.

2.2 χ2分布中期望頻數(shù)Eij取值的不足及改進(jìn)

在式(2)中，如果Cj＝0，則Eij＝0.1.也就是說，如果相鄰區(qū)間的類別數(shù)小于總的類別數(shù)(k′＜k)，則對于沒有在相鄰區(qū)間中出現(xiàn)的類，其期望頻數(shù)Eij均取一個預(yù)先給定的值0.1.然而，這忽視了數(shù)據(jù)類分布對Eij取值的影響，導(dǎo)致計算χ2不準(zhǔn)確以及不合理的區(qū)間合并順序.

假設(shè)存在兩對相鄰區(qū)間，其中一個區(qū)間對的類別數(shù)大于另一對的，且與數(shù)據(jù)集總類數(shù)不等.然而，如果類別較多的區(qū)間對的類分布較均勻，而類別較少的區(qū)間對的類分布不均勻，考慮公平性，如果區(qū)間對類別較多，則適當(dāng)降低Eij取值；如果區(qū)間對類別較少，則適當(dāng)增加Eij取值.基于上面分析，針對數(shù)據(jù)本身的特點，本文啟發(fā)式地選取(2k－v)／2k作為Eij取值的重要部分.然而，當(dāng)數(shù)據(jù)集總的類別數(shù)為3時，(2k－v)／2k中的v是常量，因此，不能區(qū)分出各對相鄰區(qū)間χ2函數(shù)中Eij的差異.本文考慮了相鄰區(qū)間對的自由度與區(qū)間大小的相關(guān)關(guān)系，即自由度越大，區(qū)間樣本數(shù)越多；自由度越小，區(qū)間樣本數(shù)越少，所以，選取(NM)／N作為Eij取值的另一部分.總之，如果相鄰兩區(qū)間的自由度較大，則使Eij按較小比例增加；如果相鄰兩區(qū)間的自由度較小，則使Eij按較大比例增加.基于上面的分析，有以下改進(jìn)方案:

如果k′＜k，并且Cj＝0，則有

其中N為數(shù)據(jù)集總的樣本數(shù)，v＝2k′－1(以改進(jìn)的自由度為標(biāo)準(zhǔn))，2≤k′≤k，i∈｛1，2｝，1＜j≤k.

注 意:式 (3)中 [(2k－v)／2k]· [(N－M)／N]前面乘以2有以下原因.

從上面的分析中可以看到，式(3)可以完整地反映出Eij取值在χ2統(tǒng)計中的合理性，并很好地解決了χ2統(tǒng)計應(yīng)用在Chi2－based算法中的缺陷.

2.3 算法描述

本文所提出的基于改進(jìn)χ2統(tǒng)計的數(shù)據(jù)離散化算法基于的是Chi2－based算法的框架，分為兩個階段進(jìn)行離散化:第一階段考慮整體屬性進(jìn)行區(qū)間合并，算法通過不一致衡量標(biāo)準(zhǔn)自動地進(jìn)行離散化，當(dāng)被離散數(shù)據(jù)的不一致率超過原始數(shù)據(jù)不一致率時，算法停止；第二階段對每個屬性進(jìn)行離散化，使得離散化更加精確.注意:新算法的區(qū)間合并標(biāo)準(zhǔn)為差異與Extended Chi2算法[9]相似，不同的是，本文提出的和χ2采用的是第2章中改進(jìn)的算法.

基于改進(jìn)χ2統(tǒng)計的離散化算法描述如下.

第一階段:

步驟1 設(shè)置顯著水平α＝0.5，根據(jù)式(1)計算數(shù)據(jù)的一致性水平γc.

步驟2 升序排序每個連續(xù)屬性的值，計算所有相鄰區(qū)間改進(jìn)后的χ2以及差異D.

步驟3 考慮整體連續(xù)屬性，選擇合適的相鄰區(qū)間進(jìn)行合并

下面，對新算法的時間復(fù)雜度做具體分析.每個連續(xù)屬性值排序的時間復(fù)雜度為O(NlogN)；對于本文提出的算法，對χ2統(tǒng)計量做了兩處改進(jìn):一是自由度的改進(jìn)；原始自由度v＝k′－1與改進(jìn)自由度v＝2k′－1都是通過相鄰兩區(qū)間中的類別數(shù)k′決定的，然而，求得相鄰區(qū)間類別數(shù)的時間復(fù)雜度是不發(fā)生變化的，因此，自由度的改進(jìn)沒有影響求得差異D所需時間的變化.二是χ2中Eij取值的改進(jìn)；對于Extended Chi2算法，計算χ2的時間復(fù)雜度為O(2kN)，改進(jìn)Eij取值后，計算χ2的時間復(fù)雜度為O(2kN)＋O(M)＝O(2kN)，這里M＜N.綜上，在對χ2統(tǒng)計量改進(jìn)后，不會影響求得差異D所需時間的變化.由于所提出算法的框架相似于Extended Chi2的框架，新算法的時間復(fù)雜度仍為O(KmNlogN)，其中m為連續(xù)屬性個數(shù)，K為算法的增量步數(shù).

3 性能評價

在實驗中，采用了UCI機器學(xué)習(xí)數(shù)據(jù)庫[11]中的9個數(shù)據(jù)集(見表1)來評價本文所提算法的性能.數(shù)據(jù)集均是數(shù)據(jù)挖掘等實驗所常用的.將所提出的基于改進(jìn)χ2統(tǒng)計的離散化算法與下列4種算法進(jìn)行了比較.

(1)EQF:經(jīng)典的無監(jiān)督離散化算法[3]；

(2)Ent－MDLP:基于熵的離散化算法[4]；

(3)Ext－Chi2:最先進(jìn)的自底向上離散化算法[9]；

(4)CACC:最先進(jìn)的自頂向下離散化算法[5].

表1 數(shù)據(jù)集描述Tab.1 Description of datasets

9個數(shù)據(jù)集全部通過上述離散化算法進(jìn)行離散化，在VC＋＋6.0環(huán)境下實現(xiàn).將離散后的數(shù)據(jù)應(yīng)用C4.5方法構(gòu)造決策樹，并采用Naive貝葉斯分類器進(jìn)行分類預(yù)測，使用Weka數(shù)據(jù)挖掘工具[12]進(jìn)行分類預(yù)測，采用10折交叉驗證的方法[13]對平均學(xué)習(xí)精度統(tǒng)計進(jìn)行對比(見表2和3).

表2 C4.5分類預(yù)測結(jié)果Tab.2 Classification and prediction results by C4.5%

表3 Naive貝葉斯分類預(yù)測結(jié)果Tab.3 Classification and prediction results by Naive Bayes %

由表2可以看出，在9個數(shù)據(jù)集上，本文算法的平均分類精度有所提高.由于EQF、Ent－MDLP和CACC均沒有考慮離散化過程中的數(shù)據(jù)信息丟失情況，與本文算法和Ext－Chi2算法相比，這3種算法有較低的分類精度.

由表3可以看出，在正確識別率方面，本文算法的平均學(xué)習(xí)精度是最高的，可見，當(dāng)χ2統(tǒng)計量改善后數(shù)據(jù)的平均學(xué)習(xí)精度顯著提高，充分顯示了本文所提算法的有效性.

4 結(jié) 語

基于概率統(tǒng)計理論的Chi2系列算法為連續(xù)屬性離散化算法的研究提供了新的思路.本文分析了Chi2系列算法中χ2統(tǒng)計量的不足，并提出了合理的改進(jìn)方案，獲得了期望的離散化結(jié)果，提高了分類器的學(xué)習(xí)精度.

[1]QUINLAN J R.C4.5:Programs for Machine Learning [M].San Mateo:Morgan Kaufmann，1993

[2]MICHALSKI R S，MOZETIC I，HONG Ja－rong，etal.The multi－purpose incremental learning system AQ15and its testing application to three medical domains [C]／／ Proceedings of Fifth National Conference on Artificial Intelligence.Pennsylvania:AAAI Press，1986:1041－1045

[3]DOUGHERTY J， KOHAVI R，SAHAMI M.Supervised and unsupervised discretization of continuous feature [C]／／ Proceedings of 12th International Conference of Machine Learning.San Mateo:Morgan Kaufmann，1995:194－202

[4]FAYYAD U，IRANI K.Multi－interval discretization of continuous－valued attributes for classification learning [C]／／ Proceedings of Thirteenth International Joint Conference on Artificial Intelligence.San Mateo:Morgan Kaufmann，1993:1022－1027

[5]TSAI C J，LEE C I，YANG W P.A discretization algorithm based on class－attributes contingency coefficient[J].Information Sciences，2008，178(17):714－731

[6]KERBER R.ChiMerge:discretization of numeric attributes [C]／／ Proceedings of Ninth National Conference on Artificial Intelligence.San Jose:AAAI Press，1992:123－128

[7]LIU H， SETIONO R. Feature selection via discretization [J].IEEE Transactions on Knowledge and Data Engineering，1997，9(4):642－645

[8]TAY E H，SHEN L.A modified Chi2algorithm for discretization [J].IEEE Transactions on Knowledge and Data Engineering，2002，14(3):666－670

[9]SU C T，HSU J H.An extended Chi2algorithm for discretization of real value attributes [J].IEEE Transactions on Knowledge and Data Engineering，2005，17(3):437－441

[10]PAWLAK Z.Rough sets[J].International Journal of Computer and Information Sciences，1982，11(5):341－356

[11]HETTICH S，BAY S D.The UCI KDD archive[DB／OL]. [2010－08－25].http:／／kdd.ics.uci.edu／，1999

[12]PENTAHO.Weka 3:data mining software in Java[EB／OL]. [2010－08－25]. http:／／www.cs.waikato.ac.nz／ml／weka，2007

[13]WEISS S M，KULIKOWSKI C A.Computer systems that learn:classification and prediction methods from statistics，neural nets [M]／／Machine Learning and Expert Systems.San Mateo:Morgan Kaufmann，1990