一种新的决策表属性值分类方法

汪小燕，程泽凯，申元霞

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

一种新的决策表属性值分类方法

汪小燕，程泽凯，申元霞

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

在粗糙集值约简算法中，常常需要对决策表的条件属性值进行分类。基于Skowron分辨矩阵，提出一种新的属性值分类矩阵。通过该矩阵可以方便的获取决策表中各条件属性的冲突记录集和重复记录集，并能够确保对这些冲突记录集和重复记录集的条件属性值进行处理后，决策表中剩下的条件属性值被删除后不会产生新的冲突记录和重复记录。理论分析与实例表明：该方法能有效处理决策表属性值分类。

粗糙集；决策表；分辨矩阵；分类；值约简

波兰数学家Pawlak在1982年提出的粗糙集理论是一种处理不确定、不精确和不完全数据的一种新的数学工具，主要用于知识的简化及知识依赖性的分析[1]。在粗糙集理论中，为了从决策表中获取有价值的知识，通常采取属性约简和值约简的方法，值约简是粗糙集理论中非常重要的研究课题，目前有很多学者提出了多种值约简算法[2-10]。在值约简算法中，一般首先对决策表的属性值进行分类，根据属性值分类后的决策表，对属性值约简，最后得出分类规则。传统的属性值分类方法是对决策表中的每条记录逐列考察各个条件属性。通过删除某一个条件属性的值来判断是否会产生冲突记录或重复记录，或冲突记录与重复记录都不会产生，根据删除条件属性后产生记录的结果将决策表中的属性值分为三类。为了能够加快决策表的属性值分类，从整体上对各个条件属性的值分类，在Skowron分辨矩阵的基础上，提出一种属性值分类矩阵，根据该分类矩阵确定条件属性的冲突记录集和重复记录集，对冲突记录集和重复记录集中的对象在对应的条件属性值上做相应处理后，决策表中剩下的属性值就是第三类属性值，避免了对第三类属性值的判断。

1　相关概念

下面给出文中所涉及到的一些相关概念。

定义1[2]一个信息系统（也称信息表）表示为S=。这里，U是对象的集合，也称为论域，R是属性集合，表示属性r的值域，f：U×R→V是一个信息函数，它指定U中的每一个对象x的属性值，即对x∈U，r∈R，有f（x，r）∈Vr。如果属性集R可以分为条件属性集C和决策属性集D，即R=C∪D，C∩D=ϕ，D≠ϕ，则该信息系统称为决策系统或决策表。

定义2属性集A的不可分辨关系IND（A）为：IND（A）＝{（x，y）∈U×U|∀a∈A，f（x，a）=f（y，a）}，U/IND（A）表示不可分辨关系IND（A）在U上导出的划分，也可表示为U/A。

定义3分辨矩阵由Skowron提出[2]，其定义为：令S=是一个信息系统，U为论域且，R=C∪D是属性集合，子集C和D分别是条件属性集和决策属性集，r（x）是对象x在属性r上的值，D（x）是记录x在D上的值，则分辨矩阵记为

显然，分辨矩阵是一个按主对角线对称的矩阵，在建立分辨矩阵的时候，只需要考虑其上三角（或下三角）部分就可以了。

2　决策表属性值分类方法

文献[3-5]提出不同的值约简算法，对决策表的属性值分类都是采用对决策表中的每条记录逐个删除各个条件属性值的方法。如果删除某条记录的一个条件属性，产生了冲突记录，则该属性是核值属性，需要保留该记录的原属性值；如果没有产生冲突记录但是有重复记录，则在该记录的此属性值上标记为“*”；如果既不产生冲突记录也不产生重复记录，则在该记录的此属性值上标记为“？”。这种属性值分类方法易于理解，但对每条记录的任意一个条件属性删除时，都要在整个决策表中观察是否产生冲突记录或重复记录，还是冲突记录和重复记录都不产生。为了改进原有的属性值分类方法，可以在决策表属性值分类时，将保留原值的核值属性所对应的记录集和标记为“*”的属性值对应记录集先提取出来，那么剩下的就是第三类属性值。

在新的决策表属性值分类方法中，需要用到属性值分类的矩阵，该矩阵是在Skowron分辨矩阵的基础上，增加相同决策类对象的比较，并且对决策属性也进行比较，如果两个对象的决策属性不同，则将决策属性也写入到属性值组合中。所提出的用于属性值分类的矩阵，定义如下。

定义4S=是一个信息系统，U为论域且，，R=C∪D是属性集合，子集C和 D分别是条件属性集和决策属性集，r（x）是对象x在属性r上的值，则用于属性值分类的矩阵记为

为了加快属性值分类，现提出如下属性值分类算法：

输入：决策信息系统S=，U为论域，R=C∪D是属性集合，子集C和D分别是条件属性集和决策属性集

输出：属性值分类表

命题1在属性值分类矩阵中，若属性组合Mij中包含决策属性且Mij=2（|·|表示Mij中包含的属性个数），c是一条件属性且c∈Mij，则Mij所对应的行列对象在属性c上要保留原值。

证明若属性组合Mij中包含决策属性且，设条件属性c∈Mij，由定义4知Mij所对应的行列对象决策属性不同，且只有一个条件属性不同，如果删除Mij所对应的行列对象的c属性值，则这两个对象一定成为冲突记录，c为核值属性，所以Mij所对应的行列对象在c属性上要保留原值。

