文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 二分K均值聚类算法优化及并行化研究
侵权投诉

二分K均值聚类算法优化及并行化研究

聚类算法的改进

计 算 机 工 程 第 37 卷 第17期

V ol.37 No.17 Computer Engineering

文章编号:1000—3428(2011)17—0023—03·软件技术与数据库·

2011年9月

September 2011

文献标识码:A

中图分类号:TP338.6

二分K均值聚类算法优化及并行化研究

张军伟1,王念滨1,黄少滨1,蔄世明2

(1. 哈尔滨工程大学计算机科学与技术学院,哈尔滨 150001;2. 哈尔滨工业大学计算机科学与技术学院,哈尔滨 150001)

摘 要:二分K均值聚类算法在二分聚类过程中的初始质心选取速度方面存在不足。为此,提出以极大距离点作为二分聚类初始质心的思想,提升算法的运行速度。研究如何在群集系统中进行快速聚类,根据二分K均值聚类算法的特性,采用数据并行的思想和均匀划分的策略,对算法进行并行化处理。实验结果表明,改进后的算法能获得比较理想的加速比和较高的使用效率。 关键词:数据挖掘;聚类算法;二分K均值;并行化;群集系统

Research on Bisecting K-Means Clustering Algorithm

Optimization and Parallelism

ZHANG Jun-wei1, WANG Nian-bin1, HUANG Shao-bin1, MAN Shi-ming2

(1. College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China; 2. College of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China)

【Abstract】Considering the insufficiency of clustering speed which exists in the selecting the initial centroid of Bisecting K-Means(BKM) clustering algorithm, the idea of selecting the two patterns with distance maximum as the initial cluster centroid is implemented. An in-depth study and analysis is carried out on how to accelerate clustering in clustering system. According to the characteristics of BKM, the parallelism algorithm based on data parallelism and symmetric data-partition is put forward. Experimental results show that the improvement of algorithm gets ideal speedup performance and efficiency.

【Key words】data mining; clustering algorithm; Bisecting K-Means(BKM); parallelism; clustering system DOI: 10.3969/j.issn.1000-3428.2011.17.006

1 概述

聚类方法在数据的组织、分析和挖掘中具有重要作用,

广泛应用于模式识别、信息检索、图像处理、机器学习等领域[1]。K-Means算法是基于原型的聚类技术,具有简单、快速并有效处理大规模数据等诸多优点,是应用最广泛的聚类方法之一。缺点是存在过度依赖初始条件,如聚类数目K值的确定、初始聚类中心的选取以及数据的输入次序的变化等都会影响聚类结果,制约了其应用范围。二分K均值聚类算法是K-Means算法的变种算法,通过使用基本K-Means算法能够产生划分聚类算法或层次聚类算法,具有不受初始质心选择影响的优点[2]。该算法在文本挖掘领域有着广泛的应用,通过优化算法的二分初始点的选择过程,把多次循环判断最优点改进为一次选择极大值点,提高了算法的整体运行速度,实验表明了算法的高效性。

聚类实际应用处理对象多为海量数据和高维数据,具有很高的时间和空间复杂性。在处理海量TB级文本数据时,利用多台主机组成的群集系统,具有强大的并行计算能力。基于群集环境下的二分K均值聚类算法并行化研究,可以极大地提高工作效率,具有一定的现实应用意义。本文通过分析与研究,对二分K均值算法中所存在的不足进行了优化,并在群集环境中实现了并行化改进。

但O(n)的时间复杂度优于层次聚类的O(n2)时间复杂度。文献[4]提出了核二分K-Means聚类算法用以减少SVM训练集样本,以改善SVM的可扩展性。该算法通过在核特征空间快速产生相似大小均衡的簇集,能够有效地减少非线性支持向量机训练样本,随着采样时间缩短,保持测试精度的同时,加快了SVM训练算法速度。文献[5]在基于整体和局部相似性的序列聚类算法中,利用带剪枝策略的二分K-Means聚类算法对基于整体相似性的序列聚类。通过启发式方法获得二分K-Means聚类算法的质心,可使整个算法关于序列数t获得多项式时间复杂度。当序列数据集的自然分类情况较明显时,分别选最长序列和最短序列来作为初始化质心,采取序列数据的概貌向量指导编辑距离的计算次序的剪枝策略,可以有效地加速序列聚类算法的运行。文献[6]利用K-Means算法对索引对象进行聚类分析,构造新的聚类中心使其能处理具有多种形体的索引对象,在QR-树中引入超结点存储聚类结果,提出QCR-树空间索引结构来提高查询效率。

