Ok, vamos começar a falar sobre o DBSCAN.
A clustering espacial baseado em densidade de aplicações com ruído (DBSCAN) é um conhecido algoritmo de clustering de dados que é comumente usado em mineração de dados e aprendizagem de máquinas.
Baseado num conjunto de pontos (vamos pensar num espaço bidimensional como exemplificado na figura), o DBSCAN agrupa pontos que estão próximos uns dos outros com base numa medição da distância (normalmente a distância euclidiana) e um número mínimo de pontos. Ele também marca como outliers os pontos que estão em regiões de baixa densidade.
Parâmetros:
O algoritmo DBSCAN requer basicamente 2 parâmetros:
eps: especifica o quão próximos os pontos devem estar uns dos outros para serem considerados como parte de um cluster. Isso significa que se a distância entre dois pontos for menor ou igual a esse valor (eps), esses pontos são considerados vizinhos.
minPoints: o número mínimo de pontos para formar uma região densa. Por exemplo, se definirmos o parâmetro minPontos como 5, então precisamos de pelo menos 5 pontos para formar uma região densa.
Parameter estimation:
A estimação do parâmetro é um problema para cada tarefa de mineração de dados. Para escolher bons parâmetros precisamos entender como eles são usados e ter pelo menos um conhecimento prévio básico sobre o conjunto de dados que será usado.
eps: se o valor eps escolhido for muito pequeno, uma grande parte dos dados não será agregada. Será considerada outliers porque não satisfaz o número de pontos para criar uma região densa. Por outro lado, se o valor escolhido for muito alto, os clusters irão se fundir e a maioria dos objetos estarão no mesmo cluster. Os eps devem ser escolhidos com base na distância do conjunto de dados (podemos usar um gráfico de k-distância para encontrá-lo), mas em geral pequenos valores eps são preferíveis.
minPoints: Como regra geral, um mínimo de minPontos pode ser derivado de um número de dimensões (D) no conjunto de dados, como minPontos ≥ D + 1. Valores maiores são geralmente melhores para conjuntos de dados com ruído e formarão clusters mais significativos. O valor mínimo para os minPontos deve ser 3, mas quanto maior o conjunto de dados, maior o valor dos minPontos que devem ser escolhidos.
Pode encontrar mais sobre a estimativa de parâmetros aqui.
Por que devemos usar DBSCAN?
O algoritmo DBSCAN deve ser usado para encontrar associações e estruturas em dados que são difíceis de encontrar manualmente mas que podem ser relevantes e úteis para encontrar padrões e prever tendências.
Os métodos de agrupamento são normalmente usados em biologia, medicina, ciências sociais, arqueologia, marketing, reconhecimento de caracteres, sistemas de gestão e assim por diante.
P>Pensemos num uso prático do DBSCAN. Suponha que temos um comércio electrónico e queremos melhorar as nossas vendas, recomendando produtos relevantes aos nossos clientes. Não sabemos exatamente o que nossos clientes estão procurando, mas com base em um conjunto de dados podemos prever e recomendar um produto relevante a um cliente específico. Nós podemos aplicar o DBSCAN ao nosso conjunto de dados (baseado no banco de dados de comércio eletrônico) e encontrar clusters baseados nos produtos que os usuários compraram. Usando estes clusters podemos encontrar semelhanças entre os clientes, por exemplo, o cliente A comprou 1 caneta, 1 livro e 1 tesoura e o cliente B comprou 1 livro e 1 tesoura, depois podemos recomendar 1 caneta ao cliente B. Este é apenas um pequeno exemplo de uso do DBSCAN, mas pode ser usado em muitas aplicações em diversas áreas.
Como podemos facilmente implementá-lo?
Como eu já escrevi (dica: não acredite em tudo que escrevo) o DBSCAN é um algoritmo bem conhecido, portanto, você não precisa se preocupar em implementá-lo você mesmo. Você pode usar uma das bibliotecas/pacotes que podem ser encontrados na internet. Aqui está uma lista de links que você pode encontrar para a implementação do DBSCAN: Matlab, R, R, Python, Python.
Eu também desenvolvi uma aplicação (em português) para explicar como funciona o DBSCAN de uma forma didática. A aplicação foi escrita em C++ e você pode encontrá-la em Github.