# Multiple partition clustering

Vincent Vandewalle, Matthieu Marbac, Marie Du Roy de Chaumaray

► To cite this version:

Vincent Vandewalle, Matthieu Marbac, Marie Du Roy de Chaumaray. Multiple partition clustering. Working Group on Model Based Clustering 2025, Jul 2025, Valbonne Sophia-Antipolis, France. hal-05451368

HAL Id: hal-05451368

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

Submitted on 9 Jan 2026

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 CC BY 4.0 - Attribution - International License
Multiple partition clustering

Vincent Vandewalle

Joint work Matthieu Marbac and Marie du Roy de Chaumaray

Working Group on Model-Based Clustering

Sophia Antipolis

Thursday, July 24, 2025

UNIVERSITÉ
CÔTE D'AZUR

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

3iA Côte d'Azur
Institut interdisciplinaire
d'intelligence artificielle

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

<figure><img src="image_4.png" /></figure>
1. Multiple partition state of the art

2. Multiple partition by classifying subspaces

3. Multiple partition by blocks of variables

* Variable selection in clustering

* Parametric setting

* Non-parametric setting

4. Conclusion and perspectives
1. Multiple partition state of the art

2. Multiple partition by classifying subspaces

3. Multiple partition by blocks of variables

* Variable selection in clustering

* Parametric setting

* Non-parametric setting

4. Conclusion and perspectives
Limitation of clustering

eresults highly depend of the chosen variables

Only dominant clustering viewpoint

Continuous variables dominate categorical variables

Class variable over-simplistic for predictive models

Large number of clusters possibly needed

Question

Each variable comes with its own partition: how to find a trade-off
between all these partitions?

Multiple partition clustering: several cluster variables

Several clustering viewpoints with respect to different linear/groups combinations of variables

Find hidden clustering

Summary of the data by several categorical variables
$$p(\mathbf{x}_i; \boldsymbol{\theta}) = \sum_{k_1=1}^{g_1} \cdots \sum_{k_B=1}^{g_B} p(\mathbf{x}_i, z_1 = k_1, \ldots, z_B = k_B; \boldsymbol{\theta})$$

## State of the art in multiple partition clustering

* Several classifying subspaces

* Attias (1999): independent factor analysis: $\mathbf{x}_i = \Gamma\mathbf{y}_i + \boldsymbol{\epsilon}_i$

* Vandewalle (2020): several classifying linear combinations of variables (continuous framework)

* Several blocks of classifying variables

* Galimberti and Soffritti (2007): Block of independent variables each one following a mixture

* Galimberti, Manisi, and Soffritti (2018): Refinement considering different roles for variables

* Poon et al. (2013): tree dependence structure between class variables

* Marbac and Vandewalle (2019): independent blocks of variables with conditional independence assumption in each block (mixed-data framework)

* Rodriguez-Sanchez, Bielza, and Larrañaga (2022): Bayesian networks framework
$$p(\mathbf{x}_i; \boldsymbol{\theta}) = \sum_{k_1=1}^{g_1} \cdots \sum_{k_B=1}^{g_B} p(\mathbf{x}_i, z_1 = k_1, \ldots, z_B = k_B; \boldsymbol{\theta})$$

## State of the art in multiple partition clustering

* Several classifying subspaces

Attias (1999): independent factor analysis: $\mathbf{x}_i = \Gamma\mathbf{y}_i + \boldsymbol{\epsilon}_i$

Vandewalle (2020): several classifying linear combinations of variables (continuous framework)

* Several blocks of classifying variables

Galimberti and Soffritti (2007): Block of independent variables each one following a mixture

Galimberti, Manisi, and Soffritti (2018): Refinement considering different roles for variables

Poon et al. (2013): tree dependence structure between class variables

Marbac and Vandewalle (2019): independent blocks of variables with conditional independence assumption in each block (mixed-data framework)

Rodriguez-Sanchez, Bielza, and Larrañaga (2022): Bayesian networks framework
1. Multiple partition state of the art

2. Multiple partition by classifying subspaces

3. Multiple partition by blocks of variables

* Variable selection in clustering

* Parametric setting

* Non-parametric setting

4. Conclusion and perspectives
## Summarize the data

* **Dimension reduction:** find components explaining the major variability in the data

* **Clustering:** find clusters explaining the major heterogeneity in the data

## Link between dimension reduction and clustering

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

Visualizing clusters on the visualization space.

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

Dimension reduction and clustering are often performed separately or sequentially but rarely simultaneously.

## Generative models allow to combine visualization and clustering

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

Trevor Hastie (1996): Reduced rank discriminant analysis

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

Kumar and Andreou (1998): Heteroscedastic discriminant analysis

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

Attias (1999): Independent Factor Analysis

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

Gormley and Murphy (2010): latent position cluster model for network data

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

Bouveyron and Brunet (2012): Model-based clustering and visualization in the Fisher discriminative subspace
Motivation

• View each cluster variable on a clustering component

* Heterogeneity-based visualization rather than inertia-based visualization

Model

● z¹, ..., z^H: latent class variables

* **y**¹, ..., **y**^H: latent classifying variables

● **u** non classifying latent variables

● $x = A \begin{pmatrix} y^1 \\ \vdots \\ y^H \\ u \end{pmatrix}$ with $A^{-1} = \begin{pmatrix} V_1 \\ \vdots \\ V_H \\ R \end{pmatrix}$

● $y^h = V_h x$ and $u = Rx$

<figure><img src="image_12.png" /><figcaption>Illustration for $H = 2$</figcaption></figure>
Motivation

* View each cluster variable on a clustering component

