不相容決策表求核方法

陳鳳娟

（遼寧對外經濟貿易學院 信息技術系，遼寧 大連116052）

0 引 言

屬性約簡 （知識約簡）是粗糙集理論中的一個主要研究方向。核屬性是決策表中最重要的特征集合，它包含在所有屬性約簡之中，可以作為屬性約簡的基礎，因此很多屬性約簡算法都從核屬性出發，在核屬性之上通過一定的方法選取屬性增加到核中，從而得到約簡集合［1］。

HU XIAOHUA等學者在文獻 ［2］中給出的利用改進差別矩陣求核的方法是一個很有效的方法，但是有學者已經證明該方法不適用于不相容決策表求核［3－4］。目前，在不相容決策表的求核問題上，主要的方法有使用代數定義［11，13－14］、HU 差別矩 陣［9－10，12，15］、 使 用 信 息 熵 定 義［5，7－8］和改進的 HU差別矩陣［3－4，6］等方法，但這些方法并沒有完全解決不相容決策表的求核問題。本文深入分析不相容決策表的性質，把不相容決策表中的核屬性分為相容核與不相容核兩部分，以文獻 ［3］和文獻 ［5］中使用的3個不相容決策表為例，分析這3個不相容決策表的相容核與不相容核，比較現有的求核方法，發現這些方法不能夠得到正確的相容核與不相容核，通過改進HU差別矩陣得到兩個新的差別矩陣，利用這兩個新的矩陣計算出不相容決策表的相容核與不相容核。

1 基本概念

代數觀中的正域、屬性必要性及核屬性的相關概念如下［1］：

定義1 設U為一個論域，P，Q為定義在U上的兩個等價關系族，Q的P正域記作POSP（Q），定義為POSP。

定義2 設U為一個論域，P，Q為定義在U上的兩個等價關系族，對于P中的關系r，若有POSIND （P）（IND （Q））＝POSIND （P－ ｛r｝）（IND （Q）成立，則稱r∈P為P中Q不必要的；否則稱r為P中Q必要的。

定義3 設U為一個論域，P，Q為定義在U上的兩個等價關系族，P中所有Q必要的原始關系族，稱為P的Q核，記為COREQ （P）。

核屬性是必要屬性的集合。

從上面的定義可知，當去掉某個屬性會導致正域發生變化時，則該屬性是核屬性。

在不相容決策表中，論域中的元素可以通過計算正域的方法，分成不包含沖突信息的相容元素和包含沖突信息的不相容元素兩部分。使用代數定義求核的方法通過判斷正域是否變化來得到核屬性，由于不相容元素的劃分塊之間的合并對正域完全沒有影響，因此，這種方法能忽略掉不相容決策表中的不相容元素之間的變化規律，把去掉后會導致正域發生變化的屬性稱為核屬性，本文稱這種核屬性為相容核屬性。

有兩種情況會導致一個不相容決策表的正域發生變化——一個相容元素的劃分塊和一個不相容元素的劃分塊發生合并；一個相容元素的劃分塊和另一個相容元素的劃分塊發生合并。多于兩個的劃分塊的合并都可以分解成上面兩種情況。由于這兩種情況會影響正域，因此定義不相容決策表的相容核如下。

定義4 在不相容決策表中，若去掉某一個條件屬性，會使包含相容元素的劃分塊與其它劃分塊發生合并，導致正域發生變化，則該屬性屬于相容部分的核屬性，簡稱相容核。

從決策表的正域的變化中不能看到不相容信息是否發生了變化，由于負域與正域完全對應，因此也不能用負域來作為衡量不相容部分是否變化的基準。

由于正域發生變化的本質就是包含相容元素的劃分塊與別的劃分塊發生了合并，因此可以用不相容信息的劃分塊之間的合并作為衡量不相容部分是否發生變化的標準。也就是說如果去掉某個屬性會導致不相容部分信息的劃分塊發生合并，那么這個屬性對不相容部分就是必要的屬性，就是不相容部分的核屬性。為了區別于相容部分的核，稱這部分核屬性為不相容核。這種屬性的存在能保證不相容決策表中不相容部分的劃分塊保持不變。根據這類屬性與決策表的不相容部分信息的變化之間存在的內在聯系，給出如下的不相容決策表的不相容核的定義。

