（计算机应用技术专业论文）基于rough+set的海量数据挖掘算法研究.pdf

重庆邮电学院硕士论义 摘要 数据挖掘是从大量的数据中挖掘出有用的或者人们感兴趣的知识的一种方 法。处理海量数据一直是数据挖掘要解决的一个重要问题。本论文结合r o u g h s e t 理论提出了一种直接处理海量数据全集的方法，并研究了分布式处理海量 数据中的关键问题，即分割海量数据集的问题。 经典的r o u g hs e t 算法要求数据常驻内存，因此不能有效地处理海量数据。 本论文首先提出了类分布链表的结构来表示一个属性组合对样本空间的分类情 况，类分布链表可以通过使用数据库技术对原始数据集进行直接分类来获取。 通过类分布链表，本论文改进了一组r o u g hs e t 知识约简算法，从而使它们能 够直接处理海量数据集。类分布链表的方法还可以作为一种框架扩展到其它的 r o u g hs o t 算法来提高这些算法的可伸缩性，同时不影响它们的正确性。 在分布式处理海量数据中，关键的第一步就是如何有效地将原始海量数据 集分割成许多可以在单机上处理的数据子集。本论文根据r o u g hs e t 的特点提 出了最佳分割的定义，然后提出了一种海量数据分割算法来寻找最佳分割。通 过实验测试证明结合本文提出的数据分割算法的分布式处理方案能够快速地处 理海量数据，而且与处理整个数据集的算法相比，j 下确性损失不大。 关键词：数据挖掘，海量数据，r o u g hs o t ，可伸缩性，分布式处理，数据分 割 重庆邮电学院硕二l 论文 a b s t r a c t d a t am i n i n gi sa p r o c e s st oe x t r a c ti n t e r e s t i n ga n du s e f u lk n o w l e d g ef r o md a t a p r o c e s s i n gh u g ed a t as e t sh a sb e e na ni m p o r t a n tt o p i ci nd a t am i n i n g a ne f f e c t i v e r o u g h s e t b a s e dm e t h o di sd e v e l o p e di nt h i st h e s i st op r o c e s sh u g ed a t as e t sd i r e c t l y a saw h o l e a n dt h e n ，a ne f f e c t i v em e t h o do fd a t ap a r t i t i o ni nd i s t r i b u t ei n f o r m a t i o n p r o c e s s i o ni sa l s od i s c u s s e d m o s to ft h er o u g h s e t b a s e da l g o r i t h m sa r ed e s i g n e do n l yf o rm e m o r y - r e s i d e n t d a t a ，s oi ti sh a r df o rt h e s ea l g o r i t h m st od e a lw i t hh u g ed a t as e t s as t m c t u r eo f c l a s sd i s t r i b u t i o nl i s t ( c d l ) i s p r e s e n t e di nt h i st h e s i st oe x p r e s st h ed i s t r i b u t i o no f a l la t t r i b u t ev a l u e si nt h ew h o l es a m p l es p a c e w i t hd a t a b a s et e c h n o l o g y , ac d lc a n b eg e n e r a t e dv i ac l a s s i l y i n gt h eo r i g i n a ld a t as e t s t h e n ，ag r o u po fr o u g h - s e t b a s e d k n o w l e d g er e d u c t i o na l g o r i t h m sa r er e v i s e du s i n gc d l t h i sm e t h o dc a np r o c e s s h u g ed a t as e t sd i r e c t l y a saf r a m e w o r k ，c d lm e t h o dc a na l s ob eu s e di no t h e r r o u g hs e ta l g o r i t h m st oi m p r o v et h e i rs c a l a b i l i t yw i t h o u td e c r e a s i n gt h e i ra c c u r a c y w h i l ea p p l y i n gd i s t r i b u t e di n f o r m a t i o np r o c e s s i o nt od e a lw i t hh u g ed a t as e t s ， t h ef i r s ti m p o r t a n ts t e pi sp a r t i t i o n i n gt h ew h o l eh u g ed a t as e ti n t om a n ys m a l l s u b s e t s o nt h eb a s eo fd e f i n i t i o no fb e s t p a r t i t i o n ，ar o u g h s e t - b a s e dp a r t i t i o n a l g o r i t h mi sd e v e l o p e dt ol o o kf o rt h eb e s tp a r t i t i o ni nt h i st h e s i s e f f i c i e n c yo ft h e r o u g h s e t b a s e dp a r t i t i o na l g o r i t h m i s p r o v e db ys i m u l a t i o ne x p e r i m e n t s t h e d i s t r i b u t e di n f o r m a t i o np r o c e s s i o nm e t h o dp r e s e n t e di nt h i st h e s i si sf a s t e rt h a n o r i g i n a lr o u g h s e t b a s e da l g o r i t h m s ，w h i l ei t sp e r f o m l a n c ei sc l o s et ot h o s e a l g o r i t h m st h a tp r o c e s st h eo r i g i n a ld a t as e ta saw h o l e k e yw o r d s ：r o u g hs e t ，h u g ed a t as e t s ，s c a l a b i l i t y ，d i s t r i b u t e d i n f o r m a t i o n p r o c e s s i o n ，d a t ap a r t i t i o n 重庆邮电学院硕上论文 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他入已经发表或撰写过的研究成果，也不包含 为获得重庆邮电堂院或其他教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示谢意。 学位论文作者签名：贸玫仁 签字日期：动口垆年夕月多弓日 学位论文版权使用授权书 本学位论文作者完全了解莺庆邮电学院有关保留、使用学 位论文的规定，有权保留并向围家有关部门或机构送交论文的复e i y 牛 和磁盘，允许论文被查阅和借列。本人授权重庆邮电学院可以 将学位论文的全部或部分内容编入有关数据库进行榆索，町以采用影 e j j 、缩印或扫描等复制手段保存、_ 7 l 编学位论文。 ( 保密的学位沦文在解密后适用本授权书) 学位论文作者签名；嗜波仁导师签名： 签字日期：沙口垆年月2 弓目签字日期：占。年牛月2 f 日 重庆邮f b 学院硕士论文 1 1 引言 第一章绪论 智能信息处理是当前信息科学理论和应用研究中的一个热点领域，过去几 十年中人们在专家系统、知识工程、人工神经网络、模糊集合等众多领域不断 实践和探索，取得了很多很好的成绩。然而，随着信息时代的到来，特别是随 着数据库技术的不断发展及数据库管理系统的广泛应用，以及网络技术的日新 月异，人们所要处理的数据呈现出许多新的特点： ( 1 ) 数据量十分巨大，通常都超出了内存的容量。因此不能把这些数据 全部调入内存中直接处理。 ( 2 ) 要处理的数据可能是由分布在世界各地的许多子数据站点组成的 分布式数据系统。由于空间和时间上的限制、保密性以及通信费用 的考虑，要把这些空间上完全独立的数据集中起来处理通常是不太 现实。 ( 3 ) 可能随时都会有大量新数据涌现，这在网络数据中犹为明显。要把 这些新数据加入到原有的数据库中，然后对整个数据库重新进行学 习在时间上是不允许的。 问题( 1 ) 是典型的海量数据处理问题，它要求算法在数据量远大于内存容 量的情况下仍然能够很好的工作。孵决问题( 1 ) 的算法通常有串行和并行两种。 串行的算法能够在单机上直接处理，但是运算的时间通常都比较长；并行算法 处理速度比串行算法要快，但是它需要并行的计算环境，而且在处理过程中需 要频繁地交换中问数据，通信代价较为昂贵。 问题( 2 ) 是典型的分布式数据处理的问题，分布式数据挖掘能够很好的解 决这个问题。分书式数据挖掘在处理分布式数据源的时候。首先在各子数据站 点上形成局部模型然后再整合成全局的最终模型。分布式数据挖掘具有高并行 性能、处理速度快以及通信负载小等优点，但和将所有的分布式数据集中起来 统一处理的方法相比，分布式数据挖掘的f 确性要差一些。 问题( 3 ) 是一个增量式学习问题，要求能够在原有知识系统的拱础上根掘 新增的数据或者知识不断地学习和更新原有的知识系统。当新数据出现的时候， 增量式学习不再需要将新数据和原来的数据。起重新学习，这样做很好地利用 了原有的知识，符合人类学习知识的习惯。 这三个问题不是相互独立而是具有相关性的。关于使用分布式数据挖掘的 方法来研究和解决( 1 ) 中的问题在文献 1 中有讨论；关于使用增量式学习的 重庆邮电学院硕士论文 方法来研究和解决问题( 1 ) 中的问题在文献 2 中有讨论。本文主要考虑使用 r ol ，g hs e t 的思想，寻求对问题( i ) 的直接解决方案，同时研究使用分布式数 据挖掘方法来解决问题( 1 ) 时的关键问题。 1 2 粗糙集理论及应用的发展状况 粗糙集( r o u g hs e t ，粗集) 理论”1 出波兰华沙理工大学逻辑学家z p a w l a k 教授于1 9 8 2 年提出，由于它能有效地分析和处理不精确、不一致、不完整等各 种不完备信息，并从中发现隐含的知识，揭示潜在的规律，近年来在机器学习、 数据挖掘等多个领域得到广泛的应用”“。 粗糙集的研究对象是由一个多值属性( 特征、症状、特点等) 集合描述的 一个对象( 观察、病历等) 集合，对于每一个对象及其属性都有一个值作为其 描述符号，对象、属性和描述符号是表达决策问题的三个基本要素。这种表达 形式也可以看成为一个二维表格，表格的行与对象对应，列对应于对象的属性； 各行包含了表示相应对象的描述符，还有关于各个对象的类别成员的信息。通 常，关于对象的已知信息不一定足以划分其成员类别。换句话说，这种不精确 性导致了对象的不可分辨性。给定对象空间的一个等价关系，即导致由等价类 构成的近似空间的不分明关系，粗糙集就用不分明对象形成的上近似和下近似 来描述。这些近似分类对应了确定属于给定类的最大的对象集合和可能属于给 定类的最小的对象集合。下近似和上近似的差是一个边界集合，它包含了所有 不能确切判定是否属于给定类的对象。粗糙集方法可以解决重要的分类问题， 所有冗余对象和属性的约简包含属性的最小子集，能够很好地近似分类，得到 可以接受质量的分类。而且，它还可以用决策规则集合的形式表示最重要属性 和特征分类之间的所有重要关系。 粗糙集理论不仪为信息科学和认识科学提供了新的科学逻辑和研究方法， 而且为智能信息处理提供了有效的处理技术。从诞生到现在虽然只有十几年的 时间，但己在许多领域取得了令人鼓舞的成果。 目前，国际上己经开发出了许多纂丁粗糙集理论的知识获取系统，并已取 得了非常丰厚的收益，例如：加拿大r e g i n a 大学利用粗糙集理论开发的水资源 渊度系统”3 ，使人们通过对水资源的合理调配，大大降低了水资源浪费：r 本 岛根医科大学津本周作( s h u s a k at s u m o t o ) 教授领导开发了f 床医疗诊断系统， 可以根据症状判断病症；p o e l 和p i a s t a 开发一个分析潜在客户应用系统可用 于客户分析。我国在粗糙集领域的研究起步较晚，但发展很快，目前我国己见 到一些应用粗糙集理论来处理不完整数据和不精确、不确定性问题的研究成果 报道。一些典型的应用如：利用粗糙集方法评选系统重要特征参数，基于不可 2 重庆邮电学院颐十论文 分辨关系进行子图分割，粗糙集理论在c b r 系统案例评定中的应用等在相应的 领域都取得了较丰硕的成果。 1 3 论文背景及工作内容 关于海量数据挖掘很早就有研究，人们首先考虑的是如何直接对整个海量 数据集进行处理。1 9 9 i 年c a r l e t t 提出了一种r a n d o ms a m p l i n g ”1 的方法来处 理大数据量问题，但是能处理的最大数据量也只有3 2 0 0 0 条。1 9 9 6 年i b m a l m a d e nr e s e a r c hc e n t e r 相继提出了s l i q ”1 和s p r i n t 。1 算法，这两个决策树 算法可以直接处理驻留磁盘的数据，特别适用于处理大数据量问题，而且得到 了与经典决策树算法相当的效果。后来人们又相继提出了c l o u d s ”，s c a l p a r c 叫 等改进算法以及针对大数据量的快速决策树生成算法框架r a i n f o r e s t “， r a i n f o r e s t 在某些场合的速度和效果都超过了s p r i n t 。近年来，我国的何清、 史忠植等教授提出了一种通用的基于超曲面的直接分类方法，提出的分类超曲 面可以有效地解决在有限区域分布很复杂的海量的非线性数据分类问题，在海 量数据处理上取得了很好的效果“3 。“1 。 本论文首先考虑使用r o u g hs e t 知识约简的方法来直接处理海量数据全集。 然而传统的r o u g hs e t 算法都是内存算法，在处理海量数据上显得力不从心， 而且这些算法都没有很好的利用成熟的数据库技术。文 1 5 和 1 6 中提到的方 法表明将数据库技术与传统的分类方法相结合将会大大提高性能。本论文利用 r o u g hs e t 算法本身的特点，从全局数据集中通过数据库技术提取出能代表全 局数据集的尽量少的信息放到内存中处理或者直接提交给数据库系统处理，从 而大大减小算法对内存容量的依赖。本文结合r o u g hs e t 理论提出了一种表示 分类的结构类分布链表( c d l ) ，它可以通过对原始数据集进行直接分类来 获得，在处理数据的每一步只需要考虑相应的c d l 即可，不需要将整个数据集 放到内存中处理。根据c d l ，我们提出了综合离散化、属性约简和值约简三个 部分的可伸缩性解决方案，能直接处理驻留磁盘的数据。通过研究发现，本文 提出多步生成类分布链表的方法解决了内存限制问题，可以处理海量数据集。 而且，本算法提出的思想可以扩展到其它的很多r o u g hs e t 算法，从而使它们 具备良好的可伸缩性，同时不影向这些算法的正确性。 由于网络计算和网络通信技术的进步，分布式计算平台已经越来越盛行。 许多平台存储着分布式数据源和计算节点。因此如何在这些分布式数据源上挖 掘有用的知识成为一个重要的课题。为此人们提出了分布式数据挖掘 ( d is t r i b u t e dd a t am i n i n g ，即d d ) 来处理分布式数据源。d d m 在处理分布 式数据源上取得了很好的效果，它同时被认为是将来处理数据的一种趋势”。 重庆邮电学院硕士论文 c h a n p 和s t o l f os 提出了一个著名的d d m 模型：m e t a l e a r n i n g “”3 。它是 基于“合唱学习”的，并且可以生成多层次的分类器。d d m 还有许多其它的算 法，比如挖掘关联规则的c d 、d d 、i d d 和h d 算法。”1 ，以及通过计算各子站点的 权值来合并规则站点的算法“”等。通常来说，d d m 的算法与将所有的分布式数 据源合起来再处理的方法比较，正确性要低一些，但它具有高并行性能和低通 信负载，以及处理速度快等优点。因此随着人们处理的数据量的不断增大，d d m 的应用将更加广泛。 本论文也研究了利用d d m 的思想来处理经典海量数据的问题。要实现分布 式地处理海量数据全集，首先要将原始的海量数据集分割成为许多能够在单机 上快速处理的数据子集。然后在这些分布式的数据子集上使用与传统d d m 相同 的方法进行分布式处理。分割原始数据集的质量对后继分布式处理的效果有着 很深的影响，因为分割后的数据子集已经遗失了的信息在后继的分布式信息处 理中是无法弥补的。因此本文把重点放在研究如何有效地分割原始数据集上。 通过分析r o u g hs e t 本身的特点本论文提出了最佳分割的定义。根据此定义， 本文提出了一种海量数据分割算法，在考虑运算代价不要太大以及各子数据站 点负载平衡的情况下，尽量使数据分割算法趁近于最佳分割。为了验证分割算 法的有效性，本文采用了一种简约的分布式知识发现模型来进行后继的分布式 处理工作。 本沧文工作得到国家自然科学基金( n o 6 0 3 7 3 1 1 1 ) 、教育部科学技术研究 重点项目、重庆市应用基础研究基金和重庆市教委科学技术研究项目资助，是 这些项目整体研究工作中的一部分。这些项目旨在从理论上系统研究基于粗糙 集的智能数据分析技术，建立一套完善的粗糙集智能数据分析模型理论，建立 基于r o u g hs e t 表示、度量、和处理不确定性信息和知识的理论系统；在r o u g h s e t 理论研究基础上，对r o u g hs e t 巾的核心约简技术进行重点突破与改进， 研究最优约简的理论框架与基于动态系统演化的实现方案；在算法开发基础上， 形成整套关于粗糙集的算法库，开发相应的软件平台和应用系统。本人在这 些项目中负责建立一套以r o u g hs e t 理论为基础的，较为有效的处理海量数据 的机制。 1 4 论文组织与结构 本论文的结构与结构如下： 第一章介绍了粗糙集理论的发展和应用现状，以及本论文的研究背景和研 究工作等。 第二章阐述了海量数据挖掘的常用方法以及策略。主要介绍了与本论文工 一4 重庆邮电学院硕十论文 作相关的几种处理海量数据集的方法，以及分布式数据挖掘的常用模型，并阐 述了分布式处理海量数据的一般方法。此外，为了后面章节的叙述方便，本章 也简单介绍了粗糙集、信息系统里的一些基本概念。 第三章讨论了直接处理整个海量数据集的可伸缩性r o u 【g hs e t 知识约简算 法。在这一章里，我们首先结合r o u g hs e t 理论提出了一个类分布链表的结构， 然后根据类分布链表改进了一组包含数据离散化、属性约简和值约简的r o u 。g h s e t 知识约简算法，使这些算法能够很好的适用于海量数据集。 第四章研究了基于r o u g hs e t 的海量数据分割算法。在这一章里，我们首 先根据分布式数据挖掘的思想以及r o u g hs e t 的基本理论，提出了一个最优的 分割原始数据集的方案，即最佳分割的概念。然后论文根据最佳分割的要求提 出了一种基于r o u g hs e t 的海量数据分割算法。 最后一章对本论文进行了总结。 重庆邮电学院硕，l 论文 2 1 引言 第二章海量数据挖掘基础 海量数据是一个形容词，它是用米形容巨大的、空前浩瀚的数据。现在， 在许多业务部门中都需要操作海量数据，如规划部门有规划方面的数据，水利 部门有水利方面的数据，气象部门有气象方面的数据，测绘部门有测绘方面的 数据，这些部门都可能有几百兆甚至几百吉的数据，如仅测绘部门的全国l ：2 5 万地形数据库的数据量就达4 5 g b ：又如包含七个波段的l a n d s a tt m 影像的数 据量有2 7 0 m 左右，如果统计覆盖全国的t m 影像的数据量将达到1 3 5 g b 。随着 人类信息化程度的提高，数据已超出它原始的范畴，它包含各神空间数据、报 表统计数据、文字、声音、图像、超文本等各种环境和文化数据信息。而且随 着社会信息化程度的提高、计算机的普及，特别是数据库技术以及数据库管理 系统的快速发展，使得人们可以越来越方便地存储和管理自己手边巨大的数据。 同时随着网络技术和互联网的迅速发展，世界各地、各行业、各部门以及个人 都能通过网络达到信息共享，使得空间上分布于世界各地的海量数据能有机地 联系在一起。 海量数据是个相对的概念，本论文考虑的对象是狭义上的海量数据，即驻 留在个中心处理器上的海量数据集。绝大多数的数据挖掘算法或多或少都会 有海量数据的闯题，因为在考虑海量数据闯题时我们总是假设数据量足够大。 本论文主要考虑的就是如何从这个驻留单机磁盘的海量数据集上快速有效地获 取知识。 下面简要介绍与本论文有关的几种挖掘海量数据的方法。此外，为了后面 章节的叙述方便，本章也简要介绍了r o u g hs e t 的基础理论。 2 2 可伸缩性决策树算法 决策树或判定树( d e c i s i o nt r e e ) 是一个类似于流程图的树结构，其中每 个内部节点表示在一个属性上的测试，每个分枝代表一个测试输出，而每个树 叶节点代表类或类分布。最著名的决策树算法是q u i n l a n 于1 9 7 9 年提出的以信 息熵的下降速度作为测试属性的标准i d 3 算法。“。但是传统的决策树算法都是 内存算法，不能有效地处理海量数据。 重庆邮电学院硕士论文 2 2 1s l i q 分类器。 为了使决策树算法能够更好地适用于海量数据集，1 9 9 6 年i b ma l m a d e n r e s e a r c hc e n t e r 提出了s l i q 算法。s l i q 是一种高速可调节的数据挖掘分类算 法，它通过预排序技术，着重解决当训练集的数据量十分巨大，无法全部放入 内存时，如何高速准确地生成决策树的问题。 s l i q 算法的几个特点使之能够很好的处理海量数据： ( 1 ) 在生成树的过程中采取几个代价比较小的措施。首先是在评价和选择 分裂点的时候采用易于计算的g i n i i n d e x 。，而不是i d 3 算法的信息 熵；其次是采用了易于实现和评价分裂点的二分叉树；此外，在剪枝 树时选用代价比较小的m d l 剪枝算法”。 ( 2 ) 采用广度优先的策略来生成树。这样在扫描一个属性表时就可以通过 计算相应的g i nji n d e x 从而知道当前所有叶节点以该属性为分裂属 性时的最佳分裂，这样大大提高了扫描速度。 ( 3 ) 预排序策略。对于连续值属性，在传统的决策树算法中每次新生成节 点时都需要重新排序一次，因此效率不理想。所以s l i q 使用了在最 开始建树时进行预排序的方法，从而在整个建树过程不再需要进行额 外的排序来生成新节点，这是s l i q 算法的重要优点之一。在预排序 时s l i q 从原始决策表分离出若干个属性表和类表。一个条件属性对 应一个属性表，如果是连续值属性则要对属性表进行排序，决策属性 对应类表，类表还包含了叶节点信息。通过预排序策略，s l i q 大大 提高了效率。 ( 4 ) 节约内存。在算法中，类表是需要频繁调用的，因此需要常驻内存， 而其余结构可以放到外存中处理。为了加快速度，在内存允许的情况 下，可以把当前要处理的属性表置入内存。因此，算法只需要将重要 的部分信息而不是整个决策表置入内存处理，从而大大节约了内存空 间，使得算法能够处理海量数据集。 综上所述，s l i q 分类器只需要对属性值进行一次排序，即在最开始的时候 进行的预排序，因此运算速度比较快。而且它利用了整个训练集的所有数据， 不做取样处理，不丧失精确度，取得了与经典决策树相当的效果。更重要的是 s l i q 分类器能够直接处理驻留磁盘的海量数据。但是s l i q 分类器在生成树的 整个过程中需要类表常驻内存来保证算法的效率，当类表不能常驻内存时，算 法的性能有很明显的下降。 重庆邮屯学院硕士论文 2 2 2s p r i n t 分类器。 s p r i n t 分类器对s l i q 分类器进行了如下修改： ( 1 ) 预排序时，不再使用类表，而在分裂出的各属性表中加入决策属性列。 因此也解除了类表的内存限制，从而使得算法能够处理比s l i q 更大 的数据集。 ( 2 )因为没有了类表，为了标识各节点的信息，在创建新叶节点的时候， 需要分配父节点上的记录给新增的叶节点，并将父节点上的属性表 分为二。因为属性表是已经排序的，因此分裂获胜属性的属性表是简 单的，但对于失败属性的属性表的分割就比较麻烦。这时，s p r i n t 先要从获胜属性表中收集到分裂一端的样本索引号( r i d ) 合成h a s h t a b l e ，再借助于h a s ht a b l e 去分裂其余的失败属性表到叶节点中。 s p r i n t 算法也是只需一次排序，不损失精确度。当h a s ht a b l e 太大以至 于不能整个置入内存时，算法需要分多步来生成h a s ht a b l e ，每一步分裂一次 父节点的属性表。与s l i q 相比，s p r i n t 几乎移除了所有的内存限制，但因为 算法需要频繁地分裂属性表，因此在效率上要低于s l i q 算法，而且当数据集太 大以至于h a s ht a b i e 需要多步处理时，算法的效率会受到影响。 2 2 3 小结 继s l i q 和s p r i n t 后，人们又相继提出了c l o u d s “，s c a l p a r c “”等改进算 法，它们都采用某种策略试图在生成树的过程中尽量地减少算法与驻留磁盘中 的数据的i o 操作。后来，j g e h r k e 又提出了针对大数据量的快速决策树生 成算法框架r a i n f o r e s t “，此框架适用于大多数决策树算法，r a i n f o r e s t 在某 些场合的速度和效果都超过了s p r i n t 算法“。 这些可伸缩性的决策树算法在建树上的思想其实与传统的决策树的算法是 一样的，都分为两步：首先评价每个属性的分裂点，并从中选择最佳的分裂点， 然后用最佳分裂点来创建新的叶分枝。其实，在生成树的每一个步骤里，不是 所有的信息都需要用到。因此这些算法提出了一种有效的结构或者一种有效的 方法将所有的信息很好的分开，需要频繁使用的真丁f 有用的信息被置入内存处 理，而当前不需要用到的信息被置入外存中以节省内存空间。通过这种方法， 这些决策树算法在一定程度上解除了内存限制，可以直接处理海量数据集。 基于这种思想，在第3 章里，我们将根据r o u g hs e t 的思想，提出一种表 示分类的结构一一类分布链表( c d l ) ，它包含了我们挖掘知识所需的所有信息， 接着，根据c d l 改进了一组基于r o u g hs e t 的知识约简算法，能够很好的处理 海量数据集。 重庆邮电学院硕上论文 2 3 分布式数据挖掘 随着分布式平台的盛行，许多平台存储着分布式数据源和计算节点。我们 可以将这些散布于网络中各个数据节点的数据集合到一个大型数据库中再进行 处理，这样做固然会得到很好的效果，但也有明显的缺陷： ( 1 ) 时间和空间上的限制。比如全国连锁的大型超市，每个超市每天都会 有几万甚至几十万条交易数据，要把这些交易数据合并起来再处理是 十分不现实的，因为以当f i ；f 舌t - 算机的计算能力，这样处理数据的速度 还跟不上数据增长的速度。 ( 2 ) 保密性方面的问题。比如银行的交易数据等。这些数据通常来说是保 密而不能公开的，把这些原始的数据全部都收集起来通常是不可能的。 因此只能在本地处理各自的原始数据然后将生成的知识收集起来。 分布式数据挖掘的方法能够很好的处理分布式数据源的问题。分布式数据 挖掘一般采用图2 1 所示的处理模型。通常来境，分布式数据挖掘算法对于分 布在各个节点上的数据集采用相同的串行数据挖掘算法，在各个节点上得到各 自的局部模型。随后，所有的局部模型被整合为全局的最终模型。分布式算法 具有高度的适应性、可伸缩性、低性能损耗和容易连接等特性，可以很好的处 理分布式数据源。 本论文还研究了使用分布式数据挖掘的思想来处理驻留单机磁盘的海量数 据集的问题。因而在此我们先介绍几种经典的d d m 模型，并讨论分布式处理海 量数据的一般方法。 图2 1 分布式数据挖掘常用模犁 重庆邮电学院硕士论文 2 3 1m e t a l e a r n i n g 7 _ 1 8 1 m e t a l e a r n i n g 框架是一个比较著名的d d m 模型。m e t a l e a r n i n g 提供了一 种从同种分布式数据源中挖掘分类器的方法。在这个方法中，监督学习技巧被 应用于局部数据集上的分类器挖掘，随后通过局部学习概念来产生一个 m e t a l e v e l 数据集，m e t a l e v e l 分类器通过在这个m e t a l e v e l 数据集上学习 得到。m e t a l e v e l 学习可以递归应用，产生多级m e t a l e v e l 分类器。图2 2 显示了m e t a l e a r n i n g 学习的一般过程，为了简便说明，图中举出一个最简单 的例子，即只有两个分布式数据源的例子。图中显示的m e t a l e a r n i n g 的四个 步骤说明如下： ( 1 ) 在每一个处理器( 节点) 中应用分类学习算法产生基础分类器； ( 2 ) 使用生成的基础分类器对预先分离出的校验集进行判定，得到关于校 验集的很多预测； ( 3 )由分离出的校验集以及( n ) 中通过分类器判定后的预测一直组合成 m e t a l e v e l 数据集； ( 4 ) 在m e t a l e v e l 数据集上进行学习从而产生最终的全局分类器 ( m e t a c l a s s i f i e r ) 。 m e t a l e a r n i n g 可以递归学习从而生成多级m e t a l e v e l 分类器，但 m e t a l e a r n in g 只能处理同质的分布式数据源，对于不同种类的分布式数据源 则无能为力。 幽2 m e t a l e a r n i n g 发现知识的过群 重庆邮电学院硕l 论文 2 3 2 直接组合规则集的方法“” 许多分布式数据挖掘算法不能处理非同种类的数据源，比如2 3 1 中的 m e t a l e a r n i n g ，而x i n d o n gw u 提出的方法就能够很好的解决这个问题。图2 3 显示了x i n d o n gw u 采用的分布式数据挖掘的模型。和大多数数据挖掘模型一样， x i n d o n gw u 也认为出现频率最高的规则是最好的规则，为此，他将所有分布式 数据源上生成的规则通过计算权重的方法组合起来并按计算的结果对规则进行 排列，即“w e i g h t i e ga n dr a n k i n g ”的方法。通过这种方法，算法将所有在局 部数据源上的局部规则最大限度地转变成能够体现全局信息的全局规则，得到 了很好的效果。因为算法处理的是已经生成了的知识即规则，而这些规则的产 生过程对于规则集的组合来说是完全透明的，因此算法可以处理非同种类的数 据源。 自由 g p d 3 ：t h ea g g r e g a t e dr u l eb a s e r b i ：a l jr u l e i n d b l d b i ：t h ei t hd a t as o u r c e 矧2 3x i n d o n gw u 采川的组合规j j ! j j 集的模型 2 3 3 分布式处理海量数据 分布式数据挖掘在处理分布式数据源上取得了很好的效果。因此人们也提 出了分布式处理驻留单机磁盘的海量数据集的方法，这种方法最先被 m e t a l e a r n i n g 所采用。分布式处理海量数据的方法总体上可以分为两步： ( 1 ) 将一个海量数据全集分割成很多的数据子集，并派送到各分布式处理 器上： ( 2 ) 把这些散布于各分布式处理器上的数据子集看成许多分布式数据源， 并在这些分布式数据源上使用相应的d d m 算法进行分布式数据挖掘。 因此，从这个意义上浇，对于一个分布式数据挖掘系统，只要将海量数据 o h n、1j a 、 r 、 ， ， d 一 一 a 一 一k g 一、一u n 、 、 g ，_ ， 、函 w 囝百甬 重庆邮电学院t 丽- i ：论文 集分割成许多数据子集作为该系统的输入数据源，则该分布式数据挖掘系统就 可以处理海量数据集。 m e t a l e a r n i n g 就使用这种方法来处理海量数据集，但和大多数的分布式 数据挖掘算法一样，m e t a l e a r n i n g 的主要目的是处理分布式数据源，因此在 处理单机上的海量数据集时它把重心放在对各子数据节点上生成的局部模型的 整合上。在前端，m e t a l e a r n i n g 采用了随机抽样的思想来将驻留在一个中心 处理器上的海量数据集分割成许多能够在单机上直接处理的数据子集。分布式 处理海量数据的方法很好的利用了分布式数据挖掘的优势，能够比较快速地挖 掘知识。但分布式处理海量数据会损失一定的正确性。 2 3 4 小结 分布式数据挖掘在处理分布式数据源上体现了很好的性能。使用分布式数 据挖掘来处理海量数据也成为海量数据处理的一个可选方案。然而一般的分布 式数据挖掘算法的设计初衷都是为了处理分布式数据源，而本论文处理的对象 是已经存放到一个大型中央处理器上的海量数据集。因此，使用分布式数据挖 掘要处理这类问题的时候，就面临一个关键问题，即如何对原始的大型海量数 据集进行分割的问题。m e t a l e a r n i n g 采用的是随机分割的思想，当分割数目 比较大的时候效果不理想，因为这时分割后的数据予集包含的样本相对于全局 海量数据集来说太小。在分布式处理海量数据中，分割成许多数据子集后遗失 的信息在后继的分布式处理及整合局部模型中都无法弥补，因此分割算法的设 计在分布式处理海量数据上具有十分重要的意义。本论文在第4 章就分割算法 进行了一定的研究。 图2 3 显示了一种易于实现而且效果不错的组合局部模型的方法。在第4 章里，本文就采用了种与图2 3 类似但更为简约的分布式学习模型来验证分 割算法的有效性。 2 4 粗糙集理论基础 粗糙集理论是一种刻划不完整性和不确定性的数学工具，能有效地分析和 处理不精确、不一致、不完整等各种不完备信息，并从中发现隐含的知识，揭 示潜在的规律。粗糙集理论的研究已经经历了近2 0 年的时间，无论是在系统理 论、计算模型的建立和应用系统的研制开发上，都已取得了很多成果，也建立 了一套较为完善的粗糙集理论体系。 由于本论文主要研究借助粗糙集理论的思想来处理海量数据，为了便于后 面章节的叙述，下面我们简要介绍与本论文相关的粗糙集基本概念和知识”。 重庆邮电学院硕士论文 2 4 1 粗糙集相关概念 定义2 1 一个决策表信息系统( 简称决策表) s = ，其中，u 是对象的集合，也称为论域，r = c u d 是属性集合，子集c 和d 分别称为条 件属性集和决策属性集，d 庐，v = u ，。n 是属性值的集合，表示属性r r 的属性值范围，即属性r 的值域，f ：u r 斗v 是一个信息函数，它指定u 中 每一个对象x 的属性值。 定义2 2 给定决策表信息系统s = ，对于每个子集x u 和不 分明关系占，j 的下近似集与上近似集分别可以由曰的基本集定义如下： 下近似集r ( x ) = u z u i i n d ( b ) ：z x ) ， 上近似集r 一( ) = u k u i i n d ( b ) ：i n x = o 。 也可以通过集合来定义： r - ( z ) = 扛e u ：b k x ) ， r 一( x ) = 扛u ：k l n o 。 定义2 3 集合b n 。( x ) = r 一( ) 一r ( x ) 称为鼻的月边界域， 集合 p o s r ( x ) = 足( ) 称为x 的r 正域，集合n e g r ( z ) = u r 一( ) 称为x 的r 负 域。 定义2 4 设【，为一个论域，p 和q 为定义在u 上的两个等价关系簇，则q 的p 正域p o s p ( q ) 和q 的p 负域n e g p ( q ) ，分别定义为： p o s p ( q ) = l jp o s ，( 爿) ； x u n e g ，( q ) = u p o s p ( q ) = un e g p ( ) a e 叫u 定义2 , 5 对一个决策表系统 ，其论域为u ，条件属性集 为c ，决策属性集为d ，有任何一个条件属性集合p c ， 令： u i p = 一，- ，。) ，u i d = 亿，k ，l 。则d 相对于p 的条件熵值为： h ( d i j p ) = - y p ( x , ) p ( l ) a o g ( p ( y j l ) ) ， 其中，p ( i l x f ) = l n x 。i x ，i = 1 , 2 ，邪，= 1 , 2 ，。 定义2 6 给定决策表s = ，c 和d 分别为决策表的条件属性和 决策属性，条件分类定义为：e i u | i n d ( c ) ，( f - l ， f ) ，m 为条件分类的 个数；决策分类定义为：x ，ur n d ( d ) ，( 户1 ，月) ，为决策分类的个数。 定义2 7 在决策表s = 中，r = c u d ，对于条件分类 x u i n d ( j p ) ，其中p c c ，如果x p o s ，( d ) 则称为p 上的个相容条 件分类，如果n e g 。( d ) 则称为p 上的一个冲突条件分类。 重庆邮电学院硕i ：论立 定义2 8 给定决策表s = 中，r = c u d ，对于任意的x u 。 决策规则出定义如下： d x ：d e s ( x c ) j d e s ( x o ) ，其中以( ) o 。，“c u d ，且d ，, l c ，d x l d 分别 称为也的条件和决策。 2 4 2 属性重要性 在信息系统中，每个条件属性所占的地位不一定相同。一些条件属性占的 地位较高，而另外的条件属性占的地位较低。如果我们能对信息系统的属性重 要性作出评价，就可以充分利用重要性高的属性取值来优化决策。属性的重要 性可以在辅助知识的基础上事先假设，并用“权重”表示。在粗糙集方法中， 不使用假设的信息，只利用表中的数据进行衡量。信息系统的属性重要性是建 立在分类能力上的，为了衡量条件属性的重要性程度，我们可以从表中删除一 些属性，来考察信息系统的分类会产生怎样的变化：如果去掉某属性会相应的 改变分类，则说明该属性的重要性高；反之说明该属性的重要性低。 分类能力可以通过分类质量来衡量，定义为：r r = j p o s r ( d ) l i u f 。 属性甜的重要性表示为：g a i n = 珞一r r “，。 表2 1 决策表 ub l0 21 210o 3230 43l1 534o 6211 1 2 0 7431 853l 例2 1 ：计算表21 所示决策表的条件属性重要性，其中c = f “ 易得：u i n d ( a ，6 ) = “1 ) ， 2 ) ， 3 ， 4 ) ， 5 ， 6 ) ， 7 ， 8 ) ) i 硼，d ( d ) = 1 ， 2 ) ， 3 ，6 ， 4 ，5 ， 7 ， 8 ； u i n d ( b ) = “1 ，5 ) ， 2 ) ， 3 ，7 ，8 ， 4 ，6 ； u l _ i n d ( a ) = “1 ，4 ，6 ，7 ，8 ) ， 2 ，3 ，5 ，。 因此：牛( d ) = ip o s c ( d ) l lul = f 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ) l 8 5 1 ， 重庆邮电学院颁士论文