L'analyse par grappes

Un article de Wikipédia, l'encyclopédie libre
Aller à la navigation Aller à la recherche
Le résultat d'une analyse par grappes est illustré par la coloration des carrés en trois grappes.

L'analyse de cluster ou le clustering consiste à regrouper un ensemble d'objets de telle sorte que les objets d'un même groupe (appelé cluster ) soient plus similaires (dans un certain sens) les uns aux autres qu'à ceux d'autres groupes (clusters). Il s'agit d'une tâche principale d' analyse de données exploratoire et d'une technique courante d' analyse de données statistiques , utilisée dans de nombreux domaines, notamment la reconnaissance de formes , l'analyse d'images , la recherche d'informations , la bioinformatique , la compression de données , l'infographie et l'apprentissage automatique .

L'analyse de cluster elle-même n'est pas un algorithme spécifique , mais la tâche générale à résoudre. Il peut être réalisé par divers algorithmes qui diffèrent considérablement dans leur compréhension de ce qui constitue un cluster et comment les trouver efficacement. Les notions populaires de clusters incluent des groupes avec de petites distances entre les membres du cluster, des zones denses de l'espace de données, des intervalles ou des distributions statistiques particulières . Le clustering peut donc être formulé comme un problème d'optimisation multi-objectifs . L'algorithme de clustering approprié et les réglages des paramètres (y compris des paramètres tels que la fonction de distance à utiliser, un seuil de densité ou le nombre de clusters attendus) dépendent de l'individuensemble de données et utilisation prévue des résultats. L'analyse de clusters en tant que telle n'est pas une tâche automatique, mais un processus itératif de découverte de connaissances ou d'optimisation interactive à objectifs multiples qui implique des essais et des échecs. Il est souvent nécessaire de modifier le prétraitement des données et les paramètres du modèle jusqu'à ce que le résultat atteigne les propriétés souhaitées.

Outre le terme regroupement , il existe un certain nombre de termes ayant des significations similaires, notamment la classification automatique , la taxonomie numérique , la botryologie (du grec βότρυς « raisin »), l'analyse typologique et la détection communautaire . Les différences subtiles résident souvent dans l'utilisation des résultats : alors qu'en fouille de données, ce sont les groupes qui en résultent qui intéressent, en classification automatique, c'est le pouvoir discriminant qui en résulte qui est intéressant.

L'analyse de cluster a été créée en anthropologie par Driver et Kroeber en 1932 [1] et introduite en psychologie par Joseph Zubin en 1938 [2] et Robert Tryon en 1939 [3] et célèbre utilisée par Cattell à partir de 1943 [4] pour la classification de la théorie des traits en psychologie de la personnalité .

Définition

