Indice de Rand

L'indice de Rand est une mesure de similarité entre deux partitions d'un ensemble. Il est principalement utilisé en catégorisation automatique. Son principe est de mesurer la consistance (le taux d'accord) entre deux partitions.

L'Indice de Rand

Soit $\pi =\{U_i{\}}_I$ une partition de l'ensemble $E$. Deux éléments $e_1$ et $e_2$ de $E$ sont dits "groupés" dans $\pi$ s'ils appartiennent à un même sous-ensemble de $\pi$, c'est-à-dire $\mathrm{\exists }i\in I:(e_1,e_2)\in U_i\times U_i$. De manière analogue, on dit qu'ils sont séparés dans $\pi$ s'ils appartiennent à deux sous-ensembles distincts de $\pi$.

Soient deux partitions ${\pi }_1$ et ${\pi }_2$ de $E$ et soient les comptages suivants:

• $a$, le nombre de paires d'éléments de $E$ groupés dans ${\pi }_1$ et également groupés dans ${\pi }_2$.
• $b$, le nombre de paires d'éléments de $E$ groupés dans ${\pi }_1$ mais séparés dans ${\pi }_2$.
• $c$, le nombre de paires d'éléments de $E$ groupés dans ${\pi }_2$ mais séparés dans ${\pi }_1$.
• $d$, le nombre de paires d'éléments de $E$ qui sont séparés dans ${\pi }_1$ et dans ${\pi }_2$.

La somme $a+d$ représente la consistance entre les deux partitions ; la somme $b+c$ représente l’inconsistance / le désaccord entre les deux partitions.

	groupés dans ${\pi }_2$	séparés ${\pi }_2$
groupés dans ${\pi }_1$	$a$	$b$
séparés dans ${\pi }_1$	$c$	$d$

L'Indice de Rand est défini par $$RI({\pi }_1,{\pi }_2)=\frac{a+d}{a+b+c+d},$$

c'est-à-dire la proportion des paires d'éléments qui sont conjointement groupées ou conjointement séparées.

La Rand distance est défini par $1-RI({\pi }_1,{\pi }_2)$ et donne le taux de doubles paires d'éléments en désaccord. Symmetric Difference Distance (SDD) est la forme non normalisée de Rand distance défini $d({\pi }_1,{\pi }_2)=1-(b+c)$ où $d(,)$ est le RI. D’après Filkov et Skiena (2004), il a été montré par Bender et al. (1999) que la complexité de $RI({\pi }_1,{\pi }_2)$ peut être de $O(n)$ en considérant de la stochasticité et donc une probabilité d’erreur. Adjusted Rand Index (ARI) est la normalisation de RI qui permet de comparer deux partitions de nombres de classes différentes.

Applications

Transport

L'indice de Rand est utilisé dans le domaine du transport pour grouper les jours présentant des états de trafic similaires.

Articles connexes

• Classification automatique
• Partitionnement de données
• Indice de Davies et Bouldin