基于不可区分序偶的属性约简算法

汪小燕，金建辉，申元霞

（安徽工业大学 计算机科学与技术学院，安徽 马鞍山 243032）

基于不可区分序偶的属性约简算法

汪小燕，金建辉，申元霞

（安徽工业大学 计算机科学与技术学院，安徽 马鞍山 243032）

属性约简是粗糙集理论中的重要研究内容之一，但属性约简是一个NP难题，需要启发式知识实现。通过研究不可区分序偶定义，提出了判断条件属性组合的分辨能力方法，并基于差别矩阵和不可区分序偶，给出一种适合一致与不一致决策表的属性约简算法，该算法能快速求最少属性且实现简单，最后通过实例证明了其正确性。

：粗糙集；差别矩阵；序偶；属性约简

粗糙集理论是Pawlak等学者在1982年提出的处理不确定、不精确和不完全数据的一种新的数学工具，主要用于知识的简化及知识依赖性的分析[1]。粗糙集的主要思想是，在保持信息系统分类能力不变的前提下，通过属性约简，导出问题的决策或分类规则。属性约简是粗糙集挖掘知识的核心内容之一,它描述了信息系统属性集中的每个属性是否都是必要的以及如何删除不必要的知识。近年来，国内外很多学者对属性约简进行了深入的研究，提出了一些属性约简算法。目前比较常见的属性约简方法可以分为:基于差别矩阵的属性约简算法[2-5]，基于正区域的属性约简算法[6-8]及基于条件信息熵的属性约简算法[9-11]。基于差别矩阵的属性约简算法需要考虑减少差别矩阵的规模，基于正区域的属性约简算法需要考虑降低计算正区域的时间，信息熵度量了平均信息量的大小，条件信息熵可反映条件属性的重要性程度，但计算比较复杂。该文将差别矩阵与属性重要度相结合，提出一种基于序偶的属性约简算法。该算法采用文献[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∪{b}|，属性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）∪{b}=Ø，

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-），女，安徽桐城人，副教授，硕士，研究方向：数据挖掘，粗糙集理论，概念格。