Clustering: incremental partitioning and density-based data stream models

This page shows how a system can automatically group similar data points together in real time, one by one, without needing any pre-assigned categories. It covers standard tracking, groups that shift positions over time, filtering out noise, and translating image patches into visual signatures.

1. Online k-means: k groups, one point at a time

Each new point joins the nearest centre, and that centre moves a little towards it.

from dense_armor.utility.cluster.kmeans import OnlineKMeans

km = OnlineKMeans(k=2, warmup=4)
for v in [0.0, 0.1, 10.0, 10.1, 0.2, 9.9]:
    km.learn_one({"x": [v]})
print(km.predict_one({"x": [0.05]}), km.predict_one({"x": [10.05]}))
print([round(float(c[0]), 3) for c in km.centers_])

0 1
[0.1, 10.0]

Two groups, around 0 and around 10; each centre is the mean of the points that joined it. The first warmup points (here 4, default 10 per centre) are kept aside; the centres are chosen among them one at a time, each the point farthest from those already chosen (the minimax rule of Roth et al. 2021, eq. 5); then learning goes on one point at a time. Starting from the first points instead could put two centres in the same group.

With the points above, the four points 0.0, 0.1, 10.0, 10.1 wait in the buffer. Farthest-first starts from the buffered point closest to their mean, 0.1, then picks the point farthest from it, 10.1. The other two buffered points join their nearest centre: 0.0 moves the first centre to 0.05, 10.0 moves the second to 10.05. Then 0.2 moves the first centre to 0.1 and 9.9 moves the second to 10.0, the means of the points in each group. The update rule moves the assigned centre by a fraction of the distance, one over the number of points that centre already has: $$c_j \leftarrow c_j + \frac{1}{n_j}\,(x - c_j)$$

where $c_j$ is the centre of group $j$, $x$ is the new point, and $n_j$ is how many points have already joined group $j$.

2. Three groups, recovered in one pass

The online method sees each point once and recovers the three groups of a synthetic stream.

import numpy as np
from collections import Counter
from dense_armor.utility.cluster.kmeans import OnlineKMeans

rng = np.random.default_rng(0)
centres = np.array([[0.0, 0.0], [10.0, 0.0], [0.0, 10.0]])
y = rng.integers(0, 3, 600)
X = centres[y] + rng.normal(0, 0.5, (600, 2))
km = OnlineKMeans(k=3)
for x in X:
    km.learn_one({"x": x.tolist()})
pred = np.array([km.predict_one({"x": x.tolist()}) for x in X])
mapping = {p: Counter(y[pred == p]).most_common(1)[0][0] for p in set(pred)}
mapped = np.array([mapping[p] for p in pred])
print(round(float((mapped == y).mean()), 4))

1.0

The adjusted Rand index measures how well two groupings agree: 1 is identical, 0 is chance, and negative is worse than chance. Six hundred points drawn around three well-separated centres, σ = 0.5, distance 10. The online version sees each point exactly once, in the order it comes; the batch version sees the whole matrix and runs ten restarts. Both reach 1.0, so the online method has not lost anything by streaming.

3. Following groups that move

With a half-life the step stays constant, $1 - 2^{-1/h}$, so old points fade and the centres follow a drifting stream.

import numpy as np
from dense_armor.utility.cluster.kmeans import OnlineKMeans

rng = np.random.default_rng(1)
km = OnlineKMeans(k=2, halflife=50)
for i in range(3000):
    shift = i / 3000 * 5.0
    c = [shift, 0.0] if i % 2 == 0 else [shift, 10.0]
    km.learn_one({"x": (np.array(c) + rng.normal(0, 0.3, 2)).tolist()})
print(sorted([round(float(c[0]), 2), round(float(c[1]), 2)] for c in km.centers_))

[[4.78, 9.99], [4.81, -0.01]]

