Indice de Davies-Bouldin
# 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.

## Définition

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

### Position du problème

Si l'on note X{\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 N{\textstyle N} le nombre d'individus et p{\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 $d(x^i,$ $x^{i′}){\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 k{\textstyle k} est alors donné par $I_k={i∈[[1,$ N]]/ C(i)=k}{\textstyle I_{k}=\{i\in [\![1, N]\!]/\ C(i)=k\}}.

### Expression de l'indice de Davies-Bouldin

L'indice (ou score) de Davies-Bouldin, $S_{DB}{\textstyle$ S_{DB}}, se base sur les points moyens de chaque groupe $μ_k=1/|I_k|$ $∑_{i∈Ik}x^i{\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 $δ^¯_k=1/|I_k|$ $∑_{i∈Ik}d(x^i,$ $μ_k){\textstyle$ {\bar {\delta }}_{k}={\frac {1}{\vert I_{k}\vert }}\sum _{i\in I_{k}}d(x^{i}, \mu _{k})}.

Il aura pour expression :

$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

### Domaine de variation

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

