A New K-means-Based Algorithm for Automatic Clustering and Outlier Discovery

K-means is one of the most popular partition-based clustering algorithms that partition data objects based on attributes/features into K number of groups or clusters. In this paper, we address the major issues affecting the performance of k-means clustering algorithm. We have proposed as well as implemented a new k-means-based clustering algorithm which forms clusters by detecting and removing both global and local outliers and automatically converging into optimal clusters which are formed by a two-part process of splitting the initial clusters into subclusters based on criterion at local level and, in the second part, merging the clusters that satisfy the nearness criterion. Experiments show that our algorithm is able to automatically generate optimal number of clusters of different sizes and shapes which are free from global and local outliers.