基于粗集的最小規(guī)則集提取算法研究

鮑松堂

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

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

屬性約簡(jiǎn)和規(guī)則提取是粗集研究的重要內(nèi)容?；诖旨椒ǖ囊?guī)則抽取過(guò)程是規(guī)則簡(jiǎn)化的過(guò)程，以這樣的方法決策可使用條件屬性的最小集合來(lái)確定。由于冗余屬性往往會(huì)降低數(shù)據(jù)挖掘結(jié)果的精度和解釋能力，屬性約簡(jiǎn)是為了去除信息表中的冗余條件屬性，并為得到一個(gè)較好的規(guī)則集做準(zhǔn)備。由于目前算法所生成的規(guī)則過(guò)多(包含許多無(wú)用規(guī)則)，不利于決策。參考文獻(xiàn)[4]介紹了一種基于粗集的最小規(guī)則集提取算法，但其無(wú)法導(dǎo)出包含所有實(shí)例的有效性規(guī)則。參考文獻(xiàn)[5]是一種改進(jìn)的規(guī)則集提取算法，然而算法過(guò)程繁瑣，在添加原子時(shí)太過(guò)單一。所以本文借用參考文獻(xiàn)[3]中支持子集的選取方法選出規(guī)則，并且在此基礎(chǔ)上提出了新的最小規(guī)則集提取算法。

1 準(zhǔn)備知識(shí)

設(shè)U為非空的論域，R是U上的等價(jià)關(guān)系。參考文獻(xiàn)[6]中將R稱為不可區(qū)分關(guān)系，因而在U上產(chǎn)生一個(gè)分 類 U/R={Y1，Y2，… ，Ym}，Y1，Y2， … ，Ym是 通 過(guò) 等 價(jià) 關(guān)系R產(chǎn)生的等價(jià)關(guān)系類，也是關(guān)系R上的元素集。

對(duì)于任何X?U，通過(guò)關(guān)系R的元素集和上、下近似來(lái)描述X。

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

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

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

2 最小規(guī)則集提取算法

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

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

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

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

3 實(shí)例分析

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

算法在實(shí)例中的運(yùn)行過(guò)程如下：

表1 決策表

出的規(guī)則為：

如在算法中加入輸出規(guī)則覆蓋的實(shí)例和支持度，與上述規(guī)則對(duì)應(yīng)的實(shí)例和支持度則分別為：

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

本文通過(guò)分析粗集中支持子集的計(jì)算，結(jié)合最小規(guī)則集的提取過(guò)程，提出一種新的最小規(guī)則集提取算法。算法相對(duì)參考文獻(xiàn)[4-5]，過(guò)程簡(jiǎn)單，規(guī)則提取完畢后不用再進(jìn)行約簡(jiǎn)，通過(guò)實(shí)例證明了，在其協(xié)調(diào)決策系統(tǒng)中最小規(guī)則提取運(yùn)行的有效性。

[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].北京：科學(xué)出版社，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]吳順祥.基于粗集理論的一種規(guī)則提取方法[J].廈門大學(xué)學(xué)報(bào)，2004(9):64-66.

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