摘  要： 提出一種基于概率與信息熵理論的實(shí)值屬性離散化方法,，綜合考慮了各對(duì)合并區(qū)間之間的差異性,；該方法利用信息熵衡量相鄰區(qū)間的相似性，同時(shí)考慮離散區(qū)間大小和區(qū)間類別數(shù)對(duì)學(xué)習(xí)精度的影響,，并通過(guò)概率的方法得到了這兩個(gè)因素的衡量標(biāo)準(zhǔn),。仿真結(jié)果表明，新方法對(duì)See5/C5.0分類器有較好的分類學(xué)習(xí)能力,，并在腫瘤診斷中得到了很好的應(yīng)用,。
關(guān)鍵詞： 離散化；數(shù)據(jù)挖掘,；概率,；信息熵

　連續(xù)屬性離散化是數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)的重要預(yù)處理步驟，直接影響到機(jī)器學(xué)習(xí)的效果,。在分類算法中,，對(duì)訓(xùn)練樣本集進(jìn)行離散化具有兩重意義：一方面可以有效降低學(xué)習(xí)算法的復(fù)雜度，加快學(xué)習(xí)速度，提高學(xué)習(xí)精度,；另一方面可以簡(jiǎn)化,、歸納獲得的知識(shí)，提高分類結(jié)果的可理解性,。很多離散化方法的提出,，主要分為以下兩種類型[1]：(1)自底向上和自頂向下的離散化方法。自底向上離散化方法是以每個(gè)屬性值為一個(gè)區(qū)間,，然后迭代地合并相鄰區(qū)間,；自頂向下離散化方法是把整個(gè)屬性的值域視為一個(gè)區(qū)間，遞歸地向該區(qū)間中添加斷點(diǎn),。(2)有監(jiān)督和無(wú)監(jiān)督離散化方法,。有監(jiān)督方法使用決策類信息進(jìn)行離散化，如Ent-MDLP[2],、CAIM[3]和Chi2-based[4-5]等算法,。Ent-MDLP使用熵的理論來(lái)評(píng)價(jià)候選斷點(diǎn)，選擇使得整體熵值最小的斷點(diǎn)作為最終斷點(diǎn),，并且通過(guò)最小描述長(zhǎng)度原則來(lái)確定離散區(qū)間數(shù),；CAIM是一種自頂向下離散化方法，該方法依據(jù)類與屬性間的關(guān)聯(lián)度,，提出一種啟發(fā)式離散化標(biāo)準(zhǔn),，計(jì)算當(dāng)前狀態(tài)的標(biāo)準(zhǔn)值來(lái)判別當(dāng)前斷點(diǎn)是否應(yīng)該被加入斷點(diǎn)集合中。自底向上的Chi2-based離散化算法使用卡方統(tǒng)計(jì)來(lái)確定當(dāng)前相鄰區(qū)間是否被合并,，并采用顯著性水平值逐漸降低的方法檢驗(yàn)系統(tǒng)的不一致率,，確定離散化進(jìn)程是否終止。然而,，Chi2-based方法在衡量區(qū)間差異時(shí)沒有考慮區(qū)間大小和區(qū)間類別數(shù)對(duì)離散化結(jié)果的影響,，可能會(huì)導(dǎo)致學(xué)習(xí)精度的降低；而無(wú)監(jiān)督離散化方法則不考慮類的信息,。傳統(tǒng)的無(wú)監(jiān)督離散化方法包括EWD(Equal Width Discretization)和EFD(Equal Frequency Discretization),，這兩個(gè)算法實(shí)現(xiàn)簡(jiǎn)單且計(jì)算消耗低，但結(jié)果往往難以滿足預(yù)計(jì)的要求,。
本文提出一種基于概率與信息熵理論的實(shí)值屬性離散化方法PIE(Probability and Information Entropy),，綜合考慮了各對(duì)合并區(qū)間之間的差異性，利用信息熵衡量相鄰區(qū)間的相似性,，同時(shí)考慮離散區(qū)間大小和區(qū)間類別數(shù)對(duì)分類能力的影響,，并通過(guò)概率的方法得到了這兩個(gè)因素的衡量指標(biāo)。實(shí)驗(yàn)結(jié)果表明,，PIE顯著地提高了See5/C5.0分類器分類學(xué)習(xí)精度，并在乳腺腫瘤診斷中得到了很好的應(yīng)用,。
1 PIE離散化
　離散化問(wèn)題描述如下：對(duì)于m個(gè)連續(xù)屬性的數(shù)據(jù)集,，樣本點(diǎn)個(gè)數(shù)為N,，決策類別數(shù)為S，數(shù)據(jù)集中任意一個(gè)連續(xù)屬性為a,，可以將連續(xù)屬性的值域離散成I個(gè)區(qū)間：
     P：{[d0,，d1]，[d1,，d2],，…，[dI-1,，dI]}
    其中,，d0是連續(xù)屬性A的最小值，dI是a的最大值,，屬性a的值按升序進(jìn)行排列,，{d0，d1,，d2,，…，dI-1,，dI}為離散過(guò)程中的斷點(diǎn)集合,。屬性a的每個(gè)值都可以劃分到離散的I個(gè)區(qū)間的某一個(gè)區(qū)間中。

