Choisir la bonne méthode de liaison pour le clustering hiérarchique

Je joue la classification hiérarchique des données que j'ai recueillies et traitées de la décharge de données reddit sur Google BigQuery.

Mon processus est le suivant:

• Recevez les 1000 derniers articles dans / r / politique
• Rassemblez tous les commentaires
• Traiter les données et calculer une n x mmatrice de données (n: utilisateurs / échantillons, m: publications / fonctionnalités)
• Calculer la matrice de distance pour le clustering hiérarchique
• Choisissez une méthode de liaison et effectuez le clustering hiérarchique
• Tracer les données sous forme de dendrogramme

Ma question est, comment puis-je déterminer quelle est la meilleure méthode de liaison ? J'utilise actuellement , Wardmais comment puis-je savoir si je devrais utiliser single, complete, average, etc?

Je suis très nouveau dans ce domaine mais je ne trouve pas de réponse claire en ligne car je ne suis pas sûr qu'il y en ait une. Alors, quelle pourrait être une bonne idée pour mon application? Notez que les données sont relativement clairsemées dans le sens où la n x mmatrice a beaucoup de zéros (la plupart des gens ne commentent pas plus de quelques articles).

Présentation des méthodes

Brève référence à certaines méthodes de liaison de l' analyse d' agrégations d'agglomérations hiérarchiques (HAC).

La version de base de l'algorithme HAC est un générique; cela revient à mettre à jour, à chaque étape, par la formule dite formule de Lance-Williams, les proximités entre le cluster émergent (fusionné de deux) et tous les autres clusters (y compris les objets singleton) existant jusqu'à présent. Il existe des implémentations n'utilisant pas la formule de Lance-Williams. Mais son utilisation est pratique: elle permet de coder différentes méthodes de liaison par le même modèle.

La formule de récurrence comprend plusieurs paramètres (alpha, bêta, gamma). Selon la méthode de liaison, les paramètres sont définis différemment et la formule non enveloppée obtient donc une vue spécifique. De nombreux textes sur HAC montrent la formule, ses vues spécifiques à la méthode et expliquent les méthodes. Je recommanderais les articles de Janos Podani comme très approfondis.

La place et la nécessité des différentes méthodes découlent du fait qu'une proximité (distance ou similitude) entre deux grappes ou entre une grappe et un objet singleton peut être formulée de différentes manières. HAC fusionne à chaque étape les deux clusters ou points les plus proches, mais comment calculer la proximité susmentionnée face à la définition de la matrice de proximité d'entrée entre les objets singleton uniquement, est le problème à formuler.

Ainsi, les méthodes diffèrent en ce qui concerne la façon dont elles définissent la proximité entre deux clusters quelconques à chaque étape. Le "coefficient de colligation" (sortie dans le calendrier / historique d'agglomération et formant l'axe "Y" sur un dendrogramme) n'est que la proximité entre les deux grappes fusionnées à une étape donnée.

• Méthode de liaison simple ou voisin le plus proche . La proximité entre deux clusters est la proximité entre leurs deux objets les plus proches. Cette valeur est l'une des valeurs de la matrice d'entrée. La métaphore conceptuelle de cet amas construit, son archétype, est spectre ou chaîne . Les chaînes peuvent être droites ou curvilignes, ou ressembler à une vue "flocon de neige" ou "amibe". Il se peut que deux membres de grappe les plus différents soient très différents par rapport aux deux plus similaires. La méthode de liaison simple contrôle uniquement la similitude des voisins les plus proches.

• Méthode de liaison complète ou voisin le plus éloigné . La proximité entre deux clusters est la proximité entre leurs deux objets les plus éloignés. Cette valeur est l'une des valeurs de la matrice d'entrée. La métaphore de cette grappe construite est cercle (dans le sens, par passe-temps ou intrigue) où deux membres les plus éloignés l'un de l'autre ne peuvent pas être beaucoup plus dissemblables que d'autres paires assez dissemblables (comme dans le cercle). De tels clusters sont des contours "compacts" par leurs bordures, mais ils ne sont pas nécessairement compacts à l'intérieur.

• Méthode de liaison moyenne entre groupes (UPGMA). La proximité entre deux grappes est la moyenne arithmétique de toutes les proximités entre les objets de l'un, d'un côté, et les objets de l'autre, de l'autre. La métaphore de ce cluster construit est assez générique, juste unie classe ou du collectif ; et la méthode est souvent définie par défaut dans les packages de clustering hiérarchiques. Des grappes de formes et de contours divers peuvent être produites.

• La moyenne simple , ou méthode de liaison moyenne entre groupes équilibrée (WPGMA) est la précédente modifiée. La proximité entre deux grappes est la moyenne arithmétique de toutes les proximités entre les objets de l'un, d'un côté, et les objets de l'autre, de l'autre côté; tandis que les sous-grappes dont chacun de ces deux grappes a été fusionné récemment ont une influence égalisée sur cette proximité - même si les sous-grappes différaient par le nombre d'objets.

