A Novel k-Means Algorithm for Clustering and Outlier Detection

A three-stage k-means algorithm of O(nkt) polynomial time is proposed to cluster the numerical data and detect the outliers. The clusters are preliminarily determined at the first stage. The local outliers of each cluster are found out and their influences on the centroid are removed at the second stage. Global outliers are consequently identified. Finally, the clusters, the densities of which are similar and some parts of which overlap, are merged. Simulation results show that the algorithm supports the discovery of clusters of different densities, different sizes and non-spherical shapes.