面向服务的分布式数据挖掘.ppt

1、1,面向服务的分布式数据挖掘,刘军丹 2011-04-29 /portal/web/csdl/doi/10.1109/MIC.2006.88,2,主要内容：,综述。 数据挖掘趋于分布式。 数据挖掘趋向于面向服务。 基于BPEL4WS的DDM处理。 使未经过检查的数据有意义。 局部数据抽象分层。 从局部抽象得到全局模型。 DDM的两个应用。 积极开发自主的DDM 。 未来的工作。,3,综述,数据挖掘如今面临着两个挑战 ： 如何使数据挖掘服务具有即时性和自主性； 如何挖掘分布式的和具有私密性的数据 . 为了解决这些问题，作者采用了BPEL4WS（基于web服务的业务流程执行语言）

2、的面向服务的DDM （分布式数据挖掘）平台来编辑DDM的服务组件，并且满足全局性的数据挖掘需求。他们也使用了从抽象学习（learning-from-abstraction）的方法来实现对隐私保护的DDM。最后他们举例说明如何在隐私性政策强制添加的进程中实现小范围自治，以帮助实现面向服务系统的自治。,4,大多数的数据挖掘算法假定，为了随后进行的频繁的数据运算，数据分析人员愿意聚集从服务器的产生式系统中提取的数据。然而，在实际情况中有的涉及到了数据的隐私问题（例如，存储在银行服务器中的客户信息）以及受到数据传输时的带宽限制（影响远程实验室中的仪器或者超级计算机TB级字节的科学数据的传输）。 研究表

3、明，随着上述这些情况的增多，为了挖掘数据而进行数据的聚集几乎是不可能的。相反，寻求一种保证数据私密性的分布式数据挖掘算法是十分必要的。另外，在当今变化莫测的市场中，需要在恰当的时机为人们提供准确的信息以支持商业决策。人们事先并不知道数据隐私的要求，能否提供面向需求和自适应的服务以便使这些公司能够处理来自异构数据库中的数据，这些需求对分布式数据挖掘（DDM)提出了新的挑战。,综述,5,我们可以从两个方面来说明这些挑战： 1 、分布式数据计算架构是否可以支持无缝整合、集成以及协调实时性和自主性的数据挖掘服务。 2、具有潜意识的保密的数据挖掘算法能否在框架的顶层执行。 在这篇文章中，描述了他们创造的

4、一种新颖的分布式数据挖掘（DDM）算法：面向服务的从抽象学习（learning-from-abstraction）的平台，这种平台的底层处理采用BPEL4WS语言。他们使用一种基于模型的方法来抽象化局部数据和分析全局数据。,综述,6,这种方法有如下优点： 控制数据隐私； 在进行数据挖掘的同时，能减少互联网的信息传输量； 减小对全局数据分析计算的复杂性； 支持自我调整的数据挖掘过程。 他们通过两个具体DDM应用来解释他们的方法：分布式数据聚集和分布式数据多种可视化。,综述,7,数据挖掘趋于分布式,现存的DDM项目大多数是通过构建一组“分布式”专家服务来解决问题，其中每一个服务都有特殊的应用目的（

5、有的进行数据清洗、有的进行数据预处理、有的进行数据挖掘）。为了自动构建每一步，人们经常使用规划算法，有时结合一个数据挖掘过程本体。 然而在这篇文章中作者对“分布式”有另一种理解。他们的兴趣点在于发现完全数据集中隐藏的模式。其中，这些数据集在逻辑上是分区的，物理上分布在不同的数据源上。（这两种关于DDM的概念绝不是孤立，而在一个完整的DDM平台上是共存的。）一个全局性的中介性服务协调了一组相同功能的专家服务，每个服务用同样的方式处理同一问题的不同部分（也就是说，在不同数据分区上执行局部分析处理）。然后，这个中介服务在局部结果的基础上进行进一步的分析从而得到全局性的结果 。,8,数据挖掘趋于分布式

6、,这篇文章描述了关于DDM的不同方法,分布式的关联规则挖掘几乎是最具有代表性的和广泛研究的数据挖掘实例。当然，Andreas L. Prodromidis 和Philip K.Chan已经考虑到一种结合基于水平分割（按记录分割，不同的记录可以分开保存，每个子表的列数相同。）数据的决策树分类器的元学习过程。 Hillo Kargupta和他的同事第一次提出了集合数据挖掘，它适用于垂直分割数据，如果这些数据集是正交集的话能够结合局部数据源的直接结果。异质性存在于各级隐私涉及的不同局部数据源中，因此一些调查研究平衡这两方面的冲突性需求数据隐私和挖掘精度。,9,数据挖掘趋向于面向服务,SOAs（面向服

