（计算机软件与理论专业论文）基于数据仓库的大规模数据集分类数据挖掘研究与设计.pdf

摘要 摘要 数据仓库是9 0 年代最受关注的发展领域之一，是旨在向决 策者、提供洁净、一致、相关数据的数据采集、管理、分析、挖 掘技术，是新一代决策支持系统的有效解决方案。数据仓库采 用统一的数据管理方式并向用户提供灵活多变的数据访问方 式，使决策者可以从不同的角度了解、掌握企业自身现状，并 对未来的发展做出预测。信息处理速度直接影响了数据仓库系 统的实用性和处理能力。我们前期完成的h d c ( h i g h w a y d e c i s i o nc e n t e r ) 系统解决了中级以下规模企事业单位的相应问 题一数据仓库重要性能参数的关键因素。大型数据仓库的处理 速度问题目前是制约其推广应用的关键所在，也是这一领域的 一个重要研究课题，也正是我们当前工作的重点：在前期研究 工作的基础上围绕提高大型数据仓库处理速度问题，建立改进 的数据仓库系统模型和相关算法，开发出面向中级以上企事业 单位的、具有数据挖掘和分析能力的大型数据仓库系统。 建立大型数据仓库所面临的关键问题，是如何妥善解决实 际业务数据的大规模、海量特征所带来的处理速度和空间等问 题，这也是当前挖掘技术研究必然面对的核心问题。广 本研究的目的是设计并实现大型数据仓库系统中的分类数 据挖掘工具一一决策树分类器，主要工作是在综合了解现有决 策树分类算法的研究情况的前提下，对决策树算法适应大规模 数据集的问题进行探讨，力求设计出能较好地适应大规模数据 的分类器算法。 论文通过对数据挖掘算法的研究，结合关系数据库和数据 仓库的知识，阐述了数据挖掘适应大规模数据处理存在的主要 问题、需解决的关键技术以及实现过程需采取的相关步骤，并 尝试了将数据挖掘中的分类器算法与成熟的关系数据库管理系 统相结合的情况。针对大数据量、多属性值的情况，对决策树 分类器所需属性信息的求解提出了新的改进算法。 ， f 。本论文的组织结构为：第一章为引言，作背景知识介绍， 阐述了数据挖掘在企业知识管理、决策支持中的定位，以及数 据挖掘的结构、分类；第二章讲述了分类数据挖掘的思路，重 点讲解了决策树分类器的构建、修剪，第三章针对大规模数据 对数据挖掘技术的影响做了讲解，提出了可采取的相应的处理 手段，以及与关系数据库、数据仓库结合的问题：第四章给出 了论文程序的框架、流程设计，以及几个关键问题的设计；第 五章对提出的设计进行简要的评述，做论文总结，并对进步 的研究进行了规划。，一a 一 关键字： 数据仓库，数据挖掘，分类器，决策树分类器，多维数据 结构，m d x 垒! ! ! ! ! ! ! 一 a b s t r a c t d a t aw a r e h o u s ei sah o tr e s e a r c ha r e ai n9 0 s 。i t sm a i nm o t i f i s t op r o v i d et h ed e c i s i o n m a k e rap o w e r f u lt o o l ：g a t h e r i n gt h ed a t a i np u r e 、c o n s i s t e n t 、r e l e v a n tp a t t e r n ，a n dm a k i n gu s eo ft h ed a t a i nm a n a g i n g 、a n a l y z i n g 、d a t a m i n i n gp u r p o s e 。t h a tm e a n st h a tt h e d e c i s i o n m a k e rc a nu s et h et o o lt ou n d e r s t a n d 、g r a s pt h es i t u a t i o n o ft h eb u s i n e s sf r o md i f f e r e n td i r e c t i o n sa n df o r e c a s tt h ef u t u r eo f i t 。w h e nu s i n gd a t aw a r e h o u s e ，t h ep r o c e s s i n gs p e e dd e t e r m i n e s d a t aw a r e h o u s e s p r a c t i c a b i l i t y a n d p r o c e s s i n ga b i l i t y 。t h e h d c ( h i g h w a y d e c i s i o nc e n t e r ) s y s t e mr e a l i z e db e f o r es o l v e s s o m e k e yp r o b l e m s a b o u ti n t e r m e d i a t es c a l e d a t a ，m a i n l y c o n c e n t r a t i n gd a t a w a r e h o u s e p e r f o r m a n c e c o e f f i c i e n t 。w h e n u s i n gh d c i n l a r g es c a l ed a t a ，i te n c o u n t e r e dp r o c e s s i n gs p e e d p r o b l e m 。t h e nt h e s e t t l e m e n to ft h i sp r o b l e mb e c o m e sam a j o r r es e a r c hp o i n t 。s o ，b a s e do nt h ef o r m e rr e s e a r c ha c h i e v e m e n t s ， t h e p r e s e n t t a s ki st oc o n s t r u c tt h er e n o w n e dd a t aw a r e h o u s e a r c h i t e c t u r ea n di t sr e l e v a n ta l g o r i t h m s ，t h e na d a p t st h es y s t e mt o t h el a r g es c a l ed a t a s e tw i t hd a t am i n i n gf u n c t i o n s 。t h i sp a p e ris ap a r to ft h er e s e a r c h 。 i no r d e rt oc o n s t r u c tt h ep o w e r f u ls y s t e m ，a k e yp r o b l e mi st o c o p e w i t ht h e p r o c e s s i n g - s p e e dp r o b l e m a n dt h ed a t a s p a c e p r o b l e m ，e t c ，c a u s e db y t h el a r g es c a l ed a t a s e ta n dm a g n i f i c e n t d a t a s e t 。t h i si sa l s ot h ec o r ei nt h ep r e s e n td a t am i n i n gr e s e a r c h 。 t h i sp a p e r sm o t i v ei st od e s i g na n dr e a l i z ead e c i s i o n t r e e c l a s s i f i e ri nt h ed a t aw a r e h o u s es y s t e mf o rl a r g e - s c a l ed a t a s e t 。 i nt h i sp a p e r ，b a s e do nt h ec o m p r e h e n s i o no ft h ec u r r e n tr e s e a r c h s i t u a t i o n ，w em a i n l yd i s c u s s e dt h ep r o b l e mh o wt o a d a p t t h e d e c i s i o nt r e ei nc o m m o nu s et ot h el a r g es c a l ed a t a s e t t h i sp a p e rf i r s ti l l u s t r a t e ds o m et y p i c a l a l g o r i t h m sf o rl a r g e d a t a s e t ，t h e ng a v eo f fap r o c e s s i n g d i a g r a mi n c o m m o nu s e 。 3 s e c o n d ，f o rt h ed a t a s e tw i t hl a r g eq u a n t i t ya n dm a n ya t t r i b u t e s ， w er e n o v a t e dt h ec a l c u l a t i o nm e t h o do ft h e a t t r i b u t e ss t a t i s t i c i n f o r m a t i o n ，g i v i n go f f aa m e l i o r a t e da l g o r i t h m 。 t h ist h e s i sc o n s i s t so ff i v es e c t i o n s 。c h a p t e ro n ed e p i c t st h e 。 b a c k g r o u n dk n o w l e d g e a n di l l u s t r a t e st h ep o s i t i o no fd a t am i n i n g a m o n gm a n yc o n c e p t s 。a l s oh e r ei s t h ed a t am i n i n g sc a t e g o r y 。 c h a p t e rt w o d e s c r i b e st h et h o u g h to fc l a s s i f i c a t i o nd a t am i n i n g t e c h n i q u e ，p u t sf o r w a r dt h ec o n s t r u c t i o na n dp r u n i n ga l g o r i t h m s o fd e c i s i o nt r e ec l a s s i f i e r 。c h a p t e rt h r e ed i s c u s s e st h ep r o b l e m s o fa d a p t i n gd a t am i n i n gt e c h n i q u ew i t hl a r g es c a l ed a t a s e t ，a n d d e m o n s t r a t e ss o m ef e a s i b l ep r o c e s ss t e p s 。a 1 s oh e r ew et o u c h e s u p o nt h ec o m b i n a t i o nr d b m s 、d a t aw a r e h o u s e 。c h a p t e rf o u ris t h ed e s i g no ft h ep r o g r a ma n ds o m er e s u l t 。c h a p t e rf i v eg i v e st h e a n n o t a t i o n 、t h ec o n c l u s i o n ，a n dt h e a r r a n g e m e n t o ff u t u r e r e s e a r c h 。 k e y w o r d s ： d a t aw a r e h o u s e ，d a t am i n i n g ，c l a s s i f i c a t i o n ，d e c i s i o nt r e e c l a s s i f i e r m u l t i d i m e n s i o na r c h i t e c t u r e ，m d x 4 图例索0 图例索引 图1 ：知识管理框架 图咆：知识发现( k d d ) 流程图 图3 ：数据仓库系统结构图 图4 ：a v c 二维表 图5 ：多维数据上的o l a p 操作 图6 ：传统关系数据库存储定单信息的结构 图7 ：多维数据结构的数据集关系图示例 图8 ：决策树分类器程序操作流程 图9 ：( 时间 下半年 ) 元组 图10 ：( 时间【下半年】，路线非陆地航空) 元组 图1 1 ：决策树分类器模块组织结构 图1 2 ：决策树设计体系架构 h 挖 ” 甜 ” 船 舶 ” 粥 埘 算法索0 算法索引 算法1 、自顶至下建树方法2 8 算法2 ：m d l 修剪算法形式描述3 3 算法3 ：r e l i e f - f 算法形式描述35 算法4 ：e s t 。g i n i l r 的算法描述4 1 算法5 ：基于概略式属性统计表阵列的混合建树算法描述5 9 公式索0 公式索引 公式( 1 ) ：熵的定义2 9 公式( 2 ) ：属性a t t 的熵定义2 9 公式( 3 ) ：信息增益3 0 公式( 4 ) ：g ir l i 指数3 0 公式( 5 ) ：属性a t t 的g i n i 指数3 0 公式( 6 ) ：c 。l 。的求解3 1 公式( 7 ) ：数据集d 进行编码的代价3 2 公式( 8 ) ：( 7 ) 与熵的关联3 2 公式( 9 ) ：权重的调解3 5 公式( 1 0 ) ：两条记录属性值间的距离公式3 5 公式q d ：一条记录属性值未知时的距离公式3 6 公式：两条记录的相应属性值都不知时的距离公式3 6 公式0 3 ) ：g i n i 。的求解公式4 0 公式( 1 4 ) ：连续属性a 在点v t 处的g i n i d 的求解公式4 0 公式a 5 ) ：g i n i d 沿x 的梯度变化的求解公式4 0 公式0 6 ) ：数据段【v i ，v 。 上的g i n i 值下界求解公式4 1 第一章0 吉 第一章 引言 随着信息技术及其相关技术的快速发展，从大量的数据源中 提取可用于制定管理、生产、市场等相关策略的信息显得越来 越重要。 1 1 研究背景 数据分析本身已经有很多年的历史，早期的数据收集和分析 的目的仅限于科学研究，同时由于计算能力的局限，致使以大 数据量数据为对象的复杂数据分析方法的实现和应用受到很大 限制。现在，由于各行业数据库及业务计算机系统的实现，产 生了大量的业务数据，这些数据最初不是为了分析的目的而收 集的，而是在商业运作过程中逐步积累的历史数据。分析这些 数据的目的也由科学研究转为为企业等的相关决策提供支持信 息。而在这一方面目前所面临的主要问题是：积累的历史数据 越来越多，从中提取有价值信息的难度也随之越来越大。因此， 从大量的数据中经过深层分析，挖掘出有利于企业运作、提高 竞争力的信息就显得非常迫切，作为解决该问题的强有力工具， 数据仓库与数据挖掘技术的研究和应用受到了越来越多的关 注。 最初数据仓库、数据挖掘是作为两种不同的技术出现的。但 随着应用的逐步推广、企业降低应用复杂度的要求和处理大量 形形色色的业务数据的应用需求的增长，二者结合得越来越紧， 形成了相辅相成的关系：数据仓库作为数据挖掘算法的数据源 提供者，能够对数据进行抽取、清洗和转化，降低无用数据的 含量，减轻噪声对数据挖掘算法的影响，保证数据挖掘算法能 够得到充足的规范化数据，提高预测精度；而数据挖掘技术为 数据仓库提供了处理复杂问题的能力和更深层次的应用。 本课题的主要研究内容，是在课题组前期研制的大型数据仓 库平台基础上作为其数据挖掘工具集中的分类挖掘工具，研制 出对于大规模数据有较强处理能力的分类器。 1 2 兰二兰型兰 一 1 2 数据仓库与数据挖掘技术研究进展 1 2 1 知识管理框架及知识发现 图l 是早期研究人员为解决将知识与实际的工作流程相结 合而创立的知识管理框架，给出了企业获取知识、利用知识的 一般结构。当前有关智能应用的许多研究大都没有脱出该结构， 但研究的深度却非当初所能企及，其中的一个方向便是人工智 能的发展。 在知识管理框架中，数据的存在形式是多种多样的，可以是 文档资料、图片展示、多媒体文件等等。如上所述，这些数据 往往是企业在长期的业务或生产等过程中积累起来的大量的历 史数据。在传统的方式中，人们利用对历史数据进行简单的转 换、图形展示进行辅助决策。但是，随着计算机尤其是数据库 和网络在企业生产、市场营销、管理等过程中的广泛应用，加 之大规模存储介质能性价格比的急剧提升，致使历史数据库的 积累快速增加。由于这类数据不仅数量巨大，而且结构更趋复 杂。在数据库的情况下，表现为汜录字段多，记录字段的域值 大，数据量高达g 级甚至t 级。这使得单纯地依靠简单的转换、 图形展示等处理手段来辅助决策变得非常困难。知识自动提取 是这一问题的一个有效的解决方案，而这也正是知识发现【j 2 。 。7 j ( k d d ：k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 、数据挖掘( d a t a m i n i n g ) 的研究范畴。 第一审引告 图1 ：知识管理框架 1 2 2 知识发现与数据挖掘 知识发现与数据挖掘是人工智能、机器学习与数据库技术相 结合的信息处理技术。 知识发现是从数据中发现有用知识的整个过程。根据1 9 9 6 年f a y y a d 、p i a t e t s k y s h a p i r o r 和s m y t h 3 对知识发现的定义， k d d 过程为：从数据中鉴别出有效模式的非平凡( n o n t r i v i a l ) 过程，该模式是新的、可能有用的和最终可理解的。 知识发现是一个多步骤的过程，一般来说其总体过程如图2 所示。其中主要步骤为： 墨二至：! ! 童 r 1 e = = 1 一 图2 ：知识发现流程图 i 、确定知识发现的目的或主题 包括理勰应用域，相关的以前的知识和终端用户的要求等； 2 、数据筛选： 按照步骤1 中的理解，从历史数据中确定此次知识发现的源 数据( 通常，源数据历史数据) ，并对源数据进行必要的处理， 如数据清洗、数据转换、数据切片等等。 该步骤的工作可交给数据仓库相应的功能模块来完成。 3 、预处理： 为提高知识发现工具对大数据量数据的处理能力，往往对给 定的数据进行特定的预处理，如将大数据集进行纵向、横向的 划分，或采用采样的方法形成规模较小的数据集，然后分别交 籀一章0 i 高 挖掘模块处理：为减少数据中的冗余数据而采取的特征提取 等等。 4 、数据挖掘： 数据挖掘是知识发现的核心。根据用户的要求，选择合适的 数据挖掘算法，基于提交的数据进行数据挖掘模型的创建。 5 、评价、解释： 为降低单纯依靠数据挖掘模型的结果安排操作的风险，必须 将基于挖掘模型的结果与实际的情况进行对比，以对数据挖掘 模型进行解释、评估；而且，随着时间的推移，以前的模型是 否还适用于当前的情况，是一个必须给出评价的问题。 如上所述，在图2 中数据挖掘是知识发现的核心步骤，是 采用机器学习、统计等方法进行知识学习以发现知识的阶段。 数据挖掘算法的好坏将直接影响到所发现知识的好坏。目前， 相当多的研究都是围绕数据挖掘算法和应用开展的。 数据挖掘一词首次出现在19 8 9 年举行的第1 1 届国际联合人 工智能学术会议上。迄今为止，由美国人工智能协会主办的k d d 国际研讨会已经召开了7 次，规模由原来的专题讨论会发展到国 际学术大会，研究重点也逐渐从发现方法转向系统应用，并且注 重多种发现策略和技术的集成，以及多种学科之间的相互渗透。 其他内容的专题会议也把数据挖掘和知识发现列为重要议题之 一。该方向已经成为当前计算机科学界的热点之。 目前，数据挖掘涉及的学科领域和方法很多，有多种分类法 【1 2 3 8 、4 叭。根据挖掘任务，可分为分类或预测模型发现、数据 总结、聚类、关联规则发现、序列模式发现、依赖关系或依赖 模型发现、异常和趋势发现等等；根据挖掘对象，可分为基于关系 数据库、面向对象数据库、空间数据库等多种数据库，以及基 于w e b 的数据挖掘；根据挖掘方法，可分为机器学习方法、统计 方法、神经网络方法和数据库方法等。 墨二至型童 当前，国外对数据挖掘的研究及其发展的主要趋势为：对知 识发现方法研究的进一步发展，如近年来注重对b a y e s 方法以 及b o o s t i n g 方法的研究和提高；传统的统计学回归法在k d d 中的应用；k d d 与数据库、数据仓库的紧密结合等。在应用方 面目前更加注重建立解决问题的整体系统，而不是孤立的过程。 国外很多计算机或软件公司也非常重视数据仓库与数据挖掘的 开发应用，i b m 、和微软等都成立了相应的研究中心进行相关 研究工作。 数据挖掘的任务是从数据发现模式( p a t t e r n s ) 。 设f e 和f 为两个数据集合，且f ef ，e 为语言l 的一个 表达式，用来描述数据集f e 中的事实，若表达式e 比f e 中所 有事实的枚举更简单，则称e 是一个模式。例如，”如果成绩在 8 1 9 0 之间，则成绩优良”为一个表达式，由于它较之”如果成 绩为8 1 、8 2 、8 3 、8 4 、8 5 、8 6 、8 7 、8 8 、8 9 或9 0 ，则成绩优 良”简单，所以该表达式是一个模式。 模式有很多种，在实际应用中，往往根据模式的实际作用将 其细分为以下6 种： 1 、分类模式 分类模式是一个分类函数( 分类器) ，能够把数据集中的数 据项映射到某个给定的类上。作为一种常用的结构，分类模式 可表现为一棵分类树，不同的叶结点分别表示一个类别。当数 据给定时，根据数据的值，从树根开始沿着其标定条件被数据 所满足的分支往下走，最后到达的叶结点所表示的类别，即为 给定数据所属类别。 2 、回归模式 回归模式的函数定义与分类模式相似，它们的差别在于分 类模式的预测值是离散的，回归模式的预测值是连续的。例如， 给出某种动物的特征，可以用分类模式判定这种动物是否哺乳 动物；给出某个人的接受教育情况、从事专业、工作经验，可 1 7 笙二塞 ! 堕 以用回归模式判定这个人的年工资在哪个范围内，是在6 0 0 0 元 以下，还是在6 0 0 0 元到1 万元之间，还是在1 万元以上的某个 值。 3 、时间序列模式 时间序列模式根据数据随时间变化的趋势预测将来的某项 指标值。例如对顾客多次购物行为进行分析可以发现，如果某 顾客先后买了过滤油和发动机油，那么以后他还会买汽油。 4 、聚类模式 聚类模式是把属于个大数据集中的数据划分到不同的子 集一一组中，属于不同组的数据之间的差别尽可能大，组内数 据的差别尽可能小。与分类模式不同，进行聚类前并不知道整 个数据集合将要被划分成几个组和什么样的组，即不知道数据 的分类信息；也不知道根据哪一( 几) 个数据项来定义组。一 般来说，相关业务知识丰富的人应该可以理解划分出的组的含 义，如果产生的模式使得组的划分无法理解或不可用，则该模 式可能是无意义的，需要回到上阶段重新组织数据。 5 、关联模式 关联模式是数据项之间的关联规则。”在无力偿还贷款的人 当中，6 0 的人的月收入在3 0 0 0 元以下”是一条关联规则的例 子。 6 、序列模式 序列模式与关联模式相仿，但前者把数据之间的关联性与时 间相联系。为了发现序列模式，不仅需要知道事件是否发生， 而且需要确定事件发生的时间。例如，在购买彩电的人们当中， 6 0 的人会在3 个月内购买影碟机。 在解决实际问题时，经常要同时使用多种模式。一般来说， 分类模式和回归模式是使用最普遍的模式。 在上述模式中，分类模式、回归模式、时间序列模式被认 为是受监督知识，因为在建立模式前数据的结果是已知的，可 以直接用来检测模式的准确性，模式的产生是在受监督的情况 下进行的。一般在建立这些模式时，使用部分数据作为样本。 1 用另一部分数据来检验、校正模式。聚类模式、关联模式、序 列模式则是非监督知识，因为在模式建立前结果是未知的，模 式的产生不受任何已知数据类别的限制。 数据挖掘涉及的学科领域和方法很多，有多种分类法【4 。 1 、根据挖掘的任务可分为分类或预测模型发现、数据总结、 聚类、关联规则发现、序列模式发现、依赖关系或依赖模型发 现、异常和趋势发现等等： 2 、根据挖掘的对象分有关系数据库、面向对象数据库、空 间数据库、时态数据库、文本数据源、多媒体数据库、异质数 据库、遗产数据库以及环球网w e b ； 3 、根据挖掘的方法可分为：机器学习方法、统计方法、神 经网络方法和数据库方法。 ( 1 ) 、机器学习包括归纳学习方法( 决策树、规则归纳等) 、基 于范例学习、遗传算法等； ( 2 ) 、统计方法包括回归分析( 多元回归、自回归等) 、判别分 析( 贝叶斯判别、费歇尔判别、非参数判别等) 、聚类分析( 系统 聚类、动态聚类等) 、探索性分析( 主元分析法、相关分析法等) 等； ( 3 ) 、神经网络方法中，可分为：前向神经网络( b p 算法等) 、 自组织神经网络( 自组织特征映射、竞争学习等1 等； ( 4 ) 、数据库方法主要是多维数据分析或o l a p ( o n l i n e a n a l y t i c a lp r o c e s s i n g ) 方法；另外还有面向属性的归纳 方法等。 在上面众多的数据挖掘算法中，分类数据挖掘是用的较为广 1 9 第一章引高 泛的5 、10 1 。 1 2 3 数据仓库 传统的数据库技术是以单一的数据资源，即数据库为中心， 进行事务处理、批处理、决策分析等各种数据处理工作，主要 的划分为两大类：操作型处理和分析型处理( 或信息型处理) 。 操作型处理也叫事务处理( o l t p ：o n l i n e t r a n s a c t i o n a l p r o c e s s i n g ) ，是指对数据库联机的日常操作，通常是对一个或 一组纪录的查询和修改，主要为企业的特定应用服务的，注重 响应时间，数据的安全性和完整性；分析型处理o l a p 则用于 管理人员的决策分析，经常要访问大量的历史数据。而传统数 据库系统优于企业的日常事务处理工作，而难于实现对数据分 析处理要求，已经无法满足数据处理多样化的要求。操作型处 理和分析型处理的分离成为必然。 随着数据库技术的应用和发展，人们尝试对数据库中的数 据进行再加工，形成一个综合的，面向分析的环境，以更好支 持决策分析，从而形成了数据仓库技术。 业界公认的数据仓库概念创始人w h n m o n 在建立数据 仓库一书中对数据仓库的定义是： “数据仓库就是面向主题的、集成的、不可更新的( 稳定性) 、 随时间不断变化( 不同时间) 的数据集合，用以支持经营管理 中的决策制定过程、数据仓库中的数据面向主题，与传统数据 库面向应用相对应”。 数据仓库是9 0 年代最受关注的发展领域之一，是旨在向决 策者提供洁净、一致、相关数据的数据采集、管理、分析、挖 掘技术。根据其工作过程可分为数据的抽取、存储和管理、数 据的表现及面向决策支持的数据分析、查询等四个方面f 2 3 - 2 4 2 5 2 6 、4 3 1 。 数据的抽取是数据进入仓库的过程。由于数据仓库是一个独 立的数据环境，它需要通过抽取过程将数据从联机事务处理系 2 0 笙= 主! i 童 统、外部数据源、脱机的数据存储介质等数据源中导入到数据 仓库。 数据的存储和管理是数据仓库的主要功能之一。而大量数据 的存储和管理是数据仓库研究的一项重要课题。数据仓库所涉 及的数据量往往比传统事务处理大得多，且随时间的推移因不 断累积而增长。从现有技术和产品来看，关系数据库系统经过 近3 0 年的发展，在数据存储和管理方面已经非常成熟，较之其 它数据管理系统有其优势。目前不少关系数据库系统已支持数 据分割技术，能够将一个大的关系表分散在多个物理存储设备 中，从而增强了系统管理大数据量的扩展能力。目前，采用关 系数据库管理数百个g b 甚至到t b 的数据已成为可能。 数据仓库支持多维分析的查询模式。用户在使用数据仓库时 的访问方式与传统的关系数据库有很大的不同，往往不是简单 的表和记录的查询，而是基于用户业务的分析模式，即联机分 析( o l a p ：o n l i n ea n a l y t i c a lp r o c e s s i n g ) 。其特点是将数据 想象成多维的立方体，用户的查询便相当于在其中的某些维上 施加条件，对立方体进行切片、分割、旋转，得到的结果则是 数值的矩阵或向量。这种多维分析的查询功能关系数据库本身 没有提供。为此，人们提出了多维数据库的概念。多维数据库 是一种以多维数据存储形式来组织数据的数据管理系统。 在数据仓库中，面向决策支持的数据分析、查询服务至关重 要。目前，数据仓库该方面功能的实现主要来自数据仓库软件 产品的供应商，如何使数据仓库具备对多维度数据操作的能力， 是提高关系数据库联机分析处理能力的关键。 1 3 基于数据仓库的数据挖掘 综上所述，建立数据仓库过程中的数据采集、数据存储与管 理、数据表现等的方法研究基本成熟，而目前需深入研究的问 题侧重于数据仓库技术与领域的进步结合、数据仓库在大规 模数据存储与处理性能上的不断提高、数据仓库与数据挖掘技 术的有机结合等。 2 1 第一帝引言 数据仓库弥补了原有的数据库的缺点，将原来的以单一数 据库为中心的数据环境发展为一种新环境一体系化环境。相应 的数据仓库系统体系结构示意如图3 。 图3 ：数据仓库系统结构图 图3 的数据仓库系统结构中数据仓库平台的引入，抹平了由 于异源数据带来的应用系统整体设计的难题，集成了方便用户 使用的诸多技术，而且使专注于数据挖掘算法研究的人员可以 第一币引言 在统的平台上精，0 研究算法的特性。 第二章分类数据挖掘及其铂大规模数据上的扩展 第二章分类数据挖掘及其在大规模数据上的扩展 2 1 分类数据挖掘 分类数据挖掘也称作分类分析，一般可描述如下： 给定一数据集t ( 称为训练集，t r a i n i n gs e t ，通常该数据 集都是某一应用领域的，满足该领域的数据分布的规律) 及其 属性集合a ，a 中的元素x 称为t 的属性。x 可为离散 ( c a t e g o r i c a l 或d i s c r e t e ) 属性或连续( n u m e r i c 或c o n t i n u o u s ) 属性。在t 的属性中，存在一个称为类别标示的离散属性c ( c t a s sl a b e l ) ，用于标示t 中记录的类别： c = c 1 ，c2 ，c t ，k 表示类别的个数。 为便于叙述，将a 一 c 记作x ，并用向量表示如下： x = k ，x ：，z 。j ，即t 除类别标示之外有n 个属性。 将属性一工( 1 i n ) 的值域记作d o m ( x ，) ，则 d o m ( x ，) = 扛。x ，x 。 ，m 为x ，的值域d o m ( x ，) 所包含元素的个 数。 则其中的一条记录t 可写作t = 。 这样，训练集丁隐含地确定了个从z 到c 的函数h ： h ) 一c 。 分类分析的目的就是采用合适的手段将函数h 拟合出来； 之后用该拟合函数对新的记录进行类别的判断。通常我们把拟 合函数称为分类器( c l a s s i f i e r ) 。 在实际应用中，拟合隐含函数h 的方法有多种，目前较为 常见的有贝叶斯网络分类器( b a y e s i a nn e t w o r kc l a s s i f i e r ) 、 d s g e n e t i ca l g o r i t h m ) 、决策树分类器( d e c i s i o nt r e ec l a s s i f i e r ) 等等。在这些分类器模型中，决策树分类器由于具有下述优点 而受到更多的关注： 鹤二审分娄数据挖掘及扎神：大规模数槲f ：的于r 展 _ - _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ - - _ _ - _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ - - _ _ _ _ 、与n e u r a ln e t w o r k 或b a y e s i a nc l a s s i f i e r 相比，更易被 用户理解、诠释； 、决策树算法与n e u r a ln e t w o r k 相比，生成效率更高 且更适合于大数据集的应用： 、与其它技术相比，决策树与贝叶斯网络分类器的预测 准确度一般较高。 尽管决策树分类器较之于其它模型更适合于大数据集，但 随着时间的推移，大数据集( 1 a r g ed a t a s e t ) 的概念也在不断的 改变：在九十年代，若数百万条记录的数据量也可算作大规模 数据量的话，现在则至少增至数g 以上。显然，决策树分类器 在这方面的能力也必须随之增强。针对这一问题，本研究旨在 给出提高决策树分类器处理大规模数据集能力的解决方案，并 在此基础上实现基于大型数据仓库的决策树分类器。 2 2 决策树分类器 2 2 1 决策树的概念 决策树【1 5 1 6 、1 8 1 是一种有向、无环图( d a g ：d i r e c t e d 、 a c y c l i cg r a p h ) 。树的根节点没有输入边( i n c o m i n ge d g e ) ； 所有其它节点即可以有输入边，也可以有输出边。如果一个节 点没有输出边，则称之为叶节点( 1 e a fn o d e ) 。 构建决策树分类器实际上就是生成一棵决策树。由于最优 决策树的生成是n p 问题，所以在实际应用中通常是利用不同 的策略构建次优决策树。由于决策树生成的过程就是对数据集 的分割过程，所以策略通常是指分割选择策略，常简记为c l ， 即根据数据的分布特征对数据进行划分的方法。现有的决策树 分割选择策略大部分采用了信息熵( e n t r o p y ) 的概念，如信息 增益、g i n i 等。决策树的修建阶段也同样需要构建次优决策树 策略，其中最常采用的是m d l 修剪方法。 常见的决策树结构有二叉树和非二叉树( 多叉树) ，为了 叙述方便，本文仅对二叉树( b i n a r yt r e e ) 结构进行描述。但 笙三里坌叁墼塑丝塑丝! ! 垄盔丝塑塑塑! ：塑芝鉴 论文中的些主要观点可以延伸至多叉树。另外，根据文献【5 】、 1o 等，利用二叉树构建的决策树分类器其数据分类具有较高 的准确度。 决策树中除叶节点外喑勺任意节点( 以下简称内部节点) i n 都有一个分割属性s a ，。( s p l i t t i n ga t t r i b u t e ) 以及相应的分割谓 词s p 。( s p l i t t i n gp r e d i c a t e ) 。所谓分割属性，就是在建树过 程中生成一个内部节点时，根据分割选择策略为将数据集分割 开来所选定的属性。而分割谓词则是指分割属性的取值。根据 分割属性的性质一一连续性或离散性，分割谓词分别称作分割 点( s p l i t t i n g p o i n tf o rn u m e r i c a la t t r i b u t e ) 和分割子集 ( s p l i t t i n gs u b s e tf o rc a t e g o r i c a la t t r i b u t e ) ： 如果s a i n 为连续属性，则s p i n 的形式为x 。x 其中 x 。d o m ( x 。，) ，称为节点i n 的分割点； 而若s a i n 为离散属性，s p i n 的形式为爿。匕，其中 l 2 “”) ，即匕为所有s a i n 的值的幂集中的一个元素。l ，称 为该节点i n 的分割子集。 通常，将节点i n 上的分割属性和分割值合称作该节点的分 割标准。 给定数据集t 。首先，将t 在决策树根节点处分割为两个 子集( n 叉树的情况下分割为n 个子集) ，分别使之进入根节 点的两个子节点( 内部节点) 。进入到内部节点i n 处等待处 理的数据集，根据此节点的分割标准被分割为不同的子集，继 续进入到i n 节点的不同的子节点。将这一过程迭加，直至根 据分割标准，任一所至节点处的子集都不能再分割为止。从决 策树的根节点到某一节点的路径上的所有节点的分割标准就 组成一组判断条件。如果一组分割条件是由从根节点到某一叶 节点的路径上的所有分割标准组成的，那么称这组分割条件为 该决策树分类器的一条判断规则。 节点n 对应的数据集f n ( f a m i l yo ft u p l e s ) 是指将训练集 塑三兰竺茎墼塑丝塑圣! ! 垫：! ：型篓墼堡! ：竺翌竺 数据按照从根节点到该节点的判断规则进行划分而进入到该 节点的数据集( 给定数据集的一个子集) ： c l e f、 f 。= f t ：厂( f ) = t r u e上且e ct ， 其中，t 为数据集t 的一条记录； 函数f ( t ) 为满足从根节点至该节点n 的判断规则的集合； 在上面数据集的迭代分割过程中，所谓“所至节点处的子 集不能再分割”，是指每个叶节点对应的数据集要么由于数据 记录太少不满足进一步分割的条件，要么节点对应的数据集中 的数据都属于同一类别。每一个叶节点标识对应着训练集类别 c 中的一个值c i ，这意味着在给定的数据集t 中，属于类别c i 的数据在且只在该叶节点对应的子集中。 另外，分类器tr 的分类错误率r t ，( m i s c l a s s i f i c a t i o nr a t e ) 定义如下： 尸( d ( ( f x ”，f x 。) ) f c ) 即：按该分类器对测试数据确定的类别不等于实际数据的 相应类别的统计概率。 决策树分类问题( d e c i s i o nt r e ec l a s s i f i c a t i o np r o b l e m ) 描 述如下： 给定一数据集t ，t = h f ：，l 。 ，其中t 满足分布规律p ， r ，( 1 f ) 是在t 中的独立随机抽样，那么，决策树分类就 是用决策树来构建分类器t r ，使得分类错误率 ( m i s c l a s s i f i c a t i o nr a t e ) r t ，( p ) 最小。 近年来，国际上分类分析的研究取得了长足的发展，该领 域的研究者提出了许多决策树分类器的构建算法，如i d 3 i 4 引、 c 4 5 4 5 】、s l i q 1 2 1 、s p r i n t l ”1 、b o a t 16 1 、c m p 4 引、s c a i p a r c 18 1 、 c l o u d s 1 5 1 、r a i n f o r e s t 1 4 1 、p u b l i c 2 2 1 等等。除p u b l i c 等 少数几个算法外，大多数的算法都将决策树的构建分成两个明 笙三兰坌茎塾堡篓堡垒墨塑：查型堡垫堡：= ! 三堕翌= 鉴 确的步骤：建树阶段( t r e eb u i l d i n g 或c o n s t r u c t i o n 、o r o w i n g p h a s e ) 和修剪阶段( p r u n i n gp h a s e ) 。 2 2 2 决策树的构建 决策树的构建是在建树阶段完成的。 在建树阶段，训练集被递归分割。分割终止的判定条件为： 被测试分割的子集中的所有记录都属于同一个类，或节点对应 的数据集的数据量太少，进一步分割已无实际意义。对应于每 一次数据集的分割，都会在决策树上产生一个新的节点。初始 时，决策树只有一个根节点对应于整个数据集；在对节点对应 的数据集d 进行分割时，首先根据分割选择策略c l 找到最好 的分割标准t ，之后用t 将d 分割成d 1 ，d 2 ，与d 对应的节 点填入分割信息，与d l ，d 2 对应的新节点就成为d 节点的子 节点。然后递归地对各个节点进行分割，直至分割终止。 建树阶段算法描述如下： i n p u t ：节点n ，与n 对应的待分割的数据集d ，分割选择策略 c l o u t p u t ：以u 为根节点的对应于d 的决策树 t d t r e e ( n ，