Scalable Clustering by Truncated Fuzzy <i>c</i>-means

Guojun Gan; Qiujun Lan; Shiyang Sima; Guojun Gan; Qiujun Lan; Shiyang Sima

doi:10.3934/bdia.2016007

Big Data and Information Analytics

2016, Volume 1, Issue 2&3: 247-259. doi: 10.3934/bdia.2016007

Previous Article Next Article

Scalable Clustering by Truncated Fuzzy c-means

Guojun Gan ^{1
,},
Qiujun Lan ^{2
,},
Shiyang Sima ^{3
,}

1.
Department of Mathematics, University of Connecticut, 341 Mansfield Road, Storrs, CT 06269-1009, USA
2.
Business School, Hunan University, Changsha, Hunan 410082, China
3.
Columbian College of Arts & Sciences, George Washington University, Washington, D.C., 20052, USA

Received: 01 July 2016 Revised: 01 August 2016 Published: 01 July 2016
Primary: 62H30, 68T10, 91C20; Secondary: 62P10

Most existing clustering algorithms are slow for dividing a large dataset into a large number of clusters. In this paper, we propose a truncated FCM algorithm to address this problem. The main idea behind our proposed algorithm is to keep only a small number of cluster centers during the iterative process of the FCM algorithm. Our numerical experiments on both synthetic and real datasets show that the proposed algorithm is much faster than the original FCM algorithm and the accuracy is comparable to that of the original FCM algorithm.
- Data clustering,
- fuzzy c-means,
- scalable clustering
Citation: Guojun Gan, Qiujun Lan, Shiyang Sima. 2016: Scalable Clustering by Truncated Fuzzy c-means, Big Data and Information Analytics, 1(2&3): 247-259. doi: 10.3934/bdia.2016007

Related Papers:

Abstract

Most existing clustering algorithms are slow for dividing a large dataset into a large number of clusters. In this paper, we propose a truncated FCM algorithm to address this problem. The main idea behind our proposed algorithm is to keep only a small number of cluster centers during the iterative process of the FCM algorithm. Our numerical experiments on both synthetic and real datasets show that the proposed algorithm is much faster than the original FCM algorithm and the accuracy is comparable to that of the original FCM algorithm.

References

