CLIO Core

Docs · Machine learning

bkm: bisecting k-means.

Divisive hierarchical clustering, the equivalent of Spark MLlib's BisectingKMeans. The tree grows one level at a time: every leaf with at least min_cluster_size points is split by 2-means started from the parent centre plus and minus a deterministic perturbation.

Module
ml_bkm
Header
clio_ml/bisecting_kmeans.h
Rows
features, then one ignored column
Limits
max_depth at most 6

What it does

Each 2-means iteration is one paged pass for all splitting leaves together: rows are routed down the existing tree inside the kernel. The result has up to 2^max_depth leaves and is bit-reproducible across paging, block counts and cluster nodes.

Rows

n_features feature columns followed by one ignored column. clio_ml.COLUMNS["bkm"] is 1.

Python

python
import numpy as np, clio_ml as cm
rng = np.random.default_rng(1)
X = rng.normal(size=(4096, 7)).astype(np.float32)
data = np.column_stack([X, np.zeros(4096)]).astype(np.float32)

r = cm.fit_bkm(data, max_depth=2, inner_iters=10)
m = r.model
leaves = [i for i, s in enumerate(m.status) if s == 2]
print(len(leaves), "leaves;", np.asarray(m.centers).reshape(m.maxN, m.nf)[leaves])
print(cm.predict("bkm", r, data[0, :7]))     # leaf node id (heap index)
  • fit_bkm(X, **options).
  • Options (BisectingKMeansOptions): max_depth (2), inner_iters (10), min_cluster_size (2), perturb (0.1), seed (1), threads (256).
  • Result BisectingKMeansResult: model and stats. model (BisectingKMeansModel): nf, maxN (heap slots), centers (maxN*nf in heap order), status (0 absent, 2 leaf, 3 split), counts (points per node).
  • predict("bkm", r, x) returns the leaf node's heap index, not a dense cluster number.

C++

cpp
struct BisectingKMeansOptions {
  u32 max_depth = 2;          // leaves <= 2^max_depth; <= 6
  u32 inner_iters = 10;
  u32 min_cluster_size = 2;
  float perturb = 0.1f;
  u32 seed = 1;
  u32 threads = 256;
  ClusterExchange cluster;
};
struct BisectingKMeansModel {
  u32 nf = 0, maxN = 0;
  std::vector<float> centers;  // maxN*nf, heap order
  std::vector<int> status;     // 0 absent, 2 leaf, 3 split
  std::vector<float> counts;
  std::vector<float> Flatten() const;
  u32 NumLeaves() const;
};
struct BisectingKMeansResult { BisectingKMeansModel model; VecStats stats; };
BisectingKMeansResult FitBisectingKMeans(Dataset &ds, const BisectingKMeansOptions &opt);
BisectingKMeansResult FitBisectingKMeansPlain(const float *data, u64 n_rows, u32 nf,
                                              u64 elems_per_page, u32 nblocks,
                                              const BisectingKMeansOptions &opt);
BisectingKMeansResult FitBisectingKMeansReference(/* same arguments */);
u32 BisectingKMeansPredict(const BisectingKMeansModel &m, const float *x);  // leaf node id

The ChiMod is module ml_bkm.

Related: k-means, Gaussian mixture, mean shift.