Qual é a relação entre o cluster de k-means e o PCA?

61

É uma prática comum aplicar o PCA (análise de componentes principais) antes de um algoritmo de armazenamento em cluster (como k-means). Acredita-se que melhora os resultados do agrupamento na prática (redução de ruído).

No entanto, estou interessado em um estudo comparativo e aprofundado da relação entre PCA e k-médias. Por exemplo, Chris Ding e Xiaofeng He, 2004, Clustering K-means via Análise de Componentes Principais mostraram que "os componentes principais são as soluções contínuas para os indicadores discretos de associação de cluster para o cluster K-means". No entanto, tenho dificuldade em entender este artigo, e a Wikipedia realmente afirma que está errado .

Além disso, os resultados dos dois métodos são um pouco diferentes no sentido de que o PCA ajuda a reduzir o número de "recursos" enquanto preserva a variação, enquanto o cluster reduz o número de "pontos de dados" ao resumir vários pontos por suas expectativas / meios (no caso de k-médias). Portanto, se o conjunto de dados consiste em pontos com recursos cada um, o PCA visa compactar os recursos , enquanto o clustering visa compactar os pontos de dados.T T NNTTN

Estou procurando uma explicação leiga das relações entre essas duas técnicas + alguns trabalhos mais técnicos relacionados às duas técnicas.

microfone
fonte
2
O cluster também pode ser considerado como redução de recurso. Onde você expressa cada amostra por sua atribuição de cluster ou codifica-as esparsamente (reduza, portanto, T para k ). Ambas as abordagens mantêm o número de pontos de dados constante, enquanto reduzem as dimensões do "recurso".
jeff

Respostas:

73

É verdade que o agrupamento K-means e o PCA parecem ter objetivos muito diferentes e, à primeira vista, não parecem estar relacionados. No entanto, conforme explicado no artigo de Ding & He 2004, K-significa Clustering via Análise de Componentes Principais , há uma conexão profunda entre eles.

A intuição é que o PCA procura representar todos os vetores de dados como combinações lineares de um pequeno número de vetores próprios e o faz para minimizar o erro de reconstrução ao quadrado médio. Por outro lado, K-means procura representar todos os n vetores de dados por meio de um pequeno número de centróides de cluster, ou seja, representá-los como combinações lineares de um pequeno número de vetores de centróides de cluster, onde os pesos de combinação lineares devem ser zero, exceto o único 1 . Isso também é feito para minimizar o erro de reconstrução ao quadrado médio.nn1

Portanto, o K-means pode ser visto como um PCA super-esparso.

O que o papel de Ding & He faz é tornar essa conexão mais precisa.


Infelizmente, o artigo de Ding & He contém algumas formulações desleixadas (na melhor das hipóteses) e pode ser facilmente mal interpretado. Por exemplo, pode parecer que Ding & He afirmam ter provado que os centróides de cluster da solução de cluster K-means estão no subespaço PCA dimensional :(K1)

Teorema 3.3. O subespaço centróide do cluster é medido pelas primeiras direções principais [...].K1

Para isso implica que as projeções no eixo PC1 serão necessariamente negativas para um cluster e positivas para outro cluster, ou seja, o eixo PC2 separará os clusters perfeitamente.K=2

Isso é um erro ou alguma escrita superficial; em qualquer caso, tomado literalmente, essa afirmação específica é falsa.

Vamos começar examinando alguns exemplos de brinquedos em 2D para . Gerei algumas amostras das duas distribuições normais com a mesma matriz de covariância, mas com médias variadas. Em seguida, executei o K-means e o PCA. A figura a seguir mostra o gráfico de dispersão dos dados acima e os mesmos dados coloridos de acordo com a solução K-means abaixo. Também mostro a primeira direção principal como uma linha preta e centróides de classe encontrados por meios K com cruzes negras. O eixo PC2 é mostrado com a linha preta tracejada. O K-means foi repetido 100 vezes com sementes aleatórias para garantir a convergência para o ótimo global.K=2100

PCA vs K-médias

Pode-se ver claramente que, embora os centróides de classe tendam a estar muito próximos da primeira direção do PC, eles não caem exatamente nela. Além disso, apesar de o eixo PC2 separar os clusters perfeitamente nas subparcelas 1 e 4, há alguns pontos do lado errado nas subparcelas 2 e 3.

Portanto, o acordo entre K-means e PCA é bastante bom, mas não é exato.

