J'ai une gamme de points dans un espace dimensionnel inconnu, tel que: et j'aimerais trouver la distance d'euclidienne moyenne entre tous les points. s'il vous plaît Notez que j'ai plus de 20 000 points, alors je voudrais le faire aussi efficacement que possible. merci.
6 Réponses :
Eh bien, je ne pense pas qu'il y ait un moyen super rapide de le faire, mais cela devrait le faire:
tot = 0.
for i in xrange(data.shape[0]-1):
tot += ((((data[i+1:]-data[i])**2).sum(1))**.5).sum()
avg = tot/((data.shape[0]-1)*(data.shape[0])/2.)
Cela prend environ 35 secondes pour fonctionner sur une machine Win32 de 1,86 GHz. Si cela est correct pour votre candidature, je dirais aller avec elle. @Justin - Un couple de petits bugs: vous devriez avoir tot + = (...). Moyenne () et avg = tot / (data.shape [0] -1) .
@mtrw Je suis d'accord qu'il y avait un bug - je divisions le total par le mauvais numéro, mais maintenant je l'ai réparé.
Il n'y a pas de contourner le nombre d'évaluations:
Mais vous pouvez vous épargner les frais de toutes les racines carrées si vous pouvez obtenir avec un Résultat approximatif . Cela dépend de vos besoins.
Si vous allez calculer une moyenne, je vous conseillerais de ne pas essayer de mettre toutes les valeurs dans un tableau avant de calculer. Calculez simplement la somme (et la somme des carrés si vous avez besoin d'un écart-type) et jetez chaque valeur lorsque vous le calculez.
Depuis 
, Je ne sais pas si cela signifie que vous devez multiplier par deux quelque part.
Si vous avez accès à Scipy, vous pouvez essayer ce qui suit:
Je pense que op exprime sciped.spatial.distance.pdist
Maintenant que vous avez indiqué votre objectif de trouver les valeurs aberrantes, vous êtes probablement mieux informé de la moyenne de l'échantillon et, avec cela, la variance de l'échantillon, car ces deux opérations vous donneront une opération O (ND). Avec cela, vous devriez être capable de trouver des valeurs aberrantes (par exemple, à l'exclusion des points d'exclusion de la moyenne que certaines fractions du STD. Dev.), Et que le processus de filtrage devrait être possible de réaliser dans O (ND) de temps pour un total de O ( nd).
Vous pourriez être intéressé par un recyclage sur Inégalité de Chebyshev .
Si vous voulez une solution rapide et inexacte, vous pouvez probablement adapter le Méthode Multiole rapide algorithme.
points séparés par une petite distance ont une contribution plus faible à la distance moyenne finale, il serait donc logique de regrouper des points en grappes et de comparer les distances des grappes.
Cela vaut-il toujours la peine d'optimiser sans solution de travail? De plus, le calcul d'une matrice de distance sur l'ensemble du jeu de données doit rarement être rapide car vous ne le faites qu'une fois - lorsque vous devez connaître une distance entre deux points, vous venez de le regarder, il est déjà calculé.
Donc, si vous n'avez pas de place pour commencer, voici un. Si vous voulez le faire dans NUMPY sans la nécessité d'écrire une inline FORTRAN ou C, cela ne devrait pas être un problème, mais peut-être que vous souhaitez peut-être inclure cette petite machine virtuelle basée sur vecteur appelée " NUMEXPR " (disponible sur PYPI, trivial à Intall) qui dans ce cas donnent une amélioration de 5x performances par rapport à un nombre unique.
ci-dessous J'ai calculé une matrice de distance
![Sum [NI, {I, 0, N}] = http: // www.equationsheet.com/latexRender/pictures/27744c0bd81116AA31C138AB38A2AA87.gif](http://www.équationsheet.com/latexrender/pictures/27744c0bd81116aa2a21c138AB38A2AA87.gif){kind=link}
Lorsque vous dites "Tous points" Voulez-vous dire la distance entre le point 1 au point 2, point 1 au point 3, ... point 1 au point N, la distance du point 2 au point 3, ... point 2 au point N, ... point n-1 au point n?
Je vous recommande de baliser cela comme une question d'algorithme. Vous essayez vraiment de trouver un algorithme qui peut faire mieux que le naïf o (DN ^ 2), où d est la dimensabilité et n est le nombre de ces points. Cela peut être trivialement parallélédiqué dans N opérations, chacun avec Runtime O (ND), qui peut être fusionné dans O (n) temps, mais étant donné que vous n'allez pas avoir 20 000 processeurs, il semble que vous recherchiez plus Algorithme efficace .... Alors, peut-être que quelqu'un peut donner un bon argument adversaire quant à la raison pour laquelle c'est oméga (DN ^ 2), ou quelqu'un peut venir avec un moyen intelligent de le faire plus rapidement ...
L'efficacité ne signifie pas toujours que ce sera assez rapide :) Je pense que c'est O (n * n), vous devrez donc calculer 200 millions de distances!
Avez-vous besoin de toutes les distances, ou juste des distances qui satisfont à certaines exigences?
Le projet plus vaste consiste à trouver les points des points d'exécution. La méthode que j'utilise nécessite la distance moyenne.
Si vous avez juste besoin de trouver des valeurs aberrantes, pourquoi ne pas trouver le point de la moyenne de la distribution (X, la moyenne de Y, la moyenne Z) et utilisez l'écart std de la distance à partir de ce point pour déterminer les valeurs aberrantes. Ce sera un algorithme O (n) plutôt que cet algorithme O (n ^ 2) que vous utilisez.
@Justin, tu m'as battu à mon post.
Si vos données sont quelque peu distribuées dans l'espace R, le test de Grubbs pourrait être une bonne option. Cela ne nécessite que de calculer le point moyen et la déviation type. en.wikipedia.org/wiki/grubbs'_test_for_outliers