Both groups slid from $x = 0$ to $x = 5$ over 3000 steps, and each point of the stream belongs to a group whose position keeps changing. With a halflife the step is a constant $1 - 2^{-1/h}$ instead of $1 / n_j$, so the influence of a point is halved after halflife samples and the centre follows the group rather than averaging over its whole history. The final centres end near $x = 5$, where the groups are now.

4. Groups of any shape, with outliers: DenStream

DenStream keeps small "micro-clusters" (a centre and a weight), lets their weight fade with time, and only groups that keep receiving points become real clusters; an isolated point stays an outlier.

import numpy as np
from dense_armor.utility.cluster.denstream import DenStream

rng = np.random.default_rng(0)
ds = DenStream(eps=1.0, beta=0.4, mu=3.0, decay=0.01)
centres = np.array([[0.0, 0.0], [8.0, 0.0], [0.0, 8.0]])
t = 0.0
for i in range(600):
    x = centres[i % 3] + rng.normal(0, 0.3, 2) if i % 20 else rng.uniform(-4, 12, 2)
    ds.learn_one({"x": x.tolist()}, t=t)
    t += 1.0
clusters, _ = ds.macro_clusters()
print(len(clusters), [[round(v, 1) for v in c["center"]] for c in clusters])

3 [[8.0, -0.0], [-0.0, 8.0], [-0.1, 0.0]]

Six hundred points around three centres, one in twenty uniform noise; DenStream finds the three groups. The clusters come back in the order they were discovered, not in the order of the input centres, so the first one in the list is the group around (8, 0). The weight of a micro-cluster fades with the damped window of the review of Zubaroğlu and Atalay (2020, section 2.3.1):

$$f(t) = 2^{-\lambda t}$$

$\lambda$ is the decay rate; a micro-cluster heavier than $\beta\mu$ is a real (potential) one, lighter ones are candidates (outliers) until more points arrive. An isolated point that lands far from every micro-cluster only creates a candidate, which will be pruned later if no other point comes near it. The offline step macro_clusters() merges reachable real micro-clusters on demand, and the centre of each resulting cluster is the weight-weighted mean of its micro- clusters.

5. A visual vocabulary

An image is cut into small patches; each patch is described by the directions of its edges; online k-means groups the patch descriptions into "visual words"; a frame becomes a histogram of the words it contains.

import numpy as np
from dense_armor.utility.vision.vocabulary import BagOfVisualWords

vert = np.zeros((32, 32), dtype=np.float32)
vert[:, ::4] = 1.0
horz = vert.T.copy()
bow = BagOfVisualWords(n_words=4, patch_size=8, n_bins=4)
for _ in range(10):
    bow.learn_one({"frame": vert})
    bow.learn_one({"frame": horz})
print(bow.transform_one({"frame": vert})["hist"], bow.transform_one({"frame": horz})["hist"])

[0.0, 0.75, 0.0, 0.25] [0.25, 0.0, 0.75, 0.0]

Vertical stripes and horizontal stripes use different words, so their histograms do not overlap: two textures, two signatures. The vocabulary is learned online with OnlineKMeans on the descriptors of the 8×8 patches, so the same estimator can be fed patches from any number of frames without ever storing them; a frame becomes a fixed-length histogram, a signature ready for a classifier.

API reference

kmeans

Sequential k-means over a data stream.

Each new point is assigned to its nearest centre and that centre moves towards the point. The step is 1 / n_j with n_j the number of points already assigned to centre j, so the centre is exactly the running mean of the points that fell into it. With a halflife the step becomes 1 - 2 ** (-1 / halflife), the exponential weight that halves the influence of a sample after halflife steps, so the centres follow a drifting stream instead of averaging over the whole past.

The online k-means setting of Bhattacharjee et al. (2021) compares the total loss

.. math::

\sum_{t=2}^{n} d(x_t, S_{t-1})^2,

where S_t is the set of centres announced after time t, to the best fixed set of k centres in hindsight,

.. math::

L_k(X_n) = \inf_{|S| = k} \sum_{x \in X_n} d(x, S)^2.

