"""
Module: Clustering Hierarchique
Categorie: Unsupervised
Difficulte: Debutant

Genere depuis la plateforme ML Formation
"""

# Imports
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score, mean_squared_error, r2_score

# Charger le dataset
df = pd.read_csv('clustering_2d.csv')

# Explorer les donnees
# Type: Code executable
print("=" * 70)
print("       EXPLORATION DES DONNEES POUR CLUSTERING HIERARCHIQUE")
print("=" * 70)

print("""
Le clustering hierarchique cree un ARBRE de clusters (dendrogramme).
Contrairement a K-Means, on n'a pas besoin de specifier k a l'avance!

Le dendrogramme nous montre la structure COMPLETE des donnees:
- En bas: chaque point est son propre cluster
- En haut: tous les points forment un seul cluster
- La hauteur indique la "dissimilarite" entre clusters fusionnes
""")

print("\n" + "=" * 70)
print("1. APERCU DU DATASET")
print("=" * 70)
display(df.head(10), title="Premieres lignes du dataset")

print("""
Ce dataset contient des points 2D qui forment naturellement des groupes.
Notre objectif: decouvrir cette structure de maniere HIERARCHIQUE.
""")

print("\n" + "=" * 70)
print("2. DIMENSIONS ET STATISTIQUES")
print("=" * 70)

n_points, n_features = df.shape
print(f"""
DIMENSIONS:
  • Nombre de points: {n_points}
  • Nombre de features: {n_features} (x, y)

STATISTIQUES DESCRIPTIVES:
""")
display(df.describe().round(2), title="Statistiques")

print(f"""
OBSERVATIONS:
  • X varie de {df['x'].min():.1f} a {df['x'].max():.1f}
  • Y varie de {df['y'].min():.1f} a {df['y'].max():.1f}
  • Les donnees semblent bien reparties dans l'espace
""")

print("\n" + "=" * 70)
print("3. VISUALISATION DES DONNEES")
print("=" * 70)

print("""
Visualisons les donnees pour avoir une intuition des clusters possibles.
""")

plt.figure(figsize=(10, 6))
plt.scatter(df['x'], df['y'], alpha=0.6, color='#9B7AC4', s=40, edgecolors='white', linewidth=0.5)
plt.xlabel('X', fontsize=12)
plt.ylabel('Y', fontsize=12)
plt.title('Donnees de Clustering - Structure a Decouvrir', fontsize=14, fontweight='bold')
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()

print("""
ANALYSE VISUELLE:
  • On distingue visuellement plusieurs groupes de points
  • Certains groupes semblent plus denses que d'autres
  • Le clustering hierarchique va nous reveler la structure COMPLETE

AVANTAGE DU HIERARCHIQUE:
  → Pas besoin de decider combien de clusters maintenant!
  → Le dendrogramme nous montrera TOUTES les possibilites.
""")

print("\n" + "=" * 70)
print("              PRET POUR LA CONSTRUCTION DU DENDROGRAMME")
print("=" * 70)


# Construire le dendrogramme
# Type: Code executable
from scipy.cluster.hierarchy import dendrogram, linkage
from sklearn.preprocessing import StandardScaler

print("=" * 70)
print("       CONSTRUCTION DU DENDROGRAMME")
print("=" * 70)

print("""
Le DENDROGRAMME est un arbre qui represente l'historique complet des
fusions de clusters. C'est l'outil principal du clustering hierarchique!

ETAPES DE CONSTRUCTION:
1. Normaliser les donnees (StandardScaler)
2. Calculer la matrice de linkage (distances entre clusters)
3. Construire l'arbre des fusions
""")

print("\n" + "=" * 70)
print("1. PREPARATION DES DONNEES")
print("=" * 70)

X = df[['x', 'y']].values
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

print(f"""
Donnees brutes: {X.shape[0]} points x {X.shape[1]} dimensions

POURQUOI NORMALISER?
  • Les features doivent avoir le meme poids dans les distances
  • Sans normalisation, une feature avec grande variance dominerait
  • StandardScaler: moyenne=0, ecart-type=1

VERIFICATION DE LA NORMALISATION:
  • Avant: X moyen = {X.mean(axis=0).round(2)}, std = {X.std(axis=0).round(2)}
  • Apres: X moyen = {X_scaled.mean(axis=0).round(4)}, std = {X_scaled.std(axis=0).round(4)}
""")