* Heterogeneity-based visualization rather than inertia-based visualization

Model

* $p(z_k^h = 1) = \pi_k^h, k \in \{1, \dots, g_h\}$

* $y^h|z_k^h = 1 \sim \mathcal{N}_{p_h}(\nu_k^h, I_{p_h}), p_h \le g_h - 1$

* $u \sim \mathcal{N}_{d-p_{\bullet}}(\gamma, I_{d-p_{\bullet}}), p_{\bullet} = \sum_{h=1}^{H} p_h$

* $x = A \begin{pmatrix} y^1 \\ \vdots \\ y^H \\ u \end{pmatrix}$ with $A^{-1} = \begin{pmatrix} V_1 \\ \vdots \\ V_H \\ R \end{pmatrix}$

* $y^h = V_h x$ and $u = Rx$

<figure><img src="image_13.png" /><figcaption>Illustration for $H = 2$</figcaption></figure>
* The classifying variables $y^1, \dots, y^H$ are

* independant

* follow a mixture

⇒ allow to visualize the data on different clustering projections

* Model invariant up to a bijective linear transformation of the data

* Limited to settings where $d < n$

* The probability distribution function of $x$ is

$$ 
\begin{aligned}
p(\boldsymbol{x}) &= \frac{1}{|\boldsymbol{A}|} p(\boldsymbol{u}) \prod_{h=1}^{H} p(\boldsymbol{y}^h) \\
&= \frac{1}{|\boldsymbol{A}|} \phi_{d-p_{\bullet}}(\boldsymbol{u}; \boldsymbol{\gamma}, I_{d-p_{\bullet}}) \prod_{h=1}^{H} \left( \sum_{k=1}^{g_h} \pi_k^h \phi_{p_h}(\boldsymbol{y}^h; \boldsymbol{\nu}_k^h, I_{p_h}) \right) \\
&= \begin{vmatrix} \boldsymbol{V}_1 \\ \vdots \\ \boldsymbol{V}_H \\ \boldsymbol{R} \end{vmatrix} \phi_{d-p_{\bullet}}(\boldsymbol{R}\boldsymbol{x}; \boldsymbol{\gamma}, I_{d-p_{\bullet}}) \prod_{h=1}^{H} \left( \sum_{k=1}^{g_h} \pi_k^h \phi_{p_h}(\boldsymbol{V}_h\boldsymbol{x}; \boldsymbol{\nu}_k^h, I_{p_h}) \right)
\end{aligned}
$$
Goal

Estimate $V_1, \dots, V_H, R$ and the mixture parameters of the distributions of $y^1, \dots, y^H, u$

GEM algorithm

Until convergence, for $h \in \{1, \dots, H\}$ iterate the following steps:

**E step:** compute

$$t_{ik}^{h(r+1)} = p(z_i^h | \mathbf{x}_i; \boldsymbol{\theta}^{(r)}) = \frac{\pi_k \phi_{p_h}(\mathbf{V}_h^{(r)} \mathbf{x}; \boldsymbol{\nu}_k^{h(r)}, \mathbf{I}_{p_h})}{\sum_{k'=1}^{g_h} \pi_{k'} \phi_{p_{h'}}(\mathbf{V}_{h'}^{(r)} \mathbf{x}; \boldsymbol{\nu}_{k'}^{h(r)}, \mathbf{I}_{p_{h'}})}$$

**GM step:** update $V_1, \dots, V_H, R, \boldsymbol{\nu}_1^h, \dots, \boldsymbol{\nu}_{g_h}^h, \pi_1^h, \dots, \pi_{g_h}^h$ and $\gamma$ to improve the expectation of the completed likelihood (not possible to maximize it in closed form)
* Constrain $V_h^{(r+1)}$ and $R^{(r+1)}$ to be linear combinations of $V_h^{(r)}$ and $R^{(r)}$, the parameters of other clustering dimension being fixed:

$$ \begin{pmatrix} V_h^{(r+1)} \\ R^{(r+1)} \end{pmatrix} = M \begin{pmatrix} V_h^{(r)} \\ R^{(r)} \end{pmatrix} = \begin{pmatrix} M_1 \\ M_2 \end{pmatrix} \begin{pmatrix} V_h^{(r)} \\ R^{(r)} \end{pmatrix}, $$

* Let $y^{(r)} = V_h^{(r)}x$ and $u^{(r)} = R^{(r)}x$,

* Find $M$ and other parameters $\Leftrightarrow$ reduced rank linear discriminant analysis on the data $\begin{pmatrix} y^{(r)} \\ u^{(r)} \end{pmatrix}$ weighted by $t_{ik}^{h(r+1)}$
Remarks

* Need to choose $H$, $g_1$, ..., $g_H$ and $p_1$, ..., $p_H$: possible selection by model choice.

* $V_1$, ..., $V_H$ and $R$ estimated up to isometric transformations.

Number of parameters

$$ \dim(\Theta) = \sum_{h=1}^{H} (g_h - 1) + \sum_{h'=1}^{H} \frac{p_{h'}(2g_{h'} + 2d - p_{h'} + 1)}{2} + \frac{(d - p_{\bullet})(d + p_{\bullet} + 3)}{2} $$
# Crabs data set

200 crabs morphological data, 5 morphological variables, 50 males orange, 50 males blue, 50 females orange, 50 females blue.

<figure><img src="image_14.png" /></figure>
Data after PCA

<figure><img src="image_15.png" /></figure>
* Performed using the BIC criterion

* Model collection: $H = 2$, $g_1 \in \{1, \dots, 5\}$, $g_2 \in \{1, \dots, 5\}$, $p_1 = p_2 = 1$

