A Genetic Algorithm Approach for Semi-Supervised Clustering
Ayhan Demiriz, Kristin P. Bennett, Mark J. Embrechts · International Journal of Smart Engineering System Design · 2002
A novel semi-supervised clustering algorithm is proposed that synergizes the benefits of supervised and unsupervised learning methods. Data are clustered using an unsupervised learning technique biased toward producing clusters as pure as possible in terms of class distribution. These clusters can then be used to predict the class of future points. For example, in database marketing this technique can be used to identify and characterize segments of the customer population likely to respond to a specific promotion. One key additional benefit of this approach is that it allows unlabeled data with unknown class to be used to improve classification accuracy. The objective function of a traditional clustering technique, cluster dispersion in the K-means algorithm, is modified to minimize both the within-cluster variance of the input attributes and a measure of cluster impurity based on the class labels. Minimizing the within-cluster variance of the examples is a form of capacity control to prevent overfitting. For the output labels, impurity measures such as the Gini index can readily be applied to this problem. In this work, a genetic algorithm is proposed to optimize such an objective function to produce clusters. Non-empty clusters are labeled with the majority class. Experimental results show that using class information often improves the generalization ability compared to unsupervised methods based only on the input attributes. Benchmark studies also indicate that the method performs very well even when few training examples are available. Training using information from unlabeled data can improve classification accuracy on that data as well.