Clustering API

kfc_procedure.core.clustering.bregman.BregmanKMeans

Bases: TransformerMixin, ClusterMixin, BaseEstimator

K-Means clustering with Bregman divergences.

Uses Lloyd's algorithm with pluggable Bregman divergences: 1. Assign points to closest centroid (using Bregman distance) 2. Update centroids using Euclidean mean surrogate 3. Repeat until convergence

Parameters:

Name	Type	Description	Default
n_clusters	int	Number of clusters	8
divergence	BaseBregmanDivergence	Divergence metric to use for distance computation	required
n_init	int	Number of random initializations	10
max_iter	int	Maximum iterations per initialization	300
tol	float	Convergence tolerance on relative distortion change	1e-4
random_state	int or RandomState	Random seed for reproducibility	None
verbose	bool	Enable iteration logging	False

Attributes:

Name	Type	Description
labels_	ndarray of shape (n_samples,)	Cluster assignment for each sample
cluster_centers_	ndarray of shape (n_clusters, n_features)	Final cluster centroids
inertia_	float	Sum of squared distances to nearest cluster center
n_iter_	int	Number of iterations run for best initialization

kfc_procedure.core.clustering.bregman.validate_divergence_domain

Ensure input data is valid for the chosen divergence.

Parameters:

Name	Type	Description	Default
div	BaseBregmanDivergence	Divergence instance with domain constraints	required
X	ndarray	Input data to validate	required

Raises:

Type	Description
ValueError	If X contains NaN/Inf or violates divergence domain constraints.
Checks:
- finite values only (no NaN or Inf)
- domain constraints of divergence (e.g., positivity for log-based divergences)

Divergences

kfc_procedure.core.clustering.divergences.base.BaseBregmanDivergence

Bases: ABC

Abstract base class for Bregman divergences.

A Bregman divergence is a generalized distance measure induced by a strictly convex and differentiable generator function phi.

For points x and y,

D_phi(x, y) = phi(x) - phi(y) - <grad_phi(y), x - y>

Unlike metric distances, Bregman divergences are generally not symmetric and do not necessarily satisfy the triangle inequality. They provide a unifying framework for many important divergence measures, including squared Euclidean distance, Kullback-Leibler divergence, Itakura-Saito divergence, and Mahalanobis-type divergences.

This interface defines the common contract for implementing Bregman divergence families used in clustering, prototype learning, and centroid-based optimization algorithms. Concrete subclasses must provide the generator function, its gradient, and domain validation logic.

Parameters:

Name	Type	Description	Default
validate_domain	bool	Whether to validate that input data belong to the valid domain of the divergence before computing distances.	True
**kwargs	dict	Additional divergence-specific parameters stored as instance attributes.	{}

Attributes:

Name	Type	Description
validate_domain	bool	Whether domain validation is enabled.
name	str	Human-readable identifier of the divergence.
family	str	Name of the divergence family.

Notes

Subclasses must implement:

• in_domain(X)
• phi(X)
• grad_phi(X)

The :meth:distance method caches quantities associated with the reference points Y to accelerate repeated divergence evaluations during iterative clustering procedures such as KFCProcedure and related Bregman clustering algorithms.

References

Bregman, L. M. (1967). "The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming."

Banerjee, A., Merugu, S., Dhillon, I. S., and Ghosh, J. (2005). "Clustering with Bregman Divergences." Journal of Machine Learning Research, 6, 1705-1749.

__init__

Initialize the divergence.

Parameters:

Name	Type	Description	Default
validate_domain	bool	Whether to enforce domain validation before divergence computations.	True
**kwargs	dict	Additional divergence-specific configuration parameters. Each key-value pair is stored as an instance attribute.	{}

in_domain abstractmethod

Check whether samples belong to the valid divergence domain.

Parameters:

Name	Type	Description	Default
X	ndarray of shape (n_samples, n_features)	Input samples.	required

Returns:

Type	Description
bool	True if all samples satisfy the domain constraints, otherwise False.

phi abstractmethod

Evaluate the convex generator function.

Parameters:

Name	Type	Description	Default
X	ndarray of shape (n_samples, n_features)	Input samples.	required

Returns:

Type	Description
ndarray of shape (n_samples,)	Generator function values evaluated at each sample.

grad_phi abstractmethod

Evaluate the gradient of the generator function.

Parameters:

Name	Type	Description	Default
X	ndarray of shape (n_samples, n_features)	Input samples.	required

Returns:

Type	Description
ndarray of shape (n_samples, n_features)	Gradient of the generator function evaluated at each sample.

distance

Compute pairwise Bregman divergences.

Given a set of samples X and reference points Y, this method computes the divergence matrix

.. math::

D_{ij}
=
D_{\phi}(X_i, Y_j)

for all sample-centroid pairs.

Parameters:

Name	Type	Description	Default
X	ndarray of shape (n_samples, n_features)	Input samples.	required
Y	ndarray of shape (n_centroids, n_features)	Reference points or centroids.	required
clip	bool	Whether to clip small negative numerical artifacts to zero.	True

Returns:

