Algorisme k-means

[1]exemple de k-means++

L'algorisme K-means és un mètode de quantificació vectorial que té com a objectiu la partició d'un conjunt n observacions en k grups en el qual cada observació pertany al grup més proper a la mitjana. És un mètode utilitzat en mineria de dades.[2]

Descripció

Donat un conjunt d'observacions (x₁, x₂, …, x_n), on cada observació és un vector real de d dimensions, k-means construeix una partició de les observacions en k conjunts (k ≤ n) S = {S₁, S₂, …, S_k}. A fi de minimitzar la suma dels quadrats a dins de cada grup (WCSS):

${\underset {\mathbf {S} }{\operatorname {arg\,min} }}\sum _{i=1}^{k}\sum _{\mathbf {x} _{j}\in S_{i}}\left\|\mathbf {x} _{j}-{\boldsymbol {\mu }}_{i}\right\|^{2}$

on µ_i és la mitjana de punts en S_i.

Aplicacions

L'algorisme k-means és fàcil d'aplicar fins i tot en grans grups de dades. S'utilitza sovint abans d'aplicar altres algorismes per donar un punt de partida al programa (preprocessing).

Clusterització de dades

Un dels seus usos és la clusterització de dades, fonamental en l'aprenentatge automàtic. Consisteix a agrupar punts de dades segons la seva similitud. Aquest us serveix, per exemple, per la segmentació de mercat, on els clients són agrupats segons característiques o comportaments similars.

Quantificació vectorial

L'algorisme k-means s'utilitza per quantificar colors dins dels grups k. Amb això es pot, per exemple, agrupar els colors d'una imatge digital per “simplificar-la” i així evitar perdre qualitat quan es comprimeix.