摘 要： 提出一種基于概率與信息熵理論的實(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í)沒(méi)有考慮區(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ù)集，見(jiàn)表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ì)比，見(jiàn)表2所示。
從表2中可以看出，除了Heart和Vowel數(shù)據(jù)集，本文提出的PIE離散化方法的See5平均學(xué)習(xí)精度均有所上升，這正是離散化方法期望得到的結(jié)果，由此充分顯示了PIE算法的優(yōu)勢(shì)。而對(duì)于CAIM、Ent-MDLP和EFD三種離散化方法均則未引入不一致衡量標(biāo)準(zhǔn)，即它們沒(méi)有對(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é)果見(jiàn)表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.