Back to search

Virginia Commonwealth University

K-NEAREST NEIGHBORS DENSITY-BASED CLUSTERING

Abstract

dc:description.abstract

Traditional density-based clustering approaches rely on a distance-based parameter to define data connectivity and density. However, an appropriate value of this parameter can be difficult to determine as it is highly dependent on the underlying distribution of the data. In particular, distribution parameters affect the scale of inter-group distances (e.g., variance); this dependence leads to a well-known inability to simultaneously detect clusters at varying levels of density. In this work, connectivity and density are defined according to the rank-order induced by the distance metric (i.e., invariant to the expected scale of the distances). Connectivity by k-nearest neighbors and density by the number of reverse k-nearest neighbors (i.e., vertex in-degree in the directed k-nearest neighbors graph). Two novel density-based clustering algorithms are proposed, the non-hierarchical RNN-DBSCAN and its hierarchical generalization Hk-DC. The advantage of RNN- DBSCAN is that it requires a single parameter k and is robust to varying levels of cluster density, whereas Hk-DC provides an efficient solution for producing a hierarchical clustering of RNN-DBSCAN solutions over k for a fixed density threshold. Importantly, heuristics are proposed for selecting k and density threshold for RNN- DBSCAN and Hk-DC, along with a method for extracting a flat clustering solution from the hierarchy. Additionally, a cluster-dependent solution for handling noise is proposed.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Computer Science

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Bryant, Avory C.
  • <a href="http://orcid.org/0000-0001-9653-6704" target="_blank">0000-0001-9653-6704</a>
Contributors dc:contributor
  • Dr. Krzysztof J Cios

Subjects

dc:subject × 9

Rights

dc:rights
Statement dc:rights
  • © The Author

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Virginia Commonwealth University
Base URL
scholarscompass.vcu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Bryant, Avory C.; <a href="http://orcid.org/0000-0001-9653-6704" target="_blank">0000-0001-9653-6704</a>. K-NEAREST NEIGHBORS DENSITY-BASED CLUSTERING. Dissertation thesis, https://doi.org/10.25772/PJKZ-Q880