En mineria de dades i estadística, l'agrupació jeràrquica (també anomenada anàlisi de clústers jeràrquics o HCA) és un mètode d'anàlisi de clústers que busca construir una jerarquia de clústers. Les estratègies per a l'agrupació jeràrquica generalment es divideixen en dues categories:
Aglomeratiu: L'agrupació aglomerativa, sovint anomenada enfocament "de baix a dalt", comença amb cada punt de dades com un clúster individual. A cada pas, l'algoritme fusiona els dos clústers més similars basant-se en una mètrica de distància escollida (per exemple, distància euclidiana) i un criteri d'enllaç (per exemple, enllaç únic, enllaç complet). Aquest procés continua fins que tots els punts de dades es combinen en un sol clúster o es compleix un criteri d'aturada. Els mètodes aglomeratius s'utilitzen més habitualment per la seva simplicitat i eficiència computacional per a conjunts de dades petits o mitjans. Divisiu: L'agrupació divisiva, coneguda com a enfocament "de dalt a baix", comença amb tots els punts de dades d'un sol clúster i divideix recursivament el clúster en altres de més petits. A cada pas, l'algoritme selecciona un clúster i el divideix en dos o més subconjunts, sovint utilitzant un criteri com ara maximitzar la distància entre els clústers resultants. Els mètodes divisius són menys comuns però poden ser útils quan l'objectiu és identificar primer clústers grans i diferents.
En general, les fusions i les divisions es determinen de manera voraç. Els resultats de l'agrupació jeràrquica se solen presentar en un dendrograma.
L'agrupació jeràrquica té l'avantatge que es pot utilitzar qualsevol mesura vàlida de distància. De fet, les observacions en si no són necessàries: tot el que s'utilitza és una matriu de distàncies. D'altra banda, excepte en el cas especial de la distància d'enllaç únic, cap dels algoritmes (excepte la cerca exhaustiva a ) es pot garantir que es trobi la solució òptima.
L'agrupació jeràrquica té l'avantatge que es pot utilitzar qualsevol mesura vàlida de distància. De fet, les observacions en si no són necessàries: tot el que s'utilitza és una matriu de distàncies. D'altra banda, excepte en el cas especial de la distància d'enllaç únic, cap dels algoritmes (excepte la cerca exhaustiva a ) es pot garantir que es trobi la solució òptima.
Complexitat L'algoritme estàndard per a l'agrupació aglomerativa jeràrquica (HAC) té una complexitat temporal de i requereix memòria, cosa que la fa massa lenta fins i tot per a conjunts de dades mitjans. Tanmateix, per a alguns casos especials, els mètodes aglomeratius òptims i eficients (de complexitat ) són coneguts: SLINK per a enllaços simples i CLINK per a clústers d'enllaços complets. Amb un heap, el temps d'execució del cas general es pot reduir a , una millora respecte al límit esmentat anteriorment de , a costa d'augmentar encara més els requisits de memòria. En molts casos, les despeses generals de memòria d'aquest enfocament són massa grans per fer-lo pràcticament utilitzable. Existeixen mètodes que utilitzen quadtrees que demostren temps total de funcionament amb espai.
L'agrupació divisiva amb una cerca exhaustiva és , però és comú utilitzar heurístiques més ràpides per triar divisions, com ara k -mitjanes.
Enllaç de clústers Per decidir quins clústers s'han de combinar (per a aglomeració) o on s'ha de dividir un clúster (per a divisió), es requereix una mesura de dissimilitat entre conjunts d'observacions. En la majoria de mètodes d'agrupació jeràrquica, això s'aconsegueix mitjançant l'ús d'una distància adequada d, com ara la distància euclidiana, entre observacions individuals del conjunt de dades, i un criteri d'enllaç, que especifica la dissimilitat dels conjunts com a funció de les distàncies per parells d'observacions dels conjunts. L'elecció de la mètrica, així com l'enllaç, pot tenir un impacte important en el resultat de l'agrupació, on la mètrica de nivell inferior determina quins objectes són més similars, mentre que el criteri d'enllaç influeix en la forma dels clústers. Per exemple, l'enllaç complet tendeix a produir més clústers esfèrics que l'enllaç únic.
El criteri d'enllaç determina la distància entre conjunts d'observacions en funció de les distàncies per parells entre observacions
Alguns criteris d'enllaç que s'utilitzen habitualment entre dos conjunts d'observacions A i B i una distància d són: NamesFormulaAgrupació d'enllaços màxims o completsAgrupació d'enllaços mínims o únicsAgrupació d'enllaços amb mitjana no ponderada (o UPGMA)Agrupació d'enllaços amb mitjana ponderada (o WPGMA)Agrupació d'enllaços centroides, o UPGMC on i són els centroides de A resp. B.Agrupació d'enllaços mitjans, o WPGMC on Agrupació d'enllaços versàtilsEnllaç de Ward , Increment mínim de la suma de quadrats (MISSQ)Suma mínima d'errors de quadrats (MNSSQ)Increment mínim de la variància (MIVAR)Variància mínima (MNVAR)Enllaç de HausdorffEnllaç Medoid de Suma Mínima de manera que m és el medoide del clúster resultantEnllaç Medoide de suma mínimaEnllaç Medoide on , són els mètodes d'agrupacions prèviesAgrupació d'energia mínima Alguns d'aquests només es poden recalcular recursivament (WPGMA, WPGMC), per a molts un càlcul recursiu amb equacions de Lance-Williams és més eficient, mentre que per a altres (Hausdorff, Medoid) les distàncies s'han de calcular amb la fórmula completa més lenta. Altres criteris d'enllaç inclouen:
La probabilitat que els clústers candidats provinguin de la mateixa funció de distribució (enllaç V). El producte del grau d'entrada i del grau de sortida en un gràfic de k veïns més propers (enllaç de graus del gràfic). L'increment d'algun descriptor de clúster (és a dir, una quantitat definida per mesurar la qualitat d'un clúster) després de fusionar dos clústers.
Exemple d'agrupació aglomerativa marc|Dades en brut Per exemple, suposem que aquestes dades s'han d'agrupar i la distància euclidiana és la mètrica de distància.
El dendrograma de clúster jeràrquic seria: marc|Representació tradicional Tallar l'arbre a una alçada determinada donarà una agrupació de particions amb una precisió seleccionada. En aquest exemple, tallar després de la segona fila (des de dalt) del dendrograma produirà clústers {a} {bc} {de} {f}. Tallar després de la tercera fila produirà clústers {a} {bc} {def}, que és una agrupació més gruixuda, amb un nombre més petit però clústers més grans.
Aquest mètode construeix la jerarquia a partir dels elements individuals fusionant progressivament els clústers. En el nostre exemple, tenim sis elements {a} {b} {c} {d} {e} i {f}. El primer pas és determinar quins elements fusionar en un clúster. Normalment, volem agafar els dos elements més propers, segons la distància escollida.
Opcionalment, també es pot construir una matriu de distàncies en aquesta etapa, on el nombre de la fila i -èsima i la columna j -èsima és la distància entre els elements i-èsim i j-èsim. Aleshores, a mesura que avança l'agrupació, les files i les columnes es fusionen a mesura que es fusionen els clústers i s'actualitzen les distàncies. Aquesta és una manera habitual d'implementar aquest tipus d'agrupació i té l'avantatge d'emmagatzemar a la memòria cau les distàncies entre els clústers. A la pàgina d'agrupació d'enllaç únic es descriu un algoritme d'aglomeració simple; es pot adaptar fàcilment a diferents tipus d'enllaç (vegeu més avall).
Suposem que hem fusionat els dos elements més propers b i c, ara tenim els següents clústers { a }, { b, c }, { d }, { e } i { f }, i volem fusionar-los encara més. Per fer-ho, hem de prendre la distància entre {a} i {bc}, i per tant definir la distància entre dos clústers. Normalment, la distància entre dos clústers i és un dels següents:
La distància màxima entre els elements de cada clúster (també anomenada agrupació d'enllaç complet):
La distància mínima entre els elements de cada clúster (també anomenada agrupació d'enllaç únic):
La distància mitjana entre els elements de cada clúster (també anomenada agrupació d'enllaços mitjana, utilitzada per exemple a UPGMA):
La suma de totes les variàncies intraclúster. L'augment de la variància per al clúster que es fusiona (mètode de Ward) La probabilitat que els clústers candidats provinguin de la mateixa funció de distribució (enllaç V).
En cas de distàncies mínimes lligades, es tria un parell aleatòriament, cosa que permet generar diversos dendrogrames estructuralment diferents. Alternativament, tots els parells lligats es poden unir alhora, generant un dendrograma únic.
Sempre es pot decidir aturar l'agrupació quan hi ha un nombre prou petit de clústers (criteri de nombre). Alguns enllaços també poden garantir que l'aglomeració es produeixi a una distància més gran entre els clústers que l'aglomeració anterior, i llavors es pot aturar l'agrupació quan els clústers estan massa separats per ser fusionats (criteri de distància). Tanmateix, aquest no és el cas, per exemple, de l'enllaç del centroide on es poden produir les anomenades inversions (inversions, desviacions de l'ultrametricitat).
Agrupació divisiva El principi bàsic de l'agrupació divisiva es va publicar com l'algoritme DIANA (DIvisive ANAlysis clustering). Inicialment, totes les dades es troben al mateix clúster i el clúster més gran es divideix fins que cada objecte està separat. Com que existeixen Per poder dividir cada clúster, calen heurístiques. DIANA tria l'objecte amb la màxima dissimilaritat mitjana i després mou tots els objectes a aquest clúster que siguin més similars al nou clúster que a la resta.
Informalment, DIANA no és tant un procés de "divisió" com de "buidat": a cada iteració, es tria un clúster existent (per exemple, el clúster inicial de tot el conjunt de dades) per formar un nou clúster dins seu. Els objectes es mouen progressivament a aquest clúster imbricat i buiden el clúster existent. Finalment, tot el que queda dins d'un clúster són els clústers imbricats que hi han crescut, sense que aquest posseeixi cap objecte solt per si mateix.
Programari Implementacions de codi obert miniatura|Dendrograma de clústering jeràrquic del conjunt de dades Iris (utilitzant R). Font
ALGLIB implementa diversos algoritmes de clústering jeràrquic (enllaç únic, enllaç complet, Ward) en C++ i C# amb memòria O(n²) i temps d'execució O(n³).
ELKI inclou múltiples algoritmes de clústering jeràrquic, diverses estratègies d'enllaç i també inclou els algoritmes eficients SLINK, CLINK i Anderberg, extracció flexible de clústers a partir de dendrogrames i diversos altres algoritmes d'anàlisi de clústers.
Julia té una implementació dins del paquet Clustering.
Octave, l'anàleg GNU de MATLAB, implementa el clústering jeràrquic a la funció "enllaç".
Orange, un conjunt de programari de mineria de dades, inclou el clústering jeràrquic amb visualització interactiva de dendrogrames.
R té funcions integrades i paquets que proporcionen funcions per al clústering jeràrquic.
SciPy implementa el clústering jeràrquic a Python, inclòs l'algoritme eficient SLINK.
scikit-learn també implementa el clústering jeràrquic a Python.
Weka inclou anàlisi de clústers jeràrquic.
miniatura|Agrupació jeràrquica i visualització interactiva de dendrogrames a la suite de mineria de dades d'Orange.
Referències
Categoria:Algorismes Categoria:Aprenentatge automàtic Categoria:Dades informàtiques