"""
Module: DBSCAN
Categorie: Unsupervised
Difficulte: Intermediaire

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 DBSCAN")
print("=" * 70)

print("\n" + "=" * 70)
print("1. APERCU DU DATASET")
print("=" * 70)
print("""
DBSCAN est un algorithme de clustering BASE SUR LA DENSITE.
Il trouve des regions denses separees par des regions creuses.

Contrairement a K-Means, DBSCAN:
  • Ne necessite pas de specifier le nombre de clusters
  • Peut trouver des clusters de formes arbitraires
  • Detecte automatiquement les outliers (bruit)
""")
display(df.head(10), title="Dataset de Clustering")

print(f"\n  Dimensions du dataset:")
print(f"    • {df.shape[0]} points")
print(f"    • {df.shape[1]} features (x, y)")

print("\n" + "=" * 70)
print("2. STATISTIQUES DE BASE")
print("=" * 70)
print(f"\n{'Feature':<10} | {'Min':^10} | {'Max':^10} | {'Moyenne':^10} | {'Std':^10}")
print("-" * 55)
for col in ['x', 'y']:
    print(f"{col:<10} | {df[col].min():^10.2f} | {df[col].max():^10.2f} | {df[col].mean():^10.2f} | {df[col].std():^10.2f}")

print("\n" + "=" * 70)
print("3. VISUALISATION INITIALE")
print("=" * 70)
print("""
Regardons les donnees sans aucun clustering.
Y voyez-vous des groupes? Des points isoles?
""")

plt.figure(figsize=(10, 6))
plt.scatter(df['x'], df['y'], alpha=0.6, color='#9B7AC4', s=40, edgecolors='black')
plt.xlabel('X')
plt.ylabel('Y')
plt.title('Donnees de Clustering (structure a decouvrir)')
plt.grid(True, alpha=0.3)
plt.show()

print("""
Questions a se poser:
  • Combien de groupes distincts voyez-vous?
  • Y a-t-il des points isoles (outliers potentiels)?
  • Les groupes sont-ils spheriques ou de formes irregulieres?

DBSCAN va repondre a toutes ces questions automatiquement!
""")


# Appliquer DBSCAN
# Type: Code executable
from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler

print("=" * 70)
print("         APPLICATION DE DBSCAN")
print("=" * 70)

# Preparer les donnees
X = df[['x', 'y']].values

print("\n" + "=" * 70)
print("1. NORMALISATION DES DONNEES")
print("=" * 70)
print("""
IMPORTANT: Le parametre eps est une DISTANCE.
Si les features ont des echelles differentes, la normalisation
est cruciale pour que eps ait un sens coherent.
""")

scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

print(f"  Avant normalisation: X dans [{X[:, 0].min():.1f}, {X[:, 0].max():.1f}]")
print(f"  Apres normalisation: X dans [{X_scaled[:, 0].min():.2f}, {X_scaled[:, 0].max():.2f}]")

print("\n" + "=" * 70)
print("2. CONFIGURATION DE DBSCAN")
print("=" * 70)
print("""
Les deux parametres cles de DBSCAN:

• eps (epsilon): Rayon de voisinage
  - Trop petit → trop de clusters et d'outliers
  - Trop grand → tous les points dans un seul cluster

• min_samples: Minimum de points pour former un core point
  - Trop petit → sensible au bruit
  - Trop grand → trop d'outliers

Parametres choisis pour cette demonstration:
""")
eps_val = 0.5
min_samples_val = 5
print(f"    • eps = {eps_val}")
print(f"    • min_samples = {min_samples_val}")

print("\n" + "=" * 70)
print("3. EXECUTION DE DBSCAN")
print("=" * 70)

import time
start = time.time()

dbscan = DBSCAN(eps=eps_val, min_samples=min_samples_val)
labels = dbscan.fit_predict(X_scaled)

exec_time = (time.time() - start) * 1000

print(f"  DBSCAN execute en {exec_time:.2f} ms")

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

n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
n_noise = (labels == -1).sum()

print(f"""
RESULTATS:
  • Nombre de clusters trouves: {n_clusters}
  • Points identifies comme bruit (outliers): {n_noise} ({n_noise/len(X)*100:.1f}%)
  • Points dans des clusters: {len(X) - n_noise} ({(len(X) - n_noise)/len(X)*100:.1f}%)
