CLIO Core

Docs · Machine learning

knn: k-nearest-neighbour classification.

Classifies a resident set of query rows against a paged, labelled training set in one pass. Each block keeps a private top-k per query ordered by squared distance and then global row index; the host merges them and takes a majority vote, with ties going to the smallest label.

Module
ml_knn
Header
clio_ml/knn.h
Rows
features, then class label
Limit
fewer than 2^24 training rows

What it does

Unlike the other modules this one has no training step: the paged pass is the prediction. The queries are passed in as a flat array and stay resident on the device. Training rows must number fewer than 2^24.

Rows

n_features feature columns followed by the class label. Queries have n_features columns and no label. clio_ml.COLUMNS["knn"] 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)
y = (X[:, 0] + X[:, 1] > 0).astype(np.float32)
data = np.column_stack([X, y]).astype(np.float32)

r = cm.fit_knn(data, queries=X[:5], k=5)
print(r.labels)                                   # 5 predicted labels
print(np.asarray(r.neighbors).reshape(5, r.k))    # global row indices, nearest first
print(np.asarray(r.dist2).reshape(5, r.k))        # squared distances
  • fit_knn(X, queries=..., **options). queries is required (a 2-D array of feature rows) and raises ValueError when missing.
  • Options (KnnOptions): k (5), threads (256), row_base (0; the global index of this node's first row on a cluster).
  • Result KnnResult: k, labels (Q), neighbors (Q*k global row indices, nearest first), dist2 (Q*k squared distances), stats.
  • predict does not apply; the labels are in the result.

C++

cpp
struct KnnOptions {
  u32 k = 5;
  u32 threads = 256;
  u64 row_base = 0;
  ClusterExchange cluster;
};
struct KnnResult {
  u32 k = 0;
  std::vector<u32> labels;     // Q
  std::vector<u32> neighbors;  // Q*k
  std::vector<float> dist2;    // Q*k
  VecStats stats;
  std::vector<float> Flatten() const;
};
KnnResult KnnClassify(Dataset &ds, const std::vector<float> &queries, const KnnOptions &opt);
KnnResult KnnClassifyPlain(const float *data, u64 n_rows, u32 nf, u64 elems_per_page,
                           u32 nblocks, const std::vector<float> &queries,
                           const KnnOptions &opt);
KnnResult KnnClassifyReference(/* same arguments */);

The ChiMod is module ml_knn.

Related: naive Bayes, k-means.