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

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

$a$ , le nombre de paires d'éléments de $E$ groupés dans $π_{1}$ et également groupés dans $π_{2}$ .
$b$ , le nombre de paires d'éléments de $E$ groupés dans $π_{1}$ mais séparés dans $π_{2}$ .
$c$ , le nombre de paires d'éléments de $E$ groupés dans $π_{2}$ mais séparés dans $π_{1}$ .
$d$ , le nombre de paires d'éléments de $E$ qui sont séparés dans $π_{1}$ et dans $π_{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 $π_{2}$	séparés $π_{2}$
groupés dans $π_{1}$	$a$	$b$
séparés dans $π_{1}$	$c$	$d$

L'Indice de Rand est défini par $R I (π_{1}, π_{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 - R I (π_{1}, π_{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 (π_{1}, π_{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 $R I (π_{1}, π_{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.

Références

↑ (en) W. M. Rand, « Objective criteria for the evaluation of clustering methods », Journal of the American Statistical Association, American Statistical Association, vol. 66, n^o 336,‎ 1971, p. 846–850 (DOI 10.2307/2284239, JSTOR 2284239)
↑ (en) Filkov, V. et Skiena, S., « Integrating microarray data by consensus clustering », International Journal on Artificial Intelligence Tools,‎ 2004, p. 863–880
↑ (en) Bender, M.A., Sethia, S. et Skiena, S.S., « Efficient Data Structures for Maintaining Set Partitions », Proceedings of the Seventh Scandinavia Workshop on Algorithm Theory,‎ 1999, p. 83-96
↑ (en) Clélia Lopez, Ludovic Leclercq, Panchamy Krishnakumari, Nicolas Chiabaut et Hans van Lint, « Revealing the day-to-day regularity of urban congestion patterns with 3D speed maps », Scientific Reports, 7, 14029,‎ 2017 (ISSN 2045-2322)

Articles connexes

Portail des probabilités et de la statistique

[rand71-1] (en) W. M. Rand, « Objective criteria for the evaluation of clustering methods », Journal of the American Statistical Association, American Statistical Association, vol. 66, n^o 336,‎ 1971, p. 846–850 (DOI 10.2307/2284239, JSTOR 2284239)

[2] (en) Filkov, V. et Skiena, S., « Integrating microarray data by consensus clustering », International Journal on Artificial Intelligence Tools,‎ 2004, p. 863–880

[3] (en) Bender, M.A., Sethia, S. et Skiena, S.S., « Efficient Data Structures for Maintaining Set Partitions », Proceedings of the Seventh Scandinavia Workshop on Algorithm Theory,‎ 1999, p. 83-96

[4] (en) Clélia Lopez, Ludovic Leclercq, Panchamy Krishnakumari, Nicolas Chiabaut et Hans van Lint, « Revealing the day-to-day regularity of urban congestion patterns with 3D speed maps », Scientific Reports, 7, 14029,‎ 2017 (ISSN 2045-2322)