基于相對(duì)熵的決策表連續(xù)屬性離散化算法_第1頁(yè)
基于相對(duì)熵的決策表連續(xù)屬性離散化算法_第2頁(yè)
基于相對(duì)熵的決策表連續(xù)屬性離散化算法_第3頁(yè)
基于相對(duì)熵的決策表連續(xù)屬性離散化算法_第4頁(yè)
基于相對(duì)熵的決策表連續(xù)屬性離散化算法_第5頁(yè)
已閱讀5頁(yè),還剩8頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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

2、值用離散數(shù)據(jù)表示.假如某些條件屬性或決策屬性的值域?yàn)檫B續(xù)值(如浮點(diǎn)數(shù)),那么在處理前必須進(jìn)展離散化處理,而且即使對(duì)于離散數(shù)據(jù),有時(shí)也需要通過(guò)將離散值進(jìn)展合并(抽象)得到更高抽象層次的離散值2。該文形式化地描繪了決策表的離散化問(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ì)象的集合,也稱為論域.=是屬性的集合,子集和分別被稱為條件屬性集和決策屬

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

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

5、評(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ā)式算法。2.2知識(shí)的信息量和相對(duì)熵下面將信息論中信息量和相對(duì)熵4-6的概念引入到信息系統(tǒng)中。定義25,6設(shè)K=(U,R)是一近似空間,R在U上的劃分(等價(jià)關(guān)系)為U/IND(R)=R1,R2,Rn,知識(shí)(屬性集合)R的信息量(也稱為信息熵)定義為:;其中=U-Ri,|Ri|/|U|表示等價(jià)類Ri在論域U上的可能

6、性(概率),|/|U|表示Ri的余集在論域U上的可能性,也即不屬于Ri的概率。定義36設(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,Y,知識(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ì)16設(shè)U為論域,K1=(U,P)和K2=(U,Q)是關(guān)于U的兩個(gè)知識(shí)庫(kù),那么有:(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)性質(zhì)26設(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,Y,D是U上的一個(gè)決策即U上的一個(gè)劃分.假如U/IND(P)U/IND(Q),那么(1)E(D;P)E(D;Q),(2)E(D|P)E(D|Q)2.3屬性重要性度量Rugh集理論認(rèn)為知識(shí)是將對(duì)象進(jìn)展分類的才能,屬性的重要性是建立在屬性的分類才能上的,為了衡量屬性的重要性程度,可從表中刪除這一屬性,再來(lái)考察信息系統(tǒng)的分類會(huì)產(chǎn)生怎樣的變化:假如去掉屬性會(huì)相應(yīng)地改變分類,那么說(shuō)明該屬性重要,

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

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

10、)令B=是一鏈表,用來(lái)存儲(chǔ)已排過(guò)序的屬性;b)對(duì)A-B中的每一個(gè)屬性p,根據(jù)定義7計(jì)算其重要性SGF(p,B,D);)選擇使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è)屬性ajA進(jìn)展下面的過(guò)程:Step4:對(duì)屬性aj中的每一個(gè)斷點(diǎn)j,考慮它的存在性,把決策表中與j相鄰的兩個(gè)屬性值的較小值改為較大值,假如斷策表不引起沖突,那么aj=ajj;否那么,把修改正的屬性值復(fù)原。Step5:此時(shí)UT=a1,a2,ak即為所求的斷點(diǎn)集,同時(shí)得到離散化后的決策表。該

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

12、n2),所以Step1時(shí)間復(fù)雜性為(kn2);(2)計(jì)算相對(duì)熵E(D|ai),屬性重要性SGF(p,B,D)的時(shí)間復(fù)雜性為(kn2),對(duì)屬性重要性SGF(p,B,D)進(jìn)展排序的時(shí)間復(fù)雜性為klgk,所以Step2時(shí)間復(fù)雜性為(kn2);(3)把決策表中與j相鄰的兩個(gè)屬性值的較小值改為較大值,檢驗(yàn)決策表是否引起沖突的時(shí)間復(fù)雜性為(n2),所以完成Step3、Step4的時(shí)間復(fù)雜性為(kn2)。因此,整個(gè)算法的時(shí)間復(fù)雜性為(3kn2)。3.3舉例設(shè)原始決策表如表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;計(jì)算屬性重要性,開場(chǎng)B=,所以SGF(a,D)=E(D)-E(D|a)E(D)-E(D|b)=SGF(b,D)對(duì)決策表1,其候選斷點(diǎn)集為:a=0.8,1.1,1.4,1.8,3;b=0.9,2,4由上面的計(jì)算知SGF(b,D)SGF(a,D),所以附屬性b開場(chǎng):首先考慮斷點(diǎn)0.9,它有相鄰屬性值為0.8和1,把屬性值0.8改為1后,不引起決策表的沖突,那么斷點(diǎn)0.9是多余的;接著考慮斷點(diǎn)2,它的相鄰屬性值為1和3;當(dāng)把1改為3時(shí),實(shí)例4和5將會(huì)沖突,這說(shuō)明斷點(diǎn)2是保持決策表的不清楚關(guān)系所必

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

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

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論