Struct coupe::KMeans

pub struct KMeans {
    pub imbalance_tol: f64,
    pub delta_threshold: f64,
    pub max_iter: usize,
    pub max_balance_iter: usize,
    pub erode: bool,
    pub hilbert: bool,
    pub mbr_early_break: bool,
}

K-means algorithm

An implementation of the balanced k-means algorithm inspired from “Balanced k-means for Parallel Geometric Partitioning” by Moritz von Looz, Charilaos Tzovas and Henning Meyerhenke (2018, University of Cologne).

From an initial partition, the K-means algorithm will generate points clusters that will, at each iteration, exchage points with other clusters that are “closer”, and move by recomputing the clusters position (defined as the centroid of the points assigned to the cluster). Eventually the clusters will stop moving, yielding a new partition.

Example

use coupe::Partition as _;
use coupe::Point2D;

let points = [
    Point2D::new(0., 0.),
    Point2D::new(1., 0.),
    Point2D::new(2., 0.),
    Point2D::new(0., 5.),
    Point2D::new(1., 5.),
    Point2D::new(2., 5.),
    Point2D::new(0., 10.),
    Point2D::new(1., 10.),
    Point2D::new(2., 10.),
];
let weights = [1.; 9];

// create an unbalanced partition:
//  - p1: total weight = 1
//  - p2: total weight = 1
//  - p3: total weight = 7
let mut partition = [0, 2, 2, 2, 2, 2, 2, 2, 1];

coupe::KMeans { delta_threshold: 0.0, ..Default::default() }
    .partition(&mut partition, (&points, &weights))?;

assert_eq!(partition[0], partition[1]);
assert_eq!(partition[0], partition[2]);

assert_eq!(partition[3], partition[4]);
assert_eq!(partition[3], partition[5]);

assert_eq!(partition[6], partition[7]);
assert_eq!(partition[6], partition[8]);

Fields

imbalance_tol: f64

delta_threshold: f64

max_iter: usize

max_balance_iter: usize

erode: bool

hilbert: bool

mbr_early_break: bool

Trait Implementations

impl Clone for KMeans

fn clone(&self) -> KMeans

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for KMeans

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for KMeans

fn default() -> Self

Returns the “default value” for a type.

impl<'a, const D: usize> Partition<(&'a [Matrix<f64, Const<D>, Const<1>, ArrayStorage<f64, D, 1>>], &'a [f64])> for KMeanswhere Const<D>: DimSub<Const<1>>, DefaultAllocator: Allocator<f64, Const<D>, Const<D>, Buffer = ArrayStorage<f64, D, D>> + Allocator<f64, DimDiff<Const<D>, Const<1>>>,

type Metadata = ()

Diagnostic data returned for a specific run of the algorithm.

type Error = Infallible

Error details, should the algorithm fail to run.

fn partition( &mut self, part_ids: &mut [usize], (points, weights): (&'a [PointND<D>], &'a [f64]) ) -> Result<Self::Metadata, Self::Error>

Partition the given data and output the part ID of each element in part_ids.

impl Copy for KMeans