""")

print("\n  Distribution des labels:")
print("  " + "-" * 40)
for label in sorted(set(labels)):
    count = (labels == label).sum()
    pct = count / len(labels) * 100
    name = "Bruit (outliers)" if label == -1 else f"Cluster {label}"
    bar = "█" * int(pct / 3)
    print(f"    {name:<18}: {count:4d} ({pct:5.1f}%)  {bar}")

print("\n" + "=" * 70)
print("INTERPRETATION")
print("=" * 70)
print(f"""
DBSCAN a trouve {n_clusters} clusters AUTOMATIQUEMENT!

Labels speciaux:
  • -1 = BRUIT (point isole, outlier)
  • 0, 1, 2, ... = Numeros de clusters

Avantage majeur: DBSCAN n'a pas besoin qu'on lui dise
combien de clusters chercher - il les decouvre!
""")


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

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

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

# DBSCAN
dbscan = DBSCAN(eps=0.5, min_samples=5)
labels = dbscan.fit_predict(X_scaled)

n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
n_noise = (labels == -1).sum()

print(f"\n  Clusters trouves: {n_clusters}")
print(f"  Outliers detectes: {n_noise}")

# Visualisation
fig, axes = plt.subplots(1, 2, figsize=(14, 5))

# Plot 1: Donnees originales
axes[0].scatter(X[:, 0], X[:, 1], c='#9B7AC4', alpha=0.6, s=40, edgecolors='black')
axes[0].set_xlabel('X')
axes[0].set_ylabel('Y')
axes[0].set_title('Donnees AVANT clustering')
axes[0].grid(True, alpha=0.3)

# Plot 2: Clusters DBSCAN
unique_labels = set(labels)
colors = plt.cm.tab10(np.linspace(0, 1, 10))

for label in unique_labels:
    if label == -1:
        # Outliers en gris avec marqueur X
        mask = labels == label
        axes[1].scatter(X[mask, 0], X[mask, 1], c='gray', marker='x',
                   s=50, alpha=0.7, label='Bruit (outliers)')
    else:
        mask = labels == label
        color = colors[label % len(colors)]
        axes[1].scatter(X[mask, 0], X[mask, 1], c=[color], s=50,
                   alpha=0.7, edgecolors='black', label=f'Cluster {label}')

axes[1].set_xlabel('X')
axes[1].set_ylabel('Y')
axes[1].set_title(f'DBSCAN: {n_clusters} clusters, {n_noise} outliers')
axes[1].legend(loc='best', fontsize=8)
axes[1].grid(True, alpha=0.3)

plt.tight_layout()
plt.show()

print("\n" + "=" * 70)
print("INTERPRETATION")
print("=" * 70)
print(f"""
GRAPHIQUE DE GAUCHE:
  → Donnees brutes sans structure apparente

GRAPHIQUE DE DROITE:
  → DBSCAN a trouve {n_clusters} clusters distincts
  → Les X gris sont des outliers (points isoles)

CE QUE DBSCAN A DECOUVERT:
  • Regions denses = clusters (couleurs)
  • Points isoles = bruit (gris X)
  • Pas de forme imposee aux clusters!
""")

# Statistiques par cluster
print("\n" + "=" * 70)
print("STATISTIQUES PAR CLUSTER")
print("=" * 70)
print(f"\n{'Cluster':<15} | {'Points':^8} | {'X moyen':^10} | {'Y moyen':^10}")
print("-" * 50)
for label in sorted(set(labels)):
    mask = labels == label
    name = "Bruit" if label == -1 else f"Cluster {label}"
    count = mask.sum()
    x_mean = X[mask, 0].mean()
    y_mean = X[mask, 1].mean()
    print(f"{name:<15} | {count:^8} | {x_mean:^10.2f} | {y_mean:^10.2f}")


# Comparer avec K-Means
# Type: Code executable
from sklearn.cluster import DBSCAN, KMeans
from sklearn.preprocessing import StandardScaler

print("=" * 70)
print("    COMPARAISON: K-MEANS vs DBSCAN")
print("=" * 70)
print("""
K-Means et DBSCAN ont des philosophies TRES differentes:

K-MEANS:
  • Vous choisissez k (nombre de clusters)
  • Clusters spheriques de taille similaire
  • Tous les points sont assignes a un cluster
  • Sensible aux outliers (ils "tirent" les centroides)

DBSCAN:
  • Trouve k automatiquement
  • Clusters de formes arbitraires
  • Detecte les outliers (bruit)
  • Robuste aux anomalies