print("\n" + "=" * 70)
print("2. CALCUL DE LA MATRICE DE LINKAGE")
print("=" * 70)

print("""
Le LINKAGE definit comment calculer la distance entre clusters.

METHODE 'WARD' (utilisee ici):
  • Minimise l'augmentation de variance intra-cluster
  • Tend a creer des clusters spheriques et de taille similaire
  • Recommandee pour la plupart des cas
""")

Z = linkage(X_scaled, method='ward')

print(f"""
MATRICE DE LINKAGE CALCULEE:
  • Forme: {Z.shape}
  • Chaque ligne = une fusion: [cluster1, cluster2, distance, nb_points]
  • Nombre de fusions effectuees: {len(Z)}
  • Distance min de fusion: {Z[:, 2].min():.4f}
  • Distance max de fusion: {Z[:, 2].max():.4f}
""")

print("\n" + "=" * 70)
print("3. VISUALISATION DU DENDROGRAMME")
print("=" * 70)

print("""
LECTURE DU DENDROGRAMME:
  • Axe X: echantillons (feuilles de l'arbre)
  • Axe Y: distance (hauteur de fusion)
  • Chaque 'pont' horizontal = une fusion de clusters
  • La hauteur du pont = dissimilarite entre les clusters fusionnes
""")

plt.figure(figsize=(14, 7))
dendrogram(Z, truncate_mode='lastp', p=30, show_leaf_counts=True,
           leaf_rotation=90, leaf_font_size=10)
plt.xlabel('Echantillons (ou nombre de points dans le sous-arbre)', fontsize=12)
plt.ylabel('Distance de fusion', fontsize=12)
plt.title('Dendrogramme - Vue Hierarchique Complete', fontsize=14, fontweight='bold')
plt.grid(True, alpha=0.3, axis='y')
plt.tight_layout()
plt.show()

print("""
INTERPRETATION:
  • Les grands "sauts" verticaux indiquent des separations naturelles
  • Plus on coupe bas, plus on a de clusters
  • Plus on coupe haut, moins on a de clusters

COMMENT CHOISIR LE NOMBRE DE CLUSTERS?
  → Cherchez le plus grand "saut" vertical (gap)
  → Cela correspond a une separation naturelle des donnees
  → On va voir comment faire dans la section suivante!

ANALOGIE BIOLOGIQUE:
  Le dendrogramme ressemble a un arbre genealogique:
  - Les feuilles = individus (points de donnees)
  - Les branches = ancetres communs (clusters)
  - La racine = ancetre commun a tous (cluster unique)
""")

print("\n" + "=" * 70)
print("              DENDROGRAMME CONSTRUIT AVEC SUCCES!")
print("=" * 70)


# Choisir le nombre de clusters
# Type: Code executable
from scipy.cluster.hierarchy import dendrogram, linkage, fcluster
from sklearn.preprocessing import StandardScaler

print("=" * 70)
print("       CHOISIR LE NOMBRE DE CLUSTERS VIA LE DENDROGRAMME")
print("=" * 70)

print("""
L'avantage majeur du clustering hierarchique: le dendrogramme nous
GUIDE pour choisir le bon nombre de clusters!

METHODE DU "GAP" (SAUT VERTICAL):
  • Cherchez l'endroit ou il y a le plus grand saut vertical
  • Tracez une ligne horizontale a cette hauteur
  • Comptez combien de lignes verticales elle croise
  • Ce nombre = nombre optimal de clusters
""")

print("\n" + "=" * 70)
print("1. PREPARATION")
print("=" * 70)

X = df[['x', 'y']].values
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)
Z = linkage(X_scaled, method='ward')

print(f"""
Donnees preparees: {X_scaled.shape[0]} points normalises
Matrice de linkage calculee avec methode 'ward'
""")

