基于不可區分序偶的屬性約簡算法

汪小燕，金建輝，申元霞

（安徽工業大學 計算機科學與技術學院，安徽 馬鞍山 243032）

基于不可區分序偶的屬性約簡算法

汪小燕，金建輝，申元霞

（安徽工業大學 計算機科學與技術學院，安徽 馬鞍山 243032）

屬性約簡是粗糙集理論中的重要研究內容之一，但屬性約簡是一個NP難題，需要啟發式知識實現。通過研究不可區分序偶定義，提出了判斷條件屬性組合的分辨能力方法，并基于差別矩陣和不可區分序偶，給出一種適合一致與不一致決策表的屬性約簡算法，該算法能快速求最少屬性且實現簡單，最后通過實例證明了其正確性。

：粗糙集；差別矩陣；序偶；屬性約簡

粗糙集理論是Pawlak等學者在1982年提出的處理不確定、不精確和不完全數據的一種新的數學工具，主要用于知識的簡化及知識依賴性的分析[1]。粗糙集的主要思想是，在保持信息系統分類能力不變的前提下，通過屬性約簡，導出問題的決策或分類規則。屬性約簡是粗糙集挖掘知識的核心內容之一,它描述了信息系統屬性集中的每個屬性是否都是必要的以及如何刪除不必要的知識。近年來，國內外很多學者對屬性約簡進行了深入的研究，提出了一些屬性約簡算法。目前比較常見的屬性約簡方法可以分為:基于差別矩陣的屬性約簡算法[2-5]，基于正區域的屬性約簡算法[6-8]及基于條件信息熵的屬性約簡算法[9-11]?；诓顒e矩陣的屬性約簡算法需要考慮減少差別矩陣的規模，基于正區域的屬性約簡算法需要考慮降低計算正區域的時間，信息熵度量了平均信息量的大小，條件信息熵可反映條件屬性的重要性程度，但計算比較復雜。該文將差別矩陣與屬性重要度相結合，提出一種基于序偶的屬性約簡算法。該算法采用文獻[12]中提出的改進的差別矩陣，并且以條件類取代原矩陣的對象，對于包含重復對象或不一致對象的決策表來說，可有效的降低矩陣的規模。該算法還以序偶表示一對不可區分的條件類，通過計算序偶的個數，來衡量對應條件屬性組合的重要度。該算法能快速求得最小條件屬性集且實現簡單。

1 相關理論

這節主要介紹一些與文中有關的基本理論。

定義1[13]設U為一個論域，P和Q為定義在U上的兩個等價關系簇，Q的P正區域為：

定義2令S=（U，R）是個信息系統，R=C∪D是屬性集合，對任意c∈C，若POSC-{c}（D）=POSC（D），稱c在R中是不必要的，否則c在R中是必要的。C的所有必要屬性組成的集合稱為C的核，記為CORE（C）。

定義3[12]對給定的信息系統IS，定義差別矩陣M={mij}為

文獻[12]提出一種改進的差別矩陣，有效地縮小了矩陣的規模。在現實中，有很多的決策表存在重復對象或沖突對象，文中屬性約簡所使用的差別矩陣在定義3的基礎上，用條件類來代替矩陣中的對象。

定理1[12]對于信息系統IS，若記IDM（C，M）={mij|mij∈M且mij為單個屬性}，則IDM（C，M）=CORE（C），即當且僅當某個mij為單個屬性時，該屬性屬于核CORE（C）。

定義4[14]由兩個具有給定次序的客體所組成的序列稱為序偶，記作＜x，y＞。

2 基于序偶的屬性約簡算法

序偶可以用來表達兩個條件類之間的關系，下面給出不可區分的條件類序偶定義。

定義5對任意決策表S=（U，C∪{d}），B?C，設RC是U上的一個等價關系，U/RC={A1，A2，…，Ai}是條件屬性分類，mij為其分辨矩陣中的元素，設HB={＜Ai，Aj＞|mij≠?∧mij∩B=?，Ai，Aj為mij所對應的矩陣行列元素}，稱HB為根據條件屬性組合B所不可區分的條件類序偶集合。

由定義5可以得到如下的推論1和推論2。

推論1令S=（U，C∪{d}）是決策表，A?C，B?C，若|HA|＞|HB|（|·|表示集合中所包含的序偶個數），屬性集合A的分類能力低于屬性集合B的分類能力。

推論2令S=（U，C∪{d}）是決策表，A?C，?a，b∈C-A，若|HA∪{a}|＞|HA∪|，屬性a相對于集合A的分類能力低于屬性b。

性質1令S=（U，C∪{d}）是決策表，在S的差別矩陣中，HC=?。

