# Clustering : une vision unifiée pour une utilisation éclairée - Partie 2 Evaluation d'une méthode de clustering

C Biernacki

► To cite this version:

C Biernacki. Clustering: une vision unifiée pour une utilisation éclairée - Partie 2 Evaluation d'une méthode de clustering. Doctoral. France. 2023. hal-04370753

HAL Id: hal-04370753

https://inria.hal.science/hal-04370753v1

Submitted on 3 Jan 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>

<figure><img src="image_7.png" /></figure>

<figure><img src="image_8.png" /></figure>

<figure><img src="image_9.png" /></figure>

Clustering : une vision unifiée pour une utilisation éclairée
—
**Partie 2**

Evaluation d'une méthode de clustering

C. Biernacki

Ateliers statistiques de la SFdS, 15 et 16 juin 2023, IHP, Paris

<figure><img src="image_10.png" /></figure>

<figure><img src="image_11.png" /></figure>

<figure><img src="image_12.png" /></figure>

<figure><img src="image_13.png" /></figure>
<figure><img src="image_14.png" /></figure>

<figure><img src="image_15.png" /></figure>

<figure><img src="image_16.png" /></figure>

<figure><img src="image_17.png" /></figure>

<figure><img src="image_18.png" /></figure>

<figure><img src="image_19.png" /></figure>

<figure><img src="image_20.png" /></figure>

## Outline

1. Data factor

2. Dissimilarity factor (and co)

3. Algorithm factor

4. Number of clusters factor

5. User factor

6. Experiments

7. To go further

<figure><img src="image_21.png" /></figure>

<figure><img src="image_22.png" /></figure>

<figure><img src="image_23.png" /></figure>

<figure><img src="image_24.png" /></figure>

<figure><img src="image_25.png" /></figure>

<figure><img src="image_26.png" /></figure>

<figure><img src="image_27.png" /></figure>

<figure><img src="image_28.png" /></figure>

<figure><img src="image_29.png" /></figure>

<figure><img src="image_30.png" /></figure>

<figure><img src="image_31.png" /></figure>
<figure><img src="image_32.png" /></figure>

<figure><img src="image_33.png" /></figure>

<figure><img src="image_34.png" /></figure>

<figure><img src="image_35.png" /></figure>

<figure><img src="image_36.png" /></figure>

<figure><img src="image_37.png" /></figure>

<figure><img src="image_38.png" /></figure>

The variable effect

■ **Medicine<fnref n="1" />**: diseases may be classified by etiology (cause), pathogenesis (mechanism by which the disease is caused), or by symptom(s). Alternatively, diseases may be classified according to the organ system involved, though this is often complicated since many diseases affect more than one organ.

■ And so on...

<figure><img src="image_39.png" /></figure>

<figure><img src="image_40.png" /></figure>

<figure><img src="image_41.png" /></figure>

<figure><img src="image_42.png" /></figure>

<footnote n="1">¹Nosologie méthodique, dans laquelle les maladies sont rangées par classes, suivant le système de Sydenham, & l'ordre des botanistes, par François Boissier de Sauvages de Lacroix. Paris, Hérisant le fils, 1771</footnote>
<figure><img src="image_43.png" /></figure>

<figure><img src="image_44.png" /></figure>

<figure><img src="image_45.png" /></figure>

<figure><img src="image_46.png" /></figure>

<figure><img src="image_47.png" /></figure>

<figure><img src="image_48.png" /></figure>

<figure><img src="image_49.png" /></figure>

<figure><img src="image_50.png" /></figure>

Need to compare partitions: empirical error rate

■ Two partitions z and ˆz

■ τ: all permutations on {1, ..., K}

■ Empirical error rate

$$ \text{err}(z, \hat{z}) = \frac{1}{n} \min_{\tau} \sum_{i=1}^{n} \mathbb{I}_{\{z_i = \tau(\hat{z}_i)\}} \in \left\{ 0, \frac{K-1}{K} \right\} $$

■ Partitions are closer when err is small

■ Restricted to compare partition with the same number of clusters

■ Example

<table><thead><tr><th>z</th><th>ẑ</th><th>err(z, ẑ)</th></tr></thead><tbody><tr><td>G<sub>1</sub> = {a, b, c}</td><td>Ĝ<sub>1</sub> = {e, f}</td><td>1/6 min{5, 1} = 1/6</td></tr><tr><td>G<sub>2</sub> = {d, e, f}</td><td>Ĝ<sub>2</sub> = {a, b, c, d}</td><td></td></tr></tbody></table>

<figure><img src="image_51.png" /></figure>

<figure><img src="image_52.png" /></figure>

<figure><img src="image_53.png" /></figure>

<figure><img src="image_54.png" /></figure>

<figure><img src="image_55.png" /></figure>

<figure><img src="image_56.png" /></figure>

<figure><img src="image_57.png" /></figure>

<figure><img src="image_58.png" /></figure>

<figure><img src="image_59.png" /></figure>

<figure><img src="image_60.png" /></figure>

<figure><img src="image_61.png" /></figure>

<figure><img src="image_62.png" /></figure>

<figure><img src="image_63.png" /></figure>

<figure><img src="image_64.png" /></figure>
<figure><img src="image_65.png" /></figure>

<figure><img src="image_66.png" /></figure>

<figure><img src="image_67.png" /></figure>

<figure><img src="image_68.png" /></figure>

<figure><img src="image_69.png" /></figure>

<figure><img src="image_70.png" /></figure>

<figure><img src="image_71.png" /></figure>

Need to compare partitions: rand index

■ Two partitions z and ź

■ A measure on basis of agreement vs. disagreement between object pairs

■ Not limited to the same number of clusters between partitions

■ Rand index [Rand 1971]

■ A: #pairs of elements in x that are in the same subset in z and in the same subset in ź

■ B: #pairs of elements in x that are in different subsets in z and in different subsets in ź

■ C: #pairs of elements in x that are in the same subset in z and in different subsets in ź

■ D: #pairs of elements in x that are in different subsets in z and in the same subset in ź

$$ \text{rand}(z, \hat{z}) = \frac{A + B}{A + B + C + D} = \frac{\text{nb. agree}}{\text{nb. agree} + \text{nb. disagree}} \in \{0, 1\} $$

■ Partitions are closer when rand is high

■ Example

<table><thead><tr><th>z</th><th>ŷ</th><th>intermediate</th><th>rand(z, ŷ)</th></tr></thead><tbody><tr><td>G<sub>1</sub> = {a, b, c}</td><td>Ĝ<sub>1</sub> = {a, b}</td><td>A = 2, B = 7</td><td>0.6</td></tr><tr><td>G<sub>2</sub> = {d, e, f}</td><td>Ĝ<sub>2</sub> = {c, d, e}</td><td>C = 4, D = 2</td><td></td></tr><tr><td>Ĝ<sub>3</sub> = {f}</td><td></td><td></td><td></td></tr></tbody></table>

