Qu'est-ce que l'algorithme K-means ?

K-means est un algorithme de clustering non supervisé qui partitionne un ensemble de données en k groupes distincts (clusters). Il est largement utilisé en apprentissage automatique pour la classification de données.

L'algorithme fonctionne en itérant entre l'affectation des points aux centroïdes les plus proches et la mise à jour de la position des centroïdes jusqu'à convergence.

Le savais-tu ?

L'algorithme K-means a été proposé pour la première fois en 1957 par Stuart Lloyd, mais n'a été publié qu'en 1982. Il est aujourd'hui l'un des algorithmes de clustering les plus utilisés.

Principe Général de K-means

K-means fonctionne selon les étapes suivantes : 1. Initialisation aléatoire des centroïdes 2. Affectation de chaque point au centroïde le plus proche 3. Recalcul des centroïdes comme moyenne des points du cluster 4. Répétition jusqu'à convergence

$$ J = \sum_{i=1}^{k} \sum_{x \in C_i} \|x - \mu_i\|^2 $$

La fonction de coût J (inertie) mesure la somme des distances au carré entre chaque point et son centroïde associé. L'algorithme cherche à minimiser cette valeur.

Comment appliquer K-means au projet de robot bipède ?

Dans un robot bipède, K-means peut être utilisé pour classifier les différents états de marche ou pour regrouper des configurations articulaires similaires. Cela permet de simplifier la planification des mouvements et d'identifier des patterns de marche optimaux.

Implémentation K-means 
from sklearn.cluster import KMeans
import numpy as np

# Données des angles articulaires du robot
joint_angles = np.array([...])  # matrice n_samples x n_joints

# Application de K-means
kmeans = KMeans(n_clusters=5, random_state=0).fit(joint_angles)
labels = kmeans.labels_
centroids = kmeans.cluster_centers_

Dans quelle partie du code peut intervenir K-means ?

Classification des patterns de marche

K-means peut être utilisé pour identifier et classifier les différents patterns de marche du robot bipède à partir des données des capteurs et des angles articulaires.

Exemple pratique :

En analysant les données historiques de marche, K-means peut découvrir des clusters naturels correspondant à différentes allures (lente, normale, rapide) ou différents types de terrain (plat, montée, descente).

Objectif : Optimiser la planification des mouvements en utilisant les centroïdes comme configurations articulaires de référence.

Références

  • MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability.
  • Lloyd, S. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory.
  • Arthur, D., & Vassilvitskii, S. (2007). k-means++: The advantages of careful seeding. Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms.
  • Pedregosa, F., et al. (2011). Scikit-learn: Machine Learning in Python. Journal of Machine Learning Research.