　對(duì)于一個(gè)連續(xù)屬性的各對(duì)相鄰區(qū)間,，它們對(duì)應(yīng)的類分布是不同的,，類分布最相似的區(qū)間應(yīng)該先被合并。事實(shí)上,，從信息通信的角度考慮,，區(qū)間在合并前與合并后需要轉(zhuǎn)換信息量，轉(zhuǎn)換的信息量越小,，說(shuō)明兩個(gè)區(qū)間對(duì)應(yīng)的類分布越相似,，它們應(yīng)該被合并，反之亦然,。由于相鄰兩區(qū)間的樣本數(shù)為M,，需要轉(zhuǎn)換M次，因此,，用M×[H(I)-H(I1,，I2)]作為區(qū)間相似性的衡量標(biāo)準(zhǔn)。
　為了更好地衡量各對(duì)合并區(qū)間之間的差異性,，僅考慮類分布的相似性是不夠的,，還需要考慮離散區(qū)間大小和區(qū)間中類別數(shù)對(duì)離散化結(jié)果的影響，進(jìn)而會(huì)影響到分類器的學(xué)習(xí)精度。通過(guò)概率的方法可獲得兩個(gè)因素的衡量標(biāo)準(zhǔn),，對(duì)于任意連續(xù)屬性,，每一對(duì)相鄰區(qū)間(I1和I2)的樣本數(shù)是不同的，可視為變量{Mi},，則p({Mi+})代表兩個(gè)區(qū)間樣本數(shù)的集合可能性,，即：

2 仿真結(jié)果
2.1 UCI數(shù)據(jù)集實(shí)驗(yàn)結(jié)果
　為了評(píng)價(jià)PIE的性能，采用了UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)[7]中的10個(gè)數(shù)據(jù)集,，見表1所示,。該數(shù)據(jù)集是數(shù)據(jù)挖掘等實(shí)驗(yàn)常用的數(shù)據(jù)，其中包括兩個(gè)大的數(shù)據(jù)集Page-blocks和Letter,。PIE方法與以下幾種方法進(jìn)行了比較：傳統(tǒng)的無(wú)監(jiān)督離散化方法EFD,；基于熵的最小描述長(zhǎng)度離散化方法Ent-MDLP；流行的自頂向下離散化方法CAIM,；經(jīng)典的自底向上離散化方法Chi2,。
　10個(gè)數(shù)據(jù)集分別采用上面的離散化方法進(jìn)行離散數(shù)據(jù)，使用Weka數(shù)據(jù)挖掘工具進(jìn)行實(shí)驗(yàn),，采用See5分類器對(duì)離散后的數(shù)據(jù)進(jìn)行分類預(yù)測(cè),。采用10折交叉驗(yàn)證的方法，將數(shù)據(jù)集分成10等份,，分別將其中9份作為訓(xùn)練集,，剩下1份作為測(cè)試集，重復(fù)10次取平均值,，對(duì)平均學(xué)習(xí)精度統(tǒng)計(jì)進(jìn)行對(duì)比,，見表2所示。