■ Caution: use the adjusted rand index [Hubert and Arabie 1985] to compare rand(z, ź) and rand(z, ŵ) when K̃ ≠ K̃

<figure><img src="image_72.png" /></figure>
<figure><img src="image_73.png" /></figure>

<figure><img src="image_74.png" /></figure>

<figure><img src="image_75.png" /></figure>

<figure><img src="image_76.png" /></figure>

<figure><img src="image_77.png" /></figure>

<figure><img src="image_78.png" /></figure>

<figure><img src="image_79.png" /></figure>

Prostate cancer data: variable detail

<table><thead><tr><th>Covariate</th><th>Abbreviation</th><th>Number of Levels (if categorical)</th></tr></thead><tbody><tr><td>Age</td><td>Age</td><td></td></tr><tr><td>Weight</td><td>Wt</td><td></td></tr><tr><td>Performance rating</td><td>PF</td><td>4</td></tr><tr><td>Cardiovascular disease history</td><td>HX</td><td>2</td></tr><tr><td>Systolic Blood pressure</td><td>SBP</td><td></td></tr><tr><td>Diastolic blood pressure</td><td>DBP</td><td></td></tr><tr><td>Electrocardiogram code</td><td>EKG</td><td>7</td></tr><tr><td>Serum haemoglobin</td><td>HG</td><td></td></tr><tr><td>Size of primary tumour</td><td>SZ</td><td></td></tr><tr><td>Index of tumour stage and histologic grade</td><td>SG</td><td></td></tr><tr><td>Serum prostatic acid phosphatase</td><td>AP</td><td></td></tr><tr><td>Bone metastases</td><td>BM</td><td>2</td></tr></tbody></table>

<figure><img src="image_80.png" /></figure>

<figure><img src="image_81.png" /></figure>

<figure><img src="image_82.png" /></figure>

<figure><img src="image_83.png" /></figure>

<figure><img src="image_84.png" /></figure>

<figure><img src="image_85.png" /></figure>

<figure><img src="image_86.png" /></figure>

<figure><img src="image_87.png" /></figure>

<figure><img src="image_88.png" /></figure>

<figure><img src="image_89.png" /></figure>

<figure><img src="image_90.png" /></figure>

<figure><img src="image_91.png" /></figure>

<figure><img src="image_92.png" /></figure>
<figure><img src="image_93.png" /></figure>

<figure><img src="image_94.png" /></figure>

<figure><img src="image_95.png" /></figure>

<figure><img src="image_96.png" /></figure>

<figure><img src="image_97.png" /></figure>

<figure><img src="image_98.png" /></figure>

<figure><img src="image_99.png" /></figure>

Prostate cancer data: partition according to retained variables

<table><thead><tr><th rowspan="2"></th><th colspan="2">quantitative</th><th colspan="2">categorical (raw)</th><th colspan="2">mixing quali/quanti</th></tr><tr><th colspan="2">err=9.46%</th><th colspan="2">err=47.16%</th><th colspan="2">err=8.63%</th></tr><tr><th></th><th>1</th><th>2</th><th>1</th><th>2</th><th>1</th><th>2</th></tr></thead><tbody><tr><th>Stage 3</th><td>247</td><td>26</td><td>142</td><td>131</td><td>252</td><td>21</td></tr><tr><th>Stage 4</th><td>19</td><td>183</td><td>120</td><td>82</td><td>20</td><td>182</td></tr></tbody></table>

* Partition varies with retained variables as expected

* A general principle: categorical variables less informative than quantitative ones

* However, categorical variables here improve quantitative ones

<figure><img src="image_100.png" /></figure>
Prostate cancer data: partition according to recoded variables

<table><thead><tr><th rowspan="3"></th><th colspan="2">categorical (raw)</th><th colspan="2">categorical (MCA)</th></tr><tr><th colspan="2">err=47.16%</th><th colspan="2">err=38.95%</th></tr><tr><th>1</th><th>2</th><th>1</th><th>2</th></tr></thead><tbody><tr><th>Stage 3</th><td>142</td><td>131</td><td>175</td><td>98</td></tr><tr><th>Stage 4</th><td>120</td><td>82</td><td>87</td><td>115</td></tr></tbody></table>

* MCA is equivalent to recoding categorical variables

* Raw data and MCA data are in a one-to-one mapping (no info. loss)

* It can however drastically impact clustering result

* It open the question of data units/coding to use

* Currently: let the user to choose the unit (prior or posterior choice)

* Next lesson: need formalizing to go further

<figure><img src="image_101.png" /></figure>
<figure><img src="image_102.png" /></figure>

<figure><img src="image_103.png" /></figure>

<figure><img src="image_104.png" /></figure>

<figure><img src="image_105.png" /></figure>

<figure><img src="image_106.png" /></figure>

<figure><img src="image_107.png" /></figure>

<figure><img src="image_108.png" /></figure>

Stability of a clustering result

■ Do not forget that $\hat{z}$ is just an estimate of (a hypothetical true) z

■ Statistical properties of this estimate should be addressed, as it stability (variance)

■ A simple (but computational demanding) attempt:

■ Use bootstrap samples $x^{(b)}$ ($b = 1, \dots, B$)

■ Obtain bootstrap partitions $z^{(b)}$

■ Deduce for instance confidence regions on centers $\mu$ through related centers $\mu^{(b)}$

■ Be careful to the permutation of labelling!

■ See the next lesson for more on the statistical properties (need formalizing)...

<figure><img src="image_109.png" /></figure>

<figure><img src="image_110.png" /></figure>

<figure><img src="image_111.png" /></figure>

<figure><img src="image_112.png" /></figure>

<figure><img src="image_113.png" /></figure>

<figure><img src="image_114.png" /></figure>

<figure><img src="image_115.png" /></figure>
<figure><img src="image_116.png" /></figure>

<figure><img src="image_117.png" /></figure>

<figure><img src="image_118.png" /></figure>

<figure><img src="image_119.png" /></figure>

<figure><img src="image_120.png" /></figure>

<figure><img src="image_121.png" /></figure>

<figure><img src="image_122.png" /></figure>

# Outline

1. Data factor

2. Dissimilarity factor (and co)

3. Algorithm factor

4. Number of clusters factor

5. User factor

6. Experiments

7. To go further

<figure><img src="image_123.png" /></figure>

<figure><img src="image_124.png" /></figure>

<figure><img src="image_125.png" /></figure>

<figure><img src="image_126.png" /></figure>

<figure><img src="image_127.png" /></figure>

<figure><img src="image_128.png" /></figure>

<figure><img src="image_129.png" /></figure>

<figure><img src="image_130.png" /></figure>

<figure><img src="image_131.png" /></figure>

<figure><img src="image_132.png" /></figure>
<figure><img src="image_133.png" /></figure>

