Detecção de anomalias: diferenças entre revisões

Fonte: aprendis
Saltar para a navegaçãoSaltar para a pesquisa
Linha 55: Linha 55:
Isto resulta em que as observações normais tem LOF próximo de 1, e as anomalias um valor maior que 1. Para série de dados suficientemente grandes, um LOF de até 2 pode ser considerado normal.
Isto resulta em que as observações normais tem LOF próximo de 1, e as anomalias um valor maior que 1. Para série de dados suficientemente grandes, um LOF de até 2 pode ser considerado normal.


As vantagens deste algoritmo são a facilidade da interpretação dos valores de LOF e sua habilidade em detetar anomalias previamente não detetadas pela abordagem global<ref name="Amer">Amer M, Goldstein M: Nearest-Neighbor and Clustering based Anomaly Detection Algorithms for RapidMiner. In Proceedings of the 3rd RapidMiner Community Meeting and Conferernce (RCOMM 2012); 2012.</ref>.
As vantagens deste algoritmo são a facilidade da interpretação dos valores de LOF e sua habilidade em detetar anomalias previamente não detetadas pela abordagem global<ref name="Amer">Amer M, Goldstein M: Nearest-Neighbor and Clustering based Anomaly Detection Algorithms for RapidMiner. In Proceedings of the 3rd RapidMiner Community Meeting and Conferernce (RCOMM 2012); 2012.</ref>. Sua complexidade computacional depende do método de ''k-NN'' escolhido, sendo dado por <big>''O(n*tempo k-NN)''</big>


=== Métodos baseados em agrupamentos (''clusters'') ===
=== Métodos baseados em agrupamentos (''clusters'') ===

Revisão das 11h35min de 25 de fevereiro de 2016

Detecção de anomalias
Sigla DA
Aplicações Processamento de dados, Análise de Dados
Conceitos relacionados Dados, Anomalias, Mineração de Dados


Introdução

Embora as anomalias costumam ser consideradas erros ou ruídos, elas podem conter informação importante[1][2], sendo assim, de forma a se obter uma análise coerente de uma observação, é crucial identificá-las antes da modelação de um algoritmo e da análise dos resultados.[3][4].

As anomalias são comumente causadas pela presença de dados de classes diferentes, variações naturais e erros de medição ou colheita de dados[1].

A definição exata de uma anomalia depende geralmente de pressupostos inerentes à estrutura de dados e ao método aplicado para sua detecção:

  • Hawkins (1980)[5] “Uma observação que se desvia demasiadamente das outras observações ao ponto de levantar suspeitas de ter sido gerada por um mecanismo diferentes.”
  • Johnson (1992)[6] “Uma observação em uma série de dados em aparenta ser inconsistente com o restante daquela série de dados.”
  • Barnett (1994)[7] “A observação anómala, ou anomalia, é aquela que aparenta desviar-se marcadamente dos outros membros da amostra em que ela ocorre.”

Os métodos de detecção de anomalias tem sido utilizados em diversas aplicações, como detecção de fraude em cartões de crédito, irregularidade em eleições, limpeza de dados, invasão de redes, previsão de tempestades, detecção de anomalias em registos e análises médicas, detecção de tumores em imagens, e outras tarefas.

Taxonomia dos métodos de detecção de anomalias

Os métodos de detecção de anomalias foram inicialmente divididos em métodos univariados e multivariados, sendo atualmente divididos em métodos paramétricos (estatísticos) e não-paramétricos (model-free).

Os métodos paramétricos ou assumem que existe alguma distribuição conhecida dos dados[5][7][8], ou tem como fundamentação a estimativa estatística de uma distribuição desconhecida[9]. Tais métodos são na maioria das vezes impróprios para uma série de dados de grandes dimensões ou para série de dados sem qualquer conhecimento prévio de sua distribuição[10].

Nos métodos não-paramétricos podemos evidenciar os métodos de data-mining, também chamados de métodos baseado em distância. Estes métodos geralmente baseiam-se em medidas de distâncias locais e são capazes de processar base de dados de grande volume[11]. Outro método de detecção de anomalias está fundamentado nas técnicas de agrupamento (clustering) onde grupos de pequenas dimensões podem ser considerados como anomalias.[12][13].

Métodos paramétricos

Para a detecção de anomalias, pode ser usada uma abordagem paramétrica, que obriga ao conhecimento prévio da série de dados e da sua respectiva distribuição.

Métodos estatísticos

Métodos não-paramétricos

Métodos baseados na distância

Inicialmente proposto por Knorr & Ng (1997)[14], tem como pressupostos que os dados normais tem uma vizinhança densa, e que as anomalias estão afastados dos seus vizinhos.

O modelo básico de Knorr & Ng considera que a observação é definida como uma anomalia (baseada em distância) se ao menos uma fração β das observações da série de dados está afastada para além de r. Tal definição está baseada em um único critério global, determinado pelos parâmetros r e β. Esta definição levanta algumas dificuldades como a determinação do valor de r e a falta de um ranking para as anomalias. Sua complexidade computacional é de O(pn2), onde p é o número de atributos e n o tamanho da amostra, sendo portanto inadequado para grandes séries de dados.