• Méthode de couplage moyen intra-groupe (MNDIS). La proximité entre deux grappes est la moyenne arithmétique de toutes les proximités de leur grappe articulaire. Cette méthode est une alternative à UPGMA. Il y perdra généralement en termes de densité de grappe, mais découvrira parfois des formes de grappe que l'UPGMA ne verra pas.

• Méthode centroïde (UPGMC). La proximité entre deux grappes est la proximité entre leurs centroïdes géométriques: distance euclidienne [au carré] entre ceux-ci. La métaphore de ce cluster construit est la proximité des plateformes (politique). Comme dans les partis politiques, ces grappes peuvent avoir des fractions ou des «factions», mais à moins que leurs figures centrales ne soient distinctes, l'union est cohérente. Les grappes peuvent être diverses par leur contour.

• La méthode médiane ou centroïde équilibrée (WPGMC) est la précédente modifiée. La proximité entre deux grappes est la proximité entre leurs centroïdes géométriques (distance euclidienne [au carré] entre ceux-ci); tandis que les centroïdes sont définis de telle sorte que les sous-grappes dont chacun de ces deux grappes a été fusionné récemment ont une influence égalisée sur son centroïde - même si les sous-grappes diffèrent dans le nombre d'objets.

• $SS_{12}-(SS_1+SS_2)$$2$. Intuitivement, un type est un nuage plus dense et plus concentrique vers son milieu, tandis que les points marginaux sont peu nombreux et pourraient être dispersés relativement librement.

