La clusterització de dades és una tècnica molt comuna en l'anàlisi estadística de dades. Bàsicament és la classificació d'objectes similars en diferents grups, o més precisament, la partició de les dades en diferents subconjunts (o clústers). Així doncs, les dades de cada subgrup idealment comparteixen un tret comú.
A grans trets, podem dividir els algorismes en jeràrquics o particionals.
En els primers, es generen clústers successius a partir de clústers ja establerts prèviament. Aquests poden ser aglomeratius si cada element es considera un clúster diferent i posteriorment van agrupant-se. O bé divisoris, si a partir del conjunt sencer es procedeix a dividir-lo en subconjunts més petits. En el segon cas, tots els clústers es determinen en una passada, sovint optimitzant-ho segons un criteri determinat. Al final del procés, es pot tornar a ubicar algunes de les entitats en altres clústers.
Per altra banda, cal destacar les tècniques de cerca per densitat i de 'clumping'. En les primeres, les entitats es consideren com a punts en un espai mètric i normalment es prima la incorporació de nous elements en clústers ja existents abans que crear-ne'n de nous. Les segones es caracteritzen per permetre l'existència de clústers que no siguin disjunts, això és, que els elements puguin incloure's en diferents subgrups simultàniament.
Definició La noció de "clúster" no es pot definir amb precisió, i és per això que hi ha tants algorismes d'agrupació. Hi ha un concepte en comú: un grup d'objectes de dades. Tanmateix, diferents investigadors utilitzen diferents models de clúster, i per a cadascun d'aquests models de clúster es poden donar, de nou, algorismes diferents. La noció de clúster, tal com la troben diferents algorismes, varia significativament en les seves propietats. Entendre aquests "models de clúster" és clau per entendre les diferències entre els diferents algorismes. Els models de clúster típics inclouen:
Models basats en connectivitat: per exemple, l'agrupació jeràrquica construeix models basats en la connectivitat a distància. Model basats en centroides: per exemple, l'algorisme de k-means representa cada clúster mitjançant un únic vector mitjà. Models de distribució: els clústers es modelen mitjançant distribucions estadístiques, com ara les distribucions normals multivariables utilitzades per l'algorisme de maximització d'expectativa. Models basats en densitat: per exemple, DBSCAN i OPTICS defineixen clústers com a regions denses connectades a l'espai de dades. Models basats en subespais: en el biclustering (també conegut com a co-clustering o clustering de dos modes), els clústers es modelen tant amb els membres del clúster com amb els atributs rellevants. Models de grup: alguns algorismes no proporcionen un model refinat per als seus resultats i només proporcionen la informació d'agrupació. Model basat en grafs: un clique és a dir, un subconjunt de nodes en un graf manera que cada dos nodes del subconjunt estan connectats per una aresta es pot considerar com una forma prototípica de clúster. Les relaxacions del requisit complet de connectivitat (pot faltar una fracció de les vores) es coneixen com a quasi-cliques, com en l'algorisme d'agrupació HCS. Models de grafs signats: Cada camí en un gràfic signat té un signe del producte dels signes de les arestes. Sota els supòsits de la teoria de l'equilibri, les arestes poden canviar de signe i donar lloc a un gràfic bifurcat. L'"axioma d'agrupació" més feble (cap cicle té exactament un avantatge negatiu) dona resultats amb més de dos grups, o subgrafs amb només arestes positives.James A. Davis (May 1967) "Clustering and structural balance in graphs", Human Relations 20:181–7 Models neuronals: La xarxa neuronal no supervisada més coneguda és el mapa autoorganitzat i aquests models normalment es poden caracteritzar com a similars a un o més dels models anteriors, i inclouen models basats en subespais quan les xarxes neuronals implementen una forma d'Anàlisi de Components Principals (ACP) o Anàlisi Independent de Components.
Un "agrupament" és essencialment un conjunt d'aquests clústers, que normalment conté tots els objectes del conjunt de dades. A més, pot especificar la relació dels clústers entre si, per exemple, una jerarquia de clústers incrustats entre si. Els agrupaments es poden distingir aproximadament com:
Clúster dur : cada objecte pertany o no a un clúster Agrupació suau (també: agrupació difusa): cada objecte pertany a cada clúster fins a un cert grau (per exemple, una probabilitat de pertànyer al clúster)
També hi ha distincions més concretes, per exemple:
Clúster de particions estrictes: cada objecte pertany exactament a un clúster. Clúster de particions estrictes amb valors atípics : els objectes també poden pertànyer a cap clúster i es consideren dades atípiques. Agrupació superposada (també:agrupació alternativa,multivista): els objectes poden pertànyer a més d'un clúster; normalment inclouen cúmuls durs. Clúster jeràrquic : els objectes que pertanyen a un clúster fill també pertanyen al clúster pare. Agrupació de subespais: Igual que una agrupació superposada, dins d'un subespai definit de manera única, però no s'espera que els clústers se superposin.
Algorismes Tal com s'ha esmentat anteriorment, els algorismes de clúster es poden classificar en funció del seu model de clúster. A continuació només es llisten els exemples més destacats d'algorismes d'agrupació, ja que hi ha més d'un centenar d'algorismes de clúster publicats. No tots proporcionen models per als seus clústers i, per tant, són difícils de categoritzar. (A la llista d'algorismes estadístics es pot trobar una visió general dels algorismes explicats a la Viquipèdia.)
No hi ha cap algorisme d'agrupament "correcte" objectivament, però com es va dir, "l'agrupament està en l'ull de l'espectador". Sovint s'ha de triar empíricament l'algorisme d'agrupació més adequat per cada problema específic, tret que hi hagi una raó matemàtica per la qual un model de clúster sigui millor respecte a la resta. Un algorisme dissenyat per a un tipus de model generalment fallarà en un conjunt de dades que conté un tipus de model radicalment diferent. Per exemple, el k-means no pot trobar clústers no convexos.
Clúster basat en connectivitat (agrupació jeràrquica) L'agrupació basada en la connectivitat, també coneguda com a agrupació jeràrquica, es basa en la idea que els objectes estan més relacionats amb objectes propers que amb objectes més allunyats. Aquests algorismes connecten "objectes" per formar "clústers" en funció de la seva distància. Un clúster es pot descriure en gran manera per la distància màxima necessària per a connectar parts del clúster. A diferents distàncies es formaran diferents clústers, que es poden representar mitjançant un dendrograma. D’aquí és d'on ve el nom "agrupació jeràrquica". Aquests algorismes no proporcionen una única partició del conjunt de dades, sinó que proporcionen una àmplia jerarquia de clústers que es fusionen entre ells en determinades distàncies. En un dendrograma, l'eix Y marca la distància a la qual es fusionen els clústers, mentre que els objectes es col·loquen al llarg de l'eix X de manera que els grups no es barregin.
El clustering basat en la connectivitat comprèn un conjunt de mètodes que es diferencien per la manera com es calculen les distàncies. A part de l'elecció habitual de funcions de distància, l'usuari també ha de decidir el criteri d'enllaç a utilitzar (atès que un clúster consta de diversos objectes, hi ha diversos candidats per a calcular la distància). Les opcions més comuns com a criteri d'enllaç es coneixen com a agrupació d'enllaç únic (el mínim de distàncies d'objecte), agrupació d'enllaç complet (el màxim de distàncies d'objecte) i UPGMA o WPGMA("Mètode de grups de parells no ponderats o ponderats amb mitjana aritmètica", també conegut com a agrupació d'enllaços mitjans). A més, l'agrupació jeràrquica pot ser aglomerativa (començant amb elements únics i agregant-los en clústers) o divisòria (començant pel conjunt de dades complet i dividint-lo en particions).
Aquests mètodes no produiran una partició única del conjunt de dades, sinó una jerarquia a partir de la qual l'usuari encara haurà de triar els clústers adequats. No són molt robusts cap a les dades atípiques, que es mostraran com a clústers addicionals o fins i tot provocaran que altres clústers es fusionin (el que es coneix com a "fenomen d'encadenament", en particular amb l'agrupament d'enllaç únic). En el cas general, la complexitat és per al clustering aglomeratiu i per a l'agrupament divisiu, que els fa massa lents per a grans conjunts de dades. Per a alguns casos especials, es coneixen mètodes òptims eficients (de complexitat ): SLINK per a l'enllaç únic i CLINK per a l'agrupació d'enllaços complets.
Clúster basat en centroides Article principal: k-means clustering
En l'agrupació basada en centroides, cada clúster està representat per un vector central, que no és necessàriament un membre del conjunt de dades. Quan el nombre de clústers es fixa en k, k-means dona una definició formal com a problema d'optimització: troba els k centres del clúster i assigna els objectes al centre del clúster més proper, de manera que les distàncies del clúster es minimitzin.
Se sap que el problema d'optimització en si és NP-complex i, per tant, l'enfocament comú és buscar només solucions aproximades. Un mètode aproximat particularment conegut és l'algorisme de Lloyd, sovint anomenat " algorisme k-means ". Tanmateix, només troba un òptim local i s'executa diverses vegades amb diferents inicialitzacions aleatòries. Les variacions de k -means sovint inclouen optimitzacions com l'elecció del millor de múltiples execucions, però també restringir els centroides als membres del conjunt de dades (k-medoids), escollint les mitjanes(k-medians clustering), escollint els centres inicials de manera menys aleatòria (k-means++) o permetent una assignació de clúster difusa (fuzzy c-means).
La majoria dels algorismes de tipus k - means requereixen que el nombre de clústers –k– s'especifiqui, cosa que es considera un dels majors inconvenients d'aquests algorismes. A més, els algorismes prefereixen clústers de mida similar, ja que sempre assignaran un objecte al centroide més proper. Això sovint condueix a tallar incorrectament les vores dels clústers (fet que no és sorprenent, ja que l'algoritme optimitza els centres del clúster, no les vores del clúster).
Els K-means tenen una sèrie de propietats teòriques interessants. En primer lloc, divideix l'espai de dades en una estructura coneguda com a diagrama de Voronoi. En segon lloc, conceptualment s'acosta a la classificació del veí més proper i, per tant, és popular en l'aprenentatge automàtic. En tercer lloc, es pot veure com una variació de l'agrupament basat en models i l'algoritme de Lloyd com una variació de l'algoritme de maximització d'expectatives per a aquest model que es discuteix a continuació.Els problemes d'agrupament basats en centroides, com ara k-means i k-medoids, són casos especials del problema d'ubicació d'instal·lacions, un problema canònic a les comunitats de recerca d'operacions i geometria computacional. En un problema bàsic d'ubicació d'instal·lacions (del qual hi ha nombroses variants que modelen configuracions més elaborades), la tasca és trobar les millors ubicacions de magatzem per atendre de manera òptima un conjunt determinat de consumidors. Es poden veure els "magatzems" com a centroides de clúster i les "ubicacions dels consumidors" com les dades que s'han d'agrupar. Això fa possible aplicar les solucions algorítmiques ben desenvolupades pel problema de les instal·lacions al problema d'agrupació basat en el centroide que s'està considerant.
Agrupació basada en la distribució