李 杰 ，王 歡

(1.中國科學(xué)院研究生院，北京 100040；2.北華航天工業(yè)學(xué)院 計(jì)算機(jī)科學(xué)與工程系，河北 廊坊 065000)

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

本文提出一種基于概率與信息熵理論的實(shí)值屬性離散化方法 PIE(Probability and Information Entropy)，綜合考慮了各對合并區(qū)間之間的差異性，利用信息熵衡量相鄰區(qū)間的相似性，同時(shí)考慮離散區(qū)間大小和區(qū)間類別數(shù)對分類能力的影響，并通過概率的方法得到了這兩個(gè)因素的衡量指標(biāo)。實(shí)驗(yàn)結(jié)果表明，PIE顯著地提高了See5/C5.0分類器分類學(xué)習(xí)精度，并在乳腺腫瘤診斷中得到了很好的應(yīng)用。

1 PIE離散化

離散化問題描述如下：對于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}為離散過程中的斷點(diǎn)集合。屬性a的每個(gè)值都可以劃分到離散的I個(gè)區(qū)間的某一個(gè)區(qū)間中。

本文主要針對自底向上離散化形式的方法，其實(shí)質(zhì)是在最小化信息丟失的情況下，根據(jù)一定的區(qū)間合并準(zhǔn)則，消除斷點(diǎn)、合并相鄰區(qū)間。對于每個(gè)自底向上離散化任務(wù)而言，連續(xù)屬性相鄰兩個(gè)值的均值被視為一個(gè)斷點(diǎn)，兩個(gè)斷點(diǎn)構(gòu)成一個(gè)區(qū)間。定義Aij為 i區(qū)間j類樣本數(shù) (i∈{1，2}，1≤j≤S)，Mi+=ΣAij為 i區(qū)間樣本數(shù)，M+j=ΣAij為相鄰兩區(qū)間中 j類樣本數(shù)，M=Σ為相鄰兩區(qū)間總的樣本數(shù)。

自底向上離散化方法的目標(biāo)是選用一種有效的區(qū)間合并標(biāo)準(zhǔn)，迭代地合并相鄰區(qū)間，在最小化信息丟失的情況下將連續(xù)屬性值域轉(zhuǎn)換成小數(shù)目有限的區(qū)間。本文提出一種基于概率與信息熵理論的實(shí)值屬性離散化方法PIE，綜合考慮各對合并區(qū)間之間的差異性；利用信息熵衡量相鄰區(qū)間的相似性，同時(shí)考慮離散區(qū)間大小和區(qū)間類別數(shù)對分類能力的影響。

信息熵可以衡量隨機(jī)變量的不確定性，它反映了隨機(jī)變量對應(yīng)類分布的特性，熵值越大，不確定性越大，反之亦然；當(dāng)每個(gè)類含有等數(shù)量樣本時(shí)，熵取最大值log S，當(dāng)區(qū)間中僅有一個(gè)類時(shí)，熵取最小值。對于兩個(gè)相鄰區(qū)間I1和I2，其信息熵可被定義為：

如果獨(dú)立地對待每一個(gè)區(qū)間，可以得到相鄰兩區(qū)間的總體熵，即帶有權(quán)重的每個(gè)區(qū)間熵的和：

對于一個(gè)連續(xù)屬性的各對相鄰區(qū)間，它們對應(yīng)的類分布是不同的，類分布最相似的區(qū)間應(yīng)該先被合并。事實(shí)上，從信息通信的角度考慮，區(qū)間在合并前與合并后需要轉(zhuǎn)換信息量，轉(zhuǎn)換的信息量越小，說明兩個(gè)區(qū)間對應(yīng)的類分布越相似，它們應(yīng)該被合并，反之亦然。由于相鄰兩區(qū)間的樣本數(shù)為M，需要轉(zhuǎn)換M次，因此，用 M×[H(I)-H(I1，I2)]作為區(qū)間相似性的衡量標(biāo)準(zhǔn)。

為了更好地衡量各對合并區(qū)間之間的差異性，僅考慮類分布的相似性是不夠的，還需要考慮離散區(qū)間大小和區(qū)間中類別數(shù)對離散化結(jié)果的影響，進(jìn)而會(huì)影響到分類器的學(xué)習(xí)精度。通過概率的方法可獲得兩個(gè)因素的衡量標(biāo)準(zhǔn)，對于任意連續(xù)屬性，每一對相鄰區(qū)間(I1和I2)的樣本數(shù)是不同的，可視為變量{Mi}，則 p({Mi+})代表兩個(gè)區(qū)間樣本數(shù)的集合可能性，即：

