Agrupamiento difuso

Tipo de agrupamiento de puntos de datos

La agrupación difusa (también conocida como agrupación suave o k -medias suaves ) es una forma de agrupación en la que cada punto de datos puede pertenecer a más de un grupo.

La agrupación o análisis de conglomerados implica asignar puntos de datos a conglomerados de modo que los elementos del mismo conglomerado sean lo más similares posible, mientras que los elementos que pertenecen a conglomerados diferentes sean lo más diferentes posible. Los conglomerados se identifican mediante medidas de similitud. Estas medidas de similitud incluyen distancia, conectividad e intensidad. Se pueden elegir diferentes medidas de similitud en función de los datos o la aplicación. ^[1]

Comparación con el agrupamiento duro

En la agrupación no difusa (también conocida como agrupación rígida), los datos se dividen en grupos distintos, donde cada punto de datos solo puede pertenecer a exactamente un grupo. En la agrupación difusa, los puntos de datos pueden pertenecer potencialmente a varios grupos. Por ejemplo, una manzana puede ser roja o verde (agrupación rígida), pero una manzana también puede ser roja Y verde (agrupación difusa). En este caso, la manzana puede ser roja hasta cierto punto y también verde hasta cierto punto. En lugar de que la manzana pertenezca al verde [verde = 1] y no al rojo [rojo = 0], la manzana puede pertenecer al verde [verde = 0,5] y al rojo [rojo = 0,5]. Estos valores se normalizan entre 0 y 1; sin embargo, no representan probabilidades, por lo que no es necesario que los dos valores sumen 1.

Afiliación

A cada uno de los puntos de datos (etiquetas) se le asignan grados de pertenencia. Estos grados de pertenencia indican el grado en que los puntos de datos pertenecen a cada grupo. Por lo tanto, los puntos en el borde de un grupo, con grados de pertenencia más bajos, pueden estar en el grupo en un grado menor que los puntos en el centro del grupo.

Agrupamiento de C-medias difusas

Uno de los algoritmos de agrupamiento difuso más utilizados es el algoritmo de agrupamiento difuso C-medias (FCM).

Historia

La agrupación por c-medias difusas (FCM) fue desarrollada por JC Dunn en 1973, ^[2] y mejorada por JC Bezdek en 1981. ^[3]

Descripción general

El algoritmo difuso c -means es muy similar al algoritmo k -means :

• Elija un número de clústeres .
• Asignar coeficientes aleatoriamente a cada punto de datos por estar en los clústeres.
• Repita hasta que el algoritmo haya convergido (es decir, el cambio de coeficientes entre dos iteraciones no sea mayor que , el umbral de sensibilidad dado): ${\displaystyle \varepsilon }$
  • Calcule el centroide para cada grupo (que se muestra a continuación).
  • Para cada punto de datos, calcule sus coeficientes de pertenencia a los grupos.

Centroide

Cualquier punto x tiene un conjunto de coeficientes que dan el grado de pertenencia al grupo k w _k ( x ). Con c -medias difusas, el centroide de un grupo es la media de todos los puntos, ponderada por su grado de pertenencia al grupo o, matemáticamente,

${\displaystyle c_{k}={{\sum _{x}{w_{k}(x)}^{m}x} \over {\sum _{x}{w_{k}(x)}^{m}}},}$

donde m es el hiperparámetro que controla qué tan difuso será el clúster. Cuanto más alto sea, más difuso será el clúster al final.

Algoritmo

El algoritmo FCM intenta particionar una colección finita de elementos en una colección de c grupos difusos con respecto a un criterio dado. ${\displaystyle n}$ ${\displaystyle X=\{\mathbf {x} _{1},...,\mathbf {x} _{n}\}}$

Dado un conjunto finito de datos, el algoritmo devuelve una lista de centros de clústeres y una matriz de partición. ${\displaystyle c}$ ${\displaystyle C=\{\mathbf {c} _{1},...,\mathbf {c} _{c}\}}$

