Algoritmo OPTICS - OPTICS algorithm

Pontos de pedido para identificar a estrutura de agrupamento ( OPTICS ) é um algoritmo para localizar clusters baseados em densidade em dados espaciais. Foi apresentado por Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel e Jörg Sander. Sua ideia básica é semelhante ao DBSCAN , mas aborda uma das principais fraquezas do DBSCAN: o problema de detectar clusters significativos em dados de densidade variável. Para fazer isso, os pontos do banco de dados são (linearmente) ordenados de forma que os pontos espacialmente mais próximos se tornem vizinhos na ordem. Além disso, uma distância especial é armazenada para cada ponto que representa a densidade que deve ser aceita para um cluster para que ambos os pontos pertençam ao mesmo cluster. Isso é representado como um dendrograma .

Ideia básica

Assim como o DBSCAN , o OPTICS requer dois parâmetros: $ε$ , que descreve a distância máxima (raio) a ser considerada, e $MinPts$ , que descreve o número de pontos necessários para formar um cluster. Um ponto $p$ é um ponto central se pelo menos pontos $MinPts$ forem encontrados dentro de seu bairro $ε$ (incluindo o próprio ponto $p$ ). Em contraste com DBSCAN , OPTICS também considera pontos que fazem parte de um cluster mais densamente compactado, então cada ponto é atribuído a uma distância central que descreve a distância para o $MinPts é$ o ponto mais próximo: ${\ displaystyle N _ {\ varepsilon} (p)}$

{\ displaystyle {\ text {core-dist}} _ {\ mathit {\ varepsilon, MinPts}} (p) = {\ begin {cases} {\ text {UNDEFINED}} & {\ text {if}} | N_ {\ varejpsilon} (p) | <{\ mathit {MinPts}} \\ {\ mathit {MinPts}} {\ text {-ésima menor distância em}} N _ {\ varejpsilon} (p) & {\ text {caso contrário }} \ end {cases}}}

A distância de alcançabilidade de outro ponto $o$ de um ponto $p$ é a distância entre $o$ e $p$ , ou a distância central de $p$ , o que for maior:

{\ displaystyle {\ text {dist-de-alcance}} _ {\ mathit {\ varepsilon, MinPts}} (o, p) = {\ begin {cases} {\ text {UNDEFINED}} & {\ text {if}} | N _ {\ varepsilon} (p) | <{\ mathit {MinPts}} \\\ max ({\ text {core-dist}} _ {\ mathit {\ varejpsilon, MinPts}} (p), {\ text {dist}} (p, o)) & {\ text {caso contrário}} \ end {cases}}}

