Um guia para o algoritmo de agrupamento DBSCAN

Na ciência de dados e no aprendizado de máquina, a capacidade de descobrir padrões ocultos e agrupar pontos de dados semelhantes é uma habilidade importante. Os algoritmos de agrupamento desempenham um papel fundamental nesse processo. 

O agrupamento é uma técnica fundamental de aprendizado de máquina e ciência de dados que envolve o agrupamento de pontos de dados semelhantes. É um método de aprendizado não supervisionado, o que significa que não requer dados rotulados para encontrar padrões. 

O principal objetivo do clustering é:

• Simplificar grandes conjuntos de dados em subgrupos significativos
• Identificar agrupamentos naturais nos dados
• Revelar padrões e estruturas ocultas

Embora existam vários algoritmos de agrupamento (você já deve ter ouvido falar do K-means ou do agrupamento hierárquico), o DBSCAN oferece vantagens exclusivas. Como um método baseado em densidade, o DBSCAN tem vários pontos fortes:

1. Flexibilidade no formato do cluster
2. Não há número predefinido de clusters
3. Manuseio de ruídos
4. Insight baseado em densidade

Neste artigo, veremos o que é o algoritmo DBSCAN, como ele funciona, como implementá-lo em Python e quando usá-lo em seus projetos de ciência de dados.

O que é DBSCAN?

DBSCAN, que significa Density-Based Spatial Clustering of Applications with Noise (Agrupamento Espacial de Aplicativos com Ruído Baseado em Densidade), é um algoritmo de agrupamento eficiente que agrupa pontos que estão muito próximos uns dos outros no espaço de dados. Diferentemente de outros algoritmos de agrupamento, o DBSCAN não exige que você especifique previamente o número de agrupamentos, o que o torna particularmente útil para a análise exploratória de dados.

O algoritmo funciona definindo clusters como regiões densas separadas por regiões de menor densidade. Essa abordagem permite que o DBSCAN descubra grupos de formato arbitrário e identifique exceções como ruído.

O DBSCAN gira em torno de três conceitos principais:

1. Pontos principais: Esses são pontos que têm pelo menos um número mínimo de outros pontos (MinPts) dentro de uma distância especificada (ε ou épsilon).
2. Pontos de fronteira: Esses são pontos que estão dentro da distância ε de um ponto central, mas não têm MinPts vizinhos.
3. Pontos de ruído: Esses são pontos que não são nem pontos centrais nem pontos de fronteira. Eles não estão próximos o suficiente de nenhum cluster para serem incluídos.

Imagem do autor

O diagrama acima ilustra esses conceitos. Os pontos centrais (azul) formam o coração dos clusters, os pontos de borda (laranja) estão na borda dos clusters e os pontos de ruído (vermelho) estão isolados.

O DBSCAN usa dois parâmetros principais:

• ε (epsilon): A distância máxima entre dois pontos para que eles sejam considerados vizinhos.
• MinPts: O número mínimo de pontos necessários para formar uma região densa.

Ao ajustar esses parâmetros, você pode controlar como o algoritmo define os clusters, permitindo que ele se adapte a diferentes tipos de conjuntos de dados e requisitos de clustering.

Na próxima seção, veremos como o algoritmo DBSCAN funciona, explorando seu processo passo a passo para identificar clusters nos dados.

Como o DBSCAN funciona?

O DBSCAN opera examinando a vizinhança de cada ponto no conjunto de dados. O algoritmo segue um processo passo a passo para identificar clusters com base na densidade dos pontos de dados. Vamos detalhar como o DBSCAN funciona:

1. Seleção de parâmetros
• Escolha ε (epsilon): A distância máxima entre dois pontos para que eles sejam considerados vizinhos.
• Selecione MinPts: O número mínimo de pontos necessários para formar uma região densa.
2. Selecione um ponto de partida
• O algoritmo começa com um ponto arbitrário não visitado no conjunto de dados.
3. Examine a vizinhança
• Ele recupera todos os pontos dentro da distância ε do ponto inicial.
• Se o número de pontos vizinhos for menor que MinPts, o ponto será rotulado como ruído (por enquanto).
• Se houver pelo menos pontos MinPts a uma distância de ε, o ponto será marcado como um ponto central e um novo cluster será formado.
4. Expandir o cluster
• Todos os vizinhos do ponto central são adicionados ao cluster.
• Para cada um desses vizinhos:
• Se for um ponto central, seus vizinhos serão adicionados ao cluster recursivamente.
• Se não for um ponto central, ele será marcado como um ponto de borda e a expansão será interrompida.
5. Repetir o processo
• O algoritmo passa para o próximo ponto não visitado no conjunto de dados.
• As etapas 3 e 4 são repetidas até que todos os pontos tenham sido visitados.
6. Finalizar clusters
• Após o processamento de todos os pontos, o algoritmo identifica todos os clusters.
• Os pontos inicialmente rotulados como ruído podem agora ser pontos de borda se estiverem a uma distância ε de um ponto central.
7. Ruído de manuseio
• Todos os pontos que não pertencem a nenhum cluster permanecem classificados como ruído.