print("\n" + "=" * 70)
print("2. ANALYSE DES DISTANCES DE FUSION")
print("=" * 70)

distances = Z[:, 2]
gaps = np.diff(distances)

print("""
DERNIERES FUSIONS (les plus significatives):
""")
print("-" * 50)
print(f"{'Fusion':<10} {'Distance':<15} {'Gap avec precedent'}")
print("-" * 50)
for i in range(-10, 0):
    gap = distances[i] - distances[i-1] if i > -len(distances) else 0
    star = " *** GRAND GAP" if gap > np.percentile(gaps, 90) else ""
    print(f"{len(distances)+i+1:<10} {distances[i]:<15.4f} {gap:.4f}{star}")

biggest_gap_idx = np.argmax(gaps[-10:]) + len(gaps) - 10
suggested_k = len(distances) - biggest_gap_idx

print(f"""
ANALYSE:
  • Plus grand gap recent a l'indice {biggest_gap_idx}
  • Cela suggere k = {suggested_k} clusters
""")

print("\n" + "=" * 70)
print("3. DENDROGRAMME AVEC LIGNES DE COUPE")
print("=" * 70)

print("""
Visualisons le dendrogramme avec differentes lignes de coupe possibles.
Chaque ligne horizontale donne un nombre different de clusters.
""")

plt.figure(figsize=(14, 8))
dendrogram(Z, truncate_mode='lastp', p=30, show_leaf_counts=True)

# Lignes de coupe pour differents k
cut_heights = [5, 8, 12, 18]
colors = ['#27ae60', '#F7E64D', '#e67e22', '#e74c3c']
for height, color in zip(cut_heights, colors):
    plt.axhline(y=height, color=color, linestyle='--', linewidth=2, alpha=0.7)

plt.xlabel('Echantillons', fontsize=12)
plt.ylabel('Distance de fusion', fontsize=12)
plt.title('Ou couper le dendrogramme? (lignes = differents k)', fontsize=14, fontweight='bold')
plt.grid(True, alpha=0.3, axis='y')

# Legende
legend_text = [f'Coupe a h={h}' for h in cut_heights]
plt.legend(legend_text, loc='upper right')
plt.tight_layout()
plt.show()

print(f"""
INTERPRETATION DES LIGNES DE COUPE:
  • Ligne verte (h=5): beaucoup de clusters (>8)
  • Ligne jaune (h=8): clusters intermediaires (~6)
  • Ligne orange (h=12): quelques clusters (~4-5)
  • Ligne rouge (h=18): tres peu de clusters (~2-3)

REGLE D'OR:
  Coupez juste EN DESSOUS du plus grand saut vertical!
  Cela capture la structure naturelle des donnees.
""")

print("\n" + "=" * 70)
print("4. VERIFICATION AVEC DIFFERENTS NOMBRES DE CLUSTERS")
print("=" * 70)

print("""
Utilisons fcluster() pour obtenir les labels a differentes hauteurs:
""")

for height in [5, 8, 12, 18]:
    labels_cut = fcluster(Z, t=height, criterion='distance')
    n_clusters = len(set(labels_cut))
    print(f"  Coupe a hauteur {height:2d} → {n_clusters} clusters")

print("""

CONSEIL PRATIQUE:
  Pour ce dataset, une coupe autour de h=8-10 semble optimale.
  Cela donne environ 5 clusters, ce qui correspond aux groupes visibles.
""")

print("\n" + "=" * 70)
print("              ANALYSE DU DENDROGRAMME TERMINEE!")
print("=" * 70)


# Appliquer le clustering
# Type: Code executable
from sklearn.cluster import AgglomerativeClustering
from sklearn.preprocessing import StandardScaler

print("=" * 70)
print("       APPLICATION DU CLUSTERING HIERARCHIQUE")
print("=" * 70)

print("""
Maintenant que nous avons analyse le dendrogramme, appliquons le
clustering avec scikit-learn pour obtenir les labels de cluster.

AGGLOMERATIVECLUSTERING:
  • Implementation efficace du clustering hierarchique
  • Parametres principaux: n_clusters, linkage
  • Retourne les labels de cluster pour chaque point
""")

