摘  要: 提出了一種基于粗糙集的決策規(guī)則挖掘算法。該算法主要包括屬性歸約、元組合并、規(guī)則提取和規(guī)則評(píng)估。最后用一個(gè)實(shí)例說明了算法的有效性。

　　關(guān)鍵詞: 粗糙集  屬性歸約  決策規(guī)則  數(shù)據(jù)挖掘

　　粗糙集是一種處理不精確與不完全數(shù)據(jù)的新的數(shù)學(xué)理論。粗糙集理論建立在分類機(jī)制的基礎(chǔ)上,將知識(shí)理解為對(duì)數(shù)據(jù)的劃分,是在特定空間上由等價(jià)關(guān)系構(gòu)成的劃分。近年來,它已被廣泛地應(yīng)用在人工智能、模式識(shí)別和數(shù)據(jù)挖掘等方面。

　　一個(gè)決策信息系統(tǒng)(本文假定決策信息系統(tǒng)是相容的)包含了某一領(lǐng)域中大量實(shí)例(元組)信息,是領(lǐng)域的實(shí)例數(shù)據(jù)庫。它記錄了大量實(shí)例的屬性值和決策情況,是領(lǐng)域知識(shí)的載體。數(shù)據(jù)挖掘的目的就是要通過分析這個(gè)實(shí)例數(shù)據(jù)庫來獲得該領(lǐng)域中事先未知的、潛在有用的和最終可理解的規(guī)律性知識(shí)。決策信息系統(tǒng)中的一個(gè)實(shí)例(元組)就代表一條基本的決策規(guī)則。如果把所有這樣的決策規(guī)則羅列出來,就可以得到一個(gè)決策規(guī)則的集合。但是,這樣的決策規(guī)則的集合是沒有任何用處的。因?yàn)槠渲械臎Q策規(guī)則沒有適應(yīng)性,只是機(jī)械地記錄了一個(gè)實(shí)例的情況,而不能適應(yīng)其他新的情況。為了從決策信息系統(tǒng)中挖掘出適應(yīng)性較大的決策規(guī)則,本文提出了一種基于粗糙集的決策規(guī)則挖掘算法。實(shí)踐證明,運(yùn)用該算法挖掘得到的決策規(guī)則具有較高的適應(yīng)性,能代表一類具有相同規(guī)律特性的實(shí)例,并可以在今后的決策過程中利用這些決策規(guī)則對(duì)未知的觀察實(shí)例進(jìn)行決策判定。

1 粗糙集的理論基礎(chǔ)

　　(1)信息系統(tǒng)

　　一個(gè)信息系統(tǒng)定義為四元組:S={U,Q,V,f}。其中:U為對(duì)象集,即論域;Q=CYD為屬性的集合;V為各屬性的值域;f為U×Q→V的映射,它為U中各對(duì)象的屬性指定惟一值。

　　(2)分辨矩陣

　　信息系統(tǒng)S中關(guān)于屬性集C的分辨矩陣M(C)=(m_i,j)_n×n定義為:

　　M(C)=(mi,j)_n×n代表了區(qū)分x_i,x_j的完整信息,它是對(duì)稱矩陣,所以只需計(jì)算m_ij(1≤j≤i≤n)。

　　(3)核  心

　　相對(duì)于屬性集D,屬于屬性集C的所有歸約的交集屬性的集合為屬性集C的核心,記為CORE(C,D)。用核心作為計(jì)算歸約集的起點(diǎn),可以簡(jiǎn)化屬性歸約集的計(jì)算。為簡(jiǎn)化計(jì)算核心,一般通過分辨矩陣進(jìn)行。具體計(jì)算的公式如下:

