基于粗集的最小規則集提取算法研究

鮑松堂

(五邑大學 信息學院，廣東 江門 529020)

粗集理論是由波蘭華沙理工大學PAWLAK Z教授[1-2]于1982年提出的，主要研究不完整數據、不精確知識的表達、學習、歸納等方法。從新的視角對知識進行了定義，將知識看作是關于論域的劃分，并引入代數中的等價關系來討論知識，為智能信息處理提供了有效的處理技術。目前已經在人工智能、機器學習與知識發現、模型識別、分類、故障診斷等方面得到了較成功的應用。

屬性約簡和規則提取是粗集研究的重要內容。基于粗集方法的規則抽取過程是規則簡化的過程，以這樣的方法決策可使用條件屬性的最小集合來確定。由于冗余屬性往往會降低數據挖掘結果的精度和解釋能力，屬性約簡是為了去除信息表中的冗余條件屬性，并為得到一個較好的規則集做準備。由于目前算法所生成的規則過多(包含許多無用規則)，不利于決策。參考文獻[4]介紹了一種基于粗集的最小規則集提取算法，但其無法導出包含所有實例的有效性規則。參考文獻[5]是一種改進的規則集提取算法，然而算法過程繁瑣，在添加原子時太過單一。所以本文借用參考文獻[3]中支持子集的選取方法選出規則，并且在此基礎上提出了新的最小規則集提取算法。

1 準備知識

設U為非空的論域，R是U上的等價關系。參考文獻[6]中將R稱為不可區分關系，因而在U上產生一個分 類 U/R={Y1，Y2，… ，Ym}，Y1，Y2， … ，Ym是 通 過 等 價 關系R產生的等價關系類，也是關系R上的元素集。

對于任何X?U，通過關系R的元素集和上、下近似來描述X。

對于決策表 S=(U，C，D，f，V)，A=C∪D， 對于每個u∈U，定義一個函數r:θ→φ。r稱為決策表S中的決策規則，θ和φ分別為決策規則θ→φ的因和果。定義原子條件集 M，表示為 M={(a，v)|?a∈C，?v∈Va}。用 C 來表示單一的原子條件，?C∈M。則θ可以表示為多個C的交集，φ為對應的決策取值。

2個屬性 a，b∈U，需要計算論域 U的下面分類U/ab：2個對象 u，v∈U在同一類當且僅當 a(u)=a(v)且b(u)=b(v)。對于屬性集 X?A，按下面定義論域 U的分類：2個對象 a，b∈U在同一類當且僅當對每個 a∈X有a(u)=a(v)。

令W?U是U的子集，對于條件屬性集X?C，定義W 的下近似為(X)=∪V∈U/X，V?WV；子集(X)稱為 W 關于X的支持子集，sptX(W)=|(X)|/|U|稱為W關于 X的支持度；定義 W 的上近似為(X)=∪V∈U/X，V∩W≠φV。

2 最小規則集提取算法

輸入：輸入決策表 S=(U，C，D，f，V)，U={u1，u2，…，un}，C={a1，a2，… ，am}是 條件屬 性集 ，D 是決 策屬 性集，U/D={Y1，Y2，…，Yk}。

輸出：決策表 S的最小規則集。決策類Y1，Y2，…，Yk對應的決策屬性 d的屬性值分別為 v1，v2，…，vk；R為規則集，C表示原子條件，[C]表示決策表中該原子條件所覆蓋的實例集合。

令 β=[C1]∩[C2]∩…∩[Ci]∩U′?Yj，

選取 1組元素最多的|β|(如果元素最多的不止 1組，則選取最先出現的進行計算)。

3 實例分析

決策表 如 表 1 所 示 ， 條 件 屬 性 集 C={a1，a2，a3，a4，a5}，決策屬性集 D=g0gggggg。

算法在實例中的運行過程如下：

表1 決策表

出的規則為：

如在算法中加入輸出規則覆蓋的實例和支持度，與上述規則對應的實例和支持度則分別為：

{覆蓋實例：1，3，6，8，12。 支持度：31.25%}{覆蓋實例 ：7，14。 支 持 度 ：12.5%}{覆 蓋 實 例 ：15。 支 持 度 ：6.25%}{覆蓋實例：10。支持度：6.25%}{覆蓋實例：2,4,9,13,16。支持度：31.25%}{覆蓋實例：5，11。支持度：12.5%}

本文通過分析粗集中支持子集的計算，結合最小規則集的提取過程，提出一種新的最小規則集提取算法。算法相對參考文獻[4-5]，過程簡單，規則提取完畢后不用再進行約簡，通過實例證明了，在其協調決策系統中最小規則提取運行的有效性。

[1]PAWLAK Z.Rough sets[J].International Jounal of Information and Computer Science，1982(5):341-356.

[2]PAWLAK Z.Rough sets and intelligent data analysis[J].Information Science， 2002，147(1/4):1-12.

[3]張文修.粗糙集理論與方法[M].北京：科學出版社，2000.

[4]STEFANOWSKI J.On rough sets based approaches to induction of decision rules[A].Rough sets in knowledge discovery[C].Heidelbery:Physica Verlag.1998:500-529.

[5]吳順祥.基于粗集理論的一種規則提取方法[J].廈門大學學報，2004(9):64-66.

[6]PAWLAK Z.Rough sets:Theoretical aspects of reasoning about data[M].Boston:Kluwer Academic Publishers，1991.