Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

I would like to compute the measure of similarity between two ordered sets of points---the ones under User compared with the ones under Teacher:

Example

The points are curves in 3D space, but I was thinking that the problem is simplified if I plotted them in 2 dimensions like in the picture. If the points overlap, similarity should be 100%.

share|improve this question
    
Do you need to account for scaling, rotation and/or translation? –  nico May 6 '12 at 7:54
    
No, I don't need to take them into account. –  Alex May 7 '12 at 14:04
    
meaning that I will apply take care of that. –  Alex May 7 '12 at 14:15

5 Answers 5

You are comparing trajectories, or curves. This is a studied topic. Procrustes analysis and dynamic time warping, as EMS says, are tools of the trade. Once you've aligned the curves you'll want to measure the distance, say the Fréchet distance. If you want to share some of your data we could take a crack at it ourselves.

Relevant reading:

If you disregard the temporal dimension:

You could fit the User and Teacher to multivariate Gaussian densities and find the volume of their product--that's pretty easy. If you want more accuracy, you could use a nonparametric density estimate instead.

share|improve this answer
    
Thank you Emre for your suggestion! I have updated the problem - I think it may be simpler now so please have a look. –  Alex May 7 '12 at 14:13
    
You could fit the User and Teacher to multivariate Gaussian densities and find the volume of their product--that's pretty easy Could you please kindly point me to the correct resources to learn this? Really newbie here. –  Sibbs Gambling Sep 6 '13 at 14:45

You might consider Procrustes distance, or some distance based on dynamic time warping (even if one of your dimensions is not "time" per se, you can still use this transformation idea). See this recent work on Tracklets for an illustrative use case of dynamic time warping for measuring similarity between 3D space curves carved out by point trajectories in videos.

There are many libraries with built-in Procrustes distance calculations, such as Matlab, or the PyGeometry library for Python.

share|improve this answer

The original post asked for a metric between ORDERED points in 3D. The only such metric is the Frechet distance. There was no mention of time as one of the dimensions, so I would assume that all the dimensions have units of distance (i.e. the units are not mixed). This can be done by modifying a function recently uploaded to the MathWorks file exchange (Frechet distance calculation: http://www.mathworks.com/matlabcentral/fileexchange/38714). These routines were written for points in the plane, but the extension to 3D points is straightforward.

share|improve this answer
1  
Are you sure the Frechet distance is between ordered pairs? the wikipedia page says that a point in one path can be matched to multiple points in another. Also, surely there is more than one such metric. What about the sum of the distances between ordered pairs? –  naught101 Oct 31 '12 at 23:09

Hausdorff Distance might be what you are looking for. Hausdorff Distance between two point sets $X$ and $Y$ is defined as, $d_H(X, Y) = \max \{\sup_{x \in X} \inf_{y \in Y} ||x - y||, \sup_{y \in Y} \inf_{x \in X} ||x - y||\}$.

share|improve this answer
    
I don't think this is a very tractable approach. Unless you mean to approximate this by replacing all of the $\sup$ and $\inf$ with $\max$ and $\min$.. but Hausdorff distance won't be well approximated by these in many cases. How do you propose to actually compute (in software) such distances? –  prpl.mnky.dshwshr May 7 '12 at 17:37
1  
@EMS There are two ways to go about this, 1. either consider $X$ and $Y$ as discrete point sets, makes things simpler 2. or try to come up with some form of convex hull for each point set (not quite sure whether this is necessary) and something like [this][1] could be used to approximately compute the distance. [1]: cg.cs.uni-bonn.de/aigaion2root/attachments/guthe-2005-fast.pdf –  TenaliRaman May 7 '12 at 18:21
    
Thank you for the link, I had only seen Hausdorff distance in computer vision in Tony Chan's book. It's cool to see more computational approaches. –  prpl.mnky.dshwshr May 7 '12 at 19:13

Similarity is quantity that reflects the strength of relationship between two objects or two features. This quantity is usually having range of either -1 to +1 or normalized into 0 to 1. Than you need to calculate the distance of two features by one of the methods below:

  1. Simple Matching distance
  2. Jaccard's distance
  3. Hamming distance
  4. Jaccard's coefficient
  5. simple matching coefficient

For line... you can represent it by angle (a) and length (l) properties or L1= P1(x1,y1), P2(x2,y2) below is the similarity with a and l.

now measure the angle for angles and lengths

  • A_user =20 and Length_User =50
  • A_teacher30 and Length_Teacher =55
  • Now, normalize the values.

Using euclidean distance

similarity = SquareRoot((A_user - A_teacher30 )^2 +(Length_User - Length_Teacher )^2)

gives the similarity measure. You can also use above mentioned methods based on the problem and the features.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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