CORE={c∈C:m_ij={c},對(duì)于所有1≤j≤i≤n

　　(4)不可分辨關(guān)系

　　對(duì)于任何一個(gè)屬性集合PQ,不可分辨關(guān)系用IND表示,其定義如下:

　　如果(x,y)∈IND(P),則x、y稱為相對(duì)于P是不可分辨的。不可分辨關(guān)系實(shí)際上就是U上的等價(jià)關(guān)系。因此,針對(duì)屬性集P上的不可分辨關(guān)系,U可劃分為幾個(gè)等價(jià)類,用U/IND(P)表示。

　　(5)下近似集

　　對(duì)任何一個(gè)對(duì)象子集XU和屬性子集PQ,P的下近似集為:

　　(6)屬性的依賴度

　　在屬性歸約中,利用二個(gè)屬性集合P、RQ之間的相互依賴程度,可以定義一個(gè)屬性α的重要性。屬性集P對(duì)R的依賴程度用表示。其定義如下:

　　其中:card()表示集合的基數(shù),POS_R(P)是屬性集R在U/IND(P)中的正區(qū)域。

　　(7)屬性的重要性

　　不同屬性對(duì)于決定條件屬性和決策屬性之間的依賴關(guān)系起著不同的作用。屬性α加入屬性集R,對(duì)于分類U/IND(P)的重要程度定義為:

　　屬性α的重要性是相對(duì)而言的,它依賴于屬性P和R。因此,在不同的背景下,屬性的重要性可能不同。如果決策屬性定義為D,則SGF(α,R,P)反映的是將屬性α加入屬性集R中以后,R與D之間的依賴程度的改變,從而體現(xiàn)出屬性α的重要性。

2  算法的基本步驟

　　運(yùn)用該算法來挖掘隱含在決策信息系統(tǒng)中的決策規(guī)則的基本步驟包括:屬性歸約、元組合并、規(guī)則提取和規(guī)則評(píng)估。

　　(1)屬性歸約。屬性歸約是粗糙集理論中的一個(gè)重要的研究課題。通常,決策信息系統(tǒng)中的屬性并非同等重要,且存在冗余,這不利于做出正確而簡(jiǎn)潔的決策。屬性歸約是在保持決策信息系統(tǒng)的分類和決策能力不變的前提下,刪除不相關(guān)或不重要的屬性。因此,在進(jìn)行屬性歸約時(shí),人們總希望找到屬性的最小約簡(jiǎn),但這是一個(gè)NP難度的問題。幸運(yùn)的是,在大多數(shù)情況下,無需找出屬性的最小約簡(jiǎn),因?yàn)橛脩糁粚?duì)與處理任務(wù)相關(guān)的最佳子集感興趣。根據(jù)屬性之間的依賴關(guān)系、重要性等,可以比較容易且有效地找出一個(gè)最佳歸約集。下面給出了計(jì)算最佳歸約集的算法。該算法以核心作為計(jì)算的起點(diǎn),每次選擇重要性最大的屬性加入屬性集REDU,在步驟④的前向選擇結(jié)束后,屬性集REDU已包含了一些起重要作用的屬性,且沒有改變?cè)紝傩约c決策屬性之間的依賴程度。最后的反饋過程是從屬性集REDU中逐個(gè)去掉屬性。如果去掉該屬性會(huì)造成依賴度變化,則恢復(fù)該屬性,否則刪除該屬性。最后剩下的屬性集就是最佳歸約集。刪除決策信息系統(tǒng)中不屬于最佳歸約集的屬性就可得到最佳屬性歸約的決策信息系統(tǒng)。

　　算法:計(jì)算最佳歸約集

　　輸入:一個(gè)具有條件屬性集C和決策屬性集D的相容決策信息系統(tǒng)S。

　　輸出:一個(gè)最佳歸約集。

　　(2)元組合并。合并最佳屬性歸約的決策信息系統(tǒng)中的元組分二個(gè)步驟。首先,如果多個(gè)(二個(gè)或二個(gè)以上)元組的各個(gè)條件屬性和決策屬性都一一對(duì)應(yīng)相同,則將這多個(gè)元組合并成一個(gè)元組;其次,如果多個(gè)元組的決策屬性相同,條件屬性只有一個(gè)不同,并且這多個(gè)元組在該條件屬性上的取值覆蓋了它所有可能的值,則將這多個(gè)元組合并成一個(gè)元組,并且將該條件屬性從該元組中刪除。最終便可得到最簡(jiǎn)決策信息系統(tǒng)。

