Fator de outlier local - Local outlier factor

Na detecção de anomalias , o fator de outlier local ( LOF ) é um algoritmo proposto por Markus M. Breunig, Hans-Peter Kriegel , Raymond T. Ng e Jörg Sander em 2000 para encontrar pontos de dados anômalos medindo o desvio local de um determinado ponto de dados com respeito aos seus vizinhos.

LOF compartilha alguns conceitos com DBSCAN e OPTICS , como os conceitos de "distância do núcleo" e "distância de alcançabilidade", que são usados ​​para estimativa de densidade local.

Ideia básica

Ideia básica de LOF: comparar a densidade local de um ponto com as densidades de seus vizinhos. A tem uma densidade muito menor do que seus vizinhos.

O fator de outlier local é baseado no conceito de densidade local, onde a localidade é dada por k vizinhos mais próximos, cuja distância é usada para estimar a densidade. Ao comparar a densidade local de um objeto com as densidades locais de seus vizinhos, pode-se identificar regiões de densidade semelhante e pontos que possuem densidade substancialmente menor do que seus vizinhos. Esses são considerados outliers .

A densidade local é estimada pela distância típica em que um ponto pode ser "alcançado" de seus vizinhos. A definição de "distância de alcançabilidade" usada no LOF é uma medida adicional para produzir resultados mais estáveis ​​dentro dos clusters. A "distância de alcance" usada pelo LOF tem alguns detalhes sutis que são freqüentemente encontrados incorretos em fontes secundárias, por exemplo, no livro de Ethem Alpaydin.

Formal

Seja k -distância ( A ) a distância do objeto A ao k -ésimo vizinho mais próximo. Observe que o conjunto dos k vizinhos mais próximos inclui todos os objetos a esta distância, que pode no caso de um "empate" ser mais do que k objetos. Denotamos o conjunto de k vizinhos mais próximos como N k (A) .

Ilustração da distância de alcance. Os objetos B e C têm a mesma distância de alcançabilidade ( k = 3 ), enquanto D não é um k vizinho mais próximo

Esta distância é usada para definir o que é chamado de distância de alcançabilidade :

distância de alcançabilidade k ( A , B ) = max { k- distância ( B ), d ( A , B )}

Em outras palavras, a distância de alcance de um objecto Uma de B é a distância real dos dois objectos, mas pelo menos o k -Distância de B . Os objetos que pertencem aos k vizinhos mais próximos de B (o "núcleo" de B , consulte a análise de cluster DBSCAN ) são considerados igualmente distantes. O motivo dessa distância é obter resultados mais estáveis . Observe que esta não é uma distância na definição matemática, pois não é simétrica. (Embora seja um erro comum usar sempre a distância k (A) , isso resulta em um método ligeiramente diferente, conhecido como LOF simplificado)

A densidade de alcançabilidade local de um objeto A é definida por

lrd k (A): = 1 / ( Σ B ∈ N k (A) distância de alcançabilidade k (A, B)/| N k (A) |)

que é o inverso da distância média de alcançabilidade do objeto A de seus vizinhos. Observe que não é a acessibilidade média dos vizinhos de A (que por definição seria a k- distância (A) ), mas a distância na qual A pode ser "alcançado" de seus vizinhos. Com pontos duplicados, esse valor pode se tornar infinito.

As densidades de alcançabilidade local são então comparadas com as dos vizinhos usando

LOF k (A): =Σ B ∈ N k (A)lrd k (B)/lrd k (A)/| N k (A) | = Σ B ∈ N k (A) lrd k (B)/| N k (A) | · Lrd k (A)

que é a densidade de alcançabilidade local média dos vizinhos dividida pela densidade de alcançabilidade local do próprio objeto. Um valor de aproximadamente 1 indica que o objeto é comparável a seus vizinhos (e, portanto, não é um outlier). Um valor abaixo de 1 indica uma região mais densa (que seria um inlier), enquanto valores significativamente maiores que 1 indicam outliers.

LOF (k) ~ 1 significa densidade semelhante aos vizinhos,

LOF (k) <1 significa densidade mais alta do que vizinhos (Inlier),

LOF (k)> 1 significa densidade mais baixa do que vizinhos (outlier)

Vantagens

Pontuações LOF conforme visualizadas por ELKI . Embora o cluster superior direito tenha uma densidade comparável aos outliers próximos ao cluster inferior esquerdo, eles são detectados corretamente.

Devido à abordagem local, LOF é capaz de identificar outliers em um conjunto de dados que não seriam outliers em outra área do conjunto de dados. Por exemplo, um ponto a uma "pequena" distância de um aglomerado muito denso é um outlier, enquanto um ponto dentro de um aglomerado esparso pode exibir distâncias semelhantes aos de seus vizinhos.

Embora a intuição geométrica de LOF seja aplicável apenas a espaços vetoriais de baixa dimensão, o algoritmo pode ser aplicado em qualquer contexto, uma função de dissimilaridade pode ser definida. Experimentou-se que ele funciona muito bem em várias configurações, muitas vezes superando os concorrentes, por exemplo, na detecção de intrusão de rede e em dados de benchmark de classificação processados.

A família de métodos LOF pode ser facilmente generalizada e então aplicada a vários outros problemas, como detecção de outliers em dados geográficos, fluxos de vídeo ou redes de autoria.

Desvantagens e Extensões