print("\n" + "=" * 70)
print("1. PREPARATION DES DONNEES")
print("=" * 70)

X = df[['x', 'y']].values
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

print(f"""
Donnees preparees:
  • {X.shape[0]} points
  • {X.shape[1]} dimensions
  • Normalisation StandardScaler appliquee
""")

print("\n" + "=" * 70)
print("2. CREATION ET ENTRAINEMENT DU MODELE")
print("=" * 70)

n_clusters = 5

print(f"""
PARAMETRES CHOISIS:
  • n_clusters = {n_clusters} (base sur l'analyse du dendrogramme)
  • linkage = 'ward' (minimise variance intra-cluster)

L'algorithme va:
  1. Considerer chaque point comme un cluster
  2. Fusionner iterativement les clusters les plus proches
  3. S'arreter quand il reste exactement {n_clusters} clusters
""")

hc = AgglomerativeClustering(n_clusters=n_clusters, linkage='ward')
labels = hc.fit_predict(X_scaled)

print(f"""
MODELE ENTRAINE!
  • Algorithme: AgglomerativeClustering
  • Nombre de fusions effectuees: {X.shape[0] - n_clusters}
""")

print("\n" + "=" * 70)
print("3. RESULTATS DU CLUSTERING")
print("=" * 70)

print(f"""
REPARTITION DES POINTS PAR CLUSTER:
""")
print("-" * 40)
print(f"{'Cluster':<12} {'Nb Points':<15} {'Pourcentage'}")
print("-" * 40)

for label in sorted(set(labels)):
    count = (labels == label).sum()
    pct = count / len(labels) * 100
    bar = "█" * int(pct / 2)
    print(f"{label:<12} {count:<15} {pct:5.1f}% {bar}")

print("-" * 40)
print(f"{'TOTAL':<12} {len(labels):<15} 100.0%")

print(f"""

ANALYSE DE L'EQUILIBRE:
  • Cluster le plus grand: {max((labels == l).sum() for l in set(labels))} points
  • Cluster le plus petit: {min((labels == l).sum() for l in set(labels))} points
  • Ratio max/min: {max((labels == l).sum() for l in set(labels)) / max(1, min((labels == l).sum() for l in set(labels))):.2f}
""")

if max((labels == l).sum() for l in set(labels)) / max(1, min((labels == l).sum() for l in set(labels))) < 3:
    print("  → Les clusters sont relativement equilibres! ✓")
else:
    print("  → Les clusters ont des tailles tres differentes.")
    print("    Cela peut indiquer des clusters de densites variees.")

print("\n" + "=" * 70)
print("4. STATISTIQUES PAR CLUSTER")
print("=" * 70)

df_with_labels = df.copy()
df_with_labels['cluster'] = labels

print("""
CENTRES DES CLUSTERS (coordonnees moyennes):
""")
cluster_stats = df_with_labels.groupby('cluster').agg({
    'x': ['mean', 'std'],
    'y': ['mean', 'std']
}).round(2)
display(cluster_stats, title="Statistiques par cluster")

print("""
INTERPRETATION:
  • 'mean' = centre du cluster (centroide)
  • 'std' = dispersion des points autour du centre
  • Un std faible = cluster compact
  • Un std eleve = cluster disperse
""")

print("\n" + "=" * 70)
print("              CLUSTERING HIERARCHIQUE APPLIQUE!")
print("=" * 70)


# Visualiser les clusters
# Type: Code executable
from sklearn.cluster import AgglomerativeClustering
from sklearn.preprocessing import StandardScaler

print("=" * 70)
print("       VISUALISATION DES CLUSTERS HIERARCHIQUES")
print("=" * 70)

print("""
Visualisons les resultats du clustering pour verifier que les
groupes identifies correspondent a la structure reelle des donnees.
""")

print("\n" + "=" * 70)
print("1. PREPARATION ET CLUSTERING")
print("=" * 70)

X = df[['x', 'y']].values
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

hc = AgglomerativeClustering(n_clusters=5, linkage='ward')
labels = hc.fit_predict(X_scaled)

