A Fast Density and Grid Based Clustering Method for Data With Arbitrary Shapes and Noise

This paper presents a density- and grid- based (DGB) clustering method for categorizing data with arbitrary shapes and noise. As most of the conventional clustering approaches work only with round-shaped clusters, other methods are needed to be explored to proceed classification of clusters with arbitrary shapes. Clustering approach by fast search and find of density peaks and density-based spatial clustering of applications with noise, and so many other methods are reported to be capable of completing this task but are limited by their computation time of mutual distances between points or patterns. Without the calculation of mutual distances, this paper presents an alternative method to fulfill clustering of data with any shape and noise even faster and with more efficiency. It was successfully verified in clustering industrial data (e.g., DNA microarray data) and several benchmark datasets with different kinds of noise. It turned out that the proposed DGB clustering method is more efficient and faster in clustering datasets with any shape than the conventional methods.

I. Introduction

An essential routine to preproceed a given industrial data is to seek its clustering structure. Many applications in industrial area using various clustering methods can be found in [1] and [2]. Clustering approaches come along with different definitions of clusters. The expectation–maximization (EM) algorithm [3] categorizes patterns into the cluster with maximum likelihood. The assumption of EM clustering algorithm is that the cluster is a combination of patterns that have most likely the same distribution. The EM algorithm fulfills this task by optimizing the distribution functions of clusters. Applications using EM are reported in [4] and [5]. The widely used K-means method [6] finds the clusters by iteratively computing the distances from patterns to the gravity centers of clusters until converge. It assumes that the patterns, which belong to the same cluster, are located around cluster's gravity center. Various applications based on K-means method can be seen in [7] and [8]. Another alternative approach is called the hierarchical clustering [9] method, which keeps the property that patterns with small distance are more related than with large distance.