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

1、基于相對熵的決策表連續(xù)屬性離散化算法摘要該文提出了一種新的決策表連續(xù)屬性離散化算法.首先使用相對熵來度量條件屬性的重要性,并據(jù)此對條件屬性按照屬性重要性從小到大排序,然后按排序后的順序,考察每個條件屬性的所有斷點,將冗余的斷點去掉,從而將條件屬性離散化.該算法易于理解，計算簡單,算法的時間復雜性為(3kn2)。關鍵詞相對熵;互信息;連續(xù)屬性;離散化;決策表1引言波蘭科學家Palak提出的粗糙集(Rughset)理論1，2是一種新型的處理模糊和不確定知識的數(shù)學工具,目前已經(jīng)在人工智能、知識與數(shù)據(jù)發(fā)現(xiàn)、形式識別與分類、故障檢測等方面得到了較為成功的應用。在運用粗糙集理論處理決策表時,要求決策表中的

2、值用離散數(shù)據(jù)表示.假如某些條件屬性或決策屬性的值域為連續(xù)值(如浮點數(shù)),那么在處理前必須進展離散化處理,而且即使對于離散數(shù)據(jù),有時也需要通過將離散值進展合并(抽象)得到更高抽象層次的離散值2。該文形式化地描繪了決策表的離散化問題,利用相對熵定義了屬性的重要性度量，提出了基于相對熵的決策表離散化算法,并分析了該算法的時間復雜度，最后用例子說明該算法的離散化過程。2根本概念應用粗糙集理論實現(xiàn)知識獲取和數(shù)據(jù)分析通常是對決策表進展處理,為此首先給出決策表的定義.定義1.一個決策表是一個由四元組T=(,)構成的知識表達系統(tǒng),其中是對象的集合,也稱為論域.=是屬性的集合,子集和分別被稱為條件屬性集和決策屬

3、性集.V=是屬性的取值范圍構成的集合,其中r是屬性的值域.:是信息函數(shù),它指定中每一個對象各個屬性的取值.在本文討論中假設決策屬性值為離散值,連續(xù)屬性變量僅出如今條件屬性中,不失一般性,以下僅考慮單個決策屬性的決策表。2.1離散化問題的描繪設T=(,)是一個決策表,其中=1,2,為論域,=,=1,2,k為條件屬性集合|=k,d為決策屬性，設決策種類的個數(shù)為r(d)。屬性a的值域Va=la,ra上的一個斷點可記為(a,),其中aR,為實數(shù)值。在Va=la,ra上的任意一個斷點集合：Da=(a,1a),(a,2a),(a,kaa)定義了Va上的一個分類Pa：Pa=0a,1a)，1a,2a)，kaa

4、,ka+1ala=0a1a2aka+1a=raVa=0a,1a1a,2akaa,ka+1a斷點集合Da將屬性的取值分成k+1個等價類，這里每一個ka就稱為一個斷點，離散化的目的就是對所有連續(xù)屬性都找到適宜的斷點集,因此,任意的P=定義了一個新的決策表:Tp=(U,R,Vp,fp)，fp(xa)=if(xa)ia,i+1a對于xU,i0,1,2,Ka,即經(jīng)過離散化之后,原來的決策表被新的決策表所代替,且不同的斷點集將同一決策表轉換成不同的新決策表。從粗糙集的觀點看,離散化的本質是在保持決策表分類才能不變,即條件屬性和決策屬性相對關系不變的條件下,尋找適宜的分割點集,對條件屬性構成的空間進展劃分。

5、評價屬性離散化的質量,主要看分割點的選擇和多少,以及保持信息系統(tǒng)所表達的樣本之間的“不可分辨關系。最優(yōu)離散化,即為決策表尋找最小(最優(yōu))的斷點集是一個NP-hard問題,為此必須尋找某種啟發(fā)式算法，人們提出了許多啟發(fā)式算法，可參考文獻2，3，該文利用決策屬性相對于條件屬性的相對熵作為啟發(fā)式算法。2.2知識的信息量和相對熵下面將信息論中信息量和相對熵4-6的概念引入到信息系統(tǒng)中。定義25，6設K=(U，R)是一近似空間,R在U上的劃分(等價關系)為U/IND(R)=R1,R2,Rn,知識(屬性集合)R的信息量(也稱為信息熵)定義為:；其中=U-Ri,|Ri|/|U|表示等價類Ri在論域U上的可能

