K-médiane

Définition

Algorithme de clustering étroitement lié à k-moyennes. La différence pratique entre les deux est la suivante :

Dans l'algorithme k-moyennes, les centroïdes sont déterminés en minimisant la somme des carrés de la distance entre un centroïde potentiel et chacun de ses exemples. Dans l'algorithme k-médiane, les centroïdes sont déterminés en minimisant la somme de la distance entre un centroïde potentiel et chacun de ses exemples. Notez que la définition du terme "distance" est également différente :

Dans l'algorithme k-moyenne, la notion de distance utilisée est la distance euclidienne entre un centroïde et un exemple. Dans un espace à deux dimensions, la distance euclidienne revient à utiliser le théorème de Pythagore pour calculer l'hypoténuse. Par exemple, la distance k-moyennes entre (2,2) et (5,-2) est : Dans l'algorithme k-médiane, la notion de distance utilisée est la distance de Manhattan entre le centroïde et un exemple. Cette distance est la somme des deltas absolus dans chaque dimension. Par exemple, la distance k-médiane entre (2,2) et (5,-2) est :