milia.cluster.models.copkmeans#

k-means with must-link and cannot-link constraints (Wagstaff et al., 2001).

Classes

ConstrainedKMeans([n_clusters, must, ...])

Lloyd's k-means whose assignment step respects pairwise constraints.

ConstrainedKMeansConfig(*[, name, kind, ...])

Validated hyperparameters of the constrained k-means clusterer.

class milia.cluster.models.copkmeans.ConstrainedKMeans(n_clusters=3, must=None, cannot=None, n_init=10, max_iter=100, random_state=0)#

Bases: BaseClusterer

Lloyd’s k-means whose assignment step respects pairwise constraints.

Must-link pairs are transitive: the points connected by must-link pairs form one block that is assigned to a single cluster, so one wrong link between two groups merges them. A block goes to the nearest centroid (by the summed squared distance of its points) among the clusters that hold no block it must not join.

Parameters:
  • n_clusters (int) – Number of clusters.

  • must (list[tuple[int, int]] | None) – Pairs of row indices that must share a cluster.

  • cannot (list[tuple[int, int]] | None) – Pairs of row indices that must not share a cluster.

  • n_init (int) – Restarts; the lowest-inertia run is kept.

  • max_iter (int) – Iterations per run.

  • random_state (int | None) – Seed for initialisation.

Raises:

ValueError – If the constraints leave a block with no admissible cluster (for example more mutually cannot-linked blocks than clusters).

Examples

>>> import numpy as np
>>> X = np.array([[0.0, 0.0], [0.1, 0.0], [5.0, 5.0], [5.1, 5.0], [2.5, 2.5]])
>>> free = ConstrainedKMeans(n_clusters=2).fit(X).labels_
>>> bool(free[4] == free[0]), bool(free[4] == free[2])
(True, False)
>>> tied = ConstrainedKMeans(n_clusters=2, must=[(4, 2)]).fit(X).labels_
>>> bool(tied[4] == tied[2])
True
class milia.cluster.models.copkmeans.ConstrainedKMeansConfig(*, name='copkmeans', kind='clusterer', space=SearchSpace(n_clusters=(2, 12)), n_clusters=3, must=None, cannot=None, n_init=10, max_iter=100, random_state=0)#

Bases: BaseModelConfig

Validated hyperparameters of the constrained k-means clusterer.

Build the clusterer with make("clusterer", "copkmeans", ...).

Examples

>>> ConstrainedKMeansConfig().name
'copkmeans'