Voisins les plus proches dans les données de grande dimension?

J'ai posé une question il y a quelques jours sur la façon de trouver les voisins les plus proches pour un vecteur donné. Mon vecteur est maintenant de 21 dimensions et avant d'aller plus loin, car je ne suis pas du domaine du Machine Learning ni des Mathématiques, je commence à me poser quelques questions fondamentales:

• La distance euclidienne est-elle une bonne métrique pour trouver les voisins les plus proches en premier lieu? Sinon, quelles sont mes options?
• De plus, comment décide-t-on du bon seuil pour déterminer les k-voisins? Y a-t-il une analyse qui peut être faite pour déterminer cette valeur?
• Auparavant, on m'avait suggéré d'utiliser kd-Trees mais la page Wikipedia dit clairement que pour les grandes dimensions, kd-Tree équivaut presque à une recherche par force brute. Dans ce cas, quelle est la meilleure façon de trouver efficacement les voisins les plus proches dans un ensemble de données à un million de points?

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

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 les algorithmes ANN ( Approximate Nearest Neighbor ). L'idée est que vous permettez à l'algorithme de renvoyer des voisins suffisamment proches (peut-être pas le voisin le plus proche); 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 la partition spatiale) se dégradent en recherche linéaire de dimensions suffisamment élevées [1] [2] [3].

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

Le LSH présente d'énormes avantages. Tout d'abord, c'est simple. Vous calculez simplement le hachage pour tous les points de votre base de données, puis créez une table de hachage à partir d'eux. Pour interroger, calculez simplement le hachage du point de requête, puis récupérez tous les points dans le même bac à partir de la table de hachage.

Deuxièmement, il existe une théorie rigoureuse qui soutient ses performances. On peut montrer que le temps de requête est sous - linéaire de la taille de la base de données, par exemple, plus rapide que la recherche linéaire. La rapidité dépend du degré d'approximation que 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 métrique de distance euclidienne, ou vous pouvez l'utiliser avec la métrique de distance Manhattan (L1). Il existe également des variantes pour la distance de Hamming et la similitude cosinus.

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

Le 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 distributions p-stables», 2004.

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

[3] Gionis, Indyk, Motwani, "Recherche de similarité en grandes dimensions via hachage", 1999.

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

I. La métrique de distance

Premièrement, le nombre d'entités (colonnes) dans un ensemble de données n'est pas un facteur dans la sélection d'une mesure de distance à utiliser en kNN. Il existe de nombreuses études publiées portant précisément sur cette question, et les bases de comparaison habituelles sont:

• la distribution statistique sous-jacente 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 des distributions à 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.

Métrique YEuclidean utilisée dans les moteurs de recommandation Web à grande échelle ainsi que dans la recherche universitaire actuelle. Les distances calculées par Euclidienne 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 dans un espace de vingt-deux dimensions.

Cela n'a échoué pour moi que quelques fois, chacun de ces cas La distance euclidienne a échoué parce que le système de coordonnées sous-jacent (cartésien) était un mauvais choix. Et vous le reconnaîtrez généralement 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 qu'Euclidienne, de même lorsque l'espace métrique est la Terre et vos distances sont trans -vols continentaux, une mesure de distance adaptée à un système de coordonnées polaires est une bonne idée (par exemple, Londres à Vienne est de 2,5 heures, Vienne à Saint-Pétersbourg est encore 3 heures, plus ou moins dans la même direction, mais Londres à St . Pétersbourg n'est pas 5,5 heures, à la place, c'est un peu plus de 3 heures.)

Mais à part les 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 ce billet de blog d'un étudiant CS, comparant plusieurs métriques de distance en examinant leur effet sur le classificateur kNN - le chi carré donne les meilleurs résultats, mais les différences ne sont pas grandes; Une étude plus complète se trouve dans l'article académique, Comparative Study of Fonctions de distance pour les voisins les plus proches - Mahalanobis (essentiellement euclidienne normalisée par pour tenir compte de la covariance de dimension) était la meilleure de cette étude.

Une condition importante: pour que les calculs de métrique de distance soient significatifs, vous devez redimensionnervos données - il est rarement possible de créer 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 sportives 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 ressemble à quelque chose comme ceci: [180.4, 66.1, 11.3, 71]. Il est clair que le calcul de la distance sera dominé par la hauteur, tandis que la contribution du% de graisse corporelle sera presque négligeable. En d'autres termes, si au contraire, les données étaient déclarées différemment, de sorte que le poids corporel était en grammes plutôt qu'en kilogrammes, alors la valeur d'origine de 86,1 serait de 86,100, ce qui aurait un effet important sur vos résultats, ce qui est exactement ce que vous ne faites pas. veux pas.

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 Voronoi Tessellation est un conteneur conceptuellement simple mais qui améliorera considérablement les performances et évoluera mieux que kd-Trees.

