Análise de desempenho de algoritmos de agrupamento

Question

Eu recebi 2 conjuntos de dados e desejo realizar análise de cluster para os conjuntos usando Knime.

Depois de ter completado o agrupamento, desejo realizar uma comparação de desempenho de 2 algoritmos diferentes de cluster.

No que diz respeito à análise de desempenho dos algoritmos de cluster, isso seria uma medida de tempo (complexidade de tempo de algoritmo e o tempo necessário para realizar o agrupamento dos dados, etc) ou a validade da saída dos clusters?(ou ambos)

Existe algum outro ângulo um olhar para identificar o desempenho (ou falta de) para um algoritmo de agrupamento?

Muito obrigado antecipadamente,

• t

Answer 1

depende muito de quais dados você tem disponível.

Uma maneira comum de medir o desempenho é em relação aos rótulos existentes ("externos") (embora isso faria mais sentido para classificação do que para agrupamento).Existem cerca de duas dúzias de medidas que você pode usar para isso.

Ao usar uma medida de qualidade "interna", certifique-se de que seja independente dos algoritmos.Por exemplo, K-significa otimiza essa medida e sempre sairá melhor ao avaliar com relação a essa medida.

Answer 2

Existem duas categorias de métodos de avaliação em cluster e a escolha depende se uma verdade terrestre está disponível. A primeira categoria é os métodos extrínsecos que exigem a existência de uma verdade terrestre e a outra categoria são os métodos intrínsecos. Em geral, os métodos extrínsecos tentam atribuir uma pontuação a um agrupamento, dada a verdade do solo, enquanto os métodos intrínsecos avaliam o agrupamento examinando quão bem os clusters são separados e como são compactos.

Para métodos extrínsecos (lembre-se que você precisa ter um terreno disponível) uma opção é usar as métricas de precisão e recuperação do BCubed. As métricas de precinas e recall da BCubed diferem da precisão tradicional e da recordação no sentido de que o agrupamento é uma técnica de aprendizagem não supervisionada e, portanto, não sabemos os rótulos dos clusters de antemão. Por esta razão, as métricas Bacubed avaliam a precion e a recordação para o objeto EVRY em um agrupamento em um determinado conjunto de dados de acordo com a verdade do solo. A precisão de um exemplo é uma indicação de quantos outros exemplos no mesmo cluster pertencem à mesma categoria do exemplo. A recordação de um exemplo reflete quantos exemplos da mesma categoria são atribuídos ao mesmo cluster. Finalmente, podemos combinar essas duas métricas em uma usando a métrica F2.

Fontes:

.
1. conceitos de mineração de dados e técnicas de Jiawei Han, Micheline, Kamber e Jian Pei
2. http://www.cs.utsa.edu / ~qitian/seminar/spring11/03_11_11/IR2009.pdf
3. minha própria experiência em avaliar o desempenho do agrupamento

Answer 3

Uma abordagem simples para os métodos extrínsecos onde há uma verdade do solo disponível é usar uma métrica de distância entre clusterings; A verdade do solo é simplesmente considerada como um agrupamento. Duas boas medidas a serem usadas são a variação da informação de Meila e, na minha humilde opinião, a Divisão participa da distância por mim também discutida por Meila. Eu não recomendo o índice Mirkin ou o índice Rand - eu escrevi mais sobre isso aqui em StackExchange .

Todas essas métricas podem ser divididas em duas partes constituintes, cada uma representando a distância de um dos clusterings para o maior subclustering comum. Vale a pena considerar as duas partes; Se a parte da verdade terrestre (para subclustering comum) é muito pequena, significa que o agrupamento testado está próximo de um superclustering; Se a outra parte for pequena, significa que o agrupamento testado está próximo ao subclustering comum e, portanto, perto de um subclustering da verdade do solo. Em ambos os casos, o agrupamento pode ser considerado compatível com a verdade terrestre. Para mais informações, consulte o link acima.

Answer 4

Existem vários benchmarks para a avaliação de algoritmos de agrupamento com medidas de qualidade extrínsecas (precisão) e medidas intrínsecas (algumas estatísticas internas dos clusters formados):

• Clubmark demonstrado em ICDM'18
• WebOcd , veja a descrição no papel
• Circo
• parallelCométrico
• clusim
• codar (as fontes podem ser adquiridas a partir do Papel Autores) < / li >.

A seleção do benchmark apropriado depende do tipo do algoritmo de agrupamento (agrupamento duro ou macio), tipo (relações pareadas, conjuntos de dados atribuídos ou misturados) e tamanho dos dados de agrupamento, as métricas de avaliação necessárias e a quantidade admissível da supervisão . O papel de clube descreve critérios de avaliação em detalhes.

O Clubmark é desenvolvido para a avaliação paralela totalmente automática de muitos algoritmos de cluster (processamento de dados de entrada especificados pelas relações pares) em muitos conjuntos de dados grandes (milhões e bilhões de elementos de cluster) e avaliados principalmente por Métricas de precisão Rastreamento de recursos de rastreamento (processamento e tempo de execução, consumo de memória residente pico, etc.). .

Mas para alguns algoritmos em alguns conjuntos de dados, até mesmo a avaliação manual é apropriada.