Davies–Bouldin

O Índice Davies–Bouldin (DBI), introduzido por David L. Davies e Donald W. Bouldin em 1979, é uma métrica para avaliar algoritmos de agrupamento.^[1] Esta é uma abordagem de avaliação interna, onde a validação de quão bem o agrupamento foi feito é realizada usando quantidades e características inerentes ao conjunto de dados. Isso tem uma desvantagem, pois um bom valor relatado por este método não implica na melhor recuperação de informações.

Para uma atribuição dada de agrupamentos, um índice Davies–Bouldin (DB) mais baixo indica um melhor agrupamento (clusters). Uma das desvantagens de usar esse índice é o custo computacional à medida que o número de agrupamentos e a dimensionalidade dos dados aumentam.

Ele mede a dispersão intracluster e a separação intercluster, logo um valor mais baixo do DB sugere que os clusters estão mais compactos e melhor separados, indicando uma configuração de agrupamento mais eficaz.

Por que é necessário a existência desses índices de validação de cluster?

• Para comparar algoritmos de cluster.
• Para comparar dois conjuntos de clusters distintos.
  • Isso é, qual deles é melhor em termos de compactação e conectividade por exemplo.
• Para determinar se existe estrutura aleatória nos dados devido ao ruído.

Preliminares

Antes de falarmos de fato sobre o índice Davies–Bouldin, 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 agrupamento.

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 Davies–Bouldin 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.

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).
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)

Dando continuidade, temos que dado um conjunto de pontos de n dimensões, seja C_i um cluster de pontos de dados. Seja X_j um vetor de características de n dimensões atribuído ao cluster C_i.

${\displaystyle S_{i}=\left({\frac {1}{T_{i}}}\sum _{j=1}^{T_{i}}{\left|\left|X_{j}-A_{i}\right|\right|_{p}^{q}}\right)^{1/q}}$

Aqui, ${\displaystyle A_{i}}$ é o centroide de C_i e T_i é o tamanho do cluster i. ${\displaystyle S_{i}}$ é a raiz q-ésima do q-ésimo momento dos pontos no cluster i em relação à média. Se ${\displaystyle q=1}$ então ${\displaystyle S_{i}}$ é a distância média entre os vetores de características no cluster i e o centróide do cluster. Normalmente, o valor de p é 2, o que torna a distância uma função de distância euclidiana. Muitas outras métricas de distância podem ser usadas, no caso de variedades e dados de dimensões mais altas, onde a distância euclidiana pode não ser a melhor medida para determinar os clusters. É importante observar que essa métrica de distância deve corresponder à métrica usada no esquema de agrupamento em si para resultados significativos.

${\displaystyle M_{i,j}=\left|\left|A_{i}-A_{j}\right|\right|_{p}={\Bigl (}\displaystyle \sum _{k=1}^{n}\left|a_{k,i}-a_{k,j}\right|^{p}{\Bigr )}^{\frac {1}{p}}}$

${\displaystyle M_{i,j}}$ é uma medida de separação entre o cluster ${\displaystyle C_{i}}$ e o cluster ${\displaystyle C_{j}}$.

${\displaystyle a_{k,i}}$ é o k-ésimo elemento de ${\displaystyle A_{i}}$, e há n tais elementos em A porque é um centróide de n dimensões.

Aqui, k indexa as características dos dados, e isso é essencialmente a distância euclidiana entre os centros dos clusters i e j quando p é igual a 2.

Definição

Deixe R_i,j ser uma medida de quão bom é o esquema de agrupamento. Essa medida, por definição, tem que levar em conta M_i,j, a separação entre o i^ésimo e o j^ésimo cluster, que idealmente deve ser o maior possível, e S_i, a dispersão dentro do cluster para o cluster i, que deve ser a menor possível. Portanto, o índice Davies–Bouldin é definido como a razão de S_i e M_i,j de forma que essas propriedades sejam conservadas:

1. ${\displaystyle R_{i,j}\geqslant 0}$.
2. ${\displaystyle R_{i,j}=R_{j,i}}$.
3. Quando ${\displaystyle S_{j}\geqslant S_{k}}$ e ${\displaystyle M_{i,j}=M_{i,k}}$ então ${\displaystyle R_{i,j}>R_{i,k}}$.
4. Quando ${\displaystyle S_{j}=S_{k}}$ e ${\displaystyle M_{i,j}\leqslant M_{i,k}}$ então ${\displaystyle R_{i,j}>R_{i,k}}$.