""")

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

# DBSCAN
dbscan = DBSCAN(eps=0.5, min_samples=5)
labels_dbscan = dbscan.fit_predict(X_scaled)
n_clusters_dbscan = len(set(labels_dbscan)) - (1 if -1 in labels_dbscan else 0)

# K-Means (utilisons le meme nombre de clusters que DBSCAN a trouve)
kmeans = KMeans(n_clusters=max(n_clusters_dbscan, 2), random_state=42, n_init=10)
labels_kmeans = kmeans.fit_predict(X_scaled)

print(f"\n  DBSCAN a trouve {n_clusters_dbscan} clusters")
print(f"  K-Means configure avec k={max(n_clusters_dbscan, 2)} clusters")

# Visualisation cote a cote
fig, axes = plt.subplots(1, 2, figsize=(14, 5))

# K-Means
scatter_km = axes[0].scatter(X[:, 0], X[:, 1], c=labels_kmeans, cmap='tab10', s=40, alpha=0.7, edgecolors='black')
# Ajouter les centroides
centers = scaler.inverse_transform(kmeans.cluster_centers_)
axes[0].scatter(centers[:, 0], centers[:, 1], c='red', marker='*', s=200, edgecolors='black', label='Centroides')
axes[0].set_title(f'K-Means (k={max(n_clusters_dbscan, 2)})')
axes[0].set_xlabel('X')
axes[0].set_ylabel('Y')
axes[0].legend()
axes[0].grid(True, alpha=0.3)

# DBSCAN
unique_labels = set(labels_dbscan)
colors = plt.cm.tab10(np.linspace(0, 1, 10))
for label in unique_labels:
    mask = labels_dbscan == label
    if label == -1:
        axes[1].scatter(X[mask, 0], X[mask, 1], c='gray', marker='x', s=50, alpha=0.7, label='Outliers')
    else:
        axes[1].scatter(X[mask, 0], X[mask, 1], c=[colors[label % 10]], s=40, alpha=0.7, edgecolors='black')

n_outliers = (labels_dbscan == -1).sum()
axes[1].set_title(f'DBSCAN ({n_clusters_dbscan} clusters, {n_outliers} outliers)')
axes[1].set_xlabel('X')
axes[1].set_ylabel('Y')
if n_outliers > 0:
    axes[1].legend()
axes[1].grid(True, alpha=0.3)

plt.tight_layout()
plt.show()

print("\n" + "=" * 70)
print("ANALYSE COMPARATIVE")
print("=" * 70)
print(f"""
K-MEANS:
  • Tous les {len(X)} points sont dans un cluster
  • Les centroides (etoiles rouges) sont les centres
  • Force des frontieres spheriques

DBSCAN:
  • {len(X) - n_outliers} points dans des clusters
  • {n_outliers} points identifies comme BRUIT
  • Pas de forme imposee

QUAND UTILISER QUOI?
  • K-Means: clusters bien separes, pas d'outliers, k connu
  • DBSCAN: formes arbitraires, detection d'anomalies, k inconnu
""")


# Tuner eps et min_samples
# Type: Code executable
from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import NearestNeighbors

print("=" * 70)
print("    COMMENT CHOISIR eps ET min_samples")
print("=" * 70)
print("""
Les parametres de DBSCAN sont cruciaux:

eps (epsilon):
  → Definit le rayon de voisinage
  → Trop petit: trop de clusters, trop d'outliers
  → Trop grand: un seul gros cluster

min_samples:
  → Minimum de points pour etre un core point
  → Trop petit: sensible au bruit
  → Trop grand: trop d'outliers
  → Recommandation: 2 * n_features (ici 2*2 = 4)
""")

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

print("\n" + "=" * 70)
print("1. METHODE DU COUDE POUR CHOISIR eps")
print("=" * 70)
print("""
Idee: tracer la distance au k-ieme plus proche voisin
pour chaque point, puis trouver le "coude".
""")

# Methode du coude pour trouver eps
k = 5  # min_samples
nn = NearestNeighbors(n_neighbors=k)
nn.fit(X_scaled)
distances, _ = nn.kneighbors(X_scaled)

# Distance au k-ieme voisin, triee
k_distances = np.sort(distances[:, k-1])

# Visualisation
plt.figure(figsize=(10, 5))
plt.plot(k_distances, color='#9B7AC4', linewidth=2)
plt.xlabel('Points (tries par distance)')
plt.ylabel(f'Distance au {k}-eme voisin')
plt.title('Methode du coude pour choisir eps')
plt.grid(True, alpha=0.3)

# Marquer des eps potentiels
for eps_test in [0.3, 0.5, 0.7]:
    idx = np.searchsorted(k_distances, eps_test)
    pct_noise = (len(k_distances) - idx) / len(k_distances) * 100
    plt.axhline(y=eps_test, linestyle='--', alpha=0.5,
               label=f'eps={eps_test} (~{pct_noise:.0f}% bruit)')

plt.legend()
plt.show()

print("""
INTERPRETATION DU GRAPHIQUE:
  • La courbe monte progressivement puis accelere
  • Le "coude" indique une bonne valeur pour eps
  • Points AVANT le coude = dans des clusters
  • Points APRES le coude = outliers potentiels
