Indice de Rand
L'indice de Rand est une mesure de similarité entre deux partitions d'un ensemble[1]. 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
modifierSoit une partition de l'ensemble . Deux éléments et de sont dits "groupés" dans s'ils appartiennent à un même sous-ensemble de , c'est-à-dire . De manière analogue, on dit qu'ils sont séparés dans s'ils appartiennent à deux sous-ensembles distincts de .
Soient deux partitions et de et soient les comptages suivants:
- , le nombre de paires d'éléments de groupés dans et également groupés dans .
- , le nombre de paires d'éléments de groupés dans mais séparés dans .
- , le nombre de paires d'éléments de groupés dans mais séparés dans .
- , le nombre de paires d'éléments de qui sont séparés dans et dans .
La somme représente la consistance entre les deux partitions ; la somme représente l’inconsistance / le désaccord entre les deux partitions.
groupés dans | séparés | |
---|---|---|
groupés dans | ||
séparés dans |
L'Indice de Rand est défini par
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 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 où 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 peut être de 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
modifierTransport
modifierL'indice de Rand est utilisé dans le domaine du transport pour grouper les jours présentant des états de trafic similaires[4].
Références
modifier- (en) W. M. Rand, « Objective criteria for the evaluation of clustering methods », Journal of the American Statistical Association, American Statistical Association, vol. 66, no 336, , 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, , 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, , 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, (ISSN 2045-2322)