文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 经管营销 > 企业管理 > A Density based Algorithm for Discovering Density
侵权投诉

A Density based Algorithm for Discovering Density

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

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email