Escolhendo um método de armazenamento em cluster

Ao usar a análise de cluster em um conjunto de dados para agrupar casos semelhantes, é preciso escolher entre um grande número de métodos de cluster e medidas de distância. Às vezes, uma escolha pode influenciar a outra, mas existem muitas combinações possíveis de métodos.

Alguém tem alguma recomendação sobre como escolher entre os vários algoritmos / métodos de clustering e medidas de distância ? Como isso está relacionado à natureza das variáveis ​​(por exemplo, categórica ou numérica) e ao problema de agrupamento? Existe uma técnica ideal?

Não há resposta definitiva para sua pergunta, pois mesmo dentro do mesmo método, a escolha da distância para representar a (des) semelhança de indivíduos pode produzir resultados diferentes, por exemplo, ao usar euclidiano versus euclidiano ao quadrado no agrupamento hierárquico. Como outro exemplo, para dados binários, você pode escolher o índice Jaccard como uma medida de similaridade e prosseguir com o cluster hierárquico clássico; mas existem abordagens alternativas, como a Mona ( Monothetic Analysis), que considera apenas uma variável de cada vez, enquanto outras abordagens hierárquicas (por exemplo, HC clássica, Agnes, Diana) usam todas as variáveis ​​em cada etapa. A abordagem k-means foi estendida de várias maneiras, incluindo particionamento em torno de medoóides (PAM) ou objetos representativos, em vez de centróides (Kaufman e Rousseuw, 1990) ou agrupamento nebuloso (Chung e Lee, 1992). Por exemplo, a principal diferença entre o k-mean e o PAM é que o PAM minimiza uma soma de dissimilaridades em vez de uma soma de distâncias euclidianas quadradas; o agrupamento difuso permite considerar a "associação parcial" (associamos a cada observação um peso que reflete a associação à classe). E para métodos baseados em uma estrutura probabilística ou no chamado cluster baseado em modelo (ou análise de perfil latentepara os psicometristas), há um ótimo pacote: Mclust . Então, definitivamente, você precisa considerar como definir a semelhança dos indivíduos, bem como o método para vincular os indivíduos (agrupamento recursivo ou iterativo, associação estrita ou difusa, classe não supervisionada ou semi-supervisionada, etc.).

Geralmente, para avaliar a estabilidade do cluster, é interessante comparar vários algoritmos que basicamente "compartilham" alguma semelhança (por exemplo, médias k e cluster hierárquico, porque a distância euclidiana funciona para ambos). Para avaliar a concordância entre duas soluções de cluster, foram sugeridos alguns indicadores em resposta a esta pergunta: Onde cortar um dendrograma? (consulte também as referências cruzadas para outro link neste site). Se você estiver usando R, verá que vários pacotes já estão disponíveis no Modo de Exibição de Tarefas na Análise de Cluster e vários pacotes incluem vinhetas que explicam métodos específicos ou fornecem estudos de caso.

Análise de Cluster: Conceitos Básicos e Algoritmos fornece uma boa visão geral de várias técnicas usadas na Análise de Cluster. Quanto a um bom livro recente com ilustrações de R, eu recomendaria o capítulo 12 de Izenman, Técnicas Estatísticas Modernas Multivariadas (Springer, 2008). Algumas outras referências padrão são dadas abaixo:

• Cormack, R., 1971. Uma revisão de classificação. Jornal da Sociedade Estatística Real, A 134, 321-367.
• Everitt, B., 1974. Análise de cluster . Londres: Heinemann Educ. Livros.
• Gordon, A., 1987. Uma revisão da classificação hierárquica. Jornal da Sociedade Estatística Real, A 150, 119–137.
• Gordon, A., 1999. Classificação , 2ª Edição. Chapman e Hall.
• Kaufman, L., Rousseuw, P., 1990. Encontrando Grupos em Dados: Uma Introdução à Análise de Cluster . Nova York, Wiley.

Uma citação de Hastie, Tibshirani e Friedman, Elements of Statistical Learning , p. 506:

"Uma medida de dissimilaridade apropriada é muito mais importante para obter sucesso com o agrupamento do que a escolha do algoritmo de agrupamento. Esse aspecto do problema ... depende do conhecimento específico do domínio e é menos passível de pesquisa geral".

(Dito isto, não seria bom se (wibni) houvesse um site onde os alunos pudessem experimentar alguns algoritmos e métricas em alguns pequenos conjuntos de dados padrão?)

Você não pode saber antecipadamente qual algoritmo de agrupamento seria melhor, mas existem algumas dicas, por exemplo, se você deseja agrupar imagens, existem certos algoritmos que você deve tentar primeiro como o Fuzzy Art ou se deseja agrupar rostos, deve começar com agrupamento geométrico global (GGCI) para imagem.

