DBSCAN - DBSCAN

O agrupamento espacial baseado em densidade de aplicativos com ruído ( DBSCAN ) é um algoritmo de agrupamento de dados proposto por Martin Ester , Hans-Peter Kriegel , Jörg Sander e Xiaowei Xu em 1996. É um algoritmo não paramétrico de agrupamento baseado em densidade : dado um conjunto de pontos em algum espaço, ele agrupa pontos que estão compactados juntos (pontos com muitos vizinhos próximos ), marcando como outliers pontos que estão isolados em regiões de baixa densidade (cujos vizinhos mais próximos estão muito distantes). DBSCAN é um dos algoritmos de agrupamento mais comuns e também o mais citado na literatura científica.

Em 2014, o algoritmo recebeu o prêmio de teste do tempo (um prêmio concedido a algoritmos que receberam atenção substancial na teoria e na prática) na principal conferência de mineração de dados, ACM SIGKDD . Em julho de 2020, o artigo de acompanhamento "DBSCAN revisitado, revisitado: por que e como você deve (ainda) usar o DBSCAN" aparece na lista dos 8 artigos mais baixados da prestigiosa revista ACM Transactions on Database Systems (TODS) .

História

Em 1972, Robert F. Ling publicou um algoritmo intimamente relacionado em "The Theory and Construction of k-Clusters" no The Computer Journal com uma complexidade de tempo de execução estimada de O (n³). DBSCAN tem um pior caso de O (n²), e a formulação de consulta de intervalo orientada a banco de dados do DBSCAN permite a aceleração do índice. Os algoritmos diferem ligeiramente no tratamento dos pontos de fronteira.

Preliminares

Considere um conjunto de pontos em algum espaço a ser agrupado. Seja $ε$ um parâmetro que especifica o raio de uma vizinhança em relação a algum ponto. Para fins de agrupamento DBSCAN, os pontos são classificados como pontos centrais , ( densidade -) pontos alcançáveis e outliers , da seguinte forma:

Um ponto $p$ é um ponto central se pelo menos os pontos $minPts$ estiverem dentro da distância $ε$ dele (incluindo $p$ ).
Um ponto $q$ é diretamente alcançável de $p$ se o ponto $q$ está dentro da distância $ε$ do ponto central $p$ . Diz-se que os pontos só podem ser acessados diretamente a partir dos pontos centrais.
Um ponto $q$ é acessível a partir de $p$ , se existe um caminho $p 1, ..., p n$ com $p 1 = p$ e $p n = Q$ , em que cada $p i 1$ é directamente acessível a partir de $p i$ . Observe que isso implica que o ponto inicial e todos os pontos no caminho devem ser pontos centrais, com a possível exceção de $q$ .
Todos os pontos não alcançáveis de qualquer outro ponto são outliers ou pontos de ruído .

Agora, se $p$ é um ponto central, então ele forma um cluster junto com todos os pontos (centrais ou não centrais) que são alcançáveis a partir dele. Cada cluster contém pelo menos um ponto central; pontos não centrais podem fazer parte de um cluster, mas eles formam sua "borda", uma vez que não podem ser usados para atingir mais pontos.

Neste diagrama,

minPts = 4

. O ponto A e os outros pontos vermelhos são pontos centrais, porque a área ao redor desses pontos em um raio

ε

contém pelo menos 4 pontos (incluindo o próprio ponto). Por serem todos alcançáveis uns dos outros, eles formam um único cluster. Os pontos B e C não são pontos centrais, mas são acessíveis de A (por meio de outros pontos centrais) e, portanto, também pertencem ao cluster. O ponto N é um ponto de ruído que não é um ponto central nem diretamente acessível.