Their Theorem 1 (page 3) shows that a certain randomised algorithm keeps O(k poly(log n)) centres and achieves O(L_k(X_n) + Lambda(X_n)) loss, with Lambda(X_n) = \sum_t d(x_t, X_{t-1})^2 the lower-bound term of the paper. Theorem 2 (page 4) shows that no algorithm with fewer than n centres can beat Omega(Lambda(X_n)) on some stream. Only the lower bound applies here, because the upper bound needs the randomised centre selection and the poly-log number of centres; this scheme keeps exactly k centres. On an i.i.d. stream the centres converge to the batch k-means solution (the classical MacQueen step); on an adversarial stream a single far-away point can push a centre anywhere.

Initialisation: the first warmup points (default 10 * k) are buffered, k distinct centres are picked among them by greedy farthest-first selection (each new centre is the point farthest from the centres already chosen, the minimax rule of the PatchCore coreset, Roth et al. 2021, eq. 5), and the buffered points are then assigned in order. Starting from the first k points instead can put two centres in the same group and leave another group without one.

Examples:

>>> from dense_armor.utility.cluster.kmeans import OnlineKMeans
>>> km = OnlineKMeans(k=2, warmup=4)
>>> for v in [0.0, 0.1, 10.0, 10.1, 0.2, 9.9]:
...     _ = km.learn_one({"x": [v]})
>>> sorted(round(float(c[0]), 2) for c in km.centers_)
[0.1, 10.0]

References

Bhattacharjee, R., Dasgupta, S., Imola, J. J., Moshkovitz, M. (2021). Online k-means clustering on arbitrary data streams. arXiv:2102.09101. Roth, K. et al. (2021). Towards total recall in industrial anomaly detection. arXiv:2106.08265 (eq. 5, greedy minimax selection).

OnlineKMeans

OnlineKMeans(
    k: int,
    halflife: float | None = None,
    seed: int = 0,
    warmup: int | None = None,
)

Bases: Transformer

Sequential k-means, one sample at a time.

Each point is assigned to the nearest centre and that centre moves towards the point. When two centres end up on the same side of the data the assignment is still decided by the nearest distance, so empty clusters are not refilled; this is the MacQueen scheme.

Memory grows with k and the dimensionality d of a point: two arrays of size k and k * d, so the footprint is fixed after the first k points.

Parameters:

Name	Type	Description	Default
k	int	number of clusters.	required
halflife	float | None	exponential half-life in samples. None (default) uses the 1 / n_j step; a positive number uses 1 - 2 ** (-1 / halflife).	None
seed	int	reserved for future random initialisation; kept for the Root interface.	0
warmup	int | None	number of points buffered before the centres are chosen. Default 10 * k.	None

Raises:

Type	Description
ValueError	if k < 1, halflife is not positive, or warmup < k.

Source code in dense_armor/utility/cluster/kmeans.py

def __init__(
    self,
    k: int,
    halflife: float | None = None,
    seed: int = 0,
    warmup: int | None = None,
) -> None:
    if k < 1:
        raise ValueError(f"k must be >= 1, got {k}")
    if halflife is not None and halflife <= 0:
        raise ValueError(f"halflife must be > 0, got {halflife}")
    self.k = k
    self.halflife = halflife
    self.seed = seed
    self.warmup = warmup if warmup is not None else 10 * k
    if self.warmup < k:
        raise ValueError(f"warmup must be >= k, got {self.warmup}")
    self._buf: list[np.ndarray] = []
    self.centers_: np.ndarray | None = None
    self.counts_: np.ndarray | None = None
    self.n_seen_ = 0
    self.n_missing_ = 0

learn_one

learn_one(
    x: Any, y: Any = None, t: float | None = None
) -> OnlineKMeans

Assign x to the nearest centre and move that centre.

Source code in dense_armor/utility/cluster/kmeans.py