print(f"""
Clustering effectue:
  • 5 clusters identifies
  • Methode de linkage: ward
""")

print("\n" + "=" * 70)
print("2. VISUALISATION PRINCIPALE")
print("=" * 70)

colors = ['#3498db', '#e74c3c', '#27ae60', '#9B7AC4', '#e67e22', '#F7E64D', '#1abc9c', '#34495e']

plt.figure(figsize=(12, 8))

for i in range(5):
    mask = labels == i
    plt.scatter(X[mask, 0], X[mask, 1],
               c=colors[i], s=60, alpha=0.7,
               label=f'Cluster {i} (n={mask.sum()})',
               edgecolors='white', linewidth=0.5)

    # Marquer le centre
    center_x = X[mask, 0].mean()
    center_y = X[mask, 1].mean()
    plt.scatter(center_x, center_y, c=colors[i], s=200, marker='X',
               edgecolors='black', linewidth=2)

plt.xlabel('X', fontsize=12)
plt.ylabel('Y', fontsize=12)
plt.title('Clustering Hierarchique (Ward, k=5)', fontsize=14, fontweight='bold')
plt.legend(loc='best', fontsize=10)
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()

print("""
LECTURE DU GRAPHIQUE:
  • Chaque couleur = un cluster different
  • X = centre (centroide) de chaque cluster
  • Les points proches ont le meme label

OBSERVATIONS:
  • Les clusters semblent bien separes visuellement
  • Le clustering hierarchique a capture la structure naturelle
  • Les centres (X) sont au coeur de chaque groupe
""")

print("\n" + "=" * 70)
print("3. VUE AVANT/APRES")
print("=" * 70)

fig, axes = plt.subplots(1, 2, figsize=(14, 6))

# Avant: donnees brutes
axes[0].scatter(X[:, 0], X[:, 1], c='#9B7AC4', s=40, alpha=0.6, edgecolors='white', linewidth=0.5)
axes[0].set_xlabel('X', fontsize=12)
axes[0].set_ylabel('Y', fontsize=12)
axes[0].set_title('Avant: Donnees brutes', fontsize=13, fontweight='bold')
axes[0].grid(True, alpha=0.3)

# Apres: clusters identifies
scatter = axes[1].scatter(X[:, 0], X[:, 1], c=labels, cmap='tab10', s=40, alpha=0.7, edgecolors='white', linewidth=0.5)
axes[1].set_xlabel('X', fontsize=12)
axes[1].set_ylabel('Y', fontsize=12)
axes[1].set_title('Apres: Clusters identifies', fontsize=13, fontweight='bold')
axes[1].grid(True, alpha=0.3)
plt.colorbar(scatter, ax=axes[1], label='Cluster')

plt.tight_layout()
plt.show()

print("""
COMPARAISON AVANT/APRES:
  • A gauche: tous les points ont la meme couleur
  • A droite: chaque cluster a sa propre couleur

Le clustering hierarchique a reussi a identifier les groupes naturels!
""")

print("\n" + "=" * 70)
print("              VISUALISATION TERMINEE!")
print("=" * 70)


# Methodes de linkage
# Type: Code executable
from sklearn.cluster import AgglomerativeClustering
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score

print("=" * 70)
print("       COMPARAISON DES METHODES DE LINKAGE")
print("=" * 70)

print("""
Le LINKAGE definit comment calculer la distance entre deux clusters.
Ce choix impacte fortement la forme des clusters obtenus!

METHODES DISPONIBLES:
  • WARD: Minimise la variance intra-cluster (clusters compacts)
  • COMPLETE: Distance max entre points des 2 clusters (evite chaines)
  • AVERAGE: Distance moyenne entre tous les points
  • SINGLE: Distance min entre points (peut creer des chaines)
""")

print("\n" + "=" * 70)
print("1. PREPARATION")
print("=" * 70)

X = df[['x', 'y']].values
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

print(f"Donnees: {X_scaled.shape[0]} points normalises")

print("\n" + "=" * 70)
print("2. APPLICATION DES 4 METHODES")
print("=" * 70)

