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

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

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

# Méthodes exploratoires en clustering

C. Biernacki

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

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

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

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

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

## What is this course?

- Be able to perform practically some methods

- Use them with discernment

## What is not this course?

- Not an exhaustive list of clustering methods (and related bibliography)

- Do not make specialists of clustering methods

This preamble is valid for all four lessons:

1. Méthodes exploratoires en clustering

2. Evaluation d'une méthode de clustering

3. Formalisation par modèles de mélange

4. Traitement de la grande dimension & co-clustering

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

* General overview of data mining (contain some pretreatments before clustering):
  Gérard Govaart et al. (2009). Data Analysis. Wiley-ISTE, ISBN: 978-1-848-21098-1.
https://www.wiley.com/en-fr/Data+Analysis-p-9781848210981

* More advanced material on clustering:

* Christian Hennig, Marina Meila, Fionn Murtagh, Roberto Rocci (2015). Handbook of Cluster Analysis. Chapman and Hall/CRC, ISBN 9781466551886, Series: Chapman & Hall/CRC Handbooks of Modern Statistical Methods.
    https://www.crcpress.com/Handbook-of-Cluster-Analysis/Hennig-Meila-Murtagh-Rocci/p/book/9781466551886

* Christophe Biernacki. Mixture models. J-J. Droesbeke; G. Saporta; C. Thomas-Agnan. Choix de modèles et agrégation, Technip, 2017.
    https://hal.inria.fr/hal-01252671/document

* Christophe Biernacki, Cathy Maugis. High-dimensional clustering. Choix de modèles et agrégation, Sous la direction de J-J. DROESBEKE, G. SAPORTA, C. THOMAS-AGNAN Edition: Technip.
    https://hal.archives-ouvertes.fr/hal-01252673v2/document

* Advanced material on co-clustering:

* Gérard Govaart, Mohamed Nadif (2013). Co-Clustering: Models, Algorithms and Applications. Wiley-ISTE, ISBN-13: 978-1848214736.
    https://www.wiley.com/en-fr/Co/Clustering:*Models,*Algorithms*and*Applications-p-9781848214736

* C. Biernacki, J. Jacques, C. Keribin (2023). A Survey on Model-Based Co-Clustering: High Dimension and Estimation Challenges, *Journal of Classification*, in press
    https://hal.science/hal-03769727/document

* Basic to more advanced R book: Pierre-Andre Cornillon, Arnaud Guyader, Francois Husson, Nicolas Jegou, Julie Josse, Maela Kloareg, Eric Matzner-Lober, Laurent Rouvière (2012). R for Statistics. Chapman and Hall/CRC, ISBN 9781439881453.
https://www.crcpress.com/R-for-Statistics/
Cornillon-Guyader-Husson-Jegou-Josse-Kloareg-Matzner-Lober-Rouvière/p/book/9781439881453

<figure><img src="image_13.png" /></figure>
Take home message

cluster

clustering

define both!

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

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

# Outline

1 Data

2 Classifications(s)

3 Clustering: motivation

4 Empirical procedures

5 Automatic procedures

6 Experiments

7 To go further

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

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

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

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

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

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

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

Everything begins from data!

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

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

Today's data (1/2)

Today, it is easy to collect many features, so it favors

- data variety and/or mixed

- data missing

- data uncertainty (or interval data)

Mixed, missing, uncertain

<table><caption>Observed individuals $x^O$</caption><tr><td>?</td><td>0.5</td><td>?</td><td>5</td></tr><tr><td>0.3</td><td>0.1</td><td>green</td><td>3</td></tr><tr><td>0.3</td><td>0.6</td><td>{red,green}</td><td>3</td></tr><tr><td>0.9</td><td>[0.25 0.45]</td><td>red</td><td>?</td></tr><tr><td>↓</td><td>↓</td><td>↓</td><td>↓</td></tr><tr><td>continuous</td><td>continuous</td><td>categorical</td><td>integer</td></tr></table>

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

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

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

Today's data (2/2)

And also

- Ranking data (like Olympics games)

- Directional data (like angle of wind direction)

- Ordinal data (a score like A > B > C)

- Functional data (like time series)<fnref n="1" />

- Graphical data (like social networks, biological network)

- ...

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

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

<footnote n="1">¹See a specific lesson for clustering times series</footnote>
<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>

## Todays features: full mixed/missing

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

categorical

Marital status
married

Integer
Children
3

missing

Size (m)
?

rank

Drink preference
beer > soda > water

Ordinal
Intelligence
low

continuous

Weight (kg)
119.5

functional

Drink consumption

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

graph

Family

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

And so on...

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

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

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

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

Data sets structure

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

<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>
Coding for data x

■ A set of n individuals

$$
\mathbf{x} = \{\mathbf{x}_1, \dots, \mathbf{x}_n\}
$$

with $\mathbf{x}_i$ a set of (possibly non-scalar) $d$ variables

$$
\mathbf{x}_i = \{ \mathbf{x}_{i1}, \dots, \mathbf{x}_{id} \}
$$

where $\mathbf{x}_{ij} \in \mathcal{X}_j$

■ A *n*-uplet of individuals

$$
\mathbf{x} = (\mathbf{x}_1, \dots, \mathbf{x}_n)
$$

with $\mathbf{x}_i$ a *d*-uplet of (possibly non-scalar) variables

$$
\mathbf{x}_i = (\mathbf{x}_{i1}, \dots, \mathbf{x}_{id}) \in \mathcal{X}
$$

where $\mathcal{X} = \mathcal{X}_1 \times \dots \times \mathcal{X}_d$

We will pass from a coding to another, depending on the practical utility
(useful for some calculus to have matrices or vectors for instance)

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

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

Large data sets (n)$^2$

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

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

<footnote n="2">²S. Alelyani, J. Tang and H. Liu (2013). Feature Selection for Clustering: A Review. *Data Clustering: Algorithms and Applications*, 29</footnote>
<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>

High-dimensional data ($d)^3$

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

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

<footnote n="3">³S. Alelyani, J. Tang and H. Liu (2013). Feature Selection for Clustering: A Review. *Data Clustering: Algorithms and Applications*, 29</footnote>
<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>

Genesis of “Big Data”

The Big Data phenomenon mainly originates in the increase of computer and digital
resources at an ever lower cost

■ Storage cost per MB: 700$ in 1981, 1$ in 1994, 0.01$ in 2013
→ price divided by 70,000 in thirty years

■ Storage capacity of HDDs: ≈1.02 Go in 1982, ≈8 To today
→ capacity multiplied by 8,000 over the same period

■ Computeur processing speed: 1 gigaFLOPS<fnref n="4" /> in 1985, 33 petaFLOPS in 2013
→ speed multiplied by 33 million

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

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

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

<footnote n="4">⁴FLOP = FLoating-point Operations Per Second</footnote>
<figure><img src="image_175.png" /></figure>

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

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

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

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

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

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

Digital flow

■ Digital in 1986: 1% of the stored information, 0.02 Eo⁵

■ Digital in 2007: 94% of the stored information, 280 Eo (multiplied by 14,000)

Global Information Storage Capacity
in optimally compressed bytes

2007 ANALOG

19 exabytes