6、性(概率)，|/|U|表示Ri的余集在論域U上的可能性,也即不屬于Ri的概率。定義36設U為論域，K1=(U，P)和K2=(U，Q)是關于U的兩個知識庫，U/IND(P)=X1,X2,Xn,U/IND(Q)=Y1,Y2,Y,知識(屬性集合)Q相對于知識(屬性集合)P的相對熵E(Q|P)定義為:P與Q的互信息定義為：定義中用“相對熵概念,而不用“條件熵,完全是式子中已經(jīng)沒有了條件概率的意義.另外,定義中使用余集來表示,純粹是為了定理的證明時簡便,實際計算時不必用余集.性質16設U為論域，K1=(U，P)和K2=(U，Q)是關于U的兩個知識庫，那么有：(1)E(Q)=E(Q;P)+E(Q|P)(2

7、)E(P)=E(P;Q)+E(P|Q)(3)E(Q;P)=E(P;Q)性質26設U為論域，K1=(U，P)和K2=(U，Q)是關于U的兩個知識庫，U/IND(P)=X1,X2,Xn,U/IND(Q)=Y1,Y2,Y,D是U上的一個決策即U上的一個劃分.假如U/IND(P)U/IND(Q)，那么(1)E(D;P)E(D;Q),(2)E(D|P)E(D|Q)2.3屬性重要性度量Rugh集理論認為知識是將對象進展分類的才能，屬性的重要性是建立在屬性的分類才能上的,為了衡量屬性的重要性程度,可從表中刪除這一屬性,再來考察信息系統(tǒng)的分類會產(chǎn)生怎樣的變化:假如去掉屬性會相應地改變分類,那么說明該屬性重要,

8、反之,那么說明該屬性的重要性低。衡量屬性重要性程度的方法較多,有代數(shù)方法和信息論方法等7，本文利用條件屬性相對于決策屬性的相對熵作為度量方法，有關相對熵的一些性質參見文獻6.定義4(屬性重要性)設T=U,D,V,f是一個決策表,B,那么對任意屬性a-B的相對于決策屬性D的重要性SGF(a,B,D)定義為:SGF(a,B,D)=E(D|B)-E(D|Ba)當B=時,簡記為SGF(a,D)=E(D)-E(D|a)=E(D;a),那么為a與D的“互信息。上述定義說明屬性a-B關于屬性集B對決策屬性D的重要性由B中添加a后所引起的相對熵的變化大小來度量。SGF(a,B,D)的值愈大,說明屬性a-B關于

9、屬性集B對決策屬性D愈重要。3決策表連續(xù)屬性的離散化在開場之前首先介紹一下斷點的概念，斷點是將某個數(shù)值型屬性的值按照由小到大的順序排序，重復的數(shù)值只計一次，兩個相鄰屬性值的均值稱為一個斷點。在離散化之前需要先生成每個條件屬性的斷點集。3.1離散化算法輸入：一個決策表T=U,Ad,V,f,其中=1,2,，A=a1,a2,ak輸出：離散化的決策表。Step1:初始化候選斷點集,令UT=a1，a2，ak,其中aj為屬性ai的候選斷點集Step2:根據(jù)條件屬性的重要性由小到大對每個條件屬性ai(i=1,2,k)進展排序,在值一樣的情形下,按條件屬性斷點個數(shù)從多到少進展排序,屬性重要性按如下步驟產(chǎn)生：a

10、)令B=是一鏈表，用來存儲已排過序的屬性；b)對A-B中的每一個屬性p，根據(jù)定義7計算其重要性SGF(p,B,D)；)選擇使SGF(p,B,D)最大的屬性(當同時有兩個以上的屬性到達最大值時，選取斷點個數(shù)最少的)，假設是p,那么將p插入到B的頭部。假如|A|=|B|，轉step;否那么，轉b);Step3:對每個屬性ajA進展下面的過程：Step4:對屬性aj中的每一個斷點j,考慮它的存在性,把決策表中與j相鄰的兩個屬性值的較小值改為較大值,假如斷策表不引起沖突,那么aj=ajj;否那么,把修改正的屬性值復原。Step5:此時UT=a1，a2，ak即為所求的斷點集,同時得到離散化后的決策表。該

