Indice de Calinski-Harabasz

L'indice de Calinski-Harabasz est une mesure de qualité d'une partition d'un ensemble de données en classification automatique

C'est le rapport entre la variance inter-groupes et la variance intra-groupe.

Il se rapproche beaucoup du critère utilisé pour stopper certains algorithmes de partitionnement, comme les K-means. De tels algorithmes vont donc maximiser ce score, par construction.

Une alternative à l'indice de Calinski-Harabasz est l'indice de Dunn ou encore l'indice de Davies-Bouldin.

Expression

Position du problème

Si l'on note ${\textstyle X}$ la matrice des données, dont chaque ligne correspond à un individu (ou observation) et chaque colonne correspond à un prédicteur (ou variable). On note ${\textstyle N}$ le nombre d'individus et ${\textstyle p}$ le nombre de prédicteurs :

$${\displaystyle X=\left({\begin{array}{ccc}x_{1}^{1}&...&x_{p}^{1}\\\vdots &&\vdots \\x_{1}^{N}&...&x_{p}^{N}\\\end{array}}\right)}$$

Notons ${\textstyle d(x^{i},x^{i'})}$ la dissimilarité entre les individus ${\displaystyle x^{i}=(x_{1}^{i},...,x_{p}^{i})}$ et ${\displaystyle x^{i'}=(x_{1}^{i'},...,x_{p}^{i'})}$ (respectivement, ligne ${\displaystyle i}$ et ${\displaystyle i'}$de ${\displaystyle X}$). Notons ${\displaystyle K\geqslant 2}$ le nombre de groupes que l'on souhaite former.

Un algorithme de partitionnement donnera une fonction d'attribution ${\displaystyle C:[\![1,N]\!]\longrightarrow [\![1,K]\!]}$ dont on cherche à évaluer la pertinence par un score. L'ensemble des points appartenant à un groupe ${\textstyle k}$ est alors donné par ${\textstyle I_{k}=\{i\in [\![1,N]\!]/\ C(i)=k\}}$.

Expression de l'indice de Calinski-Harabasz

Notons ${\textstyle \mu _{k}={\frac {1}{\vert I_{k}\vert }}\sum _{i\in I_{k}}x^{i}}$ le point moyen du groupe ${\textstyle k}$ et ${\textstyle \mu ={\frac {1}{N}}\sum _{i=1}^{N}x^{i}}$ le point moyen de tout le nuage. L'indice (ou score) de Calinski-Harabasz, ${\textstyle S_{CH}}$, se base sur la variance inter-groupes ${\textstyle B=\sum _{k=1}^{K}\vert I_{k}\vert \Vert \mu _{k}-\mu \Vert ^{2}}$ et les variances intra-groupes ${\textstyle W_{k}=\sum _{i\in I_{k}}\Vert x^{i}-\mu _{k}\Vert ^{2}}$.

Il aura pour expression^[1] :

$${\displaystyle S_{CH}={\frac {\displaystyle (N-K)B}{\displaystyle (K-1)\sum _{k=1}^{K}W_{k}}}}$$

Propriétés

Domaine de variation

L'indice de Calinski-Harabasz varie entre 0 (pire classification) et ${\textstyle +\infty }$ (meilleure classification). Il dépend fortement de ${\textstyle N}$ (le nombre de points dans l'échantillon). Toutes choses égales par ailleurs, il croit linéairement avec ${\textstyle N}$. Par conséquent, son ordre de grandeur peut varier considérablement d'un jeu de données à l'autre.

Complexité

Notes et références

1. (en) « Clustering Indices », sur cran.r-project.org (consulté le 19 juin 2019)

Voir aussi

• Partitionnement de données
• Indice de Davies-Bouldin
• Indice de Dunn

• Portail des mathématiques
• Portail de l'informatique théorique
• Portail des probabilités et de la statistique