A Density based Algorithm for Discovering Density Varied Clusters in Large Spatial Databases
Volume 3 – No.6, June 2010
A Density based Algorithm for Discovering Density
Varied Clusters in Large Spatial Databases
Anant Ram
G.L.A Institute of Sunita Jalal
G.B. Pant University of
Anand S. Jalal
G.L.A Institute of Manoj Kumar
G.L.A Institute of Technology &
Agriculture & Management, Mathura,
Technology, India
Pantnagar, India
ABSTRACT
DBSCAN is a base algorithm for density based clustering. It can detect the clusters of different shapes and sizes from the large amount of data which contains noise and outliers. However, it is fail to handle the local density variation that exists within the cluster. In this paper, we propose a density varied DBSCAN algorithm which is capable to handle local density variation within the cluster. It calculates the growing cluster density mean and then the cluster density variance for any core object, which is supposed to be expended further, by considering density of its -neighborhood with respect to cluster density mean. If cluster density variance for a core object is less than or equal to a threshold value and also satisfying the cluster similarity index, then it will allow the core object for expansion. The experimental results show that the proposed clustering algorithm gives optimized results.
General Terms
Density Based Clustering
Keywords
Core object, Cluster density mean, Cluster density variance, Cluster Similarity Index, Density differs
1. INTRODUCTION
Clustering is an important data analysis task that tries to separate a collection of objects into reasonable homogeneous groups called cluster [1]. Clustering in data mining is a discovery progression that groups a set of data in such a way that the inter-cluster similarity is minimized and intra-cluster similarity is maximized .There are five different techniques for clustering i.e. Partitioning, Hierarchical, Density based, Grid based and Model based. In addition to above five one more clustering technique, known as subspace clustering technique, which tries to remove the irrelevant dimensions in high dimensional database to generate the good quality cluster, because the irrelevant dimensions hide the real facts in the high dimensional database [2]. Density based algorithms are more important to find out the clusters of different shapes and sizes. However, most of the density based clustering algorithms, are not able to handle the local density variation exist within the cluster in high dimensional database. DBSCAN [3], a pioneer density based clustering algorithms, also fail to detect the density varied clusters due to the global parameter ‘minimum points’. There are a number of clustering algorithms exist as an improvement of DBSCAN for handling the density variation within the cluster.
In the proposed work, we present a new density varied algorithm which is successful to handle local density variation within the cluster. It calculates the growing cluster density mean
Technology &
Technology and Management, Mathura,
Management, Mathura,
India
India
and then the cluster density variance for any core object, which is supposed to be expended further, by considering density of its -neighborhood with respect to cluster density mean. If cluster density variance for a core object is less than or equal to a threshold value and also satisfying the cluster similarity index, then it will allow the core object for expansion.
Rest of the paper is organized as follows. Section 2 presents related work on density based clustering technique for high dimensional database. Section 3 discuses the existing DBSCAN clustering algorithm and required modification to get better clustering results. The proposed modification along with algorithm is discussed in section 4. Experimental results are presented in section 5. Finally, Section 6 presents conclusion and future work.
2. RELATED WORK
The DBSCAN (Density Based Spatial Clustering of Applications with Noise) [3] is a base algorithm of density based clustering. It requires user specified two global input parameters i.e. minimum objects (µ) and radius ().The density of an object is the number of objects in its -neighborhood of that object. DBSCAN does not specify upper limit of a core object i.e. how much objects may present in its -neighborhood. So due to this, the clusters detected by it, are having wide variation in local density. Such clusters may be represented by several smaller clusters so that each cluster may have reasonably uniform density. OPTICS [4] algorithm is an enhancement of DBSCAN to achieve this goal. In contrast to DBSCAN, OPTICS does not assign cluster memberships but computes an ordering in which the objects are processed and additionally generates the information, which would be used by an extended DBSCAN algorithm to assign cluster memberships. This information consists of two values for each object, the core-distance and the reachability-distance. The Valleys in reachability plot indicates clusters. The parameter ξ is crucial for identifying the valleys as ξ-clusters.
Another enhancement of the DBSCAN algorithm is DENCLUE [5], which is based on an influence function that describes the impact of an object upon its neighborhood. The algorithm allows a compact mathematical description of arbitrarily shaped clusters in high-dimensional data sets and is significantly faster as compared to the other density based clustering algorithms. It produces good clustering results even when a large amount of noise is present. EDBSCAN [6] algorithm is another improvement of DBSCAN; it keeps tracks of density variation which exists within the cluster. It calculates the density variance of a core object with respect to its -neighborhood. If density variance of a core object is less than or equal to a threshold value and also satisfying the homogeneity index with respect to
1
A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise KDD 1996 Martin Ester, Hans-Peter Kriegel, J? rg Sander, Xiaowei...
Published in Proceedings of 2nd International Conference on Knowledge Discovery and Data Mining (KDD-96) A Density-Based Algorithm for Discovering Clusters in...
[6] Ester M.,Kriegel H.-P.,Sander J.,Xu X.:A Density-Based Algorithm For Discovering Clusters in Large Spatial Databases with Noise[C]. Proc.2nd...
A Density-based Algorithm for Discovering Clusters in Large Databases[C]//Proc. of the 2nd 结束语 图4 本文算法的延展性 International Conference on ...
[4] ESTER M,KRIEGEL H P,SANDER J.A density— based algorithm for discovering clusters in large spatial databases with noise[C].Proc of the 2nd ...
datamining density-based clustering_IT/计算机_专业资料。Density-based clustering...“A densitybased algorithm for discovering clusters in large spatial databases ...
(2010)22—0203—03 文献标识码:A 2010 年 11 月 November 2010 中图分类...A Density Based Algorithm for Discovering Clusters in Large Spatial Databases ...
Martin Ester, Hans-Peter Kriegel, Jrg Sander.A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise[A]. Proceedings of ...
Xu. 1996. A density-based algorithm for discovering clusters in large spatial databases. KDD'96 聚类分析 QT clustering ? QT(Quality Threshold)聚类算法是...
(基于高密度连接区域 的密度聚类方法) Density-Based Spatial Clustering of Applications with Noise A Density-Based Algorithm for Discovering Clusters in Large ...
热门文档