# An Implementation of the HDBSCAN* Clustering Algorithm
## 2 Background and Literature Review
### Hdbscan
#### 2.2.2 The HDBSCAN* Algorithm  
This section describes the HDBSCAN* algorithm presented in [8]. There are two required input parameters to this algorithm in addition to the dataset targeted for clustering. The first parameter is the minimum number of points \(s\) to be used in the distance calculation, as it will be shown later in this paper. The second required parameter is the minimum cluster size \(p\) that defines a lower bound on the number of data points required to form a cluster. The dataset is a set of homogeneous points where a point is a record of numerical features. Figure 1 shows a simple dataset of 39 two-dimensional points that will be used as an example throughout this section. The first step in the algorithm is to compute the core distances for each point in the dataset. The core distance of a point is the distance to the \(k\)th nearest neighbor. The value of \(k\) includes the point itself. This is a technique to obtain an approximate density for each point. Figure 2 shows the core distances for the points \((2.7,2.7)\) and \((3.0,3.0)\) for \(k=5\), from the simple dataset. Note that both points' 5 th nearest neighbor is common. The point \((3.0,3.0)\) has a smaller core distance value than the point \((2.7,2.7)\) because its neighboring points are closer, which implies it has a higher approximate density. \begin{table}
\begin{tabular}{l l l} \hline \hline
**Algorithm** & **Strengths** & **Weaknesses** \\ \hline DBSCAN & Faster than the HDBSCAN* algorithm. & The algorithm requires an obscure, data dependent, distance parameter. \\  & Discovers the clusters in a dataset. & Not effective at identifying clusters of varying density. \\  & Identifies outlier points. & The algorithm has higher complexity compared to DBSCAN. \\ \hline HDBSCAN* & Identifies clusters of varying density & The algorithm has higher complexity compared to DBSCAN. \\  & Discovers the clusters in a dataset. & Identifies outlier points. \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Summary of the strengths and weaknesses of DBSCAN and HDBSCAN*. Using the core distances, a new distance metric is computed which is called the mutual reachability distance. The mutual reachability distance between two points \(x\) and \(y\), is the maximum value of: the core distance of \(x\), the core distance of \(y\), or the distance between \(x\) and \(y\). The points \((2.7,2.7)\) and \((3.0,3.0)\) shown in Figure 2 have a mutual reachability distance equal to the distance between the two points. Concretely, for \(k=5\), the core distance of \((2.7,2.7)\) is \(0.22\), the core distance of \((3.0,3.0)\) is \(0.31\) and the distance between the two points is \(0.42\). Therefore, the mutual reachability distance between these points is \(0.42\). Next, the mutual reachability distances between the points can be used to establish a weighted graph, where the data points are vertices and an edge between any two points has the weight of the mutual reachability distance of those points. This complete graph is only a conceptual artifact in the algorithm, since it is the graph's minimum spanning tree which needs to be computed. A minimum spanning tree is a spanning tree whose sum of edge weights is as small as possible. That is, it has all vertices connected with a subset of the edges from the complete graph, without any cycles and with the minimum possible total edge weight. The resulting minimum spanning tree is modified by adding a self-edge to each vertex with the point's core distance as the weight. This gives a graph called the extended minimum spanning tree. Figure 3 shows the minimum spanning tree of the simple dataset. Now, the graph can be used to build the HDBSCAN* hierarchy. To begin with, there is one cluster label, and all the points are assigned to this cluster. This cluster is added to a cluster list. The graph is then sorted by edge weight in ascending order. Starting from the bottom of the graph, edges are iteratively removed from the extended minimum spanning tree. Edges with equal weights must be removed simultaneously.