　　(3)規(guī)則提取。盡管由上述步驟得到的最簡(jiǎn)決策信息系統(tǒng)已經(jīng)可以為決策者提供正確而簡(jiǎn)潔的決策,但用這種方法表示決策知識(shí)的可讀性很差,不易被人理解,尤其是當(dāng)生成的最簡(jiǎn)決策信息系統(tǒng)仍然較大時(shí)。因此,有必要提取出隱含在其中的決策規(guī)則,并以IF-THEN的形式表示出來。其具體方法是:對(duì)于簡(jiǎn)化的決策信息系統(tǒng)中的每一個(gè)元組,將它的每一個(gè)條件屬性的屬性-值對(duì)形成規(guī)則前件(IF部分)的一個(gè)合取項(xiàng);將它的每一個(gè)決策屬性的屬性-值對(duì)形成規(guī)則后件(THEN部分)的一個(gè)合取項(xiàng)。最終便可得到用IF-THEN形式表示的決策規(guī)則集。

　　(4)規(guī)則評(píng)估。對(duì)于特定的決策者來說,他不一定對(duì)上述生成的所有決策規(guī)則都感興趣。因此,決策者需要根據(jù)自己的目標(biāo)進(jìn)一步限制挖掘過程產(chǎn)生的不感興趣的決策規(guī)則的數(shù)量。這可以通過設(shè)定規(guī)則興趣度度量方法來實(shí)現(xiàn)。規(guī)則興趣度度量的方法很多,其中最常見的方法有支持度度量和置信度度量。只有那些支持度和置信度都大于或等于決策者事先設(shè)定的最小支持度閾值和最小置信度閾值的決策規(guī)則才被認(rèn)為是有趣的。對(duì)于形如“A?圯B”的決策規(guī)則,其支持度和置信度的定義分別為:

3 算法的應(yīng)用實(shí)例

　　表1(見參考文獻(xiàn)[3])給出了一個(gè)關(guān)于汽車信息的決策信息系統(tǒng)(系統(tǒng)是相容的)。其條件屬性C={類型、汽缸、渦輪式、燃料、排氣量、壓縮率、功率、換檔、重量},決策屬性D={里程}。挖掘的目標(biāo)是提取出隱含在該相容決策信息系統(tǒng)中的被決策者感興趣的實(shí)際決定汽車?yán)锍痰臎Q策規(guī)則。運(yùn)用算法的第(1)、(2)步可以得到如表1所示的最簡(jiǎn)決策信息系統(tǒng);運(yùn)用算法的第(3)、(4)步可以得到如表2所示的決策規(guī)則集。假如某一決策者設(shè)定最小支持度閾值和最小置信度閾值分別為15%和90%,則表2中的所有規(guī)則中就只有規(guī)則1、5、6是有趣的。

4 結(jié)束語

　　隨著KDD和DM的興起,粗糙集方法正贏得越來越多的研究者的青睞,并在各個(gè)領(lǐng)域獲得了廣泛的應(yīng)用。究其原因有:①KDD和DM的對(duì)象多為關(guān)系數(shù)據(jù)庫,其中就有許多可視為粗糙集理論中的決策信息系統(tǒng),這給粗糙集方法的應(yīng)用帶來了極大的方便。②現(xiàn)實(shí)世界中的規(guī)則有確定性的,也有不確定性的。從數(shù)據(jù)庫中發(fā)現(xiàn)的不確定性的規(guī)則為粗糙集方法提供了用武之地。③基于粗糙集的挖掘算法有利于并行執(zhí)行,可以極大地提高挖掘效率。④粗糙集方法能夠自動(dòng)地選擇合適的屬性集,去掉多余的屬性,提高挖掘的效率。⑤與其他方法相比,用粗糙集方法得到的決策規(guī)則更易驗(yàn)證和檢測(cè)。

參考文獻(xiàn)

1  劉同明.數(shù)據(jù)挖掘技術(shù)及其應(yīng)用.北京:國防工業(yè)出版社,2001

2  王國胤.Rough集理論與知識(shí)獲取.西安:西安交通大學(xué)出版社,2001

3  代建華.一種基于粗糙集的決策系統(tǒng)屬性約簡(jiǎn)算法.小型微型計(jì)算機(jī)系統(tǒng),2003;24(3)

4  Kryszkiewicz M,Rybinski H.Reducing Information Systems with Uncertain Attributes.In:9th International Symposium on Foundations of Intelligent Systems,1996