Rough集在知识发现中的价值分析

1、Rough集在知识发现中的价值分析0 引言Rough集理论是一种数据分析理论，是由波兰数学家Z.Pawlak等一批科学家提出的，是对不完整数据及不精确知识进行表达、学习、归纳的一种方法。现在，Rough集理论主要应用在知识发现、机器学习、决策分析、医院诊断、数据挖掘等领域。它的优点是不需要先验知识便可从数据或经验中获得知识，生成决策规则。1 Rough集的基本概念现实生活中的信息一般都用二维表来表示，行代表不同的个体，列代表对应个体的属性。信息表中的数据可以从各行各业的业务数据中收集。以表1为例介绍Rough集的概念。对于p1，p2，p3这三个实例，其头疼和肌肉疼的属性值都是是;，因此，从条件

2、属性头疼和肌肉疼的角度看，这三个实例是不可分辨的。同样，p4，p6在这两个属性上也是不可分辨的。所以由头疼和肌肉疼这两个条件属性构成的不分明集p1，p2，p3，p4，p6，p5被称为基本集。定义1 令X？哿U，当X能用属性子集B确切地描述时，称X是B可定义的，否则称X是B不可定义的。B可定义集也称作B精确集，B不可定义集也称为B非精确集或B Rough集（在不发生混淆的情况下也简称Rough集）。例1 在表1所示的决策表中，集合p1，p2，p4，p5就是条件属性子集B=头疼，肌肉疼不可定义的，是B Rough集。因为根据条件属性子集B，样例p3和p1，p2是不可分辨的，p6和p4是不可分辨的。

3、我们不能根据条件属性子集B来对所有实例是否属于集合p1，p2，p4，p5作精确判定。但是，如果样例的属性取值头疼为否;，肌肉疼为否;，则我们可以确定地说该样例属于集合p1，p2，p4，p5。由此可见，对于一个样例子集，也称为一个概念，根据一个条件属性子集所确定的不分明关系，我们有可能能够准确地判定某些样例是否属于该概念，也有可能不能够判定某些样例是否属于该概念。为了描述这个问题，Rough集理论采用了上近似、下近似的概念。定义2 给定知识表达系统S=，对于每个子集X？哿U和不分明关系B，X的上近似集和下近似集分别可以由B的基本集定义如下：下近似集：B-（X）=∪Yi|（Yi∈

4、U| IND（B）∧Yi=X）；上近似集：B-（X）=∪Yi|（Yi∈U| IND（B）∧Yi∩X≠ ？覫）；边界域BNB（x）=B-（X）B-（X）；正域POSB（X）=B-（X）；例2 在表1所示的决策表中，对于属性子集B=头疼，肌肉疼，集合X=p3，p4，p5是一个B Rough集，下面分别计算集合X的上近似集、下近似集、正域、边界域。首先计算论域U的所有B基本集，U|IND（B）=p1，p2，p3，p4，p6，p5，令B1=p1，p2，p3，B2=p4，p6，B3=p5集合X与基本集有如下关系：X∩B1=p3≠？覫，X&ca

5、p;B2=p4≠？覫，X∩B3=p5≠？覫由此可得集合X的上近似集、下近似集、正域、边界域：B-（X）=B1∪ B2∪B3=p1，p2，p3，p4，p5，p6，B-（X）=B3=p5，POSB（X）=B-（X）=p5，BNB（x）=B-（X）B-（X）=B1∪ B2= p1，p2，p3，p4，p62 知识发现的基本概念知识发现是识别出存在于数据库中有效的、新颖的、具有潜在效用的乃至最终可理解的模式的非平凡过程。知识发现包括数据预处理、数据约简、规则生成、数据依赖关系获取等多个步骤。Rough集理论支持知识发现的每个步骤，所以Rough集理论广泛应用于

6、各行各业的知识发现研究之中。3 Rough集在知识发现中的应用决策表中包含了某一领域中大量的数据记录，是领域内的实例数据库。它记录了大量实例的属性值和决策情况，是领域内的知识载体。知识发现的目的就是要通过分析这个实例数据库中的数据来得到该领域中有用的、潜在的规律性知识。样例的记录，可能不完整，或者有差错，或者有噪音，甚至还可能有矛盾。这就需要我们对记录数据进行预处理和约简，使得数据能够更好地应用于数据挖掘。3.1 数据预处理 我们可以采用不同的方法从不同的领域收集原始数据，但收集来的原始数据往往不能直接用于知识发现，必须对它进行数据预处理。即对原始数据进行集成、清洗、转换和简化等操作，把数据组