定义5在属性值分类矩阵中，若属性组合Mij中包含决策属性且，c是一条件属性且c∈Mij，则所有只包含c属性和决策属性的Mij对应的行列对象的并集，称为c冲突记录集，记为Tc。

命题3令S=是一个信息系统，U为论域且，c为一条件属性，若c存在冲突记录集Tc和重复记录集Fc，则U-Tc-Fc中的所有对象删除c属性后都不会产生冲突记录和重复记录。

定义7令S=是一个信息系统，U为论域且，R=C∪D是属性集合，子集C和D分别是条件属性集和决策属性集，c为一条件属性，若c存在冲突记录集Tc和重复记录集Fc，则称UTc-Fc为c无冲突重复记录集。

由定义7知，若c只存在冲突记录集Tc，不存在重复记录集Fc，则U-Tc为c无冲突重复记录集；若c不存在冲突记录集Tc，只存在重复记录集Fc，则U-Fc为c无冲突重复记录集。若c不存在冲突记录集Tc和重复记录集Fc，则U为c无冲突重复记录集。

决策表属性值分类的新方法步骤描述：（1）对决策表进行属性约简，去掉决策表中重复记录；（2）根据约简后的决策表，按照属性值分类矩阵的生成算法生成属性值分类矩阵；（3）扫描属性值分类矩阵，对任意条件属性c，看是否存在冲突记录集Tc和重复记录集Fc，如果存在，分别记录冲突记录集Tc和重复记录集Fc；（4）根据第（3）步的结果，对任意条件属性c，若存在冲突记录集Tc，则在约简后的决策表中，保留冲突记录集中c属性的原值；（5）根据第（3）步的结果，对任意条件属性c，若存在重复记录集Fc，则在约简后的决策表中，将重复记录集中属性所对应的值标记为“*”；（6）决策表中剩余的条件属性值，也就是去除该属性后，既不会产生冲突记录也不会产生重复记录的属性值，将这些属性值标记为“?”。最后得出属性值分类的决策表。

新的决策表属性值分类方法在建立了属性值分类矩阵后，对前两类属性值很容易判断，并且避免了对第三类属性值的判断。

3　实例

例如某一约简后的决策表见表1：其中条件属性集C={a，b，d}，决策属性集D={e}。为表1建立属性值分类矩阵如表2所示。由表2知：Ta={2，3}，Tb={1，4}，Td={4，5}，Fa={5，6}，Fb={6，7}，Fd={1，2}。根据表2获得的冲突记录集，将对象2，3在属性a上保留原值，将对象1，4在属性b上保留原值，将对象4，5在属性d上保留原值，根据表2获得的重复记录集，将对象5，6在属性a上标记为*，将对象6，7在属性b上标记为*，将对象1，2在属性d上标记为*，表1中剩下的条件属性值标记为？。属性值分类后的决策表如表3所示。

表1　属性约简后的决策表

表2　表1的属性值分类矩阵

表3　属性值分类表

4　结语

文中基于Skowron分辨矩阵，提出属性值分类矩阵，利用该分类矩阵给出决策表中属性值快速分类的方法，并通过实例给出了该方法具体实现，将该方法加入到值约简算法中，可以提高值约简的速度。

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

[2]王国胤.Rough集理论与知识获取[M].西安：西安交通大学出版社，2003.

[3]常犁云，王国胤，吴渝.一种基于Rough Set理论的属性约简及规则提取方法[J].软件学报，1999，10（11）：1206-1211.

[4]林嘉宜，彭宏，郑启伦.一种新的基于粗糙集的值约简算法[J].计算机工程，2003，29（4）：70-71.

[5]杨振峰，郭景峰，常峰.一种基于粗集的值约简方法[J].计算机工程，2003，29（9）：96-97.

[6]邓少波，黎敏，关素洁，等.一种非相容决策表的属性值与属性约简方法[J].计算机应用研究，2011，28（4）：1308-1310.

[7]鄂旭，邵良杉，张毅智，等.一种基于粗糙集理论的规则提取方法[J].计算机科学，2011，38（1）：232-235.

[8]杜跃，王治和，景永霞.基于关联规则挖掘的粗糙集属性值约简算法研究[J].苏州科技学院学报（自然科学版），2008，25（1）：16-19.

[9]罗秋瑾，成蓉华，纳静.基于不可辨识矩阵的值约简算法[J].云南民族大学学报（自然科学版），2011，20（6）：508-510.

[10]兰聪花，王逢娟.一种新的基于区分矩阵的值约简算法[J].工业仪表与自动化装置，2014（2）：113-116.

A new classification method for attribute values in a decision table

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

In rough set attribute value reduction,it is necessary to classify condition attribute values in a decision table.A new classification matrix for attribute values is put forward based on Skowron discernible matrix.By using this matrix,we can easily obtain the conflict record set and duplicate record set of each condition attribute in a decision table,and no more other conflict records or duplicate records can be produced after handling the corresponding condition attribute values of these conflict record sets and duplicate record sets and deleting the rest of condition attribute values in a decision table.The theoretical analysis and example show that this method can effectively deal with attribute value classification in a decision table.

rough set；decision table；discernible matrix；classification；value reduction

TP301

A

1672－0687（2016）01－0061－04

责任编辑：艾淑艳

2014－05－28

国家青年科学基金资助项目（61300059）；安徽省高校自然科学基金资助项目（KJ2012Z024；KJ2012Z031）

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