Índice Dunn

O Índice Dunn (introduzido por J. C. Dunn em 1974) é uma métrica para avaliar algoritmos de clusterização (agrupamento). Isso faz parte de um grupo de índices de validação, incluindo o Índice de Davies-Bouldin ou Índice de Silhueta, no sentido de que é um esquema de avaliação interna, onde o resultado é baseado nos próprios dados agrupados. Como todos os outros índices desse tipo, o objetivo é identificar conjuntos de agrupamentos que sejam compactos, com uma pequena variância entre os membros do agrupamento, e bem separados, onde as médias de diferentes agrupamentos estão suficientemente distantes, em comparação com a variância dentro do agrupamento.

Para uma atribuição dada de agrupamentos, um índice de Dunn mais alto indica um melhor agrupamento. Uma das desvantagens de usar isso é o custo computacional à medida que o número de agrupamentos e a dimensionalidade dos dados aumentam.

Preliminares

Antes de falarmos de fato sobre o índice Dunn, precisamos explicitar algumas coisas mais gerais que se aplicam na validade de um cluster.

Classes de validação

As medidas de validade de clusters, usadas para avaliar a qualidade ou a validade de agrupamentos de dados, podem ser classificadas em três categorias distintas. Essas categorias podem representar diferentes abordagens ou critérios usados para avaliar a eficácia de algoritmos de clustering.

1. Validação de cluster interno:
   • O resultado do cluster é avaliado com base nos próprios dados clusterizados (informações internas) sem referência a informações externas, como por exemplo rótulos verdadeiros ou classes conhecidas.
   • O indice Dunn pertence a essa classe de validação.
2. Validação de cluster externo:
   • Os resultados do cluster são avaliados com base em algum resultado conhecido externamente, como rótulos de classe fornecidos externamente.
3. Validação relativa de cluster
   • Os resultados do cluster são avaliados variando diferentes parâmetros para o mesmo algoritmo (por exemplo, alterando o número de clusters).

Distâncias (intercluster e intraclusters)

Outro conceito muito importante quando falamos sobre análise de clusters esta relacionado à validação e avaliação da qualidade dos agrupamentos.

Para isso, é crucial entender como os clusters estão separados uns dos outros (distância intercluster) e quão coesos são internamente (distância intracluster). A combinação dessas métricas pode fornecer uma visão abrangente da qualidade do agrupamento resultante.

Distância intracluster

Essa métrica avalia quão similares são os pontos dentro de um cluster em comparação com outros clusters, isso é, expressa o quão coesão ou disperso é cluster. O diâmetro é uma maneira comum de representar a distância intracluster, sendo definido como a maior distância entre dois pontos dentro do mesmo cluster.

Existem muitas maneiras de defini-la:

1. Pode ser a distância entre os pontos mais distantes dentro de um cluster.
2. Pode ser a média de todas as distâncias entre pares de pontos de dados dentro do cluster.
3. Pode ser a distância de cada ponto de dados do centroide do cluster.

Cada uma dessas formulações é mostrada matematicamente abaixo:

Seja C_i um agrupamento de vetores. Sejam x e y dois vetores de características n dimensionais atribuídos ao mesmo agrupamento C_i.

1. $\Delta _{i}={\underset {x,y\in C_{i}}{\text{max}}}d(x,y),$ que calcula a distância máxima (a versão proposta por Dunn).
2. $\Delta _{i}={\dfrac {2}{|C_{i}|(|C_{i}|-1)}}{\underset {x,y\in C_{i},x\neq y}{\sum }}d(x,y),$ que calcula a distância média entre todos os pares.
3. $\Delta _{i}={\dfrac {{\underset {x\in C_{i}}{\sum }}d(x,\mu )}{|C_{i}|}},\mu ={\dfrac {{\underset {x\in C_{i}}{\sum }}x}{|C_{i}|}},$ calcula a distância de todos os pontos da média.

Distância intercluster

Essa métrica avalia quão separados ou distintos são os clusters uns dos outros, isso é, refere-se à medida de distância ou dissimilaridade entre dois clusters distintos.

Existem muitas maneiras de defini-la:

1. A distância mínima entre dois objetos pertencentes a clusters distintos (Single-linkage clustering). Foi a utilizada por J. C. Dunn.
2. A distância máxima entre qualquer ponto de dados no primeiro cluster e qualquer ponto de dados no segundo cluster (Complete-linkage clustering)
3. A distância média entre todos os objetos pertencentes a dois clusters distintos (Average linkage distance)
4. A distância entre o centróide de dois clusters distintos (Centroid linkage distance)

Cada uma dessas formulações é mostrada matematicamente abaixo:

Seja:

• $d(x,y)$ a distância entre os elementos $x\in X$ e $y\in Y$;
• $X$ e $Y$ dois conjuntos de elementos (clusters);
• $D(X,Y)$ a distância entre os dois clusters $X$ e $Y$;
• $|X|$ e $|Y|$ o número de elementos em cada cluster respectivamente;
• $c_{X}$ e $c_{Y}$ os centróides dos respectivos clusters;
• $d(c_{X},c_{Y})$ a distância entre os centróides.

Temos que,