3 算法优化及并行化

3.1 二分K均值聚类算法

二分K均值聚类算法是基本K均值算法的变种,它基于以下思想:为得到K个簇,首先将所有数据集作为一个簇V,放到簇集S中。然后,循环从簇集S中取出一个簇,用基本

基金项目:国家自然科学基金资助项目(60973028);国家科技支撑计划基金资助项目(2009BAH42B02)

作者简介:张军伟(1971-),男,硕士研究生,主研方向:并行数据处理;王念滨、黄少滨,教授、博士;蔄世明,硕士 收稿日期:2011-03-18 E-mail:zjw_1997@yahoo.com.cn

2 相关研究

文献[3]为研究各种文档聚类技术效果,利用层次聚类算

法、K-Means聚类算法和二分K-Means聚类算法进行对比实验。结果表明二分K-Means聚类算法聚类效果要高于K-Means聚类算法,具有和层次聚类算法相当的聚类质量,

第1页

你可能喜欢

热门文档

相关文档

  • 一种改进的快速聚类算法及并行化研究

    二分K均值聚类算法优化及并... 3页 2财富值 二分K均值聚类算法优化及并.... 兰州大学 硕士学位论文 一种改进的快速聚类算法及并行化研究 姓名:祁小丽 申请...

  • 基于均衡化函数的k均值优化算法

    二分K均值聚类算法优化及并... 3页 2财富值 二分K均值聚类算法优化及并....华东计算技术研究所,上海200233;3中国科技大学计算机科学与技术系,合肥230027) 捕...

  • 并行k均值聚类算法的完备性证明与实现

    目前,虽然 k 均值算法的并行化已有过一些研究 [1,3-4], 但在聚类信息抽取... 百度图片搜索引擎优化方法 88份文档 2014全国高考状元联手分享状元笔记 衡水...

  • 学习特征权值对K_均值聚类算法的优化

    K 均值聚类算法的优化王熙照 1 2 1 王亚东 2 湛 燕 1 袁 方 1 保定 150001) 071002) ( 河北 大学数学与计算机科学学院机器学习研究中心 ( 哈尔 滨工业...

  • 学习特征权值对K_均值聚类算法的优化

    K2均值聚类算法的应用 收稿日期 :2002204210 ; 修回日期 :2002212204 学习特征权值对 K2均值聚类算法的优化 ( 河北大学数学与计算机科学学院机器学习研究中心 保定 ...

  • 3.基于蚁群算法原型系统优化的K均值聚类算法研究

    3.基于蚁群算法原型系统优化的K均值聚类算法研究_数学_自然科学_专业资料。基于 ACO 原型系统优化的 K 均值聚类算法研究摘要:聚类分析是图像识别、信息检索、数据...

  • 基于粒子群的K均值聚类算法

    基于粒子群的K均值聚类算法_IT/计算机_专业资料。2005 年 6 月 系统工程理论...粒子群优化算法( PSO) 是一种源于对鸟群捕食行为的研究而发明的进化技术, 同...

  • K-均值聚类算法的研究与改进

    和K一均值聚类算法相结合,较好地解决了K一均值 聚类算法初始中心的优化问题,...和Price.K在1995年提出来的一种新的进化算法,它是~种随机的并行全局搜索算法...

  • K均值聚类学习笔记

    K 均值聚类学习笔记 目录 聚类聚类 定量表述 聚类与分类相比较 聚类算法类型 ...使得每一次改进之后的分 组方案都较前一次优化,即同一分组中的元素相异度降低...

  • 遗传优化的K均值聚类算法

    遗传优化的K均值聚类算法 在K均值聚类算法中,K值需事先确定且在整个聚类过程中不能改变其大小,而按照经验K值划分所得的最终聚类结果一般并非最佳结果。通过求解...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email