Os valores resultantes são valores de quociente e difíceis de interpretar. Um valor de 1 ou até menos indica um inlier claro, mas não há uma regra clara para quando um ponto é um outlier. Em um conjunto de dados, um valor de 1,1 pode já ser um outlier, em outro conjunto de dados e parametrização (com fortes flutuações locais) um valor de 2 ainda pode ser um inlier. Essas diferenças também podem ocorrer dentro de um conjunto de dados devido à localidade do método. Existem extensões do LOF que tentam melhorar em relação ao LOF nestes aspectos:

  • Recurso Bagging para detecção de outlier executa LOF em várias projeções e combina os resultados para qualidades de detecção aprimoradas em dimensões altas. Esta é a primeira abordagem de aprendizado de conjunto para detecção de valores discrepantes; para outras variantes, consulte a ref.
  • Local Outlier Probability (LoOP) é ​​um método derivado de LOF, mas usa estatísticas locais baratas para se tornar menos sensível à escolha do parâmetro k . Além disso, os valores resultantes são escalados para um intervalo de valores de [0: 1] .
  • Interpretar e unificar pontuações atípicas propõe uma normalização das pontuações atípicas de LOF para o intervalo [0: 1] usando escala estatística para aumentar a usabilidade e pode ser vista uma versão aprimorada das idéias de LoOP.
  • On Evaluation of Outlier Rankings e Outlier Scores propõe métodos para medir similaridade e diversidade de métodos para construir conjuntos de detecção de outliers avançados usando variantes LOF e outros algoritmos e melhorando a abordagem de Feature Bagging discutida acima.
  • Detecção de outlier local reconsiderada: uma visão generalizada da localidade com aplicativos para detecção espacial, de vídeo e de rede discute o padrão geral em vários métodos de detecção de outlier local (incluindo, por exemplo, LOF, uma versão simplificada de LOF e LoOP) e resumos disso em uma estrutura geral. Esta estrutura é então aplicada, por exemplo, para detectar outliers em dados geográficos, fluxos de vídeo e redes de autoria.

Referências

  1. ^ Breunig, MM; Kriegel, H.-P. ; Ng, RT; Sander, J. (2000). LOF: Identificação de valores discrepantes locais baseados em densidade (PDF) . Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data . SIGMOD . pp. 93–104. doi : 10.1145 / 335191.335388 . ISBN 1-58113-217-4.
  2. ^ Breunig, MM; Kriegel, H.-P. ; Ng, RT; Sander, JR (1999). "OPTICS-OF: Identificando outliers locais" (PDF) . Princípios de mineração de dados e descoberta de conhecimento . Notas de aula em Ciência da Computação. 1704 . p. 262. doi : 10.1007 / 978-3-540-48247-5_28 . ISBN 978-3-540-66490-1.
  3. ^ Alpaydin, Ethem (2020). Introdução ao aprendizado de máquina (quarta edição). Cambridge, Massachusetts. ISBN 978-0-262-04379-3. OCLC  1108782604 .
  4. ^ a b c d Schubert, E .; Zimek, A .; Kriegel, H. -P. (2012). "Detecção de outlier local reconsiderada: uma visão generalizada sobre a localidade com aplicações para detecção de outlier espacial, de vídeo e de rede". Mineração de dados e descoberta de conhecimento . 28 : 190–237. doi : 10.1007 / s10618-012-0300-z . S2CID  19036098 .
  5. ^ Lazarevic, A .; Ozgur, A .; Ertoz, L .; Srivastava, J .; Kumar, V. (2003). "Um estudo comparativo de esquemas de detecção de anomalias na detecção de intrusão de rede" (PDF) . Proc. 3ª Conferência Internacional SIAM sobre Mineração de Dados : 25–36. Arquivado do original (PDF) em 17/07/2013 . Página visitada em 2010-05-14 .CS1 maint: usa o parâmetro de autores ( link )
  6. ^ Campos, Guilherme O .; Zimek, Arthur; Sander, Jörg; Campello, Ricardo JGB; Micenková, Barbora; Schubert, Erich; Assent, Ira; Houle, Michael E. (2016). "Sobre a avaliação da detecção de outliers não supervisionados: medidas, conjuntos de dados e um estudo empírico". Mineração de dados e descoberta de conhecimento . 30 (4): 891–927. doi : 10.1007 / s10618-015-0444-8 . ISSN  1384-5810 . S2CID  1952214 .
  7. ^ Lazarevic, A .; Kumar, V. (2005). "Recurso de ensacamento para detecção de outlier". Proc. 11ª Conferência Internacional ACM SIGKDD sobre descoberta de conhecimento em mineração de dados : 157–166. doi : 10.1145 / 1081870.1081891 . ISBN 159593135X. S2CID  2054204 .
  8. ^ Zimek, A .; Campello, RJGB; Sander, JR (2014). "Conjuntos para detecção de outliers não supervisionados". Boletim Informativo ACM SIGKDD Explorations . 15 : 11–22. doi : 10.1145 / 2594473.2594476 . S2CID  8065347 .
  9. ^ Kriegel, H.-P. ; Kröger, P .; Schubert, E .; Zimek, A. (2009). LoOP: Probabilidades atípicas locais (PDF) . Proceedings of the 18th ACM Conference on Information and Knowledge Management . CIKM '09. pp. 1649–1652. doi : 10.1145 / 1645953.1646195 . ISBN 978-1-60558-512-3.
  10. ^ Kriegel, HP ; Kröger, P .; Schubert, E .; Zimek, A. (2011). Interpretando e unificando pontuações atípicas . Proceedings of the 2011 SIAM International Conference on Data Mining. pp. 13–24. CiteSeerX  10.1.1.232.2719 . doi : 10.1137 / 1.9781611972818.2 . ISBN 978-0-89871-992-5.
  11. ^ Schubert, E .; Wojdanowski, R .; Zimek, A .; Kriegel, HP (2012). Sobre a avaliação de classificações e pontuações atípicas . Proceedings of the 2012 SIAM International Conference on Data Mining. pp. 1047–1058. CiteSeerX  10.1.1.300.7205 . doi : 10.1137 / 1.9781611972825.90 . ISBN 978-1-61197-232-0.