Esse processo permite que o DBSCAN forme clusters de formas arbitrárias e identifique outliers de forma eficaz. A capacidade do algoritmo de encontrar clusters sem especificar previamente o número de clusters é um de seus principais pontos fortes.

É importante observar que a escolha de ε e MinPts pode afetar significativamente os resultados do agrupamento. Na próxima seção, discutiremos como escolher esses parâmetros de forma eficaz e apresentaremos métodos como o gráfico de distância k para a seleção de parâmetros.

Conceitos e parâmetros principais do DBSCAN

Para entender completamente como o DBSCAN forma clusters, é importante compreender dois conceitos-chave: acessibilidade de densidade e conectividade de densidade.

Alcançabilidade da densidade

Um ponto q é alcançável por densidade a partir de um ponto p se:

1. p é um ponto central (tem pelo menos MinPts a uma distância de ε)

2. Há uma cadeia de pontos p = p₁, ..., p_n = q em que cada p_i+1 é diretamente alcançável por densidade a partir de p_i.

Em termos mais simples, você pode chegar a q a partir de p passando por pontos centrais, onde cada passo não é maior que ε.

Conectividade de densidade

Dois pontos p e q são conectados por densidade se existir um ponto o de modo que tanto p quanto q sejam acessíveis por densidade a partir de o.

A conectividade de densidade é a base para a formação de clusters no DBSCAN. Todos os pontos em um cluster estão mutuamente conectados por densidade e, se um ponto estiver conectado por densidade a qualquer ponto no cluster, ele também pertencerá a esse cluster.

Escolha dos parâmetros do DBSCAN

A eficácia do DBSCAN depende muito da escolha de seus dois parâmetros principais: ε (epsilon) e MinPts. Veja a seguir como você deve selecionar esses parâmetros:

Seleção de ε (Epsilon)

O parâmetro ε determina a distância máxima entre dois pontos para que eles sejam considerados vizinhos. Para escolher um ε adequado:

1. Use o conhecimento do domínio: Se você tiver uma ideia de qual distância é significativa para o seu problema específico, use-a como ponto de partida.

2. Gráfico de distância K: Essa é uma abordagem mais sistemática:

• Calcule a distância até o k-ésimo vizinho mais próximo de cada ponto (onde k = MinPts).
• Trace essas distâncias k em ordem crescente.
• Procure um "cotovelo" no gráfico - um ponto em que a curva começa a se nivelar.
• O valor ε nesse cotovelo costuma ser uma boa escolha.

Seleção de MinPts

MinPts determina o número mínimo de pontos necessários para formar uma região densa. Aqui estão algumas diretrizes:

1. Regra geral: Um bom ponto de partida é definir MinPts = 2 * num_features, em que num_features é o número de dimensões em seu conjunto de dados.

2. Consideração de ruído: Se os seus dados tiverem ruído ou se você quiser detectar clusters menores, talvez seja melhor diminuir o MinPts.

3. Tamanho do conjunto de dados: Para conjuntos de dados maiores, talvez você precise aumentar o MinPts para evitar a criação de muitos clusters pequenos.

Lembre-se de que a escolha dos parâmetros pode afetar significativamente os resultados. Geralmente, é vantajoso fazer experiências com valores diferentes e avaliar os clusters resultantes para encontrar a melhor opção para o conjunto de dados e o problema específicos que você tem.

Implementação do DBSCAN em Python

Nesta seção, veremos a implementação do DBSCAN usando Python e a biblioteca scikit-learn. Usaremos o conjunto de dados Make Moons para demonstrar o processo.

Configuração do ambiente

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons
from sklearn.cluster import DBSCAN
from sklearn.neighbors import NearestNeighbors