<figure><img src="image_134.png" /></figure>

<figure><img src="image_135.png" /></figure>

<figure><img src="image_136.png" /></figure>

<figure><img src="image_137.png" /></figure>

<figure><img src="image_138.png" /></figure>

<figure><img src="image_139.png" /></figure>

Effect of the metric M (1/5)

$$ \mathcal{X} = \mathbb{R}^2, \mathbf{M} = \begin{pmatrix} a & 0 \\ 0 & 1 \end{pmatrix}, \mathbf{x}_1 = \begin{pmatrix} 0 \\ 0 \end{pmatrix}, \mathbf{x}_2 = \begin{pmatrix} 3 \\ 0 \end{pmatrix}, \mathbf{x}_3 = \begin{pmatrix} 0 \\ 1 \end{pmatrix} $$

<figure><img src="image_140.png" /></figure>

$$ \delta_M(\mathbf{x}_1, \mathbf{x}_2)^2 = (\mathbf{x}_1 - \mathbf{x}_2)' \begin{pmatrix} a & 0 \\ 0 & 1 \end{pmatrix} (\mathbf{x}_1 - \mathbf{x}_2) = a(\mathbf{x}_{21} - \mathbf{x}_{11})^2 = 9a $$

$$ \delta_M(\mathbf{x}_1, \mathbf{x}_3)^2 = (\mathbf{x}_1 - \mathbf{x}_3)' \begin{pmatrix} a & 0 \\ 0 & 1 \end{pmatrix} (\mathbf{x}_1 - \mathbf{x}_3) = (\mathbf{x}_{32} - \mathbf{x}_{12})^2 = 1 $$

<figure><img src="image_141.png" /></figure>

<figure><img src="image_142.png" /></figure>

<figure><img src="image_143.png" /></figure>

<figure><img src="image_144.png" /></figure>

<figure><img src="image_145.png" /></figure>

<figure><img src="image_146.png" /></figure>

<figure><img src="image_147.png" /></figure>

<figure><img src="image_148.png" /></figure>

<figure><img src="image_149.png" /></figure>

<figure><img src="image_150.png" /></figure>

<figure><img src="image_151.png" /></figure>

<figure><img src="image_152.png" /></figure>
<figure><img src="image_153.png" /></figure>

<figure><img src="image_154.png" /></figure>

<figure><img src="image_155.png" /></figure>

<figure><img src="image_156.png" /></figure>

<figure><img src="image_157.png" /></figure>

<figure><img src="image_158.png" /></figure>

<figure><img src="image_159.png" /></figure>

Effect of the metric M (2/5)

$$ \delta_M(\mathbf{x}_1, \mathbf{x}_2)^2 \le \delta_M(\mathbf{x}_1, \mathbf{x}_3)^2 \Leftrightarrow a \le \frac{1}{9} $$

■ The distance is impacted by the metric, thus the clustering could be also

■ Somewhere the metric is also related to variable selection (try $a = 0...$)

<figure><img src="image_160.png" /></figure>
<figure><img src="image_161.png" /></figure>

<figure><img src="image_162.png" /></figure>

<figure><img src="image_163.png" /></figure>

<figure><img src="image_164.png" /></figure>

<figure><img src="image_165.png" /></figure>

<figure><img src="image_166.png" /></figure>

<figure><img src="image_167.png" /></figure>

Effect of the metric M (3/5)

■ Animals represented by 13 Boolean features related to appearance and activity

■ Large weight on the appearance features compared to the activity features: the animals were clustered into mammals vs. birds

■ Large weight on the activity features: partitioning predators vs. non-predators

■ Both partitions are equally valid, and uncover meaningful structures in the data

■ The user has to carefully choose his representation to obtain a desired clustering

<figure><img src="image_168.png" /><figcaption>(a)</figcaption></figure>

<figure><img src="image_169.png" /><figcaption>(b)</figcaption></figure>

**Figure 6** Different weights on features result in different partitioning of the data. Sixteen animals are represented based on 13 Boolean features related to appearance and activity. (a) partitioning with large weights assigned to appearance based features; (b) a partitioning with large weights assigned to the activity features (figure reproduced from [Pampalk et al., 2003]).

<figure><img src="image_170.png" /></figure>
<figure><img src="image_171.png" /></figure>

<figure><img src="image_172.png" /></figure>

<figure><img src="image_173.png" /></figure>

<figure><img src="image_174.png" /></figure>

<figure><img src="image_175.png" /></figure>

<figure><img src="image_176.png" /></figure>

<figure><img src="image_177.png" /></figure>

Effect of the metric M (4/5)

If $M = I$...

<figure><img src="image_178.png" /></figure>

Alternative: estimate $M_{(k)}$ by minimizing $W_{M_{(k)}}(z)$ over $(z, M_{(k)})$

<figure><img src="image_179.png" /></figure>

<figure><img src="image_180.png" /></figure>

<figure><img src="image_181.png" /></figure>

<figure><img src="image_182.png" /></figure>

<figure><img src="image_183.png" /></figure>

<figure><img src="image_184.png" /></figure>

<figure><img src="image_185.png" /></figure>

<figure><img src="image_186.png" /></figure>

<figure><img src="image_187.png" /></figure>

<figure><img src="image_188.png" /></figure>

<figure><img src="image_189.png" /></figure>

<figure><img src="image_190.png" /></figure>

<figure><img src="image_191.png" /></figure>

<figure><img src="image_192.png" /></figure>

<figure><img src="image_193.png" /></figure>

<figure><img src="image_194.png" /></figure>

<figure><img src="image_195.png" /></figure>

<figure><img src="image_196.png" /></figure>

<figure><img src="image_197.png" /></figure>
Effect of the metric<fnref n="4" /> M (5/5)

Alternative: estimate $M_{(k)}$ by minimizing $W_{M_{(k)}}(z)$ over $(z, M_{(k)})$

<figure><img src="image_198.png" /></figure>

<figure><img src="image_199.png" /></figure>

<figure><img src="image_200.png" /></figure>

<figure><img src="image_201.png" /></figure>

<figure><img src="image_202.png" /></figure>

<figure><img src="image_203.png" /></figure>

<figure><img src="image_204.png" /></figure>

<figure><img src="image_205.png" /></figure>

<figure><img src="image_206.png" /></figure>

<figure><img src="image_207.png" /></figure>

<figure><img src="image_208.png" /></figure>

<figure><img src="image_209.png" /></figure>

<figure><img src="image_210.png" /></figure>

<figure><img src="image_211.png" /></figure>

<figure><img src="image_212.png" /></figure>

<figure><img src="image_213.png" /></figure>

<figure><img src="image_214.png" /></figure>

<figure><img src="image_215.png" /></figure>

<footnote n="4">⁴Figures from A.K. Jain (2008). Data Clustering: 50 Years Beyond K-Means. □</footnote>
<figure><img src="image_216.png" /></figure>