Acessibilidade não é uma relação simétrica: por definição, apenas pontos centrais podem alcançar pontos não centrais. O oposto não é verdadeiro, portanto, um ponto não essencial pode ser alcançável, mas nada pode ser alcançado a partir dele. Portanto, uma noção adicional de conectividade é necessária para definir formalmente a extensão dos clusters encontrados pelo DBSCAN. Dois pontos $p$ e $q$ são conectados por densidade se houver um ponto $o$ tal que $p$ e $q$ sejam alcançáveis a partir de $o$ . A conexão por densidade é simétrica.

Um cluster, então, satisfaz duas propriedades:

Todos os pontos dentro do cluster são conectados mutuamente por densidade.
Se um ponto puder ser alcançado por densidade a partir de algum ponto do cluster, ele também fará parte do cluster.

Algoritmo

Algoritmo baseado em consulta original

DBSCAN requer dois parâmetros: ε (eps) e o número mínimo de pontos necessários para formar uma região densa (minPts). Ele começa com um ponto de partida arbitrário que não foi visitado. A vizinhança ε deste ponto é recuperada e, se ela contiver muitos pontos suficientes, um cluster é iniciado. Caso contrário, o ponto é rotulado como ruído. Observe que este ponto pode mais tarde ser encontrado em um ambiente ε de tamanho suficiente de um ponto diferente e, portanto, ser feito parte de um cluster.

Se um ponto for considerado uma parte densa de um aglomerado, sua vizinhança ε também faz parte desse aglomerado. Assim, todos os pontos que são encontrados dentro da vizinhança ε são adicionados, assim como sua própria vizinhança ε quando eles também são densos. Esse processo continua até que o cluster conectado por densidade seja completamente encontrado. Então, um novo ponto não visitado é recuperado e processado, levando à descoberta de outro cluster ou ruído.

DBSCAN pode ser usado com qualquer função de distância (bem como funções de similaridade ou outros predicados). A função de distância (dist) pode, portanto, ser vista como um parâmetro adicional.

O algoritmo pode ser expresso em pseudocódigo da seguinte maneira:

DBSCAN(DB, distFunc, eps, minPts) {
    C := 0                                                  /* Cluster counter */
    for each point P in database DB {
        if label(P) ≠ undefined then continue               /* Previously processed in inner loop */
        Neighbors N := RangeQuery(DB, distFunc, P, eps)     /* Find neighbors */
        if |N| < minPts then {                              /* Density check */
            label(P) := Noise                               /* Label as Noise */
            continue
        }
        C := C + 1                                          /* next cluster label */
        label(P) := C                                       /* Label initial point */
        SeedSet S := N \ {P}                                /* Neighbors to expand */
        for each point Q in S {                             /* Process every seed point Q */
            if label(Q) = Noise then label(Q) := C          /* Change Noise to border point */
            if label(Q) ≠ undefined then continue           /* Previously processed (e.g., border point) */
            label(Q) := C                                   /* Label neighbor */
            Neighbors N := RangeQuery(DB, distFunc, Q, eps) /* Find neighbors */
            if |N| ≥ minPts then {                          /* Density check (if Q is a core point) */
                S := S ∪ N                                  /* Add new neighbors to seed set */
            }
        }
    }
}

onde RangeQuery pode ser implementado usando um índice de banco de dados para melhor desempenho ou usando uma varredura linear lenta:

RangeQuery(DB, distFunc, Q, eps) {
    Neighbors N := empty list
    for each point P in database DB {                      /* Scan all points in the database */
        if distFunc(Q, P) ≤ eps then {                     /* Compute distance and check epsilon */
            N := N ∪ {P}                                   /* Add to result */
        }
    }
    return N
}

Algoritmo abstrato

O algoritmo DBSCAN pode ser abstraído nas seguintes etapas:

Encontre os pontos na vizinhança ε (eps) de cada ponto e identifique os pontos centrais com mais do que vizinhos minPts.
Encontre os componentes conectados dos pontos centrais no gráfico vizinho, ignorando todos os pontos não centrais.
Atribua cada ponto não central a um cluster próximo se o cluster for um vizinho ε (eps), caso contrário, atribua-o ao ruído.