Essas importações fornecem as ferramentas necessárias para manipulação de dados, visualização, criação de conjuntos de dados e implementação do algoritmo DBSCAN.

Geração de dados de amostra

X, _ = make_moons(n_samples=200, noise=0.05, random_state=42)

Esse código cria um conjunto de dados sintético usando a funçãomake_moons do scikit-learn. Aqui está uma breve descrição do conjunto de dados:

A função make_moons gera uma classificação binária classificação que se assemelha a duas meias-luas intercaladas. No nosso caso:

• Criamos 200 amostras (n_samples=200)
• Adicionamos uma pequena quantidade de ruído gaussiano (noise=0.05) para tornar o conjunto de dados mais realista
• Definimos random_state=42 para reprodutibilidade

Esse conjunto de dados é particularmente útil para demonstrar o DBSCAN porque:

1. Ele tem uma forma não convexa que muitos agrupamento (como o K-means) teriam dificuldade em lidar com ele
2. Os dois clusters estão claramente separados, mas têm uma forma complexa
3. O ruído adicionado fornece um cenário mais realista em que alguns pontos podem ser classificados como discrepantes

Vamos visualizar esse conjunto de dados para que você entenda melhor sua estrutura:

# Visualize the dataset
plt.figure(figsize=(10, 6))
plt.scatter(X[:, 0], X[:, 1])
plt.title('Moon-shaped Dataset')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.show()

Isso mostrará a você as duas formas de meia-lua intercaladas em nosso conjunto de dados, conforme mostrado abaixo

Determinação do parâmetro epsilon

Usamos o método gráfico de distância k para ajudar você a escolher um valor de epsilon adequado:

1. Definimos uma função plot_k_distance_graph que calcula a distância até o k-ésimo vizinho mais próximo para cada ponto.
2. As distâncias são classificadas e plotadas.
3. Procuramos um "cotovelo" no gráfico resultante para escolher o épsilon.

# Function to plot k-distance graph
def plot_k_distance_graph(X, k):
    neigh = NearestNeighbors(n_neighbors=k)
    neigh.fit(X)
    distances, _ = neigh.kneighbors(X)
    distances = np.sort(distances[:, k-1])
    plt.figure(figsize=(10, 6))
    plt.plot(distances)
    plt.xlabel('Points')
    plt.ylabel(f'{k}-th nearest neighbor distance')
    plt.title('K-distance Graph')
    plt.show()
# Plot k-distance graph
plot_k_distance_graph(X, k=5)

Saída

Em nosso exemplo, com base no gráfico de distância k, escolhemos um epsilon de 0,15.

Execução de clustering DBSCAN

Usamos a implementação do DBSCAN do scikit-learn:

1. Definimos epsilon=0.15 com base em nosso gráfico de distância k.
2. Definimos min_samples=5 (2 * num_features, pois nossos dados são 2D).
3. Ajustamos o modelo aos nossos dados e prevemos os clusters.

# Perform DBSCAN clustering
epsilon = 0.15  # Chosen based on k-distance graph
min_samples = 5  # 2 * num_features (2D data)
dbscan = DBSCAN(eps=epsilon, min_samples=min_samples)
clusters = dbscan.fit_predict(X)

Visualização dos resultados

Criamos um gráfico de dispersão de nossos pontos de dados, colorindo-os de acordo com os clusters atribuídos. Os pontos classificados como ruído são normalmente coloridos de forma diferente (geralmente em preto).

# Visualize the results
plt.figure(figsize=(10, 6))
scatter = plt.scatter(X[:, 0], X[:, 1], c=clusters, cmap='viridis')
plt.colorbar(scatter)
plt.title('DBSCAN Clustering Results')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.show()

Saída

Interpretação dos resultados

Por fim, imprimimos o número de clusters encontrados e o número de pontos classificados como ruído. Isso nos dá um resumo rápido dos resultados de agrupamento.

# Print number of clusters and noise points
n_clusters = len(set(clusters)) - (1 if -1 in clusters else 0)
n_noise = list(clusters).count(-1)
print(f'Number of clusters: {n_clusters}')
print(f'Number of noise points: {n_noise}')

Saída

Número de clusters: 2

Número de pontos de ruído: 5

Essa implementação oferece um fluxo de trabalho completo, desde a geração de dados até a interpretação dos resultados. É importante observar que, em cenários do mundo real, você substituiria a geração de dados de amostra pelo carregamento e pré-processamento do conjunto de dados real.