證明假設HC≠?，設序偶＜Ai，Aj＞∈HC，mij為條件類Ai，Aj在差別矩陣中所對應的元素，根據定義5知mij∩C=?，而C是整個條件屬性集合，則mij?C，mij=?，所以＜Ai，Aj＞?HC，與假設矛盾，故HC=?。

性質2令S=（U，C∪{d}）是決策表，|C|=n，若n-1個條件屬性所對應的不可區分的條件類序偶集合的交集非空，則該非空集合中的序偶在差別矩陣中所對應的元素為核屬性。

證明若n-1個條件屬性所對應的不可區分的條件類序偶集合的交集非空，設序偶＜Ai，Aj＞為非空交集中的元素，則條件類Ai，Aj根據n-1個條件屬性都無法區分，根據定義5知條件類Ai，Aj在分辨矩陣中所對應的元素mij≠?，所以mij僅包含第n個條件屬性，根據定理1知mij中包含的條件屬性為核屬性。

性質3令S=（U，C∪{d}）是決策表，|C|=n，若任意n-1個條件屬性所對應的不可區分的條件類序偶集合的交集為空，則該決策表沒有核屬性。

證明假設該決策表存在核屬性a∈C，若mij={a}，mij所對應的條件類序偶為＜Ai，Aj＞，根據定義5，其他n-1個條件屬性所對應的不可區分的條件類序偶集合中都含有序偶＜Ai，Aj＞，則該n-1個條件屬性所對應的不可區分的條件類序偶集合的交集非空，與任意n-1個條件屬性所對應的不可區分的條件類序偶集合的交集為空矛盾，所以該決策表沒有核屬性。

性質4令S=（U，C∪{d}）是決策表，|C|=n，設該決策表存在唯一的核屬性a∈C，則包含核屬性a的任意n-1個條件屬性所對應的不可區分的條件類序偶集合的交集為空。

證明假設包含核屬性a的n-1個條件屬性所對應的不可區分的條件類序偶集合的交集不為空，由性質2知該非空集合中的序偶在差別矩陣中所對應的元素為核屬性，也就是說在該決策表中還存在其他的核屬性，與該決策表存在唯一的核屬性矛盾，故該性質成立。

定理2令S=（U，C∪{d}）是決策表，A?C，若HA=HC，對?a∈A，HA-{a}≠HC，屬性集合A為信息系統S的屬性約簡。

證明由性質1知：HC=?，根據條件屬性集合C，不同的條件類之間都可以區分。若HA=HC，則HA=?，根據條件屬性集合A，不同的條件類之間也都可以區分。對?a∈A，HA-{a}≠HC，如果去掉集合A中的任意一個屬性，會存在不同的條件類不可區分的情況，則屬性集合A為信息系統S的屬性約簡。

定理3令S=（U，C∪{d}）是決策表，A?C，若HA=?，對?a∈A，HA-{a}≠?，屬性集合A為信息系統S的屬性約簡。

證明由性質1和定理2可證。

基于序偶的屬性約簡算法，通過計算各條件屬性組合所對應的不可區分的條件類序偶集合，根據集合所包含的序偶數目的大小，選擇分類能力大的條件屬性加入到屬性約簡集RED（R）中，不需要先計算核屬性。當HRED（R）=HC時，就可以獲得屬性約簡集RED（R）。新的屬性約簡算法描述如下：

輸入：決策表S=（U，R），R=C∪D，C是條件屬性集，D={d}是決策屬性集。

輸出：約簡集RED（R）

（1）RED（R）=?

（2）for i=1 to m//m為條件屬性的個數

（3）計算 Hci

（4）next i

（5）取c1滿足：|Hc1|=min{|Hci|}（ci∈C）

（6）置RED（R）=RED（R）∪{c1}；

（7）if HRED（R）=HCthen go 10 else go 8；

（8）計算所有c∈C-RED（R）的值HRED（R）∪{c}，取c2滿足：|HRED（R）∪{c2}|=min{|HRED（R）∪{c}|}（c∈C-RED（R））

（9）RED（R）=RED（R）∪{c2}，go 7；

（10）輸出最小約簡RED（R）。

3 實例分析

下面通過例子說明算法的正確性。

例某一決策表見表1，其中條件屬性集C={a，b，c，e}，決策屬性集D={d}，其差別矩陣見表2。

對表1中的對象按照條件屬性分類如下：

A1={X1，X2，X6}，A2={X3}，A3={X4，X7}，A4={X5}。

（1）計算各條件屬性的區分能力

Ha={＜A2，A1＞}，