Uma implementação ingênua disso requer o armazenamento das vizinhanças na etapa 1, exigindo assim uma memória substancial. O algoritmo DBSCAN original não exige isso, executando essas etapas para um ponto de cada vez.

Complexidade

O DBSCAN visita cada ponto do banco de dados, possivelmente várias vezes (por exemplo, como candidatos a diferentes clusters). Para considerações práticas, no entanto, a complexidade do tempo é principalmente governada pelo número de invocações de regionQuery. DBSCAN executa exatamente uma consulta para cada ponto, e se uma estrutura de indexação é usada que executa uma consulta de vizinhança em $O (log n)$ , uma complexidade de tempo de execução média geral de $O (n log n)$ é obtida (se o parâmetro $ε$ for escolhido em uma forma significativa, ou seja, de forma que, em média, apenas $O (log n)$ pontos sejam retornados). Sem o uso de uma estrutura de índice de aceleração, ou em dados degenerados (por exemplo, todos os pontos dentro de uma distância menor que $ε$ ), o pior caso de complexidade de tempo de execução permanece $O (n ²)$ . A matriz de distância de tamanho $(n ²- n) / 2$ pode ser materializada para evitar recomputações de distância, mas isso precisa de memória $O (n ²)$ , enquanto uma implementação de DBSCAN não baseada em matriz precisa apenas de memória $O (n)$ .

O DBSCAN pode localizar clusters separáveis não linearmente. Este conjunto de dados não pode ser adequadamente agrupado com k-médias ou agrupamento EM de mistura gaussiana.

Vantagens

O DBSCAN não exige que se especifique o número de clusters nos dados a priori, ao contrário do k-means .
O DBSCAN pode localizar clusters de formato arbitrário. Ele pode até encontrar um cluster completamente cercado por (mas não conectado a) um cluster diferente. Devido ao parâmetro MinPts, o chamado efeito de link único (diferentes clusters sendo conectados por uma linha fina de pontos) é reduzido.
DBSCAN tem noção de ruído e é robusto para outliers .
DBSCAN requer apenas dois parâmetros e é geralmente insensível à ordem dos pontos no banco de dados. (No entanto, os pontos situados na borda de dois clusters diferentes podem trocar a associação do cluster se a ordem dos pontos for alterada e a atribuição do cluster for única até o isomorfismo.)
DBSCAN é projetado para uso com bancos de dados que podem acelerar consultas de região, por exemplo, usando uma árvore R * .
Os parâmetros minPts e ε podem ser definidos por um especialista no domínio, se os dados forem bem compreendidos.

Desvantagens

O DBSCAN não é totalmente determinístico: os pontos de fronteira que são alcançáveis de mais de um cluster podem fazer parte de qualquer cluster, dependendo da ordem em que os dados são processados. Para a maioria dos conjuntos de dados e domínios, essa situação não surge com frequência e tem pouco impacto no resultado do agrupamento: tanto nos pontos principais quanto nos pontos de ruído, o DBSCAN é determinístico. DBSCAN * é uma variação que trata os pontos de fronteira como ruído e, dessa forma, obtém um resultado totalmente determinístico, bem como uma interpretação estatística mais consistente dos componentes conectados por densidade.
A qualidade do DBSCAN depende da medida de distância usada na função regionQuery (P, ε). A métrica de distância mais comum usada é a distância euclidiana . Especialmente para dados de alta dimensão , esta métrica pode se tornar quase inútil devido à chamada " Maldição da dimensionalidade ", tornando difícil encontrar um valor apropriado para ε. Esse efeito, entretanto, também está presente em qualquer outro algoritmo baseado na distância euclidiana.
DBSCAN não pode agrupar conjuntos de dados bem com grandes diferenças em densidades, uma vez que a combinação minPts-ε não pode então ser escolhida apropriadamente para todos os clusters.
Se os dados e a escala não forem bem compreendidos, pode ser difícil escolher um limiar de distância ε significativo.

