Multi-step density-based clustering
Multi-step density-based clustering
复制标题
基于密度的多步聚类
DOI：
10.1007/s10115-005-0217-6
复制
发表时间：
2006
影响因子：
2.7
通讯作者：
M. Pfeifle
中科院分区：
文献类型：
--
作者：
S. Brecheisen;H. Kriegel;M. Pfeifle
从科学、工程或多媒体应用的复杂对象的大型数据库中进行数据挖掘变得越来越重要。在许多地区，复杂的距离度量是首选，但也有更简单的距离函数，可以更有效地计算。在本文中，我们将演示如何将依赖于精确和下限近似距离函数的多步查询处理范例集成到两种基于密度的聚类算法DBSCAN和OPTICS中，从而大大提高效率。我们的方法试图将自己限制在对简单距离函数的范围查询上，并且仅在聚类算法的阶段执行复杂的距离计算，这些阶段必须计算正确的聚类结果。此外，我们将展示如何将我们的方法用于近似聚类，允许用户在质量和效率之间找到个人的权衡。为了评估聚类结果的质量，我们引入了合适的质量度量，这些度量通常用于评估近似划分和分层聚类的质量。在基于真实世界测试数据集的广泛实验评估中，我们证明了我们的方法将基于密度的精确聚类的生成速度提高了一个数量级以上。此外，我们表明，我们的近似聚类方法产生了高质量的聚类，其中所需的质量相对于（w.r.t.）精确距离计算的总数是可扩展的。
Data mining in large databases of complex objects from scientific, engineering or multimedia applications is getting more and more important. In many areas, complex distance measures are first choice but also simpler distance functions are available which can be computed much more efficiently. In this paper, we will demonstrate how the paradigm of multi-step query processing which relies on exact as well as on lower-bounding approximated distance functions can be integrated into the two density-based clustering algorithms DBSCAN and OPTICS resulting in a considerable efficiency boost. Our approach tries to confine itself to ɛ-range queries on the simple distance functions and carries out complex distance computations only at that stage of the clustering algorithm where they are compulsory to compute the correct clustering result. Furthermore, we will show how our approach can be used for approximated clustering allowing the user to find an individual trade-off between quality and efficiency. In order to assess the quality of the resulting clusterings, we introduce suitable quality measures which can be used generally for evaluating the quality of approximated partitioning and hierarchical clusterings. In a broad experimental evaluation based on real-world test data sets, we demonstrate that our approach accelerates the generation of exact density-based clusterings by more than one order of magnitude. Furthermore, we show that our approximated clustering approach results in high quality clusterings where the desired quality is scalable with respect to (w.r.t.) the overall number of exact distance computations.