<figure><img src="image_217.png" /></figure>

<figure><img src="image_218.png" /></figure>

<figure><img src="image_219.png" /></figure>

<figure><img src="image_220.png" /></figure>

<figure><img src="image_221.png" /></figure>

<figure><img src="image_222.png" /></figure>

Effect of the linkage criterion (1/3)

[A. Jain at al. . Data Clustering: A Review.]

<figure><img src="image_223.png" /><figcaption>Fig. 12. A single-link clustering of a pattern set containing two classes (1 and 2) connected by a chain ofony patterns (^).</figcaption></figure>

<figure><img src="image_224.png" /><figcaption>Fig. 13. A complete-link clustering of a pattern set containing two classes (1 and 2) connected
by a chain ofony patterns (^).</figcaption></figure>

<figure><img src="image_225.png" /></figure>

<figure><img src="image_226.png" /></figure>

<figure><img src="image_227.png" /></figure>

<figure><img src="image_228.png" /></figure>

<figure><img src="image_229.png" /></figure>

<figure><img src="image_230.png" /></figure>

<figure><img src="image_231.png" /></figure>

<figure><img src="image_232.png" /></figure>

<figure><img src="image_233.png" /></figure>

<figure><img src="image_234.png" /></figure>

<figure><img src="image_235.png" /></figure>

<figure><img src="image_236.png" /></figure>

<figure><img src="image_237.png" /></figure>

<figure><img src="image_238.png" /></figure>

<figure><img src="image_239.png" /></figure>

<figure><img src="image_240.png" /></figure>
<figure><img src="image_241.png" /></figure>

<figure><img src="image_242.png" /></figure>

<figure><img src="image_243.png" /></figure>

<figure><img src="image_244.png" /></figure>

<figure><img src="image_245.png" /></figure>

<figure><img src="image_246.png" /></figure>

<figure><img src="image_247.png" /></figure>

Effect of the linkage criterion (2/3)

[P.-N. Tan *at al.* (2005). Introduction to data mining, second edition, Addison-Wesley, Chap.8]

<figure><img src="image_248.png" /><figcaption>Figure 8.15. Set of 6 two-dimensional points.</figcaption></figure>

<table><caption>Table 8.3. xy coordinates of 6 points.</caption><thead><tr><th>Point</th><th>x Coordinate</th><th>y Coordinate</th></tr></thead><tbody><tr><td>p1</td><td>0.40</td><td>0.53</td></tr><tr><td>p2</td><td>0.22</td><td>0.38</td></tr><tr><td>p3</td><td>0.35</td><td>0.32</td></tr><tr><td>p4</td><td>0.26</td><td>0.19</td></tr><tr><td>p5</td><td>0.08</td><td>0.41</td></tr><tr><td>p6</td><td>0.45</td><td>0.30</td></tr></tbody></table>

<table><caption>Table 8.4. Euclidean distance matrix for 6 points.</caption><thead><tr><th></th><th>p1</th><th>p2</th><th>p3</th><th>p4</th><th>p5</th><th>p6</th></tr></thead><tbody><tr><th>p1</th><td>0.00</td><td>0.24</td><td>0.22</td><td>0.37</td><td>0.34</td><td>0.23</td></tr><tr><th>p2</th><td>0.24</td><td>0.00</td><td>0.15</td><td>0.20</td><td>0.14</td><td>0.25</td></tr><tr><th>p3</th><td>0.22</td><td>0.15</td><td>0.00</td><td>0.15</td><td>0.28</td><td>0.11</td></tr><tr><th>p4</th><td>0.37</td><td>0.20</td><td>0.15</td><td>0.00</td><td>0.29</td><td>0.22</td></tr><tr><th>p5</th><td>0.34</td><td>0.14</td><td>0.28</td><td>0.29</td><td>0.00</td><td>0.39</td></tr><tr><th>p6</th><td>0.23</td><td>0.25</td><td>0.11</td><td>0.22</td><td>0.39</td><td>0.00</td></tr></tbody></table>

<figure><img src="image_249.png" /></figure>

<figure><img src="image_250.png" /></figure>

<figure><img src="image_251.png" /></figure>

<figure><img src="image_252.png" /></figure>

<figure><img src="image_253.png" /></figure>

<figure><img src="image_254.png" /></figure>

<figure><img src="image_255.png" /></figure>

<figure><img src="image_256.png" /></figure>

<figure><img src="image_257.png" /></figure>

<figure><img src="image_258.png" /></figure>
<figure><img src="image_259.png" /></figure>

<figure><img src="image_260.png" /></figure>

<figure><img src="image_261.png" /></figure>

<figure><img src="image_262.png" /></figure>

<figure><img src="image_263.png" /></figure>

<figure><img src="image_264.png" /></figure>

<figure><img src="image_265.png" /></figure>

Effect of the linkage criterion (3/3)

[P.-N. Tan *et al.* (2005). Introduction to data mining, second edition, Addison-Wesley, Chap.8]

<figure><img src="image_266.png" /><figcaption>Single link dendrogram.</figcaption></figure>

<figure><img src="image_267.png" /><figcaption>Complete link dendrogram.</figcaption></figure>

<figure><img src="image_268.png" /><figcaption>Group average dendrogram.</figcaption></figure>

<figure><img src="image_269.png" /><figcaption>Ward's dendrogram.</figcaption></figure>

<figure><img src="image_270.png" /></figure>

<figure><img src="image_271.png" /></figure>

<figure><img src="image_272.png" /></figure>

<figure><img src="image_273.png" /></figure>

<figure><img src="image_274.png" /></figure>

<figure><img src="image_275.png" /></figure>

<figure><img src="image_276.png" /></figure>

<figure><img src="image_277.png" /></figure>
What is “and co”?

Notice also obviously that:

■ Kernel clustering result depends on the kernel choice

■ Spectral clustering result depends on the Laplacian choice

■ ...

<figure><img src="image_278.png" /></figure>
<figure><img src="image_279.png" /></figure>

<figure><img src="image_280.png" /></figure>

<figure><img src="image_281.png" /></figure>

<figure><img src="image_282.png" /></figure>

<figure><img src="image_283.png" /></figure>

<figure><img src="image_284.png" /></figure>

<figure><img src="image_285.png" /></figure>

A meaningful way to be less metric (and co) dependent: idea

* Clustering interesting if separated clusters

* If separated clusters, partition less metric dependent

* Thus, the problem is partially reported on choosing *K* (see later in this lesson)

* It will be an interesting element to be used in next lesson also

This idea is also applicable for hierarchy, kernel, spectral clustering...

<figure><img src="image_286.png" /></figure>
<figure><img src="image_287.png" /></figure>

<figure><img src="image_288.png" /></figure>

<figure><img src="image_289.png" /></figure>