**Table:** Value of the BIC criterion according to $g_1$ and $g_2$, for the choice of the number of clusters on the crabs dataset, best value in bold.

<table><thead><tr><th>$g_1 \setminus g_2$</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th></tr></thead><tbody><tr><th>1</th><td>-62.66</td><td>0.41</td><td>10.40</td><td>5.11</td><td>0.80</td></tr><tr><th>2</th><td></td><td>17.82</td><td>16.57</td><td>18.88</td><td>0.49</td></tr><tr><th>3</th><td></td><td></td><td>3.75</td><td><strong>22.52</strong></td><td>17.44</td></tr><tr><th>4</th><td></td><td></td><td></td><td>-26.65</td><td>-26.64</td></tr><tr><th>5</th><td></td><td></td><td></td><td></td><td>12.06</td></tr></tbody></table>
Principal clustering components: $H = 2, g_1 = 3, g_2 = 4,$
$p_1 = p_2 = 1$

<figure><img src="image_16.png" /><figcaption>Data on the principal clustering subspaces</figcaption></figure>
Principal clustering components: $H = 2$, $g_1 = g_2 = 2$, $p_1 = p_2 = 1$

<figure><img src="image_17.png" /><figcaption>Data on the principal clustering components</figcaption></figure>
1. Multiple partition state of the art

2. Multiple partition by classifying subspaces

3. Multiple partition by blocks of variables

* Variable selection in clustering

* Parametric setting

* Non-parametric setting

4. Conclusion and perspectives
## Which variables to use?

* Well-posed problem in supervised setting with a ground truth to rely on

* Ill-posed problem in clustering since the class variable is unknown:

* Pragmatic solution 1: prior choice of the variables by the practitioner among the available variable (given some goal)

* Pragmatic solution 2: posterior re-interpretation and only keep the most influential variables

## Why performing variable selection?

* Gain in interpretability

* Decrease the number of parameters to estimate and thus the variance of the parameters ⇒ better recovering of the partition
## Generic idea

* Generative model on $p(x_i; \theta)$

* Add the assumption that some variables do not depend on the cluster

## Some models

* Split variables in Classifying and Redundant variables (Raftery and Dean, 2006)

$$p(x_i; \theta) = \left( \sum_{k=1}^{g} \pi_k p(x_i^C; \alpha_k) \right) p(x_i^R | x_i^C; \beta)$$

* Split variables in Classifying, Redundant and Independent variables (Maugis, Celeux, and Martin-Magniette, 2009)

$$p(x_i; \theta) = \left( \sum_{k=1}^{g} \pi_k p(x_i^C; \alpha_k) \right) p(x_i^R | x_i^C; \beta) p(x_i^I; \gamma)$$
## Limitations of the previous approaches

Combinatorial problem with the refined approaches when the number of variables is large

## Solution: use simpler model for a better model search (Marbac and Sedki, 2017)

* Class conditional independence assumption
  $p(x_i^C; \alpha_k) = \prod_{j \in C} p(x_{ij}; \alpha_{jk})$

* Non-classifying variables are independent of each others

* Better results than competitors when the number of variables is large and for moderated sample size

* Class conditional independence allow to consider heterogeneous variables setting

## Extension in the non-parametric mixture setting (Chaumaray and Marbac, 2021)

Model selection based on a latent class model on the binned data, then a non-parametric mixture is learnt on the classifying variables.
Multiple partition by blocks of variables

<table><thead><tr><th></th><th>x<sub>1</sub></th><th>x<sub>2</sub></th><th>x<sub>3</sub></th><th>x<sub>4</sub></th><th>z<sub>1</sub></th><th>z<sub>2</sub></th></tr></thead><tbody><tr><th>x<sub>1</sub></th><td>6.1</td><td>3.8</td><td>3.7</td><td>1.3</td><td>?</td><td>?</td></tr><tr><th>x<sub>2</sub></th><td>2.0</td><td>2.7</td><td>4.8</td><td>3.8</td><td>?</td><td>?</td></tr><tr><th>x<sub>3</sub></th><td>5.7</td><td>4.7</td><td>3.3</td><td>4.0</td><td>?</td><td>?</td></tr><tr><th>x<sub>4</sub></th><td>2.2</td><td>4.4</td><td>4.5</td><td>4.1</td><td>?</td><td>?</td></tr><tr><th>x<sub>5</sub></th><td>3.4</td><td>4.7</td><td>-3.1</td><td>-5.0</td><td>?</td><td>?</td></tr><tr><th>x<sub>6</sub></th><td>3.0</td><td>5.3</td><td>-3.3</td><td>-3.1</td><td>?</td><td>?</td></tr><tr><th>x<sub>7</sub></th><td>4.9</td><td>4.5</td><td>-3.1</td><td>-6.5</td><td>?</td><td>?</td></tr><tr><th>x<sub>8</sub></th><td>-4.8</td><td>-3.0</td><td>3.7</td><td>3.8</td><td>?</td><td>?</td></tr><tr><th>x<sub>9</sub></th><td>-2.9</td><td>-3.7</td><td>5.2</td><td>5.1</td><td>?</td><td>?</td></tr><tr><th>x<sub>10</sub></th><td>-2.7</td><td>-4.8</td><td>-5.9</td><td>-4.8</td><td>?</td><td>?</td></tr><tr><th>x<sub>11</sub></th><td>-4.3</td><td>-3.2</td><td>-3.8</td><td>-4.7</td><td>?</td><td>?</td></tr><tr><th>x<sub>12</sub></th><td>-2.0</td><td>-4.6</td><td>-4.5</td><td>-5.1</td><td>?</td><td>?</td></tr></tbody></table>

