KNNAC: An Efficient K Nearest Neighbor Based Clustering With Active Core Detection

MCML Authors

Yao Zhang

→ Group Volker Tresp
 Database Systems, Data Mining and AI

Thomas Seidl

Prof. Dr.

Director

Database Systems, Data Mining and AI

Abstract

Density-based clustering algorithms are commonly adopted when arbitrarily shaped clusters exist. Usually, they do not need to know the number of clusters in prior, which is a big advantage. Conventional density-based approaches such as DBSCAN, utilize two parameters to define density. Recently, novel density-based clustering algorithms are proposed to reduce the problem complexity to the use of a single parameter k by utilizing the concepts of k Nearest Neighbor (kNN) and Reverse k Nearest Neighbor (RkNN) to define density. However, those kNN-based approaches are either ineffective or inefficient. In this paper, we present a new clustering algorithm KNNAC, which only requires computing the densities for a chosen subset of points due to the use of active core detection. We empirically show that, compared to other nearest neighbor based clustering approaches (e.g., RECORD, IS-DBSCAN, etc.), KNNAC can provide competitive performance while taking a fraction of the runtime.

inproceedings

---

iiWAS 2020

22nd International Conference on Information Integration and Web-based Applications and Services. Chiang Mai, Thailand, Nov 30-Dec 02, 2020.

---

Authors

Y. Zhang • Y. Lu • T. Seidl

---

Links

DOI

---

Research Area

 A3 | Computational Models