Agrupamiento de datos de alta dimensión

La agrupación de datos de alta dimensión es el análisis de agrupaciones de datos con un número que va desde unas pocas docenas hasta muchos miles de dimensiones . Estos espacios de datos de alta dimensión se encuentran a menudo en áreas como la medicina , donde la tecnología de microarrays de ADN puede producir muchas mediciones a la vez, y la agrupación de documentos de texto , donde, si se utiliza un vector de frecuencia de palabras, el número de dimensiones es igual al tamaño del vocabulario .

Problemas

Es necesario superar cuatro problemas para realizar la agrupación en datos de alta dimensión: ^[1]

• Es difícil pensar en múltiples dimensiones, imposible visualizarlas y, debido al crecimiento exponencial de la cantidad de valores posibles con cada dimensión, la enumeración completa de todos los subespacios se vuelve insoluble a medida que aumenta la dimensionalidad. Este problema se conoce como la maldición de la dimensionalidad .
• El concepto de distancia se vuelve menos preciso a medida que aumenta el número de dimensiones, ya que la distancia entre dos puntos cualesquiera en un conjunto de datos determinado converge. La discriminación del punto más cercano y el más lejano en particular pierde sentido:

${\displaystyle \lim _{d\to \infty }{\frac {dist_{\max }-dist_{\min }}{dist_{\min }}}=0}$

• Un clúster tiene como objetivo agrupar objetos relacionados, en función de las observaciones de los valores de sus atributos. Sin embargo, dada una gran cantidad de atributos, algunos de ellos normalmente no serán significativos para un clúster determinado. Por ejemplo, en el cribado de recién nacidos , un clúster de muestras podría identificar recién nacidos que comparten valores sanguíneos similares, lo que podría dar lugar a conocimientos sobre la relevancia de determinados valores sanguíneos para una enfermedad. Pero para diferentes enfermedades, diferentes valores sanguíneos podrían formar un clúster y otros valores podrían no estar correlacionados. Esto se conoce como el problema de relevancia de características locales : se pueden encontrar diferentes clústeres en diferentes subespacios, por lo que un filtrado global de atributos no es suficiente.
• Dado un gran número de atributos, es probable que algunos atributos estén correlacionados . Por lo tanto, podrían existir grupos en subespacios afines orientados arbitrariamente .

Investigaciones recientes indican que los problemas de discriminación sólo ocurren cuando hay un gran número de dimensiones irrelevantes y que los enfoques de vecino más cercano compartido pueden mejorar los resultados. ^[2]

Aproches

Los enfoques para la agrupación en subespacios afines orientados arbitrariamente o paralelos al eje difieren en cómo interpretan el objetivo general, que es encontrar agrupaciones en datos con alta dimensionalidad. ^[1] Un enfoque general diferente es encontrar agrupaciones basadas en patrones en la matriz de datos, a menudo denominado biclustering , que es una técnica utilizada con frecuencia en bioinformática .

Agrupamiento de subespacios

Ejemplo de espacio 2D con cúmulos de subespacios

La agrupación de subespacios tiene como objetivo buscar grupos en diferentes combinaciones de dimensiones (es decir, subespacios) y, a diferencia de muchos otros enfoques de agrupación, no supone que todos los grupos de un conjunto de datos se encuentren en el mismo conjunto de dimensiones. ^[3] La agrupación de subespacios puede adoptar enfoques de abajo hacia arriba o de arriba hacia abajo. Los métodos de abajo hacia arriba (como CLIQUE) identifican heurísticamente las dimensiones relevantes dividiendo el espacio de datos en una estructura de cuadrícula, seleccionando unidades densas y luego vinculándolas iterativamente si son adyacentes y densas. ^[3]

La imagen adyacente muestra un simple espacio bidimensional en el que se pueden identificar varios conglomerados. En los subespacios unidimensionales, se pueden encontrar los conglomerados (en el subespacio ) y , , (en el subespacio ). no se puede considerar un conglomerado en un (sub)espacio bidimensional, ya que está distribuido de forma demasiado dispersa en el eje. En dos dimensiones, se pueden identificar los dos conglomerados y . ${\displaystyle c_{a}}$ ${\displaystyle \{x\}}$ ${\displaystyle c_{b}}$ ${\displaystyle c_{c}}$ ${\displaystyle c_{d}}$ ${\displaystyle \{y\}}$ ${\displaystyle c_{c}}$ ${\displaystyle x}$ ${\displaystyle c_{ab}}$ ${\displaystyle c_{ad}}$

