É 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 N
Estou procurando uma explicação leiga das relações entre essas duas técnicas + alguns trabalhos mais técnicos relacionados às duas técnicas.
fonte
Respostas:
É 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.n n 1
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 :( K- 1 )
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= 2 100
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 q ∈ R n da seguinte maneira: q i = √K= 2 n1 n2 n = n1+ n2 q∈ Rn sei-ésimo pontos pertencer ao cluster 1 eqi=-√qEu= n2/ n n1------√ Eu se pertencer ao cluster 2. O vetor indicador de cluster possui comprimento unitário__q″=1e é "centrado", ou seja, seus elementos somam zero.qEu= - n1/ n n2------√ ∥ q∥ = 1 ∑ qEu= 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. - q ⊤ G q G∑k∑i(xi−μk)2 −q⊤Gq G G = X ⊤ c X c X n × 2 X cn×n G=X⊤cXc X n×2 Xc
(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.q ⊤ G q p p ⊤ G p q pq q⊤Gq p p⊤Gp q p
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 . - √p √−n1/nn2−−−−−−√ qn2/nn1−−−−−−√ q
Ding e Ele parecem entender isso bem porque formulam seu teorema da seguinte maneira:
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.pq p
No entanto, Ding & He, em seguida, desenvolvem um tratamento mais geral para e acabam formulando o Teorema 3.3 comoK>2
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
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
fonte
kmeans
funçã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.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.yx y
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 2v1 v2 v2 v2 v2
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
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.
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 δi xi d iμi d i
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).
fonte
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.
fonte
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
fonte
Relação intuitiva de PCA e KMeans
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.
K significa tentar minimizar a distância geral dentro de um cluster para um determinado K
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:
fonte