基于決策規則的屬性約簡算法

廖 倩，李相朋

（武漢紡織大學 數學與計算機學院，湖北 武漢 430073）

基于決策規則的屬性約簡算法

廖 倩，李相朋*

（武漢紡織大學 數學與計算機學院，湖北 武漢 430073）

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

屬性約簡；決策規則；重要性；黃金分割

1 引言

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

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

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

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

3 基于決策規則的屬性約簡和屬性重要性

3.1 屬性約簡

3.2 屬性重要性

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

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

4 屬性約簡算法

4.1 黃金分割法[14]

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

4.2 改進的屬性約簡算法

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

5 實例分析

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

表1 決策表

6 結束語

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

[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].計算機應用,2008,28(8):2000-2002.

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

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

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

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

[13] 吳今培，孫德山. 現代數據分析[M]. 北京:機械工業出版社,2006.

[14] 宋巨龍，錢富才. 基于黃金分割法的全局最優方法[J]. 計算機工程與應用，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-），男，教授，研究方向：信息系統與知識發現.