Analyse des clusters – Wikipédia

Techniques
2 avril 2021
1197
208 minutes read

Tâche de regrouper un ensemble d’objets afin que les objets du même groupe (ou cluster) soient plus similaires les uns aux autres qu’à ceux des autres clusters

Le résultat d’une analyse de grappes montré comme la coloration des carrés en trois grappes.

L’analyse par grappes ou regroupement est la tâche de regrouper un ensemble d’objets de telle manière que les objets d’un même groupe (appelé grappe) sont plus similaires (dans un certain sens) les uns aux autres qu’à ceux des autres groupes (grappes). Il s’agit d’une tâche principale d’analyse de données exploratoire et d’une technique commune 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. Cela 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 grappes incluent des groupes avec de petites distances entre les membres de la grappe, 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 regroupement approprié et les réglages des paramètres (y compris les paramètres tels que la fonction de distance à utiliser, un seuil de densité ou le nombre de groupes attendus) dépendent de l’ensemble de données individuel et de l’utilisation prévue des résultats. L’analyse de cluster en tant que telle n’est pas une tâche automatique, mais un processus itératif de découverte de connaissances ou d’optimisation multi-objectifs interactive 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 classification automatique, taxonomie numérique, botryologie (du grec βότρυς « raisin »), analyse typologique, et détection de la communauté. Les différences subtiles résident souvent dans l’utilisation des résultats: alors que dans l’exploration de données, les groupes résultants sont intéressants, dans la classification automatique, le pouvoir discriminant qui en résulte est intéressant.

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

