Internal quality criteria

Les critères de qualité internes  mesurent généralement la compacité des clusters à l’aide d’une mesure de similitude. Il mesure généralement l’homogénéité intra-cluster, la séparabilité inter-cluster ou une combinaison de ces deux. Il n’utilise pas d’informations externes à côté des données elles-mêmes. 

critères de qualité internes

Liste

  • Sum of the quadratic error
  • Dispersion criteria
  • Category utility metric
  • Cutting measures
  • Ball-Hall
  • Banfeld-Raftery
  • Condorcet criterion
  • Criterion C
  • Calinski-Harabasz
  • Davies-Bouldin
  • Det_Ratio
  • Dunn
  • GDImn
  • Gamma
  • G+
  • Ksq_DetW
  • Log_Det_Ratio
  • Log_SS_Ratio
  • McClain-Rao
  • PBM
  • Point biserial
  • Ratkawsky-Lance
  • Ray-Turi
  • Scott-Symons
  • SD_Scat
  • SD_Dis
  • S_Dbw
  • Silhouette
  • Trace W
  • Trace WiB
  • Wemmert-Gançarski
  • Xie-Beni

Comment lire les mesures de qualité interne

Afin de trouver la meilleure partition des données, on exécute généralement un algorithm of clustering avec différentes valeurs du nombre attendu de clusters K : disons que Km ≤ K ≤ KM. L’algorithme de clustering appliqué pourrait être un clustering hiérarchique ascendant (AHC) ou l’algorithme k-means ou toute autre technique. On calcule ensuite un indice de qualité QK pour chaque valeur de K et sélectionne la partition qui a conduit à la « meilleure » valeur pour QK.

Cette section explique ce qui est considéré comme la « meilleure » valeur pour les différents indices de qualité.

Le tableau résume, pour chaque indice, quelle règle doit être appliquée afin de déterminer la meilleure valeur d’indice. Par exemple, dans le cas de l’indice de Calinski-Harabasz, si l’indice de qualité a été calculé pour différentes partitions des données, la meilleure partition est celle correspondant à la plus grande valeur de l’indice.

qualité interne

Les règles de décision appelées max et min dans le tableau signifient qu’il faut sélectionner respectivement la plus grande ou la plus petite valeur d’indice. La règle de décision appelée max diff signifie que la meilleure valeur de K est celle correspondant à la plus grande différence entre deux pentes successives. Sur un diagramme représentant les valeurs d’index par rapport au number of clusters sélectionnés, cela correspond à un coude.

qualité interne

Sum of squared error

Internal quality metrics typically measure cluster compactness using a measure of similarity (such as Sum of Squared Error). It typically measures intra-cluster homogeneity, inter-cluster separability, or a combination of these two. It does not use external information alongside the data itself.

Sum of squared error is the simplest and most widely used criterion measure for clustering. It is calculated as:

Sum of squared error

where C_k is the set of instances of cluster k; μ_k is the vector mean of cluster k. The components of μ_k are calculated as:

Sum of squared error

where N_k = | C_k | is the number of instances belonging to cluster k.

The methods of partitioning which minimize the SSE criterion are often called minimum variance partitions, because by simple algebraic manipulation the SSE criterion can be written:

Sum of squared error

The SSE criterion function is suitable for cases where the clusters form compact clouds well separated from each other.

Additional minimum criteria for SSE can be produced by replacing the value of S_k with expressions such as:

Sum of squared error

Dispersion criteria

Internal quality metrics generally measure the compactness of clusters using a measure of similarity (such as Dispersion criteria: trace, determinant, invariance). It typically measures intra-cluster homogeneity, inter-cluster separability, or a combination of these two. It does not use external information alongside the data itself.

The scalar diffusion criteria are derived from the diffusion matrices, reflecting the intra-cluster diffusion, the inter-cluster diffusion and their summation – the total diffusion matrix. For the k-th cluster, the diffusion matrix can be calculated as follows:

Dispersion criteria

The intra-cluster dispersion matrix is calculated as the sum of the last definition over all W clusters:

Dispersion criteria

The diffusion matrix between clusters can be calculated as follows:

Dispersion criteria

where μ is the total mean vector and is defined as:

Dispersion criteria

The total diffusion matrix should be calculated as follows:

Dispersion criteria

Three scalar criteria can be derived from S_W, S_B and S_T.

The trace is the sum of the diagonal elements of a matrix. Minimizing the trace of S_W is similar to minimizing HSE and is therefore commonly used. This criterion, representing the intra-cluster dispersion, is calculated as follows:

Trace dispersion criteria