　從表2中可以看出,，除了Heart和Vowel數(shù)據(jù)集,，本文提出的PIE離散化方法的See5平均學(xué)習(xí)精度均有所上升，這正是離散化方法期望得到的結(jié)果,，由此充分顯示了PIE算法的優(yōu)勢(shì),。而對(duì)于CAIM、Ent-MDLP和EFD三種離散化方法均則未引入不一致衡量標(biāo)準(zhǔn),，即它們沒有對(duì)數(shù)據(jù)的有效性進(jìn)行控制,，在離散化過(guò)程中丟失了大量的信息，導(dǎo)致分類預(yù)測(cè)的精度比Chi2和PIE方法平均低很多,。
2.2 PIE在乳腺腫瘤診斷上的效用
　乳腺腫瘤診斷的實(shí)驗(yàn)數(shù)據(jù)來(lái)自于UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中的Breast Cancer Wisconsin數(shù)據(jù)集,，將Breast Cancer Wisconsin刪掉屬性值不全的病例樣本，剩下683個(gè)病例樣本,，病理檢測(cè)有9項(xiàng)(Clump Thickness,、Uniformity of Cell Size,、Uniformity of Cell Shape、 Marginal Adhension,、Single Epithelial Cell Size,、Bare Nuclei、Bland Chromatin,、Normal Nucleoli、Mitoses),，即9個(gè)屬性,，每個(gè)屬性取值范圍[1，10],，病情狀況分為兩類：一類表示腫瘤為惡性,，另一類表示腫瘤為良性。這樣,，每個(gè)樣本有9個(gè)連續(xù)條件屬性,，1個(gè)決策屬性，選取樣本的80%作為訓(xùn)練集,，20%作為測(cè)試集,。
　將Breast Cancer Wisconsin用本文所提出的PIE算法進(jìn)行離散化，然后分別使用See5和PIE+See5對(duì)離散前和離散后的數(shù)據(jù)進(jìn)行分類預(yù)測(cè),，結(jié)果見表3,。

　從表3中可以明顯看出，未經(jīng)過(guò)離散化處理的BCW病例數(shù)據(jù)集進(jìn)行See5分類預(yù)測(cè)的測(cè)試準(zhǔn)確度為92.55%,，而PIE+See5方法的測(cè)試準(zhǔn)確度為99.27%,，比未被離散化的進(jìn)行See5預(yù)測(cè)精度高出6.72%，相當(dāng)于每1 000個(gè)患者中就多出約67個(gè)患者可以被準(zhǔn)確地診斷出腫瘤為良性或是惡性,，對(duì)患者及時(shí)治療有很大幫助,。
　在BCW數(shù)據(jù)被離散化后，其病理指標(biāo)被刪去了三項(xiàng)：Uniformity of Cell Shape(細(xì)胞形狀均勻度),、Bland Chromatin(平淡的染色質(zhì)),、Mitoses，可以只考慮其他六項(xiàng),，簡(jiǎn)化了信息系統(tǒng),，減輕了醫(yī)生的工作量。另外,，利用PIE+See5方法離散后不同樣本占樣本總數(shù)比例只有44.36%,，刪除冗余的病例樣本后，只剩余了303個(gè)病例樣本,，從而使原來(lái)的病例樣本空間在橫向和縱向上都得到了降維,，可以得到更加穩(wěn)固的訓(xùn)練模型,，在醫(yī)學(xué)數(shù)據(jù)挖掘中具有良好的發(fā)展前景。
　連續(xù)屬性離散化方法的研究對(duì)數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)領(lǐng)域的研究與應(yīng)用具有重要的作用,。本文提出一種基于概率與信息熵理論的實(shí)值屬性離散化方法,，綜合考慮了各對(duì)合并區(qū)間之間的差異性，能夠更合理準(zhǔn)確地離散化,，該方法為該領(lǐng)域提供了新思路,，具有一定應(yīng)用價(jià)值意義。
參考文獻(xiàn)
[1] DOUGHERTY J,， KOHAVI R,， SAHAMI M. Supervised and unsupervised discretization of continuous feature[C]. Proceedings of the 12th International Conference of Machine learning. San Francisco： Morgan Kaufmann， 1995.
[2] FAYYAD U,， IRANI K. Multi-interval discretization of continuous-valued attributes for classification learning[C]. Proceedings of the 13th International Joint Conference on Artificial Intelligence. San Mateo,， CA： Morgan Kaufmann， 1993.
[3] KURGAN L A,， CIOS K J. CAIM discretization algorithm[J]. IEEE Transactions on Knowledge and Data Engineering,，2004， 16(2)： 145–153.
[4] LIU H,， SETIONO R. Feature selection via discretization[J]. IEEE Transactions on Knowledge and Data Engineering,，1997， 9(4)： 642-645.
[5] CHAO T S,， JYH H H. An extended chi2 algorithm for discretization of real value attributes[J]. IEEE Transactions Knowledge and Data Engineering,， 2005，17(3)：437-441.
[6] PAWLAK Z. Rough sets[J]. International Journal of Computer and Information Sciences,， 1982,，１１(5)：341-356.
[7] HETTICH S， BAY S D. The UCI KDD Archive [DB/OL]. http：//kdd.ics.uci.edu/,， 1999.