L'algorithme K-Means peut être utilisé par exemple pour l'affectation de cible dans un espace. Dans ce cas, nous allons utiliser un jeu de données aléatoire en utilisant une fonction custom qui va nous permettre de générer des coordonnées sur mesure.
Imaginons que vous venez d'être embauché en tant qu'ingénieur au sein d'une équipe dans une société à la pointe de la technologie sur les drones. Votre société est contactée par l'un de ses clients les plus importants, l'occasion pour vous de faire vos preuves. Ce client a besoin d'une solution pour traiter des plantes dans ces champs. Souhaitant moderniser et optimiser sa production, ce client fait naturellement appel à vous. Lors de la répartition des tâches, votre équipe vous demande de proposer une stratégie lors de la partie affectation des objectifs à traiter pour chaque agent. Il vous est précisé que la répartition des objectifs doit se faire le plus vite possible (l'optimalité n'est pas la priorité) et de façon relativement équitable entre les agents (drones) disponibles.
Votre collègue en charge de l'acquisition des données vous fournit un échantillon qui a été récupéré lors du prototypage de sa méthode. Les coordonnées récupérées sont disponibles via la méthode 'generate_dataset'. Il s'agit des coordonnées des plantes sur 4 rangées.
def generate_dataset(num_rect=4, rect_width=150, rect_height=2000, rect_spacing=200, num_points=200): x = [] y = [] for i in range(num_rect): # dimensionnement du rectangle rect_x = np.array([i * (rect_width + rect_spacing), i * (rect_width + rect_spacing), (i + 1) * rect_width + i * rect_spacing, (i + 1) * rect_width + i * rect_spacing, i * (rect_width + rect_spacing)]) rect_y = np.array([0, rect_height, rect_height, 0, 0]) # Génération des points dans le rectangle courant x_points = np.random.uniform(low=rect_x[0], high=rect_x[2], size=num_points//num_rect) y_points = np.random.uniform(low=rect_y[0], high=rect_y[1], size=num_points//num_rect) x.append(x_points) y.append(y_points) # Concaténation des points de tous les rectangles x = np.concatenate(x) y = np.concatenate(y) return np.column_stack((x, y))
Vous décidez donc de proposer la méthode K-Means sur ce jeu de données :
from sklearn.cluster import KMeans import numpy as np import seaborn as sns import matplotlib.pyplot as plt # Initialisation des paramètres np.random.seed(42) def generate_dataset(num_rect=4, rect_width=150, rect_height=2000, rect_spacing=200, num_points=200): x = [] y = [] for i in range(num_rect): rect_x = np.array([i * (rect_width + rect_spacing), i * (rect_width + rect_spacing), (i + 1) * rect_width + i * rect_spacing, (i + 1) * rect_width + i * rect_spacing, i * (rect_width + rect_spacing)]) rect_y = np.array([0, rect_height, rect_height, 0, 0]) # Génération des points dans le rectangle courant x_points = np.random.uniform(low=rect_x[0], high=rect_x[2], size=num_points//num_rect) y_points = np.random.uniform(low=rect_y[0], high=rect_y[1], size=num_points//num_rect) x.append(x_points) y.append(y_points) # Concaténation des points de tous les rectangles x = np.concatenate(x) y = np.concatenate(y) return np.column_stack((x, y)) # Récupération des coordonnées X = generate_dataset() # Définition du modèle KMeans en fonction du nombre d'agents disponibles n = 10 kmeans = KMeans(n_clusters=n, random_state=42) # Entraînement du modèle sur les données kmeans.fit(X) # Attribution des étiquettes de cluster à chaque point labels = kmeans.labels_ # affichage de la répartition des cibles par clusters classes, cpt = np.unique(labels, return_counts=True) for classe, cpt in zip(classes, cpt): print("Nombre de cibles affectées à l'agent {}: {}".format(classe, cpt)) # génération du plot en utilisant seaborn sns.scatterplot(x=X[:, 0], y=X[:, 1], hue=labels, palette="colorblind") # Ajout des centres de cluster trouvés par le modèle sns.scatterplot(x=kmeans.cluster_centers_[:, 0], y=kmeans.cluster_centers_[:, 1], marker="X", color='red', s=200) # affichage du plot plt.legend(bbox_to_anchor=(1.05, 1), loc=2, borderaxespad=0.) ax = plt.gca() ax.set_aspect('equal', adjustable='box') plt.show()
OUTPUT: Nombre de cibles affectées à l'agent 0: 22 Nombre de cibles affectées à l'agent 1: 23 Nombre de cibles affectées à l'agent 2: 20 Nombre de cibles affectées à l'agent 3: 15 Nombre de cibles affectées à l'agent 4: 20 Nombre de cibles affectées à l'agent 5: 17 Nombre de cibles affectées à l'agent 6: 27 Nombre de cibles affectées à l'agent 7: 13 Nombre de cibles affectées à l'agent 8: 21 Nombre de cibles affectées à l'agent 9: 22
L'implémentation d'un algorithme de clustering K-means peut être un exercice utile pour comprendre comment les algorithmes de clustering fonctionnent et comment les données peuvent être regroupées en clusters significatifs.
Or, nous venons de voir comment utiliser K-means pour affecter des cibles à des agents en les regroupant par clusters. Nous avons constaté que l'algorithme de clustering K-means permet une bonne répartition des cibles et une rapidité d'exécution acceptable pour notre cas d'utilisation.
Cependant, il est important de noter que K-means n'est qu'un des nombreux algorithmes de clustering disponibles et qu'il peut ne pas être le plus approprié pour tous les types de données et de cas d'utilisation. Il est alors important de choisir soigneusement l'algorithme de clustering le plus approprié en fonction des besoins spécifiques de chaque projet.