Partie 4 – Clustering avec K-means et graphes avec GraphFrames

• 15h15 – 17h00
• Théorie 20 min · TP 8 45 min · partage et récap 30 min
• Slides 33 à 40

Et si les courses se rangeaient toutes seules en familles, sans qu'on leur dise lesquelles ? Si vous deviez ranger les 120 000 courses en 3 piles, quelles piles feriez-vous ?

K-means : regrouper sans étiquette

 1. Placer k centres au hasard
 2. Chaque point rejoint le centre le plus proche
 3. Chaque centre va au milieu de son groupe
 4. Répéter 2 et 3 jusqu'à stabilité

Au tableau, une dizaine de points et 2 centres : deux itérations suffisent pour comprendre.

Sur le fil rouge, avec distance, montant et heure normalisés, k = 3 :

Famille	Distance	Montant	Heure	Nom métier
Courtes du soir	≈ 2,2 mi	≈ 21 $	≈ 18 h	Trajets urbains de fin de journée
Courtes du matin	≈ 2,2 mi	≈ 21 $	≈ 9 h	Trajets urbains du matin
Longues / aéroport	≈ 14,1 mi	≈ 87 $	≈ 14 h	Aéroports et longues distances

Deux familles de courses courtes qui ne diffèrent que par l’heure, et une famille longue. C’est le métier qui nomme et juge les groupes, pas l’algorithme.

Choisir k : la silhouette

ClusteringEvaluator(metricName="silhouette") mesure à quel point chaque point est proche de son groupe plutôt que des autres (entre −1 et 1). Sur le fil rouge : 0,66 pour k = 3, 0,53 pour k = 6. On choisit k avec la silhouette et le sens métier : 3 familles nommables valent mieux que 6 illisibles.

Normaliser : StandardScaler

Sans normalisation, le montant (dizaines de dollars) écrase l’heure (0 à 23) et la distance (miles) dans la distance euclidienne : les 3 centres auraient tous une heure moyenne de 14 h, l’heure n’aurait joué aucun rôle. C’est l’étape 5 du TP 8.

Ne comparez pas des silhouettes avec et sans scaler

Elles sont calculées dans des espaces différents. Une silhouette plus haute sans normalisation ne veut pas dire « meilleur modèle ».

🧮 Calcul à la main : Pourquoi StandardScaler est obligatoire avant K-Means ? (La preuve par Pythagore)

K-Means regroupe deux courses si leur distance géométrique (Pythagore) est petite. Comparons trois courses décrites par (Montant en $, Heure de 0 à 23) sans normalisation :

• Course A : 20 $ à 8 h du matin
• Course B : 20 $ à 22 h le soir (14 heures d’écart !)
• Course C : 50 $ à 8 h du matin (même heure, 30 $ d’écart)

Calculons la distance au carré $\Delta\text{Montant}^2 + \Delta\text{Heure}^2$ :

• Distance entre A et B (matin vs soir, même prix) : $(20 - 20)^2 + (8 - 22)^2 = 0 + 196 =$ 196.
• Distance entre A et C (même heure, prix différent) : $(20 - 50)^2 + (8 - 8)^2 = 900 + 0 =$ 900 (presque 5× plus grand !).

Conséquence sans StandardScaler : comme les dollars vont de 0 à 200 $ alors que les heures vont de 0 à 23, l’écart en dollars écrase totalement l’écart en heures ! K-Means découpe uniquement par tranche de prix (pas cher / moyen / cher) et les 3 groupes ont tous la même heure moyenne (≈ 14 h). Avec StandardScaler(withMean=True, withStd=True), chaque variable est ramenée en « nombre d’écarts-types » (autour de $-2$ à $+2$) : l’heure et la distance pèsent enfin autant que le montant, et les deux familles « Courtes du matin (9 h) » et « Courtes du soir (18 h) » apparaissent immédiatement !

🔍 Vulgarisation : Comment fonctionne le score de Silhouette (entre −1 et +1) ?

Pour chaque course $i$, Spark calcule deux distances moyennes :

• $a(i)$ : la distance moyenne entre la course $i$ et toutes les autres courses de sa propre famille (mesure la cohésion : plus $a$ est petit, plus la famille est compacte).
• $b(i)$ : la distance moyenne entre la course $i$ et les courses de la famille voisine la plus proche (mesure la séparation : plus $b$ est grand, mieux les familles sont distinctes).

La formule de la silhouette est : $$\text{Silhouette} = \frac{b - a}{\max(a, b)}$$

• Proche de $+1$ ($a \ll b$) : chaque course est très proche de son groupe et très loin des autres groupes (excellent découpage).
• Proche de $0$ ($a \approx b$) : les groupes se chevauchent à la frontière.
• Négatif ($< 0$) : les courses ont été rangées dans la mauvaise famille !

KNN n’est pas K-means

	K-means	KNN (k plus proches voisins)
