（计算机系统结构专业论文）基于ocsvm的分布式聚类技术研究.pdf

中文摘要 摘要 随着信息技术的飞速发展以及数据的不断积累，如何从现有的历史数据中 发掘对用户未来决策有指导性的信息是计算机科学技术面临的挑战性任务之 一。聚类分析技术通过根据数据的相似性划分为不同的类别，从而完成对未知 数据的类别划分，并被广泛的应用于机器学习、数据挖掘、信息检索、图像处 理等多个领域。 如何在有效的时间内完成对海量数据的处理并给出合理的分析结果是聚类 分析面临的主要问题之一，针对这一问题本文提出了一种基于0 c s v m 的分布式 学习系统框架，使得学习过程能最大程度的整合现有的计算资源，从而提高了 学习效率。 本文研究了基于o c s v m 聚类算法的分布式计算策略，利用分治的策略将 数据集分配给多个a g e n t ，通过多个a g e n t 的协作来完成聚类任务，然后对各 个a g e n t 的聚类结果进行汇总得到与串行算法一致的聚类结果。另外，在单类 支持向量机的理论基础上，本文对所提出聚类算法中涉及的两个参数的设置规 律以及聚类数目确定的方法进行了研究。 最后，通过对实验结果的对比以及分析，证明了分布式框架的有效性以及 分布式聚类算法的正确性。 关键词分布式计算，m u l t i a g e n t ，单类支持向量机，聚类 i a b s t r a c t a b s t r a c t a st h er a p i dd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g ya n dt h ea c c u m u l a t i o no f t h ed a t a , t of m do u tt h eh e l p f u ld e c i s i o ni n f o r m a t i o nf r o mt h ed a t ah a sb e c o m ea c h a l l e n g et a s kt oc o m p u t e rs c i e n c e c l u s t e ra n a l y s i st e c h n o l o g yc l a s s i f i e st h ed a t a i n t od i f f e r e n tc l u s t e ra c c o r d i n gt ot h es i m i l a r i 锣o ft h ei n s t a n c e s a n d ，t h i s t e c h n o l o g yh a sb e e nw i d e l yu s e di n t h em a c h i n el e a r n i n g , d a t am i n i n g , i n f o r m a t i o nr e t r i e v a l ，i m a g ep r o c e s s i n g ，e t c n o w a d a y s ，h o wt og e tt h er e a s o n a b l er e s u l ti nl i m i t a t i v et i m eh a sb e c o m eo n e o ft h em o s ti m p o r t a n tp r o b l e m sf o rt h ec l u s t e ra n a l y s i s t os o l v et h ep r o b l e m ，t h i s p a p e rp r o p o s e saf r a m e w o r kb a s e do no c s v m d i s t r i b u t e dl e a r n i n gs y s t e m , w h i c h c o u l df u r t h e s tm a k eu s eo ft h e c o m p u t a t i o nr e s o u r c e t h e r e f o r e ，t h el e a r n i n g e f f i c i e n c yi sh i g h l yi m p r o v e d t h i sp a p e rf o c u s e so nt h ec o m p u t a t i o ns t r a t e g yo fo c s v ma l g o r i t h mb a s e do n t h em u l t i a g e n tf r a m e w o r k t h ed a t ai sd i v i d e dt od i f f e r e n ta g e n t sf i r s t ，a n dt h e g l o b a lc l u s t e r i n gr e s u rc a l lb eg e n e r a l i z e df r o mt h ea g e n t s m o r e o v e r , a c c o r d i n gt o t h eo n e c l a s ss u p p o r tv e c t o rm a c h i n et h e o r y , t h i sp a p e rd o e sas t u d yo nt h et w o p a r a m e t e r si n v o l v e di nt h ep a p e ra n dt h em e t h o d so fd e t e r m i n i n gt h en u m b e ro f t h e c l u s t e r s f i n a l l y , t h ee f f i c i e n c yo ft h ed i s t r i b u t e ds y s t e ma n dt h ec o r r e c t n e s so ft h e d i s t r i b u t i o nc l u s t e r i n gh a v eb e e np r o v e da c c o r d i n gt ot h ec o m p a r i s o na n dt h e a n a l y s i so ft h ee x p e r i m e n t s k e yw o r d s ：d i s t r i b u t e dc o m p u t i n g ，m u l t i - a g e n t ，o c s v m ，c l u s t e r i n g i i 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提 供本学位论文全文或者部分的阅览服务；学校有权按有关规定向国 家有关部门或者机构送交论文的复印件和电子版；在不以赢利为目 的的前提下，学校可以适当复制论文的部分或全部内容用于学术活 动。 学位论文作者签名：秘 2 嘶年铲月；1 日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进 行研究工作所取得的成果。除文中已经注明引用的内容外，本学位 论文的研究成果不包含任何他人创作的、已公开发表或者没有公开 发表的作品的内容。对本论文所涉及的研究工作做出贡献的其他个 人和集体，均已在文中以明确方式标明。本学位论文原创性声明的 法律责任由本人承担。 学位论文作者签名：弓邑妻三譬 2 卵年9 月尹1 日 南开大学学位论文电子版授权使用协议 ( 请将此协议书装订于论文首页) 论文勤。洲约务髑叛扔碹 系本人在 南开大学工作和学习期间创作完成的作品，并已通过论文答辩。 本人系本作品的唯一作者( 第一作者) ，即著作权入。现本人同意将本作品收 录于“南开大学博硕士学位论文全文数据库。本人承诺：已提交的学位论文电子 版与印刷版论文的内容一致，如因不同而引起学术声誉上的损失由本人自负。 本人完全了解笪直珏太堂图盘绾羞王堡在：焦厦堂焦途塞的笪堡盘洼滏。同意 南开大学图书馆在下述范围内免费使用本人作品的电子版： 本作品呈交当年，在校园网上提供论文目录检索、文摘浏览以及论文全文部分 浏览服务( 论文前1 6 页) 。公开级学位论文全文电子版于提交1 年后，在校园网上允 许读者浏览并下载全文。 注：本协议书对于搿非公开学位论文”在保密期限过后同样适用。 院系所名称：侣屉移喇隍 作者签名：貂丝仁 哞号： 2 t z o 以内 日期：知降爹月孑1 日 第一章聚类的概念 第一章聚类的概念 随着计算机技术的飞速发展、计算机支撑系统在各种场所的普及，尤其是 数据库技术和数据库管理系统( d b m s ) 的广泛使用，政府机构、科研部门以 及商业组织等的数据库中存储的数据量急剧增大。据德国世界报的资料分 析，如果说1 9 世纪时科学定律的认识数量一百年增长一倍，到本世纪6 0 年代 中期以后，每五年就增加一倍，并且这一增长的速度还在以惊人的加速度加快。 然而，人类的各项活动都是基于人类的智慧和知识，如果没有一种行而有效的 方法将这些把人类容易掌握的知识从数据中提取出来，面对海量的数据，人类 会感觉到像大海捞针一样，从而陷入“丰富的数据”而“贫乏的知识 的尴尬 境地。 面对急切的需求，1 9 8 9 年8 月在美国底特律召开的第1 1 届国际人工智能 联合会议( a a a i ) 上，首次提出基于数据库的知识发现( k n o w l e d g ed i s c o v e r y ， l d ) 【l 】一词。作为人工智能的一个重要分支聚类分析技术在许多研究领域得 到了广泛应用，比如数据挖掘、图像处理、信息检索、信号压缩与编码、现代 生物信息学、客户细分等等，尤其在数据挖掘领域，聚类分析已成为一个重要 的研究方向。与分类算法有所不同，聚类分析是在没有任何先验知识的前提下， 根据数据的相似性将数据划分为不同的类( c l a s s ) 或簇( c l u s t e r ) ，使得同一个 组内的数据对象具有较高的相似度；而不同组中的数据对象具有较大的差异【2 】， 因此又被称为非监督分类( u n s u p e r v i s e dc l a s s i f i c a t i o n ) 。聚类既可以是一个独立 工具，也可以是已知模式算法的一个预处理过程【3 】。 聚类分析是一个非常活跃的研究课题，其中涉及到机器学习、统计学、数 据挖掘、数据库等多门学科。针对各种不同的应用，目前的文献已经提出了大 量的聚类算法，主要分为基于划分的方法、基于层次的方法、基于密度的方法 和基于网格的方法等，这些算法无论是在可伸缩性，还是在处理不同类型属性 的能力上都有了很大的改进。然而，在面对海量数据时，现有的聚类算法却在 时间和空间复杂性上遇到了瓶颈，这也是数据挖掘研究领域中亟需解决的问题 之一。 第一章聚类的概念 1 1 1 什么是聚类 第一节聚类分析简介 聚类( c l u s t e r i n g ) 就是将对象集合分割称为多个类( 也叫簇，c l u s t e r ) ，使 得同一类中的对象之间具有较高的相似性( s i m i l a r i t y ) ，而不同类中的对象具有 较大的相异性( d i s s i m i l a r i t y ) 。 聚类分析方法是一个无监督的学习过程，是指按照事物的某些属性，把事 物聚集成若干类，使得类间相似性尽量小，类内相似性尽量大。一个聚类分析 系统的输入是一组样本和一个度量两个样本间相似度( 相异度) 的标准：它的 输出是数据集的几个组( 类) ，这些组构成一个分区或一个分区结构。数据聚类 分析是一个正在蓬勃发展的领域，它所涉及的领域包括数据挖掘、统计学、机 器学习、空间数据库技术、生物学和市场学等。由于各应用数据库所包含的数 据量越来越大，聚类分析是己成为机器学习和数据挖掘研究中的一个非常活跃 的研究课题。 聚类分析可作为一个独立的工具来获取数据分布的情况，观察每个簇的特 点，集中对特定的簇做进一步分析。如在商务上，聚类分析可以帮助市场分析 人员从客户基本库中发现不同的客户群，并且用购买模式来刻画不同的客户群 的特征。聚类分析也可以作为其他算法( 如特征抽取、分类等) 的预处理步骤， 这些算法在聚类结果上进行处理。迄今为止，人们提出了大量的聚类算法，算 法的选择取决于数据的类型、聚类的目的和应用。如果聚类分析用于描述或探 索的工具，可以对同样的数据尝试多种算法，以便发现数据可能隐含的规律与 结果。 1 1 2 聚类算法的评价标准 一个好的聚类算法应该产生具有如下特性的聚类结果：类内的对象之间高 度相似( h i g hi n t r a c l a s ss i m i l a r i t y ) ，而属于不同类的对象之间很少相似 ( l o wi n t e r - c l a s ss i m i l a r i t y ) 但是如何评价一个聚类结果的好坏，到目前 为止还没有一个统一的标准，现在人们通常从以下几个方面来评价一个聚类算 法的优劣： 2 第一章聚类的概念 1 、处理大的数据集合的能力； 2 、处理任意形状、不同类型数据的能力； 3 、算法是否独立于输入顺序； 4 、处理数据噪声( 脏数据) 的能力； 5 、是否需要预先知道聚类个数，是否需要用户给出领域知识； 6 、算法处理具有多属性数据的能力。 以上即目前评价一个聚类算法需综合考虑的方面。 第二节聚类分析方法分类 目前常用的聚类分析算法主要有以下几种类型：基于划分的聚类方法、基 于层次的聚类方法、基于密度的聚类方法、基于网格的聚类方法、基于模型的 聚类方法等。以下内容分别对这几种聚类方法作一下介绍。 1 2 1 基于划分的聚类 基于划分的聚类算法的基本思想是：对于一个包含n 个数据对象的数据集， 构建k ( k l ； 4 、通过随机采样消除异常数据，即若一个聚类增长太慢就去除它； 5 、对部分聚类进行再聚类，落在每个新获得的聚类中的代表点根据收缩因 子口移向聚类中心，这些点用于代表并描述聚类的边界； 6 、对聚类的数据标记上相应的聚类号。 4 第一章聚类的概念 c u r e 算法对含有异常数据对象进行分析时也能够获得较高的聚类质量， 允许聚类具有复杂的形状和不同的大小，并且只对数据进行一边扫描。 1 2 3 基于密度的聚类 基于密度的方法主要思想是：只要邻近区域的密度超过某个阈值，就继续 聚类，最终相对高密度的区域被相对低密度的区域分割开来形成簇。该方法可 以发现任意形状的簇，并有效过滤噪声点。代表算法有：d b s c a n 算法、o p t i c s 算法、d e n c l u e 算法、d b c l a s d 算法、c l i q u e 算法等。 基于密度的方法中最为著名的是d b s c a n ( d e n s i t y b a s e ds p a t i a lc l u s t e r i n g o fa p p l i c a t i o n sw i t hn o i s e ) 【_ 7 】算法。d b s c a n 算法通过不断生长有足够高密度 的区域来进行聚类。它基于这样的思想：在一个数据空间中，高密度区总是被 低密度区所分割。它能够从含有噪音的空间数据中发现任意形状的聚类。 d b s c a n 算法将一个聚类定义为一组密度连接的点集。 基于密度的聚类算法对于任意形状特性的数据集具有很好的适应能力，但 是最初的算法是要用户来确定参数，这大大限制了它的自适应能力。 1 2 4 基于网格的聚类 基于网格方法将对象空间划分为有限数目的单元( c e l l ) ，从而形成网格结 构，然后在这个网格上进行所有的聚类操作。该方法主要优点就是处理时间由 于与数据对象个数无关而仅与划分对象空间的网格数相关，从而获得相对较快 的速度。代表算法有s t r i n g 算法、w a v e c l u s t e r 算法、o p t i g r i d 算法等。 1 2 5 基于模型的聚类 基于模型方法的基本思想是：首先为每个聚类假设一个模型( 可以是数据 点在空间中的密度分布函数或者其它) ，然后再去寻找符合相应模型的样本。一 个基于模型的算法可以通过构造一个样本空间的密度函数来确定具体聚类，该 算法潜在地假设聚类样本是按某种概率分布的。基于模型的聚类方法主要有两 种【8 】：统计学方法和神经网络方法。统计学方法有c o b w e b 算法、c l a s s i t 算法、a u t o c l a s s 算法；神经网络方法有竞争学习法和自组织特征影射法( s o m ) 。 5 第一章聚类的概念 1 2 6 综合方法 有些聚类算法本来就是多学科交叉的成果，因此其往往涵盖多种以上基本 方法，在实际应用中针对不同的问题也需要结合不同算法方可实现预期的聚类 目标。d e n c l u e ( d e n s i t yb a s e dc l u s t e r i n g ) 【9 】就是结合了划分方法、层次方法 和局部方法的一个综合方法。s t i n g 1 0 】方法也结合了基于网格的方法和自顶向 下的方法。在现在交叉学科蓬勃发展的今天，不同算法之间的融合与渗透也必 将持续发展。 上述部分聚类算法可能同时属于多个类别，这里将它们分列在主要所属的 类别中。 第三节聚类分析过程及应用现状 1 3 1 聚类分析的一般过程 聚类分析是一个反复迭代的处理过程，该过程需要经历多个步骤，从宏观 上看，主要由三个部分组成，即数据预处理、聚类和聚类结果解释评估。详细 过程主要由以下步骤组成： 1 2 1 1 数据预处理 数据预处理是所有机器学习过程的第一阶段，首先需要了解数据所承载的 业务逻辑，确定学习的目标，之后经过e t l ( e x t r a c t t r a n s f o r m l o a d ) 从原始 数据库中选取基本聚类样本。选出的数据进行再处理，检查数据的完整性及数 据一致性，消除噪声，利用统计学方法或者其他机器学习方法对数据进行探索， 选取相应特征作为算法输入。 1 2 1 2 聚类 在数据处理完成之后，根据业务需求确定相应的聚类算法以及聚类目标函 数、算法参数。同样的目标可以选择用不同的算法来解决，可以根据具体情况 进行分析选择，有两种选择算法的途径，一是根据数据的特点不同，选择与之 6 第一章聚类的概念 相关的算法；二是根据业务的具体需求，选择合适的算法模型。 确定算法和目标函数后，需要对预处理后的数据再进行变换，将业务数据 或者物理数据转换成算法能够直接处理的逻辑数据，最后将逻辑数据送与算法 执行聚类过程。 1 2 1 3 聚类评估与解释 聚类是一个无监督过程，所以如何对聚类结果做出合理的评估一直是研究 中的热点和难点，根据不同具体应用环境，研究者已经提出了一些聚类评估标 准，例如文本聚类中的纯度和f 值【1 1 】【1 2 1 。另外，如何将聚类结果结合业务逻辑 予以合理的解释并转化为可视化图形、图表等用户易于理解的方式也是聚类在 应用中重要环节。 在上述步骤中，聚类过程占据非常重要的地位，它主要是利用某些特定的 知识发现算法，在一定的运算效率范围内，从数据中发现出有关模式，聚类决 定了整个学习过程的效果与效率。人们已经遵循以上机器学习过程开发了很多 实用的聚类分析工具。 1 3 2 主流聚类分析系统 在国外，数据挖掘等理论研究和应用开展得相对早，数据挖掘、模式识别 等技术的发展也很迅速。目前，已经开发出了许多功能强大并且使用简便的数 据挖掘、机器学习系统，其中很多系统已经形成产品，为需要对数据进行处理 的企业提供支持，其中绝大多数都包含聚类算法。下面，对当前国外流行的数 据挖掘、统计分析系统作一些简单介绍。 1 3 2 1s a se n t e r p r i s em i n e r s a s 系统全称为s t a t i s t i c sa n a l y s i ss y s t e m ，最早由北卡罗来纳大学的两位 生物统计学研究生编制，并于1 9 7 6 年成立了s a s 软件研究所，正式推出了s a s 软件。s a s 是美国使用最为广泛的三大著名统计分析软件( s a s ，s p s s 和 s y s 仉玎) 之一，是目前国际上最为流行的一种大型统计分析系统，被誉为统计 分析的标准软件。 7 第一章聚类的概念 s a s 是一个基于图形化界面、菜单驱动、拖拉式操作、对用户非常友好且 功能强大的数据挖掘集成环境。其中集成了e t l 工具、数据预处理工具、谱系 聚类工具、决策树工具、多种形式的回归工具、模型可视化工具、数据挖掘的 评价模型等工具。这些具有明确代表意义的图形化模块将各个数据挖掘的工具 单元组成一个处理流程图，并依此来组织数据挖掘的过程。同时可以根据具体 情况的需要进行修改、更新并将需要的模式存储起来，以便此后重新调出来使 用。 1 3 2 2s p s sc l e m e n t i n e s p s s 是世界上最早和应用最广泛的专业的统计分析软件之一，由美国斯坦 福大学的三位研究生于2 0 世纪6 0 年代末研制，同时成立了s p s s 公司，并于 1 9 7 5 年在美国伊利诺斯的芝加哥市组建了s p s s 总部。 s p s s 最突出的特点就是操作界面极为友好，输出结果美观漂亮，并有着良 好的数据输入与管理数据，数据接口较为通用，能方便地从其它数据库中读入 数据。s p s s 数据挖掘产品和服务通过支持交叉行业数据挖掘标准c r i s p 。d m 来 保证及时、可靠的结果。其中s p s sc l e m e n t i n e 模块把有价值的商务知识融入到 数据挖掘的每一步过程，实现交互式数据挖掘。并且提供聚类、分类、神经网 络、关联规则、时间序列等丰富的数据挖掘模型，应用业界领先的模型发布技 术使数据挖掘结果更好的传递到相应的管理和决策人员手中。 1 3 2 3i b m i n t e l l i g e n tm i n e r i b m 依靠其平台优势推出了嵌入于d b 2 的数据挖掘平台，其中包括 i n t e l l i g e n tm i n e rf o rd a t a 和i b mi n t e l l i g e n tm i n e rf o rt e x t 两个数据挖掘模块，将 数据仓库和数据挖掘整合到一个平台之上。前者主要针对结构化数据，分为建 模，浏览，评估三个部分；后者则针是对文本的挖掘模块，主要功能包括特征 抽取、文本聚类、文本分类和检索。 i n t e l l i g e n tm i n e rf o rd a t a 可以寻找包含于传统文件、数据库、数据仓库和数 据中心中的隐含信息。拥有改进的用户界面，增强了并行性，提供新的平台支 持、统计功能、新的价值预测技术以及优化的算法。i b mi n t e l l i g e n tm i n e rf o rt e x t 允许企业从文本信息中获取有价值的客户信息。文本数据源可以是w e b 页面、 8 第一章聚类的概念 在线服务、传真、电子邮件、l o t u sn o t e s 数据库、协定和专利库。它扩展了i b m 的数据采集功能，可以从文本文档和数据源中获取信息。数据源包括客户反馈、 在线新闻服务、电子邮件和w e b 页面。其功能包括：识别文档语言；建立姓名、 用语或其它词汇的词典：提取文本的涵义；将类似的文档分组；根据内容将文 档归类等。新版本中还包括一个多功能的先进文本搜索引擎和非常高效的w e b 文本搜索功能。 1 3 3 聚类分析的应用 聚类分析的应用非常广泛。在实践中聚类可以多角度应用于市场分析，为 市场营销战略和策略的制定提供科学合理的参考，例如在客户细分、实验市场 选择、抽样方案设计、销售片区确定、市场机会研究等方面都可以应用聚类分 析来进行辅助研究；聚类分析在电子商务中网站建设数据挖掘中也是很重要的 一个方面，通过分组聚类出具有相似浏览行为的客户，并分析客户的共同特征， 可以更好的帮助电子商务的用户了解自己的客户，向客户提供更合适的服务： 在生物学上，聚类分析被用来动植物分类和对基因进行分类，获取对种群固有 结构的认识；聚类还可以用来从空间数据库中识别出具有相似特征的空间对象； 可以从保险公司的数据库中发现汽车保险中具有较高索赔概率的群体；还可以 用来分类万维网上不同类型的文档或分析w e b 日志以发现特殊的访问模式等。 第四节聚类算法研究面临的挑战 聚类，是一个富有挑战性的研究领域，它的研究工作集中在为大型数据库 的有效和实际的聚类分析寻求适当的方法，目前的研究主要包含以下几个方面： ( 1 ) 算法的可伸缩性：在很多聚类算法中，对于小的数据集有着较好的鲁 棒性，而对大规模数据库进行聚类时，将会导致有不同的偏差结果，这就需要 聚类算法具有高度的可伸缩性，能有效地处理海量数据，并且时间复杂度不能 太高( 最好是多项式时间) ，消耗的内存空间也有限。为了将算法拓展到超大数 据库( v l d b ) 领域，研究人员已经进行了许多有益的尝试，包括增量式挖掘、 可靠的采样、数据挤压( d a t as q u a s h i n g ) 等。其中，数据挤压技术首先通过扫 描数据来获得数据的统计信息，然后在这些统计信息的基础上进行聚类分析。 9 第一章聚类的概念 比如b i r c h 算法中使用c f 树就是属于数据挤压技术。 ( 2 ) 算法的可适应性：许多聚类算法是基于欧几里德距离或者曼哈顿距离， 这使得其方便于处理只包含数值型特征的样本且趋向于发现具有相近密度和尺 寸的球状簇。但现实环境中的数据对象已经远远超出关系型数据的范围，往往 包含字符、日期等多种数据类型，并且数据的分布也是难以确定的，因此提出 能适应多种数据类型以及发现任意形状簇的算法非常重要。 ( 3 ) 算法的效率问题：提高算法的效率问题是当前聚类领域中研究的又一 个重要问题。通过改进现有的聚类算法，使之具有增量聚类的能力，或者通过 并行的方法提高其对大数据量数据集的运行效率。 ( 4 ) 聚类参数的选择问题：在聚类分析中，许多聚类算法要求用户输入一 定的参数，如希望簇的数目。聚类结果对于输入参数很敏感，通常参数较难确 定，尤其是对于含有高维数据集更是如此。要求人工输入参数不但加重了用户 的负担，而且也使聚类质量难以控制。 ( 5 ) 聚类结果的评估与描述问题：聚类是一个无监督的学习过程，因此如 何对聚类结果进行合理的评估是比较困难的；另外，通常用户希望聚类结果是 可解释的，可理解的和可用的。因此，应用目标如何影响聚类方法的选择也是 一项重要的研究课题。 第五节本文的研究内容和组织结构 如今，随着w e b 挖掘、生物信息学、图像处理等领域对聚类算法的大量采 用，大型以及超大型数据集对于聚类任务已经非常常见，然而现在常规的聚类 算法要么无法在大数据集上完成聚类运算，要么难以在合理的时间内给出聚类 结果。现在虽然有了一些优秀的统计、数据挖掘软件提供了方便易用的聚类工 具箱，但是这些软件都是基于单处理器和单机计算的，虽然计算机硬件技术在 高速发展，但是硬件的发展速度已经远远不能满足于计算和数据处理的需求。 针对这一问题，在研究分布式计算与m a s 的基础上，本文提出了一种基于m a s 的分布式机器学习框架，在该框架下研究了单类支持向量机聚类的分布式策略， 并对分布式系统的性能通过试验进行了证明。 本文的组织结构如下： 第一章聚类的概念。 第一章聚类的概念 介绍了聚类的一般概念以及聚类的一般实施过程，对当前存在的一系列问 题做了总结，引出本文的研究内容。 第二章基于m a s 的机器学习引擎设计 首先介绍了分布式计算的基本概念和并行设计中常用分治策略，然后介绍 了多a g e n t 系统的基本特性以及流行开发方法。在此基础上完成了一个多a g e n t 系统的机器学习引擎系统设计，并对系统中各个模块进行了简要说明。 第三章o c s v m 技术研究 本章在支持向量机的理论基础上，提出了基于单类支持向量机( o c s v m ) 的聚类算法，并对其涉及到的几个重要问题进行了研究。 第四章分布式o c s v m 聚类算法研究 本章首先介绍了几种比较成熟的分布式聚类算法，然后给出基于o c s v m 的聚类算法的分布式计算框架。 第五章分布式系统评估与实验结果分析 通过实验结果的分析，证明了分布式算法的有效性。 第六章总结与展望 本章对本文的研究工作做了总结，并对下一步工作的方向和方法给出了建 议。 第二章基于m a 5 的机器学习引擎设计 第二章基于m a s 的机器学习引擎设计 机器学习算法丰富多样，而每一种算法的理论基础和执行策略差异都很大， 同时分布式机器学习系统要求具有高性能的协同计算能力，辅助完成相关的决 策任务，因此与其他分布式软件平台相比，机器学习系统对软件构架有着更高 的要求。本章首先研究了分布式计算和m a s 的一般性理论，然后在此基础上 提出了一种基于m a s 的分布式机器学习引擎的设计框架【1 3 1 。 第一节分布式计算与多a g e n t 系统 2 1 1 分布式计算概述 在计算机高速发展的几十年中出现了许多支持高性能计算的技术，理论和 应用较为成熟的包括大规模并行处理器、对称对处理器、网格计算、集群系统 等。其中集群系统以其低廉的成本、高可用性、高稳定性和良好的扩展性得到 了人们广泛的认可。分布式计算( d i s t r i b u t e dc o m p u t i n g ) 是计算机科学的一个 重要分支，是集群技术的基础。分布式计算主要研究如何把一个需要巨大的计 算能力才能解决的问题分解成若干个小的子问题，然后把这些子问题分配给许 多计算机进行处理，最后把这些计算结果综合起来得到最终的结果。 2 1 1 1 分布式计算 分布式计算的最早形态出现在8 0 年代末的i n t e l 公司。i n t e l 公司利用他们 的工作站的空闲时间为芯片设计计算数据集，利用局域网调整研究。分布式计 算是一种新的计算方式，它是计算机网络的产物，也是计算机网络应用未来的 发展方向。它通过网络把成千上万台计算机连接起来，组成一台虚拟的超级计 算机，完成单台计算机无法完成的超大规模的问题求解。 分布式计算技术研究主要集中在分布式操作系统研究和分布式计算环境研 究。在过去的2 0 多年里出现了大量的分布式计算技术，如中间件技术、网格 第二章基于m a s 的机器学习引擎设计 技术、移动a g e n t 技术、p 2 p 技术以及w e bs e r v i c e 技术等，每一种技术都针 对特定的应用领域得到了大力发展和广泛应用，一定程度的认可，在特定的范 围内得到了广泛的应用。 虽然分布式计算得到了广泛的关注，但是由于其技术的复杂性和多样性使 得普及变得非常困难。目前虽然有l i n u x 等这样优秀的分布式操作系和大量的 分布式中间件，但是还没有一套统一的分布式计算标准，在很大程度上制约了 分布式计算技术的发展【1 4 1 。另外，如何在分布式计算系统中提供高质量的服务， 服务的可用程度如何，服务的安全性和可靠性如何保证，这些问题已成为分布 式计算技术研究的难点。而结构化程序设计方法、面向对象的程序设计方法等 传统程序设计方法不能完全适应于分布式，而尚没有针对分布式计算系统的软 件开发方法，这些使得分布式计算系统的质量和可用性问题很难得到保证。 随着分布式计算技术研究的不断深入，许多研究者发现单个技术在技术本 身、应用领域等方面的局限性越来越明显，从而把目光投向了多种现有分布式 计算技术的综合，并在特定方面取得了重要的突破，取得了令人满意的成果。 文献【1 5 j 将分布式计算与支持向量机相结合提出了一种分布式机器学习体系结 构；【1 6 】【l 7 】对分布式聚类技术进行了探讨。 2 1 1 2 分布式分治机制 对于并行处理机或者大规模的集群分布式系统，并行程序设计是实现并行 处理完成大任务分割的基础。并行程序设计方式通常可以分为两种： ( 1 ) 数据并行机制( d a t ap a r a l l e l i s m ) 同一种操作可以同时被应用到一 个数据结构的全部元素上。可以隐式或显式地使用增加的说明语句来描述数据 结构如何分解，以及如何被分配到物理处理机上。该方式通常适用于可以将对 全局数据的求解划分为对其子集求解的问题，此时需要对数据进行划分和分布。 在网络环境中，数据并行机制通常采用m a s t e r s l a v e 模型，各子任务( s l a v e ) 分别对分配来的数据进行计算，结束后将结果返回给m a s t e r 。 数据并行机制的优点是它的标量性。同一操作被同样的应用于许多数据， 没有差别，因此开发应用比较简单，代码具有高度的一致性。使用高级编译器 可以自动地检测出并行结构，不必强迫用户显式地管理进程、通信或同步。缺 点是通用性较差，随着数据源的变化和数据规模的调整，并行度不一定会随着 第二章基于m a s 的机器学习引擎设计 处理器数目的增加而线性地提高。 ( 2 ) 任务并行机制( t a s kp a r a l l e l i s m ) ：任务并行也称为功能并行或控制并 行，指的是多控制流或多任务的显式建立，在程序设计者的控制下进行通信和 同步。任务并行的程序通过显示通信和同步这样相互作用的并行任务集构成。 任务并行机制的优点是灵活性好，强调独立任务的显式协调，可以用来开发结 构的和非结构的并行形式。与数据并行机制相比，较少依赖于高级编译技术， 减少了对编译器优化功能的依赖。缺点是为了建立显示的并行任务和管理他们 之间的通信和同步，增加了程序设计者的负担，需要考虑数据本身特点、程序 结构等多方面因素。在很多并行算法中，这两种机制总是同时存在的。在一个 应用程序中集成多种程序设计风格，对提高程序设计效率，以及改善程序设计 性能都有很好的帮助。 2 1 1 3 分布式并行编程模型 随着分布式技术的广泛应用，各种不同的并行编程环境得到了很大的发展， 同时得到发展的还有很多相应的编程辅助工具，包括并行调试器和各种跟踪监 测工具。许多这样的环境作为标准出现，这些标准反过来又促进了可移植并行 环境模型的发展。 并行程序设计模型【l 8 】【l9 】是硬件和软件之间的桥梁，是并行计算的低层实现 与高层抽象的界面。基于不同的目的、面向不同的问题、不同的假设及不同的 抽象层次，目前研究人员已经开发出了几十种不同的抽象并行程序设计模型， 如函数模型、面向对象的模型、数据并行模型、消息传递模型及共享存储模型 在盘 守。 虽然存在着如此多的并行程序设计模型，但并不是每一种模型都适合分布 式计算。这是因为在分布式环境下的并行应用程序的开发是一个很复杂的任务， 开发人员必须面对一系列复杂的问题，这些问题涉及到不确定性、通信、同步、 数据划分和分配、负载平衡、容错、异构、共享或者分布存储、死锁以及竞争 条件等因素。这些对软件开发人员提出了新的重大挑战。目前在分布式环境下 应用最多的是消息传递模型。在消息传递模型中，各个并行执行的部分之间通 过传递消息来交换信息、协调步伐、控制执行。消息传递一般是面向分布式内 存的，但是它也可以用于共享内存的并行机。消息传递为编程者提供了更灵活 1 4 第二章基于m a s 的机器学习引擎设计 的控制手段和表达并行的方法，灵活性和控制手段的多样化是消息传递并行程 序能够提供较高执行效率的重要原因。消息传递模型一方面为编程者提供了灵 活性；另一方面它也将各个并行执行部分之间复杂的信息交换和协调控制任务 交给了编程者，在一定程度上增加了编程者的负担，这也是消息传递编程模型 编程级别低的主要原因。 在当前所有的消息传递软件中，最重要、最流行的是并行虚拟机( p a r a l l e l v i r t u a lm a c h i n e ，p v m ) 和消息传递口( m e s s a g ep a s s i n gi n t e r f a c e ，m p i ) 2 0 】 2 i 】。 p v m 是第一个被广泛接受的消息传递环境，其最大的优点是灵活性，包括异构 平台上的可移植性、交互性和容错功能。m p i 是一个显示的消息传递模式，在 其中，任务通过发送消息进行相互通信。其最大的优点是高性能，点到点通信 函数模型、可操作数据类型都比p v m 丰富，群组通信的函数库也更大，但是 不如p v m 灵活。m p i 和p v m 都提供了一套函数集，且各有所专。它们能运行 在所有的并行平台上，包括p v p 、s m p 、m p p ( m a s s i v e l yp a r a l l e lp r o c e s s o r ) 、 工作站和p c 机组成的集群系统，并已经在w i n d o w s 平台上实现，提供了对c 、 f o r t r a n 和j a v a 语言的绑定。 2 1 2m u l t i a g e n t 系统 在i n t e r n e t 这一目前最庞大的互联网络环境中，计算机软件体系结构和组织 结构的复杂性不断增加，传统的软件设计方法已经无法满足实际需要，分布式、 智能化才是今后软件发展的基本方向。软件分布式的目标是要将问题进行分解， 由多个实现了知识共享的软件模块或网络节点来共同完成问题求解，而智能化 的目标是要在智能主机之间实现智能行为的协调，两者的结合就产生了a g e n t 的概念。 2 1 2 1a g e n t 简介 a g e n t 的理论、技术，特别是多a g e n t 的理论、技术，为分布开放系统的 分析、设计和实现提供了一个崭新的途径，被誉为“软件开发的又一重大突破”。 a g e n t 理论与技术研究最早源于分布式人工智能( d i s t r i b u t ea r t i f i c i a l i n t e l l i g e n t ，d a i ) ，但从8 0 年代末开始，a g e n t 理论、技术研究从d a i 领域中 拓展开来，并与许多其他领域相互借鉴和融合，在许多不同于最初d a i 应用的 第二章基于m a s 的机器学习引擎设计 领域得到了更为广泛的应用。面向a g e n t 技术作为- - i 设计和开发软件系统的 新方法已经得到了学术界和企业界的广泛关注。 目前软件a g e n t 在研究领域中尚没有一个理想的定义，但人们普通认为： a g e n t 是运行于动态环境的、具有高度自治能力的实体，它能够接受其它实体 的委托并为之服务。它具有以下特征： ( 1 ) 自治性( a u t o n o m y ) 软件a g e n t 在运行过程中不直接由人或其它主 体控制，它能在没有与环境相互作用的情况下自主执行任务，对自己的行为和 内部状态有一定的控制权。自治性是软件a g e n t 区别于普通软件程序的基本特 征。 ( 2 ) 响应性( r e a c t i v i t y ) 软件a g e n t 能对来自环境的信息做出适当的响 应，它能感知所处的环境，并能通过自己的行为改变环境。 ( 3 ) 主动性( p r o a c t i v e l y ) 传统应用程序接受用户指令被动执行，而软件 a g e n t 不仅能对环境变化做出反应，而且更重要的是能在特定情况下采取主动 行为。 ( 4 ) 推理性( r e a s o n i n g ) 软件a g e n t 可根据已有的知识和经验，以理性 的方式进行推理。软件a g e n t 的智能由三个主要部件来完成，即内部知识库、 自适应能力以及基于知识库的推理能力。 对a g e n t 的研究大致可分为智能a g e n t 、多a g e n t 系统( m u l t i a g e n ts y s t e m ， 简称m a s ) 和面向a g e n t 的程序设计( a g e n to r i e n t e dp r o g r a m m i n g ，a o p ) 3 个相互关联的方面。智能a g e n t 是m a s 研究的基础，我们可以将有关智能a g e n t 的研究统一在m a s 的研究之下，这样，智能a g e n t 被看成是m a s 研究中的微 观层次，主要研究a g e n t 的理论和结构；而有关a g e n t 间关系的研究则构成了 m a s 研究的宏观层次。智能a g e n t 和m a s 的成功应用要借助于a g e n t 的应用 方法，即a o p 以及a o p 开发工具或平台。 2 1 2 2 多a g e n t 系统 随着高效的并行计算机的开发，计算机网络技术的日益成熟以及对许多涉 及到群体的人类问题求解与活动的认识，人们对人工智能中的并发性与分布性 越来越感兴趣，从而导致了分布式人工智能( d i s t r i b u t e da r t i f i c i a li n t e l l i g e n c e ， d a i ) 的产生。d a i 研究中包括分布式问题求解( d i s t r i b u t e dp r o b l e ms o l v i n g ) 第二章基于m a 5 的机器学习引擎设计 和多a g e n t 系统( m u l t i a g e n ts y s t e m ，m a s ) 两个分支2 2 】【2 3 1 。d p s 研究如何进 行问题分解和任务分布，并在共享数据、知识、求解状态以及部分结果的基础 上协作完成整个问题的分布求解。m a s 系统研究如何在一组自治的智能a g e n t 间协调它们的智能行为，即协调它们的知识、目标、技能和规划，从而完成资 源冲突的消解以及任务的分解和协同处理。 m a s 的协作求解问题的能力超过单个a g e n t ，这是m a s 产生的最直接的 原因。导致m a s 研究逐渐兴起的其他原因还包括：与已有系统或软件的互操 作；求解那些数据、能力和控制具有分布特性的问题以及提