Scholar.Cluster.MeanShift (Scholar v0.5.0)

Mean shift clustering.

Mean shift moves every seed towards the mean of the samples inside a ball of radius :bandwidth around it, repeating until the seed stops moving. Seeds that settle within one bandwidth of each other describe the same mode, so the weaker ones are discarded and the survivors become the cluster centers.

The number of clusters is discovered from the data rather than given, and the bandwidth is what controls it.

Distances are Euclidean. The update step averages the samples in a neighborhood, which only has meaning in a space where the arithmetic mean is the centroid.

The time complexity is $O(I * S * N)$ for $N$ samples, $S$ seeds and $I$ iterations. The space complexity is $O(S * N)$.

Summary

Functions

fit(x, opts \\ [])

Fits a mean shift model for sample inputs x.

prune(model)

Drops the centers that lost to a stronger one and renumbers the labels.

Functions

fit(x, opts \\ [])

Fits a mean shift model for sample inputs x.

Options

:bandwidth - Required. The radius of the region a seed averages over. Larger values merge more modes together and yield fewer clusters.
:max_iterations (pos_integer/0) - The maximum number of times a seed is moved past its first step. Seeds stop early once none of them moves further than bandwidth / 1000. The default value is 300.
:cluster_all (boolean/0) - If true, every sample is assigned to the nearest cluster center. If false, samples further than :bandwidth from every center are labeled -1. The default value is true.
:seeds (term/0) - The points to start from, given as a tensor of shape {num_seeds, num_features}. Defaults to the samples themselves. Fewer seeds make the fit cheaper at the risk of missing a mode.

Return Values

The function returns a struct with the following parameters:

:cluster_centers - The point every seed settled on, ordered by how many samples it gathered. Rows that lost to a stronger center are set to :infinity, so the tensor keeps the shape of the seeds. Use prune/1 to drop them.
:labels - The row of :cluster_centers each sample belongs to, or -1 when :cluster_all is false and the sample is further than :bandwidth from every center.
:num_clusters - The number of centers that survived.
:iterations - How many times the seeds were moved past their first step. This is zero when every seed settles on that first step.

Examples

iex> x = Nx.tensor([[1, 1], [1.2, 1.1], [8, 8], [8.1, 8.2]])
iex> Scholar.Cluster.MeanShift.fit(x, bandwidth: 1.0)
%Scholar.Cluster.MeanShift{
  cluster_centers: Nx.f32(
    [
      [8.050000190734863, 8.100000381469727],
      [:infinity, :infinity],
      [1.100000023841858, 1.0499999523162842],
      [:infinity, :infinity]
    ]
  ),
  labels: Nx.s32([2, 2, 0, 0]),
  num_clusters: Nx.u32(2),
  iterations: Nx.u32(1)
}

prune(model)

Drops the centers that lost to a stronger one and renumbers the labels.

fit/2 keeps one row per seed so the shapes stay static. This returns a model holding only the :num_clusters centers that survived, with :labels renumbered to index them.

Examples

iex> x = Nx.tensor([[1, 1], [1.2, 1.1], [8, 8], [8.1, 8.2]])
iex> model = Scholar.Cluster.MeanShift.fit(x, bandwidth: 1.0)
iex> Scholar.Cluster.MeanShift.prune(model)
%Scholar.Cluster.MeanShift{
  cluster_centers: Nx.f32(
    [
      [8.050000190734863, 8.100000381469727],
      [1.100000023841858, 1.0499999523162842]
    ]
  ),
  labels: Nx.s32([1, 1, 0, 0]),
  num_clusters: Nx.u32(2),
  iterations: Nx.u32(1)
}