一種基于分布約簡的規則獲取方法

摘 要：基于決策表分布約簡定義規則的分布核與分布約簡概念，提出一種基于分布約簡的規則獲取方法。首先確定條件類的分布核，進而采用啟發式算法計算其分布約簡，挖掘出最簡產生式規則。該方法能適應決策表的不一致情形，且運用此方法所提取的規則集能夠保持與原信息系統一致。

關鍵詞：粗糙集； 分布約簡； 分布核； 規則獲取

中圖分類號：TP301.6文獻標志碼：A

文章編號：1001-3695(2007)06-0042-03

粗糙集理論是一種能有效處理不精確、不確定和含糊信息的數學理論。經過二十余年的發展，它已在數據挖掘、機器學習、模式識別與智能信息處理等領域得到了廣泛應用。

規則獲取一直是粗糙集理論研究的重要課題。目前已有較多學者就規則獲取方法進行了一定的研究。文獻[1]提出一種最簡規則挖掘方法，可挖掘出滿足給定精確度的最簡產生式規則。該方法簡潔有效，但是它通過人為給定一個分類正確度修改不一致對象決策值，最后所得規則可能與原信息系統不一致。文獻[2]提出一種決策表約簡的增量式學習方法。利用該方法得到分類規則知識庫，但并沒有考慮決策表不相容的情形。文獻[3]在等價矩陣概念基礎上提出進行數據清洗、提取決策規則的矩陣算法。但該方法通過數據清洗刪除不一致對象會導致原信息系統信息的損失，最后所提取規則與原信息系統可能不一致。文獻[4]討論了最大分布約簡、分配約簡、分布約簡和近似約簡之間的關系，并給出了相應的可辨識矩陣、不協調目標信息系統的知識約簡新方法，但并沒有進一步給出獲取規則的具體方法。

1 粗糙集基本概念

2 基于分布約簡的規則獲取方法

決策表核屬性的確定對屬性約簡具有重要意義，一直受到粗糙集理論界學者的關注。Hu等人［5］根據Skowron提出的可辨識矩陣得出一個確定決策表信息系統核屬性集的方法。葉東毅教授等人［6］對Hu的結論提出質疑，并通過改進可辨識矩陣提出了一種計算核屬性的方法。王國胤教授［7］對上述兩種方法進行了分析，分別指出其局限性，并提出一種決策表信息熵定義下的核屬性計算方法。他指出，對于相容決策表可采用Hu的方法計算核屬性；對于不相容決策表可采用葉的方法計算核屬性；而無論決策表是否相容均可使用信息熵定義下的核屬性計算方法。

本章將基于文獻[4]提出的分布約簡概念定義決策表的分布核屬性，并與文獻[7]中信息熵定義下的核屬性進行比較研究。然后定義條件類的分布核與分布約簡，簡述基于分布約簡生成最簡規則的基本原理。

定理1表明分布核概念的意義主要體現在兩個方面：①分布核可解釋為決策表中不能消去的屬性集，因為缺少核屬性將導致部分對象關于某些決策類的隸屬程度發生改變；②分布核可以作為分布約簡的計算基礎，因為分布核包含在所有分布約簡之中，并且計算可以直接進行。

引理1表明，①如果將決策表條件屬性的分類進行合并，將導致條件熵的單調上升；只有在發生合并的兩個分類對于決策類的隸屬度（概率）相等的情況下，才不會導致條件熵的變化。②劃分U/IND（C-{a}）是可以通過將劃分U/IND（C）中的部分等價塊合并得到的。如果H（D|C-{a})=H（D|C)，則所有被合并在一起的等價塊對于決策類的隸屬度均相等。因此在合并后，條件屬性分類中的等價塊對于各個決策屬性分類的隸屬度不會發生變化。

下面證明定理2。

求條件類的最小分布約簡是一個NP完全問題。算法1利用屬性重要性作為啟發函數求近似最小約簡。其基本過程是，首先得到條件類的分布核作為求取其分布約簡的基礎，然后按照屬性的重要程度從大到小逐個加入屬性，直到得到其分布約簡為止。無論決策表是否一致，此規則提取方法均適用，且所提取的規則集保持與原信息系統一致。

3 結束語

本文提出了一種基于分布約簡的規則獲取方法，它能適應決策表的不一致性。該方法將傳統的屬性約簡和值約簡合而為一，并且同樣適用于一致決策表。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。