Les voisins les plus proches avec des données de haute dimension?

I. La Distance Métrique

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

• les statistiques sous-jacents distribution de vos données;

• le relation entre les caractéristiques qui constituent vos données (sont-ils indépendant, c'est à dire, ce qui ne l' matrice de covariance); et

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

si vous n'avez aucune connaissance préalable de la(des) distribution (s) à partir de laquelle vos données ont été échantillonnées, au moins une (bien documentée et complète) l'étude conclut que la distance euclidienne est le meilleur choix.

YEuclidean mesure utilisée dans les méga-échelle Web, les Moteurs de Recommandation ainsi que dans les recherches universitaires actuelles. Les Distances calculées par euclidien ont un sens intuitif et les échelles de calcul--c.-à-d., la distance euclidienne est calculée de la même façon, si les deux points sont dans deux dimensions ou dans l'espace de vingt-deux dimensions.

il a échoué pour moi seulement quelques fois, chacun de ces cas distance euclidienne échoué parce que la le système de coordonnées sous-jacent (cartésien) était un mauvais choix. 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 appropriée pour 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 un autre 3 hrs, plus ou moins dans la même direction, mais Londres à Saint-Pétersbourg n'est pas 5,5 heures, à la place, est 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 matériel. (Voir ce post de blog D'un étudiant de CS, comparant plusieurs mesures de distance en examinant leur effet sur kNN classifier -- chi carré donner les meilleurs résultats, mais les différences ne sont pas Grandes; une étude plus complète est dans le document académique, étude Comparative des 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étrique de distance soient significatifs, vous devez re-échelle vos données--il est rarement possible de construire un kNN modèle 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 athlétique, et vos variables d'attente sont la taille (cm), le poids (kg), la masse adipeuse ( % ), et l'impulsion au repos( battements par minute), alors un point de données typique pourrait ressembler à 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 pourcentage de graisse corporelle sera presque négligeable. Mettez une autre façon, si à la place, les données le poids corporel était exprimé en grammes plutôt qu'en kilogrammes, alors la valeur originale de 86.1, serait de 86.100, ce qui aurait un grand effet 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 caractéristique de cet ensemble de données; X se rapporte à une entrée/cellule individuelle dans une rangée 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 de l'arbre kd, un Voronoi Tessellation est un conteneur conceptuellement simple, mais qui améliorera radicalement la performance et les échelles mieux que les arbres kd.

Ce n'est pas la façon la plus courante de persister les données de formation de kNN, bien que L'application de VT à cette fin, ainsi que les avantages de performance qui en découlent, sont bien documentées (voir par exemple ce Microsoft Research report ). La signification pratique de ceci est que, pourvu que vous employiez une langue 'mainstream' (par exemple, dans le TIOBE Index ) alors vous devriez trouver une bibliothèque pour effectuer VT. Je sais que dans Python et R, Il y a plusieurs options pour chaque langue (par exemple, le voronoi package for R disponible sur CRAN )

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

à partir de vos données, sélectionnez au hasard les points w--ce sont vos centres Voronoi. Une cellule Voronoï regroupe tous les points voisins les plus proches de chaque centre. Imaginez si vous assignez une couleur différente à chacun des centres Voronoï, de sorte que chaque point assigné à un centre donné est peint cette couleur. Tant que vous avez un densité suffisante, ce faisant montrera bien les limites de chaque centre Voronoï (comme la frontière qui sépare deux couleurs.

comment sélectionner les centres Voronoi? J'utilise deux lignes directrices orthogonales. Après avoir choisi au hasard les points w, calculez la VT pour vos données de formation. Vérifiez ensuite le nombre de points de données attribués à chaque centre Voronoi--ces valeurs doivent être à peu près les mêmes (étant donné la densité uniforme de points dans votre espace de données). En deux dimensions, cela permettrait cause un VT avec des tuiles de la même taille.C'est la première règle, voici le deuxième. Sélectionnez w par itération--exécutez votre algorithme kNN avec w comme paramètre variable, et mesurez la performance (temps requis pour retourner une prédiction en interrogeant la VT).

alors imaginez que vous avez un million de points de données..... Si les points étaient maintenus dans une structure de données 2D ordinaire, ou dans un arbre de kd, vous effectueriez en moyenne quelques millions de calculs de distance pour chaque nouveaux points de données dont vous souhaitez prédire la variable de réponse. Bien sûr, ces calculs sont effectués sur un ensemble de données unique. 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 Voronoï, puis une fois que le centre le plus proche est 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 combinés) , ces deux recherches sont beaucoup plus rapides qu'une seule recherche de force brute. C'est facile à voir: pour les points de données 1M, supposons que vous sélectionnez 250 centres Voronoi pour tessélater votre espace de données. En moyenne, chaque cellule Voronoï disposera de 4 000 points de données. Ainsi, au lieu d'effectuer en moyenne 500 000 calculs de distance (brute force), vous effectuez beaucoup moins, en moyenne seulement 125 + 2 000.

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

