Measuring similarity between data

Similarity measures how alike two objects are (usually 0 to 1; larger = more alike). Dissimilarity/distance measures how different they are (minimum often 0). The choice depends on the attribute type.

Numeric attributes (distance measures)

For objects x = (x₁…xₙ) and y = (y₁…yₙ):

• Euclidean: d = √Σ(xᵢ − yᵢ)²
• Manhattan: d = Σ|xᵢ − yᵢ|
• Minkowski: d = (Σ|xᵢ − yᵢ|ʰ)^(1/h) (h = 1 Manhattan, h = 2 Euclidean, h = ∞ Chebyshev/supremum)
• Cosine similarity: cos(x, y) = (x·y)/(‖x‖‖y‖), used for documents.
• Correlation coefficient for linear relation between two objects.
• Mahalanobis distance takes account of correlation between attributes. Attributes should be normalised first so that one large-range attribute does not dominate.

Binary attributes

Using counts q (1,1), r (1,0), s (0,1), t (0,0):

• Simple matching coefficient (SMC) = (q + t)/(q + r + s + t) for symmetric attributes
• Jaccard coefficient = q/(q + r + s) for asymmetric attributes (ignores 0-0 matches)

Nominal attributes

Simple matching: d = (p − m)/p, where m = number of matching attributes and p = total attributes.

Ordinal attributes

Replace ranks by (r − 1)/(M − 1), a value from 0 to 1, then use a numeric distance.

Mixed attributes

Weighted combination of the per-attribute distances (Gower's measure).

Other

Edit distance for strings, Tanimoto/extended Jaccard, KL divergence for distributions.

Example: x = (1, 2), y = (4, 6): Euclidean = √(9 + 16) = 5; Manhattan = 3 + 4 = 7.