<figure><img src="image_290.png" /></figure>

<figure><img src="image_291.png" /></figure>

<figure><img src="image_292.png" /></figure>

A meaningful way to be less metric (and co) dependent: illustration

- K-means with $M = I$

- Not well-separated clusters

<figure><img src="image_293.png" /></figure>

- Well-separated clusters

<figure><img src="image_294.png" /></figure>

<figure><img src="image_295.png" /></figure>
A meaningful way to be less metric (and co) dependent: limit

However, it is not always sufficient...

<figure><img src="image_296.png" /><figcaption>Spectral clustering</figcaption></figure>

<figure><img src="image_297.png" /><figcaption>K-means clustering</figcaption></figure>

<figure><img src="image_298.png" /></figure>
## Outline

1. Data factor

2. Dissimilarity factor (and co)

3. Algorithm factor

4. Number of clusters factor

5. User factor

6. Experiments

7. To go further

<figure><img src="image_299.png" /></figure>

<figure><img src="image_300.png" /></figure>

<figure><img src="image_301.png" /></figure>

<figure><img src="image_302.png" /></figure>

<figure><img src="image_303.png" /></figure>

<figure><img src="image_304.png" /></figure>

<figure><img src="image_305.png" /></figure>

<figure><img src="image_306.png" /></figure>

<figure><img src="image_307.png" /></figure>

<figure><img src="image_308.png" /></figure>

<figure><img src="image_309.png" /></figure>

<figure><img src="image_310.png" /></figure>

<figure><img src="image_311.png" /></figure>

<figure><img src="image_312.png" /></figure>

<figure><img src="image_313.png" /></figure>
<table><thead><tr><th>Data factor</th><th>Algorithm factor</th><th>Number of clusters factor</th><th>User factor</th><th>Experiments</th><th>To go further</th></tr></thead><tbody><tr><td>○○○○○○○○○○○</td><td>○○○○○</td><td>○○○○○○○○○○</td><td>○○○○○○○○○○</td><td>○○</td><td>○○</td></tr></tbody></table>

Local maxima with *K*-means: explanation

<figure><img src="image_314.png" /></figure>

Run *K*-means from several random centers and keep the best *W* value

<figure><img src="image_315.png" /></figure>
Empty clusters with *K*-means

Two successive steps in Kmeans

<figure><img src="image_316.png" /></figure>

Restart *K*-means when the empty cluster case occurs

<figure><img src="image_317.png" /></figure>
What about hierarchical clustering?

- No problem of starting point

- No problem of local maxima

- But the price is strong constraints on nested partitions (see previous lesson)

<figure><img src="image_318.png" /></figure>

<figure><img src="image_319.png" /></figure>

<figure><img src="image_320.png" /></figure>

<figure><img src="image_321.png" /></figure>

<figure><img src="image_322.png" /></figure>

<figure><img src="image_323.png" /></figure>

<figure><img src="image_324.png" /></figure>
<table><tr><td>Data factor</td><td>Dissimilarity factor (and co)</td><td>Algorithm factor</td><td>Number of clusters factor</td><td>User factor</td><td>Experiments</td><td>To go further</td></tr><tr><td>○○○○○○○○○○</td><td>○○○○○○○○○○○○○○○</td><td>○○○○○</td><td>●○○○○○○○○○○</td><td>○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○</td><td>○○</td><td>○○</td></tr></table>

## Outline

1. Data factor

2. Dissimilarity factor (and co)

3. Algorithm factor

4. Number of clusters factor

5. User factor

6. Experiments

7. To go further

<figure><img src="image_325.png" /></figure>

<figure><img src="image_326.png" /></figure>

<figure><img src="image_327.png" /></figure>

<figure><img src="image_328.png" /></figure>

<figure><img src="image_329.png" /></figure>

<figure><img src="image_330.png" /></figure>

<figure><img src="image_331.png" /></figure>

<figure><img src="image_332.png" /></figure>

<figure><img src="image_333.png" /></figure>

<figure><img src="image_334.png" /></figure>

<figure><img src="image_335.png" /></figure>

<figure><img src="image_336.png" /></figure>

<figure><img src="image_337.png" /></figure>

<figure><img src="image_338.png" /></figure>

<figure><img src="image_339.png" /></figure>

<figure><img src="image_340.png" /></figure>
Different values of *K* are valid!

[P.-N. Tan *et al.* (2005). Introduction to data mining, second edition, Addison-Wesley, Chap.8]

<figure><img src="image_341.png" /></figure>

<figure><img src="image_342.png" /></figure>
<figure><img src="image_343.png" /></figure>

<figure><img src="image_344.png" /></figure>

<figure><img src="image_345.png" /></figure>

<figure><img src="image_346.png" /></figure>

<figure><img src="image_347.png" /></figure>

<figure><img src="image_348.png" /></figure>

<figure><img src="image_349.png" /></figure>

Wk not enough

$$W_K = \arg \min_{z \text{ with } K \text{ clusters}} W(z)$$

- $W_{K+1} \le W_K$

- $W_n = 0$

<figure><img src="image_350.png" /></figure>

<figure><img src="image_351.png" /></figure>

<figure><img src="image_352.png" /></figure>

<figure><img src="image_353.png" /></figure>

<figure><img src="image_354.png" /></figure>

<figure><img src="image_355.png" /></figure>

<figure><img src="image_356.png" /></figure>

<figure><img src="image_357.png" /></figure>

<figure><img src="image_358.png" /></figure>

<figure><img src="image_359.png" /></figure>

<figure><img src="image_360.png" /></figure>

<figure><img src="image_361.png" /></figure>
Typology of methods for choosing the number of clusters<fnref n="5" />

- There exists many other empirical criteria (ex: cross-validation)

- There exists clustering methods including automatic choice of *K* (ex: DBSCAN)

<figure><img src="image_362.png" /><figcaption>**Figure 1:** A taxonomy for the approaches to choosing the number of clusters as described in the paper. Here DK is Domain Knowledge in which DA is Direct Adjustment of algorithm and AP is Adjustment by Post-processing of clustering results, GC is modelling of the process of Generation of Clusters, and CS is Cluster Structures. This last item is further divided in MD, that is, Mixture of Distributions, P, Partitions, BH, Binary Hierarchies, and OS, Other cluster Structures. MD involves HFT which is Hypothesis Testing, AL, Additional terms in the Likelihood criterion, CoS, Collateral Statistics, and W1, Weighted Likelihood, BH involves SC, Stopping according to a Criterion, and CO, using a cut-off level over a completed tree. Item PA covers PP, Partition Post-processing, and IC, pre-processing by Initialization of Centroids. The latter involves DC, Distant Centroids, and AP, Anomalous Patterns. PP involves V, Variance based approach, S, Structure based approach, C, Combining clusterings approach, and R, Resampling based approach. The latter is composed of SS, Sub-sampling, SD, Splitting the Data, BS, Bootstrapping, and AN, Adding Noise.</figcaption></figure>

