K-Means clustering with multiple initialization methods.
Classes
K-Means clustering algorithm.
Partitions data into k clusters by iteratively assigning points to the nearest centroid and updating centroids to the mean of assigned points. The goal is to minimize the total inertia (within-cluster sum of squared distances).
Constructor
__init__( self, n_clusters: int = 2, init: str = 'k-means++', max_iter: int = 300, n_init: int = 10, tol: float = 0.0001, distance: str = 'euclidean', random_state: Optional[int] = None, )
Overview
The algorithm follows Lloyd's iterative refinement procedure:
- Initialize k centroids using the chosen method (k-means++, random, or farthest)
- Assign each point to the nearest centroid
- Update each centroid to the mean (or median for Manhattan) of its assigned points
-
Repeat steps 2--3 until convergence or
max_iteris reached -
Select the best result across
n_initindependent runs
Theory
K-Means minimizes the within-cluster sum of squares (inertia):
J = \sum_{i=1}^{n} \min_{\mu_j \in C} \| x_i - \mu_j \|^2
The k-means++ initialization selects the next center \mu_i with probability proportional to D(x)^2, the squared distance to the nearest existing center:
P(\mu_i = x) = \frac{D(x)^2}{\sum_{x' \in X} D(x')^2}
This provides an O(\log k) competitive approximation to the optimal k-means solution.
Parameters
n_clusters
int
= 2
The number of clusters to form as well as the number of centroids to generate.
init
{"k-means++", "random", "farthest"}
= "k-means++"
Method for initialization:
- •
"k-means++": Smart initialization that selects centers far from each other - •
"random": Randomly selects :math:`k` observations from the data - •
"farthest": Farthest-first traversal initialization
max_iter
int
= 300
Maximum number of iterations of the k-means algorithm for a single run.
n_init
int
= 10
Number of times the k-means algorithm will be run with different centroid seeds. The final results will be the best output of n_init runs in terms of inertia.
tol
float
= 1e-4
Relative tolerance with regards to Frobenius norm of the difference in the cluster centers of two consecutive iterations to declare convergence.
distance
{"euclidean", "manhattan"}
= "euclidean"
Distance metric to use.
random_state
int
= None
Determines random number generation for centroid initialization.
Attributes
cluster_centers_
np.ndarray of shape (n_clusters, n_features)
Coordinates of cluster centers.
labels_
np.ndarray of shape (n_samples,)
Labels of each point.
inertia_
float
Sum of squared distances of samples to their closest cluster center.
n_iter_
int
Number of iterations run.
Notes
Complexity:
- Training: O(n \cdot k \cdot m \cdot i) where n is samples,
- Space: O((n+k) \cdot m).
- When the number of clusters is known or can be estimated
- When clusters are roughly spherical and similar in size
- Large datasets (linear complexity per iteration)
- As a baseline clustering method before trying more complex approaches
References
Arthur2007
Arthur, D., & Vassilvitskii, S. (2007).
k-means++: The advantages of careful seeding.
Proceedings of the eighteenth annual ACM-SIAM symposium on
Discrete algorithms, pp. 1027-1035.
Lloyd1982
Lloyd, S. P. (1982).
Least squares quantization in PCM.
IEEE Transactions on Information Theory, 28(2), pp. 129-137.
Basic K-Means clustering:
python
>>> import numpy as np
>>> from tuiml.algorithms.clustering import KMeansClusterer
>>> X = np.array([[1, 2], [1, 4], [1, 0],
... [10, 2], [10, 4], [10, 0]])
>>> kmeans = KMeansClusterer(n_clusters=2, random_state=0)
>>> kmeans.fit(X)
>>> kmeans.labels_
array([0, 0, 0, 1, 1, 1], dtype=int32)
>>> kmeans.predict([[0, 0], [12, 3]])
array([0, 1], dtype=int32)
>>> kmeans.cluster_centers_
array([[1., 2.], [10., 2.]])