<figure><img src="image_18.png" /></figure>
Multiple partition by blocks of variables

<table><thead><tr><th></th><th>x1</th><th>x2</th><th>x3</th><th>x4</th><th>z1</th><th>z2</th></tr></thead><tbody><tr><td>x1</td><td>6.1</td><td>3.8</td><td>3.7</td><td>1.3</td><td>1</td><td>1</td></tr><tr><td>x2</td><td>2.0</td><td>2.7</td><td>4.8</td><td>3.8</td><td>1</td><td>1</td></tr><tr><td>x3</td><td>5.7</td><td>4.7</td><td>3.3</td><td>4.0</td><td>1</td><td>1</td></tr><tr><td>x4</td><td>2.2</td><td>4.4</td><td>4.5</td><td>4.1</td><td>1</td><td>1</td></tr><tr><td>x5</td><td>3.4</td><td>4.7</td><td>-3.1</td><td>-5.0</td><td>1</td><td>2</td></tr><tr><td>x6</td><td>3.0</td><td>5.3</td><td>-3.3</td><td>-3.1</td><td>1</td><td>2</td></tr><tr><td>x7</td><td>4.9</td><td>4.5</td><td>-3.1</td><td>-6.5</td><td>1</td><td>2</td></tr><tr><td>x8</td><td>-4.8</td><td>-3.0</td><td>3.7</td><td>3.8</td><td>2</td><td>1</td></tr><tr><td>x9</td><td>-2.9</td><td>-3.7</td><td>5.2</td><td>5.1</td><td>2</td><td>1</td></tr><tr><td>x10</td><td>-2.7</td><td>-4.8</td><td>-5.9</td><td>-4.8</td><td>2</td><td>2</td></tr><tr><td>x11</td><td>-4.3</td><td>-3.2</td><td>-3.8</td><td>-4.7</td><td>2</td><td>2</td></tr><tr><td>x12</td><td>-2.0</td><td>-4.6</td><td>-4.5</td><td>-5.1</td><td>2</td><td>2</td></tr></tbody></table>

<figure><img src="image_19.png" /></figure>
Multiple partition by blocks of variables

<table><thead><tr><th></th><th>x<sub>1</sub></th><th>x<sub>2</sub></th><th>x<sub>3</sub></th><th>x<sub>4</sub></th><th>z<sub>1</sub></th><th>z<sub>2</sub></th></tr></thead><tbody><tr><th>x<sub>1</sub></th><td>6.1</td><td>3.8</td><td>3.7</td><td>1.3</td><td>1</td><td>1</td></tr><tr><th>x<sub>2</sub></th><td>2.0</td><td>2.7</td><td>4.8</td><td>3.8</td><td>1</td><td>1</td></tr><tr><th>x<sub>3</sub></th><td>5.7</td><td>4.7</td><td>3.3</td><td>4.0</td><td>1</td><td>1</td></tr><tr><th>x<sub>4</sub></th><td>2.2</td><td>4.4</td><td>4.5</td><td>4.1</td><td>1</td><td>1</td></tr><tr><th>x<sub>5</sub></th><td>3.4</td><td>4.7</td><td>-3.1</td><td>-5.0</td><td>1</td><td>2</td></tr><tr><th>x<sub>6</sub></th><td>3.0</td><td>5.3</td><td>-3.3</td><td>-3.1</td><td>1</td><td>2</td></tr><tr><th>x<sub>7</sub></th><td>4.9</td><td>4.5</td><td>-3.1</td><td>-6.5</td><td>1</td><td>2</td></tr><tr><th>x<sub>8</sub></th><td>-4.8</td><td>-3.0</td><td>3.7</td><td>3.8</td><td>2</td><td>1</td></tr><tr><th>x<sub>9</sub></th><td>-2.9</td><td>-3.7</td><td>5.2</td><td>5.1</td><td>2</td><td>1</td></tr><tr><th>x<sub>10</sub></th><td>-2.7</td><td>-4.8</td><td>-5.9</td><td>-4.8</td><td>2</td><td>2</td></tr><tr><th>x<sub>11</sub></th><td>-4.3</td><td>-3.2</td><td>-3.8</td><td>-4.7</td><td>2</td><td>2</td></tr><tr><th>x<sub>12</sub></th><td>-2.0</td><td>-4.6</td><td>-4.5</td><td>-5.1</td><td>2</td><td>2</td></tr></tbody></table>

Model assumptions

* B independent blocks of variables

* Each block b follows a $g_b$ mixture with class conditional independence

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

Probability distribution function of $x_i$

