一种基于k维树的模糊C均值聚类算法

doi:10.3969/j.issn.1006-2475.2015.11.001

计算机与现代化 ›› 2015, Vol. 0 ›› Issue (11): 1-5+11.doi: 10.3969/j.issn.1006-2475.2015.11.001

• 数据库与数据挖掘 • 下一篇

一种基于k维树的模糊C均值聚类算法

（南京航空航天大学计算机科学与技术学院,江苏南京210016）

收稿日期:2015-08-03 出版日期:2015-11-12 发布日期:2015-11-16
作者简介:吴非(1991-),男,安徽池州人,南京航空航天大学计算机科学与技术学院硕士研究生,研究方向：数据库，数据挖掘；毛宇光(1962-),男,副教授,博士,研究方向：数据库系统及理论，数据挖掘与数据仓库，多值逻辑。
基金资助:
2014年中央高校基本科研业务费专项资金资助项目；南京航空航天大学研究生创新基地（实验室）开放基金资助项目（kfjj201460）

A Novel Fuzzy C-Means Algorithm Based on k-d Tree

（College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China）


Received:2015-08-03 Online:2015-11-12 Published:2015-11-16

摘要/Abstract

摘要： 初始聚类中心的选择极大地影响了模糊C均值聚类算法的性能，一个好的初始聚类中心能显著加快算法的收敛速度和减少算法的运行时间。本文提出一种新的基于k维树的模糊C均值聚类算法。通过使用k维树的方法分割原始数据集得到多个网格，并选取网格的加权中心作为新的数据点构成一个简化的数据集，在此基础上可快速查找一组距离实际聚类中心较近的初始聚类中心,显著减少模糊C聚类算法的迭代次数。通过在16个人工数据集和一组真实图像数据上的实验结果表明，数据集的数据量较大时，在不损失聚类精确度的情况下，本算法相对于普通的模糊C均值聚类算法，收敛速度提升了近2倍，算法的运行时间也缩短到经典FCM算法的一半以下。

关键词: 模糊C均值聚类算法, k维树, 初始聚类中心, 无监督学习

Abstract: Abstract: The performance of the Fuzzy C-Means(FCM) algorithm largely depends on the selection of the initial cluster center. A set of good initial cluster centers which are close to the actual final cluster center will not only speed up the rate of convergence but also reduce the overall processing time of the FCM dramatically. In this paper, we propose a novel FCM algorithm based on k-d tree which is a kind of multidimensional binary tree. The original data sets are split into several grids by using k-d tree. Then we form a new simplified data set by using the weighted centers of the grids, and based on which we find a good initial cluster center that is close to actual final cluster center so that reduce the iterations of FCM signally. The experiments on sixteen artificial datasets and real-life image data show that comparing with original FCM algorithm, the convergence rate of the proposed algorithm is advanced nearly twice as FCM algorithm, and the overall processing time reduce to less than half of the FCM.

Key words: Fuzzy C-Means cluster algorithm, k-d tree, initial cluster center, unsupervised learning

中图分类号:

TP274

吴非，毛宇光. 一种基于k维树的模糊C均值聚类算法[J]. 计算机与现代化, 2015, 0(11): 1-5+11.

WU Fei, MAO Yu-guang. A Novel Fuzzy C-Means Algorithm Based on k-d Tree[J]. Computer and Modernization, 2015, 0(11): 1-5+11.

参考文献

［1］修宇,王士同,吴锡生,等. 方向相似性聚类方法DSCM［J］. 计算机研究与发展, 2006,43(8):1425-1431.
［2］ Zadeh L A. Fuzzy sets［J］. Information and Control, 1965,8(3):338-353.
［3］ Dunn J C. Wellseparated clusters and optimal fuzzy partitions［J］. Journal of Cybernetics, 1974,4(1):95-104.
［4］ Bentley J L. Multidimensional binary search trees used for associative searching［J］. Communications of the ACM, 1975,18(9):509-517.
［5］ Arima C, Hakamada K, Okamoto M, et al. Modifiedfuzzy gap statistic for estimating preferable number of clusters in fuzzy k-means clustering［J］. Journal of Bioscience and Bioengingeering, 2008,105(3):273-281.
［6］ Zanaty E A. Determining the number of clusters for kernelized fuzzy C-means algorithms for automatic medical image segmentation［J］. Egyptian Informatics Journal, 2012,13(1):39-58.
［7］ Zhou Kai-le, Ding Shuai, Fu Chao, et al. Comparison and weighted summation type of fuzzy cluster validity indices［J］. International Journal of Computers, Communications & Control, 2014,9(3):370-378.
［8］ Kannan S R, Ramathilagam S, Chung P C. Effective fuzzy c-means clustering algorithms for data clustering problems［J］. Expert Systems with Applications, 2012,39(7):6292-6300.
［9］ Hung Ming-chuan, Yang Don-lin. An efficient fuzzy c-means clustering algorithm［C］// Proceedings IEEE International Conference on Data Mining,2001. 2001:225-232.［10］匡泰,朱清新,孙跃. FCM算法用于灰度图像分割的初始化方法的研究［J］. 计算机应用, 2006,26(4):784-786.
［11］边肇祺,张学工. 模式识别［M］. 北京:清华大学出版社, 2000:234-237.
［12］Pal N R, Bezdek J C. On cluster validity for the fuzzy c-means model ［J］. IEEE Transactions on Fuzzy Systems, 1995,3(3):370-379.
［13］Liu Hsiang-chuan, Jeng Bai-cheng, Yi Jeng-ming, et al. Fuzzy c-means algorithm based on standard mahalanobis distances［C］// Proceedings of the 2009 International Symposium on Information Processing. 2009:422-427.
［14］Chaira T. A novel intuitionistic fuzzy C means clustering algorithm and its application to medical images［J］. Applied Soft Computing, 2011,11(2):1711-1717.
［15］Vasuda P, Satheesh S. Improved fuzzy c-means algorithm for MR brain image segmentation［J］. International Journal on Computer Science and Engineering, 2010,2(5):1713-1715.
［16］Mitra S, Pedrycz W, Barman B. Shadowed c-means: Integrating fuzzy and rough clustering［J］. Pattern Recognition, 2010,43(4):1282-1291.
［17］章毓晋. 图象分割［M］. 北京:科学出版社, 2001.
［18］Marsaglia G, Bray T A. A convenient method for generating normal variables［J］. SIAM Review, 1964,6(3):260-264.

[1]	段桂芹1，邹臣嵩2，刘锋2. 基于优化初始聚类中心的K中心点算法[J]. 计算机与现代化, 2019, 0(04): 1-.
[2]	刘微，杨慧婕，刘守印. 基于ACCA-FCM和SVM-RFE的蓄电池SOH特征选择算法[J]. 计算机与现代化, 2018, 0(01): 11-18.
[3]	王丽红,何熊熊. 基于数据场的FCM改进算法[J]. 计算机与现代化, 2014, 0(6): 94-97.
[4]	宁波，宋砚. 基于无监督方法的视频中的人物识别[J]. 计算机与现代化, 2014, 0(12): 49-53.
[5]	胡伟. 一种改进的K_means聚类方法[J]. 计算机与现代化, 2012, 1(1): 22-24,5.

一种基于k维树的模糊C均值聚类算法

A Novel Fuzzy C-Means Algorithm Based on k-d Tree

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics

本文评价