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

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

1 引言

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

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

定義2:對于決策信息系統(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是一個論域,P和U為論域U上的2 個等價關(guān)系族,U/ind(P)={X1,X2,…Xn},U/ind(Q)={Y1,Y2,…Yn},則P、Q在U上的子集的概率分布定義如下

(2)

其中

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

重要度

(3)

3 算法描述

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

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

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

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

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

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

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

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

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

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

4 仿真及分析

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

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

4.1 初始斷點集的形成

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

表1 實驗樣本

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

4.2 確定屬性離散次序

從表2的實驗樣本可以得到,決策屬性不可分辨集為{{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)計算得到三個屬性的客觀重要度為{0.3846,0.2308,0.3846},屬性c1、c3的重要度比屬性c2的重要度大,而屬性c3的斷點數(shù)是9個,屬性c1c1的斷點數(shù)是8個,因此在屬性離散時,離散順序為屬性c2c1c3。

4.3 各屬性斷點選取

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

表3 刪除某個斷點后的離散結(jié)果

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

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

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

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

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

4.4 仿真結(jié)果分析

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

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

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

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

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

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

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

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

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

5 結(jié)論

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