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

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

Sin embargo, estoy interesado en un estudio comparativo y en profundidad de la relación entre PCA y k-means. Por ejemplo, Chris Ding y Xiaofeng He, 2004, K-means Clustering a través del análisis de componentes principales mostraron que "los componentes principales son las soluciones continuas para los indicadores de membresía de clúster discretos para K-means clustering". Sin embargo, me cuesta entender este artículo, y Wikipedia en realidad afirma que está mal .

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" al resumir varios puntos por sus expectativas / medios (en el caso de k-means). Entonces, si el conjunto de datos consiste en puntos con características cada uno, PCA apunta a comprimir las características mientras que la agrupación apunta a comprimir los puntos de datos.$N$$T$$T$$N$

Estoy buscando una explicación laica de las relaciones entre estas dos técnicas + algunos documentos técnicos más relacionados con las dos técnicas.

Es cierto que el agrupamiento K-means y PCA parecen tener objetivos muy diferentes y, a primera vista, no parecen estar relacionados. Sin embargo, como se explica en el documento Ding & He 2004 K-means Clustering a través del análisis de componentes principales , existe una profunda conexión entre ellos.

La intuición es que PCA busca representar todos los vectores de datos como combinaciones lineales de un pequeño número de vectores propios, y lo hace para minimizar el error de reconstrucción cuadrático medio. Por el contrario, K-means busca representar todos los vectores de datos a través de un pequeño número de centroides de agrupación, es decir, representarlos como combinaciones lineales de una pequeña cantidad de vectores de centroide de agrupación donde los pesos de combinación lineal deben ser todos cero, excepto el único . Esto también se hace para minimizar el error de reconstrucción cuadrático medio.n $n$$n$$1$

Por lo tanto, K-means puede verse como una PCA súper dispersa.

Lo que hace el papel de Ding & He es hacerlo para hacer esta conexión más precisa.

Desafortunadamente, el documento de Ding & He contiene algunas formulaciones descuidadas (en el mejor de los casos) y puede ser fácilmente mal entendido. Por ejemplo, podría parecer que Ding & He afirman haber demostrado que los centroides de agrupación de la solución de agrupación K-means se encuentran en el subespacio PCA dimensional :$(K-1)$

Teorema 3.3. El subespacio centroide del clúster se extiende por las primeras direcciones principales [...].$K-1$

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

Esto es un error o una escritura descuidada; en cualquier caso, tomado literalmente, esta afirmación particular es falsa.

Comencemos mirando algunos ejemplos de juguetes en 2D para . Generé algunas muestras de las dos distribuciones normales con la misma matriz de covarianza pero con medias variables. Luego ejecuté K-means y PCA. La siguiente figura muestra el diagrama de dispersión de los datos anteriores y los mismos datos coloreados de acuerdo con la solución K-means a continuación. También muestro la primera dirección principal como una línea negra y centroides de clase encontrados por medios K con cruces negras. El eje PC2 se muestra con la línea negra discontinua. K-means se repitió veces con semillas aleatorias para garantizar la convergencia al óptimo global.$K=2$$100$

Se puede ver claramente que, aunque los centroides de clase tienden a estar bastante cerca de la primera dirección de PC, no caen exactamente sobre ella. Además, aunque el eje PC2 separa perfectamente los clústeres en las subparcelas 1 y 4, hay un par de puntos en el lado equivocado en las subparcelas 2 y 3.

Entonces, el acuerdo entre K-means y PCA es bastante bueno, pero no es exacto.

Entonces, ¿qué probaron Ding y Él? Por simplicidad, consideraré solo el caso . Deje que el número de puntos asignados a cada grupo sea y y el número total de puntos . Siguiendo a Ding & He, definamos el vector indicador de clúster siguiente manera: si -th puntos pertenece al clúster 1 y si pertenece al clúster 2. El vector indicador del clúster tiene una unidad de longitud y está "centrado", es decir, sus elementos suman cero .n 1 n 2 n = n 1 + n 2 q ∈ R n q i = $K=2$$n_1$$n_2$$n=n_1+n_2$ $\mathbf q\in\mathbb R^n$ iqi=-$q_i = \sqrt{n_2/nn_1}$$i$$q_i = -\sqrt{n_1/nn_2}$$\|\mathbf q\| = 1$$\sum q_i = 0$

Ding y Él muestran que la función de pérdida K-means (que minimiza el algoritmo K-means) puede reescribirse de manera equivalente como , donde es la matriz de Gram de productos escalares entre todos los puntos: , donde es la matriz de datos y es la matriz de datos centrada.$\sum_k \sum_i (\mathbf x_i - \boldsymbol \mu_k)^2$$-\mathbf q^\top \mathbf G \mathbf q$$\mathbf G$$n\times n$$\mathbf G = \mathbf X_c^\top \mathbf X_c$$\mathbf X$$n\times 2$$\mathbf X_c$

