Les indices de qualité externes sont des indices destinés à mesurer la similitude entre deux partitions. Ils prennent en compte uniquement la répartition des points dans les différents clusters et ne permettent pas de mesurer la qualité de cette répartition.
Liste
- Mesure de rappel de précision
- Variables indicatrices
- Mesure fondée sur l’information mutuelle
- Entropie, pureté et V-mesure
- Czekanowski-Dice
- Folkes-Mallows
- Hubert Γ
- Jaccard
- Kulczynski
- McNemar
- Phi
- Rand
- Rogers-Tanimoto
- Russel-Rao
- Sokal-Sneath
Notation
Tous les indices proposés s’appuient sur une matrice de confusion représentant le décompte des paires de points selon qu’ils sont considérés ou non comme appartenant au même cluster selon la partition P1 ou la partition P2. Il y a donc quatre possibilités :
• les deux points appartiennent au même cluster, selon P1 et P2
• les deux points appartiennent au même cluster selon P1 mais pas à P2
• les deux points appartiennent au même cluster selon P2 mais pas à P1
• les deux points n’appartiennent pas au même cluster, selon P1 et P2.
Notons yy, yn, ny, nn (y signifie oui, et n signifie non) le nombre de points appartenant respectivement à ces quatre catégories. NT étant le nombre total de paires de points, on a :
Mesure de rappel de précision et F-mesure
Si la partition P1 est utilisée comme référence, on définit le coefficient de précision comme la proportion de points justement regroupés dans P2, c’est-à-dire qui sont également regroupés selon la partition de référence P1. Parmi les points yy + ny regroupés selon P2, yy sont à juste titre regroupés. On a donc :
De même, on définit le coefficient de rappel comme la proportion de points regroupés dans P1 qui sont également regroupés dans la partition P2. Il s’agit de la proportion de points qui sont censés être regroupés selon la partition de référence P1 et qui sont effectivement repérés comme tels par la partition P2. Parmi les points yy+yn regroupés dans P1, yy sont également regroupés dans P2. On a donc :
En termes de probabilités conditionnelles, on peut écrire
où les événements gp1 et gp2 signifient que deux points sont regroupés respectivement en P1 et en P2.
La mesure F est la moyenne harmonique des coefficients de précision et de rappel :
Il existe également une version pondérée de cette mesure, appelée mesure Fα, définie ainsi :
Variables indicatrices
Associons à chaque partition Pa (a = 1, 2) la variable aléatoire binaire Xa définie sur l’ensemble des indices i et j tels que i < j comme suit : sa valeur est 1 si les points Mi et Mj sont classés dans le même cluster que dans la partition Pa et 0 sinon. La variable Xa fonctionne comme une variable indicatrice.
Il existe NT paires de points et on ne s’intéresse qu’aux indices i et j tels que i < j. Considérons la moyenne et l’écart type de Xa :
Les formules suivantes établissent un lien entre ces variables aléatoires et les variables de comptage concordantes et discordantes :
De là, nous obtenons :
Mesure fondée sur l'information mutuelle
Le critère d’information mutuel peut être utilisé comme une mesure externe pour le clustering. La mesure pour m instances regroupées en utilisant C = {C_1,. . . , C_g} et faisant référence à l’attribut cible y dont le domaine est dom (y) = {c_1,. . . , c_k} est défini comme suit :
où m_l,h indique le nombre d’instances qui se trouvent dans le cluster C_l et également dans la classe c_h. m.,h indique le nombre total d’instances dans la classe c_h. De même, m_l,. indique le nombre d’instances du cluster C_l.
MI est combiné avec l’entropie dans le NMI :
MI est combiné avec l’entropie dans l’AMI :
Entropie, pureté et V-mesure
Étant donné que le cluster complet (tous les objets d’une même classe sont affectés à un seul cluster) et le cluster homogène (chaque cluster ne contient que des objets d’une même classe) sont rarement atteints, nous visons à atteindre un équilibre satisfaisant entre ces deux approches. Par conséquent, nous appliquons généralement cinq critères de regroupement bien connus afin d’évaluer les performances de la partition, qui sont la pureté, l’entropie H, la mesure V, l’indice RAND et la mesure F. Cette page expose les trois premiers. Les autres sont exposés dans une autre page.
La mesure d’entropie est utilisée pour montrer comment les clusters de phrases sont partitionnées au sein de chaque cluster, et elle est connue comme la moyenne des valeurs pondérées dans chaque entropie de cluster sur tous les clusters C = {c_1, …, c_n} :
La pureté d’un cluster est la fraction de la taille du cluster que représente la plus grande classe de phrases affectée à ce cluster, à savoir :
La pureté globale est la somme pondérée des puretés des clusters individuelles donnée par :
Bien que la pureté et l’entropie soient utiles pour comparer des partitionnement avec le même nombre de clusters, elles ne sont pas fiables lors de la comparaison de partitionnement avec différents nombres de clusters. En effet, l’entropie et la pureté fonctionnent sur la façon dont les ensembles de phrases sont partitionnés au sein de chaque cluster, et cela conduira à un cas d’homogénéité. Les scores les plus élevés de pureté et les scores d’entropie les plus faibles sont généralement obtenus lorsque le nombre total de clusters est trop grand, où cette étape conduira à être la plus faible dans la complétude. La mesure suivante considère à la fois les approches d’exhaustivité et d’homogénéité.
La mesure V est connue sous le nom de moyenne harmonique d’homogénéité et de complétude; c’est-à-dire, V = homogénéité * complétude/ (homogénéité + complétude), où homogénéité et exhaustivité sont définies comme homogénéité = 1-H (C | L) / H (C) et complétude = 1-H (L | C) / H (L) où:
Czekanowski-Dice
L’indice de Czekanowski-Dice (alias l’indice d’Ochiai) est défini comme ceci :
Cet indice est la moyenne harmonique des coefficients de précision et de rappel, c’est-à-dire qu’il est identique à la F-mesure :
Folkes-Mallows
L’indice Folkes-Mallows est défini comme ceci :
Cet indice est la moyenne géométrique (racine carré de la multiplication) des coefficients de précision et de rappel.
Hubert Γ
L’indice d’Hubert ˆΓ est le coefficient de corrélation des variables indicatrices. Il est défini ainsi :
L’indice d’Hubert ˆΓ apparaît comme une variante standardisée (centrée et réduite) de l’indice de Russel-Rao. Sa valeur est comprise entre -1 et 1. On peut écrire l’indice ˆΓ comme suit :
Jaccard
L’indice Jaccard est défini ainsi :
Kulczynski
L’indice de Kulczynski est défini ainsi :
Cet indice est la moyenne arithmétique des coefficients de précision et de rappel.
McNemar
L’indice de McNemar est défini comme ceci :
Sous l’hypothèse nulle H0 que les discordances entre les partitions P1 et P2 sont aléatoires, l’indice C suit approximativement une distribution normale. Il s’agit d’une adaptation du test non paramétrique de McNemar pour la comparaison des fréquences entre deux échantillons appariés : la statistique du test de McNemar (appelée distance χ2) est le carré de l’indice :
et suit, sous l’hypothèse nulle d’homogénéité marginale du tableau de contingence, une distribution du Chi carré à 1 degré de liberté.
Phi
L’indice Phi est une mesure classique de la corrélation entre deux variables dichotomiques. Il est défini ainsi :
Rand
L’indice Rand est un critère simple utilisé pour comparer une structure d’agrégation induite (C1) avec une structure d’agrégation donnée (C2). Soit a le nombre de paires d’instances affectées au même cluster dans C1 et dans le même cluster dans C2; soit b le nombre de paires d’instances qui se trouvent dans le même cluster C1, mais pas dans le même cluster C2; soit c le nombre de paires d’instances qui se trouvent dans le même cluster C2, mais pas dans le même cluster C1; et d le nombre de paires d’instances attribuées à différents clusters que C1 et C2.
Les quantités a et d peuvent être interprétées comme des accords, et b et c comme des désaccords. L’indice Rand est défini comme:
Ce qui revient avec le système de notation à
(yy+nn)/NT
L’index Rand est compris entre 0 et 1. Lorsque les deux partitions s’accordent parfaitement, l’indice Rand est 1.
Un problème avec l’indice Rand est que sa valeur attendue de deux regroupements aléatoires ne prend pas une valeur constante (telle que zéro). Hubert et Arabie en 1985 suggèrent un indice Rand ajusté qui surmonte cet inconvénient.
Rogers-Tanimoto
L’indice Rogers-Tanimoto est défini comme ceci :
Russel-Rao
L’indice de Russel-Rao mesure la proportion de concordances entre les deux partitions. Il est défini ainsi :
Cet indice peut aussi s’écrire :
Sokal-Sneath
Il existe deux versions de l’indice Sokal-Sneath. Ils sont définis respectivement ainsi :
