Measuring Distance for Categorical Data

In this post, we will talk about measuring distance for categorical observations. Categorical dimensions can always be translated into numeric dimensions, and numeric distance metrics continue to be meaningful. However, for purely categorical observations there are some special metrics which can be used.

There are two cases for purely categorical data: where number of dimensions is not constant across observations, and where they are. Example of former is text documents where number of words is number of dimensions in each document. Finding distances among documents is one the most common tasks in text analytics and Natural Language Processing. Example of later is from bio-informatics where gene-sequence is constant length categorical sequence of genotypes.

For purpose of demonstrations in this post, we shall use following three sentences as three observations among which we want to compute distances. Metrics discussed shall apply equally well to cases where number of dimensions are constant.

• I think, therefore I am
• Can you think?
• I don’t think, therefore I don’t know who I am

Let x_iw refer to count of word w in sentence i. Using “bag of word” approach (That is, we ignore order of words in the sentence) we can transform these sentences into following vectors:

Distance Metrics

Cosine similarity is measure of number of common words in two observations, scaled by length of sentences. Cosine distance is computed as

Cosine distance between sentence 1 and sentence 2 is computed as…

Number of common words: 1 (“think”)

Length of sentence 1: 4 (“I” repeated twice)

Length of sentence 2: 3

Similarly,

Thus sentence 1 and 3 are closest, but sentence 1 is closer to sentence 2 than sentence 3.

Tanimato coefficient extends idea of Cosine distance and changes the normalization figure in denominator. Tanimato distance is computed as

Tanimato distance between sentence 1 and 2 is

Jaccard distance is one minus Jaccard similarity, which is number of common words in two sentences divided by total number of unique words. This is particularly popular distance metric for text comparison, because it is fairly fast to compute as we are essentially counting number of common and unique words without complex mathematical computation.

Sorensen–Dice coefficient is variation of Jaccard’s and computed as

Hamming distance is most commonly used for equal length documents, and is equal to number of places changes are required to convert one document into another. This is computationally expensive metric as it also takes into account order of words. Sentence 1 can be converted into sentence 2 in following series of operations –

Thus, hamming distance d₁₂ = 6, and d₁₃ = 4 (insert “don’t”, “don’t”, “know”, “who”) and d₂₃ = 11 (drop “can”, “you”; insert “I”, “don’t”, “therefore”, “I”, “don’t”, “know”, “who”, “I”, “am”).

String Edit distance is generalization of Hamming distance and is O(n²)computational operation. While Hamming distance permits only ‘insert’ and ‘drop’ operation, String Edit distance permits third operation of ‘replace’ which is equivalent to one ‘insert’ and ‘drop’ combined. Further, Hamming distance computation weighs each operation (insert or drop) equally, String Edit distance can weight insert, replace, and delete separately, in counting number of operations. However, commonly applied variant works with equal weight for all three actions. String Edit distance between Sentence 1 and sentence 2 is 5 as shown in table below.

Remember that…

• In our examples, we have used words as basic unit of observation, but same can be done at character level.
• Tanimato and Cosine distance can also be computed consider x_iw a binary number rather than word count.
• Different distance measures give distance in different units and hence one must be cautious about subsequent use of distance number, and remember that distances only makes sense in relative terms, and not in absolute. Distance between A and B can be compared to that between A and C, but by itself has no meaning.
• Most of these metrics do not follow triangle equality (can you prove?) and hence user is advised to remember if that is important.