1
$\begingroup$

Need to determine similarity of sentences in some body of text. The sentences are not exactly human language (internal technical terms and abbreviations), so word2vec and similar approach is not useful.

Trying to line up all the sentences in 1-dimensional space and apply clustering. For that purpose I'm thinking of using some string distance measure from empty string to the given string.

Question: is there any string distance measure that satisfies triangle equality (d(a, b) = d(a) + d(b))? Distances like Levenshtein distance satisfy triangle inequality, while it seems to me distance that gives equality would be a much better predictor of "closeness" for strings (considering they are lined up in 1-d space by distance from empty string, that is strings are close if abs(d(a, '') - d(b, '') < ε)

Clarification: From definition of metric distance properties 1, 2, 3, but property 4 should be d(x, z) = d(x, y) + d(y, z)

$\endgroup$

put on hold as unclear what you're asking by whuber Aug 22 at 12:58

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ You may interest in Levenshtein distance en.wikipedia.org/wiki/Levenshtein_distance. $\endgroup$ – Ben Dai Dec 4 '17 at 7:22
  • $\begingroup$ As far as I understand, Levenshtein distance doesn't produce strong equality for all cases of triangle inequality. $\endgroup$ – ssanin82 Dec 4 '17 at 7:24
  • $\begingroup$ The relation you cite is not the triangle inequality (it isn't even an inequality): it's additivity. Is that what you really meant? $\endgroup$ – whuber Aug 22 at 12:58
0
$\begingroup$

Your approach to line up the strings in a 1D-space is not the way to go. Instead use a distance like Levenshtein to build up the distance matrix between all strings and then use a clustering method that can work on metric spaces, e.g. agglomerative hierarchical linkage clustering (e.g. single-linkage).

$\endgroup$

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