Agrupación de datos de alta dimensión

La agrupación de datos de alta dimensión es el análisis de agrupaciones de datos con 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. el tamaño del vocabulario .

Problemas

Es necesario superar cuatro problemas para agrupar datos de alta dimensión: ^[1]

• Es difícil pensar en múltiples dimensiones, imposible visualizarlas y, debido al crecimiento exponencial del número de valores posibles con cada dimensión, la enumeración completa de todos los subespacios se vuelve intratable 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 crece el número de dimensiones, ya que la distancia entre dos puntos cualesquiera en un conjunto de datos determinado converge. En particular, la discriminación entre el punto más cercano y el más lejano deja de tener sentido:

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

• Un grupo está destinado a agrupar objetos que están relacionados, basándose en observaciones de los valores de sus atributos. Sin embargo, dada una gran cantidad de atributos, algunos de ellos generalmente no serán significativos para un grupo determinado. Por ejemplo, en el cribado neonatal, un grupo de muestras podría identificar a recién nacidos que comparten valores sanguíneos similares, lo que podría conducir a conocimientos sobre la relevancia de ciertos valores sanguíneos para una enfermedad. Pero para diferentes enfermedades, diferentes valores sanguíneos podrían formar un grupo y otros valores podrían no estar correlacionados. Esto se conoce como problema de relevancia de características locales : se pueden encontrar diferentes grupos en diferentes subespacios, por lo que un filtrado global de atributos no es suficiente.
• Dada una gran cantidad de atributos, es probable que algunos atributos estén correlacionados . Por lo tanto, los grupos podrían existir 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]

Enfoques

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

Agrupación subespacial

Ejemplo de espacio 2D con grupos subespaciales

La agrupación subespacial tiene como objetivo buscar agrupaciones en diferentes combinaciones de dimensiones (es decir, subespacios) y, a diferencia de muchos otros enfoques de agrupación, no supone que todas las agrupaciones de un conjunto de datos se encuentren en el mismo conjunto de dimensiones. ^[3] La agrupación subespacial puede adoptar enfoques ascendentes o descendentes. Los métodos ascendentes (como CLIQUE) identifican heurísticamente 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 mero espacio bidimensional donde se pueden identificar varios grupos. En los subespacios unidimensionales, se pueden encontrar los grupos (en el subespacio ) y , (en el subespacio ) . no puede considerarse un grupo en un (sub)espacio bidimensional, ya que está demasiado dispersamente distribuido en el eje. En dos dimensiones, se pueden identificar los dos grupos 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 viene dado por el hecho de que existen 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 agrupamiento subespacial utilizan algún tipo de heurística para seguir siendo computacionalmente factibles, a riesgo de producir resultados inferiores. Por ejemplo, la propiedad de cierre descendente (cf. reglas de asociación ) se puede utilizar para construir subespacios de dimensiones superiores sólo combinando los de dimensiones inferiores, ya que cualquier subespacio T que contenga un grupo dará como resultado un espacio completo S que también contendrá ese cluster (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}$

Agrupación proyectada

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

Por ejemplo, el algoritmo PreDeCon verifica qué atributos parecen admitir 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, el grupo se puede encontrar usando 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 un grupo. ${\displaystyle c_{c}}$ ${\displaystyle x}$ ${\displaystyle y}$

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

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

Agrupación basada en proyecciones

La agrupación basada en proyecciones 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 preservar solo 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 partir de entonces, 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 agrupación, que implica dos opciones dependiendo del 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 fue capaz de encontrar la distancia de alta dimensión o la estructura basada en la densidad del conjunto de datos. ^[11] Se puede acceder a la agrupación en clústeres basada en proyecciones en el paquete R de código abierto "ProjectionBasedClustering" en CRAN. ^[17]

Agrupación basada en Bootstrap

La agregación Bootstrap (empaquetado) se puede utilizar para crear múltiples clústeres y agregar los hallazgos. Esto se hace tomando submuestras aleatorias de los datos, realizando un análisis de conglomerados en cada una de ellas y luego agregando los resultados de los agrupamientos para generar una medida de disimilitud que luego puede usarse 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 embolsado para aumentar el impacto de los aspectos más informativos. Esto produce "diferencias ABC" que luego pueden usarse 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 grupo única para cada punto o todos los grupos en todos los subespacios; muchos se conforman con un resultado intermedio, donde se encuentran varios grupos de grupos posiblemente superpuestos, pero no necesariamente exhaustivos. Un ejemplo es FIRES, que desde su enfoque básico es un algoritmo de agrupación subespacial, pero utiliza una heurística demasiado agresiva para producir de manera creíble todas las agrupaciones subespaciales. ^[23] Otro enfoque híbrido es incluir un ser humano en el bucle algorítmico: la experiencia en el dominio humano puede ayudar a reducir un espacio de búsqueda exponencial mediante la selección heurística de muestras. Esto puede resultar beneficioso en el ámbito de la salud donde, por ejemplo, los médicos se enfrentan a descripciones detalladas de las condiciones de los pacientes y mediciones del éxito de determinadas terapias. Una cuestión importante en dichos datos es comparar y correlacionar las condiciones del paciente y los resultados de la terapia junto con combinaciones de dimensiones. El número de dimensiones suele ser muy grande, por lo que es necesario asignarlas a un número menor de dimensiones relevantes para que sean más susceptibles al análisis de expertos. Esto se debe a que dimensiones irrelevantes, redundantes y conflictivas pueden afectar negativamente la efectividad y eficiencia de todo el proceso analítico. ^[24]

