基于云计算平台Hadoop的并行k_means聚类算法设计研究

第３８卷　第１０期 ２０１１年１０月 计 算 机 科 学 Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ Ｖｏｌ．３８Ｎｏ．１０ Ｏｃｔ　２０１１ 到稿日期：２０１０－１１－０１　返修日期：２０１１－０３－２１　　本文受国家自然科学基金（６０９３３００４，６０９７５０３９，６１０７２０８５），国家９７３项目（２００７ＣＢ３１１００４）， 西北师范大学青年教师科研能力提升 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 骨干项目（ＮＷＮＵ－ＬＫＱＮ－１０－１），湘潭大学博士启动基金（１０ＱＤＺ４２），湖南省教育厅一般项目 （０９Ｃ９６７）资助。 赵卫中（１９８１－），男，博士，讲师，主要研究领域为机器学习、数据挖掘、算法分析与 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 ，Ｅ－ｍａｉｌ：ｚｈａｏｗｅｉｚｈｏｎｇ＠ｇｍａｉｌ．ｃｏｍ；马慧芳（１９８１－）， 女，博士，副教授，主要研究领域为机器学习、数据挖掘；傅燕翔（１９７９－），女，讲师，主要研究领域为人机界面交互；史忠植（１９４１－），男，研究员， 博士生导师，主要研究领域为人工智能、机器学习、神经计算、认知科学。 基于云计算平台Ｈａｄｏｏｐ的并行ｋ－ｍｅａｎｓ 聚类算法设计研究 赵卫中１，４　马慧芳２，４　傅燕翔３　史忠植４ （湘潭大学信息工程学院　湘潭４１１１０５）１　（西北师范大学数学与信息科学学院　兰州７３００７０）２ （湘潭大学机械工程学院　湘潭４１１１０５）３ （中国科学院计算技术研究所智能信息处理重点实验室　北京１００１９０）４ 　 摘　要　随着数据库技术的发展和Ｉｎｔｅｒｎｅｔ的迅速普及，实际应用中需要处理的数据量急剧地增长，致聚类研究面临 许多新的问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 和挑战，如海量数据和新的计算环境等。深入研究了基于云计算平台 Ｈａｄｏｏｐ的并行ｋ－ｍｅａｎｓ聚类算 法，给出了算法设计的 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 和策略。在多个不同大小数据集上的实验表明，设计的并行聚类算法具有优良的加速比、 扩展率和数据伸缩率等性能，适合用于海量数据的分析和挖掘。 关键词　云计算，Ｈａｄｏｏｐ平台，并行ｋ－ｍｅａｎｓ，ＭａｐＲｅｄｕｃｅ 　 Ｒｅｓｅａｒｃｈ　ｏｎ　Ｐａｒａｌｌｅｌ　ｋ－ｍｅａｎｓ　Ａｌｇｏｒｉｔｈｍ　Ｄｅｓｉｇｎ　Ｂａｓｅｄ　ｏｎ　Ｈａｄｏｏｐ　Ｐｌａｔｆｏｒｍ ＺＨＡＯ　Ｗｅｉ－ｚｈｏｎｇ１，４　ＭＡ　Ｈｕｉ－ｆａｎｇ２，４　ＦＵ　Ｙａｎ－ｘｉａｎｇ３　ＳＨＩ　Ｚｈｏｎｇ－ｚｈｉ　４ （Ｃｏｌｌｅｇｅ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｘｉａｎｇｔａｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉａｎｇｔａｎ　４１１１０５，Ｃｈｉｎａ）１ （Ｃｏｌｌｅｇｅ　ｏｆ　Ｍａｔｈｅｍａｔｉｃｓ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ，Ｎｏｒｔｈｗｅｓｔ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｌａｎｚｈｏｕ　７３００７０，Ｃｈｉｎａ）２ （Ｃｏｌｌｅｇｅ　ｏｆ　Ｍｅｃｈａｎｉｃａｌ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｘｉａｎｇｔａｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉａｎｇｔａｎ　４１１１０５，Ｃｈｉｎａ）３ （Ｋｅｙ　Ｌａｂｏｒａｔｏｒｙ　ｏｆ　Ｉｎｔｅｌｌｉｇｅｎｔ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｐｒｏｃｅｓｓｉｎｇ，Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｃｏｍｐｕｔｉｎｇ　Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈｉｎｅｓｅ　Ａｃａｄｅｍｙ　ｏｆ　Ｓｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ　１００１９０，Ｃｈｉｎａ）４ 　 Ａｂｓｔｒａｃｔ　Ｉｎ　ｔｈｅ　ｐａｓｔ　ｄｅｃａｄｅｓ，ｄａｔａ　ｃｌｕｓｔｅｒｉｎｇ　ｈａｓ　ｂｅｅｎ　ｓｔｕｄｉｅｄ　ｅｘｔｅｎｓｉｖｅｌｙ　ａｎｄ　ａ　ｍａｓｓ　ｏｆ　ｍｅｔｈｏｄｓ　ａｎｄ　ｔｈｅｏｒｉｅｓ　ｈａｖｅ ｂｅｅｎ　ａｃｈｉｅｖｅｄ．Ｈｏｗｅｖｅｒ，ｗｉｔｈ　ｔｈｅ　ｄｅｖｅｌｏｐｍｅｎｔ　ｏｆ　ｄａｔａｂａｓｅ　ａｎｄ　ｐｏｐｕｌａｒｉｔｙ　ｏｆ　Ｉｎｔｅｒｎｅｔ，ａ　ｌｏｔ　ｏｆ　ｎｅｗ　ｃｈａｌｌｅｎｇｅｓ　ｓｕｃｈ　ａｓ ｍａｓｓｉｖｅ　ｄａｔａ　ａｎｄ　ｎｅｗ　ｃｏｍｐｕｔｉｎｇ　ｅｎｖｉｒｏｎｍｅｎｔ　ｌｉｅ　ｉｎ　ｔｈｅ　ｒｅｓｅａｒｃｈ　ｏｎ　ｄａｔａ　ｃｌｕｓｔｅｒｉｎｇ．Ｗｅ　ｃｏｎｄｕｃｔｅｄ　ａ　ｄｅｅｐ　ｒｅｓｅａｒｃｈ　ｏｎ ｐａｒａｌｌｅｌ　ｋ－ｍｅａｎｓ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　Ｈａｄｏｏｐ，ｗｈｉｃｈ　ｉｓ　ａ　ｎｅｗ　ｃｌｏｕｄ　ｃｏｍｐｕｔｉｎｇ　ｐｌａｔｆｏｒｍ．Ｗｅ　ｓｈｏｗｅｄ　ｈｏｗ　ｔｏ　ｄｅｓｉｇｎ　ｐａｒａｌ－ ｌｅｌ　ｋ－ｍｅａｎｓ　ａｌｇｏｒｉｔｈｍｓ　ｏｎ　Ｈａｄｏｏｐ．Ｅｘｐｅｒｉｍｅｎｔｓ　ｏｎ　ｄｉｆｆｅｒｅｎｔ　ｓｉｚｅ　ｏｆ　ｄａｔａｓｅｔｓ　ｄｅｍｏｎｓｔｒａｔｅ　ｔｈａｔ　ｏｕｒ　ｐｒｏｐｏｓｅｄ　ａｌｇｏｒｉｔｈｍ ｓｈｏｗｓ　ｇｏｏｄ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｎ　ｓｐｅｅｄｕｐ，ｓｃａｌｅｕｐ　ａｎｄ　ｓｉｚｅｕｐ．Ｔｈｕｓ　ｉｔ　ｆｉｔｓ　ｔｏ　ｄａｔａ　ｃｌｕｓｔｅｒｉｎｇ　ｏｎ　ｈｕｇｅ　ｄａｔａｓｅｔｓ． Ｋｅｙｗｏｒｄｓ　Ｃｌｏｕｄ　ｃｏｍｐｕｔｉｎｇ，Ｈａｄｏｏｐ，Ｐａｒａｌｌｅｌ　ｋ－ｍｅａｎｓ，ＭａｐＲｅｄｕｃｅ 　 １　引言 聚类是数据挖掘中重要的研究课题之一。所谓聚类，就 是将物理或抽象对象的集合组成为由类似的对象组成的多个 类或簇的过程。由聚类生成的簇是一组数据对象的集合，同 一簇中的对象尽可能相似，而不同簇中的对象尽可能相异［１］。 随着数据库技术的成熟和数据应用的普及，商业、企业、科研 机构或者政府部门都积累了大量的、以不同形式存储的数据。 如何存储、处理这些海量数据，以及进一步从中挖掘出有用 的、可以指导应用的知识，成为一个棘手的问题。在面对海量 数据时，现有的聚类算法在时间复杂性和空间复杂性上遇到 了瓶颈，这也是聚类算法研究领域中亟需解决的问题之一。 解决该问题的一个思路就是将并行处理技术应用到聚类中， 设计出高效的并行聚类算法，来提高聚类算法处理海量数据 时的性能。 云计算作为一种新兴的商业计算模型得到了人们的广泛 关注［２－５］。Ｈａｄｏｏｐ是一个可以更容易开发和并行处理大规模 数据的云计算平台，它的主要特点包括扩容能力强、成本低、 效率高以及可靠性好等。Ｈａｄｏｏｐ平台由两部分组成：Ｈａ－ ｄｏｏｐ分布式文件系统（ＨＤＦＳ）［６］和 ＭａｐＲｅｄｕｃｅ计算模型［７］。 ＨＤＦＳ采用 Ｍ／Ｓ架构，一个 ＨＤＦＳ集群是由一个管理节 点（Ｎａｍｅｎｏｄｅ）和一定数目的数据节点（Ｄａｔａｎｏｄｅ）组成，每个 节点均是一台普通ＰＣ。在使用上，ＨＤＦＳ与单机上的文件系 统非常类似，同样可以建目录，创建、复制、删除文件，查看文 件内容等。但其底层实现上是把文件切割成块，然后这些块 分散地存储于不同的数据节点上。每个块还可以复制若干 ·６６１· 份，存储于不同的数据节点上，以达到容错之目的。管理节点 是一 个 中 心 服 务 器，负 责 管 理 文 件 系 统 的 名 字 空 间 （Ｎａｍｅｓｐａｃｅ）以及客户端对文件的访问。集群中的数据节点 负责管理它所在节点上的存储。管理节点是整个 ＨＤＦＳ的 核心，它通过维护一组数据结构，记录每一个文件被切割成了 多少块、这些块可以从哪些数据节点中获得、各个数据节点的 状态等重要信息。 ＭａｐＲｅｄｕｃｅ是一种高效的分布式编程模型，也是一种用 于处理和生成大规模数据集的实现方式。ＭａｐＲｅｄｕｃｅ计算 模型各个阶段的工作流程如下： １）Ｉｎｐｕｔ：一个基于 Ｈａｄｏｏｐ平台 ＭａｐＲｅｄｕｃｅ框架的应用 通常需要一对通过实现合适的接口或抽象类提供的 Ｍａｐ和 Ｒｅｄｕｃｅ函数，还应该指明输入、输出的位置和其他一些运行 参数。此阶段还会把输入目录下的大数据文件划分为若干独 立的数据块。 ２）Ｍａｐ：ＭａｐＲｅｄｕｃｅ框架把应用的输入看作一组〈ｋｅｙ， ｖａｌｕｅ〉键值对。在 Ｍａｐ这个阶段，框架会调用用户自定义的 Ｍａｐ函数，处理每个〈ｋｅｙ，ｖａｌｕｅ〉键值对。同时生成一批新的 中间〈ｋｅｙ，ｖａｌｕｅ〉键值对。这两组键值对的类型可能不同。 ３）Ｓｈｕｆｆｌｅ：为了保证Ｒｅｄｕｃｅ的输入是 Ｍａｐ排好序的输 出，在Ｓｈｕｆｆｌｅ阶段，框架通过 ＨＴＴＰ为每个 Ｒｅｄｕｃｅ获得所 有 Ｍａｐ输出中与之相关的〈ｋｅｙ，ｖａｌｕｅ〉键值对；ＭａｐＲｅｄｕｃｅ 框架按照ｋｅｙ值对 Ｒｅｄｕｃｅ阶段的输入进行分组（因为不同 Ｍａｐ的输出中可能会有相同的ｋｅｙ）。 ４）Ｒｅｄｕｃｅ：此阶段会遍历中间数据，对每一个唯一的 ｋｅｙ，执行用户自定义的Ｒｅｄｕｃｅ函数。输入参数是〈ｋｅｙ，｛ｌｉｓｔ ｏｆ　ｖａｌｕｅｓ｝〉，输出是新的〈ｋｅｙ，ｖａｌｕｅ〉键值对。 ５）Ｏｕｔｐｕｔ：此阶段会把Ｒｅｄｕｃｅ输出的结果写入到输出目 录指定的位置。这样，一个典型的 ＭａｐＲｅｄｕｃｅ过程就完成 了。 ２　基于Ｈａｄｏｏｐ的并行ｋ－ｍｅａｎｓ聚类算法设计 由上一部分的介绍可以看出，基于 Ｈａｄｏｏｐ的并行算法 设计，用户最主要的工作是设计和实现 Ｍａｐ和Ｒｅｄｕｃｅ函数， 包括输入和输出〈ｋｅｙ，ｖａｌｕｅ〉键值对的类型以及 Ｍａｐ和Ｒｅ－ ｄｕｃｅ函数的具体逻辑等。 串行的ｋ－ｍｅａｎｓ算法的步骤为： １）任意选择ｋ个样本作为聚簇初始的中心点； ２）迭代； ａ）根据每个聚簇的中心点坐标，将每个样本分配给距离 其最近的聚簇； ｂ）更新聚簇的中心点坐标，即计算每个聚簇中所有样本 的均值； ３）直到收敛。 从ｋ－ｍｅａｎｓ算法中可以看出，算法中主要的计算工作是 将每个样本分配给距离其最近的聚簇，并且分配不同样本的 操作之间是相互独立的，因此考虑将这一步骤并行地执行。 在每次迭代中，算法执行相同的操作，并行ｋ－ｍｅａｎｓ算法 （Ｐａｒａｌｌｅｌ　ＫＭｅａｎｓ：ＰＫＭｅａｎｓ）在每次迭代中分别执行相同的 Ｍａｐ和Ｒｅｄｕｃｅ操作就可以完成。 首先随机选择ｋ个样本作为中心点，并将这ｋ个中心点 存储在 ＨＤＦＳ上的一个文件中，作为全局变量。接下来每次 迭代由３部分组成：Ｍａｐ函数、Ｃｏｍｂｉｎｅ函数和Ｒｅｄｕｃｅ函数。 ２．１　Ｍａｐ函数的设计 Ｍａｐ函数输入的〈ｋｅｙ，ｖａｌｕｅ〉对是 ＭａｐＲｅｄｕｃｅ框架默认 的格式，即ｋｅｙ是当前样本相对于输入数据文件起始点的偏 移量，ｖａｌｕｅ是当前样本的各维坐标值组成的字符串。首先， 从ｖａｌｕｅ中解析出当前样本各维的值；然后计算其与ｋ个中 心点的距离，找出距离最近的聚簇的下标；最后输出〈ｋｅｙ′， ｖａ－ｌｕｅ′〉，其中ｋｅｙ′是距离最近的聚簇的下标，ｖａｌｕｅ′是当前样 本的各维坐标组成的字符串。函数的伪码为： ｍａｐ（〈ｋｅｙ，ｖａｌｕｅ〉，〈ｋｅｙ′，ｖａｌｕｅ′〉） ｛ 　从ｖａｌｕｅ中解析出样本对象，记作ｉｎｓｔａｎｃｅ； 辅助变量ｍｉｎＤｉｓ初始化为可能的最大值； ｉｎｄｅｘ初始化为－１； Ｆｏｒ　ｉ＝０ｔｏ　ｋ－１ｄｏ｛ 　　ｄｉｓ＝ｉｎｓｔａｎｃｅ与第ｉ个中心点的距离； 　　ｉｆ　ｄｉｓ小于ｍｉｎＤｉｓ｛ 　　　　ｍｉｎＤｉｓ＝ｄｉｓ； 　　　　ｉｎｄｅｘ＝ｉ； 　　｝ ｝ 将ｉｎｄｅｘ作为ｋｅｙ′； 将各维坐标值作为ｖａｌｕｅ′； 输出〈ｋｅｙ′，ｖａｌｕｅ′〉； ｝ 为了减少算法迭代过程中传输的数据量和通讯代价，在 Ｍａｐ操作之后，ＰＫＭｅａｎｓ算法中设计一个Ｃｏｍｂｉｎｅ的操作， 将每个 Ｍａｐ函数处理完后的输出数据进行本地合并。因为 每个 Ｍａｐ操作后输出的数据，总是先存储在本地的节点，所 以每个Ｃｏｍｂｉｎｅ操作都是在本地执行，通信代价很小。 ２．２　Ｃｏｍｂｉｎｅ函数的设计 Ｃｏｍｂｉｎｅ函数输入的〈ｋｅｙ，Ｖ〉对中，ｋｅｙ是聚簇的下标，Ｖ 是分配给下标为ｋｅｙ的聚簇的每个样本的各维坐标值组成的 字符串链表。首先从字符串链表中依次解析出每个样本的各 维坐标值，并将每一维对应的坐标值分别相加，同时记录下链 表中样本的总数。输出的 〈ｋｅｙ′，ｖａｌｕｅ′〉对中ｋｅｙ′是聚簇的 下标；ｖａｌｕｅ′是字符串，包括两部分信息：样本总数和各维坐 标值的累加和组成的字符串。函数伪码为： ｃｏｍｂｉｎｅ（〈ｋｅｙ，Ｖ〉，〈ｋｅｙ′，ｖａｌｕｅ′〉） ｛　 　初始化一个数组，用于存储各维坐标的累加值，每个分量初始值为 ０； 初始化变量ｎｕｍ，记录分配给相同聚簇的样本个数，初始值为０； Ｗｈｉｌｅ（Ｖ．ｈａｓＮｅｘｔ（））｛ 　　从Ｖ．ｎｅｘｔ（）中解析出一个样本的各维坐标值； 将各维坐标值累加到数组相应的分量中； ｎｕｍ＋＋； ｝ 将ｋｅｙ作为ｋｅｙ′； 构造一个字符串，包含ｎｕｍ和数组各个分量的信息，将该字符串作 为ｖａｌｕｅ′； 输出〈ｋｅｙ′，ｖａｌｕｅ′〉； ｝ ２．３　Ｒｅｄｕｃｅ函数的设计 Ｒｅｄｕｃｅ函数输入的〈ｋｅｙ，Ｖ〉中，ｋｅｙ是聚簇的下标，Ｖ 是 ·７６１· 从各个Ｃｏｍｂｉｎｅ函数传输的中间结果。在Ｒｅｄｕｃｅ函数中首 先解析出从每个Ｃｏｍｂｉｎｅ中处理的样本个数和相应节点各 维的坐标累加值；然后将对应的各维累加值分别对应相加，再 除以总的样本个数，即得新的中心点坐标。函数伪码为： ｒｅｄｕｃｅ（〈ｋｅｙ，Ｖ〉，〈ｋｅｙ′，ｖａｌｕｅ′〉） ｛　 　初始化一个数组，用于存储各维坐标的累加值，每个分量初始值为 ０； 初始化变量ＮＵＭ，记录分配给相同聚簇的总的样本个数，初始值 为０； Ｗｈｉｌｅ（Ｖ．ｈａｓＮｅｘｔ（））｛ 　　从Ｖ．ｎｅｘｔ（）中解析出一个样本的各维坐标值和样本个数 ｎｕｍ； 　　将各维坐标值累加到数组相应的分量中； 　　ＮＵＭ＋＝ｎｕｍ； ｝ 将数组中的每个分量除以ＮＵＭ，得到新的中心点坐标； 将ｋｅｙ作为ｋｅｙ′； 构造一个字符串，包含新的中心点各维坐标值的信息，将该字符串 作为ｖａｌｕｅ′； 输出〈ｋｅｙ′，ｖａｌｕｅ′〉； ｝ 根据Ｒｅｄｕｃｅ的输出结果，得到新的中心点坐标，并更新 到 ＨＤＦＳ上的文件中，然后进行下一次迭代，直到算法收敛。 ３　实验与结果分析 ３．１　实验环境、数据集和评价指标 本文中所有的实验都是在我们实验室搭建的 Ｈａｄｏｏｐ平 台上运行的。平台由１０台机器、３２核（２核×４＋４核×６）构 成。其中，有４台机器是双核２．８Ｇ，４ＧＢ内存；有６台机器是 四核２．３３Ｇ，８Ｇ内存。Ｈａｄｏｏｐ版本是０．１７．０，ｊａｖａ版本是 １．５．０－１４。每台机器之间用千兆以太网卡，通过交换机连接。 实验所用的数据是人工数据，维度是４８维。为了测试算 法的性能，实验中构造了１Ｇ，２Ｇ，４Ｇ，８Ｇ，１６Ｇ和３２Ｇ等６个 不同大小的数据集。 在实验中，采用加速比（ｓｐｅｅｄｕｐ）、扩展率（ｓｃａｌｅｕｐ）和数 据伸缩率（ｓｉｚｅｕｐ）［８］作为评价指标。 ３．２　实验结果 由于ＰＫＭｅａｎｓ算法中有随机初始化中心点的操作，因此 对每一组实验重复执行２０次，取其平均执行时间作为最终每 组实验的结果。 在实验中，我们测试了算法ＰＫＭｅａｎｓ处理不同大小数据 集时的加速比，实验结果如图１所示。 图１　加速比性能测试结果 从图１中可以看出，ＰＫＭｅａｎｓ算法的加速比是接近线性 的。并且，随着数据集规模的增大，算法的加速比性能会越来 越好。原因有两个：１）ＰＫＭｅａｎｓ算法的 Ｍａｐ和Ｒｅｄｕｃｅ中设 计的〈ｋｅｙ，ｖａｌｕｅ〉对比较合理，使算法能够高效、快捷地实现 和执行；２）在并行算法设计中，增加了Ｃｏｍｂｉｎｅ的操作，使主 节点和从节点之间的通讯代价大幅度减少，并且数据集规模 越大，通讯量减少的比例越高。因此，当数据集规模越大时， 算法的加速比性能越好。 我们用３组实验测试ＰＫＭｅａｎｓ算法的扩展率。第一组 是测试不同大小的数据集１Ｇ，２Ｇ，４Ｇ和８Ｇ分别在１节点、２ 节点、４节点和８节点上的运行效率；第二组是测试不同大小 的数据集２Ｇ，４Ｇ，８Ｇ和１６Ｇ分别在１节点、２节点、４节点和 ８节点上的运行效率；第三组是测试不同大小的数据集４Ｇ， ８Ｇ，１６Ｇ和３２Ｇ分别在１节点、２节点、４节点和８节点上的 运行效率。实验结果如图２所示。 图２　扩展率性能测试结果 从图２中可以看出，对于同一组数据集，当平台节点个数 和测试数据集大小同比例增长时，ＰＫＭｅａｎｓ算法的扩展率是 逐渐减小的。这是因为，当平台节点个数增加时，节点之间的 通讯代价会逐渐增大。当数据规模随节点个数同比例增大 时，算法的执行时间会增加。但是，从结果中我们可以看到， 随着数据集规模的逐渐增大，ＰＫＭｅａｎｓ算法的扩展率性能越 来越好。这是因为，当数据规模增大时，更能发挥每个节点全 部的计算能力。并且，在对加速比的分析中指出，ＰＫＭｅａｎｓ 中增加了Ｃｏｍｂｉｎｅ的过程，数据集规模越大，主节点和从节 点之间通讯代价减少的比例就越高。因此，ＰＫＭｅａｎｓ算法在 第二组数据集上的性能优于第一组数据集，在第三组数据集 上的性能优于第二组数据集。 图３给出了数据伸缩率的性能测试结果。在实验中，分 别测试了在不同节点个数的平台下算法的数据伸缩率性能。 从结果中可以看出，当平台节点个数少于３时，算法的执行时 间几乎随数据集的规模同比例增长。随着平台中节点个数的 不断增加，算法处理大数据集的效率越来越高。例如，在１０ 个节点平台下，算法处理３２Ｇ数据的执行时间才是处理１Ｇ 数据时的１０倍。实验说明，ＰＫＭｅａｎｓ算法适合运行于大规 模的云计算平台，并可以有效地应用于实际中海量数据的分 析和挖掘。 图３　数据伸缩率性能测试结果 结束语　本文对基于云计算平台 Ｈａｄｏｏｐ的并行ｋ－ ｍｅａｎｓ算法设计进行了深入的研究。首先简要介绍了 Ｈａ－ ｄｏｏｐ平台的基本组成，包括 ＨＤＦＳ框架和 ＭａｐＲｅｄｕｃｅ各个 　　　 （下转第１７６页） ·８６１· Ｖａｌｕｅｓ：ｎｏｎｅ）进行处理，当其缺失率分别为１０％，２０％，３０％， ４０％，５０％，６０％，７０％，８０％，９０％时，利用两算法分别对数据 集进行分类，得出如图１所示的实验结果。 图１　算法Ｊ４８、ＭｕｌｔｉＩｎｆｏＴｒｅｅ在不同样本缺失率下分类精度比较 ２．２　结果分析 比较表１中两种算法分类结果可以看出，分类所得结果 有明显不同，原因在于 ＭｕｌｔｉＩｎｆｏＴｒｅｅ算法和Ｊ４８算法对属性 进行分割的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 不同，它们分别选用联合熵和Ｓｈａｎｎｏｎ熵作 为分割标准。改进后的算法 ＭｕｌｔｉＩｎｆｏＴｒｅｅ效率提高１０～２０ 倍。其原因是联合熵的计算比Ｓｈａｎｎｏｎ熵要简单得多，避免 了计算对数ｌｏｇ消耗的时间，改进算法的执行效率明显优于 Ｃ４．５。 从图１的实验结果可以看出，随着数据样本缺失值的增 加，Ｊ４８算法的分类精度下降明显，而 ＭｕｌｔｉＩｎｆｏｔｒｅｅ算法的分 类精度未有很大变化。这说明Ｊ４８算法在处理属性值遗漏数 据时会带入偏置，而 ＭｕｌｔｉＩｎｆｏｔｒｅｅ算法在生成决策树的过程 中能够消除值遗漏数据对测试属性选择的影响。当缺失率大 于５０％时，改进后的算法的分类精度提高最为明显，这说明 ＭｕｌｔｉＩｎｆｏＴｒｅｅ算法较适合于缺失率在这个区间的数据集。 结束语　在实际的数据中，属性值遗漏数据是无处不在 的。本文把基于联合熵的信息增益率作为决策树测试属性选 择的标准，它能够在生成决策树的过程中消除值遗漏数据对 测试属性选择的影响，更适合于实际数据。最后，通过实验数 据验证了 ＭｕｌｔｉＩｎｆｏＴｒｅｅ算法能够从总体上提高算法执行效 率和分类精度，非常适合于样本缺失率大于５０％的数据集的 分类问题。当样本缺失率在其他区间时，将通过组合分类 器［１０］的技术来提高分类准确率。我们会在以后的工作中不 断扩展和细化这个领域的研究，使之更加完善。本文研究成 果解决了从大规模、不确定性数据集中发现决策树分类模型 的问题，为应用决策树分类技术提供了更为广阔的空间。 参 考 文 献 ［１］ Ｇｕｓｔａｖｏ　Ｅ　Ａ，Ｂａｔｉｓｔａ　Ｐ　Ａ，Ｍｏｎａｒｄ　Ｍ　Ｃ．Ａｎ　Ａｎａｌｙｓｉｓ　ｏｆ　Ｆｏｕｒ Ｍｉｓｓｉｎｇ　Ｄａｔａ　Ｔｒｅａｔｍｅｎｔ　Ｍｅｔｈｏｄｓ　ｆｏｒ　Ｓｕｐｅｒｖｉｓｅｄ　Ｌｅａｒｎｉｎｇ［Ｊ］． Ａｐｐｌｉｅｄ　Ａｒｔｉｆｉｃｉａｌ　Ｉｎｔｅｌｌｉｇｅｎｃｅ，２００３，１７（５／６）：５１９－５３３ ［２］ Ｋｒｙｓｚｋｉｅｗｉｃｚ　Ｍ．Ｒｕｌｅｓ　ｉｎ　ｉｎｃｏｍｐｌｅｔｅ　ｉｎｆｏｒｍａｔｉｏｎ　ｓｙｓｔｅｍｓ［Ｊ］． Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅｓ，１９９９，１１３：２７１－２９２ ［３］ Ｍｉｎｇｅｒｓ　Ｊ．Ａｎ　ｅｍｐｉｒｉｃａｌ　ｃｏｍｐａｒｉｓｏｎ　ｏｆ　ｓｅｌｅｃｔｉｏｎ　ｍｅａｓｕｒｅｓ　ｆｏｒ ｄｅｃｉｓｉｏｎ－ｔｒｅｅ　ｉｎｄｕｃｔｉｏｎ［Ｊ］．Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ，１９８９，３（４）：３１９－ ３４２ ［４］ Ｓａｆａｖｉａｎ　Ｓ　Ｒ，Ｌａｎｄｇｒｅｂｅ　Ｄ．Ａ　Ｓｕｒｖｅｙ　ｏｆ　Ｄｅｃｉｓｉｏｎ　Ｔｒｅｅ　Ｃｌａｓｓｉｆｉｅｒ Ｍｅｔｈｏｄｏｌｏｇｙ［Ｒ］．４７９０７．Ｓｃｈｏｏｌ　ｏｆ　Ｅｌｅｃｔｒｉｃａｌ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｐｕｒ－ ｄｕｅ　Ｕｎｉｖｅｒｓｉｔｙ，１９９１：１－５８ ［５］ 冯少荣．决策树算法的研究与改进［Ｊ］．厦门大学学报：自然科学 版，２００７，２０（４）：４９８－５００ ［６］ Ｑｕｉｎｌａｎ　Ｊ　Ｒ．Ｃ４．５：Ｐｒｏｇｒａｍｓ　ｆｏｒ　Ｍａｃｈｉｎｅ　Ｌｅａｒｎｉｎｇ［Ｓ］．Ｍｏｒｇａｎ Ｋａｕｆｍａｎ，１９９３ ［７］ Ｑｉａｎ　Ｙｕｎｈｕａ，Ｌｉａｎｇ　Ｊｉｙｅ．Ａ　ｎｅｗ　ｍｅｔｈｏｄ　ｆｏｒ　ｍｅａｓｕｒｉｎｇ　ｔｈｅ　ｕｎ－ ｃｅｒｔａｉｎｔｙ　ｉｎ　ｉｎｃｏｍｐｌｅｔｅ　ｉｎｆｏｒｍａｔｉｏｎ　ｓｙｓｔｅｍｓ［Ｊ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ　ｏｆ　Ｕｎｃｅｒｔａｉｎｔｙ．Ｆｕｚｚｉｎｅｓｓ　ａｎｄ　Ｋｎｏｗｌｅｄｇｅ－Ｂａｓｅｄ　Ｓｙｓ－ ｔｅｍｓ，２００８（９） ［８］ Ｌｅｕｎｇ　Ｙ，Ｌｉ　Ｄ　Ｙ．Ｍａｘｉｍａｌ　ｃｏｎｓｉｓｔｅｎｔ　ｂｌｏｃｋ　ｔｅｃｈｎｉｑｕｅ　ｆｏｒ　ｒｕｌｅ ａｃｑｕｉｓｉｔｉｏｎ　ｉｎ　ｉｎｃｏｍｐｌｅｔｅ　ｉｎｆｏｒｍａｔｉｏｎ　ｓｙｓｔｅｍｓ［Ｊ］．Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ，２００３，１５３：８５－１０６ ［９］ 赵蕊．基于 ＷＥＫＡ平台的决策树算法设计与实现［Ｄ］．长沙：中 南大学，２００７：４３－４６ ［１０］旷海兰，罗可，刘新华，等．一种基于粗糙集理论的组合分类器构 造方法［Ｊ］．计算机工程与应用，２００６，１６ （上接第１６８页） 阶段的工作流程以及结构关系。然后，给出基于 Ｈａｄｏｏｐ的 并行ｋ－ｍｅａｎｓ算法设计时需要思考的主要问题、算法设计的 主要流程以及方法和策略等。最后，通过在多组不同大小数 据集上的实验表明，我们设计的并行聚类算法ＰＫＭｅａｎｓ适合 运行于大规模云计算平台，可以有效地应用于实际中海量数 据的分析和挖掘。 随着云计算概念的兴起，基于云计算平台的数据挖掘、聚 类算法的研究逐渐成为国内外学者的研究热点。未来的研究 方向包括：１）研究聚类算法并行化的一般规律，找到数据规 模、算法复杂性、节点数之间的关系，发现加速比和可扩展性 的影响因素，从而设计出高效的并行聚类算法；２）研究基于 云计算平台的数据挖掘应用中的信息安全和隐私保护等问 题，该问题的解决对于云计算在实际商务中的应用将起到关 键性的作用。 参 考 文 献 ［１］ Ｈａｎ　Ｊ　Ｗ，Ｋａｍｂｅｒ　Ｍ．Ｄａｔａ　ｍｉｎｉｎｇ：ｃｏｎｃｅｐｔｓ　ａｎｄ　ｔｅｃｈｎｉｑｕｅｓ ［Ｍ］．Ｓａｎ　Ｆｒａｎｃｉｓｃｏ，ＵＳ：Ｍｏｒｇａｎ　Ｋａｕｆｍａｎｎ，２００１ ［２］ Ｂｕｙｙａ　Ｒ，Ｙｅｏ　Ｃ　Ｓ，Ｖｅｎｕｇｏｐａｌ　Ｓ．Ｍａｒｋｅｔ－ｏｒｉｅｎｔｅｄ　ｃｌｏｕｄ　ｃｏｍｐｕ－ ｔｉｎｇ：ｖｉｓｉｏｎ，ｈｙｐｅ，ａｎｄ　ｒｅａｌｉｔｙ　ｆｏｒ　ｄｅｌｉｖｅｒｉｎｇ　ＩＴ　ｓｅｒｖｉｃｅｓ　ａｓ　ｃｏｍ－ ｐｕｔｉｎｇ　ｕｔｉｌｉｔｉｅｓ，Ｋｅｙｎｏｔｅ　Ｐａｐｅｒ［Ｃ］∥Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１０ｔｈ ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｈｉｇｈ　Ｐｅｒｆｏｒｍａｎｃｅ　Ｃｏｍｐｕｔｉｎｇ ａｎｄ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ．Ｄａｌｉａｎ，Ｃｈｉｎａ，２００９：２５－２７ ［３］ Ａｒｍｂｒｕｓｔ　Ｍ，Ｆｏｘ　Ａ．Ａｂｏｖｅ　ｔｈｅ　ｃｌｏｕｄｓ：ａ　Ｂｅｒｋｅｌｅｙ　ｖｉｅｗ　ｏｆ　ｃｌｏｕｄ ｃｏｍｐｕｔｉｎｇ［Ｒ］．ＵＳＡ：Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｃａｌｉｆｏｒｎｉａ　ａｔ　Ｂｅｒｋｅｌｅｙ，２００９ ［４］ Ｅｒｄｏｇｍｕｓ　Ｈ．Ｃｌｏｕｄ　ｃｏｍｐｕｔｉｎｇ：ｄｏｅｓ　ｎｉｒｖａｎａ　ｈｉｄｅ　ｂｅｈｉｎｄ　ｔｈｅ ｎｅｂｕｌａ［Ｊ］．ＩＥＥＥ　Ｓｏｆｔｗａｒｅ，２００９，２６（２）：４－６ ［５］ 郑纬民．云计算的大幕已经拉开［Ｊ］．中国计算机学会通讯， ２００９，２（６）：６－７ ［６］ Ｇｈｅｍａｗａｔ　Ｓ，Ｇｏｂｉｏｆｆ　Ｈ，Ｌｅｕｎｇ　Ｓ．Ｔｈｅ　ｇｏｏｇｌｅ　ｆｉｌｅ　ｓｙｓｔｅｍ［Ｊ］．Ｓ ＡＣＭ　ＳＩＧＯＰＳ　Ｏｐｅｒａｔｉｎｇ　Ｓｙｓｔｅｍｓ　Ｒｅｖｉｅｗ，２００３，３７（５）：２９－４３ ［７］ Ｄｅａｎ　Ｊ，Ｇｈｅｍａｗａｔ　Ｓ．ＭａｐＲｅｄｕｃｅ：ｓｉｍｐｌｉｆｉｅｄ　ｄａｔａ　ｐｒｏｃｅｓｓｉｎｇ　ｏｎ ｌａｒｇｅ　ｃｌｕｓｔｅｒｓ［Ｃ］∥Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　Ｏｐｅｒａｔｉｎｇ　Ｓｙｓｔｅｍｓ　Ｄｅｓｉｇｎ ａｎｄ　Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ．Ｓａｎ　Ｆｒａｎｃｉｓｃｏ，ＣＡ，２００４：１３７－１５０ ［８］ Ｘｕ　Ｘ　Ｗ，Ｊａｇｅｒ　Ｊ，Ｋｒｉｅｇｅｌ　Ｈ　Ｐ．Ａ　ｆａｓｔ　ｐａｒａｌｌｅｌ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏ－ ｒｉｔｈｍ　ｆｏｒ　ｌａｒｇｅ　ｓｐａｔｉａｌ　ｄａｔａｂａｓｅｓ［Ｊ］．Ｄａｔａ　Ｍｉｎｉｎｇ　ａｎｄ　Ｋｎｏｗ－ ｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｙ，１９９９，３（３）：２６３－２９０ ·６７１·