Agrupación de datos de alta dimensión

El agrupamiento de subespacios tiene como objetivo buscar clústeres en diferentes combinaciones de dimensiones (es decir, subespacios) y, a diferencia de muchos otros enfoques de agrupamiento, no asume que todos los clústeres en un conjunto de datos se encuentren en el mismo conjunto de dimensiones. ^{[ 3 ]} El agrupamiento de subespacios puede adoptar enfoques ascendentes o descendentes. Los métodos ascendentes (como CLIQUE) identifican heurísticamente las dimensiones relevantes dividiendo el espacio de datos en una estructura de cuadrícula, seleccionando unidades densas y luego enlazándolas iterativamente si son adyacentes y densas. ^{[ 3 ]}

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

El problema de la agrupación de subespacios viene dado por el hecho de que hay${\displaystyle 2^{d}}$diferentes subespacios de un espacio con${\displaystyle d}$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 de subespacios 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 ) puede utilizarse para construir subespacios de dimensiones superiores solo combinando subespacios de dimensiones inferiores, ya que cualquier subespacio T que contenga un clúster, dará como resultado un espacio completo S que también contendrá ese clúster (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 ]}

El agrupamiento proyectado busca asignar cada punto a un clúster único, pero los clústeres pueden existir en diferentes subespacios. El enfoque general consiste en utilizar una función de distancia especial junto con un algoritmo de agrupamiento regular .

Por ejemplo, el algoritmo PreDeCon comprueba qué atributos parecen respaldar una agrupación para cada punto y ajusta la función de distancia de manera que las dimensiones con baja varianza se amplifiquen en la función de distancia. ^{[ 9 ]} En la figura anterior, el clúster${\displaystyle c_{c}}$podría encontrarse utilizando DBSCAN con una función de distancia que pone menos énfasis en el${\displaystyle x}$eje y por lo tanto exagera la baja diferencia en el${\displaystyle y}$-eje suficientemente suficiente para agrupar los puntos en un clúster.

PROCLUS utiliza un enfoque similar con un agrupamiento k-medoid . ^{[ 10 ]} Se estiman los medoides iniciales y, para cada medoide, se determina el subespacio generado por los atributos con baja varianza. Se asignan puntos al medoide más cercano, considerando únicamente el subespacio de dicho medoide para determinar la distancia. El algoritmo procede entonces como el algoritmo PAM convencional.

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

La agrupación basada 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 t-distributed stochastic neighbor embedding (t-SNE), ^{[ 12 ]} o neighbor retrieval visualizer (NerV) ^{[ 13 ]} se utilizan para proyectar datos explícitamente en dos dimensiones, ignorando los subespacios de dimensión superior a dos y preservando solo vecindarios relevantes en datos de alta dimensión. En el siguiente paso, se calcula el grafo 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. Posteriormente, 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 puede decidirse observando 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 proyección fue el único algoritmo que siempre pudo encontrar la estructura de alta dimensión basada en distancia o densidad del conjunto de datos. ^{[ 11 ]} El agrupamiento basado en proyección está disponible en el paquete de R de código abierto "ProjectionBasedClustering" en CRAN. ^{[ 17 ]}

La agregación bootstrap (bagging) se puede utilizar para crear múltiples clústeres y agregar los resultados. Esto se hace tomando submuestras aleatorias de los datos, realizando un análisis de clúster en cada una de ellas y luego agregando los resultados de los clústeres 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 ponderaciones 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 ser más impactantes en la definición de los clústeres. ^{[ 20 ] [ 21 ] [ 22 ]}

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 encuentra un conjunto de clústeres que posiblemente se superpongan, pero no necesariamente sean exhaustivos. Un ejemplo es FIRES, que desde su enfoque básico es 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 humano en el bucle algorítmico: la experiencia humana en el dominio puede ayudar a reducir un espacio de búsqueda exponencial mediante 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 dimensionalidad de las condiciones de los pacientes y mediciones sobre el éxito de ciertas terapias. Una pregunta importante en dichos 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 suele ser muy grande, por lo que es necesario mapearlas a un número menor de dimensiones relevantes para que sean más adecuadas para el análisis de expertos. Esto se debe a que las dimensiones irrelevantes, redundantes y conflictivas pueden afectar negativamente la efectividad y la eficiencia de todo el proceso analítico. ^{[ 24 ]}

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