7、务式架构）是通过连接能完成特定任务的独立功能实体实现的一种软件系统架构。由于最近形成的Web服务相关的标准和技术，使得这个概念在过去几年很盛行，这些标准和技术包括WSDL（web服务描述语言），UDDI（通用描述、发现与集成服务，是核心的Web服务标准之一），SOAP（简单对象访问协议）。 可行的web服务（Web-service-enabled） SOAs现在被按需计算以及发展更具互通性的组内或组间系统广泛地接受。（虽然这些发展处于不同的发展阶段，取决于SOA的架构级别。）,10,数据挖掘趋向于面向服务,基于Agent的分布式挖掘环境(DAME; Distributed Agent-base

8、d Mining Environment) 以及XML分析（XMLA;XML for Analysis是一种关于客户端应用程序访问多维或OLAP数据源的标准），数据挖掘服务请求借助网络以XML语言的格式由电子服务（e-service）实现。 文中介绍了几个与DDM服务提供有关的项目。 Weka4WS (使Weka 在网格环境下支持分布式数据挖掘的一种框架) 和 Gridminer (网格数据挖掘系统)通过使用一种网络计算工具软件提供DDM服务，这种软件是应用于网格（grid，一个新兴的中介标准）上的一种开源的、面向服务的软件开发工具包，事实上是一种新兴的资源共享的中间件标准 ，例如计算能力，T

9、B级字节的存储以及可信任的知识库。在这些项目中，DDM服务流由间接服务或中介服务组成（有时从图形用户界面获得帮助）然后这些服务流以协调和控制的流动方式执行。,11,数据挖掘趋向于面向服务,采用SOA（面向服务架构）至少有以下三方面的优势： 1 可以使得我们集中精力进行数据挖掘服务，而不必去处理类似消息传递协议的连接细节； 2 通过简单地创建和发现新服务，我们很容易扩展和修改DDM的应用程序，指定相关介质来重置服务流声明； 3 它使得面向需求的DDM成为可能。 因此使用者可以仅仅关心他们的商业或科学问题而不必担心数据挖掘的实现问题。通常情况下，SOA（面向服务架构）作为基础可以使DDM的开发程序

10、的重点从算法实现转变到发现下一代DDM应用程序的算法。,12,数据挖掘趋向于面向服务,我们提出的SOA框架采用了现有DDM系统的Web服务标准。我们使用WSDL（Web服务描述语言）来规范DDM的组件如何在缓解互联网压力下输入和输出它们的功能，这就需要准确指定它们的端口，端口类型和绑定（消息传输协议）方法。另外，我们可以设置UDDI（通用描述、发现与集成）服务软件库，这样DDM服务提供者可以对DDM组件服务功能的高级描述进行说明和分类，使得服务使用者很方便的发现它们。 对于具体的面向服务的DDM应用，我们可以把相关服务“融合”一体形成对应的服务流来开发系统。,13,基于EPEL4WS的DDM处

11、理,WSDL支持一种简单的仅仅包括输入和输出的无状态的交互模型。不是用来处理长期运行的有状态的服务提供者和使用者的交互。然而，多数的DDM要求使用这样的交互模式，尤其是涉及到多方面的业务流程 。 业内人士提出了多种标准来说明相应的长期运行的交互模式，包括WSCI （Web服务协作接口），WSFL（网络服务流程的叙述语言，WSFL是IBM公司制订的作为叙述网络服务流程的语言，其包括流程模型和总体模型）以及XLANG（是一种扩展的WSDL语言）。最终，IBM和微软公司将其提出的WFSL及XLANG组合到BPEL4WS中，形成目前关于指定业务流程行为的业界标准。,14,基于EPEL4WS的DDM处理

12、,BPEL4WS通过网络服务端口为业务流程及它的伙伴之间的特定交互定义了模型及语法规范。Web服务之间的关系表现为合作链接（）和进程（）主要定义了在多个合作服务之间采取什么样的交互方式实现业务目标。交互可能是时序的()并发的()或者是有条件的()。BPEL4WS也同样定义了处理特殊业务及引入补偿的机制，在发生异常或者某个伙伴请求撤销时起作用。 作者采用了 BPEL4WS来说明DDM过程业务的目标及过程成为数据挖掘要求，并为执行有关的DDM服务组件定义了次序。目前的业务关系是局部和全局组件服务的角色关系。采用BPEL4WS意味着只要保证必要的DDM组件服务可以满足，我们只需要以服务流的形式说明D

