Proximity Matrices and Dissimilarity
Proximity Matrices and Dissimilarity¶

Computer Science Dept, Ferdowsi University of Mashhad
Where this page sits¶
Sections 14.3.1-14.3.3 of Hastie et al. (2009) (pp. 503-507) contain no clustering algorithm. They come first because every method in the rest of the chapter takes a matrix of dissimilarities as its input: the numbers in that matrix decide the answer, and the algorithm only decides how those numbers are grouped. The book is blunt about the priority (p. 506):
Specifying an appropriate dissimilarity measure is far more important in obtaining success with clustering than choice of clustering algorithm.
This page covers the three sections in order:
| section | question |
|---|---|
| 14.3.1 Proximity matrices | what if the data is a table of proximities? |
| 14.3.2 Dissimilarities based on attributes | how is one attribute compared? |
| 14.3.3 Object dissimilarity | how are the attributes combined, and with what weights? |
What you should be able to do at the end¶
read a proximity matrix and say which of the four conventions (nonnegative, zero diagonal, symmetric, metric) it satisfies, and what to do when one fails;
choose an attribute dissimilarity for quantitative, ordinal and categorical variables, and say what each choice assumes;
write the weighted combination of (14.24) and explain why equal weights are not equal influence;
compute the average dissimilarity of (14.27) and use it to decide whether standardisation is a good idea for a given data set.
1. Data given directly as proximity matrix¶
Sometimes there are no attribute values at all. In social-science experiments participants are asked how different two objects are, and the answers are averaged into a number; in information retrieval the number is a similarity between documents; in psychology it comes from confusion rates. The result is an matrix with the proximity of objects and , and it is handed to the clustering algorithm as it stands.
Four conventions are almost universal, and it pays to check all four before clustering anything:
Nonnegative entries, zero diagonal: . A similarity is turned into a dissimilarity by any monotone decreasing function, for example or ; the choice of function is part of the model.
Symmetry: most algorithms assume , so an asymmetric matrix must be replaced by .
Triangle inequality : subjectively judged dissimilarities rarely satisfy it, so it must be checked, not assumed.
Comparability of scale: the entries of one matrix must be measured on one scale; mixing two surveys means rescaling one of them.
The example below is Table 14.3 of the book: twelve countries, judged pairwise by political-science students. Only the lower triangle is printed in the book.
import numpy as np
names = ["BEL", "BRA", "CHI", "CUB", "EGY", "FRA",
"IND", "ISR", "USA", "USS", "YUG", "ZAI"]
lower = { # Table 14.3 of ESL: average pairwise dissimilarities, lower triangle
"BRA": [5.58],
"CHI": [7.00, 6.50],
"CUB": [7.08, 7.00, 3.83],
"EGY": [4.83, 5.08, 8.17, 5.83],
"FRA": [2.17, 5.75, 6.67, 6.92, 4.92],
"IND": [6.42, 5.00, 5.58, 6.00, 4.67, 6.42],
"ISR": [3.42, 5.50, 6.42, 6.42, 5.00, 3.92, 6.17],
"USA": [2.50, 4.92, 6.25, 7.33, 4.50, 2.25, 6.33, 2.75],
"USS": [6.08, 6.67, 4.25, 2.67, 6.00, 6.17, 6.17, 6.92, 6.17],
"YUG": [5.25, 6.83, 4.50, 3.75, 5.75, 5.42, 6.08, 5.83, 6.67, 3.67],
"ZAI": [4.75, 3.00, 6.08, 6.67, 5.00, 5.58, 4.83, 6.17, 5.67, 6.50, 6.92],
}
D = np.zeros((len(names), len(names)))
for i, country in enumerate(names[1:], start=1):
for j, value in enumerate(lower[country]):
D[i, j] = D[j, i] = value # the table is symmetric: fill both halves
print(" " + " ".join(f"{n:>5}" for n in names))
for i, n in enumerate(names):
print(f"{n:>4} " + " ".join(f"{D[i, j]:5.2f}" for j in range(len(names)))) BEL BRA CHI CUB EGY FRA IND ISR USA USS YUG ZAI
BEL 0.00 5.58 7.00 7.08 4.83 2.17 6.42 3.42 2.50 6.08 5.25 4.75
BRA 5.58 0.00 6.50 7.00 5.08 5.75 5.00 5.50 4.92 6.67 6.83 3.00
CHI 7.00 6.50 0.00 3.83 8.17 6.67 5.58 6.42 6.25 4.25 4.50 6.08
CUB 7.08 7.00 3.83 0.00 5.83 6.92 6.00 6.42 7.33 2.67 3.75 6.67
EGY 4.83 5.08 8.17 5.83 0.00 4.92 4.67 5.00 4.50 6.00 5.75 5.00
FRA 2.17 5.75 6.67 6.92 4.92 0.00 6.42 3.92 2.25 6.17 5.42 5.58
IND 6.42 5.00 5.58 6.00 4.67 6.42 0.00 6.17 6.33 6.17 6.08 4.83
ISR 3.42 5.50 6.42 6.42 5.00 3.92 6.17 0.00 2.75 6.92 5.83 6.17
USA 2.50 4.92 6.25 7.33 4.50 2.25 6.33 2.75 0.00 6.17 6.67 5.67
USS 6.08 6.67 4.25 2.67 6.00 6.17 6.17 6.92 6.17 0.00 3.67 6.50
YUG 5.25 6.83 4.50 3.75 5.75 5.42 6.08 5.83 6.67 3.67 0.00 6.92
ZAI 4.75 3.00 6.08 6.67 5.00 5.58 4.83 6.17 5.67 6.50 6.92 0.00
The first three conventions are easy to test, and this matrix passes all of them.
print("nonnegative entries :", D.min() >= 0)
print("zero diagonal :", np.allclose(np.diag(D), 0))
print("symmetric :", np.allclose(D, D.T))nonnegative entries : True
zero diagonal : True
symmetric : True
The fourth is the interesting one. It also passes, and that is worth noticing because it is not guaranteed by the way such numbers are produced. Squaring every entry is a monotone increasing transformation, which is exactly the kind of change an analyst might make to emphasise large differences; it preserves the three easy conventions and destroys the fourth.
import itertools
def triangle_violations(M, tol=1e-12):
"""All ordered triples (a, b, c) with d(a, b) > d(a, c) + d(c, b)."""
out = []
for a, b, c in itertools.permutations(range(len(M)), 3):
if M[a, b] > M[a, c] + M[c, b] + tol:
out.append((a, b, c))
return out
print("violations in Table 14.3 :", len(triangle_violations(D)))
violations = triangle_violations(D ** 2)
print("violations after squaring them:", len(violations))
for a, b, c in violations[:3]:
print(f" d({names[a]},{names[b]}) = {D[a, b] ** 2:.2f} > "
f"d({names[a]},{names[c]}) + d({names[c]},{names[b]}) = "
f"{D[a, c] ** 2 + D[c, b] ** 2:.2f}")violations in Table 14.3 : 0
violations after squaring them: 56
d(BEL,BRA) = 31.14 > d(BEL,USA) + d(USA,BRA) = 30.46
d(BEL,CHI) = 49.00 > d(BEL,USA) + d(USA,CHI) = 45.31
d(BEL,CHI) = 49.00 > d(BEL,YUG) + d(YUG,CHI) = 47.81
So “is this a distance?” is a property of the numbers you hand to the algorithm, not of the objects being clustered. An algorithm that only uses the ordering of the entries cannot notice the difference; one that adds and multiplies them can. That distinction returns on the hierarchical clustering page, where single and complete linkage turn out to depend on ordering alone.
This is also why K-medoids works and K-means does not on data like Table 14.3: K-means needs coordinates to average, and here there are none.
2. Dissimilarities computed from attributes¶
Usually there are attributes: measurements for objects and variables . The recipe of the book is to define a dissimilarity per attribute and add them up:
with the default, by a wide margin,
The default is not universal, and the alternatives follow from the type of the variable:
| type of variable | dissimilarity of two values | note |
|---|---|---|
| quantitative | , , or | squared error emphasises large differences; absolute error does not |
| ordinal | treat the codes as the numbers | (14.23), order preserved, spacing invented |
| categorical | a loss matrix , , | unequal losses are allowed and encode domain knowledge |
Two warnings come with the table. For quantitative variables, clustering by correlation (14.22) is the same as clustering by squared distance after standardising each observation: if the rows are centred and scaled, then , so the two dissimilarities are monotone functions of each other. The cell below checks the identity on two iris flowers.
from sklearn.datasets import load_iris
iris = load_iris()
X = iris.data
y = iris.target
# each observation centred and scaled to unit variance, so that sum_j x_ij^2 = p
Z = (X - X.mean(axis=1, keepdims=True)) / X.std(axis=1, keepdims=True)
i, k = 0, 60
a, b = Z[i], Z[k]
rho = np.corrcoef(a, b)[0, 1]
p = X.shape[1]
print(f"correlation of the two flowers : {rho:.4f}")
print(f"squared distance between the scaled rows : {((a - b) ** 2).sum():.4f}")
print(f"2 p (1 - rho) : {2 * p * (1 - rho):.4f}")correlation of the two flowers : 0.7232
squared distance between the scaled rows : 2.2144
2 p (1 - rho) : 2.2144
For ordinal variables the codes are replaced by evenly spaced numbers in and then treated as quantitative. The transformation is a modelling decision: it asserts that the step from “can’t stand” to “dislike” is the same size as the step from “like” to “terrific”.
grades = ["A", "B", "C", "D", "F"]
M = len(grades)
scale = {g: (r + 1 - 0.5) / M for r, g in enumerate(grades)}
print({g: round(v, 2) for g, v in scale.items()}){'A': 0.1, 'B': 0.3, 'C': 0.5, 'D': 0.7, 'F': 0.9}
For categorical variables a loss matrix says what each confusion costs. The default is “any two different values differ by 1”, which is what a naive mismatch count does; a domain-specific matrix can say, for instance, that confusing black with red is a smaller error than confusing black with blond.
colours = ["black", "blond", "red"]
index = {c: r for r, c in enumerate(colours)}
L = np.array([[0.0, 1.0, 0.5], # black
[1.0, 0.0, 1.0], # blond
[0.5, 1.0, 0.0]]) # red
print("d(black, red) =", L[index["black"], index["red"]],
" (the default would be 1)")
print("d(black, blond)=", L[index["black"], index["blond"]])d(black, red) = 0.5 (the default would be 1)
d(black, blond)= 1.0
3. Object dissimilarity: combining the attributes¶
Once every attribute has its own dissimilarity, they are combined by a weighted average. The weights are constrained to sum to one, so that stays on the scale of the :
Setting all weights equal does not give all attributes equal influence. The influence of attribute is , where
is the average dissimilarity on that attribute; an attribute whose values are spread over a wide range contributes more no matter what its weight says. Equal influence needs , and for squared error the identity
makes the weight explicit: . That is exactly what standardising each attribute does. The cell below verifies (14.27) on the iris data.
X = iris.data
n = len(X)
dbar = np.zeros(X.shape[1])
for j in range(X.shape[1]):
diffs = (X[:, j][:, None] - X[:, j][None, :]) ** 2
dbar[j] = diffs.sum() / n ** 2
print("dbar_j :", np.round(dbar, 3))
print("2 * var_j :", np.round(2 * X.var(axis=0), 3))
print("ratio :", np.round(dbar / (2 * X.var(axis=0)), 12))dbar_j : [1.362 0.377 6.191 1.154]
2 * var_j : [1.362 0.377 6.191 1.154]
ratio : [1. 1. 1. 1.]
Standardisation is therefore not a neutral preprocessing step: it is a statement that every attribute deserves the same influence on the distance. When the groups are separated by one attribute that also carries the most variance, this statement is wrong, and equalising the attributes can obscure groups that were obvious before. ESL Figure 14.5 is the standard picture of that failure: two well-separated groups, a second attribute on a much larger scale, and a clustering that follows the scale instead of the groups.
The experiment below runs K-means on the iris data twice, once on the raw attributes and once on standardised ones, and reports the agreement with the species labels. Read the two rows as “how much did the rescaling matter here?”
import warnings
from sklearn.cluster import KMeans
from sklearn.metrics import adjusted_rand_score
warnings.filterwarnings("ignore", message="KMeans is known to have a memory leak")
Z_std = (X - X.mean(axis=0)) / X.std(axis=0)
for name, Z in [("raw", X), ("standardised", Z_std)]:
km = KMeans(n_clusters=3, n_init=10, random_state=0).fit(Z)
print(f"{name:>13}: within-cluster SS {km.inertia_:8.2f} "
f"ARI with species {adjusted_rand_score(y, km.labels_):.3f}") raw: within-cluster SS 78.85 ARI with species 0.730
standardised: within-cluster SS 139.82 ARI with species 0.620
Two further remarks from the section, both practical:
Different weights are a modelling decision, not a technicality. If the question is “which tumours are alike?”, the genes that matter are the ones known to matter biologically; giving all 6830 of them equal influence is a choice, and usually a bad one.
Missing values. The common recipe is to compute from the attributes that both observations have, and to drop a pair that shares no measured attribute. Imputing the mean or median is the alternative, and for categorical variables “missing” can be treated as just another value - if it is reasonable that two objects are similar because both fail to report the same variable.
Summary¶
Every clustering method in this chapter is a function of a dissimilarity matrix; data sometimes arrives as that matrix, and then there are no coordinates to average.
Check the conventions: nonnegative, zero diagonal, symmetric, and - separately
whether the entries behave like a metric. Squaring them keeps the first three and can break the fourth.
The attribute dissimilarity depends on the variable type: squared or absolute error, correlation, an ordinal rescaling, or a loss matrix for categorical values.
Attributes are combined in a convex combination (14.24), and the effective influence of attribute is , not . Equal weights give influence proportional to the variance; standardising equalises it, which is sometimes exactly what you do not want.
Exercises¶
Turn the similarity matrix back into Table 14.3 by inverting the transformation. Which clustering method in this course can work on the similarities directly, and which cannot?
Apply the monotone transformation to Table 14.3 and compare the 3-medoid solution with the one on the K-medoids page. Did the medoids move?
Compute for the four iris attributes and the corresponding weights . Which attribute has the largest influence after standardisation, and which had it before?
Construct three objects and two quantitative attributes such that K-means on the raw data recovers two obvious groups and K-means on the standardised data does not. (Hint: make the separating attribute the high-variance one.)
With a missing value in one coordinate of one observation, compute the dissimilarity matrix both by dropping the pair and by mean imputation, and cluster. Is the difference visible?
Write the loss matrix for three eye colours such that blue/green is a smaller error than blue/brown, and explain what claim about the domain that matrix makes.
Sources¶
The conventions, (14.20)-(14.25), the discussion of standardisation and the quotation: §14.3.1-14.3.3 of Hastie et al. (2009), pp. 503-507.
Table 14.3 and the country survey: Kaufman and Rousseeuw (1990), cited there; the data are reused on the K-medoids page.
The iris data:
sklearn.datasets.load_iris, the same data set used in Clustering-Part1.
- Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd ed.). Springer. 10.1007/978-0-387-84858-7