A Simple Yet Effective Data Clustering Algorithm

ProceedingsPublished 1 December 2006

Soujanya Vadapalli, Satyanarayana R. Valluri, Kamalakar Karlapalem

DOI10.1109/icdm.2006.9

Citations51

TL;DR

The experimental results with published datasets, synthetic and real-life datasets show that RECORD not only handles noisy data, but also identifies the relevant clusters.

Abstract

In this paper, we use a simple concept based on k-reverse nearest neighbor digraphs, to develop a framework RECORD for clustering and outlier detection. We developed three algorithms - (i) RECORD algorithm (requires one parameter), (ii) Agglomerative RECORD algorithm (no parameters required) and (iii) Stability-based RECORD algorithm (no parameters required). Our experimental results with published datasets, synthetic and real-life datasets show that RECORD not only handles noisy data, but also identifies the relevant clusters. Our results are as good as (if not better than) the results got from other algorithms.

Keywords

Computer Science

A density-based algorithm for discovering clusters in large spatial Databases with Noise

19,114 Citations1996Martin Ester, Hans‐Peter Kriegel +2 more

DBSCAN, a new clustering algorithm relying on a density-based notion of clusters which is designed to discover clusters of arbitrary shape, is presented which requires only one input parameter and supports the user in determining an appropriate value for it.

ACM SIGMOD RecordOPTICS

3,965 Citations1999Mihael Ankerst, Markus Breunig +2 more

View PDF

ComputerChameleon: hierarchical clustering using dynamic modeling

2,102 Citations1999George Karypis, Eui-Hong Han +1 more

Chameleon's key feature is that it accounts for both interconnectivity and closeness in identifying the most similar pair of clusters, which is important for dealing with highly variable clusters.

Outlier detection for high dimensional data

1,034 Citations2001Charų C. Aggarwal, Philip S. Yu

New techniques for outlier detection are discussed which find the outliers by studying the behavior of projections from the data set by studying the behavior of projections from the data set.

IEEE Transactions on ComputersClustering Using a Similarity Measure Based on Shared Near Neighbors

957 Citations1973R.A. Jarvis, Edward A. Patrick

A nonparametric clustering technique incorporating the concept of similarity based on the sharing of near neighbors is presented, which is an essentially paraliel approach and is applicable to a wide class of practical problems involving large sample size and high dimensionality.

Finding Clusters of Different Sizes, Shapes, and Densities in Noisy, High Dimensional Data

710 Citations2003Levent Ertöz, Michael Steinbach +1 more

A novel clustering technique that addresses problems with varying densities and high dimensionality, while the use of core points handles problems with shape and size, and a number of optimizations that allow the algorithm to handle large data sets are discussed.

ACM SIGMOD RecordInfluence sets based on reverse nearest neighbor queries

517 Citations2000Flip Korn, S. Muthukrishnan

View PDF

Information Processing LettersAn improved algorithm for hierarchical clustering using strong components

36 Citations1983Robert E. Tarjan

The present paper gives a simpler algorithm with the faster running time of O(m log n) time for hierarchically decomposing a directed n-vertex, m-edge graph with weighted edges into strong components.

Conference on Management of DataSynDECA: A Tool to Generate Synthetic Datasets for Evaluation of Clustering Algorithms.

12 Citations2005Jhansi Rani Vennam, Soujanya Vadapalli