MLA 011 Practical Clustering Tools

Primary clustering tools for practical applications include K-means using scikit-learn or Faiss, agglomerative clustering leveraging cosine similarity with scikit-learn, and density-based methods like DBSCAN or HDBSCAN. For determining the optimal number of clusters, silhouette score is generally preferred over inertia-based visual heuristics, and it natively supports pre-computed distance matrices. Links • Notes and resources at ocdevel.com/mlg/mla-11 Try a walking desk • stay healthy & sharp while you learn & code K-means Clustering • K-means is the most widely used clustering algorithm and is typically the first method to try for general clustering tasks. • The scikit-learn KMeans implementation • is suitable for small to medium-sized datasets, while Faiss's kmeans • is more efficient and accurate for very large datasets. • K-means requires the number of clusters to be specified in advance and relies on the Euclidean distance metric, which performs poorly in high-dimensional spaces. • When document embeddings have high dimensionality (e.g., 768 dimensions from sentence transformers), K-means becomes less effective due to the limitations of Euclidean distance in such spaces. Alternatives to K-means for High Dimensions • For text embeddings with high dimensionality, agglomerative (hierarchical) clustering methods are preferable, particularly because they allow the use of different similarity metrics. Agglomerative clustering • in scikit-learn accepts a pre-computed cosine similarity matrix, which is more appropriate for natural language processing. • Constructing the pre-computed distance (or similarity) matrix involves normalizing vectors and computing dot products, which can be efficiently achieved with linear algebra libraries like PyTorch. • Hierarchical algorithms do not use inertia in the same way as K-means and instead rely on external metrics, such as silhouette score. • Other clustering algorithms exist, including spectral, mean shift, and affinity propagation, which are not covered in this episode. Semantic Search and Vector Indexing • Libraries such as Faiss, Annoy, and HNSWlib provide approximate nearest neighbor search for efficient semantic search on large-scale vector data. • These systems create an index of your embeddings to enable rapid similarity search, often with the ability to specify cosine similarity as the metric. • Sample code using these libraries with sentence transformers can be found in the UKP Lab sentence-transformers examples directory • . Determining the Optimal Number of Clusters • Both K-means and agglomerative clustering require a predefined number of clusters, but this is often unknown beforehand. • The "elbow" method involves running the clustering algorithm with varying cluster counts and plotting the inertia (sum of squared distances within clusters) to visually identify the point of diminishing returns; see kmeans.inertia_ • . • The kneed package • can automatically detect the "elbow" or "knee" in the inertia plot, eliminating subjective human judgment; sample code available here • . • The silhouette score, calculated via silhouette_score • , considers both inter- and intra-cluster distances and allows for direct selection of the number of clusters with the maximum score. • The silhouette score can be computed using a pre-computed distance matrix (such as from cosine similarities), making it well-suited for applications involving non-Euclidean metrics and hierarchical clustering. Density-Based Clustering: DBSCAN and HDBSCAN DBSCAN • is a hierarchical clustering method that does not require specifying the number of clusters, instead discovering clusters based on data density. HDBSCAN • is a more popular and versatile implementation of density-based clustering, capable of handling various types of data without significant parameter tuning. • DBSCAN and HDBSCAN can be preferable to K-means or agglomerative clustering when automatic determination of cluster count or robustness to noise is important. • However, these algorithms may not perform well with all types of high-dimensional embedding data, as illustrated by the challenges faced when clustering 768-dimensional text embeddings. Summary Recommendations and Links • For low- to medium-sized, low-dimensional data, use K-means with silhouette score to choose the optimal number of clusters: scikit-learn KMeans • , silhouette_score • . • For very large data or vector search, use Faiss.kmeans • . • For high-dimensional data using cosine similarity, use Agglomerative Clustering • with a pre-computed square matrix of cosine similarities; sample code • . • For density-based clustering, consider DBSCAN • or HDBSCAN • . • Exploratory code and further examples can be found in the UKP Lab sentence-transformers examples • .