# An Implementation of the HDBSCAN* Clustering Algorithm
## 3 Materials and Methods
### Main Development Phase
#### 3.4.3 Develop a Novel Prediction Technique  
As described in Section 2, the Tribuo library has a standard workflow that should be followed when using the API. Instantiating a Trainer object and calling the Trainer's train method with a dataset, returns a trained model to the user. A model can be used to make predictions on unseen data points, by calling the model's predict method. This implies that the new HdbscanModel class must also implement the predict method. However, the reference implementation does not provide any prediction functionality, and a technique for making predictions is not found in any of the reviewed literature. The Python implementation of the HDBSCAN* algorithm called hdbscan [4], which was described earlier, provides the functionality to predict the cluster assignments and outlier scores. A careful review of the code implementing this prediction functionality is performed. The hdbscan module's implementation relies on several computed structures not currently available in Tribuo Hdbscan, accompanied by logic specific to those data structures. Unfortunately, implementing prediction logic similar to what is done in the hdbscan Python module is not feasible at this time. To achieve the goal of providing prediction functionality as part of Tribuo Hdbscan, a novel prediction technique for HDBSCAN* clusters is being proposed. Conceptually, the technique is straight-forward. First, determine a good set of cluster exemplars which are representative of the HDBSCAN* clustering result. The use of exemplar points for clustering data is described by the authors of [15] which supports this approach. Then, for a new data point, it can be approximated with the cluster label and outlier score of its nearest exemplar point. The cluster exemplars are computed during training and are stored as an attribute of the HdbscanModel. This makes prediction calls very fast. However, how are a \"good\" set of cluster exemplars determined? What is the appropriate number of exemplars given a dataset and its computed clusters? An algorithm is developed which provides the answers to these questions. Algorithm 2 shows the high-level steps of the algorithm. ```
Generate the list of clusters. Each cluster list is a TreeMap sorted by outlier score;  Make the exemplar number calculation; forcluster in clusterListdo  Compute the number of exemplars for this cluster; ifthis is the Noise clusterthen  Poll the exemplars from the end of the TreeMap; else  Poll the exemplars from the front of the TreeMap;  end if  end for
```  
**Algorithm 2**Compute cluster exemplars. The input to the algorithm is the dataset, and a list of cluster assignments. First, the cluster assignments are used to create a map, where the key of this map is the cluster label, and the value is a collection of the points assigned to this cluster label. The collection of points is sorted by a point's outlier score. Next, the number of exemplars must be established. Let \(l\) be the size of the dataset and let \(c\) represent the number of identifiedclusters, for a given dataset and its corresponding HDBSCAN* result. The exemplar number formula is shown in Equation (3). \[\textit{exemplar number}=\lfloor\sqrt{\frac{l}{2}}+c\rfloor \tag{3}\]  
There are some important details to mention about this formula. The square root of half of \(l\) allows the number of exemplars to grow as the size of the dataset increases, but the growth slows as size of the dataset increases. Adding the value of \(c\) ensures there are always at least as many exemplars as there are cluster assignments. Lastly, the floor function is applied to return the greatest integer less than or equal to the computed value. The exemplar formula is not rigorously proven by induction or through formal methods. Instead, it is empirically shown to produce values for the exemplar number which result in accurate predictions, without growing too large, which would reduce prediction speed.