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

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

Un algorithme de partitionnement donnera une fonction d'attribution C : [ [ 1 , N ] ] ⟶ [ [ 1 , K ] ] {\displaystyle 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 D B {\textstyle S_{DB}} , se base sur les points moyens de chaque groupe μ k = 1 | I k | ∑ i ∈ I k 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 ∈ I k 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[2] :

S D B = 1 K ∑ k = 1 K max k ′ ≠ k ( δ ¯ k + δ ¯ k ′ d ( μ k , μ k ′ ) ) {\displaystyle 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).

Complexité


Notes et références

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

Voir aussi

  • icône décorative Portail de l’informatique