A Clustering Algorithm Using Dynamic Nearest Neighbors Selection Model
Zuo Wan · Chinese Journal of Computers · 2007
ROCK,proposed by Sudipno Guha et al in 1999,is a well known,robust,categorical attribute oriented clustering algorithm.The main contribution of ROCK is the introduction of a novel concept called common neighbors(links) as similarity measure between a pair of data points.Compared with traditional distance-based approaches,links capture global information over the whole data set rather than local information between two data points.Despite its success in clustering some categorical databases such as Mushroom,there are still some underlying weaknesses.First,the user is required to select a similarity threshold θ,a value that can significantly influence final clustering results.Without sufficient prior-knowledge,it is difficult to make a proper choice of value θ.Second,similarity function sim is only used to judge neighbors and the degree of similarity is lost during the iterative process of clustering,making the algorithm sensitive to the value of θ.Third,the number of desired final clusters must be pre-specified,which is also difficult without fully understanding of the data set.These shortcomings either hinder the algorithm from achieving even better clustering result,or make the algorithm inconvenient to use.This paper investigates the above problems and proposes a novel algorithm named DNNS using Dynamic Nearest Neighbors Selection model,which improves clustering quality with an appropriate selection of nearest neighbors.A new cohesion measure also is discussed to control the clustering process.Experimental results on standard databases VOTE and ZOO demonstrate that DNNS outperforms ROCK and VBACC based on the evaluation metrics of fα.