Agrupación de correlación

Otro tipo de subespacios se considera en el clustering de correlación (Minería de datos) .

Software

• ELKI incluye varios algoritmos de agrupamiento de correlación y subespacio
• FCPS incluye más de cincuenta algoritmos de agrupamiento ^[25]

Referencias

1. Kriegel, HP ; Kröger, P.; Zimek, A. (2009). "Agrupación de datos de alta dimensión". Transacciones ACM sobre descubrimiento de conocimiento a partir de datos . 3 : 1–58. doi :10.1145/1497577.1497578. S2CID  17363900.
2. Houle, YO; Kriegel, HP ; Kröger, P.; Schubert, E.; Zimek, A. (2010). ¿Pueden las distancias entre vecinos compartidos derrotar la maldición de la dimensionalidad? (PDF) . Gestión de Bases de Datos Científicas y Estadísticas. Apuntes de conferencias sobre 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). "Agrupación subespacial para datos de alta dimensión: una revisión". Boletín de exploraciones de ACM SIGKDD . 6 (1): 90-105. doi :10.1145/1007730.1007731. ISSN  1931-0145.
4. Agrawal, R.; Gehrke, J.; Gunópulos, D.; Raghavan, P. (2005). "Agrupación subespacial automática de datos de alta dimensión". Minería de datos y descubrimiento de conocimientos . 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). "Agrupación subespacial conectada 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 clúster anómalo en agrupación de K-Means". Reconocimiento de patrones . 45 (3): 1061. Código bibliográfico : 2012PatRe..45.1061C. doi :10.1016/j.patcog.2011.08.012.
7. Carbonera, Joel Luis; Abel, Mara (noviembre de 2014). "Un algoritmo de agrupación subespacial basado en entropía para datos categóricos". 2014 IEEE 26ª Conferencia Internacional sobre Herramientas con Inteligencia Artificial . IEEE. págs. 272-277. doi :10.1109/ictai.2014.48. ISBN 9781479965724. S2CID  7208538.
8. Carbonera, Joel Luis; Abel, María (2015). "Modos CBK: un algoritmo basado en correlación para agrupación de datos categóricos". Actas de la 17ª Conferencia Internacional sobre Sistemas de Información Empresarial . SCITEPRESS - Publicaciones de ciencia y tecnología. págs. 603–608. doi :10.5220/0005367106030608. ISBN 9789897580963.
9. Böhm, C.; Kailing, K.; Kriegel, H.-P. ; Kröger, P. (2004). Agrupación conectada por densidad con preferencias de subespacio local (PDF) . Cuarta Conferencia Internacional IEEE sobre Minería de Datos (ICDM'04). pag. 27. doi : 10.1109/ICDM.2004.10087. ISBN 0-7695-2142-8.
10. Aggarwal, CC; Lobo, JL; Yu, PD; Procopiuc, C.; Parque, JS (1999). "Algoritmos rápidos para agrupamiento proyectado". Registro ACM SIGMOD . 28 (2): 61. CiteSeerX 10.1.1.681.7363 . doi :10.1145/304181.304188. 
11. Thrun, MC y Ultsch, A.: Uso de agrupaciones basadas en proyecciones para encontrar agrupaciones basadas 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 mediante 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 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 proyecciones de alta dimensión 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 - Paquete ProjectionBasedClustering". Archivado desde el original el 17 de marzo de 2018.
18. Dudoit, S. y Fridlyand, J. (2003). Embolsado para mejorar la precisión de un procedimiento de agrupación. Bioinformática, 19/9, 1090–1099. doi:10.1093/bioinformática/btg038.
19. Strehl, A. y Ghosh, J. (2002). Conjuntos de clústeres: un marco de reutilización de conocimientos para combinar múltiples particiones. Revista de investigación sobre aprendizaje automático. 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/bioestadística/kxm017.
21. Amaratunga, D. y Cabrera, J. y Lee, YS (2014). Medidas de similitud basadas en remuestreo para datos de alta dimensión. Revista de biología computacional. 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 subespacial eficiente de datos de alta dimensión (PDF) . Quinta Conferencia Internacional IEEE sobre Minería de Datos (ICDM'05). pag. 250. doi :10.1109/ICDM.2005.5. ISBN 0-7695-2278-5.
24. Perro, 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 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 agrupación en clústeres fundamentales, SoftwareX, vol. 13(C), págs. 100642, doi: 10.1016/j.softx.2020.100642, 2021.