Com essa formulação, quanto menor o valor, melhor a separação dos clusters e a 'coesão' dentro dos clusters.

Uma solução que satisfaz essas propriedades é:

${\displaystyle R_{i,j}={\frac {S_{i}+S_{j}}{M_{i,j}}}}$

Isso é usado para definir D_i:

${\displaystyle D_{i}\equiv \max _{j\neq i}R_{i,j}}$

Se N é o número de clusters:

${\displaystyle {\mathit {DB}}\equiv {\frac {1}{N}}\displaystyle \sum _{i=1}^{N}D_{i}}$

DB é chamado de índice Davies–Bouldin. Isso depende tanto dos dados quanto do algoritmo. D_i escolhe o pior cenário, e esse valor é igual a R_i,j para o cluster mais semelhante ao cluster i. Pode haver muitas variações dessa formulação, como escolher a média da semelhança do cluster, média ponderada, entre outros.

Explicação

Valores mais baixos do índice indicam um resultado de agrupamento melhor. O índice é aprimorado (reduzido) pelo aumento da separação entre clusters e pela diminuição da variação dentro dos clusters.

Essas condições limitam o índice definido a ser simétrico e não negativo. Devido à maneira como é definido, como uma função da razão entre a dispersão dentro do cluster e a separação entre clusters, um valor menor significará que o agrupamento é melhor. Acontece de ser a semelhança média entre cada cluster e seu mais semelhante, em média sobre todos os clusters, onde a semelhança é definida como S_i acima. Isso afirma a ideia de que nenhum cluster precisa ser semelhante a outro e, portanto, o melhor esquema de agrupamento minimiza essencialmente o índice Davies–Bouldin. Esse índice, assim definido, é uma média de todos os clusters i, e portanto, uma boa medida de decidir quantos clusters realmente existem nos dados é plotá-lo em relação ao número de clusters sobre os quais é calculado. O número i para o qual esse valor é o menor é uma boa medida do número de clusters nos quais os dados poderiam ser idealmente classificados. Isso tem aplicações na decisão do valor de k no algoritmo kmeans, onde o valor de k não é conhecido a priori.

Vantagens do índice Davies-Bouldin

Uma das vantagens de utilizar o índice como critério de agrupamento é que ele não exige o conhecimento prévio do número real de clusters ou dos rótulos de cluster verdadeiros. Ele pode ser empregado para comparar diferentes algoritmos de agrupamento ou diversos números de clusters no mesmo conjunto de dados. Além disso, é relativamente fácil de calcular e interpretar, uma vez que possui um limite inferior claro de zero; assim, valores mais altos indicam uma qualidade de agrupamento inferior.

Desvantagens do índice Davies-Bouldin

Ele também possui limitações a serem consideradas. Pode ser sensível a outliers e ruídos, o que pode resultar em uma avaliação equivocada da qualidade do agrupamento. Além disso, sua suposição de formas esféricas com tamanhos e densidades semelhantes para cada cluster pode não refletir adequadamente a complexidade de muitos conjuntos de dados do mundo real.

Outro ponto a ser destacado é que o DBI não leva em conta a presença de estruturas mais complexas, como clusters dentro de clusters ou relações não-lineares entre os dados.

Dicas para usar o índice Davies-Bouldin

Se você optar por utilizar esse índice como métrica para avaliação de agrupamentos, algumas estratégias podem ser empregadas para aumentar sua confiabilidade e utilidade. Inicialmente, considera-se a importância do pré-processamento dos dados, visando remover ou reduzir outliers e ruídos. Técnicas como normalização, padronização ou redução de dimensionalidade podem ser aplicadas nesse sentido.

Além disso, é aconselhável escolher uma medida de distância ou similaridade adequada ao tipo de dados e ao domínio específico. Opções como distância euclidiana, distância Manhattan ou coeficiente de Jaccard podem ser exploradas, dependendo das características do seu conjunto de dados.

