Select Git revision
main.py 4.94 KiB
# Importation des bibliothèques
from typing import Tuple, List
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
def import_csv(filename: str, h: int or None) -> pd.DataFrame:
"""
Importe un fichier CSV et retourne un DataFrame pandas.
Args:
filename (str): Le chemin du fichier CSV.
h (int or None, optional): L'entête du fichier CSV.
Returns:
pandas.DataFrame: Les données importées sous forme de DataFrame.
"""
return pd.read_csv(filename, header=h)
def manhattan_distance(x1: np.ndarray, x2: np.ndarray) -> float:
"""
Calcule la distance de Manhattan (L2) entre deux vecteurs.
Args:
x1 (numpy.ndarray): Le premier vecteur.
x2 (numpy.ndarray): Le deuxième vecteur.
Returns:
float: La distance de Manhattan entre x1 et x2.
"""
squared_diff = (x1 - x2) ** 2 # Carré des différences
l2_manhattan = np.sqrt(np.sum(squared_diff)) # Racine carrée de la somme des carrés
return l2_manhattan
def assign_clusters(X: np.ndarray, centroids: np.ndarray) -> np.ndarray:
"""
Attribue chaque point de données à son cluster le plus proche en utilisant la distance de Manhattan.
Args:
X (numpy.ndarray): Les données.
centroids (numpy.ndarray): Les centroïdes des clusters.
Returns:
numpy.ndarray: Les étiquettes de cluster attribuées à chaque point de données.
"""
distances = np.array([[manhattan_distance(x, centroid) for centroid in centroids] for x in X])
return np.argmin(distances, axis=1)
def k_means(X: np.ndarray, k: int, max_iterations: int = 100) -> Tuple[np.ndarray, np.ndarray]:
"""
Implémente l'algorithme K-Means pour regrouper les données en k clusters.
Args:
X (numpy.ndarray): Les données à regrouper.
k (int): Le nombre de clusters à former.
max_iterations (int, optional): Le nombre maximal d'itérations. Défaut à 100.
Returns:
tuple: Une paire contenant les étiquettes de cluster et les centroïdes finaux.
"""
# Initialisation des k-centroïdes de manière aléatoire
np.random.seed(0)
centroids = X[np.random.choice(X.shape[0], k, replace=False)] # séléctionne k points aléatoirement dans la liste X
old_centroids = np.zeros(centroids.shape)
new_centroids = centroids.copy()
distances_history = [] # Pour stocker la somme des distances
iteration = 0
# pour vérifier que les centroides ne changent plus , il faut check que l'ancien et le nouveau soient pareils , on ajoute tout de même un nombre d'itérations max pour ne pas tourner à l'infini
while not np.array_equal(old_centroids, new_centroids) and iteration < max_iterations:
iteration += 1
labels = assign_clusters(X, new_centroids)
old_centroids = new_centroids.copy()
for i in range(k):
new_centroids[i] = np.mean(X[labels == i], axis=0)
# Calcul de la somme des distances au sein de chaque cluster (fonction objectif)
total_distance = 0
for i in range(k):
cluster_points = X[labels == i]
cluster_distance = np.sum([manhattan_distance(point, new_centroids[i]) for point in cluster_points])
total_distance += cluster_distance
distances_history.append(total_distance)
# Affichage des clusters à cette itération
plt.figure(figsize=(8, 6))
for i in range(k):
cluster_points = X[labels == i]
plt.scatter(cluster_points[:, 0], cluster_points[:, 1], label=f"Cluster {i + 1}")
plt.scatter(new_centroids[:, 0], new_centroids[:, 1], marker="X", color="black", label="Centroids")
plt.xlabel("Caractéristique 1")
plt.ylabel("Caractéristique 2")
plt.legend()
plt.title(f"Iteration {iteration}")
plt.show()
# Tracer la somme des distances à chaque itération
plt.figure(figsize=(8, 6))
plt.plot(range(1, iteration + 1), distances_history, marker='o')
plt.xlabel("Iteration")
plt.ylabel("Somme des distances")
plt.title("Evolution de la somme des distances")
plt.show()
return labels, new_centroids
if __name__ == "__main__":
# Initialiser k-centroides
# attribuer les points aux centroïde le plus proche (Manhattan / L2)
# Tant que les centroïdes bougent :
# Pour chaque cluster, calculer le point central du cluster (moyenne des coordonnées)
# noter si ancien centroïde ~= nouveau centroïde
# attribution des points aux nouveaux centroïdes
# calcul de la somme des distances au sein d'un cluster
# fonction objectif à minimiser
# plot la somme de la somme des distances à chaque itération
# afficher les nouveaux cluster à chaque itérations
# Charger les données depuis le fichier CSV
df = import_csv("Data/iris.csv", h=None)
X = df.iloc[:, :-1].values
k = 3
labels, centroids = k_means(X, k)
print("Nouveaux centroïdes finaux:")
print(centroids)