def learn_one(
    self, x: Any, y: Any = None, t: float | None = None
) -> "OnlineKMeans":
    """Assign ``x`` to the nearest centre and move that centre."""
    self._time_step(t)
    v = _vec(x)
    if v is None:
        self.n_missing_ += 1
        return self
    if not self._warm_up(v):
        self.n_seen_ += 1
        return self
    centers = self.centers_
    assert centers is not None
    if v.shape[0] != centers.shape[1]:
        self.n_missing_ += 1
        return self
    d2 = ((centers - v) ** 2).sum(axis=1)
    j = int(np.argmin(d2))
    a = self._alpha(j)
    centers[j] += a * (v - centers[j])
    assert self.counts_ is not None
    self.counts_[j] += 1
    self.n_seen_ += 1
    return self

predict_one

predict_one(x: Any, t: float | None = None) -> int

Return the index of the nearest centre (or 0 if not fitted).

Source code in dense_armor/utility/cluster/kmeans.py

def predict_one(self, x: Any, t: float | None = None) -> int:
    """Return the index of the nearest centre (or 0 if not fitted)."""
    v = _vec(x)
    if v is None or self.centers_ is None:
        return 0
    centers = self.centers_
    if v.shape[0] != centers.shape[1]:
        return 0
    d2 = ((centers - v) ** 2).sum(axis=1)
    return int(np.argmin(d2))

transform_one

transform_one(x: Any, t: float | None = None) -> dict

Return {"cluster": i, "distances": [...]}.

Source code in dense_armor/utility/cluster/kmeans.py

def transform_one(self, x: Any, t: float | None = None) -> dict:
    """Return ``{"cluster": i, "distances": [...]}``."""
    v = _vec(x)
    if v is None or self.centers_ is None:
        return {"cluster": 0, "distances": []}
    centers = self.centers_
    if v.shape[0] != centers.shape[1]:
        return {"cluster": 0, "distances": []}
    d = np.sqrt(((centers - v) ** 2).sum(axis=1))
    return {"cluster": int(np.argmin(d)), "distances": d.tolist()}

denstream

Density-based stream clustering with micro-clusters and a damped window.

A micro-cluster is a small set of close points, kept as a compact summary (centre, weight, timestamp of the last update). Two micro-clusters are directly density reachable when the distance between their centres is at most the sum of their radii; a chain of direct reachability is density reachable (Zubaroglu and Atalay 2020, page 9). Recent points weigh more than old ones through a damped window with the decay function f(t) = 2 ** (-lam * t) (Section 2.3.1, page 5). A micro-cluster whose cardinality is far below the average is an outlier (Section 2.4, page 6).

The stream is summarised with two kinds of micro-clusters:

• potential micro-clusters (pMCs), with weight at least beta * mu, which are the real clusters;
• outlier micro-clusters (oMCs), with weight below beta * mu, which are the candidates.

A new point is added to the nearest pMC within eps if any, else to the nearest oMC within eps, else it opens a new oMC. An oMC whose weight reaches beta * mu is promoted to pMC; a pMC whose weight drops below beta * mu is removed, and an oMC whose weight drops below beta * mu / 4 is removed. The last threshold is a choice of this implementation: the review (Section 2.4, page 6) defines an outlier as a cluster whose cardinality is much smaller than the average and does not give a numeric threshold, so a quarter of beta * mu was chosen as a small fraction. In the same section the review is also silent on how to reduce the weight over time for an oMC versus a pMC, so the same decay rate is used for both.

The offline step :meth:macro_clusters merges reachable pMCs on demand into macro-clusters, which is the final answer of the algorithm. Reachability uses eps as the distance between two centres; the review (page 9) states the sum-of-radii rule, but each pMC has radius at most eps (points are only added within eps), so the sum is at most 2 eps and eps is the conservative choice. The macro-cluster centre is the weight-weighted mean of its pMCs.

The weights and centres use the real timestamps passed to learn_one.

Examples:

>>> from dense_armor.utility.cluster.denstream import DenStream
>>> ds = DenStream(eps=0.5, beta=0.4, mu=1.0, decay=0.1)
>>> for i in range(30):
...     _ = ds.learn_one({"x": [0.0, 0.0]}, t=float(i))
>>> clusters, _ = ds.macro_clusters()
>>> len(clusters)
1

