《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 嵌入式技術(shù) > 設(shè)計應(yīng)用 > 基于系統(tǒng)熵的粗糙集屬性約簡新方法
基于系統(tǒng)熵的粗糙集屬性約簡新方法
來源:微型機與應(yīng)用2011年第9期
李偉濤,劉瓊蓀
(重慶大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院,重慶 401331)
摘要: 在系統(tǒng)熵的基礎(chǔ)上,定義了一種新的屬性重要度并提出了一種基于改進系統(tǒng)熵的粗糙集屬性約簡算法,實驗分析表明,該屬性重要度為啟發(fā)式信息進行的屬性約簡,取得了理想效果。
Abstract:
Key words :

摘  要:系統(tǒng)熵的基礎(chǔ)上,定義了一種新的屬性重要度并提出了一種基于改進系統(tǒng)熵的粗糙集屬性約簡算法,實驗分析表明,該屬性重要度為啟發(fā)式信息進行的屬性約簡,取得了理想效果。
關(guān)鍵詞: 粗糙集;屬性約簡;系統(tǒng)熵

 粗糙集(Rough Set)理論[1]是一種處理不確定、不完整知識的數(shù)學(xué)工具,最早是由Pawlak于1982年提出的?,F(xiàn)在廣泛應(yīng)用于數(shù)據(jù)挖掘、智能控制、模式識別等領(lǐng)域[2-3]。屬性約簡是粗糙集理論中的核心內(nèi)容之一,有許多學(xué)者致力于粗糙集屬性約簡算法的研究。其中應(yīng)用較多的是基于差別矩陣及在此基礎(chǔ)上的一些改進算法[4],雖然該算法可以得到所有的約簡,但是只適合較小的數(shù)據(jù)集;基于代數(shù)觀點的相對約簡算法不能精確地度量粗糙集中的信息粒度劃分;苗奪謙[5]等人提出基于互信息的屬性約簡算法,是建立在條件屬性對決策屬性的信息量基礎(chǔ)上的。然而以上這些屬性約簡算法所依據(jù)的都是條件屬性的分類能力,它們的出發(fā)點都是一樣的,只是采用的標(biāo)準有所不同。最近,有些學(xué)者提出新的屬性約簡定義,認為只關(guān)心條件屬性的分類能力是不夠的,決策屬性的分類能力也應(yīng)該充分考慮,即基于系統(tǒng)熵的屬性約簡定義[6],這種屬性約簡定義同時考慮到了條件屬性和決策屬性的分類能力,是一種較周全的屬性約簡模型。
 本文從系統(tǒng)熵的角度出發(fā),改進了原先的屬性重要度定義,給出了新的屬性重要性的度量方法,并構(gòu)造了相應(yīng)的啟發(fā)式算法,并通過實例驗證了算法的有效性。

 


 這種新的度量方法同時兼顧了系統(tǒng)熵作為一種同時考慮了條件屬性和決策屬性的分類能力和數(shù)值大小對約簡結(jié)果的影響,并充分考慮到了在屬性子集R中添加屬性a∈C-R后系統(tǒng)熵的增量(R自身的熵也被考慮在內(nèi))。這種新的屬性重要性的定義有如下特點:(1)當(dāng)系
3 仿真實例和相關(guān)比較
 為了驗證上述算法的有效性,從UIC數(shù)據(jù)庫中選取了三個具有離散屬性的數(shù)據(jù)庫實例進行驗證。分別采用文中所提到的兩種不同屬性重要性定義的約簡算法對其進行屬性約簡。約簡結(jié)果如表1所示。其中C為該屬性集合所包含的條件屬性的個數(shù),算法1和算法2分別是以系統(tǒng)熵增益率和本文改進的系統(tǒng)熵增益率為屬性重要性度量方法的啟發(fā)式屬性約簡算法。從表中可以看到本文所提出的算法在大多數(shù)情況下獲得的相對約簡屬性個數(shù)較少。


 為了進一步驗證文中所改進算法的特點,使用Zoo數(shù)據(jù)集如表2所示。其中論域U={1,…,101},條件屬性C={hair,feathers,eggs,milk,airborne,aquatic,predator,toothed,backbone,breathes,venomous,fins,legs,tail,domestic,catsize},D={type}為決策屬性。

 如果按照式(1)所提出的屬性重要性來度量各個屬性的重要性,經(jīng)計算得出屬性重要性最大的是{milk}。而依據(jù)本文所提出的屬性重要性得到的結(jié)果是{eggs},算法1所得到的屬性約簡結(jié)果是:Ra={feathers,milk,airborne,aquatic,backbone,breathes,fins,legs}。
 依照本文算法2所得到的屬性約簡結(jié)果是:Rb={milk,eggs,aquatic,legs}。這是因為利用式(1)計算屬性重要性的時候只考慮了屬性本身的值的分布而沒有考慮屬性的相對信息熵,如果某一屬性的相對信息熵較小會導(dǎo)致該屬性的屬性重要度較大,從而會使所選屬性并不是最重要的,或者造成錯選。
本文從系統(tǒng)熵的角度出發(fā),定義了一種新的度量屬性重要性的方法,構(gòu)造了相應(yīng)的啟發(fā)式算法。相對于原算法,本文算法優(yōu)勢明顯,通過實例證明,在大多數(shù)情況下本文的算法所得到的屬性約簡個數(shù)較少。
參考文獻
[1] PAWLAK Z. Rough sets[J]. Int computer & science,1982;11(5):341-356.
[2] 常犁云,王國胤,吳渝.一種基于Rough Set理論的屬性約簡及規(guī)則提取方法[J].軟件學(xué)報,1999,10(11):1206-1211.
[3] Hu Xiaohua, CERCONE N. Learning in relational databases a rough set approach[J]. International Journal of Computational Intelligence,1995,11(2):320-340.
[4] RAUSZER S. The discernibility matrices and functions in information systems[M]. Intelligent Decision Support-Handbook of Applications and Advances of the Rough Sets Theory. Dordrecht Kluwer,1992,31-362.
[5] 苗奪謙,胡桂榮.知識約簡的一種啟發(fā)式算法[J].計算機研究與發(fā)展,1999,36(6):681-684.
[6] Zhao Jun,Wu Zhongfu,Li Hua. System entropy and its application in feature selection[J]. The Journal of China Universities of Posts and Telecommunications, 2004,11(1):100-105.
[7] 苗奪謙,李道國.粗糙集理論算法與應(yīng)用[M].北京:清華大學(xué)出版社,2008.
[8] 王雄彬,鄭雪峰,等,基于系統(tǒng)熵的屬性約簡的簡化差別矩陣方法[J].計算機應(yīng)用研究,2009,26(7):2461-2464.

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載。