2
$\begingroup$

I found this paper Using Pivots to Speed-Up k-Medoids Clustering in which authors explain how to use triangular geometry and cosine law to speed up search of new medoids in case of K-medoids.

My question is - can I use this approach if I'm using Dynamic Time Warping as distance measure? Or some similar measure (for example Euclidean distance that takes into count only features that exist in both vectors, when calculating distance between them)?

Or it can be used only in the case of Euclidean distance?

Short clarification about Dynamic Time Warping:

  • Dynamic Time Warping finds optimal alignment between two signals that could be skewed, shifted, in certain manner
  • Signals being compared may have different length
  • It does that by creating a matrix that allows to repeat values from one of the signals certain number of times, to find the optimal alignment of signals
  • When used as a distance measure you specify operation on two features of a signal (for example, distance of two components of vector could be (a[i] - b[i])^2)

This is explanation from top of my head, it should be more clearer from the link I specified.

So, if we have two vectors (signals) like

A = 1, 1, 1, 2, 2, 3

B = 1,2,3

D(A,B) = 0, because 1 will be repeated three times and 2 will be repeated two times in vector B.

Improve this question
$\endgroup$
2
  • $\begingroup$ Can you decipher in the question what is DTW? $\endgroup$
    – ttnphns
    Commented Mar 25, 2015 at 9:08
  • $\begingroup$ I have edited my question. $\endgroup$
    – Kobe-Wan Kenobi
    Commented Mar 25, 2015 at 9:25

1 Answer 1

Reset to default
0
$\begingroup$

The paper below does K-means for DTW. While non-trivial, medoids are defined under DTW.

However, if speed-up is important under DTW, you will get more speed-up by using constrained DTW, and with a careful (iterative, not recursive) implementation of DTW.

http://www.cs.ucr.edu/~eamonn/ICDM_2014_DTW_average.pdf

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ This answer is too cryptic, please elaborate rather than pointing to an external reference. $\endgroup$
    – Xi'an
    Commented Mar 26, 2015 at 20:14

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.