Mostrar código-fonte de Davies–Bouldin

{{short description|Métrica para avaliar algoritmos de agrupamento}}

O '''Índice Davies–Bouldin (DBI)''', introduzido por David L. Davies e Donald W. Bouldin em 1979, é uma métrica para avaliar [[:en:Cluster analysis|algoritmos de agrupamento]].<ref>{{Cite journal | last1 = Davies | first1 = David L. | last2 = Bouldin | first2 = Donald W. | doi = 10.1109/TPAMI.1979.4766909 | title = A Cluster Separation Measure | journal = IEEE Transactions on Pattern Analysis and Machine Intelligence | volume = PAMI-1| issue = 2 | pages = 224–227 | year = 1979 | s2cid = 13254783 }}</ref> 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.

# '''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 i'''ndice Davies–Bouldin''' pertence a essa classe de validação.
# '''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.
# '''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:

# Pode ser a '''distância entre os pontos mais distantes dentro de um cluster.'''
# Pode ser a '''média de todas as distâncias entre pares de pontos de dados dentro do cluster.'''
# 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:

# A distância mínima entre dois objetos pertencentes a clusters distintos ([[:en:Single-linkage clustering#:~:text=In single-linkage clustering, the,are involved to be merged.|'''Single-linkage clustering''']]). 
# A distância máxima entre qualquer ponto de dados no primeiro cluster e qualquer ponto de dados no segundo cluster [[:en:Complete-linkage clustering|('''Complete-linkage clustering''')]]
# A distância média entre todos os objetos pertencentes a dois clusters distintos [https://www.solver.com/xlminer/help/hierarchical-clustering-intro#:~:text=In%20Average%20linkage%20clustering%2C%20the,one%20object%20from%20each%20group.&text=D(r%2Cs)%20%3D%20Trs%20%2F%20(%20N,cluster%20r%20and%20cluster%20s. ('''Average linkage distance''')]
# A distância entre o [[Centroide|centróide]] de dois clusters distintos [https://online.stat.psu.edu/stat505/lesson/14/14.4 ('''Centroid linkage distance''')]

Dando continuidade, temos que dado um conjunto de pontos de ''n'' dimensões, seja ''C''<sub>''i''</sub> um cluster de pontos de dados. Seja ''X''<sub>''j''</sub> um vetor de características de ''n'' dimensões atribuído ao cluster ''C''<sub>''i''</sub>.

: <math> 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}</math>

Aqui, <math>A_i</math> é o [[:en:Centroid|centroide]] de ''C''<sub>''i''</sub> e ''T''<sub>''i''</sub> é o tamanho do cluster ''i''. <math> S_i</math> é a raiz ''q''-ésima do ''q''-ésimo momento dos pontos no cluster ''i'' em relação à média. Se <math> q=1</math> então <math> S_i</math> é 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.

: <math> 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} </math>

: <math> M_{i,j}</math> é uma medida de separação entre o cluster <math>C_i</math> e o cluster <math>C_j</math>.

: <math> a_{k,i} </math> é o ''k''-ésimo elemento de <math>A_i</math>, 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''<sub>''i,j''</sub> ser uma medida de quão bom é o esquema de agrupamento. Essa medida, por definição, tem que levar em conta ''M''<sub>''i,j''</sub>, a separação entre o ''i''<sup>''ésimo''</sup> e o ''j''<sup>''ésimo''</sup> cluster, que idealmente deve ser o maior possível, e ''S''<sub>''i''</sub>, 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''<sub>''i''</sub> e ''M''<sub>''i,j''</sub> de forma que essas propriedades sejam conservadas:

# <math> R_{i,j} \geqslant 0 </math>.
# <math> R_{i,j} = R_{j,i} </math>.
# Quando <math> S_j \geqslant S_k </math> e <math> M_{i,j} = M_{i,k} </math> então <math> R_{i,j} > R_{i,k} </math>.
# Quando <math> S_j = S_k </math> e <math> M_{i,j} \leqslant M_{i,k} </math> então <math> R_{i,j} > R_{i,k} </math>.
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 é:
: <math> R_{i,j} = \frac{S_i + S_j}{M_{i,j}} </math>

Isso é usado para definir ''D''<sub>''i''</sub>:
: <math> D_i \equiv \max_{j \neq i} R_{i,j}</math>

Se N é o número de clusters:

: <math> \mathit{DB} \equiv \frac{1}{N}\displaystyle\sum_{i=1}^N D_i</math>

