# An Implementation of the HDBSCAN* Clustering Algorithm
## 1 Introduction  
Cluster analysis is the task of arranging a set of similar data points into groups. It is an unsupervised machine learning task that can discover patterns or identify related groups from a dataset. There are many different algorithms proposed for cluster analysis [1; 2]. The K-Means algorithm is commonly used for clustering since it is fast and easy to understand. However, there are some potential problems with this algorithm. First, the number of clusters, or partitions, need to be provided as input to the algorithm. The number of clusters that may be present in a new dataset is, however, not always known. Another problem is that K-means is more of a partitioning algorithm than a clustering algorithm, since it partitions all the data into groups by minimizing distances between data points. These problems are also exist in other clustering algorithms. For example, the affinity propagation and spectral clustering algorithms also partition all the data into groups, so even outliers or noisy data points are included in the clusters. Another well-known algorithm is agglomerative clustering, which like K-Means, requires the number of clusters to be provided as input to the algorithm when a threshold parameter is not used.  
The HDBSCAN* clustering algorithm [3] is a density-based algorithm. Unlike K-Means, it does not require that every data point is assigned to a cluster, since it identifies dense clusters. Points not assigned to a cluster are considered as outliers, or noise. An algorithm that can effectively find distinct groups in a dataset and identify outliers is a valuable technique. There is an established Python implementation of the HDBSCAN* algorithm [4] which is included as a scikit-learn compatible project. It is well known that Python is a very popular language for data mining and machine learning tasks, such as clustering. Java, on the other hand, is not as popular for these types of tasks, even though there are numerous Java enterprise applications running in production currently. Machine learning libraries offer the benefit of providing a consistent API to variety of learning algorithms and utilities. Tribuo [5] is a recent open-sourced Java machine learninglibrary. Tribuo is proven to be robust and performant, but currently it only supports the K-Means clustering algorithm. Therefore, it is valuable to build an implementation of the HDBSCAN algorithm in the Tribuo library.  
This work offers a new and optimized implementation of the HDBSCAN algorithm in Java. A full tutorial about this implementation is available at [6]. The proposed implementation leverages Tribuo's infrastructure to provide a train/predict interface consistent with the library's other learning algorithms and features. This gives the ability to train models which discover clusters and identify outliers. This work introduces a novel prediction technique which uses a trained model to make predictions for unseen data points natively in Java. Functionality such as this provides the foundation for applications, such as a streaming clustering service. Furthermore, the methodology presented in this work illustrates a generic development process which can be reused for the implementation of an existing learning algorithm in an existing machine learning library.  
The remainder of this article is structured as follows. A background and literature review are presented in Section 2. Section 3 provides a description of the methodology of this work. Section 4 discusses the results of the comparisons between the HDBSCAN implementations. Finally, Section 5 presents a summary discussion of the work.