El problema de la agrupación de subespacios se da por el hecho de que hay diferentes subespacios de un espacio con dimensiones. Si los subespacios no son paralelos a los ejes, es posible un número infinito de subespacios. Por lo tanto, los algoritmos de agrupación de subespacios utilizan algún tipo de heurística para seguir siendo computacionalmente factibles, con el riesgo de producir resultados inferiores. Por ejemplo, la propiedad de cierre hacia abajo (cf. reglas de asociación ) se puede utilizar para construir subespacios de dimensión superior solo mediante la combinación de los de dimensión inferior, ya que cualquier subespacio T que contenga un grupo, dará como resultado un espacio completo S que también contenga ese grupo (es decir, S ⊆ T), un enfoque adoptado por la mayoría de los algoritmos tradicionales como CLIQUE, ^[4] SUBCLU . ^[5] También es posible definir un subespacio utilizando diferentes grados de relevancia para cada dimensión, un enfoque adoptado por iMWK-Means, ^[6] EBK-Modes ^[7] y CBK-Modes. ^[8] ${\displaystyle 2^{d}}$ ${\displaystyle d}$

Agrupamiento proyectado

La agrupación proyectada busca asignar cada punto a un grupo único, pero los grupos pueden existir en diferentes subespacios. El enfoque general consiste en utilizar una función de distancia especial junto con un algoritmo de agrupación regular .

Por ejemplo, el algoritmo PreDeCon verifica qué atributos parecen respaldar una agrupación para cada punto y ajusta la función de distancia de modo que las dimensiones con baja varianza se amplifiquen en la función de distancia. ^[9] En la figura anterior, la agrupación se puede encontrar utilizando DBSCAN con una función de distancia que pone menos énfasis en el eje y, por lo tanto, exagera la baja diferencia en el eje lo suficiente como para agrupar los puntos en una agrupación. ${\displaystyle c_{c}}$ ${\displaystyle x}$ ${\displaystyle y}$

PROCLUS utiliza un enfoque similar con un agrupamiento de k-medoides . ^[10] Se estiman los medoides iniciales y, para cada medoide, se determina el subespacio abarcado por atributos con baja varianza. Se asignan puntos al medoide más cercano, considerando solo el subespacio de ese medoide para determinar la distancia. Luego, el algoritmo procede como el algoritmo PAM regular .

Si la función de distancia pondera los atributos de forma diferente, pero nunca con 0 (y, por lo tanto, nunca descarta atributos irrelevantes), el algoritmo se denomina algoritmo de agrupamiento proyectado "suave" .

Agrupamiento basado en proyecciones

El agrupamiento basado en proyección se basa en una proyección no lineal de datos de alta dimensión en un espacio bidimensional. ^[11] Los métodos de proyección típicos como la incrustación de vecinos estocásticos distribuidos en t (t-SNE), ^[12] o el visualizador de recuperación de vecinos (NerV) ^[13] se utilizan para proyectar datos explícitamente en dos dimensiones sin tener en cuenta los subespacios de dimensión superior a dos y conservando solo los vecindarios relevantes en datos de alta dimensión. En el siguiente paso, se calcula el gráfico de Delaunay ^[14] entre los puntos proyectados y cada vértice entre dos puntos proyectados se pondera con la distancia de alta dimensión entre los puntos de datos de alta dimensión correspondientes. A continuación, se calcula el camino más corto entre cada par de puntos utilizando el algoritmo de Dijkstra . ^[15] Los caminos más cortos se utilizan luego en el proceso de agrupamiento, que implica dos opciones según el tipo de estructura en los datos de alta dimensión. ^[11] Esta elección booleana se puede decidir mirando el mapa topográfico de estructuras de alta dimensión. ^[16] En una evaluación comparativa de 34 métodos de agrupamiento comparables, el agrupamiento basado en proyecciones fue el único algoritmo que siempre pudo encontrar la distancia de alta dimensión o la estructura basada en densidad del conjunto de datos. ^[11] El agrupamiento basado en proyecciones está disponible en el paquete R de código abierto "ProjectionBasedClustering" en CRAN. ^[17]

Agrupamiento basado en Bootstrap

La agregación bootstrap (bagging) se puede utilizar para crear múltiples grupos y agregar los hallazgos. Esto se hace tomando submuestras aleatorias de los datos, realizando un análisis de conglomerados en cada uno de ellos y luego agregando los resultados de los agrupamientos para generar una medida de disimilitud que luego se puede utilizar para explorar y agrupar los datos originales. ^{[18] [19]} Dado que es probable que los datos de alta dimensión tengan muchas características no informativas, se pueden utilizar pesos durante el proceso de bagging para aumentar el impacto de los aspectos más informativos. Esto produce "disimilitudes ABC" que luego se pueden utilizar para explorar y agrupar los datos originales y también para evaluar qué características parecen tener más impacto en la definición de los grupos. ^{[20] [21] [22]}

