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 $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 $N$ le nombre d'individus et $p$ le nombre de prédicteurs :

$$X=\left(\begin{array}{ccc}{x}_1^1& ...& x_p^1\\ ⋮& & ⋮\\ x_1^N& ...& x_p^N\end{array}\right)$$

Notons $d(x^i,x^{i^{\prime }})$ la dissimilarité entre les individus $x^i=(x_1^i,...,x_p^i)$ et $x^{i^{\prime }}=(x_1^{i^{\prime }},...,x_p^{i^{\prime }})$ (respectivement, ligne $i$ et $i^{\prime }$de $X$). Notons $K⩾2$ le nombre de groupes que l'on souhaite former.

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

Expression de l'indice de Calinski-Harabasz

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

Il aura pour expression :

$$S_{CH}=\frac{(N-K)B}{(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 $+\mathrm{\infty }$ (meilleure classification). Il dépend fortement de $N$ (le nombre de points dans l'échantillon). Toutes choses égales par ailleurs, il croit linéairement avec $N$. Par conséquent, son ordre de grandeur peut varier considérablement d'un jeu de données à l'autre.

Voir aussi

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