Então, o que Ding e Ele provaram? Por simplicidade, considerarei apenas . Deixe o número de pontos atribuídos a cada grupo ser n 1 e n 2 e o número total de pontos n = n 1 + n 2 . Seguindo Ding & He, vamos definir o vetor indicador de cluster qR n da seguinte maneira: q i = K=2n1n2n=n1+n2 qRn sei-ésimo pontos pertencer ao cluster 1 eqi=-qi=n2/nn1i se pertencer ao cluster 2. O vetor indicador de cluster possui comprimento unitário__q=1e é "centrado", ou seja, seus elementos somam zero.qi=n1/nn2q=1qi=0

Ding & He mostram que a função de perda K- (que o algoritmo K-significa minimiza) pode ser reescrita de maneira equivalente como , onde é a matriz Gram de produtos escalares entre todos os pontos: , onde é a matriz de dados e é a matriz de dados centralizada. - qG q Gki(xiμk)2qGqGG = X c X c X n × 2 X cn×nG=XcXcXn×2Xc

(Nota: estou usando notação e terminologia que diferem um pouco do trabalho deles, mas acho mais claro).

Portanto, a solução K-means é um vetor de unidade centralizada maximizando . É fácil mostrar que o primeiro componente principal (quando normalizado para ter a soma unitária dos quadrados) é o vetor próprio principal da matriz Gram, ou seja, também é um vetor unitário centrado maximizando . A única diferença é que é adicionalmente restrito a ter apenas dois valores diferentes, enquanto não possui essa restrição.qG q p pG p q pqqGqppGpqp

Em outras palavras, K-means e PCA maximizam a mesma função objetivo , com a única diferença é que K-mean possui restrição "categórica" ​​adicional.

É lógico que na maioria das vezes as soluções K-means (restritas) e PCA (irrestritas) serão muito próximas umas das outras, como vimos acima na simulação, mas não se deve esperar que sejam idênticas. Tomar definir todos os seus elementos negativos como iguais a e todos os seus elementos positivos como geralmente não fornecerão exatamente . - pn1/nn2 qn2/nn1q

Ding e Ele parecem entender isso bem porque formulam seu teorema da seguinte maneira:

Teorema 2.2. Para cluster K-significa em que , a solução contínua do vetor indicador de cluster é o [primeiro] componente principalK=2

Observe que as palavras "solução contínua". Após provar esse teorema, eles comentam adicionalmente que o PCA pode ser usado para inicializar iterações K-means, o que faz total sentido, pois esperamos que esteja próximo de . Mas ainda é necessário executar as iterações, porque elas não são idênticas.pqp

No entanto, Ding & He, em seguida, desenvolvem um tratamento mais geral para e acabam formulando o Teorema 3.3 comoK>2

Teorema 3.3. O subespaço centróide do cluster é medido pelas primeiras direções principais do [...].K1

Não passei pela matemática da Seção 3, mas acredito que esse teorema de fato também se refere à "solução contínua" de K-means, ou seja, sua afirmação deve ler "o espaço do centróide do cluster da solução contínua de K-means é estendido [...] ".

Ding & He, no entanto, não fazem essa qualificação importante e, além disso, escrevem em seu resumo que

Aqui, provamos que os principais componentes são as soluções contínuas para os indicadores discretos de associação ao cluster para K-means clustering. Equivalentemente, mostramos que o subespaço medido pelos centróides do cluster é dado pela expansão espectral da matriz de covariância de dados truncada em termos .K1

A primeira frase está absolutamente correta, mas a segunda não. Não está claro para mim se esta é uma escrita (muito) superficial ou um erro genuíno. Eu, educadamente, enviei um e-mail aos dois autores pedindo esclarecimentos. (Atualize dois meses depois: nunca recebi notícias deles.)