Enfoques híbridos

No todos los algoritmos intentan encontrar una asignación de clúster única para cada punto o todos los clústeres en todos los subespacios; muchos se conforman con un resultado intermedio, donde se encuentran varios conjuntos de clústeres posiblemente superpuestos, pero no necesariamente exhaustivos. Un ejemplo es FIRES, que es, desde su enfoque básico, un algoritmo de agrupamiento de subespacios, pero utiliza una heurística demasiado agresiva para producir de manera creíble todos los clústeres de subespacios. ^[23] Otro enfoque híbrido es incluir un bucle humano en el algoritmo: la experiencia humana en el dominio puede ayudar a reducir un espacio de búsqueda exponencial a través de la selección heurística de muestras. Esto puede ser beneficioso en el dominio de la salud donde, por ejemplo, los médicos se enfrentan a descripciones de alta dimensión de las condiciones de los pacientes y mediciones sobre el éxito de ciertas terapias. Una cuestión importante en tales datos es comparar y correlacionar las condiciones de los pacientes y los resultados de la terapia junto con combinaciones de dimensiones. El número de dimensiones es a menudo muy grande, en consecuencia, es necesario mapearlas a un número menor de dimensiones relevantes para que sean más susceptibles al análisis experto. Esto se debe a que las dimensiones irrelevantes, redundantes y conflictivas pueden afectar negativamente la eficacia y la eficiencia de todo el proceso analítico. ^[24]

Agrupamiento de correlación

Otro tipo de subespacios se considera en el agrupamiento por correlación (minería de datos) .

Software

• ELKI incluye varios algoritmos de agrupamiento de subespacios y correlaciones
• FCPS incluye más de cincuenta algoritmos de agrupamiento ^[25]

Referencias

