La «malédiction de la dimension»

Exercice supplémentaire · niveau 3 (difficile) · NSI (première), chapitre 8 — Dichotomie, voisins et gloutons · Aux frontières

Énoncé

La « malédiction de la dimension ». Tirer des points au hasard dans le cube unité en dimension $1$ , $2$ , $10$ , $100$ , $1000$ , et regarder l'écart entre la plus petite et la plus grande distance, rapporté à la distance moyenne. Que devient la notion de « plus proche voisin » ?

Corrigé


def distances_moyennes(d, n=500):
    pts = [[random.random() for _ in range(d)] for _ in range(n)]
    ech = [distance(tuple(pts[i]), tuple(pts[j]))
           for i in range(0, n, 7) for j in range(i + 1, n, 11)]
    return min(ech), max(ech), sum(ech) / len(ech)

dimension	min	max	moyenne	$(max - min) / moy$
$1$	$0, 000$	$0, 95$	$0, 32$	$2, 96$
$2$	$0, 009$	$1, 28$	$0, 55$	$2, 34$
$10$	$0, 355$	$2, 06$	$1, 26$	$1, 35$
$100$	$3, 373$	$4, 85$	$4, 09$	$0, 36$
$1000$	$12, 121$	$13, 67$	$12, 90$	$0, 12$

En grande dimension, tous les points sont à peu près à la même distance les uns des autres. L'écart relatif s'effondre de $2, 96$ à $0, 12$ : en dimension mille, le voisin le plus proche est à $12, 1$ et le plus lointain à $13, 7$ — treize pour cent de différence. La notion de « plus proche » perd tout contenu : le premier voisin n'est plus significativement plus proche que le dernier.

La conséquence pour l'algorithme. Les $k$ plus proches voisins, qui reposent entièrement sur le fait que « proche » veut dire quelque chose, se dégradent quand le nombre de descripteurs augmente. Ajouter des colonnes à un jeu de données n'améliore donc pas mécaniquement la prédiction — au-delà d'un certain point, cela la détruit. C'est contre-intuitif, et c'est mesurable.

Pourquoi cela se produit. La distance est une somme de $d$ carrés ; en additionnant beaucoup de contributions aléatoires indépendantes, les écarts se compensent et la somme se concentre autour de sa moyenne. Le phénomène porte un nom en probabilités, et il sera revu bien plus tard — ici, on le constate.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.