基于相對(duì)熵的決策表連續(xù)屬性離散化算法

基于相對(duì)熵的決策表連續(xù)屬性離散化算法

摘要該文提出了一種新的決策表連續(xù)屬性離散化算法.首先使用相對(duì)熵來(lái)度量條件屬性的重要性,并據(jù)此對(duì)條件屬性按照屬性重要性從小到大排序,然后按排序后的順序,考察每個(gè)條件屬性的所有斷點(diǎn),將冗余的斷點(diǎn)去掉,從而將條件屬性離散化.該算法易于理解，計(jì)算簡(jiǎn)單,算法的時(shí)間復(fù)雜性為O(3kn2)。關(guān)鍵詞相對(duì)熵;互信息;連續(xù)屬性;離散化;決策表1引言波蘭科學(xué)家Pawlak提出的粗糙集(Roughset)理論[1，2]是一種新型的處理模糊和不確定知識(shí)的數(shù)學(xué)工具,目前已經(jīng)在人工智能、知識(shí)與數(shù)據(jù)發(fā)現(xiàn)、模式識(shí)別與分類(lèi)、故障檢測(cè)等方面得到了較為成功的應(yīng)用。在運(yùn)用粗糙集理論處理決策表時(shí),要求決策表中的值用離散數(shù)據(jù)表示.如果某些條件屬性或決策屬性的值域?yàn)檫B續(xù)值(如浮點(diǎn)數(shù)),則在處理前必須進(jìn)行離散化處理,而且即使對(duì)于離散數(shù)據(jù),有時(shí)也需要通過(guò)將離散值進(jìn)行合并(抽象)得到更高抽象層次的離散值。該文形式化地描述了決策表的離散化問(wèn)題,利用相對(duì)熵定義了屬性的重要性度量，提出了基于相對(duì)熵的決策表離散化算法,并分析了該算法的時(shí)間復(fù)雜度，最后用例子說(shuō)明該算法的離散化過(guò)程。2基本概念應(yīng)用粗糙集理論實(shí)現(xiàn)知識(shí)獲取和數(shù)據(jù)分析通常是對(duì)決策表進(jìn)行處理,為此首先給出決策表的定義.定義1.一個(gè)決策表是一個(gè)由四元組T=(Ｕ,Ｒ,Ｖ,ｆ)構(gòu)成的知識(shí)表達(dá)系統(tǒng),其中Ｕ是對(duì)象的集合,也稱(chēng)為論域.Ｒ=Ｃ∪Ｄ是屬性的集合,子集Ｃ和Ｄ分別被稱(chēng)為條件屬性集和決策屬性集.V=是屬性的取值范圍構(gòu)成的集合,其中Ｖr是屬性ｒ的值域.ｆ:Ｕ×Ｒ→Ｖ是信息函數(shù),它指定Ｕ中每一個(gè)對(duì)象各個(gè)屬性的取值.Ｄ≠Φ.在本文討論中假設(shè)決策屬性值為離散值,連續(xù)屬性變量?jī)H出現(xiàn)在條件屬性中,不失一般性,以下僅考慮單個(gè)決策屬性的決策表。離散化問(wèn)題的描述設(shè)T=(Ｕ,Ｒ,Ｖ,ｆ)是一個(gè)決策表,其中Ｕ={ｘ1,ｘ2,…,ｘｎ}為論域,Ｒ=Ｃ∪{ｄ},C={C1,C2,…,Ck}為條件屬性集合|C|=k,dnbxppd為決策屬性，設(shè)決策種類(lèi)的個(gè)數(shù)為r(d)。屬性a的值域Va=[la,ra]上的一個(gè)斷點(diǎn)可記為(a,c),其中a∈R,c為實(shí)數(shù)值。在Va=[la,ra]上的任意一個(gè)斷點(diǎn)集合：Da={(a,c1a),(a,c2a),…,(a,ckaa)}定義了Va上的一個(gè)分類(lèi)Pa：Pa={[c0a,c1a)，[c1a,c2a)，…，[ckaa,cka+1a]}la=c0ac1ac2a…cka+1a=raVa=[c0a,c1a]∪[c1a,c2a]∪…∪[ckaa,cka+1a]斷點(diǎn)集合Da將屬性ａ的取值分成kａ+1個(gè)等價(jià)類(lèi)，這里每一個(gè)cka就稱(chēng)為一個(gè)斷點(diǎn)，離散化的目的就是對(duì)所有連續(xù)屬性都找到適宜的斷點(diǎn)集,因此,任意的P=定義了一個(gè)新的決策表:Tp=(U,R,Vp,fp)，fp(xa)=if(xa)∈[cia,ci+1a]對(duì)于x∈U,i∈{0,1,2,…,Ka},即經(jīng)過(guò)離散化之后,原來(lái)的決策表被新的決策表所代替,且不同的斷點(diǎn)集將同一決策表轉(zhuǎn)換成不同的新決策表。從粗糙集的觀點(diǎn)看,離散化的實(shí)質(zhì)是在保持決策表分類(lèi)能力不變,即條件屬性和決策屬性相對(duì)關(guān)系不變的條件下,尋找合適的分割點(diǎn)集,對(duì)條件屬性構(gòu)成的空間進(jìn)行劃分。評(píng)價(jià)屬性離散化的質(zhì)量,主要看分割點(diǎn)的選擇和多少,以及保持信息系統(tǒng)所表達(dá)的樣本之間的“不可分辨關(guān)系”。最優(yōu)離散化,即為決策表尋找最小(最優(yōu))的斷點(diǎn)集是一個(gè)NP-hard問(wèn)題,為此必須尋找某種啟發(fā)式算法，人們提出了許多啟發(fā)式算法，可參考文獻(xiàn)[2，3]，該文利用決策屬性相對(duì)于條件屬性的相對(duì)熵作為啟發(fā)式算法。知識(shí)的信息量和相對(duì)熵下面將信息論中信息量和相對(duì)熵[4-6]的概念引入到信息系統(tǒng)中。定義2[5，6]設(shè)K=(U，R)是一近似空間,R在U上的劃分(等價(jià)關(guān)系)為U/IND(R)={R1,R2,…,Rn},知識(shí)(屬性集合)R的信息量(也稱(chēng)為信息熵)定義為:；其中=U-Ri,|Ri|/|U|表示等價(jià)類(lèi)Ri在論域U上的可能性(概率)，||/|U|表示Ri的余集在論域U上的可能性,也即不屬于Ri的概率。定義3設(shè)U為論域，K1=(U，P)和K2=(U，Q)是關(guān)于U的兩個(gè)知識(shí)庫(kù)，U/IND(P)={X1,X2,…,Xn},U/IND(Q)={Y1,Y2,…,Ym},知識(shí)(屬性集合)Q相對(duì)于知識(shí)(屬性集合)P的相對(duì)熵E(Q|P)定義為:P與Q的互信息定義為：定義中用“相對(duì)熵”概念,而不用“條件熵”,完全是式子中已經(jīng)沒(méi)有了條件概率的意義.另外,定義中使用余集來(lái)表示,純粹是為了定理的證明時(shí)簡(jiǎn)便,實(shí)際計(jì)算時(shí)不必用余集.性質(zhì)1設(shè)U為論域，K1=(U，P)和K2=(U，Q)是關(guān)于U的兩個(gè)知識(shí)庫(kù)，則有：(1)E(Q)=E(Q;P)+E(Q|P)(2)E(P)=E(P;Q)+E(P|Q)(3)E(Q;P)=E(P;Q)性質(zhì)2設(shè)U為論域，K1=(U，P)和K2=(U，Q)是關(guān)于U的兩個(gè)知識(shí)庫(kù)，U/IND(P)={X1,X2,…,Xn},U/IND(Q)={Y1,Y2,…,Ym},D是U上的一個(gè)決策.如果U/IND(P)U/IND(Q)，則(1)E(D;P)≥E(D;Q),(2)E(D|P)≤E(D|Q)屬性重要性度量Rough集理論認(rèn)為知識(shí)是將對(duì)象進(jìn)行分類(lèi)的能力，屬性的重要性是建立在屬性的分類(lèi)能力上的,為了衡量屬性的重要性程度,可從表中刪除這一屬性,再來(lái)考察信息系統(tǒng)的分類(lèi)會(huì)產(chǎn)生怎樣的變化:如果去掉屬性會(huì)相應(yīng)地改變分類(lèi),則說(shuō)明該屬性重要,反之,則說(shuō)明該屬性的重要性低。衡量屬性重要性程度的方法較多,有代數(shù)方法和信息論方法等，本文利用條件屬性相對(duì)于決策屬性的相對(duì)熵作為度量方法，有關(guān)相對(duì)熵的一些性質(zhì)參見(jiàn)文獻(xiàn).定義4(屬性重要性)設(shè)T=〈U,C∪D,V,f〉是一個(gè)決策表,BC,則對(duì)任意屬性a∈{C-B}的相對(duì)于決策屬性D的重要性SGF(a,B,D)定義為:SGF(a,B,D)=E(D|B)-E(D|B∪{a})當(dāng)B=Φ時(shí),簡(jiǎn)記為SGF(a,D)=E(D)-E(D|{a})=E(D;a),則為a與D的“互信息”。上述定義表明屬性a∈C-B關(guān)于屬性集B對(duì)決策屬性D的重要性由B中添加{a}后所引起的相對(duì)熵的變化大小來(lái)度量。SGF(a,B,D)的值愈大,說(shuō)明屬性a∈C-B關(guān)于屬性集B對(duì)決策屬性D愈重要。3決策表連續(xù)屬性的離散化在開(kāi)始之前首先介紹一下斷點(diǎn)的概念，斷點(diǎn)是將某個(gè)數(shù)值型屬性的值按照由小到大的順序排序，重復(fù)的數(shù)值只計(jì)一次，兩個(gè)相鄰屬性值的均值稱(chēng)為一個(gè)斷點(diǎn)。在離散化之前需要先生成每個(gè)條件屬性的斷點(diǎn)集。離散化算法輸入：一個(gè)決策表T=,其中Ｕ={ｘ1,ｘ2,…,ｘｎ}，A={a1,a2,…,ak}輸出：離散化的決策表。Step1:初始化候選斷點(diǎn)集,令CUT={Ca1，Ca2，…，Cak},其中Caj為屬性ai的候選斷點(diǎn)集Step2:根據(jù)條件屬性的重要性由小到大對(duì)每個(gè)條件屬性ai(i=1,2,…,k)進(jìn)行排序,在值相同的情形下,按條件屬性斷點(diǎn)個(gè)數(shù)從多到少進(jìn)行排序,屬性重要性按如下步驟產(chǎn)生：a)令B=Φ是一鏈表，用來(lái)存儲(chǔ)已排過(guò)序的屬性；b)對(duì)A-B中的每一個(gè)屬性p，根據(jù)定義7計(jì)算其重要性SGF(p,B,D)；