<figure><img src="image_363.png" /></figure>

<figure><img src="image_364.png" /></figure>

<footnote n="5">⁵Mirkin, Boris. (2011). Choosing the number of clusters. Wiley Interdisc. Rev.: Data Mining and Knowledge Discovery. 1. 252-260.</footnote>
<figure><img src="image_365.png" /></figure>

<figure><img src="image_366.png" /></figure>

<figure><img src="image_367.png" /></figure>

<figure><img src="image_368.png" /></figure>

<figure><img src="image_369.png" /></figure>

<figure><img src="image_370.png" /></figure>

<figure><img src="image_371.png" /></figure>

What about methods other than K-means?

■ Hierarchical clustering: previous criteria, an elbow in Δ...

■ Spectral clustering: an elbow in the eigenvalues curve

[U. von Luxburg (2006). A Tutorial on Spectral Clustering.]

Histogram of the sample

<figure><img src="image_372.png" /></figure>

Eigenvalues

+

<figure><img src="image_373.png" /></figure>

Histogram of the sample

<figure><img src="image_374.png" /></figure>

Eigenvalues

+

<figure><img src="image_375.png" /></figure>

Histogram of the sample

<figure><img src="image_376.png" /></figure>

Eigenvalues

+

<figure><img src="image_377.png" /></figure>

<figure><img src="image_378.png" /></figure>

<figure><img src="image_379.png" /></figure>

<figure><img src="image_380.png" /></figure>

<figure><img src="image_381.png" /></figure>

<figure><img src="image_382.png" /></figure>

<figure><img src="image_383.png" /></figure>

<figure><img src="image_384.png" /></figure>

<figure><img src="image_385.png" /></figure>

<figure><img src="image_386.png" /></figure>

<figure><img src="image_387.png" /></figure>

<figure><img src="image_388.png" /></figure>

<figure><img src="image_389.png" /></figure>

<figure><img src="image_390.png" /></figure>

<figure><img src="image_391.png" /></figure>

<figure><img src="image_392.png" /></figure>

<figure><img src="image_393.png" /></figure>

<figure><img src="image_394.png" /></figure>

<figure><img src="image_395.png" /></figure>
<figure><img src="image_396.png" /></figure>

<figure><img src="image_397.png" /></figure>

<figure><img src="image_398.png" /></figure>

<figure><img src="image_399.png" /></figure>

<figure><img src="image_400.png" /></figure>

<figure><img src="image_401.png" /></figure>

<figure><img src="image_402.png" /></figure>

## Outline

1. Data factor

2. Dissimilarity factor (and co)

3. Algorithm factor

4. Number of clusters factor

5. User factor

6. Experiments

7. To go further

<figure><img src="image_403.png" /></figure>

<figure><img src="image_404.png" /></figure>

<figure><img src="image_405.png" /></figure>

<figure><img src="image_406.png" /></figure>

<figure><img src="image_407.png" /></figure>

<figure><img src="image_408.png" /></figure>

<figure><img src="image_409.png" /></figure>

<figure><img src="image_410.png" /></figure>

<figure><img src="image_411.png" /></figure>

<figure><img src="image_412.png" /></figure>

<figure><img src="image_413.png" /></figure>
<figure><img src="image_414.png" /><figcaption>Data factor
○○○○○○○○○○○
○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○

Dissimilarity factor (and co)
○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○

Algorithm factor
○○○○○

Number of clusters factor
○○○○○○○○○○○

User factor
○○○○○○○○○○○
○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○○</figcaption></figure>

Little readable...

<figure><img src="image_415.png" /></figure>
<figure><img src="image_416.png" /></figure>

<figure><img src="image_417.png" /></figure>

<figure><img src="image_418.png" /></figure>

<figure><img src="image_419.png" /></figure>

<figure><img src="image_420.png" /></figure>

<figure><img src="image_421.png" /></figure>

<figure><img src="image_422.png" /><figcaption>Marketing Data: MCA visualization</figcaption></figure>

<figure><img src="image_423.png" /></figure>

<figure><img src="image_424.png" /></figure>

<figure><img src="image_425.png" /></figure>

<figure><img src="image_426.png" /></figure>

<figure><img src="image_427.png" /></figure>

<figure><img src="image_428.png" /></figure>

<figure><img src="image_429.png" /></figure>

<figure><img src="image_430.png" /></figure>

<figure><img src="image_431.png" /></figure>

<figure><img src="image_432.png" /></figure>

<figure><img src="image_433.png" /></figure>

<figure><img src="image_434.png" /></figure>

<figure><img src="image_435.png" /></figure>

<figure><img src="image_436.png" /></figure>

<figure><img src="image_437.png" /></figure>

<figure><img src="image_438.png" /></figure>

<figure><img src="image_439.png" /></figure>
SPAM E-mail database: description<fnref n="7" />

■ $n = 4601$ e-mails composed by 1813 "spams" and 2788 "good e-mails"

■ $d = 48 + 6 = 54$ continuous descriptors<fnref n="6" />

■ 48 percentages that a given word appears in an e-mail ("make", "you"...)

■ 6 percentages that a given char appears in an e-mail ("a", "b", "$"...)

■ Transformation of continuous descriptors into binary descriptors

$$x_{ij} = \begin{cases} 1 & \text{if word/char } j \text{ appears in e-mail } i \\ 0 & \text{otherwise} \end{cases}$$

<figure><img src="image_440.png" /></figure>

<figure><img src="image_441.png" /></figure>

<figure><img src="image_442.png" /></figure>

<figure><img src="image_443.png" /></figure>

<figure><img src="image_444.png" /></figure>

<figure><img src="image_445.png" /></figure>

<figure><img src="image_446.png" /></figure>

<figure><img src="image_447.png" /></figure>

<figure><img src="image_448.png" /></figure>

<figure><img src="image_449.png" /></figure>

<footnote n="6">⁶There are 3 other continuous descriptors we do not use</footnote>

<footnote n="7">⁷https://archive.ics.uci.edu/ml/machine-learning-databases/spambase/</footnote>
<table><caption>SPAM E-mail database: raw visualization</caption><thead><tr><th>Data factor</th><th>Dissimilarity factor (and co)</th><th>Algorithm factor</th><th>Number of clusters factor</th><th>User factor</th><th>Experiments</th><th>To go further</th></tr></thead><tbody><tr><td>○○○○○○○○○○○</td><td>○○○○○○○○○○○○○○○○○○○</td><td>○○○○○○○○○○○</td><td>○○○○○○○○○○○</td><td>○○○○○○○○○○○○○○○○○○○○○○○○○○○○</td><td>○○</td><td>○○</td></tr></tbody></table>

<figure><img src="image_450.png" /></figure>