Código de simulação 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    
ameba diz Restabelecer Monica
fonte
2
Acabei de olhar dentro do jornal Ding & He. No teorema 2.2, eles afirmam que se você fizer médias de k (com k = 2) de alguma nuvem de dados p-dimensionais e também executar PCA (com base em covariâncias) dos dados, todos os pontos pertencentes ao cluster A serão negativos e todos pontos pertencentes ao cluster B serão positivos nas pontuações do PC1. Declaração interessante, - deve ser testada em simulações. O problema, no entanto, é que ele assume uma solução globalmente ótima de K-means, eu acho; mas como sabemos se o cluster alcançado foi ideal?
ttnphns
1
@ttnphns, atualizei minha simulação e descobri para testar essa reivindicação mais explicitamente. Se as projeções no PC1 devem ser positivas e negativas para as classes A e B, isso significa que o eixo PC2 deve servir como um limite entre elas. Isso está muito próximo de ser o caso nas minhas 4 simulações de brinquedos, mas nos exemplos 2 e 3 há alguns pontos do lado errado do PC2. Em relação à convergência, eu executei a kmeansfunção com 100 repetições: ela escolhe uma inicialização aleatória diferente a cada vez e, em seguida, seleciona a melhor solução, portanto, esperamos garantir que o melhor global seja alcançado.
ameba diz Restabelecer Monica
1
@ttnphns: Acho que descobri o que está acontecendo, por favor, veja minha atualização.
ameba diz Restabelecer Monica
ameba, obrigado por digerir o artigo em discussão para todos nós e por fornecer suas conclusões (+2); e por me avisar pessoalmente! Espero voltar daqui a alguns dias para ler e investigar sua resposta. Mas apreciando isso já agora.
precisa
Postagem excelente. Existe uma razão pela qual você usou o Matlab e não o R? Apenas curioso, porque estou fazendo o curso ML Coursera e Andrew Ng também usa Matlab, em oposição a R ou Python. É uma escolha geral de ML?
Antoni Parellada
10

PCA e K-significa fazem coisas diferentes.

O PCA é usado para redução de dimensionalidade / seleção de recursos / aprendizado de representação, por exemplo, quando o espaço de recursos contém muitos recursos irrelevantes ou redundantes. O objetivo é encontrar a dimensionalidade intrínseca dos dados.

Aqui está um exemplo bidimensional que pode ser generalizado para espaços dimensionais mais altos. O conjunto de dados tem dois recursos, e , cada círculo é um ponto de dados.yxy

insira a descrição da imagem aqui

Na imagem tem uma magnitude maior que . Estes são os vetores próprios. A dimensão dos dados é reduzida de duas dimensões para uma dimensão (neste caso, não há muita escolha) e isso é feito projetando na direção do vetor (após uma rotação em que se torna paralelo ou perpendicular a um dos eixos) . Isso ocorre porque é ortogonal à direção da maior variação. Uma maneira de pensar nisso é a perda mínima de informações. (Ainda há uma perda, pois um eixo de coordenadas é perdido).v 2 v 2 v 2 v 2v1v2v2v2v2

K-means é um algoritmo de agrupamento que retorna o agrupamento natural de pontos de dados, com base em sua similaridade. É um caso especial de Gaussian Mixture Models .

Na imagem abaixo, o conjunto de dados tem três dimensões. Pode ser visto no gráfico 3D à esquerda que a dimensão pode ser 'descartada' sem perder muita informação. O PCA é usado para projetar os dados em duas dimensões. Na figura à esquerda, o plano de projeção também é mostrado. Em seguida, os meios K podem ser usados ​​nos dados projetados para rotular os diferentes grupos, na figura à direita, codificados com cores diferentes.X

insira a descrição da imagem aqui

O PCA ou outras técnicas de redução de dimensionalidade são usadas antes dos métodos não supervisionados ou supervisionados no aprendizado de máquina. Além dos motivos descritos por você e os mencionados acima, ele também é usado para fins de visualização (projeção em 2D ou 3D de dimensões mais altas).

Quanto ao artigo, não acredito que exista nenhuma conexão, o PCA não possui informações sobre o agrupamento natural de dados e opera em todos os dados, não em subconjuntos (grupos). Se alguns grupos podem ser explicados por um vetor próprio (apenas porque esse cluster específico está espalhado nessa direção) é apenas uma coincidência e não deve ser tomada como regra geral.

"O PCA visa compactar os recursos T, enquanto o clustering visa compactar os N pontos de dados".

De fato, a compactação é uma maneira intuitiva de pensar sobre o PCA. No entanto, em K-significa, para descrever cada ponto em relação ao cluster, você ainda precisa de pelo menos a mesma quantidade de informações (por exemplo, dimensões) , onde é a distância e é armazenado em vez de . E você também precisa armazenar o para saber a que se o delta. É claro que você pode armazenar e no entanto, não poderá recuperar as informações reais nos dados.d δ i x ixi=d(μi,δi)dδixi d iμidi