il y a deux étapes pour calculer la valeur prévue à partir d'un ensemble de données de formation de kNN. Le premier est d'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.

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 utilise 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 l'intrigue de l'erreur en fonction de n. Si vous voulez juste une valeur plausible pour n pour commencer, encore une fois, il suffit d'utiliser n = 3.

la deuxième composante est 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é par une certaine constante dérivée empiriquement, K. Je ne suis pas un fan de cette technique parce qu'elle surestime 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 dépend entièrement d'un seul voisin, ce qui à son tour augmente la sensibilité de l'algorithme au bruit.

une meilleure fonction de pondération doit absolument éviter 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 identifiez les n voisins les plus proches du point de données dont la réponse variable que vous souhaitez prédire ('test instance'), 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 renvoie 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 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 peut-être 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és dans un livre appelé Traitement de Signal biomédical par Rangayyan (j'espère m'en souvenir correctement). de l'ACI n'est pas une simple technique, mais il a été développé par des chercheurs en Finlande et je pense que le code Matlab pour il est publiquement disponible pour le téléchargement. PCA est une technique plus largement utilisée et je crois que vous devriez être en mesure de trouver son R ou d'autres implémentation logicielle. L'ACP est effectuée en résolvant des équations linéaires de façon itérative. Je l'ai fait trop longtemps pour se 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 indique le montant de la contribution que chaque fonction propre fournit à chacune de vos mesures. Si une valeur propre est minuscule, vous pouvez représenter les signaux de très près sans utiliser sa fonction propre correspondante du tout, et c'est ainsi que vous vous débarrassez d'une dimension.

pour répondre à vos questions une par une:

• non, la distance euclidienne est une mauvaise métrique dans l'espace de haute dimension. Essentiellement en haute dimensions il y a peu de différence entre le plus proche et le plus éloigné prochain.
• beaucoup de documents/recherche sont là dans les données de haute dimension, mais la plupart des choses nécessite beaucoup de sofistication mathématique.
• arbre KD est mauvais pour les données de haute dimension ... l'éviter par tous les signifie

voici un beau papier pour vous lancer dans la bonne direction. " quand dans le plus proche voisin significatif ?"par Beyer et tous.

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

les meilleures réponses sont bonnes mais vieilles, donc j'aimerais ajouter un 2016 réponse .

comme dit, dans un espace de haute dimension, la malédiction de la dimensionnalité se cache autour du coin, faisant les approches traditionnelles, comme l'arbre K-D populaire, pour être aussi lent qu'une approche de la force brute. En conséquence, nous tournons notre intérêt dans recherche approximative du plus proche voisin (ANNS) , qui en faveur d'une certaine précision, la vitesse du processus. Vous obtenez une bonne approximation de la NN exacte, avec une bonne propability.

sujets Chauds qui pourraient être digne:

1. les approches Modernes de LSH , comme Razenshteyn .
2. RKD forest : Forêt (s) D'arbres K-D aléatoires (RKD), comme décrit dans FLANN , ou plus approche récente, je faisais partie de, kd-GeRaF .
3. LOPQ qui signifie quantification de produit optimisée localement, comme décrit ici . Il est très similaire à la nouvelle approche de Babenko+Lemptitsky "1519340920 .

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

1. deux séries de haut points dimensionnels: trouver le plus proche voisin dans l'autre ensemble
2. la Comparaison de l'exécution de la méthode du plus Proche Voisin des requêtes sur les différentes structures de données
3. PCL kd-tree mise en œuvre extrêmement lent