13、DM的应用，通常直接采取无环图的形式(DAGs)。,15,基于EPEL4WS的DDM处理,图1说明了一个以BPEL4WS描述、以无环图形式实现可视化的DDM执行方案。只要我们精确的定义了BPEL4WS的描述，BPEL4WS的中间件可以自动处理执行服务的后续部分，异常处理过程及服务质量都将达到最佳性能。换句话说，DDM的应用程序开发人员可以只关注数据挖掘本身。这种方法的另一个优点是可以重复使用先前服务流程的组成部分，进一步加强DDM应用开发的灵活性。,16,使未经过检查的数据有意义,我们采用从抽象学习的方法使SOA（面向服务式架构）具有隐私控制能力。与借助端口控制规则保护数据的方法不同，从抽象学

14、习的方法一般只对从数据中发现数据模式感兴趣，对外只显示局部数据的抽象分析 。局部数据的拥有者使用隐私规则控制数据的粒度级别，并规定隐私保护程度。特别的，我们定义了一个类似于GMMs（由粗到细的连续的高斯混合模型）的局部数据泛化。然后直接基于局部数据泛化使用不同的潜在变量模型学习进行全局数据分析,每一种都有一个特定的可控粒度级别。,17,局部数据抽象分层,假定分布式数据源包含特征向量形式的数据项 ，我们把每个数据源抽象为一个参数形式的概率密度分布函数。GMM可以作为任何多模式的分布式数据的逼近器，是一种基于向量表示形式的理想数据建模。（向量的形式已经广泛应用于描述性的程序诸如文档、传感器的信号接

15、收以及客户的兴趣档案） 给出如下公式 其中 表示混合比，满足 。并且 表示第l个数据源的第j个高斯分量的参数包括期望 和协方差矩阵 .,18,局部数据抽象分层,我们不可能满足所有数据源的所有要求，因此我们把每个局部数据源描述为GMMS模式的一个分级，最低粒度级的数据源包含一个高斯分量（全部的数据由期望和方差概括）并且最高粒度级包含一系列的高斯分量等价于数据（也就是说，一个分量代替一个数据点）。在任何特定时间，从外部观察到的每个局部数据源仅仅是一个脱离整个抽象层次的在特定粒度级别的GMM抽象，这使得我们可以控制局部数据的隐私性。 一个在低粒度级的GMM很明显的比在高粒度级提供的信息少（也就是说，

16、隐私性更强）。在带宽方面，如果第l个数据源的数据总量 非常大，而粒度级别允许的数据量通常会比 低。因此，所要求的带宽很低了与传输数据相比，传输参数通常需要很低的的带宽。,19,局部数据抽象分层,为了计算局部数据抽象分层，我们需要在每个泛化级上反复的应用传统的“期望最大化”（EM）的算法。然而，这可能太费时间。考虑到泛化主要是隐藏数据的具体值，通常可以在一定程度上牺牲最优性（对于模型的精确性和表示方法的有效性）所以我们可以组合更多的近似算法代替。在实验中，作者采用自底向上的方式用两个简单的步骤进行了数据泛化。首先，分层聚集每个局部数据子集。由于已计算出聚集树（也就是聚集层次）可以迭代的计算树上每

17、个聚集分层的期望和协方差矩阵。,20,从局部抽象得到全局模型,得到从局部数据源聚集的数据抽象（也就是一系列的GMM参数） 后，我们采用基于模型的方法进行全局数据分析。通常，我们可以指定 作为一个全局变量模型，在这里 是指模型的参数具有潜在变量的概率性结构和潜在空间到数据域的映射的特征 。为了得到这个全局模型，全局代理可以为虚拟数据重采样聚集的局部抽象，然后应用所有现有的模型学习（model-learning）技术，例如EM算法。 然而，因为重采样过程可能要进行大量计算因此这种重采样方法并不完全适合于我们的需求。这种方法也没有用到这些知识，即相似的数据对全局模型参数的估计的作用也是相似的。而这些