""")

# Recommandation basee sur la courbe
# Trouver le coude (point d'inflexion)
second_derivative = np.diff(np.diff(k_distances))
knee_idx = np.argmax(second_derivative) + 2
recommended_eps = k_distances[knee_idx]

print(f"\n  eps recommande (coude automatique): {recommended_eps:.2f}")
print(f"  min_samples recommande: {k} (2 * n_features)")

print("\n" + "=" * 70)
print("2. TEST DE DIFFERENTS eps")
print("=" * 70)

eps_to_test = [0.3, 0.5, 0.7, 1.0]
results = []

print(f"\n{'eps':^6} | {'Clusters':^10} | {'Outliers':^10} | {'% Bruit':^10}")
print("-" * 45)

for eps in eps_to_test:
    dbscan = DBSCAN(eps=eps, min_samples=k)
    labels = dbscan.fit_predict(X_scaled)
    n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
    n_noise = (labels == -1).sum()
    pct_noise = n_noise / len(X) * 100

    results.append({'eps': eps, 'clusters': n_clusters, 'noise': n_noise, 'pct': pct_noise})
    print(f"{eps:^6.1f} | {n_clusters:^10} | {n_noise:^10} | {pct_noise:^10.1f}")

print("-" * 45)

print(f"""
OBSERVATIONS:
  • eps petit (0.3): beaucoup de clusters et d'outliers
  • eps grand (1.0): peu de clusters, tout est regroupe
  • eps optimal: equilibre entre separation et bruit
""")


# Impact des parametres
# Type: Code executable
from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler

print("=" * 70)
print("    IMPACT VISUEL DES PARAMETRES")
print("=" * 70)
print("""
Voyons comment eps et min_samples affectent les resultats.
""")

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

# Grille de parametres
eps_values = [0.3, 0.5, 0.8]
min_samples_values = [3, 5, 10]

fig, axes = plt.subplots(3, 3, figsize=(15, 12))

for i, eps in enumerate(eps_values):
    for j, min_samples in enumerate(min_samples_values):
        ax = axes[i, j]

        dbscan = DBSCAN(eps=eps, min_samples=min_samples)
        labels = dbscan.fit_predict(X_scaled)

        n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
        n_noise = (labels == -1).sum()

        # Colorier
        unique_labels = set(labels)
        colors = plt.cm.tab10(np.linspace(0, 1, 10))

        for label in unique_labels:
            mask = labels == label
            if label == -1:
                ax.scatter(X[mask, 0], X[mask, 1], c='gray', marker='x', s=20, alpha=0.5)
            else:
                ax.scatter(X[mask, 0], X[mask, 1], c=[colors[label % 10]], s=20, alpha=0.7)

        ax.set_title(f'eps={eps}, min={min_samples}\n{n_clusters} clusters, {n_noise} outliers', fontsize=9)
        ax.set_xticks([])
        ax.set_yticks([])

# Labels des axes
for i, eps in enumerate(eps_values):
    axes[i, 0].set_ylabel(f'eps={eps}', fontsize=12)
for j, ms in enumerate(min_samples_values):
    axes[2, j].set_xlabel(f'min_samples={ms}', fontsize=12)

plt.suptitle('Impact de eps et min_samples sur DBSCAN', fontsize=14, y=1.02)
plt.tight_layout()
plt.show()

print("\n" + "=" * 70)
print("ANALYSE DE LA GRILLE")
print("=" * 70)
print("""
EFFET DE eps (lignes, haut → bas):
  • eps petit (0.3): beaucoup de petits clusters, beaucoup d'outliers
  • eps moyen (0.5): equilibre
  • eps grand (0.8): peu de clusters, points regroupes

EFFET DE min_samples (colonnes, gauche → droite):
  • min_samples petit (3): peu strict, peu d'outliers
  • min_samples moyen (5): equilibre
  • min_samples grand (10): strict, beaucoup d'outliers

