Improved K-means algorithm based on clustering criterion function

Computer Engineering and Applications ›› 2011, Vol. 47 ›› Issue (11): 123-127.

• 数据库、信号与信息处理 • Previous Articles Next Articles

Improved K-means algorithm based on clustering criterion function

ZHANG Xuefeng1，ZHANG Guizhen2，LIU Peng1，2

1.School of Information Management and Engineering，Shanghai University of Finance & Economics，Shanghai 200433，China
2.School of Continuing Education，Shanghai University of Finance & Economics，Shanghai 200080，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-04-11 Published:2011-04-11

基于聚类准则函数的改进K-means算法

张雪凤1，张桂珍2，刘鹏1，2

1.上海财经大学信息管理与工程学院，上海 200433
2.上海财经大学继续教育学院，上海 200080

Abstract

Abstract: The criterion function used in K-means algorithm is the sum of the squared error，which may not work well for dataset containing clusters with different sizes and densities.In this study，the criterion function is improved by being defined as the sum of the weighted standard deviation，and the weight is the ratio of the number of points in each cluster to the whole points.The way each point being assigned to the centroid in the K-means algorithm is also modified：Instead of being assigned to the closest centroid，each point is assigned to the centroid which has minimum weighted distance.Experiments on simulation datasets show that the improved K-means algorithm significantly enhances the clustering quality by reducing the probability of misclassifying the points of big sparse clusters to its neighboring compact clusters.Experiments on UCI datasets show that the improved algorithm can obtain more compact cluster.Therefore，the improved K-means algorithm is effective.

Key words: K-means algorithm, cluster, clustering criterion function

摘要： K-means算法所使用的聚类准则函数是将数据集中各个簇的误差平方值直接相加而得到的，不能有效处理簇的密度不均且大小差异较大的数据集。为此，将K-means算法的聚类准则函数定义为加权的簇内标准差之和，权重为簇内数据对象数占总数目的比例。同时，调整了传统K-means算法将数据对象重新分配给簇的方法，采用一个数据对象到中心点的加权距离代替传统K-means算法中的距离，将数据对象分配给使加权距离最小的中心点所在的簇。实验结果表明，针对模拟数据集的聚类，改进K-means算法可以明显减少大而稀的簇中数据对象被错误地分配到相邻的小而密簇的可能性，改善了聚类的质量；针对UCI数据集的聚类，改进算法使得各个簇更为紧凑，从而验证了改进K-means算法的有效性。

关键词: K-means算法, 簇, 聚类准则函数

ZHANG Xuefeng1，ZHANG Guizhen2，LIU Peng1，2. Improved K-means algorithm based on clustering criterion function[J]. Computer Engineering and Applications, 2011, 47(11): 123-127.

张雪凤1，张桂珍2，刘鹏1，2. 基于聚类准则函数的改进K-means算法[J]. 计算机工程与应用, 2011, 47(11): 123-127.

[1]	LAN Hong, HUANG Min. Fusion of KNN Optimized Density Peaks and FCM Clustering Algorithm [J]. Computer Engineering and Applications, 2021, 57(9): 81-88.
[2]	GUO Xiaojing, SUI Haoda. Application of Improved YOLOv3 in Foreign Object Debris Target Detection on Airfield Pavement [J]. Computer Engineering and Applications, 2021, 57(8): 249-255.
[3]	LI Li, JI Xinyuan, SONG Song. Prediction Model for Number of Software Defects in Loop [J]. Computer Engineering and Applications, 2021, 57(7): 158-163.
[4]	YANG Fang, YIN Xi, SI Jianhui, LIU Hongyuan, WANG Xue. Mathematical Expression Similarity Calculation Method Based on Focus Clustering [J]. Computer Engineering and Applications, 2021, 57(6): 88-93.
[5]	ZHAO Fan, ZHANG Lin, WEN Zhiquan, YANG Linlin, LIN Guangfeng. Direct and Efficient Natural Scene Chinese Character Approaching Spotting Method [J]. Computer Engineering and Applications, 2021, 57(6): 159-167.
[6]	HUO Guangyu, ZHANG Yong, SUN Yanfeng, YIN Baocai. Research on Archive Data Intelligent Classification Based on Semantic [J]. Computer Engineering and Applications, 2021, 57(6): 247-253.
[7]	PENG Qihui, XUAN Shibin, GAO Qing. Distribution Automatic Threshold Density Peak Clustering Algorithm [J]. Computer Engineering and Applications, 2021, 57(5): 71-78.
[8]	LI Yongzhen, LIAO Husheng. Multi-view Clustering via Graph Convolutional Neural Network [J]. Computer Engineering and Applications, 2021, 57(5): 115-122.
[9]	WANG Changlong, ZHANG Yuandong, MIAO Hong, YANG Yuheng. Application of Double Channel Convolutional Neural Network in Pumpkin Diseases Identification [J]. Computer Engineering and Applications, 2021, 57(5): 183-189.
[10]	HU Xiaomin, WANG Mingfeng, ZHANG Shourong, LI Min. New Differential Evolution with Particle Swarm Optimization Algorithm for Text Clustering [J]. Computer Engineering and Applications, 2021, 57(4): 61-67.
[11]	WANG Junling, LU Xinming. Video Key Frame Extraction Algorithm Based on Semantic Correlation [J]. Computer Engineering and Applications, 2021, 57(4): 192-198.
[12]	WANG Fuyin, ZHANG Desheng, ZHANG Xiao. Adaptive Density Peaks Clustering Algorithm Combining with Whale Optimization Algorithm [J]. Computer Engineering and Applications, 2021, 57(3): 94-102.
[13]	CHEN Junfeng, ZHENG Zhongtuan. Over-Sampling Method on Imbalanced Data Based on WKMeans and SMOTE [J]. Computer Engineering and Applications, 2021, 57(23): 106-112.
[14]	ZHANG Zhonglin, ZHAO Yu, YAN Guanghui. Natural Neighbor Density Extremum Clustering Algorithm [J]. Computer Engineering and Applications, 2021, 57(23): 200-210.
[15]	MEI Jie, WEI Yuanyuan, XU Taosheng. Fusion Clustering Algorithm Based on Multi-Prototypes Using Density Peaks [J]. Computer Engineering and Applications, 2021, 57(22): 78-85.

Improved K-means algorithm based on clustering criterion function

基于聚类准则函数的改进K-means算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics