¿Cuál es la relación entre el clustering k-means y el PCA?

Question

Es una práctica común aplicar PCA (análisis de componentes principales) antes de un algoritmo de clustering (como k-means). Se cree que mejora los resultados de agrupación en la práctica (reducción de ruido).

Sin embargo, estoy interesado en un estudio comparativo y profundo de la relación entre PCA y k-means. Por ejemplo, Chris Ding y Xiaofeng He, 2004, K-means Clustering via Principal Component Analysis mostraron que "los componentes principales son soluciones continuas a los indicadores de membresía de clúster discretos para el clustering de K-means". Sin embargo, me resulta difícil entender este documento, y Wikipedia realmente afirma que está equivocado.

Además, los resultados de los dos métodos son algo diferentes en el sentido de que PCA ayuda a reducir el número de "características" mientras preserva la varianza, mientras que la agrupación reduce el número de "puntos de datos" resumiendo varios puntos por sus expectativas/medias (en el caso de k-means). Entonces, si el conjunto de datos consiste en $N$ puntos con $T$ características cada uno, PCA tiene como objetivo comprimir las $T$ características mientras que la agrupación tiene como objetivo comprimir los $N$ puntos de datos.

Estoy buscando una explicación sencilla de las relaciones entre estas dos técnicas + algunos artículos técnicos relacionados con las dos técnicas.

Answer 1

Es cierto que el clustering de K-means y el PCA parecen tener objetivos muy diferentes y a primera vista no parecen estar relacionados. Sin embargo, como se explica en el artículo de Ding & He 2004 Agrupación de K-means mediante el análisis de componentes principales Hay una profunda conexión entre ellos.

La intuición es que el ACP busca representar todos los $n$ vectores de datos como combinaciones lineales de un pequeño número de vectores propios, y lo hace para minimizar el error medio de reconstrucción al cuadrado. En cambio, K-means trata de representar todos los $n$ vectores de datos a través de un pequeño número de centroides de clúster, es decir, representarlos como combinaciones lineales de un pequeño número de vectores de centroides de clúster, donde los pesos de la combinación lineal deben ser todos nulos, excepto el único $1$ . Esto también se hace para minimizar el error medio de reconstrucción al cuadrado.

Por lo tanto, K-means puede verse como un PCA superespeso.

El documento de Ding y He precisa esta conexión.

---

Desgraciadamente, el artículo de Ding y He contiene algunas formulaciones descuidadas (en el mejor de los casos) y puede ser fácilmente malinterpretado. Por ejemplo, podría parecer que Ding y He afirman haber demostrado que los centros de los clusters de la solución de clustering de K-means se encuentran en el $(K-1)$ -subespacio PCA:

Teorema 3.3. El subespacio del centroide del clúster está abarcado por el primer $K-1$ direcciones principales [...].

Para $K=2$ esto implicaría que las proyecciones en el eje PC1 serán necesariamente negativas para un cluster y positivas para otro cluster, es decir, el eje PC2 separará perfectamente los clusters.

Se trata de un error o de una redacción descuidada; en cualquier caso, tomada literalmente, esta afirmación concreta es falsa.

Empecemos por ver algunos ejemplos de juguetes en 2D para $K=2$ . Generé algunas muestras de las dos distribuciones normales con la misma matriz de covarianza pero con medias diferentes. A continuación, ejecuté tanto K-means como PCA. La siguiente figura muestra el gráfico de dispersión de los datos de arriba, y los mismos datos coloreados según la solución de K-means de abajo. También muestro la primera dirección principal como una línea negra y los centros de clase encontrados por K-means con cruces negras. El eje PC2 se muestra con la línea negra discontinua. K-means se repitió $100$ veces con semillas aleatorias para asegurar la convergencia al óptimo global.

Se puede ver claramente que, aunque los centroides de las clases tienden a estar bastante cerca de la primera dirección del PC, lo hacen no caer en ella exactamente. Además, aunque el eje PC2 separa perfectamente los conglomerados en las subparcelas 1 y 4, hay un par de puntos en el lado equivocado de éste en las subparcelas 2 y 3.