First, 1 terabyte and 1 million 64-bit analog video disks (64 bit, 94% 1986

Fortran media, Flashdrive: 2%

Portable harddisks: 2.4%

CDs and minidisk: 8.8%

DIGITAL

Computer servers and mainframes: 8.9%

Digital tape: 11.8%

DVD/Blu-ray: 22.8%

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

PC harddisks: 64.4%

123 billion gigabytes

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

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

Source: Hilbert, M., & López-P. (2011). The World's Technological Capacity to Store, Communicate, and Compute Information. Science, 332(6625), 60–65. http://www.martinhilbert.net/WorldInfoCapacity.html

DIGITAL

280 exabytes

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

Societal phenomenon

All human activities are impacted by data accumulation

- Trade and business: corporate reporting system, banks, commercial transactions, reservation systems...

- Governments and organizations: laws, regulations, standardizations, infrastructure...

- Entertainment: music, video, games, social networks...

- Sciences: astronomy, physics and energy, genome,...

- Health: medical record databases in the social security system...

- Environment: climate, sustainable development, pollution, power...

- Humanities and Social Sciences: digitization of knowledge, literature, history, art, architecture, archaeological data...

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

## More data for what?

Opportunity to improve accuracy of traditional questionings

## Synthetic examples

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

* Here is just illustrated the effect of *n*

* In further lessons will be illustrated the effect of *d* (be patient)

<figure><img src="image_197.png" /></figure>
<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>

# Outline

1. Data

2. Classifications(s)

3. Clustering: motivation

4. Empirical procedures

5. Automatic procedures

6. Experiments

7. To go further

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

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

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

<figure><img src="image_218.png" /></figure>
Supervised classification (1/3)

■ **Data:** learning dataset $\mathcal{D} = \{\mathbf{x}^O, \mathbf{z}\}$

■ $n$ individuals: $\mathbf{x} = \{\mathbf{x}_1, \dots, \mathbf{x}_n\} = \{\mathbf{x}^O, \mathbf{x}^M\}$, each $\mathbf{x}_i \in \mathcal{X}$

■ Observed individuals $\mathbf{x}^O$

■ Missing individuals $\mathbf{x}^M$

■ Partition in $K$ groups $G_1, \dots, G_K$: $\mathbf{z} = (\mathbf{z}_1, \dots, \mathbf{z}_n)^6$, $\mathbf{z}_i = (z_{i1}, \dots, z_{ik})'$

$\mathbf{x}_i \in G_k \Leftrightarrow z_{ih} = \mathbb{I}_{\{h=k\}}$

■ **Aim:** estimation of an allocation rule $r$ from $\mathcal{D}$

$$r: \begin{array}{ccc} \mathcal{X} & \longrightarrow & \{1, \dots, K\} \\ \mathbf{x}_{n+1}^{O} & \longmapsto & r(\mathbf{x}_{n+1}^{O}). \end{array}$$

Other possible coding for $\mathbf{z}$

Sometimes it can be more convenient in formula to code $\mathbf{z} = (\mathbf{z}_1, \dots, \mathbf{z}_n)^a$ where

$$\mathbf{x}_i \in G_k \Leftrightarrow z_i = k$$

<footnote>a Sometimes it would be more convenient to use a set also: $\mathbf{z} = \{\mathbf{z}_1, \dots, \mathbf{z}_n\}$</footnote>

<footnote n="6">6 Sometimes it would be more convenient to use a set also: $\mathbf{z} = \{\mathbf{z}_1, \dots, \mathbf{z}_n\}$</footnote>
Supervised classification (2/3)

1st coding for z

Mixed, missing, uncertain

<table><thead><tr><th></th><th colspan="3">Individuals x<sup>O</sup></th><th colspan="3">Partition z</th><th>Group</th></tr></thead><tbody><tr><td>?</td><td>0.5</td><td>red</td><td>5</td><td>0</td><td>1</td><td>0</td><td>↔ G<sub>2</sub></td></tr><tr><td>0.3</td><td>0.1</td><td>green</td><td>3</td><td>1</td><td>0</td><td>0</td><td>↔ G<sub>1</sub></td></tr><tr><td>0.3</td><td>0.6</td><td>{red,green}</td><td>3</td><td>1</td><td>0</td><td>0</td><td>↔ G<sub>1</sub></td></tr><tr><td>0.9</td><td>[0.25 0.45]</td><td>red</td><td>?</td><td>0</td><td>0</td><td>1</td><td>↔ G<sub>3</sub></td></tr><tr><td>↓</td><td>↓</td><td>↓</td><td>↓</td><td></td><td></td><td></td><td></td></tr><tr><td>continuous</td><td>continuous</td><td>categorical</td><td>integer</td><td></td><td></td><td></td><td></td></tr></tbody></table>

2nd coding for z

Mixed, missing, uncertain

<table><thead><tr><th></th><th colspan="3">Individuals x<sup>O</sup></th><th colspan="3">Partition z</th><th>Group</th></tr></thead><tbody><tr><td>?</td><td>0.5</td><td>red</td><td>5</td><td>2</td><td>↔</td><td>G<sub>2</sub></td><td></td></tr><tr><td>0.3</td><td>0.1</td><td>green</td><td>3</td><td>1</td><td>↔</td><td>G<sub>1</sub></td><td></td></tr><tr><td>0.3</td><td>0.6</td><td>{red,green}</td><td>3</td><td>1</td><td>↔</td><td>G<sub>1</sub></td><td></td></tr><tr><td>0.9</td><td>[0.25 0.45]</td><td>red</td><td>?</td><td>3</td><td>↔</td><td>G<sub>3</sub></td><td></td></tr><tr><td>↓</td><td>↓</td><td>↓</td><td>↓</td><td></td><td></td><td></td><td></td></tr><tr><td>continuous</td><td>continuous</td><td>categorical</td><td>integer</td><td></td><td></td><td></td><td></td></tr></tbody></table>

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

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

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

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

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

Supervised classification (3/3)

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

<figure><img src="image_228.png" /></figure>
Semi-supervised classification (1/3)

■ Data: learning dataset $\mathcal{D} = \{\mathbf{x}^O, \mathbf{z}^O\}$

■ $n$ individuals: $\mathbf{x} = \{\mathbf{x}_1, \dots, \mathbf{x}_n\} = \{\mathbf{x}^O, \mathbf{x}^M\}$ belonging to a space $\mathcal{X}$

■ Observed individuals $\mathbf{x}^O$

■ Missing individuals $\mathbf{x}^M$

■ Partition: $\mathbf{z} = \{\mathbf{z}_1, \dots, \mathbf{z}_n\} = \{\mathbf{z}^O, \mathbf{z}^M\}$

■ Observed partition $\mathbf{z}^O$

■ Missing partition $\mathbf{z}^M$

■ Aim: estimation of an allocation rule $r$ from $\mathcal{D}$

$$r: \begin{array}{ccc} \mathcal{X} & \rightarrow & \{1, \dots, K\} \\ \mathbf{x}_{n+1}^{O} & \longmapsto & r(\mathbf{x}_{n+1}^{O}). \end{array}$$

■ Idea: $\mathbf{x}$ is cheaper than $\mathbf{z}$ so $\#\mathbf{z}^M \gg \#\mathbf{z}^O$

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

## Semi-supervised classification (2/3)

### Mixed, missing, uncertain

<table><thead><tr><th></th><th>Individuals x<sup>O</sup></th><th></th><th></th><th>Partition z<sup>O</sup></th><th>Group</th></tr></thead><tbody><tr><td>?</td><td>0.5</td><td>red</td><td>5</td><td>0 ? ?</td><td>G<sub>2</sub> or G<sub>3</sub></td></tr><tr><td>0.3</td><td>0.1</td><td>green</td><td>3</td><td>1 0 0</td><td>G<sub>1</sub></td></tr><tr><td>0.3</td><td>0.6</td><td>{ red, green }</td><td>3</td><td>?</td><td>???</td></tr><tr><td>0.9</td><td>[0.25 0.45]</td><td>red</td><td>?</td><td>0 0 1</td><td>G<sub>3</sub></td></tr><tr><td>↓</td><td>↓</td><td>↓</td><td>↓</td><td></td><td></td></tr><tr><td>continuous</td><td>continuous</td><td>categorical</td><td>integer</td><td></td><td></td></tr></tbody></table>

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

Semi-supervised classification (3/3)

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

<figure><img src="image_246.png" /></figure>
Unsupervised classification (1/3)

■ Data: learning dataset $\mathcal{D} = \mathbf{x}^O$, so $\mathbf{z}^O = \emptyset$

■ Aim: estimation of the partition $z^7$ and the number of groups $K$

■ Also known as: clustering

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

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

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

<footnote n="7">⁷We will see other clustering structures further, here to fix ideas with the main one</footnote>
<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>

Unsupervised classification (2/3)

Mixed, missing, uncertain

<table><thead><tr><th></th><th colspan="3">Individuals x<sup>O</sup></th><th colspan="3">Partition z<sup>O</sup> ⇔ Group</th></tr></thead><tbody><tr><td>?</td><td>0.5</td><td>red</td><td>5</td><td>?</td><td>?</td><td>???</td></tr><tr><td>0.3</td><td>0.1</td><td>green</td><td>3</td><td>?</td><td>?</td><td>???</td></tr><tr><td>0.3</td><td>0.6</td><td>{red,green}</td><td>3</td><td>?</td><td>?</td><td>???</td></tr><tr><td>0.9</td><td>[0.25 0.45]</td><td>red</td><td>?</td><td>?</td><td>?</td><td>???</td></tr><tr><td>↓</td><td>↓</td><td>↓</td><td>↓</td><td></td><td></td><td></td></tr><tr><td>continuous</td><td>continuous</td><td>categorical</td><td>integer</td><td></td><td></td><td></td></tr></tbody></table>

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

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

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

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

<figure><img src="image_269.png" /></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>

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

Unsupervised classification (3/3)

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

<figure><img src="image_287.png" /></figure>
Traditional solutions (1/3)

Two main model-based frameworks<fnref n="8" />

- Generative models

- Model $p(x, z)$

- Thus direct model for $p(x) = \sum_z p(x, z)$

- Easy to take into account some missing $z$ and $x$

- Predictive models

- Model $p(z|x)$ or sometimes $1_{\{p(z|x)>1/2\}}$ or also ranking on $p(z|x)$

- Avoid assumptions on $p(x)$, thus avoids associated error model

- difficult to take into account some missing $z$ and $x$

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

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

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

<footnote n="8">⁸Sometimes presented as distance-based instead of model-based: see some links in my 3th lesson</footnote>
Traditional solutions (2/3)

No mixed, missing or uncertain data:

■ Supervised classification<fnref n="9" />

■ Generative models: linear/quadratic discriminant analysis

■ Predictive models: logistic regression, support vector machines (SVM), k nearest
  neighbourhood, classification trees...

■ Semi-supervised classification<fnref n="10" />

■ Generative models: mixture models

■ Predictive models: low density separation (transductive SVM), graph-based methods...

■ Unsupervised classification<fnref n="11" />

■ Generative models: k-means like criteria, hierarchical clustering, mixture models

■ Predictive models: -

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

<footnote n="9">⁹Govaert et al., Data Analysis, Chap.6, 2009</footnote>

<footnote n="10">¹⁰Chapelle et al., Semi-supervised learning, 2006</footnote>

<footnote n="11">¹¹Govaert et al., Data Analysis, Chap.7-9, 2009</footnote>
<figure><img src="image_292.png" /></figure>

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

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

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

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

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

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

## Traditional solutions (3/3)

But more complex with mixed, missing or uncertain data...

* **Missing/uncertain data:** multiple imputation is possible but it should ideally take into account the classification purpose at hand

* **Mixed data:** some heuristic methods with recoding

We will gradually answer along the lessons:

How to marry the classification aim with mixed, missing or uncertain data?

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

1 Data

2 Classifications(s)

3 Clustering: motivation

4 Empirical procedures

5 Automatic procedures

6 Experiments

7 To go further

<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>
Clustering everywhere<fnref n="12" />

Regression, Cluster Analysis, & Decision Trees: The Core Algorithm Triad

RA

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

What algorithms/analytic methods do you TYPICALLY use?

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

Rexer Analytics' surveys since 2007 have consistently shown that data scientists primarily work with the algorithm triad of regression, decision trees, and cluster analysis. In every survey since 2007, over half of respondents reported using each of these methods in the prior year. Among these three, regression is clearly dominant, with more than two thirds (67%) of respondents indicating that they use regression "often" or "most of the time".

On average 2017 respondents use 11 different algorithms in the course of their work (slightly down from 12 in 2015). Despite extensive media hype about AI, Cognitive Computing, Deep Learning, and the rise of machine learning and its related algorithms, no algorithms showed substantial increased usage since the 2015 survey.

RA) REXER
ANALYTICS
2018

