CodeBlanks Logo Icon CodeBlanks
Login Register

KMeans algorithm

KMeans initializes k centroids randomly and updates them iteratively.

Lloyd's algorithm

The standard solution for KMeans is Lloyd's algorithm. At each step inertia either drops or stays the same; that's why the algorithm always converges, but the solution it finds may be a local optimum.

def kmeans_adim(X, merkez):
    d = ((X[:, None, :] - merkez[None, :, :]) ** 2).sum(axis=2)
    etiket = d.argmin(axis=1)                                   # assignment
    yeni = np.array([X[etiket == k].mean(axis=0) for k in range(len(merkez))])
    return etiket, yeni                                         # update

n_iter_ shows how many rounds were needed to converge; max_iter is the upper limit.

Distance matrix with broadcasting

The expression X[:, None, :] - merkez[None, :, :] broadcasts the shapes (n, 1, d) and (1, k, d) to (n, k, d); summing along the last axis gives each example's squared distance to each centre. It is loop-free and fast:

print(X.shape, merkez.shape)               # (500, 2) (5, 2)
d = ((X[:, None, :] - merkez[None, :, :]) ** 2).sum(axis=2)
print(d.shape)                             # (500, 5)

You'll meet the same pattern in KNN, the RBF kernel and the attention computation.

Practice KMeans by hand

Taking the first 5 examples as the initial centres, run Lloyd's algorithm for 10 rounds (assignment + update). Print the final inertia (sum of squared distances to the nearest centre) as an integer with round.

Starter code

model.py
import numpy as np
from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans

X, _ = make_blobs(n_samples=500, centers=5, cluster_std=1.0, random_state=3)

# buraya yaz

Sample solution

model.py
import numpy as np
from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans

X, _ = make_blobs(n_samples=500, centers=5, cluster_std=1.0, random_state=3)

merkez = X[:5].copy()
for _ in range(10):
    d = ((X[:, None, :] - merkez[None, :, :]) ** 2).sum(axis=2)
    etiket = d.argmin(axis=1)
    merkez = np.array([X[etiket == k].mean(axis=0) for k in range(5)])
d = ((X[:, None, :] - merkez[None, :, :]) ** 2).sum(axis=2)
print(round(d.min(axis=1).sum()))

Expected output

1083

Questions and answers

Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.

1 How does inertia change from one round to the next in Lloyd's algorithm?

  • It changes randomly
  • It is always constant
  • It decreases or stays the same Correct answer
  • It always increases

Explanation: Neither the assignment nor the update step can increase the sum of squared distances.

2 Assign each example to the nearest centre.

Question 
etiket = d.____(axis=1)
Answer 
etiket = d.argmin(axis=1)

Explanation: argmin(axis=1) gives the column of the smallest distance in each row.

3 Match the pieces.

Term Meaning
assignment d.argmin(axis=1)
update Cluster mean
n_iter_ Rounds to converge
local optimum Lloyd's limitation

All lessons in Intermediate

1 scikit-learn basics

  1. What is scikit-learn?
  2. Estimator API
  3. The fit method
  4. The predict method
  5. The score method
  6. Summary - scikit-learn

2 Pipeline

  1. What is a Pipeline?
  2. Steps
  3. fit and predict
  4. Advantages
  5. ColumnTransformer
  6. Summary - Pipeline

3 Cross-validation

  1. What is cross-validation?
  2. K-fold
  3. cross_val_score
  4. Stratified
  5. Advantages
  6. Summary - Cross-validation

4 Grid search

  1. What is grid search?
  2. GridSearchCV
  3. param_grid
  4. best_params_
  5. best_score_
  6. Summary - Grid search

5 SVM

  1. What is SVM?
  2. Margin
  3. Kernel
  4. C parameter
  5. Classification
  6. Summary - SVM

6 Project: SVM

  1. Preparing data
  2. Training model
  3. Prediction
  4. Evaluation

7 Random forest

  1. What is random forest?
  2. Ensemble
  3. n_estimators
  4. Bagging
  5. Feature importance
  6. Summary - Random forest

8 Boosting

  1. What is boosting?
  2. AdaBoost
  3. Gradient boosting
  4. Learning rate
  5. Advantages
  6. Summary - Boosting

9 Clustering

  1. What is clustering?
  2. KMeans
  3. Centroid
  4. Elbow method
  5. Labels
  6. Summary - Clustering

10 KMeans in depth

  1. KMeans algorithm
  2. Initialization
  3. n_init
  4. inertia_
  5. random_state
  6. Summary - KMeans

11 Hierarchical clustering

  1. What is hierarchical clustering?
  2. Dendrogram
  3. Agglomerative
  4. Linkage
  5. Advantages
  6. Summary - Hierarchical clustering

12 Project: Clustering

  1. Preparing data
  2. Training KMeans
  3. Label analysis
  4. Printing results

13 PCA

  1. What is PCA?
  2. Variance
  3. n_components
  4. fit_transform
  5. explained_variance_
  6. Summary - PCA

14 Dimensionality reduction

  1. What is dimensionality reduction?
  2. Why reduce?
  3. PCA vs t-SNE
  4. Visualization
  5. Advantages
  6. Summary - Dimensionality reduction

15 Feature selection

  1. What is feature selection?
  2. Variance threshold
  3. SelectKBest
  4. Recursive elimination
  5. Feature importance
  6. Summary - Feature selection

16 Imbalanced data

  1. What is imbalanced data?
  2. SMOTE
  3. Class weight
  4. Oversampling
  5. Metric selection
  6. Summary - Imbalanced data

17 Project: Features

  1. Feature extraction
  2. Feature selection
  3. Training model
  4. Evaluation

18 Ensemble methods

  1. What is ensemble?
  2. Voting
  3. Bagging
  4. Boosting
  5. Stacking
  6. Summary - Ensemble

19 Regularization

  1. What is regularization?
  2. L1 (Lasso)
  3. L2 (Ridge)
  4. alpha
  5. ElasticNet
  6. Summary - Regularization

20 Intermediate final

  1. Challenge 1
  2. Challenge 2
  3. Challenge 3
  4. Challenge 4