粗糙集理論的連續(xù)屬性自適應(yīng)離散化算法

楊素敏,陳 翔,劉啟明,崔 靜

(1. 電子信息系統(tǒng)復(fù)雜電磁環(huán)境效應(yīng)國(guó)家重點(diǎn)實(shí)驗(yàn)室,河南 洛陽(yáng)471003;2. 陸軍工程大學(xué)石家莊校區(qū),河北 石家莊050003)

1 引言

數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)算法大多數(shù)使用的是離散化的數(shù)據(jù),數(shù)據(jù)離散化質(zhì)量的高低直接影響著數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)效果的好壞。連續(xù)屬性離散化的關(guān)鍵是在保證信息丟失最小化的情況下,選擇若干個(gè)有代表性的斷點(diǎn),將每一個(gè)連續(xù)屬性域分割成若干個(gè)有意義的區(qū)間。目前已經(jīng)提出了很多連續(xù)數(shù)據(jù)離散化方法,如基于高斯統(tǒng)計(jì)分布的離散方法[1]、基于不同類型遺傳算法的方法[2,3],以及基于布爾運(yùn)算和粗糙集的算法[4]等,這些算法的不足點(diǎn)是斷點(diǎn)集的選取帶有很大的主觀性,導(dǎo)致大多數(shù)的離散化算法難以得到滿意的離散效果。在分析已有離散化算法的基礎(chǔ)上,提出了粗糙集自適應(yīng)的連續(xù)屬性離散化算法,算法利用粗糙集理論[5-8]計(jì)算各屬性的重要性,在確保信息系統(tǒng)不可分辨關(guān)系不變的情況下,按照重要性由低到高的順序依次進(jìn)行各屬性的離散,以及斷點(diǎn)的選取。算法在確保離散點(diǎn)總數(shù)相對(duì)較少基礎(chǔ)上,保留了重要屬性較多特征點(diǎn),也有效解決了數(shù)據(jù)不相容問(wèn)題。離散結(jié)果為后續(xù)的屬性約簡(jiǎn)提供了有效數(shù)據(jù)保證。

2 粗糙集理論的數(shù)據(jù)離散化問(wèn)題描述

定義2:對(duì)于決策信息系統(tǒng)S=(U,A,V,f),任意屬性集B?A,不可分辨關(guān)系

IND(B)={(x,y)∈U×U:?a∈B(f(x,a)=f(y,a)}

(1)

定義3:設(shè)U是一個(gè)論域,P和U為論域U上的2 個(gè)等價(jià)關(guān)系族,U/ind(P)={X1,X2,…Xn},U/ind(Q)={Y1,Y2,…Yn},則P、Q在U上的子集的概率分布定義如下

(2)

其中

定義4:條件屬性C相對(duì)于決策屬性的分類重要度[9]定義如下:對(duì)于任意B?A,X?U,B的下近似、正域和重要度分別為

重要度

(3)

3 算法描述

連續(xù)屬性離散化質(zhì)量的好壞直接影響后續(xù)數(shù)據(jù)挖掘的效能,為了保證離散的效果,在離散過(guò)程中斷點(diǎn)選取時(shí)必須保證以下兩個(gè)條件:

1)樣本條件屬性和對(duì)應(yīng)決策結(jié)果相對(duì)關(guān)系保證不變;

2)重要性的屬性盡可能保留更多的斷點(diǎn)。

信息系統(tǒng)經(jīng)過(guò)離散化之后,原來(lái)的信息系統(tǒng)轉(zhuǎn)換為離散化的信息系統(tǒng),不同離散方式產(chǎn)生不同決策表。本文首選利用式(3)進(jìn)行屬性重要性的計(jì)算,對(duì)屬性的重要性從低到高排序,離散時(shí)先從重要性低的屬性開(kāi)始,離散過(guò)程中確保不可分辨關(guān)系不變的前提下對(duì)條件屬性構(gòu)成的空間進(jìn)行斷點(diǎn)自適應(yīng)選取。算法具體描述如下:

輸入:決策系統(tǒng)S=(U,A,V,f)

輸出:離散化的決策系統(tǒng)Sd=(U,A,Vd,fd),具體步驟如下:

步驟1:建立各屬性的候選斷點(diǎn)集。將每個(gè)屬性的值按照從小到大排序,然后求取相鄰兩個(gè)屬性值的平均值,并舍棄重復(fù)值,得到初始斷點(diǎn)集。

步驟2:計(jì)算每個(gè)條件屬性的重要性。根據(jù)式(3)計(jì)算每個(gè)條件屬性重要性,并按照條件屬性重要性值的大小對(duì)條件屬性各列由小到大重新排列, 當(dāng)重要性值相同時(shí), 按條件屬性候選斷點(diǎn)個(gè)數(shù)從多到少進(jìn)行排列Ci-1≤Ci≤Ci+1(i=1…N),N為屬性個(gè)數(shù);

步驟3:進(jìn)行各屬性的離散點(diǎn)選取。依次對(duì)每個(gè)條件屬性進(jìn)行如下操作:

按照每個(gè)屬性的候選斷點(diǎn)順序,從小到大刪除各個(gè)候選斷點(diǎn),然后每個(gè)屬性按照剩余候選斷點(diǎn)集進(jìn)行離散,如果離散樣本出現(xiàn)了不相容問(wèn)題,則保留此斷點(diǎn),放入到結(jié)果斷點(diǎn)集,否則舍棄此候選斷點(diǎn)。依次類推,得到所有屬性的斷點(diǎn)集,算法描述如下:

4 仿真及分析

按照第3節(jié)中算法進(jìn)行仿真的詳細(xì)流程如下。

for i=1 to 所有條件屬性列數(shù) 讀取條件屬性列的所有初始斷點(diǎn) 刪除重復(fù)斷點(diǎn)值 讀取條件屬性原始列值 for j=1 to 條件屬性的總行數(shù) 進(jìn)行每個(gè)數(shù)據(jù)的離散 保存原始離散值 end for j=1 to 每個(gè)條件屬性的所有斷點(diǎn)數(shù) 逐個(gè)刪除屬性列的各個(gè)斷點(diǎn) 利用剩余斷點(diǎn)進(jìn)行離散 判斷新的離散結(jié)果是否改變了系統(tǒng)不可變關(guān)系 if 系統(tǒng)不可變關(guān)系沒(méi)有改變 從斷點(diǎn)集中刪除這個(gè)斷點(diǎn) else 保留該斷點(diǎn) end endend

4.1 初始斷點(diǎn)集的形成

數(shù)據(jù)樣本如表1所示,該樣本集包含三個(gè)條件屬性列{c1,c2,c3},決策屬性集D的值域{0,1}。屬性c1的候選斷點(diǎn)集為{1.395,1.44,1.7,1.975,2.18,2.525,3.31,4.2,4.665},屬性c2的候選斷點(diǎn)集為{0.645,0.72,0.8,1.07,1.42,1.575},屬性c3的候選斷點(diǎn)集為{1.15,1.25,1.45,1.8,2.3,2.8,3.3,3.65,3.85},利用候選斷點(diǎn)集得到樣本的初始離散值如表2所示。

表1 實(shí)驗(yàn)樣本

表2 初始離散結(jié)果

4.2 確定屬性離散次序

從表2的實(shí)驗(yàn)樣本可以得到,決策屬性不可分辨集為{{X1,X2,X3,X5,X7,X10},{X4,X6,X8,X9}}。

屬性c1、c2和c3的正域樣本分別為{{X1},{X2},{X3},{X4},{X5},{X6},{X7},{X8},{X9},{X10}}、{{X1},{X2},{X5},{X7},{X8},{X9}}、{{X1},{X2},{X3},{X4},{X5},{X6},{X7},{X8},{X9},{X10}},利用第2節(jié)式(3)計(jì)算得到三個(gè)屬性的客觀重要度為{0.3846,0.2308,0.3846},屬性c1、c3的重要度比屬性c2的重要度大,而屬性c3的斷點(diǎn)數(shù)是9個(gè),屬性c1c1的斷點(diǎn)數(shù)是8個(gè),因此在屬性離散時(shí),離散順序?yàn)閷傩詂2c1c3。

4.3 各屬性斷點(diǎn)選取

