A Novel Approach for Constraint selection Using Genetic Algorithm

Abstract: K-means algorithm has simple implementation and high speed. However, this algorithm is not capable of using the side information. Since this deficiency is effective on the performance of the algorithm, some improvements like Cop-k-means and CVQE algorithms have been designed. However, they encounter with another shortage which is equalizing the importance of constraints. To resolve this problem, the present paper proposes a mechanism to select the constraints of a data set through the use of CVQE clustering algorithm and the Imperialist Competitive Algorithm. The improvement measure in this method is the minimum constraint violation, reduction in the inter-cluster distances, and increase the distance between separate clusters. Thus, Davies Bouldin index is utilized to compare the results of the proposed algorithm with those of Cop-k-means, and CVQE algorithms. After clustering four data sets using these algorithms, the results proved that the proposed algorithm performs successfully in improving the constrained clustering.

Keywords: Clustering, constrained clustering, Constraint selection