Consulte a seção abaixo sobre extensões para modificações algorítmicas para lidar com esses problemas.

Estimativa de parâmetro

Cada tarefa de mineração de dados tem o problema de parâmetros. Cada parâmetro influencia o algoritmo de maneiras específicas. Para DBSCAN, os parâmetros ε e minPts são necessários. Os parâmetros devem ser especificados pelo usuário. Idealmente, o valor de ε é dado pelo problema a ser resolvido (por exemplo, uma distância física), e minPts é então o tamanho mínimo de cluster desejado.

MinPts : Como regra geral, um mínimo de minPts pode ser derivado do número de dimensões D no conjunto de dados, como minPts ≥ D + 1. O valor baixo de minPts = 1 não faz sentido, pois então todo ponto é um ponto central por definição. Com minPts ≤ 2, o resultado será o mesmo do agrupamento hierárquico com a métrica de link único, com o corte do dendrograma na altura ε. Portanto, minPts deve ser escolhido pelo menos 3. No entanto, valores maiores são geralmente melhores para conjuntos de dados com ruído e produzirão clusters mais significativos. Como regra geral, minPts = 2 · dim pode ser usado, mas pode ser necessário escolher valores maiores para dados muito grandes, para dados com ruído ou para dados que contêm muitas duplicatas.
ε: O valor para ε pode então ser escolhido usando um gráfico de k-distância , traçando a distância para o vizinho mais próximo k = minPts -1 ordenado do maior para o menor valor. Bons valores de ε estão onde este gráfico mostra um "cotovelo": se ε for escolhido muito pequeno, uma grande parte dos dados não será agrupada; enquanto para um valor muito alto de ε, os clusters se fundirão e a maioria dos objetos estará no mesmo cluster. Em geral, pequenos valores de ε são preferíveis e, como regra geral, apenas uma pequena fração dos pontos deve estar dentro dessa distância um do outro. Alternativamente, um gráfico OPTICS pode ser usado para escolher ε, mas então o próprio algoritmo OPTICS pode ser usado para agrupar os dados.
Função de distância: A escolha da função de distância está fortemente associada à escolha de ε e tem um grande impacto nos resultados. Em geral, será necessário primeiro identificar uma medida razoável de similaridade para o conjunto de dados, antes que o parâmetro ε possa ser escolhido. Não há estimativa para este parâmetro, mas as funções de distância precisam ser escolhidas apropriadamente para o conjunto de dados. Por exemplo, em dados geográficos, a distância do grande círculo costuma ser uma boa escolha.

OPTICS pode ser visto como uma generalização do DBSCAN que substitui o parâmetro ε por um valor máximo que afeta principalmente o desempenho. MinPts, então, torna-se essencialmente o tamanho mínimo do cluster a ser encontrado. Embora o algoritmo seja muito mais fácil de parametrizar do que o DBSCAN, os resultados são um pouco mais difíceis de usar, pois geralmente produzirá um clustering hierárquico em vez do particionamento de dados simples que o DBSCAN produz.

Recentemente, um dos autores originais do DBSCAN revisitou o DBSCAN e o OPTICS, e publicou uma versão refinada do DBSCAN hierárquico (HDBSCAN *), que não possui mais a noção de pontos de fronteira. Em vez disso, apenas os pontos centrais formam o cluster.

Relação com agrupamento espectral

