1、分布式数据挖掘张敏灵 陈兆乾 周志华 南京大学软件新技术国家重点实验室2002.10.11提纲简介 数据挖掘 分布式数据挖掘研究现状 同构与异构 分布式数据挖掘算法 应用实例进一步的工作简介数据挖掘什么是数据挖掘？数据挖掘是指从巨量数据中获取有效的、新颖的、从巨量数据中获取有效的、新颖的、潜在有用的、最终可理解的模式的非平凡过程潜在有用的、最终可理解的模式的非平凡过程。(From U.Fayyad et al.s definition at KDD96)巨量的：对于少量数据的分析不需要使用数据挖掘。有效的：所获得的模式必须是正确的。新颖的：对于已知知识的投资收益不大。潜在有用的：所得的模式应能
2、提供相关的决策支持。最终可理解的：所得的模式是提交给决策制定者的。数据挖掘的研究领域数据挖掘是一门涉及机器学习、统计学、数据库、可视化技术、高性能计算等诸多方面的交叉学科。数据挖掘续数据挖掘的应用范围 描述性规则发现(Characterization)对比性规则发现(Discrimination)关联规则发现(Association)分类分析(Classification)预测（回归）分析(Prediction)聚类分析(Clustering)异常分析(Outlier analysis)简介分布式数据挖掘产生背景 各相关学科的飞速发展，各种网络尤其是Internet的广泛使用。实际应用要求数据
3、挖掘系统具有更好的可扩展性。实例 研究某种疾病在某地的发病情况与气候的关系（疾病控制数据库环境数据库）金融组织间通过合作防止信用卡欺诈（数据共享）大型跨国公司营销策略的制定（销售点分散，数据仓库构造十分耗时）分布式数据挖掘正是在这一背景下产生的，它是数据挖掘技术与分布式计算的有机结合，主要用于分布式环境下的数据模式发现。分布式数据挖掘续分布式数据挖掘的优点出于对安全性、容错性、商业竞争以及法律约束等多方面因素的考虑，在许多情况下，将所有数据集中在一起进行分析往往是不可行的。分布式数据挖掘系统则可以充分利用分布式计算的能力对相关的数据进行分析与综合。在传统的数据挖掘系统中，如果能将数据合理地划分
4、为若干个小模块，并由数据挖掘系统并行地处理，最后再将各个局部处理结果合成最终的输出模式，则可节省大量的时间和空间开销。面临的问题 算法方面 数据预处理，实现各种数据挖掘算法。结合系统所处的分布式计算环境。系统方面 能在对称多处理机(SMP)、大规模并行处理机(MPP)等具体的分布式平台上实现。结点间负载平衡、减少同步与通讯开销、异构数据集成等。分布式数据挖掘续系统分类根据结点间数据分布情况 同构：结点间数据的属性空间相同 异构：结点间数据具有不同的属性空间按照数据模式的生成方式 集中式：先把数据集中于中心点，再生成全局数据模式（模型精度较高，但只适合于数据量较小的情况）。局部式：先在各结点处生
5、成局部数据模式，然后再将局部数据模式集中到中心结点生成全局数据模式（模型精度较低，但效率较高）。数据重分布式：首先将所有数据在各个结点间重新分布，然后再按照与局部式系统相同的方法生成数据模式。按系统功能、通讯与合作方式等情况划分研究现状结点的同构与异构性 元学习(Meta-learning)CDM(Collective data mining)分布式数据挖掘算法 分布式决策树生成 分布式关联规则发现应用系统实例结点的同构与异构性元学习同构结点间的数据挖掘在同构分布式数据挖掘系统中，各个结点存储的数据都具有相同的属性空间。为了实现同构结点的数据挖掘，研究者们先后提出了元学习(meta-learn
6、ing)、合作学习(coactive learning)等方法，其中元学习方法最具代表性。元学习的概念是由Prodromidis等人于2000年首先提出的，该方法采用集成学习(ensemble learning)的方式来生成最终的全局预测模型（即元分类器）。该方法的基本思想是从已经获得的知识中再进行学习，从而得到最终的数据模式。元学习续元学习的具体过程图1 元学习的具体过程元学习续基分类器输出的集成方式 投票(Voting):绝对（相对）多数投票，加权投票。决策(Arbitration):指定特殊的“决策者”，当各基分类器的输出无法达成一致时，采用“决策者”的输出。结合(Combining):
7、使用相关的先验与领域知识指导各输出的集成。元学习的优点在基学习阶段，各个结点可以自主地选择合适的学习算法来生成局部的基分类器。与此同时，各结点间不存在任何通讯与同步开销，因此系统效率较高。在元学习阶段，由于系统可灵活采用各种集成策略，因此最终生成的元分类器具有较高的预测精度。结点的同构与异构性CDM异构结点间的数据挖掘在异构分布式数据挖掘系统中，各个结点存储的数据具有不同的属性空间，一般而言，异构分布式数据挖掘系统所要处理的数据集称为垂直分划数据集。图2 一个典型的垂直分划数据集CDM续CDM研究结果表明，如果简单地将同构系统所采用的数据挖掘方法应用于异构分布式数据挖掘系统，那么为了得到一个精
8、确的预测模型往往需要很大的系统开销，有时甚至是不可行的。()Ikkkf xw 为了能够在结点异构的情况下有效地进行数据挖掘，Kargupta等人提出了CDM(Collective Data Mining)的概念，其基本思想是任一函数f都可以由一组基函数所表示，即 。最近，Kargupta等人结合传统的ID3决策树学习算法以及小波变换技术，成功地将CDM技术应用于分布式决策树生成以及回归分析中，取得了令人满意的结果。分布式数据挖掘算法分布式决策树生成分布式决策树生成决策树是一种用于分类与回归分析的传统预测模型，由于其简单易用，并且具有很好的可理解性与较强的可扩展性，因此被数据挖掘领域所广泛使用。
9、早期的分布式决策树生成算法主要基于对传统算法(例如ID3算法)的并行实现，这些算法假设所需的数据都位于主存之中，并且没有考虑磁盘读写、负载平衡等实际问题，因此具有很大的局限性。针对上述的情况，Mehta等人提出了一种新的决策树生成算法SLIQ(Supervised Learning In Quest)。该方法定义了类列表（常驻内存）和属性列表（位于内存或磁盘中）两种数据结构，在一定程度上克服了内存大小对训练集规模的限制，且易于实现并行处理(SLIQ/R、SLIQ/D)。分布式决策树生成续其他算法 SLIQ算法中使用的类列表是随着数据规模的增大而线性增长的，由于类列表在运行时刻常驻于内存中，这就
10、限制了SLIQ算法所能处理的问题的规模。Shafer等人在SLIQ算法的基础上设计出了SPRINT(Scalable PaRallelizable INduction of decision Trees)算法，并且给出了SPRINT算法在分布式计算环境下的具体实现。实验结果表明，SPRINT算法很好地解决了内存大小对于问题数据规模的限制问题，并且在系统运行时间、规模可扩展性、应用可扩展性等方面均优于SLIQ算法。Arguello等人基于对决策树增量学习算法的研究，针对共享存储器和无共享两种多处理器结构，分别提出了DSD(Distributed Subtree Derivation)和DTD(D
11、istributed Tree Derivation)两种分布式决策树生成算法。这两种算法具有很强的灵活性，生成的决策树规模也较小，但是算法运行过程中需要较大的通讯与同步开销。分布式数据挖掘算法分布式关联规则发现分布式关联规则发现 随着大规模事务数据库的广泛使用以及企业数据分布范围的逐步扩大，使得设计高效的分布式关联规则挖掘算法变得越来越重要。Agrawal等人在 Apriori 这一传统的关联规则挖掘算法基础之上，设计了计数分布(Count Distribution)、数据分布(Data Distribution)以及候选分布(Candidate Distribution)三种分布式关联规则
12、挖掘算法。在计数分布算法中，各个结点都含有完整的频繁项目集，减少了系统的通讯与同步开销；另一方面，频繁项目集在系统各结点处的冗余存储也降低了系统资源的利用率。在数据分布算法中，整个频繁项目集均匀地分散于各个结点，系统的资源利用率较高，但增加了结点间的通讯和同步开销。在候选分布算法中，算法将根据问题领域所提供的语义信息把整个频繁项目集在各个结点中重新分布，从而达到平衡各结点负载的目的，同时减少了结点间的同步开销。同样基于Apriori算法，Cheung等人提出了另一种分布式关联规则挖掘算法FDM(Fast Distributed Mining of association rules)。FDM算
13、法产生的候选频繁项目集规模要小于计数分布算法，并且降低了结点间的通讯开销以及算法的运行时间。应用系统实例JAM：该系统基于元学习方法，利用从各个稀疏的数据源处收集的信息来构造最终的全局分类模式。PADMA：该系统采用了合作Agent技术，主要用于分布式计算环境下的文档分析。Papyrus：该系统基于与JAM系统相似的理论基础，主要用于对分部在广域网内的数据进行有效的分布式数据挖掘。Kensington：该系统采用了分布式组件技术，主要用于Internet上的分布式数据挖掘。进一步的工作目前，虽然有关异构结点的分布式数据挖掘已经做了大量的工作，但过高的通讯与计算开销却限制了系统对巨量数据的处理能力。因此，设计可扩展性较好的异构分布式数据挖掘系统显得十分重要。设计理想的系统抽象模型，实施标准化，可为开发通用的商用分布式数据挖掘系统提供了一条有效的途径。对于其他一些分布式数据挖掘算法，例如分布式多层关联规则挖掘、聚类分析、异常检测等，还需要进一步的研究。设计出通用高效的系统开发环境，将大大提高分布式数据挖掘系统的开发效率。Thanks
