RoughSet理论在数据挖掘中的应用

JournalofHengyangNormalUniversityNo.3Vol.26Jun.2005

RoughSet理论在数据挖掘中的应用

旷海兰,罗

1,2

可,王

1

樱

2

(1.长沙理工大学计算机与通信工程学院,湖南长沙󰀁410076;

2.衡阳师范学院计算机系,湖南衡阳󰀁421008)

摘󰀁要:RoughSet理论是一种新的处理模糊和不确定信息的数学工具。近20年来,RoughSet理论由于在知识发现等领域的成功应用而受到广泛关注,并得到飞速发展,已成为数据挖掘中的一个很重要的方法。作者讨论了RoughSet理论在数据挖掘过程中的应用,并对RoughSet理论在数据挖掘应用中存在的问题和挑战提出了自己的见解。

关键词:RoughSet理论;数据挖掘;知识发现中图分类号:TP18

文献标识码:A

文章编号:1673󰀁0313(2005)03󰀁0081󰀁04

具,主要用来进行数据分析,尤其是对不精确和不确定的数据进行分析。其主要思想是:将知识等价为通过不可分辨关系来对论域进行分类的能力,使用上、下近似、成员关系等概念来对数据中的不确定性和模糊性进行逼近和分析;在保证信息系统的分类能力不变的前提下,通过知识约简,得到尽可能精简的规则[5]。以下给出RoughSet理论中的基本概念[6,7]:

定义1󰀁

信息系统S=(U,A,V,F)

U为论域,A为属性集,V为属性的值域,F为U和A的关系集。如果A=C󰀁D,且C󰀁D=󰀁,则称信息系统为一个决策系统(或决策表),其中C为条件属性集,D为决策属性集。

定义2󰀁

等价关系。在信息系统中,对于任何一个属性

集合PU,等价关系用IND表示:

IND(P)={(x,y)󰀁U󰀁U|f(x,a)=f(y,a),a󰀁P}即对于属性集P中的任意一个属性a,如果实例x和实例y对于属性a的取值都是相同的,我们称实例x和y对于属性集P是等价的,或称实例x和y对于属性集P是不可分辨的。

定义3󰀁下近似aprX=󰀁{x|[x]RX}={x󰀁U|[x]RX}

上近似aprX=󰀁{x|[x]R󰀁X󰀁󰀁}={x󰀁U|[x]R󰀁X󰀁󰀁}

1󰀁数据挖掘的概述

数据挖掘又称数据库知识发现(KDD),它是󰀁从数据集中识别出有效的、新颖的、潜在有用的、以及最终可理解的模式的非平凡过程󰀁[1],是近年来随着人工智能和数据库技术的发展而出现的一门较新兴的技术。知识发现包括数据预处理、数据挖掘、模式评估和知识表示等几个步骤。按照数据挖掘技术所能发现的规则,可以将挖掘任务分成5种。总结规则挖掘:从指定的数据中,从不同的角度或层次上挖掘出平均值/极小值/极大值、总和、百分比等;关联规则挖掘󰀁󰀁󰀁从数据库中挖掘出满足一定条件的依赖性关系;分类规则挖掘󰀁󰀁󰀁在已知训练集的特征和分类结果的基础上,为每一种类别找到一个合理的描述或模型;聚类规则挖掘󰀁󰀁󰀁客观地按被处理对象的特征分类,将有相同特征的对象归为一类;预测及趋势性规则挖掘󰀁󰀁󰀁对数据进行分类或回归分析,或对数据将来的发展趋势进行估计。为了完成数据挖掘任务,常用的方法有统计分析方法、决策树方法、人工神经网络、遗传算法和粗糙集方法等[2~

4]

。

2󰀁RoughSet理论的概述

20世纪80年代,波兰的Pawlak教授提出了RoughSet理论,这是一种新型的处理模糊和不确定性知识的数学工

收稿日期:2004󰀁10󰀁28

基金项目:湖南省教育厅资助项目(04C075)

作者简介:旷海兰(1976󰀁),女,湖南衡阳人,衡阳师范学院计算机系讲师,硕士,从事数据挖掘,粗糙理论及应用研究󰀁82󰀁

衡阳师范学院学报2005年第26卷

X的上近似是根据知󰀁󰀁其中[x]R是x所在的R等价类。

识R判断肯定属于X的U中元素组成的集合,X的下近似是那些根据知识判断可能属于X的U中元素组成的集合。apr当X=aprX时,称X是可定义的;X是不可定义的当且仅当aprX󰀁aprX,此时称X是粗糙集。

定义4󰀁