Así que la concordancia entre K-means y PCA es bastante buena, pero no es exacta.

¿Qué han demostrado Ding y He? Para simplificar, sólo consideraré $K=2$ caso. Sea el número de puntos asignados a cada cluster $n_1$ y $n_2$ y el número total de puntos $n=n_1+n_2$ . Siguiendo a Ding y He, definamos vector de indicadores de cluster $\mathbf q\in\mathbb R^n$ de la siguiente manera: $q_i = \sqrt{n_2/nn_1}$ si $i$ -ésimos puntos pertenecen al clúster 1 y $q_i = -\sqrt{n_1/nn_2}$ si pertenece al clúster 2. El vector indicador de clústeres tiene longitud unitaria $\|\mathbf q\| = 1$ y está "centrado", es decir, sus elementos suman cero $\sum q_i = 0$ .

Ding y He demuestran que la función de pérdida K-means $\sum_k \sum_i (\mathbf x_i^{(k)} - \boldsymbol \mu_k)^2$ (que el algoritmo K-means minimiza), donde $x_i^{(k)}$ es el $i$ -ésimo elemento en el clúster $k$ se puede reescribir de forma equivalente como $-\mathbf q^\top \mathbf G \mathbf q$ , donde $\mathbf G$ es el $n\times n$ Matriz Gram de productos escalares entre todos los puntos: $\mathbf G = \mathbf X_c \mathbf X_c^\top$ , donde $\mathbf X$ es el $n\times 2$ matriz de datos y $\mathbf X_c$ es la matriz de datos centrada.

(Nota: estoy utilizando una notación y una terminología que difiere ligeramente de la de su documento, pero que me parece más clara).

Así que la solución K-means $\mathbf q$ es un vector unitario centrado que maximiza $\mathbf q^\top \mathbf G \mathbf q$ . Es fácil demostrar que el primer componente principal (cuando se normaliza para tener una suma de cuadrados unitaria) es el vector propio principal de la matriz de Gram, es decir, también es un vector unitario centrado $\mathbf p$ maximizando $\mathbf p^\top \mathbf G \mathbf p$ . La única diferencia es que $\mathbf q$ se limita además a tener sólo dos valores diferentes, mientras que $\mathbf p$ no tiene esta restricción.

En otras palabras, K-means y PCA maximizan la misma función objetivo con la única diferencia de que K-means tiene una restricción "categórica" adicional.

Es lógico que la mayoría de las veces las soluciones de K-means (con restricciones) y de PCA (sin restricciones) se acerquen bastante entre sí, como vimos anteriormente en la simulación, pero no hay que esperar que sean idénticas. Tomando $\mathbf p$ y poniendo todos sus elementos negativos a la altura de $-\sqrt{n_1/nn_2}$ y todos sus elementos positivos a $\sqrt{n_2/nn_1}$ generalmente no dar exactamente $\mathbf q$ .

Ding y He parecen entenderlo bien porque formulan su teorema como sigue:

Teorema 2.2. Para la agrupación de K-means donde $K= 2$ la solución continua del vector indicador de cluster es el [primer] componente principal

Nótese que las palabras "solución continua". Después de demostrar este teorema, comentan además que el PCA puede utilizarse para inicializar las iteraciones de K-means, lo que tiene todo el sentido del mundo, dado que esperamos $\mathbf q$ para estar cerca de $\mathbf p$ . Pero todavía hay que realizar las iteraciones, porque no son idénticas.

Sin embargo, Ding y He desarrollan a continuación un tratamiento más general para $K>2$ y terminamos formulando el Teorema 3.3 como

Teorema 3.3. El subespacio del centroide del clúster está abarcado por el primer $K-1$ direcciones principales [...].

No he repasado las matemáticas de la sección 3, pero creo que este teorema también se refiere a la "solución continua" de K-means, es decir, su enunciado debería decir "el espacio del centroide del clúster de la solución continua de K-means se extiende [...]".

Sin embargo, Ding y He no hacen esta importante salvedad, y además escriben en su resumen que