© 2016 REXER Analytics

Why such a success despite its complexity relatively to other classification purposes?

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

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

<footnote n="12">¹²Rexer Analytics's Annual Data Miner Survey is the largest survey of data mining, data science, and analytics professionals in the industry (survey of 2018)</footnote>
<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>

A 1st aim: explanatory task

■ A clustering for a **marketing study**

■ **Data:** *d* = 13 demographic attributes (nominal and ordinal variables) of *n* = 6 876 shopping mall customers in the San Francisco Bay (SEX (1. Male, 2. Female), MARITAL STATUS (1. Married, 2. Living together, not married, 3. Divorced or separated, 4. Widowed, 5. Single, never married), AGE (1. 14 thru 17, 2. 18 thru 24, 3. 25 thru 34, 4. 35 thru 44, 5. 45 thru 54, 6. 55 thru 64, 7. 65 and Over), etc.)*

■ **Partition:** retrieve less that 19 999$ (group of “low income”), between 20 000$ and 39 999$ group of “average income”), more than 40 000$ (group of “high income”).)

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

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

Another explanatory example: acoustic emission control

■ Data: $n = 2$ 061 event locations in a rectangle of $\mathbb{R}^2$ representing the vessel

■ Groups: sound locations = vessel defects

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

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

A 2nd aim: preprocessing step (1/2)

A synthetic example in **supervised classification**: predict two groups (blue and black)<fnref n="13" />

■ Logit model:

■ Not very flexible since linear borderline

