¿Cómo sé que mi algoritmo de agrupación k-means sufre la maldición de la dimensionalidad?

Question

Creo que el título de esta pregunta lo dice todo.

Answer 1

Ayuda a pensar en lo que La maldición de la dimensionalidad es. Hay varios hilos muy buenos sobre CV que vale la pena leer. Aquí hay un lugar para empezar: Explicar la "maldición de la dimensionalidad" a un niño .

Observo que está interesado en cómo se aplica esto a $k$ -significa clustering. Hay que tener en cuenta que $k$ -means es una estrategia de búsqueda para minimizar (sólo) la distancia euclidiana al cuadrado. A la luz de esto, vale la pena pensar en cómo la distancia euclidiana se relaciona con la maldición de la dimensionalidad (ver: ¿Por qué la distancia euclidiana no es una buena métrica en dimensiones altas? ).

La respuesta breve de estos hilos es que el volumen (tamaño) del espacio aumenta a un ritmo increíble en relación con el número de dimensiones. Incluso $10$ dimensiones (que no me parece que sea muy "alta dimensión") puede provocar la maldición. Si los datos se distribuyeran uniformemente en ese espacio, todos los objetos serían aproximadamente equidistantes entre sí. Sin embargo, como señala @Anony-Mousse en su responder A esta pregunta, este fenómeno depende de cómo estén dispuestos los datos en el espacio; si no son uniformes, no se tiene necesariamente este problema. Esto nos lleva a preguntarnos si los datos de alta dimensión distribuidos uniformemente son muy comunes (véase: ¿Existe realmente la "maldición de la dimensionalidad" en los datos reales? ).

Yo diría que lo que importa no es necesariamente el número de variables (la dimensionalidad literal de sus datos), sino la dimensionalidad efectiva de sus datos. Bajo el supuesto de que $10$ dimensiones es "demasiado alta" para $k$ -significa que la estrategia más sencilla sería contar el número de características que tiene. Pero si se quiere pensar en términos de dimensionalidad efectiva, se puede realizar un análisis de componentes principales (PCA) y observar cómo caen los valores propios. Es bastante común que la mayor parte de la variación exista en un par de dimensiones (que normalmente atraviesan las dimensiones originales de su conjunto de datos). Eso implicaría que es menos probable que tenga un problema con $k$ -significa en el sentido de que su dimensionalidad efectiva es en realidad mucho menor.

Un enfoque más complicado sería examinar la distribución de las distancias entre pares en su conjunto de datos según lo que sugiere @hxd1011 en su responder . Observar las distribuciones marginales simples le dará alguna pista sobre la posible uniformidad. Si se normalizan todas las variables para que estén dentro del intervalo $[0,\ 1]$ las distancias entre pares deben estar dentro del intervalo $[0,\ \sqrt{\sum D}]$ . Las distancias muy concentradas causarán problemas; por otro lado, una distribución multimodal puede ser esperanzadora (puedes ver un ejemplo en mi respuesta aquí: ¿Cómo utilizar conjuntamente variables binarias y continuas en la agrupación? ).

Sin embargo, si $k$ -significa que "funcionará" sigue siendo una cuestión complicada. Bajo el supuesto de que hay agrupaciones latentes significativas en sus datos, no necesariamente existen en todas sus dimensiones o en las dimensiones construidas que maximizan la variación (es decir, los componentes principales). Las agrupaciones podrían estar en las dimensiones de menor variación (véase: Ejemplos de PCA en los que las PC con baja varianza son "útiles" ). Es decir, podría tener conglomerados con puntos que están cerca dentro y bien separados entre sí en sólo algunas de sus dimensiones o en PC de baja variación, pero que no son ni remotamente similares en PC de alta variación, lo que causaría $k$ -significa ignorar los clústeres que se buscan y elegir en su lugar clústeres falsos (algunos ejemplos pueden verse aquí: Cómo entender los inconvenientes de K-means ).

Answer 2

Mi respuesta no se limita a K-means, sino que comprueba si tenemos maldición de la dimensionalidad para cualquier método basado en la distancia. K-means se basa en una medida de distancia (por ejemplo, la distancia euclidiana)

Antes de ejecutar el algoritmo, podemos comprobar la distribución de las métricas de distancia, es decir, todas las métricas de distancia para todos los pares de datos. Si tiene $N$ puntos de datos, debería tener $0.5\cdot N\cdot(N-1)$ métrica de la distancia. Si los datos son demasiado grandes, podemos comprobar una muestra de los mismos.

Si tenemos el problema de la maldición de la dimensionalidad, lo que verás es que estos valores están muy cerca unos de otros. Esto parece muy contra-intuitivo, porque significa que cada uno está cerca o lejos de cada uno y la medida de distancia es básicamente inútil.

---

A continuación, una simulación para mostrar estos resultados contraintuitivos. Si todas las características están distribuidas uniformemente, y si hay demasiadas dimensiones, cada métrica de distancia debería estar cerca de $\frac 1 6$ que viene de $\int_{x_i=0}^1\int_{x_j=0}^1 (x_i-x_j)^2 dx_i dx_j$ . Siéntase libre de cambiar la distribución uniforme por otras distribuciones. Por ejemplo, si cambiamos a la distribución normal (cambiar runif a rnorm ), convergerá a otro número con grandes dimensiones numéricas.

Aquí está la simulación para la dimensión de 1 a 500, las características son la distribución uniforme de 0 a 1.

plot(0, type="n",xlim=c(0,0.5),ylim=c(0,50))
abline(v=1/6,lty=2,col=2)
grid()

n_data=1e3
for (p in c(1:5,10,15,20,25,50,100,250,500)){
    x=matrix(runif(n_data*p),ncol=p)
    all_dist=as.vector(dist(x))^2/p
    lines(density(all_dist))
}