Les plus proches voisins dans les données hautement dimensionnelles ?

Question

J'ai demandé à un question il y a quelques jours sur la façon de trouver les plus proches voisins d'un vecteur donné. Mon vecteur a maintenant 21 dimensions et avant de poursuivre, parce que je ne suis pas du domaine de l'apprentissage automatique ni des mathématiques, je commence à me poser quelques questions fondamentales :

• La distance euclidienne est-elle une bonne métrique pour trouver les plus proches voisins en premier lieu ? Si non, quelles sont mes options ?
• En outre, comment décider du bon seuil pour déterminer les k-voisins ? Peut-on effectuer une analyse pour déterminer cette valeur ?
• Auparavant, on m'avait suggéré d'utiliser les kd-Trees, mais la page Wikipedia indique clairement que pour les hautes dimensions, les kd-Trees sont presque équivalents à une recherche par force brute. Dans ce cas, quelle est la meilleure façon de trouver efficacement les plus proches voisins dans un ensemble de données d'un million de points ?

Quelqu'un peut-il clarifier certaines (ou toutes) des questions ci-dessus ?

Answer 1

J'étudie actuellement de tels problèmes - classification, recherche du plus proche voisin - pour la recherche d'informations musicales.

Vous pourriez être intéressé par Proche voisin approximatif ( ANN ) algorithmes. L'idée est que vous permettez à l'algorithme de retourner suffisamment voisins proches (peut-être pas le plus proche voisin) ; ce faisant, vous réduisez la complexité. Vous avez mentionné le kd-tree c'est un exemple. Mais comme vous l'avez dit, kd-tree fonctionne mal en haute dimension. En effet, tous Les techniques d'indexation actuelles (basées sur le partitionnement de l'espace) se dégradent en recherche linéaire pour des dimensions suffisamment élevées [1][2][3].

Parmi ANN algorithmes proposés récemment, dont le plus populaire est peut-être Hachage sensible à la localité ( LSH ), qui fait correspondre un ensemble de points dans un espace à haute dimension à un ensemble de cases, c'est-à-dire à une table de hachage [1][3]. Mais contrairement aux hachages traditionnels, une sensible à la localité places de hachage à proximité de dans le même bac.

LSH présente d'énormes avantages. Tout d'abord, il est simple. Il suffit de calculer le hachage de tous les points de votre base de données, puis de créer une table de hachage à partir de ces points. Pour effectuer une requête, il suffit de calculer le hachage du point de la requête, puis de récupérer tous les points dans le même emplacement dans la table de hachage.

Deuxièmement, il existe une théorie rigoureuse qui soutient ses performances. On peut montrer que le temps d'interrogation est de sublinéaire dans la taille de la base de données, c'est-à-dire plus rapide que la recherche linéaire. Le degré de rapidité dépend du degré d'approximation que l'on peut tolérer.

Enfin, LSH est compatible avec toute norme Lp pour 0 < p <= 2 . Par conséquent, pour répondre à votre première question, vous pouvez utiliser LSH avec la métrique de la distance euclidienne, ou vous pouvez l'utiliser avec la métrique de la distance de Manhattan (L1). Il existe également des variantes pour la distance de Hamming et la similarité en cosinus.

Une bonne vue d'ensemble a été rédigée par Malcolm Slaney et Michael Casey pour IEEE Signal Processing Magazine en 2008 [4].

LSH a été appliquée apparemment partout. Vous pourriez vouloir l'essayer.

---

[1] Datar, Indyk, Immorlica, Mirrokni, "Locality-Sensitive Hashing Scheme Based on p-Stable Distributions," 2004.

[2] Weber, Schek, Blott, "A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces", 1998.

[3] Gionis, Indyk, Motwani, "Similarity search in high dimensions via hashing," 1999.

[4] Slaney, Casey, "Locality-sensitive hashing for finding nearest neighbors", 2008.

Answer 2

I. La métrique de la distance