(Nota: estoy usando notación y terminología que difiere ligeramente de su documento pero que me parece más claro).

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

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 pensar que la mayoría de las veces las soluciones K-medias (restringidas) y PCA (sin restricciones) serán bastante cercanas entre sí, como vimos anteriormente en la simulación, pero no se debe esperar que sean idénticas. Tomar y configurar todos sus elementos negativos para que sean iguales a y todos sus elementos positivos a generalmente no darán exactamente .$\mathbf p$$-\sqrt{n_1/nn_2}$$\sqrt{n_2/nn_1}$$\mathbf q$

Ding y Él parecen entender esto bien porque formulan su teorema de la siguiente manera:

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

Tenga en cuenta que las palabras "solución continua". Después de probar este teorema, comentan adicionalmente que PCA se puede usar para inicializar iteraciones de K-medias, lo que tiene mucho sentido dado que esperamos que esté cerca de . Pero todavía hay que realizar las iteraciones, porque no son idénticas.$\mathbf q$$\mathbf p$

Sin embargo, Ding y Él luego desarrollan un tratamiento más general para y terminan formulando el Teorema 3.3 como$K>2$

Teorema 3.3. El subespacio centroide del clúster se extiende por las primeras direcciones principales [...].$K-1$

No revisé las matemáticas de la Sección 3, pero creo que este teorema, de hecho, también se refiere a la "solución continua" de K-medias, es decir, su enunciado debería leer "espacio centroide de agrupamiento de la solución continua de K-medias es abarcado [...] ".

Ding & He, sin embargo, no hacen esta calificación importante, y además escriben en su resumen que

Aquí demostramos que los componentes principales son las soluciones continuas para los indicadores de membresía de clúster discretos para la agrupación de K-means. De manera equivalente, mostramos que el subespacio que abarcan los centroides del grupo están dados por la expansión espectral de la matriz de covarianza de datos truncada en términos .$K-1$

La primera oración es absolutamente correcta, pero la segunda no. No me queda claro si se trata de una escritura (muy) descuidada o un error genuino. Envié un correo electrónico muy cortésmente a ambos autores para pedirles una aclaración. (Actualización dos meses después: nunca he tenido noticias suyas).

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    

PCA y K-means hacen cosas diferentes.

PCA se utiliza para la 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í hay un ejemplo bidimensional que puede generalizarse a espacios dimensionales superiores. El conjunto de datos tiene dos características, e , cada círculo es un punto de datos.$x$$y$

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

K-means es un algoritmo de agrupamiento que devuelve la agrupación natural de puntos de datos, en función de su similitud. Es un caso especial de los modelos de mezcla gaussiana .

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

PCA u otras técnicas de reducción de dimensionalidad se utilizan antes de los métodos no supervisados ​​o supervisados ​​en el aprendizaje automático. Además de las razones expuestas por usted y las que mencioné anteriormente, también se usa para 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 ser explicados por un vector propio (solo porque ese grupo particular se extiende a lo largo de esa dirección) es solo una coincidencia y no debe tomarse como una regla general.

"PCA apunta a comprimir las características T, mientras que el agrupamiento apunta a 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 con su clúster, todavía necesita al menos la misma cantidad de información (por ejemplo, dimensiones) , donde es la distancia y está almacenado en lugar de . Y también necesita almacenar para saber con qué se relaciona el delta. Por supuesto, puede almacenar e sin embargo, no podrá recuperar la información real en los datos.$x_i = d( \mu_i, \delta_i)$$d$$\delta_i$$x_i$$\mu_i$$d$$i$

La agrupación agrega información realmente. Pienso en ello como dividir los datos en grupos naturales (que no necesariamente tienen que ser disjuntos) sin saber lo que significa la etiqueta para cada grupo (bueno, hasta que se miren los datos dentro de los grupos).

Es común blanquear los datos antes de usar k-means. La razón es que k-means es extremadamente sensible a la escala, y cuando tiene atributos mixtos ya no hay una escala "verdadera". Luego debe normalizar, estandarizar o blanquear sus datos. Ninguno es perfecto, pero el blanqueamiento eliminará la correlación global que a veces puede dar mejores resultados. PCA / blanqueamiento es ya que opera en la matriz de covarianza.$O(n\cdot d^2 + d^3)$

A mi entender, la relación de k-means con PCA no está en los datos originales . Se trata de usar PCA en la matriz de distancia (que tiene entradas, y hacer PCA completo es , es decir, prohibitivamente costoso, en particular en comparación con k-means que es donde es el único término grande), y tal vez solo para . 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 pertenencia al clúster de mínimos cuadrados.$n^2$$O(n^2\cdot d+n^3)$$O(k\cdot n \cdot i\cdot d)$$n$$k=2$

El primer Eigenvector tiene la mayor varianza, por lo tanto, la división en este vector (que se parece a la pertenencia al clúster, no a las coordenadas de datos de entrada) significa maximizar la varianza del clúster . Al maximizar entre la varianza del clúster, también minimiza la varianza dentro del clúster.

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

Resolver las medias k en su aproximación de rango bajo O (k / epsilon) (es decir, proyectar en el lapso de los primeros vectores singulares más grandes como en PCA) produciría una aproximación (1 + epsilon) en términos de error multiplicativo.

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

