（计算机软件与理论专业论文）分布式环境下的数据挖掘算法的研究与实现.pdf

分布式环境下的数据挖掘算法的研究l j 实现筇1 页共5 3 负 摘要 随着网络技术的发展和计算机使用的f = 1 益广泛，电子化数据越来越多，人们 【1 i 面f 临“数据丰富而知识贫乏”的问题。数据挖掘技术为解决此问题开辟了一条 道路，并越来越受到人们的重视。但随着数据集规模越来越庞大，且多为分卸存 储，单台计算机的资源对于挖掘大规模数据集越来越无能为力，所以在分布式环 境r 进行数据挖掘算法的研究显得尤为重要。 对分布式算法的研究主要有两个途径，一个是改造现有的串行算法，使之适 应分布式并行环境：另一个则是设计全新的分布式并行算法。由于前一种方法容 易进行工作衔接，而且能够充分利用已有的集中式环境下的研究成果，所以被广 泛采用。 我 f 1 提出了一个分如式聚类算法g d b s c a n 。g d b s c a n 算法主要是在经 典的基1 二密度的d b s c a n 算法的基础上进行改进的，并结合了空间矩形覆盖算 法g m d l 。在各个局部节点，g d b s c a n 算法用d b s c a n 算法产生局部模型， 并使用g m d l 算法对局部模型进行近似处理，以减少传输到中央节点的数据量。 中央节点根据局部节点提交的局部模型，使用空间分格以及我们改进的 r d b s c a n 算法得到全局模型，并使用g m d l 算法对模型描述进行简化。最后 将全局模型发送到各个局部节点以更新局部模型。 另外，利用g - d b s c a n 算法，我们还开发了一个网格环境下的分向式聚类 挖掘系统g c 系统，并使用g c 系统对g d b s c a n 算法进行了评估。 关键词：分粕式，网格，聚类挖掘，基于密度 分类号：t p 3 1 1 复口人学硕t ：学位论文 坌塑些! 垫! 堕垫塑丝塑竺堕塑! 壅兰壅型塑! 墨苤塑墨 t h er e s e a r c ha n d i m p l e m e n t a t i o no f d a t a m i n i n g a l g o r i t h m s i nad i s t r i b u t e de n v i r o n m e n t a b s t r a c t w i t ht h ed e v e l o p m e n to fn e t w o r kt e c h n o l o g ya n dt h ew i d eu s a g eo f c o m p u t e r s ， t h e r ea r em o r ea n dm o r ee l e c t r o n i cd a t a ，a n dp e o p l ea r en o w f a c i n gt h ep r o b l e mo f “r i c hd a t am a d p o o rk n o w l e d g e ”d a t a - m i n i n gt e c h n o l o g y b l a z e saw a yi nt h i s p r o b l e ma n di st h o u g h tm o r ea n dm o r ei m p o r t a n tb yp e o p l e b u tn o w d a t as e t sa r e b e c o m i n gl a r g e ra n dl a r g e ri ns c a l e ，a n dm o s t o ft h e ma r ed i s t r i b u t e d ，t h er e s o u r c eo f as i n g l ec o m p u t e rc a nd oa l m o s tn o t h i n gi nt h em i n i n go fs u c hl a r g ed a t as e t s s oi ti s i m p o r t a n t t od os o m er e s e a r c ho ft h e d a t a - m i n i n ga l g o r i t h m s i nd i s t r i b u t e d e n v i r o n m e n t t h e r ea r et w ow a y si nt h er e s e a r c ho f d i s t r i b u t e d a l g o r i t h m s o n ei st oi m p r o v e a s e r i a la l g o r i t h ms ot h a ti tc a nb eu s e di nt h ed i s t r i b u t e de n v i r o n m e n t ，a n dt h eo n ei st o d e s i g naw h o l en e w d i s t r i b u t e dp a r a l l e la l g o r i t h m t h ef o r m e ro n ec a nf u l l yr e u s e d t h er e s e a r c hr e s u l t si nc e n t r a l i z e dm i n i n g ，s oi ti sw i d e l yu s e d w e p r o p o s e an e wd i s t r i b u t e dc l u s t e r i n ga l g o r i t h m ，g - d b s c a n g d b s c a ni s b a s e do dt h ec l a s s i c a l d e n s i t y b a s e da l g o r i t h md b s c a n a n dc o m b i n e sw i t h t h e r e g i o n c o v e r i n ga l g o r i t h m ，g m d la l g o r i t h m i ne a c h l o c a ln o d e ，d b s c a n a l g o r i t h m i su s e dt o g e n e r a t eal o c a lm o d e l ，a n dt h e ng m d la l g o r i t h mi sa p p l i e dt og e t a n a p p r o x i m a t em o d e l ，s o t h a tt h ed a t as i z et r a n s f e r r e dt ot h ec e n t r a ln o d ec a nb er e d u c e d b a s e do na l ll o c a l r e p r e s e n t a t i v e s ，t h e c e n t r a ln o d eg e n e r a t e dt h e g l o b a l m o d e l f i n a l l yt h eg l o b a lm o d e l i ss e n dt oe a c hl o c a ln o d et ou p d a t et h e i rd a t ai n f o r m a t i o n a n d b yu s i n gg d b s c a na l g o r i t t u n ，w ed e v e l o pad i s t r i b u t e dc l u s t e r i n gs y s t e m ， g c ，i ng r i de n v i r o n m e n t a n dw e d os o m ee v a l u a t i o nf o rg d b s c a n a l g o r i t h mv i a g c s y s t e m k e yw o r d ：d i s t r i b u t e d ，g r i d ，c l u s t e r i n g ，d e n s i t yb a s e d 复旦犬学硕士学位论文 1 1 数据挖掘简介 第一章引言 计算机和通讯技术的发展，使得我们这个社会越来越依赖信息，而大多数的 信息都以最原始的方式数据的形式存在。如果数据可以看作是人们记录的事 实，则信息就是数据中暗含的一组规则，或者况是期望。在过去的数十年中，随 着网络和存储技术的发展以及条形码在大部分商业产品中的广泛应用，商业公司 和政府机构办公自动化逐步普及，数据采集工具迅速发展，这一切使得我们产生、 收集和存储数据的能力已经迅速提高。这一切将我们淹没在数据的海洋中，而“丰 富的数据与贫乏的知识”问题也r 益突出。不同领域的人们都期待着从这些数据 中得到自己想要的答案，将数据转化为信息，从数据的矿山中找到蕴涵的知识金 矿。 数据挖掘( d a t am i n i n g ) 正是这样一种从数据中挖掘信息的工具，它集数据 收集、数据清理、降维、规则规约、模式识别、数据结果分析及评估、可视化输 出等多种过程于一身，是数据库技术、人工智能、机器学习、神经网络、统计学、 模式识别、知识库系统、知识获取、信息检索、高性能计算和数据可视化相结合 的产物。它出现于2 0 世纪8 0 年代后期，9 0 年代有了突飞猛进的发展，并可望 在新t - 年中继续繁荣。实际上，世界5 0 0 强企业中的8 0 都涉足数据挖掘的前瞻 性研究或拥有一个或多个数据挖掘产品系统。它们帮助企业进行客，1 关系管理， 减少不必要的投资，提高资金周转和回报；帮助人们迅速获取所需的知识和信息， 提高工作效率，改进服务质量。它让人们有能力最终认识数据的真正价值，即真 正认识蕴藏在数据中的信息和知识 a i s 9 3 ，c h y 9 6 】。 目前，对数据挖掘有广义的和狭义的两种理解。 广义的理解认为数据挖掘即数据库中的知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e ，k d d ) ，即从大规模的数据库中抽取非平凡的、隐含的、未知的、有潜 在使用价值的信息的过程 f p s 9 6 a 1 。 狭义的理解认为数据挖掘是k d d 的一个步骤。k d d 为从数据中识别正确 的、新颖的、有潜在使用价值的、最终可理解的模式的非平凡的过程 f p s 9 6 b 1 。 它包括数据选取、数据预处理和数据清洗、数据挖掘、知识评估等多个步骤。数 据挖掘足其中对经过预处理的数据进行处理，抽取知识的过程。 数据挖掘可以在众多的数据库上进行，包括关系数据库、数据仓库、事务数 据库、面向对象的数据库、对象一关系数据库、空间数据库、文本数据库和多媒 复且大学硕士学位论文 分布武环境下的数据挖掘算法的研究lj 实现始4 页共5 3 页 体数据库、异种数据库和遗产数据库以及w w w 。 数据挖掘的任务一般可分为描述和预测两类，其中描述性数据挖掘任务刻划 数据库中数据的一般特性，预测性数据挖掘任务在当前数据上进行推断，咀进行 预测。而数据挖掘的功能指定了数据挖掘任务中要找的模式类型。j i a w e ih a n 在 ( ( d a t am i n i n g ：c o n c e p t & t e c h n i q u e s ) ) 【n k o o 中，将目前的数据挖掘技术主要分 为以下几类：概念描述、关联分析、分类和预测、聚类分析、例外分析、趋势分 析。 夺概念描述( 特征描述和区分) 数据可以由定的概念和类来抽象表示人们对其关心的那部分性质。分别简 单明了地描述这些概念和类显然是非常有用的。关于这些概念的描述称为概念描 述( c o n c e p td e s c r i p t i o n ) ，它包括了特征描述和区分。 夺关联分析 关联分析( a s s o c i a t i o na n a l y s i s ) 是在一个给定的数据集中发现经常同时发生 的多个属性值条件( 般称为关联规则) 的过程，最常用于市场销售和事务数据 分析。但日| j ，其应用范围也日益拓展。 夺分类和预测 分类( c l a s s i f i c a t i o n ) 是指为了能够使用模型预测类标签( c l a s sl a b e l ) 还未 知的对象所属的类，而寻找可以描述和区分类或概念的模型的过程，其中类标签 指用来区分类的属性。包括两个步骤：通过分析训练数据空间中的数据，运用分 类算法，建立分类模型；用测试数据空间中的数据估计己建立的模型的预测准确 性，如果用户可以接受，则用该模型对未知其类别的数据进行分类预测。所谓预 测( p r e d i c t i o n ) ，专指对丢失或无效的数据的值的预测。 夺聚类分析 聚类分析( c l u s t e r i n ga n a l y s i s ) 是一个将指定数据集中的数据进行归类的过 程。其遵循的原则是每个类内部各对象间的相似性尽可能最大，而不同类对象间 的相似性尽可能最小。在具体实现中，一般用计算对象属性的距离( 欧几罩德距 离、曼哈顿距离等) 来体现对象间的相似度。 夺例外分析 一个数据库中的数据可能不都遵循总的数据模型的行为，这些数据称为例外 ( o u t l i e r ) 。通常数据挖掘方法把例外作为垃圾而抛弃，不过在一些场合下，比如 欺诈检测中，例外却成为了最受关注的焦点。例外分析大致有统计、基于距离、 基于偏差三种方法。 夺趋势分析 数据趋势分析( e v o l u t i o na n a l y s i s ) 描述对象行为随时问变化的趋向和规律。这 复旦大学硕，f j 学位论文 分布式环境下的数据挖掘算法的研究与实现 个概念和特性描述、关联分析、分类、与时问相关的数据的聚类都有些类似，然 而前者更强调对时序( t i m e s e r i e s ) 数据的分析、有序和周期性模式的匹配、基 丁 相似度的数据分析。 1 2 分布式数据挖掘 近几年，数据挖掘的研究有了很大进展。但是，随着数据规模的不断扩张， 也出现了很多新的问题： 夺现在的数据挖掘算法和模型主要采用集中式，即使在数据分布存储的情 况下，也要求把这些数据重新收集到一个集中的地方( 如数据仓库) 以 进行挖掘。由于数据挖掘的目标一般是大规模的数据集，这就要求有高 速的数据通信网络，并且会导致响应时间变长，数据的私有性和安全性 被破坏。虽然网络带宽在增加，但还是比不上数据增长的速度，结果只 能通过有限的网络带宽来移动大容量的数据。这就越来越不适合于大容 量、分布式的数据分析应用。 夺数据规模的扩张，导致对数据进行挖掘所需要的资源如c p u 运算能力、 内存、硬盘等的需求量十分巨大，往往难以由单台机器独自提供。 夺随着w w w 的快速应用普及，i n t e m e t 成为人类历史上最大的数据源， 其中的数据在以几何级数的速度增长。因为i n t e m e t 本身就是一个巨大的 分布式系统，而且数据量巨大，根本不可能把数据收集集中，也就不可 能进行集中式的挖掘。 夺随着无线和移动式计算机越来越流行，要求开发出能挖掘这些系统数据 的算法和系统，而它们本身是分布的，较难进行集中。 夺此外，由于数据的私有性和保密性、系统的不兼容性等方面的原因，把 所有的数据都收集到一个集中式平台中也是不现实的。 所以，在分布式环境下进行数据挖掘算法的研究显得尤为突出。所谓分布式 数据挖掘( d i s t r i b u t e dd a t am i n i n g ，d d m ) ，就是使用分布式计算，从分布式数 据库中发现知识的过程。 目前，开发分布式并行数据挖掘算法主要有两种途径：其一是对已有的串行 算法进行改进，挖掘其中的并行性质并加以利用，使得“串行程序并行化”；其 j 是对蒯题的本质重新审视，设计全新的并行算法。第一种途径相对容易些， 也比较能充分利用已有的串行数据挖掘算法的研究成果，但是并行粒度较小，通 信量较大。第二种途径需要全新设计，但如果成功，就会得到粗粒度并行算法， 适合于在分布式并行机上应用。目前对分布式数据挖掘算法的研究多采用第一种 谂径。 复且大学顺。 ：学位论文 分布式环境下的数据挖掘算法的研究j 实现第6 负共5 3 页 分布式数据挖掘算法的一般过程是：首先，对于分布在各个节点上的数据集 采用相同的串行数据挖掘算法，在各个节点上得到各自的局部模型。随后，所 有的局部模型被整合为全局的最终模型。分布式数据挖掘算法面临的主要问题 有： 1 ) 算法如何进行分解，在保证结果完备性、一致性的基础上实现较大的并 行度。 2 ) 在保证结果准确性的前提下尽量减少网络的通讯量。这就要求在局部数 据模型中应该尽量抽象数拥，但是又不能影响全局模型的整合。 3 1 挖掘数据源若是异构的，那么挖掘得到的局部模型如何整合为全局最终 模型? 其中前两点是相辅相成的。一个设计、分解得好的算法，常常可以大大降低 网络通讯的数据量。 目前，已经研究出了许多分布式数据挖掘的算法。 l h w 0 2 】 分布式关联规则挖掘 在分布式关联挖掘规则挖掘中，有两个典型的分布式关联规则挖掘算法： c o u n td i s t r i b u t i o n ( c d ) 年1 1d a t ad i s t r i b u t i o n ( d d ) a s 9 6 】。c d 算法几乎可以达到 线性加速比。然而，c d 算法有两个缺点。其一是建立哈希树是一个不可并行的 过程。对于串行程序来蜕，建立哈希树占用时间极少。但对于并行程序来说，可 能成为一个影响效率的瓶颈。其二是如果哈希树不能装进内存，那么就必须进行 昂贵的磁盘读写操作。d d 算法通过把候选集划分到各个处理器来克服c d 算法 的缺陷，然而d d 算法在以下方面效率较低：其一是由于数据移动方案效率低导 致通信负载较高；其二是处理器问的交互模式易导致处理器处于空闲状惫：其三 是每一笔交易记录都要根据多个哈希树进行处理，导致冗余计算。基于此分析， e u i h o n gh a n 、g e o r g ek a r y p i s 以及v i p i nk u m a r 等人提出了新的关联规则挖掘 算法，称之为i n t e l l i g e n t d a t ad i s t r i b u t i o n ( i d d ) 算法，以改进d d 算法( 通信极 小化和处理器空闲时间极小化) 。然而，i d d 算法的通信量依然随着交易记录的 个数线性增长。为了克服这一缺陷，他们又提出了h y b r i d d i s t r i b u t i o n ( h d ) 算法， 组合了c d 算法和i d d 算法的优点。应该指出的是，上述所有算法都是以经典 算法a p r i o r i 为基础的。 分布式分类器 大多数分布式分类器以“合唱学习”( e n s e m b l el e a r n i n g ) 为基础。许多领域 都采用合唱的方法来提高预言模型的分类准确率。分布式分类器首先由各个处理 器产生多个模型( 基础分类器) ，通常各个处理器中的数掘集是同种的，然后再 组合基础分类器以提高准确率，一般采用“投票”方案( 加权或者非加权) 。 复旦大学硕士学位论文 分布式环境下的数据挖掘算法的研究，实现 “m e t a l e a r n i n g ”框架是一个比较著名的“合唱学习”方案 p s 9 3 a 】 p s 9 3 b p s 9 8 ，它提供了一种从同种分布式数据源中挖掘分类器的方法。 在这个方法中，监督学列技巧被应用于局部数据集上的分类器挖掘，随后通过局 部学习概念来产生一个数据集，m e t a - l e v e l 分类器通过在这个数据集上学列得到。 m e t a - l e v e l 学习可以递归应用，产生多级m e t a c l a s s i f i e r s 。m e t a 1 e a r n i n g 主要由三 步构成： 1 ) 在每一个处理器( 节点) 中应用分类学习算法产生基础分类器。 2 ) 收集基础分类器到中心节点。从一个分离的校验集上产生m e t a - l e v e l 数 据集，并应用基础分类器产生预言模型。 3 ) 从m e t a 1 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 展示了分布式数据挖掘算法的两个特征：高并行性能和低通信 负载。所有的基础分类器在各个节点上同时独立产生，然后和校验集一块被收集 到中心节点上。其通信负载和需要传递整个源数据的并行算法比起来可以忽略。 分布式聚类挖掘 大多数分柿式聚类算法致力于以并行方式执行基于中心的聚类算法，如 k m e a n s ，k h a r m o n i cm e a n s 以及e m i d 9 9 m p 0 0 b m g 0 0 。有两种途径：第 一种是通过聚合方法提供近似的距离度量标准；第二种通过数据广播提供精确的 距离度量。第一种途径易受聚合方式的影响，而第二种方式需要大量的消息通信。 f o r m a n 和z h a n g 【g b 0 0 提出了基于中心的分布式聚类算法，仅仅需要充足的统 计表的交换。p a r t h a s a r a t h y 和o g i h a r a s m 0 0 注意到分布式聚类算法的关键问题 是找到合适的距离度量标准，他们定义了一种基于关联规则的度量标准。然而这 种方法局限于各处理器中的数据表是同类的。m c c l e a n 等人考虑了异种数据表的 分御式聚类算法 s b k 0 0 1 。 1 3 聚类数据挖掘 所谓聚类( c l u s t e r i n g ) ，就是将数据对象分组成为多个类或簇( c l u s t e r ) ，在 同一个簇中的对象之问具有较高的相似度，而不同簇中的对象差别较大。相似度 是根据描述对象的属性值来计算的，距离是经常采用的度量方式。聚类分析源于 许多研究领域，包括数据挖掘、统计学、生物学，以及机器学习。 相比较关联挖掘和分类挖掘而言，聚类挖掘有一个很好的特性，就是聚类挖 掘的结果模式比较“局部化”。聚类挖掘得到的模式的某个部分，只和数据集的 一部分数据有关系，而和整个数据集关联不大。例如，某个数据是否属于某个簇， 往往只和它“周围”的若干数据有关，而与整个数据集没有很大关系。尤其在基 于密度的聚类挖掘方法中，是根据数据空间中局部区域的数据点的密度来区分各 复旦人学硕十学位论文 分布式环境下的数据挖掘算法的研究与实现第8 负共5 3 负 个簇，将簇看作是数据空间中被低密度区域分割丌的高密度对象区域，这一“模 式局部化”特性更加明显。 聚类挖掘的“模式局部化”特性，使得对聚类挖掘的“分布式”改进较为容 易。因为每个分柿的局部站点可以对a 己的局部数据集分别独立地进行挖掘，而 相互之白j 的影响比较小。因此，我们选择聚类挖掘作为切入点，研究分布式环境 卜的聚类数据挖掘算法。 1 4分布式聚类挖掘算法基础 前面提到，目前丌发分布式并行数据挖掘算法主要有两种途径：其一是对已 有的串行算法进行改进：其二是对问题的本质重新审视，设计全新的并行算法。 我们采用第一种途径，因为它比较能充分利用已有的串行数据挖掘算法的研究成 果，并且难度较小。 1 4 1 分布式聚类的基本概念 夺分布式环境 这里所说的分稚式环境，是指若干台在逻辑上独立的计算机，相互之阳j 主要 通过网络连接。其中有一台或者多台起主要作用的计算机，称为中央节点，记为 c 。其余的计算机称为局部节点，记为l 1 ，l 2 ，l n a 夺局部数据集 每个局部节点上的数据集称为局部数据集。考虑到节省网络通讯的因素，我 们规定，局部节点只能对它自身的局部数据集进行挖掘。l i 上的局部数据集记为 d i 。 冷全局数据集 n 全局数据集是各个局部数据集的并集，记为d ，即d 。u d ，。 f = l 夺局部模型 局部模型是指在局部节点l i 上对其局部数据集d ，进行聚类数据挖掘所得到 的结果，记为m 。 夺局部代表 局部代表是对局部模型的近似表示，记为r i 。考虑到节省网络带宽，不可能 将整个局部模型都传到中央节点，而只能用少量的局部代表来近似表示局部模型 的信息，并将局部代表传递到中央节点进行分析。一个局部模型可能由若干个局 部代表共同表示。 分布式环境f 的数据挖掘算法的研究与实珧第9 负共5 3 负 夺全局模型 所有局部代表产生后，集中到中央节点，综合分析后得出的结果称为全局模 型，记为m 。全局模型是整个分布式聚类算法的最终运行结果。 夺分布式聚类挖掘任务 分布式聚类挖掘的任务，就是产生与集中式挖掘相近或者相同的挖掘结果。 由于m 是独立产生的，而d ；之间有可能存在依赖性，所以可能会产生误差。尽 量减少误差是算法的改进目标之一。 1 4 2 分布式聚类算法结构 根据局部节点之间是否相互独立，分布式聚类算法的结构可以分为两类。 第类算法结构中的局部节点是不独立的，除了与中央节点通讯之外，局部 节点之间也有大量的通讯，以协调局部模型的建立。这类算法的优点是由于局部 ：前点之间互相协调，可以发现局部数据集之间相互依赖的部分，从而有助于建立 更加精确的局部模型。但是缺点也很明显，一方面大大增加了对网络带宽的占用， 另一方面对整个系统的稳定性要求也很高，如果有少数局部节点发生故障，对算 法的性能影响比较大。 第二类算法结构中的局部节点之间是相互独立的，除了与中央节点通讯之 外，局部节点之间基本上不通讯，这样对网络带宽的占用就小得多。而且即使少 数局部节点发生故障，对整个算法的影响也比较小。对于这类算法而言，关键技 术是局部代表的产生以及根据局部代表建立全局模型，这两个步骤对算法的总体 性能和准确度影响很大。第二类算法结构是我们的主要研究对象，以后文中所称 的“分布式聚类算法”也主要指采用第二类算法结构的分布式聚类算法。 分布式聚类假定所有需要聚类的对象分布在不同地点的局部节点l i 。局部数 据集d 在l i 单独地进行聚类，而不是传输到中央节点c 进行常规的聚类分析。 c 根据l 。所产生的局部模型m i ，建立全局模型m j k m 0 3 。相对于整个数据集 d ，对m 进行聚类要快得多。而m ，的产生可以由多台计算机并发进行。因此一 般米说，分抑式聚类算法比起相同数据集上的集中式聚类算法运行速度更快。 分佑式聚类是在两个不同层次上分别进行的，即局部层与全局层，参见图 1 1 。 在局部层中，所有的局部节点l i 相互独立地在本地数据集d 上进行聚类挖 掘。聚类结束后，每个客户端产生局部聚类模型m i 。在每个客户端的局部模型 中，对每个簇，产生一些局部代表r i 。这些局部代表必须是能够反映这个簇的特 性的。 然后，在全局层，各个节点的局部代表被传输到中央站点以产生全局模型。 复旦大学硕士学位论文 分布，c 环境下的数据挖掘算沾的研究r ，虫蜕 由于局部代表比起整个数据集来说少得多，这就大大减少了网络通讯量。 伞局模犁产，e 后，发送到局部展中的各个局部节点以用于更新局部模型。冈 为也许在某个局部节点中，两个数据点分属于不同的簇，但是在中央节点中，综 合其它局部节点的信息，这两个数据点最终处于全局模型中的相同簇中。另外， 局部模型中的噪声点，也有可能经过其它局部节点信息的综合，而属于全局模型 中的某个簇。 硒帮节点i 1辟醯节点l 2廊郎节点h j d 丽戥槲蜒ll 肺档越抛挺i ) ：! ll 蠲1 1 ；彀捌f 融1 ) n 硒帮壤粪 褂剿埘1 1 1 5 摊搿 i 确定埘部代表 r i 鼬赧聚凳 褂i 坷挪模型 雌 确赶射舯代袁 融 辟 i i ；壤擞 村黜局揶坦州 碓超硒部代衰 r n 全局模罐m 蜓瓢蛐部填型 m l 蜓新蛐鄙懊艘 螗 型毹 d 摄挺删 图1 - 1 ：分布式聚类算法结构 总的来既分和式聚类包括以下四个1 i 同步骤 1 1 局部聚类，确定局部模型； 2 1 产生局部代表； 3 1 基于所有的局部代表，确定全局模型； 4 1 利用伞局模璎，更新各个局部模型。 1 5分布式新技术网格 ；6 讳鬟 书目艇 蜀椰辊 5 _ ) - 4 j j 式技术本身也是在小断发展中的。最早的分布式环境往往只是局限于同 一个局域网内并且要求各个节点的软件环境相同。随着广域网技术以及互联网 的发展，分布式环境的跨度越来越大，特别是w e b 服务技术的提t h , ，使得不同 体系结构、不同操作系统的节点可以加a 到同个分稚式环境中。而近几年来， 复旦大学坝土学位论文 分布式环境下的数据挖掘算法的研究j 实现第1 0 贞共5 3 虹 由于局部代表比起整个数据集来说少得多，这就大大减少了网络通讯量。 全局模型产生后，发送到局部层中的各个局部节点以用于更新局部模型。因 为也许在某个局部节点中，两个数据点分属于不同的簇，但是在中央节点中，综 合其它局部节点的信息，这两个数据点最终处于全局模型中的相同簇中。另外， 局部模型中的噪声点，也有可能经过其它局部节点信息的综合，而属于全局模型 中的某个簇。 图1 - 1 ：分布式聚类算法结构 总的来说，分布式聚类包括以下四个不同步骤 1 ) 局部聚类，确定局部模型； 2 ) 产生局部代表； 3 ) 基于所有的局部代表，确定全局模型； 4 1 利用全局模型，更新各个局部模型。 1 。5分布式新技术网格 分布式技术本身也是在不断发展中的。最早的分布式环境往往只是局限于同 一个局域网内，并且要求各个节点的软件环境相同。随着广域网技术以及互联网 的发展，分布式环境的跨度越来越大，特别是w e b 服务技术的提出，使得不同 体系结构、不同操作系统的节点可以加入到同一个分布式环境中。而近几年来， 复旦大学硕士学位论文 分布武环境下的数据挖掘算法的研究与实现第l l 页共5 3 页 最热门的分布式技术莫过于网格了。 美同福柿斯杂志的科技版( ( f o r b e sa s a p ) ) 2 0 0 1 年9 月1 0 同发表一组 文章，预测信息技术的下一波大浪潮将在2 0 0 4 2 0 0 5 年度出现，并带来互联网的 新生。这一波新浪潮的本质特征就是万维网( w o r l dw i d ew e b ，3 w ) 升华为网 格( g r e a tg l o b a lg r i d ，3 g ) 。如果网格技术能促使市场按预期的1 7 年增长率持 续增长的活，到2 0 2 0 年，由3 g 产生的互联网将成长为一个2 0 万亿美元产值的 人产业。 网格( g r i d ) 实际上是继传统的互联网( i n t e m e t ) 、万维网( w o r l dw i d ew e b ) 之后的第三代互联网技术。传统互联网实现了世界范围内计算机硬件技术上的联 通；万维网实现了基于互联网的网页的联通；而网格试图实现互联网上所有资源 的全面联通，包括计算资源、存储资源、通信资源、软件资源、信息资源、知识 资源等等，最终实现网络虚拟环境上的资源共享和协同工作，消除资源孤岛和信 息孤岛。i b m 公司副总裁、i b m 公司g r i d 计划的总设计师欧文伯杰蜕：网格 是种整合电脑资源的新手段，它通过互联刚把分散在各地的个人电脑连接起 来，刁i 仅可使每台个人电脑通过充分利用相互间闲置的电脑能源，来提升各自的 电脑处理能力，还可使成千上万的用户在大范围的网络上共享电脑处理功能、文 件以及应用软件。 为了更好地理解g r i d ，可以在计算机系统内部把g r i d 与w e b 进行比较，也 可以把g r i d 计算机系统与并行的电力系统进行比较。g r i d 原本源于“p o w e rg r i d ( 电力供应网) ”的专业术语，因而不妨把g r i d 计算机系统与并行的电力系统进 行比较。现在，人们不会在打开电灯的时候考虑电是从哪个电站来的。而目前， 人们获耿信息并不直接从互联网本身随意获取，必须先告诉电脑去访问某一个网 站，这就好比我们在打开电灯的丌关时必须告诉它我们需要某一电站的电一样。 网格的目标就是让人们使用网络资源像使用电一样简单。电力系统的模式就是网 格努力的方向。 1 9 9 6 年，美国能源部、美国国家科学基金会、太空总署、i b m 、微软、c i s c o 等组织为了发展并推广分布式计算，联合成立了g l o b u s 组织。该组织从事与网 格计算相关技术的研发、提供开发者测试环境、研制工具包以供开发者下载，它 逐步成为g r i d 研究的代表性组织。目前，美国以能源部及n a s a 等政府的研发 机构为主在推动网格计算的主要项目。网格计算不仅受到需要大型科学计算的国 家级部门如航天、气象部门的关注，而且目前很多大公司也开始有了相关“动作”。 美国微软公司已经决定支援g l o b u s 计划，日本的软件公司也向从事网格计算研 究的新兴企业u n i t e dd e v i c e s 投资。除此以外，辉瑞( p f i z e r ) 制药公司以及飞机 制造商波音公司等大公司都已丌f 始进行有关网格计算的实验。它们的实验目标主 复日大学坝，i ：学位论义 分布式环境下的数据挖掘算法的研究与安玑第1 2 页共5 3 页 要着眼于将网格计算应用于大规模的科学仿真方面。 2 0 0 2 年2 月，i b m 公司与g l o b u s 共同发表了丌放网格服务协议框架( o p e n g r i ds e r v i c e s a r c h i t e c t u r e ，o g s a ) 。o g s a 主要是将w e b 服务、数据库存取、j 2 e e 等技术规范纳入，初步的技术规格已经公稚在网络上供大众评估建议。 网格出现的最直接的技术背景就是分布式计算。从计算模式上讲，网格计算 实质上是一种分柿式计算。从1 9 4 5 年现代计算机发明到1 9 8 5 年左右，计算模式 以集中式计算方式为主。进入2 0 世纪9 0 年代，计算机网络技术的乜速发展，尤 其是互联网的迅速普及使得全球范围内的数百万台计算机连接起来得以进行信 息交换，改变了人们传统的获取、处理信息的方式。随着计算资源的网络化，拥 有个人计算机或工作站的广大用户，迫切需要共享或集成分布于网络上的丰富信 息资源，用以廉价获得超出局部计算机能力的高品质服务。因此在多个资源上进 行分布式处理就变得越来越迫切。从简单的数据共享到多个服务的先进系统，大 量的计算转移到了网络环境下的各种资源和个人桌面。分布式计算时代初露端 倪，成为影口内当今计算机技术发展的关键技术力量之一。分布式计算或者称分布 式系统包含许多物理资源和逻辑资源，通过网络通信实现信息交换，有一个高层 的操作系统能够对整个系统进行管理，系统对用户透明以及系统中各部分资源既 相互独立又相互配合。但是对这个系统的用户来说，系统就像一台计算机一样。 总之，网格意在使今天不同的网络和包括数据、计算能力、存储、应用等在 内的计算资源能够发展成为整合、无缝集成的计算环境，从而将一系列分布式计 算资源组合为一台单一的大型虚拟计算机。通过使用一组丌放标准和协议，网格 使各组织机构能够通过全球互联网或自己的内部网访问数据、处理能力、存储和 其它异构计算资源。因此，网格技术的发展前景十分光明。 1 6 本文的主要工作 对分柿式环境下的聚类数据挖掘算法的研究将是本文讨论的重点。本文的目 标是改进一个现有的聚类算法，提出它的分布式版本，使之能够充分利用分布式 环境，同叫保持一定的准确度。 我们提出了g d b s c a n 算法。它以基于密度的聚类算法d b s c a n e k s x 9 6 】 作为改进对象，并结合g m d l 算法【l n w z j 0 2 ，生成分布式挖掘的局部模型代 表。然后使用我们改进的r d b s c a n 算法，综合各个局部模型，生成分布式挖 掘的全局模型。 另外，我们利用g l o b u s 工具包开发了一个分靠式的数据聚类挖掘系统 g c 系统，成功地将g d b s c a n 算法在网格环境下加以实现，并在此实现基础 之l ，对算法进行了测试与评估。 复日大学硕士学位论文 分布式王_ l 、境下的数据挖掘算法的研究1 j 实现 1 。7 本文的组织 本文是对分布式环境下聚类挖掘算法改进和扩展的研究署实现。首先在第二 章中提出了我们的g d b s c a n 算法，叙述了算法的四个步骤以及各个步骤的详 细过程，并对算法的运行结果以及参数进行了评测。在第三章中，我们将算法部 署在一个网格环境中，并描述了系统的架构以及各个模块的功能。最后，第四章 对本文的i ：作进行了总结和展望。 分布式环境下的数据挖掘算法的研究与实现 第二章g d b s c a n 算法结构 g - d b s c a n 算法遵循分布式聚类挖掘算法的一般结构，主要由四个步骤组 成：产生局部模型、生成局部代表、产生全局模型、更新局部模型。 2 1 产生局部模型 产生局部模型是整个挖掘过程的第一步，是在各个局部节点各自的局部数据 集卜进行的。我们使用经典的d b s c a n 算法作为产生局部模型的方法，因为： 首先，d b s c a n 算法很适合进行分布式版本的改造。本身聚类挖掘算法的 结果模式就有很好的“模式局部性”，即对于结果模式的一个子集来蜕，往往产 生它的也只是原数据集的个子集，而和整个数据集关系并不大。例如，在数据 空问中，某个数据点是否属于一个簇，一般只和它“周围”的若干数据点有关系， 而和“较远”的其它数据点没有关系或者关系不大。聚类算法的这个特性，使得 它特别适应于分柿式环境，很适合对整个数据集进行分割，然后“分而治之”地 进行挖掘。而相对基于距离的聚类挖掘算法例如k - m e a n s h a t 7 5 、 c l a r a n s i n h 9 4 来说，基于密度的聚类挖掘算法的“模式局部性”更加明显。 所以我们选择了经典的基于密度的聚类挖掘算法d b s c a n 作为产生局部模型的 方法。 其次，由于d b s c a n 算法是基于局部密度的，它可以发现任意形状的聚类 模式。而基于距离的聚类挖掘算法往往只擅长处理球形或者规则形状的聚类。 阿次，d b s c a n 算法在处理例外点( o u t l i e r ) 时相当健壮。它将密度低于阈 值的例外点区域作为噪声处理，基本上不影响别的聚类的生成。 另外，多年的实践也表明，d b s c a n 算法是一个十分有效且效率较高的聚 类算法。 2 1 1d b s c a n 算法原理 d b s c a n 算法在各个局部节点上运行，以产生局部聚类模型。 d b s c a n 算法是基于密度的聚类算法，其思路仿照人类的聚类行为。以二 维空问( 即二维平面) 上的点的聚类为例，假设有三个样本数据库 e k s x 9 6 ， 数据库中的数据点是在二维平面上。各个数据库中点的分布如图2 一l 所示。 我们观看这三张数据点分布图的时候，很容易就能区分出每个数据库中有几 个聚类，每个聚类包括哪些点，以及不属于任何聚类的噪声点。人之所以能辨别 出聚类的外形以及噪声点，主要是因为聚类中的点密度比聚类外的点密度高得 复旦大学硕士学位论义 分布式环境下的数据挖掘算法的研究1 j 实现 多，而噪声点的密度比任何聚类的点密度都低得多。 i t a l a b a s e1i l a t a b a 5 e2 d a t a b a s e3 图2 - 1 ：样本数据库 按照这个想法，我们尝试给出“聚类”和“噪声”的形式化定义。设有数据 库d ，其中的数据点是在k 维空间s 上的点。应该来说这个基于密度的想法不仅 仅是对二维空问成立，对于k 维的空间也是成立的，但是为了直观起见，我们后 面的举例以二维空间点为主。主要思路是对于聚类中的每个点，它的给定半径的 邻域必须包含多于一定数目的数据点。也就是说，邻域的点密度必须超过某个闽 值。邻域的形状是由s 中两个点p 、q 之间的距离函数( 记为d i s t ( p ，q ) ) 决定的， 例如如果在：维空间中使用曼哈顿距离，那么邻域的形状是+ 个f 方形。在这罩， 我们使用欧几里德距离作为距离函数，那么二维空间中邻域的形状是一个圆形。 定义2 1 ：e p s 邻域 点p 的e p s 一邻域，记为n e p 。( p ) ，定义为：n 5 p 。( p ) = q e did i s t ( p ，q ) ，凄：= ： 图2 - 2 ；核心点和边界点 在图2 - 2 ( a ) o o ，点q 是核心点，而点p 是边界点。在( b ) 中可以看到，点p 从 点q 直接密度可达，但是点q 从点p 不能直接密度可达，因为点p 不是核心点。 利用直接密度可达的概念，我们可以给出密度可达的定义。 定义2 3 ：密度可达 点p 从点q 关于e p s 和m i n p t s 密度可达，指的是存在这样一系列点p l 、 p 。，其中p t = q ，p 。= p ，1 i n ，并且点p i + 1 从点p i 关于e p t 和m i n p t s 是直接密 度町达的。 密度可达是直接密度可达的一个扩展。密度可达是传递的，但是是非对称的。 例如图2 - 2 ( c ) 中，点p 从点q 是密度可达的，但是反之不然。但是对于两个核心 点来说，密度可达是对称的。 同一个簇c 中的两个边界点之间是相互不密度可达的，因为它们都不满足 定义2 2 中的核心点条件。但是，在c 中必然存在某个核心点，从这个核心点到 这两个边界点都是密度可达的。因此我们引入密度相连的概念以描述边界点之间 的这利，关系。 定义2 4 ：密度相连 如果存在点0 ，使得点p 和点q 都从点0 关于e p s 和m i n p t s 密度可达，那 么点p 和点q 之问关于e p s 和m i n p t s 是密度相连的。 密度相连是对称的。如在图2 - 2 ( d ) q h ，点p 和点q 是密度相连的，那么点q 和点p