Certaines parmi les méthodes moins connues (voir Podany J. Nouvelles méthodes de regroupement combinatoire // Vegetatio, 1989, 81: 61-77.) [Également implémenté par moi comme une macro SPSS trouvée sur ma page Web]:

• $SS_{12}$$2$

• $MS_{12}-(n_1MS_1+n_2MS_2)/(n_1+n_2) = [SS_{12}-(SS_1+SS_2)]/(n_1+n_2)$$4$

• $MS_{12} = SS_{12}/(n_1+n_2)$$4$

Les 5 premières méthodes permettent toutes les mesures de proximité (similitudes ou distances) et les résultats dépendront naturellement de la mesure choisie.

Les 6 dernières méthodes nécessitent des distances; et tout à fait correct sera d'utiliser uniquement des distances euclidiennes au carré avec eux, car ces méthodes calculent les centroïdes dans l'espace euclidien. Par conséquent, les distances doivent être euclidiennes dans un souci d'exactitude géométrique (ces 6 méthodes sont appelées ensemble méthodes de liaison géométrique ). Dans le pire des cas, vous pouvez entrer une autre métriquedistances à admettre une analyse plus heuristique, moins rigoureuse. Maintenant à propos de ce "carré". Le calcul des centroïdes et des écarts par rapport à ceux-ci est le plus pratique mathématiquement / par programmation pour effectuer sur des distances au carré, c'est pourquoi les packages HAC nécessitent généralement une entrée et sont réglés pour traiter ceux au carré. Cependant, il existe des implémentations - entièrement équivalentes mais un peu plus lentes - basées sur l'entrée de distances non carrées et nécessitant celles-ci; voir par exemple l' implémentation de "Ward-2" pour la méthode de Ward. Vous devriez consulter la documentation de votre programme de clustering pour savoir quelles - au carré ou non - distances il attend en entrée d'une "méthode géométrique" afin de bien faire les choses.

Les méthodes MNDIS, MNSSQ et MNVAR nécessitent des étapes, en plus de simplement mettre à jour la formule de Lance-Williams, pour stocker une statistique intra-cluster (qui dépend de la méthode).

Les méthodes les plus fréquemment utilisées dans les études où les grappes devraient être des nuages ​​solides plus ou moins ronds, sont les méthodes de liaison moyenne, la méthode de liaison complète et la méthode de Ward.

La méthode de Ward est la plus proche, par ses propriétés et son efficacité, du clustering K-means; ils partagent la même fonction objective - minimiser les SS regroupés au sein du cluster "à la fin". Bien sûr, K-means (étant itératif et s'il est pourvu de centroïdes initiaux décents) est généralement un meilleur minimiseur de celui-ci que Ward. Cependant, Ward me semble un peu plus précis que K-means pour découvrir des grappes de tailles physiques inégales (variances) ou des grappes projetées dans l'espace de manière très irrégulière. La méthode MIVAR est bizarre pour moi, je ne peux pas imaginer quand elle pourrait être recommandée, elle ne produit pas de grappes suffisamment denses.

Méthodes centroïdes, médiane, augmentation minimale de la variance - peuvent parfois donner les soi-disant inversions : un phénomène lorsque les deux grappes fusionnées à un certain stade apparaissent plus proches l'une de l'autre que les paires de grappes fusionnées plus tôt. En effet, ces méthodes n'appartiennent pas au soi-disant ultramétrique. Cette situation n'est pas pratique mais est théoriquement OK.

Les méthodes de liaison simple et de centroïde appartiennent à ce que l'on appelle la contraction de l' espace , ou «chaînage». Cela signifie - grosso modo - qu'ils ont tendance à attacher les objets un par un aux grappes, et qu'ils démontrent donc une croissance relativement régulière de la courbe «% d'objets groupés». Au contraire, les méthodes de couplage complet, de Ward, de somme des carrés, d'augmentation de la variance et de la variance obtiennent généralement une part considérable d'objets regroupés même aux premières étapes, puis procèdent à la fusion de ceux-ci - donc leur courbe «% des objets groupés »Est raide dès les premiers pas. Ces méthodes sont appelées dilatation de l' espace . D'autres méthodes se situent entre les deux.

Versions flexibles . En ajoutant le paramètre supplémentaire dans la formule Lance-Willians, il est possible de faire en sorte qu'une méthode s'auto-ajuste spécifiquement sur ses étapes. Le paramètre apporte une correction pour la proximité entre les clusters calculée, qui dépend de la taille (quantité de décompactité) des clusters. La signification du paramètre est qu'il rend la méthode d'agglomération plus dilatante ou plus compacte que la méthode standard est vouée à l'être. La mise en œuvre la plus connue de la flexibilité à ce jour est la moyenne des méthodes de liaison UPGMA et WPGMA (Belbin, L. et al. A Comparison of Two Approaches to Beta-Flexible Clustering // Multivariate Behavioral Research, 1992, 27, 417–433. ).

Dendrogramme. Sur un dendrogramme «Y», la distance entre les clusters fusionnés est généralement affichée, comme défini par les méthodes ci-dessus. Par conséquent, par exemple, dans la méthode centroïde, la distance au carré est généralement mesurée (en fin de compte, cela dépend du package et des options) - certaines recherches ne le savent pas. De plus, selon la tradition, avec des méthodes basées sur l' augmentation de la non-densité, telles que celles de Ward, généralement indiquées sur le dendrogramme, la valeur cumulative est plus rapide pour des raisons de commodité que pour des raisons théoriques. Ainsi, (dans de nombreux packages), le coefficient tracé dans la méthode de Ward représente la somme globale, à travers tous les clusters, des carrés au sein du cluster observés au moment d'une étape donnée.

Il faut s'abstenir de juger quelle méthode de couplage est "meilleure" pour ses données en comparant l'apparence des dendrogrammes: non seulement parce que l'apparence change lorsque vous changez la modification du coefficient que vous y tracez - comme cela vient d'être décrit, - mais parce que l'apparence sera différente même sur les données sans clusters.

Choisir la "bonne" méthode

Il n'y a pas de critère unique . Certaines lignes directrices sur la façon de sélectionner une méthode d'analyse de cluster (y compris une méthode de liaison dans HAC en tant que cas particulier) sont décrites dans cette réponse et tout le fil conducteur.

La corrélation entre la matrice de distance et la distance cophénétique est une métrique pour aider à évaluer la liaison de clustering à sélectionner. De ?cophenetic:

On peut faire valoir qu'un dendrogramme est un résumé approprié de certaines données si la corrélation entre les distances d'origine et les distances cophénétiques est élevée.

Cette utilisation de cor(dist,cophenetic(hclust(dist)))métrique de sélection de liaison est référencée à la page 38 de cette vegan vignette .

Voir l'exemple de code ci-dessous:

# Data
d0=dist(USArrests)

# Hierarchical Agglomerative Clustering
h1=hclust(d0,method='average')
h2=hclust(d0,method='complete')
h3=hclust(d0,method='ward.D')
h4=hclust(d0,method='single')

# Cophenetic Distances, for each linkage
c1=cophenetic(h1)
c2=cophenetic(h2)
c3=cophenetic(h3)
c4=cophenetic(h4)

# Correlations
cor(d0,c1) # 0.7658983
cor(d0,c2) # 0.7636926
cor(d0,c3) # 0.7553367
cor(d0,c4) # 0.5702505

# Dendograms
par(mfrow=c(2,2))
plot(h1,main='Average Linkage')
plot(h2,main='Complete Linkage')
plot(h3,main='Ward Linkage')
plot(h4,main='Single Linkage')
par(mfrow=c(1,1))

Nous voyons que les corrélations pour averageet completesont extrêmement similaires, et leurs dendogrammes semblent très similaires. La corrélation pour wardest similaire à averageetcomplete mais le dendogramme semble assez différent. singlele lien fait sa propre chose. Le meilleur jugement professionnel d'un expert en la matière, ou la préséance envers un certain lien dans le domaine d'intérêt devrait probablement remplacer la sortie numérique de cor().