k-NN & k-Means : Classification et Clustering

import math

def distance_euclidienne(a, b):
    total = 0
    for i in range(len(a)):
        total = total + (a[i] - b[i]) ** 2
    return math.sqrt(total)

def distance_manhattan(a, b):
    total = 0
    for i in range(len(a)):
        total = total + abs(a[i] - b[i])
    return total

print(distance_euclidienne([0, 0], [3, 4]))  # 5.0
print(distance_manhattan([0, 0], [3, 4]))  # 7

X = [[d["heures"], d["presence"]] for d in donnees]
y = [d["resultat"] for d in donnees]

print("X :", X)
print("y :", y)

def knn_classifier(X, y, nouveau_point, k):
    """k-NN : classe un nouveau point par vote majoritaire des k voisins."""
    # Calcul des distances
    distances = []
    for i in range(len(X)):
        d = distance_euclidienne(X[i], nouveau_point)
        distances.append((d, y[i]))
    
    # Tri par distance
    distances.sort(key=lambda paire: paire[0])
    
    # Vote des k plus proches
    votes = {}
    for i in range(k):
        etiquette = distances[i][1]
        votes[etiquette] = votes.get(etiquette, 0) + 1
    
    # Trouver l'étiquette majoritaire
    majoritaire = None
    max_votes = -1
    for etiquette, compte in votes.items():
        if compte > max_votes:
            max_votes = compte
            majoritaire = etiquette
    
    return majoritaire

nouveau = [3, 0.75]
print("k=3 →", knn_classifier(X, y, nouveau, 3))
print("k=5 →", knn_classifier(X, y, nouveau, 5))

def taux_classification(X, y, k):
    bons = 0
    for i in range(len(X)):
        pred = knn_classifier(X, y, X[i], k)
        if pred == y[i]:
            bons = bons + 1
    return bons / len(X)

for k in [1, 3, 5, 7]:
    print("k =", k, "→ précision :", taux_classification(X, y, k))

from random import sample

def kmeans(points, k, iterations=20):
    """k-means : regroupe les points en k clusters.
    
    Retourne :
        centroides — liste des k centres finaux
        assign — liste de l'indice du cluster pour chaque point
    """
    # Initialisation : choisir k points aléatoires comme centroïdes
    centroides = sample(points, k)
    
    for _ in range(iterations):
        # Étape 1 : assigner chaque point au centroïde le plus proche
        assign = []
        for p in points:
            distances = [distance_euclidienne(p, c) for c in centroides]
            cluster = distances.index(min(distances))
            assign.append(cluster)
        
        # Étape 2 : recalculer les centroïdes
        nouveaux_centroides = []
        for j in range(k):
            # Récupérer tous les points du cluster j
            points_du_cluster = [points[i] for i in range(len(points))
                                 if assign[i] == j]
            if points_du_cluster:
                moyenne_x = sum(p[0] for p in points_du_cluster) / len(points_du_cluster)
                moyenne_y = sum(p[1] for p in points_du_cluster) / len(points_du_cluster)
                nouveaux_centroides.append([moyenne_x, moyenne_y])
            else:
                # Si un cluster n'a plus de points, on garde l'ancien centroïde
                nouveaux_centroides.append(centroides[j])
        
        centroides = nouveaux_centroides
    
    # Dernière assignation
    assign = []
    for p in points:
        distances = [distance_euclidienne(p, c) for c in centroides]
        assign.append(distances.index(min(distances)))
    
    return centroides, assign

centroides, assign = kmeans(points, 3)

print("Centroïdes finaux :")
for i, c in enumerate(centroides):
    print("  Cluster", i, ":", [round(v, 2) for v in c])

# Compter les points par cluster
for i in range(3):
    nb = sum(1 for a in assign if a == i)
    print("  Cluster", i, "a", nb, "points")

for k in range(1, 7):
    c, a = kmeans(points, k)
    inert = inertie(points, c, a)
    print("k =", k, "→ inertie :", round(inert, 2))

import matplotlib.pyplot as plt
import numpy as np

# Créer une grille de points dans l'espace [0, 6] × [0, 1]  
# (on agrandit un peu pour voir la frontière)
xx, yy = np.meshgrid(np.linspace(0, 6, 60),
                     np.linspace(0, 1.1, 40))
grille = np.c_[xx.ravel(), yy.ravel()]

# Classifier chaque point de la grille avec k=3
Z = [knn_classifier(X, y, p, 3) for p in grille]
Z = np.array(Z).reshape(xx.shape)

# Tracer la frontière de décision
plt.contourf(xx, yy, Z == "A", alpha=0.3, cmap="RdYlGn")
plt.contour(xx, yy, Z == "A", colors="k", linewidths=0.5)

# Tracer les points d'apprentissage
for i in range(len(X)):
    couleur = "green" if y[i] == "A" else "red"
    plt.scatter(X[i][0], X[i][1], color=couleur, s=100, edgecolors="white", zorder=5)

plt.xlabel("Heures de révision")
plt.ylabel("Taux de présence")
plt.title("Frontière de décision k-NN (k=3)")
plt.show()

centroides, assign = kmeans(points, 3)

couleurs_clusters = ["blue", "orange", "purple"]
for i in range(len(points)):
    plt.scatter(points[i][0], points[i][1],
                color=couleurs_clusters[assign[i]], alpha=0.6, s=40)

# Centroïdes en étoiles
for i, c in enumerate(centroides):
    plt.scatter(c[0], c[1], marker="*", color=couleurs_clusters[i],
                s=300, edgecolors="white", linewidth=2, zorder=10)

plt.title("k-Means : 3 clusters trouvés")
plt.xlabel("x")
plt.ylabel("y")
plt.grid(True)
plt.show()