（计算机软件与理论专业论文）基于粗糙集的多维数据挖掘的研究与应用.pdf

中山大学硕士学位论文 基于粗糙集的多维数据挖掘的研究与应川 论文题目：基于粗糙集的多维数据挖掘的研究与应用 专业：计算机软件与理论 硕士生：李舒萍 指导老师：高集荣 摘要 随着数据仓库技术和o l a p 技术的发，人们提出了联机分析处理和数据挖掘 技术集成的多维挖掘技术。多维数据挖掘能使得用户能够选择相关数据的任何部 分，在不同的层次上分析数据。本论文结合粗糙集与决策树技术的研究多维数据 挖掘方法。 面对决策树技术和粗糙集各自的优缺点，在研究过程中将这两者结合起来取 长补短。对于仅有离散值属性的情况下，利用粗糙集理论对数据集进行属性约简。 本文提出了一种基于信息熵的属性约简算法。该算法很大程度上改进了属性约简 的效率。在此基础上本文提出基于粗糙集和决策树技术结合的数据挖掘算法。该 算法大大减小了决策树的规模从而使数据挖掘的效率有所提高。 最后本文利用结合粗糙集和决策树技术的数据挖掘算法设计了一个多维数 据挖掘系统，并实现了这个基于s q ls e r v e ra n a l y s i ss e r v e r 开发的多维数据挖掘系 统。 关键字：多维数据挖掘，粗糙集，决策树技术，信息熵 基于粗糙集的多维数据挖掘的研究与应用 巾山大学硕士学位论文 t i t l e ：t h er e s e a r c ha n da p p l i c a t i o no f m u l t i - d i m e n s i o n a ld a t am i n i n gb a s e do n r o u g hs e t m a j o r ：c o m p m e rs o f t w a r ea n dt h e o r y n a m e ：s h u p i n gl i s u p e r v i s o r ：j i r o n gg a o a b s t r a c t a st h ed e v e l o p m e n to f d a t aw a r e h o u s et e c h n o l o g ya n do l a pt e c h n o l o g y ，p e o p l e p r o p o s e dm u l t i d i m e n s i o n a ld a t am i n i n gt e c h n o l o g yw h i c h w a si n t e g r a t e db yo l a p t e c h n o l o g ya n dt h ed a t am i n i n gt e c h n o l o g y m u l t i d i m e n s i o n a ld a t am i n i n g e a r l e n a b l et h eu s e r st oc h o o s et h ed a t a 丘o ma n yp a r to ft h ed a t as e t ，s ot h eu s e r sc a n a n a l y z et h ed a t ai nt h ed i f f e r e n tl e v e l s t h i sp a p e ru n i o n sr o u g h s e ta n dd e c i s i o nt r e e t e c h n o l o g yt or e s e a r c hm u l t i - d i m e n s i o n a ld a t am i n i n g t h er o u g hs e ta n dd e c i s i o nt r e et e c h n o l o g yb o t hh a v em e r i ta n ds h o r t c o m i n g ，s o w es t u d yw i t ht h et w ot e c h n o l o g i e s w h e nt h ed a t as e to n l yh a sd i s c r e t ev a l u e a t t r i b u t e ，w ec a nu s er o u g hs e tt e c h n o l o g yt op r o c e s st h ea t t r i b u t er e d u c t i o n t h i s p a p e rp r o p o s e s a na t t r i b u t er e d u c t i o n a l g o r i t h m b a s e do nt h ei n f o r m a t i o n e n t r o p y t h i sa l g o r i t h me n h a n c e st h ee f f i c i e n c yo f a t t r i b u t er e d u c t i o n b a s e do nt h e a t t r i b u t er e d u c t i o na l g o r i t h m ，t h ed a t am i n i n ga l g o r i t h mw h i c hu n i o n sr o u g hs e ta n d d e c i s i o n ：t r e et e c h n o l o g yi sp r o p o s e d t h i sa l g o r i t h mr e d u c e st h es c a l eo f t h ed e c i s i o n t r e ea n de n h a n c et h ee f f i c i e n c yo f d a t am i n i n g f i n a l l yu s i n gt h ed a t am i n i n ga l g o r a h mw h i c h u n i o n sr o u g hs e ta n dd e c i s i o nt r e e t e c h n o l o g y ，t h i sp a p e rh a sd e s i g n e da n dd e v e l o p e dam u l t i - d i m e n s i o n a ld a t am i n i n g s y s t e m w ed e v e l o pt h es y s t e mb a s e do ns q b s e r v e ra n a l y s i ss e e v e r k e y w o r d ：m u l t i d i m e n s i o n a ld a t am i n i n g ，r o u g hs e t ，d e c i s i o nt r e e ，i n f o r m a t i o ne n t r o p y i i 中山大学硕士学位论文基于粗糙集的多维数据挖掘的研究与应用 引言 随着现代信息技术的迅猛发展，全球掀起了信息化浪潮。信息产生的渠道越 来越多，信息更新的频率日益加快，各行各业均产生了数以亿计的数据库。用户 需要从大量的业务数据中探索业务活动的规律性、市场的运作趋势，并从中得到 市场竞争所需的决策信息。但利用关系数据库中的数据进行决策分析时往往会产 生许多麻烦，所查询的数据信息不是缺乏分析能力，就是因各信息系统之间相互 隔离、结构各异，使信息分析及决策人员不能据此对某一主题的相关数据进行多 角度的比较、分析，得出科学的分析结果。随着需求的变化发展，一种新的信息 处理技术数据仓库技术应运而生。数据仓库】将来自各个数据库的信息进 行集成，从事务的历史和发展的角度来组织和存储数据，供用户进行数据分析， 并辅助决策。对数据仓库中数据分析的方法主要有o l a p 联机分析的方法、数据 挖掘。 o l a p 联机分析i0 1 是指对以多维形式组织起来的数据采取切片、切块、旋转 等各种分析，以求剖析数据，使最终用户能从多个角度、多侧面地观察数据库中 的数据，从而深入地了解包含在数据中的信息、内涵。 数据挖掘【2 3 “是从数据中发现隐含着的有用的信息或知识的技术，它是随 着人类进入信息社会对信息的价值认识不断提高而不断发展的，是为满足和解决 当前“数据太多，信息不足”的技术。简单的说，数据挖掘是一个利用分析工具 从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取出隐含在其中、 事先未知、但又潜在有用的信息和知识的过程，建立数据间关系模型，并用其做 出预测。 数据挖掘是各种方法的相互交叉、渗透和协作。数据挖掘的方法主要有：神 经网络方法、遗传算法、决策树方法、粗糙集方法、覆盖正例排斥反例方法、统 计分析方法、模糊集方法。 随着数据仓库技术和o l a p 技术的发展，人们提出了联机分析处理和数据挖 掘技术集成的多维挖掘技术。多维数据挖掘【1 】能使得用户能够选择相关数据的任 何部分，能够在不同的层次上分析数据。 基于粗糙集的多维数据挖掘的研究与应用中山大学硕士学位沦文 本文的组织 本论文重点研究基于粗糙集的多维数据挖掘。通过研究粗糙集理论以及信息 熵，本论文提出结合粗糙集和决策树技术的数据挖掘方法，提高了多维数据挖掘 的效率和效果。下面简单介绍一下本文的内容安排： 第一章：介绍了多维数据集的相关概念、数据挖掘的相关知识以及粗糙集的 主要概念和定理。 第二章：介绍知识与信息熵方面的理论知识，并在此基础上提出了基于信息 熵的属性约简的算法。接下来对该算法进行分析。 第三章：简单介绍决策树技术，并说明把粗糙集与决策树技术结合的原因 和优点以及阐述了粗糙集与决策树技术结合的新的挖掘的算法的流程。 第四章：介绍设计多维数据挖掘系统的原因、系统设计的目标以及系统的设 计的实现。 第五章：对本论文的工作进行总结以及对后期工作的展望。 中山大学硕士学位论文基于粗糙集的多维数据挖掘的研究与应用 第1 章综述 1 1o l a p 多维数据集的基本概念 数据仓库中存储海量数据，这些面向主题的、集成的、随时间变化的、非易 失的数据用于支持管理决策。数据仓库从多维的、逻辑的角度展示数据，因而又 形成多维数据库或多维数据集。 ( 1 ) 维 维f l 】是人们观察数据的特定角度。例如，企业常常关心产品销售数据随着时 间推移而产生的变化情况，这时他是从时间的角度来观察产品的销售，所以时间 就是一个维。企业也时常关心自己的产品在不同地区的销售情况，这时他是从地 理分布的角度来观察产品的销售，所以地理分布也是一个维。 ( 2 ) 维的层次 数据的某个维还可以存在细节程度不同的多个描述方面，称为维的层次”1 。 一个维往往具有多个层次，例如描述时间维时，可以从日期、月份、季度、年等 不同层次来描述。 ( 3 ) 维成员 维的一个取值称为该维的一个维成员”。如果一个维是多层次的，那么该维 的维成员是在不同维层次的取值的组合。例如，时问维具有日期、月份、年这三 个层次，分别在日期、月份、年上各取一个值组合起来，就得到了时问维的一个 维成员，即“某年某月某日”。 ( 4 ) 数据单元 多维数组的取值称为数据单元。当多维数组的各个维都选中一个维成员， 这些维成员的组合就唯一确定一个变量的值。那么数据单元就可以表示为：f 维l 维成员、维2 维成员、维n 维成员，变量的值) 。例如，在地区、时间和 销售渠道上各取维成员“北京”、“1 9 9 7 年1 月”和“批发”，就唯一确定了变 量“销售额”的一个值( 假设为 o o o ) ，则该数据单元可表示为：( 北京、1 9 9 7 年1 月、批发、1 0 0 0 1 。 ( 5 ) 度量 基于粗糙集的多维数据挖掘的研究与应用中山大学硕士论文 度量是数据的实际意义，即描述数据的一个量值。一般情况下，它总是一 些数值度量指标，例如：“人数”、“单价”、“销售额”等。 ( 6 ) 多维分析 多维分析【1 1 是指对以多维形式组织起来的数据采取切片、切块、旋转等各种 分析，以求剖析数据，使最终用户能从多个角度、多侧面地观察数据库中的数据， 从而深入地了解包含在数据中的信息、内涵。 数据切片：多维数据集中数据的一个子集，由维度的成员限制一个或多个维 度来指定。例如，特定年份的事实数据构成多年数据的一个切片。 数据切块：将完整的数据立方体切取一部分数据而得到的新的数据立方体。 数据钻取：从较高的维度层次下降到较低的维度层次上的多维数据。 数据聚合：也就是钻取的逆向操作，是对数据进行高层次综合的操作。 数据旋转：改变维度的位置关系，使得最终用户可以从其他视角来观察多维 数据。 1 2 数据挖掘概念 数据挖掘是从数据中发现隐含着的有用的信息或知识的技术，它是随着人类 进入信息社会对信息的价值认识不断提高而不断发展的，是为满足和解决当“数 据太多，信息不足”的技术。简单的说，数据挖掘是一个利用分析工具从大量不 完全的、有噪声的、模糊的、随机的数据中，提取出隐含在其中、事先未知、但 又潜在有用的信息和知识的过程，建立数据间关系模型，并用其做出预测。与传 统信息处理方法相比，数据挖掘技术有其自身的特点【2 3 l ： 1 ) 处理对象为大规模数据库，数据规模十分巨大： 2 ) 信息查询一般是由决策制定者( 用户) 提出的即时随机查询，往往没有精 确的查询要求，需要靠数据挖掘技术寻找其可能感兴趣的东西； 3 ) 在现实的一些应用中，某些行动并没有实际发生或很少发生，因而它 们对输出所造成的影响还没有在数据库中体现出来，此时就需要利用 数据挖掘技术从数据库中提取有用的规则，为这种情况提出预测； 4 ) 在一些应用中，由于数据的变化迅速，可能导致数据很快过时，因此 要求数据挖掘技术能快速对数据变化做出反应以提供决策支持。数据 4 中山大学硕士学位论文 基于租糙集的多维数据挖掘的研究与应用 挖掘既要发现潜在的规则，还要管理和维护规则。而规则是动态的， 当前的规则只能反应当前状态的数据库特征，随着新数据的不断加入， 规则需要随之更新； 5 ) 数据挖掘中规则的发现主要基于大样本的统计规律，发现的规则不必 适用所有的数据，当达到某一阀值时便可认为有这个规律。 与数据挖掘关系密切的研究领域包括归纳学习( i n d u c t i v el e a r n i n g ) 、机器学 ( m a c h i n el e a r n i n g ) 和统计( s t a t i s t i c s ) 分析，特别是机器学习被认为和数据挖掘 的关系最密切。二者的主要区别在于：数据挖掘的任务是发现可以理解的知识， 而机器学习关心的是提高系统的性能，因此训练神经网络来控制一根倒立棒是一 种机器学习过程但不是数据挖掘；数据挖掘的对象是大型的数据库，一般来说机 器学习处理的数据集要小得多，因此效率问题对数据挖掘是至关重要的。 1 3 数据挖掘过程 数据挖掘是指一个完整的过程，该过程从大型数据库中挖掘先前未知的，有 效的，可实用的信息，并使用这些信息做出决策或丰富知识。其过程 2 1 如图1 1 所示 卜数据准备卜数据挖掘 一结果表选 一 图1 1 描述了数据挖掘的基本过程和主要步骤 1 3 1 确定业务对象与主题分析 清晰地定义出业务问题，认清数据挖掘的目的是数据挖掘的重要一步。开始 真正的数据挖掘之前最先也是最重要的就是了解用户的数据和业务问题。有效的 问题定义还应该包含一个对数据挖掘的结果进行衡量的标准。 在确定用户的需求后，应对现有资源如己有的历史数据进行评估，进一步确 慕于粗糙集的多维数据挖掘的研究与应用 中山大学硕士论文 定数据挖掘的目标和制定数据挖掘计划。数据是数据挖掘工作成败的基础，因此， 分析主题的任务包括对数据进行进一步的理解，如确定数据挖掘所需要的具体数 据，对数据进行描述，检查数据的质量等。 1 3 2 数据准备 数据挖掘所处理的数据集通常不仅有海量数据，而且可能存在大量的噪声数 据、冗余数据、稀疏数据或不完全数据等解决数据的应用质量问题是数据挖掘 的基础。数据准备包括数据抽取、清洗、转换和加载，具体包含数据的清洗、集 成、选择、变换、规约，以及数据的质量分析等步骤。 1 3 3 数据挖掘 对所得到的经过转换的数据进行挖掘。根据数据功能的类型和和数据的特点 选择相应的算法( 如汇总、分类、回归、聚类等) ，在净化和转换过的数据集上进 行数据挖掘。数据挖掘算法的好坏将直接影响到所发现知识的好坏。 1 3 4 结果分析和验证 数据挖掘发现的模式应是新的、可能有用的和最终可理解的。因此，需要对 数据挖掘的结果进行解释和评价，解释某个发现的模式，去掉多余的不切题意的 模式，转换某个有用的模式，成为能够最终被用户理解的知识。 评估的方法一种是直接使用原先建立的挖掘数据库中的数据来进行校验，也 可以另找新的测试数据并对其进行检验。另一种方法是使用实际运行环境中的当 前数据进行检验。检验的目的是对整个数据挖掘过程的前面步骤进行评估，确定 是发布模型还是对数据挖掘过程进行调整，重复挖掘过程。 1 3 5 知识的同化 数据挖掘的目的是为了应用，因此我们需要将数据挖掘中发现的知识集成到 业务信息系统的组织结构中去，并在业务系统中进一步验证这些知识，用预先、 可信的知识检查和解决知识中可能的矛盾。 6 中山大学硕士学位论文 基于粗糙集的多维数据挖掘的研究与应用 1 4 粗糙集理论基础知识 r o u g hs e t s 理论是由波兰华沙理工大学p a w l a k 【6 ，7 1 教授于1 9 8 2 年提出一种数 据分析理论，主要研究不完整、不确定知识和数据的表达、学习和归纳的方法， 近年来受到国际上的众多学者的重视。其主要思想是在保持分类能力不变的前提 下，提出知识约简，导出问题的决策和分类规则。目前，粗糙集理论已被成功地 应用于机器学习、决策分析、过程控制、模式识别和数据挖掘等领域。本章主要 介绍粗糙集理论的相关概念，其中包括知识和知识库嗍、不可分辨关系 6 1 2 , 1 3 1 、 上下近似集 6 , 1 0 1 、约简和核【6 1 以及知识的依赖性陋瞎。 1 4 1 知识和知识库 设非空集u 是我们感兴趣的对象组成的有限集合，称为论域。任何子x c _ u ， 称为u 中的一个概念或范畴。为规范化起见，我们认为空集也是一个概念。u 中 的任何概念族称为关于u 的抽象知识，简称知识；u 上的一族划分称为关于u 的 一个知识库。 设r 是u 上的一个等价关系，u r 表示r 的所有等价类( 或者u 上的分类) 构成 的集合，【) ( 】r 表示包含元素x u 的r 等价类。一个知识库就是一个关系系统k = ( u ，r ) ，其中u 为非空有限集，称为论域，r 是u 上的一族等价关系。 设p c r ，且p 中，则np ( p 中所有等价关系的交集) 也是一个等价关系， 称为p 上的不可区分关系5 1 ，记为i n d ( p ) ，且有【x 】删p ) = 忿【x k ，这样，u i n d ( p ) 表示与等价关系族p 相关的知识，称为k 中关于u 的p 基本知识，为简单起见，我 们用u p 代替u i n d ( p ) ，i n d ( p ) 的等价类称为知识p 的基本概念或基本范畴，特别 地，如果q r ，则称q 为k 中关于u 的q 初等知识，q 的等价类为知识r 的q 初等 概念或q 初等范畴。事实上，p 基本范畴是拥有知识p 的论域的基本特征。换句话 说，它们是知识的基本模块。同样，我们可以定义：当k = ( u ，r ) 为一个知识库， i n d ( ：k ) 定义为k 中所有等价关系的族，记i n d ( k ) = i n d ( p ) l m p 月) 。 下面我们讨论两个知识库之间的关系，令k = ( u ，p ) 和k = ( u ，q ) 为两个知识 库。若i n d ( p ) ；i n d ( q ) ，l i p u p = u q ，则称k 和k i ( p 和q ) 是等价的。因此，当k 和k t 基于 ! i 糙集的多维数据挖掘的研究与应用中山大学硕士论文 有同样的基本范畴集时，知识库k 和k 中的知识都能使我们确切的表达关于论域 的完全相同的事实。 对于k = ( u ，p ) 和k = ( u ，q ) 两个知识库，当i n d ( p ) c i n d ( q ) 时，我们称知识p ( 知 识库k ) 比知识q 知识库k ) 更精细，或者说q 比p 更粗糙。当p 比q 更精细时，我们 也称p 为q 的特化，q 为p 的推广。这意味着，推广是将某些范畴组合在一起，而 特化则是将范畴分割成更小的单元。 1 4 2 粗糙集的定义 粗糙集理论将用于分类的知识嵌入到集合内，作为集合的一个组成部分，根 据现有的知识判断，一个对象a 是否属于集合x 有三种情况：1 1 对象a 肯定属于x ： 2 1 对象a 肯定不属于集合x ；3 1 对象a 可能属于也可能不属于集合x 。由此出现了粗 糙集中最重要的两个概念：下近似( l o w e ra p p r o x i m a t i o n ) 和上近似( u p p e r a p p r o x i m a t i o r l l 。 设xcu 是一组对象，对于一个等价关系r ，b 1 r cc 是一组条件属性，则 x 相对于r 的下近似、上近似可表示为： 一r x = x u r | 【x 】r x ) 公式卜1 砑= j u r f 【j 】r n x 中 公式i - 2 通过以上概念可知，r x 是指由那些根据知识r 判断肯定属于x 的u 中的元素 组成的集合；r x 是指那些根据知识r 判断可能属于x 的u 中的元素组成的集合。 由上近似和下近似，可以定义正域( p o s i t i v er e g i o n ) 、负域( n e g a t i v er e g i o n ) 和边界域( b o u n d a r yr e g i o n ) 的概念。 正域：集合x 相对于r 的正区域就是x 的下近似，即：p o s r ( d ) = 负域：集合x 相对于r 的负区域是n e g r ( x ) = u r x 边界域：集合x 相对于r 的边界域是b n d r ( x ) = r x 一型 边界域中的元素是可能属于也可能不属于x 的元素组成的集合，如果边界域 为空，则称集合x 是关于r 的精确集；反之，则称集合x 是关于r 的粗糙集( r o u g h s e t ) 。 r 中山大学硕十学位论文基于靼糙集的多维数据挖掘的研究与席用 1 4 3 知识的简化：约简 在工程应用中，我们经常要在保持知识库中初等范畴的情况下消去冗余基本 范畴，进行知识的简化。完成知识简化的基本工作是利用两个基本概念：约简 ( r e d u c t i o m 、核( c o r e ) 来进行的。首先做如下定义： 定义( 省略和不省略) ：设一等价关系为属性集合r c _ c ，属性r c - r ，当i n d ( r ) = i n d ( r f r ) ，称r 为r 中可省略的，否, j j r 为r 中不可省略的。 定义r 独立1 ：对任- - r e r ，若r 不可省略，则r 为独立的。属性是可省略的意 味着属性去掉后不影响分类的结果，因此可以计算属性与集合间的依赖程度。 定义( 依赖) ：设一等价关系为属性集合r c ，对于属性d 以依赖度7 r ( d ) 依 赖于s 中a 的子集p ，若k = y r ( d ) = c a r d ( p o s p ( d ) ) c a r d ( p o s a ( d ) ) ，决策属性和条件 属性有内在的联系，即决策属性对条件属性的依赖度，k = y 。( d ) 表示在信息系 统s 中的条件属性p 下，肯定支持决策的对象个数占全部对象个数的比例。 r 定义( 属性重要性) 设属性a e c ，贝, r j a 的属性重要度可以定义为：s g f ( a ，c ， d ) = ( d ) 一，。( d ) ，s gf ( a ，c ，d ) 表明从c 中去掉a 后对分类决策的影响 程度，有了这些概念后，就可以定义核( c o r e ) 和约简( r e d u c t i o n ) 的概念。 定义( 核) c 中所有不可省略属性的集合称为c 的核，即：c o f e ( d ) = n r ed ( d ) 核这个概念有两方面的作用，首先它可以做为所有约简的计算基础，因为核 包括在所有的约简之中，并且计算可以直接进行；其次它可以解释为：当知识化 简时它是不能消去的知识特征部分的集合。下面举例说明上述概念。 例2 2 表2 2 包含p ，q ，r 三个条件属性和一个决策属性d 表格1 1 某信息决策表 up q rd x 1ool0 x 2 1 00l x 3ll2o x 4o2ll x 510o1 9 基于粗糙集的多维数据挖掘的研究与应用i n 山大学硕士沦文 u d = ( ( x l ，x 3 x 2 ，x 4 ，x 5 ) ) u p = “x l ，x 4 ， x 2 ，x 3 ，x 5 ) ) u q = “x l ，x 2 ，x 5 ， x 3 ， x 4 ) u r = x l ，x 4 ， x 2 ，x 5 ， x 3 ) ) 所以得到 p o s p ( d 、2 中 p o s r ( d ) = x 3 ，x 4 p o s 0 ( d ) 2 ) ( 2 ，) 【3 ，x 5 ) p o s ( p ，q 】( d ) 。 ) ( 2 ，x 5 ，x l ，x 3 ，x 4 p o s ( p , r ) ( d ) = x 2 ，x 5 ，x 3 p o s ( q , r ) ( d ) 2 x 2 ，x 5 ，x l ，x 3 ，x a p o s ( p , q ，r ) ( d ) 2 x 2 ，x 5 ，x l ，x 3 ，x 4 因为p o s l q ) ( d ) = p o s ( q r ) ( d ) = p o s ( p , q , r ) ( d ) ，所以 p ，q ) 和 q ，r ) 是该信息系 统的约简，进一步c o r e ( d ) =