Measuring similarity and distance function

Measuring similarity or distance between two data points is very fundamental to many Machine Learning algorithms such as K-Nearest-Neighbor, Clustering ... etc. Depends on the nature of the data point, various measurement can be used.

Distance between numeric data points

When the dimension of data point is numeric, the general form is called Minkowski distance

( (x₁ - x₂)^p + (y₁- y₂)^p)^1/p

When p = 2, this is equivalent to Euclidean distance. When p = 1, this is equivalent to Manhattan distance.

This measure is independent of the underlying data distribution. But what if the value along the x-dimension is much bigger than that from the y-dimension. So we need to bring all of them into the same scale first. A common way is to perform a z-transform where each data point first subtract the mean value, and then divide the standard deviation.

(x₁, y₁) becomes ( (x₁ � �_x)/s_x, (y₁ � �_y)/s_y )

This measure, although taking into consideration of the distribution of each dimension, it assumes the dimension are independent of each other. But what if x-dimension and y-dimension has some correlation. To consider correlation between different dimensions, we use ...

Mahalanobis distance = (v₁^?- v₂^?)^T.CovMatrix.(v₁^?- v₂^?) where v₁^? = (x₁, y₁)

If we care about the direction of the data rather than the magnitude, then cosine distance is a common approach. It computes the dot product of the two data points divided by the product of their magnitude. Cosine distance, together with term/document matrix, is commonly used to measure the similarity between documents.

Distance between categorical data points

Since there is no ordering between categorical value, we can only measure whether the categorical value is the same or not. Basically we are measuring the degree of overlapping of attribute values. Hamming distance can be used to measure how many attributes need to changed in order to match each other. We can calculate the ratio to determine how similar (or difference) between two data points using simple matching coefficient:
noOfMatchAttributes / noOfAttributes

However, when the data point contains asymmetric binary data attributes, equality of certain value doesn't mean anything. For example, lets say the data point represents a user with attributes represent each movie. The data point contains a high dimensional binary value representing whether the user has seen the movie. (1 represent yes and 0 represent no). Given that most users only see a very small portion of all movies, if both user hasn't seen a particular movie (both value is zero), it doesn't indicate any similarity between the user. On the other hand, if both user saw the same movie (both value is one), it implies a lot of similarity between the user. In this case, equality of one should carry a much higher weight than equality of zero. This lead to Jaccard similarity :
noOfOnesInBoth / (noOfOnesInA + noOfOnesInB - noOfOnesInAandB)

Besides matching or not, if category is structured as a Tree hierarchy, then the distance of two category can be quantified by path length of their common parent. For example, "/product/spot/ballgame/basketball" is closer to "/product/spot/ballgame/soccer/shoes" than "/product/luxury/handbags" because the common parent has a longer path.

Similarity between instances containing mixed types of attributes

When the data point contain a mixed of attributes, we can calculate the similarity of each attribute (or group the attributes of the same type), and then combine them together using some weighted average.

But we have to be careful when treating asymmetric attributes where its presence doesn't mean anything.

combined_similarity(x, y) = S_{over_k}[w_k * d_k * similarity(x_k, y_k)] / S_{over_k}(d_k)

where S_{over_k}(w_k) = 1

Distance between sequence (String, TimeSeries)

In case each attribute represent an element of a sequence, we need a different way to measure the distance. For example, lets say each data point is a string (which contains a sequence of characters), then edit distance is a common measurement. Basically, edit distance is how many "modifications" (which can be insert, modify, delete) is needed to change stringA into stringB. This is usually calculated by using dynamic programming technique.

Time Series is another example of sequence data. Similar to the concept of edit distance, Dynamic Time Warp is about distorting the time dimension by adding more data points in both time series such that their square error between corresponding pairs is minimized. Where to add these data points are solved using a similar dynamic programming technique. Here is a very good paper that describe the details.

Distance between nodes in a network

In a homogenous undirected graph (nodes are of the same type), distance between nodes can be measured by the shortest path.

In a bi-partite graph, there are two types of nodes in which each node only connects to the other type. (e.g. People joining Communities). Similarity between nodes (of same type) can be measured by analyzing how similar their connected communities are.

SimRank is an iterative algorithm that compute the similarity of each type of nodes by summing the similarity between all pairs of other type of nodes that it has connected, while other type of nodes' similarity is computed in the same way.

We can also use a probabilistic approach such as RandomWalk to determine the similarity. Each people node will pass a token (label with the people's name) along a randomly picked community node which it is connected to (weighted by the strength of connectivity). Each community node will propagated back the received token back to a randomly picked people. Now the people who received the propagated token may drop the token (with a chance beta) or propagated to a randomly chosen community again. This process continues under all the tokens are die out (since they have a chance of being dropped). After that, we obtain the trace Matrix and compute the similarity based on the dot product of the tokens it receives.

Distance between population distribution

Instead of measuring distance between individual data points, we can also compare a collection of data points (ie: population) and measure the distance between them. In fact, one important part of statistics is to measure the distance between two groups of samples and see if the "difference" is significant enough to conclude they are from different populations.

Lets say the population contains members that belongs to different categories and we want to measure if population A and population B have same or different proportions of members across these categories, then we can use Chi-Square or KL-Divergence to measure their distance.

In case every member of the population has two different numeric attributes (e.g. weight and height), and we want to infer one attribute from the other if they are correlated, correlation coefficient is a measure that quantify their degree of correlation; whether these two attributes are moving along the same direction (heavier people are taller), different direction (heavier people are shorter), or independent. The correlation coefficient ranges from -1 (negatively correlated) to 0 (no correlation) to 1 (positively correlated).

If the two attributes are categorical (rather than numeric), then mutual information is a common way to measure their dependencies and give a good sense of whether knowing the value of one attribute can help inferring the other attribute.

Now if there are two judges who rank a collection of items and we are interested in the degree of agreement of their ranking order. We can use Spearman's rank coefficient to measure their degree of consensus in the ranking order.