按照第3節(jié)步驟3,先舍棄屬性c2最小斷點(diǎn)0.645,然后得到的離散結(jié)果如表3所示:

表3 刪除某個(gè)斷點(diǎn)后的離散結(jié)果

從表中可以看出,刪除屬性c2中0.645這個(gè)斷點(diǎn)后,系統(tǒng)的不可分辨關(guān)系沒(méi)有變化,因此0.645這個(gè)斷點(diǎn)可以去掉。

接著依次刪除屬性c2的其它斷點(diǎn),運(yùn)算結(jié)果都不影響系統(tǒng)的不可分辨關(guān)系,屬性c2最后斷點(diǎn)集{1.575}。

依據(jù)和屬性c2相同流程,對(duì)屬性c1和屬性c3重復(fù)以上的計(jì)算,屬性c1最終斷點(diǎn)值{4.665},屬性c3最終斷點(diǎn)值為{1.15,1.25,1.8,2.8,3.3,3.85}。實(shí)驗(yàn)樣本的最終離散結(jié)果如表4所示。

表4 最終離散結(jié)果

從表4可以看出,對(duì)重要屬性c3保留了較多的離散點(diǎn),而且整體的決策分類關(guān)系沒(méi)有變化。

4.4 仿真結(jié)果分析

對(duì)于實(shí)驗(yàn)樣本又進(jìn)行了直接離散(不考慮屬性重要性)、CAIM典型算法以及基于布爾運(yùn)算的粗糙集理論三種離散算法的實(shí)驗(yàn),結(jié)果分別如表5、表6和表7。

表5 原始順序離散結(jié)果

表6 CAIM典型算法離散結(jié)果

表7 基于布爾運(yùn)算和粗糙集理論算法的離散結(jié)果

從結(jié)果可以看出,按照原始順序離散時(shí)樣本的離散間距為2*2*7=28,本文算法的樣本離散間距為2*2*6=24,離散點(diǎn)總數(shù)也大于本文所提的算法。

其次,從表6和表7可以看出,表6中的樣本X1和X6和表7中的X7和X8的條件屬性值相同,但決策結(jié)果值卻是為0和1,結(jié)果是相矛盾的,即CAIM算法和文獻(xiàn)[4]提出的基于布爾運(yùn)算和粗糙集理論的離散算法都出現(xiàn)了不相容問(wèn)題。

4.5 計(jì)算復(fù)雜度分析

本文所提的算法、CAIM算法、和基于布爾運(yùn)算和粗糙理論的三種算法的計(jì)算復(fù)雜度也是有差別的,結(jié)果如表8所示,其中m代表樣本行,nc代表斷點(diǎn)數(shù),k代表指標(biāo)數(shù)。例如當(dāng)樣本行數(shù)為1000,斷點(diǎn)數(shù)為20,指標(biāo)為10個(gè)時(shí),本文算法的計(jì)算量為2×106,而基于布爾運(yùn)算和粗糙理論的離散算法的計(jì)算量為4×1012,當(dāng)樣本數(shù)較大時(shí),一般計(jì)算機(jī)的性能難以承受計(jì)算能力。

表8 不同算法計(jì)算復(fù)雜度比較

5 結(jié)論

針對(duì)屬性離散質(zhì)量的高低對(duì)后續(xù)屬性約簡(jiǎn)和數(shù)據(jù)挖掘算法的影響,本文提出的粗糙集理論的連續(xù)屬性自適應(yīng)離散化算法較好地降低了離散對(duì)原有數(shù)據(jù)信息量的損失。算法首先利用粗糙集理論計(jì)算出各個(gè)屬性的客觀重要性權(quán)重,先離散重要性低的屬性,算法在保證總斷點(diǎn)數(shù)較少、計(jì)算復(fù)雜度較低情況下較多保留了重要性高的屬性特性,而且在離散過(guò)程中始終檢測(cè)斷點(diǎn)對(duì)決策類別的影響,避免了出現(xiàn)數(shù)據(jù)不相容問(wèn)題,算法對(duì)常規(guī)連續(xù)數(shù)據(jù)的離散有一定的應(yīng)用價(jià)值。