Indice de Davies-Bouldin

En apprentissage automatique, plus précisément en classification automatique, l'indice de Davies-Bouldin est une mesure de qualité d'une partition d'un ensemble de données, introduite par David L. Davies et Donald W. Bouldin en 1979^[1].

Définition[modifier | modifier le code]

C'est la moyenne du rapport maximal entre la distance d'un point au centre de son groupe et la distance entre deux centres de groupes.

Expression[modifier | modifier le code]

Position du problème[modifier | modifier le code]

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 :

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 $x^{i}=(x_{1}^{i},...,x_{p}^{i})$ et $x^{i'}=(x_{1}^{i'},...,x_{p}^{i'})$ (respectivement, ligne $i$ et $i'$ de $X$ ). Notons $K\geqslant 2$ le nombre de groupes que l'on souhaite former.

Un algorithme de partitionnement donnera une fonction d'attribution $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 Davies-Bouldin[modifier | modifier le code]

L'indice (ou score) de Davies-Bouldin, ${\textstyle S_{DB}}$ , 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 la distance moyenne entre un point et le centre de son groupe ${\textstyle {\bar {\delta }}_{k}={\frac {1}{\vert I_{k}\vert }}\sum _{i\in I_{k}}d(x^{i},\mu _{k})}$ .

Il aura pour expression^[2] :

S_{DB}={\frac {1}{K}}\sum _{k=1}^{K}\max _{k'\neq k}\left({\frac {{\bar {\delta }}_{k}+{\bar {\delta }}_{k'}}{d(\mu _{k},\mu _{k'})}}\right)

Elle peut varier un peu selon les implémentations (distance imposée ou choix limité).

Propriétés[modifier | modifier le code]

Domaine de variation[modifier | modifier le code]

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

Complexité[modifier | modifier le code]

Notes et références[modifier | modifier le code]

↑ D. L. Davies et D. W. Bouldin, « A Cluster Separation Measure », IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-1, n^o 2,‎ avril 1979, p. 224–227 (ISSN 0162-8828, DOI 10.1109/TPAMI.1979.4766909, lire en ligne, consulté le 19 juin 2019)
↑ (en) « Clustering Indices », sur cran.r-project.org (consulté le 19 juin 2019)

Voir aussi[modifier | modifier le code]

Portail de l’informatique

[1] D. L. Davies et D. W. Bouldin, « A Cluster Separation Measure », IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-1, n^o 2,‎ avril 1979, p. 224–227 (ISSN 0162-8828, DOI 10.1109/TPAMI.1979.4766909, lire en ligne, consulté le 19 juin 2019)

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

[1]

[2]