1. Kriegel, HP ; Kröger, P.; Zimek, A. (2009). "Agrupamiento de datos de alta dimensión". ACM Transactions on Knowledge Discovery from Data . 3 : 1–58. doi :10.1145/1497577.1497578. S2CID  17363900.
2. Houle, ME; Kriegel, HP ; Kröger, P.; Schubert, E.; Zimek, A. (2010). ¿Pueden las distancias entre vecinos compartidos vencer la maldición de la dimensionalidad? (PDF) . Gestión de bases de datos científicas y estadísticas. Apuntes de clase en informática. Vol. 6187. pág. 482. doi :10.1007/978-3-642-13818-8_34. ISBN 978-3-642-13817-1.
3. Parsons, Lance; Haque, Ehtesham; Liu, Huan (1 de junio de 2004). "Agrupamiento de subespacios para datos de alta dimensión: una revisión". Boletín de exploraciones de la ACM SIGKDD . 6 (1): 90–105. doi :10.1145/1007730.1007731. ISSN  1931-0145.
4. Agrawal, R.; Gehrke, J.; Gunopulos, D.; Raghavan, P. (2005). "Agrupamiento automático de subespacios de datos de alta dimensión". Minería de datos y descubrimiento de conocimiento . 11 : 5–33. CiteSeerX 10.1.1.131.5152 . doi :10.1007/s10618-005-1396-1. S2CID  9289572. 
5. Kailing, K.; Kriegel, HP ; Kröger, P. (2004). Agrupamiento de subespacios conectados por densidad para datos de alta dimensión . Actas de la Conferencia internacional SIAM de 2004 sobre minería de datos. págs. 246. doi : 10.1137/1.9781611972740.23 . ISBN . 978-0-89871-568-2.
6. De Amorim, RC; Mirkin, B. (2012). "Métrica de Minkowski, ponderación de características e inicialización de conglomerados anómalos en el agrupamiento de K-Means". Reconocimiento de patrones . 45 (3): 1061. Bibcode :2012PatRe..45.1061C. doi :10.1016/j.patcog.2011.08.012.
7. Carbonera, Joel Luis; Abel, Mara (noviembre de 2014). "Un algoritmo de agrupamiento de subespacios basado en entropía para datos categóricos". 2014 IEEE 26th International Conference on Tools with Artificial Intelligence . IEEE. págs. 272–277. doi :10.1109/ictai.2014.48. ISBN. 9781479965724.S2CID 7208538  .
8. Carbonera, Joel Luis; Abel, Mara (2015). "CBK-Modes: Un algoritmo basado en correlación para la agrupación de datos categóricos". Actas de la 17.ª Conferencia Internacional sobre Sistemas de Información Empresarial . SCITEPRESS - Publicaciones científicas y tecnológicas. pp. 603–608. doi :10.5220/0005367106030608. ISBN 9789897580963.
9. Böhm, C.; Kailing, K.; Kriegel, H. -P. ; Kröger, P. (2004). Agrupamiento conectado por densidad con preferencias de subespacio local (PDF) . Cuarta Conferencia Internacional IEEE sobre Minería de Datos (ICDM'04). pág. 27. doi :10.1109/ICDM.2004.10087. ISBN 0-7695-2142-8.
10. Aggarwal, CC; Wolf, JL; Yu, PS; Procopiuc, C.; Park, JS (1999). "Algoritmos rápidos para agrupamiento proyectado". ACM SIGMOD Record . 28 (2): 61. CiteSeerX 10.1.1.681.7363 . doi :10.1145/304181.304188. 
11. Thrun, MC, & Ultsch, A. : Uso de agrupamiento basado en proyección para encontrar agrupamientos basados ​​en distancia y densidad en datos de alta dimensión, J. Classif., págs. 1-33, doi: 10.1007/s00357-020-09373-2.
12. Van der Maaten, L., y Hinton, G.: Visualización de datos usando t-SNE, Journal of Machine Learning Research, vol. 9 (11), págs. 2579-2605. 2008.
13. Venna, J., Peltonen, J., Nybo, K., Aidos, H. y Kaski, S.: Perspectiva de recuperación de información para la reducción de dimensionalidad no lineal para visualización de datos, The Journal of Machine Learning Research, vol. 11 , págs. 451-490. 2010.
14. Delaunay, B.: Sur la esfera vide, Izv. Akád. Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk, vol. 7 (793-800), págs.1-2. 1934.
15. Dijkstra, EW: Una nota sobre dos problemas relacionados con gráficos, Numerische mathematik, vol. 1 (1), págs. 269-271. 1959.
16. Thrun, MC, y Ultsch, A.: Descubrimiento de estructuras de alta dimensión de proyecciones a partir de métodos de reducción de dimensionalidad, MethodsX, vol. 7, págs. 101093, doi: 10.1016/j.mex.20200.101093,2020.
17. "CRAN - Agrupamiento basado en proyecciones de paquetes". Archivado desde el original el 17 de marzo de 2018.
18. Dudoit, S. y Fridlyand, J. (2003). Bagging para mejorar la precisión de un procedimiento de agrupamiento. Bioinformática, 19/9, 1090–1099. doi:10.1093/bioinformatics/btg038.
19. Strehl, A. y Ghosh, J. (2002). Conjuntos de clústeres: un marco de reutilización de conocimientos para combinar múltiples particiones. Journal of Machine Learning Research. 3. 583-617. 10.1162/153244303321897735.
20. Amaratunga, D., Cabrera, J. y Kovtun, V. (2008). Aprendizaje de microarrays con ABC. Bioestadística. 9. 128-36. 10.1093/biostatistics/kxm017.
21. Amaratunga, D. y Cabrera, J. y Lee, YS (2014). Medidas de similitud basadas en remuestreo para datos de alta dimensión. Journal of Computational Biology. 22. 10.1089/cmb.2014.0195.
22. Cherkas, Y., Amaratunga, D., Raghavan, N., Sasaki, J. y McMillian, M. (2016). Clasificación de genes ABC para la predicción de colestasis inducida por fármacos en ratas, Toxicology Reports, 3: 252–261.
23. Kriegel, H. ; Kröger, P.; Renz, M.; Wurst, S. (2005). Un marco genérico para la agrupación eficiente de subespacios de datos de alta dimensión (PDF) . Quinta Conferencia Internacional IEEE sobre Minería de Datos (ICDM'05). pág. 250. doi :10.1109/ICDM.2005.5. ISBN 0-7695-2278-5.
24. Hund, M.; Böhm, D.; Sturm, W.; Sedlmair, M.; Schreck, T.; Keim, DA; Majnaric, L.; Holzinger, A. (2016). "Análisis visual para la exploración de conceptos en subespacios de grupos de pacientes: dar sentido a conjuntos de datos complejos con el Doctor-in-the-loop". Informática del cerebro . 3 (4): 233–247. doi :10.1007/s40708-016-0043-5. PMC 5106406 . PMID  27747817. 
25. Thrun, MC y Stier, Q.: Conjunto de algoritmos de agrupamiento fundamental, SoftwareX, vol. 13(C), págs. 100642, doi: 10.1016/j.softx.2020.100642, 2021.