汪小燕，金建輝，申元霞

（安徽工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 馬鞍山 243032）

基于不可區(qū)分序偶的屬性約簡算法

汪小燕，金建輝，申元霞

（安徽工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 馬鞍山 243032）

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

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

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

1 相關(guān)理論

這節(jié)主要介紹一些與文中有關(guān)的基本理論。

定義1[13]設(shè)U為一個(gè)論域，P和Q為定義在U上的兩個(gè)等價(jià)關(guān)系簇，Q的P正區(qū)域?yàn)椋?/p>

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

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

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

定理1[12]對于信息系統(tǒng)IS，若記IDM（C，M）={mij|mij∈M且mij為單個(gè)屬性}，則IDM（C，M）=CORE（C），即當(dāng)且僅當(dāng)某個(gè)mij為單個(gè)屬性時(shí)，該屬性屬于核CORE（C）。

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

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

序偶可以用來表達(dá)兩個(gè)條件類之間的關(guān)系，下面給出不可區(qū)分的條件類序偶定義。

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

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

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

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

性質(zhì)1令S=（U，C∪j5i0abt0b）是決策表，在S的差別矩陣中，HC=?。

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

性質(zhì)2令S=（U，C∪j5i0abt0b）是決策表，|C|=n，若n-1個(gè)條件屬性所對應(yīng)的不可區(qū)分的條件類序偶集合的交集非空，則該非空集合中的序偶在差別矩陣中所對應(yīng)的元素為核屬性。

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

性質(zhì)3令S=（U，C∪j5i0abt0b）是決策表，|C|=n，若任意n-1個(gè)條件屬性所對應(yīng)的不可區(qū)分的條件類序偶集合的交集為空，則該決策表沒有核屬性。

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

性質(zhì)4令S=（U，C∪j5i0abt0b）是決策表，|C|=n，設(shè)該決策表存在唯一的核屬性a∈C，則包含核屬性a的任意n-1個(gè)條件屬性所對應(yīng)的不可區(qū)分的條件類序偶集合的交集為空。

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

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

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

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

證明由性質(zhì)1和定理2可證。

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

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

輸出：約簡集RED（R）

（1）RED（R）=?

（2）for i=1 to m//m為條件屬性的個(gè)數(shù)

（3）計(jì)算 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）計(jì)算所有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 實(shí)例分析

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

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

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

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

（1）計(jì)算各條件屬性的區(qū)分能力

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的區(qū)分度最大。所以設(shè)RED（R）={a}。而HC=?，

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

（3）計(jì)算

HRED（R）∪=?，

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

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

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

表1 某一決策表

表1 決策表差別矩陣

4 結(jié)語

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

參考文獻(xiàn)：

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

[2]周建華，徐章艷，章晨光.改進(jìn)的差別矩陣的快速屬性約簡算法[J].小型微型計(jì)算機(jī)系統(tǒng)，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]徐章艷，劉作鵬，楊炳儒，等.一個(gè)復(fù)雜度為max（O（|C||U|），O（|C|2｜U/C｜））的快速屬性約簡算法[J].計(jì)算機(jī)學(xué)報(bào)，2006，29（3）：391-399.

[7]LI J，F(xiàn)AN X W，WANG X.An improved attribute reduction algorithm based on importance of attribute value[J].Procedia Engineering，2010，7：356-359.

[8]李俊麗，秦振吉.改進(jìn)的基于正區(qū)域的知識(shí)約簡算法及其應(yīng)用研究[J].計(jì)算機(jī)與數(shù)字工程，2014，42（7）：1153-1156.

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

[10]甄宇峰，施化吉.基于條件信息熵和相關(guān)系數(shù)的屬性約簡算法[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（16）：26-28.

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

[12]楊明.一種基于改進(jìn)差別矩陣的核增量式更新算法[J].計(jì)算機(jī)學(xué)報(bào)，2006，29（3）：407-413.

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

[14]汪小燕，葉紅，楊思春，等.離散數(shù)學(xué)[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

責(zé)任編輯：艾淑艷

TP301

：A

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

2015-07-01

國家青年科學(xué)基金資助項(xiàng)目（61300059）；安徽省高校自然科學(xué)基金資助項(xiàng)目（KJ2012Z024；KJ2012Z031）

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