■ Unbiased ML estimate but asymptotic variance ~ $(x'wx)^{-1}$ is influenced by correlations

$$ \operatorname{logit}(\mathbf{p}(\text{blue}|\mathbf{x}_{n+1})) = \beta' \mathbf{x}_{n+1} $$

■ A clustering may improve logistic regression prediction

■ More flexible borderline: piecewise linear

■ Decrease correlation so decrease variance

$$ \operatorname{logit}(\mathbf{p}(\text{blue}|\mathbf{x}_{n+1})) = \beta'_{z_{n+1}} \mathbf{x}_{n+1} $$

Do not confound groups blue and black and clusters $z_{n+1}!!$

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

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

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

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

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

<footnote n="13">¹³Another lesson will retain a similar idea through a mixture of regressions</footnote>
<figure><img src="image_371.png" /></figure>

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

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

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

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

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

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

A 2nd aim: preprocessing step (2/2)

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

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

1. Data

2. Classifications(s)

3. Clustering: motivation

4. Empirical procedures

5. Automatic procedures

6. Experiments

7. To go further

<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>
A first systematic attempt

■ Carl von Linné (1707–1778), Swedish botanist, physician, and zoologist

■ Father of modern taxonomy based on the most *visible similarities* between species

■ *Linnaeus's Systema Naturae* (1st ed. in 1735) lists about 10,000 species of organisms (6,000 plants, 4,236 animals)

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

<figure><img src="image_392.png" /></figure>
Remind data we use

Data set of *n* individuals **x** = (**x**₁, . . . , **x**ₙ), **x**ᵢ described by *d* variables

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

<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>
Four main clustering structures: partition

Each object belongs to exactly one cluster

■ Definition: a set of *K* non-empty parts of **x**: $P = (G_1, \dots, G_K)$

■ For all $k \neq k'$, $G_k \cap G_{k'} = \emptyset$

■ $G_1 \cup \dots \cup G_K = \mathbf{x}$

■ Example: $\mathbf{x} = \{a, b, c, d, e\}$

$$P = \underbrace{\{a, b\}}_{G_1} \underbrace{\{c, d, e\}}_{G_2}$$

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

■ Notation: $z = (z_1, \dots, z_n)$, with $z_i \in \{1, \dots, K\}$

<figure><img src="image_412.png" /></figure>
Four main clustering structures: partition with outliers

Each object belongs to one cluster or less

■ Definition: a set of *K* non-empty parts of **x**: $P = (G_1, \dots, G_K)$:

■ For all $k \neq k'$, $G_k \cap G_{k'} = \emptyset$

■ $G_1 \cup \dots \cup G_K \subseteq \mathbf{x}$

■ Example: $\mathbf{x} = \{a, b, c, d, e\}$

$$P = \{\underbrace{\{a, b\}}_{G_1}, \underbrace{\{d, e\}}_{G_2}\}, \text{ c excluded}$$

c

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

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

■ See more in Lesson 3

<figure><img src="image_415.png" /></figure>
Four main clustering structures: multiclass partition

Each object belongs to one cluster or more

■ Definition: a set of *K* non-empty parts of **x**: $P = (G_1, \dots, G_K)$

■ $G_1 \cup \dots \cup G_K = \mathbf{x}$

■ Example: $\mathbf{x} = \{a, b, c, d, e\}$

$$P = \{ \underbrace{\{a, b, c\}}_{G_1}, \underbrace{\{c, d, e\}}_{G_2} \}$$

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

■ Not considered in lessons

<figure><img src="image_417.png" /></figure>
Four main clustering structures: hierarchy

Each object belongs to nested partitions

■ Definition: *H* is a hierarchy of *x* if

■ $x \in H$

■ For any $x_i \in x$, $\{x_i\} \in H$

■ For any $G_1, G_2 \in H$, $G_1 \cap G_2 \in \{G_1, G_2, \emptyset\}$

■ Example: $x = \{a, b, c, d, e\}$

$$H = \{\{a\}, \{b\}, \{c\}, \{d\}, \{e\}, \{d, e\}, \{a, b\}, \{c, d, e\}, \{a, b, c, d, e\}\}$$

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

■ Case of the species taxonomy

<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" /></figure>

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

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

<figure><img src="image_425.png" /></figure>
Four main clustering structures: indexed hierarchy

Each element of a hierarchy is associated to an index value

■ Definition: $ι: H \to \mathbb{R}^+$ is an index of a hierarchy H if

■ $ι$ is a non-decreasing mapping: $(G_1, G_2) \in H^2$, $G_1 \subset G_2$, $G_1 \neq G_2 \Rightarrow ι(G_2) < ι(G_1)$

■ For all $x_i \in x$, $ι(\{x_i\}) = 0$

■ The couple $(H, ι)$ is an indexed hierarchy and can be visualized by a dendrogram

■ Example (continued):

$$H = \{ \underbrace{\{a\}}_{0}, \underbrace{\{b\}}_{0}, \underbrace{\{c\}}_{0}, \underbrace{\{d\}}_{0}, \underbrace{\{e\}}_{0}, \underbrace{\{d, e\}}_{1}, \underbrace{\{a, b\}}_{2}, \underbrace{\{c, d, e\}}_{2.5}, \underbrace{\{a, b, c, d, e\}}_{5} \}$$

<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>
Interdisciplinary endeavour

Typology

From Wikipedia, the free encyclopedia

Typology is the study of types. Typology may refer to:

* Typology (anthropology), division of culture by races

* Typology (archaeology), classification of artifacts according to their characteristics

* Typology (linguistics), study and classification of languages according to their structural features

* Typology (psychology), a model of personality types

* Typology (theology), in Christian theology, the interpretation of some figures and events in the Old Testament as foreshadowing the New Testament

* Typology (urban planning and architecture), the classification of characteristics common to buildings or urban spaces

* Typology (statistics), a concept in statistics, research design and social sciences

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

Look up typology
*typologist*, *typological*, or
*typologically*, in Wiktionary,
the free dictionary

<figure><img src="image_434.png" /></figure>
Limit of visualization (1/3)

Prostate cancer data¹⁴

- **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%)

Questions

- Doctors say two stages of the disease are *well* separated with the variables

- We forget the classes (Stages of the disease) to retrieve clustering by visualizing

<figure><img src="image_435.png" /></figure>
Limit of visualization (2/3)

- Perform PCA for continuous variables, MCA for categorical ones

- Discard missing values since not convenient for traditional PCA and MCA

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

We do not “see” anything...

<figure><img src="image_437.png" /></figure>
Limit of visualization (2/3)

If we have a look at the true partition, indeed visualizing was not enough...

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

Need to define more "automatic" methods acting directly in the space $\mathcal{X}$

<figure><img src="image_439.png" /></figure>
# Clustering is the cluster building process

## Cluster analysis

From Wikipedia, the free encyclopedia

*For the supervised learning approach, see Statistical classification.*

**Cluster analysis or clustering** is the task of grouping a set of objects in such a way that objects in the same group (called a **cluster**) are more similar (in some sense or another) to each other than to those in other groups (clusters). It is a main task of exploratory data mining, and a common technique for statistical data analysis, used in many fields, including machine learning, pattern recognition, image analysis, information retrieval, and bioinformatics.

Cluster analysis itself is not one specific algorithm, but the general task to be solved. It can be achieved by various algorithms that differ significantly in their notion of what constitutes a cluster and how to efficiently find them.