''DB'' é chamado de índice Davies–Bouldin. Isso depende tanto dos dados quanto do algoritmo. ''D''<sub>''i''</sub> escolhe o pior cenário, e esse valor é igual a ''R''<sub>''i,j''</sub> 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''<sub>''i''</sub> 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 [[K-means|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 [[Valor atípico|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 [[Valor atípico|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]], [[Geometria do táxi|distância Manhattan]] ou [[Índice Jaccard|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 [[:en:Elbow method (clustering)|método do cotovelo]] ou a [[:en:Determining the number of clusters in a data set|estatística gap]], que se mostram particularmente úteis nesse contexto.<ref>{{cite web |https://www.linkedin.com/advice/0/what-some-challenges-limitations-cluster-analysis?lang=en |title=What are some challenges and limitations of cluster analysis using Davies-Bouldin index? |accessdate=23 de novembro de 2022 }}</ref>

== Versão suave do índice Davies–Bouldin ==
Recentemente, o índice Davies–Bouldin foi estendido para o domínio de categorias de agrupamento suave.<ref>{{Cite journal |last=Vergani |first=Alberto A. |last2=Binaghi |first2=Elisabetta |date=Julho de 2018 |title=A Soft Davies-Bouldin Separation Measure |url=https://ieeexplore.ieee.org/document/8491581/ |publisher=IEEE |pages=1–8 |doi=10.1109/FUZZ-IEEE.2018.8491581 |isbn=978-1-5090-6020-7}}</ref> Essa extensão é baseada na abordagem de agrupamento de categorias de acordo com o framework da [[fuzzy logic|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, [[Agrupamento difuso (fuzzy)|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]].<ref>{{cite web |url=http://www.cis.hut.fi/somtoolbox/package/docs2/db_index.html |title=Implementação em Matlab |accessdate=12 de novembro de 2011 }}</ref> Uma implementação em MATLAB também está disponível através da MATLAB Statistics and Machine Learning Toolbox, utilizando o comando "evalclusters".<ref>{{Cite web | url=http://www.mathworks.com/help/stats/evalclusters.html |title = Avaliar soluções de agrupamento - MATLAB evalclusters}}</ref>
* Abaixo, um exemplo usando o '''método evalclusters:'''

<code>rng("default")</code>

<code>n = 200;</code>

<code>mu1 = [2 2];</code>

<code>sigma1 = [0.9 -0.0255; -0.0255 0.9];</code>

<code>mu2 = [5 5];</code>

<code>sigma2 = [0.5 0; 0 0.3];</code>

mu3 = [-2 -2];

<code>sigma3 = [1 0; 0 0.9];</code>

<code>X = [mvnrnd(mu1,sigma1,n); ...</code>

<code>mvnrnd(mu2,sigma2,n); ...</code>

<code>mvnrnd(mu3,sigma3,n)];</code>

<code>evaluation = '''evalclusters'''(X,"kmeans","DaviesBouldin","KList",1:6)</code>
* Para saber mais sobre a documentação, [https://www.mathworks.com/help/stats/clustering.evaluation.daviesbouldinevaluation.html clique aqui.]
* Uma implementação em [[Java (linguagem de programação)|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, [https://elki-project.github.io/releases/current/javadoc/elki/evaluation/clustering/internal/DaviesBouldinIndex.html clique aqui.]
* No [[Python]], a implementação pode ser encontrada dentro do pacote '''<nowiki/>'sklearn.base',''' mais especificamente no módulo '''<nowiki/>'sklearn.metrics.davies_bouldin_score',''' que pode ser encontrado com mais detalhes '''[https://scikit-learn.org/stable/modules/generated/sklearn.metrics.davies_bouldin_score.html aqui.]'''
* Abaixo, um exemplo utilizando esse módulo:

<code>'''from''' '''sklearn''' '''import''' datasets</code>

<code>iris = datasets.load_iris()</code>

<code>X = iris.data</code>

<code>'''from''' '''sklearn.cluster''' '''import''' KMeans</code>

<code>'''from''' '''sklearn.metrics''' '''import''' davies_bouldin_score</code>

<code>kmeans = KMeans(n_clusters=3, random_state=1).fit(X)</code>

<code>labels = kmeans.labels_</code>

<code>'''davies_bouldin_score'''(X, labels)</code>
* Para o R, também existe uma implementação já criada. Ela pode ser encontrada importando a biblioteca '''<nowiki/>'clusterSim',''' e para mais detalhes a documentação se encontra [https://search.r-project.org/CRAN/refmans/clusterSim/html/index.DB.html aqui].
* Abaixo, um exemplo do método:

<code>library(clusterSim)</code>

<code>data(data_ratio)</code>

<code>cl2 <- pam(data_ratio, 5)</code>

<code>print('''index.DB'''(data_ratio, cl2$clustering, centrotypes="centroids"))</code>

== Ver também ==
* [[Método da silhueta|Pontuação da Silhueta]]
* [[Índice Dunn]]
* [[:en:Cluster analysis|Análise de Cluster]]
* [[:en:Calinski–Harabasz index|Índice Calinski-Harabasz]]
* [[:en:Determining the number of clusters in a data set|Determinação do número de clusters em um conjunto de dados]]

{{Referências}}

{{DEFAULTSORT:Índice Davies-Bouldin}}
[[Categoria:Critérios de agrupamento]]