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

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

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

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

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

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

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

　　(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的完整信息,它是對稱矩陣,所以只需計算m_ij(1≤j≤i≤n)。

　　(3)核  心

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

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

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

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

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

　　(5)下近似集

　　對任何一個對象子集XU和屬性子集PQ,P的下近似集為:

　　(6)屬性的依賴度

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

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

　　(7)屬性的重要性

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

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

2  算法的基本步驟

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

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

　　算法:計算最佳歸約集

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

　　輸出:一個最佳歸約集。

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

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

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

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

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

4 結(jié)束語

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

參考文獻

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

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

3  代建華.一種基于粗糙集的決策系統(tǒng)屬性約簡算法.小型微型計算機系統(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