linkages = ['ward', 'complete', 'average', 'single']
results = {}

print("""
Appliquons chaque methode avec k=5 clusters:
""")
print("-" * 60)
print(f"{'Methode':<12} {'Silhouette':<15} {'Distribution des clusters'}")
print("-" * 60)

for link in linkages:
    hc = AgglomerativeClustering(n_clusters=5, linkage=link)
    labels = hc.fit_predict(X_scaled)
    score = silhouette_score(X_scaled, labels)

    # Distribution
    dist = [f"{(labels == i).sum()}" for i in range(5)]
    dist_str = ", ".join(dist)

    results[link] = {'labels': labels, 'score': score}

    star = " ★ MEILLEUR" if link == 'ward' else ""
    print(f"{link:<12} {score:>10.3f}     [{dist_str}]{star}")

print("-" * 60)

best_method = max(results, key=lambda x: results[x]['score'])
print(f"\nMeilleure methode: {best_method} (Silhouette = {results[best_method]['score']:.3f})")

print("\n" + "=" * 70)
print("3. VISUALISATION COMPARATIVE")
print("=" * 70)

print("""
Visualisons les resultats de chaque methode:
""")

fig, axes = plt.subplots(2, 2, figsize=(14, 12))

for ax, link in zip(axes.flat, linkages):
    labels = results[link]['labels']
    score = results[link]['score']

    scatter = ax.scatter(X[:, 0], X[:, 1], c=labels, cmap='tab10', s=40, alpha=0.7, edgecolors='white', linewidth=0.5)
    ax.set_title(f'Linkage: {link.upper()}\nSilhouette: {score:.3f}', fontsize=12, fontweight='bold')
    ax.grid(True, alpha=0.3)
    ax.set_xlabel('X')
    ax.set_ylabel('Y')

plt.tight_layout()
plt.show()

print("""
ANALYSE DES RESULTATS:

WARD (recommande):
  • Clusters compacts et equilibres
  • Minimise la variance intra-cluster
  • Meilleur choix pour la plupart des cas

COMPLETE:
  • Evite les "chaines" de points
  • Clusters plus larges que ward
  • Bon pour eviter les clusters etires

AVERAGE:
  • Compromis entre single et complete
  • Resultat intermediaire
  • Robuste aux outliers

SINGLE:
  • Peut creer des clusters en forme de chaine
  • Sensible au bruit et outliers
  • Utile pour detecter des formes allongees
""")

print("\n" + "=" * 70)
print("GUIDE DE CHOIX DU LINKAGE:")
print("=" * 70)
print("""
┌─────────────────┬──────────────────────────────────────────┐
│ Situation       │ Methode recommandee                      │
├─────────────────┼──────────────────────────────────────────┤
│ Cas general     │ WARD (clusters spheriques)               │
│ Clusters etires │ SINGLE (peut creer des chaines)          │
│ Eviter chaines  │ COMPLETE ou AVERAGE                      │
│ Donnees bruitees│ AVERAGE (plus robuste)                   │
└─────────────────┴──────────────────────────────────────────┘
""")

print("\n" + "=" * 70)
print("              COMPARAISON DES LINKAGES TERMINEE!")
print("=" * 70)


# Exercice: Trouver le bon nombre de clusters
# Type: Exercice
# Exercice: Utilisez le dendrogramme pour trouver k optimal

from scipy.cluster.hierarchy import dendrogram, linkage
from sklearn.cluster import AgglomerativeClustering
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score

print("=" * 70)
print("       EXERCICE: TROUVER LE NOMBRE OPTIMAL DE CLUSTERS")
print("=" * 70)

print("""
OBJECTIF:
Utilisez le dendrogramme ET le silhouette score pour determiner
le nombre optimal de clusters pour ce dataset.

ETAPES A SUIVRE:
1. Tracer le dendrogramme et identifier les grands sauts
2. Tester differents k (de 2 a 8) et calculer le silhouette score
3. Choisir le k qui donne le meilleur equilibre
""")