<figure><img src="image_451.png" /></figure>
<table><tr><td>Data factor</td><td>Dissimilarity factor (and co)</td><td>Algorithm factor</td><td>Number of clusters factor</td><td>User factor</td><td>Experiments</td><td>To go further</td></tr><tr><td>○○○○○○○○○○○</td><td>○○○○○○○○○○○○○○○○</td><td>○○○○○○○○○○○</td><td>○○○○○○○○○○○</td><td>○○○○○○○○○○○○○○○○○○○</td><td>○○</td><td>○○</td></tr></table>

SPAM E-mail database: two clusters (1/4)

<figure><img src="image_452.png" /></figure>

<figure><img src="image_453.png" /></figure>
<table><thead><tr><th>Data factor</th><th>Dissimilarity factor (and co)</th><th>Algorithm factor</th><th>Number of clusters factor</th><th>User factor</th><th>Experiments</th><th>To go further</th></tr></thead><tbody><tr><td>○○○○○○○○○○○</td><td>○○○○○○○○○○○○○○○○</td><td>○○○○○○○○○○○</td><td>○○○○○○○○○○○</td><td>○○○○○○○○○○○○○○○○</td><td>○○</td><td>○○</td></tr></tbody></table>

SPAM E-mail database: two clusters (2/4)

<figure><img src="image_454.png" /></figure>

<figure><img src="image_455.png" /></figure>
SPAM E-mail database: two clusters (3/4)

<figure><img src="image_456.png" /></figure>

<figure><img src="image_457.png" /></figure>
Data factor

<figure><img src="image_458.png" /></figure>

Dissimilarity factor (and co)

<figure><img src="image_459.png" /></figure>

Algorithm factor

<figure><img src="image_460.png" /></figure>

Number of clusters factor

<figure><img src="image_461.png" /></figure>

User factor

<figure><img src="image_462.png" /></figure>

<figure><img src="image_463.png" /></figure>

Experiments

<figure><img src="image_464.png" /></figure>

To go further

<figure><img src="image_465.png" /></figure>

SPAM E-mail database: two clusters (4/4)

<figure><img src="image_466.png" /></figure>

<figure><img src="image_467.png" /></figure>

<figure><img src="image_468.png" /></figure>

<figure><img src="image_469.png" /></figure>

<figure><img src="image_470.png" /></figure>

<figure><img src="image_471.png" /></figure>

<figure><img src="image_472.png" /></figure>

<figure><img src="image_473.png" /></figure>

<figure><img src="image_474.png" /></figure>

<figure><img src="image_475.png" /></figure>

<figure><img src="image_476.png" /></figure>

<figure><img src="image_477.png" /></figure>

<figure><img src="image_478.png" /></figure>

<figure><img src="image_479.png" /></figure>

<figure><img src="image_480.png" /></figure>

<figure><img src="image_481.png" /></figure>
<figure><img src="image_482.png" /><figcaption>SPAM E-mail database: three clusters (1/4)</figcaption></figure>

<figure><img src="image_483.png" /></figure>
<figure><img src="image_484.png" /><figcaption>SPAM E-mail database: three clusters (2/4)</figcaption></figure>

<figure><img src="image_485.png" /></figure>
<table><tr><td>Data factor</td><td>Dissimilarity factor (and co)</td><td>Algorithm factor</td><td>Number of clusters factor</td><td>User factor</td><td>Experiments</td><td>To go further</td></tr><tr><td>○○○○○○○○○○○</td><td>○○○○○○○○○○○○○○○○</td><td>○○○○○○○○○○○</td><td>○○○○○○○○○○○</td><td>○○○○○○○○○○○○○○○○</td><td>○○</td><td>○○</td></tr></table>

SPAM E-mail database: three clusters (3/4)

<table><thead><tr><th rowspan="2" colspan="2"></th><th colspan="3">clustering</th></tr><tr><th>○○○○○</th><th>○○○○○</th><th>○○○○○</th></tr></thead><tbody><tr><th rowspan="2">human</th><th>spams</th><td>10</td><td>1205</td><td>598</td></tr><tr><th>spams</th><td>800</td><td>117</td><td>1871</td></tr></tbody></table>

<figure><img src="image_486.png" /></figure>
<table><tr><td>Data factor</td><td>Dissimilarity factor (and co)</td><td>Algorithm factor</td><td>Number of clusters factor</td><td>User factor</td><td>Experiments</td><td>To go further</td></tr><tr><td>○○○○○○○○○○○</td><td>○○○○○○○○○○○○○○○</td><td>○○○○○</td><td>○○○○○○○○○○○</td><td>○○○○○○○○○○○○○○○</td><td>○○</td><td>○○</td></tr></table>

SPAM E-mail database: three clusters (4/4)

<figure><img src="image_487.png" /></figure>

<figure><img src="image_488.png" /></figure>
<figure><img src="image_489.png" /></figure>

<figure><img src="image_490.png" /></figure>

<figure><img src="image_491.png" /></figure>

<figure><img src="image_492.png" /></figure>

<figure><img src="image_493.png" /></figure>

<figure><img src="image_494.png" /></figure>

<figure><img src="image_495.png" /></figure>

Prostate cancer data: description<fnref n="8" />

- **Individuals**: 506 patients with prostatic cancer grouped on clinical criteria into two Stages 3 and 4 of the disease

- **Variables**: *d* = 12 pre-trial variates were measured on each patient, composed by **eight continuous variables** (age, weight, systolic blood pressure, diastolic blood pressure, serum haemoglobin, size of primary tumour, index of tumour stage and histolic grade, serum prostatic acid phosphatase) and **four categorical variables** with various numbers of levels (performance rating, cardiovascular disease history, electrocardiogram code, bone metastases)

- **Some missing data**: 62 missing values (≈ 1%)

We forget the classes (Stages of the disease) for performing clustering

<figure><img src="image_496.png" /></figure>

<figure><img src="image_497.png" /></figure>

<figure><img src="image_498.png" /></figure>

<figure><img src="image_499.png" /></figure>

<figure><img src="image_500.png" /></figure>

<figure><img src="image_501.png" /></figure>

<figure><img src="image_502.png" /></figure>

<figure><img src="image_503.png" /></figure>

<footnote n="8">⁸Byar DP, Green SB (1980): Bulletin Cancer, Paris 67:477-488</footnote>
<figure><img src="image_504.png" /></figure>

<figure><img src="image_505.png" /></figure>

<figure><img src="image_506.png" /></figure>

<figure><img src="image_507.png" /></figure>

<figure><img src="image_508.png" /></figure>

<figure><img src="image_509.png" /></figure>

<figure><img src="image_510.png" /></figure>

Prostate cancer data: PCA and MCA partition visualization

<figure><img src="image_511.png" /></figure>

Seems to be not well separated

<figure><img src="image_512.png" /></figure>
<figure><img src="image_513.png" /><figcaption>Prostate cancer data:
chart of individuals sorted by distance to centers visualization</figcaption></figure>