近似精度󰀁A(X)=|aprX|反映了根据现有

aprX|

程度从大到小逐个加入属性,直到集合是一个约简或满足用户要求为止。

󰀁检查该集合中每一个元素,看移走某一属性是否会改变集合对决策属性的依赖度,如果不影响则将该属性删除。

这样得到的就是一个基于属性重要性的最小约简,或用户定义的最小属性集。

根据对属性重要性的分类,可以将约简算法分为基于正区域的、基于分辨矩阵的和基于信息熵的三种。A.Skowron提出的基于分辨矩阵计算约简的步骤为:

󰀁计算信息系统的分辨矩阵M(S)󰀁计算与M(S)对应的区分函数fM(S)

󰀁计算fM(S)的最小析取范式,其中每个合取分量对应一个约简。

在以上算法的基础上,研究者们又提出了很多高效实用的算法[8,9,10]。但这些算法都只能对完备的信息系统进行约简,而在利用RoughSet理论对不完备信息系统进行约简前,必须先将信息系统完备化[11,12],而对包含连续属性的信息系统进行约简前也要先对连续值进行离散化[13]。

3󰀁2󰀁

基于RoughSet理论的规则挖掘

利用RoughSet理论进行规则挖掘是一个进行属性值约简的过程,也称规则约简。其基本方法是:通过约简操作降低属性的维数,根据可信度阀值提取出适用于决策支持的规则。粗糙集方法生成规则的一般步骤为:

󰀁进行元组的约简,删除重复实例;󰀁进行属性的约简,删除多余的属性;󰀁对每个实例删除多余的属性;󰀁求出最小约简;

󰀁根据最小约简找出最小规则集。

全局覆盖算法LEM算法以覆盖和下边界为主要工具,将论域按决策属性集D划分为D*=(D1,D2,󰀁,Dv),寻找aprDi和aprDi(i󰀁v)的所有覆盖,就可以分别得出必然规则和可能规则[14]。

若该决策表是不一致的,则常用的方法是先将决策表分成两个一致的子表。或者采用如下的方法:

󰀁计算决策表条件属性的核值,即把该行中一个条件属性的值从表中删除,然后看根据该行中剩下的条件属性的值所得到的决策值的集合与未删除前所得到的决策属性值的集合是否相同,若不是,这个值就是核值。

󰀁求条件属性值的约简,即将一些条件属性值加入到核值中,保证得到的决策属性值的集合与原来的决策属性值的集合相同,并且每个条件属性值都不可省。

对于数据量大、存在数据缺失或噪声干扰时,传统RoughSet模型与程序的结果可能不理想。所以,一些改进型、扩展型的方法被提出:如在RoughSet基础上进行多层次、逐步求精的规则挖掘,基于可变精度模型的规则挖掘、基于RoughSet的决策树规则挖掘等[9,15-18]。

知识对X的了解程度,其中|X|为集合X的基数。

粗糙度󰀁A(X)=1-󰀁A(X)表示集合X的知识的不完全程度。此外,利用上近似和下近似可以计算得到分类精度,用来表示可能的决策中正确决策的百分比。

定义5󰀁

约简设(U,A,V,F)为信息系统,其中U为有

限对象集,BA是(U,A,V,F)的约简,是指RB=RA,且对任意b󰀁B都有RB-{b}󰀁RA。A可以有多种约简,所有约简中的必要关系组成的集合称为核。

定义6󰀁

分辨矩阵信息系统中条件属性集C的分辨矩

阵M(C)=(mij)n󰀁n定义为mij=

󰀁󰀁xixj=󰀁D的同一等价数

{c󰀁C󰀁f(xi,c)󰀁f(xj,c)}󰀁xixj󰀁D的同一等价类M(C)是一个对称矩阵,利用它可方便地计算约简和核。扩展的粗糙集模型由于传统的粗糙集模型中的等价关系对于实际应用太苛刻,且没有考虑到数据噪声和数据缺失等情况,所以,许多RoughSet理论研究者就利用模态逻辑和概率统计信息,对原有的理论进行了扩展,使其应用的范围更广泛。提出了变精度粗糙集模型、概率粗糙集模型、模糊粗糙集模型、容差关系模型等。

RoughSet理论被广泛地应用于处理不确定的和模糊的信息,是由于它具有这样几方面的优点:󰀁仅利用数据本身所提供的信息,不需要数据集合之外的任何先验知识,具有一定的客观性;󰀁可以从不同的抽象层次来对数据进行建模和分析,以更好地揭示数据间的依赖关系,发现数据间的规律。󰀁产生的规则简洁准确、易于验证。此外,由于现在数据挖掘的对象多为关系数据库,而关系表可以看作RoughSet理论中的决策表,所以RoughSet方法已成为数据挖掘中越来越重要的一种方法。

