基于Rough集的集成離散化算法

劉 靜 何賢芳

（1.重慶三峽學(xué)院實(shí)驗(yàn)中心，重慶萬州 404100）

（2.重慶信息學(xué)院，重慶萬州 404100）

波蘭邏輯學(xué)家Z. Pawlak教授于1982年提出粗糙集理論，[1][2][3]它是一種軟計(jì)算工具，能有效地分析和處理不精確、不一致、不完整等各種不完備信息，并能從中揭示潛在的規(guī)律.近年來粗糙集理論廣泛應(yīng)用于機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等多個(gè)領(lǐng)域.[4]

經(jīng)典的Rough集理論處理的數(shù)據(jù)類型主要針對的是離散型，而現(xiàn)實(shí)世界的數(shù)據(jù)大多是連續(xù)型，因此，離散化處理對于基于Rough理論的知識獲取方法至關(guān)重要.近年來，國內(nèi)外很多學(xué)者已經(jīng)對離散化方法進(jìn)行了相關(guān)研究，并提出了多種算法，如文[4]介紹了等距離劃分的離散化算法和等頻率劃分的離散化算法，文[5]提出了一種結(jié)合多項(xiàng)式超平面與支持向量機(jī)的離散化算法，文[6]提出了基于云理論的離散化算法，文[7]提出了基于層次聚類的離散化算法，文[8]給出了基于分割區(qū)間合并的離散化算法，這類算法有一個(gè)共同特征就是不考慮決策表離散化前后的相容性問題，雖然離散化處理速度較快，離散化后卻可能會導(dǎo)致決策表中的對象產(chǎn)生新的不相容.另一類算法則充分考慮離散化前后決策表的相容性.如文[9，10]提出了基于斷點(diǎn)重要性的離散化算法和貪心算法，這是兩種被廣大研究人員認(rèn)可的識別率較高的離散化算法，文[11]提出了基于信息熵的離散化算法.此類算法雖考慮了決策表的相容性，但算法的計(jì)算復(fù)雜性較高，當(dāng)決策表的候選斷點(diǎn)數(shù)時(shí)較大時(shí)，運(yùn)算速度較慢，處理大數(shù)據(jù)集的性能有待提高.文[12]提出了基于屬性重要性的離散化算法，該算法考慮了決策表的相容性且離散化速度較快，但離散化后斷點(diǎn)較多，識別率較低.因而，研究新的離散化算法是非常有必要的.

本文分析了基于斷點(diǎn)重要性和基于屬性重要性兩種粗糙集離散化算法，根據(jù)這兩種算法的特點(diǎn)提出了基于Rough集的集成離散化算法，實(shí)現(xiàn)了整個(gè)決策表的離散化.實(shí)驗(yàn)結(jié)果表明：文中提出的離散化算法在識別率上和Skowron教授提出的貪心算法相當(dāng)，且能快速處理大數(shù)據(jù)集.

1 Rough集的基本概念

定義 1（決策表[4]）：一個(gè)決策表 S＝＜U,A=C∪D,V, f＞,其中，U是對象的集合，也稱為論域，A=C∪D是屬性集合，C和D分別稱為條件屬性集和決策屬性集，D≠φ，V是屬性值的集合， f: U× A→ V 是一個(gè)信息函數(shù)，它指定了U中每個(gè)對象x的屬性值.

定義 2（不分明關(guān)系[4]）：給定決策表 S＝＜U,A=C∪D,V, f＞,對于每個(gè)屬性子集B?A，定義一個(gè)不分明關(guān)系IND(B)，即

顯然，不分明關(guān)系是一種等價(jià)關(guān)系.

定義3（上、下近似集[4]）：給定決策表S＝＜U, A=C∪D,V, f＞,對于每個(gè)子集X?U和不分明關(guān)系IND(B)，X的上、下近似集分別可以由B的基本集定義如下：

定義4（條件分類和決策分類[4]）：給定決策表S＝＜U, A=C∪D,V, f＞，C和D分別為決策表的條件屬性集和決策屬性集，U|IND(C)和U|IND(D)分別為論域U在屬性集C和D上形成的劃分，條件分類定義為：Ei∈U|IND(C) (i=1,…,m, m為條件分類的個(gè)數(shù))；決策分類定義為：Xj∈U|IND(D) (j=1,…,n, n為決策分類的個(gè)數(shù)).

