-1
$\begingroup$

how to measure similarity? and what edit or transformation distance means? I have looked in the literature and all give some complicated, fancy explanations, except one who used the Simpson family to demonstrate how to calculate the distance measure

Still really don't get what edit distance term means ? should we narrow the differences to reach the similarity? but for how far and what is the threshold to consider two or more objects similar or different

$\endgroup$

1 Answer 1

2
$\begingroup$

Similarity is usually inverse proportional to the distance between two objects. What a distance between any two objects mean is typically very application specific.

Consider for instance the Levenshtein distance (also string edit distance)[1], where you want to measure the distance between two strings a and b. "the edit distance d(a, b) is the minimum-weight series of edit operations that transforms a into b."[1]. In this statement, it is still left out, how we define "edit operations", which in case of the Levenshtein distance are 1. Insertion (of a character of the string) 2. Deletion (of a character of the string) 3. Substitution (of a character of the string)

but this could be also others! (E.g. some other distances use only Insertion+Deletion).

So, the L. distance is basically asking: Given these 3 operations, how can I reach from one string a, another string b "in the fastest way"? And how long is that way (i.e. number of operations)?

Example: d("car", "star") = 2

-> 1. Substitute "c" with "t"

-> 2. Insert "s"

So, for your application you're basically free to decide on how distance is computed and from that similarity can be derived. (The smaller the defined distance, the more similar are two objects). Note however, that distances must obey following properties:

d(x,x) = 0

d(x,y) = d(y,x) (Symmetry)

d(x,z) <= d(x,y) + d(y,z) (Triangle inequality)

I don't get quite what you mean by "how far and what is the threshold[...]". Usually, you set up a distance metric for some other algorithm, which uses it and comes up with a final configuration (e.g. K-Means where you get K clusters of your data given your distance).

A very interesting and relatively new research topic related to that is the so called "Metric Learning" [2] where you can use learning algorithms that will find a suitable distance for your dataset.

[1] https://en.wikipedia.org/wiki/Edit_distance

[2] Kulis, Brian. "Metric learning: A survey." Foundations and Trends® in Machine Learning 5.4 (2013): 287-364.

I hope that helps a bit! :)

$\endgroup$
1
  • $\begingroup$ Nice answer--welcome to our site! $\endgroup$
    – whuber
    Aug 19, 2017 at 16:07

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.