External quality criteria

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.

critères de qualité externes

Liste

  • Precision recall measurement
  • Variables indicatrices
  • Measure based on mutual information
  • Entropy, purity and V-measure
  • Czekanowski-Dice
  • Folkes-Mallows
  • Hubert Γ
  • Jaccard
  • Kulczynski
  • McNemar
  • Phi
  • Rand
  • Rogers-Tanimoto
  • Russel-Rao
  • Sokal-Sneath

Rating

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 :

qualité externe

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 :

precision recall

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 :

precision recall

En termes de probabilités conditionnelles, on peut écrire

precision recall

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 :

F-mesure

Il existe également une version pondérée de cette mesure, appelée mesure Fα, définie ainsi :

F-mesure

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 :

External quality

Les formules suivantes établissent un lien entre ces variables aléatoires et les variables de comptage concordantes et discordantes :

External quality

De là, nous obtenons :

External quality

Mesure fondée sur l'information mutuelle

The mutual information criterion can be used as an external measure for clustering. The measure for m instances grouped together using C = {C_1 ,. . . , C_g} and referring to the target attribute y whose domain is dom (y) = {c_1 ,. . . , c_k} is defined as follows:

external quality criteria (measurement based on mutual information, precision recall measurement, RAND index)

where m_l, h indicates the number of instances that are in cluster C_l and also in class c_h. m., h indicates the total number of instances in class c_h. Likewise, m_l ,. indicates the number of instances of the C_l cluster.

MI is combined with entropy in the NMI:

external quality criteria (measurement based on mutual information, precision recall measurement, RAND index)

MI is combined with entropy in AMI:

external quality criteria (measurement based on mutual information, precision recall measurement, RAND index)

Entropy, purity and V-measure

Since the complete cluster (all objects of a same class are assigned to a single cluster) and the homogeneous cluster (each cluster contains only objects of a same class) are rarely achieved, we aim to achieve an equilibrium satisfactory between these two approaches. Therefore, we generally apply five well-known clustering criteria in order to evaluate partition performance, which are purity, H-entropy, V-metric, RAND index, and F-metric. This page exposes the three first. The others are exposed in another page.

The entropy measure is used to show how sentence clusters are partitioned within each cluster, and it is known as the average of the weighted values in each cluster entropy over all clusters C = {c_1, …, c_n} :

Entropy purity and V-measure

The purity of a cluster is the fraction of the size of the cluster represented by the largest class of sentences assigned to this cluster, namely:

Entropy purity and V-measure

The overall purity is the weighted sum of the purities of the individual clusters given by:

Entropy purity and V-measure

Although purity and entropy are useful for comparing partitioning with the same number of clusters, elles ne sont pas fiables lors de la comparaison de partitioning 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é.

The V measure is known as the harmonic mean of homogeneity and completeness; that is, V = homogeneity * completeness / (homogeneity + completeness), where homogeneity and completeness are defined as homogeneity = 1-H (C | L) / H (C) and completeness = 1-H (L | C) / H (L) where:

Entropy purity and V-measure

Czekanowski-Dice

L’indice de Czekanowski-Dice (alias l’indice d’Ochiai) est défini comme ceci :

Czekanowski-Dice

Cet indice est la moyenne harmonique des coefficients de précision et de rappel, c’est-à-dire qu’il est identique à la F-mesure :

Czekanowski-Dice

Folkes-Mallows

L’indice Folkes-Mallows est défini comme ceci :

Folkes-Mallows

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 correlation des variables indicatrices. Il est défini ainsi :

Hubert Gamma

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 :

Hubert gamma

Jaccard

L’indice Jaccard est défini ainsi :

Jaccard

Kulczynski

L’indice de Kulczynski est défini ainsi :

Kulczynski

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 :

McNemar

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 :

McNemar

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 :

Phi

Rand

The Rand index is a simple criterion used to compare an induced aggregation structure (C1) with a given aggregation structure (C2). Let a be the number of pairs of instances assigned to the same cluster in C1 and in the same cluster in C2; let b be the number of pairs of instances which are in the same cluster C1, but not in the same cluster C2; let c be the number of pairs of instances which are in the same cluster C2, but not in the same cluster C1; and d the number of pairs of instances allocated to different clusters than C1 and C2.

The quantities a and d can be interpreted as agreements, and b and c as disagreements. The Rand index is defined as:

external quality criteria (measurement based on mutual information, precision recall measurement, RAND index)

Ce qui revient avec le système de notation à

(yy+nn)/NT

The Rand index is between 0 and 1. When the two partitions match perfectly, the Rand index is 1.

One problem with the Rand index is that its expected value of two random groupings does not take a constant value (such as zero). Hubert and Arabia in 1985 suggest an adjusted Rand index which overcomes this drawback.

Rogers-Tanimoto

L’indice Rogers-Tanimoto est défini comme ceci :

Rogers-Tanimoto

Russel-Rao

L’indice de Russel-Rao mesure la proportion de concordances entre les deux partitions. Il est défini ainsi :

Russel-Rao

Cet indice peut aussi s’écrire :

Russel-Rao

Sokal-Sneath

Il existe deux versions de l’indice Sokal-Sneath. Ils sont définis respectivement ainsi :

Sokal-Sneath

To share