2 Rough集離散化算法分析

基于Rough集的離散化算法要求離散化前后應(yīng)保持決策表數(shù)據(jù)相容性.很多學(xué)者都對此進(jìn)行了深入的研究，并提出了很多的離散化方法，根據(jù)斷點(diǎn)選擇的過程，又可以把離散化算法分為“逐步添加斷點(diǎn)”和“逐步刪除斷點(diǎn)”的離散化算法.文[10]中的基于斷點(diǎn)重要性的離散化算法屬于“逐步添加斷點(diǎn)”的離散化算法，該算法非常強(qiáng)調(diào)候選斷點(diǎn)之間的相互影響，在實(shí)驗(yàn)中都能取得比較好的效果，不足之處是該算法在對候選斷點(diǎn)的選擇問題上，采取了“每選擇一個(gè)斷點(diǎn)，都需要計(jì)算剩余所有候選斷點(diǎn)的重要性值”的策略，當(dāng)屬性值為浮點(diǎn)且數(shù)據(jù)量較大時(shí)，候選斷點(diǎn)的數(shù)目會接近決策表中的對象數(shù)，因而直接導(dǎo)致了算法的效率不高；文[12]中的基于屬性重要的離散化算法屬于“逐步刪除斷點(diǎn)”的離散化算法，該算法按照屬性重要性對候選斷點(diǎn)依次進(jìn)行刪除判定處理，弱化了候選斷點(diǎn)之間的相互影響，運(yùn)行速度較快，但是該算法對屬性進(jìn)行了排序，依次對屬性上的斷點(diǎn)進(jìn)行“刪除判斷處理”，這種處理方式會導(dǎo)致最終得到的斷點(diǎn)數(shù)目多，從而識別率不高.

2.1 斷點(diǎn)重要性及規(guī)律分析

文獻(xiàn)[10]中給出了一種計(jì)算斷點(diǎn)重要性值的方法.該算法用斷點(diǎn)能區(qū)分的實(shí)例個(gè)數(shù)來衡量斷點(diǎn)的重要性.將能夠被斷點(diǎn)區(qū)分開的實(shí)例對的個(gè)數(shù)定義為其中：為屬性a的第i個(gè)斷點(diǎn)，為屬性a的斷點(diǎn)總數(shù)，集合X基 (X?U)是由斷點(diǎn)可以分開的實(shí)例的集合，U為屬性全集.

決策屬性值為 j( j= 1,...,r,r為決策的種類數(shù))的實(shí)例中，屬于X且屬性a的值小于斷點(diǎn)值的實(shí)例的個(gè)數(shù)記為

所以有：

該算法每次在所有候選斷點(diǎn)集中選取重要性最高的斷點(diǎn)，因而得到的斷點(diǎn)數(shù)目較為合理.但也正是由于它每一次選擇都要重新遍歷所有候選斷點(diǎn)集，當(dāng)數(shù)據(jù)集斷點(diǎn)規(guī)模較大時(shí)，執(zhí)行效率不高.

2.2 基于屬性重要性的算法

基于屬性重要性的算法將知識定義為對對象進(jìn)行分類的能力，該算法通過對分類能力的影響程度來評價(jià)屬性的重要性.為了衡量屬性的重要性程度，可從決策表中刪除這一屬性，再考察決策表的分類會產(chǎn)生的變化.如果去掉該屬性會相應(yīng)地改變分類，則說明該屬性重要性高；反之，說明該屬性的重要性低.該算法首先求出所有的候選斷點(diǎn)，然后求出條件屬性的重要性，對條件屬性按照屬性重要性由小到大對斷點(diǎn)進(jìn)行處理，如果相鄰斷點(diǎn)合后，決策表不引入沖突，則該斷點(diǎn)為冗余斷點(diǎn)，否則加入斷點(diǎn)集，從而將連續(xù)值屬性離散化.這樣可以使屬性重要性較小的屬性的斷點(diǎn)被淘汰的可能性更大，避免了從屬性重要性較大的屬性中去掉過多的斷點(diǎn).

