Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

Proximity Matrices and Dissimilarity

English · فارسی

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:

sectionquestion
14.3.1 Proximity matriceswhat if the data is a table of proximities?
14.3.2 Dissimilarities based on attributeshow is one attribute compared?
14.3.3 Object dissimilarityhow 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 2⋅varj2 \cdot \mathrm{var}_j 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 N×NN \times N matrix D\mathbf{D} with dii′d_{ii'} the proximity of objects ii and i′i', 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:

  1. Nonnegative entries, zero diagonal: dii=0d_{ii} = 0. A similarity is turned into a dissimilarity by any monotone decreasing function, for example d=1−sd = 1 - s or d=1/s−1d = 1/s - 1; the choice of function is part of the model.

  2. Symmetry: most algorithms assume dii′=di′id_{ii'} = d_{i'i}, so an asymmetric matrix must be replaced by (D+DT)/2(\mathbf{D} + \mathbf{D}^T)/2.

  3. Triangle inequality dii′≤dik+dki′d_{ii'} \le d_{ik} + d_{ki'}: subjectively judged dissimilarities rarely satisfy it, so it must be checked, not assumed.

  4. 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.

       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.

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.

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 xijx_{ij} for objects i=1,…,Ni = 1,\dots,N and variables j=1,…,pj = 1,\dots,p. The recipe of the book is to define a dissimilarity per attribute and add them up:

D(xi,xi′)=∑j=1pdj(xij,xi′j),(14.20)D(x_i, x_{i'}) = \sum_{j=1}^{p} d_j(x_{ij}, x_{i'j}), \qquad \text{(14.20)}

with the default, by a wide margin,

dj(xij,xi′j)=(xij−xi′j)2.(14.21)d_j(x_{ij}, x_{i'j}) = (x_{ij} - x_{i'j})^2 . \qquad \text{(14.21)}

The default is not universal, and the alternatives follow from the type of the variable:

type of variabledissimilarity of two valuesnote
quantitative(⋅)2(\cdot)^2, ∣⋅∣\lvert \cdot \rvert, or 1−ρ1 - \rhosquared error emphasises large differences; absolute error does not
ordinaltreat the codes as the numbers r−1/2M\frac{r - 1/2}{M}(14.23), order preserved, spacing invented
categoricala loss matrix Lrr′L_{rr'}, Lrr=0L_{rr} = 0, Lrr′=1L_{rr'} = 1unequal 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 ∑j(xij−xi′j)2=2p (1−ρ(xi,xi′))\sum_j (x_{ij} - x_{i'j})^2 = 2p\,(1 - \rho(x_i, x_{i'})), so the two dissimilarities are monotone functions of each other. The cell below checks the identity on two iris flowers.

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 [0,1][0, 1] 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”.

{'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.

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 DD stays on the scale of the djd_j:

D(xi,xi′)=∑j=1pwj dj(xij,xi′j),∑jwj=1.(14.24)D(x_i, x_{i'}) = \sum_{j=1}^{p} w_j \, d_j(x_{ij}, x_{i'j}), \qquad \sum_j w_j = 1 . \qquad \text{(14.24)}

Setting all weights equal does not give all attributes equal influence. The influence of attribute jj is wjdˉjw_j \bar d_j, where

dˉj=1N2∑i=1N∑i′=1Ndj(xij,xi′j)(14.25)\bar d_j = \frac{1}{N^2} \sum_{i=1}^{N} \sum_{i'=1}^{N} d_j(x_{ij}, x_{i'j}) \qquad \text{(14.25)}

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 wj=1/dˉjw_j = 1/\bar d_j, and for squared error the identity

dˉj=1N2∑i∑i′(xij−xi′j)2=2⋅varj(14.27)\bar d_j = \frac{1}{N^2} \sum_i \sum_{i'} (x_{ij} - x_{i'j})^2 = 2 \cdot \mathrm{var}_j \qquad \text{(14.27)}

makes the weight explicit: wj=1/(2 varj)w_j = 1/(2\,\mathrm{var}_j). That is exactly what standardising each attribute does. The cell below verifies (14.27) on the iris data.

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?”

          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 D(xi,xi′)D(x_i, x_{i'}) 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 jj is wjdˉjw_j \bar d_j, not wjw_j. Equal weights give influence proportional to the variance; standardising equalises it, which is sometimes exactly what you do not want.

Exercises

  1. Turn the similarity matrix sii′=1/(1+dii′)s_{ii'} = 1/(1 + d_{ii'}) back into Table 14.3 by inverting the transformation. Which clustering method in this course can work on the similarities directly, and which cannot?

  2. Apply the monotone transformation d↦d3d \mapsto d^3 to Table 14.3 and compare the 3-medoid solution with the one on the K-medoids page. Did the medoids move?

  3. Compute dˉj\bar d_j for the four iris attributes and the corresponding weights 1/dˉj1/\bar d_j. Which attribute has the largest influence after standardisation, and which had it before?

  4. 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.)

  5. 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?

  6. 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.

References
  1. 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