Méthodes non paramétriques comme K-Nearest-Neighbors dans l'espace d'entités de haute dimension

L'idée principale de k-voisin le plus proche prend en compte les points les plus proches et décide de la classification des données par vote majoritaire. Si tel est le cas, il ne devrait pas avoir de problèmes dans les données de dimension supérieure, car des méthodes telles que le hachage sensible à la localité peuvent trouver efficacement les voisins les plus proches. $k$

De plus, la sélection des fonctionnalités avec les réseaux bayésiens peut réduire la dimension des données et faciliter l'apprentissage.

Cependant, cet article de revue de John Lafferty dans l'apprentissage statistique souligne que l'apprentissage non paramétrique dans des espaces d'entités de haute dimension est toujours un défi et non résolu.

Qu'est-ce qui ne va pas?

machine-learning artificial-intelligence Strin
la source

Veuillez donner une référence complète pour le document; les auteurs ne semblent pas figurer (bien en vue) dans le it.

Raphael

Réponses:

Ce problème est connu sous le nom de malédiction de la dimensionnalité . Au fond, comme vous augmentez le nombre de dimensions, , les points dans l'espace ont généralement tendance à devenir de loin tous les autres points. Cela rend le partitionnement de l'espace (tel que nécessaire pour la classification ou le clustering) très difficile. $d$

Vous pouvez le constater très facilement par vous-même. J'ai généré points aléatoires de dimension dans l'hypercube d'unité à 20 valeurs uniformément sélectionnées de de 1 à . Pour chaque valeur de j'ai calculé la distance entre le premier point et tous les autres et j'ai pris la moyenne de ces distances. En traçant cela, nous pouvons voir que la distance moyenne augmente avec la dimensionnalité même si l'espace dans lequel nous générons les points dans chaque dimension reste le même. $50$ $d$ $d$ $1..1000$ $d$

Distance moyenne vs dimensionnalité

pseudo
la source

Bien sûr. Vous augmentez le nombre de points dans une hypersphère de rayon fixe de façon exponentielle dans la dimension, donc si vous choisissez 50 points uniformément au hasard, cela doit se produire. Par conséquent, si votre raisonnement est correct, le partitionnement devrait devenir facile si j'ai de nombreux échantillons; est-ce vrai?

Raphael

Je crois que vous l'avez inversé. En augmentant la dimensionnalité, JE RÉDUIT le nombre de points dans une hypersphère. Le partitionnement devient plus difficile parce que la mesure de la distance perd essentiellement son sens (par exemple, tout est loin).

Nick

Je voulais dire: Le nombre total de points dans une hypersphère de rayon dans disons , c'est-à-direaugmente avec .

k

$k$

N^{n}

$\mathbb{N}^n$

| N^{n} \cap S_{n} (k) |

$|\mathbb{N}^n \cap S_n(k)|$

n

$n$

Raphael

Notez également que ce que les gens veulent dire lorsqu'ils se réfèrent à un espace d'entités de grande dimension est que le nombre d'échantillons, , est beaucoup moins que la dimensionnalité de chaque point, , ( ). Donc, dans ces problèmes, vous supposez que vous n'avez PAS «beaucoup d'échantillons».

n

$n$

d

$d$

n << d

$n << d$

Nick

Je ne vois pas que cela soit valable par définition; il semble cependant que ce soit une convention basée sur l'expérience.

Raphael

Pas une réponse complète, mais la page wikipedia que vous avez citée dit:

La précision de l'algorithme k-NN peut être gravement dégradée par la présence de caractéristiques bruyantes ou non pertinentes, ou si les échelles de caractéristiques ne sont pas cohérentes avec leur importance.

La probabilité que cela se produise augmente en présence d'espaces caractéristiques de grande dimension.

Dave Clarke
la source

Mais je pense qu'avec PCA (analyse des composants principaux) ou toute autre méthode pour réduire la dimensionnalité et supprimer les données non pertinentes, k-NN peut toujours fonctionner. Et ce que les pages wikipedia signifient, c'est que le k-NN naïf échouera. Cela n'explique donc pas le document de synthèse.

Strin

L'ACP peut certainement fonctionner, mais pas dans toutes les situations.

Dave Clarke