Aquí demostramos que los componentes principales son las soluciones continuas soluciones a los indicadores discretos de pertenencia a un clúster indicadores de pertenencia a clusters para clustering de K-means. De forma equivalente, mostramos que el subespacio abarcado por los centroides de los clusters vienen dados por la expansión espectral de la matriz de covarianza de los datos truncada en $K-1$ términos.

La primera frase es absolutamente correcta, pero la segunda no. No me queda claro si se trata de una redacción (muy) descuidada o de un auténtico error. He enviado un correo electrónico muy educado a ambos autores pidiendo aclaraciones. (Actualización dos meses después: no me han contestado).

---

Código de simulación Matlab

figure('Position', [100 100 1200 600])

n = 50;
Sigma = [2 1.8; 1.8 2];

for i=1:4
    means = [0 0; i*2 0];

    rng(42)
    X = [bsxfun(@plus, means(1,:), randn(n,2) * chol(Sigma)); ...
         bsxfun(@plus, means(2,:), randn(n,2) * chol(Sigma))];
    X = bsxfun(@minus, X, mean(X));
    [U,S,V] = svd(X,0);
    [ind, centroids] = kmeans(X,2, 'Replicates', 100);

    subplot(2,4,i)
    scatter(X(:,1), X(:,2), [], [0 0 0])

    subplot(2,4,i+4)
    hold on
    scatter(X(ind==1,1), X(ind==1,2), [], [1 0 0])
    scatter(X(ind==2,1), X(ind==2,2), [], [0 0 1])
    plot([-1 1]*10*V(1,1), [-1 1]*10*V(2,1), 'k', 'LineWidth', 2)
    plot(centroids(1,1), centroids(1,2), 'w+', 'MarkerSize', 15, 'LineWidth', 4)
    plot(centroids(1,1), centroids(1,2), 'k+', 'MarkerSize', 10, 'LineWidth', 2)
    plot(centroids(2,1), centroids(2,2), 'w+', 'MarkerSize', 15, 'LineWidth', 4)
    plot(centroids(2,1), centroids(2,2), 'k+', 'MarkerSize', 10, 'LineWidth', 2)

    plot([-1 1]*5*V(1,2), [-1 1]*5*V(2,2), 'k--')
end

for i=1:8
    subplot(2,4,i)
    axis([-8 8 -8 8])
    axis square
    set(gca,'xtick',[],'ytick',[])
end

Answer 2

PCA y K-means hacen cosas diferentes.

PCA se utiliza para reducción de dimensionalidad / selección de características / aprendizaje de representación, por ejemplo cuando el espacio de características contiene demasiadas características irrelevantes o redundantes. El objetivo es encontrar la dimensionalidad intrínseca de los datos.

Aquí tienes un ejemplo bidimensional que se puede generalizar a espacios de dimensiones superiores. El conjunto de datos tiene dos características, $x$ y $y$, cada círculo es un punto de datos.

En la imagen, $v1$ tiene una magnitud mayor que $v2$. Estos son los autovectores. La dimensión de los datos se reduce de dos dimensiones a una dimensión (no hay mucha elección en este caso) y esto se hace proyectando en la dirección del vector $v2$ (después de una rotación donde $v2$ se vuelve paralelo o perpendicular a uno de los ejes). Esto se debe a que $v2$ es ortogonal a la dirección de mayor varianza. Una forma de pensarlo es como una pérdida mínima de información. (Todavía hay una pérdida ya que se pierde un eje de coordenadas).

K-means es un algoritmo de agrupamiento que devuelve la agrupación natural de puntos de datos, basada en su similitud. Es un caso especial de Modelos de Mezcla Gaussiana.

En la imagen a continuación, el conjunto de datos tiene tres dimensiones. Se puede ver en la gráfica 3D a la izquierda que la dimensión $X$ se puede 'eliminar' sin perder mucha información. PCA se utiliza para proyectar los datos a dos dimensiones. En la figura de la izquierda, también se muestra el plano de proyección. Luego, K-means se puede utilizar en los datos proyectados para etiquetar los diferentes grupos, en la figura de la derecha, codificados con diferentes colores.