# Preparez les donnees
X = df[['x', 'y']].values
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# TODO: Tracez le dendrogramme
# TODO: Identifiez le nombre de clusters optimal (grand saut)
# TODO: Appliquez le clustering avec ce k
# TODO: Calculez le silhouette score

print("""
VOTRE CODE ICI:
---------------
# Indice: utilisez linkage() et dendrogram() de scipy
# Puis AgglomerativeClustering de sklearn
# Et silhouette_score pour evaluer
""")


# Comparaison K-Means vs Hierarchique
# Type: Code executable
from sklearn.cluster import KMeans, AgglomerativeClustering
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score, calinski_harabasz_score

print("=" * 70)
print("       COMPARAISON: K-MEANS vs CLUSTERING HIERARCHIQUE")
print("=" * 70)

print("""
Les deux methodes les plus populaires de clustering sont K-Means et
le clustering hierarchique. Comparons-les sur notre dataset!

K-MEANS:
  ✓ Rapide (O(n))
  ✓ Donne les centres de clusters
  ✗ Necessite k a l'avance
  ✗ Sensible a l'initialisation

HIERARCHIQUE:
  ✓ Pas besoin de k a l'avance
  ✓ Dendrogramme informatif
  ✓ Deterministe (pas d'initialisation aleatoire)
  ✗ Lent (O(n²) a O(n³))
  ✗ Pas adapte aux grands datasets
""")

print("\n" + "=" * 70)
print("1. PREPARATION")
print("=" * 70)

X = df[['x', 'y']].values
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)
n_clusters = 5

print(f"""
Configuration:
  • Dataset: {X.shape[0]} points, {X.shape[1]} dimensions
  • Nombre de clusters: {n_clusters}
""")

print("\n" + "=" * 70)
print("2. APPLICATION DES DEUX ALGORITHMES")
print("=" * 70)

# K-Means
import time

start = time.time()
kmeans = KMeans(n_clusters=n_clusters, random_state=42, n_init=10)
labels_km = kmeans.fit_predict(X_scaled)
time_km = time.time() - start

# Hierarchique
start = time.time()
hc = AgglomerativeClustering(n_clusters=n_clusters, linkage='ward')
labels_hc = hc.fit_predict(X_scaled)
time_hc = time.time() - start

print(f"""
TEMPS D'EXECUTION:
  • K-Means: {time_km*1000:.2f} ms
  • Hierarchique: {time_hc*1000:.2f} ms
  • Ratio: K-Means est {time_hc/time_km:.1f}x plus rapide
""")

print("\n" + "=" * 70)
print("3. METRIQUES DE QUALITE")
print("=" * 70)

# Calculer les metriques
sil_km = silhouette_score(X_scaled, labels_km)
sil_hc = silhouette_score(X_scaled, labels_hc)
ch_km = calinski_harabasz_score(X_scaled, labels_km)
ch_hc = calinski_harabasz_score(X_scaled, labels_hc)

print("""
COMPARAISON DES METRIQUES:
""")
print("-" * 65)
print(f"{'Metrique':<25} {'K-Means':<18} {'Hierarchique':<18}")
print("-" * 65)
print(f"{'Silhouette Score':<25} {sil_km:<18.4f} {sil_hc:<18.4f}")
print(f"{'Calinski-Harabasz':<25} {ch_km:<18.1f} {ch_hc:<18.1f}")
print(f"{'Temps (ms)':<25} {time_km*1000:<18.2f} {time_hc*1000:<18.2f}")
print("-" * 65)

# Determine le gagnant
winner_sil = "K-Means" if sil_km > sil_hc else "Hierarchique" if sil_hc > sil_km else "Egalite"
winner_ch = "K-Means" if ch_km > ch_hc else "Hierarchique" if ch_hc > ch_km else "Egalite"

print(f"""
INTERPRETATION:
  • Silhouette: {winner_sil} est meilleur
    (mesure la coherence des clusters, plus haut = mieux)
  • Calinski-Harabasz: {winner_ch} est meilleur
    (ratio variance inter/intra, plus haut = mieux)
""")

print("\n" + "=" * 70)
print("4. VISUALISATION COMPARATIVE")
print("=" * 70)

