廖 倩，李相朋

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

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

廖 倩，李相朋*

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

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

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

1 引言

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

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

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

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

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

3.1 屬性約簡

3.2 屬性重要性

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

用式（1）計算屬性重要度后，對其進行排序，如果存在多個屬性的重要度相同，則這些屬性之間可任排。以此排序為啟發(fā)式信息進行屬性約簡。

4 屬性約簡算法

4.1 黃金分割法[14]

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

4.2 改進的屬性約簡算法

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

5 實例分析

下面通過一個例子來說明改進的約簡算法，表1為某決策表。

表1 決策表

6 結(jié)束語

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

[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集的屬性約簡的改進算法[J].計算機應(yīng)用,2008,28(8):2000-2002.

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

[6] 王玨，王任，苗奪謙，等. 基于Rough Set理論的“數(shù)據(jù)濃縮”[J].計算機學(xué)報, 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] 苗奪謙，胡桂榮. 知識約簡的一種啟發(fā)式算法[J]. 計算研究與發(fā)展, 1999 , 36 (6) : 681-684.

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

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

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

[14] 宋巨龍，錢富才. 基于黃金分割法的全局最優(yōu)方法[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)與知識發(fā)現(xiàn).