References

Zubaroglu, A., Atalay, V. (2020). Data stream clustering: a review. arXiv:2007.10781. Sections 2.3.1 (page 5), 2.4 (page 6); density reachability on page 9.

DenStream

DenStream(
    eps: float = 0.5,
    beta: float = 0.2,
    mu: float = 1.0,
    decay: float = 0.1,
)

Bases: Transformer

Density-based stream clustering with a damped window.

Potential and outlier micro-clusters fade with time; new points join the nearest reachable micro-cluster, and isolated points stay in the outlier list. The final answer comes from :meth:macro_clusters.

Memory grows with the number of micro-clusters kept: bounded by the effective window set by decay and mu, so the footprint is the size of the current micro-cluster lists.

Parameters:

Name	Type	Description	Default
eps	float	neighbourhood radius.	0.5
beta	float	multiplier that separates pMCs from oMCs.	0.2
mu	float	minimum weight of a pMC.	1.0
decay	float	decay rate lam of the damped window.	0.1

Raises:

Type	Description
ValueError	if any parameter is not positive, or beta is not in (0, 1].

Source code in dense_armor/utility/cluster/denstream.py

def __init__(
    self,
    eps: float = 0.5,
    beta: float = 0.2,
    mu: float = 1.0,
    decay: float = 0.1,
) -> None:
    if eps <= 0:
        raise ValueError(f"eps must be > 0, got {eps}")
    if not 0.0 < beta <= 1.0:
        raise ValueError(f"beta must be in (0, 1], got {beta}")
    if mu <= 0:
        raise ValueError(f"mu must be > 0, got {mu}")
    if decay <= 0:
        raise ValueError(f"decay must be > 0, got {decay}")
    self.eps = eps
    self.beta = beta
    self.mu = mu
    self.decay = decay
    self.pmc_: list[_MC] = []
    self.omc_: list[_MC] = []
    self.n_seen_ = 0
    self.n_missing_ = 0

learn_one

learn_one(
    x: Any, y: Any = None, t: float | None = None
) -> DenStream

Process one sample: fade, join, promote, prune.

Source code in dense_armor/utility/cluster/denstream.py

def learn_one(
    self, x: Any, y: Any = None, t: float | None = None
) -> "DenStream":
    """Process one sample: fade, join, promote, prune."""
    self._time_step(t)
    v = _vec(x)
    if v is None:
        self.n_missing_ += 1
        return self
    tt = float(t) if t is not None else float(self.n_seen_)
    self.n_seen_ += 1
    p, dp = self._nearest(self.pmc_, v)
    if p is not None and dp <= self.eps:
        self._merge(p, v, tt)
    else:
        o, do = self._nearest(self.omc_, v)
        if o is not None and do <= self.eps:
            self._merge(o, v, tt)
            if o.w >= self.beta * self.mu:
                self.omc_.remove(o)
                self.pmc_.append(o)
        else:
            self.omc_.append(_MC(v.copy(), 1.0, tt))
    self._prune(tt)
    return self

transform_one

transform_one(x: Any, t: float | None = None) -> dict

Return the nearest pMC index within eps, or -1.

Source code in dense_armor/utility/cluster/denstream.py

def transform_one(self, x: Any, t: float | None = None) -> dict:
    """Return the nearest pMC index within ``eps``, or ``-1``."""
    v = _vec(x)
    if v is None or not self.pmc_:
        return {"cluster": -1, "distance": float("inf")}
    best_i = -1
    best_d = float("inf")
    for i, mc in enumerate(self.pmc_):
        d = float(np.linalg.norm(mc.c - v))
        if d < best_d:
            best_d = d
            best_i = i
    if best_d > self.eps:
        return {"cluster": -1, "distance": best_d}
    return {"cluster": best_i, "distance": best_d}

macro_clusters