Clustering adiciona informações realmente. Penso nisso como dividir os dados em grupos naturais (que não precisam necessariamente ser separados) sem saber o significado do rótulo para cada grupo (bem, até que você veja os dados dentro dos grupos).

shuriken x blue
fonte
3
A maneira como seus PCs são rotulados na trama parece inconsistente com a discussão correspondente no texto. Observe que, embora o PCA seja normalmente aplicado às colunas, & k-mean às linhas, ambos podem ser aplicados a qualquer uma. Não li o jornal, mas aposto que é disso que eles estão falando.
gung - Restabelece Monica
Desculpe, eu quis dizer a figura principal: os rótulos v1 e v2 para os PCs.
gung - Restabelece Monica
Bom ponto, pode ser útil (não é possível descobrir para que) compactar grupos de pontos de dados. Encontre grupos usando k-means, comprima registros em menos usando pca. Quanto ao agrupamento de recursos, isso pode ser realmente útil.
shuriken x blue
2
Então você está basicamente dizendo que o jornal está errado? Ele afirma explicitamente (consulte as 3ª e 4ª sentenças no resumo) e afirma ter provado matematicamente que existe uma conexão específica, enquanto você diz que não há conexão.
ameba diz Restabelecer Monica
O que obtive disso: o PCA aprimora as soluções de clustering K-means. A conexão é que a estrutura do cluster é incorporada nos primeiros componentes principais K-1. Esta é a contribuição.
shuriken x blue
7

O(nd2+d3)

n2O(n2d+n3)O(knid)nk=2. K-means é um problema de otimização de mínimos quadrados, assim como o PCA. O k-means tenta encontrar a partição dos mínimos quadrados dos dados. O PCA localiza o vetor de associação do cluster dos mínimos quadrados.

O primeiro Eigenvector tem a maior variação, portanto, dividir esse vetor (que se assemelha à associação do cluster, não às coordenadas de dados de entrada!) Significa maximizar a variação do cluster . Ao maximizar a variação do cluster, você também minimiza a variação dentro do cluster.

Mas para problemas reais, isso é inútil. É apenas de interesse teórico.

Anony-Mousse
fonte
2
Seria ótimo ver uma explicação / visão geral mais específica do artigo de Ding & He (ao qual o OP estava vinculado). Ainda não estou familiarizado com isso, mas já o vi mencionado vezes suficientes para ser bastante curioso.
Ameba diz Reinstate Monica
3
Você quer dizer isso ? Sim, eu também me deparei com isso; Eu acho que isso só aumenta a minha confusão. Eu esperava que esse fosse o fio que pudesse esclarecer isso para mim ... Agora que penso nisso, talvez eu deva dar uma recompensa a ele. Acho que não terei tempo nos próximos dias para estudar esse tópico.
Ameba diz Reinstate Monica
3
Este parágrafo do wiki é muito estranho. Diz que Ding & He (2001/2004) estava errado e não era um resultado novo! Para demonstrar que não era novo, cita um artigo de 2004 (?!). Para demonstrar que estava errado, cita um artigo mais recente de 2014 que nem cita Ding & He. Duvidoso.
Ameba diz Reinstate Monica
3
Talvez cite spam novamente. A Wikipedia está cheia de autopromoção.
Anony-Mousse
1
n×nkk
4

Resolver as médias de k em sua aproximação de baixo escalão O (k / epsilon) (ou seja, projetar no intervalo dos primeiros maiores vetores singulares como no PCA) produziria uma aproximação (1 + epsilon) em termos de erro multiplicativo.

Particularmente, projetar no vetor k maior resultaria em uma aproximação 2.

De fato, a soma das distâncias ao quadrado para QUALQUER conjunto de k centros pode ser aproximada por essa projeção. Em seguida, podemos calcular o conjunto de cores nos dados reduzidos para reduzir a entrada em pontos poli (k / eps) que se aproximam dessa soma.

Veja: Dan Feldman, Melanie Schmidt, Christian Sohler: Transformando Big Data em Dados Minúsculos: Coresets de tamanho constante para k-means, PCA e clustering projetivo. SODA 2013: 1434-1453

Dan Feldman
fonte
3