c)選擇使SGF(p,B,D)最大的屬性(當(dāng)同時(shí)有兩個(gè)以上的屬性達(dá)到最大值時(shí)，選取斷點(diǎn)個(gè)數(shù)最少的)，假設(shè)是p,則將p插入到B的頭部。如果|A|=|B|，轉(zhuǎn)step;否則，轉(zhuǎn)b);Step3:對(duì)每個(gè)屬性aj∈A進(jìn)行下面的過(guò)程：Step4:對(duì)屬性aj中的每一個(gè)斷點(diǎn)cj,考慮它的存在性,把決策表中與cj相鄰的兩個(gè)屬性值的較小值改為較大值,如果決策表不引起沖突,則Caj=Caj“{cj};否則,把修改過(guò)的屬性值還原。Step5:此時(shí)CUT={Ca1，Ca2，…，Cak}即為所求的斷點(diǎn)集,同時(shí)得到離散化后的決策表。該算法判定每一個(gè)斷點(diǎn)存在的必要性,去掉冗余的斷點(diǎn),簡(jiǎn)化了決策表,易于生成更一般的決策規(guī)則.由于離散化過(guò)程始終不改變決策表的不可分辯關(guān)系，因此算法得到的新決策表仍然是一致的.由于斷點(diǎn)的判定是從它所屬的條件屬性相對(duì)于決策屬性的相對(duì)熵由大到小的順序進(jìn)行的,所以,屬性重要性較小的屬性的斷點(diǎn)被淘汰的概率更大,從而避免了從重要性較大的屬性中去掉過(guò)多的斷點(diǎn),提高了決策表的分類(lèi)能力.這個(gè)離散化過(guò)程同時(shí)也是屬性約簡(jiǎn)的過(guò)程(如果一個(gè)屬性的所有斷點(diǎn)都被去掉了,就意味著這個(gè)屬性是冗余的,可以從決策表中去掉)。算法的時(shí)間復(fù)雜性(1)求一個(gè)屬性的候選斷點(diǎn)集，要經(jīng)過(guò)排序和求平均，其時(shí)間復(fù)雜性為O(n2),所以Step1時(shí)間復(fù)雜性為O(kn2);(2)計(jì)算相對(duì)熵E(D|ai),屬性重要性SGF(p,B,D)的時(shí)間復(fù)雜性為O(kn2),對(duì)屬性重要性SGF(p,B,D)進(jìn)行排序的時(shí)間復(fù)雜性為klogk,所以Step2時(shí)間復(fù)雜性為O(kn2);(3)把決策表中與cj相鄰的兩個(gè)屬性值的較小值改為較大值,檢驗(yàn)決策表是否引起沖突的時(shí)間復(fù)雜性為O(n2),所以完成Step3、Step4的時(shí)間復(fù)雜性為O(kn2)。因此，整個(gè)算法的時(shí)間復(fù)雜性為O(3kn2)。舉例設(shè)原始決策表如表1所示，其中，決策屬性A={a,b},條件屬性D=hnz1nnj.顯然有：U/hjn5d1n={{1,4,6,7,8},{2,3,5}}={Y1,Y2};U/{a}={{1},{2},{3,6},{4,5},{7,8}}={X1,X2,X3,X4,X5};U/={{1,5},{2},{3,7,8},{4,6}}={Z1,Z2,Z3,Z4};計(jì)算屬性重要性，開(kāi)始B=Φ，所以SGF(a,D)=E(D)-E(D|a)E(D)-E(D|b)=SGF(b,D)對(duì)決策表1，其候選斷點(diǎn)集為：Ca={,,,,3};Cb={,2,4}由上面的計(jì)算知SGF(b,D)SGF(a,D),所以從屬性b開(kāi)始：首先考慮斷點(diǎn),它有相鄰屬性值為和1,把屬性值改為1后，不引起決策表的沖突，則斷點(diǎn)是多余的；接著考慮斷點(diǎn)2，它的相鄰屬性值為1和3；當(dāng)把1改為3時(shí)，實(shí)例4和5將會(huì)沖突，這說(shuō)明斷點(diǎn)2是保持決策表的不分明關(guān)系所必須具有的斷點(diǎn)，故應(yīng)該保留；最后考慮斷點(diǎn)4,它的相鄰屬性值為3和5,把屬性值3改為5后，不引起決策表的沖突，則斷點(diǎn)4是多余的；得到的決策表為表2表1原始決策表表2屬性b離散化后的決策表

