DWDM第14章.docx
- 文档编号:17403104
- 上传时间:2023-07-25
- 格式:DOCX
- 页数:33
- 大小:158.61KB
DWDM第14章.docx
《DWDM第14章.docx》由会员分享,可在线阅读,更多相关《DWDM第14章.docx(33页珍藏版)》请在冰点文库上搜索。
DWDM第14章
14数据挖掘的发展与应用314
14.1分布式数据挖掘314
14.1.1分布式数据挖掘简介314
14.1.2分布式数据挖掘系统316
14.1.3研究现状317
14.2分布式数据挖掘算法318
14.2.1分布式关联规则319
14.2.2分布式分类算法323
14.3数据挖掘软件发展326
14.3.1系统功能的发展326
14.3.2应用模式的发展327
14.4数据挖掘标准329
14.4.1过程标准329
14.4.2实现标准335
本章要点342
参考文献345
14数据挖掘的发展与应用
随着信息技术的不断发展,数据挖掘研究领域也日新月异,新的研究问题不断涌现。
同时随着研究的深入以及大量的商业应用,数据挖掘已经从实验室走向市场,形成了数据挖掘行业。
与此同时数据挖掘系统也在逐渐演进,关于数据挖掘系统的标准也正在形成。
本章分为四个部分,前两个部分介绍数据挖掘的新领域——分布式数据挖掘以及相应的算法,第三部分介绍数据挖掘系统的发展,最后一部分介绍数据挖掘的相关标准。
14.1分布式数据挖掘
14.1.1分布式数据挖掘简介
随着计算技术与网络的飞速发展出现了大量的分布式环境如Internet、Intranet、无线网络等。
这些环境中拥有不同的分布式数据以及多个计算节点,分析与监视这些环境中的数据需要数据挖掘技术。
图14-1传统的基于数据仓库的数据挖掘的结构
传统的数据挖掘技术建立在集成式的数据仓库基础之上,其典型的结构如图14-1所示。
这种方法需要将大量的数据集成到数据仓库中,但在实际应用中有许多缺点:
数据集成本身存在着许多问题;响应时间过长、不适合实时的数据挖掘;需要有高速的网络连接、没有充分地利用计算资源。
同时在有些情况下基于法律上或商业上的考虑而不能将数据集成到一起。
显然传统的基于集中式处理的数据挖掘方法不适应在分布式环境中。
分布式数据挖掘(DistributedDataMining,DDM)可以解决上述传统数据挖掘所存在的不足之处。
DDM的目标是在分布式、异构的资源上进行数据挖掘工作,典型的DDM的结构如图14-2所示。
图14-2典型的DDM结构图
如同传统的数据挖掘方法一样,DDM也可以分为确定数据分布、预处理、数据挖掘三个步骤。
由于大多数DDM算法基于关系数据库而不是数据仓库,而关系数据库中数据库模式(DatabaseSchema)存储关系信息,数据库模式决定数据表之间的依赖关系,并会影响到DDM算法的选择。
因此DDM的第一步工作是确定数据如何分布。
数据分布有两种形式:
第一种为同构分布,既不同的数据站点有相同的属性集,这样的分布式数据通常属于同一个企业。
另外一种为异构分布,即各个站点的数据之间有不同的属性集。
在异构分布情况下,各个数据表需要通过共享的主键连接起来。
与传统的数据挖掘所采用的数据预处理方法不同,DDM的数据预处理需要以分布式的方式进行。
分布式数据预处理的第一步是交换数据库模式和元数据(Meta-Data),这通常只需要较低的通讯成本。
另外还可能需要交换度量单位、属性的物理含义和其它相关信息。
如果数据站点是异构的,主键关联是一个必需的步骤。
主键关联的目的是通过选择一组主键将不同站点上的数据联系起来。
数据模式信息和属性的物理含义可以用来连接各个站点。
如果没有可以利用的主键,可以使用聚类技术创建相应的主键。
通常空间数据库可以使用坐标位置作为主键,临时数据库可使用时间戳作为主键。
另外DDM的数据预处理与传统的数据挖掘一样同样涉及到数据的规范化,两者要求的技术与方法基本相同。
14.1.2分布式数据挖掘系统
一个分布式数据挖掘系统(DistributedDataMiningSystem,DDMS)是一个复杂的软件实体。
它由许多部件构成如:
挖掘算法、通信子系统、资源管理、任务计划、用户界面等。
DDMS应有效的利用计算资源,监视整个数据挖掘过程,以合适的方式将结果呈现给用户。
一个成功的DDMS应该有足够的柔性来适应变化,它应该在给定资源的状态下动态地调整挖掘策略。
因此DDMS设计中最重要的是架构和通讯问题。
在许多组织中有高性能的计算集群,它们可以用来进行大规模的分布式数据挖掘。
然而美国学者Parthssartuy指出,CPU、网络、I/O的竞争会严重影响到DDMS的性能,因此他提出应该逐步分配资源,使应用符合资源的约束[]。
三层结构是一个有效的利用资源的方法,Kensington系统[]属于这种类型,该系统分为客户端、应用服务器、第三层服务器。
客户端用来创建挖掘任务、将结果可视化;应用服务器提供用户认证、任务协调、数据管理;第三层则提供高性能的数据挖掘服务。
在DDMS中通常要求有高效的数据通讯。
Grossman等人在研究Papyrus系统[,]时指出通讯的方法有三种:
移动结果、移动模型和移动数据。
移动结果指在本地处理数据,然后将产生的结果移动到另外的站点上等待进一步处理;移动模型指的是本地处理数据,然后将产生的模型移动到另外一个节点上;而移动数据指的是将数据移动到另外的站点上处理。
Papyrus系统是一个用来在高速网络条件下进行最优化数据挖掘的系统。
由于DDMS是一个异常复杂的系统,要求高度的可扩展性、柔性以及可靠性,传统的软件开发技术很难适应。
大多数系统使用了Agent技术,将Agent技术应用到分布式数据挖掘中可以结合Agent系统的优点。
首先,基于Agent技术为DDM提供了并行机制,Agent系统的分布式特征允许并行执行数据挖掘任务,可以提高速度、效率、可靠性。
并行机制还意味着可以在局部挖掘中使用已有的算法,因为本地操作不需要了解其它站点的信息。
其次Agent技术可以提供用户在挖掘过程中检索信息和知识的能力。
例如用户可以在知识合并之前观察一个局部Agent所挖掘的知识。
最后,应用Agent原理有助于分布式数据挖掘系统的设计。
使用Agent封装了数据挖掘对象后,设计者可以在以后复用该Agent。
在基于Agent分布式数据挖掘系统中,Agent是一个软件实体,它有如下功能:
与其它Agent进行互操作;接受和收集原始数据;处理收集到的数据并从中学习;与其它Agent协作产生相关的、有用的知识和信息。
在基于Agent分布式数据挖掘系统中,Agent方面的研究主要集中在Agent如何操作数据以及Agent如何从分布式的数据源中抽取信息。
基于Agent的数据挖掘方法有两种:
(1)各个Agent独立的处理和挖掘本地数据,然后将各个站点的模型合并;
(2)在Agent的学习过程中交换信息。
第一种方法可以利用已有的数据挖掘算法,且通信量较少,第二种方法要求研究新的数据挖掘算法,并且通信量比较大。
Agent的知识合并有两种方法,它们是理论修正和知识集成。
两种方法都使用本地学习,但发现知识的方法不同。
理论修正采用增量式的学习,各个Agent将自己所发展的理论传递给其它Agent并进一步修正。
而知识集成用所有的训练数据集来测试模型或理论,最后选择最适合的理论或模型。
14.1.3研究现状
DDM研究近年来得到了飞速的发展,1998年召开了第一届并行与分布式数据挖掘国际会议,到现在已有数年的历史。
越来越多的研究者从事这方面的研究。
许多学者在DDM的算法研究方面已经作了大量的工作,并且已经出现了许多DDM系统,如美国哥伦比亚大学Stolfo教授设计的JAM(JavaAgentforMeta-Learning)系统[],JAM系统是一个从多个金融数据库中挖掘信用卡欺诈的分布式数据挖掘系统,JAM系统在实际使用中获得了良好的效果[]。
WoRLD(WorldwideRelationalLearningDaemon)系统是由美国匹兹堡大学Aronis教授设计的分布式数据挖掘系统,采用了贝叶斯网络用来进行数据挖掘和知识发现[]。
美国马里兰大学Kargupta教授设计的BODHI(BeseizingknOwledgethroughDistributedHeterogeneousInduction)系统则是使用组合数据挖掘框架来进行分布式的数据挖掘和知识发现[,],同时,他还设计了可以使用个人数字助理的分布式数据挖掘系统[]。
国内武汉大学的何炎祥教授所领导的研究小组也对分布式数据挖掘进行了相关的研究[,]。
以上分布式数据挖掘系统大多数采用了基于Agent的结构。
虽然DDM方面的研究已经取得了很大的进展,但仍存在许多尚未解决的问题:
(1)现有的研究大多集中在同构数据集上进行,异构数据集方面的研究较少;
(2)目前的研究主要集中在算法领域,在数据预处理等方面只有很少的文献。
(3)大多数的算法集中在分布式关联规则、分布式分类领域;
(4)现有的分布式数据挖掘系统大多数是实验室中的原型系统,没有真正成熟的应用,并且这些系统只针对特定的问题而设计与开发的,没有普遍性和通用性。
14.2分布式数据挖掘算法
一个分布式算法的效率主要受到通讯成本、数据存取、计算资源这三个因素的影响,因此一个高效的算法要权衡三者之间的关系。
分布式算法主要有三种策略:
独立搜索、串行算法的并行化以及串行算法复制化[]。
在独立搜索类型的算法中每个处理器都可以存取整个数据集,但每个处理器的搜索范围不相同。
独立搜索类型的算法比较适合寻找最优解问题,一般不适合数据挖掘问题。
而串行算法并行化是将已有的串行算法作适当的修改使其适应分布式的环境。
这类算法可分为两类:
每个处理器生成全局模型,但每个处理器处理的数据集范围不同;每个处理器独立生成局部模型,对整个数据集的部分字段进行存取。
前者可以视为将数据集水平划分,后者则是将数据集垂直划分。
串行算法并行化试图减少通讯量以及计算成本,但是在这两方面都没有成功。
串行算法复制化则是首先通过每个处理器处理部分行集得到局部模型,然后将局部模型合并得到全局模型。
研究表明串行算法复制化比较适合分布式数据挖掘,大多数分布式数据挖掘算法基于这种策略。
因此,一般的分布式数据挖掘算法在每个站点上采用相同的算法,产生局部模型,然后将各个站点上的局部模型合并成最终的全局模型。
大多数DDM算法的可靠性依赖于局部模型的合并过程。
由于每个局部模型只体现了与局部信息一致的模式,但缺乏与全局一致的知识,因此许多DDM算法要求将一部分局部数据集中到一个站点上来弥补上述缺点。
近年来DDM得到了飞速的发展,研究人员提出了许多DDM算法,这些DDM的算法主要分为以下几类:
分布式关联规则、分布式分类、组合数据挖掘、分布式聚类。
本小节主要介绍分布式关联规则、分布式分类。
14.2.1分布式关联规则
基于Apriori的三种并行算法可以分为CountDistribution、DataDistribution和CandidateDistribute三类。
这些算法的前提是处理器结构上没有任何共享,有专用内存和磁盘,各处理器用通信网络连接,靠消息传递进行通信。
数据平均分配到每个处理器的专用磁盘上。
这些算法需要用到的符号意义如表14-1。
表14-1 算法中使用的符号及它们的意义
Lk
频繁集
Ck
候选集
Pi
ID号为i的处理器
Di
分配到Pi的数据集
DRi
Di重新分配后的数据集
第k次搜索,Pi所产生的当地候选集
CountDistribution是Apriori的一个简单并行化算法。
算法是通过分割数据库来完成并行化的。
如果有N个处理器节点,则各节点获得数据库的1/N,然后分别在各数据库子集上完成类似于Apriori的算法。
它的步骤如下:
k=1:
1)Pi根据本地数据集Di产生本地
,
2)Pi将各自的
与其它处理器交换,各处理器合并所有的
得出完整的C1。
k>1:
1)Pi根据完整的频繁集Lk-1产生完整Ck,
2)Pi对Di进行搜索,计算Ck中候选集在本地的支持数。
3)各Pi与其它所有处理器交换本地对
中候选集支持数之后,算出Ck的候选集支持数。
在这一步,各个处理器被强制同步。
4)Pi用Ck来计算Lk。
5)各Pi独立的决定是否终止或继续进行下一次搜索。
由于所有的Pi都有同样的Lk,所以每个Pi的决定是一致。
DataDistribution是在各节点之间分割频繁集的候选集,各节点分别计算各自所得候选集的支持度。
DataDistribution算法的步骤如下
k=1:
与CountDistribution算法相同。
k>1:
1)Pi从Lk-1中产生Ck。
根据Pi个数把项目集分割成N份,Pi仅保留1份来构成
。
处理器可根据其ID号来决定保留哪一部分而不需要与其它处理器通信。
2)利用本地数据和其它处理器传来的数据,Pi计算在
中项目集的支持数,
3)在一次数据搜索结束时,各Pi用本地的
来计算
,
4)处理器之间相互通信获取其它
,之后每个Pi得到完整的Lk,用于下一次产生Ck+1。
这一步要求处理器同步。
获得完整的Lk后,每个Pi能独立的决定是否终止或继续下一次搜索。
CandidateDistribution算法综合了DataDistribution和CountDistribution算法,以弥补它们各自的不足。
在前l步采用DataDistribution算法或CountDistribution算法。
到第l步(其中l由启发而定),为了减少各处理器之间的数据依赖,算法对频繁集Ll-1进行分配,同时对数据进行重新分配,使Pi能独立于其它处理器生成
。
为了减少处理器对候选集的依赖,CandidateDistribution算法不等待从其它处理器传来完整的剪枝信息,它尽可能快的剪枝。
而滞后到达的剪枝信息在下一次剪枝时使用。
该算法的具体内容如下:
k 沿用DataDistribution算法或CountDistribution算法。 k=l: 1)在N个处理器间分配Lk-1(简单的方法是根据Lk-1的前k-2项前缀进行分配)。 2)处理器Pi利用分配得到的 生成 。 3)根据 将数据库重新分割成DRi。 4)Pi根据 计算出 ,并发送到其它各处理器。 k>l: 1)Pi收集所有从其它处理器发送来的频繁项目集,用于对候选集剪枝。 2)Pi用本地的 生成 。 如果Pi没有收到其它处理器传来的 则Pi剪枝时要作相应的处理。 3)Pi搜索DRi,对 中的项目计数.然后根据 计算出 并把它传到其它处理器。 在CountDistribution算法中每个处理器都拥有完整候选集的副本,每个候选集的局部支持数要向所有站点进行广播。 因此,CountDistribution算法的通讯量比较少。 但是每个处理器都拥有完整候选集的副本,因此没有有效的利用内存。 而DataDistribution的中心在于最大程度上利用并行机制。 它将候选集分布到每一个站点上,每一个站点计算一个不相交的子集。 由于DataDistribution算法中每个处理器都要访问整个数据集,因此DataDistribution算法通讯量非常大,要求有高速的网络连接。 CandidateDistribution算法在计算过程中需要对数据进行移动,所以该算法的通讯成本也比较高。 实验结果表明,上述的三种算法中CountDistribution算法的综合性能最好。 Cheung等人提出了基于CountDistribution的FDM(FastDistributedMining)算法将通讯成本由 降低到 ,|C|和n分别为候选集的大小以及站点的个数,CP为可能的候选集的大小(所有局部候选集并集的大小)。 该算法基于如下原理: 一般来讲,只有很少的候选集在所有站点上均是局部频繁的,因此对于每个候选集X使用一个分配函数,例如哈希散列方法将X分配到某个站点,该站点称为它的轮询站点,并负责处理它是否是全局频繁的,X的轮询站点与它是否在该站点上频繁无关。 因此,即使X在多个站点上是频繁的,它也将被发送到同一轮询站点,所以对于每个候选集仅有一个轮询站点)。 FDM算法有三种优化策略: 本地剪枝、全局剪枝、轮询计数。 我国学者Wang等人在FDM算法的基础上提出了MLFDM(FastDistributedMiningofMultiLevelAssociationRules)算法[],该算法包括分布式编码交易表的有效修剪,候选集的产生及修剪技术,候选集的全局支持数的计算方法等。 Cheung等人提出的FMP-LP算法[]是基于本地剪枝优化策略,FMP-LP算法是基于以下原理: 如果项集在DB中是频繁集合,则它在其中的一个DBi(DB的第i个站点Si上的子数据库)肯定是频繁集。 如果项集X在DB和DBi都是频繁集,则称X在站点Si是gl-large. 设D是DB中的事务数目,Di是DBi中的事务数,Xsup是X的全局支持数,Xsup[i]是X在站点Si上的局部支持数,s是最小支持度,L(k)是k项全局频繁集,CA[k]是从L(k)中产生的候选集,GLi(K)是站点Si上的k项gl-large集,CGi(k)是从GLi(k-1)中产生的候选集,LLi(k),是CGi(k)中的k项局部频繁集。 FMP-LP算法主要分为以下几步: (1)生成候选集CGi(k); (2)局部剪枝。 对每一个X∈CGi(k),扫描DBi计算Xsup(i),在站点Si不是频繁集,就把它从候选集LLi(k)中删除; (3)交换支持数。 把候选集LLi(K)广播到其它站点以收集支持数。 同时计算全局支持数和搜寻所有站点上的k项gl-large项集; (4)广播挖掘结果。 把找到的k项集gl-large项集广播到其它站点。 14.2.2分布式分类算法 大多数分布式分类学习算法基于总体(ensemble)学习方法[]。 该方法首先产生多个基本分类器——一般称为同构数据子集,然后将它们合并。 总体学习方法可以直接应用到分布式环境中,并可以显著地提高分类的准确性。 分布式分类算法可以分为同构方法和异构方法。 在同构分布式分类算法中比较著名的是Stolfo所提出的元学习框架[]。 这种方法使用任何算法产生一组基本分类器(或使用一种算法在不同部分的数据上产生不同的分类器),然后把这些分类器的集成和合并作为一个学习任务。 在这种方法中每一个分类器用来扫描和标记一组数据并产生元层次的训练数据。 元层次的训练数据包括每一个分类器所产生的数据,可以用来产生最终的分类器。 最后所形成的元分类器比任何一个单独基础分类器精度要高。 他在研究JAM系统时指出元学习框架应有以下三步组成[,]: (1)在每一个站点上使用分类算法产生基本分类器; (2)将各个基本分类器合并到一个站点,然后利用基本分类器产生的数据集产生元层次的数据; (3)从元层次数据集中产生最终分类器。 在元层次学习中还可以采用不同的方法,例如可以用本地分类器产生一个新的数据集;也可以从训练数据中抽取数据,将它与本地分类器生成的数据相结合,然后可以使用任何一种学习算法来产生元层次的分类器。 元学习展示了DDM算法的两个特征: 并行机制和减少通信流量。 在计算过程中基本分类器是并行生成的,计算过程中通信成本也比传输整个原始数据要少的多。 另外,由Guo等人提出的DLKP(DistributedLearningKnowledgeProbing)是另外一种通过合并局部模型形成全局模型的元学习方法[]。 这种方法首先通过知识探查(KnowledgeProbing)从一个黑箱模型(如神经网络)形成描述性的知识。 它分为预测和学习两个阶段,基本步骤如下: (1)输入: 一组n个没有标识的数据、一个黑箱模型B、学习算法D以及一组分布式站点S。 (2)预测阶段: 为数据项创建分类值 。 (3)学习阶段: 利用C在S上创建新的训练数据集,并从这个数据集中学习。 (4)输出: 。 DLKP是知识探查的分布式扩展,它由以下四个步骤构成: (1)使用黑箱机制生成基本分类器; (2)为探查数据集选择一组没有标识的数据; (3)合并 (2)中的数据为探查数据集; (4)从探查数据集中直接生成最终的模型。 其中第三步,产生探查数据集可以使用许多方法。 DLKP与元学习的主要差别在于第二阶段的学习。 在元学习中使用特别的分类器来合并局部模型,最后的分类器包括元层次分类器和局部模型。 而DLKP直接通过探查数据集来生成最后描述性的模型。 DLKP的关键问题是局部模型的一致性。 为了合并局部模型,DLPK首先假设所有的局部模型是一致的,但这在实际中是不可能的。 DLKP通过枚举学习过程解决了这个问题。 因为局部模型反映了数据的分布,可以使用这一信息改变他们的分布。 每一个数据站点通过一致性测试数据集来测试,一致性测试数据集是随机的从每一个站点上选出的,导致各个模型不一致的数据被添加到所有的站点中。 通过这一步各个站点中的数据分布趋于一致。 在局部模型一致后,DLKP可以产生一个精确的、综合的、稳定的全局模型。 与同构式分类学习算法不同,异构式分类学习算法在每一个站点上只拥有关于整个数据集的不完全知识。 每一个站点局部的模型体现了问题一个不相交的领域,而DDM需要产生一个全局的数据模型或关联,因此异构式分类学习算法比同构式分类学习算法的难度大的多。 Provost和Buchanan提出了基于归纳方法的分类方法[]。 这种方法假定异构式特征空间分区可以通过将问题分解为子问题的方法来解决。 Aronis等人在开发WoRLD系统时通过传播激活(SpreadingActivation)方法来解决了局部站点的概念学习问题。 传播激活首先对每一个数据项使用加减号进行标记,然后计算每一个站点的特征值的基本分布,再将分布信息在各个站点之间传播,确认与概念空间有强相关关系的特征。 传播激活的基本过程如下: 假设我们要在表一中发现Sam、John、Bob组成的集合的特征。 在传统的方法中使用自顶向下的方法从一个空的规则开始,然后生成形式如城市=“匹兹堡”,汽车=“Corvett“,城市=“纽卡斯尔”的连接,最后再使用表中数据来比较生成每一个连接。 表14-2汽车销售记录表 姓名 城市 汽车 萨姆 匹兹堡 Corvette 约翰 匹兹堡 Cutlass 鲍勃 纽卡斯尔 BMW 提姆 洛杉矶 BMW 玛丽 纽约 Jaguar 而传播激活的方法则是通过对每一个数据项使用加减号标记来完成比较步骤。 如果元组属于由萨姆、约翰、鲍勃组成的集合,则对相应元组的每一个属性用加号标记;反之,则用减号标记。 最后产生结果如图14-3所示。 在属性连接中传播这些标记,学习算法通过计算相应节点上加减号的个数来检查谓词的覆盖范围。 这样通过传播激活替代了传统分类算法中的比较步骤。 图14-3传播激活图示例 Tumer等人提出了整体学习方法与异构的本地分类结合的方法[],这种方法通过序列统计的方法消除各个局部模型不一致的问题,最后产生一个一致的全局模型。 Park指出任何全局模型不可能由合并异构的局部分类器来获得[]。 为了获得这种模型,他们首先找到一组不能由局部分类器分类的子数据,然后将这些数据合并到中心站点,并由此生成全局分类器。 这种方法的性能比前面所提到的方法要好,然而这种方法的性能与数据集的大小紧密相关。 14.3数据挖掘软件发展 随着数据挖掘研究的深入,针对不同的业务需求人们开发了许多数据挖掘系统。 目前有数百个数据挖掘软件产品(),这些系统用途各异,功能也各不相同。 因此需要对数据挖掘系统进行分类,从中总结数据挖掘系统的发展趋势。 目前已经有学者从事该方面的研究,美国学者Grossman和Grego
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- DWDM 14