[R] frechet distance

[Liaw, Andy]

[Sorry for coming to this so late...  I've been trying to play catch-up with
~1000 unread messages in my R-help folder...]

If the curves are sufficiently smooth (i.e., `kinks' are quite small,
relative to the real sigmoidal features of interest), what I would try is
something like smoothing splines or local polynomials, but over-smooth
(i.e., use "large enough" smoothing parameters) so that only the essential
features of the sigmoidal or double sigmoidal features remains, then look at
the zero crossings of the derivatives.  Martin has functions like D1ss() in
the `sfsmisc' package to do this.

HTH,
Andy


From: Rajarshi Guha
> 
> On Thu, 2006-06-22 at 19:52 -0700, Spencer Graves wrote:
> > 	  RSiteSearch("Frechet distance") returned only one hit 
> for me just 
> > now, and that was for a Frechet distribution, as you 
> mentioned.  Google 
> > found "www.cs.concordia.ca/cccg/papers/39.pdf", which suggests that 
> > computing it may not be easy.
> 
> In addition, from what I have read it is supposed to be 
> NP-hard. However
> my problems are usually small. 
> 
> > 1.  If you absolutely need the Frechet distance and you can 
> describe 
> > an algorithm for computing it but get stuck writing a 
> function for it, 
> > please submit another question outlining what you've tried and that 
> > obstacle you've found.
> > 
> > 	  2.  Alternatively, you might describe the more 
> general problem you 
> > are trying to solve, why you thought the Frechet distance 
> might help and 
> > invite alternative suggestions.
> 
> I have some curves (in the form of points) which are sigmoidal. I also
> have some curves which look like 2 sigmoid curves joined head to tail.
> Something like
> 
> 
>                                      -----
> 				    /
> 			           /
> 			     ------
> 		            /
> 			   /
> 			  /
> 		   ------
> 
> Now these curves can vary: in some cases the initial lower 
> tail might be
> truncated.  For the 'stepwise' sigmoidal curves, the middle step might
> not be horizontal but inclined to some degree and so on.
> 
> My goal is to be given a set of points representing a curve 
> and try and
> identify whether it is of the standard sigmoid form or of the 
> 'stepwise'
> sigmoid form.
> 
> My plan was to generate a 'canonical sigmoid curve' via the logistic
> equation and then perform a curve matching operation. Thus for a
> supplied curve that is sigmoid in nature it will match the 'canonical
> curve' to a better extent than would a curve that is stepwise 
> in nature.
> (The matching is performed after applying a Procrustes transformation)
> 
> Initially I tried using the Hausdorff distance, but this does not take
> into account the ordering of the points in the curve and did 
> not always
> give a conclusive answer. A number of references (including the one
> above) indicate that the Frechet distance is better suited for curve
> matching problems.
> 
> As you noted, evaluating the Frechet distance is non-trivial and the
> only code that I could find was some code that is dependent 
> on the CGAL
> (http://www.cgal.org/) library. As far as I could see, CGAL does not
> have any R bindings.
> 
> An alternative that I had considered was to to evaluate the distance
> matrix of the points making up the curve and then evaluating the root
> mean square error of the matrix elements for the canonical 
> curve and the
> supplied curve. My initial experiments indicated that this generally
> works but I observed some cases where a stepwise curve matched the
> canonical sigmoid better (ie lower RMSE) than an actual sigmoid curve.
> 
> Another alternative is look at a graph of the first derivative of the
> curve. A standard sigmoidal curve will result in a graph with a single
> peak, a stepwise curve like above will result in a graph with 2 peaks.
> Thus this could be reduced to a peak picking problem. The 
> problem is the
> curves I'll get are not smooth and can have small kinks - 
> this leads to
> (usually) quite small peaks in the graph of the first derivative - but
> most of the code that has been described on this list for peak picking
> also picks them up, thus making identification of the curve ambiguous.
> 
> To be honest I do not fully understand the algorithm used to evaluate
> the Frechet distance hence my request for code. However, I'm 
> not fixated
> on the Frechet distance :) If there are simpler approaches I'm open to
> them.
> 
> Thanks,
> 
> -------------------------------------------------------------------
> Rajarshi Guha <rxg218 at psu.edu> <http://jijo.cjb.net>
> GPG Fingerprint: 0CCA 8EE2 2EEB 25E2 AB04 06F7 1BB9 E634 9B87 56EE
> -------------------------------------------------------------------
> Q: What do you get when you cross a mosquito with a mountain climber?
> A: Nothing. You can't cross a vector with a scaler.
> 
> ______________________________________________
> R-help at stat.math.ethz.ch mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide! 
> http://www.R-project.org/posting-guide.html
> 
>