What is a metric can I use to calculate the distance between labels?

Question

Let's say we have a set of labels of the same length, and we need to find the distance between them.

In the case of binary labels, one can use the Hamming distance. For example, if $l_1 = 01101$ and $l_2 = 00111$, then $d(l_1, l_2) = 2$.

In my case, labels are formed from the alphabet $A=\{a, b, c, d, e\}$, so the length of the alphabet is $|A|=5$, and the length of each label is $n=4$.

In my case, an ordinal scale is applicable for letters from alphabet $A$:

$$a < b < c < d < e.$$

Examples of labels: deed, aaaa, aaad, aaae, dada, cccd.

Edit. The Hemming distance for three labels aaaa, aaad, aaae gives $$d(aaaa, aaad) = d(aaaa, aaae)$$ but I am looking for a metric which will distinguish $d$ and $e$ and return $$d(aaaa, aaad)<d(aaaa, aaae)$$ because $d<e$.

Edit 2.

For creating a label we use a threshold $T \in \mathbf{R}$ and apply the next function for the $i$-th element of $X=(x_1, x_2, \ldots, x_n)$: \begin{equation} f(x_i) = \begin{cases} a, & x_i \leq -T, \\ b, & -T < x_i \leq 0, \\ c, & x_i = 0, \\ d, & 0 < x_i \leq T, \\ e, & x_i >T. \ \end{cases} \end{equation} Finally, we use the concatination operator $\&$, for example, $a \& a \& a \& a= aaaa$.

Question. What a metric can I use to calculate the distance between labels?

Answer 1

It really depends on what kind of words you are referring to. There are two distance that I wish to talk about :

1. Edit Distance

   If you wish to capture difference in terms of how different two sequence are, you can use levenshtein distance or Damerau-Levenshtein distance. Mathematically for a word $A$ or $B$, the levenshtein distance is the least number of moves/operations to transform word $A$ to word $B$. This is what you might be looking for when your definition of word as a sequence of alphabet.

2. Context Similarity

   For words we can also talk about contextual meaning of each word. If the two words are related or have similar meaning then we expect this measure to be small. This can be implemented with word2vec. Basically we train our model in unsupervised manner and will have it's vectorized representation and we measure the distance by comparing the two vectors. The most popular way for measuring the distance is using cosine similarity.

The two distances does not correlate with each other. For example, deed and deer, the edit distance is small (in fact it is equals to 1), but the similarity distance will be big since those words are not related.

Edit : Since the asker explained his specific case.

You can consider using Earth Mover's/Wasserstein distance.

This is my idea how you might approach this. Suppose you wish to imply ordering for each letter such that $a < b < c < d < e$ and you have 3 words on your letter. Suppose you have a word $abc$, for 3 letters let $t_1=0,t_2=1,t_3=2$, and $w_1=a,w_2=b,w_3=c$. Also let $T$ be a key value mapping between letter and some arbitrary value and should reflect your ordering.

\begin{equation} f(x) = \begin{cases} T(w_i), & t_i \leq x < t_{i+1}, \\ 0, & otherwise\\ \end{cases} \end{equation} Forgive my poor use of notations though, but the idea is (if we let $T(a)=0.8$ and $T(b)=1.5$) for example you have a function that have value $f(x)=0.8$ for $x\in[0,1]$ and then value of $f(x)=1.5$ for $x\in[1,2]$. Now you can see this as an unnormalized distribution and you could calculate earthmovers/wasserstein distance. This is just some random idea, might not necessarily make sense though.

Here is a useful link.

Answer 2

You can still use the Hamming distance for 5 letters. Another metric than you can use is the Levenshtein distance - the minimum number of single-character edits required to change one word into the other.

If there is some meaning to the order of your letters, such that for example the distance between a and c is larger than the distance between a and b, then you can use a metric such as the euclidean distance.

Answer 3

It sounds to me like you may be looking for a simple sum of absolute differences (also called L1 distance).

Assuming that we can extend your ordinal relation $a < b < c < d < e$ into a metric (e.g. $b - a = c - b = 1$, $e - a = 4$, etc.), then you can let the difference between two words of the same length be the sum of absolute differences of symbols in the same position.

For example, $ abcd - edcb = |a-e| + |b-d| + |c-c| + |d-b| = 4 + 2 + 0 + 2 = 8$.

In the case of an alphabet of two symbols, this is identical to the Hamming distance, and like the Hamming distance it doesn't have any idea of context or transposition — $aaea$ and $aeaa$ are separated by a distance of 8, just as much as $aaaa$ and $cccc$.

Answer 4

Usually when people talk about word similarity, they refer to something like Yohanes Alfredo's answer.

In your case, you want to take into account the sort order of the characters. In that case, it might be that hobbs has the answer you need.

Do you want to find distance according to the overall sort order of the word? In other words, do you want $$d(aaaa, aaad)<d(aaaa, daaa)$$ because words that start with the same letter are closer to each other in the dictionary than words that differ in other letters?

If so, then you're better off calculating a value of each word using the following algorithm that takes into account the position of the letters in the word.

initially set value1 = 0
for i in 1 to length:
    value1 = value1 + (alphabetSize ^ i) * letters1[length - i]
initially set value2 = 0
for i in 1 to length:
    value2 = value2 + (alphabetSize ^ i) * letters2[length - i]
distance = abs(value1 - value2)

What this is doing is treating each word as a number written in base alphabetSize.

I apologize for writing this in pseudocode. Using mathematical notation with capital Sigma would be clearer but I don't know my way around the typography.