* According to JSTOR, **data clustering** first appeared in the title of a 1954 article dealing with anthropological data

* Need to be automatic (**algorithms**) for complex data: mixed features, large data sets, high-dimensional data...

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

1. Data

2. Classifications(s)

3. Clustering: motivation

4. Empirical procedures

5. Automatic procedures

6. Experiments

7. To go further

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

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

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

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

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

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

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

Clustering of clustering algorithms¹⁵

* Jain et al. (2004) hierarchical clustered 35 different clustering algorithms into 5 groups based on their partitions on 12 different datasets.

* It is not surprising to see that the related algorithms are clustered together.

* For a visualization of the similarity between the algorithms, the 35 algorithms are also embedded in a two-dimensional space obtained from the 35x35 similarity matrix.

<figure><img src="image_457.png" /><figcaption>Figure 10 Clustering of clustering algorithms. (a) Hierarchical clustering of 35 different algorithms; (b) Sammon's mapping of the 35 algorithms into a two-dimensional space, with the clusters highlighted for visualization. The algorithms in the group (4, 29, 31-35) correspond to K-means, spectral clustering, Gaussian mixture models, and Ward's linkage. The algorithms in group (6, 8-10) correspond to CHAMELEON algorithm with different objective functions.</figcaption></figure>

<figure><img src="image_458.png" /></figure>
# Dissimilarities, distances, similarities: definitions

## General idea

* Put in the same cluster individuals $x_1$ and $x_2$ which are similar

* Put in different clusters individuals $x_1$ and $x_2$ which are dissimilar

* Definition of a dissimilarity $\delta: \mathcal{X} \times \mathcal{X} \to \mathbb{R}^+$

* Separation: for any $(x_1, x_2) \in \mathcal{X}^2$, $\delta(x_1, x_2) = 0 \Leftrightarrow x_1 = x_2$

* Symmetry: for any $(x_1, x_2) \in \mathcal{X}^2$, $\delta(x_1, x_2) = \delta(x_2, x_1)$

* Definition of a distance $\delta: \mathcal{X} \times \mathcal{X} \to \mathbb{R}^+$: it is a dissimilarity with a new property

* Triangular inequality: for any $(x_1, x_2, x_3) \in \mathcal{X}^3$, $\delta(x_1, x_2, x_3) \le \delta(x_1, x_2) + \delta(x_2, x_3)$

* Definition of a similarity (or affinity) $s: \mathcal{X} \times \mathcal{X} \to \mathbb{R}^+$

* For any $x_1 \in \mathcal{X}$, $\delta(x_1, x_1) = s_{\max}$ with $s_{\max} \ge s(x_1, x_2)$ for any $(x_1, x_2) \in \mathcal{X}^2$, $x_1 \ne x_2$

* Symmetry: for any $(x_1, x_2) \in \mathcal{X}^2$, $s(x_1, x_2) = s(x_2, x_1)$

Often dissimilarities (or similarities) are enough for clustering

<figure><img src="image_459.png" /></figure>
Similarities, dissimilarities, distances: examples for quantitative data

$$ \mathcal{X} = \mathbb{R}^d $$

■ Euclidean distance (or $L_1$ norm) with metric $\mathbf{M}$:

$$ \delta_{\mathbf{M}}(\mathbf{x}_1; \mathbf{x}_2) = \|\mathbf{x}_1 - \mathbf{x}_2\|_{\mathbf{M}} = \sqrt{(\mathbf{x}_1 - \mathbf{x}_2)' \mathbf{M} (\mathbf{x}_1 - \mathbf{x}_2)} $$

with a metric $\mathbf{M}$: symmetric and positive definite $d \times d$ matrix

■ Manhattan distance or city-block distance or $L_1$ norm:

$$ \delta(\mathbf{x}_1, \mathbf{x}_2) = \sum_{j=1}^{d} \|\mathbf{x}_{1j} - \mathbf{x}_{2j}\| $$

■ ...

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

<figure><img src="image_461.png" /></figure>
Similarities, dissimilarities, distances: examples for binary data

$$ \mathcal{X} = \{0,1\}^d \text{ thus } \mathbf{x}_{ij} \in \{0,1\} $$

■ The Hamming distance counts the dimensions on which both vectors are different:

$$ \delta(\mathbf{x}_1, \mathbf{x}_2) = \sum_{j=1}^{d} \mathbb{I}_{\{\mathbf{x}_{1j} \neq \mathbf{x}_{2j}\}} $$

■ The matching coefficient counts dimensions on which both vectors are non-zero:

$$ \delta(\mathbf{x}_1, \mathbf{x}_2) = \sum_{j=1}^{d} \mathbb{I}_{\{\mathbf{x}_{1j}=\mathbf{x}_{2j}=1\}} $$

■ ...

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

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

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

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

<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" /></figure>

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

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

A lot of dissimilarities and distances...

For instance, in the binary case<fnref n="16" />:

<figure><img src="image_485.png" /><figcaption>Figure 2: Hierarchical Clustering Result of Random Binary Data Set</figcaption></figure>

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

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

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

<footnote n="16">¹⁶S.-S. Choi, S.-H. Cha, C. C. Tappert (2010). A Survey of Binary Similarity and Distance Measures. Systemics, Cybernetics and INinformatics, 8, 1–43–48.</footnote>
Similarities, dissimilarities, distances: similarities proposals

■ It is easy to construct similarities from dissimilarities or distances

■ A typical example:

$$s(\mathbf{x}_1, \mathbf{x}_2) = \exp(-\delta(\mathbf{x}_1, \mathbf{x}_2))$$

Thus $s_{\max} = 1$

■ The Gaussian similarity is an important case ($\sigma > 0$):

$$s(\mathbf{x}_1, \mathbf{x}_2) = \exp \left( - \frac{\| \mathbf{x}_1 - \mathbf{x}_2 \|^2}{2\sigma^2} \right)$$

<figure><img src="image_500.png" /></figure>
Weaken a two restrictive requirement

The property that two individuals in the same cluster are closer than any other individual in another cluster is two strong

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

Relax this **local** criterion by a **global** criterion

<figure><img src="image_502.png" /></figure>
Within-cluster inertia criterion

Select the partition z minimizing the criterion

$$W_M(z) = \sum_{i=1}^{n} \sum_{k=1}^{K} z_{ik} \|x_i - \bar{x}_k\|_M^2$$

■ Look for compact clusters (individuals of the same cluster are close from each other)

■ $\| \cdot \|_M$ is the Euclidian distance with metric $M$ in $\mathbb{R}^d$

■ $\bar{x}_k$ is the mean (or center) of the kth cluster

$$\bar{x}_k = \frac{1}{n_k} \sum_{i=1}^{n_k} z_{ik} x_i$$

and $n_k = \sum_{k=1}^{n} z_{ik}$ indicates the number of individuals in cluster k

<figure><img src="image_503.png" /></figure>
Between-cluster inertia criterion

Select the partition z maximizing the criterion

$$B_M(z) = \sum_{k=1}^{K} n_k \|\bar{x} - \bar{x}_k\|_M^2$$

■ Look for clusters far from each other

■ $\bar{x}$ the mean (or center) of the whole data set x:

$$\bar{x} = \frac{1}{n} \sum_{i=1}^{n} x_i$$

■ It is in fact equivalent to minimize $W_M(z)$ since

$$B_M(z) + W_M(z) = \text{cste}$$

<figure><img src="image_504.png" /></figure>
A combinatorial problem

■ Number of possible partitions z: $\#\{z\} \approx \frac{K^n}{K!}$

■ For instance : $n = 40$, $K = 3$, $\#\{z\} \approx 2.10^{18}$ (two billion of billion), thus about 64000 years for a computer calculating one million of partitions per second

■ Thus impossible to minimize directly $W_M(z)$

■ But equivalent to minimize on z and $\mu = \{\mu_1, \dots, \mu_K\}$ with $\mu_k \in \mathbb{R}^d$, the criterion

$$ \tilde{W}_M(z, \mu) = \sum_{i=1}^{n} \sum_{k=1}^{K} z_{ik} \|x_i - \mu_k\|_M^2 $$

It leads to the famous K-means algorithm

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

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

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

K-means algorithm

Alternating optimization between the partition **z** and the center **μ** of clusters

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

données

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

2 individus au hasard

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

affection aux centres

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

calcul des centres

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

affection aux centres

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

calcul des centres

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

affection aux centres

Algorithme des centres mobiles

■ Start from a random $\mu$ among $x$ (avoid to start from a random $z$)

■ Each iteration decreases the criterion $\tilde{W}_M(z, \mu)$ (so also $W_M(z)$)

■ Converge into a finite (and often low) number of iterations

■ Memory complexity $O((n + K)d)$, time complexity $O(nb \cdot \text{iter} \cdot Kdn)$

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

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

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

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

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

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

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

<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>
Fuzzy within-cluster inertia criterion

Select the fuzzy partition **c** minimizing the criterion

$$
W_{M,m}^{\text{fuzzy}}(\mathbf{c}) = \sum_{i=1}^{n} \sum_{k=1}^{K} c_{ik}^{m} \|\mathbf{x}_{i} - \bar{\mathbf{x}}_{k}\|_{M}^{2}
$$

■ Fuzzy partition **c** = {**c**₁, ..., **c**ₖ}, **c**ₖ = (c₁ₖ, ..., cₙₖ), cᵢₖ ∈ [0, 1] defined by

$$
c_{ik} = \frac{1}{\sum_{k'=1}^{K} \left( \frac{\| \mathbf{x}_i - \bar{\mathbf{x}}_k \|_{\mathbf{M}}}{\| \mathbf{x}_i - \bar{\mathbf{x}}_{k'} \|_{\mathbf{M}}} \right)^{\frac{2}{m-1}}}
$$