定義5 在不相容決策表中，若去掉某一個條件屬性，會使包含不相容元素的劃分塊之間發生合并，則該屬性屬于不相容部分的核屬性，簡稱不相容核。

對于一個不相容決策表，完整的核屬性包含兩部分，即相容核與不相容核。相容核部分能考察相容部分的變化，而不相容核能考察不相容部分的變化。一個核屬性只能是相容核與不相容核中的一種，不可能二者兼為。

2 現有求核方法存在的問題

在文獻 ［3］中，葉東毅教授分析了HU差別矩陣運用于不相容決策表中求核時產生的錯誤，并改進HU差別矩陣，得到與代數定義相同的結果。葉的方法通過改進HU矩陣，把不相容信息對HU矩陣的影響去掉，只計算與相容部分信息相關的屬性。類似的改進矩陣的方法還有很多，如楊明的改進矩陣等［4，6］，這些方法雖然得到不同形式的差別矩陣，但是它們的思想是完全一致的，都是把不相容決策表中影響計算結果的沖突信息忽略掉。這類改進HU矩陣的方法計算結果與代數定義方法完全相容，可以與代數定義方法歸為一類。

在文獻 ［5］中，王國胤教授使用條件信息熵的方法計算不相容決策表的核，由于條件信息熵是由不相容信息產生的，因此計算條件信息熵的方法能考察到不相容部分的變化，但是由于條件信息熵是由比率得到的，因此當某些不相容部分的劃分塊發生了合并，而其比率不發生變化的情況，就會被條件信息熵方法忽略掉，導致該方法不能判斷所有的不相容劃分塊發生合并的情況。

下面針對文獻 ［3］和文獻 ［5］中用到的3個不相容決策表，分別分析這些決策表中相容部分劃分塊和不相容部分劃分塊的變化，從而說明現有的求核方法存在的問題，如表1～表3所示。

表1 不相容決策表1

決策表1的劃分如下：

U/IND （｛C1，C2，C3｝）＝ ｛｛x1，x2｝， ｛x3，x4｝，｛x5｝｝；

U/IND （D）＝ ｛｛x1，x3，x5｝，｛x2，x4｝｝；

正域POSC（D）＝ ｛x5｝。

去掉屬性C1，有 U/IND （｛C2，C3｝）＝ ｛｛x1，x2，x3，x4｝，｛x5｝｝；

去掉屬性C2，有 U/IND （｛C1，C3｝）＝ ｛｛x1，x2，x5｝，｛x3，x4｝｝；

去掉屬性C3，有 U/IND （｛C1，C2｝）＝ ｛｛x1，x2｝，｛x3，x4｝，｛x5｝｝；

從上面的計算可知：

（1）決策表1中相容部分為 ｛x5｝，相容部分的劃分為｛｛x5｝｝，存在不相容信息的部分為 ｛x1，x2，x3，x4｝，不相容部分的劃分為 ｛｛x1，x2｝，｛x3，x4｝｝；

（2）去掉屬性C1，相容部分的劃分沒有發生變化，而不相容部分的劃分發生了變化，即不相容部分的劃分塊｛x1，x2｝和 ｛x3，x4｝合并成了一個劃分塊 ｛x1，x2，x3，x4｝，因此，C1屬于不相容核。

（3）去掉屬性C2，使相容部分的劃分塊 ｛x5｝和不相容部分的劃分塊 ｛x1，x2｝合并成了一個劃分塊 ｛x1，x2，x5｝，導致正域POSC（D）發生變化，因此，C2屬于相容核。

（4）去掉屬性C3，對相容部分的劃分沒有影響，對不相容部分的劃分也沒有影響，因此，C3不屬于任何核。

由以上分析可得，決策表1的核屬性集為 ｛C1，C2｝，其中，相容核為 ｛C2｝，不相容核為 ｛C1｝。代數方法求得的核為相容核 ｛C2｝；改進的差別矩陣 （如文獻 ［3－4］所示）中求得的也是相容核 ｛C2｝；信息熵的方法求得的核也是相容核 ｛C2｝；HU矩陣的方法求得的核是 ｛C1，C2｝，是所有的核。

表2 不相容決策表2

決策表2的劃分如下：

U/IND （｛C1，C2，C3｝）＝ ｛｛x1｝，｛x2，x3｝，｛x4｝｝；

