k‑średnich

k‑średnich (ang. k‑means) to popularny algorytm grupowania danych stosowany w statystyce i uczeniu automatycznym. Należy do klasy metod klasteryzacji partycjonującej, w której zbiór obiektów dzielony jest na k nieprzecinających się podzbiorów (klastrów) w taki sposób, aby suma odległości kwadratowych między obiektami a środkiem ich klastra była minimalna.

Historia

Idea grupowania oparta na średnich pojawiła się już w latach 1950 – 1960, ale pierwsza formalna prezentacja algorytmu k‑średnich została opublikowana w 1967 roku przez Jamesa MacQueena. Od tego czasu algorytm został zaadaptowany w wielu dziedzinach, m.in. w biologii molekularnej, przetwarzaniu obrazu oraz w analizie rynkowej.

Podstawowe pojęcia

• k – liczba klastrów określana przez użytkownika przed uruchomieniem algorytmu.
• Centroid (środek klastra) – wektor będący średnią arytmetyczną wszystkich punktów przypisanych do danego klastra.
• Funkcja celu – suma kwadratów odległości (zwykle euklidesowej) między punktami a ich centroidami.

Opis działania

Algorytm k‑średnich przebiega w kilku krokach:

1. Wybór początkowych k centroidów – najczęściej losowo ze zbioru danych lub przy użyciu metod heurystycznych (np. k‑medoidy, k‑means++).
2. Przypisanie każdego punktu do najbliższego centroidu (etap przypisania).
3. Obliczenie nowych centroidów jako średnich arytmetycznych punktów w każdym klastrze (etap aktualizacji).
4. Powtórzenie kroków 2 i 3 aż do spełnienia warunku stopu: brak zmiany przynależności punktów, zmiana wartości funkcji celu poniżej ustalonego progu lub maksymalna liczba iteracji.

Warianty algorytmu

Istnieje wiele modyfikacji klasycznego k‑średnich, które mają na celu poprawę jakości grupowania lub przyspieszenie obliczeń:

• k‑means++ – metoda inicjalizacji centroidów zmniejszająca ryzyko utknięcia w słabych minima.
• Mini‑Batch k‑means – algorytm przyspieszający działanie na dużych zbiorach danych poprzez przetwarzanie małych podzbiorów (mini‑batch).
• Fuzzy c‑means – wersja rozmyta, w której punkty mogą należeć do wielu klastrów z określonymi stopniami przynależności.
• k‑medoidy – zamiana centroidów na faktyczne obiekty z danych, co czyni algorytm bardziej odpornym na wartości odstające.

Zastosowania

Algorytm k‑średnich znajduje zastosowanie w wielu dziedzinach, m.in.:

• segmentacji obrazu – grupowanie pikseli o podobnych kolorach lub intensywności.
• analizie klastrów klientów w marketingu – segmentacja bazy klientów pod kątem zachowań zakupowych.
• Kompresji danych – zamiana dużej liczby punktów na ograniczoną liczbę centroidów.
• Wstępnej redukcji wymiarowości przed zastosowaniem metod bardziej złożonych, takich jak klasteryzacja hierarchiczna.

Zalety i wady

Zalety	Wady
Prosta implementacja i szybka konwergencja w praktyce.	Wrażliwość na wybór początkowych centroidów.
Skalowalność – działa w czasie liniowym względem liczby punktów.	Wymaga z góry określenia liczby klastrów k.
Łatwość interpretacji wyników (średnie jako reprezentatywne centra).	Wrażliwość na wartości odstające (outliers).

Implementacje i dostępne biblioteki

W najpopularniejszych środowiskach programistycznych można znaleźć gotowe implementacje k‑średnich:

• Python – sklearn.cluster.KMeans w bibliotece scikit‑learn.
• R – funkcja kmeans() w pakiecie stats.
• MATLAB – kmeans w toolboxie Statistics and Machine Learning Toolbox.
• Julia – pakiet Clustering.jl.

Przykładowy kod (Python)

import numpy as np
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt

# Generowanie przykładowych danych
X = np.random.rand(300, 2)

# Definicja modelu k‑średnich dla 3 klastrów
kmeans = KMeans(n_clusters=3, init='k-means++', random_state=42)
kmeans.fit(X)

# Wyniki
centroids = kmeans.cluster_centers_
labels = kmeans.labels_

# Wizualizacja
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis', s=30)
plt.scatter(centroids[:, 0], centroids[:, 1], c='red', marker='X', s=200)
plt.title('Klasteryzacja metodą k‑średnich')
plt.show()

Bibliografia

1. MacQueen, J. (1967). “Some Methods for Classification and Analysis of Multivariate Observations”. Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, 1: 281–297.
2. Arthur, D., & Vassilvitskii, S. (2007). “k‑means++: The Advantages of Careful Seeding”. Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1027–1035.
3. Han, J., Kamber, M., & Pei, J. (2012). Data Mining: Concepts and Techniques. Morgan Kaufmann.
4. Pedregosa, F. et al. (2011). “Scikit‑learn: Machine Learning in Python”. Journal of Machine Learning Research, 12: 2825‑2830.

Algorytm k‑średnich pozostaje jednym z fundamentów współczesnej analizy danych, a jego prostota oraz efektywność sprawiają, że jest najczęściej wybieranym narzędziem wstępnej grupowania w projektach uczenia automatycznego i data science.