An improved genetic algorithm with Lagrange and density method for clustering

摘要

To overcome the shortcomings of K-means clustering including clustering numbers, sensitivity to clustering center (seeds) and local optimization, this article proposes an improved genetic algorithm (GA) with a novel Lagrange-based fitness function and an initial population technique(called NicheClust algorithm); the NicheClust can determine the best chromosomes and then feeds these into K-means as initial seeds to achieve higher-quality clustering results by allowing the initial seeds to readjust in terms of clustering demands. The GA approach is proposed to search for a global optimally solution. The initial population method is presented to automatically capture the appropriate number of clusters and find the initial seeds. The Lagrange-based approach is used to prevent the fitness function from prematurely converging and capture global optimization for K-means clustering results. Experimental results based on six taxi Global Positioning System (GPS) datasets verify the higher performance of NicheClust compared to other clustering methods and validate the effectiveness with statistical analysis method.