# An Implementation of the HDBSCAN* Clustering Algorithm
## 2 Background and Literature Review
### Tribuo Machine Learning Library  
Tribuo [5] was developed by the Oracle Labs Machine Learning Research Group, a team within Oracle Corporation. They realized there is need for a single node machine learning framework on the JVM. Initially it was only available internally to Oracle but has been recently open sourced to help build the machine learning ecosystem on the Java platform. The version of Tribuo being reviewed, and at which it has been forked, is 4.2.0-SNAPSHOT. This version is currently compiled with Java 8.  
Some initial work has been done to evaluate the Tribuo library. When comparing machine learning tasks, such as classification, regression, and clustering, results from these experiments [13] show that Tribuo and scikit-learn achieve very similar performance measurements. This indicates that Tribuo is an interesting subject of further study.  
To implement a new algorithm in the Tribuo project, a detailed review of the source code is conducted. Overall, the code is very well organized, and has a very modular design. The first thing to mention is that Tribuo uses a maven build system. At the root of the project there are Classification, Regression, and Clustering maxen modules, among others. The Clustering module is the parent of the KMeans module. It seems logical that a new clustering algorithm should be added here, adjacent to the KMeans module.  
Looking more closely at the source code shows there are several frequently used classes which provide interesting functionality. There is a DenseVector class which is backed by an array of doubles. This class provides methods for many vector operations, such as addition, subtraction, and dot product. Most notably, the class provides methods which can be used to compute the distance between two vectors, including Euclidean and cosine distances. There is also a SparseVector class which implements the same interface as DenseVector but is optimized for, as the name suggests, sparse array data.  
In general, to perform a machine learning task with Tribuo, there is a standard workflow that should be followed. At a high-level, the first step is to instantiate the appropriate Trainer object. Calling a trainer's train method (and providing a dataset), returns a trained model to the user. For example, calling the train method on an instantiated KMeansTrainer object returns a KMeansModel object. A model may have attributes or methods specific to its task. Continuing with the example, a KMeansModel has a getCentroids method which returns the points which are the cluster centroids. Every model implements the Model interface, and one of the methods in this interface is predict. This indicates that every model should provide some functionality to make predictions on unseen data points.  
The Tribuo K-Means implementation leverages concurrency to perform portions of the algorithm in parallel. Specifically, Java parallel streams are used, and are assigned to a custom ForkJoinPool that controls the number of threads in the thread pool. This concurrency technique is considered for the new HDBSCAN* implementation.  
Tribuo provides a feature called Provenance which is ubiquitous throughout the library's code. This feature captures the details on how any model, dataset, and evaluation were created in Tribuo. The main benefit it offers is that any of these objects can be regenerated from scratch, which is valuable for reproducibility. Implementing a new feature in Tribuo requires some additional considerations to cooperate with the Provenance system.