此算法的優(yōu)點(diǎn)是不改變信息系統(tǒng)的不可分辨關(guān)系，還可以刪除冗余的屬性，從而減少了數(shù)據(jù)集的空間維數(shù)且運(yùn)行速度較快.但僅考慮單個(gè)屬性的重要性，沒有考慮各條件屬性之間的相互關(guān)系，可能會導(dǎo)致結(jié)果斷點(diǎn)集產(chǎn)生冗余，得到斷點(diǎn)過多，因而識別率不高.

2.3 基于Rough集的集成離散化算法

根據(jù)以上兩種算法的特點(diǎn)，我們考慮：如果先用基于屬性重要性的算法對決策表進(jìn)行離散化，降低候選斷點(diǎn)的數(shù)目，然后在所有屬性上用基于斷點(diǎn)重要性的算法對候選斷點(diǎn)區(qū)間進(jìn)行選取，可能會又好又快地實(shí)現(xiàn)決策表的離散化.故此，提出了基于Rough集的集成離散化算法.

算法1 基于Rough集的集成離散化算法

Input：決策表 S =＜ U,A =C ∪ D,V,f ＞

Output：決策表S的斷點(diǎn)集 CUTlast和離散化后的決策表S

Step1：根據(jù)條件屬性的重要性由小到大對條件屬性進(jìn)行排序；在屬性重要性相同的情況下，按條件屬性斷點(diǎn)個(gè)數(shù)由多到少對條件屬性進(jìn)行排序；

Step2：對每個(gè)屬性上的斷點(diǎn)進(jìn)行如下過程：將每個(gè)斷點(diǎn)相鄰的兩個(gè)屬性值的較小值改為較大值，如果決策表不引入沖突，則去掉該斷點(diǎn)；否則，把修改過的屬性值還原.由此生成新的候選斷點(diǎn)集CUTfirst；

Step3：令L表示實(shí)例能被斷點(diǎn)集 CUTlast所劃分成的等價(jià)類的集合， CUTlast=?,L ={U};

Step4： 對 每 一 個(gè) c∈CUTfirst， 計(jì) 算WCUTlast(c)；

Step5：選擇 WCUTlast(c)最大的斷點(diǎn)cmax添加到CUTlast中，令

Step6：對所有的X∈L，如果cmax把等價(jià)類X分成X1和X2，那么，從L中去掉X，把等價(jià)類X1和X2加到L中.

Step7：如果L中個(gè)等價(jià)類中的實(shí)例都具有相同的決策則算法結(jié)束，否則轉(zhuǎn)到Step3.

Step8：使用斷點(diǎn)集 CUTlast離散化決策表S，得到新決策表S1， S=S1；

Step9：RETURN CUTlast和離散化后的新決策表S.

設(shè)條件屬性平均取值個(gè)數(shù)為w，即平均斷點(diǎn)個(gè)數(shù)為w×|C|.Step～Step2是一個(gè)典型的基于屬性重要性算法，其時(shí)間復(fù)雜度為：

Step3～Step7是一個(gè)典型的基于斷點(diǎn)重要性算法，其時(shí)間復(fù)雜度為：

所以算法1的時(shí)間復(fù)雜度為：

（這里的k表示經(jīng)第一次離散化后條件屬性上平均斷點(diǎn)個(gè)數(shù)）.空間復(fù)雜度為：

3 實(shí)驗(yàn)結(jié)果

為了驗(yàn)證本文提出算法的運(yùn)行效率和離散化效果，從UCI數(shù)據(jù)庫中選取8組數(shù)據(jù)集進(jìn)行測試，表1是每個(gè)數(shù)據(jù)集的記錄數(shù)和條件屬性個(gè)數(shù).對于每組數(shù)據(jù)集，隨機(jī)抽取一半作為訓(xùn)練集，另一半作為測試集，隨機(jī)抽取5次取平均值作為最終的測試結(jié)果.每個(gè)數(shù)據(jù)集均采用同樣的方法進(jìn)行規(guī)則提取.相關(guān)實(shí)驗(yàn)數(shù)據(jù)如表1、表2和表3所示.

表1 仿真試驗(yàn)數(shù)據(jù)集

表2 離散化后得到的斷點(diǎn)個(gè)數(shù)