In fact it is well separated

<figure><img src="image_514.png" /></figure>
<table><caption>Prostate cancer data: cluster weight</caption><thead><tr><th></th><th></th><th></th><th></th></tr></thead><tbody><tr><td>Data factor</td><td>Dissimilarity factor (and co)</td><td>Algorithm factor</td><td>Number of clusters factor</td><td>User factor</td><td>Experiments</td><td>To go further</td></tr><tr><td>○○○○○○○○○</td><td>○○○○○○○○○○○○</td><td>○○○○○</td><td>○○○○○○○○○</td><td>○○○○○</td><td>○○</td><td>○○</td></tr></tbody></table>

<figure><img src="image_515.png" /></figure>

<figure><img src="image_516.png" /></figure>
Prostate cancer data: variable "Age" difference between clusters

<figure><img src="image_517.png" /></figure>

Variable
Parameters

This chart summarizes the distribution of the selected variable.

Age

<figure><img src="image_518.png" /></figure>

Age (Gaussian)

<figure><img src="image_519.png" /></figure>

Hide model parameters

Class 1

Class 2

mean: 71.534, sigma: 6.760 mean: 71.313, sigma: 7.463

"Age" seems to be **not very** discriminant

<figure><img src="image_520.png" /></figure>
Prostate cancer data: variable “SG” difference between clusters

<figure><img src="image_521.png" /></figure>

Variable

Parameters

This chart summarizes the distribution of the selected variable.

SG

<figure><img src="image_522.png" /></figure>

SG (Gaussian)

♥ Hide model parameters

Class 1

Class 2

mean: 8.940, sigma: 1.154 mean: 12.087, sigma: 1.405

“Age” seems to be *very* discriminant

<figure><img src="image_523.png" /></figure>
Prostate cancer data: variable "BM" difference between clusters

<figure><img src="image_524.png" /></figure>

Variable

Parameters

This chart summarizes the
distribution of the selected
variable.

BM

<figure><img src="image_525.png" /></figure>

BM (Multinomial)

Hide model parameters

Class 1

Class 2

scatter: [0.993,0.007]

scatter: [0.633,0.367]

"BM" seems to be very discriminant

<figure><img src="image_526.png" /></figure>
<table><thead><tr><th></th><th></th><th></th><th></th></tr></thead><tbody><tr><td>Data factor</td><td>Dissimilarity factor (and co)</td><td>Algorithm factor</td><td>Number of clusters factor</td><td>User factor</td><td>Experiments</td><td>To go further</td></tr><tr><td>○○○○○○○○○○</td><td>○○○○○○○○○○○○○○○</td><td>○○○○○</td><td>○○○○○○○○○○</td><td>○○○○○○○○○○○○○○○○○○○</td><td>●○</td><td>○○</td></tr></tbody></table>

## Outline

1. Data factor

2. Dissimilarity factor (and co)

3. Algorithm factor

4. Number of clusters factor

5. User factor

6. Experiments

7. To go further

<figure><img src="image_527.png" /></figure>

<figure><img src="image_528.png" /></figure>

<figure><img src="image_529.png" /></figure>

<figure><img src="image_530.png" /></figure>

<figure><img src="image_531.png" /></figure>

<figure><img src="image_532.png" /></figure>

<figure><img src="image_533.png" /></figure>

<figure><img src="image_534.png" /></figure>

<figure><img src="image_535.png" /></figure>

<figure><img src="image_536.png" /></figure>

<figure><img src="image_537.png" /></figure>

<figure><img src="image_538.png" /></figure>

<figure><img src="image_539.png" /></figure>
<figure><img src="image_540.png" /></figure>

<figure><img src="image_541.png" /></figure>

<figure><img src="image_542.png" /></figure>

<figure><img src="image_543.png" /></figure>

<figure><img src="image_544.png" /></figure>

<figure><img src="image_545.png" /></figure>

See experiments on the US census in Part 1

In particular, we can observe the effect on the partition from:

- the linkage criterion for HCA

- the algorithm (HCA vs. K-means)

<figure><img src="image_546.png" /></figure>

<figure><img src="image_547.png" /></figure>

<figure><img src="image_548.png" /></figure>

<figure><img src="image_549.png" /></figure>

<figure><img src="image_550.png" /></figure>

<figure><img src="image_551.png" /></figure>

<figure><img src="image_552.png" /></figure>
<figure><img src="image_553.png" /></figure>

<figure><img src="image_554.png" /></figure>

<figure><img src="image_555.png" /></figure>

<figure><img src="image_556.png" /></figure>

<figure><img src="image_557.png" /></figure>

<figure><img src="image_558.png" /></figure>

<figure><img src="image_559.png" /></figure>

## Outline

1. Data factor

2. Dissimilarity factor (and co)

3. Algorithm factor

4. Number of clusters factor

5. User factor

6. Experiments

7. To go further

<figure><img src="image_560.png" /></figure>

<figure><img src="image_561.png" /></figure>

<figure><img src="image_562.png" /></figure>

<figure><img src="image_563.png" /></figure>

<figure><img src="image_564.png" /></figure>

<figure><img src="image_565.png" /></figure>

<figure><img src="image_566.png" /></figure>

<figure><img src="image_567.png" /></figure>

<figure><img src="image_568.png" /></figure>

<figure><img src="image_569.png" /></figure>

<figure><img src="image_570.png" /></figure>

<figure><img src="image_571.png" /></figure>

<figure><img src="image_572.png" /></figure>

<figure><img src="image_573.png" /></figure>

<figure><img src="image_574.png" /></figure>
<figure><img src="image_575.png" /></figure>

<figure><img src="image_576.png" /></figure>

<figure><img src="image_577.png" /></figure>

<figure><img src="image_578.png" /></figure>

<figure><img src="image_579.png" /></figure>

<figure><img src="image_580.png" /></figure>

Next lesson

To go further towards clustering evaluation, there is a need to further formalize...

Clustering : une vision unifiée pour une utilisation éclairée
Formalisation par modèles de mélange

<figure><img src="image_581.png" /></figure>

<figure><img src="image_582.png" /></figure>

<figure><img src="image_583.png" /></figure>

<figure><img src="image_584.png" /></figure>

<figure><img src="image_585.png" /></figure>

<figure><img src="image_586.png" /></figure>

<figure><img src="image_587.png" /></figure>

<figure><img src="image_588.png" /></figure>

<figure><img src="image_589.png" /></figure>

<figure><img src="image_590.png" /></figure>

<figure><img src="image_591.png" /></figure>

<figure><img src="image_592.png" /></figure>

<figure><img src="image_593.png" /></figure>

<figure><img src="image_594.png" /></figure>

<figure><img src="image_595.png" /></figure>

<figure><img src="image_596.png" /></figure>