${\displaystyle W=w_{i,j}\in [0,1],\;i=1,...,n,\;j=1,...,c}$, donde cada elemento, , indica el grado en que el elemento, , pertenece al grupo . ${\displaystyle w_{ij}}$ ${\displaystyle \mathbf {x} _{i}}$ ${\displaystyle \mathbf {c} _{j}}$

El FCM tiene como objetivo minimizar una función objetivo:

${\displaystyle J(W,C)=\sum _{i=1}^{n}\sum _{j=1}^{c}w_{ij}^{m}\left\|\mathbf {x} _{i}-\mathbf {c} _{j}\right\|^{2}}$,

dónde:

${\displaystyle w_{ij}={\frac {1}{\sum _{k=1}^{c}\left({\frac {\left\|\mathbf {x} _{i}-\mathbf {c} _{j}\right\|}{\left\|\mathbf {x} _{i}-\mathbf {c} _{k}\right\|}}\right)^{\frac {2}{m-1}}}}}$.

Comparación con el agrupamiento de K-medias

La agrupación en clústeres de K-medias también intenta minimizar la función objetivo mostrada arriba, excepto que en K-medias, los valores de pertenencia son cero o uno, y no pueden tomar valores intermedios, es decir . En Fuzzy C-means, el grado de imprecisión está parametrizado por , donde un mayor da como resultado clústeres más difusos. En el límite , las pertenencias, , convergen a 0 o 1, y el objetivo de Fuzzy C-means coincide con el de K-medias. En ausencia de experimentación o conocimiento del dominio, se establece comúnmente en 2. El algoritmo también minimiza la varianza intra-clúster, pero tiene los mismos problemas que 'k'-means; el mínimo es un mínimo local, y los resultados dependen de la elección inicial de pesos. ${\displaystyle w_{ij}\in \{0,1\}}$ ${\displaystyle m\in (1,\infty )}$ ${\displaystyle m}$ ${\displaystyle m\rightarrow 1}$ ${\displaystyle w_{ij}}$ ${\displaystyle m}$

Implementación

Hay varias implementaciones de este algoritmo que están disponibles públicamente. ^{[4] [5]}

Algoritmos relacionados

Los C-means difusos (FCM) determinados automáticamente para el número de clústeres podrían mejorar la precisión de la detección. ^[6] El uso de una mezcla de gaussianas junto con el algoritmo de maximización de expectativas es un método estadísticamente más formalizado que incluye algunas de estas ideas: membresía parcial en clases.

Ejemplo

Para comprender mejor este principio, se muestra a continuación un ejemplo clásico de datos unidimensionales en el eje x.

Este conjunto de datos se puede agrupar tradicionalmente en dos grupos. Al seleccionar un umbral en el eje x, los datos se separan en dos grupos. Los grupos resultantes se etiquetan como "A" y "B", como se ve en la siguiente imagen. Por lo tanto, cada punto perteneciente al conjunto de datos tendría un coeficiente de pertenencia de 1 o 0. Este coeficiente de pertenencia de cada punto de datos correspondiente se representa mediante la inclusión del eje y.

En la agrupación difusa, cada punto de datos puede pertenecer a varios clústeres. Al relajar la definición de coeficientes de pertenencia de estrictamente 1 o 0, estos valores pueden variar desde cualquier valor entre 1 y 0. La siguiente imagen muestra el conjunto de datos de la agrupación anterior, pero ahora se aplica la agrupación difusa de c-medias. Primero, se puede generar un nuevo valor de umbral que defina dos clústeres. A continuación, se generan nuevos coeficientes de pertenencia para cada punto de datos en función de los centroides de los clústeres, así como de la distancia desde cada centroide de clúster.

Como se puede ver, el punto de datos del medio pertenece al grupo A y al grupo B. El valor de 0,3 es el coeficiente de pertenencia de este punto de datos para el grupo A. ^[7]

Aplicaciones