O DBSCAN pode ser visto como uma variante especial (eficiente) de agrupamento espectral : Os componentes conectados correspondem a agrupamentos espectrais ideais (sem corte de bordas - agrupamento espectral tenta particionar os dados com um corte mínimo ); DBSCAN encontra componentes conectados no gráfico de alcançabilidade (assimétrico). No entanto, o agrupamento espectral pode ser computacionalmente intensivo (até sem aproximação e outras suposições), e é necessário escolher o número de clusters para o número de autovetores a escolher e o número de clusters a serem produzidos com k-médias na incorporação espectral . Assim, por razões de desempenho, o algoritmo DBSCAN original permanece preferível a uma implementação espectral, e essa relação é até agora apenas de interesse teórico. ${\ displaystyle O (n ^ {3})}$ ${\ displaystyle k}$

Extensões

DBSCAN generalizado (GDBSCAN) é uma generalização pelos mesmos autores para predicados "vizinhança" e "denso" arbitrários. Os parâmetros ε e minPts são removidos do algoritmo original e movidos para os predicados. Por exemplo, em dados de polígono, a "vizinhança" pode ser qualquer polígono de interseção, enquanto o predicado de densidade usa as áreas do polígono em vez de apenas a contagem de objetos.

Várias extensões para o algoritmo DBSCAN foram propostas, incluindo métodos para paralelização, estimativa de parâmetros e suporte para dados incertos. A ideia básica foi estendida ao agrupamento hierárquico pelo algoritmo OPTICS . DBSCAN também é usado como parte de algoritmos de clustering de subespaço como PreDeCon e SUBCLU . HDBSCAN é uma versão hierárquica do DBSCAN que também é mais rápida do que o OPTICS, da qual uma partição plana consistindo dos clusters mais proeminentes pode ser extraída da hierarquia.

Disponibilidade

Diferentes implementações do mesmo algoritmo exibiram enormes diferenças de desempenho, com a mais rápida em um conjunto de dados de teste terminando em 1,4 segundos, a mais lenta levando 13803 segundos. As diferenças podem ser atribuídas à qualidade da implementação, diferenças de linguagem e compilador e ao uso de índices para aceleração.

O Apache Commons Math contém uma implementação Java do algoritmo em execução em tempo quadrático.
ELKI oferece uma implementação de DBSCAN, bem como GDBSCAN e outras variantes. Esta implementação pode usar várias estruturas de índice para tempo de execução subquadrático e suporta funções de distância arbitrária e tipos de dados arbitrários, mas pode ser superada por implementações otimizadas de baixo nível (e especializadas) em pequenos conjuntos de dados.
mlpack inclui uma implementação de DBSCAN acelerada com técnicas de pesquisa de intervalo de árvore dupla.
PostGIS inclui ST_ClusterDBSCAN - uma implementação 2D de DBSCAN que usa índice R-tree. Qualquer tipo de geometria é compatível, por exemplo, Point, LineString, Polygon, etc.
R contém implementações de DBSCAN nos pacotes dbscan e fpc . Ambos os pacotes suportam funções de distância arbitrária por meio de matrizes de distância. O pacote fpc não tem suporte de índice (e, portanto, tem tempo de execução quadrático e complexidade de memória) e é bastante lento devido ao interpretador R. O pacote dbscan fornece uma implementação rápida de C ++ usando árvores kd (apenas para distância euclidiana) e também inclui implementações de DBSCAN *, HDBSCAN *, OPTICS, OPTICSXi e outros métodos relacionados.
scikit-learn inclui uma implementação Python do DBSCAN para métricas Minkowski arbitrárias , que pode ser acelerado usando árvores kd e árvores bola, mas que usa memória quadrática de pior caso. Uma contribuição para o scikit-learn fornece uma implementação do algoritmo HDBSCAN *.
A biblioteca pyclustering inclui uma implementação em Python e C ++ do DBSCAN apenas para distância euclidiana, bem como para o algoritmo OPTICS.
O SPMF inclui uma implementação do algoritmo DBSCAN com suporte à árvore kd apenas para distância euclidiana.
Weka contém (como um pacote opcional nas versões mais recentes) uma implementação básica de DBSCAN que roda em tempo quadrático e memória linear.

Languages

In other projects