La notion de "cluster" ne peut pas être définie avec précision, ce qui est l'une des raisons pour lesquelles il existe tant d'algorithmes de clustering. [5] Il existe un dénominateur commun : un groupe d'objets de données. Cependant, différents chercheurs utilisent différents modèles de cluster, et pour chacun de ces modèles de cluster, des algorithmes différents peuvent à nouveau être donnés. La notion de cluster, telle que trouvée par différents algorithmes, varie considérablement dans ses propriétés. La compréhension de ces "modèles de cluster" est essentielle pour comprendre les différences entre les différents algorithmes. Les modèles de cluster typiques incluent :

  • Modèles de connectivité : par exemple,leclustering hiérarchiqueconstruit des modèles basés sur la connectivité à distance.
  • Modèle centroïde s: par exemple, l'algorithme k-meansreprésente chaque cluster par un seul vecteur moyen.
  • Modèles de distribution : lesclusters sont modélisés à l'aide de distributions statistiques, telles queles distributions normales multivariéesutilisées par l'algorithme de maximisation des attentes.
  • Modèles de densité : par exemple,DBSCANetOPTICSdéfinissent les clusters comme des régions denses connectées dans l'espace de données.
  • Modèles: dansle biclustering (également connu sous le nom de co-clustering ou two-mode-clustering), les clusters sont modélisés avec à la fois les membres du cluster et les attributs pertinents.
  • Modèles de groupe : certains algorithmes ne fournissent pas de modèle raffiné pour leurs résultats et fournissent uniquement les informations de groupement.
  • Modèles basés sur des graphes : uneclique, c'est-à-dire un sous-ensemble de nœuds dans ungraphetel que tous les deux nœuds du sous-ensemble sont connectés par une arête peut être considérée comme une forme prototypique de cluster. Les relaxations de l'exigence de connectivité complète (une fraction des arêtes peut être manquante) sont appelées quasi-cliques, comme dans l'algorithme de clustering HCS.
  • Modèles de graphes signés : Chaque chemin dans un graphe signé a un signe issu du produit des signes sur les arêtes. Sous les hypothèses de la théorie de l'équilibre , les arêtes peuvent changer de signe et donner lieu à un graphe bifurqué. L '« axiome de clusterabilité » plus faible (aucun cycle n'a exactement un bord négatif) donne des résultats avec plus de deux clusters, ou des sous-graphes avec seulement des bords positifs. [6]
  • Modèles de neurones : leréseau de neuronesnon supervisé le plus connuest lacarte auto-organisatriceet ces modèles peuvent généralement être caractérisés comme similaires à un ou plusieurs des modèles ci-dessus, et comprenant des modèles de sous-espace lorsque les réseaux de neurones mettent en œuvre une forme d'analyse en composantes principalesouAnalyse en composantes indépendantes.

Un "clustering" est essentiellement un ensemble de tels clusters, contenant généralement tous les objets de l'ensemble de données. De plus, il peut spécifier la relation des clusters entre eux, par exemple, une hiérarchie de clusters imbriqués les uns dans les autres. Les regroupements peuvent être grossièrement distingués comme suit :

  • Hard clustering : chaque objet appartient ou non à un cluster
  • Soft clustering (également :clustering flou ) : chaque objet appartient à chaque cluster à un certain degré (par exemple, une probabilité d'appartenir au cluster)

Des distinctions plus fines sont également possibles, par exemple :

  • Clustering de partitionnement strict : chaque objet appartient à exactement un cluster
  • Regroupement de partitionnement strict avec valeurs aberrantes : les objets peuvent également n'appartenir à aucun cluster et sont considérés comme desvaleurs aberrantes
  • Regroupement superposé (également :clustering alternatif,multi-vues) : les objets peuvent appartenir à plusieurs clusters ; impliquant généralement des clusters durs
  • Clustering hiérarchique : les objets qui appartiennent à un cluster enfant appartiennent également au cluster parent
  • Regroupement de sous-espace : alors qu'un regroupement se chevauchant, dans un sous-espace défini de manière unique, les clusters ne devraient pas se chevaucher

Algorithmes

Comme indiqué ci-dessus, les algorithmes de clustering peuvent être classés en fonction de leur modèle de cluster. L'aperçu suivant ne répertorie que les exemples les plus importants d'algorithmes de clustering, car il existe peut-être plus de 100 algorithmes de clustering publiés. Tous ne fournissent pas de modèles pour leurs clusters et ne peuvent donc pas être facilement catégorisés. Un aperçu des algorithmes expliqués dans Wikipedia peut être trouvé dans la liste des algorithmes statistiques .

Il n'y a pas d'algorithme de clustering objectivement "correct", mais comme il a été noté, "le clustering est dans l'œil du spectateur". [5] L'algorithme de clustering le plus approprié pour un problème particulier doit souvent être choisi expérimentalement, à moins qu'il n'y ait une raison mathématique de préférer un modèle de cluster à un autre. Un algorithme conçu pour un type de modèle échouera généralement sur un ensemble de données contenant un type de modèle radicalement différent. [5] Par exemple, k-means ne peut pas trouver de clusters non convexes. [5]

Clustering basé sur la connectivité (clustering hiérarchique)

Le clustering basé sur la connectivité, également connu sous le nom de clustering hiérarchique , est basé sur l'idée centrale selon laquelle les objets sont plus liés aux objets proches qu'aux objets plus éloignés. Ces algorithmes connectent des "objets" pour former des "clusters" en fonction de leur distance. Un cluster peut être décrit en grande partie par la distance maximale nécessaire pour connecter les parties du cluster. A différentes distances, différents clusters vont se former, qui peuvent être représentés à l'aide d'un dendrogramme , ce qui explique d'où vient le nom commun « clustering hiérarchique »." vient de : ces algorithmes ne fournissent pas un partitionnement unique de l'ensemble de données, mais fournissent à la place une hiérarchie étendue de clusters qui fusionnent les uns avec les autres à certaines distances. Dans un dendrogramme, l'axe des ordonnées marque la distance à laquelle les clusters fusionnent , tandis que les objets sont placés le long de l'axe des x de sorte que les clusters ne se mélangent pas.

Le clustering basé sur la connectivité est une famille entière de méthodes qui diffèrent par la manière dont les distances sont calculées. Outre le choix habituel des fonctions de distance , l'utilisateur doit également décider du critère de liaison (puisqu'un cluster est composé de plusieurs objets, il existe plusieurs candidats pour calculer la distance) à utiliser. Les choix populaires sont connus sous le nom de clustering à liaison unique (le minimum de distances d'objets), le clustering de liaison complet (le maximum de distances d'objets) et UPGMA ou WPGMA("Méthode de groupe de paires non pondérées ou pondérées avec moyenne arithmétique", également connue sous le nom de regroupement de liaison moyenne). De plus, le clustering hiérarchique peut être agglomérant (commençant par des éléments uniques et les agrégeant en clusters) ou diviseur (commençant par l'ensemble de données complet et le divisant en partitions).

Ces méthodes ne produiront pas un partitionnement unique de l'ensemble de données, mais une hiérarchie à partir de laquelle l'utilisateur doit toujours choisir les clusters appropriés. Ils ne sont pas très robustes vis-à-vis des valeurs aberrantes, qui apparaîtront soit comme des clusters supplémentaires, soit même provoqueront la fusion d'autres clusters (connu sous le nom de "phénomène de chaînage", en particulier avec le clustering à liaison unique ). Dans le cas général, la complexité estpour le regroupement agglomératif etpour le clustering avec division , [7] ce qui les rend trop lents pour les grands ensembles de données. Pour certains cas particuliers, des méthodes efficaces optimales (de complexité) sont connus : SLINK [8] pour single-linkage et CLINK [9] pour complete-linkage clustering. Dans la communauté de l' exploration de données, ces méthodes sont reconnues comme un fondement théorique de l'analyse par grappes, mais souvent considérées comme obsolètes [ citation nécessaire ] . Ils ont cependant inspiré de nombreuses méthodes ultérieures telles que le regroupement basé sur la densité.

Clustering basé sur le centroïde

Dans le clustering basé sur le centroïde, chaque cluster est représenté par un vecteur central, qui n'est pas nécessairement un membre de l'ensemble de données. Lorsque le nombre de clusters est fixé à k , k -means clustering donne une définition formelle en tant que problème d'optimisation : trouver les k centres de cluster et affecter les objets au centre de cluster le plus proche, de sorte que les distances au carré du cluster soient minimisées.

Le problème d'optimisation lui-même est connu pour être NP-difficile , et donc l'approche courante consiste à rechercher uniquement des solutions approchées. Une méthode approchée particulièrement bien connue est l'algorithme de Lloyd , [10] souvent simplement appelé " algorithme k-means " (bien qu'un autre algorithme ait introduit ce nom ). Cependant, il ne trouve qu'un optimum local et est généralement exécuté plusieurs fois avec différentes initialisations aléatoires. Les variations de k -means incluent souvent des optimisations telles que le choix du meilleur de plusieurs exécutions, mais aussi la restriction des centroïdes aux membres de l'ensemble de données ( k -medoids ), le choix des médianes( k -medians clustering ), en choisissant les centres initiaux de manière moins aléatoire ( k -means++ ) ou en permettant une affectation floue des clusters ( fuzzy c-means ).

La plupart des algorithmes de type k -means nécessitent que le nombre de clusters - k - soit spécifié à l'avance, ce qui est considéré comme l'un des plus grands inconvénients de ces algorithmes. De plus, les algorithmes préfèrent les clusters de taille approximativement similaire, car ils attribueront toujours un objet au centroïde le plus proche. Cela conduit souvent à couper incorrectement les bordures des clusters (ce qui n'est pas surprenant puisque l'algorithme optimise les centres des clusters, pas les bordures des clusters).

K-means a un certain nombre de propriétés théoriques intéressantes. Tout d'abord, il partitionne l'espace de données dans une structure connue sous le nom de diagramme de Voronoi . Deuxièmement, il est conceptuellement proche de la classification du voisin le plus proche et, en tant que tel, est populaire dans l'apprentissage automatique . Troisièmement, il peut être considéré comme une variante du clustering basé sur un modèle et l'algorithme de Lloyd comme une variante de l' algorithme de maximisation des attentes pour ce modèle décrit ci-dessous.

Les problèmes de clustering basés sur le centroïde tels que k -means et k -medoids sont des cas particuliers du problème de localisation d'installations métriques sans capacité , un problème canonique dans les communautés de recherche opérationnelle et de géométrie computationnelle. Dans un problème d'emplacement d'installation de base (dont il existe de nombreuses variantes qui modélisent des paramètres plus élaborés), la tâche consiste à trouver les meilleurs emplacements d'entrepôt pour desservir de manière optimale un ensemble donné de consommateurs. On peut considérer les « entrepôts » comme des centroïdes de cluster et les « lieux de consommation » comme les données à regrouper. Cela permet d'appliquer les solutions algorithmiques bien développées de la littérature sur la localisation des installations au problème de clustering basé sur le centroïde actuellement considéré.

Clustering basé sur la distribution

Le modèle de regroupement le plus étroitement lié aux statistiques est basé sur les modèles de distribution . Les clusters peuvent alors être facilement définis comme des objets appartenant très probablement à la même distribution. Une propriété pratique de cette approche est qu'elle ressemble étroitement à la manière dont les ensembles de données artificiels sont générés : en échantillonnant des objets aléatoires à partir d'une distribution.

Bien que la base théorique de ces méthodes soit excellente, elles souffrent d'un problème clé connu sous le nom de surajustement , à moins que des contraintes ne soient imposées sur la complexité du modèle. Un modèle plus complexe sera généralement en mesure de mieux expliquer les données, ce qui rend le choix de la complexité du modèle approprié intrinsèquement difficile.

Une méthode importante est connue sous le nom de modèles de mélange gaussien (utilisant l' algorithme de maximisation des attentes ). Ici, l'ensemble de données est généralement modélisé avec un nombre fixe (pour éviter le surajustement) de distributions gaussiennes qui sont initialisées de manière aléatoire et dont les paramètres sont optimisés de manière itérative pour mieux s'adapter à l'ensemble de données. Cela convergera vers un optimum local , de sorte que plusieurs exécutions peuvent produire des résultats différents. Afin d'obtenir un clustering dur, les objets sont souvent ensuite affectés à la distribution gaussienne à laquelle ils appartiennent le plus probablement; pour les regroupements souples, ce n'est pas nécessaire.

Le clustering basé sur la distribution produit des modèles complexes pour les clusters qui peuvent capturer la corrélation et la dépendance entre les attributs. Cependant, ces algorithmes imposent une charge supplémentaire à l'utilisateur : pour de nombreux ensembles de données réelles, il peut ne pas y avoir de modèle mathématique défini de manière concise (par exemple, supposer que les distributions gaussiennes sont une hypothèse assez forte sur les données).

Clustering basé

Dans le clustering basé sur la densité, [11] les clusters sont définis comme des zones de densité plus élevée que le reste de l'ensemble de données. Les objets dans les zones clairsemées - qui sont nécessaires pour séparer les clusters - sont généralement considérés comme des points de bruit et de frontière.

La méthode de clustering basée sur la densité la plus populaire [12] est DBSCAN . [13]Contrairement à de nombreuses méthodes plus récentes, il comporte un modèle de cluster bien défini appelé "densité-joignabilité". Semblable au clustering basé sur la liaison, il est basé sur des points de connexion à l'intérieur de certains seuils de distance. Cependant, il ne relie que les points qui satisfont à un critère de densité, dans la variante d'origine défini comme un nombre minimum d'autres objets dans ce rayon. Un cluster se compose de tous les objets connectés à la densité (qui peuvent former un cluster de forme arbitraire, contrairement à de nombreuses autres méthodes) ainsi que de tous les objets qui se trouvent dans la plage de ces objets. Une autre propriété intéressante de DBSCAN est que sa complexité est assez faible - il nécessite un nombre linéaire de requêtes de plage sur la base de données - et qu'il découvrira essentiellement les mêmes résultats (il est déterministepour les points centraux et de bruit, mais pas pour les points frontières) dans chaque exécution, il n'est donc pas nécessaire de l'exécuter plusieurs fois. OPTICS [14] est une généralisation de DBSCAN qui supprime la nécessité de choisir une valeur appropriée pour le paramètre de portée, et produit un résultat hiérarchique lié à celui du clustering de liens . DeLi-Clu, [15] Density-Link-Clustering combine des idées de clustering à liaison unique et OPTICS, éliminant leparamètre entièrement et offrant des améliorations de performances par rapport à OPTICS en utilisant un index R-tree .

Le principal inconvénient de DBSCAN et OPTICS est qu'ils s'attendent à une sorte de chute de densité pour détecter les frontières des clusters. Sur des ensembles de données avec, par exemple, des distributions gaussiennes qui se chevauchent - un cas d'utilisation courant dans les données artificielles - les bordures de cluster produites par ces algorithmes sembleront souvent arbitraires, car la densité de cluster diminue continuellement. Sur un ensemble de données composé de mélanges de gaussiennes, ces algorithmes sont presque toujours surpassés par des méthodes telles que le clustering EM qui sont capables de modéliser précisément ce type de données.

Le décalage moyen est une approche de regroupement dans laquelle chaque objet est déplacé vers la zone la plus dense de son voisinage, en fonction de l'estimation de la densité du noyau . Finalement, les objets convergent vers des maxima locaux de densité. Semblables au clustering k-means, ces "attracteurs de densité" peuvent servir de représentants pour l'ensemble de données, mais le décalage moyen peut détecter des clusters de forme arbitraire similaires à DBSCAN. En raison de la procédure itérative coûteuse et de l'estimation de la densité, le décalage moyen est généralement plus lent que DBSCAN ou k-Means. En outre, l'applicabilité de l'algorithme de décalage moyen aux données multidimensionnelles est entravée par le comportement non régulier de l'estimation de la densité du noyau, ce qui entraîne une sur-fragmentation des queues de cluster. [15]

Clustering basé sur la grille

La technique basée sur la grille est utilisée pour un ensemble de données multidimensionnel . [16] Dans cette technique, nous créons une structure de grille et la comparaison est effectuée sur des grilles (également appelées cellules). La technique basée sur la grille est rapide et a une faible complexité de calcul. Il existe deux types de méthodes de clustering basées sur la grille : STING et CLIQUE. Les étapes impliquées dans l' algorithme de clustering basé sur la grille sont :

  1. Divisez l'espace de données en un nombre fini de cellules.
  2. Sélectionnez au hasard une cellule 'c', où c ne doit pas être parcouru au préalable.
  3. Calculer la densité de 'c'
  4. Si la densité de 'c' est supérieure à la densité de seuil
    1. Marquer la cellule 'c' comme un nouveau cluster
    2. Calculer la densité de tous les voisins de 'c'
    3. Si la densité d'une cellule voisine est supérieure à la densité de seuil, ajoutez la cellule dans le cluster et répétez les étapes 4.2 et 4.3 jusqu'à ce qu'il n'y ait pas de voisin avec une densité supérieure à la densité de seuil.
  5. Répétez les étapes 2, 3 et 4 jusqu'à ce que toutes les cellules soient traversées.
  6. Arrêter.

Développements récents

Ces dernières années, des efforts considérables ont été déployés pour améliorer les performances des algorithmes existants. [17] [18] Parmi eux figurent CLARANS , [19] et BIRCH . [20] Avec le besoin récent de traiter des ensembles de données de plus en plus volumineux (également appelés mégadonnées ), la volonté d'échanger la signification sémantique des clusters générés contre la performance a augmenté. Cela a conduit au développement de méthodes de pré-clustering telles que le clustering de la canopée , qui peuvent traiter efficacement d'énormes ensembles de données, mais les "clusters" résultants ne sont qu'un pré-partitionnement approximatif de l'ensemble de données pour ensuite analyser les partitions avec des méthodes plus lentes existantes telles que commek-signifie le regroupement .

Pour les données de grande dimension , de nombreuses méthodes existantes échouent en raison de la malédiction de la dimensionnalité , ce qui rend les fonctions de distance particulières problématiques dans les espaces de grande dimension. Cela a conduit à de nouveaux algorithmes de clustering pour les données de grande dimension qui se concentrent sur le clustering de sous-espace (où seuls certains attributs sont utilisés et les modèles de cluster incluent les attributs pertinents pour le cluster) et le clustering de corrélation qui recherche également un sous-espace à rotation arbitraire ("corrélé"). clusters qui peuvent être modélisés en donnant une corrélation de leurs attributs. [21] Des exemples de tels algorithmes de clustering sont CLIQUE [22] et SUBCLU. [23]

Les idées issues des méthodes de clustering basées sur la densité (en particulier la famille d'algorithmes DBSCAN / OPTICS ) ont été adaptées au clustering de sous-espaces (HiSC, [24] hierarchical subspace clustering and DiSH [25] ) et au clustering de corrélation (HiCO, [26] hierarchical correlation clustering, 4C [27] utilisant la "connectivité de corrélation" et ERiC [28] explorant les clusters de corrélation basés sur la densité hiérarchique).

Plusieurs systèmes de regroupement différents basés sur des informations mutuelles ont été proposés. L'un est la variation de la métrique d'information de Marina Meilă ; [29] un autre fournit un regroupement hiérarchique. [30] En utilisant des algorithmes génétiques, un large éventail de différentes fonctions d'ajustement peut être optimisé, y compris l'information mutuelle. [31] De plus , la propagation des croyances , un développement récent en informatique et en physique statistique , a conduit à la création de nouveaux types d'algorithmes de regroupement. [32]

Évaluation et appréciation

L'évaluation (ou "validation") des résultats du clustering est aussi difficile que le clustering lui-même. [33] Les approches populaires impliquent une évaluation « interne », où le regroupement est résumé à un seul score de qualité, une évaluation « externe », où le regroupement est comparé à une classification de « vérité terrain » existante, une évaluation « manuelle » par un expert humain, et l'évaluation « indirecte » en évaluant l'utilité du regroupement dans son application prévue. [34]

Les mesures d'évaluation interne souffrent du problème qu'elles représentent des fonctions qui elles-mêmes peuvent être considérées comme un objectif de regroupement. Par exemple, on pourrait regrouper les données définies par le coefficient 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 similarité des problèmes d'optimisation [34] et pas nécessairement l'utilité du regroupement.

L'évaluation externe a des problèmes similaires : si nous avons de telles étiquettes de « vérité de terrain », alors nous n'aurions pas besoin de grouper ; 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 un clustering différent, et peut-être même meilleur.

Aucune de ces approches ne peut donc finalement juger de la qualité réelle d'un clustering, mais cela nécessite une évaluation humaine, [34] qui est très subjective. Néanmoins, de telles statistiques peuvent être très instructives pour identifier les mauvais regroupements, [35] mais il ne faut pas rejeter l'évaluation humaine subjective. [35]

Évaluation interne

Lorsqu'un résultat de regroupement 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 similarité au sein d'un cluster et une faible similarité entre les clusters. Un inconvénient de l'utilisation de critères internes dans l'évaluation des clusters est que des scores élevés sur une mesure interne ne se traduisent pas nécessairement par des applications de recherche d'informations efficaces. [36] De plus, cette évaluation est biaisée en faveur d'algorithmes qui utilisent le même modèle de cluster. Par exemple, le regroupement k-means optimise naturellement les distances des objets, et un critère interne basé sur la distance surestimera probablement le regroupement résultant.

Par conséquent, les mesures d'évaluation internes sont les mieux adaptées pour avoir un aperçu des situations dans lesquelles un algorithme fonctionne mieux qu'un autre, mais cela n'implique pas qu'un algorithme produit des résultats plus valides qu'un autre. [5] La validité mesurée par un tel indice dépend de l'affirmation selon laquelle 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 de modèles radicalement différent, ou si l'évaluation mesure un critère radicalement différent. [5] Par exemple, le clustering k-means ne peut trouver que des clusters convexes, et de nombreux indices d'évaluation supposent des clusters convexes. Sur un ensemble de données avec des clusters non convexes, ni l'utilisation de k-signifie, ni d'un critère d'évaluation qui suppose la convexité, est solide.

Il existe plus d'une douzaine de mesures d'évaluation internes, 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 groupes différents. [37] : 115–121  Par exemple, les méthodes suivantes peuvent être utilisées pour évaluer la qualité des algorithmes de clustering sur la base de critères internes :

L' indice Davies-Bouldin peut être calculé par la formule suivante :
n est le nombre de clusters,est le centre de gravité du cluster,est la distance moyenne de tous les éléments du clusterau centre de gravité, etest la distance entre les centroïdeset. Étant donné que les algorithmes qui produisent des clusters avec de faibles distances intra-cluster (haute similarité intra-cluster) et des distances inter-cluster élevées (faible similarité inter-cluster) auront un faible indice Davies-Bouldin, l'algorithme de clustering qui produit une collection de clusters avec le plus petit indice Davies-Bouldin est considéré comme le meilleur algorithme basé sur ce critère.
L'indice Dunn vise à identifier des clusters denses et bien séparés. Elle est définie comme le rapport entre la distance minimale inter-cluster et la distance maximale intra-cluster. Pour chaque partition de cluster, l'indice de Dunn peut être calculé par la formule suivante : [38]
d ( i , j ) représente la distance entre les clusters i et j , et d '( k ) mesure la distance intra-cluster du cluster k . La distance inter-cluster d ( i , j ) entre deux clusters peut être n'importe quel nombre 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 toute paire d'éléments dans le cluster  k. Étant donné que le critère interne recherche des clusters avec une forte similarité intra-cluster et une faible similarité inter-cluster, les algorithmes qui produisent des clusters avec un indice de Dunn élevé sont plus souhaitables.
Le coefficient de silhouette compare la distance moyenne aux éléments du même groupe avec la distance moyenne aux éléments d'autres groupes. Les objets avec une valeur de silhouette élevée sont considérés comme bien regroupés, les objets avec une valeur faible peuvent être des valeurs aberrantes. Cet index fonctionne bien avec le clustering k -means, [ citation nécessaire ] et est également utilisé pour déterminer le nombre optimal de clusters.

Évaluation externe

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 références externes. De tels 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. [33] Ces types de méthodes d'évaluation mesurent à quel point le regroupement est proche des 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é terrain factuelle, puisque 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 . [39]De plus, du point de vue de la découverte des connaissances , la reproduction des connaissances connues n'est pas nécessairement le résultat escompté. [39] Dans le scénario particulier du regroupement contraint , où les méta-informations (telles que les étiquettes de classe) sont déjà utilisées dans le processus de regroupement, la rétention d'informations à des fins d'évaluation n'est pas triviale. [40]

Un certain nombre de mesures sont adaptées à partir de variantes utilisées pour évaluer les tâches de classification. Au lieu de compter le nombre de fois qu'une classe a été correctement attribuée à un seul point de données (connu sous le nom de 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 censée être dans le même groupe. [33]

Comme pour l'évaluation interne, plusieurs mesures d'évaluation externe existent, [37] : 125–129  par exemple :

  • Pureté : La pureté est une mesure de la mesure dans laquelle les grappes contiennent une seule classe. [36] Son calcul peut être pensé comme suit : Pour chaque cluster, comptez le nombre de points de données de la classe la plus courante 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 clusterset un ensemble de classes, les deux partitionnantpoints de données, la pureté peut être définie comme :
Cette mesure ne pénalise pas le fait d'avoir de nombreux clusters, et plus de clusters faciliteront la production d'une grande pureté. Un score de pureté de 1 est toujours possible en plaçant chaque point de données dans son propre cluster. De plus, 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 jeu de données de taille 1000 se compose de deux classes, l'une contenant 999 points et l'autre contenant 1 point, alors chaque partition possible aura une pureté d'au moins 99,9 %.
L'indice Rand calcule à quel point les clusters (renvoyés par l'algorithme de clustering) sont similaires aux classifications de référence. Il peut être calculé à l'aide de la formule suivante :
est le nombre de vrais positifs,est le nombre de vrais négatifs ,est le nombre de faux positifs , etest le nombre de faux négatifs . Les instances comptées ici sont le nombre d' affectations correctes par paires . C'est-à-dire,est le nombre de paires de points regroupés dans la partition prédite et dans la partition de vérité terrain,est le nombre de paires de points regroupés dans la partition prédite mais pas dans la partition de vérité terrain, etc. Si l'ensemble de données est de taille N, alors.

Un problème avec l' indice Rand est que les faux positifs et les faux négatifs sont pondérés de la même manière. Cela peut être une caractéristique indésirable pour certaines applications de clustering. La mesure F répond à cette préoccupation, [ citation nécessaire ] , tout comme l' indice Rand ajusté corrigé du hasard .

La mesure F peut être utilisée pour équilibrer la contribution des faux négatifs en pondérant le rappel via un paramètre. Définissons la précision et le rappel (les deux mesures d'évaluation externe en elles-mêmes) comme suit :
est le taux de précision etest le taux de rappel . Nous pouvons calculer la F-mesure en utilisant la formule suivante : [36]
Lorsque,. En d'autres termes, le rappel n'a pas d'impact sur la F-mesure lorsque, et augmentantalloue une quantité croissante de poids à rappeler dans la F-mesure finale.
Égalementn'est pas pris en compte et peut varier de 0 vers le haut sans borne.
L'indice de Jaccard est utilisé pour quantifier la similarité entre deux jeux de données. L' indice Jaccard prend une valeur comprise entre 0 et 1. Un indice de 1 signifie que les deux jeux de données sont identiques, et un indice de 0 indique que les jeux de données n'ont aucun élément commun. L'indice Jaccard est défini par la formule suivante :
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.
Égalementn'est pas pris en compte et peut varier de 0 vers le haut sans borne.
La mesure symétrique Dice double le poids surtout en ignorant:
L'indice Fowlkes-Mallows calcule la 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é à l'aide de la formule suivante :
est le nombre de vrais positifs ,est le nombre de faux positifs , etest le nombre de faux négatifs . leindex est la moyenne géométrique de la précision et du rappel et, et est donc également connue sous le nom de mesure G, tandis que la mesure F est leur moyenne harmonique. [43] [44] De plus, la précision et le rappel sont également connus sous le nom d'indices de Wallaceet. [45] Les versions normalisées par hasard du rappel, de la précision et de la mesure G correspondent à l' information , à la marque et à la corrélation de Matthew et sont fortement liées à Kappa . [46]
Une matrice de confusion peut être utilisée pour visualiser rapidement les résultats d'un algorithme de classification (ou de regroupement). Il montre à quel point un cluster est différent du cluster de référence.

Tendance cluster

Mesurer la tendance des clusters consiste à mesurer dans quelle mesure les clusters existent dans les données à regrouper, et peut être effectué comme test initial, avant de tenter le clustering. Une façon de le faire est de comparer les données à des données aléatoires. En moyenne, les données aléatoires ne doivent pas avoir de clusters.

Il existe plusieurs formulations de la statistique de Hopkins . [47] Un cas typique est le suivant. [48] ​​Laissezêtre l'ensemble depoints de données dansespace dimensionnel. Considérons un échantillon aléatoire (sans remise) depoints de données avec les membres. Générer également un ensembledepoints de données uniformément répartis au hasard. Définissez maintenant deux mesures de distance,être la distance dede son plus proche voisin en X etêtre la distance dede son voisin le plus proche en X. Nous définissons alors la statistique de Hopkins comme suit :
Avec cette définition, les données aléatoires uniformes devraient avoir tendance à avoir des valeurs proches de 0,5, et les données groupées devraient avoir tendance à avoir des valeurs plus proches 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 à distance uniformes).

Candidatures

Biologie, biologie computationnelle et bioinformatique

Écologie végétale et animale
L'analyse typologique est utilisée pour décrire et faire des comparaisons spatiales et temporelles de communautés (assemblages) d'organismes dans des environnements hétérogènes. Il est également utilisé dans la systématique des plantes pour générer des phylogénies artificielles ou des groupes d'organismes (individus) au niveau de l'espèce, du genre ou à un niveau supérieur qui partagent un certain nombre d'attributs.
Transcriptomique
Le clustering est utilisé pour construire des groupes de gènes avec des modèles d'expression apparentés (également appelés gènes coexprimés) comme dans l'algorithme de clustering HCS . [49] [50] Souvent, ces groupes contiennent des protéines fonctionnellement apparentées, telles que des enzymes pour une voie spécifique ou des gènes qui sont co-régulés. Les expériences à haut débit utilisant des étiquettes de séquence exprimées (EST) ou des puces à ADN peuvent être un outil puissant pour l'annotation du génome - un aspect général de la génomique .
Analyse de séquence
Le regroupement de séquences est utilisé pour regrouper des séquences homologues en familles de gènes . [51] C'est un concept très important en bioinformatique et en biologie évolutive en général. Voir évolution par duplication de gène .
Plateformes de génotypage à haut débit
Des algorithmes de clustering sont utilisés pour attribuer automatiquement des génotypes. [52]
Regroupement génétique humain
La similarité des données génétiques est utilisée dans le regroupement pour déduire les structures de population.

Médecine

L'imagerie médicale
Sur les scans TEP , l'analyse par grappes peut être utilisée pour différencier différents types de tissus dans une image tridimensionnelle à de nombreuses fins différentes. [53]
Analyse de l'activité antimicrobienne
L'analyse par grappes peut être utilisée pour analyser les schémas de résistance aux antibiotiques, pour classer les composés antimicrobiens en fonction de leur mécanisme d'action, pour classer les antibiotiques en fonction de leur activité antibactérienne.
Segmentation IMRT
Le regroupement peut être utilisé pour diviser une carte de fluence en régions distinctes pour la conversion en champs livrables en radiothérapie basée sur MLC.

Commerce et marketing

Étude de marché
L'analyse par grappes est largement utilisée dans les études de marché lorsque l'on travaille avec des données multivariées provenant d' enquêtes et de panels de test. Les chercheurs de marché utilisent l'analyse par grappes pour répartir la population générale des consommateurs en segments de marché et pour mieux comprendre les relations entre les différents groupes de consommateurs/ clients potentiels , et pour une utilisation dans la segmentation du marché , le positionnement des produits , le développement de nouveaux produits et la sélection des marchés tests.
Regroupement d'articles commerciaux
Le regroupement peut être utilisé pour regrouper tous les articles d'achat disponibles sur le Web dans un ensemble de produits uniques. Par exemple, tous les articles sur eBay peuvent être regroupés en produits uniques (eBay n'a pas le concept de SKU ).

Web mondial

Analyse des réseaux sociaux
Dans l'étude des réseaux sociaux , le regroupement peut être utilisé pour reconnaître les communautés au sein de grands groupes de personnes.
Regroupement des résultats de recherche
Dans le processus de regroupement intelligent des fichiers et des sites Web, le regroupement peut être utilisé pour créer un ensemble de résultats de recherche plus pertinent par rapport aux moteurs de recherche normaux comme Google [ citation nécessaire ] . Il existe actuellement un certain nombre d'outils de clustering basés sur le Web tels que Clusty . Il peut également être utilisé pour renvoyer un ensemble de résultats plus complet dans les cas où un terme de recherche pourrait faire référence à des choses très différentes. Chaque utilisation distincte du terme correspond à un cluster unique de résultats, permettant à un algorithme de classement de renvoyer des résultats complets en sélectionnant le meilleur résultat de chaque cluster. [54]
Optimisation de la carte glissante
La carte de photos de Flickr et d'autres sites cartographiques utilisent le regroupement pour réduire le nombre de marqueurs sur une carte. Cela le rend à la fois plus rapide et réduit la quantité d'encombrement visuel.

Informatique

Évolution du logiciel
Le clustering est utile dans l'évolution des logiciels car il aide à réduire les propriétés héritées du code en réformant les fonctionnalités qui se sont dispersées. C'est une forme de restructuration et donc un moyen de maintenance préventive directe.
Segmentation des images
Le regroupement peut être utilisé pour diviser une image numérique en régions distinctes pour la détection de bordure ou la reconnaissance d'objets . [55]
Algorithmes évolutionnaires
Le regroupement peut être utilisé pour identifier différentes niches au sein de la population d'un algorithme évolutif afin que les opportunités de reproduction puissent être réparties plus uniformément entre les espèces ou sous-espèces en évolution.
Systèmes de recommandation
Les systèmes de recommandation sont conçus pour recommander de nouveaux articles en fonction des goûts de l'utilisateur. Ils utilisent parfois des algorithmes de clustering pour prédire les préférences d'un utilisateur en fonction des préférences des autres utilisateurs dans le cluster de l'utilisateur.
Chaîne de Markov Méthodes de Monte Carlo
Le regroupement est souvent utilisé pour localiser et caractériser les extrema dans la distribution cible.
Détection d'une anomalie
Les anomalies/valeurs aberrantes sont généralement - que ce soit explicitement ou implicitement - définies par rapport à la structure de regroupement des données.
Traitement du langage naturel
Le regroupement peut être utilisé pour résoudre l'ambiguïté lexicale . [54]

Sciences sociales

Analyse de séquences en sciences sociales
L'analyse typologique est utilisée pour identifier des modèles de trajectoires de vie familiale, de carrières professionnelles et d'utilisation du temps quotidienne ou hebdomadaire, par exemple.
Analyse de la criminalité
L'analyse par grappes peut être utilisée pour identifier les zones où il y a une plus grande incidence de types particuliers de crime. En identifiant ces zones distinctes ou « points chauds » où un crime similaire s'est produit au cours d'une période donnée, il est possible de gérer plus efficacement les ressources d'application de la loi.
Exploration de données éducatives
L'analyse typologique est par exemple utilisée pour identifier des groupes d'écoles ou d'élèves ayant des propriétés similaires.
Typologies
À partir des données des sondages, des projets tels que ceux entrepris par le Pew Research Center utilisent l'analyse par grappes pour discerner les typologies d'opinions, d'habitudes et de données démographiques qui peuvent être utiles en politique et en marketing.

Autres

Robotique de terrain
Les algorithmes de clustering sont utilisés pour la connaissance robotique de la situation afin de suivre les objets et de détecter les valeurs aberrantes dans les données des capteurs. [56]
Chimie mathématique
Pour trouver une similitude structurelle, etc., par exemple, 3000 composés chimiques ont été regroupés dans l'espace de 90 indices topologiques . [57]
Climatologie
Pour trouver les régimes météorologiques ou les modèles atmosphériques de pression au niveau de la mer préférés. [58]
La finance
L'analyse par grappes a été utilisée pour regrouper les actions en secteurs. [59]
Géologie pétrolière
L'analyse de grappes est utilisée pour reconstruire les données de carotte de fond de trou manquantes ou les courbes logarithmiques manquantes afin d'évaluer les propriétés du réservoir.
Géochimie
Le regroupement des propriétés chimiques dans différents emplacements d'échantillons.

Voir aussi

Types spécialisés d'analyse de cluster

Techniques utilisées dans l'analyse de cluster

Projection et prétraitement des données

Autre

Références

  1. ^ Pilote et Kroeber (1932). "Expression quantitative des relations culturelles" . Publications de l'Université de Californie en archéologie et ethnologie américaines . Expression quantitative des relations culturelles : 211–256 – via http://dpg.lib.berkeley.edu . {{cite journal}}: Lien externe dans |via=( aide )
  2. ^ Zubin, Joseph (1938). "Une technique pour mesurer la similitude d'esprit". Le Journal de la psychologie anormale et sociale . 33 (4): 508–516. doi : 10.1037/h0055441 . ISSN 0096-851X . 
  3. ^ Tryon, Robert C. (1939). Analyse de cluster : profil de corrélation et analyse orthométrique (facteur) pour l'isolement des unités dans l'esprit et la personnalité . Edwards Frères.
  4. ^ Cattell, RB (1943). "La description de la personnalité: traits de base résolus en grappes". Journal de psychologie anormale et sociale . 38 (4): 476–506. doi : 10.1037/h0054116 .
  5. ^ un bcdef Estivill - Castro , Vladimir (20 juin 2002). "Pourquoi tant d'algorithmes de clustering - Un document de position". Bulletin ACM SIGKDD Explorations . 4 (1): 65–75. doi : 10.1145/568574.568575 . S2CID 7329935 . 
  6. ^ James A. Davis (mai 1967) "Clustering et équilibre structurel dans les graphiques", Human Relations 20: 181–7
  7. ^ Everitt, Brian (2011). Analyse groupée . Chichester, West Sussex, Royaume-Uni : Wiley. ISBN 9780470749913.
  8. ^ Sibson, R. (1973). "SLINK : un algorithme d'une efficacité optimale pour la méthode de cluster à lien unique" (PDF) . La revue informatique . Société informatique britannique. 16 (1): 30–34. doi : 10.1093/comjnl/16.1.30 .
  9. ^ Defays, D. (1977). "Un algorithme efficace pour une méthode de lien complète". La revue informatique . Société informatique britannique. 20 (4): 364–366. doi : 10.1093/comjnl/20.4.364 .
  10. ^ Lloyd, S. (1982). "Quantification des moindres carrés en PCM". Transactions IEEE sur la théorie de l'information . 28 (2): 129-137. doi : 10.1109/TIT.1982.1056489 .
  11. ^ Kriegel, Hans-Peter ; Kröger, pair ; Sander, Jörg; Zimek, Arthur (2011). « Clustering basé sur la densité » . WIREs Exploration de données et découverte de connaissances . 1 (3): 231-240. doi : 10.1002/widm.30 . S2CID 36920706 . 
  12. ^ Recherche académique Microsoft : articles d'exploration de données les plus cités
  13. ^ Ester, Martin; Kriegel, Hans-Peter ; Sander, Jörg; Xu, Xiaowei (1996). "Un algorithme basé sur la densité pour découvrir des clusters dans de grandes bases de données spatiales avec du bruit". A Simoudis, Evangelos ; Han, Jiawei ; Fayyad, Usama M. (éd.). Actes de la deuxième conférence internationale sur la découverte des connaissances et l'exploration de données (KDD-96) . AAAA Appuyez sur . p. 226–231. ISBN 1-57735-004-9.
  14. ^ Ankerst, Mihael; Breunig, Markus M.; Kriegel, Hans-Peter ; Sander, Jörg (1999). "OPTICS : Ordonner des points pour identifier la structure de regroupement". Conférence internationale ACM SIGMOD sur la gestion des données . ACM Appuyez sur . p. 49–60. CiteSeerX 10.1.1.129.6542 . 
  15. ^ un b Achtert, E.; Bohm, C.; En ligneKröger, P. (2006). "DeLi-Clu : renforcer la robustesse, l'exhaustivité, la convivialité et l'efficacité du clustering hiérarchique par un classement de paire la plus proche". Progrès dans la découverte des connaissances et l'exploration de données . Notes de cours en informatique. Vol. 3918. pp. 119–128. CiteSeerX 10.1.1.64.1161 . doi : 10.1007/11731139_16 . ISBN  978-3-540-33206-0.
  16. ^ Aggarwal, Charu C., éditeur. Reddy, Chandan K., éditeur. Clustering de données : algorithmes et applications . ISBN 978-1-315-37351-5. OCLC  1110589522 . {{cite book}}: |last=a un nom générique ( aide )Maint CS1 : noms multiples : liste des auteurs ( lien )
  17. ^ Sculley, D. (2010). Clustering k-means à l'échelle du Web . Proc. 19ème WW.
  18. ^ Huang, Z. (1998). "Extensions de l' algorithme k -means pour regrouper de grands ensembles de données avec des valeurs catégorielles". Exploration de données et découverte de connaissances . 2 (3): 283–304. doi : 10.1023/A:1009769707641 . S2CID 11323096 . 
  19. ^ R. Ng et J. Han. "Méthode de regroupement efficace et efficace pour l'exploration de données spatiales". Dans : Actes de la 20e Conférence VLDB, pages 144-155, Santiago, Chili, 1994.
  20. ^ Tian Zhang, Raghu Ramakrishnan, Miron Livny. " Une méthode efficace de clustering de données pour les très grandes bases de données ". Dans : Proc. Conf. sur la gestion des données, ACM SIGMOD, pp. 103–114.
  21. ^ Kriegel, Hans-Peter ; Kröger, pair ; Zimek, Arthur (juillet 2012). "Regroupement de sous-espaces". Examens interdisciplinaires de Wiley : exploration de données et découverte de connaissances . 2 (4): 351–364. doi : 10.1002/widm.1057 . S2CID 7241355 . 
  22. ^ Agrawal, R.; Gehrke, J.; Gunopulos, D.; En ligneRaghavan, P. (2005). « Regroupement automatique de sous-espace de données de haute dimension ». Exploration de données et découverte de connaissances . 11 : 5–33. CiteSeerX 10.1.1.131.5152 . doi : 10.1007/s10618-005-1396-1 . S2CID 9289572 .  
  23. ^ Karin Kailing, Hans-Peter Kriegel et Peer Kröger. Clustering de sous-espaces à densité connectée pour des données de grande dimension . Dans : Proc. SIAM Int. Conf. sur l'exploration de données (SDM'04) , pp. 246–257, 2004.
  24. ^ Achtert, E.; Bohm, C.; Kriegel, H.-P. ; Kröger, P.; Müller-Gorman, I.; En ligneZimek, A. (2006). "Trouver des hiérarchies de clusters de sous-espace". Découverte des connaissances dans les bases de données : PKDD 2006 . Notes de cours en informatique. Vol. 4213. pp. 446–453. CiteSeerX 10.1.1.705.2956 . doi : 10.1007/11871637_42 . ISBN  978-3-540-45374-1.
  25. ^ Achtert, E.; Bohm, C.; Kriegel, HP ; Kröger, P.; Müller-Gorman, I.; En ligneZimek, A. (2007). "Détection et visualisation des hiérarchies de clusters de sous-espace". Avancées dans les bases de données : concepts, systèmes et applications . Notes de cours en informatique. Vol. 4443. pp. 152–163. CiteSeerX 10.1.1.70.7843 . doi : 10.1007/978-3-540-71703-4_15 . ISBN  978-3-540-71702-7.
  26. ^ Achtert, E.; Bohm, C.; Kröger, P.; En ligneZimek, A. (2006). "Hiérarchies minières des clusters de corrélation". Proc. 18e Conférence internationale sur la gestion des bases de données scientifiques et statistiques (SSDBM) : 119–128. CiteSeerX 10.1.1.707.7872 . doi : 10.1109/SSDBM.2006.35 . ISBN  978-0-7695-2590-7. S2CID  2679909 .
  27. ^ Bohm, C.; Kailing, K.; Kröger, P.; En ligneZimek, A. (2004). "Calcul des Grappes d'Objets Connectés de Corrélation". Actes de la conférence internationale ACM SIGMOD 2004 sur la gestion des données - SIGMOD '04 . p. 455. CiteSeerX 10.1.1.5.1279 . doi : 10.1145/1007568.1007620 . ISBN  978-1581138597. S2CID  6411037 .
  28. ^ Achtert, E.; Bohm, C.; Kriegel, HP ; Kröger, P.; En ligneZimek, A. (2007). "Sur l'exploration des relations complexes des grappes de corrélation". 19e Conférence internationale sur la gestion des bases de données scientifiques et statistiques (SSDBM 2007) . p. 7. CiteSeerX 10.1.1.71.5021 . doi : 10.1109/SSDBM.2007.21 . ISBN  978-0-7695-2868-7. S2CID  1554722 .
  29. ^ Meila, Marina (2003). "Comparer les regroupements par la variation de l'information". Théorie de l'apprentissage et machines à noyau . Notes de cours en informatique. Vol. 2777. pp. 173–187. doi : 10.1007/978-3-540-45167-9_14 . ISBN 978-3-540-40720-1.
  30. ^ Kraskov, Alexandre; Stögbauer, Harald; Andrzejak, Ralph G.; Grassberger, Peter (1er décembre 2003). "Clusterisation hiérarchique basée sur des informations mutuelles". arXiv : q-bio/0311039 . Bibcode : 2003q.bio....11039K . {{cite journal}}:Citer le journal nécessite |journal=( aide )
  31. ^ Auffarth, B. (18-23 juillet 2010). "Clustering par un algorithme génétique avec un opérateur de mutation biaisé" . Wcci Cec . IEEE.
  32. ^ Frey, BJ; En ligneDueck, D. (2007). "Clustering en passant des messages entre les points de données". Sciences . 315 (5814): 972–976. Bibcode : 2007Sci...315..972F . CiteSeerX 10.1.1.121.3145 . doi : 10.1126/science.1136800 . PMID 17218491 . S2CID 6502291 .   
  33. ^ un bcd Pfitzner , Darius ; Leibbrandt, Richard; Pouvoirs, David (2009). "Caractérisation et évaluation des mesures de similarité pour les paires de regroupements". Connaissances et systèmes d'information . Springer. 19 (3): 361–394. doi : 10.1007/s10115-008-0150-6 . S2CID 6935380 . 
  34. ^ un bc Feldman , Ronen; Sanger, James (2007-01-01). Le manuel de Text Mining : Approches avancées dans l'analyse de données non structurées . Université de Cambridge. Presse. ISBN 978-0521836579. OCLC  915286380 .
  35. ^ un b Weiss, Sholom M.; Indurkhya, Nitin; Zhang, Tong ; En ligneDamerau, Fred J. (2005). Text Mining : méthodes prédictives pour l'analyse d'informations non structurées . Springer. ISBN 978-0387954332. OCLC  803401334 .
  36. ^ un bc Manning , Christopher D.; Raghavan, Prabhakar ; Schütze, Hinrich (2008-07-07). Introduction à la recherche d'informations . La presse de l'Universite de Cambridge. ISBN 978-0-521-86571-5.
  37. ^ a b Découverte de connaissances dans les bases de données - Partie III - Clustering (PDF) , Université de Heidelberg , 2017
  38. ^ Dunn, J. (1974). "Amas bien séparés et partitions floues optimales". Journal de cybernétique . 4 : 95–104. doi : 10.1080/01969727408546059 .
  39. ^ un b Färber, Ines; Günnemann, Stephan; Kriegel, Hans-Peter ; Kröger, pair ; Muller, Emmanuel; Schubert, Erich; Seidl, Thomas; Zimek, Arthur (2010). "Sur l'utilisation des étiquettes de classe dans l'évaluation des clusters" (PDF) . Dans Fern, Xiaoli Z.; Davidson, Ian; Dy, Jennifer (éd.). MultiClust : découvrir, résumer et utiliser plusieurs clusters . ACM SIGKDD .
  40. ^ Pourrajabi, M.; Moulavi, D.; Campello, RJGB; Zimek, A. ; Sander, J.; En ligneGoebel, R. (2014). "Sélection de modèle pour le clustering semi-supervisé". Actes de la 17e Conférence internationale sur l'extension de la technologie des bases de données (EDBT) . p. 331–342. doi : 10.5441/002/edbt.2014.31 .
  41. ^ Rand, WM (1971). "Critères objectifs pour l'évaluation des méthodes de clustering". Journal de l'Association statistique américaine . Association statistique américaine. 66 (336): 846–850. arXiv : 1704.01036 . doi : 10.2307/2284239 . JSTOR 2284239 . 
  42. ^ Fowlkes, EB; Mallows, CL (1983). "Une méthode pour comparer deux regroupements hiérarchiques". Journal de l'Association statistique américaine . 78 (383): 553–569. doi : 10.1080/01621459.1983.10478008 . JSTOR 2288117 . 
  43. ^ Pouvoirs, David (2003). Rappel et Précision contre le Bookmaker . Conférence internationale sur les sciences cognitives. pages 529–534.
  44. ^ Arabie, P. (1985). "Comparer des partitions". Journal de classement . 2 (1) : 1985. doi : 10.1007/BF01908075 . S2CID 189915041 . 
  45. ^ Wallace, DL (1983). "Commenter". Journal de l'Association statistique américaine . 78 (383): 569–579. doi : 10.1080/01621459.1983.10478009 .
  46. ^ Pouvoirs, David (2012). Le problème avec Kappa . Chapitre européen de l'Association for Computational Linguistics. p. 345–355.
  47. ^ Hopkins, Brian; Skellam, John Gordon (1954). "Une nouvelle méthode pour déterminer le type de distribution des individus végétaux". Annales de Botanique . Annals Botany Co. 18 (2): 213–227. doi : 10.1093/oxfordjournals.aob.a083391 .
  48. ^ Banerjee, A. (2004). "Validation des clusters à l'aide de la statistique de Hopkins". Conférence internationale IEEE sur les systèmes flous . 1 : 149–153. doi : 10.1109/FUZZY.2004.1375706 . ISBN 978-0-7803-8353-1. S2CID  36701919 .
  49. ^ Johnson, Stephen C. (1967-09-01). "Schémas de clustering hiérarchiques". Psychométrie . 32 (3): 241–254. doi : 10.1007/BF02289588 . ISSN 1860-0980 . PMID 5234703 . S2CID 930698 .   
  50. ^ Hartuv, Erez; Shamir, Ron (2000-12-31). "Un algorithme de clustering basé sur la connectivité graphique". Lettres de traitement de l'information . 76 (4): 175–181. doi : 10.1016/S0020-0190(00)00142-3 . ISSN 0020-0190 . 
  51. ^ Remm, Maido; Tempête, Christian EV; Sonnhammer, Erik LL (2001-12-14). "Regroupement automatique des orthologues et des paralogues à partir de comparaisons d'espèces par paires11Édité par F. Cohen". Tourillon de biologie moléculaire . 314 (5): 1041–1052. doi : 10.1006/jmbi.2000.5197 . ISSN 0022-2836 . PMID 11743721 .  
  52. ^ Botstein, David; Cox, David R.; Risch, Neil; Olshen, Richard; Bordure, David ; Dzau, Victor J.; Chen, Yii-Der I.; Hébert, Joan; Pesich, Robert (2001-07-01). "Génotypage à haut débit avec des polymorphismes de nucléotide unique" . Recherche sur le génome . 11 (7): 1262-1268. doi : 10.1101/gr.157801 . ISSN 1088-9051 . PMC 311112 . PMID 11435409 .   
  53. ^ Filipovych, romain; Resnick, Susan M.; Davatzikos, Christos (2011). "Analyse de grappes semi-supervisée de données d'imagerie" . NeuroImage . 54 (3): 2185–2197. doi : 10.1016/j.neuroimage.2010.09.074 . PMC 3008313 . PMID 20933091 .  
  54. ^ un b Di Marco, Antonio; Navigli, Roberto (2013). "Regroupement et diversification des résultats de recherche Web avec l'induction de sens de mot basée sur des graphiques". Linguistique computationnelle . 39 (3): 709–754. doi : 10.1162/COLI_a_00148 . S2CID 1775181 . 
  55. ^ Bewley, A., & Upcroft, B. (2013). Avantages de l'exploitation de la structure de projection pour segmenter les nuages ​​de points 3D denses. Dans la conférence australienne sur la robotique et l'automatisation [1]
  56. ^ Bewley, A.; et coll. "Estimation du volume en temps réel d'une charge utile de dragline". Conférence internationale IEEE sur la robotique et l'automatisation . 2011 : 1571–1576.
  57. ^ Basak, SC; Magnuson, RV ; Niemi, CJ; Régal, RR (1988). "Déterminer la similarité structurelle des produits chimiques à l'aide d'indices théoriques de graphes". Discr. Appl. Mathématiques . 19 (1–3) : 17–44. doi : 10.1016/0166-218x(88)90004-2 .
  58. ^ Huth, R.; et coll. (2008). "Classifications des modèles de circulation atmosphérique: avancées récentes et applications". Anne. NY Acad. Sci . 1146 : 105–152. Bibcode : 2008NYASA1146..105H . doi : 10.1196/annals.1446.019 . PMID 19076414 . S2CID 22655306 .  
  59. ^ Arnott, Robert D. (1980-11-01). "Analyse de grappe et co-mouvement des prix des actions". Journal des analystes financiers . 36 (6): 56–62. doi : 10.2469/faj.v36.n6.56 . ISSN 0015-198X .