Les voisins les plus proches dans les données de grande dimension?

J’étudie actuellement ces problèmes – la classification, la recherche du plus proche voisin – pour la recherche d’informations musicales.

Vous pourriez être intéressé par les algorithmes de voisins les plus proches approximatifs ( ANN ). L’idée est que vous permettez à l’algorithme de retourner suffisamment près des voisins (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 dans les grandes dimensions. En fait, toutes 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 les algorithmes ANN proposés récemment, le plus populaire est peut-être le hachage sensible à la localité ( LSH ), qui associe un ensemble de points dans un espace de grande dimension à un ensemble de cases, à savoir une table de hachage [1] [3]. Mais contrairement aux hachages traditionnels, un hachage sensible à la localité place les points proches dans le même bac.

LSH présente des avantages considérables. Tout d’abord, c’est simple. Il vous suffit de calculer le hachage pour tous les points de votre firebase database, puis de créer une table de hachage. Pour interroger, calculez simplement le hachage du sharepoint requête, puis récupérez tous les points dans le même bac à partir de la table de hachage.

Deuxièmement, une théorie rigoureuse soutient ses performances. On peut montrer que le temps de la requête est quasi- linéaire dans la taille de la firebase database, c’est-à-dire plus rapide que la recherche linéaire. Combien plus rapide dépend de combien d’approximation nous pouvons 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 mesure de distance euclidienne ou vous pouvez l’utiliser avec la mesure de distance Manhattan (L1). Il existe également des variantes pour la distance de Hamming et la similarité des cosinus.

Un aperçu décent a été écrit par Malcolm Slaney et Michael Casey pour IEEE Signal Processing Magazine en 2008 [4].

LSH a été appliqué apparemment partout. Vous voudrez peut-être essayer.

[1] Datar, Indyk, Immorlica, Mirrokni, "Schéma de hachage sensible à la localité basé sur des dissortingbutions p-stables", 2004.

[2] Weber, Schek, Blott, "Une parsing quantitative et une étude de performance pour les méthodes de recherche de similarité dans les espaces de grande dimension", 1998.

[3] Gionis, Indyk, Motwani, "Recherche de similarité dans des dimensions élevées via le hachage", 1999.

[4] Slaney, Casey, "Le hachage sensible à la localité pour trouver les voisins les plus proches", 2008.

I. La distance mésortingque

Tout d’abord, le nombre d’entités (colonnes) dans un dataset n’est pas un facteur dans la sélection d’une mesure de distance à utiliser dans kNN. Il existe pas mal d’études publiées portant précisément sur cette question, et les bases de comparaison habituelles sont:

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

• la relation entre les caractéristiques qui composent vos données (sont-elles indépendantes – c.-à-d. à quoi ressemble la masortingce 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 ou des dissortingbutions à partir desquelles vos données ont été échantillonnées, au moins une étude (bien documentée et approfondie) conclut que la distance euclidienne est le meilleur choix.

Mesure métropolitaine utilisée dans les moteurs de recommandation Web à grande échelle, ainsi que dans la recherche universitaire actuelle. Les distances calculées par Euclidean ont une signification intuitive et les échelles de calcul – c’est-à-dire que la distance euclidienne est calculée de la même manière, que les deux points soient en deux dimensions ou en vingt-deux dimensions.

Cela a seulement échoué pour moi à quelques resockets, chacun de ces cas de distance euclidienne a échoué parce que le système de coordonnées (cartésien) sous-jacent était un mauvais choix. Et vous le reconnaîtrez généralement parce que, par exemple, les longueurs de chemin (les distances) ne sont plus additives – par exemple, lorsque l’espace mésortingque est un échiquier, la distance de Manhattan est meilleure que celle d’Euclide; -les vols continentaux, une mésortingque de distance adaptée à un système de coordonnées polaires est une bonne idée (par exemple, Londres est de 2 heures et demie à Vienne, et de 3 heures à Vienne ou à peu près dans le même sens). Pétersbourg n’est pas 5,5 heures au lieu de 3 heures.

Mais mis à part les cas où vos données appartiennent à un système de coordonnées non cartésien, le choix de la mésortingque de distance n’est généralement pas matériel. (Voir cet article d’un étudiant CS, comparant plusieurs mesures de distance en examinant leur effet sur le classificateur kNN – chi carré donne les meilleurs résultats, mais les différences ne sont pas grandes; une étude plus complète est dans l’étude académique, Étude comparative de Fonctions de distance pour les voisins les plus proches – Mahalanobis (essentiellement euclidienne normalisé par pour tenir compte de la covariance de dimension) était le meilleur dans cette étude.

Une condition importante: pour que les calculs de mésortingques de distance soient significatifs, vous devez redimensionner vos données – il est rarement possible de construire un modèle de réseau de base pour générer des prévisions précises sans le faire. Par exemple, si vous construisez un modèle kNN pour prédire la performance sportive et que vos variables d’attente sont la hauteur (cm), le poids (kg), la graisse corporelle (%) et le pouls au repos (battements par minute) ressemble à ceci: [180.4, 66.1, 11.3, 71]. De toute évidence, le calcul de la distance sera dominé par la hauteur, tandis que la consortingbution de% de graisse corporelle sera presque négligeable. En d’autres termes, si les données étaient rapscopes différemment, de sorte que le poids était en grammes plutôt que de kilogrammes, alors la valeur initiale de 86,1 serait de 86 100, ce qui aurait un effet important sur vos résultats, ce qui est exactement ce que vous avez fait. Je ne veux pas. La technique de mise à l’échelle la plus courante consiste probablement à soustraire la moyenne et à la diviser par l’écart type (moyenne et référence sd calculées séparément pour chaque colonne, ou caractéristique dans cet dataset; X désigne une entrée / cellule individuelle dans une ligne de données):

 X_new = (X_old - mu) / sigma 

II. La structure de données

Si vous êtes préoccupé par la performance de la structure kd-tree, A Tesser est un conteneur conceptuellement simple mais qui améliorera considérablement les performances et les échelles, mieux que kd-Trees.

Ce n’est pas la manière la plus courante de persister les données de formation kNN, bien que l’application de VT à cette fin, ainsi que les avantages de performances qui en découlent, soient bien documentés (voir par exemple ce rapport Microsoft Research ). La signification pratique de ceci est que, à condition que vous utilisiez un langage “grand public” (par exemple, dans l’ index TIOBE ), vous devriez alors trouver une bibliothèque pour effectuer VT. Je sais en Python et R, il y a plusieurs options pour chaque langue (par exemple, le paquet voronoi pour R disponible sur CRAN )

Utiliser un VT pour kNN fonctionne comme ceci:

À partir de vos données, sélectionnez aléatoirement des points – ce sont vos centres Voronoi. Une cellule de Voronoi encapsule tous les points voisins les plus proches de chaque centre. Imaginez si vous atsortingbuez une couleur différente à chacun des centres de Voronoi, de sorte que chaque point atsortingbué à un centre donné soit peint de cette couleur. Tant que vous avez une densité suffisante, cela montre bien les limites de chaque centre de Voronoi (comme la frontière qui sépare deux couleurs).

Comment sélectionner les centres Voronoi? J’utilise deux directives orthogonales. Après avoir sélectionné au hasard les points w, calculez le TV pour vos données d’entraînement. Vérifiez ensuite le nombre de points de données affectés à chaque centre Voronoi. Ces valeurs doivent être à peu près identiques (étant donné la densité de points uniforme dans votre espace de données). En deux dimensions, cela provoquerait un VT avec des tuiles de 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 de variable et mesurez les performances (temps nécessaire pour renvoyer une prédiction en interrogeant le VT).

Imaginez 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 une arborescence, vous effectueriez en moyenne quelques millions de calculs de distance pour chaque nouveau sharepoint données dont la variable de réponse vous souhaitez prédire. Bien entendu, ces calculs sont effectués sur un seul dataset. Avec un V / T, la recherche du plus proche voisin est effectuée en deux étapes l’une après l’autre, contre deux populations de données différentes – d’abord contre les centres de Voronoi, puis une fois le centre le plus proche, les points correspondant à ce centre est recherché pour trouver le voisin le plus proche (par des calculs de distance successifs). Combinés, ces deux recherches sont beaucoup plus rapides qu’une recherche de force brute. C’est facile à voir: pour les points de données 1M, supposez que vous sélectionniez 250 centres Voronoi pour configurer votre espace de données. En moyenne, chaque cellule de Voronoi aura 4 000 points de données. Ainsi, au lieu d’effectuer en moyenne 500 000 calculs de distance (force brute), vous réalisez beaucoup moins, en moyenne seulement 125 + 2 000.

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

Il y a deux étapes pour calculer la valeur prédite à partir d’un dataset d’entraînement kNN. Le premier est l’identification de n ou le nombre de voisins les plus proches à utiliser pour ce calcul. La seconde est comment pondérer leur consortingbution à la valeur prédite.

Avec le premier composant, vous pouvez déterminer la meilleure valeur de n en résolvant un problème d’optimisation (très similaire à l’optimisation des moindres carrés). C’est la théorie; dans la pratique, la plupart des gens utilisent n = 3. Dans tous les cas, 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 voulez juste une valeur plausible pour que n commence, utilisez n = 3.

La seconde composante est la façon de pondérer la consortingbution de chacun des voisins (en supposant que n> 1).

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

La 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, identifiez les n voisins les plus proches du sharepoint données dont vous souhaitez prédire la variable de réponse («instance de test»), puis appelez la fonction weight_gauss pour chacun des n voisins. dans la distance entre chaque voisin le sharepoint test.Cette fonction retournera le poids pour chaque voisin, qui est ensuite utilisé comme coefficient de ce voisin dans le calcul de la moyenne pondérée.

Ce que vous faites face est connu comme la malédiction de la dimensionnalité . Il est parfois utile d’exécuter un algorithme tel que PCA ou ICA pour vous assurer que vous avez réellement besoin de toutes les 21 dimensions et éventuellement trouver une transformation linéaire qui vous permettrait d’utiliser moins de 21 avec approximativement la même qualité de résultat.

Mise à jour: je les ai rencontrées dans un livre intitulé Biomedical Signal Processing par Rangayyan (j’espère que je m’en souviens bien). ICA n’est pas une technique sortingviale, mais elle a été développée par des chercheurs en Finlande et je pense que le code Matlab pour ce document est disponible au téléchargement. PCA est une technique plus largement utilisée et je pense que vous devriez pouvoir trouver son implémentation R ou autre logiciel. L’ACP est réalisée en résolvant itérativement des équations linéaires. Je l’ai fait il y a trop longtemps pour me rappeler comment. =)

L’idée est que vous divisez vos signaux en vecteurs propres indépendants (fonctions propres discrètes, vraiment) et leurs valeurs propres, 21 dans votre cas. Chaque valeur propre indique la consortingbution de chaque fonction propre à chacune de vos mesures. Si une valeur propre est minuscule, vous pouvez très bien représenter les signaux sans utiliser sa fonction propre correspondante, et c’est ainsi que vous vous débarrassez d’une dimension.

Répondre à vos questions une par une:

• Non, la distance euclidienne est une mauvaise mesure dans un espace de grande dimension. Dans les grandes dimensions, il y a peu de différence entre le voisin le plus proche et le plus proche.
• Beaucoup de documents / recherches sont là dans les données de grande dimension, mais la plupart des choses nécessitent beaucoup de simplification mathématique.
• L’arbre KD est mauvais pour les données de grande dimension … évitez-le par tous les moyens

Voici un bon article pour vous aider à démarrer dans la bonne direction. ” Quand le plus proche voisin a- t-il un sens ?” par Beyer et tous.

Je travaille avec des données textuelles de dimensions 20K et supérieures. Si vous voulez des conseils liés au texte, je pourrais peut-être vous aider.

Les meilleures réponses sont bonnes mais anciennes. J’aimerais donc append une réponse pour 2016 .

Comme on l’a dit, dans un espace de grande dimension, la malédiction de la dimensionnalité se cache au coin de la rue, faisant que les approches traditionnelles, telles que l’arbre populaire kd, sont aussi lentes qu’une approche par force brute. En conséquence, nous nous intéressons à la recherche de voisins les plus proches approximatifs (ANNS) , qui, en faveur d’une certaine précision, accélère le processus. Vous obtenez une bonne approximation du NN exact, avec une bonne probabilité.

Des sujets d’actualité qui pourraient valoir la peine:

1. Les approches modernes du LSH , telles que celles de Razenshteyn .
2. Forêt RKD : Forêt (s) d’arbres kd randomisés (RKD), comme décrit dans FLANN , ou dans une approche plus récente à laquelle je faisais partie, kd-GeRaF .
3. LOPQ, qui signifie «Quantification optimisée localement», décrite ici . Il est très similaire à la nouvelle approche de Babenko + Lemptitsky.

Vous pouvez également vérifier mes réponses pertinentes:

1. Deux ensembles de points de grande dimension: trouver le plus proche voisin dans l’autre ensemble
2. Comparaison de l’exécution des requêtes de voisinage le plus proche sur différentes structures de données
3. Implémentation PCL kd-tree extrêmement lente

La similarité des cosinus est un moyen courant de comparer les vecteurs de grande dimension. Notez que comme c’est une similarité et non une distance, vous voudrez la maximiser sans la minimiser. Vous pouvez également utiliser une méthode spécifique au domaine pour comparer les données. Par exemple, si vos données étaient des séquences d’ADN, vous pourriez utiliser une similarité de séquence prenant en compte les probabilités de mutations, etc.

Le nombre de voisins les plus proches à utiliser varie selon le type de données, la quantité de bruit, etc. Il n’y a pas de règles générales, il suffit de trouver ce qui convient le mieux à vos données et problèmes en essayant toutes les valeurs d’une plage . Les gens comprennent intuitivement que plus il y a de données, moins il y a de voisins. Dans une situation hypothétique où vous disposez de toutes les données possibles, il vous suffit de rechercher le seul voisin le plus proche à classer.

La méthode du k plus proche voisin est connue pour être coûteuse en calcul. C’est l’une des principales raisons pour lesquelles les gens se tournent vers d’autres algorithmes tels que les machines à vecteurs de support.

Beaucoup dépend de la raison pour laquelle vous voulez connaître les voisins les plus proches. Vous pouvez vous pencher sur l’algorithme de décalage moyen http://en.wikipedia.org/wiki/Mean-shift si vous voulez vraiment trouver les modes de votre dataset.

kd-trees ne fonctionnera pas très bien sur des données de grande dimension. Parce que l’étape d’élagage n’aide plus beaucoup, car le bord le plus proche – une déviation à 1 dimension – sera presque toujours plus petit que l’écart par rapport aux voisins les plus proches connus.

Mais de plus, les kd-trees ne fonctionnent bien qu’avec les normes Lp pour tout ce que je sais, et il y a l’effet de concentration de distance qui fait que les algorithmes basés sur la distance se dégradent avec la dimensionnalité croissante.

Pour plus d’informations, vous pouvez lire la malédiction de la dimensionnalité et ses différentes variantes (il y a plus d’un côté!)

Je ne suis pas convaincu qu’il soit très utile de rapprocher aveuglément les voisins les plus proches d’Euclide, par exemple en utilisant des projections LSH ou aléatoires. Il peut être nécessaire d’utiliser une fonction de distance beaucoup plus fine en premier lieu!

iDistance est probablement le meilleur pour une récupération exacte dans des données de grande dimension. Vous pouvez le voir comme une approximation approximative de Voronoi.

Les arbres KD fonctionnent bien pour 21 dimensions, si vous quittez tôt, après avoir regardé par exemple 5% de tous les points. FLANN fait ceci (et d’autres accélérations) pour correspondre aux vecteurs SIFT de 128 dimensions. (Malheureusement, FLANN ne fait que la mésortingque euclidienne, et le scipy.spatial.cKDTree rapide et solide ne fait que des mésortingques Lp; celles-ci peuvent ou non convenir à vos données).

(Si vous pouviez décrire votre dissortingbution de données Ndata, Nquery, cela pourrait aider les gens à essayer des données similaires.)

Ajout du 26 avril, temps d’exécution de cKDTree avec coupure sur mon ancien mac ppc, pour donner une idée très approximative de la faisabilité:

 kdstats.py p=2 dim=21 N=1000000 nask=1000 nnear=2 cutoff=1000 eps=0 leafsize=10 clustype=uniformp 14 sec to build KDtree of 1000000 points kdtree: 1000 queries looked at av 0.1 % of the 1000000 points, 0.31 % of 188315 boxes; better 0.0042 0.014 0.1 % 3.5 sec to query 1000 points distances to 2 nearest: av 0.131 max 0.253 kdstats.py p=2 dim=21 N=1000000 nask=1000 nnear=2 cutoff=5000 eps=0 leafsize=10 clustype=uniformp 14 sec to build KDtree of 1000000 points kdtree: 1000 queries looked at av 0.48 % of the 1000000 points, 1.1 % of 188315 boxes; better 0.0071 0.026 0.5 % 15 sec to query 1000 points distances to 2 nearest: av 0.131 max 0.245 

Vous pouvez essayer la courbe d’ordre z. C’est facile pour 3 dimensions.

Je pense que le cosinus sur tf-idf des fonctionnalités booléennes fonctionnerait bien pour la plupart des problèmes. C’est parce que son heuristique éprouvée utilisée dans de nombreux moteurs de recherche comme Lucene. La distance euclidienne dans mon expérience montre de mauvais résultats pour toute donnée de type texte. La sélection de différents poids et exemples de k peut être effectuée à l’aide des données d’entraînement et de la sélection des parameters de force brute.

J’ai rencontré le même problème et je peux dire ce qui suit.

1. La distance euclidienne est une bonne mesure de distance, mais elle est plus coûteuse que la distance de Manhattan et donne parfois des résultats légèrement plus faibles. Je choisirais donc la dernière.

2. La valeur de k peut être trouvée empiriquement. Vous pouvez essayer différentes valeurs et vérifier les courbes ROC résultantes ou une autre mesure de précision / rappel afin de trouver une valeur acceptable.

3. Les distances euclidiennes et les distances de Manhattan respectent toutes les deux l’ inégalité de Triangle , vous pouvez donc les utiliser dans les arbres mésortingques. En effet, les performances des arbres KD sont fortement dégradées lorsque les données ont plus de 10 dimensions (j’ai moi-même rencontré ce problème). J’ai trouvé que les arbres VP étaient une meilleure option.

La distance euclidienne est-elle une bonne mesure pour trouver les voisins les plus proches en premier lieu? Si non, quelles sont mes options?

Je suggérerais la mise en grappe des sous-espaces logiciels , une approche assez courante de nos jours, où les pondérations des entités sont calculées pour trouver les dimensions les plus pertinentes. Vous pouvez utiliser ces poids lorsque vous utilisez la distance euclidienne, par exemple. Voir la malédiction de la dimensionnalité pour les problèmes courants et cet article peut aussi vous éclairer:

Un algorithme de clustering de type k-means pour le regroupement de sous-espaces de jeux de données numériques et catégoriques mixtes