式中取負(fù)對數(shù)，將概率的最大化轉(zhuǎn)化為最小化形式：

由于每個(gè)區(qū)間中的類別數(shù)越小，類分布可能越相似，即區(qū)間樣本數(shù)和類數(shù)越少，越應(yīng)該被合并。因此根據(jù)式(3)，采用SilogMi+作為區(qū)間合并標(biāo)準(zhǔn)的重要部分來評(píng)價(jià)兩個(gè)因素對離散化結(jié)果的影響?；诖耍诟怕逝c熵的區(qū)間合并標(biāo)準(zhǔn)pie被定義為：

其中，Si代表 i區(qū)間中類別數(shù)，i∈{1，2}。 pie 代表了離散區(qū)間之間的差異性衡量，其值越小，區(qū)間越應(yīng)該被合并，反之亦然。PIE采用粗糙集中的近似精度[6]來控制數(shù)據(jù)的信息丟失。PIE算法具體步驟如下：

輸入：N個(gè)樣本的數(shù)據(jù)集，m個(gè)連續(xù)屬性，S個(gè)類。

輸出：離散后的數(shù)據(jù)集，每個(gè)屬性有ti個(gè)區(qū)間。

(1)計(jì)算原始數(shù)據(jù)的近似精度Lcoriginal；

(2)對每一個(gè)連續(xù)屬性值從小到大排序。初始，相同值的集合視為一個(gè)區(qū)間；

(3)計(jì)算所有屬性相鄰區(qū)間對的合并標(biāo)準(zhǔn)值pie，合并最小pie值的兩個(gè)區(qū)間；

(4)計(jì)算當(dāng)前數(shù)據(jù)的一致性水平Lcdiscretized，如果Lcoriginal-Lcdiscretized<θ(θ為數(shù)據(jù)可容忍的信息丟失率)， 返回步驟(3)；否則，停止離散化。

對PIE算法的時(shí)間復(fù)雜性進(jìn)行分析：計(jì)算一致性水平的時(shí)間為O(N2)；對連續(xù)屬性值排序的時(shí)間為O(Nlog2N)；計(jì)算區(qū)間合并標(biāo)準(zhǔn)的時(shí)間為 O(S)，則計(jì)算所有屬性相鄰區(qū)間的合并標(biāo)準(zhǔn)為O(mNS)。因此，該算法總的時(shí)間復(fù)雜性為O(N2)+O(Nlog2N)+O(mNS)-O(N2)。

2 仿真結(jié)果

2.1 UCI數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

為了評(píng)價(jià)PIE的性能，采用了UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫[7]中的10個(gè)數(shù)據(jù)集，見表1所示。該數(shù)據(jù)集是數(shù)據(jù)挖掘等實(shí)驗(yàn)常用的數(shù)據(jù)，其中包括兩個(gè)大的數(shù)據(jù)集Pageblocks和Letter。PIE方法與以下幾種方法進(jìn)行了比較：傳統(tǒng)的無監(jiān)督離散化方法EFD；基于熵的最小描述長度離散化方法Ent-MDLP；流行的自頂向下離散化方法CAIM；經(jīng)典的自底向上離散化方法Chi2。

表1 數(shù)據(jù)信息表

10個(gè)數(shù)據(jù)集分別采用上面的離散化方法進(jìn)行離散數(shù)據(jù)，使用Weka數(shù)據(jù)挖掘工具進(jìn)行實(shí)驗(yàn)，采用See5分類器對離散后的數(shù)據(jù)進(jìn)行分類預(yù)測。采用10折交叉驗(yàn)證的方法，將數(shù)據(jù)集分成10等份，分別將其中9份作為訓(xùn)練集，剩下1份作為測試集，重復(fù)10次取平均值，對平均學(xué)習(xí)精度統(tǒng)計(jì)進(jìn)行對比，見表2所示。

表2 See5平均學(xué)習(xí)精度/%

