Existem casos em que não há k ideal em k-médias?

11

Isso está em minha mente há pelo menos algumas horas. Eu estava tentando encontrar um k ideal para a saída do algoritmo k-means (com uma métrica de similaridade de cosseno ), então acabei plotando a distorção em função do número de clusters. Meu conjunto de dados é uma coleção de 800 documentos em um espaço de 600 dimensões.

Pelo que entendi, encontrar o ponto do joelho ou o cotovelo nessa curva deve indicar pelo menos aproximadamente o número de clusters nos quais preciso colocar meus dados. Coloquei o gráfico abaixo. O ponto em que a linha vertical vermelha foi traçada foi obtido usando o teste de segunda derivada máxima . Depois de fazer tudo isso, fiquei preso a algo muito mais simples: o que esse gráfico me diz sobre o conjunto de dados?

Isso me diz que não vale a pena agrupar e que meus documentos não têm estrutura ou que preciso definir um k muito alto? Uma coisa estranha é que, mesmo com baixo k, estou vendo documentos semelhantes sendo agrupados, por isso não sei por que estou conseguindo essa curva. Alguma ideia?

insira a descrição da imagem aqui

machine-learning clustering k-means lenda
fonte
2
O que sinceramente não entendo é como você foi capaz de empregar um cluster de k-means com entrada da matriz de proximidade (e isso é cosseno!). O cluster K-means precisa de entrada de dados brutos (objetos X variáveis) e opera internamente na distância euclidiana.
ttnphns
2
@ttnphns: Espero ter entendido seu ponto de vista, mas, pelo que sei, podemos usar qualquer métrica de distância com k-means, não é? Estou fazendo isso em Python, mas parece que existe até uma biblioteca disponível para R: cran.r-project.org/web/packages/skmeans/index.html A entrada não era uma matriz de proximidade, mas sim uma terms x documentobtida após a execução de um vetor singular decomposição. Por favor, corrija-me se eu estiver enganado.
Legend
O agrupamento esférico de k-meios , baseado na medida do cosseno, é novo para mim, devo admitir. Espero ler mais sobre isso um dia.
ttnphns
@ttnphns: Obrigado por voltar. Só queria ter certeza que eu não estava usando maçãs e laranjas juntos :)
Legend
K-médias não modificadas são sensíveis apenas a -Norms. Porque calcula vetores médios e isso não é uma estimativa de ML apropriada para outras funções de distância. Lp
QuIT - Anony-Mousse

Respostas:

12

Na maioria das situações, eu pensaria que esse gráfico significa basicamente que não há estrutura de cluster nos dados. No entanto, agrupar em dimensões muito altas como essa é complicado, pois para a métrica de distância euclidiana todas as distâncias tendem a ser iguais à medida que o número de dimensões aumenta. Veja esta página da Wikipedia para referências a alguns documentos sobre este tópico. Em suma, pode ser apenas a alta dimensionalidade do conjunto de dados que é o problema.

Isso é essencialmente "a maldição da dimensionalidade", veja esta página da Wikipedia também.

Um artigo que pode ser interessante é Sanguinetti, G., "Redução de dimensionalidade de conjuntos de dados em cluster", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 30 no. 3, pp. 535-540, março de 2008 ( www ). O que é um pouco como uma versão não supervisionada do LDA que procura um espaço de baixa dimensão que enfatiza a estrutura do cluster. Talvez você possa usar isso como um método de extração de recursos antes de executar k-means?

Dikran Marsupial
fonte
OPA, desculpe. Eu deveria ter mencionado que estou usando similaridade de cosseno.
Legenda
Eu acho que é bem provável que a maldição da dimensionalidade também se aplique à semelhança de cosseno. Basicamente, diz que você precisa (no pior dos casos) exponencialmente de mais padrões para definir uma distribuição à medida que o número de dimensões aumenta. Ao agrupar em cluster, o que você está efetivamente fazendo é identificar distribuições representando subpopulações, portanto, agrupar em altas dimensões provavelmente será inerentemente complicado.
Dikran Marsupial
+1 Obrigado pelo link. Vou passar por isso e voltar. Eu apliquei o SVD na minha matriz original antes de aplicar o k-means para reduzir o número de dimensões.
Legend
3

