Quando combinamos redução de dimensionalidade com clustering?

16

Estou tentando executar o cluster no nível do documento. Eu construí a matriz de frequência termo-documento e estou tentando agrupar esses vetores de alta dimensão usando k-means. Em vez de agrupar diretamente, o que eu fiz foi aplicar primeiro a decomposição de vetor singular do LSA (Latent Semantic Analysis) para obter as matrizes U, S, Vt, selecionou um limite adequado usando o gráfico scree e aplicou o agrupamento nas matrizes reduzidas (especificamente Vt porque isso me dá uma informação de documento conceitual) que parecia estar me dando bons resultados.

Ouvi algumas pessoas dizerem que SVD (decomposição de vetor singular) está agrupando (usando a medida de similaridade de cosseno etc.) e não tinha certeza se eu poderia aplicar k-means na saída de SVD. Eu pensei que era logicamente correto, porque SVD é uma técnica de redução de dimensionalidade, me dá um monte de novos vetores. Por outro lado, k-significa tomará o número de clusters como entrada e dividirá esses vetores no número especificado de clusters. Esse procedimento é defeituoso ou existem maneiras de melhorar isso? Alguma sugestão?

lenda
fonte
boa pergunta. pessoalmente, estive pensando sobre essas coisas. mas não tem uma boa resposta.
suncoolsu
1
Existem métodos que executam simultaneamente redução de dimensionalidade e agrupamento. Esses métodos buscam uma representação de baixa dimensão idealmente escolhida, a fim de facilitar a identificação de clusters. Por exemplo, consulte pacote clustrd em R e as referências associadas.
Nat

Respostas:

6

Esta não é de forma alguma uma resposta completa, a pergunta que você deve fazer é "que tipo de distâncias são preservadas ao fazer a redução da dimensionalidade?". Como algoritmos de agrupamento como meios K operam apenas em distâncias, a métrica de distância correta a ser usada (teoricamente) é a métrica de distância que é preservada pela redução de dimensionalidade. Dessa forma, a etapa de redução de dimensionalidade pode ser vista como um atalho computacional para agrupar os dados em um espaço dimensional inferior. (também para evitar mínimos locais, etc)

Existem muitas sutilezas aqui que não pretendo entender (distâncias locais versus distâncias globais, como as distâncias relativas são distorcidas etc.), mas acho que essa é a direção certa para pensar teoricamente sobre essas coisas.

gabgoh
fonte
+1 Essa é uma opinião muito interessante sobre a questão. Nesse caso, o euclidiano pode ser considerado uma dessas métricas? À medida que a dimensionalidade é reduzida, os pontos são projetados em um espaço dimensional inferior, mas isso pode significar que a noção de distância pode ser perdida. Estou tendo dificuldades para ver como as distâncias podem ser preservadas ao usar reduções como essa.
Legend
1
Eu acho que essa resposta está basicamente certa. Você deseja encontrar alguma incorporação em um espaço menor que preserve distâncias (para alguma noção de distância). Dois bons algoritmos para verificar são Isomap e Incorporação local-linear . A "preservação da vizinhança" parece ser uma boa abordagem se o seu objetivo for agrupar.
Stumpy Joe Pete
5

Em resposta ao seu título "Quando combinamos redução de dimensionalidade com clustering?" ao invés da pergunta completa. Uma razão possível é óbvia: quando queremos garantir discrepâncias agaístas. K significa que algo, se sem dicas iniciais dos centros, separa k os pontos mais distantes da nuvem como centros iniciais, e, à direita, é provável que sejam discrepantes. Pregar pelo PCA neutraliza os outliers que se encontram ao longo dos componentes juniores - projetando-os nos poucos componentes seniores que são retidos no PCA.

ttnphns
fonte