從表2中可以看出，除了Heart和Vowel數(shù)據(jù)集，本文提出的PIE離散化方法的See5平均學(xué)習(xí)精度均有所上升，這正是離散化方法期望得到的結(jié)果，由此充分顯示了PIE算法的優(yōu)勢。而對于CAIM、Ent-MDLP和EFD三種離散化方法均則未引入不一致衡量標(biāo)準(zhǔn)，即它們沒有對數(shù)據(jù)的有效性進(jìn)行控制，在離散化過程中丟失了大量的信息，導(dǎo)致分類預(yù)測的精度比Chi2和PIE方法平均低很多。

2.2 PIE在乳腺腫瘤診斷上的效用

乳腺腫瘤診斷的實(shí)驗(yàn)數(shù)據(jù)來自于UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫中的BreastCancerWisconsin數(shù)據(jù)集，將Breast Cancer Wisconsin刪掉屬性值不全的病例樣本，剩下683個(gè)病例樣本，病理檢測有9項(xiàng) (Clump Thickness、Uniformity of Cell Size、Uniformity of Cell Shape、 Marginal Adhension、Single EpithelialCellSize、Bare Nuclei、Bland Chromatin、Normal Nucleoli、Mitoses)，即 9 個(gè)屬性，每個(gè)屬性取值范圍[1，10]，病情狀況分為兩類：一類表示腫瘤為惡性，另一類表示腫瘤為良性。這樣，每個(gè)樣本有9個(gè)連續(xù)條件屬性，1個(gè)決策屬性，選取樣本的80%作為訓(xùn)練集，20%作為測試集。

將Breast Cancer Wisconsin用本文所提出的PIE算法進(jìn)行離散化，然后分別使用See5和PIE+See5對離散前和離散后的數(shù)據(jù)進(jìn)行分類預(yù)測，結(jié)果見表3。

表3 BCW病例數(shù)據(jù)集實(shí)驗(yàn)結(jié)果對比

從表3中可以明顯看出，未經(jīng)過離散化處理的BCW病例數(shù)據(jù)集進(jìn)行See5分類預(yù)測的測試準(zhǔn)確度為92.55%，而PIE+See5方法的測試準(zhǔn)確度為99.27%，比未被離散化的進(jìn)行See5預(yù)測精度高出6.72%，相當(dāng)于每1 000個(gè)患者中就多出約67個(gè)患者可以被準(zhǔn)確地診斷出腫瘤為良性或是惡性，對患者及時(shí)治療有很大幫助。

在BCW數(shù)據(jù)被離散化后，其病理指標(biāo)被刪去了三項(xiàng)：Uniformity of Cell Shape(細(xì) 胞 形 狀 均 勻 度 )、Bland Chromatin(平淡的染色質(zhì))、Mitoses，可以只考慮其他六項(xiàng)，簡化了信息系統(tǒng)，減輕了醫(yī)生的工作量。另外，利用PIE+See5方法離散后不同樣本占樣本總數(shù)比例只有44.36%，刪除冗余的病例樣本后，只剩余了303個(gè)病例樣本，從而使原來的病例樣本空間在橫向和縱向上都得到了降維，可以得到更加穩(wěn)固的訓(xùn)練模型，在醫(yī)學(xué)數(shù)據(jù)挖掘中具有良好的發(fā)展前景。

連續(xù)屬性離散化方法的研究對數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)領(lǐng)域的研究與應(yīng)用具有重要的作用。本文提出一種基于概率與信息熵理論的實(shí)值屬性離散化方法，綜合考慮了各對合并區(qū)間之間的差異性，能夠更合理準(zhǔn)確地離散化，該方法為該領(lǐng)域提供了新思路，具有一定應(yīng)用價(jià)值意義。

[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， IRANIK.Multi-intervaldiscretization of continuous-valued attributes for classification learning[C].Proceedings of the 13th International Joint Conference onArtificial Intelligence.San Mateo， CA： Morgan Kaufmann，1993.

[3]KURGAN L A，CIOS K J.CAIM discretization algorithm[J].IEEE Transactionson Knowledge and DataEngineering，2004， 16(2)： 145–153.

[4]LIU H，SETIONO R.Feature selection via discretization[J].IEEE Transactionson Knowledgeand DataEngineering，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，11(5)：341-356.

[7]HETTICH S，BAY S D.The UCI KDD Archive[DB/OL].http：//kdd.ics.uci.edu/， 1999.