PCA u otras técnicas de reducción de dimensionalidad se utilizan antes de los métodos supervisados o no supervisados en aprendizaje automático. Además de las razones mencionadas por ti y las que mencioné anteriormente, también se utiliza con fines de visualización (proyección a 2D o 3D desde dimensiones superiores).

En cuanto al artículo, no creo que haya ninguna conexión, PCA no tiene información sobre la agrupación natural de datos y opera en todos los datos, no en subconjuntos (grupos). Si algunos grupos pueden explicarse por un autovector (solo porque ese cluster en particular se extiende a lo largo de esa dirección) es solo una coincidencia y no debe tomarse como una regla general.

"PCA tiene como objetivo comprimir las T características mientras que el clustering tiene como objetivo comprimir los N puntos de datos."

De hecho, la compresión es una forma intuitiva de pensar en PCA. Sin embargo, en K-means, para describir cada punto en relación a su cluster, aún necesitas al menos la misma cantidad de información (por ejemplo, dimensiones) $x_i = d(\mu_i, \delta_i)$, donde $d$ es la distancia y $\delta_i$ se almacena en lugar de $x_i$. Y también necesitas almacenar el $\mu_i$ para saber a qué se refiere el delta. Por supuesto, puedes almacenar $d$ e $i`, sin embargo, no podrás recuperar la información real en los datos.

El clustering realmente agrega información. Yo lo veo como dividir los datos en grupos naturales (que no necesariamente tienen que ser disjuntos) sin saber qué significa la etiqueta de cada grupo (bueno, hasta que mires los datos dentro de los grupos).

Answer 3

Es común blanquear los datos antes de utilizar k-means. La razón es que k-means es extremadamente sensible a la escala, y cuando tienes atributos mixtos ya no hay una escala "verdadera". Entonces tienes que normalizar, estandarizar o blanquear tus datos. Ninguna es perfecta, pero blanquear eliminará la correlación global que a veces puede dar mejores resultados. PCA/blanqueo es $O(n\cdot d^2 + d^3)$ porque se opera sobre la matriz de covarianza.

Según mi entendimiento, la relación de k-means con PCA no es sobre los datos originales. Es aplicar PCA a la matriz de distancias (que tiene $n^2$ entradas, y hacer un PCA completo es $O(n^2\cdot d+n^3)$ - es decir, prohibitivamente caro, en particular en comparación con k-means que es $O(k\cdot n \cdot i\cdot d)$ donde $n$ es el único término grande), y tal vez solo para $k=2$. K-means es un problema de optimización de mínimos cuadrados, al igual que PCA. k-means intenta encontrar la partición de mínimos cuadrados de los datos. PCA encuentra el vector de membresía de clúster de mínimos cuadrados.

El primer eigenvector tiene la mayor varianza, por lo tanto, dividir en este vector (que se asemeja a la membresía de clúster, no a las coordenadas de los datos de entrada!) significa maximizar la varianza entre clústeres. Al maximizar la varianza entre clústeres, también se minimiza la varianza dentro de los clústeres.

Pero para problemas reales, esto es inútil. Solo es de interés teórico.

Answer 4

Relación intuitiva de PCA y KMeans

0. Teóricamente, el análisis dimensional de PCA (las primeras K dimensiones que retienen, por ejemplo, el 90% de la varianza... no necesita tener una relación directa con los clusters de K Means), sin embargo, el valor de usar PCA proviene de a) consideraciones prácticas dadas la naturaleza de los objetos que analizamos tienden a agruparse naturalmente alrededor / evolucionar a partir de (un cierto segmento de) sus componentes principales (edad, género...) b) PCA elimina esas dimensiones de baja varianza (ruido), por lo que agrega valor (y de alguna manera similar a la agrupación) al enfocarse en esas dimensiones clave En términos sencillos, es como decir que los ejes X-Y nos ayudan a dominar cualquier concepto matemático abstracto pero de una manera más avanzada.

1. KMeans intenta minimizar la distancia general dentro de un cluster para un K dado

2. Para un conjunto de objetos con parámetros de N dimensiones, por defecto, objetos similares tendrán la MAYORÍA de los parámetros "similares" excepto unas pocas diferencias clave (por ejemplo, un grupo de jóvenes estudiantes de TI, bailarines jóvenes, humanos... tendrán algunas características altamente similares (baja varianza) pero algunas características clave aún bastante diversas y capturar esas "Componentes Principales" clave esencialmente captura la mayoría de la varianza, por ejemplo, color, área de residencia.... Por lo tanto, baja distorsión si delgamos esas características de diferencias menores, o la conversión a PCs más bajos no perderá mucha información

3. Es "muy probable" y "muy natural" agruparlos para ver las diferencias (variaciones) tiene sentido para la evaluación de datos (por ejemplo, si realizas 1,000 encuestas en una semana en la calle principal, agruparlas basadas en la etnia, edad o antecedentes educativos como PC tiene sentido) Bajo la misión de K Means, intentamos establecer un número justo de K para que los elementos del grupo (en un cluster) tengan la menor distancia general (minimizada) entre el Centroid y mientras que el costo de establecer y ejecutar los K clusters sea óptimo (cada miembro como un cluster no tiene sentido ya que sería muy costoso de mantener y no tendría valor)

4. El agrupamiento de KMeans podría ser fácilmente "inspeccionado visualmente" para ser óptimo, si ese K está a lo largo de las Componentes Principales (por ejemplo, si para personas en diferentes edades, grupos étnicos/religiosos tienden a expresar opiniones similares, entonces si agrupas esas encuestas basadas en esas PCs, entonces se logra el objetivo de minimización (ref. 1) Además, esas PCs (etnia, edad, religión...) con frecuencia son ortogonales, por lo tanto, visualmente distintas al ver en PCA

5. Sin embargo, esta deducción intuitiva lleva a una condición suficiente pero no necesaria. (Ref 2: Sin embargo, que PCA sea una relajación útil de la agrupación de KMeans no fue un resultado nuevo (ver, por ejemplo,[35]), y es fácil descubrir contraejemplos a la declaración de que el subespacio del centroide del cluster está abarcado por las direcciones principales.[36])

   Elegir clusters basados en / a lo largo de los CPs puede llevar cómodamente a un mecanismo de asignación cómodo

   Este podría ser un ejemplo si x es el primer CP a lo largo del eje X: (...........CC1...............CC2............CC3 Eje X) donde el eje X captura más del 9X% de la varianza y digamos que es el único CP

6. Finalmente, PCA también se utiliza para visualizar después de que se haya realizado KMeans (Ref 4)

   Si la visualización de PCA muestra que nuestro resultado de agrupación de K es ortogonal o cercano a ello, entonces es una señal de que nuestra agrupación es sólida, cada una de las cuales exhibe características únicas

   (*ya que por definición PCA encuentra / muestra esas dimensiones principales (de 1D a 3D) de tal manera que digamos K (PCA) capturará probablemente sobre una gran parte de la varianza.

Así que PCA es útil tanto para visualizar y confirmar una buena agrupación, así como un elemento intrínsecamente útil para determinar la agrupación de KMeans, para ser utilizado antes o después de KMeans.

Referencias:

1. https://msdn.microsoft.com/en-us/library/azure/dn905944.aspx
2. https://en.wikipedia.org/wiki/Principal_component_analysis
3. Agrupamiento utilizando análisis de componentes principales: aplicación de autonomía-discapacidad en personas mayores (Combes & Azema)
4. http://cs229.stanford.edu/notes/cs229-notes10.pdf Andrew Ng

Answer 5

Resolver el k-means en su aproximación de baja graduación de O(k/epsilon) (es decir, proyectando en el espacio de los primeros vectores singulares más grandes como en PCA) produciría una aproximación de (1+epsilon) en términos de error multiplicativo.

Particularmente, proyectar en el k-ésimo vector más grande produciría una aproximación de 2.

De hecho, la suma de las distancias al cuadrado para CUALQUIER conjunto de k centros puede ser aproximada por esta proyección. Luego podemos calcular un coreset en los datos reducidos para reducir la entrada a puntos polinomiales (k/eps) que aproximan esta suma.

Ver: Dan Feldman, Melanie Schmidt, Christian Sohler: Turning big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering. SODA 2013: 1434-1453