L’évaluation (ou « validation ») des résultats de clustering est aussi difficile que le clustering lui-même. Les approches populaires comprennent l’évaluation « interne », où le regroupement est résumé à un score de qualité unique, l’évaluation » externe », où le regroupement est comparé à une classification » vérité au sol « existante, l’évaluation » manuelle « par un expert humain et l’évaluation » indirecte » en évaluant l’utilité du regroupement dans son application prévue.,
Les mesures D’évaluation interne souffrent du problème qu’elles représentent des fonctions qui peuvent elles-mêmes être considérées comme un objectif de regroupement. Par exemple, on pourrait regrouper l’ensemble de données par le coefficient de Silhouette; sauf qu’il n’y a pas d’algorithme efficace connu pour cela. En utilisant une telle mesure interne pour l’évaluation, on compare plutôt la similitude des problèmes d’optimisation, et pas nécessairement l’utilité du clustering.,
l’évaluation externe a des problèmes similaires: si nous avons de telles étiquettes de « vérité au sol », alors nous n’aurions pas besoin de regrouper; et dans les applications pratiques, nous n’avons généralement pas de telles étiquettes. D’autre part, les étiquettes ne reflètent qu’un partitionnement possible de l’ensemble de données, ce qui n’implique pas qu’il n’existe pas de clustering différent, et peut-être même meilleur.
aucune de ces approches ne peut donc en fin de compte juger de la qualité réelle d’un regroupement, mais cela nécessite une évaluation humaine, qui est hautement subjective., Néanmoins, de telles statistiques peuvent être très instructives pour identifier les mauvais groupements, mais il ne faut pas rejeter l’évaluation humaine subjective.
Internal evaluationEdit
Lorsqu’un résultat de clustering est évalué sur la base des données qui ont été elles-mêmes regroupées, on parle d’évaluation interne. Ces méthodes attribuent généralement le meilleur score à l’algorithme qui produit des clusters avec une forte similitude au sein d’un cluster et une faible similitude entre les clusters., Un inconvénient de l’utilisation de critères internes dans l’évaluation par grappes est que des scores élevés sur une mesure interne n’entraînent pas nécessairement des applications efficaces de recherche d’information. De plus, cette évaluation est biaisée vers des algorithmes qui utilisent le même modèle de cluster. Par exemple, le clustering k-means optimise naturellement les distances des objets, et un critère interne basé sur la distance dépassera probablement le clustering résultant.,
Par conséquent, les mesures d’évaluation interne sont les mieux adaptées pour obtenir un aperçu des situations où un algorithme fonctionne mieux qu’un autre, mais cela ne doit pas impliquer qu’un algorithme produit des résultats plus valides qu’un autre. Validité telle que mesurée par l’indice dépend de la revendication que ce type de structure existe dans l’ensemble de données. Un algorithme conçu pour certains types de modèles n’a aucune chance si l’ensemble de données contient un ensemble radicalement différent de modèles, ou si l’évaluation mesure un critère radicalement différent., Par exemple, le clustering k-means ne peut trouver que des clusters convexes, et de nombreux index d’évaluation supposent des clusters convexes. Sur un ensemble de données avec des grappes non convexes, ni l’utilisation de K-moyennes, ni d’un critère d’évaluation qui suppose la convexité, n’est saine.
Il existe plus d’une douzaine de mesures d’évaluation interne, généralement basées sur l’intuition que les éléments d’un même groupe devraient être plus similaires que les éléments de différents groupes., formule suivante: D B = 1 n i i = 1 N max j max i ( σ I + σ J d ( c I , c j ) ) {\displaystyle DB={\frac {1}{n}}\sum _{i=1}^{n}\max _{j\neq i}\left({\frac {\sigma _{i}+\sigma _{j}}{d(c_{i},c_{j})}}\right)} où n est le nombre de clusters, c i {\displaystyle C_{i}} est le centroïde du cluster i {\displaystyle I} , σ i {\displaystyle \Sigma _{i}} est la distance moyenne de tous les éléments du cluster i {\displaystyle I} au centroïde c i {\displaystyle C_{i}} , et d ( c i , c j ) {\displaystyle d(c_{i},c_{j})} est la distance entre les centroïdes C I {\il s’agit d’un code qui peut être utilisé pour afficher le code ., Étant donné que les algorithmes qui produisent des clusters avec de faibles distances intra-clusters (similarité intra-clusters élevée) et des distances inter-clusters élevées (similarité inter-clusters faible) auront un faible indice de Davies–Bouldin, l’algorithme de clustering qui produit une collection de clusters avec le plus petit indice de Davies–Bouldin est considéré comme le meilleur algorithme basé sur ce critère.
- indice de Dunn
l’indice de Dunn vise à identifier les grappes denses et bien séparées. Il est défini comme le rapport entre la distance minimale entre les grappes et la distance maximale entre les grappes., Pour chaque partition de cluster, l’indice Dunn peut être calculé par la formule suivante: D = min 1 ≤ i < j ≤ N d ( i , j ) max 1 ≤ K ≤ N D ‘ ( k ) , {\displaystyle D={\frac {\min _{1\leq i<j\leq N}d(I,j)}{\Max _{1\LEQ K\LEQ n}d^{\prime }(k)}}\,,} où d(I,J) représente la distance entre les clusters i et j, Et D ‘(K) mesure la distance intra-clusters du cluster k. la distance inter-clusters d(i,j) entre deux clusters peut être un nombre quelconque de mesures de distance, telles que la distance entre les centroïdes des clusters. , De même, la distance intra-cluster d ‘(k) peut être mesurée de diverses manières, telles que la distance maximale entre n’importe quelle paire d’éléments dans le cluster K. étant donné que le critère interne recherche des clusters avec une similitude intra-cluster élevée et une similitude inter-cluster faible, les algorithmes qui produisent des clusters avec un indice de Dunn élevé sont
- coefficient de Silhouette
le coefficient de silhouette oppose la distance moyenne aux éléments d’un même groupe à la distance moyenne aux éléments d’autres groupes., Les objets avec une valeur de silhouette élevée sont considérés comme bien groupés, les objets avec une valeur faible peuvent être aberrants. Cet indice fonctionne bien avec k-means, et est également utilisé pour déterminer le nombre optimal de clusters.
external evaluationEdit
dans l’évaluation externe, les résultats du clustering sont évalués sur la base de données qui n’ont pas été utilisées pour le clustering, telles que les étiquettes de classe connues et les benchmarks externes. Ces repères consistent en un ensemble d’éléments pré-classifiés, et ces ensembles sont souvent créés par des humains (experts)., Ainsi, les ensembles de référence peuvent être considérés comme un étalon-or pour l’évaluation. Ces types de méthodes d’évaluation mesurent la proximité du regroupement avec les classes de référence prédéterminées. Cependant, il a été récemment discuté si cela est adéquat pour des données réelles, ou seulement sur des ensembles de données synthétiques avec une vérité factuelle, car les classes peuvent contenir une structure interne, les attributs présents peuvent ne pas permettre la séparation des clusters ou les classes peuvent contenir des anomalies., De plus, du point de vue de la découverte des connaissances, la reproduction des connaissances connues peut ne pas nécessairement être le résultat escompté. Dans le scénario spécial de clustering contraint, où les méta-informations (telles que les étiquettes de classe) sont déjà utilisées dans le processus de clustering, le blocage des informations à des fins d’évaluation n’est pas trivial.
un certain nombre de mesures sont adaptées des variantes utilisées pour évaluer les tâches de classification., Au lieu de compter le nombre de fois où une classe a été correctement affectée à un seul point de données (appelés vrais positifs), ces métriques de comptage de paires évaluent si chaque paire de points de données qui se trouve vraiment dans le même cluster est prévue pour être dans le même cluster.
comme pour l’évaluation interne, plusieurs mesures d’évaluation externe existent:125-129 par exemple:
- pureté: la pureté est une mesure de la mesure dans laquelle les grappes contiennent une seule classe. Son calcul peut être pensé comme suit: pour chaque cluster, comptez le nombre de points de données de la classe la plus commune dans ledit cluster., Maintenant, prenez la somme sur tous les clusters et divisez par le nombre total de points de données. Formellement, étant donné un ensemble de clusters m {\displaystyle M} et un ensemble de classes D {\displaystyle D} , les deux partitionnant N {\displaystyle N} points de données, la pureté peut être définie comme suit:
1 N m m ∈ M max D ∈ D | M d d | {\displaystyle {\frac {1}{N}}\sum _{m\in m}\max _{d\in D}{|M\cap d|}} cette mesure ne pénalise pas beaucoup de grappes, et plus de grappes, il sera plus facile de produire une grande pureté. Un score de pureté de 1 est toujours possible en plaçant chaque point de données dans son propre cluster., En outre, la pureté ne fonctionne pas bien pour les données déséquilibrées, où même des algorithmes de clustering peu performants donneront une valeur de pureté élevée. Par exemple, si un ensemble de données de taille 1000 se compose de deux classes, l’une contenant 999 points et l’autre contenant 1 point, chaque partition possible aura une pureté d’au moins 99,9%.
- index Rand
l’index Rand calcule la similitude des clusters (renvoyés par l’algorithme de clustering) avec les classifications de référence., Il peut être calculé en utilisant la formule suivante: R I = T P + T N T P + F P + F N + T N {\displaystyle RI={\frac {TP+TN}{TP+FP+FN+TN}}} où T P {\displaystyle TP} est le nombre de vrais positifs, T N {\displaystyle TN} est le nombre de vrais négatifs, F P {\displaystyle FP} est le nombre de faux positifs, et F N {\displaystyle FN} est le nombre de faux négatifs. Les instances comptées ici sont le nombre d’affectations correctes par paires., C’est-à-dire que TP {\displaystyle TP} est le nombre de paires de points qui sont regroupées dans la partition prédite et dans la partition de vérité au sol, F P {\displaystyle FP} est le nombre de paires de points qui sont regroupées dans la partition prédite mais pas dans la partition de vérité au sol, etc. Si l’ensemble de données est de taille N, Alors T P + T N + F P + F N = ( N 2) {\displaystyle TP+TN+FP+FN={\binom {N}{2}}} .
un problème avec l’indice Rand est que les faux positifs et les faux négatifs sont également pondérés. Cela peut être une caractéristique indésirable pour certaines applications de clustering., La mesure F répond à cette préoccupation, tout comme l’indice Rand ajusté corrigé du hasard.
- F-mesure
La F-mesure peut être utilisée pour équilibrer la contribution des faux négatifs en pondérant le rappel par un paramètre β ≥ 0 {\displaystyle \beta \geq 0} . Soit la précision et le rappel (les deux mesures d’évaluation externes en elles-mêmes) définis comme suit: P = T P T P + F P {\displaystyle P={\frac {TP}{TP+FP}}} R = T P T P + F n {\displaystyle R={\frac {TP}{TP+FN}}} où P {\displaystyle P} est le taux de précision et R {\displaystyle R} est le taux de rappel., Nous pouvons calculer la F-mesure à l’aide de la formule suivante: F β = ( β 2 + 1 ) ⋅ P ⋅ R β 2 ⋅ P + R {\displaystyle F_{\beta }={\frac {(\beta ^{2}+1)\cdot P\cdot R}{\beta ^{2}\cdot P+R}}} Lorsque β = 0 {\displaystyle \beta =0} , F 0 = P {\displaystyle F_{0}=P} . En d’autres termes, le rappel n’a aucun impact sur la mesure F lorsque β = 0 {\displaystyle \beta =0} , et l’augmentation de β {\displaystyle \beta } alloue une quantité croissante de poids au rappel dans la mesure F finale. Aussi t n {\displaystyle TN} n’est pas pris en compte et peut varier de 0 vers le haut sans limite.,
- indice Jaccard
l’indice Jaccard est utilisé pour quantifier la similitude entre deux ensembles de données. L’index Jaccard prend une valeur comprise entre 0 et 1. Un index de 1 signifie que les deux ensembles de données sont identiques, et un index de 0 indique que les ensembles de données n’ont pas d’éléments communs. L’indice de Jaccard est défini par la formule suivante: J ( A , B ) = | A B B | | A A B | = T P T P + F P + F n {\displaystyle J(A,B)={\frac {|a\cap b|}{|a\cup B|}}={\frac {TP}{TP+FP+FN}}} il s’agit simplement du nombre d’éléments uniques communs aux deux ensembles divisé par le nombre total d’éléments uniques dans les deux ensembles., Aussi t n {\displaystyle TN} n’est pas pris en compte et peut varier de 0 vers le haut sans limite.
- Dice index
la mesure symétrique des dés double le poids sur T P {\displaystyle TP} tout en ignorant t n {\displaystyle TN} : D S C = 2 T P 2 T P + F P + F n {\displaystyle DSC={\frac {2TP}{2TP+FP+FN}}}
- Fowlkes–Mallows index
l’indice Fowlkes–Mallows similarité entre les clusters renvoyés par l’algorithme de clustering et les classifications de référence., Plus la valeur de L’indice Fowlkes–Mallows est élevée, plus les grappes et les classifications de référence sont similaires. Il peut être calculé en utilisant la formule suivante: F M = T P T P + F P ⋅ T P T P + F N {\displaystyle FM={\sqrt {{\frac {TP}{TP+FP}}\cdot {\frac {TP}{TP+FN}}}}} où T P {\displaystyle TP} est le nombre de vrais positifs, F P {\displaystyle FP} est le nombre de faux positifs, et F N {\displaystyle FN} est le nombre de faux négatifs., L’indice F m {\displaystyle FM} est la moyenne géométrique de la précision et du rappel P {\displaystyle P} et R {\displaystyle R} , et est donc également connu sous le nom de mesure G, tandis que la mesure F est leur moyenne harmonique. De plus, la précision et le rappel sont également connus sous le nom d’indices de Wallace B I {\displaystyle B^{I}} et B I i {\displaystyle B^{II}}. Les versions normalisées par hasard du rappel, de la précision et de la mesure G correspondent à L’Informedness, à la Markedness et à la corrélation de Matthews et se rapportent fortement à Kappa.,
- l’information mutuelle est une mesure théorique de l’information de la quantité d’information partagée entre un clustering et une classification de vérité au sol qui peut détecter une similitude non linéaire entre deux clusterings. L’information mutuelle normalisée est une famille de variantes corrigées pour hasard de celle-ci qui a un biais réduit pour des nombres de grappes variables.
- matrice de Confusion
une matrice de confusion peut être utilisée pour visualiser rapidement les résultats d’un algorithme de classification (ou de clustering). Il montre à quel point un cluster est différent du cluster gold standard.,
Cluster tendencyEdit
mesurer la tendance des clusters consiste à mesurer dans quelle mesure les clusters existent dans les données à regrouper, et peuvent être effectués comme un test initial, avant de tenter le clustering. Une façon de le faire est de comparer les données avec des données aléatoires. En moyenne, les données aléatoires ne devraient pas avoir de clusters.
- Hopkins statistiques
Il existe plusieurs formulations de la Hopkins statistique. Un exemple typique est comme suit. Soit X {\displaystyle X} l’ensemble de n {\displaystyle n} points de données dans d {\displaystyle d} espace dimensionnel., Considérons un échantillon aléatoire (sans remplacement) de M n n {\displaystyle M\ll N} points de données avec les membres x i {\displaystyle x_{i}} . Générez également un ensemble Y {\displaystyle Y} de m {\displaystyle m} points de données uniformément répartis de manière aléatoire. Maintenant définir deux mesures de distance, u i {\displaystyle u_{i}} à la distance de y i ∈ A {\displaystyle y_{i}\Y} à partir de son plus proche voisin de X et w i {\displaystyle w_{i}} à la distance de x i ∈ X {\displaystyle x_{i}\X} de son voisin le plus proche de X., On définit alors le Hopkins statistique: H = ∑ i = 1 m u i d ∑ i = 1 m u i d + ∑ i = 1 m w i d , {\displaystyle H={\frac {\sum _{i=1}^{m}{u_{i}^{d}}}{\sum _{i=1}^{m}{u_{i}^{d}}+\sum _{i=1}^{m}{w_{i}^{d}}}}\,,} Avec cette définition, l’uniforme des données aléatoires devraient ont tendance à avoir des valeurs de près de 0,5 et de données en cluster devrait avoir tendance à avoir des valeurs plus proche de 1., Cependant, les données contenant une seule gaussienne obtiendront également un score proche de 1, car cette statistique mesure l’écart par rapport à une distribution uniforme, et non la multimodalité, ce qui rend cette statistique largement inutile dans l’application (car les données réelles ne sont jamais uniformes à distance).