Los problemas de agrupamiento tienen aplicaciones en la ciencia de superficies, la biología, la medicina, la psicología, la economía y muchas otras disciplinas. ^[8]

Bioinformática

En el campo de la bioinformática, la agrupación se utiliza para diversas aplicaciones. Una de ellas es como técnica de reconocimiento de patrones para analizar datos de expresión génica a partir de datos de secuenciación de ARN u otras tecnologías. ^[9] En este caso, los genes con patrones de expresión similares se agrupan en el mismo grupo, y los diferentes grupos muestran patrones de expresión distintos y bien separados. El uso de la agrupación puede proporcionar información sobre la función y la regulación de los genes. ^[8] Debido a que la agrupación difusa permite que los genes pertenezcan a más de un grupo, permite la identificación de genes que están co-regulados o co-expresados ​​condicionalmente. ^[10] Por ejemplo, un gen puede ser afectado por más de un factor de transcripción , y un gen puede codificar una proteína que tiene más de una función. Por lo tanto, la agrupación difusa es más apropiada que la agrupación dura.

Análisis de imágenes

El algoritmo FCM ha sido una herramienta muy importante para el procesamiento de imágenes en la agrupación de objetos en una imagen. En la década de 1970, los matemáticos introdujeron el término espacial en el algoritmo FCM para mejorar la precisión de la agrupación en condiciones de ruido. ^[11] Además, los algoritmos FCM se han utilizado para distinguir entre diferentes actividades utilizando características basadas en imágenes, como los momentos Hu y Zernike. ^[12] Alternativamente, un modelo de lógica difusa se puede describir en conjuntos difusos que se definen en tres componentes del espacio de color HSL y HSV ; Las funciones de pertenencia tienen como objetivo describir los colores siguiendo la intuición humana de identificación del color. ^[13]

Marketing

En marketing, los clientes pueden agruparse en grupos difusos en función de sus necesidades, elecciones de marca, perfiles psicográficos u otras particiones relacionadas con el marketing. ^{[ cita requerida ]}

Ejemplo de procesamiento de imágenes

Imagen segmentada por agrupamiento difuso, con el mapa original (arriba a la izquierda), el agrupado (arriba a la derecha) y el de pertenencia (abajo)

La segmentación de imágenes mediante algoritmos de agrupamiento de k-medias se ha utilizado durante mucho tiempo para el reconocimiento de patrones, la detección de objetos y la obtención de imágenes médicas. Sin embargo, debido a limitaciones del mundo real, como el ruido, las sombras y las variaciones en las cámaras, el agrupamiento duro tradicional a menudo no puede realizar de manera confiable las tareas de procesamiento de imágenes como se indicó anteriormente. ^{[ cita requerida ]} Se ha propuesto el agrupamiento difuso como un algoritmo más aplicable en el desempeño de estas tareas. Se da una imagen en escala de grises que se ha sometido a agrupamiento difuso en Matlab. ^[14] La imagen original se ve junto a una imagen agrupada. Se utilizan colores para dar una representación visual de los tres grupos distintos utilizados para identificar la pertenencia de cada píxel. A continuación, se proporciona un gráfico que define los coeficientes de pertenencia difusa de sus valores de intensidad correspondientes.

Dependiendo de la aplicación para la cual se utilizarán los coeficientes de agrupamiento difuso, se pueden aplicar diferentes técnicas de preprocesamiento a las imágenes RGB . La conversión de RGB a HCL es una práctica común. ^[15]

Véase también

• Agrupamiento FLAME
• Análisis de conglomerados
• Algoritmo de maximización de expectativas (un método similar, pero más formalizado estadísticamente)

Referencias