Another criterion, which can be maximized, is the criterion between clusters:

Trace dispersion criteria

The determinant of a scattering matrix measures approximately the square of the scattering volume. Since S_B will be singular if the number of clusters is less than or equal to dimensionality, or if mc is less than dimensionality, its determinant is not an appropriate criterion. If we assume that S_W is not singular, the function of the determinant criterion is:

Decisive dispersion criteria

The eigenvalues λ_1, λ_2 ,. . . , λ_d of S_W * S_B are the basic linear invariants of the diffusion matrices. The good partitions are those for which the non-zero eigenvalues are large. As a result, several criteria can be derived, including eigenvalues. Three of these criteria are:

Dispersion invariance criteria

Uutilitaire de catégorie

Category utility is defined as increasing the expected number of entity values that can be correctly predicted given a certain grouping. This metric is useful for problems that contain a relatively small number of nominal features each having a small cardinality.

Mesure de Coupe

In some cases, it is useful to represent the clustering problem as a minimal cutting problem. In such cases, the quality is measured as the ratio of the remaining weights to the total cut weights. If there is no restriction on the size of the clusters, it is easy to find the optimal value. Thus, the min-cut measurement is revised to penalize unbalanced structures.

Ball-Hall

La dispersion moyenne d’un cluster est la moyenne des carrés des distances des points du cluster par rapport à leur barycentre. L’indice Ball-Hall est la moyenne, à travers tous les clusters, de leur dispersion moyenne :

ball-hall

Dans le cas particulier où tous les clusters ont la même taille N/K, cette somme se réduit à WGSS/N.

Banfeld-Raftery

Cet indice est la somme pondérée des logarithmes des traces de la matrice de variance-covariance de chaque cluster.

L’index peut s’écrire ainsi :

Banfeld-Raftery

La quantité Tr(WG{k})/nk peut être interprétée comme la moyenne des carrés des distances entre les points du cluster Ck et leur barycentre G{k}. Si un cluster contient un seul point, cette trace est égale à 0 et le logarithme n’est pas défini.

Concordet

Une autre approche appropriée consiste à appliquer la solution de Condorcet au problème de clustering. Dans ce cas, le critère est calculé comme suit:

internal quality criteria condorcet criterion

where s (x_j, x_k) and d (x_j, x_k) measure the similarity and distance of vectors x_j and x_k.

Criterion C

Criterion C is an extension of Condorcet's criterion and is defined as (where γ is a threshold value):

internal quality criteria criterion C

Si l’on considère les distances NT entre paires de points comme une suite de valeurs triées par ordre croissant, l’indice C utilise les plus petites valeurs NW et les valeurs NW les plus grandes pour calculer les sommes Smin et Smax : la somme S implique les distances NW dans cette séquence qui correspondent à des paires présentes dans un cluster (c’est-à-dire des paires dont les deux points sont dans un même cluster). Au maximum, les distances 3NW sont effectivement retenues dans le calcul de cet indice.

Le critère C s’écrit alors ainsi :

C-index

Calinski-Harabasz

Performance based on HSE average intra and inter-cluster (Tr):

Calinski-Harabasz, Davies-Bouldin, Dunn and Silhouette

where B_k is the matrix of dispersion between clusters and W_k is the intra-cluster scatter matrix defined by:

Calinski-Harabasz, Davies-Bouldin, Dunn and Silhouette

with N the number of points in our data, C_q the set of points in cluster q, c_q the center of cluster q, c the center of E, n_q the number of points in cluster q.

Davies-Bouldin

This index treats each cluster individually and seeks to measure how similar it is to the cluster closest to it. The DB index is formulated as follows:

Calinski-Harabasz, Davies-Bouldin, Dunn and Silhouette

I (c_i) represents the average of the distances between the objects belonging to the cluster C_i and its center. And I (c_i, c_j) represents the distance between the centers of the two clusters C_i and C_j.

For each cluster i of the partition, we seek the cluster j which maximizes the index described as follows:

Calinski-Harabasz, Davies-Bouldin, Dunn and Silhouette

The best partition is therefore the one that minimizes the average of the value calculated for each cluster. In other words, the best partition is the one that minimizes the similarity between clusters.

Det_Ratio

L’index Det_Ratio est défini comme ceci :

Det_Ratio

T désigne la matrice de diffusion totale. C’est la somme des matrices BG et WG.

Dunn

Dunn's Index is another internal cluster validation metric that can be calculated as follows:

  1. For each cluster, calculate the distance between each of the objects of the cluster and the objects of the other clusters
  2. Use the minimum of this distance per pair as inter-cluster separation (min.separation)
  3. For each cluster, calculate the distance between objects in the same cluster.
  4. Use maximum intra-cluster distance (i.e. maximum diameter) as intra-cluster compactness
  5. Calculate Dunn's Index (D) as follows:
Calinski-Harabasz, Davies-Bouldin, Dunn and Silhouette

GDImn

L’indice de Dunn généralisé (GDI) donne une valeur basée sur le « bon comportement » des clusters et de leurs membres, mesurée en fonction des distances entre les clusters et à l’intérieur des clusters.

Notons par la lettre δ une mesure de la distance inter-cluster et par Δ une mesure de la distance intra-cluster (qui est aussi appelée diamètre du cluster). L’indice GDI, relatif à ces distances, est défini ainsi :

GDI

Avec k et k’ entre 1 et K.

Six définitions différentes de δ (notées δ1 à δ6) et trois définitions de Δ (notées Δ1 à Δ3) ont été suggérées. Cela conduit à 18 indices différents notés Cuv : ici u est un entier désignant la distance entre les clusters (1 ≤ u ≤ 6) et v un entier désignant la distance au sein des groupes (1 ≤ v ≤ 3). Les définitions des distances Δ au sein du cluster sont :

GDI

Ici d est la distance euclidienne. Le facteur 2 dans la définition de Δ3 permet d’interpréter la valeur comme un diamètre plutôt que comme un rayon. Les définitions des distances entre clusters δ sont :

GDI

Les quatre premières distances (δ1 à δ4) apparaissent dans les algorithmes de clustering ascendant et sont respectivement appelées liaison simple, liaison complète, liaison moyenne et liaison centroïde. La mesure δ5 est la moyenne pondérée (avec les poids nk et nk′ ) des distances moyennes entre les points des clusters Ck et Ck′ et leur barycentre respectif. La mesure δ6 est la distance de Hausdorff DH.

Baker-Hubert Gamma

L’indice Gamma de Baker-Hubert est une adaptation, dans le cadre du clustering, de l’indice Γ de correlation entre deux vecteurs de données A et B de même taille.

Généralement, pour deux indices i et j tels que ai < aj , on dit que les deux vecteurs sont concordants si bi < bj , autrement dit si les valeurs se classent dans le même ordre dans les deux vecteurs. On calcule le nombre s+ de couples concordants {i, j} et le nombre s− de couples discordants. Notez que les inégalités sont strictes, ce qui signifie que les égalités sont supprimées. Dans ce contexte, l’indice Γ est classiquement défini ainsi :

Gamma

La valeur est entre -1et 1.

Dans le cadre d’une partition, le premier vecteur A est choisi pour être l’ensemble des distances dij entre couples de points {Mi,Mj} (avec i < j). Le deuxième vecteur B est un vecteur binaire : dans ce vecteur, la coordonnée correspondant à un couple {Mi,Mj} vaut 0 si les deux points sont dans le même cluster et 1 sinon. Ces deux vecteurs ont une longueur NT = N(N − 1)/2.

Le nombre s+ représente le nombre de fois qu’une distance entre deux points appartenant à un même cluster (c’est-à-dire un couple pour lequel la valeur du vecteur B est 0) est strictement inférieure à la distance entre deux points n’appartenant pas au même cluster. cluster (c’est-à-dire un couple pour lequel la valeur du vecteur B est 1).

Le nombre s− représente le nombre de fois où la situation inverse se produit, c’est-à-dire qu’une distance entre deux points appartenant à un même cluster (valeur 0 dans B) est strictement supérieure à une distance entre deux points n’appartenant pas au même cluster. (valeur 1 en B). Les cas où il y a égalité (égalité ou ex-aequos) ne sont pas pris en compte.

Il existe des distances inter-clusters NB et, pour chacune d’entre elles, on compare avec les distances intra-clusters NW : on effectue finalement des comparaisons NB × NW. On peut écrire les nombres s+ et s− sous la forme suivante :

Gamma

G+

En utilisant les mêmes notations que pour l’indice Γ de Baker-Hubert, l’indice G+ est défini ainsi :

G+

C’est la proportion de couples discordants parmi tous les couples de points distincts.

Ksq_DetW

Comme son nom l’indique, sa formule est K²|WG|.

Log_Det_Ratio

L’index Log_Det_Ratio est défini comme ceci :

Log_Det_Ratio

où T est la matrice de diffusion et WG. Il s’agit d’une variante logarithmique de l’indice Det_Ratio.

Log_SS_Ratio

L’index Log_SS_Ratio est défini comme ceci :

Log_SS_Ratio

où BGSS et WGSS sont respectivement les traces des matrices BG et WG.