11、算法斷定每一個斷點存在的必要性,去掉冗余的斷點,簡化了決策表,易于生成更一般的決策規(guī)那么.由于離散化過程始終不改變決策表的不可分辯關系，因此算法得到的新決策表仍然是一致的.由于斷點的斷定是從它所屬的條件屬性相對于決策屬性的相對熵由大到小也即屬性重要性由小到大的順序進展的,所以,屬性重要性較小的屬性的斷點被淘汰的概率更大,從而防止了從重要性較大的屬性中去掉過多的斷點,進步了決策表的分類才能.這個離散化過程同時也是屬性約簡的過程(假如一個屬性的所有斷點都被去掉了,就意味著這個屬性是冗余的,可以從決策表中去掉)。3.2算法的時間復雜性(1)求一個屬性的候選斷點集，要經(jīng)過排序和求平均，其時間復雜性為(

12、n2),所以Step1時間復雜性為(kn2);(2)計算相對熵E(D|ai),屬性重要性SGF(p,B,D)的時間復雜性為(kn2),對屬性重要性SGF(p,B,D)進展排序的時間復雜性為klgk,所以Step2時間復雜性為(kn2);(3)把決策表中與j相鄰的兩個屬性值的較小值改為較大值,檢驗決策表是否引起沖突的時間復雜性為(n2),所以完成Step3、Step4的時間復雜性為(kn2)。因此，整個算法的時間復雜性為(3kn2)。3.3舉例設原始決策表如表1所示，其中，決策屬性A=a,b,條件屬性D=d.顯然有：U/d=1,4,6,7,8,2,3,5=Y1,Y2;U/a=1,2,3,6,4,

13、5,7,8=X1,X2,X3,X4,X5;U/b=1,5,2,3,7,8,4,6=Z1,Z2,Z3,Z4;計算屬性重要性，開場B=，所以SGF(a,D)=E(D)-E(D|a)E(D)-E(D|b)=SGF(b,D)對決策表1，其候選斷點集為：a=0.8,1.1,1.4,1.8,3;b=0.9,2,4由上面的計算知SGF(b,D)SGF(a,D),所以附屬性b開場：首先考慮斷點0.9,它有相鄰屬性值為0.8和1,把屬性值0.8改為1后，不引起決策表的沖突，那么斷點0.9是多余的；接著考慮斷點2，它的相鄰屬性值為1和3；當把1改為3時，實例4和5將會沖突，這說明斷點2是保持決策表的不清楚關系所必

14、須具有的斷點，故應該保存；最后考慮斷點4,它的相鄰屬性值為3和5,把屬性值3改為5后，不引起決策表的沖突，那么斷點4是多余的；得到的決策表為表2表1原始決策表表2屬性b離散化后的決策表UabD10.631210.831.2541.61151.6361.21172518451UabD10.65121131.2541.61151.6561.21172518451同樣對屬性a的斷點a=0.9,1.15,1.35,1.5,2.2進展判斷，得決策表為表3，最終得到的決策表為表4。表3屬性a離散化后的決策表表4最終的決策表UabD115121131.6541.61151.6561.61174518451U

15、abD1112311411511611721182114完畢語提出的基于相對熵的離散化算法可在離散化數(shù)據(jù)的同時約簡冗余的屬性,而且保持決策表的一致性不變。數(shù)值離散化以后對屬性表的所有數(shù)據(jù)作屬性約簡和值約減操作,最終獲得簡化的決策表，決策表的每一條記錄就是一個決策規(guī)那么.該算法易于理解，計算簡單。參考文獻:1PalakZ.Rughsettheretialaspetsfreasningabutdate.Pland:arsa,19912王國胤.Rugh集理論與知識獲取.西安:西安交通大學出版社,2001.24-31,51.3林仁炳,王基一.連續(xù)屬性離散化算法的時間復雜性分析J.計算機與現(xiàn)代化,2022,9:40-424林鎮(zhèn)飚,桂現(xiàn)才.粗糙集理論中決策表屬性約簡的信息量表示J.廣西師范學院學報,2022,22(2):35-385梁吉業(yè),曲開社,徐宗本.信息系統(tǒng)的屬性約簡J.系統(tǒng)工程理論與理論,2001,21(12