Por fim, experimentar diferentes algoritmos ou ajustes de parâmetros de clustering também é uma abordagem recomendada. A busca pelo número ideal de clusters, que minimize o valor de DBI, pode ser realizada utilizando métodos como o método do cotovelo ou a estatística gap, que se mostram particularmente úteis nesse contexto.^[2]

Versão suave do índice Davies–Bouldin

Recentemente, o índice Davies–Bouldin foi estendido para o domínio de categorias de agrupamento suave.^[3] Essa extensão é baseada na abordagem de agrupamento de categorias de acordo com o framework da lógica fuzzy. O ponto de partida para essa nova versão do índice de validação é o resultado de um determinado algoritmo de agrupamento suave (por exemplo, fuzzy c-means), moldado com as partições de agrupamento calculadas e os valores de associação de pertencimento que associam os elementos aos clusters. No domínio suave, cada elemento do sistema pertence a todas as classes, dados os valores de pertencimento. Portanto, esta versão suave do índice Davies–Bouldin é capaz levar em consideração, além das medidas padrão de validação, como compacidade e separação de clusters, o grau em que os elementos pertencem às classes.

Implementações

• A caixa de ferramentas SOM contém uma implementação em MATLAB.^[4] Uma implementação em MATLAB também está disponível através da MATLAB Statistics and Machine Learning Toolbox, utilizando o comando "evalclusters".^[5]
• Abaixo, um exemplo usando o método evalclusters:

rng("default")

n = 200;

mu1 = [2 2];

sigma1 = [0.9 -0.0255; -0.0255 0.9];

mu2 = [5 5];

sigma2 = [0.5 0; 0 0.3];

mu3 = [-2 -2];

sigma3 = [1 0; 0 0.9];

X = [mvnrnd(mu1,sigma1,n); ...

mvnrnd(mu2,sigma2,n); ...

mvnrnd(mu3,sigma3,n)];

evaluation = evalclusters(X,"kmeans","DaviesBouldin","KList",1:6)

• Para saber mais sobre a documentação, clique aqui.
• Uma implementação em Java pode ser encontrada no ELKI e pode ser comparada com muitos outros índices de qualidade de agrupamento. Para saber mais cobre a documentação, clique aqui.
• No Python, a implementação pode ser encontrada dentro do pacote 'sklearn.base', mais especificamente no módulo 'sklearn.metrics.davies_bouldin_score', que pode ser encontrado com mais detalhes aqui.
• Abaixo, um exemplo utilizando esse módulo:

from sklearn import datasets

iris = datasets.load_iris()

X = iris.data

from sklearn.cluster import KMeans

from sklearn.metrics import davies_bouldin_score

kmeans = KMeans(n_clusters=3, random_state=1).fit(X)

labels = kmeans.labels_

davies_bouldin_score(X, labels)

• Para o R, também existe uma implementação já criada. Ela pode ser encontrada importando a biblioteca 'clusterSim', e para mais detalhes a documentação se encontra aqui.
• Abaixo, um exemplo do método:

library(clusterSim)

data(data_ratio)

cl2 <- pam(data_ratio, 5)

print(index.DB(data_ratio, cl2$clustering, centrotypes="centroids"))

Ver também

• Pontuação da Silhueta
• Índice Dunn
• Análise de Cluster
• Índice Calinski-Harabasz
• Determinação do número de clusters em um conjunto de dados

Referências

1. Davies, David L.; Bouldin, Donald W. (1979). «A Cluster Separation Measure». IEEE Transactions on Pattern Analysis and Machine Intelligence. PAMI-1 (2): 224–227. doi:10.1109/TPAMI.1979.4766909 
2. «What are some challenges and limitations of cluster analysis using Davies-Bouldin index?»  Parâmetro desconhecido |https://www.linkedin.com/advice/0/what-some-challenges-limitations-cluster-analysis?lang= ignorado (ajuda); Em falta ou vazio |url= (ajuda); |acessodata= requer |url= (ajuda)
3. Vergani, Alberto A.; Binaghi, Elisabetta (Julho de 2018). «A Soft Davies-Bouldin Separation Measure». IEEE: 1–8. ISBN 978-1-5090-6020-7. doi:10.1109/FUZZ-IEEE.2018.8491581 
4. «Implementação em Matlab». Consultado em 12 de novembro de 2011 
5. «Avaliar soluções de agrupamento - MATLAB evalclusters»