3󰀁RoughSet理论在数据挖掘中的应用

RoughSet理论在数据挖掘中最初的应用是分类,之后,随着研究的深入,它在数据预处理方面的能力被人们所认识。现在,RoughSet理论的适用范围已从简单的结构化数据挖掘发展到复杂类型数据的挖掘。

3󰀁1󰀁基于RoughSet理论的数据预处理

计算属性集的所有约简已被证明是一个NP完全问题,而RoughSet理论借助核的概念分析属性间的依赖程度,对属性进行约简,大大降低了约简的复杂性。启发式属性约简算法步骤为:

󰀁从核或一个用户指定的约简出发,按照属性的重要2005年第3期

3󰀁3󰀁基于RoughSet理论的分类

旷海兰等:RoughSet理论在数据挖掘中的应用

83󰀁

上所具有的优势,将RoughSet理论与其它人工智能方法相结合能提高对数据处理的能力。与模糊数学相结合能更好地处理不完全知识;与遗传算法相结合可以降低优化的复杂度;与SVM相结合进行数据预处理可提高预测精度;与神经网络的结合可提高神经网络分类器的分类精度和分类能力[24-26]。多方法的结合是数据挖掘当前和今后研究的热点。

根据事物的特征差别将其分类是推理、学习、决策的关键。RoughSet理论中的一些概念和方法可以用来从数据库中发现分类规则。其基本思想是:将数据库中实例根据各属性不同的属性值分成相应的子集,然后,对条件属性划分的子集与决策属性划分的子集之间的上下近似关系生成分类规则。

目前基于RoughSet理论的分类方法很多。如采取自下而上的搜索策略,从空属性集出发进行分层挖掘,可以有效地去除噪声[19];将求所有对象的覆盖化为求各个决策类的覆盖,使挖掘出的分类规则的条件部分具有最小的描述长度的方法,可以对不相容决策表进行分类[20];借助扩张矩阵可以有效地从信息表中获取精简的分类规则[21];可以利用分辨矩阵对属性值进行约简,得到泛化的分类规则,并利用决策属性的基本集关于条件属性的上下近似来判断所挖掘分类规则的确定性[22]。此外,RoughSet理论也可以和基于案例分析(CBR)结合进行分类。

3󰀁4󰀁复杂数据挖掘

对复杂数据的挖掘主要是指对时间序列、空间数据、文本信息、WEB数据和多媒体数据等进行挖掘。

RoughSet理论处理的数据往往不依赖于时间,为使粗糙集方法能够应用于时间序列的挖掘,必须对表示的时间信息系统进行转换,使之成为粗糙集方法适用的信息系统方式。

空间数据挖掘需要综合数据挖掘与空间数据库技术,对空间数据库中非显示存在的知识、空间关系或其它有意义的模式等进行提取。在空间数据挖掘中,利用粗糙集可以分析空间数据库中的属性重要性、属性不确定性、属性表和属性依赖,发现数据中的范式及因果关系,生成最小决策和分类算法,指导不确定影像分类、模糊边界划分、地价评估和空间表达等。RoughSet理论已被用于分辨不精确的空间影像和面向目标的影像评估,实现空间数据清理中的数据转换,用于基于属性不确定性的银行粗选址,从数据库中发现不确定属性的知识[23]。

同样利用粗糙集的上、下近似集及其近似精度的理论,可以进行Web网页挖掘和文本挖掘。Web挖掘与传统的数据挖掘相比有很多独特之处。首先,Web挖掘的对象是大量、异质、分布的Web文档。其次,Web在逻辑上是一个由文档结点和超链构成的图,因此Web挖掘所得到的模式可能是关于Web内容的,也可能是关于Web结构的。此外,由于Web文档本身是半结构化或无结构的,且缺乏机器可理解的语义,而数据挖掘应用比较成功的对象是数据库中的结构化数据。因此要使数据挖掘技术适用于Web挖掘,就必须对Web文档进行预处理。如建立用户兴趣树并对该树进行约简,实现搜索引擎的智能搜索,使呈献在用户面前的网页页面尽量准确。

5󰀁结束语