Hb={＜A2，A3＞，＜A2，A4＞，＜A3，A2＞，＜A4，A2＞}，

Hc={＜A2，A4＞，＜A2，A1＞，＜A4，A2＞，＜A4，A1＞}，

He={＜A2，A3＞，＜A2，A1＞，＜A3，A2＞，＜A3，A1＞}。

（2）由于|Ha|=1，所以a的區分度最大。所以設RED（R）={a}。而HC=?，

HRED（R）≠HC，故需要增加其他屬性，以構成最小約簡。

（3）計算

HRED（R）∪=?，

HRED（R）∪{c}={＜A2，A1＞}，

HRED（R）∪{e}={＜A2，A1＞}。

選擇b加入到RED（R）={a，b}，此時HRED（R）=HC，所以該決策表的最小屬性約簡為{a，b}。

表1 某一決策表

表1 決策表差別矩陣

4 結語

文中討論了基于差別矩陣的屬性重要度的屬性約簡算法，利用不可區分的序偶個數作為啟發式信息，選擇屬性，當某一條件屬性組合對應的不可區分序偶集合為空時，可獲得屬性約簡。并且以不可區分序偶研究了屬性約簡的相關理論。該算法的屬性重要度計算簡單，差別矩陣規模小，判斷約簡條件簡單。最后通過實例分析,驗證該算法是有效的。

參考文獻：

[1]PAWLAK Z.Rough sets[J].International Journal of Computer and Information Science，1982，11（5）：341-356.

[2]周建華，徐章艷，章晨光.改進的差別矩陣的快速屬性約簡算法[J].小型微型計算機系統，2014，35（4）：831-834.

[3]葛浩，李龍澍，楊傳健.新的可分辨矩陣及其約簡方法[J].控制與決策，2010，25（12）：1891-1895.

[4]CHEN H H，PEI Z，ZHANG L.Knowledge reduction based on binary discernibility matrix in variable precision rough set[C]//2006 International Symposium on Communications and Information Technologies，2006：949-954.

[5]HAO W L，ZHANG X B.A simplified discernibility matrix of the attribute reduction method[C]//Information Management，Innovation Management and Industrial Engineering（ICIII），2010 International Conference on，2010，2：166-168.

[6]徐章艷，劉作鵬，楊炳儒，等.一個復雜度為max（O（|C||U|），O（|C|2｜U/C｜））的快速屬性約簡算法[J].計算機學報，2006，29（3）：391-399.

[7]LI J，FAN X W，WANG X.An improved attribute reduction algorithm based on importance of attribute value[J].Procedia Engineering，2010，7：356-359.

[8]李俊麗，秦振吉.改進的基于正區域的知識約簡算法及其應用研究[J].計算機與數字工程，2014，42（7）：1153-1156.

[9]王國胤，于洪，楊大春.基于條件信息熵的決策表約簡[J].計算機學報，2002，25（7）：759-766.

[10]甄宇峰，施化吉.基于條件信息熵和相關系數的屬性約簡算法[J].計算機工程與應用，2011，47（16）：26-28.

[11]李俊麗.改進的基于條件信息熵的屬性約簡算法[J].中北大學學報（自然科學版），2014，35（6）：709-712.

[12]楊明.一種基于改進差別矩陣的核增量式更新算法[J].計算機學報，2006，29（3）：407-413.

[13]王國胤.Rough理論與知識獲取[M].西安：西安交通大學出版社，2001.

[14]汪小燕，葉紅，楊思春，等.離散數學[M].北京：人民郵電出版社，2014.

Attribute reduction algorithm based on indiscernibility ordered pair

WANG Xiaoyan，JIN Jianhui，SHEN Yuanxia
（School of Computer Science&Technology，Anhui University of Technology，Ma’anshan 243032，China）

Attribution reduction is one of the important topics in rough set theory.But it is a NP problem and needs to be realized by knowledge of elicitation method.After exploring the definition of indiscernibility ordered pair,we proposed a discernibility method for judging condition attribute combination.Based on discernable matrix and indiscernibility ordered pair,we put forward an attribute reduction algorithm suitable for consistent and inconsistent decision table.Using this algorithm,we can obtain the smallest attributes quickly and easily.The examples show it is workable in the practice.

rough set；discernable matrix；ordered pair；attribute reduction

責任編輯：艾淑艷

TP301

：A

：2096-3289（2017）02-0055-04

2015-07-01

國家青年科學基金資助項目（61300059）；安徽省高校自然科學基金資助項目（KJ2012Z024；KJ2012Z031）

汪小燕（1974-），女，安徽桐城人，副教授，碩士，研究方向：數據挖掘，粗糙集理論，概念格。