Tout d'abord, le nombre de caractéristiques (colonnes) dans un ensemble de données n'est pas un facteur dans la sélection d'une métrique de distance à utiliser dans kNN. Il existe un grand nombre d'études publiées portant précisément sur cette question, et les bases habituelles de comparaison sont les suivantes :

• la distribution statistique sous-jacente distribution de vos données ;

• la relation entre les caractéristiques qui composent vos données (sont-elles indépendantes - c'est-à-dire, à quoi ressemble la matrice de covariance) ; et

• l'espace de coordonnées à partir duquel vos données ont été obtenues.

Si vous n'avez aucune connaissance préalable de la (des) distribution(s) à partir de laquelle (desquelles) vos données ont été échantillonnées, au moins un (bien documenté et approfondi) étude conclut que la distance euclidienne est le meilleur choix.

Métrique YEuclidienne utilisée dans les moteurs de recommandation Web à grande échelle ainsi que dans la recherche universitaire actuelle. Les distances calculées par la métrique euclidienne ont une signification intuitive et le calcul est échelonné - c'est-à-dire que la distance euclidienne est calculée de la même manière, que les deux points soient dans un espace à deux dimensions ou à vingt-deux dimensions.

Il n'a échoué pour moi qu'à quelques reprises, à chaque fois la distance euclidienne a échoué parce que le système de coordonnées (cartésien) sous-jacent était un mauvais choix. Et vous vous en rendrez généralement compte parce que, par exemple, les longueurs de chemin (distances) ne sont plus additives - par exemple, lorsque l'espace métrique est un échiquier, la distance de Manhattan est meilleure que la distance euclidienne, de même lorsque l'espace métrique est la Terre et que vos distances sont des vols transcontinentaux, une métrique de distance adaptée à un système de coordonnées polaires est une bonne idée (par exemple, Londres à Vienne est 2,5 heures, Vienne à Saint-Pétersbourg est 3 heures de plus, plus ou moins dans la même direction, mais Londres à Saint-Pétersbourg n'est pas 5,5 heures, mais un peu plus de 3 heures).

Mais en dehors des cas où vos données appartiennent à un système de coordonnées non cartésien, le choix de la métrique de distance n'est généralement pas important. (Voir cette article de blog d'un étudiant en informatique, comparant plusieurs mesures de distance en examinant leur effet sur le classificateur kNN - le carré de chi donne les meilleurs résultats, mais les différences ne sont pas importantes ; une étude plus complète se trouve dans l'article universitaire, Étude comparative des fonctions de distance pour les plus proches voisins --Mahalanobis (essentiellement Euclidien normalisé par pour tenir compte de la covariance des dimensions) était le meilleur dans cette étude.

Une réserve importante : pour que les calculs de la distance métrique soient significatifs, vous devez redimensionner vos données - il est rarement possible de construire un modèle kNN pour générer des prédictions précises sans faire cela. Par exemple, si vous construisez un modèle kNN pour prédire les performances athlétiques, et que vos variables d'attente sont la taille (cm), le poids (kg), la graisse corporelle (%) et le pouls au repos (battements par minute), alors un point de données typique pourrait ressembler à ceci : [ 180.4, 66.1, 11.3, 71 ]. Il est clair que le calcul de la distance sera dominé par la taille, tandis que la contribution du pourcentage de graisse corporelle sera presque négligeable. En d'autres termes, si les données étaient rapportées différemment, de manière à ce que le poids corporel soit exprimé en grammes plutôt qu'en kilogrammes, la valeur originale de 86,1 deviendrait 86,100, ce qui aurait un effet important sur vos résultats, ce qui est exactement ce que vous ne voulez pas. La technique de mise à l'échelle la plus courante consiste probablement à soustraire la moyenne et à la diviser par l'écart type (la moyenne et l'écart type sont calculés séparément pour chaque colonne ou élément de cet ensemble de données ; X désigne une entrée/cellule individuelle dans une ligne de données) :

X_new = (X_old - mu) / sigma

II. La structure des données

Si vous êtes préoccupé par les performances de la structure kd-tree, A Tessellation de Voronoï est un conteneur simple d'un point de vue conceptuel, mais qui améliore considérablement les performances et s'adapte mieux que les kd-Trees.

Ce n'est pas la façon la plus courante de conserver les données d'entraînement des kNN, bien que l'application de la VT à cette fin, ainsi que les avantages de performance qui en découlent, soient bien documentés (voir, par exemple, l'article suivant Rapport de Microsoft Research ). En pratique, cela signifie que, si vous utilisez un langage "courant" (par exemple, dans le cadre de l Indice TIOBE ), vous devriez trouver une bibliothèque pour effectuer le VT. Je sais qu'en Python et R, il y a plusieurs options pour chaque langage (par exemple, la librairie voronoï pour R disponible sur CRAN )