McClain-Rao

Quant à l’indice C, notons SW la somme des distances intra-cluster :

McClain-Rao

Rappelons que le nombre total de distances entre des paires de points appartenant à un même cluster est NW. Notons SB la somme des distances entre clusters :

McClain-Rao

Le nombre total de distances entre des paires de points qui n’appartiennent pas au même cluster est NB = N(N − 1)/2 − NW. L’indice de McClain-Rao est défini comme le quotient entre les distances moyennes au sein d’une cluster et entre les clusters :

McClain-Rao

PBM

L’indice PBM (acronyme constitué des initiales des noms de ses auteurs, Pakhira, Bandyopadhyay et Maulik) est calculé à partir des distances entre les points et leurs barycentres et des distances entre les barycentres eux-mêmes.

Notons par DB la plus grande distance entre deux barycentres de cluster :

PBM

En revanche, notons EW la somme des distances des points de chaque cluster à leur barycentre et ET la somme des distances de tous les points au barycentre G de l’ensemble des données :

PBM

L’index PBM est défini comme ceci :

PBM

ET est une constante qui ne dépend ni de la partition, ni du nombre de clusters.

Point-Bisérial

De manière générale, en statistique, le coefficient point-bisérial est une mesure de corrélation entre une variable continue A et une variable binaire B (c’est-à-dire une variable dont les valeurs sont 0 ou 1). A et B sont des ensembles de même longueur n.

Les valeurs de A sont réparties en deux groupes A0 et A1 selon que la valeur correspondante dans B est 0 ou 1. Notons MA0 et MA1 les moyennes dans A0 et A1, et nA0 et nA1 le nombre d’éléments dans chaque groupe. Le coefficient de corrélation point-bisérial est défini comme la quantité :

point-biserial

où sn est l’écart type de A.

Dans le cadre d’une comparaison entre différents clusterings, le terme sn peut être omis car il ne dépend pas des partitions mais uniquement de l’ensemble des données.

Comme dans le cas de l’indice Γ, on adapte cette définition en choisissant A comme l’ensemble des NT distances entre couples de points Mi et Mj. La valeur correspondante dans B est 1 si les deux points se trouvent dans le même cluster et 0 sinon :

point-biserial

MA1 est la moyenne de toutes les distances au sein du cluster et MA0 est la moyenne de toutes les distances entre les clusters. Ainsi, la définition de l’indice point-bisérial est :

point-biserial

Ratkowsky-Lance

On calcule la moyenne ¯R des quotients entre BGSS et TSS pour chaque dimension de la donnée, c’est-à-dire pour chaque colonne de la matrice A. Notons :

Ratkowsky-Lance

BGSSj est en fait le j-ème terme diagonal de la matrice BG. L’indice de Ratkowsky-Lance (¯c/√K) est défini comme ceci :

Ratkowsky-Lance

Ray-Turi

L’indice de Ray-Turi est défini comme un quotient :

– le numérateur est la moyenne des carrés des distances de tous les points par rapport au barycentre du cluster auquel ils appartiennent :

Ray-Turi

– le dénominateur est le minimum des carrés des distances Δkk′ entre tous les barycentres du cluster :

Ray-Turi

L’indice de Ray-Turi peut donc s’écrire ainsi :

Ray-Turi

Scott-Symons

Cet indice est la somme pondérée des logarithmes des déterminants de la matrice de variance-covariance de chaque cluster. Cela peut s’écrire ainsi :

Scott-Symons

Les déterminants des matrices WG{k} sont supérieurs ou égaux à 0 car ces matrices sont semi-définies positives. Si l’un d’eux est égal à 0, l’index est indéfini.

SD_Scat et SD_Dis

On définit deux grandeurs S et D appelées respectivement diffusion moyenne des clusters et séparation totale entre clusters.

La diffusion moyenne des clusters, notée S, est définie comme suit. Considérons le vecteur de variances pour chaque variable de l’ensemble de données. C’est un vecteur V de taille p défini par :

SD

De même, on définit des vecteurs de variance V{k} pour chaque cluster Ck :

SD

La quantité S est la moyenne des normes des vecteurs V{k} divisée par la norme du vecteur V :

SD

En revanche, la séparation totale entre clusters, notée D, est définie comme suit. Notons Dmax et Dmin respectivement la plus grande et la plus petite distance entre les barycentres des clusters :

SD

L’index SD est finalement défini comme ceci :

SD