18、数据点有助于对全局模型参数相似性的估计实际上局部的高斯模型的组件可以捕获这些知识 ，然后就可以利用借助于从抽象学习的方法提高全局模型的学习效率。,21,从局部抽象得到全局模型,这里，我们发现了这样一个事实，考虑到潜变量的值和从潜变量空间到数据域的映射，我们可以假定相应的数据服从一个高斯分布。几个常用的潜变量模型（LVMs），包括GMM，生成的地形图（GTM，generative topographical mapping ）以及隐马尔可夫模型（HMM），可以满足这些假设。这些说明，我们可以为基于数据抽象学习LVMs（潜变量模型）得出一个新的EM算法。关键是理解局部高斯模型分量如何影响不同的LV

19、Ms（潜变量模型）的局部高斯组件的参数估计。尽管我们后来证明从抽象学习的方法与应用程序同时使用GMM和GTM作为局部模型，然而由于篇幅所限我们只涉及了高斯混合模型（GMM）的技术细节。,22,从局部抽象得到全局模型,传统的EM算法通过迭代的执行一个E-step（用来估计由第j个高斯分量形成的数据项的后验概率），以及一个M-step（计算高斯混合模型（GMM）的极大似然参数估计），来最大化高斯混合模型（GMM）观测数据的期望记录的可能性。为了改进传统的E-step以及达到从抽象学习，我们计算个别的局部高斯分量的后验概率（作为总体的抽象）通过全局高斯分量产生 例如 这里 表示两个高斯分量 和 （一

20、个为局部的一个为全局的）KL散度（信息增益、信息散度, 是一个信息度量，通常用来衡量两个概率分布之间的距离。）。,23,从局部抽象得到全局模型,我们以在近似值的修改为基础，那么数据对应于局部分量的后验概率有局部分量决定是恒定的。存在一个KL散度的近似形式 我们可以把前两项看做两个高斯分布的协方差矩阵之间的“区别”，当两个分布的离差（反映了反映了x与其数学期望Ex的偏离程度）相同时前两项为零。第三项实际上是两个高斯均值向量的马氏距离（它用到了协方差矩阵），并且当他们相等时其值为零。如果 的值收敛于零（也就是说，每一分量代表它的数据项），则E-step退化成传统的形式。,24,从局部抽象得到全局模

21、型,对于新的M-step，它是 这里 是作为总体抽象的局部高斯分量总数。我们已经证明了为从抽象学习GTM的E-step本质上是和为学习GMM是相同的。同样的，为学习GTM的M-step仅仅是对原始的GTM的M-step的略微改进。 采用从抽象学习的方法通过系数 ，可以降低关于M-step以及E-step的计算复杂度，在这里N是指数据项的个数。通常情况下， 要比N小得多，因此速度（与重采样的方法相比）是显著的。图2显示了整体的知识框架。,25,DDM的两个应用,经过仔细的执行和测试，成功的证明从抽象学习的方法对DDM的两个不同应用分布式的数据聚集和多面进行分布式可视化的有效性。前者使用GMM作为

22、全局模型，后者使用了GTM作为模型。在面向服务的实现细节上，这篇文章中只讨论了GMM的情况 ，对于GTM来说也是一样的。第一个执行程序解决的问题是如何选用已有的面向服务的体系结构（SOA）工具的版本. 在实现中，作者使用了Java SDK版本1.4.2以及Apache Axis Web Services Library版本1.2，为开发DDM服务并把它们寄存在服务器上，运行Apache Tomcat version 5.5。我们也使用Oracle BPEL4WS执行引擎10.1.2版本去设计DDM服务取决于the processBPEL4WS指定以及Oracle BPEL4WS Designe

23、r是一个支持可视化模式的Eclipse插件。,26,DDM的两个应用,图一中的1a和1b显示了一个在BPEL4WS指定的流及BPEL4WS引擎执行后产生的审计报告的一部分的可视化。他们是一个特殊的尝试用三个局部数据源即存在三个不同的服务器上，每一个Web服务在约定的数据粒度级上提供局部数据抽象。我们在第四层服务器上部署全局中介作为另外一个Web服务。每一个局部数据集包含167个二维数据值。我们设定进行数据抽象的元组的个数，从每个局部数据源中抽取10个全局数据源中抽取5个。,27,DDM的两个应用,图3和图4显示了全局GMMs(K=5)和GTMs各自基于不同的数据粒度级别的局部数据抽象的质量。图