fig, axes = plt.subplots(1, 2, figsize=(14, 6))

# K-Means
axes[0].scatter(X[:, 0], X[:, 1], c=labels_km, cmap='tab10', s=40, alpha=0.7, edgecolors='white', linewidth=0.5)
# Ajouter les centres K-Means (denormalises)
centers_original = kmeans.cluster_centers_ * scaler.scale_ + scaler.mean_
axes[0].scatter(centers_original[:, 0], centers_original[:, 1],
               c='red', marker='X', s=200, edgecolors='black', linewidth=2, label='Centres')
axes[0].set_title(f'K-Means\nSilhouette: {sil_km:.3f}', fontsize=12, fontweight='bold')
axes[0].set_xlabel('X')
axes[0].set_ylabel('Y')
axes[0].grid(True, alpha=0.3)
axes[0].legend()

# Hierarchique
axes[1].scatter(X[:, 0], X[:, 1], c=labels_hc, cmap='tab10', s=40, alpha=0.7, edgecolors='white', linewidth=0.5)
axes[1].set_title(f'Hierarchique (Ward)\nSilhouette: {sil_hc:.3f}', fontsize=12, fontweight='bold')
axes[1].set_xlabel('X')
axes[1].set_ylabel('Y')
axes[1].grid(True, alpha=0.3)

plt.tight_layout()
plt.show()

print("""
OBSERVATIONS VISUELLES:
  • Les deux methodes trouvent des clusters similaires
  • K-Means fournit des centres explicites (croix rouges)
  • Hierarchique donne des resultats deterministes
""")

print("\n" + "=" * 70)
print("5. CONCORDANCE DES LABELS")
print("=" * 70)

# Calculer la matrice de contingence
from collections import Counter

concordance = []
for i in range(n_clusters):
    for j in range(n_clusters):
        count = ((labels_km == i) & (labels_hc == j)).sum()
        if count > 0:
            concordance.append((i, j, count))

print("""
MATRICE DE CORRESPONDANCE K-Means / Hierarchique:
(combien de points en commun dans chaque paire de clusters)
""")

print("-" * 50)
print(f"{'K-Means':<10} {'Hierarchique':<15} {'Nb points'}")
print("-" * 50)
for km, hc, count in sorted(concordance, key=lambda x: -x[2])[:10]:
    bar = "█" * min(int(count/5), 30)
    print(f"{km:<10} {hc:<15} {count:<8} {bar}")
print("-" * 50)

# Calculer l'accord global (adjusted rand index approximatif)
max_match = sum(max((labels_km == i).sum() for i in range(n_clusters) if ((labels_km == i) & (labels_hc == j)).sum() == (labels_km == i).sum() or ((labels_km == i) & (labels_hc == j)).sum() == (labels_hc == j).sum()) for j in range(n_clusters))

print("""
QUAND UTILISER CHAQUE METHODE?
""")
print("┌" + "─" * 65 + "┐")
print("│" + " K-MEANS".ljust(65) + "│")
print("├" + "─" * 65 + "┤")
print("│" + " • Grands datasets (>10K points)".ljust(65) + "│")
print("│" + " • Besoin de rapidite".ljust(65) + "│")
print("│" + " • Clusters spheriques attendus".ljust(65) + "│")
print("│" + " • Besoin des centres de clusters".ljust(65) + "│")
print("└" + "─" * 65 + "┘")
print()
print("┌" + "─" * 65 + "┐")
print("│" + " HIERARCHIQUE".ljust(65) + "│")
print("├" + "─" * 65 + "┤")
print("│" + " • Petits/moyens datasets (<10K points)".ljust(65) + "│")
print("│" + " • Explorer la structure a plusieurs niveaux".ljust(65) + "│")
print("│" + " • Pas sur du nombre de clusters".ljust(65) + "│")
print("│" + " • Besoin de resultats deterministes".ljust(65) + "│")
print("└" + "─" * 65 + "┘")

print("\n" + "=" * 70)
print("              COMPARAISON TERMINEE!")
print("=" * 70)