刘远峰 杨碧华

（1.暨南大学信息技术研究所，广东广州510075；2.暨南大学信息科学技术学院，广东广州510632）

1.引言

粗糙集理论[1-4]是一种处理不确定和不精确性问题的新的数学工具，它是波兰华沙理工大学科学家帕克拉克（Paw lak）于1982年提出的，该理论具有很强的定性分析能力，能够有效地表达不确定的或不精确的知识，善于从数据中获取知识，并能利用不定性、不完整的经验知识进行推理等。粗糙集理论中对象的隶属函数值依赖于知识库，它可以从所需处理的数据中直接得到，无需外界的任何信息，所以用它来反映知识的模糊性是比较客观的。

1.1 粗糙集理论的基本概念

定义1知识库K=(U,R)，对于每个子集

XU⊆U和一个等价关系R，定义两个子集：下近似集和上近似集

1.2 知识约简

粗糙集知识约简[5-7]，就是在保持知识库的分类和决策能力不变的条件下，删除其中不相关或不重要的知识。

定义2设P和Q是U中的等价关系族，R∈P，如果POSP(Q)=POS(P-{R})(Q)，则称R为P中Q不必要的；否则称R为P中Q必要的。如果P中每个R都是Q必要的，则称P为Q独立的；否则称为依赖的。

定义3给定一个知识库K=（U，S）和知识库上的两个等价关系簇P，Q属于S，对任意的G属于P，若G满足以下两条：

(1)G是Q独立的，即G是P的Q独立子集

(2)PosG(Q)=POSP(Q)

则称G是P的一个Q约简。

2.知识约简的应用

以下的例子是基于知识约简在病人是否得了流感的简单应用。

条件属性决策属性病人头痛肌肉痛体温流感e1是是正常否e2是是高是e3是是很高是e4否是正常否e5否否高否e6否是很高是e7否否高是e8否是很高否

U={e1,e2,e3,e4,e5,e6,e7,e8},C={头痛,肌肉痛,体温},D={流感}，设C1=头痛,C2=肌肉痛,C3=体温。

3.问题的提出

如果属性约简的结果只有一个相对约简，例如上面的例子只有一个相对约简，那么决策表属性的约简结果就是这个相对约简；但是如果约简的结果出现多个相对约简的情况，那么如何在这些约简中进行选择，就是一个问题。因为根据决策树自身的特点，不同的属性选择结果会直接影响决策树的构建和最终的决策规则。而决策树属性的选取的传统方法是主成分分析，那么由此方法得到启发，从而作了这样的设想，对每个属性约简所包含的每个属性进行逐一的重要属性计算，从中选取属性综合重要性大的那个约简作为决策树最后的条件属性。而属性重要性的基本思想是，在决策表中,不同的属性可能具有不同的重要性,为了找出某些属性(或属性集)的重要性,可以从表中去掉一些属性,再来考察没有该属性后分类会怎样变化。若去掉该属性相应分类变化较大,则说明该属性的强度大,即重要性高;反之,说明该属性的强度小,即重要性低。不过这种设想是否可行仍还在研究中。

计算每个约简中属性子集的重要性，属性子集C'⊆C关于D的重要性如下：

4.结论

本文是基于粗糙理论的属性约简在决策树中的应用，从而能去掉决策属性中一些冗余的属性，得到最高的分类准确率，而不依赖人的主观知识和经验，使决策树的构架更准确；同时提出了如何选取相对约简的问题，该问题仍在探讨中。

[1] Paw lak Z.A treatiseon rough sets.In:Peters JF,Skowron A,des.Proc.of the Trans.on Rough Sets IV.LNCS 3700,Belin,Heiderberg:Springer-Verlag,2005.1-17.

[2] 陈波,周明天.粒度粗糙理论研究[J].软件学报,2008,03:565-583.

[3] Chen B,Zhou MT.A lesniewski mereological analysis on roughness theory.Computer Science,2006,33(7):171-175.

[4] Radzikowska AM,Kerre EE.A comparative study of fuzzy Sets and Systems,2002,126(2):137-155.

[5] 苗夺谦,胡桂荣.知识简约的一种启发式算法[J].计算机研究与发展,1999,06:42-45.

[6] Wei-Hua Gui,Chun-Hua Yang,Jing Teng.Intelligent fault diagnosis in lead-zinc smelting process[J].International of Automation and Computing,2007,4(2).

[7] Daniel Merkle,Martin Midderndorf.Ant Colony Optimization with Global Pheromone Evaluation for Scheduling a Single Machine[J].Applied Intelligence,2003,18(1).