■ $m \ge 1$ determines the level of cluster fuzziness: $m$ large produces fuzzier clusters;
$m = 1$ (in the limit) produces hard clustering ($m$ converges to 0 or 1)

■ $\bar{\mathbf{x}}_k$ is the fuzzy mean (or center) of the $k$th cluster

$$
\bar{\mathbf{x}}_k = \frac{1}{n_k} \frac{\sum_{i=1}^{n} c_{ik}^m \mathbf{x}_i}{\sum_{i=1}^{n} c_{ik}^m}
$$

and $n_k = \sum_{k=1}^{n} c_{ik}$ indicates the fuzzy number of individuals in cluster $k$

■ Optimize $W_{M,m}^{\text{fuzzy}}(\mathbf{c})$ (through $\tilde{W}_{M,m}^{\text{fuzzy}}(\mathbf{c}, \mu)$) by the fuzzy K-means algorithm

<figure><img src="image_532.png" /></figure>
Kernel clustering: the idea

■ Original (input) space: **non-linearly separable** clusters

■ Feature space: a **non-linear** mapping $\phi$ to a higher-dimensional space

$$ \phi: \mathcal{X} \mapsto \mathcal{Y} \\ \mathbf{x}_i \mapsto \phi(\mathbf{x}_i) $$

■ Expected property: **linearly separable** clusters in the feature space

■ Difficulty: define $\phi$

■ The “kernel trick”: not necessary to define $\phi$, **define just an inner product**