Se $p$ e $o$ são vizinhos mais próximos, precisamos assumir que $p$ e $o$ pertencem ao mesmo cluster. ${\ displaystyle \ varepsilon '<\ varepsilon}$

Tanto a distância do núcleo quanto a distância de alcançabilidade são indefinidas se nenhum cluster suficientemente denso (wrt $ε$ ) estiver disponível. Dado um $ε$ suficientemente grande , isso nunca acontece, mas então cada consulta de $ε-$ bairro retorna o banco de dados inteiro, resultando em tempo de execução. Portanto, o parâmetro $ε$ é necessário para cortar a densidade de clusters que não são mais interessantes e para acelerar o algoritmo. ${\ displaystyle O (n ^ {2})}$

O parâmetro $ε$ é, estritamente falando, desnecessário. Ele pode simplesmente ser definido para o valor máximo possível. Quando um índice espacial está disponível, no entanto, ele desempenha um papel prático no que diz respeito à complexidade. OPTICS abstrai do DBSCAN removendo este parâmetro, pelo menos ao ponto de apenas ter que fornecer o valor máximo.

Pseudo-código

A abordagem básica do OPTICS é semelhante ao DBSCAN , mas em vez de manter membros de cluster conhecidos, mas até agora não processados em um conjunto, eles são mantidos em uma fila de prioridade (por exemplo, usando um heap indexado ).

function OPTICS(DB, eps, MinPts) is
    for each point p of DB do
        p.reachability-distance = UNDEFINED
    for each unprocessed point p of DB do
        N = getNeighbors(p, eps)
        mark p as processed
        output p to the ordered list
        if core-distance(p, eps, MinPts) != UNDEFINED then
            Seeds = empty priority queue
            update(N, p, Seeds, eps, MinPts)
            for each next q in Seeds do
                N' = getNeighbors(q, eps)
                mark q as processed
                output q to the ordered list
                if core-distance(q, eps, MinPts) != UNDEFINED do
                    update(N', q, Seeds, eps, MinPts)

Em update (), a fila de prioridade Seeds é atualizada com o -bizinho de e , respectivamente: ${\ displaystyle \ varepsilon}$ ${\ displaystyle p}$ ${\ displaystyle q}$

function update(N, p, Seeds, eps, MinPts) is
    coredist = core-distance(p, eps, MinPts)
    for each o in N
        if o is not processed then
            new-reach-dist = max(coredist, dist(p,o))
            if o.reachability-distance == UNDEFINED then // o is not in Seeds
                o.reachability-distance = new-reach-dist
                Seeds.insert(o, new-reach-dist)
            else               // o in Seeds, check for improvement
                if new-reach-dist < o.reachability-distance then
                    o.reachability-distance = new-reach-dist
                    Seeds.move-up(o, new-reach-dist)

OPTICS, portanto, produz os pontos em uma ordem particular, anotada com sua menor distância de alcançabilidade (no algoritmo original, a distância do núcleo também é exportada, mas isso não é necessário para processamento posterior).

Extraindo os clusters

Usando um gráfico de alcançabilidade (um tipo especial de dendrograma ), a estrutura hierárquica dos clusters pode ser obtida facilmente. É um gráfico 2D, com a ordenação dos pontos processados pelo OPTICS no eixo xe a distância de alcançabilidade no eixo y. Como os pontos pertencentes a um cluster têm uma distância de alcançabilidade baixa para seu vizinho mais próximo, os clusters aparecem como vales no gráfico de alcançabilidade. Quanto mais profundo o vale, mais denso é o aglomerado.

A imagem acima ilustra esse conceito. Em sua área superior esquerda, um conjunto de dados de exemplo sintético é mostrado. A parte superior direita visualiza a árvore geradora produzida pelo OPTICS e a parte inferior mostra o gráfico de alcançabilidade calculado pelo OPTICS. As cores neste gráfico são rótulos e não calculadas pelo algoritmo; mas é bem visível como os vales no gráfico correspondem aos aglomerados no conjunto de dados acima. Os pontos amarelos nesta imagem são considerados ruído e nenhum vale é encontrado em seu gráfico de alcançabilidade. Eles geralmente não são atribuídos a clusters, exceto o cluster onipresente "todos os dados" em um resultado hierárquico.

A extração de clusters deste gráfico pode ser feita manualmente selecionando um intervalo no eixo x após a inspeção visual, selecionando um limite no eixo y (o resultado é então semelhante a um resultado de agrupamento DBSCAN com os mesmos parâmetros e minPts; aqui um valor de 0,1 pode produzir bons resultados) ou por diferentes algoritmos que tentam detectar os vales por declividade, detecção de joelho ou máximos locais. Os agrupamentos obtidos dessa forma geralmente são hierárquicos e não podem ser obtidos por uma única execução do DBSCAN. ${\ displaystyle \ varepsilon}$

Complexidade

Como o DBSCAN , o OPTICS processa cada ponto uma vez e executa uma consulta ao bairro durante esse processamento. Dado um índice espacial que concede uma consulta de vizinhança em tempo de execução, é obtido um tempo de execução geral de . Os autores do artigo OPTICS original relatam um fator de desaceleração constante real de 1,6 em comparação com DBSCAN. Observe que o valor de pode influenciar fortemente o custo do algoritmo, uma vez que um valor muito grande pode elevar o custo de uma consulta de vizinhança à complexidade linear. ${\ displaystyle \ varepsilon}$ ${\ displaystyle O (\ log n)}$ ${\ displaystyle O (n \ cdot \ log n)}$ ${\ displaystyle \ varepsilon}$

Em particular, escolher (maior do que a distância máxima no conjunto de dados) é possível, mas leva à complexidade quadrática, uma vez que cada consulta na vizinhança retorna o conjunto de dados completo. Mesmo quando nenhum índice espacial está disponível, isso tem um custo adicional no gerenciamento do heap. Portanto, deve ser escolhido de forma adequada para o conjunto de dados. ${\ displaystyle \ varepsilon> \ max _ {x, y} d (x, y)}$ ${\ displaystyle \ varepsilon}$

Extensões

OPTICS-OF é um algoritmo de detecção de outlier baseado em OPTICS. O principal uso é a extração de outliers de uma execução existente de OPTICS a baixo custo em comparação com o uso de um método de detecção de outlier diferente. A versão LOF mais conhecida é baseada nos mesmos conceitos.

DeLi-Clu, Density-Link-Clustering combina ideias de clustering de ligação única e OPTICS, eliminando o parâmetro e oferecendo melhorias de desempenho em relação ao OPTICS. ${\ displaystyle \ varepsilon}$

HiSC é um método de agrupamento de subespaço hierárquico (paralelo ao eixo) baseado em OPTICS.

HiCO é um algoritmo de agrupamento de correlação hierárquica baseado em OPTICS.

DiSH é uma melhoria em relação ao HiSC que pode encontrar hierarquias mais complexas.

FOPTICS é uma implementação mais rápida usando projeções aleatórias.

HDBSCAN * é baseado em um refinamento de DBSCAN, excluindo pontos de fronteira dos clusters e, portanto, seguindo mais estritamente a definição básica de níveis de densidade de Hartigan.

Disponibilidade

Implementações Java de OPTICS, OPTICS-OF, DeLi-Clu, HiSC, HiCO e DiSH estão disponíveis no framework de mineração de dados ELKI (com aceleração de índice para várias funções de distância, e com extração automática de cluster usando o método de extração ξ). Outras implementações Java incluem a extensão Weka (sem suporte para extração de cluster ξ).

O pacote R "dbscan" inclui uma implementação C ++ do OPTICS (com extração de cluster tradicional semelhante a dbscan e ξ) usando uma árvore kd para aceleração de índice apenas para distância euclidiana.

As implementações do OPTICS em Python estão disponíveis na biblioteca PyClustering e no scikit-learn . HDBSCAN * está disponível na biblioteca hdbscan .

Languages

In other projects