Définition[[[[Éditer]

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, à nouveau, des algorithmes différents peuvent être donnés. La notion de cluster, telle qu’elle est 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èle de connectivités: par exemple, le clustering hiérarchique crée des modèles basés sur la connectivité à distance.
Modèle centroïdes: par exemple, l’algorithme k-means représente chaque cluster par un seul vecteur moyen.
Modèle de distributions: les grappes sont modélisées à l’aide de distributions statistiques, telles que les distributions normales multivariées utilisées par l’algorithme de maximisation des espérances.
Modèle de densités: par exemple, DBSCAN et OPTICS définissent les clusters comme des régions denses connectées dans l’espace de données.
Modèle de sous-espaces: dans le biclustering (également connu sous le nom de co-clustering ou de clustering à deux modes), les clusters sont modélisés avec les membres du cluster et les attributs pertinents.
Modèle de groupes: certains algorithmes ne fournissent pas un modèle raffiné pour leurs résultats et fournissent simplement les informations de regroupement.
Modèle basé sur un graphiques: une clique, c’est-à-dire un sous-ensemble de nœuds dans un graphe tel 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 assouplissements de l’exigence de connectivité complète (une fraction des arêtes peut être manquante) sont appelés quasi-cliques, comme dans l’algorithme de clustering HCS.
Modèles de graphes signés: Chaque chemin dans un graphe signé a un signe 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 un graphique bifurqué. L ‘«axiome de clusterability» plus faible (aucun cycle n’a exactement un front négatif) donne des résultats avec plus de deux clusters, ou sous-graphes avec seulement des fronts positifs.^[6]
Modèle neuronals: le réseau de neurones non supervisé le plus connu est la carte auto-organisée et ces modèles peuvent généralement être caractérisés comme similaires à un ou plusieurs des modèles ci-dessus, et incluent des modèles de sous-espace lorsque les réseaux de neurones implémentent une forme d’analyse en composants principaux ou d’analyse en composants indépendants .

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:

Clustering dur: chaque objet appartient ou non à un cluster
Clustering souple (également: regroupement flou): chaque objet appartient à chaque cluster dans une certaine mesure (par exemple, une probabilité d’appartenir au cluster)

Il existe également des distinctions plus fines possibles, par exemple:

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

Algorithmes[[[[Éditer]

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 Wikipédia se trouve dans la liste des algorithmes statistiques.

Il n’y a pas d’algorithme de regroupement objectivement «correct», mais comme il a été noté, «le regroupement 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)[[[[Éditer]

Clustering basé sur la connectivité, également appelé classification hiérarchique, est basé sur l’idée fondamentale que 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 des parties du cluster. À différentes distances, différents clusters se formeront, qui peuvent être représentés à l’aide d’un dendrogramme, ce qui explique d’où vient le nom commun de «clustering hiérarchique»: ces algorithmes ne fournissent pas un partitionnement unique de l’ensemble de données, mais fournissent plutôt une hiérarchie étendue de clusters qui fusionnent les uns avec les autres à certaines distances. Dans un dendrogramme, l’axe des y 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 toute une famille de méthodes qui diffèrent par la façon 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 se compose 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’objet), de clustering de liaison complet (le maximum de distances d’objet) et UPGMA ou WPGMA (« Méthode de groupe de paires non pondérées ou pondérées avec moyenne arithmétique », également connu sous le nom de liaison moyenne clustering). En outre, le regroupement hiérarchique peut être agglomératif (en commençant par des éléments uniques et en les agrégeant en grappes) ou en division (en commençant par l’ensemble de données complet et en 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 se présenteront soit comme des grappes supplémentaires, soit même provoqueront la fusion d’autres grappes (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é est ${displaystyle {mathcal {O}}(n^{3})}$ pour le clustering agglomératif et ${ displaystyle { mathcal {O}} (2 ^ {n-1})}$ pour clustering qui divise,^[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é ${displaystyle {mathcal {O}}(n^{2})}$ ) sont connus: SLINK [8] pour liaison simple et CLINK^[9] pour un clustering à liaison complète. Dans la communauté de l’exploration de données, ces méthodes sont reconnues comme un fondement théorique de l’analyse de cluster, mais souvent considérées comme obsolètes^{[[[[citation requise]}. Ils ont cependant inspiré de nombreuses méthodes ultérieures telles que le regroupement basé sur la densité.

Exemples de regroupement de liens
Liaison unique sur des données gaussiennes. À 35 clusters, le plus grand cluster commence à se fragmenter en parties plus petites, alors qu’avant il était toujours connecté au deuxième plus grand en raison de l’effet de liaison unique.
Lien unique sur les grappes basées sur la densité. 20 clusters extraits, dont la plupart contiennent des éléments uniques, car le clustering de liaison n’a pas de notion de «bruit».

Clustering basé sur le centre de gravité[[[[Éditer]

Dans le clustering centroïde, les clusters sont représentés par un vecteur central, qui ne fait pas nécessairement partie de l’ensemble de données. Lorsque le nombre de clusters est fixé à k, k-means le clustering donne une définition formelle comme un problème d’optimisation: trouvez le k centres de cluster et attribuez 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 approximatives. Une méthode approchée particulièrement connue est l’algorithme de Lloyd,^[10] souvent simplement appelé « algorithme k-means« (bien qu’un autre algorithme ait introduit ce nom). Il ne trouve cependant qu’un optimum local et est généralement exécuté plusieurs fois avec différentes initialisations aléatoires. Variations de k-les moyens incluent souvent des optimisations telles que le choix de la meilleure des exécutions multiples, mais aussi la restriction des centres de gravité aux membres de l’ensemble de données (k-médoïdes), en choisissant les médianes (k-medians clustering), en choisissant les centres initiaux moins aléatoirement (k-means ++) ou autoriser une affectation de cluster floue (fuzzy c-means).

Les plus kles algorithmes de type -means nécessitent le nombre de clusters – k – à préciser à l’avance, ce qui est considéré comme l’un des plus gros inconvénients de ces algorithmes. De plus, les algorithmes préfèrent des clusters de taille approximativement similaire, car ils attribueront toujours un objet au centre de gravité le plus proche. Cela conduit souvent à une coupe incorrecte des frontières des clusters (ce qui n’est pas surprenant puisque l’algorithme optimise les centres des clusters, pas les frontières des clusters).

K-means a un certain nombre de propriétés théoriques intéressantes. Premièrement, il partitionne l’espace de données en 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 discuté ci-dessous.

k-signifie des exemples de clustering
k-means sépare les données en cellules Voronoi, ce qui suppose des clusters de taille égale (pas adéquat ici)
k-means ne peut pas représenter des clusters basés sur la densité

Problèmes de clustering basés sur le centre de gravité, tels que k-moyens et k-médoïdes 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 centres de gravité de cluster et les «emplacements des consommateurs» comme les données à regrouper. Cela permet d’appliquer les solutions algorithmiques bien développées de la littérature sur l’emplacement des installations au problème de clustering basé sur les centroïdes actuellement considéré.

Clustering basé sur la distribution[[[[Éditer]

Le modèle de clustering le plus étroitement lié aux statistiques est basé sur des modèles de distribution. Les clusters peuvent alors être facilement définis comme des objets appartenant le plus vraisemblablement à la même distribution. Une propriété pratique de cette approche est que cela ressemble étroitement à la façon 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 à la complexité du modèle. Un modèle plus complexe sera généralement en mesure d’expliquer mieux 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 gaussiens (utilisant l’algorithme de maximisation des espérances). 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 assigné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éels, il se peut qu’il n’y ait pas de modèle mathématique défini de manière concise (par exemple, supposer que les distributions gaussiennes est une hypothèse assez forte sur les données).

Exemples de regroupement de modèles de mélange gaussien
Sur les données distribuées en Gauss, EM fonctionne bien, car il utilise des gaussiens pour modéliser les clusters
Les clusters basés sur la densité ne peuvent pas être modélisés à l’aide de distributions gaussiennes

Clustering basé sur la densité[[[[Éditer]

Dans le clustering basé sur la densité,^[11] les grappes sont définies comme des zones de densité plus élevée que le reste de l’ensemble de données. Les objets situés dans des 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.

Le plus populaire^[12] La méthode de clustering basée sur la densité est DBSCAN.^[13] Contrairement à de nombreuses méthodes plus récentes, il présente un modèle de cluster bien défini appelé «densité-atteignabilité». Semblable au clustering basé sur les liaisons, il est basé sur des points de connexion dans certains seuils de distance. Cependant, il ne connecte que les points qui satisfont à un critère de densité, dans la variante d’origine définie 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éterministe pour les points de base et de bruit, mais pas pour les points de frontière) à chaque exécution, il n’est donc pas nécessaire de l’exécuter plusieurs fois. OPTIQUE^[14] est une généralisation de DBSCAN qui supprime la nécessité de choisir une valeur appropriée pour le paramètre de plage ${displaystyle varepsilon }$ , et produit un résultat hiérarchique lié à celui de regroupement de liens. DeLi-Clu,^[15] Density-Link-Clustering combine des idées de clustering à liaison unique et OPTICS, éliminant le ${displaystyle varepsilon }$ paramètre entièrement et offrant des améliorations de performances par rapport à OPTICS en utilisant un Index de R-tree.

Le principal inconvénient de DBSCAN et OPTICS est qu’ils s’attendent à une sorte de baisse de densité pour détecter les frontières de cluster. Sur les ensembles de données avec, par exemple, des distributions gaussiennes qui se chevauchent – un cas d’utilisation courant dans les données artificielles – les frontières de cluster produites par ces algorithmes seront souvent arbitraires, car la densité de cluster diminue continuellement. Sur un ensemble de données constitué de mélanges de gaussiens, 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 où chaque objet est déplacé vers la zone la plus dense de son voisinage, sur la base d’une estimation de la densité du noyau. Finalement, les objets convergent vers des maxima locaux de densité. Semblable au regroupement de k-moyennes, ces «attracteurs de densité» peuvent servir de représentants pour l’ensemble de données, mais le décalage de moyenne peut détecter des grappes 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 uniforme de l’estimation de la densité du noyau, ce qui entraîne une sur-fragmentation des queues de cluster.^[15]

Exemples de clustering basés sur la densité
Clustering basé sur la densité avec DBSCAN.
DBSCAN suppose des clusters de densité similaire et peut avoir des problèmes pour séparer les clusters à proximité
OPTICS est une variante DBSCAN, améliorant la gestion des clusters de différentes densités

Clustering basé sur la grille[[[[Éditer]

La technique basée sur la grille est utilisée pour un ensemble de données multidimensionnelles.^[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:

Divisez l’espace de données en un nombre fini de cellules.
Sélectionnez au hasard une cellule «c», où c ne doit pas être parcouru au préalable.
Calculer la densité de «c»
Si la densité de «c» est supérieure à la densité seuil
1. Marquer la cellule «c» comme 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é 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é seuil.
Répétez les étapes 2, 3 et 4 jusqu’à ce que toutes les cellules soient traversées.
Arrêter.

DEVELOPPEMENTS récents[[[[Éditer]

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 se trouvent CLARANS,^[19] et BOULEAU.^[20] Avec le besoin récent de traiter des ensembles de données de plus en plus volumineux (également connus sous le nom de Big Data), la volonté d’échanger la signification sémantique des clusters générés contre des performances s’est accrue. Cela a conduit au développement de méthodes de pré-clustering telles que le clustering canopy, 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 comme k-signifie clustering.

Pour les données de grande dimension, de nombreuses méthodes existantes échouent en raison de la malédiction de la dimensionnalité, 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 haute dimension qui se concentrent sur le clustering de sous-espaces (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 modélisables 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 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] clustering de sous-espaces hiérarchiques et DiSH^[25]) et le clustering de corrélation (HiCO,^[26] clustering de corrélation hiérarchique, 4C^[27] utilisant la «connectivité de corrélation» et ERiC^[28] explorant les clusters de corrélation hiérarchiques basés sur la densité).

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

Évaluation et appréciation[[[[Éditer]

L’évaluation (ou «validation») des résultats du regroupement est aussi difficile que le regroupement lui-même.^[33] Les approches populaires impliquent « interne« évaluation, où le regroupement est résumé en un seul score de qualité, »externe« évaluation, où le regroupement est comparé à une classification de » vérité terrain « existante, »Manuel« évaluation par un expert humain, et »indirect« évaluation 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 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 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,^[34] et pas nécessairement à quel point le regroupement est utile.

L’évaluation externe a des problèmes similaires: si nous avons de telles étiquettes de «vérité terrain», alors nous n’aurions pas besoin de regrouper; et dans les applications pratiques, nous n’avons généralement pas de telles étiquettes. D’un autre côté, les étiquettes ne reflètent qu’un seul 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 finalement juger de la qualité réelle d’un clustering, mais cela nécessite une évaluation humaine,^[34] ce qui est hautement subjectif. Néanmoins, ces statistiques peuvent être assez informatives pour identifier les mauvais regroupements,^[35] mais il ne faut pas écarter l’évaluation humaine subjective.^[35]

Évaluation interne[[[[Éditer]

Lorsqu’un résultat de clustering est évalué en fonction des données qui ont été groupées elles-mêmes, cela s’appelle une é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 des grappes 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 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 surestimera probablement le clustering 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 produise 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 radicalement différent de modèles, 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 index d’évaluation supposent des clusters convexes. Sur un ensemble de données avec des clusters non convexes, ni l’utilisation de k-moyens, ni d’un critère d’évaluation qui suppose la convexité, n’est solide.

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 cluster devraient être plus similaires que les éléments de différents clusters.^[37]^:115–121 Par exemple, les méthodes suivantes peuvent être utilisées pour évaluer la qualité des algorithmes de clustering en fonction de critères internes:

L’indice de Davies – Bouldin peut être calculé par la formule suivante:

{ 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,

{displaystyle c_{i}}

est le centre de gravité du cluster

{ displaystyle i}

{ displaystyle sigma _ {i}}

est la distance moyenne de tous les éléments du cluster

{ displaystyle i}

au centre de gravité

{ displaystyle c_ {i}}

, et

{ displaystyle d (c_ {i}, c_ {j})}

est la distance entre les centres de gravité

{ displaystyle c_ {i}}

{ displaystyle c_ {j}}

. Étant donné que les algorithmes qui produisent des clusters avec de faibles distances intra-cluster (forte similarité intra-cluster) et des distances inter-cluster élevées (faible similitude inter-cluster) 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.

L’indice de Dunn vise à identifier des grappes denses et bien séparées. Il est défini comme le rapport entre la distance minimale inter-cluster et la distance intra-cluster maximale. Pour chaque partition de cluster, l’indice Dunn peut être calculé par la formule suivante:^[38]

{ displaystyle D = { frac { min _ {1 leq i

où ré(je,j) représente la distance entre les clusters je et j, et ré ‘(k) mesure la distance intra-cluster du cluster k. La distance inter-cluster ré(je,j) entre deux clusters peut être n’importe quel nombre de mesures de distance, comme la distance entre les centres de gravité des clusters. De même, la distance intra-cluster ré ‘(k) peut être mesurée de diverses manières, comme la distance maximale entre toute paire d’éléments dans le cluster k. Étant donné que les critères internes recherchent des clusters avec une similarité intra-cluster élevée et une faible similitude inter-cluster, les algorithmes qui produisent des clusters avec un indice de Dunn élevé sont plus souhaitables.

Le coefficient de silhouette met en contraste la distance moyenne entre les éléments du même cluster et la distance moyenne par rapport aux éléments d’autres clusters. 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 k– signifie clustering,^{[[[[citation requise]} et est également utilisé pour déterminer le nombre optimal de grappes.

Évaluation externe[[[[Éditer]

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. De tels référentiels 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 la proximité du regroupement par rapport aux classes de référence prédéterminées. Cependant, il a récemment été discuté de savoir si cela est adéquat pour des données réelles, ou uniquement sur des ensembles de données synthétiques avec une vérité 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 de connaissances, la reproduction de connaissances connues peut ne pas être nécessairement le résultat escompté.^[39] Dans le scénario spécial du clustering contraint, où les méta-informations (telles que les étiquettes de classe) sont déjà utilisées dans le processus de clustering, le maintien d’informations à des fins d’évaluation n’est pas trivial.^[40]

Un certain nombre de mesures sont adaptées 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 affectée à un seul point de données (connu sous le nom de vrais positifs), comme comptage de paires les métriques évaluent si chaque paire de points de données qui est vraiment dans le même cluster est prévue pour être dans le même cluster.^[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 clusters 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 commune dans ledit cluster. Maintenant, prenez la somme de tous les clusters et divisez-la par le nombre total de points de données. Formellement, étant donné un ensemble de clusters ${ displaystyle M}$ et un ensemble de classes ${ displaystyle D}$ , à la fois partitionnement ${ displaystyle N}$ points de données, la pureté peut être définie comme:

{ displaystyle { frac {1} {N}} sum _ {m in M} max _ {d in D} {| m cap d |}}

Cette mesure ne pénalise pas le fait d’avoir de nombreux clusters, et plus de clusters facilitera 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 ensemble 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 la similitude des clusters (renvoyés par l’algorithme de clustering) avec les classifications de référence. Il peut être calculé à l’aide de la formule suivante:

{ displaystyle RI = { frac {TP + TN} {TP + FP + FN + TN}}}

où

{displaystyle TP}

est le nombre de vrais positifs,

{ displaystyle TN}

est le nombre de vrais négatifs,

{displaystyle FP}

est le nombre de faux positifs, et

{displaystyle FN}

est le nombre de faux négatifs. Les instances comptées ici sont le nombre de bons par paire affectations. C’est-à-dire,

{displaystyle TP}

est le nombre de paires de points regroupés dans la partition prédite et dans la partition de vérité terrain,

{ 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é terrain, etc. Si le jeu de données est de taille N, alors

{displaystyle TP+TN+FP+FN={binom {N}{2}}}

One issue with the Rand index is that false positives and false negatives are equally weighted. This may be an undesirable characteristic for some clustering applications. The F-measure addresses this concern,^{[[[[citation needed]} as does the chance-corrected adjusted Rand index.

The F-measure can be used to balance the contribution of false negatives by weighting recall through a parameter

{displaystyle beta geq 0}

. Let precision et recall (both external evaluation measures in themselves) be defined as follows:

{displaystyle P={frac {TP}{TP+FP}}}

{displaystyle R={frac {TP}{TP+FN}}}

où

{displaystyle P}

is the precision rate and

{displaystyle R}

is the recall rate. We can calculate the F-measure by using the following formula:^[36]

{displaystyle F_{beta }={frac {(beta ^{2}+1)cdot Pcdot R}{beta ^{2}cdot P+R}}}

Lorsque

{displaystyle beta =0}

{displaystyle F_{0}=P}

. In other words, recall has no impact on the F-measure when

{displaystyle beta =0}

, and increasing

{displaystyle beta }

allocates an increasing amount of weight to recall in the final F-measure.

Également

{displaystyle TN}

is not taken into account and can vary from 0 upward without bound.

The Jaccard index is used to quantify the similarity between two datasets. le Jaccard index takes on a value between 0 and 1. An index of 1 means that the two dataset are identical, and an index of 0 indicates that the datasets have no common elements. The Jaccard index is defined by the following formula:

{displaystyle J(A,B)={frac {|Acap B|}{|Acup B|}}={frac {TP}{TP+FP+FN}}}

This is simply the number of unique elements common to both sets divided by the total number of unique elements in both sets.

Également

{displaystyle TN}

is not taken into account and can vary from 0 upward without bound.

The Dice symmetric measure doubles the weight on

{displaystyle TP}

while still ignoring

{displaystyle TN}

{displaystyle DSC={frac {2TP}{2TP+FP+FN}}}

The Fowlkes–Mallows index computes the similarity between the clusters returned by the clustering algorithm and the benchmark classifications. The higher the value of the Fowlkes–Mallows index the more similar the clusters and the benchmark classifications are. It can be computed using the following formula:

{displaystyle FM={sqrt {{frac {TP}{TP+FP}}cdot {frac {TP}{TP+FN}}}}}

où

{displaystyle TP}

is the number of true positives,

{displaystyle FP}

is the number of false positives, and

{displaystyle FN}

is the number of false negatives. le

{displaystyle FM}

index is the geometric mean of the precision and recall

{displaystyle P}

{displaystyle R}

, and is thus also known as the G-measure, while the F-measure is their harmonic mean.[43]^[44] Moreover, precision and recall are also known as Wallace’s indices

{displaystyle B^{I}}

{displaystyle B^{II}}

.[45] Chance normalized versions of recall, precision and G-measure correspond to Informedness, Markedness and Matthews Correlation and relate strongly to Kappa.^[46]

A confusion matrix can be used to quickly visualize the results of a classification (or clustering) algorithm. It shows how different a cluster is from the gold standard cluster.

Cluster tendency[[[[edit]

To measure cluster tendency is to measure to what degree clusters exist in the data to be clustered, and may be performed as an initial test, before attempting clustering. One way to do this is to compare the data against random data. On average, random data should not have clusters.

There are multiple formulations of the Hopkins statistic.^[47] A typical one is as follows.^[48] Let

{displaystyle X}

be the set of

{displaystyle n}

data points in

{displaystyle d}

dimensional space. Consider a random sample (without replacement) of

{displaystyle mll n}

data points with members

{displaystyle x_{i}}

. Also generate a set

{displaystyle Y}

{displaystyle m}

uniformly randomly distributed data points. Now define two distance measures,

{displaystyle u_{i}}

to be the distance of

{displaystyle y_{i}in Y}

from its nearest neighbor in X and

{displaystyle w_{i}}

to be the distance of

{displaystyle x_{i}in X}

from its nearest neighbor in X. We then define the Hopkins statistic as:

{displaystyle H={frac {sum _{i=1}^{m}{u_{i}^{d}}}{sum _{i=1}^{m}{u_{i}^{d}}+sum _{i=1}^{m}{w_{i}^{d}}}},,}

With this definition, uniform random data should tend to have values near to 0.5, and clustered data should tend to have values nearer to 1.

However, data containing just a single Gaussian will also score close to 1, as this statistic measures deviation from a uniform distribution, not multimodality, making this statistic largely useless in application (as real data never is remotely uniform).

Applications[[[[edit]

Biology, computational biology and bioinformatics[[[[edit]

Plant and animal ecology: Cluster analysis is used to describe and to make spatial and temporal comparisons of communities (assemblages) of organisms in heterogeneous environments. It is also used in plant systematics to generate artificial phylogenies or clusters of organisms (individuals) at the species, genus or higher level that share a number of attributes.
Transcriptomics: Clustering is used to build groups of genes with related expression patterns (also known as coexpressed genes) as in HCS clustering algorithm.^[49]^[50] Often such groups contain functionally related proteins, such as enzymes for a specific pathway, or genes that are co-regulated. High throughput experiments using expressed sequence tags (ESTs) or DNA microarrays can be a powerful tool for genome annotation—a general aspect of genomics.
Sequence analysis: Sequence clustering is used to group homologous sequences into gene families.^[51] This is a very important concept in bioinformatics, and evolutionary biology in general. See evolution by gene duplication.
High-throughput genotyping platforms: Clustering algorithms are used to automatically assign genotypes.^[52]
Human genetic clustering: The similarity of genetic data is used in clustering to infer population structures.

Medicine[[[[edit]

Medical imaging: On PET scans, cluster analysis can be used to differentiate between different types of tissue in a three-dimensional image for many different purposes.^[53]
Analysis of antimicrobial activity: Cluster analysis can be used to analyse patterns of antibiotic resistance, to classify antimicrobial compounds according to their mechanism of action, to classify antibiotics according to their antibacterial activity.
IMRT segmentation: Clustering can be used to divide a fluence map into distinct regions for conversion into deliverable fields in MLC-based Radiation Therapy.

Business and marketing[[[[edit]

Market research: Cluster analysis is widely used in market research when working with multivariate data from surveys and test panels. Market researchers use cluster analysis to partition the general population of consumers into market segments and to better understand the relationships between different groups of consumers/potential customers, and for use in market segmentation, product positioning, new product development and selecting test markets.
Grouping of shopping items: Clustering can be used to group all the shopping items available on the web into a set of unique products. For example, all the items on eBay can be grouped into unique products (eBay does not have the concept of a SKU).

World wide web[[[[edit]

Social network analysis: In the study of social networks, clustering may be used to recognize communities within large groups of people.
Search result grouping: In the process of intelligent grouping of the files and websites, clustering may be used to create a more relevant set of search results compared to normal search engines like Google^{[[[[citation needed]}. There are currently a number of web-based clustering tools such as Clusty. It also may be used to return a more comprehensive set of results in cases where a search term could refer to vastly different things. Each distinct use of the term corresponds to a unique cluster of results, allowing a ranking algorithm to return comprehensive results by picking the top result from each cluster.^[54]
Slippy map optimization: Flickr’s map of photos and other map sites use clustering to reduce the number of markers on a map. This makes it both faster and reduces the amount of visual clutter.

Computer science[[[[edit]

Software evolution: Clustering is useful in software evolution as it helps to reduce legacy properties in code by reforming functionality that has become dispersed. It is a form of restructuring and hence is a way of direct preventative maintenance.
Image segmentation: Clustering can be used to divide a digital image into distinct regions for border detection or object recognition.^[55]
Evolutionary algorithms: Clustering may be used to identify different niches within the population of an evolutionary algorithm so that reproductive opportunity can be distributed more evenly amongst the evolving species or subspecies.
Recommender systems: Recommender systems are designed to recommend new items based on a user’s tastes. They sometimes use clustering algorithms to predict a user’s preferences based on the preferences of other users in the user’s cluster.
Markov chain Monte Carlo methods: Clustering is often utilized to locate and characterize extrema in the target distribution.
Anomaly detection: Anomalies/outliers are typically – be it explicitly or implicitly – defined with respect to clustering structure in data.
Natural language processing: Clustering can be used to resolve lexical ambiguity.^[54]

Social science[[[[edit]

Crime analysis: Cluster analysis can be used to identify areas where there are greater incidences of particular types of crime. By identifying these distinct areas or « hot spots » where a similar crime has happened over a period of time, it is possible to manage law enforcement resources more effectively.
Educational data mining: Cluster analysis is for example used to identify groups of schools or students with similar properties.
Typologies: From poll data, projects such as those undertaken by the Pew Research Center use cluster analysis to discern typologies of opinions, habits, and demographics that may be useful in politics and marketing.

Autres[[[[edit]

Field robotics: Clustering algorithms are used for robotic situational awareness to track objects and detect outliers in sensor data.^[56]

Mathematical chemistry: To find structural similarity, etc., for example, 3000 chemical compounds were clustered in the space of 90 topological indices.^[57]

Climatology: To find weather regimes or preferred sea level pressure atmospheric patterns.^[58]

La finance: Cluster analysis has been used to cluster stocks into sectors.^[59]

Petroleum geology: Cluster analysis is used to reconstruct missing bottom hole core data or missing log curves in order to evaluate reservoir properties.

Geochemistry: The clustering of chemical properties in different sample locations.

References[[[[edit]

^ Driver and Kroeber (1932). « Quantitative Expression of Cultural Relationships ». University of California Publications in American Archaeology and Ethnology. Quantitative Expression of Cultural Relationships: 211–256 – via http://dpg.lib.berkeley.edu.
^ Zubin, Joseph (1938). « A technique for measuring like-mindedness ». The Journal of Abnormal and Social Psychology. 33 (4): 508–516. doi:10.1037/h0055441. ISSN 0096-851X.
^ Tryon, Robert C. (1939). Cluster Analysis: Correlation Profile and Orthometric (factor) Analysis for the Isolation of Unities in Mind and Personality. Edwards Brothers.
^ Cattell, R. B. (1943). « The description of personality: Basic traits resolved into clusters ». Journal of Abnormal and Social Psychology. 38 (4): 476–506. doi:10.1037/h0054116.
^ ^une ^b ^c ^d ^e ^f Estivill-Castro, Vladimir (20 June 2002). « Why so many clustering algorithms – A Position Paper ». ACM SIGKDD Explorations Newsletter. 4 (1): 65–75. doi:10.1145/568574.568575. S2CID 7329935.
^ James A. Davis (May 1967) « Clustering and structural balance in graphs », Human Relations 20:181–7
^ Everitt, Brian (2011). Cluster analysis. Chichester, West Sussex, U.K: Wiley. ISBN 9780470749913.
^ Sibson, R. (1973). « SLINK: an optimally efficient algorithm for the single-link cluster method » (PDF). The Computer Journal. British Computer Society. 16 (1): 30–34. doi:10.1093/comjnl/16.1.30.
^ Defays, D. (1977). « An efficient algorithm for a complete link method ». The Computer Journal. British Computer Society. 20 (4): 364–366. doi:10.1093/comjnl/20.4.364.
^ Lloyd, S. (1982). « Least squares quantization in PCM ». IEEE Transactions on Information Theory. 28 (2): 129–137. doi:10.1109/TIT.1982.1056489.
^ Kriegel, Hans-Peter; Kröger, Peer; Sander, Jörg; Zimek, Arthur (2011). « Density-based Clustering ». WIREs Data Mining and Knowledge Discovery. 1 (3): 231–240. doi:10.1002/widm.30. S2CID 36920706.
^ Microsoft academic search: most cited data mining articles Archived 2010-04-21 at the Wayback Machine: DBSCAN is on rank 24, when accessed on: 4/18/2010
^ Ester, Martin; Kriegel, Hans-Peter; Sander, Jörg; Xu, Xiaowei (1996). « A density-based algorithm for discovering clusters in large spatial databases with noise ». In Simoudis, Evangelos; Han, Jiawei; Fayyad, Usama M. (eds.). Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96). AAAI Press. pp. 226–231. ISBN 1-57735-004-9.
^ Ankerst, Mihael; Breunig, Markus M.; Kriegel, Hans-Peter; Sander, Jörg (1999). « OPTICS: Ordering Points To Identify the Clustering Structure ». ACM SIGMOD international conference on Management of data. ACM Press. pp. 49–60. CiteSeerX 10.1.1.129.6542.
^ ^une ^b Achtert, E.; Böhm, C.; Kröger, P. (2006). « DeLi-Clu: Boosting Robustness, Completeness, Usability, and Efficiency of Hierarchical Clustering by a Closest Pair Ranking ». Advances in Knowledge Discovery and Data Mining. Lecture Notes in Computer Science. 3918. pp. 119–128. CiteSeerX 10.1.1.64.1161. doi:10.1007/11731139_16. ISBN 978-3-540-33206-0.
^ Aggarwal, Charu C., editor. Reddy, Chandan K., editor. Data Clustering : Algorithms and Applications. ISBN 978-1-315-37351-5. OCLC 1110589522.CS1 maint: multiple names: authors list (link)
^ Sculley, D. (2010). Web-scale k-means clustering. Proc. 19th WWW.
^ Huang, Z. (1998). « Extensions to the k-means algorithm for clustering large data sets with categorical values ». Data Mining and Knowledge Discovery. 2 (3): 283–304. doi:10.1023/A:1009769707641. S2CID 11323096.
^ R. Ng and J. Han. « Efficient and effective clustering method for spatial data mining ». In: Proceedings of the 20th VLDB Conference, pages 144–155, Santiago, Chile, 1994.
^ Tian Zhang, Raghu Ramakrishnan, Miron Livny. « An Efficient Data Clustering Method for Very Large Databases. » In: Proc. Int’l Conf. on Management of Data, ACM SIGMOD, pp. 103–114.
^ Kriegel, Hans-Peter; Kröger, Peer; Zimek, Arthur (July 2012). « Subspace clustering ». Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery. 2 (4): 351–364. doi:10.1002/widm.1057. S2CID 7241355.
^ Agrawal, R.; Gehrke, J.; Gunopulos, D.; Raghavan, P. (2005). « Automatic Subspace Clustering of High Dimensional Data ». Data Mining and Knowledge Discovery. 11: 5–33. CiteSeerX 10.1.1.131.5152. doi:10.1007/s10618-005-1396-1. S2CID 9289572.
^ Karin Kailing, Hans-Peter Kriegel and Peer Kröger. Density-Connected Subspace Clustering for High-Dimensional Data. In: Proc. SIAM Int. Conf. on Data Mining (SDM’04), pp. 246–257, 2004.
^ Achtert, E.; Böhm, C.; Kriegel, H.-P.; Kröger, P.; Müller-Gorman, I.; Zimek, A. (2006). « Finding Hierarchies of Subspace Clusters ». Knowledge Discovery in Databases: PKDD 2006. Lecture Notes in Computer Science. 4213. pp. 446–453. CiteSeerX 10.1.1.705.2956. doi:10.1007/11871637_42. ISBN 978-3-540-45374-1.
^ Achtert, E.; Böhm, C.; Kriegel, H. P.; Kröger, P.; Müller-Gorman, I.; Zimek, A. (2007). « Detection and Visualization of Subspace Cluster Hierarchies ». Advances in Databases: Concepts, Systems and Applications. Lecture Notes in Computer Science. 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.
^ Achtert, E.; Böhm, C.; Kröger, P.; Zimek, A. (2006). « Mining Hierarchies of Correlation Clusters ». Proc. 18th International Conference on Scientific and Statistical Database Management (SSDBM): 119–128. CiteSeerX 10.1.1.707.7872. doi:10.1109/SSDBM.2006.35. ISBN 978-0-7695-2590-7. S2CID 2679909.
^ Böhm, C.; Kailing, K.; Kröger, P.; Zimek, A. (2004). « Computing Clusters of Correlation Connected objects ». Proceedings of the 2004 ACM SIGMOD international conference on Management of data – SIGMOD ’04. p. 455. CiteSeerX 10.1.1.5.1279. doi:10.1145/1007568.1007620. ISBN 978-1581138597. S2CID 6411037.
^ Achtert, E.; Bohm, C.; Kriegel, H. P.; Kröger, P.; Zimek, A. (2007). « On Exploring Complex Relationships of Correlation Clusters ». 19th International Conference on Scientific and Statistical Database Management (SSDBM 2007). p. 7. CiteSeerX 10.1.1.71.5021. doi:10.1109/SSDBM.2007.21. ISBN 978-0-7695-2868-7. S2CID 1554722.
^ Meilă, Marina (2003). « Comparing Clusterings by the Variation of Information ». Learning Theory and Kernel Machines. Lecture Notes in Computer Science. 2777. pp. 173–187. doi:10.1007/978-3-540-45167-9_14. ISBN 978-3-540-40720-1.
^ Kraskov, Alexander; Stögbauer, Harald; Andrzejak, Ralph G.; Grassberger, Peter (1 December 2003). « Hierarchical Clustering Based on Mutual Information ». arXiv:q-bio/0311039. Bibcode:2003q.bio….11039K.
^ Auffarth, B. (July 18–23, 2010). « Clustering by a Genetic Algorithm with Biased Mutation Operator ». Wcci Cec. IEEE.
^ Frey, B. J.; Dueck, D. (2007). « Clustering by Passing Messages Between Data Points ». La science. 315 (5814): 972–976. Bibcode:2007Sci…315..972F. CiteSeerX 10.1.1.121.3145. doi:10.1126/science.1136800. PMID 17218491. S2CID 6502291.
^ ^une ^b ^c ^d Pfitzner, Darius; Leibbrandt, Richard; Powers, David (2009). « Characterization and evaluation of similarity measures for pairs of clusterings ». Knowledge and Information Systems. Springer. 19 (3): 361–394. doi:10.1007/s10115-008-0150-6. S2CID 6935380.
^ ^une ^b ^c Feldman, Ronen; Sanger, James (2007-01-01). The Text Mining Handbook: Advanced Approaches in Analyzing Unstructured Data. Cambridge Univ. Press. ISBN 978-0521836579. OCLC 915286380.
^ ^une ^b Weiss, Sholom M.; Indurkhya, Nitin; Zhang, Tong; Damerau, Fred J. (2005). Text Mining: Predictive Methods for Analyzing Unstructured Information. Springer. ISBN 978-0387954332. OCLC 803401334.
^ ^une ^b ^c Manning, Christopher D.; Raghavan, Prabhakar; Schütze, Hinrich (2008-07-07). Introduction to Information Retrieval. Cambridge University Press. ISBN 978-0-521-86571-5.
^ ^une ^b Knowledge Discovery in Databases – Part III – Clustering (PDF), Heidelberg University, 2017
^ Dunn, J. (1974). « Well separated clusters and optimal fuzzy partitions ». Journal of Cybernetics. 4: 95–104. doi:10.1080/01969727408546059.
^ ^une ^b Färber, Ines; Günnemann, Stephan; Kriegel, Hans-Peter; Kröger, Peer; Müller, Emmanuel; Schubert, Erich; Seidl, Thomas; Zimek, Arthur (2010). « On Using Class-Labels in Evaluation of Clusterings » (PDF). In Fern, Xiaoli Z.; Davidson, Ian; Dy, Jennifer (eds.). MultiClust: Discovering, Summarizing, and Using Multiple Clusterings. ACM SIGKDD.
^ Pourrajabi, M.; Moulavi, D.; Campello, R. J. G. B.; Zimek, A.; Sander, J.; Goebel, R. (2014). « Model Selection for Semi-Supervised Clustering ». Proceedings of the 17th International Conference on Extending Database Technology (EDBT). pp. 331–342. doi:10.5441/002/edbt.2014.31.
^ Rand, W. M. (1971). « Objective criteria for the evaluation of clustering methods ». Journal of the American Statistical Association. American Statistical Association. 66 (336): 846–850. arXiv:1704.01036. doi:10.2307/2284239. JSTOR 2284239.
^ Fowlkes, E. B.; Mallows, C. L. (1983). « A Method for Comparing Two Hierarchical Clusterings ». Journal of the American Statistical Association. 78 (383): 553–569. doi:10.1080/01621459.1983.10478008. JSTOR 2288117.
^ Powers, David (2003). Recall and Precision versus the Bookmaker. International Conference on Cognitive Science. pp. 529–534.
^ Arabie, P. (1985). « Comparing partitions ». Journal of Classification. 2 (1): 1985. doi:10.1007/BF01908075. S2CID 189915041.
^ Wallace, D. L. (1983). « Comment ». Journal of the American Statistical Association. 78 (383): 569–579. doi:10.1080/01621459.1983.10478009.
^ Powers, David (2012). The Problem with Kappa. European Chapter of the Association for Computational Linguistics. pp. 345–355.
^ Hopkins, Brian; Skellam, John Gordon (1954). « A new method for determining the type of distribution of plant individuals ». Annals of Botany. Annals Botany Co. 18 (2): 213–227. doi:10.1093/oxfordjournals.aob.a083391.
^ Banerjee, A. (2004). « Validating clusters using the Hopkins statistic ». IEEE International Conference on Fuzzy Systems. 1: 149–153. doi:10.1109/FUZZY.2004.1375706. ISBN 978-0-7803-8353-1. S2CID 36701919.
^ Johnson, Stephen C. (1967-09-01). « Hierarchical clustering schemes ». Psychometrika. 32 (3): 241–254. doi:10.1007/BF02289588. ISSN 1860-0980. PMID 5234703. S2CID 930698.
^ Hartuv, Erez; Shamir, Ron (2000-12-31). « A clustering algorithm based on graph connectivity ». Information Processing Letters. 76 (4): 175–181. doi:10.1016/S0020-0190(00)00142-3. ISSN 0020-0190.
^ Remm, Maido; Storm, Christian E. V.; Sonnhammer, Erik L. L. (2001-12-14). « Automatic clustering of orthologs and in-paralogs from pairwise species comparisons11Edited by F. Cohen ». Journal of Molecular Biology. 314 (5): 1041–1052. doi:10.1006/jmbi.2000.5197. ISSN 0022-2836. PMID 11743721.
^ Botstein, David; Cox, David R.; Risch, Neil; Olshen, Richard; Curb, David; Dzau, Victor J.; Chen, Yii-Der I.; Hebert, Joan; Pesich, Robert (2001-07-01). « High-Throughput Genotyping with Single Nucleotide Polymorphisms ». Genome Research. 11 (7): 1262–1268. doi:10.1101/gr.157801 (inactive 2021-01-17). ISSN 1088-9051. PMC 311112. PMID 11435409.CS1 maint: DOI inactive as of January 2021 (link)
^ Filipovych, Roman; Resnick, Susan M.; Davatzikos, Christos (2011). « Semi-supervised Cluster Analysis of Imaging Data ». NeuroImage. 54 (3): 2185–2197. doi:10.1016/j.neuroimage.2010.09.074. PMC 3008313. PMID 20933091.
^ ^une ^b Di Marco, Antonio; Navigli, Roberto (2013). « Clustering and Diversifying Web Search Results with Graph-Based Word Sense Induction ». Computational Linguistics. 39 (3): 709–754. doi:10.1162/COLI_a_00148. S2CID 1775181.
^ Bewley, A., & Upcroft, B. (2013). Advantages of Exploiting Projection Structure for Segmenting Dense 3D Point Clouds. In Australian Conference on Robotics and Automation [1]
^ Bewley, A.; et al. « Real-time volume estimation of a dragline payload ». IEEE International Conference on Robotics and Automation. 2011: 1571–1576.
^ Basak, S.C.; Magnuson, V.R.; Niemi, C.J.; Regal, R.R. (1988). « Determining Structural Similarity of Chemicals Using Graph Theoretic Indices ». Discr. Appl. Math. 19 (1–3): 17–44. doi:10.1016/0166-218x(88)90004-2.
^ Huth, R.; et al. (2008). « Classifications of Atmospheric Circulation Patterns: Recent Advances and Applications ». Ann. N.Y. Acad. Sci. 1146: 105–152. Bibcode:2008NYASA1146..105H. doi:10.1196/annals.1446.019. PMID 19076414. S2CID 22655306.
^ Arnott, Robert D. (1980-11-01). « Cluster Analysis and Stock Price Comovement ». Financial Analysts Journal. 36 (6): 56–62. doi:10.2469/faj.v36.n6.56. ISSN 0015-198X.

Source de l’article

Post Views: 2 048