RoughSet理论作为一种有效进行数据分析的数学方法,特别是为分析数据的模糊性和不确定性提供了一系列严谨的数学工具,因而广泛应用在数据挖掘的数据预处理、分类及规则生成等方面,并取得了令人鼓舞的成果,但它仍存在一些不足,如对模糊概念的边界区域的刻划过于简单;存在如何与关系数据库理论有机结合的问题。今后,针对RoughSet理论中高效约简算法的研究、在复杂数据挖掘和海量数据库挖掘方面的应用研究、与其它方法融合进行数据挖掘的研究将是RoughSet理论在数据挖掘应用中的值得深入研究的方向。参考文献:

[1]FayyadU.,PiatetskyS.,Smyth,Uthurusamy.Advancesin

KnowledgeDiscoveryandDataMining[M].MITPress,1996.[2]HanJ.W.andKamberM.数据挖掘:概念与技术[M].

北京:机械工业出版社,2001.

[3]史忠植.知识发现[M].北京:清华大学出版社,2002.[4]罗可等.数据挖掘及其发展研究[J].计算机工程与应

用,2002,38(14):182-184.

[5]张文修,吴伟志.粗糙集理论介绍与研究综述[J].模糊

系统与数学,2000,39(4):1-12.

[6]张文修等.粗糙集理论与方法[M].北京:科学出版社,

2001.

[7]张文修等.信息系统与知识发现[M].北京:科学出版

社,2003.

[8]刘少辉等.Rough集高效算法的研究[J].计算机学报,

2003,26(5):524-529.

[9]常犁云等.一种基于RoughSet理论的属性约简及规则

提取方法[J].软件学报,1999,10(11):1206-1211.[10]邵明文等.信息系统知识约简简便算法[J].计算机科

学,2003,30(11):25-28.

[11]KryszkiewiczM.RoughSetapproachtoincomplete

informationsystems[J].112(1-4):39-49.

[12]乔斌等.针对信息系统不完备性的粗糙集递减约简

[J].电路与系统学报,2001,6(2):78-82.

[13]黄梯云等.数据挖掘中一种基于粗糙集理论的属性值

离散映射方法[J].情报学报,2002,21(4):391-396.[14]OrlowskaE,ed.IncompleteInformationRoughSetInformationScience,1998,

4󰀁目前的研究方向和研究热点

由于RoughSet理论在处理不确定性知识和模糊知识

84󰀁

衡阳师范学院学报

Analysis[M].NewYork:Physica-VerlagHeidelberg,1998

2005年第26卷

[20]安利平等.不相容决策系统中获取规则的粗糙集方法

[J].青岛大学学报,2002,17(1):53-55.

[21]赵士亮等.结合粗糙集理论与扩张矩阵理论的数据挖

掘方法[J].福州大学学报(自然科学版),2001,29(4):49-52.

[22]谢娟英,冯德明.一种基于决策表的分类规则挖掘新算

法[J].计算机科学,2003,30(10):61-63.

[23]李德仁等.论空间数据挖掘和知识发现的理论与方法

[J].武汉大学学报(信息科学版),2002,27(3):221-233.[24]Bjorvand,A.T.,Komorowski,J.:PracticalApplicationsof

GeneticAlgorithmsforEfficientReductComputation[J].Wissenschaft&TechnikVerlag,1997,4:601-606.

[25]曾黄麟,王晓.一种粗模糊神经分类器[J].中国工程科

学,2003,5(12):60-65.

[15]SonajhariaM.andRajniJ.RoughSetbasedDecision

TreeModelforClassification.[J].DaWak,LNCS2737,2003,172-181.

[16]苏健,高济.粗糙决策支持方法[J].计算机学报,2003,

26(6):727-745,

[17]ZhongN.,DongJ.Anincremental,probabilistic

roughsetapproachtorulediscovery[M].The1998IEEEinternationalconferenceonFuzzyProceedings,1998.

[18]Pawlak,Z.:DrawingConclusionsfromData-TheRough

SetWay[J].IJISW,2001,16:3-11.

[19]尹旭日,陈世福.一种基于Rough集的缺省规则挖掘算

法[J].计算机研究与发展,2000,37(12):1441-1445.

Systems

TheApplicationsofRoughSetTheorytoDataMining

KUANGHai-lan

1,2

,LUOKe,WANGYing

12

(1.ComputerandCommunicationEngineeringCollege,

ChangshaUniversityofScience&Technology,ChangshaHunan410076,China;2.ComputerDepartmentofHenyangNormalUniversity,HengyangHunan421008,China)

Abstract:Roughsettheoryisanovelmathematicaltooltransactingvaguenessanduncertainty.Inthepassed20years,RoughSettheoryhasbecomeanimportantmethodfordatamining.ThispapermainlydiscussapplicationsofRoughSettheoryindatamining.

Keywords:Roughsettheory;datamining;knowledgediscovery