Implementation of Various Clustering Techniques

Abstract

Clustering is one of the important streams in data mining useful for discovering groups and identifying interesting distributions in the underlying data. This project aims in analyzing and comparing the partitional and density based clustering algorithms namely K-Means and DBSCAN. The comparison is done based on the extent to which each of these algorithms identify the clusters and their pros and cons. K-Means is a partitional clustering technique that helps to identify k clusters from a given set of n data points in d-dimensional space. It starts with k random centers and refines it at each step arriving to k clusters. DBSCAN discovers clusters of arbitrary shape relying on a density based notion of clusters. Given eps as the input parameter, unlike k-means clustering, it tries to find out all possible clusters by classifying each point as core, border or noise. DBSCAN can be expensive as computation of nearest neighbors requires computing all pair wise proximities. Our implementation would provide a comparative study of K-Means against DBSCAN algorithm.