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

　　關鍵詞: 粗糙集  屬性歸約  決策規則  數據挖掘

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

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

1 粗糙集的理論基礎

　　(1)信息系統

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

　　(2)分辨矩陣

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

　　M(C)=(mi,j)_n×n代表了區分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)不可分辨關系

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

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

　　(5)下近似集

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

　　(6)屬性的依賴度

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

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

　　(7)屬性的重要性

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

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

2  算法的基本步驟

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

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

　　算法:計算最佳歸約集

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

　　輸出:一個最佳歸約集。

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

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

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

3 算法的應用實例

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

4 結束語

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

參考文獻

1  劉同明.數據挖掘技術及其應用.北京:國防工業出版社,2001

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

3  代建華.一種基于粗糙集的決策系統屬性約簡算法.小型微型計算機系統,2003;24(3)

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