la similarité des cosinus est une façon courante de comparer les vecteurs de grande dimension. Notez que puisque c'est une similitude non loin, vous voulez maximiser il pas le minimiser. Vous pouvez également utiliser un moyen spécifique au domaine pour comparer les données, par exemple si vos données sont des séquences D'ADN, vous pouvez utiliser une similarité de séquence qui tient compte des probabilités de mutations, etc.

le nombre de voisins les plus proches à utiliser varie selon le type de données, Combien de bruit il est, etc. Il n'y a pas de règles générales, vous avez juste à trouver ce qui fonctionne le mieux pour vos données spécifiques et le problème en essayant toutes les valeurs dans une gamme. Les gens comprennent intuitivement que plus il y a de données, moins il y a de voisins dont on a besoin. Dans une situation hypothétique où vous avez toutes les données possibles, vous n'avez qu'à chercher le voisin le plus proche pour le classer.

la méthode K du plus proche voisin est connue pour être coûteuse en termes de calcul. C'est l'un des principaux raisons les gens se tournent vers d'autres algorithmes comme les machines vectorielles de soutien.

cela dépend beaucoup de la raison pour laquelle vous voulez connaître les voisins les plus proches. Vous pourriez regarder dans l'algorithme de déplacement 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.

KD-arbres en effet ne fonctionnera pas très bien sur les données de haute dimension. Parce que l'élagage n'aide plus beaucoup, car le bord le plus proche - une déviation de 1 dimension - sera presque toujours plus petit que la déviation de pleine dimension aux voisins les plus proches connus.

mais de plus, les arbres kd ne fonctionnent bien avec les normes Lp que pour ce que je sais, Et il y a l'effet de concentration de la distance qui fait que les algorithmes basés sur la distance se dégradent avec une dimensionnalité croissante.

pour plus d'informations, vous pouvez 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 y ait beaucoup d'utilité à se rapprocher aveuglément des plus proches voisins euclidiens, par exemple en utilisant LSH ou des projections aléatoires. Il peut être nécessaire d'utiliser une fonction de distance beaucoup plus précise en premier lieu!

iDistance est probablement le meilleur exacte de la knn de récupération de données de haute dimension. Vous pouvez le voir comme une estimation du Voronoï tessalation.

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 est-ce (et autres accélérations) pour correspondre à 128-dim Vecteurs de tamis. (Malheureusement FLANN ne fait que la métrique euclidienne, et la rapide et solide scipy.spatial.cKDTree n'Lp métriques; celles-ci peuvent ou non être adéquates pour vos données .) Il y a bien sûr un compromis entre la vitesse et la précision.

(si vous pouvez décrire votre Ndata, Nquery, data distribution, qui pourraient aider les gens à essayer des données similaires.)

ajouté le 26 Avril, les temps d'exécution pour cKDTree avec coupure sur mon vieux 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 une courbe d'ordre z. C'est facile pour 3 dimensions.

je pense que le cosinus sur tf-idf booléen fonctionnalités fonctionnent bien pour la plupart des problèmes. C'est parce que son heuristique prouvé dans le temps utilisé dans de nombreux moteurs de recherche comme Lucene. La distance euclidienne dans mon expérience montre de mauvais résultats pour n'importe quelles données textuelles. La sélection de différents poids et K-exemples peut se faire avec des données d'entraînement et la sélection de paramètres de force brute.

j'ai connu 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 que la Manhattan distance , 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 "151960920, ou de quelque autre précision/rappel de la mesure, afin de trouver une valeur acceptable.

3. les distances euclidienne et Manhattan respectent le Triangle inégalité , donc vous pouvez les utiliser dans les arbres métriques. En effet, les arbres KD voient leurs performances gravement dégradées lorsque les données ont plus de 10 dimensions (j'ai moi-même éprouvé ce problème). J'ai trouvé VP-arbres pour être un une meilleure option.

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

je suggère doux subspace clustering , une jolie approche commune de nos jours, où la fonction de pondération sont calculés pour trouver les dimensions les plus pertinentes. Vous pouvez utiliser ces poids en utilisant la distance euclidienne, par exemple. Voir malédiction de la dimensionalité pour les problèmes communs et aussi ce l'article peut vous éclairer d'une manière ou d'une autre:

k-means type d'algorithme de clustering pour subspace clustering de mixte numérique et ensembles de données catégoriques