Indice de Rand

Soit ${\displaystyle \pi =\{U_{i}\}_{I}}$ une partition de l'ensemble ${\displaystyle E}$. Deux éléments ${\displaystyle e_{1}}$ et ${\displaystyle e_{2}}$ de ${\displaystyle E}$ sont dits "groupés" dans ${\displaystyle \pi }$ s'ils appartiennent à un même sous-ensemble de ${\displaystyle \pi }$, c'est-à-dire ${\displaystyle \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 ${\displaystyle \pi }$ s'ils appartiennent à deux sous-ensembles distincts de ${\displaystyle \pi }$.

Soient deux partitions ${\displaystyle \pi _{1}}$ et ${\displaystyle \pi _{2}}$ de ${\displaystyle E}$ et soient les comptages suivants:

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

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

	groupés dans ${\displaystyle \pi _{2}}$	séparés ${\displaystyle \pi _{2}}$
groupés dans ${\displaystyle \pi _{1}}$	${\displaystyle a}$	${\displaystyle b}$
séparés dans ${\displaystyle \pi _{1}}$	${\displaystyle c}$	${\displaystyle d}$

L'Indice de Rand est défini par

$${\displaystyle 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 ${\displaystyle 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 ${\displaystyle d(\pi _{1},\pi _{2})=1-(b+c)}$ où ${\displaystyle d(,)}$ est le RI. D’après Filkov et Skiena (2004)[2], il a été montré par Bender et al. (1999)[3] que la complexité de ${\displaystyle RI(\pi _{1},\pi _{2})}$ peut être de ${\displaystyle 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.

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