BIRCH (reducció i agrupament iteratiu equilibrat mitjançant jerarquies) és un algoritme de mineria de dades no supervisat que s'utilitza per realitzar agrupaments jeràrquics sobre conjunts de dades particularment grans. Amb modificacions, també es pot utilitzar per accelerar l'agrupament de k-means i la modelització de mescles gaussiana amb l'algoritme d'expectativa-maximització. Un avantatge de BIRCH és la seva capacitat d'agrupar de manera incremental i dinàmica punts de dades mètriques multidimensionals entrants en un intent de produir l'agrupament de millor qualitat per a un conjunt de recursos determinat (restriccions de memòria i temps). En la majoria dels casos, BIRCH només requereix una sola exploració de la base de dades.
Els seus inventors afirmen que BIRCH és el "primer algorisme de clústering proposat a l'àrea de bases de dades per gestionar el 'soroll' (punts de dades que no formen part del patró subjacent) de manera efectiva", superant DBSCAN per dos mesos. L'algoritme BIRCH va rebre el premi SIGMOD de prova de temps de 10 anys el 2006.
Problema amb mètodes anteriors Els algoritmes de clústering anteriors tenien un rendiment menys eficaç en bases de dades molt grans i no consideraven adequadament el cas en què un conjunt de dades era massa gran per cabre a la memòria principal. Com a resultat, hi havia molta sobrecàrrega per mantenir una alta qualitat de clústering alhora que es minimitzava el cost de les operacions d'E/S (entrada/sortida) addicionals. A més, la majoria dels predecessors de BIRCH inspeccionen tots els punts de dades (o tots els clústers existents actualment) per igual per a cada "decisió de clústering" i no realitzen una ponderació heurística basada en la distància entre aquests punts de dades.
Avantatges amb BIRCH És local, ja que cada decisió de clústerització es pren sense escanejar tots els punts de dades i els clústers existents actualment. Explota l'observació que l'espai de dades no sol estar ocupat uniformement i no tots els punts de dades són igualment importants. Fa un ús complet de la memòria disponible per derivar els millors subclústers possibles alhora que minimitza els costos d'E/S. També és un mètode incremental que no requereix tot el conjunt de dades per endavant.
Algoritme L'algoritme BIRCH pren com a entrada un conjunt de punts de dades, representats com a vectors amb valors reals, i un nombre desitjat de clústers Opera en quatre fases, la segona de les quals és opcional.
La primera fase crea una funció d'agrupació en clústers () arbre a partir dels punts de dades, una estructura de dades d'arbre amb alçada equilibrada, definida de la següent manera:
Donat un conjunt de N punts de dades d-dimensionals, la característica d'agrupació del conjunt es defineix com el triplet , on és la suma lineal. és la suma quadrada dels punts de dades.
Les característiques de clúster s'organitzen en un arbre CF, un arbre equilibrat en alçada amb dos paràmetres: factor de ramificació B i llindar 𝑇.
En el segon pas, l'algoritme escaneja totes les entrades de les fulles de la configuració inicial. arbre per reconstruir-ne un de més petit arbre, mentre s'eliminen els valors atípics i s'agrupen els subclústers concorreguts en subclústers més grans. Aquest pas està marcat com a opcional a la presentació original de BIRCH.
En el tercer pas, s'utilitza un algorisme de clústering existent per agrupar totes les entrades de les fulles. Aquí s'aplica directament un algorisme de clústering jeràrquic aglomeratiu als subclústers representats pels seus vectors. També ofereix la flexibilitat de permetre a l'usuari especificar el nombre desitjat de clústers o el llindar de diàmetre desitjat per als clústers. Després d'aquest pas s'obté un conjunt de clústers que captura el patró de distribució principal de les dades. Tanmateix, hi pot haver inexactituds menors i localitzades que es poden gestionar amb un pas opcional 4. Al pas 4, els centroides dels clústers produïts al pas 3 s'utilitzen com a llavors i es redistribueixen els punts de dades a les llavors més properes per obtenir un nou conjunt de clústers. El pas 4 també ens ofereix l'opció de descartar valors atípics. És a dir, un punt que està massa lluny de la seva llavor més propera es pot tractar com un valor atípic.
Càlculs amb les característiques d'agrupació en clústers Donada només la funció de clústering , les mateixes mesures es poden calcular sense conèixer els valors reals subjacents.
Centroide: Radi: Distància mitjana d'enllaç entre clústers i :
En casos multidimensionals, l'arrel quadrada s'ha de substituir per una norma adequada.
BIRCH utilitza les distàncies DO a D3 per trobar la fulla més propera, i després el radi R o el diàmetre D per decidir si absorbir les dades a la fulla existent o si afegir-ne una de nova.
Problemes numèrics en les característiques d'agrupació en clústers de BIRCH Malauradament, hi ha problemes numèrics associats amb l'ús del terme en BIRCH. Quan es resta o similars en altres distàncies com ara , es pot produir una cancel·lació catastròfica i produir una precisió deficient, i que en alguns casos fins i tot pot fer que el resultat sigui negatiu (i que l'arrel quadrada esdevingui indefinida). Això es pot resoldre mitjançant les característiques del clúster BETULA. en canvi, que emmagatzemen el recompte , significa , i la suma de desviacions al quadrat basada en algoritmes en línia numèricament més fiables per calcular la variància. Per a aquestes característiques, es compleix un teorema d'aditivitat similar. Quan s'emmagatzema un vector respectivament una matriu per a les desviacions al quadrat, l'arbre CF de BIRCH resultant també es pot utilitzar per accelerar la modelització de mescles gaussiana amb l'algoritme d'expectativa-maximització, a més de l'agrupació de k-mitjanes i l'agrupació aglomerativa jeràrquica.
En lloc d'emmagatzemar la suma lineal i la suma dels quadrats, podem emmagatzemar la mitjana i la desviació al quadrat de la mitjana a cada característica del clúster. , on
𝑛 és el pes del node (nombre de punts) 𝜇 és el vector del centre del node (mitjana aritmètica, centroide)
𝑆 és la suma de les desviacions al quadrat de la mitjana (ja sigui un vector o una suma per estalviar memòria, depenent de l'aplicació)
La principal diferència aquí és que S es calcula en relació amb el centre, en lloc de fer-ho en relació amb l'origen.
Un sol punt es pot convertir en una característica de clúster Per tal de combinar dues característiques de clúster , fem servir
(actualització incremental de la mitjana) en vector forma utilitzant el producte element a element, per actualitzar una suma escalar de desviacions quadrades
Aquests càlculs utilitzen càlculs numèricament més fiables (cf. càlcul en línia de la variància) que eviten la resta de dos valors quadrats similars. El centroide és simplement el vector central del node. , i es pot utilitzar directament per a càlculs de distàncies utilitzant, per exemple, les distàncies euclidianes o de Manhattan. El radi es simplifica a i el diàmetre a .
Ara podem calcular les diferents distàncies D0 a D4 utilitzades en l'algoritme BIRCH com:
Distància euclidiana i la distància de Manhattan es calculen utilitzant els centres CF Distància entre clústers Distància intraclúster Distància d'augment de la variància
Aquestes distàncies també es poden utilitzar per inicialitzar la matriu de distàncies per a l'agrupació jeràrquica, depenent de l'enllaç escollit. Per a una agrupació jeràrquica precisa i una agrupació de k-means, també hem d'utilitzar el pes del node. .
Pas de clústering L'arbre CF proporciona un resum comprimit del conjunt de dades, però les fulles en si mateixes només proporcionen una agrupació de dades molt deficient. En un segon pas, les fulles es poden agrupar mitjançant, per exemple,
k-means clustering, on les fulles es ponderen pel nombre de punts, N. k-means++, mostrant característiques de clúster proporcionals a on el són els centres escollits prèviament, i és la característica del clúster BETULA. Modelització de mescles gaussiana, on també es pot tenir en compte la variància S, i si les fulles emmagatzemen covariàncies, també les covariàncies. Agrupació aglomerativa jeràrquica, on l'enllaç es pot inicialitzar utilitzant la següent equivalència d'enllaços a distàncies BIRCH:
Correspondència entre els enllaços HAC i les distàncies Enllaç HACDistància BIRCHUPGMAD2²WPGMAD0²Sala2 D4²
Referències
Categoria:Algorismes Categoria:Aprenentatge automàtic