1
$\begingroup$

I am looking for a distance metric between vectors whose elements are ordered, i.e so the vectors:

[1,5,0,0,0,0,1], [1,0,4,0,0,1,0]

will be considered closer than

[1,5,0,0,0,0,1], [1,0,0,1,5,0,0]

for example if you perform pacf on a time series you get the importance of the lags on the time series, where the first elements represent 1 lag, the second element 2 lags etc. Naturally if for one time series lag 10 is important and for another it is 11, they are closer than 10 and 15 are...

Is there a metric like that? are vectors like that still called vectors or do they have another name?

edit: a simpler example:

[1,0,0,0,0] should be closer to [0,1,0,0,0] than to [0,0,0,0,1]

the index of the elements should be taken into account...

Improve this question
$\endgroup$
5
  • $\begingroup$ That's usually how it's done, for ex. Euclidean distance is calculated pairwise. $\endgroup$
    – user2974951
    Commented Jun 24, 2020 at 7:10
  • $\begingroup$ I think you misunderstood me. I don't want it to be calculated pairwise because if the pair is off by 1 they are considered completely distant. e.g. [1,0,0,0,0] is as far from [0,1,0,0,0] as it is from [0,0,0,0,1]. That's not what I want.. in my vectors the order of the elements in the vector is meaningful, so if you have high values with close indices to one another (but not identical), they should be considered closer. $\endgroup$
    – Oren Matar
    Commented Jun 24, 2020 at 7:21
  • $\begingroup$ Alternate distance metrics for two time series $\endgroup$
    – user2974951
    Commented Jun 24, 2020 at 7:37
  • 1
    $\begingroup$ Time series distance metric $\endgroup$
    – user2974951
    Commented Jun 24, 2020 at 7:38
  • $\begingroup$ A standard metric with this property is determined by the lexicographic ordering of these vectors. $\endgroup$
    – whuber ♦
    Commented Jun 24, 2020 at 13:45

1 Answer 1

Reset to default
1
$\begingroup$

It seems that the Earth Mover's Distance does exactly what you want. It moves all data ("dirt") from the first vector into the second such that the amount of dirt moved times the dsitance is minimal.

Applying its R implementation on your data yields (the first column in the data represents the value, the second the spatial location, which is the index in your case):

> library(emdist)
> A <- cbind(c(1,5,0,0,0,0,1),1:7)
> B <- cbind(c(1,0,4,0,0,1,0),1:7)
> C <- cbind(c(1,0,0,1,5,0,0),1:7)
> emd(A,B)
[1] 0.8333333
> emd(A,C)
[1] 2.285714
Improve this answer
$\endgroup$
5
  • $\begingroup$ I tried it with the python implementation and it didn't do what I wanted... the EMD didn't seem to care about how far I have to move the 5. if you try emd when you replace the 4 in B with 5 for me it gave a 0 distance, and that's how I understand the metric... which isn't right either... $\endgroup$
    – Oren Matar
    Commented Jun 24, 2020 at 14:03
  • $\begingroup$ Hm, I do not obtain 0 when I replace the 4 in B with a 5, but 0.857. Conceptually, the EMD assumes that the data has been normalized to sum up to one (in other words: the data represents distributions), but principlally the algorithm also works for non-normalized data. $\endgroup$
    – cdalitz
    Commented Jun 24, 2020 at 14:10
  • 1
    $\begingroup$ Just an idea: I had the same problem of obtaining zero at the beginning, because I had not understand the interface: the data must be presentied in two columns (not rows!), with the index as the second column. Maybe you have inadvertantly created a transposed matrix? $\endgroup$
    – cdalitz
    Commented Jun 24, 2020 at 14:12
  • 1
    $\begingroup$ I'll check it out, Thank you, fyi, so far this stackoverflow.com/questions/48497756/… let me to the best solutions. The idea is simple - transform the data to cumsum and then use any distance metric. It's also the idea behind Kolmogorov–Smirnov test, which can be applied here as well. $\endgroup$
    – Oren Matar
    Commented Jun 24, 2020 at 17:34
  • $\begingroup$ a = np.array([1,5,0,0,0,0,1]) b = np.array([1,0,5,0,0,0,1]) wasserstein_distance(a, b) [1] 0 And I was told this makes sense... I don't know the metric very well.. $\endgroup$
    – Oren Matar
    Commented Jun 25, 2020 at 6:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.