U/IND （D）＝ ｛｛x1，x3｝，｛x2，x4｝｝；

正域POSC（D）＝ ｛x1，x4｝。

去掉屬性C1，有U/IND （｛C2，C3｝）＝ ｛｛x1，x2，x3｝，｛x4｝｝；

去掉屬性C2，有 U/IND （｛C1，C3｝）＝ ｛｛x1，x4｝，｛x2，x3｝｝；

去掉屬性C3，有 U/IND （｛C1，C2｝）＝ ｛｛x1｝，｛x2，x3｝，｛x4｝｝。

從上面的計算可知：

（1）決策表2中相容部分為 ｛x1，x4｝，相容部分的劃分為 ｛｛x1｝，｛x4｝｝，存在不相容信息的部分為 ｛x2，x3｝，不相容部分的劃分為 ｛｛x2，x3｝｝；

（2）去掉屬性C1，使相容部分的劃分塊 ｛x1｝和不相容部分的劃分塊 ｛x2，x3｝合并成了一個劃分塊 ｛x1，x2，x3｝，導致正域POSC（D）發生變化，因此，C1屬于相容核。

（3）去掉屬性C2，使相容部分的劃分塊 ｛x1｝和 ｛x4｝合并成了一個劃分塊 ｛x1，x4｝，導致正域POSC（D）發生變化，因此，C2屬于相容核。

（4）去掉屬性C3，相容部分的劃分和不相容部分的劃分都沒有發生變化，因此，C3不屬于任何核。

由以上分析可得，決策表2的核屬性集為 ｛C1，C2｝，其中，相容核為 ｛C1，C2｝，不相容核為Φ。代數方法、改進的差別矩陣方法、信息熵的方法和HU矩陣的方法求得的核都是 ｛C1，C2｝。

表3 不相容決策表3

決策表3的劃分：

U/IND （｛C1，C2，C3｝）＝ ｛｛x1，x2，x3｝， ｛x4，x5｝，｛x6｝｝；

U/IND （D）＝ ｛｛x1，x4，x6｝，｛x2，x5｝，｛x3｝｝；

正域POSC（D）＝ ｛x6｝。

去掉屬性C1，有 U/IND （｛C2，C3｝）＝ ｛｛x1，x2，x3，x4，x5｝，｛x6｝｝；

去掉屬性C2，有 U/IND （｛C1，C3｝）＝ ｛｛x1，x2，x3，x6｝，｛x4，x5｝｝；

去掉屬性C3，有 U/IND （｛C1，C2｝）＝ ｛｛x1，x2，x3｝，｛x4，x5｝，｛x6｝｝。

從上面的計算可知：

（1）決策表3中相容部分為 ｛x6｝，相容部分的劃分為｛｛x6｝｝，存在不相容信息的部分為 ｛x1，x2，x3，x4，x5｝，不相容部分的劃分為 ｛｛x1，x2，x3｝，｛x4，x5｝｝；

（2）去掉屬性C1，使不相容部分的劃分塊 ｛x1，x2，x3｝和 ｛x4，x5｝合并成了一個劃分塊 ｛x1，x2，x3，x4，x5｝，因此，C1屬于不相容核。

（3）去掉屬性C2，使相容部分的劃分塊 ｛x6｝和不相容部分的劃分塊 ｛x1，x2，x3｝合并成了一個劃分塊 ｛x1，x2，x3，x6｝，導致正域POSC（D）發生變化，因此，C2屬于相容核。

（4）去掉屬性C3，相容部分的劃分和不相容部分的劃分都沒有發生變化，因此，C3不屬于任何核。

由以上分析可得，決策表3的核屬性集為 ｛C1，C2｝，其中，相容核為 ｛C2｝，不相容核為 ｛C1｝。代數方法和改進的差別矩陣的方法求得的核是相容核 ｛C2｝，信息熵的方法和HU矩陣的方法求得的核是所有核 ｛C1，C2｝。

對于上面的表1、表2和表3，代數方法和改進的差別矩陣方法完全等價，它們只能求得不相容決策表的相容核；信息熵方法有時得到的是相容核，有時得到的是全部核屬性；HU矩陣方法能計算出不相容決策表的全部核屬性。