24、3a到图3d显示了GMM的情况，只有当粒度级别显著的减小时聚簇的中心开始偏离正确值。图4显示了GTM的情况，在这不同颜色表示相应的数据有不同的类标号。原有的GTM学习正确的展现（分开）了三种类型的数据在二维摄影空间分离并且同时为可视化保留数据的拓扑结构的潜在可能性。随着数据粒度级别降低（图4b到图4d），展开（分开）的类数开始逐渐降低，同时一些不同类型的数据开始互相重叠。 图3和图4也显示了学习的收敛时间。以GMM和GTM为例，与传统的没有使用局部数据抽象的情况相比，加速的比率分别为从3到10和1到24。与传统的方法相比，关于GMM和GTM的精确度及加速比率的更多的经验评价在其他地方也可以得到

25、。,28,积极开发自主的DDM,他们提出的从抽象学习的方法结合SOA平台对实现具有保密意识的DDM提供了必要的机制。实际上，分布式的环境具有不同的不确定性方面，这就要求DDM的组成服务去适应自治。DDM的组成服务，包括数据提供服务和数据挖掘服务，必须自主的决定是否共享（信任和访问控制），共享什么（数据粒度级别）以及哪个服务最适合它（一个数据为主的透视）等等。为了满足特定的数据挖掘的需要，这些数据服务代理和数据挖掘服务代理彼此之间可以积极自主协商发现最好的方式来得到最好的结果。,29,积极开发自主的DDM,为了解释自主的DDM，我们做了一个实验用GMM作为全局模型来证明如何通过自治在整体数据挖掘

26、质量和局部数据源的粒度级别之间达到最好的权衡。我们不是假设隐私控制组件是被动的，而是执行有自治特性的局部数据源去和全局中间服务协商在哪个数据抽象级别去呈现。全局的中介首先要求一个来自每个局部数据源的低粒度级别数据抽象。然后，他主动的要求更多的来自这些数据源的需要知道的（need-to-know）详细的细节，以便它可以用一个有效的方式学习全局模型 。 例如，全局的中介服务可以送局部数据源到全局模型尽量学习一直到一个特定的时刻，这时局部数据源可以返回它们的基于局部数据可能性（定义为产生数据的概率）计算得到的投标值（bid values）得到每个单位成本（per unit cost），通过在局部数据

27、源上提升一个粒度级。全局服务将会要求来自有更高返回值的源的更多的数据详细资料。这个协议一直持续到数据可能性停止显著的增长或计算的预算用完。,30,积极开发自主的DDM,图5显示了这种主动探索的分布式聚集的模拟结果。模拟经历了六个连续的迭代，每次都涉及到了一个完整的从抽象学习的过程。在每一次迭代的过程中，我们基于在先前的迭代中的聚集GMM初始化全局GMM。图5a到图5d显示了在前四次迭代，全局中介为得到一个更详细的抽象一直询问数据源1（蓝色的三角形代表它的数据）以帮助解决最左边三个聚簇的不精确性。 图5e和图5f显示了全局中介转换到数据源2（数据以红加号显示）以得到更多的细节来解决最右边两个聚簇

28、的不精确性。所有的迭代通过一个简单的命令程序来实现独立和自治。对于将来的研究，应该是值得使用一个更正式的数学框架（比如一个风险理论）公式化主动开发过程。,31,未来的工作,当DDM趋于面向服务的时候，它不能仅仅以一个被动的面向服务的数据挖掘中介软件结束。在这个研究领域的研究人员应该考虑新的因素-比如说自治的各个方面-这可能帮助数据拥有者和数据分析专家在数据挖掘领域平衡准确性和隐私性以得到最好的“分配”。 通常情况下，我们相信发现更好的方法去控制和管理所关心的例如精确性，隐私性，有效性，以及资源利用率将继续推动DDM将来的研究和发展。当前，我们正在研究如何在局部数据抽象中引入一个适当的定量的隐私性测量。我们也正在研究使用一个更正式的框架描述自治的DDM的性能。,32,谢谢！,33,分布式数据挖掘服务流。来自三个局部数据源，每个数据源包括167个数据。（a）用BPEL4WS详细说明服务流。（b）特定的流执行后由BPEL4WS引擎产生的审计报告,34,图2.基于模型的分布式数据挖掘示例。局部数据源的拥有者首先抽象化数据为高斯混合模型然后送到全局中介进行聚集。应用