不相容決策表求核方法

陳鳳娟

（遼寧對外經(jīng)濟(jì)貿(mào)易學(xué)院 信息技術(shù)系，遼寧 大連116052）

0 引 言

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

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

1 基本概念

代數(shù)觀中的正域、屬性必要性及核屬性的相關(guān)概念如下［1］：

定義1 設(shè)U為一個論域，P，Q為定義在U上的兩個等價(jià)關(guān)系族，Q的P正域記作POSP（Q），定義為POSP。

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

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

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

從上面的定義可知，當(dāng)去掉某個屬性會導(dǎo)致正域發(fā)生變化時(shí)，則該屬性是核屬性。

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

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

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

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

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

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

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

2 現(xiàn)有求核方法存在的問題

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

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

下面針對文獻(xiàn) ［3］和文獻(xiàn) ［5］中用到的3個不相容決策表，分別分析這些決策表中相容部分劃分塊和不相容部分劃分塊的變化，從而說明現(xiàn)有的求核方法存在的問題，如表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｝｝；

從上面的計(jì)算可知：

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

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

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

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

由以上分析可得，決策表1的核屬性集為 ｛C1，C2｝，其中，相容核為 ｛C2｝，不相容核為 ｛C1｝。代數(shù)方法求得的核為相容核 ｛C2｝；改進(jìn)的差別矩陣 （如文獻(xiàn) ［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｝｝。

從上面的計(jì)算可知：

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

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

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

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

由以上分析可得，決策表2的核屬性集為 ｛C1，C2｝，其中，相容核為 ｛C1，C2｝，不相容核為Φ。代數(shù)方法、改進(jìn)的差別矩陣方法、信息熵的方法和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｝｝。

從上面的計(jì)算可知：

（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｝，導(dǎo)致正域POSC（D）發(fā)生變化，因此，C2屬于相容核。

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

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

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

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

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

3 改進(jìn)的差別矩陣

HU差別矩陣定義如下：

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

文獻(xiàn)中給出如下結(jié)論：當(dāng)且僅當(dāng)某個mij為單個屬性時(shí)，該屬性屬于核CORE（C）。

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

定義7 對于信息系統(tǒng)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）。當(dāng)mij為單個屬性時(shí)，該屬性是相容核屬性。這個結(jié)果與代數(shù)觀的核屬性定義方法計(jì)算的核屬性等價(jià)

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

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

決策表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是不相容核。

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

4 結(jié)束語

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

［1］WANG Guo－yin.Rough set theory and knowledge acquisition［M］.Xi’an：Xi’an Jiaotong University Press，2001 （in Chinese）.［王國胤.Rough集理論與知識獲取 ［M］.西安：西安交通大學(xué)出版社，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］.電子機(jī)學(xué)報(bào)，2002，30 （7）：1086－1088］

［4］YANG Ming，SUN Zhi－h(huán)ui.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ìn)的差別矩陣及其求核方法 ［J］.復(fù)旦大學(xué)學(xué)報(bào) （自然科學(xué)版），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ì)算方法［J］.計(jì)算機(jī)學(xué)報(bào)，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］.計(jì)算機(jī)科學(xué)，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］.計(jì)算機(jī)學(xué)報(bào)，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］.小型微型計(jì)算機(jī)系統(tǒng)，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ì)算的一個改進(jìn)方法［J］.小型微型計(jì)算機(jī)系統(tǒng)，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ìn)制可辨識矩陣及其核的計(jì)算 ［J］.小型微型計(jì)算機(jī)系統(tǒng)，2004，25 （6）：965－967.］

［11］QIN Zhi－h(huán)ua，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ì)算［J］.計(jì)算機(jī)工程與應(yīng)用，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］.計(jì)算機(jī)工程與應(yīng)用，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］.計(jì)算機(jī)工程與應(yīng)用，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ìn)的屬性核計(jì)算方法 ［J］.計(jì)算機(jī)工程與應(yīng)用，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）.［徐鳳生.一種新的可區(qū)分矩陣與求核方法 ［J］.計(jì)算機(jī)工程與應(yīng)用，2007，43 （1）：38－40.］