[1]	C. C. Aggarwal and C. K. Reddy (eds.), Data Clustering: Algorithms and Applications, CRC Press, Boca Raton, FL, USA, 2014. MR3307640
[2]	D. Arthur and S. Vassilvitskii, k-means++: The advantages of careful seeding, in Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '07, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2007, 1027-1035. MR2485254
[3]	Bezdek J. C., Ehrlich R., Full W. (1984) FCM: The fuzzy c-means clustering algorithm. Computers & Geosciences 10: 191-203.
[4]	J. Bezdek, Pattern Recognition with Fuzzy Objective Function Algorithms, Kluwer Academic Publishers, Norwell, MA, USA, 1981. MR631231
[5]	A. Broder, L. Garcia-Pueyo, V. Josifovski, S. Vassilvitskii and S. Venkatesan, Scalable kmeans by ranked retrieval, in Proceedings of the 7th ACM International Conference on Web Search and Data Mining, WSDM '14, ACM, 2014, 233-242. 10.1145/2556195.2556260
[6]	Cannon R. L., Dave J. V., Bezdek J. (1986) Efficient implementation of the fuzzy c-means clustering algorithms. IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-8: 248-255.
[7]	Cheng T. W., Goldgof D. B., Hall L. O. (1998) Fast fuzzy clustering. Fuzzy Sets and Systems 93: 49-56.
[8]	M. de Souto, I. Costa, D. de Araujo, T. Ludermir and A. Schliep, Clustering cancer gene expression data: A comparative study, BMC Bioinformatics, 9 (2008), p497. 10.1186/1471-2105-9-497
[9]	Dunn J. C. (1973) A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters. Journal of Cybernetics 3: 32-57.
[10]	G. Gan, Data Clustering in C++: An Object-Oriented Approach, Data Mining and Knowledge Discovery Series, Chapman & Hall/CRC Press, Boca Raton, FL, USA, 2011. 10.1201/b10814 MR
[11]	Gan G. (2013) Application of data clustering and machine learning in variable annuity valuation. Insurance: Mathematics and Economics 53: 795-801.
[12]	G. Gan, A multi-asset Monte Carlo simulation model for the valuation of variable annuities, in Proceedings of the Winter Simulation Conference, 2015, 3162-3163. 10.1109/WSC.2015.7408450
[13]	Gan G., Lin S. (2015) Valuation of large variable annuity portfolios under nested simulation: A functional data approach. Insurance: Mathematics and Economics 62: 138-150.
[14]	Gan G., Ng M. K.-P. (2015) Subspace clustering using affinity propagation. Pattern Recognition 48: 1455-1464.
[15]	Gan G., Ng M. K.-P. (2015) Subspace clustering with automatic feature grouping. Pattern Recognition 48: 3703-3713.
[16]	Gan G., Zhang Y., Dey D. K. (2016) Clustering by propagating probabilities between data points. Applied Soft Computing 41: 390-399.
[17]	Hathaway R. J., Bezdek J. C. (2006) Extending fuzzy and probabilistic clustering to very large data sets. Computational Statistics & Data Analysis 51: 215-234.
[18]	Havens T., Bezdek J., Leckie C., Hall L., Palaniswami M. (2012) Fuzzy c-means algorithms for very large data. IEEE Transactions on Fuzzy Systems 20: 1130-1146.
[19]	M.-C. Hung and D.-L. Yang, An efficient fuzzy c-means clustering algorithm, in Proceedings IEEE International Conference on Data Mining, 2001, 225-232.
[20]	Ji Z.-X., Sun Q.-S., Xia D.-S. (2011) A modified possibilistic fuzzy c-means clustering algorithm for bias field estimation and segmentation of brain MR image. Computerized Medical Imaging and Graphics 35: 383-397.
[21]	Jiang D., Tang C., Zhang A. (2004) Cluster analysis for gene expression data: A survey. IEEE Transactions on Knowledge and Data Engineering 16: 1370-1386.
[22]	Klawonn F. (2004) Fuzzy clustering: Insights and a new approach. Mathware & Soft Computing 11: 125-142.
[23]	Kolen J. F., Hutcheson T. (2002) Reducing the time complexity of the fuzzy c-means algorithm. IEEE Transactions on Fuzzy Systems 10: 263-267.
[24]	T. Kwok, K. Smith, S. Lozano and D. Taniar, Parallel fuzzy c-means clustering for large data sets, in Euro-Par 2002 Parallel Processing (eds. B. Monien and R. Feldmann), vol. 2400 of Lecture Notes in Computer Science, Springer, 2002, 365-374. 10.1007/3-540-45706-2_48
[25]	Liu H., Zhao F., Jiao L. (2012) Fuzzy spectral clustering with robust spatial information for image segmentation. Applied Soft Computing 12: 3636-3647.
[26]	J. D. MacCuish and N. E. MacCuish, Clustering in Bioinformatics and Drug Discovery, CRC Press, Boca Raton, FL, 2010. 10.1201/b10331
[27]	J. Macqueen, Some methods for classification and analysis of multivariate observations, in Proceedings of the 5th Berkeley Symposium on Mathematical Statistics andProbability (eds. L. LeCam and J. Neyman), University of California Press, Berkely, CA, USA, 1 (1967), 281-297. MR0214227
[28]	Shalom S. A. A., Dash M., Tue M. (2008) Graphics hardware based efficient and scalable fuzzy c-means clustering. Proceedings of the 7th Australasian Data Mining Conference 87: 179-186.
[29]	Stetco A., Zeng X.-J., Keane J. (2015) Fuzzy c-means++: Fuzzy c-means with effective seeding initalization. Expert Systems with Applications 42: 7541-7548.

Reader Comments

Your name:*

Email:*
© 2016 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)