Undersampled K-means approach for handling imbalanced distributed data

摘要

K-means is a partitional clustering technique that is well known and widely used for its low computational cost. However, the performance of K-means algorithm tends to be affected by skewed data distributions, i.e., imbalanced data. They often produce clusters of relatively uniform sizes, even if input data have varied cluster size, which is called the “uniform effect”. In this paper, we analyze the causes of this effect and illustrate that it probably occurs more in the K-means clustering process. As the minority class decreases in size, the “uniform effect” becomes evident. To prevent the effect of the “uniform effect”, we revisit the well-known Kmeans algorithm and provide a general method to properly cluster imbalance distributed data. The proposed algorithm consists of a novel undersampling technique implemented by intelligently removing noisy and weak instances from majority class.We conduct experiments using twelve UCI datasets from various application domains using five algorithms for comparison on eight evaluationmetrics. Experimental results show the effectiveness of the proposed clustering algorithm in clustering balanced and imbalanced data.