1. "Agrupamiento difuso". reference.wolfram.com . Consultado el 26 de abril de 2016 .
2. Dunn, JC (1 de enero de 1973). "Un pariente difuso del proceso ISODATA y su uso en la detección de cúmulos compactos bien separados". Journal of Cybernetics . 3 (3): 32–57. doi :10.1080/01969727308546046. ISSN  0022-0280.
3. Bezdek, James C. (1981). Reconocimiento de patrones con algoritmos de funciones objetivas difusas . ISBN 0-306-40671-3 . 
4. Alobaid, Ahmad, fuzzycmeans: Fuzzy c-means según el artículo de investigación de James C. Bezdek et. al , consultado el 18 de enero de 2023
5. Dias, Madson, fuzzy-c-means: Una implementación simple en Python del algoritmo Fuzzy C-means. , consultado el 18 de enero de 2023
6. Said, E El-Khamy; Rowayda A Sadek; Mohamed A El-Khoreby (octubre de 2015). "Una detección eficiente de la masa cerebral con C-media difusa basada en clústeres adaptativos y umbralización". Conferencia internacional IEEE de 2015 sobre aplicaciones de procesamiento de señales e imágenes (ICSIPA) : 429–433.
7. "Agrupamiento - C-medias difusas". home.deib.polimi.it . Consultado el 1 de mayo de 2017 .
8. Ben-Dor, Amir; Shamir, Ron; Yakhini, Zohar (1999-10-01). "Agrupamiento de patrones de expresión génica". Revista de biología computacional . 6 (3–4): 281–297. CiteSeerX 10.1.1.34.5341 . doi :10.1089/106652799318274. ISSN  1066-5277. PMID  10582567. 
9. Valafar, Faramarz (1 de diciembre de 2002). "Técnicas de reconocimiento de patrones en el análisis de datos de microarrays". Anales de la Academia de Ciencias de Nueva York . 980 (1): 41–64. Bibcode :2002NYASA.980...41V. CiteSeerX 10.1.1.199.6445 . doi :10.1111/j.1749-6632.2002.tb04888.x. ISSN  1749-6632. PMID  12594081. S2CID  343093. 
10. Valafar F. Técnicas de reconocimiento de patrones en el análisis de datos de microarrays. Anales de la Academia de Ciencias de Nueva York. 1 de diciembre de 2002;980(1):41-64.
11. Ahmed, Mohamed N.; Yamany, Sameh M.; Mohamed, Nevin; Farag, Aly A .; Moriarty, Thomas (2002). "Un algoritmo de C-medias difusas modificado para la estimación del campo de sesgo y la segmentación de datos de resonancia magnética" (PDF) . IEEE Transactions on Medical Imaging . 21 (3): 193–199. CiteSeerX 10.1.1.331.9742 . doi :10.1109/42.996338. PMID  11989844. S2CID  8480349. Archivado desde el original (PDF) el 2011-10-02 . Consultado el 2011-10-02 . .
12. Banerjee, Tanvi (2014). "Reconocimiento de actividad diurna o nocturna a partir de video utilizando técnicas de agrupamiento difuso". IEEE Transactions on Fuzzy Systems . 22 (3): 483–493. CiteSeerX 10.1.1.652.2819 . doi :10.1109/TFUZZ.2013.2260756. S2CID  11606344. 
13. Alireza, Kashani; Kashani, Amir; Milani, Nargess; Akhlaghi, Peyman; Khezri, Kaveh (2008). "Clasificación robusta de colores mediante razonamiento difuso y algoritmos genéticos en las ligas de fútbol RoboCup". RoboCup 2007: Copa del Mundo de Fútbol Robótico XI . Apuntes de clase en Ciencias de la Computación. Vol. 5001. págs. 548–555. doi :10.1007/978-3-540-68847-1_59. ISBN 978-3-540-68846-4. {{cite book}}: |journal=ignorado ( ayuda )
14. "Agrupamiento difuso: MATLAB y Simulink" www.mathworks.com . Consultado el 3 de mayo de 2017 .
15. Lecca, Paola (2011). Enfoques sistémicos en bioinformática y biología de sistemas computacionales . IGI Global. pág. 9. ISBN 9781613504369.