L'utilisation d'un VT pour kNN fonctionne comme suit : :

À partir de vos données, sélectionnez au hasard w points - ce sont vos centres de Voronoï. Une cellule de Voronoï englobe tous les points voisins qui sont les plus proches de chaque centre. Imaginez que vous attribuiez une couleur différente à chacun des centres de Voronoï, de sorte que chaque point attribué à un centre donné soit peint de cette couleur. Tant que la densité est suffisante, cette méthode permet de faire apparaître les limites de chaque centre de Voronoï (comme la limite qui sépare deux couleurs).

Comment sélectionner les centres de Voronoï ? J'utilise deux directives orthogonales. Après avoir sélectionné aléatoirement les points w, calculez le VT pour vos données d'entraînement. Vérifiez ensuite le nombre de points de données attribués à chaque centre de Voronoï - ces valeurs devraient être à peu près identiques (étant donné la densité uniforme des points dans votre espace de données). En deux dimensions, cela donnerait un VT avec des tuiles de la même taille.c'est la première règle, voici la seconde. Sélectionnez w par itération - exécutez votre algorithme kNN avec w comme paramètre variable, et mesurez la performance (temps nécessaire pour retourner une prédiction en interrogeant le VT).

Imaginons donc que vous ayez un million de points de données...... Si les points étaient conservés dans une structure de données 2D ordinaire, ou dans un arbre kd, vous effectueriez en moyenne quelques millions de calculs de distance pour les points suivants chaque de nouveaux points de données dont vous souhaitez prédire la variable de réponse. Bien entendu, ces calculs sont effectués sur un seul ensemble de données. Avec un V/T, la recherche du plus proche voisin est effectuée en deux étapes, l'une après l'autre, sur deux populations de données différentes : d'abord sur les centres de Voronoï, puis une fois le centre le plus proche trouvé, les points à l'intérieur de la cellule correspondant à ce centre sont recherchés pour trouver le plus proche voisin réel (par des calculs de distance successifs). C'est facile à voir : pour 1M de points de données, supposons que vous sélectionniez 250 centres de Voronoï pour tesseler votre espace de données. En moyenne, chaque cellule de Voronoï comportera 4 000 points de données. Ainsi, au lieu d'effectuer en moyenne 500 000 calculs de distance (force brute), vous en effectuez beaucoup moins, en moyenne seulement 125 + 2 000.

III. Calcul du résultat (la variable de réponse prédite)

Le calcul de la valeur prédite à partir d'un ensemble de données de formation kNN se fait en deux étapes. La première consiste à identifier n, ou le nombre de voisins les plus proches à utiliser pour ce calcul. Le second est comment pondérer leur contribution à la valeur prédite.

Pour la première composante, vous pouvez déterminer la meilleure valeur de n en résolvant un problème d'optimisation (très similaire à l'optimisation par les moindres carrés). C'est la théorie ; en pratique, la plupart des gens utilisent simplement n=3. Quoi qu'il en soit, il est simple d'exécuter votre algorithme kNN sur un ensemble d'instances de test (pour calculer les valeurs prédites) pour n=1, n=2, n=3, etc. et de tracer l'erreur en fonction de n. Si vous souhaitez simplement une valeur plausible pour n pour commencer, utilisez n = 3.