1. $D(X,Y)=\min _{x\in X,y\in Y}d(x,y),$ representa a distância de ligação única (Single-linkage clustering).
2. $D(X,Y)=\max _{x\in X,y\in Y}d(x,y),$ representa a distância de ligação completa (Complete-linkage clustering)
3. $D(X,Y)={\frac {\sum _{x\in X}\sum _{y\in Y}d(x,y)}{|X|\times |Y|}},$ representa a distância média de ligação (Average linkage distance)
4. $D(X,Y)=d(c_{X},c_{Y}),$ representa a distância de ligação do centróide (Centroid linkage distance)

Logo, as distâncias entre clusters fornecem uma maneira de quantificar a separação ou proximidade entre grupos de dados, permitindo uma compreensão mais aprofundada da estrutura implícita dos dados.

Definição

Logo, seja C_i um agrupamento de vetores e seja x e y dois vetores de características n dimensionais atribuídos ao mesmo agrupamento C_i.

Com a notação acima, se houver m agrupamentos, então o Índice de Dunn para o conjunto é definido como:

${\mathit {DI}}_{m}={\frac {{\underset {1\leqslant i<j\leqslant m}{\text{min}}}\left.\delta (C_{i},C_{j})\right.}{{\underset {1\leqslant k\leqslant m}{\text{max}}}\left.\Delta _{k}\right.}}$.

Pela formula, conseguimos perceber que o índice Dunn compara a distância mínima entre clusters (separação) com a distância máxima dentro de cada cluster (coesão). O objetivo é maximizar a separação e minimizar a coesão, em outras palavras, ele procura agrupamentos onde a distância entre clusters é grande em comparação com a distância dentro dos clusters, sendo indicativo de clusters compactos e bem separados.

Explicação

Sendo definido dessa maneira, o DI depende de m, o número de agrupamentos no conjunto. Se o número de agrupamentos não for conhecido a priori, o m para o qual o DI é o mais alto pode ser escolhido como o número de agrupamentos. Também há alguma flexibilidade quando se trata da definição de d(x,y) onde qualquer uma das métricas conhecidas pode ser usada, como a distância de Manhattan ou distância euclidiana com base na geometria do problema de agrupamento. Esta formulação tem um problema peculiar, pois se um dos agrupamentos se comporta mal, enquanto os outros estão bem agrupados, uma vez que o denominador contém um termo 'max' em vez de um termo médio, o Índice de Dunn para esse conjunto de agrupamentos será atipicamente baixo. Isso é, portanto, um indicador de pior caso e deve ser levado em consideração. Existem implementações prontas do índice de Dunn em algumas linguagens de programação baseadas em vetores como MATLAB, R e Apache Mahout.

Implementação

Por se tratar de uma métrica conhecida quando se fala em índices para avaliar a qualidade de clusters, diversas linguagens apresentam implementações já prontas em suas bibliotecas padrão ou em específicas.

• No R, ela pode ser encontrada em dentro do pacote, clValid: Validation of Clustering Results. Para saber mais sobre os detalhes de implementação, consulte aqui.
• Abaixo, um exemplo em R de utilização da biblioteca:

library(clValid)

data(mouse)

express <- mouse[1:25,c("M1","M2","M3","NC1","NC2","NC3")]

rownames(express) <- mouse$ID[1:25]

## hierarchical clustering

clusterObj <- hclust(Dist, method="average")

nc <- 2 ## number of clusters

cluster <- cutree(clusterObj,nc)

dunn(Dist, cluster)

• No Python, ela deveria ser encontrada no pacote chamado "jqmcvi" , porém ao tentar usar os comandos from jqmcvi import base ou pip install jqmcvi, erros podem aparecer.
• Isso ocorre, pois aparentemente essa biblioteca não esta instalada no Python Package Index (PyPI), para encontrar se uma biblioteca ainda se encontra ou não listada, entre aqui.
• Uma alternativa é instalar diretamente do github de pessoas que implementaram esse método, por exemplo aqui. Porém, cuidado ao baixar algo malicioso, estou indicando apenas para ter uma alternativa e assim não precise implementa-la do zero.

Ligações externas

• Pakhira, Malay K.; Bandyopadhyay, Sanghamitra; Maulik, Ujjwal (2004). «Índice de validade para agrupamentos nítidos e difusos». Pattern Recognition. 37 (3): 487–501. Bibcode:2004PatRe..37..487P. doi:10.1016/j.patcog.2003.06.005 
• Bezdek, J.C.; Pal, N.R. (1995). «Validação de agrupamentos com índices generalizados de Dunn». Proceedings 1995 Second New Zealand International Two-Stream Conference on Artificial Neural Networks and Expert Systems. [S.l.]: IEEE Xplore. pp. 190–193. ISBN 0-8186-7174-2. doi:10.1109/ANNES.1995.499469 
• «Agglomerative Hierarchical Clustering». Consultado em 19 de dezembro de 2022 
• «Dunn index and DB index – Cluster Validity indices». Consultado em 19 de dezembro de 2022 
• «What are some challenges and limitations of cluster analysis using Davies-Bouldin index?». Consultado em 23 de dezembro de 2022