CSHARP: A Clustering Using Shared Reference Points Algorithm

Abstract

Clustering algorithms partition data objects into a certain number of clusters, where a cluster is described in terms of internal homogeneity and external separation. A new clustering algorithm CSHARP is presented for the purpose of finding clusters of arbitrary shapes and arbitrary densities in high dimensional feature spaces. It can be considered as a variation of the Shared NearestNeighbor algorithm (SNN), in which each sample data point votes for the points in its k-nearest neighborhood. Sets of points sharing a common mutual nearest neighbor are considered as dense regions/blocks. These blocks are the seeds from which clusters may grow up. Therefore, CSHARP is not a point-to-point clustering algorithm. Rather, it is a block-to-block clustering technique. Much of its advantages come from these facts: Noise points and outliers correspond to blocks of small sizes, and homogeneous blocks highlyoverlap. This technique is not prone to merge clusters of different densities or different homogeneity. The algorithm has been applied to a variety of low and high-dimensional data sets with superior results over existing techniques such as DBScan, K-means, Chameleon,Mitosis and Spectral Clustering. The quality of its results as well as its time complexity, place it at the front of these techniques.