Entendendo DBSCAN
Autores:
Gabriel Monteiro
Hugo Carl
O que é “Clustering” ?
Clustering se trata de uma técnica muito utilizada em diferentes campos de análises estatísticas. Análise de imagens, mineração de dados, bioinformática e machine learning são apenas algumas áreas onde esta técnica pode ser aplicada. No campo de Machine Learning, ela faz parte da área de aprendizado não supervisionado.
Aplicar a técnica de clustering se resume em agrupar dados que se relacionam. Imagine-se como um comerciante que possui uma boa quantidade de dados sobre seus clientes e pretende com isso segmentá-los para entender suas necessidades individuais. Utilizar um método de clustering parece ser uma ótima iniciativa, pois você conseguirá agrupar os clientes baseados em dados como registros de compras, frequência das compras entre outros. No entanto, para cada problema é necessário escolher o algoritmo de clustering mais interessante de análise.
Modelos famosos de Clustering
- K-Means
O modelo conhecido como K-Means é um dos mais famosos e importantes nas análises de clustering. O objetivo por trás dele é encontrar um número K de clusters em uma amostra. Ele faz isso definindo centróides, que são sempre atualizados utilizando o valor médio dos pontos próximos daquele cluster. O aprimoramento desses centróides nas iterações do algoritmo são chave para que estes virem referências confiáveis para classificação de novos dados posteriormente.
- Clustering Hierárquico
Outro modelo muito conhecido para realizar clustering se trata do Clustering Hierárquico. Este algoritmo trabalha de uma forma parecida com uma árvore de decisão. Na abordagem Top-Down, é criado um único cluster com todos os dados que depois se divide em diversos clusters menores. Já na abordagem Bottom-Up ocorre o inverso, primeiro são gerados diversos clusters pequenos que se juntam em um cluster maior ao final. Em ambas abordagens é gerado um Dendograma, um gráfico responsável por concluir qual o melhor número de clusters para aquela amostra.
Modelo DBSCAN
Finalmente, o modelo DBSCAN, sigla dada para “Density-Based Spatial Clustering of Applications with Noise”, possui uma abordagem de agrupamento baseado na densidade. A densidade de pontos em determinada região é responsável pela formação dos clusters. Caso um determinado ponto não obedeça critérios de densidade ou critérios dos limites de distância, este não pode ser classificado em um cluster.
Parâmetros
Os dois parâmetros necessários para aplicação do modelo DBSCAN são:
- Eps: Raio máximo em que dois pontos podem estar para serem considerados do mesmo cluster.
- MinPts: Número mínimo de pontos em uma região necessários para garantir uma densidade desejada.
A escolha dos parâmetros é algo crucial para o bom funcionamento do algoritmo. Escolher um Eps pequeno demais levará a muitos ruídos, já que não será possível classificar estes pontos mais distantes. Porém, escolher um valor alto pode levar a classificação de poucos clusters muito generalizados. Técnicas como gráfico de k-distância podem ajudar a definir o melhor valor de Eps. Agora quando se trata do MinPts é recomendável a decisão do valor baseado na dimensão do dataset. Valores maiores para este parâmetro são efetivos para datasets com muito ruído.
Algoritmo
Na seção de parametros, já foi mencionado a presença de ruídos. Isto é porque a classificação de um ponto do dataset é crucial para a aplicação do algoritmo. São três tipos de pontos que podemos encontrar:
- Núcleos: Um ponto é considerado núcleo quando possui MinPts pontos ou mais dentro de um raio de Eps de distância.
- Bordas: Um ponto é considerado borda quando não possui MinPts dentro de um raio Eps de distância, porém está inserido dentro de um raio Eps de um outro ponto no qual é núcleo.
- Ruídos(ou Outliers): Um ponto é considerado um ruído quando este não está presente no raio Eps de um núcleo e nem possui MinPts dentro do seu raio Eps.
Com os tipos de classificações em mente, podemos partir para como o algoritmo itera sobre os dados:
- Escolher um ponto arbitrário
- Classificá-lo como Núcleo, Borda ou Ruído
- Se o ponto do momento é um Núcleo, todos os pontos à sua volta com um raio de distância Eps formam um cluster. Reclassificações podem ocorrer.
- Depois de classificar todos os pontos da região do núcleo, volta-se à etapa 1.
- O algoritmo termina quando todos os pontos tiverem sido classificados corretamente.
Um conceito muito importante a ser mencionado no método DBSCAN é o de Densidade Alcançável. Pode se dizer que um ponto possui uma densidade alcançável direta de outro se e apenas se a distância entre os mesmos estiver dentro de um raio Eps, porém um dos pontos deve ser um núcleo. Já pontos do tipo borda podem ser incluídos em clusters quando possuem densidade alcançável de um ponto que faz parte de uma cadeia de núcleos com densidade alcançável direta. Pontos que são núcleos podem alcançar pontos não-núcleos, porém pontos não-núcleos por mais que alcancem núcleos, não podem ser alcançados por outros pontos. Observe a imagem abaixo para facilitar o entendimento:
Implementação
Observe abaixo como implementar a técnica DBSCAN utilizando a biblioteca sklearn do Python. Cada gráfico representa a atuação do DBSCAN em agrupar dados em diferentes em datasets exemplo da própria biblioteca:
Gerando os pontos de forma aleatória seguindo os datasets já prontos no sklearn é possível observar a qualidade do DBSCAN na hora de encontrar e dividir núcleos mais densos de dados.
Aplicando DBSCAN no mundo real
Agora que já sabemos como a técnica DBSCAN funciona e como aplicá-la utilizando sklearn, vamos contextualizar sua aplicação em um caso real.
Para esse estudo foi utilizado uma base de dados da UC Irvine contendo dados de pacientes com câncer. A coleção de dados é uma parte da sequência RNA (Hi-Seq) PANCAN, ela representa uma extração aleatória de expressões genéticas de pacientes tendo 5 diferentes tipos de tumor, BRCA, KIRC, COAD, LUAD e PREAD.
O DataFrame possui dados de 801 pacientes, cada valor representando a quantidade do gene presente no RNA do paciente. Para tratar os dados foi utilizado um simple inputer, objetivando preencher os valores faltantes com a média de cada coluna e também uma normalização simples dos dados, para tornar todos equiparáveis entre si.
Para aplicar o DBSCAN, antes era necessário tornar os dados mais facilmente agrupáveis. Uma forma de fazer isso tornando sua visualização possível é a redução da dimensionalidade dos parâmetros do modelo, a biblioteca scikit-learn possui métodos prontos para resolver a situação. Nesta análise foi usado o método PCA.
Após aplicar o DBSCAN com os parâmetros Eps e MinPts, é evidente no plot dos resultados a formação de 5 clusters principais, representados pelas cores verde, vermelho, ciano, azul e amarelo.
Para validar os resultados foi usado uma segunda base de dados contendo o tipo de tumor que cada paciente com os labels já definidos e assim, ao associar nossa base inicial com dimensionalidade reduzida e plotar o gráfico é possível observar que os clusters formados pelo DBSCAN são exatamente os 5 tumores separados pelas cores definidas pelos tumores de cada paciente:
Conclusão
Por fim, conseguimos discutir o que é um modelo de clustering, quais as principais técnicas usadas, como o modelo DBSCAN funciona e suas aplicações. As vantagens desta técnica apresentada são muitas:
- Utilizar DBSCAN não requer a pré definição de números de clusters e utiliza apenas dois parâmetros.
- Os parâmetros são facilmente ajustados caso haja um bom conhecimento sobre os dados.
- DBSCAN se comporta muito bem em identificar clusters de tamanhos arbitrários, como visto no exemplo de implementação.
- A classificação de ruídos é muito bem feita.
No entanto, é importante listar também porque esta técnica pode não ser a mais indicada em certos casos:
- Se não há um bom conhecimento sobre os dados, a definição de parâmetros pode se tornar uma tarefa mais complicada.
- Quando se trata de dados com alta dimensionalidade, a distância Euclidiana que é mais utilizada para determinar o parâmetro Eps acaba não funcionando. Desta forma, a definição deste parâmetro se torna um desafio.
- DBSCAN não performa bem em datasets com variabilidade de densidade entre os dados.
- O DBSCAN não é uma técnica completamente determinística. Isto é possível de perceber tratando de pontos de borda que estão dentro do raio de núcleos referentes a diferentes clusters. Na maioria das situações, pode ser que isso não influencie em uma análise.
Referências
https://www.geeksforgeeks.org/implementing-dbscan-algorithm-using-sklearn/
https://scikit-learn.org/stable/auto_examples/cluster/plot_cluster_comparison.html
https://towardsdatascience.com/how-dbscan-works-and-why-should-i-use-it-443b4a191c80
https://en.wikipedia.org/wiki/DBSCAN#Parameter_estimation
https://www.youtube.com/watch?v=sKRUfsc8zp4
https://www.youtube.com/watch?v=6jl9KkmgDIw
https://archive.ics.uci.edu/ml/datasets/gene+expression+cancer+RNA-Seq