où α est un poids égal à la valeur de D obtenue pour la partition comportant le plus grand nombre de clusters. Afin de comparer plusieurs partitions des données, il faut d’abord calculer la valeur de D correspondant au plus grand nombre de clusters afin de retrouver la valeur du coefficient α puis calculer les autres indices à partir de ce coefficient.

S_Dbw

Cet indice s’appuie sur la notion de densité de points appartenant à deux clusters. On définit d’abord une valeur limite σ égale à la racine carrée de la somme des normes des vecteurs de variance V{k} divisée par le nombre de clusters :

S_Dbw

La densité γkk′ pour un point donné, relative à deux clusters Ck et Ck′ , est égale au nombre de points dans ces deux clusters dont la distance à ce point est inférieure à σ. Géométriquement, cela revient à considérer la boule de rayon σ centrée en un point donné et à compter le nombre de points de Ck ∪ Ck′ situés dans cette boule.

Pour chaque paire de clusters, évaluons les densités pour les barycentres G{k} et G{k′} des clusters et pour leur milieu Hkk′ . On forme le quotient Rkk’ entre la densité au milieu et la plus grande densité aux deux barycentres :

S_Dbw

En revanche, on définit une densité inter-clusters G comme la moyenne des quotients Rkk′ :

S_Dbw

L’indice S-Dbw est défini comme la somme de la dispersion moyenne dans les clusters S et de la densité inter-clusters G :

S_Dbw

Silhouette

Validates performance based on intra and inter-cluster distances:

Calinski-Harabasz, Davies-Bouldin, Dunn and Silhouette

with a (i) the average dissimilarity with the other data of the cluster and b (i) the weakest dissimilarity with any non-member cluster for each x_i and center of the cluster y:

Calinski-Harabasz, Davies-Bouldin, Dunn and Silhouette

The silhouette coefficient varies between -1 (worst ranking) and 1 (best ranking). Silhouette's overall average is often calculated.

Calinski-Harabasz, Davies-Bouldin, Dunn and Silhouette

Tau

Utilisant les mêmes notations que pour l’indice Gamma, l’indice τ de Kendall entre deux vecteurs de données de longueur NT est classiquement défini en statistique comme la quantité :

Tau

Les nombres s+ et s− ne comptent pas les liens, donc si une distance entre clusters et une distance intra-cluster sont égales, elles n’entrent pas dans le numérateur. Afin de prendre en compte les égalités, on modifie le dénominateur et définit l’indice corrigé τc comme ceci :

Tau

with

Tau

où ti est le nombre de valeurs dans le i-ème groupe de liens pour le vecteur A et uj est le nombre de valeurs dans le j-ème groupe de liens pour le vecteur B. Ici le vecteur B est constitué uniquement de valeurs 0 et 1 (correspondant respectivement aux paires inter-cluster et intra-cluster) et on a ainsi :

Tau

Un calcul simple montre que ν0 − ν2 = NBNW. Si l’on fait l’hypothèse raisonnable que le vecteur A contient peu de valeurs identiques, on peut estimer que ν2 est négligeable par rapport à ν0. Ceci justifie la définition suivante de l’indice de clustering Tau :

Tau

Trace_W

L’index Trace_W est défini comme ceci :

Trace_W

Trace_WiB

L’index Trace_WiB est défini comme ceci :

Trace_WiB

Wemmert-Gançarski

L’indice de Wemmert-Gançarski est construit à partir des quotients de distances entre les points et les barycentres de tous les clusters.

Pour un point M appartenant au cluster Ck, on forme le quotient R(M) entre la distance de ce point au barycentre du cluster auquel il appartient et la plus petite distance de ce point aux barycentres de tous les autres clusters :

Wemmert-Gançarski

On fait ensuite la moyenne de ces quotients dans chaque cluster. Si cette moyenne est supérieure à 1, on l’ignore, sinon on prend son complément à 1. Précisément, définissons :

Wemmert-Gançarski

L’indice de Wemmert-Gançarski est défini comme la moyenne pondérée, pour tous les clusters, des quantités Jk comme ceci :

Wemmert-Gançarski

Ce qui peut se réécrire comme :

Wemmert-Gançarski

Xie-Beni

L’indice de Xie-Beni est un indice de clustering flou, mais il s’applique également au clustering net.

Elle est définie comme le quotient entre l’erreur quadratique moyenne et le minimum des distances carrées minimales entre les points des clusters. L’erreur quadratique moyenne, dans le cas d’un clustering net, est simplement la quantité 1/N*WGSS, autrement dit la moyenne des carrés des distances de tous les points par rapport au barycentre du cluster auquel ils appartiennent.

Xie-Beni

et l’indice Xie-Beni peut s’écrire ainsi :

Xie-Beni

To share