Geometric algorithms for density-based data clustering
Geometric algorithms for density-based data clustering
复制标题
DOI：
10.1142/s0218195905001683
复制
发表时间：
2005-06-01
影响因子：
--
通讯作者：
Xu, B
中科院分区：
文献类型：
--
作者：
Chen, DZ;Smid, M;Xu, B
Data clustering is a fundamental problem arising in many practical applications. In this paper, we present new geometric approximation and exact algorithms for the density-based data clustering problem in d-dimensional space R-d (for any constant integer d >= 2). Previously known algorithms for this problem are efficient only when the specified range around each input point, called the delta-neighborhood, contains on average a constant number of input points. Different distributions of the input data points have significant impact on the efficiency of these algorithms. In the worst case when the data points are highly clustered, these algorithms run in quadratic time, although such situations might not occur very frequently on real data. By using computational geometry techniques, we develop faster approximation and exact algorithms for the density-based data clustering problem in R-d. In particulax, our approximation algorithm based on the C-fuzzy distance function takes O(n log n) time for any given fixed value epsilon > 0, and our exact algorithms take sub-quadratic time. The running times and output quality of our algorithms do not depend on any particular data distribution. We believe that our fast approximation algorithm is of considerable practical importance, while our sub-quadratic exact algorithms are more of theoretical interest. We implemented our approximation algorithm and the experimental results show that our approximation algorithm is efficient on arbitrary input point sets.
