Intelligent Optimization Algorithms For Several Clustering Problems

In recent years,due to the rapid development of the Internet and the popularization of database technology,various information resources have grown exponentially.The widespread use of sensing and storage technologies and the dramatic growth of applications such as digital imaging and video surveillance have created many high-volume,highdimensional data sets.It is an urgent need to find information of interest in a large data ocean to help make a reasonable decision.Data Mining technology has been widely studied and achieved great success in this background.As a powerful tool for Data Mining,Clustering Analysis has attracted more and more attention and has been successfully applied in many fields such as image processing,pattern recognition,machine learning and information retrieval.Cluster Analysis is a multivariate statistical analysis method that classifies samples or data points according to the idea of “birds of a feather flock together”.Clustering is the process of classifying data into different classes or clusters,so that objects in the same cluster have great similarity,while objects in different clusters have great heterogeneity.In this work,K-means and other partition-based clustering methods are mainly studied.However,K-means is very sensitive to initial solutions and is easy to fall into local optimum.Therefore,several intelligent optimization algorithms are introduced in this paper to solve several clustering problems.When the intelligent optimization algorithm deals with many practical problems,it can get good quality solutions in a reasonable time.Common intelligent optimization algorithms include greedy algorithm,hill climbing algorithm,simulated annealing algorithm,genetic algorithm,tabu search,variable neighborhood search algorithm,particle swarm optimization algorithm,etc.In this work,tabu search algorithm,hybrid evolutionary algorithm,memetic algorithm and other intelligent optimization algorithms were successfully applied to several clustering problems.First,we propose a very effective heuristic algorithm: tabu search method to solve the capacitated clustering problem.For highly constrained problems,considering infeasible solutions in the search process may help better explore the search space rather than limit the search process to the feasible region.So the proposed algorithm searches alternately in feasible and infeasible search spaces.The results of 183 examples in 5 groups show that the tabu search algorithm has advantages over the state-of-the-art algorithms.Specifically,the algorithm proposed in this chapter improves the 25 best known solutions out of 183 instances.Secondly,following the work of the previous chapter,we propose a memetic algorithm to solve the capacitated clustering problem,which uses cluster-based crossover to generate promising offspring solutions and improves the offspring solution with the tabu search algorithm proposed in the previous chapter.In addition,the memetic algorithm updates the population using a quality-distance based updating strategy.The experimental results in this chapter show that the memetic algorithm can further improve the performance of tabu search under the extended time limit.Thirdly,we propose a memetic algorithm based on reformulation local search to solve the minimum sum of squares clustering on network.The proposed algorithm integrates the backbone-based crossover operator which preserves common shared elements between parents for generation of offspring with the reformulation local search method for local optimization.The main idea behind the reformulation local search algorithm is to use the relationship between the continuous model and its corresponding discrete model.The results show that the algorithm is very competitive with the state-of-the-art algorithms in the literature-it reports new improved upper bounds for 10 out of 40 instances,and reaches the current best known solutions on all the remaining instances.Finally,we study the balanced minimum sum of squares clustering problem.We propose a hybrid evolutionary algorithm for balanced minimum sum of squares clustering problem.It uses the recombination operator to generate promising offspring solutions,and then uses the responsive threshold search(RTS)to improve it.RTS alternates between the threshold based exploration phase and the descent based improvement phase until the specified search depth is reached.In addition,it uses the classical population management strategy to update the population.The experimental results show that our hybrid evolutionary algorithm has obvious advantages over the state-of-the-art algorithms for solving the balanced minimum sum of squares clustering problem.More precisely,the proposed algorithm reports new improved upper bounds in 115 out of 152 test graphs and obtains the current best known solutions on all the(except two)remaining instances.