Agrupamiento jeràrquic
En mineria de senyes, el agrupament jeràrquic és un mètoto d'anàlisis de grups puntuals, el qual busca construir una jerarquia de grups. Estratègies per a agrupament jeràrquic generalment cauen en dos tipos:
- Aglomerativas: Est és un acostament ascendent: cada observació comença en el seu propi grup, i els parells de grups són mesclats mentres un puja en la jerarquia.
- Divisivas: Est és un acostament descendent: totes les observacions comencen en un grup, i es realisen divisions mentres un baixa en la jerarquia.
En general, les mescles i divisions són determinades en un Algoritme voraç. Els resultats de l'agrupament jeràrquic són usualment presentats en un dendrograma.
En el cas general, la complexitat de l'agrupament aglomerativo és , lo que els fa massa llents per a grans conjunts de senyes. El agrupament divisivo en busca exhaustiva és lo que és encara pijor. No obstant, per a alguns casos especials, òptims i eficients métodos aglomerativos (de complexitat ) són coneguts: SLINK[1] per a agrupament d'enllaç-simple i CLINK[2] per a agrupament d'enllaç complet.
Dissimilitut de grup
En orde de decidir qué grups deurien ser combinats (per a aglomerativo), o quan un grup deuria ser dividit (per a divisivo), una mida de dissimilitut entre conjunts d'observacions és requerida. En la majoria dels métodos de agrupament jeràrquic, açò és conseguit per mig d'ús d'una mètrica apropiada (una mida de distància entre parells d'observacions), i un criteri d'enllaç el qual especifica la dissimilitut de conjunts com una funció de les distàncies dos a dos entre observacions en els conjunts.
Mètrica
L'elecció d'una mètrica apropiada influenciarà la forma dels grups, ya que alguns poden estar prop uns d'uns atres d'acort a una distància i més llunt d'acort a una atra. Per eixemple, en un espai 2-dimensional, la distància entre el punt (1,0) i l'orige (0,0) és sempre 1 d'acort a les normes usuals, pero la distància entre el punt (1,1) i l'orige (0,0) pot ser 2, o 1 baix la distància Manhattan, la distància euclidiana o la distància màxima respectivament.
Algunes mètriques comunament usades per a agrupament jeràrquic són:[3]
| Names | Formula |
|---|---|
| Distància euclidiana | |
| Distància euclidiana al quadrat | |
| Distància Manhattan | |
| distància màxima | |
| Distància de Mahalanobis | a on S és la matriu de covariància |
| Similitut coseno |
Per a text o una atra senya no numèrica, mètriques com la Distància de Hamming o la Distància de Levenshtein són freqüentment usades.
Criteri d'enllaç
El criteri d'enllaç determina la distància entre conjunts d'observacions com una funció de les distàncies entre observacions dos a dos.
Alguns criteris d'enllaç entre dos conjunts d'observacions A i B freqüentment usats són:[4][5]
| Noms | Fòrmula |
|---|---|
| Agrupament de màxim o complet enllaç | |
| Agrupament de mínim o simple enllaç | |
| Agrupament d'enllaç mija o promig, o UPGMA | |
| Agrupament de mínima energia |
A on d és la mètrica triada. Atres criteris d'enllaç inclou:
- La suma de totes les variància intragrupo.
- L'afluixó en la variància per als grups que estan sent mesclats (criteri de Ward).
- La probabilitat de que grups candidats es produïxquen des de la mateixa funció de distribució.(V-enllaç)
Discussió
El agrupament jeràrquic té la ventaja distintiva de que qualsevol mida de distància pot ser usada. De fet, les observacions de per sí no són requerides: tot lo que s'usa és una matriu de distància.
Vore també
Referències
- ↑ R. Sibson(1973).«SLINK: an optimally efficient algorithm for the single-link cluster method».The Computer Journal.British Computer Society.16(1): 30–34.
- ↑ D. Defays(1977).«An efficient algorithm for a complete link method».The Computer Journal.British Computer Society.20(4): 364–366.
- ↑ «The DISTANCE Procedure: Proximity Measures». SAS/STAT 9.2 Users Guide. SAS Institute. Consultat el 26 d'abril de 2009.
- ↑ «The CLUSTER Procedure: Clustering Methods». SAS/STAT 9.2 Users Guide. SAS Institute. Consultat el 26 d'abril de 2009.
- ↑ Székely, G. J. and Rizzo, M. L. (2005) Hierarchical clustering via Joint Between-Within Distances: Extending Ward's Minimum Variance Method, Journal of Classification 22, 151-183.
Bibliografia
- Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2009). «14.3.12 Hierarchical clustering», The Elements of Statistical Learning (PDF), 2nd edició, Nova York: Springer, pp. 520–528. ISBN 0-387-84857-6. Consultat el 20 d'octubre de 2009.
- Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). «Section 16.4. Hierarchical Clustering by Phylogenetic Trees», Numerical Recipes: The Art of Scientific Computing, 3rd edició, Cambridge University Press. ISBN 978-0-521-88068-8. Consultat el 19 de decembre de 2012.
- Este artícul conté una traducció derivada de «Agrupamiento jerárquico» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.