De qualquer forma, isso não garante o melhor resultado, então o que eu faria é usar um programa que permita executar metodicamente diferentes algoritmos de cluster, como weka, RapidMiner ou mesmo R (que não é visual). Lá, configurarei o programa para inicie todos os algoritmos de clustering que puder, com todas as distâncias possíveis e, se eles precisarem de parâmetros, experimente cada um com uma variedade de valores de parâmetros diferentes (além disso, se eu não souber a quantidade de clusters, execute cada um com uma variedade de números). Depois de concluir o experimento, deixe-o em execução, mas lembre-se de armazenar em algum lugar os resultados de cada execução de cluster.

Em seguida, compare os resultados para obter o melhor cluster resultante. Isso é complicado porque há várias métricas que você pode comparar e nem todas são fornecidas por todos os algoritmos. Por exemplo, algoritmos de cluster nebuloso têm métricas diferentes das não nebulosas, mas ainda podem ser comparados considerando os grupos resultantes nebulosos como não nebulosos, farei a comparação com as métricas clássicas, como:

• SSE: soma do erro quadrado dos itens de cada cluster.

• Distância entre clusters: soma da distância quadrada entre cada centróide do cluster.

• Distância intra cluster para cada cluster: soma da distância quadrada entre os itens de cada cluster e seu centróide.

• Raio máximo: a maior distância de uma instância ao centróide do cluster.

• Raio médio: soma da maior distância de uma instância ao centróide do cluster, dividida pelo número de clusters.

Escolher a distância certa não é uma tarefa elementar. Quando queremos fazer uma análise de cluster em um conjunto de dados, resultados diferentes podem aparecer usando distâncias diferentes, por isso é muito importante ter cuidado em qual distância escolher, pois podemos criar um artefato falso bom que captura bem a variabilidade, mas na verdade sem sentido em nosso problema.

A distância euclidiana é apropriada quando tenho variáveis ​​numéricas contínuas e quero refletir distâncias absolutas. Essa distância leva em consideração todas as variáveis ​​e não remove redundâncias, portanto, se eu tivesse três variáveis ​​que explicam o mesmo (estão correlacionadas), ponderaria esse efeito em três. Além disso, essa distância não é invariável à escala, então geralmente tenho que escalar anteriormente para usar a distância.
Exemplo de ecologia: Temos observações diferentes de muitas localidades, das quais os especialistas coletaram amostras de alguns fatores microbiológicos, físicos e químicos. Queremos encontrar padrões nos ecossistemas. Esses fatores têm uma alta correlação, mas sabemos que todos são relevantes, portanto, não queremos remover essas redundâncias. Usamos a distância euclidiana com dados em escala para evitar o efeito de unidades.

A distância de Mahalanobis é apropriada quando tenho variáveis ​​numéricas contínuas e quero refletir distâncias absolutas, mas queremos remover redundâncias. Se tivermos variáveis ​​repetidas, seu efeito repetitivo desaparecerá.

A família Hellinger , Species Profile e Chord distance são apropriadas quando queremos enfatizar as diferenças entre as variáveis, quando queremos diferenciar perfis. Essas distâncias pesam em quantidades totais de cada observação, de tal forma que as distâncias são pequenas quando variáveis ​​por variáveis, os indivíduos são mais semelhantes, embora em magnitudes absolutas fosse muito diferente. Cuidado! Essas distâncias refletem muito bem a diferença entre perfis, mas perdem o efeito de magnitude. Eles podem ser muito úteis quando temos diferentes tamanhos de amostra. Exemplo de ecologia: queremos estudar a fauna de muitas terras e temos uma matriz de dados de um inventário do gastrópode (locais de amostragem em linhas e nomes de espécies em colunas). A matriz é caracterizada por ter muitos zeros e magnitudes diferentes, porque algumas localidades têm algumas espécies e outras têm outras espécies. Poderíamos usar a distância de Hellinger.

Bray-Curtis é bastante semelhante, mas é mais apropriado quando queremos diferenciar perfis e também levar em consideração as magnitudes relativas.

Para mim, se você quiser uma escolha segura, os métodos de agrupamento espectral têm atingido as mais altas taxas de precisão nos últimos anos - pelo menos no agrupamento de imagens.

Quanto à métrica de distância, depende muito de como seus dados são organizados. A opção segura é a distância euclidiana simples, mas se você souber que seus dados contêm coletores, mapeie os pontos através dos métodos do kernel.

PS: todos eles estão relacionados a valores numéricos, não categóricos. Não tenho certeza de como alguém poderia agrupar dados categóricos.

Aqui está um resumo de vários algoritmos de armazenamento em cluster que podem ajudar a responder à pergunta

