Indice de Dunn

L'indice de Dunn est une mesure de qualité d'une partition d'un ensemble de données en classification automatique^[1].

C'est le rapport entre la distance minimum qui sépare deux éléments classés séparément et la distance maximum qui sépare deux éléments classés ensemble.

C'est un indice qui ne repose pas sur une distance particulière et qui peut donc être utilisée dans une grande variété de situations.

Une alternative à l'indice de Dunn est 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 Dunn

L'indice (ou score) de Dunn, ${\textstyle S_{D}}$, se base sur les points moyens de chaque groupe ${\textstyle \mu _{k}={\frac {1}{\vert I_{k}\vert }}\sum _{i\in I_{k}}x^{i}}$ et le diamètre du groupe ${\textstyle \Delta _{k}=\max _{i,i'\in I_{k}}d(x^{i},x^{i'})}$.

Il aura pour expression^[2] :

$${\displaystyle S_{D}={\frac {\displaystyle \min _{1\leqslant k<k'\leqslant K}d(\mu _{k},\mu _{k'})}{\displaystyle \max _{1\leqslant k\leqslant K}\Delta _{k}}}}$$Elle peut varier un peu selon les implémentations (définition du diamètre d'un groupe, distance entre centres remplacée par une autre distance entre groupe).

Propriétés

Domaine de variation

L'indice de Dunn varie entre 0 (pire classification) et ${\textstyle +\infty }$(meilleure classification).

Complexité

Notes et références

1. A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters, Dunn, Joseph C., Journal of Cybernetics, 1973.
2. (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 Calinski-Harabasz

• Portail de l’informatique