Type	Non supervisé (clustering)	Supervisé (classification ou régression)
k	Nombre de groupes	Nombre de voisins étiquetés consultés
Dans Spark MLlib	KMeans	Absent. On l’approche avec BucketedRandomProjectionLSH, ou on le fait en scikit-learn sur un échantillon

Confusion fréquente

K-means et KNN sont souvent présentés côte à côte dans les ressources d’introduction. Ce sont des algorithmes différents : K-means est non supervisé et disponible dans MLlib ; KNN est supervisé et absent de MLlib. Nous clarifions ce point parce qu’il revient régulièrement en entretien et dans les quiz techniques.

GraphFrames : les liens entre zones (démonstration)

        JFK ──────► Midtown ◄────── UES
         ▲             │  ▲
         │             ▼  │
        LGA ◄──── Times Sq ────► Brooklyn

 sommets = zones · arêtes = courses (départ → arrivée)

Notion	Dans GraphFrames
Sommets (vertices)	Un DataFrame avec une colonne id
Arêtes (edges)	Un DataFrame avec src et dst
inDegrees / outDegrees	Zones les plus desservies / les plus quittées
pageRank	Zones les plus « centrales »
Motifs	(a)-[]->(b); (b)-[]->(a) = allers-retours
Autres algorithmes	Plus courts chemins, composantes connexes, comptage de triangles

from graphframes import GraphFrame

v = zones.withColumnRenamed("LocationID", "id")
e = trips.select(F.col("PULocationID").alias("src"), F.col("DOLocationID").alias("dst"))
g = GraphFrame(v, e)
g.pageRank(resetProbability=0.15, maxIter=10).vertices.orderBy(F.desc("pagerank")).show(5)
g.inDegrees.orderBy(F.desc("inDegree")).show(5)

GraphFrames est le successeur de GraphX, qui ne fonctionne qu’en Scala sur des RDD. Il travaille sur des DataFrames, donc en Python aussi.

Package externe, à installer avant la session

GraphFrames n’est pas inclus dans Spark. Pour Spark 4 : pip install graphframes-py et le JAR io.graphframes:graphframes-spark4_2.13:<version> via spark.jars.packages. Vérifier la version compatible sur le dépôt GraphFrames avant la formation. Mode dégradé : calculer les degrés avec un simple groupBy("dst").count().

GraphFrames est présenté en démonstration : le formateur exécute le code en direct et les participants le refont en bonus du TP 8. Point à retenir : PageRank ≠ degré. Une zone peu fréquentée mais reliée à des zones centrales peut être bien classée.

🔍 Vulgarisation : Pourquoi PageRank est plus subtil qu'un simple comptage des arrivées (inDegree) ?

• inDegree (degré entrant) compte simplement : « Combien de courses se terminent dans cette zone ? » C’est un compteur de volume brut.
• PageRank (l’algorithme historique de Google adapté aux graphes dans Spark) ajoute une règle de qualité : « Une zone est importante si les courses qui y arrivent proviennent elles-mêmes de zones très importantes ! »
  • Exemple sur New York : une zone d’affaires ou un nœud de correspondance qui reçoit directement des navettes depuis JFK Airport et Midtown Center hérite d’une partie de leur prestige et obtient un PageRank élevé, même si son nombre total de courses est inférieur à celui d’un quartier résidentiel périphérique qui ne reçoit que de tout petits trajets locaux.

À vous de jouer

TP 8 – Les familles de courses (45 min) : K-means pour k de 2 à 6, silhouette, familles nommées avec des mots métier, et l’effet de StandardScaler.

Partage et remédiation

• Quel k avez-vous choisi, et pourquoi ? Silhouette et sens métier.
• Sans StandardScaler, l’heure n’a joué aucun rôle : pourquoi ? Le montant domine la distance euclidienne.
• À retenir : non supervisé = pas de bonne réponse. Le métier juge l’utilité des groupes.

Ce qu’il faut retenir de la journée

Faites reformuler chaque idée par un participant différent, puis reprenez les attentes du tour de table du jour 1 : lesquelles sont couvertes, lesquelles restent pour le jour 3 ?

	Idée	En une phrase
1	Supervisé ou non	Avec label : régression ou classification. Sans label : clustering.
2	Le Pipeline	Les Estimators apprennent (fit), les Transformers transforment. Un seul objet, sauvegardable.
3	Train / test	On juge un modèle sur des données jamais vues : RMSE, R², AUC selon le problème.
4	La fuite de données	Chaque feature doit être connue au moment de prédire.
5	Visualiser d’abord	Agréger dans Spark, tracer en pandas.

Ce soir : terminez le TP 8 si besoin, les corrigés sont sur le dépôt Git. Révisez avec la fiche mémo et les quiz 5 à 8.

Demain : nos taxis arrivent en temps réel. Les courses arrivent une par une, en direct : notre modèle de pourboire saura-t-il répondre à la volée ? Dernière étape de la journée : l’émargement.