Ce n'est pas la manière la plus courante de conserver les données d'entraînement 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 la TV. Je sais qu'en Python et R, il existe plusieurs options pour chaque langue (par exemple, le package voronoi pour R disponible sur CRAN )

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

À partir de vos données, sélectionnez aléatoirement w points - ce sont vos centres Voronoi. Une cellule Voronoi encapsule tous les points voisins les plus proches de chaque centre. Imaginez si vous attribuez une couleur différente à chacun des centres de Voronoi, de sorte que chaque point affecté à un centre donné soit peint de cette couleur. Tant que vous avez une densité suffisante, cela montrera 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 lignes directrices orthogonales. Après avoir sélectionné au hasard 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 Voronoi - ces valeurs doivent être à peu près les mêmes (é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 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 persistants dans une structure de données 2D ordinaire, ou dans un arbre kd, vous effectueriez en moyenne quelques millions de calculs de distance pour chaquenouveaux 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, contre deux populations différentes de données - d'abord contre les centres de Voronoi, puis une fois le centre le plus proche trouvé, les points à l'intérieur de la cellule correspondant à ce centre est recherché pour trouver le voisin le plus proche réel (par des calculs de distance successifs) Combinés, ces deux recherches sont beaucoup plus rapides qu'une seule recherche par force brute. C'est facile à voir: pour 1M de points de données, supposons que vous sélectionniez 250 centres Voronoi pour tesseler votre espace de données. En moyenne, chaque cellule Voronoi aura 4 000 points de données. Ainsi, au lieu d'effectuer en moyenne 500000 calculs de distance (force brute), vous effectuez beaucoup moins, en moyenne seulement 125 + 2000.

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

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

W / r / t 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; en pratique, la plupart des gens utilisent simplement 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 qu'une valeur plausible pour n commence, encore une fois, utilisez simplement n = 3.

La deuxième composante est de savoir comment pondérer la contribution de chacun des voisins (en supposant 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, K. I je ne suis pas fan de cette technique car elle surestime souvent les voisins les plus proches (et sous-pondère en même temps 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 à son tour augmente la sensibilité de l'algorithme au bruit.

Une fonction de pondération incontournable, qui évite considérablement cette limitation est 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, 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 passant dans la distance entre chaque voisin le point de 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 à quoi vous faites face est connu comme 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'utiliser moins de 21 avec à peu près la même qualité de résultat.

Mise à jour: je les ai rencontrés dans un livre intitulé Biomedical Signal Processing de Rangayyan (j'espère m'en souvenir correctement). 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 est disponible publiquement pour téléchargement. La PCA est une technique plus largement utilisée et je pense que vous devriez pouvoir trouver son R ou une autre implémentation logicielle. 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 que vous divisez vos signaux en vecteurs propres indépendants (fonctions propres discrètes, en fait) et leurs valeurs propres, 21 dans votre cas. Chaque valeur propre montre la quantité de contribution que chaque fonction propre fournit à chacune de vos mesures. Si une valeur propre est minuscule, vous pouvez représenter très étroitement les signaux sans utiliser du tout sa fonction propre correspondante, et c'est ainsi que vous vous débarrassez d'une dimension.

Les principales réponses sont bonnes mais anciennes, alors j'aimerais ajouter une réponse de 2016 .

Comme dit, dans un espace dimensionnel élevé, la malédiction de la dimensionnalité se cache au coin de la rue, rendant les approches traditionnelles, telles que l'arbre kd populaire, aussi lentes qu'une approche par force brute. En conséquence, nous nous intéressons à la recherche approximative des voisins les plus proches (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 propabilité.

Sujets d'actualité qui pourraient valoir la peine:

1. Approches modernes du LSH , comme celle de Razenshteyn .
2. Forêt RKD : forêt (s) d'arbres kd aléatoires (RKD), comme décrit dans FLANN , ou dans une approche plus récente dont j'ai fait partie, kd-GeRaF .
3. LOPQ qui signifie quantification de produit optimisée localement, comme décrit ici . C'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: trouvez le voisin le plus proche dans l'autre ensemble
2. Comparaison de l'exécution des requêtes du voisin le plus proche sur différentes structures de données
3. Implémentation de kd-tree PCL extrêmement lente

Pour répondre à vos questions une par une:

• Non, la distance euclidienne est une mauvaise métrique dans un espace dimensionnel élevé. Fondamentalement, dans des dimensions élevées, les points de données présentent de grandes différences entre eux. Cela diminue la différence relative de distance entre un point de données donné et son voisin le plus proche et le plus éloigné.
• Il existe de nombreux articles / recherches dans des données de grande dimension, mais la plupart des éléments nécessitent beaucoup de sophistication 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 voisin le plus proche est-il significatif ?" par Beyer et all.

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

La similitude cosinus est un moyen courant de comparer des vecteurs de grande dimension. Notez que puisqu'il s'agit d'une similitude et non d'une distance, vous voudrez la maximiser et non la minimiser. Vous pouvez également utiliser un moyen spécifique au domaine pour comparer les données, par exemple si vos données étaient des séquences d'ADN, vous pouvez utiliser une similarité de séquence qui prend en compte les probabilités de mutations, etc.

Le nombre de voisins les plus proches à utiliser varie en fonction du type de données, de la quantité de bruit, etc. Il n'y a pas de règles générales, il vous suffit de trouver ce qui fonctionne le mieux pour vos données et votre problème spécifiques en essayant toutes les valeurs dans une plage . Les gens comprennent intuitivement que plus il y a de données, moins vous avez besoin de voisins. Dans une situation hypothétique où vous avez toutes les données possibles, il vous suffit de rechercher le voisin le plus proche à classer.

La méthode k Nearest Neighbor 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 comme les machines vectorielles de support.

Les kd-tree ne fonctionneront en effet pas très bien sur des données de grande dimension. Parce que l'étape d'élagage n'aide plus beaucoup, car l'arête la plus proche - une déviation à une dimension - sera presque toujours plus petite que la déviation pleine dimension par rapport aux voisins les plus proches connus.

Mais de plus, les kd-arbres ne fonctionnent bien qu'avec les normes Lp pour autant que je sache, 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 voudrez peut-être lire sur 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 utile de simplement approximer aveuglément les voisins les plus proches euclidiens, par exemple en utilisant LSH ou des projections aléatoires. Il peut être nécessaire d'utiliser une fonction de distance beaucoup plus fine en premier lieu!

Cela dépend beaucoup de la raison pour laquelle vous souhaitez connaître les voisins les plus proches. Vous pourriez regarder dans l'algorithme de décalage moyen http://en.wikipedia.org/wiki/Mean-shift si ce que vous voulez vraiment est de trouver les modes de votre ensemble de données.

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 est utilisée dans de nombreux moteurs de recherche comme Lucene. D'après mon expérience, la distance euclidienne montre de mauvais résultats pour toutes les données de type texte. La sélection de différents poids et k-exemples peut être effectuée avec des données d'entraînement et une sélection de paramètres de force brute.

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

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

1. La distance euclidienne est une bonne métrique de distance, mais elle est plus coûteuse en calcul que la distance de Manhattan , et donne parfois des résultats légèrement plus mauvais, donc je choisirais la plus tardive.

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 de Manhattan respectent l' inégalité du triangle , vous pouvez donc les utiliser dans des arbres métriques. En effet, les performances des arbres KD sont gravement 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.

Les arbres KD fonctionnent bien pour 21 dimensions, si vous arrêtez tôt, après avoir examiné, par exemple, 5% de tous les points. FLANN fait cela (et d'autres accélérations) pour faire correspondre les vecteurs SIFT de 128 dim. (Malheureusement, FLANN ne fait que la métrique euclidienne, et le scipy.spatial.cKDTree rapide et solide ne fait que les métriques Lp; celles-ci peuvent ou non être adéquates pour vos données.) Il y a bien sûr un compromis vitesse-précision ici.

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

Ajouté le 26 avril, temps d'exécution pour 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 az. C'est facile pour 3 dimensions.

La distance euclidienne est-elle une bonne métrique pour trouver les voisins les plus proches en premier lieu? Sinon, quelles sont mes options?

Je suggérerais le clustering de sous-espaces souples , une approche assez courante de nos jours, où les poids des caractéristiques sont calculés 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 également vous éclairer:

Un algorithme de clustering de type k-means pour le clustering de sous-espaces d'ensembles de données numériques et catégoriels mixtes