De hecho, la suma de distancias al cuadrado para CUALQUIER conjunto de k centros puede ser aproximada por esta proyección. Entonces podemos calcular el conjunto de núcleos en los datos reducidos para reducir la entrada a los puntos poli (k / eps) que se aproximan a esta suma.

Ver: Dan Feldman, Melanie Schmidt, Christian Sohler: Convertir datos grandes en datos pequeños: conjuntos de núcleos de tamaño constante para k-means, PCA y agrupación proyectiva. SODA 2013: 1434-1453

Relación intuitiva de PCA y KMeans

1. Teóricamente, el análisis dimensional de PCA (la primera dimensión K que retiene dice que el 90% de la varianza ... no necesita tener una relación directa con el grupo K Means), sin embargo, el valor de usar PCA proviene de a) consideración práctica dada la naturaleza de los objetos que el análisis tiende a agruparse naturalmente / evolucionar desde (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 forma un sentido similar a la agrupación ) al centrarse en esas dimensiones clave En términos simples, es como si el eje XY fuera lo que nos ayuda a dominar cualquier concepto matemático abstracto, pero de una manera más avanzada.

2. K Significa tratar de minimizar la distancia total dentro de un grupo para una K dada

3. Para un conjunto de objetos con parámetros de dimensión N, los objetos similares por defecto tendrán la mayoría de los parámetros "similares", excepto algunas diferencias clave (por ejemplo, un grupo de jóvenes estudiantes de TI, jóvenes bailarines, humanos ... tendrán algunas características muy similares (baja varianza) pero algunas características clave siguen siendo bastante diversas y capturar esos "Componentes principales clave" esencialmente capturan la mayoría de la variación, por ejemplo, color, área de residencia ... Por lo tanto, baja distorsión si descuidamos esas características de diferencias menores, o la conversión a PC inferiores no perderán mucha información
4. Por lo tanto, es "muy probable" y "muy natural" que agruparlos para observar las diferencias (variaciones) tenga sentido para la evaluación de datos (por ejemplo, si realiza 1,000 encuestas en una semana en la calle principal, agrupándolas según la etnia , edad o antecedentes educativos como PC tiene sentido) Bajo la misión de K Means, tratamos de establecer un número justo de K para que esos elementos del grupo (en un grupo) tengan la distancia general más pequeña (minimizada) entre Centroid y mientras el costo establecer y ejecutar los grupos K es óptimo (cada miembro como grupo no tiene sentido ya que es demasiado costoso de mantener y no tiene valor)
5. K La agrupación de medios podría ser fácilmente "inspeccionada visualmente" para que sea óptima, si tal K está junto con los Componentes Principales (por ejemplo, si para personas de diferentes edades, grupos étnicos / regios tienden a expresar opiniones similares, por lo que si agrupa esas encuestas en función de esas PC, entonces que logran el objetivo de minización (ref. 1) También esas PC (étnicas, de edad, de religión ...) con frecuencia son ortogonales, por lo tanto visualmente distintas al ver la PCA
6. Sin embargo, esta deducción intuitiva conduce a una condición suficiente pero no necesaria. (Ref. 2: Sin embargo, que PCA es una relajación útil de la agrupación de k-medias no fue un resultado nuevo (véase, por ejemplo, [35]), y es sencillo descubrir contraejemplos a la afirmación de que el subespacio centroide del clúster se extiende por las instrucciones principales. [36])

Elegir grupos basados ​​en / a lo largo de las PC puede conducir cómodamente a un mecanismo de asignación cómodo

Este podría ser un ejemplo si x es la primera PC a lo largo del eje X: (........... CC1 ............... CC2 ..... ....... CC3 X axis) donde el eje X dice capturar más del 9X% de varianza y dice que es la única PC

6. Finalmente, PCA también se usa para visualizar después de que K Means está hecho (Ref. 4)

Si la PCA muestra * nuestro resultado de agrupamiento K es ortogonal o cercano, entonces es una señal de que nuestro agrupamiento es sólido, cada uno de los cuales exhibe características únicas

(* dado que, por definición, PCA descubre / muestra esas dimensiones principales (1D a 3D) de modo que K (PCA) capturará probablemente sobre una gran mayoría de la varianza.

Por lo tanto, PCA es útil para visualizar y confirmar un buen agrupamiento, así como un elemento intrínsecamente útil para determinar el agrupamiento de K Means, que se utilizará antes de los K Means.

Referencia:

1. https://msdn.microsoft.com/en-us/library/azure/dn905944.aspx
2. https://en.wikipedia.org/wiki/Principal_component_analysis
3. CLUSTERING UTILIZANDO EL ANÁLISIS PRINCIPAL DE COMPONENTES: APLICACIÓN DE LAS PERSONAS MAYORES CON DISCAPACIDAD DE AUTONOMÍA (Combes y Azema)
4. http://cs229.stanford.edu/notes/cs229-notes10.pdf Andrew Ng