A NOVEL HYBRID META-HEURISTIC ALGORITHM BASED ON BLACK HOLE AND HARMONY SEARCH FOR FUZZY CLUSTERING PROBLEM

Pham Minh Chuan; Le Hoang Son; Vu Khanh Quy; Nguyen Dinh Chien

Pham Minh Chuan Hung Yen University of Technology and Education
Le Hoang Son VNU Information Technology Institute, Vietnam National University
Vu Khanh Quy Hung Yen University of Technology and Education
Nguyen Dinh Chien Hung Yen University of Technology and Education

Keywords: Black Hole; Clustering quality; Fuzzy clustering problem; Harmony Search; Meta-heuristic algorithms

Abstract

Fuzzy clustering problem (FCP) is a process of assigning data elements to clusters associated with membership values showing the level of degrees that the elements belong to the groups. It is an optimization problem whose constraints involve the membership degrees. The conventional approach to solve the FCP problem is using an iterative scheme to calculate the membership degrees and the centers until the stopping conditions hold. This approach, named as Fuzzy C-Means (FCM), was invented by Bezdek et al. (1984). Nonetheless, it was shown to converge to local optimum or the saddle points. This leads to a natural question of how to define an algorithm that is able to escape from local optimal point to improve solution quality. In this paper, a new hybrid meta-heuristic algorithm for FCP called BHHS which combines the power of existing meta-heuristic frameworks such as Black Hole and Harmony Search is proposed. These two algorithms cooperate and support each other. The Black Hole part of the algorithm has the goal to find good candidate solution while the Harmony Search part has the goal to generate new candidate solutions for Black Hole when the event horizon of the Black Hole occurs. In addition, new best solutions of these two components are exchanged with each other to improve the quality of the search. The experiments on the benchmark UCI Machine Learning datasets indicate that the proposed framework outperforms the recent state-of-art algorithms for this problem.

References

Aha, D. (2018). Datasets. UCI Machine Learning Repository. Available at: https://archive.ics.uci.edu/ml/datasets. Accessed 26 March 2018.

Belacel, N., Hansen, P., & Mladenovic, N., Fuzzy J-means: a new heuristic for fuzzy clustering. Pattern Recognition, 2002, 35(10), pp. 2193-2200.

Benati, S., Categorical data fuzzy clustering: an analysis of local search heuristics. Computers & Operations Research, 2008, 35(3), pp. 766-775.

Bezdek, J. C., et al., FCM: the fuzzy c-means clustering algorithm. Computers & Geosciences, 1984, 10, 191-203.

Cuong, B.C., Son, L.H., Chau, H.T.M., Some Context Fuzzy Clustering Methods for Classification Problems. Proceedings of the 2010 Symposium on Information and Communication Technology, 2010, pp. 34 – 40.

Delgado, M., Skármeta, A. G., & Barberá, H. M. A tabu search approach to the fuzzy clustering problem. Proceedings of the Sixth IEEE International Conference on Fuzzy Systems, 1997, 1, pp. 125-130.

Dunn, J. C., A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters. Journal of Cybernetics, 1973, 3(3), pp. 32-57.

Geem, Z. W., Music-inspired harmony search algorithm: theory and applications. Springer Science & Business Media, 2009.

Geem, Z. W., Kim, J. H., & Loganathan, G.V., A new heuristic optimization algorithm: harmony search. Simulation, 2001, 76(2), pp. 60-68.

Hatamlou, A., Black hole: A new heuristic optimization approach for data clustering. Information Sciences, 2013, 222, pp. 175-184.

Long, H. V., Ali, M., Khan, M., & Tu, D. N., A novel approach for fuzzy clustering based on neutrosophic association matrix. Computers & Industrial Engineering, 2019, 127, pp. 687-697.

Izakian, H., & Abraham, A. Fuzzy C-means and fuzzy swarm for fuzzy clustering problem. Expert Systems with Applications, 2011, 38(3), pp. 1835-1838.

Liu, Y., Yi, Z., Wu, H., Ye, M., & Chen, K., A tabu search approach for the minimum sum-of-squares clustering problem. Information Sciences, 2008, 178(12), pp. 2680-2704.

Omran, M. G., Salman, A., & Engelbrecht, A. P., Dynamic clustering using particle swarm optimization with application in image segmentation. Pattern Analysis and Applications, 2006, 8(4), pp. 332-344.

Ozturk, C., Hancer, E., & Karaboga, D., Improved clustering criterion for image clustering with artificial bee colony algorithm. Pattern Analysis and Applications, 2014, pp. 1-13.

Pang, W., Wang, K. P., Zhou, C. G., & Dong, L. J., Fuzzy discrete particle swarm optimization for solving traveling salesman problem. 4th IEEE International Conference on Computer and Information Technology, 2004, pp. 796-800.

Parvin, H., & Minaei-Bidgoli, B., A clustering ensemble framework based on selection of fuzzy weighted clusters in a locally adaptive clustering algorithm. Pattern Analysis and Applications, 2015, 18(1), pp. 87-112.

Reinelt, G., TSPLIB - a library of sample instances for the TSP. Universität Heidelberg, 2015. Available at: http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95. Accessed 12 April 2015.