Como exatamente você usa a semelhança de cosseno? É isso que é chamado de K-means esférico? Seu conjunto de dados é muito pequeno, então eu tentaria visualizá-lo como uma rede. Para isso, é natural usar uma similaridade (de fato, por exemplo, a similaridade de cosseno ou correlação de Pearson), aplicar um ponto de corte (considerar apenas relações acima de uma certa similaridade) e visualizar o resultado como uma rede, por exemplo, Cytoscape ou BioLayout . Isso pode ser muito útil para ter uma ideia dos dados. Segundo, eu computaria os valores singulares para sua matriz de dados ou os valores próprios de uma matriz adequadamente transformada e normalizada (uma matriz documento-documento obtida de alguma forma). A estrutura de cluster (novamente) deve aparecer como um salto na lista ordenada de autovalores ou valores singulares.

micans
fonte
+1 Obrigado pelos ponteiros. Eu não estava ciente do Cytoscape. Vou tentar isso. E sim, parece que os meios-k com similaridade de cosseno são chamados de meios-esféricos. Eu apliquei esse k-means após aplicar o SVD e reduzir o número de dimensões. A maneira como reduzi o número de dimensões foi usar a regra de variação (escolha os valores singulares que contribuem para 95% da variação nos dados originais).
Legend
Se você não se importa, poderia apontar para um tutorial que explica como fazer isso (ou pelo menos algo assim). Depois de gerar a matriz, exporto-a e importo-a no Cytoscape e execute o que você sugeriu? O que me interessa é se o Cytoscape possui métodos internos para similaridade de cosseno ou devo precomputar algum formato de dados e fornecê-lo como entrada?
Legend
Quando trabalho com esses programas, calculo externamente todas as semelhanças em pares, filtre por limite e produzo um arquivo com o formato <label1> <label2> <similarity>. Qualquer um deve poder ler essa entrada. No BioLayout, deve haver um sufixo .txt, eu acho; no CytoScape use 'importar da tabela'.
micans
Entendido. Eu farei isso e voltarei em breve. Agradeço novamente.
Legenda
Desculpe a pergunta idiota, mas eu formatei meus dados como <label1> <label2> <similarity>, mas não consigo descobrir como importá-los exatamente. Eu fiz Arquivo-> Importar-> Rede da Tabela e selecionei minhas colunas de origem e destino. Deixei a interação como padrão. Mas como devo importar pesos das arestas junto com as arestas? Você tem alguma sugestão, por favor?
Legenda
2

Geralmente sim, o k-means pode convergir para soluções muito distintas que podem ser julgadas inadequadas. Isso acontece principalmente para clusters com formas irregulares.

Para obter mais intuição, você também pode tentar outra abordagem de visualização: para k-means, você pode visualizar várias execuções com k-means usando o Graphgrams (consulte o pacote de grafos WEKA - melhor obtido pelo gerenciador de pacotes ou aqui . Uma introdução e exemplos também podem ser encontrado aqui .

Johannes Schneider
fonte
1

Se eu entendi o gráfico corretamente, é um gráfico do número de clusters, K no eixo x e a distância dentro dos clusters no eixo y?

Como a função objetivo do K-means é minimizar o WCSS, esse gráfico deve sempre diminuir monotonicamente. À medida que você adiciona mais clusters, a distância entre os pontos no cluster sempre diminui. Esse é o problema fundamental da seleção de modelos, então você precisa empregar um pouco mais de sofisticação.

Talvez tente a estatística Gap: www-stat.stanford.edu/~tibs/ftp/gap.ps ou outros semelhantes.

Além disso, você pode achar que o K-means não é a ferramenta certa para o trabalho. Quantos clusters você espera encontrar? O uso da regra de variação para redução de dimensionalidade para cluster não é apropriado. Consulte este documento para quando projetar nos primeiros PCs K-1 é uma medida de pré-processamento apropriada: http://people.csail.mit.edu/gjw/papers/jcss.ps

Você pode ver rapidamente se isso é o correto, plotando a projeção nos dois primeiros componentes principais. Se houver uma separação clara, o K-significa deve estar bem; caso contrário, você precisa procurar outra coisa. Talvez subespaços K ou outros métodos de agrupamento de subespaços. Lembre-se de que esses métodos se aplicam à distância euclidiana. Não tenho certeza de como isso muda para o cosseno.

bmc
fonte