基于均衡化函数的快速K-means算法

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (3): 189-191.

基于均衡化函数的快速K-means算法

施培蓓¹,钱雪忠¹,汪中²

1.江南大学信息工程学院，江苏无锡 214122
2.中国科技大学计算机科学与技术系，合肥 230027

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2008-01-21 发布日期:2008-01-21
通讯作者: 施培蓓

Algorithm for fast K-means based on balanced function

SHI Pei-bei¹,QIAN Xue-zhong¹,WANG Zhong²

1.School of Information Engineering，Southern Yangtze University，Wuxi，Jiangsu 214122，China
2.Department of Computer Science，University of Science and Technology of China，Hefei 230027，China

Received:1900-01-01 Revised:1900-01-01 Online:2008-01-21 Published:2008-01-21
Contact: SHI Pei-bei

摘要/Abstract

摘要： 聚类分析的应用很广泛，传统的K-means算法要求事先给定k值，限制了很多实际的应用，由于聚类的质量主要考察类内的紧凑性和类间的距离，提出了均衡化的评价函数，使用最近邻搜索算法减少算法的计算量，不仅自动生成聚类的数目，同时均衡了类内差异和类间差异对于聚类结果的影响，实验结果证明改进的K-means算法的有效性。

关键词: K-均值算法, 类内差异, 类间差异, 均衡化函数, 扩展的部分失真搜索

Abstract: Clustering analysis is widely used.In the usage of traditional K-means algorithm，value K must be confirmed in advance.This demand restricts a large number of practical applications.The quality of clustering mainly depends on the compaction and the distance among clusters.This paper presents a balanced evaluative function and it uses a nearest neighborhood search algorithm to reduce the amount of computation.The algorithm not only generates the number of clusters automatically，at the same time the affections on the clustering result coming from the differences between and within the clusters are well balanced.Results of the experiment prove the efficiency of the improved K-means algorithm.

Key words: K-means algorithm, within cluster variation, between cluster variation, balanced function, EPDS

施培蓓¹,钱雪忠¹,汪中². 基于均衡化函数的快速K-means算法[J]. 计算机工程与应用, 2008, 44(3): 189-191.

SHI Pei-bei¹,QIAN Xue-zhong¹,WANG Zhong². Algorithm for fast K-means based on balanced function[J]. Computer Engineering and Applications, 2008, 44(3): 189-191.

[1]	王建仁，马鑫，段刚龙. 改进的K-means聚类k值选择算法[J]. 计算机工程与应用, 2019, 55(8): 27-33.
[2]	周本金，陶以政，纪斌，谢永辉. 最小化误差平方和k-means初始聚类中心优化方法[J]. 计算机工程与应用, 2018, 54(15): 48-52.
[3]	王兆丰，单甘霖. 一种基于k-均值的DBSCAN算法参数动态选择方法[J]. 计算机工程与应用, 2017, 53(3): 80-86.
[4]	王春芳，高煜妤. 基于KL距离的KPCA人脸识别算法[J]. 计算机工程与应用, 2016, 52(9): 130-134.
[5]	王会青，陈俊杰，郭凯. 启发式初始化独立的k-均值算法研究[J]. 计算机工程与应用, 2012, 48(11): 129-132.
[6]	施海滨，周勇. 混合聚类彩色图像分割方法研究[J]. 计算机工程与应用, 2011, 47(9): 181-184.
[7]	洪亮亮，罗可. 改进的基于遗传算法的粗糙聚类方法[J]. 计算机工程与应用, 2010, 46(25): 142-145.
[8]	孙洋，罗可. 基于改进的粒子群算法的聚类算法[J]. 计算机工程与应用, 2009, 45(33): 132-134.
[9]	刘盈盈,石跃祥,莫浩澜. 基于改进K-均值算法在彩色图像分割中的应用[J]. 计算机工程与应用, 2008, 44(29): 191-192.
[10]	段霞霞,刘彦明,李小平,杨一展. 基于ART2改进算法的故障聚类研究[J]. 计算机工程与应用, 2008, 44(15): 56-57.
[11]	钱光超,贾瑞玉,张然,李龙澍. 基于遗传聚类算法的离群点检测[J]. 计算机工程与应用, 2008, 44(11): 155-157.
[12]	刘艳丽,刘希玉. 一种基于密度的K-均值算法[J]. 计算机工程与应用, 2007, 43(32): 153-155.
[13]	刘艳丽¹,刘希云². 一种基于密度的K-均值算法[J]. 计算机工程与应用, 2007, 43(32): 153-155.