Density-based clustering: algorithms and evaluation techniques

Abstract

Density-based clustering algorithms involve a relevant subset of all the methods developed for cluster analysis, which is one of the fundamental pillars of unsupervised learning [2]. While the origins of clustering can be traced to the early 20th century [3], it is not until the 1990s that the concerns that would lead to develop density-based clustering algorithms are raised [4]. In 1996, the most popular density-based clustering algorithm to date (DBSCAN) is published [5] and, with it, many applications for density-based clustering are found within increasingly different fields over the next decades. In this introductory chapter, we present an overview of the research that led to this dissertation, focused mainly on density-based clustering. The work presented in this document can be divided into two main blocks, which, briefly stated, are: (1) research on the development of novel density-based algorithms and (2) research on evaluation techniques and metrics for density -based clustering. The motivation that led to this approach is expressed in Section 1.1. First, the original motivation to pursue the study of densitybased clustering algorithms (landmark discovery) is introduced in Section 1.1.1. After that, in Section 1.1.2, we explain the demand for an evaluation benchmark applicable to density-based clustering algorithms. In Section 1.2, the main objectives of this thesis, which emerge from the demands and opportunities introduced in the motivation section, are presented and justified. Subsequently, we introduce the main scientific contributions of this thesis (Section 1.3). A notation guide is then included to serve as a reference for the reader (Section 1.4). Lastly, the description regarding the structure of this document is included in Section 1.5.