Perspectiva global vs. perspectiva local: um objecto pode parecer anómalo em relação a todos os objetos, mas não em relação aos objetos vizinhos. Por exemplo, uma pessoa com 1,95m de altura é anormalmente alto em relação a população geral, mas não em relação a jogadores de basketball proficionais[1]. Desta forma, os métodos atuais baseados distância procuram abordar ambas as situações.

k-Vizinho mais Próximo (k-Nearest Neighbor: k-NN)

Proposta por Ramaswamy (2000)[12], é uma abordagem global, que considera que as anomalias são as n observações que possuem as maiores distâncias ao seu k-ésimo vizinho mais próximo. Uma deficiência deste método é que ele só considera a distância do k-ésimo vizinho e ignora a informação das observações mais próximas. Uma alternativa também utilizada é obter a distância média dos k vizinhos mais próximos, com a vantagem de ser mais robusto a flutuações estatísticas, e a desvantagem de levar mais tempo para ser calculado. Possui uma complexidade computacional variável dependendo do algoritmo de procura do vizinho mais próximo[15].

Fator de Anomalia Local (Local Outlier Factor: LOF )

Foi o primeiro algoritmo baseado em densidade, proposto em 2000 por Breunig et al.[16], e é provavelmente o método atualmente mais utilizado.

Este método compara a densidade local de uma observação com a densidade dos seus vizinhos, dado que a densidade é inversamente proporcional a média das distâncias dos k-vizinhos mais próximos. O valor LOF atribuído à observação é dado pela razão da densidade local desta observação pela média das densidades dos seus vizinhos.

Isto resulta em que as observações normais tem LOF próximo de 1, e as anomalias um valor maior que 1. Para série de dados suficientemente grandes, um LOF de até 2 pode ser considerado normal.

As vantagens deste algoritmo são a facilidade da interpretação dos valores de LOF e sua habilidade em detetar anomalias previamente não detetadas pela abordagem global[17]. Sua complexidade computacional depende do método de k-NN escolhido, sendo dado por O(n*tempo k-NN)

Métodos baseados em agrupamentos (clusters)

Fator de Anomalia Local Baseado em Aglomerados (Cluster-Based Local Outlier Factor: CBLOF)

Densidade Local do Fator de Anomalia Baseado em Aglomerados (Local Density Cluster-Based Outlier Factor: LDCOF)

Referências

  1. ↑ 1,0 1,1 1,2 Pang-Ning T, Steinbach M, Kumar V: Introduction to Data Mining. 2006.
  2. ↑ Maletic JI, Marcus A: Data Mining and Knowledge Discovery Handbook. 2nd edition. Boston, MA: Springer US; 2010.
  3. ↑ Liu H, Shah S, Jiang W: On-line outlier detection and data cleaning. Comput Chem Eng 2004, 28:1635–1647.
  4. ↑ Williams G, Baxter R, Hawkins S: A comparative study of RNN for outlier detection in data mining. In 2002 IEEE International Conference on Data Mining, 2002. Proceedings.; 2002:709–712.
  5. ↑ 5,0 5,1 Hawkins D, Identification of Outliers, Chapman and Hall, 1980.
  6. ↑ Johnson R, Applied Multivariate Statistical Analysis. Prentice Hall, 1992.
  7. ↑ 7,0 7,1 Barnett V, Lewis T, Outliers in Statistical Data. JohnWiley, 1994.
  8. ↑ Rousseeuw PJ, Leroy AM: Robust Regression and Outlier Detection. Time 1987, 3:329.
  9. ↑ Hadi AS: Identifying Multiple Outliers in Multivariate Data. Journal of the Royal Statistical Society. Series B (Methodological) 1992:761–771.
  10. ↑ Papadimitriou S, Kitagawa H, Gibbons PB, Faloutsos C: LOCI: Fast outlier detection using the local correlation integral. In Proceedings - International Conference on Data Engineering; 2003:315–326.
  11. ↑ Knorr E, Ng R, Tucakov V: Distance-based outliers: algorithms and applications. VLDB J Int J Very Large Data Bases 2000, 8:237–253.
  12. ↑ 12,0 12,1 Ramaswamy S, Rastogi R, Shim K: Efficient algorithms for mining outliers from large data sets. ACM SIGMOD Rec 2000, 29:427–438.
  13. ↑ Kaufman L, Kaufman L, Rousseeuw PJ, Rousseeuw PJ: Finding Groups in Data: An Introduction to Cluster Analysis (Wiley Series in Probability and Statistics). 2005.
  14. ↑ Knorr E, Ng R, ”A unified approach for mining outliers,” In Proceedings Knowledge Discovery KDD, 219-222, 1997.
  15. ↑ Weber R, Schek HJ, Blott S: A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces. Proc 24th VLDB Conf 1998, New York C:194–205.
  16. ↑ Breunig MM, Kriegel H-P, Ng RT, Sander J: LOF: Identifying Density-Based Local Outliers. In Proceedings of the 2000 ACM SIGMOD international conference on Management of data - SIGMOD ’00. New York, New York, USA: ACM Press; 2000(February):93–104.
  17. ↑ Amer M, Goldstein M: Nearest-Neighbor and Clustering based Anomaly Detection Algorithms for RapidMiner. In Proceedings of the 3rd RapidMiner Community Meeting and Conferernce (RCOMM 2012); 2012.
Obtida de "https://aprendis.med.up.pt/index.php?title=Detecção_de_anomalias&oldid=3128"