同樣對(duì)屬性a的斷點(diǎn)Ca={,,,,}進(jìn)行判斷，得決策表為表3，最終得到的決策表為表4。表3屬性a離散化后的決策表表4最終的決策表

4結(jié)束語(yǔ)提出的基于相對(duì)熵的離散化算法可在離散化數(shù)據(jù)的同時(shí)約簡(jiǎn)冗余的屬性,而且保持決策表的一致性不變。數(shù)值離散化以后對(duì)屬性表的所有數(shù)據(jù)作屬性約簡(jiǎn)和值約減操作,最終獲得簡(jiǎn)化的決策表，決策表的每一條記錄就是一個(gè)決策規(guī)則.該算法易于理解，計(jì)算簡(jiǎn)單。參考文獻(xiàn):[1]PawlakZ.Roughsettheoreticalaspectsofreasoningaboutdate[M].Poland:Warsaw,1991王國(guó)胤.Rough集理論與知識(shí)獲取[M].西安:西安交通大學(xué)出版社,,51.林仁炳,王基一.連續(xù)屬性離散化算法的時(shí)間復(fù)雜性分析[J].計(jì)算機(jī)與現(xiàn)代化,2005,9:40-42林鎮(zhèn)飚,桂現(xiàn)才.粗糙集理論中決策表屬性約簡(jiǎn)的信息量表示[J].廣西師范學(xué)院學(xué)報(bào),2005,22(2):35-38梁吉業(yè),曲開(kāi)社,徐宗本.信息系統(tǒng)的屬性約簡(jiǎn)[J].系統(tǒng)工程理論與實(shí)踐,2001,21(12):Liang,Chin,