一種基于分布約簡的規(guī)則獲取方法

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

關(guān)鍵詞：粗糙集； 分布約簡； 分布核； 規(guī)則獲取

中圖分類號：TP301.6文獻(xiàn)標(biāo)志碼：A

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

粗糙集理論是一種能有效處理不精確、不確定和含糊信息的數(shù)學(xué)理論。經(jīng)過二十余年的發(fā)展，它已在數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、模式識別與智能信息處理等領(lǐng)域得到了廣泛應(yīng)用。

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

1 粗糙集基本概念

2 基于分布約簡的規(guī)則獲取方法

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

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

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

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

下面證明定理2。

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

3 結(jié)束語

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

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