L'agrupació difusa (també anomenada agrupació suau o k- mitjanes suaus) és una forma d'agrupació en què cada punt de dades pot pertànyer a més d'un clúster.
L'anàlisi de clústers o agrupament en clústers implica assignar punts de dades a clústers de manera que els elements del mateix clúster siguin el més similars possible, mentre que els elements que pertanyen a clústers diferents siguin el més diferents possible. Els clústers s'identifiquen mitjançant mesures de similitud. Aquestes mesures de similitud inclouen la distància, la connectivitat i la intensitat. Es poden triar diferents mesures de similitud en funció de les dades o de l'aplicació.
Comparació amb l'agrupació dura En l'agrupació no difusa (també coneguda com a agrupació difícil), les dades es divideixen en clústers diferents, on cada punt de dades només pot pertànyer a exactament un clúster. En l'agrupació difusa, els punts de dades poden pertànyer potencialment a diversos clústers. Per exemple, una poma pot ser vermella o verda (agrupació difícil), però una poma també pot ser vermella I verda (agrupació difusa). Aquí, la poma pot ser vermella fins a un cert grau, així com verda fins a un cert grau. En lloc que la poma pertanyi al verd [verd = 1] i no al vermell [vermell = 0], la poma pot pertànyer al verd [verd = 0,5] i al vermell [vermell = 0,5]. Aquests valors es normalitzen entre 0 i 1; tanmateix, no representen probabilitats, de manera que els dos valors no han de sumar 1.
Membresia Els graus de pertinença s'assignen a cadascun dels punts de dades (etiquetes). Aquests graus de pertinença indiquen el grau en què els punts de dades pertanyen a cada clúster. Per tant, els punts a la vora d'un clúster, amb graus de pertinença més baixos, poden estar al clúster en menor grau que els punts al centre del clúster.
Agrupació difusa de C-means Un dels algoritmes de clústering difús més utilitzats és l'algoritme Fuzzy C-means clustering (FCM).
Història vL'agrupació de c-means difuses (FCM) va ser desenvolupada per JC Dunn el 1973, i millorada per JC Bezdek el 1981. L'agrupació de c-means difuses (FCM) va ser desenvolupada per JC Dunn el 1973, i millorada per JC Bezdek el 1981.
Descripció general L'algoritme fuzzy c-means és molt similar a l'algoritme k-means:
Trieu un nombre de clústers. Assigneu coeficients aleatòriament a cada punt de dades per pertànyer als clústers. Repetiu-ho fins que l'algoritme hagi convergit (és a dir, que el canvi de coeficients entre dues iteracions no sigui superior a , el llindar de sensibilitat donat) : Calcula el centroide per a cada clúster (que es mostra a continuació). Per a cada punt de dades, calculeu els seus coeficients de pertinença als clústers.
Centroide Qualsevol punt x té un conjunt de coeficients que donen el grau de pertinença al k -èsim clúster wk(x). Amb c -mitges difuses, el centroide d'un clúster és la mitjana de tots els punts, ponderada pel seu grau de pertinença al clúster, o, matemàticament,
on m és l'hiperparàmetre que controla com de difús serà el clúster. Com més alt sigui, més difús serà el clúster al final.
Algorisme L'algoritme FCM intenta particionar una col·lecció finita de elements en una col·lecció de c clústers difusos respecte a algun criteri donat.
Donat un conjunt finit de dades, l'algoritme retorna una llista de centres de clústers i una matriu de partició W
, where each element, , tells the degree to which element, , belongs to cluster .
on:
Comparació amb l'agrupació de K-means L'agrupació de K-means també intenta minimitzar la funció objectiu mostrada anteriorment, excepte que a K-means, els valors de pertinença són zero o un, i no poden prendre valors intermedis, és a dir, En Fuzzy C-means, el grau de difuminació està parametritzat per , on un més gran resulta en clústers més borrosos. En el límit , les adhesions, , convergeixen a 0 o 1, i l'objectiu de les C-mitjanes difuses coincideix amb el de les K-mitjanes. En absència d'experimentació o coneixement del domini, normalment es defineix a 2. L'algoritme també minimitza la variància intraclúster, però té els mateixos problemes que les 'k'-mitges; el mínim és un mínim local i els resultats depenen de l'elecció inicial dels pesos.
Implementació Hi ha diverses implementacions d'aquest algoritme que estan disponibles públicament.
Algorismes relacionats Les mitjanes C difuses (FCM) amb determinació automàtica del nombre de clústers podrien millorar la precisió de la detecció. L'ús d'una barreja de gaussianes juntament amb l'algoritme de maximització de l'expectativa és un mètode més formalitzat estadísticament que inclou algunes d'aquestes idees: la pertinença parcial a classes.
Exemple Per entendre millor aquest principi, a continuació es mostra un exemple clàssic de dades monodimensionals en un eix x. center|sense marc|342x342px Tradicionalment, aquest conjunt de dades es pot agrupar en dos clústers. En seleccionar un llindar a l'eix x, les dades se separen en dos clústers. Els clústers resultants s'etiqueten com a "A" i "B", tal com es veu a la imatge següent. Per tant, cada punt que pertany al conjunt de dades tindria un coeficient de pertinença d'1 o 0. Aquest coeficient de pertinença de cada punt de dades corresponent es representa mitjançant la inclusió de l'eix y. center|sense marc|363x363px En l'agrupació difusa, cada punt de dades pot tenir pertinença a diversos clústers. Si es relaxa la definició dels coeficients de pertinença d'estrictament 1 o 0, aquests valors poden variar des de qualsevol valor d'1 a 0. La imatge següent mostra el conjunt de dades de l'agrupació anterior, però ara s'aplica l'agrupació difusa de c-means. Primer, es pot generar un nou valor llindar que defineix dos clústers. A continuació, es generen nous coeficients de pertinença per a cada punt de dades basats en els centroides dels clústers, així com en la distància des de cada centroide del clúster. center|sense marc|375x375px Com es pot veure, el punt de dades del mig pertany al clúster A i al clúster B. El valor de 0,3 és el coeficient de pertinença d'aquest punt de dades per al clúster A.
Aplicacions Els problemes de clústering tenen aplicacions en ciència de superfícies, biologia, medicina, psicologia, economia i moltes altres disciplines.
Bioinformàtica En el camp de la bioinformàtica, l'agrupació s'utilitza per a diverses aplicacions. Un ús és com a tècnica de reconeixement de patrons per analitzar dades d'expressió gènica a partir de dades de seqüenciació d'ARN o altres tecnologies. En aquest cas, els gens amb patrons d'expressió similars s'agrupen en el mateix clúster, i diferents clústers mostren patrons d'expressió diferents i ben separats. L'ús de l'agrupació pot proporcionar informació sobre la funció i la regulació dels gens. Com que l'agrupació difusa permet que els gens pertanyin a més d'un clúster, permet la identificació de gens que estan corregulats o coexpressats condicionalment. Per exemple, un gen pot ser afectat per més d'un factor de transcripció, i un gen pot codificar una proteïna que té més d'una funció. Per tant, l'agrupació difusa és més adequada que l'agrupació dura.
Anàlisi d'imatges El c-means difús ha estat una eina molt important per al processament d'imatges en l'agrupació d'objectes en una imatge. A la dècada de 1970, els matemàtics van introduir el terme espacial a l'algoritme FCM per millorar la precisió de l'agrupació sota soroll. A més, els algoritmes FCM s'han utilitzat per distingir entre diferents activitats utilitzant característiques basades en imatges com ara els moments de Hu i Zernike. Alternativament, es pot descriure un model de lògica difusa en conjunts difusos que es defineixen en tres components de l'espai de color HSL HSL i HSV; Les funcions de pertinença tenen com a objectiu descriure els colors seguint la intuïció humana de la identificació del color.
Màrqueting En màrqueting, els clients es poden agrupar en clústers difusos segons les seves necessitats, eleccions de marca, perfils psicogràfics o altres particions relacionades amb el màrqueting.
Exemple de processament d'imatges miniatura|168x168px|Imatge segmentada per agrupament difús, amb l'original (a dalt a l'esquerra), agrupat (a dalt a la dreta) i el mapa de pertinença (a baix) La segmentació d'imatges mitjançant algoritmes de clústering k-means s'ha utilitzat durant molt de temps per al reconeixement de patrons, la detecció d'objectes i les imatges mèdiques. Tanmateix, a causa de les limitacions del món real, com ara el soroll, les ombres i les variacions en les càmeres, el clústering dur tradicional sovint no pot realitzar de manera fiable les tasques de processament d'imatges tal com s'ha esmentat anteriorment. S'ha proposat l'agrupació difusa com un algorisme més aplicable en el rendiment d'aquestes tasques. Es mostra una imatge en escala de grisos que s'ha sotmès a una agrupació difusa a Matlab. La imatge original es veu al costat d'una imatge agrupada. Els colors s'utilitzen per donar una representació visual dels tres clústers diferents que s'utilitzen per identificar la pertinença de cada píxel. A continuació, es proporciona un gràfic que defineix els coeficients de pertinença difusa dels seus valors d'intensitat corresponents.
Segons l'aplicació per a la qual s'hagin d'utilitzar els coeficients de clústering difús, es poden aplicar diferents tècniques de preprocessament a les imatges RGB. La conversió de RGB a HCL és una pràctica habitual.
Referències
Categoria:Algorismes Categoria:Bases de dades