# An Implementation of the HDBSCAN* Clustering Algorithm
## 2 Background and Literature Review
### Hdbscan
#### 2.2.2 The HDBSCAN* Algorithm
The weight value of the edge(s) being removed is used to denote the current hierarchical level. As an edge is  
Figure 1: A simple dataset of two-dimensional points. removed, the cluster containing the removed edge is explored. Clusters that have become disconnected and contain fewer points than s (minimum cluster size) are all assigned with the noise label. A cluster that has become disconnected, but has more than s points, is assigned a new cluster label. This is called a cluster split. Additionally, the new cluster is added to the list of clusters. A new hierarchy level is created when an edge removal has resulted in new clusters due to cluster splits. By the end of the process, in the last level of the hierarchy, all the points in the dataset will have been assigned to noise. The hierarchy produced by this process is the HDBSCAN* hierarchy. Figure 4 shows a table representation of the HDBSCAN* hierarchy of the simple dataset. Each column of the table represents a data point, and the rows contain the cluster assignments as the algorithm runs. In the top row, all the points are assigned to the same, single cluster. In the second row, some points are set to zero because they have been split off and are marked as outliers. In the third row, there are now two distinct clusters and one additional outlier. By the last row, all the points are assigned as outliers or noise points. During the construction of the HDBSCAN* hierarchy, a list of the clusters is also maintained, where each cluster holds a reference to its parent. Figure 2: The core distances for the points (2.7,2.7) and (3.0,3.0) for \(k=5\), using a zoomed in view on a particular area of the simple dataset. With the HDBSCAN* hierarchy and the list of clusters computed, the next step is to identify the prominent clusters from this hierarchy. To proceed, a new measure needs to be established that can be used towards determining the stability of a cluster. This is called lambda, such that \(\lambda=1/\)edge weight. Further, for a cluster we also define values \(\lambda_{birth}\) and \(\lambda_{death}\) to be the lambda value when a new cluster was created from a cluster split, and the lambda value when that same cluster was itself split, respectively. For each point in a cluster, we can define the value \(\lambda_{p}\) as the lambda value at which that point dropped out of the cluster. The stability for a cluster can be computed, as shown in Equation (1). \[stability=\sum_{p\in Cluster}\left(\lambda_{p}-\lambda_{birth}\right) \tag{1}\]  
The stability needs to be propagated through the clusters. Leaf clusters are clusters with no children, and they can be identified from the list of clusters. Starting with these leaf clusters, traverse up using the reference to the cluster's parent. Leaf clusters always propagate their stability to their parents and add themselves as a propagated descendent in the parent cluster. For non-leaf clusters one of two things will occur. If the cluster being processed has a higher stability than the cumulative stability of its descendants, it alone will be propagated to the parent cluster. Otherwise, the cumulative stability of all the current cluster's descendants will be propagated to the parent cluster. Clearly, no propagation occurs for the root cluster since it has no parent. When this process is  
Figure 4: A tabular representation of the HDBSCAN* hierarchy of the simple dataset. Figure 3: The minimum spanning tree of the simple dataset. An extended minimum spanning tree would contain self-edges for each point, with the weight of the self-edge being the point’s core distance value. finished, the root cluster will contain the references to descendent clusters with the highest stabilities. The clusters with the highest stabilities are the most prominent clusters. Using the HDBSCAN* hierarchy together with the details of the most prominent clusters, the list of cluster assignments for each data point can be quickly generated. This is the most significant artifact generated as output of the HDBSCAN* algorithm described in [8].