Type	Description
ndarray of shape (n_samples, n_centroids)	Pairwise divergence matrix where entry (i, j) corresponds to D_phi(X[i], Y[j]).

Raises:

Type	Description
ValueError	If either X or Y contains values outside the divergence domain.

Notes

Quantities dependent only on Y are cached internally to improve performance when repeatedly evaluating distances against the same reference points.

pairwise

Compute pairwise divergences.

This method is an alias for :meth:distance.

Parameters:

Name	Type	Description	Default
X	ndarray of shape (n_samples, n_features)	Input samples.	required
Y	ndarray of shape (n_centroids, n_features)	Reference points.	required

Returns:

Type	Description
ndarray of shape (n_samples, n_centroids)	Pairwise divergence matrix.

centroid

Compute the arithmetic centroid of a sample set.

Parameters:

Name	Type	Description	Default
X	ndarray of shape (n_samples, n_features)	Input samples.	required

Returns:

Type	Description
ndarray of shape (n_features,)	Arithmetic mean of the input samples.

assign_clusters

Assign samples to the nearest centroid.

Each sample is assigned to the centroid that minimizes the corresponding Bregman divergence.

Parameters:

Name	Type	Description	Default
X	ndarray of shape (n_samples, n_features)	Input samples.	required
centroids	ndarray of shape (n_clusters, n_features)	Cluster centroids.	required

Returns:

Type	Description
ndarray of shape (n_samples,)	Index of the nearest centroid for each sample.

__repr__

Return a string representation of the divergence.

Returns:

Type	Description
str	Representation containing the class name and public configuration attributes.

kfc_procedure.core.clustering.divergences.base.BregmanDivergenceFactory

Bases: BaseFactory

Factory class for Bregman divergence implementations.

This factory maintains a registry mapping divergence identifiers to concrete subclasses of :class:BaseBregmanDivergence. It enables dynamic creation of divergence objects from configuration files, user parameters, or runtime specifications.

Notes

The registry associates string names with divergence classes. New divergences can be registered and instantiated without modifying client code, supporting extensible clustering and optimization pipelines.

Examples:

>>> divergence = BregmanDivergenceFactory.create("squared_euclidean")
>>> divergence
SquaredEuclideanDivergence()

Attributes:

Name	Type	Description
_registry	dict of str to type	Internal mapping from divergence names to concrete divergence classes.

kfc_procedure.core.clustering.divergences.euclidean.SquaredEuclidean

Bases: BaseBregmanDivergence

Squared Euclidean distance.

Generator φ(x) = ‖x‖²₂ = Σᵢ xᵢ² Divergence D(x, y) = ‖x − y‖²₂ Gradient ∇φ(x) = 2x

Exponential family : Gaussian Domain : ℝᵈ (no restriction)

Note :

distance is overridden to use the identity ‖x − y‖² = ‖x‖² − 2⟨x, y⟩ + ‖y‖²

Which reduces the computation to a single matrix multiplication, avoiding the explicit (n, K, d) intermediate tensor create by the base-class einsum implementation.

distance

Reduced distance computation for squared Euclidean: D(x, y) = ‖x‖² − 2⟨x, y⟩ + ‖y‖² via BLAS-Level matrix multiplication

Uses ‖x−y‖² = ‖x‖² − 2 x·y + ‖y‖², O(nKd) with near-peak BLAS throughput. Avoids the (n, K, d) broadcast tensor of the base-class einsum → lower peak memory.

kfc_procedure.core.clustering.divergences.gkl.GKLDivergence

Bases: BaseBregmanDivergence

Generalised Kullback-Leibler (I-divergence).

Generator φ(x) = Σᵢ xᵢ ln(xᵢ) Divergence D(x, y) = Σᵢ [ xᵢ ln(xᵢ/yᵢ) − (xᵢ − yᵢ) ] Gradient ∇φ(x) = ln(x) + 1

Exponential family : Poisson Domain : (0, +∞)ᵈ

Note

0 ln(0) = 0 and 0 ln(0/y) = 0 (continuity limit, paper §0/0 = 0).

kfc_procedure.core.clustering.divergences.itakura_saito.ItakuraSaito

Bases: BaseBregmanDivergence

Itakura-Saito divergence.

Generator φ(x) = −Σᵢ ln(xᵢ) Divergence D(x, y) = Σᵢ [ xᵢ/yᵢ − ln(xᵢ/yᵢ) − 1 ] Gredient ∇φ(x) = −1/x

Exponential family : Exponential / Gamma Domain : (0, +∞)ᵈ

kfc_procedure.core.clustering.divergences.logistic.LogisticLoss

Bases: BaseBregmanDivergence

Logistic / binary cross-entropy loss.

Generator φ(x) = Σᵢ [ xᵢ ln(xᵢ) + (1−xᵢ) ln(1−xᵢ) ] Divergence D(x, y) = Σᵢ [ xᵢ ln(xᵢ/yᵢ) + (1−xᵢ) ln((1−xᵢ)/(1−yᵢ)) ]

Exponential family : Bernoulli / Binomial Domain : (0, 1)ᵈ