HU矩陣方法雖然得到了全部的核屬性集合，但是該矩陣把這兩種核屬性混合在一起，使人很難分辨出哪個是相容核，哪個是不相容核，這種現象使得許多學者認為HU矩陣不適用于不相容決策表。

下面通過對HU差別矩陣進行修改，使HU矩陣中的相容核與不相容核分開，從而得到不相容決策表的所有的核屬性集合。

3 改進的差別矩陣

HU差別矩陣定義如下：

定義6 對于信息系統S＝ （U，A，V，f），A＝C∪D，C∩D＝Φ，C和D分別是條件屬性和決策屬性。S的差別矩陣M是一個n＊n對稱矩陣，a（x）是記錄x在屬性a上的值，mij表示差別矩陣中第i行，第j列的元素，因此差別矩陣定義為

文獻中給出如下結論：當且僅當某個mij為單個屬性時，該屬性屬于核CORE（C）。

根據前面給出的相容核與不相容核的計算過程及方法，修改HU矩陣為下面兩個新的矩陣，這兩個矩陣分別計算不相容決策表的相容核與不相容核。

定義7 對于信息系統S＝ （U，A，V，f），A＝C∪D，C∩D＝Φ，C和D分別是條件屬性和決策屬性。S的差別矩陣MS1和MS2都是n＊n的對稱矩陣，a（x）是記錄x在屬性a上的值，mij和m′ij分別表示差別矩陣MS1和MS2中第i行，第j列的元素，這兩個差別矩陣分別定義為

其中U1＝POSC（D）。當mij為單個屬性時，該屬性是相容核屬性。這個結果與代數觀的核屬性定義方法計算的核屬性等價

其中U2＝U－POSC（D）。當m′ij為單個屬性時，該屬性是不相容核屬性，刪除該屬性將導致大于等于兩個不相容部分塊發生合并。它的存在保證了不相容部分的分類與原始決策表的不相容部分的分類一致。

下面使用改進的兩個差別矩陣，計算以上3個不相容決策表的相容核與不相容核，由矩陣的對稱性，可以只計算這些矩陣的下三角矩陣。

決策表1的新的差別矩陣MS1和MS2如表4和表5所示。

表4 決策表1的差別矩陣MS1

由于C2是矩陣MS1中的單個屬性，因此，C2是相容核。

表5 決策表1的差別矩陣MS2

由于C1是矩陣MS2中的單個屬性，因此，C1是不相容核。

決策表2的新的差別矩陣MS1和MS2如表6和表7所示。

表6 決策表2的差別矩陣MS1

由于C1，C2都是矩陣MS1中的單個屬性，因此，C1，C2都是相容核。

表7 決策表2的差別矩陣MS2

由于矩陣MS2中的沒有單個屬性，因此，該決策表的不相容核為Φ。

決策表3的新的差別矩陣MS1和MS2如表8和表9所示。

表8 決策表3的差別矩陣MS1

由于C2是矩陣 MS1中的單個屬性，因此，C2是相容核。

表9 決策表3的差別矩陣MS2

由于C1是矩陣MS2中的單個屬性，因此，C1是不相容核。

改進的差別矩陣MS1處理所有相容元素參與的比較，所以該矩陣中的單個元素是相容部分的核屬性，即相容核；而改進的差別矩陣MS2處理不相容元素之間的比較，所以該矩陣中的單個元素是不相容部分的核屬性，即不相容核。

4 結束語

對于不相容決策表的核屬性的計算問題，一直有很多種方法。代數定義的方法能忽略掉不相容決策表中的不相容部分的信息，很多改進的差別矩陣方法也都以得到與代數方法相同的結果為目標。本文在深入研究不相容決策表的特性后，把不相容決策表的核屬性分為相容核與不相容核兩部分。通過改進HU差別矩陣得到兩個新的差別矩陣，這兩個差別矩陣能分別計算出不相容決策表的相容核與不相容核。

［1］WANG Guo－yin.Rough set theory and knowledge acquisition［M］.Xi’an：Xi’an Jiaotong University Press，2001 （in Chinese）.［王國胤.Rough集理論與知識獲取 ［M］.西安：西安交通大學出版社，2001.］

［2］HU X H，Cercone N.Learning in relational databases：A rough set approach ［J］.Computation Intelligence，1995，11（2）：323－337.

