A fast particle swarm optimization for clustering
详细信息 查看全文
- 作者：Chun-Wei Tsai (1) (2)
Ko-Wei Huang (2)
Chu-Sing Yang (2)
Ming-Chao Chiang (3)
1. Department of Applied Informatics and Multimedia ; Chia Nan University of Pharmacy and Science ; Tainan ; 71710 ; Taiwan ; R.O.C.
2. Institute of Computer and Communication Engineering ; Department of Electrical Engineering ; National Cheng Kung University ; Tainan ; 70101 ; Taiwan ; R.O.C.
3. Department of Computer Science and Engineering ; National Sun Yat-sen University ; Kaohsiung ; 80424 ; Taiwan ; R.O.C. - 关键词：Clustering ; Particle swarm optimization ; Pattern reduction
- 刊名：Soft Computing - A Fusion of Foundations, Methodologies and Applications
- 出版年：2015
- 出版时间：February 2015
- 年：2015
- 卷：19
- 期：2
- 页码：321-338
- 全文大小：870 KB
- 参考文献：1. Abraham A, Das S, Konar A (2007) Kernel based automatic clustering using modified particle swarm optimization algorithm, In: Proceedings of the Annual Conference on Genetic and Evolutionary Computation, pp 2鈥?
2. Ahmadi A, Karray F, Kamel M (2007a) Cooperative swarms for clustering phoneme data, In: Proceedings of the IEEE/SP Workshop on Statistical, Signal Processing, pp 606鈥?10
3. Ahmadi A, Karray F, Kamel M (2007b) Multiple cooperating swarms for data clustering, In: Proceedings of the IEEE Swarm Intelligence Symposium, pp 206鈥?12
4. Ahmadyfard A, Modares H (2008) Combining PSO and \(k\) -means to enhance data clustering, In: Proceedings of the International Symposium on Telecommunications, pp 688鈥?91
5. Bagirov AM, Ugon J, Webb D (2011) Fast modified global \(k\) -means algorithm for incremental cluster construction. Patt Recogn 44(4):866鈥?76 CrossRef
6. Banks A, Vincent J, Anyakoha C (2008) A review of particle swarm optimization. part II: hybridisation, combinatorial, multicriteria and constrained optimization, and indicative applications. Nat Comput 7(1):109鈥?24 CrossRef
7. Bradley PS, Fayyad UM (1998) Refining initial points for \(k\) -means clustering, In: Proceedings of the International Conference on Machine Learning, pp 91鈥?9
8. Bradley PS, Fayyad UM, Reina C (1998) Scaling clustering algorithms to large databases, In: Proceedings of the International Conference on Knowledge Discovery and Data Mining, pp 9鈥?5
9. Bratton D, Kennedy J (2007) Defining a standard for particle swarm optimization, In: Proceedings of the IEEE Swarm Intelligence Symposium, pp 120鈥?27
10. Buzo A, Gray AH Jr, Gray RM, Markel JD (1980) Speech coding based upon vector quantization. IEEE Trans Acoust Speech Signal Proc 28(5):562鈥?74 CrossRef
11. Cai W, Chen S, Zhang D (2007) Fast and robust fuzzy \(c\) -means clustering algorithms incorporating local information for image segmentation. Patt Recogn 40(3):825鈥?38 CrossRef
12. Chen CY, Ye F (2004) Particle swarm optimization algorithm and its application to clustering analysis, In: Proceedings of the IEEE International Conference on Networking, Sensing & Control, 2:789鈥?794
13. Chen CY, Feng HM, Ye F (2006) Automatic particle swarm optimization clustering algorithm. Intern J Electr Eng 13(4):379鈥?87
14. Cheng TW, Goldgof DB, Hall LO (1998) Fast fuzzy clustering. Fuzzy sets and systems 93(1):49鈥?6
15. Chen Q, Yang J, Gou J (2005) Image compression method using improved PSO vector quantization, In: Proceedings of the Advances in Natural Computation, pp 490鈥?95
16. Chiang MC, Tsai CW, Yang CS (2011) A time-efficient pattern reduction algorithm for \(k\) -means clustering. Info Sci 181(4):716鈥?31 CrossRef
17. Cohen SCM, de Castro LN (2006) Data clustering with particle swarms, In: Proceedings of the IEEE Congress on Evolutionary Computation, pp 1792鈥?798
18. Das S, Abraham A, Konar A (2008) Automatic kernel clustering with a multi-elitist particle swarm optimization algorithm. Patt Recogn Lett 29(5):688鈥?99 CrossRef
19. Derrac J, Garc铆a S, Molina D, Herrera F (2011) A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm Evol Comput 1(1):3鈥?8 CrossRef
20. Ding C, He X (2004) \(K\) -means clustering via principal component analysis, In: Proceedings of the International Conference on Machine Learning, 69:225鈥?32
21. Elkan C (2003) Using the triangle inequality to accelerate \(k\) -means, In: Proceedings of the International Conference on Machine Learning, pp 147鈥?53
22. Engelbrecht AP (2006) Fundamentals of computational swarm intelligence. Wiley, West Sussex, England
23. Eschrich S, Ke J, Hall LO, Goldgof DB (2003) Fast accurate fuzzy clustering through data reduction. IEEE Trans Fuzzy Syst 11(2):262鈥?70 CrossRef
24. Ester M, Kriegel H-P, Sander J, Xu X (1996) A density-based algorithm for discovering clusters in large spatial databases with noise, In: Proceedings of the International Conference on Knowledge Discovery and Data Mining, pp 226鈥?31
25. Feng HM, Chen CY, Ye F (2007) Evolutionary fuzzy particle swarm optimization vector quantization learning scheme in image compression. Exp Syst Appl 32(1):213鈥?22 CrossRef
26. Getz G, Gal H, Kela I, Notterman DA, Domany E (2003) Coupled two-way clustering analysis of breast cancer and colon cancer gene expression data. Bioinformatics 19(9):1079鈥?089 CrossRef
27. Guha S, Meyerson A, Mishra N, Motwani R, O鈥機allaghan L (2003) Clustering data streams: theory and practice. IEEE Trans Knowl Data Eng 15(3):515鈥?28 CrossRef
28. Hammouda KM, Kamel MS (2004) Efficient phrase-based document indexing for web document clustering. IEEE Trans Knowl Data Eng 16(10):1279鈥?296 CrossRef
29. Jain AK, Murty MN, Flynn PJ (1999) Data clustering: a review. ACM Comput Surv 31(3):264鈥?23 CrossRef
30. Jarboui B, Cheikh M, Siarry P, Rebai A (2007) Combinatorial particle swarm optimization (CPSO) for partitional clustering problem. Appl Math Comput 192(2):337鈥?45 CrossRef
31. Karthi R, Arumugam S, RameshKumar K (2009) A novel discrete particle swarm clustering algorithm for data clustering, In: Proceedings of the Bangalore Annual Compute Conference, pp 16:1鈥?6:4
32. Kaukoranta T, Fr盲nti P, Nevalainen O (2000) A fast exact GLA based on code vector activity detection. IEEE Trans Image Proc 9(8):1337鈥?342 CrossRef
33. Kekre HB, Sarode TK (2009) Fast codebook search algorithm for vector quantization using sorting technique, In: Proceedings of the International Conference on Advances in Computing, Communication and Control, pp 317鈥?25
34. Kogan J (2007) Introduction to clustering large and high-dimensional data. Cambridge University Press, New York
35. Kulkarni RV, Venayagamoorthy GK (2011) Particle swarm optimization in wireless-sensor networks: a brief survey. IEEE Trans Syst Man Cybernet Part C 41(2):262鈥?67 CrossRef
36. Kuo RJ, Wang MJ, Huang TW (2011) An application of particle swarm optimization algorithm to clustering analysis. Soft Comput 15(3):533鈥?42 CrossRef
37. Lai JZC, Liaw YC, Liu J (2008) A fast VQ codebook generation algorithm using codeword displacement. Patt Recogn 41(1):315鈥?319
38. Lai JZC, Huang TJ, Liaw YC (2009) A fast \(k\) -means clustering algorithm using cluster center displacement. Patt Recogn 42(11):2551鈥?556 CrossRef
39. Leuski A (2001) Evaluating document clustering for interactive information retrieval, In: Proceedings of the International Conference on Information and Knowledge Management, pp 33鈥?0
40. Li C, Zhou J, Kou P, Xiao J (2012) A novel chaotic particle swarm optimization based fuzzy clustering algorithm. Neurocomputing 83:98鈥?09 CrossRef
41. Lughofer E (2008) Extensions of vector quantization for incremental clustering. Patt Recogn 41(3):995鈥?011 CrossRef
42. Lu Y, Lu S, Fotouhi F, Deng Y, Brown SJ (2004) FGKA: a fast genetic \(k\) -means clustering algorithm, In: Proceedings of the ACM Symposium on Applied, Computing, pp 622鈥?23
43. Marinakis Y, Marinaki M, Matsatsinis N (2008) A stochastic nature inspired metaheuristic for clustering analysis. Intern J Bus Intel Data Mining 3(1):30鈥?4 CrossRef
44. Miranda V, Keko H, Duque AJ (2008) Stochastic star communication topology in evolutionary particle swarms (EPSO). Intern J Comput Intel Res 4(2):105鈥?16
45. Ng RT, Han J (2002) CLARANS: a method for clustering objects for spatial data mining. IEEE Trans Knowl Data Eng 14(5):1003鈥?016 CrossRef
46. Niknam T, Amiri B, Olamaei J, Arefi A (2009) An efficient hybrid evolutionary optimization algorithm based on PSO and SA for clustering. J Zhejiang Univ SCI A 10(4):512鈥?19 CrossRef
47. Omran MGH, Salman AA, Engelbrecht AP (2002) Image classification using particle swarm optimization, In: Proceedings of the Asia-Pacific Conference on Simulated Evolution and Learning, pp 370鈥?74
48. Omran MGH, Engelbrecht AP, Salman AA (2005a) Particle swarm optimization method for image clustering. Intern J Patt Recogn Artif Intel 19(3):297鈥?21
49. Omran MGH, Engelbrecht AP, Salman AA (2005b) Dynamic clustering using particle swarm optimization with application in unsupervised image segmentation. Proc World Acad Sci Eng Technol 2005:199鈥?04
50. Omran MGH, Salman AA, Engelbrecht AP (2006) Dynamic clustering using particle swarm optimization with application in image segmentation. Patt Anal Appl 8(4):332鈥?44 CrossRef
51. Ordonez C, Omiecinski E (2004) Efficient disk-based \(k\) -means clustering for relational databases. IEEE Trans Knowl Data Eng 16(8):909鈥?21
52. Parsopoulos KE, Vrahatis MN (2010) Particle swarm optimization and intelligence: advances and applications. IGI Global Snippet
53. Paterlini S, Krink T (2006) Differential evolution and particle swarm optimisation in partitional clustering. Comput Stat Data Anal 50(5):1220鈥?247 CrossRef
54. Ratnaweera A, Halgamuge SK, Watson HC (2004) Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients. IEEE Trans Evol Comput 8(3):240鈥?55 CrossRef
55. Shi Y, Eberhart RC (1999) Empirical study of particle swarm optimization, In: Proceedings of the Congress on Evolutionary Computation, 3:1945鈥?950
56. Theodoridis S, Koutroumbas K (2009) Chapter 16: cluster validity, in pattern recognition, 4th edn. Academic Press, Boston
57. Tillett JC, Rao RM, Sahin F, Rao TM (2003) Particle swarm optimization for the clustering of wireless sensors, In: Proceedings of SPIE 5100:73鈥?3
58. Tsai CW, Yang CS, Chiang MC (2007) A time efficient pattern reduction algorithm for \(k\) -means based clustering, In: Proceeding of the IEEE International Conference on Systems, Man and Cybernetics, pp 504鈥?09
59. Tsai CW, Lin CF, Chiang MC, Yang CS (2010) A fast particle swarm optimization algorithm for vector quantization. ICIC Expr Lett Part B 1(2):137鈥?43
60. van der Merwe DW, Engelbrecht AP (2003) Data clustering using particle swarm optimization, In: Proceedings of IEEE Congress on Evolutionary Computation, 1:215鈥?20
61. Xiang S, Nie F, Zhang C (2008) Learning a Mahalanobis distance metric for data clustering and classification. Patt Recogn 41(12):3600鈥?612 CrossRef
62. Xiao X, Dow ER, Eberhart R, Miled ZB, Oppelt RJ (2003) Gene clustering using self-organizing maps and particle swarm optimization, In: Proceedings of the International Symposium on Parallel and Distributed Processing
63. Xu R, Wunsch-II DC (2005) Survey of clustering algorithms. IEEE Trans Neural Netw 16(3):645鈥?78 CrossRef
64. Xu R, Wunsch-II DC (2008) Clustering. Wiley, Hoboken, New Jersey
65. Xu W, Liu X, Gong Y (2003) Document clustering based on non-negative matrix factorization, In: Proceedings of the International ACM SIGIR Conference on Research and Development in, Information Retrieval, pp 267鈥?73
66. Yang CS, Chuang LY, Ke CH, Yang CH (2008) Comparative particle swarm optimization (CPSO) for solving optimization problems, In: Proceedings of the International Conference on Research, Innovation and Vision for the Future in Computing & Communication Technologies, pp 86鈥?0
67. Zhang WF, Liu CC, Yan H (2010) Clustering of temporal gene expression data by regularized spline regression and an energy based similarity measure. Patt Recogn 43(12):3969鈥?976
68. Zhang T, Ramakrishnan R, Livny M (1996) BIRCH: an efficient data clustering method for very large databases, In: Proceedings of the ACM SIGMOD International Conference on Management of Data, pp 103鈥?14 - 刊物类别：Engineering
- 刊物主题：Numerical and Computational Methods in Engineering
Theory of Computation
Computing Methodologies
Mathematical Logic and Foundations
Control Engineering - 出版者：Springer Berlin / Heidelberg
- ISSN：1433-7479
文摘
This paper presents a high-performance method to reduce the time complexity of particle swarm optimization (PSO) and its variants in solving the partitional clustering problem. The proposed method works by adding two additional operators to the PSO-based algorithms. The pattern reduction operator is aimed to reduce the computation time, by compressing at each iteration patterns that are unlikely to change the clusters to which they belong thereafter while the multistart operator is aimed to improve the quality of the clustering result, by enforcing the diversity of the population to prevent the proposed method from getting stuck in local optima. To evaluate the performance of the proposed method, we compare it with several state-of-the-art PSO-based methods in solving data clustering, image clustering, and codebook generation problems. Our simulation results indicate that not only can the proposed method significantly reduce the computation time of PSO-based algorithms, but it can also provide a clustering result that matches or outperforms the result PSO-based algorithms by themselves can provide.