La deuxième composante est la manière de pondérer la contribution de chacun des voisins (en supposant que n > 1).

La technique de pondération la plus simple consiste à multiplier chaque voisin par un coefficient de pondération, qui est juste le 1/(dist * K), ou l'inverse de la distance entre ce voisin et l'instance de test, souvent multiplié par une constante empirique, K. Je ne suis pas un fan de cette technique parce qu'elle surpondère souvent les voisins les plus proches (et sous-pondère concomitamment les plus éloignés) ; la signification de ceci est qu'une prédiction donnée peut dépendre presque entièrement d'un seul voisin, ce qui augmente la sensibilité de l'algorithme au bruit.

Une fonction de pondération nettement meilleure, qui évite sensiblement cette limitation, est la fonction de pondération suivante fonction gaussienne qui, en python, ressemble à ceci :

def weight_gauss(dist, sig=2.0) :
    return math.e**(-dist**2/(2*sig**2))

Pour calculer une valeur prédite à l'aide de votre code kNN, vous devez identifier les n voisins les plus proches du point de données dont vous souhaitez prédire la variable de réponse ("instance de test"), puis appeler la fonction weight_gauss, une fois pour chacun des n voisins, en indiquant la distance entre chaque voisin et le point de test.

Answer 3

Ce à quoi vous faites face est connu sous le nom de la malédiction de la dimensionnalité . Il est parfois utile d'exécuter un algorithme comme PCA ou ICA pour s'assurer que vous avez vraiment besoin des 21 dimensions et éventuellement trouver une transformation linéaire qui vous permettrait d'en utiliser moins de 21 avec une qualité de résultat à peu près équivalente.

Mise à jour : Je les ai rencontrés dans un livre intitulé Biomedical Signal Processing de Rangayyan (j'espère me souvenir correctement). L'ICA n'est pas une technique triviale, mais elle a été développée par des chercheurs en Finlande et je pense que le code Matlab pour cette technique est disponible publiquement en téléchargement. L'ACP est une technique plus largement utilisée et je pense que vous devriez être en mesure de trouver son implémentation R ou un autre logiciel. L'ACP est réalisée en résolvant des équations linéaires de manière itérative. Je l'ai fait il y a trop longtemps pour me rappeler comment. = )

L'idée est de décomposer vos signaux en vecteurs propres indépendants (fonctions propres discrètes, en fait) et leurs valeurs propres, 21 dans votre cas. Chaque valeur propre indique le degré de contribution de chaque fonction propre à chacune de vos mesures. Si une valeur propre est minuscule, vous pouvez représenter très fidèlement les signaux sans utiliser du tout la fonction propre correspondante, et c'est ainsi que vous vous débarrassez d'une dimension.

Answer 4

Pour répondre à vos questions une par une :

• Non, la distance euclidienne est une mauvaise métrique dans les espaces à haute dimension. En fait, dans les hautes dimensions, les points de données présentent de grandes différences entre eux. Cela diminue la différence relative de la distance entre un point de données donné et son voisin le plus proche et le plus éloigné.
• Il existe beaucoup d'articles et de recherches sur les données de haute dimension, mais la plupart de ces travaux nécessitent une grande sophistication mathématique.
• L'arbre KD est mauvais pour les données à haute dimension... évitez-le par tous les moyens.

Voici un bon document pour vous mettre sur la bonne voie. " En cas de sens du plus proche voisin ?" par Beyer et autres.

Je travaille avec des données textuelles de dimensions 20K et plus. Si vous voulez des conseils sur le texte, je peux peut-être vous aider.

Answer 5

Cet article examine le problème de la recherche des plus proches voisins : Correspondance de caractéristiques à haute dimension : utilisation du concept de plus proches voisins significatifs . J'espère que cela vous sera utile.