"qual técnica de agrupamento devo usar?"

Não há objetivamente "correta" algoritmo de agrupamento Ref

Os algoritmos de cluster podem ser classificados com base em seu "modelo de cluster". Um algoritmo projetado para um tipo específico de modelo geralmente falha em um tipo diferente de modelo. Por exemplo, os meios-k não conseguem encontrar aglomerados não convexos, podem encontrar apenas aglomerados de formato circular.

Portanto, entender esses "modelos de cluster" se torna a chave para entender como escolher entre os vários algoritmos / métodos de cluster. Os modelos de cluster típicos incluem:

[1] Modelos de conectividade: constrói modelos com base na conectividade à distância. Por exemplo, cluster hierárquico. Usado quando precisamos de particionamento diferente com base na altura de corte da árvore. Função R: hclust no pacote de estatísticas.

[2] Modelos centróides: constrói modelos representando cada cluster por um único vetor médio. Usado quando precisamos de particionamento nítido (em oposição ao cluster nebuloso descrito posteriormente). Função R: kmeans no pacote de estatísticas.

[3] Modelos de distribuição: constrói modelos baseados em distribuições estatísticas, como distribuições normais multivariadas usadas pelo algoritmo de maximização de expectativa. Usado quando as formas de cluster podem ser arbitrárias, ao contrário de k-means, que assume clusters circulares. Função R: emcluster na embalagem do emcluster.

[4] Modelos de densidade: constrói modelos baseados em clusters como regiões densas conectadas no espaço de dados. Por exemplo, DBSCAN e OPTICS. Usado quando as formas de cluster podem ser arbitrárias, diferentemente do k-means, que assume clusters circulares. Função R dbscan no pacote dbscan.

[5] Modelos de subespaço: constrói modelos baseados em membros de cluster e atributos relevantes. Por exemplo, biclustering (também conhecido como co-clustering ou cluster de dois modos). Usado quando o cluster simultâneo de linhas e colunas é necessário. Função R biclust no pacote biclust.

[6] Modelos de grupo: constrói modelos com base nas informações de agrupamento. Por exemplo, filtragem colaborativa (algoritmo de recomendação). Função R Recomendador no pacote recomenderlab.

[7] Modelos baseados em gráficos: constrói modelos baseados em clique. Os algoritmos de detecção da estrutura da comunidade tentam encontrar subgráficos densos em gráficos direcionados ou não direcionados. Por exemplo, função R cluster_walktrap no pacote igraph.

[8] Mapa de recursos auto-organizáveis ​​de Kohonen: constrói modelos baseados em redes neurais. Função R som no pacote kohonen.

[9] Clustering espectral: constrói modelos com base na estrutura de conglomerados não convexos ou quando uma medida do centro não é uma descrição adequada do cluster completo. Função R specc no pacote kernlab.

[10] agrupamento de subespaços: para dados de alta dimensão, as funções de distância podem ser problemáticas. modelos de cluster incluem os atributos relevantes para o cluster. Por exemplo, função hddc no pacote R HDclassif.

[11] Agrupamento de sequências: agrupe sequências relacionadas. Pacote rBlast.

[12] Propagação por afinidade: constrói modelos com base na passagem de mensagens entre pontos de dados. Não requer que o número de clusters seja determinado antes da execução do algoritmo. É melhor para determinadas tarefas de visão computacional e biologia computacional, por exemplo, agrupar imagens de rostos humanos e identificar transcrições regulamentadas do que k-means, Ref Rpackage APCluster.

[13] Cluster de fluxo: cria modelos baseados em dados que chegam continuamente, como registros telefônicos, transações financeiras etc. Por exemplo, pacote R BIRCH [ https://cran.r-project.org/src/contrib/Archive/birch/]

[14] Cluster de documentos (ou cluster de texto): constrói modelos baseados em SVD. Ele foi usado na extração de tópicos. Por exemplo, o Carrot [ http://search.carrot2.org] é um mecanismo de cluster de resultados de pesquisa de código aberto que pode agrupar documentos em categorias temáticas.

[15] Modelo de classe latente: relaciona um conjunto de variáveis ​​multivariadas observadas a um conjunto de variáveis ​​latentes. A ACV pode ser usada na filtragem colaborativa. Função R O recomendador no pacote recomenderlab possui a funcionalidade de filtragem colaborativa.

[16] Biclustering: usado para agrupar simultaneamente linhas e colunas de dados em dois modos. Por exemplo, função R biclust na embalagem biclust.

[17] Agrupamento suave (agrupamento difuso): cada objeto pertence a cada cluster até um certo grau. Por exemplo, função R Fclust na embalagem fclust.