7、织成一种标准形式，使其能被数据挖掘工具和其他基于计算机的工具处理。比如对原始数据中缺少的信息进行补充；对原始数据中值域为实型的数据进行离散化。3.1.1 决策表补齐 现在，有很多方法可以对决策表中缺少的属性进行补齐，在Rough集理论中，ROUSTIDA算法是比较有效的一种。ROUSTIDA的原则是尽可能使补齐后的信息系统产生的分类规则集中，具有尽可能高的支持度。3.1.2 决策表离散化 现在，基于Rough集理论决策表离散化的研究成果有很多，其中比较适用的是Nguyen H.S.和Skowron提出的布尔逻辑和Rough集理论相结合的离散化算法。这种算法充分考虑到了Rough集理论对决策表的

8、特殊要求，采取了结合方法来解决离散化问题。它的优点是利用贪心算法来实现断点集的求取。采用任意的一种断点集，得到的新的信息表不会引入冲突。3.2 数据约简 Rough集理论在知识发现的应用中，数据约简是很重要的一个步骤。数据约简就是在保持决策表中条件属性和决策属性之间的依赖关系不变的情况下，对决策表进行数据约简，包括属性约简和值约简。3.2.1 决策表属性约简 在数据分析、数据挖掘过程中，原始信息表中条件属性具有不同的重要性，有的属性还是多余的。多余属性不仅浪费资源，而且会干扰决策的制定。决策表属性约简，就是在维持分类能力不变的情况下，删除其中不必要的或不重要的属性，从而更好的分析约简后的条件属

9、性对于决策属性的决策规则，进而发现更正确的知识和做出更准确的判断。在实际应用中，人们总是希望找出决策表的最小约简。在AI领域，求决策表的最小约简有多种算法，其中，基于区分矩阵的一般算法能较容易地计算约简和核。3.2.2 决策表值约简 对决策表进行属性约简后，还要进一步对决策表进行值约简。因为属性约简只是去掉了决策表中不必要的、冗余的属性，而值约简可以充分去掉决策表中的冗余信息，从而得到更简化的决策表。决策表值约简算法有很多，比如一般值约简算法、启发式值约简算法、基于决策矩阵的值约简算法等。我们需要根据具体情况做出合适的选择。3.3 规则生成 根据约简后得到的信息系统，对于约简结果中的每行（约简

10、后条件属性集的不可区分关系）Xi，我们可以直接得到如下形式的概率决策规则：Des（Xi） Des（Y）， if P（Y|Xi）≥βDes（Xi） Des（Y），if P（Y| Xi）≤1-β其中，Ci是规则的可信因子，在（1）式中等于P（Y| Xi），在（2）式中等于1-P（Y| Xi）。以表2为例来介绍规则的生成。表2是某信息系统的约简结果，则可以生成如下规则：（a2=7）∧（a3=7） ∧（a7=0） （d=1），（a2=7）∧（a3=7） ∧（a7=1） （d≠1），（a2=7）∧（a3=6） ∧（a7

11、=0） （d≠1），（a2=8）∧（a3=7） ∧（a7=0） （d≠1），正如在值约简部分介绍的那样，这些规则中的一些条件属性是冗余的，还需要通过值约简进行进一步的简化。采用决策矩阵的方法来进行值约简，最终可得到如下简化决策规则：（a2=7）∧（a3=7） ∧（a7=0）（d=1），（a7=1）（d=0），（a3=6）（d=0），（a2=8）（d=2）。4 总结Rough集理论在处理模糊与不精确问题时，具有很多优势，所以它被越来越多地应用在数据挖掘、知识发现等领域。我国这方面的研究相对落后，但已得到国家的大力支持，相信Rough集理论的研究及应用将对我国的人工智能发展做出新的贡献。参考文献：【1】翟俊海，王熙熙，张沧生.基于粗糙集技术