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 ».

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.

À 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.