$$ \kappa(\mathbf{x}_i, \mathbf{x}_{i'}) = \phi(\mathbf{x}_i)' \phi(\mathbf{x}_{i'}) $$

$\kappa$ is so-called a **kernel**

■ Lesson 4: more arguments on the discriminant interest of higher dimension

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

Kernel clustering: illustration

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

<figure><img src="image_542.png" /></figure>
Kernel clustering: fuzzy within-cluster rewriting

■ $W^{\text{fuzzy}}$ with the data set $\phi(\mathbf{x}) = \{\phi(\mathbf{x}_1), \dots, \phi(\mathbf{x}_n)\}$ (we drop $\mathbf{M}$ and $m$)

$$W^{\text{fuzzy}}(\mathbf{c}) = \sum_{i=1}^{n} \sum_{k=1}^{K} c_{ik}^{m} \|\phi(\mathbf{x}_{i}) - \bar{\phi}_{k}(\mathbf{x})\|^{2}$$

with

$$\bar{\phi}_k(\mathbf{x}) = \frac{1}{n_k} \frac{\sum_{i=1}^{n} c_{ik}^{m} \phi(\mathbf{x}_i)}{\sum_{i=1}^{n} c_{ik}^{m}} \quad \text{and} \quad c_{ik} = \frac{1}{\sum_{k'=1}^{K} \left( \frac{\|\phi(\mathbf{x}_i) - \bar{\phi}_k(\mathbf{x})\|}{\|\phi(\mathbf{x}_i) - \phi_{k'}(\mathbf{x})\|} \right)^{\frac{2}{m-1}}}$$

■ After some algebra, only appears inside an inner product since:

$$\begin{align*}
\|\phi(\mathbf{x}_i) - \bar{\phi}_k(\mathbf{x})\|^2 &= \phi(\mathbf{x}_j)' \phi(\mathbf{x}_i) - 2 \frac{\sum_{i=1}^{n} c_{ik}^{m} \phi(\mathbf{x}_i)' \phi(\mathbf{x}_{i'})}{\sum_{i'=1}^{n} c_{i'k}^{m}} + \frac{\sum_{i'=1}^{n} \sum_{i''=1}^{n} c_{i'k}^{m} c_{i''k}^{m} \phi(\mathbf{x}_{i'})' \phi(\mathbf{x}_{i''})}{(\sum_{i'=1}^{n} c_{i'k}^{m})^2} \\
&= \kappa(\mathbf{x}_i, \mathbf{x}_i) - 2 \frac{\sum_{i=1}^{n} c_{ik}^{m} \kappa(\mathbf{x}_i, \mathbf{x}_{i'})}{\sum_{i'=1}^{n} c_{i'k}^{m}} + \frac{\sum_{i'=1}^{n} \sum_{i''=1}^{n} c_{i'k}^{m} c_{i''k}^{m} \kappa(\mathbf{x}_{i'}, \mathbf{x}_{i''})}{(\sum_{i'=1}^{n} c_{i'k}^{m})^2}
\end{align*}$$

Consequently, need only to define $\kappa$ for performing the (fuzzy) K-means...

<figure><img src="image_543.png" /></figure>
Kernel clustering: kernel examples

■ Polynomial

$$\kappa(\mathbf{x}_i, \mathbf{x}_{i'}) = (\mathbf{x}'_i \mathbf{x}_{i'} + a)^b$$

■ Gaussian

$$\kappa(\mathbf{x}_i, \mathbf{x}_{i'}) = \exp(-\|\mathbf{x}_i - \mathbf{x}_{i'}\|/(2\sigma^2))$$

■ Sigmoid

$$\kappa(\mathbf{x}_i, \mathbf{x}_{i'}) = \tanh(a\mathbf{x}'_i \mathbf{x}_{i'} + b)$$

<figure><img src="image_544.png" /></figure>
Spectral clustering: the idea<fnref n="17" />

■ Build a similarity matrix $S$ $n \times n$ from $x$:

$$S_{ii'} = s_{ii'} \text{ if } i \neq i', \quad S_{ii} = 0$$

■ Similarities can be viewed as proximities between individuals (nodes) in a graph

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

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

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

■ If some disconnected sub-graphs, $S$ can be reordered as block diagonal

<figure><img src="image_548.png" /><figcaption>(a) Well-separated clusters.</figcaption></figure>

<figure><img src="image_549.png" /><figcaption>(b) Similarity matrix sorted by cluster labels.</figcaption></figure>

■ We “can see” the clusters thus clustering is expected to be easy

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

<footnote n="17">¹⁷Figures from [A. Jain *at al.*. Data Clustering: A Review.]</footnote>
Spectral clustering: Laplacian matrix

■ For technical reasons, we study (unnormalized graph) Laplacian L instead of S

$$L = D - S$$

where $D = \text{diag}(d_1, \dots, d_n)$ is the diagonal degree matrix with $d_i = \sum_{i'=1}^n S_{ii'}$

■ Have in mind S if easier ; the structure of L is similar

Properties of L

1. For every vector $u = (u_1, \dots, u'_n) \in \mathbb{R}^n$, we have

$$u'Lu = \frac{1}{2} \sum_{i=1}^{n} \sum_{i'=1}^{n} s_{ii'} (u_i - u_{i'})^2$$

2. L is symmetric and positive semi-definite

3. The smallest eigenvalue of L is 0, the corresponding eigenvector is the constant one vector $1 = (1, \dots, 1)' \in \mathbb{R}^n$

4. L has n non-negative, real-valued eigenvalues $0 = \lambda_1 \le \lambda_2 \le \dots \le \lambda_n$

<figure><img src="image_551.png" /></figure>
# Spectral clustering: specific spectral structure of L

## Linking clusters and L

1. The multiplicity $K$ of the eigenvalue 0 of $L$ equals the number of clusters $G_1, \dots, G_K$ (or the connected components in the graph)

2. The eigenspace of eigenvalue 0 is spanned by the indicator vectors $1_{G_1}, \dots, 1_{G_K}$ of those components, where $1_{G_k}(i) = 1$ if $x_i \in G_k$, zero otherwise

## [A. Singh (2010). Spectral Clustering. Machine Learning.]

* If graph is connected, first Laplacian eigvec is constant (all 1s)

* If graph is disconnected (k connected components), Laplacian is block diagonal and first k Laplacian evecs are:

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

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

<figure><img src="image_554.png" /><figcaption>First three eigenvectors</figcaption></figure>

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

<figure><img src="image_556.png" /></figure>
Spectral clustering: eigenvectors as new data to cluster

■ Define a new data set $\mathbf{y} = \{\mathbf{y}_1, \dots, \mathbf{y}_n\} \in \mathbb{R}^K$ where

$$ \mathbf{y}_i = (\mathbf{1}_{G_1}(i), \dots, \mathbf{1}_{G_K}(i)) $$

■ From the previous property, $y_i$s in the same clusters are very similar...

■ ...whereas $y_i$s in different clusters are very different

■ Thus just run a K-means (for instance) to finish the clustering job!

[A.K. Jain (2008). Data Clustering: 50 Years Beyond K-Means]

<figure><img src="image_557.png" /><figcaption>Figure 5 Importance of a good representation (a) “Two rings” dataset where K-means fails to find the two “natural” clusters; the dashed line shows the linear cluster separation boundary obtained by running K-means with K = 2. (b) a new representation of the data in (a) based on the top 2 eigenvectors of the graph Laplacian of the data, computed using an RBF kernel. K-means now can easily detect the two clusters</figcaption></figure>

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

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

<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>
Spectral clustering: summary<fnref n="18" />

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

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

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

<footnote n="18">¹⁸ [J. Suykens and C. Alzate (2011). Kernel spectral clustering: model representations, sparsity and out-of-sample extensions.]</footnote>
Spectral clustering: some last elements

■ Other Laplacian choices are possible, as the normalized one

$$L^{\text{norm}} = D^{-1/2}LD^{-1/2} = I - D^{-1/2}SD^{-1/2}$$

■ Its overall complexity is $O(n^2)$ thus problem when $n$ large

■ It is in fact equivalent to kernel K-means modulo relaxed version<fnref n="19" />

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

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

<footnote n="19">¹⁹See details in [I.S. Dhillon et al. (2004). Kernel kmeans, Spectral Clustering and Normalized Cuts. KDD'04.]</footnote>
# Hierarchical agglomerative clustering: algorithm

## Aim

Design a procedure to build an indexed hierarchy

* **Start:** make a dissimilarity matrix from $\delta$ between singletons $\{x_i\}$ of $x$

* **Iterations:**

* Merge two clusters that are the closest from a linkage criterion $\Delta$

* Compute dissimilarities between new clusters

* **End:** as soon as a unique cluster

* Need to define $\Delta: H \times H \rightarrow \mathbb{R}^+$ from $\delta$

* If $\Delta$ is non-decreasing, it defines an index on the final hierarchy

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

Single linkage criterion

$$ \Delta(G_1, G_2) = \min\{\delta(\mathbf{x}_i, \mathbf{x}_{i'}) : \mathbf{x}_i \in G_1, \mathbf{x}_{i'} \in G_2\} $$

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

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

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

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

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

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

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

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

<figure><img src="image_604.png" /></figure>
<figure><img src="image_605.png" /></figure>

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

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

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

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

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

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

Complete linkage criterion

$$ \Delta(G_1, G_2) = \max\{\delta(\mathbf{x}_i, \mathbf{x}_{i'}) : \mathbf{x}_i \in G_1, \mathbf{x}_{i'} \in G_2\} $$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

<figure><img src="image_629.png" /></figure>
Average linkage criterion

$$ \Delta(G_1, G_2) = \frac{1}{n_1 n_2} \sum_{\mathbf{x}_i \in G_1} \sum_{\mathbf{x}_{i'} \in G_2} \delta(\mathbf{x}_i, \mathbf{x}_{i'}) $$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

<figure><img src="image_645.png" /></figure>
<figure><img src="image_646.png" /></figure>

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

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

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

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

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

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

Ward linkage criterion

$$ \Delta(G_1, G_2) = \frac{n_1 n_2}{n_1 + n_2} \delta^2(\mu_1, \mu_2) $$

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

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

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

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

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

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

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

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

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

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

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

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

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

<figure><img src="image_666.png" /></figure>
Hierarchical agglomerative clustering: Ward example

<figure><img src="image_667.png" /><figcaption>Classification hiérarchique ascendante
(méthode de Ward)</figcaption></figure>

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

■ A partition is obtained by cutting the dendrogram

■ A dissimilarity matrix between pairs of individuals is enough

■ Memory complexity $O(n^2 \ln n)$, space complexity $O(n^2)$ (do not scale well...)

■ Suboptimal optimisation of $W_M(\cdot)$ (see next slide)

<figure><img src="image_669.png" /></figure>
Link between Ward and K-means

Two successive Ward hierarchical algorithm iterations minimize W

■ Partition at a given iteration: $P = \{G_1, \dots, G_K, G_{K+1}, G_{K+2}\}$

$$W(P) = \sum_{k=1}^{K} \sum_{x_i \in G_k} \delta(x_i, \mu_k) + \sum_{x_i \in G_{K+1}} \delta(x_i, \mu_{K+1}) + \sum_{x_i \in G_{K+2}} \delta(x_i, \mu_{K+2})$$

■ Partition at the next iteration: $P^+ = \{G_1, \dots, G_K, \underbrace{G_{K+1} \cup G_{K+2}}_{G_{K+1}^+}$

$$W(P^+) = \sum_{k=1}^{K} \sum_{x_i \in G_k} \delta(x_i, \mu_k) + \sum_{x_i \in G_{K+1} \cup G_{K+2}} \delta(x_i, \mu_{K+1}^+)$$

■ After some algebra and using the Koenig-Huygens theorem, we obtain

$$W(P^+) - W(P) = \frac{n_{K+1} n_{K+2}}{n_{K+1} + n_{K+2}} \delta(\mu_{K+1}, \mu_{K+2})$$

■ Thus, it is like performing K-means under (partial) partition P constraints

<figure><img src="image_670.png" /></figure>
Popularity of *K*-means and hierarchical clustering

Even *K*-means was first proposed over 50 years ago, it is still one of the most widely used algorithms for clustering for several reasons: ease of implementation, simplicity, efficiency, empirical success... and model-based interpretation (see later)

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

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

1 Data

2 Classifications(s)

3 Clustering: motivation

4 Empirical procedures

5 Automatic procedures

6 Experiments

7 To go further

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

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

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

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

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

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

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

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

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

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

<figure><img src="image_683.png" /></figure>
# Data set used for illustration

## US State Facts and Figures

### Description

Data sets related to the 50 states of the United States of America.

**state.x77:** matrix with 50 rows and 8 columns giving the following statistics in the respective columns.

**Population:** population estimate as of July 1, 1975

**Income:** per capita income (1974)

**Illiteracy:** illiteracy (1970, percent of population)

**Life Exp:** life expectancy in years (1969-71)

**Murder:** murder and non-negligent manslaughter rate per 100,000 population (1976)

**HS Grad:** percent high-school graduates (1970)

**Frost:** mean number of days with minimum temperature below freezing (1931-1960) in capital or large city

**Area:** land area in square miles

### Source

U.S. Department of Commerce, Bureau of the Census (1977) *Statistical Abstract of the United States*.

U.S. Department of Commerce, Bureau of the Census (1977) *County and City Data Book*.

### References

Becker, R. A., Chambers, J. M. and Wilks, A. R. (1988) *The New S Language*. Wadsworth & Brooks/Cole.

<figure><img src="image_684.png" /></figure>
<figure><img src="image_685.png" /></figure>

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

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

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

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

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

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

# HCA & kmeans example

Load data US census

5]: data(state)
plot(state.center,type='n') # affiche position etats...
text(state.center,state.abb) # ... avec abréviations

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

<figure><img src="image_693.png" /></figure>
<figure><img src="image_694.png" /></figure>

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

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

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

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

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

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

CAH avec "complete" linkage

```r
]: hc <- hclust(dist(state.x77), method='complete') # CAH...
plot(hc,hang=1) # ... + dendogramme
partitionUS <- cutree(hc,4) # partition en 4 classes
plot(state.center,pch=partitionUS,col=partitionUS) # répartition géographique
```

<figure><img src="image_701.png" /><figcaption>diststate.x77
hclust(., "complete")</figcaption></figure>

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

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

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

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

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

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

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

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

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

<figure><img src="image_711.png" /></figure>
CAH avec "Ward" linkage

[8]: hc <- hclust(dist(state.x77), method='ward.D2') # CAH...
plot(hc, hang=1) # ... and dendogramme
partitionUS <- cutree(hc,4) # partition en 4 classes
plot(state.center, pch=partitionUS, col=partitionUS) # répartition géographique

Cluster Dendrogram

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

dist(state.x77)
heuder ("Ward.D2")

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

<figure><img src="image_714.png" /></figure>
Data

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

Classifications(s)

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

Clustering: motivation

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

Empirical procedures

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

Automatic procedures

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

Experiments

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

To go further

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

kmeans en 4 classes

[9]: km <- kmeans(state.x77, 4, nstart=5) plot(state.center, pch=km$cluster, col=km$cluster) # répartition géographique

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

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

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

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

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

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

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

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

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

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

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

1 Data

2 Classifications(s)

3 Clustering: motivation

4 Empirical procedures

5 Automatic procedures

6 Experiments

7 To go further

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

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

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

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

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

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

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

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

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

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

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

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

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

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

<figure><img src="image_747.png" /></figure>
Data
○○○○○
○○○○○○

Classifications(s)
○○○○○○○○○○○
○○○○○○

Clustering: motivation
○○○○○○
○○○○○

Empirical procedures
○○○○○○○○○○○
○○○○○○

Automatic procedures
○○○○○○○○○○○
○○○○○○○○○○○○

Experiments
○○○○○○
○○○○○

To go further
○●○○

Packages

■ R (statistical community): have a look at the CRAN library

■ Python (machine learning community): have a look at the scikit-learn library

<figure><img src="image_748.png" /></figure>
Semi-supervised clustering²⁰

■ The user has to provide any external information he has on the partition

■ Pair-wise constraints:

■ A *must-link* constraint specifies that the point pair connected by the constraint belong to the same cluster

■ A *cannot-link* constraint specifies that the point pair connected by the constraint do not belong to the same cluster

■ Attempts to derive constraints from domain ontology and other external sources into clustering algorithms include the usage of WordNet ontology, gene ontology, Wikipedia, etc. to guide clustering solutions

<figure><img src="image_749.png" /><figcaption>**Figure 12** Semi-supervised learning (a) Input image with must-link (solid blue lines) and must not link (broken red lines) constraints. (b) Clustering (segmentation) without constraints. (c) Improved clustering with 10% of the data points included in the pair-wise constraints [6].</figcaption></figure>
Online clustering

* Dynamic data are quite recent: blogs, Web pages, retail chain, credit card transaction streams, network packets received by a router and stock market, etc.

* As the data gets modified, clustering must be updated accordingly: ability to detect emerging clusters, etc.

* Often all data cannot be stored on a disk

* This imposes additional requirements to traditional clustering algorithms to rapidly process and summarize the massive amount of continuously arriving data

* Data stream clustering a significant challenge since they are expected to involved single-pass algorithms

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

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

<figure><img src="image_752.png" /></figure>
Next lesson

Clustering : une vision unifiée pour une utilisation éclairée

**Evaluation d'une méthode de clustering**

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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