RECOMMANDATIONS:
  • Commencer avec min_samples = 2 * n_features
  • Utiliser la methode du coude pour eps
  • Ajuster iterativement selon le resultat
""")


# Exercice: Detection d'outliers
# Type: Exercice
# Exercice: Utilisez DBSCAN pour detecter les anomalies

from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler

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

# TODO: Trouvez les parametres qui detectent environ 5-10% d'outliers
# TODO: Visualisez les outliers
# TODO: Affichez les coordonnees des outliers


# Metriques de clustering
# Type: Code executable
from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score, calinski_harabasz_score

print("=" * 70)
print("    EVALUATION DE LA QUALITE DU CLUSTERING")
print("=" * 70)
print("""
Comment savoir si notre clustering DBSCAN est bon?
Plusieurs metriques peuvent nous aider.
""")

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

# DBSCAN
dbscan = DBSCAN(eps=0.5, min_samples=5)
labels = dbscan.fit_predict(X_scaled)

n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
n_outliers = (labels == -1).sum()

print("\n" + "=" * 70)
print("1. RESUME DU CLUSTERING")
print("=" * 70)
print(f"""
Parametres: eps=0.5, min_samples=5

Resultats:
  • Clusters trouves: {n_clusters}
  • Outliers: {n_outliers} ({n_outliers/len(X)*100:.1f}%)
  • Points dans clusters: {len(X) - n_outliers}
""")

print("\n" + "=" * 70)
print("2. SILHOUETTE SCORE")
print("=" * 70)
print("""
Le Silhouette Score mesure:
  • Cohesion: les points sont-ils proches de leur cluster?
  • Separation: les clusters sont-ils eloignes les uns des autres?

Plage: [-1, 1]
  • 1: clusters parfaitement separes
  • 0: clusters qui se chevauchent
  • -1: points mal assignes
""")

# Calculer le silhouette score (exclure les outliers)
mask = labels != -1
if len(set(labels[mask])) > 1:
    sil_score = silhouette_score(X_scaled[mask], labels[mask])
    print(f"\n  Silhouette Score: {sil_score:.3f}")

    if sil_score > 0.5:
        interpretation = "Excellent! Clusters bien definis"
    elif sil_score > 0.25:
        interpretation = "Bon. Clusters raisonnables"
    else:
        interpretation = "Faible. Clusters peu distincts"

    print(f"  Interpretation: {interpretation}")
else:
    print("\n  Pas assez de clusters pour calculer le Silhouette Score")

print("\n" + "=" * 70)
print("3. CALINSKI-HARABASZ INDEX")
print("=" * 70)
print("""
Aussi appele Variance Ratio Criterion.
Plus eleve = meilleur clustering.
""")

if len(set(labels[mask])) > 1:
    ch_score = calinski_harabasz_score(X_scaled[mask], labels[mask])
    print(f"\n  Calinski-Harabasz Index: {ch_score:.2f}")
    print("  (Plus eleve = meilleur)")

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

print(f"\n{'Cluster':<12} | {'Points':^8} | {'Densite':^10} | {'Compacite':^12}")
print("-" * 50)

for label in sorted(set(labels)):
    if label == -1:
        continue

    mask_cluster = labels == label
    points_in_cluster = X_scaled[mask_cluster]
    n_points = len(points_in_cluster)

    # Densite: nombre de points / aire (approximative)
    if n_points > 1:
        centroid = points_in_cluster.mean(axis=0)
        distances = np.sqrt(((points_in_cluster - centroid)**2).sum(axis=1))
        avg_dist = distances.mean()
        compacity = f"{avg_dist:.3f}"
    else:
        compacity = "N/A"

    print(f"Cluster {label:<4} | {n_points:^8} | {'dense':^10} | {compacity:^12}")

print(f"{'Bruit':<12} | {n_outliers:^8} | {'sparse':^10} | {'N/A':^12}")

print("\n" + "=" * 70)
print("CONCLUSION")
print("=" * 70)
print(f"""
RESUME DE L'EVALUATION:

DBSCAN a trouve {n_clusters} clusters avec {n_outliers} outliers.

Pour ameliorer:
  • Si trop d'outliers: augmenter eps ou diminuer min_samples
  • Si pas assez de clusters: diminuer eps
  • Si clusters mal definis: ajuster les deux parametres

N'oubliez pas: DBSCAN est concu pour trouver des clusters
de formes arbitraires ET detecter les anomalies!
""")