表3 離散化算法運(yùn)行時(shí)間和正確識別率

從表2可以看出，使用基于屬性重要性的算法進(jìn)行初次離散化后，各數(shù)據(jù)集的候選斷點(diǎn)數(shù)目大規(guī)模下降.

從表3可以看出，算法1的正確識別率與貪心算法、基于斷點(diǎn)重要性的離散化算法基本相當(dāng)，但是運(yùn)行速度更快，處理的數(shù)據(jù)量更大.從算法1的時(shí)間復(fù)雜度分析，算法1與基于斷點(diǎn)重要性的離散化算法在時(shí)間復(fù)雜度是相當(dāng)?shù)?，但?jīng)過基于屬性重要性的算法初次離散化處理后，候選點(diǎn)急劇下降，因此，雖然算法1的時(shí)間復(fù)雜度與基于斷點(diǎn)重要性算法相同，但運(yùn)行速度要高于貪心算法和基于斷點(diǎn)重要性的離散化算法.

4 結(jié)束語

在基于Rough集的知識獲取過程中，離散化是首要解決的問題.現(xiàn)有的很多離散化算法沒有結(jié)合Rough集的特性，在很大程度上阻礙了Rough集實(shí)際應(yīng)用.文中分別分析了基于斷點(diǎn)重要性的算法和基于屬性重要性的算法，確定了“首先用基于屬性重要性的算法進(jìn)行初次離散化，然后在所有條件屬性集上進(jìn)行斷點(diǎn)選擇”的離散化思路，提出了基于Rough集的集成離散化算法.實(shí)驗(yàn)結(jié)果表明，通過兩種離散化算法的集成，能有效的選中重要的候選斷點(diǎn)，大大降低了候選斷點(diǎn)的數(shù)目，提高了算法的運(yùn)算效率，同時(shí)，也保持了與已有算法可比的識別率.

[1]Pawlak Z. Rough Set[J]. International Journal Of Computer and Information Sciences, 1982, 11: 341-356.

[2]Pawlak Z., Grzymala-Busse J., Slowinski R., Ziarko W. Rough sets[J]. Communications of the ACM, 1995, 38(11): 89-95.

[3]Pawlak Z. Vagueness-a rough set view[A]. In: Mycielski J., Rozenberg G., Salomaa A., eds. Structures in Logic and Computer Science: A selection of Essays in Honor of Andrzej Ehrenfeucht[C], Berlin: Springer-Verlag, 1997: 106-117.

[4]王國胤.Rough集理論與知識獲取[M].西安:西安交通大學(xué)出版社，2001.

[5]何亞群，胡壽松.粗糙集中連續(xù)屬性離散化的一種新方法[J].南京航空航天大學(xué)學(xué)報(bào)，2005，35（3）: 213-215.

[6]李興生.一種基于云模型的連續(xù)屬性離散化方法[J].模式識別與人工智能，2006，16（3）:33-38.

[7]Li M X, Wu C D, Han Z H, Yue Y. A hierarchical clustering method for attribute discretization in rough set theory [A]. In: Proceedings of 3th International Conference on Machining Learning and Cybemetics[C], Shanghai, 2004: 3650-3654.

[8]Su C T, Hsu J H. An extended Chi2 algorithm for discretization of real value attributes [J]. IEEE Transaction on Knowledge and Data Engineering, 2005, 17（3）: 437-441.

[9]Skowron A, Rauszer C. The discernibility functions matrics and functions in information systems [A], in: Intelligent Decision Support-Hand-book of Applications and Advances of the Rough Sets Theory [C], edited by Slowinski A, Dordrecht, Kluwer Academic Publisher, 1992: 331-362

[10]Nguyen H S, Nguyen S H. Some efficient algorithms for rough set methods [A], in: Proceedings of the Sixth International Conference, Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU"96) [C], Granada, Spain, 1996: 1451-1456.

[11]謝宏，程浩忠，牛東曉.基于信息熵的粗糙集連續(xù)屬性離散化算法[J].計(jì)算機(jī)學(xué)報(bào)，2005，28（9）: 1570-1574.

[12]候利娟，王國胤，吳渝.粗糙集理論中的離散化問題[J].計(jì)算機(jī)科學(xué)，2000，27（12）:89-94.