Relação intuitiva de PCA e KMeans

  1. Teoricamente, a análise dimensional do PCA (a primeira retenção de dimensão K diz que 90% da variação ... não precisa ter relação direta com o cluster K Means); no entanto, o valor do uso do PCA veio de a) consideração prática, dada a natureza dos objetos que analisamos tende a agrupar-se naturalmente / evoluir a partir de (um determinado segmento) de seus principais componentes (idade, sexo ...) b) O PCA elimina a dimensão de baixa variação (ruído), agregando valor (e criando um sentido semelhante ao agrupamento) ), concentrando-se nessas dimensões principais Em termos simples, é como o eixo XY é o que nos ajuda a dominar qualquer conceito matemático abstrato, mas de uma maneira mais avançada.

  2. K significa tentar minimizar a distância geral dentro de um cluster para um determinado K

  3. Para um conjunto de objetos com parâmetros de dimensão N, por padrão, objetos semelhantes terão a maioria dos parâmetros "semelhantes", exceto algumas diferenças importantes (por exemplo, um grupo de jovens estudantes de TI, jovens dançarinos, humanos ... terão alguns recursos muito semelhantes (baixa variação) mas algumas características-chave ainda bastante diversas e capturando esses "principais componentes principais" capturam essencialmente a maioria das variações, por exemplo, cor, área de residência ... Portanto, baixa distorção se negligenciarmos essas características de pequenas diferenças ou a conversão para PCs mais baixos não perderão muita informação
  4. Portanto, é "muito provável" e "muito natural" que agrupá-los para observar as diferenças (variações) faz sentido para a avaliação dos dados (por exemplo, se você fizer 1.000 pesquisas por semana na rua principal, agrupá-las com base em questões étnicas). , idade ou formação educacional como o PC faz sentido) Sob a missão de K Means, tentamos estabelecer um número razoável de K para que esses elementos do grupo (em um cluster) tenham a menor distância geral (minimizada) entre o Centroid e o custo. estabelecer e executar os clusters K é ideal (cada membro como um cluster não faz sentido, pois é muito caro para manter e sem valor)
  5. K O agrupamento de meios pode ser facilmente "visualmente inspecionado" para ser ideal, se esse K estiver ao longo dos componentes principais (por exemplo, se para pessoas em diferentes faixas etárias, grupos étnicos / regiosos, eles tendem a expressar opiniões semelhantes, por isso, se você agrupar essas pesquisas com base em aqueles PCs, que atingem a meta de minimização (ref. 1) Também aqueles PCs (étnicos, idade, religião ..) geralmente são ortogonais, portanto visualmente distintos ao visualizar o PCA
  6. No entanto, essa dedução intuitiva leva a uma condição suficiente, mas não necessária. (Ref. 2: No entanto, que PCA é um relaxamento útil do agrupamento de médias k não foi um resultado novo (consulte, por exemplo, [35])) e é fácil descobrir contra-exemplos à afirmação de que o subespaço do centróide do cluster é estendido pelas principais direções. [36])

A escolha de clusters com base / ao longo dos CPs pode levar confortavelmente a um mecanismo de alocação confortável

Este poderia ser um exemplo se x é o primeiro PC ao longo do eixo X: (........... CC1 ............... CC2 ..... ....... CC3 eixo X) onde o eixo X diz capturar mais de 9X% da variação e diz que é o único PC

6.Finalmente, o PCA também é usado para visualizar após o K Keans ser concluído (Ref 4)

Se o PCA exibir * o resultado do clustering K for ortogonal ou próximo dele, é um sinal de que o clustering é bom, cada um dos quais exibindo características únicas

(* uma vez que, por definição, o PCA descobre / exibe essas dimensões principais (1D a 3D), tais como K (PCA), provavelmente capturarão sobre a grande maioria da variação.

Portanto, o PCA é útil na visualização e confirmação de um bom agrupamento, bem como um elemento intrinsecamente útil na determinação do agrupamento K Means - a ser usado antes e depois do K Means.

Referência:

  1. https://msdn.microsoft.com/en-us/library/azure/dn905944.aspx
  2. https://en.wikipedia.org/wiki/Principal_component_analysis
  3. CLUSTERIZAÇÃO USANDO ANÁLISE PRINCIPAL DE COMPONENTES: APLICAÇÃO DE PESSOAS IDOSAS - DESABILITAR A AUTONOMIA (Combes & Azema)
  4. http://cs229.stanford.edu/notes/cs229-notes10.pdf Andrew Ng
r poon
fonte