$$p(x_i|m, \theta) = \prod_{b=1}^{B} p(x_{i\{b\}}|m, \theta) \text{ with } p(x_{i\{b\}}|m, \theta) = \sum_{k=1}^{g_b} \pi_{bk} \prod_{j \in \Omega_b} p(x_{ij}|\alpha_{jk}),$$
<table><thead><tr><th></th><th>x<sub>1</sub></th><th>x<sub>2</sub></th><th>x<sub>3</sub></th><th>x<sub>4</sub></th><th>z<sub>1</sub></th><th>z<sub>2</sub></th></tr></thead><tbody><tr><th>x<sub>1</sub></th><td>6.1</td><td>3.8</td><td>3.7</td><td>1.3</td><td>1</td><td>1</td></tr><tr><th>x<sub>2</sub></th><td>2.0</td><td>2.7</td><td>4.8</td><td>3.8</td><td>1</td><td>1</td></tr><tr><th>x<sub>3</sub></th><td>5.7</td><td>4.7</td><td>3.3</td><td>4.0</td><td>1</td><td>1</td></tr><tr><th>x<sub>4</sub></th><td>2.2</td><td>4.4</td><td>4.5</td><td>4.1</td><td>1</td><td>1</td></tr><tr><th>x<sub>5</sub></th><td>3.4</td><td>4.7</td><td>-3.1</td><td>-5.0</td><td>1</td><td>2</td></tr><tr><th>x<sub>6</sub></th><td>3.0</td><td>5.3</td><td>-3.3</td><td>-3.1</td><td>1</td><td>2</td></tr><tr><th>x<sub>7</sub></th><td>4.9</td><td>4.5</td><td>-3.1</td><td>-6.5</td><td>1</td><td>2</td></tr><tr><th>x<sub>8</sub></th><td>-4.8</td><td>-3.0</td><td>3.7</td><td>3.8</td><td>2</td><td>1</td></tr><tr><th>x<sub>9</sub></th><td>-2.9</td><td>-3.7</td><td>5.2</td><td>5.1</td><td>2</td><td>1</td></tr><tr><th>x<sub>10</sub></th><td>-2.7</td><td>-4.8</td><td>-5.9</td><td>-4.8</td><td>2</td><td>2</td></tr><tr><th>x<sub>11</sub></th><td>-4.3</td><td>-3.2</td><td>-3.8</td><td>-4.7</td><td>2</td><td>2</td></tr><tr><th>x<sub>12</sub></th><td>-2.0</td><td>-4.6</td><td>-4.5</td><td>-5.1</td><td>2</td><td>2</td></tr></tbody></table>

Assumptions

* B blocs of independent variables

* b follows a g<sub>b</sub> class mixture

Probability distribution of x<sub>i</sub>

$$p(x_i|m, \theta) = \prod_{b=1}^{B} p(x_{i\{b\}}|m, \theta) \text{ avec } p(x_{i\{b\}}|m, \theta) = \sum_{k=1}^{g_b} \pi_{bk} \prod_{j \in \Omega_b} p(x_{ij}|\alpha_{jk})$$

Simultaneous search of m and θ: modified EM algorithm which optimises the BIC

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

* Permits variable selection (Marbac and Sedki, 2017) and multiple partitions explained by subsets of variables (variables classification) in an heterogeneous data setting

* Sparse model: low number of parameters

* Better model search expected than in Galimberti, Manisi, and Soffritti (2018)

## Model collection $\mathcal{M}$

* $\omega = (\omega_j; j = 1, \dots, d)$ the repartition of the variables in blocks; $\omega_j = b$ if variable $j$ belongs to block $b$.

* $m = (g_1, \dots, g_B, \omega)$ defines the model

$\mathcal{M} = \{m : \omega_j \le B_{\max} \text{ and } g_b \le g_{\max}; j = 1, \dots, d; b = 1, \dots, B_{\max}\}$

### $\mathcal{M}$ |$\mathcal{M}$ large!
Additive effect of the variables on the completed log-likelihood

$$ \ell(\boldsymbol{\theta}_m | \mathbf{m}, \mathbf{x}, \mathbf{z}) = \sum_{b=1}^{B} \ln p(\mathbf{z}_b | \boldsymbol{\pi}_b) + \sum_{j=1}^{d} \ln p(\mathbf{x}_j | \mathbf{z}_{\omega_j}, \boldsymbol{\alpha}_j) $$

where $\mathbf{z}_b$ is the partition related to block $b$.

⇒ straightforward affectation of the variables to the blocks, for $B$ and $(g_1, \dots, g_B)$ fixed and the partitions known:

$$ \hat{\omega}_j = \underset{b \in \{1, \dots, B\}}{\operatorname{argmax}} \max_{\boldsymbol{\alpha}_j} \ln p(\mathbf{x}_j | \mathbf{z}_b, \boldsymbol{\alpha}_j). $$
Additive effect of the variables on the completed log-likelihood

$$ \ell_{pen}(\boldsymbol{\theta}_m | \mathbf{m}, \mathbf{x}, \mathbf{z}) = \sum_{b=1}^{B} \ln p(\mathbf{z}_b | \boldsymbol{\pi}_b) + \sum_{j=1}^{d} \ln p(\mathbf{x}_j | \mathbf{z}_{\omega_j}, \boldsymbol{\alpha}_j) - \sum_{j=1}^{d} \frac{g_b \nu_{\omega_j}}{2} \ln n $$

where $\mathbf{z}_b$ is the partition related to block $b$.

⇒ straightforward affectation of the variables to the blocks to optimize penalized likelihood, for $B$ and $(g_1, \dots, g_B)$ fixed and the partitions known:

$$ \hat{\omega}_j = \underset{b \in \{1, \dots, B\}}{\operatorname{argmax}} \max_{\boldsymbol{\alpha}_j} \ln p(\mathbf{x}_j | \mathbf{z}_b, \boldsymbol{\alpha}_j) - \frac{g_b \nu_j}{2} \ln n. $$
Additive effect of the variables on the completed log-likelihood

$$ \ell_{pen}(\theta_m | \mathbf{m}, \mathbf{x}, \mathbf{z}) = \sum_{b=1}^{B} \ln p(\mathbf{z}_b | \pi_b) + \sum_{j=1}^{d} \ln p(\mathbf{x}_j | \mathbf{z}_{\omega_j}, \alpha_j) - \sum_{j=1}^{d} \frac{g_b \nu_{\omega_j}}{2} \ln n $$

where $\mathbf{z}_b$ is the partition related to block $b$.

⇒ straightforward affection of the variables to the blocks to optimize penalized likelihood, for B and ($g_1, \dots, g_B$) fixed and the partitions known:

$$ \hat{\omega}_j = \underset{b \in \{1, \dots, B\}}{\operatorname{argmax}} \max_{\alpha_j} \ln p(\mathbf{x}_j | \mathbf{z}_b, \alpha_j) - \frac{g_b \nu_j}{2} \ln n. $$

Modified EM algorithm increasing the BIC

$$ \text{BIC}(m) = \max_{\theta_m} \ell_{pen}(\theta_m | \mathbf{m}, \mathbf{x}) \text{ with } \ell_{pen}(\theta_m | \mathbf{m}, \mathbf{x}) = \ell(\theta_m | \mathbf{m}, \mathbf{x}) - \frac{\nu_m}{2} \ln n. $$

$$ m^* = \underset{m}{\operatorname{argmax}} \operatorname{BIC}(m) \Leftrightarrow (m^*, \hat{\theta}_{m^*}) = \underset{(m, \theta_m)}{\operatorname{argmax}} \ell_{pen}(\theta_m | \mathbf{m}, \mathbf{x}) $$

⇒ Alternate optimization between $m$ and $\theta_m$

* Affectation step for each variable between the E and the M step
Modified EM algorithm (B and $g_1, \dots, g_B$ fixed)

**E-step** Computation of the fuzzy partitions $t_{ibk}^{[r]} := \mathbb{E}[Z_{ibk} | \mathbf{x}_i, \mathbf{m}, \mathbf{\theta}^{[r-1]}]$