［3］YE D Y，CHEN Z J.A new discernibility matrix and the computation of a core［J］.Acta Electronica Sinica，2002，30 （7）：1086－1088（in Chinese）.［葉東毅，陳昭炯.一個新的差別矩陣及其求核方法 ［J］.電子機學報，2002，30 （7）：1086－1088］

［4］YANG Ming，SUN Zhi－hui.Improvement of discernibility matrix and the computation of a core ［J］.Journal of Fudan University （Nature Science），2004，43 （5）：865－868 （in Chinese）.［楊明，孫志揮.改進的差別矩陣及其求核方法 ［J］.復旦大學學報 （自然科學版），2004，43 （5）：865－868.］

［5］WANG Guo－yin.Calculation methods for core attribute of decision table［J］.Chinese Journal of Computes，2003，26 （5）：611－615（in Chinese）. ［王國胤.決策表核屬性的計算方法［J］.計算機學報，2003，26 （5）：611－615.］

［6］YANG Ming，YANG Ping.Discernibility matrix enriching and computation for attributes reduction ［J］.Computer Science，2006，33 （9）：181－183 （in Chinese）. ［楊明，楊萍.差別矩陣濃縮及其屬性約簡求解方法 ［J］.計算機科學，2006，33（9）：181－183.］

［7］WANG G Y，YU Hong，YANG D C.Decision table reduction based on conditional information entropy ［J］.Chinese Journal of Computers，2002，25 （7）：759－766 （in Chinese）. ［王國胤，于洪，楊大春.基于條件信息熵的決策表約簡 ［J］.計算機學報，2002，25 （7）：759－766.］

［8］XU Zhang－yan，YANG Bing－ru，GUO Yan－ping，et al.Quick algorithm for computing core based on information entropy ［J］.Journal of Chinese Computer Systems，2007，28 （2）：279－282 （in Chinese）.［徐章艷，楊炳儒，郭燕萍，等.基于信息熵的快速求核算法 ［J］.小型微型計算機系統，2007，28 （2）：279－282.］

［9］YE Dong－yi，CHEN Zhao－jiong.Improved method for computing all attribute reducts of an inconsistent decision table ［J］.Mini－Micro Systems，2006，27 （10）：1909－1913 （in Chinese）. ［葉東毅，陳昭炯.不相容決策表全部屬性約簡計算的一個改進方法［J］.小型微型計算機系統，2006，27 （10）：1909－1913.］

［10］YE Dong－yi.New binary discernibility matrix and the computation of a core ［J］.Mini－Micro Systems，2004，25 （6）：965－967（in Chinese）.［葉東毅.一個新的二進制可辨識矩陣及其核的計算 ［J］.小型微型計算機系統，2004，25 （6）：965－967.］

［11］QIN Zhi－hua，TANG Cheng－chao，WANG Jia－yang.A calculation for core attributes of inconsistent decision table ［J］.Computer Engineering and Applications，2005，41 （35）：44－46.［覃志華，唐承超，王加陽.不相容決策表的核屬性計算［J］.計算機工程與應用，2005，41 （35）：44－46.］

［12］QIN Chuan，CHEN Hai－jun，SHI Hua－ji，et al.Attribute reduction algorithm for inconsistent decision tables［J］.Computer Engineering and Applications，2008，44 （24）：162－164（in Chinese）.［秦川，陳海軍，施化吉，李星毅.不相容決策表的屬性約簡算法 ［J］.計算機工程與應用，2008，44（24）：162－164.］

［13］GE Hao，YANG Chuan－jian，LI Long－shu.Efficient algorithm for computing core attributes ［J］.Computer Engineering and Applications，2010，46 （26）：138－141 （in Chinese）.［葛浩，楊傳健，李龍澍.一種高效的核屬性求解方法 ［J］.計算機工程與應用，2010，46 （26）：138－141.］

［14］XU Feng－sheng.An improved approach to computer the feature core［J］.Computer Engineering and Applications，2006，42（13）：57－59 （in Chinese）.［徐鳳生.一種改進的屬性核計算方法 ［J］.計算機工程與應用，2006，42 （13）：57－59.］

［15］XU Feng－sheng.New discernibility matrix and computation of core ［J］.Computer Engineering and Applications，2007，43（1）：38－40 （in Chinese）.［徐鳳生.一種新的可區分矩陣與求核方法 ［J］.計算機工程與應用，2007，43 （1）：38－40.］