larch

This crate provides a generic, trait-based framework for clustering and sampling algorithms. The main goal of this library is to implemenent a hierarchical clustering method to determine k for seeding a kmeans clustering algorithm.

It supports:

• Metric-based clustering via the [Metric] trait.
• Hierachical seeding of kmeans through tree cutting agglomerative clustering algorithm.
• Centroid-based clustering methods like k-means and hierarchical clustering through [ClusterCompare].

Overview

The crate is designed for composability and generic use. Implement the [Metric] trait for your own data type, then derive additional clustering behavior automatically through the provided default methods.

Example

use larch::prelude::*;

#[derive(Clone, Copy, Debug)]
struct Point(f64, f64);

impl Metric<Point> for Point {
    fn distance(&self, other: &Point) -> f64 {
        ((self.0 - other.0).powi(2) + (self.1 - other.1).powi(2)).sqrt()
    }
}

impl ClusterCompare<Point> for Point {
    fn compute_centroid(data: &Vec<Point>) -> Point {
        let (sx, sy): (f64, f64) = data.iter().fold((0.0, 0.0), |acc, p| (acc.0 + p.0, acc.1 + p.1));
        let n = data.len() as f64;
        Point(sx / n, sy / n)
    }
}

let points = vec![Point(0.0, 0.0), Point(1.0, 1.0), Point(10.0, 10.0)];
// normal k-means
let kmeans_clusters = Point::kmeans(&points, 2);
// determine k by hierarchical clustering + tree cutting then run kmeans
let seeded_clusters = Point::hierarchical_seeded_kmeans(&points);
println!("K-means clusters: {:?}", kmeans_clusters);
println!("Seeded K-means clusters: {:?}", seeded_clusters);

Note

This library is not highly optmized and due to the Rust implementation of [BinaryHeap] the hierarchical clustering is not deterministic.

License

larch is licensed under the BSD 3 license (see LICENSE in the main repository).