$$t_{ibk}^{[r]} = \frac{\pi_{bk}^{[r-1]} \prod_{j \in \Omega_b^{[r-1]}} p(x_{ij} | \alpha_{jk}^{[r-1]})}{\sum_{k'=1}^{g_b} \pi_{bk'}^{[r-1]} \prod_{j \in \Omega_b^{[r-1]}} p(x_{ij} | \alpha_{jk'}^{[r-1]})},$$

**M-step1** Update the affectation of the variables to blocks

$$\omega_j^{[r]} = \underset{b \in \{1, \dots, B\}}{\operatorname{argmax}} \left( \sum_{k=1}^{g_b} \max_{\alpha_{jk} \in \Theta_j} Q(\alpha_{jk} | \mathbf{x}_j, \mathbf{t}_{bk}^{[r]}) - \frac{\nu_j g_b}{2} \ln n \right),$$

with $Q(\alpha_{jk} | \mathbf{x}_j, \mathbf{t}_{bk}) = \sum_{i=1}^n t_{ibk} \ln p(x_{ij} | \alpha_{jk})$ and $n_{bk}^{[r]} = \sum_{i=1}^n t_{ibk}^{[r]}$.

**M-step2** Updating the model parameters

$$\pi_{bk}^{[r]} = \frac{n_{bk}^{[r]}}{n} \quad \text{and} \quad \alpha_{jk}^{[r]} = \underset{\alpha_{jk} \in \Theta_j}{\operatorname{argmax}} Q(\alpha_{jk} | \mathbf{x}_j, \mathbf{t}_{\omega_j^{[r]}}^{[r]}).$$
Integrated complete-data likelihood

$$p(\mathbf{x}, \mathbf{z} | \mathbf{m}) = \int p(\mathbf{x}, \mathbf{z} | \mathbf{m}, \boldsymbol{\theta}) p(\boldsymbol{\theta} | \mathbf{m}) d\boldsymbol{\theta}.$$

Assumptions

* Independence between the prior distributions

* Standard conjugate priors

* Closed form of the complete-data integrated likelihood

MICL (maximum integrated complete-data likelihood) criterion

$$\text{MICL}(\mathbf{m}) = \ln p(\mathbf{x}, \mathbf{z}_m^* | \mathbf{m}) \text{ with } \mathbf{z}_m^* = \underset{\mathbf{z}_m}{\operatorname{argmax}} \ln p(\mathbf{x}, \mathbf{z} | \mathbf{m}).$$

Thus

$$(\mathbf{m}^*, \mathbf{z}_m^*) = \underset{(\mathbf{m}, \mathbf{z}_m)}{\operatorname{argmax}} \ln p(\mathbf{x}, \mathbf{z} | \mathbf{m}).$$
Motivation

* Take into account the clustering purpose : model the data distribution and provide well-separated components

* Replace the optimization over the parameters by the optimization on the partitions

Optimisation of MICL over (z, ω) for B and g₁, ..., gB fixed

Starting at the initial value ω[0], each ωj is uniformly sampled among {1, ..., B}, the algorithm at iteration [r] is

Partition step: find z_b^{[r]} such that for all b = 1, ..., B

$$p(\mathbf{x}_{\{b\}}^{[r-1]}, \mathbf{z}_{b}^{[r]}) \geq p(\mathbf{x}_{\{b\}}^{[r-1]}, \mathbf{z}_{b}^{[r-1]}),$$

where $\mathbf{x}_{\{b\}}^{[r-1]} = (\mathbf{x}_j; \omega^{[r-1]} = b)$.

Model step: find ω[r] such that for j = 1, ..., d

$$\omega_j^{[r]} = \underset{b \in \{1, \dots, B\}}{\operatorname{argmax}} p(\mathbf{x}_j | \mathbf{z}_b^{[r]}).$$
Data (available in the package pgmm)

* 27 chemical and physical properties of three types of Italian wines: Barolo, Grignolino, Barbera

* Data collected during the time period of 1970–1979

Models selected by BIC

<table><thead><tr><th>B</th><th>BIC</th><th>Time</th><th>Block</th><th>G</th><th>ARI<fnref n="1" /></th></tr></thead><tbody><tr><td>1</td><td>-6025.00</td><td>30</td><td>1</td><td>4</td><td>0.78</td></tr><tr><td rowspan="2">2</td><td rowspan="2">-5947.88</td><td rowspan="2">280</td><td>1</td><td>3</td><td>0.87</td></tr><tr><td>2</td><td>4</td><td>0.16</td></tr><tr><td rowspan="3">3</td><td rowspan="3">-5921.42</td><td rowspan="3">1590</td><td>1</td><td>4</td><td>0.74</td></tr><tr><td>2</td><td>4</td><td>0.20</td></tr><tr><td>3</td><td>2</td><td>0.02</td></tr><tr><td rowspan="4">4</td><td rowspan="4">-5918.06</td><td rowspan="4">6065</td><td>1</td><td>4</td><td>0.75</td></tr><tr><td>2</td><td>2</td><td>0.21</td></tr><tr><td>3</td><td>3</td><td>0.02</td></tr><tr><td>4</td><td>2</td><td>0.00</td></tr></tbody></table>

<footnote n="1">¹ARI between the estimated partition and the type of wine</footnote>
Block 1: the type of wines (ARI=0.75)

19 variables: Alcohol, Sugar-free Extract, Tartaric Acid, Uronic Acids, Alcalinity of Ash, Calcium, Magnesium, Phosphate, Total Phenols, Flavanoids, Non-flavanoid Phenols, Proanthocyanins, Color Intensity, Hue, OD280/OD315 of Diluted Wines, OD280/OD315 of Flavanoids, Glycerol, 2-3-Butanediol, Proline

<table><thead><tr><th></th><th>Barolo</th><th>Grignolino</th><th>Barbera</th></tr></thead><tbody><tr><th>Class 1</th><td>0</td><td>45</td><td>0</td></tr><tr><th>Class 2</th><td>0</td><td>5</td><td>48</td></tr><tr><th>Class 3</th><td>58</td><td>1</td><td>0</td></tr><tr><th>Class 4</th><td>1</td><td>20</td><td>0</td></tr></tbody></table>

Block 2: year of production

4 variables: Fixed Acidity, Malic Acid, pH, Total Nitrogen

<table><thead><tr><th rowspan="2"></th><th colspan="9">Year</th></tr><tr><th>1970</th><th>1971</th><th>1972</th><th>1973</th><th>1974</th><th>1975</th><th>1976</th><th>1978</th><th>1979</th></tr></thead><tbody><tr><th>Class 1</th><td>8</td><td>25</td><td>4</td><td>27</td><td>31</td><td>3</td><td>1</td><td>0</td><td>0</td></tr><tr><th>Class 2</th><td>1</td><td>3</td><td>3</td><td>2</td><td>14</td><td>6</td><td>16</td><td>29</td><td>5</td></tr></tbody></table>
Multiple partition by blocks of variables: non-parametric extension

**Idea:** Replace $p(x_{ij}|\alpha_{jk})$ by a non-parametric model $\eta_{jk}(x_{ij})$ to gain in flexibility (Benaglia, Chauveau, and Hunter, 2009)

**Problem:** Difficult to perform model selection in the case of non-parametric mixture (no BIC ...)

**Solution:** Rely on the same strategy as Chaumaray and Marbac (2021) to perform variable selection in model-based clustering in a non-parametric setting:

* Discretization of each continuous variable into $R$ bins

* Perform model selection using a latent class model for categorical data in each block where each component is a product of multinomial distributions

* Fit the selected model (fixed block structure, and number of clusters in each block) in a non-parametric setting

**Remark:** In variable selection in clustering as $R \xrightarrow[n \to \infty]{} +\infty$ this strategy is consistent to find the number of clusters and the relevant variables (Chaumaray and Marbac, 2021)
Each variable is discretized into $B$ non-overlapping bins $I_{Rj1}, \dots, I_{RjR}$ such that

* $\cup_{r=1}^R I_{Rjr} = \mathcal{X}_j$

* for any $(r, r')$ with $r \neq r'$, $I_{Rjr} \cap I_{Rjr'} = \emptyset$

* $l_{Rjr}$ size of bin $I_{Rjr}$ and $\sigma_{Rjr}$ its indicator function.

Discretized pdf of the subject $i$ for the variables in block $b$

$$p_{Rb}(\mathbf{x}_{i\{b\}} | \mathbf{m}, \boldsymbol{\theta}_{Rb}) = \sum_{g=1}^{G_b} \pi_{bg} \prod_{j \in \Omega_b} \prod_{r=1}^{R} \left( \frac{\alpha_{Rgjr}}{|I_{Rjr}|} \right)^{\sigma_{Rjr}(x_{ij})},$$

where

* $\boldsymbol{\theta}_{Rb}$ groups

* the component proportions $\pi_{bg}$

* the probabilities $\alpha_{Rgjr}$ that one subject drawn from component $g$ takes level $r$ for the variable $j$ when this variable is discretized into $R$ bins.

* The probabilities $\alpha_{Rgjr}$ are unknown and must be estimated from the observed sample.
* three blocks of variables $B = 3$

* each block being a mixture of three components $G = (3, 3, 3)$

* well-balanced clusters (i.e., with equal proportions $\pi_{bg} = 1/3$) and with the same number of involved variables (i.e., $|\Omega_1| = |\Omega_2| = |\Omega_3|$).

In block $b$, the marginal density of $X_i$ given the component membership is a product of $|\Omega_b|$ univariate densities such that

$$X_{ij} = \sum_{g=1}^{G_b} z_{ibg} \delta_{gj} + \xi_{ij}$$

where all the $\xi_{ij}$ are independent and where $\delta_{gj} = \tau$ if $j$ is equal to $g$ modulo $G_b$ and $\delta_{gj} = 0$ otherwise. The value of $\tau$ is tuned in order to obtain a chosen theoretical misclassification rate.
We consider:

* three distributions for the $\xi_{ij}$ (standard Gaussian, Student with three degrees of freedom and Laplace)

* four sample sizes ($n = 50, 100, 200, 400$)

* different numbers of variables in each block ($|\Omega_b| = 6, 9$ and $12$)

* the value of $\tau$ to tune theoretical misclassification rates of 5%

For each situation (sample size, number of variables, law), 100 replicates are generated.

**Discretization step:** $R$ bins given by the empirical quantiles
$1/R, 2/R, \dots$, with $R = [n^{1/4}], [n^{1/5}], [n^{1/6}]$ and $[n^{1/7}]$.

**Model selection:** with the proposed modified EM algorithm, with
$B_{max} = 3$ and $G_{max} = 3$, and with a BIC penalty.

**Parameters and density estimation:** is conducted with the package `mixtools`, leading to a more accurate estimated partition.
<figure><img src="image_22.png" /><figcaption>Figure: ARI between the true and the estimated blocks of variables.</figcaption></figure>
<figure><img src="image_23.png" /><figcaption>Figure: mean ARI between the true and the estimated partition of individuals.</figcaption></figure>
1. Multiple partition state of the art

2. Multiple partition by classifying subspaces

3. Multiple partition by blocks of variables

* Variable selection in clustering

* Parametric setting

* Non-parametric setting

4. Conclusion and perspectives
## Conclusion

* Multiple partition by classifying subspaces

* Several classifying subspaces

* Each subspace related to a class variable

* GEM algorithm based on reduced rank LDA

* Multiple partition by blocks of variables

* Several latent class variables

* Groups of variables related to the same clustering

* Simultaneous model search and parameters estimation

* Extension to the non-parametric setting

## Perspectives

* Unsupervised setting

* Extend multiple partition clustering models: deep-learning setting, consider dependency between latent class variables

* Consider not only categorical latent variables but also continuous latent variables

* Connect models with supervised learning

* Consider predictive clustering framework

* Latent class variables seen as concepts
<figure><img src="image_24.png" /></figure>

Attias, Hagai (1999). "Independent factor analysis". In: *Neural computation* 11.4, pp. 803–851.

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

Benaglia, Tatiana, Didier Chauveau, and David R Hunter (2009). "An EM-like algorithm for semi-and nonparametric estimation in multivariate mixtures". In: *Journal of Computational and Graphical Statistics* 18.2, pp. 505–526.

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

Bouveyron, Charles and Camille Brunet (2012). "Simultaneous model-based clustering and visualization in the Fisher discriminative subspace". In: *Statistics and Computing* 22.1, pp. 301–324.

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

Chaumaray, Marie Du Roy de and Matthieu Marbac (2021). *Full Model Estimation for Non-Parametric Multivariate Finite Mixture Models*. arXiv: 2112.05684 [math.ST].

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

Galimberti, Giuliano, Annamaria Manisi, and Gabriele Soffritti (2018). "Modelling the role of variables in model-based cluster analysis". In: *Statistics and Computing* 28.1, pp. 145–169.

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

Galimberti, Giuliano and Gabriele Soffritti (2007). "Model-based methods to identify multiple cluster structures in a data set". In: *Computational Statistics & Data Analysis* 52.1, pp. 520–536.
<figure><img src="image_30.png" /></figure>

Gormley, Isobel Claire and Thomas Brendan Murphy (2010). "A mixture of experts latent position cluster model for social network data". In: *Statistical methodology* 7.3, pp. 385-405.

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

Kumar, Nagendra and Andreas G Andreou (1998). "Heteroscedastic discriminant analysis and reduced rank HMMs for improved speech recognition". In: *Speech communication* 26.4, pp. 283-297.

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

Marbac, Matthieu and Mohammed Sedki (2017). "Variable selection for model-based clustering using the integrated complete-data likelihood". In: *Statistics and Computing* 27.4, pp. 1049-1063.

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

Marbac, Matthieu and Vincent Vandewalle (2019). "A tractable multi-partitions clustering". In: *Computational Statistics & Data Analysis* 132, pp. 167-179.

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

Maugis, Cathy, Gilles Celeux, and Marie-Laure Martin-Magniette (2009). "Variable selection for clustering with Gaussian mixture models". In: *Biometrics* 65.3, pp. 701-709.

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

Poon, Leonard KM et al. (2013). "Model-based clustering of high-dimensional data: Variable selection versus facet determination". In: *International Journal of Approximate Reasoning* 54.1, pp. 196-215.
<figure><img src="image_36.png" /></figure>

Raftery, Adrian E and Nema Dean (2006). "Variable Selection for Model-Based Clustering". In: *Journal of the American Statistical Association* 101.473, pp. 168-178. eprint: https://doi.org/10.1198/016214506000000113.

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

Rodriguez-Sanchez, Fernando, Concha Bielza, and Pedro Larrañaga (2022). "Multipartition clustering of mixed data with Bayesian networks". In: *International Journal of Intelligent Systems* 37.3, pp. 2188-2218.

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

Trevor Hastie, Robert Tibshirani (1996). "Discriminant Analysis by Gaussian Mixtures". In: *Journal of the Royal Statistical Society. Series B (Methodological)* 58.1, pp. 155-176.

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

Vandewalle, Vincent (2020). "Multi-Partitions Subspace Clustering". In: *Mathematics* 8.4, p. 597.