Lembre-se de que a chave para o sucesso do agrupamento DBSCAN geralmente está na seleção adequada dos parâmetros. Não hesite em experimentar diferentes valores de epsilon e min_samples para encontrar o melhor ajuste para seu conjunto de dados específico.

DBSCAN vs. K-Means

Embora o DBSCAN e o K-Means sejam algoritmos de agrupamento populares, eles têm características distintas que os tornam adequados para diferentes tipos de dados e casos de uso. Vamos comparar esses dois algoritmos para que você entenda quando usar cada um deles.

Comparação visual

Para ilustrar essas diferenças, vamos aplicar os dois algoritmos ao nosso conjunto de dados em forma de lua

from sklearn.cluster import KMeans

# DBSCAN clustering
dbscan = DBSCAN(eps=0.15, min_samples=5)
dbscan_labels = dbscan.fit_predict(X)

# K-Means clustering
kmeans = KMeans(n_clusters=2, random_state=42)
kmeans_labels = kmeans.fit_predict(X)

# Visualize the results
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(15, 6))

ax1.scatter(X[:, 0], X[:, 1], c=dbscan_labels, cmap='viridis')
ax1.set_title('DBSCAN Clustering')

ax2.scatter(X[:, 0], X[:, 1], c=kmeans_labels, cmap='viridis')
ax2.set_title('K-Means Clustering')

plt.show()

Esse código aplica o DBSCAN e o K-Means ao nosso conjunto de dados e visualiza os resultados lado a lado.

Saída

Você perceberá que

1. O DBSCAN identifica corretamente as duas formas de meia-lua como clusters separados.
2. O K-Means tem dificuldades com a forma não convexa, muitas vezes dividindo uma lua em dois grupos ou combinando partes de ambas as luas em um único grupo.
3. O DBSCAN pode identificar alguns pontos como ruído (geralmente com cores diferentes), enquanto o K-Means atribui cada ponto a um cluster.

Quando usar o DBSCAN?

Agora que já vimos como o DBSCAN funciona e o comparamos com o K-Means, vamos ver quando o DBSCAN é a escolha certa para nossas necessidades de clustering. As propriedades exclusivas do DBSCAN o tornam particularmente adequado para determinados tipos de dados e domínios de problemas.

Formas complexas de clusters 

Com base em nossa comparação anterior, o DBSCAN realmente se destaca ao lidar com formas de cluster não globulares. Se os seus dados formarem padrões arbitrários, como as meias-luas que exploramos anteriormente, é provável que o DBSCAN supere os algoritmos tradicionais, como o K-Means. 

Por exemplo, na análise geográfica, as formações naturais, como os sistemas fluviais ou a expansão urbana, geralmente têm formas irregulares que o DBSCAN pode identificar com eficiência.

Número desconhecido de clusters

Uma das principais vantagens do DBSCAN é sua capacidade de determinar automaticamente o número de clusters. Isso é particularmente útil na análise exploratória de dados, em que você pode não ter conhecimento prévio sobre a estrutura subjacente dos dados. 

Considere um problema de segmentação de mercado: talvez você não saiba antecipadamente quantos grupos de clientes distintos existem. O DBSCAN pode ajudar a descobrir esses segmentos sem que você precise adivinhar o número de clusters.

Conjuntos de dados com ruído 

A abordagem do DBSCAN para lidar com pontos de ruído o torna robusto em relação a valores discrepantes. Isso é crucial em muitos conjuntos de dados do mundo real em que erros de medição ou anomalias são comuns.

Por exemplo, em sistemas de detecção de anomalias para segurança de rede, o DBSCAN pode separar com eficiência os padrões normais de tráfego de rede das possíveis ameaças à segurança.

Variação das densidades de cluster

Ao contrário do K-Means, que pressupõe clusters de densidade semelhante, o DBSCAN pode identificar clusters de densidades variadas. Isso é particularmente útil em cenários em que alguns grupos em seus dados são mais compactados do que outros.

Um exemplo poderia ser a análise das distribuições de galáxias na astronomia, em que diferentes regiões do espaço têm densidades variadas de objetos celestes.

Embora o DBSCAN seja eficiente, é importante que você esteja ciente de suas limitações:

1. Sensibilidade do parâmetro: Conforme discutido anteriormente, é fundamental escolher os valores adequados para ε e MinPts. Escolhas inadequadas podem levar a resultados de agrupamento abaixo do ideal.
2. Dados de alta dimensão: O desempenho do DBSCAN pode se degradar com dados de alta dimensão devido à "maldição da dimensionalidade".
3. Densidades variáveis: Embora o DBSCAN possa lidar com clusters de diferentes densidades, densidades extremamente variadas no mesmo conjunto de dados ainda podem representar desafios.
4. Escalabilidade: Para conjuntos de dados muito grandes, o DBSCAN pode ser computacionalmente caro em comparação com algoritmos como o K-Means.

Na próxima seção, veremos algumas aplicações práticas do DBSCAN.

Exemplos práticos de DBSCAN

O DBSCAN encontra aplicações em vários domínios.

Análise de dados espaciais

Nos sistemas de informações geográficas (GIS), o DBSCAN pode identificar áreas de alta atividade ou interesse. Por exemplo, um estudo intitulado 'Revelando a mobilidade humana urbana a partir de dados de GPS de táxi em grande escala' demonstra como o DBSCAN pode detectar pontos de acesso urbanos a partir de dados de GPS de táxi.

Esse aplicativo mostra a capacidade do DBSCAN de identificar regiões de atividade densa em dados espaciais, o que é fundamental para o planejamento urbano e o gerenciamento de transportes.

Processamento de imagens 

O DBSCAN pode agrupar pixels em objetos distintos para tarefas como reconhecimento de objetos em imagens. Um estudo intitulado 'Segmentation of Brain Tumour from MRI Image - Analysis of K-means and DBSCAN Clustering' demonstra a eficácia do DBSCAN na análise de imagens médicas .

Os pesquisadores usaram o DBSCAN para segmentar com precisão tumores cerebrais em exames de ressonância magnética, demonstrando seu potencial no diagnóstico auxiliado por computador e na geração de imagens médicas.

Detecção de anomalias 

Na detecção de fraudes ou no monitoramento da integridade do sistema, o DBSCAN pode isolar padrões incomuns. Um estudo intitulado 'Densidade eficiente e detecção incremental de outlier baseada em cluster em fluxos de dados' demonstra a aplicação de um algoritmo DBSCAN modificado para detecção de anomalias em tempo real.

Os pesquisadores aplicaram uma versão incremental do DBSCAN para detectar discrepâncias em dados de fluxo contínuo, o que tem aplicações potenciais na detecção de fraudes e no monitoramento da integridade do sistema. 

Este estudo mostra como o DBSCAN pode ser adaptado para identificar padrões incomuns em fluxos de dados contínuos, um recurso essencial para sistemas de detecção de fraudes em tempo real.

Sistemas de recomendação

O DBSCAN pode agrupar usuários com preferências semelhantes, ajudando a gerar recomendações mais precisas. Por exemplo, um estudo intitulado "Sistema de recomendação de serviços baseado em várias nuvens usando o algoritmo DBSCAN" demonstra a aplicação do DBSCAN no aprimoramento da filtragem colaborativa para sistemas de recomendação. Os pesquisadores usaram o DBSCAN como parte de uma abordagem de agrupamento para agrupar usuários com base em suas preferências e classificações de filmes, o que melhorou a precisão das recomendações de filmes.

Essa abordagem mostra como o DBSCAN pode aprimorar as recomendações personalizadas em domínios como os serviços de streaming de entretenimento.

Conclusão

O DBSCAN é uma ferramenta poderosa no kit de ferramentas do cientista de dados, particularmente valiosa ao lidar com conjuntos de dados complexos e ruidosos em que o número de clusters é desconhecido. No entanto, como qualquer algoritmo, não se trata de uma solução única para todos. 

A chave para um clustering bem-sucedido está em entender seus dados, os pontos fortes e as limitações dos diferentes algoritmos e escolher a ferramenta certa para o trabalho. Em muitos casos, tentar várias abordagens de clustering, incluindo DBSCAN e K-Means, e comparar seus resultados pode fornecer informações valiosas sobre a estrutura dos dados.

Com a prática e a experiência, você desenvolverá uma intuição para saber quando o DBSCAN provavelmente revelará os padrões ocultos em seus dados.

Você pode saber mais sobre as várias tecnologias e métodos que abordamos neste post sobre o DataCamp com os seguintes recursos: 

• Cientista de aprendizado de máquina em Python
• Folha de dicas de aprendizado de máquina não supervisionado
• Curso de aprendizado não supervisionado em Python