A new variant of black hole algorithm based on multi population and levy flight for clustering problem - Haneen Abdul Wahab, Abdul Raheem (2020)
Data clustering is one of the most popular branches in machine learning and data analysis. Partitioning-based type of clustering algorithms, such as K-means, is prone to the problem of producing a set of clusters that is far from perfect due to its probabilistic nature. The clustering process starts with some random partitions at the beginning, and it tries to improve the partitions progressively. Different initial partitions can result in different final clusters. Trying through all the possible candidate clusters for the perfect result is too time consuming. Metaheuristic algorithm aims to search for global optimum in high dimensional problems. Meta-heuristic algorithm has been successfully implemented on data clustering problems seeking a near optimal solution in terms of quality of the resultant clusters. Recently, nature-inspired algorithms have been proposed and utilized for solving the optimization problems in general, and data clustering problem in particular. Black Hole (BH) optimization algorithm has been underlined as a solution for data clustering problems. The BH is a population-based metaheuristic that emulates the phenomenon of the BH in the universe. In this instance, every solution in motion within the search space represents an individual star. The original BH has shown a superior performance when applied on a benchmark dataset; however, it lacks exploration capabilities. In keeping with this limitation, this study proposes a new variant of BH through two different modifications on the original BH. The first modification is the integration of BH algorithm and levy flight, which result in data clustering method, namely “Levy Flight Black Hole (LBH)”. In LBH, the movement of each star mainly depends on the step size generated by the Levy distribution. Therefore, the star explores a far area from the current BH when the value step size is big, and vice versa. The second modification is the multiple population BH that is proposed as a generalization to the BH algorithm, in which the algorithm was not reliant upon the best solution but rather on a set of best solutions generated, called “MBH”. As a result, a new variant of BH for high dimensional datasets which is called multiple population levy black hole (MLBH) has been proposed for handling normal and high dimensional datasets through the integration of LBH and MBH. The obtained results were compared with the BH and previous optimization algorithms for both test functions as well as data clustering in terms of normal and high dimensional datasets. Overall, the experimental outcomes and analysis of the obtained results indicated that the proposed algorithms have satisfied most of the required criteria. Furthermore, the results revealed a high convergence rate, upon which the algorithm’s performance was subjected to data clustering problems and investigated using six real datasets. The datasets were retrieved from the UCI machine-learning laboratory. The future research directions are also discussed in the study.