论文部分内容阅读
摘 要：Rough Set理论是一种新的处理模糊和不确定信息的数学工具。近20年来,Rough Set理论由于在知识发现等领域的成功应用而受到广泛关注,并得到飞速发展,已成为数据挖掘中的一个很重要的方法。本文讨论了Rough Set理论在数据挖掘过程中的应用,并对Rough Set理论在数据挖掘应用中存在的问题和挑战提出了自己的见解。
关键词：Rough Set理论；数据挖掘；知识发现
中图分类号：TP311文献标识码：A
The Research and Application of Rough Set Theory in Data Mining
CHEN Qin-fu，MI Gen-suo，HE Jiang-yan
(Electronic and Information Engineering College of Lanzhou Jiaotong University, Gansu Lanzhou 730070)
Key words： Rough Set theory；data mining；knowledge discovery
数据挖掘(Data Mining,DM) 就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中,提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的非平凡过程[1]。它被认为是知识发现过程中用专门算法从数据中抽取模式的一个特定步骤。知识发现过程可以概括为数据准备、数据挖掘、结果的解释和评估等几个步骤。按照数据挖掘技术所能发现的规律 ,可以将挖掘任务分成七种：分类、聚类、关联、回归、预测、序列分析、偏差分析。为了完成数据挖掘任务,常用的方法有统计分析方法、决策树方法、人工神经网络、遗传算法和粗糙集方法等。
1 Rough Set理论的概述
Rough Set[2]理论是波兰数学家Z.Pawlak于1982年提出的,它是一种新型的处理模糊和不确定性知识的数学工具,主要用来进行数据分析,尤其是对不精确和不确定的数据进行分析。其主要思想是:将知识等价为通过不可分辨关系来对论域进行分类的能力,使用上近似、下近似、成员关系等概念来对数据中的不确定性和模糊性进行逼近和分析；在保证信息系统的分类能力不变的前提下,通过知识约简,得到尽可能精简的规则。
定义1 粗糙集的定义[3]为：
给定一个有限的非空集合U称为论域，R为U上的等价关系，R将U划分为互不相交的基本等价类，二元对K= (U，R)构成一个近似空间。设X为U的一个子集，当X为某些R的基本等价类的并时，称X是R可定义的，否则X为R不可定义的。R可定义集是论域的子集，它可在K中被精确地定义，而R不可定义集不能在K中被定义。R可定义集也称为R精确集，R不可定义集也称为非精确集或R粗糙集。
定义2 知识库和不可分辨关系的定义为：
（1）知识库定义：给定一个论域U，子集X U表示U中的一个概念，U中的知识即表现为概念的族集，一个U上的分类族定义为U上的知识库，它构成了一个特定的分类。在U与R的定义下，知识库可定义为属于R中的关系对U中元素的划分，记为K=(U，R)。
（2）不可分辨关系定义：若P R且P≠Q，则∩P(P中全部等价关系的交集)也是一个等价关系，称为P上的不可分辨关系，记为ind(P):
[X]ind(p)=∩R∈P[X]R
当对于一等价关系R∈ind(K)，但X为R粗糙集，则X称为K中的粗糙集。粗糙集可以近似地定义，为达到这个目的，使用两个精确集(粗糙集的上近似集和下近似集)来描述。
定义3 上、下近似集的定义为：
假设给定知识库K=(U， R),对于每个子集X U和一个等价关系R∈ind(K)，可以根据R的基本集合的描述来划分集合X。为了精确地说明X中对象的隶属关系情况，定义两个子集：
R_(X)=U{Y∈U/R: Y X}
R-(X)=U{Y∈U/R:Y∩X≠Φ}
分别称它们为X的R下近似集和R 的上近似集。
在粗糙集理论中，对象的知识是通过指定对象的基本特征(属性)和它们的特征值(属性值)来描述的。
定义4 知识表达系统[4]定义为：
S=(U,A,{Va},a)
其中，U为非空有限集，称论域；A为非空有限集，称属性集合；Va为属性a∈A的值域；a:U→Va为一单射，使论域U中任一元素取属性a在Va中的某一唯一值。如果A由条件属性集合C和结论属性集合D组成，C、D满足C∪D＝A，C∩D＝Φ，则称S为决策系统。这种定义方式使对象的知识可以方便地以数据表格形式描述，这种数据表称为知识表达系统。
定义5 知识约简[5]与核的定义为：
令R为一等价关系族，且r∈R，当ind(R)=ind(R-{r}),称r为R中可省略的，否则r为R中不可省略的。当对于任一r∈R，若R不可省略，则族R为独立的。当Q独立，且ind(Q)=ind(P)，Q为P的简约，显然P可以有多种简约。P中所有不可省略关系的集合,称为P的核，记为core(P).
粗糙集理论在知识表达系统的基础上定义了约简与核的概念，进而提供了分析多余属性的方法，对知识的处理是通过对数据表格中的条件属性和决策属性的值进行处理来实现的。一般的处理步骤如下：（1）删除重复的实例；（2）删除多余的属性；（3）对每个实例删除多余的属性值；（4）求出最小约简；（5）根据最小约简，求出逻辑规则。
综上所述，粗糙集理论的基本框架可归纳为：以不可分辨关系划分所研究论域的知识，形成知识表达系统，利用上、下近似集逼近描述对象，通过知识约简获得最简知识。
2 Rough Set理论在数据挖掘中的应用
Rough Set理论在数据挖掘中最初的应用是分类问题。随着研究的深入,它在数据预处理方面的能力也被人们所认识。现在,Rough Set理论的适用范围已从简单的结构化数据挖掘发展到复杂类型数据的挖掘。
2.1基于Rough Set理论的分类
根据事物的特征差别将其分类是推理、学习、决策的关键。Rough Set 理论中的一些概念和方法可以用来从数据库中发现分类规则。其基本思想是：将数据库中实例根据各属性不同的属性值分成相应的子集，然后对条件属性划分的子集与决策属性划分的子集之间的上下近似关系生成分类规则。
2.2 基于Rough Set理论的规则挖掘
利用Rough Set理论进行规则挖掘是一个进行属性值约简的过程,也称规则约简。其基本方法是：通过约简操作降低属性的维数,根据可信度阀值提取出适用于决策支持的规则。
2.3基于Rough Set理论的数据预处理
计算属性集的所有约简已被证明是一个NP完全问题,而Rough Set理论借助核的概念分析属性间的依赖程度,对属性进行约简,大大降低了约简的复杂性，得到的就是一个基于属性重要性的最小约简或用户定义的最小属性集。
2.4实例
表1是某公司的职员数据库DOC(Name, Sex, Major , Education, Experience ,Salary),我们希望从中发掘工资(Salary)与其它属性的关系。根据发掘的要求,我们只需要选取有Sex, Major, Education, Experience , Salary等字段的数据：
表1
其中数据的意义及各属性的概念层次树如下:
性别Sex: 0 - 男, 1 - 女;
专业Major: 1 - 计算机, 2 - 电子工程, 0 - 其它;
学历Education: 0 - 大专, 1 - 本科, 2 - 硕士, 3- 博士;
工作经历 Experience: 0 - 0～0. 5 , 1 - 0. 5～1 ,2 - 1 年以上;
工资 Salary: 0 - 小于1000 , 1 - 1000～2000 , 2 -2000～3000 , 3 - 3000 以上
经过概念提升后,得到表2所示的数据表 (已合并重复的元组):
表2
针对表2,采用粗糙集进行分析,可知属性a是多余的,因此, 表2可以简化成表3:
表3
至此,可得7条规则,如第1,3,5条分别为:
R1:IF(Major=0)∧(Education=1)∧(Experience=1)THEN(Salary=1)
R3:IF(Major=0)∧(Education=0)∧(Experience=0)THEN(Salary=0)
R5:IF(Major=1)∧(Education=1)∧(Experience=2)THEN(Salary=2)
3 结束语
本文实例利用概念普遍化和粗糙集对数据进行压缩和维数精简的特长,达到高效挖掘感兴趣模式的目的。但它仍存在一些不足，如对模糊概念的边界区域的刻划过于简单;存在如何与关系数据库理论有机结合的问题。今后,针对Rough Set理论中高效约简算法的研究、在复杂数据挖掘和海量数据库挖掘方面的应用研究、与其他方法融合进行数据挖掘的研究将是Rough Set 理论在数据挖掘应用中的值得深入研究的方向。
参考文献：
[1]Chen Ruey-Shun ,Tzeng Gwo-Hshiung ,Chen C C,et al. Discovery of Fuzzy Sequential Patterns for Fuzzy Partitions in Quantitative Attributes[A ]. Proc of the ACS/ IEEE Int'lConf on Computer Systems and Applications[C]. 2001. 144-150.
[2]Pawlak Z. Rough sets International journal of information and computer science[J] , 1982.11 (5).
[3]曾黄麟.粗集理论及应用[M].重庆：重庆大学出版社. 1996.
[4]谢克明, 杨静.粗糙集理论及其在智能控制领域的应用前景[J].太原理工大学学报, 1999. 30 (4).
[5]常犁云等.一种基于 Rough Set理论的属性约简及规则提取方法[J].软件学报, 1999 .
关键词：Rough Set理论；数据挖掘；知识发现
中图分类号：TP311文献标识码：A
The Research and Application of Rough Set Theory in Data Mining
CHEN Qin-fu，MI Gen-suo，HE Jiang-yan
(Electronic and Information Engineering College of Lanzhou Jiaotong University, Gansu Lanzhou 730070)
Key words： Rough Set theory；data mining；knowledge discovery
数据挖掘(Data Mining,DM) 就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中,提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的非平凡过程[1]。它被认为是知识发现过程中用专门算法从数据中抽取模式的一个特定步骤。知识发现过程可以概括为数据准备、数据挖掘、结果的解释和评估等几个步骤。按照数据挖掘技术所能发现的规律 ,可以将挖掘任务分成七种：分类、聚类、关联、回归、预测、序列分析、偏差分析。为了完成数据挖掘任务,常用的方法有统计分析方法、决策树方法、人工神经网络、遗传算法和粗糙集方法等。
1 Rough Set理论的概述
Rough Set[2]理论是波兰数学家Z.Pawlak于1982年提出的,它是一种新型的处理模糊和不确定性知识的数学工具,主要用来进行数据分析,尤其是对不精确和不确定的数据进行分析。其主要思想是:将知识等价为通过不可分辨关系来对论域进行分类的能力,使用上近似、下近似、成员关系等概念来对数据中的不确定性和模糊性进行逼近和分析；在保证信息系统的分类能力不变的前提下,通过知识约简,得到尽可能精简的规则。
定义1 粗糙集的定义[3]为：
给定一个有限的非空集合U称为论域，R为U上的等价关系，R将U划分为互不相交的基本等价类，二元对K= (U，R)构成一个近似空间。设X为U的一个子集，当X为某些R的基本等价类的并时，称X是R可定义的，否则X为R不可定义的。R可定义集是论域的子集，它可在K中被精确地定义，而R不可定义集不能在K中被定义。R可定义集也称为R精确集，R不可定义集也称为非精确集或R粗糙集。
定义2 知识库和不可分辨关系的定义为：
（1）知识库定义：给定一个论域U，子集X U表示U中的一个概念，U中的知识即表现为概念的族集，一个U上的分类族定义为U上的知识库，它构成了一个特定的分类。在U与R的定义下，知识库可定义为属于R中的关系对U中元素的划分，记为K=(U，R)。
（2）不可分辨关系定义：若P R且P≠Q，则∩P(P中全部等价关系的交集)也是一个等价关系，称为P上的不可分辨关系，记为ind(P):
[X]ind(p)=∩R∈P[X]R
当对于一等价关系R∈ind(K)，但X为R粗糙集，则X称为K中的粗糙集。粗糙集可以近似地定义，为达到这个目的，使用两个精确集(粗糙集的上近似集和下近似集)来描述。
定义3 上、下近似集的定义为：
假设给定知识库K=(U， R),对于每个子集X U和一个等价关系R∈ind(K)，可以根据R的基本集合的描述来划分集合X。为了精确地说明X中对象的隶属关系情况，定义两个子集：
R_(X)=U{Y∈U/R: Y X}
R-(X)=U{Y∈U/R:Y∩X≠Φ}
分别称它们为X的R下近似集和R 的上近似集。
在粗糙集理论中，对象的知识是通过指定对象的基本特征(属性)和它们的特征值(属性值)来描述的。
定义4 知识表达系统[4]定义为：
S=(U,A,{Va},a)
其中，U为非空有限集，称论域；A为非空有限集，称属性集合；Va为属性a∈A的值域；a:U→Va为一单射，使论域U中任一元素取属性a在Va中的某一唯一值。如果A由条件属性集合C和结论属性集合D组成，C、D满足C∪D＝A，C∩D＝Φ，则称S为决策系统。这种定义方式使对象的知识可以方便地以数据表格形式描述，这种数据表称为知识表达系统。
定义5 知识约简[5]与核的定义为：
令R为一等价关系族，且r∈R，当ind(R)=ind(R-{r}),称r为R中可省略的，否则r为R中不可省略的。当对于任一r∈R，若R不可省略，则族R为独立的。当Q独立，且ind(Q)=ind(P)，Q为P的简约，显然P可以有多种简约。P中所有不可省略关系的集合,称为P的核，记为core(P).
粗糙集理论在知识表达系统的基础上定义了约简与核的概念，进而提供了分析多余属性的方法，对知识的处理是通过对数据表格中的条件属性和决策属性的值进行处理来实现的。一般的处理步骤如下：（1）删除重复的实例；（2）删除多余的属性；（3）对每个实例删除多余的属性值；（4）求出最小约简；（5）根据最小约简，求出逻辑规则。
综上所述，粗糙集理论的基本框架可归纳为：以不可分辨关系划分所研究论域的知识，形成知识表达系统，利用上、下近似集逼近描述对象，通过知识约简获得最简知识。
2 Rough Set理论在数据挖掘中的应用
Rough Set理论在数据挖掘中最初的应用是分类问题。随着研究的深入,它在数据预处理方面的能力也被人们所认识。现在,Rough Set理论的适用范围已从简单的结构化数据挖掘发展到复杂类型数据的挖掘。
2.1基于Rough Set理论的分类
根据事物的特征差别将其分类是推理、学习、决策的关键。Rough Set 理论中的一些概念和方法可以用来从数据库中发现分类规则。其基本思想是：将数据库中实例根据各属性不同的属性值分成相应的子集，然后对条件属性划分的子集与决策属性划分的子集之间的上下近似关系生成分类规则。
2.2 基于Rough Set理论的规则挖掘
利用Rough Set理论进行规则挖掘是一个进行属性值约简的过程,也称规则约简。其基本方法是：通过约简操作降低属性的维数,根据可信度阀值提取出适用于决策支持的规则。
2.3基于Rough Set理论的数据预处理
计算属性集的所有约简已被证明是一个NP完全问题,而Rough Set理论借助核的概念分析属性间的依赖程度,对属性进行约简,大大降低了约简的复杂性，得到的就是一个基于属性重要性的最小约简或用户定义的最小属性集。
2.4实例
表1是某公司的职员数据库DOC(Name, Sex, Major , Education, Experience ,Salary),我们希望从中发掘工资(Salary)与其它属性的关系。根据发掘的要求,我们只需要选取有Sex, Major, Education, Experience , Salary等字段的数据：
表1
其中数据的意义及各属性的概念层次树如下:
性别Sex: 0 - 男, 1 - 女;
专业Major: 1 - 计算机, 2 - 电子工程, 0 - 其它;
学历Education: 0 - 大专, 1 - 本科, 2 - 硕士, 3- 博士;
工作经历 Experience: 0 - 0～0. 5 , 1 - 0. 5～1 ,2 - 1 年以上;
工资 Salary: 0 - 小于1000 , 1 - 1000～2000 , 2 -2000～3000 , 3 - 3000 以上
经过概念提升后,得到表2所示的数据表 (已合并重复的元组):
表2
针对表2,采用粗糙集进行分析,可知属性a是多余的,因此, 表2可以简化成表3:
表3
至此,可得7条规则,如第1,3,5条分别为:
R1:IF(Major=0)∧(Education=1)∧(Experience=1)THEN(Salary=1)
R3:IF(Major=0)∧(Education=0)∧(Experience=0)THEN(Salary=0)
R5:IF(Major=1)∧(Education=1)∧(Experience=2)THEN(Salary=2)
3 结束语
本文实例利用概念普遍化和粗糙集对数据进行压缩和维数精简的特长,达到高效挖掘感兴趣模式的目的。但它仍存在一些不足，如对模糊概念的边界区域的刻划过于简单;存在如何与关系数据库理论有机结合的问题。今后,针对Rough Set理论中高效约简算法的研究、在复杂数据挖掘和海量数据库挖掘方面的应用研究、与其他方法融合进行数据挖掘的研究将是Rough Set 理论在数据挖掘应用中的值得深入研究的方向。
参考文献：
[1]Chen Ruey-Shun ,Tzeng Gwo-Hshiung ,Chen C C,et al. Discovery of Fuzzy Sequential Patterns for Fuzzy Partitions in Quantitative Attributes[A ]. Proc of the ACS/ IEEE Int'lConf on Computer Systems and Applications[C]. 2001. 144-150.
[2]Pawlak Z. Rough sets International journal of information and computer science[J] , 1982.11 (5).
[3]曾黄麟.粗集理论及应用[M].重庆：重庆大学出版社. 1996.
[4]谢克明, 杨静.粗糙集理论及其在智能控制领域的应用前景[J].太原理工大学学报, 1999. 30 (4).
[5]常犁云等.一种基于 Rough Set理论的属性约简及规则提取方法[J].软件学报, 1999 .