macro_clusters() -> tuple[list[dict], list[int]]

Merge reachable pMCs into macro-clusters on demand.

Two pMCs are directly density reachable when the distance between their centres is at most eps (see the module docstring for the choice). The macro-cluster centre is the weight-weighted mean of its pMCs.

Returns:

Type	Description
list[dict]	A tuple (clusters, labels): clusters is a list of
list[int]	dicts with keys "center", "weight" and
tuple[list[dict], list[int]]	"n_pmc", and labels assigns each pMC in
tuple[list[dict], list[int]]	attr:pmc_ to a macro-cluster index.

Source code in dense_armor/utility/cluster/denstream.py

def macro_clusters(self) -> tuple[list[dict], list[int]]:
    """Merge reachable pMCs into macro-clusters on demand.

    Two pMCs are directly density reachable when the distance
    between their centres is at most ``eps`` (see the module
    docstring for the choice). The macro-cluster centre is the
    weight-weighted mean of its pMCs.

    Returns:
        A tuple ``(clusters, labels)``: ``clusters`` is a list of
        dicts with keys ``"center"``, ``"weight"`` and
        ``"n_pmc"``, and ``labels`` assigns each pMC in
        :attr:`pmc_` to a macro-cluster index.
    """
    n = len(self.pmc_)
    labels = [-1] * n
    clusters: list[dict] = []
    for i in range(n):
        if labels[i] != -1:
            continue
        cid = len(clusters)
        stack = [i]
        labels[i] = cid
        members: list[int] = []
        while stack:
            j = stack.pop()
            members.append(j)
            cj = self.pmc_[j].c
            for k in range(n):
                if labels[k] != -1:
                    continue
                if float(np.linalg.norm(cj - self.pmc_[k].c)) <= self.eps:
                    labels[k] = cid
                    stack.append(k)
        ws = np.array([self.pmc_[m].w for m in members])
        cs = np.stack([self.pmc_[m].c for m in members])
        center = (ws[:, None] * cs).sum(axis=0) / ws.sum()
        clusters.append(
            {
                "center": center.tolist(),
                "weight": float(ws.sum()),
                "n_pmc": len(members),
            }
        )
    return clusters, labels

vocabulary

Bag of visual words: a k-means vocabulary over image patches.

The frame is split into square patches (default 8 by 8 pixels). Each patch is described with a small histogram of oriented gradients (Huang and Huang 2017), the same construction used by the frame features. An online k-means learns a vocabulary of n_words visual words over the patch descriptors, one word per cluster. A frame becomes a normalised histogram of visual words: every patch votes for its nearest word and the histogram is divided by the number of patches. The result is a fixed-length signature of the frame, the missing piece of the visual pipeline.

The vocabulary is grown online, so the same estimator can be fed patch descriptors from many frames without ever storing them.

Examples:

>>> import numpy as np
>>> from dense_armor.utility.vision.vocabulary import BagOfVisualWords
>>> bow = BagOfVisualWords(n_words=3, patch_size=8, n_bins=4)
>>> img = np.zeros((16, 16), dtype=np.float32)
>>> img[:, 8:] = 1.0
>>> out = bow.transform_one({"frame": img})
>>> len(out["hist"])
3

References

Huang, C., Huang, J. (2017). A fast HOG descriptor using lookup table and integral image. arXiv:1703.06256.

BagOfVisualWords

BagOfVisualWords(
    n_words: int = 8,
    patch_size: int = 8,
    n_bins: int = 8,
    seed: int = 0,
)

Bases: Transformer

Visual vocabulary over image patches and per-frame histogram.

learn_one extracts patches from a frame and feeds their descriptors to an internal :class:OnlineKMeans. transform_one returns a normalised histogram of word counts. A frame that is empty, has a wrong shape, or contains a non-finite value is skipped and counted in n_missing.

Memory grows with the vocabulary (n_words centres of 2 * n_bins floats each) and the number of patches per frame, both bounded, so the footprint is fixed.

Parameters:

Name	Type	Description	Default
n_words	int	size of the visual vocabulary.	8
patch_size	int	side of a square patch in pixels.	8
n_bins	int	number of gradient orientation bins inside a patch.	8
seed	int	passed to the internal :class:OnlineKMeans.	0

Raises:

Type	Description
ValueError	if any parameter is not positive.

Source code in dense_armor/utility/vision/vocabulary.py

def __init__(
    self,
    n_words: int = 8,
    patch_size: int = 8,
    n_bins: int = 8,
    seed: int = 0,
) -> None:
    if n_words < 1:
        raise ValueError(f"n_words must be >= 1, got {n_words}")
    if patch_size < 2:
        raise ValueError(f"patch_size must be >= 2, got {patch_size}")
    if n_bins < 1:
        raise ValueError(f"n_bins must be >= 1, got {n_bins}")
    self.n_words = n_words
    self.patch_size = patch_size
    self.n_bins = n_bins
    self.seed = seed
    self.kmeans_ = OnlineKMeans(k=n_words, seed=seed)
    self.n_missing_ = 0

learn_one

learn_one(
    x: Any, y: Any = None, t: float | None = None
) -> BagOfVisualWords

Update the vocabulary with the patches of one frame.

Source code in dense_armor/utility/vision/vocabulary.py

def learn_one(
    self, x: Any, y: Any = None, t: float | None = None
) -> "BagOfVisualWords":
    """Update the vocabulary with the patches of one frame."""
    self._time_step(t)
    img = _as_array(x)
    if img is None:
        self.n_missing_ += 1
        return self
    descs = self._descriptors(img)
    if descs.shape[0] == 0:
        self.n_missing_ += 1
        return self
    for d in descs:
        self.kmeans_.learn_one({"_d": d.tolist()})
    return self

transform_one

transform_one(x: Any, t: float | None = None) -> dict

Return {"hist": [...]}, the normalised word histogram.

Source code in dense_armor/utility/vision/vocabulary.py

def transform_one(self, x: Any, t: float | None = None) -> dict:
    """Return ``{"hist": [...]}``, the normalised word histogram."""
    img = _as_array(x)
    if img is None:
        self.n_missing_ += 1
        return {"hist": [0.0] * self.n_words}
    descs = self._descriptors(img)
    if descs.shape[0] == 0 or self.kmeans_.centers_ is None:
        return {"hist": [0.0] * self.n_words}
    hist = np.zeros(self.n_words)
    for d in descs:
        j = self.kmeans_.predict_one({"_d": d.tolist()})
        hist[j] += 1.0
    s = hist.sum()
    if s > 0:
        hist = hist / s
    return {"hist": hist.tolist()}

---

Details

• OnlineKMeans buffers the first warmup points (default 10 * k) and picks the centres by greedy farthest-first selection (Roth et al. 2021, eq. 5). Bhattacharjee et al. (2021) compare the online loss $\sum_t d(x_t, S_{t-1})^2$ with the best k fixed centres in hindsight; their lower bound (Theorem 2, p. 4) applies to any online method, their upper bound (Theorem 1, p. 3) needs a randomised algorithm with more than k centres and does not apply to this simple scheme.
• DenStream: an outlier micro-cluster is removed when its weight falls below $\beta\mu/4$ (the review gives no number); two micro-clusters are reachable when their centres are within eps (the review, p. 9, uses the sum of the radii; each radius is at most eps).
• Sources: Zubaroğlu, A., Atalay, V. (2020), "Data stream clustering: a review", Artificial Intelligence Review, arXiv:2007.10781. Bhattacharjee, R., Dasgupta, S., Imola, J. J., Moshkovitz, M. (2021), "Online k-means clustering on arbitrary data streams", arXiv:2102.09101. Huang, C., Huang, J. (2017), "A fast HOG descriptor using lookup table and integral image", arXiv:1703.06256. Roth, K. et al. (2021), "Towards total recall in industrial anomaly detection", arXiv:2106.08265. ````