基于決策規(guī)則的屬性約簡(jiǎn)算法

廖 倩，李相朋

（武漢紡織大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，湖北 武漢 430073）

基于決策規(guī)則的屬性約簡(jiǎn)算法

廖 倩，李相朋*

（武漢紡織大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院，湖北 武漢 430073）

屬性約簡(jiǎn)是粗糙集的核心問題之一。本文基于決策規(guī)則給出屬性約簡(jiǎn)相關(guān)結(jié)論和屬性重要性，提出啟發(fā)式約簡(jiǎn)算法，引入黃金分割法思想，提高算法效率，并以實(shí)例驗(yàn)證算法有效性和正確性。

屬性約簡(jiǎn)；決策規(guī)則；重要性；黃金分割

1 引言

粗糙集理論[1,2]是由Z.pawlak于1982年提出的，它是一種刻畫不完整性和不確定性的數(shù)學(xué)工具，能有效地分析和處理不精確、不一致、不完整等各種不完備信息，并從中發(fā)現(xiàn)隱含的知識(shí)，揭示潛在的規(guī)律。目前，粗糙集理論已被廣泛應(yīng)用在機(jī)器學(xué)習(xí)與知識(shí)發(fā)現(xiàn)、數(shù)據(jù)挖掘、決策支持與分析等方面。

信息系統(tǒng)是粗糙集理論的主要研究對(duì)象，屬性約簡(jiǎn)是信息系統(tǒng)的核心問題之一。所謂屬性約簡(jiǎn)就是在保持分類能力或決策能力不變的情況下，刪除冗余屬性。由于求所有約簡(jiǎn)已被證明是NP完全問題[3]，故很多算法[4,5]一般采用啟發(fā)式信息找出最優(yōu)或次優(yōu)約簡(jiǎn)，這些算法的共同特點(diǎn)是利用屬性的重要性作為啟發(fā)式信息。因此，如何有效的計(jì)算屬性的重要性，對(duì)提高算法效率是非常重要的。目前對(duì)屬性重要性的度量主要有基于分辨矩陣屬性頻率[6,7]、基于正區(qū)域[8,9]和基于信息熵[10]等方法。然而，這些方法的復(fù)雜度較高，影響約簡(jiǎn)算法的效率。

現(xiàn)有粗糙集算法的低效性在一定程度上限制了粗糙集理論的廣泛應(yīng)用，故尋求高效的粗糙集算法具有重要的意義。目前許多約簡(jiǎn)算法都是基于保持正域不變的思想來(lái)實(shí)現(xiàn)[11,12]，本文基于確定決策規(guī)則不變給出屬性約簡(jiǎn)相關(guān)結(jié)論和屬性重要性，提出改進(jìn)約簡(jiǎn)算法。改進(jìn)的算法不需要計(jì)算分辨矩陣和正域，并且一次性可刪除多個(gè)屬性，減少計(jì)算量，從而提高算法效率。通過(guò)實(shí)例驗(yàn)證該約簡(jiǎn)算法有效性和正確性。

2 粗糙集基本概念[11,13]

3 基于決策規(guī)則的屬性約簡(jiǎn)和屬性重要性

3.1 屬性約簡(jiǎn)

3.2 屬性重要性

前面已經(jīng)提到，很多算法都以屬性重要性為啟發(fā)信息進(jìn)行屬性約簡(jiǎn)。而我們知道屬性約簡(jiǎn)只是手段，獲取決策規(guī)則才是最終目的。為了保證決策規(guī)則的完整性，下面我們就在決策規(guī)則的基礎(chǔ)上定義屬性重要性。

用式（1）計(jì)算屬性重要度后，對(duì)其進(jìn)行排序，如果存在多個(gè)屬性的重要度相同，則這些屬性之間可任排。以此排序?yàn)閱l(fā)式信息進(jìn)行屬性約簡(jiǎn)。

4 屬性約簡(jiǎn)算法

4.1 黃金分割法[14]

黃金分割法是優(yōu)化計(jì)算中的經(jīng)典算法，以算法簡(jiǎn)單、效果顯著而著稱，是許多優(yōu)化算法的基礎(chǔ)。其基本思想是：依照“去壞留好”原則、對(duì)稱原則、以及等比收縮原則來(lái)逐步縮小搜索范圍。具體來(lái)說(shuō)，就是在區(qū)間，如果x1的結(jié)果較好，令a=x1；如果x2的結(jié)果較好，令，重新開始。這樣每次可將搜索區(qū)間縮小0.382倍或0.618倍，直至縮為一點(diǎn)。受該算法的啟發(fā)，我們將這一方法應(yīng)用到屬性約簡(jiǎn)算法中。由于在約簡(jiǎn)算法中取兩點(diǎn)進(jìn)行研究時(shí)，判斷過(guò)程較復(fù)雜，會(huì)增加算法本身的復(fù)雜度。因此，本文只取一個(gè)點(diǎn)進(jìn)行研究，每次也能將搜索空間縮小0.618倍。

4.2 改進(jìn)的屬性約簡(jiǎn)算法

該算法的基本思想是根據(jù)屬性的重要性從條件屬性中逐漸刪除屬性重要性小的屬性，從而得到一個(gè)相對(duì)約簡(jiǎn)。本算法改進(jìn)的方面有三：一、計(jì)算屬性重要度。根據(jù)定義6計(jì)算重要度時(shí)，無(wú)需生成分辨矩陣，節(jié)省空間；二、刪除過(guò)程。傳統(tǒng)約簡(jiǎn)算法，一次只刪除一個(gè)屬性，本文引入黃金分割的思想，一次性可以刪除一個(gè)屬性集，減少計(jì)算量；三、判斷標(biāo)準(zhǔn)。傳統(tǒng)約簡(jiǎn)算法基于正區(qū)域判斷是否是約簡(jiǎn)集，而本算法根據(jù)是否為包含關(guān)系來(lái)判斷。記該算法為算法2，具體步驟如下：

5 實(shí)例分析

下面通過(guò)一個(gè)例子來(lái)說(shuō)明改進(jìn)的約簡(jiǎn)算法，表1為某決策表。

表1 決策表

6 結(jié)束語(yǔ)

本文深入分析屬性約簡(jiǎn)，提出改進(jìn)約簡(jiǎn)算法。總的來(lái)說(shuō)，改進(jìn)算法以屬性重要性為啟發(fā)信息，基于等價(jià)類計(jì)算重要性，無(wú)需生成分辨矩陣，節(jié)省空間；以條件屬性集為起點(diǎn)，無(wú)需計(jì)算核屬性，降低復(fù)雜度；給出屬性約簡(jiǎn)相關(guān)結(jié)論判斷是否為相對(duì)約簡(jiǎn)，無(wú)需計(jì)算正域，判斷過(guò)程更簡(jiǎn)單高效；引入黃金分割法思想，逐漸刪除重要性小的屬性集，節(jié)省時(shí)間。通過(guò)實(shí)例證明了本算法的有效性。本文算法只適用于一致決策表，應(yīng)用該算法在不一致決策表中進(jìn)行屬性約簡(jiǎn)有待做進(jìn)一步的研究。

[1] PAWLAK Z. Rough sets [J]. Communication of the ACM, 1995, 38(11):89-95.

[2] PAWLAK Z. Rough set theory and its applications to data analysis [J]. Cyberneties and System, 1998, 29(7): 661-668.

[3] Wong S K M, Ziarko W. On optimal decision rules in decision tables[J]. Bulletin of Polish Academy of Sciences, 1985, 33 (11-12):693-696.

[4] 李永華，蔣蕓，王小菊. 一種基于Rough集的屬性約簡(jiǎn)的改進(jìn)算法[J].計(jì)算機(jī)應(yīng)用,2008,28(8):2000-2002.

[5] 吳靜，鄒海. 基于屬性重要性的屬性約簡(jiǎn)算法[J].計(jì)算機(jī)應(yīng)用與軟件，2010,27(2)：255-257.

[6] 王玨，王任，苗奪謙，等. 基于Rough Set理論的“數(shù)據(jù)濃縮”[J].計(jì)算機(jī)學(xué)報(bào), 1998 , 21 (5): 393-399.

[7] Wang Jue, Wang Ju. Reduction algorithms based on discernibility matrix: The ordered attributes method[J]. Journal of Computer Science & Technology , 2001 , 16 (6) : 489-504.

[8] Hu X H, Cercone N. Learning in relational databases: A rough setapproach[J]. International Journal of Computational Intelligence,1995, 11 (2): 323-338.

[9] Jelonek J, Krawiec K, Slowinski R. Rough set reduction of attributes and their domains for neural networks[J].International Journal of Computational Intelligence , 1995 , 11 (2) : 339-347.

[10] 苗奪謙，胡桂榮. 知識(shí)約簡(jiǎn)的一種啟發(fā)式算法[J]. 計(jì)算研究與發(fā)展, 1999 , 36 (6) : 681-684.

[11] 張文修，吳偉志，梁吉業(yè)，等. 粗糙集理論與方法[M]. 北京：科學(xué)出版社,2001.

[12] 羅來(lái)鵬，劉而根，王廣超. 基于矩陣的最簡(jiǎn)決策規(guī)則獲取[J]. 計(jì)算機(jī)工程，2008,34(19):41-43.

[13] 吳今培，孫德山. 現(xiàn)代數(shù)據(jù)分析[M]. 北京:機(jī)械工業(yè)出版社,2006.

[14] 宋巨龍，錢富才. 基于黃金分割法的全局最優(yōu)方法[J]. 計(jì)算機(jī)工程與應(yīng)用，2005,4:94-95.

Attribute Reduction Algorithm Based on Decision Rule

LIAO Qian, LI Xiang-peng
(College of Mathematics and Computer Science, Wuhan Textile University, Wuhan Hubei 430073, China)

Attribute reduction is one of the key problems of rough set. In this paper, some relative conclusions of attribute reduction and definition of attribute significance were proposed based on decision rule. This paper also gives heuristic algorithm, which used golden-section thinking to improve algorithm efficiency. The algorithm efficiency and correctness have been illustrated with an example.

Attribute Reduction; Decision Rule; Attribute Significance; Golden-section

O236

A

1009－5160(2011)06－0085－05

*

李相朋（1963-），男，教授，研究方向：信息系統(tǒng)與知識(shí)發(fā)現(xiàn).