Outliers Detecção de Anomalias

AULA 18

DATA MINING

O que são outliers ? Um outlier é um fato que desvia tanto de

outros fatos a ponto de gerar suspeitas de que foi gerado um mecanismo diferente.

D.Hawkins: Identification of Outliers. Chapman and Hall, London, 1980.

Detecção de outliers - aplicações Detecção de fraudes

o comportamento de compras de alguém que rouba um cartão de crédito é provavelmente diferente daquele do proprietário do cartão.

Detecção de intrusões Ataques em sistemas de computadores apresentam comportamento

diferente do comportamento usual dos sistemas. Perturbações em ecossistemas

Furacões, secas, enchentes, ondas de calor, incêndios. Saúde pública

Casos de varíola são considerados anomalias, que podem indicar um problema com o processo de vacinação na cidade.

Medicina Para um certo paciente, certos sintomas ou resultados de testes podem

indicar problemas de saúde.

Técnicas de detecção de anomalias Enfoques estatísticos Baseadas em distância Baseadas em densidade

Definição baseada em distânciaUm objeto O de um banco de dados BD é

chamado de BD(p,d)-outlier se pelo menos uma fração p (0 < p < 1) de objetos de BD estão fora de uma vizinhança de raio d de O

p = 2/3

outlier

Processo não inteiramente automático

Determinação dos parâmetros p e d

Teste de validade: decidir se os objetos identificados como outliers são realmente outliers

Tarefa de um especialista humano

Problema Entrada

Banco de dados D com N objetos Um número p, 0 < p < 1 Um número d > 0 Dist = função distância considerada

Saida Conjunto dos outliers de D, i.e., conjunto dos objetos O

tais que o número máximo de objetos dentro de uma d-vizinhança de O é M = N (1-p)

Algoritmo Simples Determinar para cada objeto do BD sua vizinhança de

tamanho d Determinar aqueles objetos cuja vizinhança tem um número

de elementos ≤ M Estrutura de indice multidimensional Executa-se uma busca dentro de um raio d para cada

objeto p de BD No momento em que M+1 objetos são encontrados, a

busca termina e O é declarado não-outlier Os objetos que sobram são declarados outliers

Problemas: construção da estrutura de indice e o tempo da busca, para cada objeto p do BD.

Algoritmo NL (Nested Loop) Evita a construção da estrutura de índice

multidimensional Foco: diminuir o custo de acesso a disco Complexidade = O(kN2)

k = número de atributos do BD N = número de tuplas do BD

Idéia do algoritmo NL

Banco de Dados

Bloco A

Bloco B

Bloco C

Bloco D

Buffer

Bloco A

Para cada objeto t de A - Cont := 0 - Para cada objeto s de A se dist(t,s) ≤ d então Cont:= Cont + 1 - se Cont ≥ M etiqueta-se t como não-outlier

Algoritmo NL

Banco de Dados

Bloco A

Bloco B

Bloco C

Bloco D

Buffer

Bloco A

Para cada objeto t de A não etiquetado - Cont := 0 - Para cada objeto s de B se dist(t,s) ≤ d então Cont:= Cont + 1 - se Cont > M etiqueta-se t como não-outlier

Bloco BBloco CBloco D

4 acessos ao banco de dados

Algoritmo NL

Banco de Dados

Bloco A

Bloco B

Bloco C

Bloco D

Buffer

Bloco A

Bloco D

Ao final do loop são realizados2 acessos ao banco de dados: 1 para carregar o bloco B no segundo arraye outro para carregar o bloco C no segundo arrayNo final do loop, tem-se o bloco C no segundoarray.

Algoritmo NL

Banco de Dados

Bloco A

Bloco B

Bloco C

Bloco D

Buffer

Bloco D

Bloco C

Ao final do loop são realizados2 acessos ao banco de dados: 1 para carregar o bloco A no segundo array e outro para carregar o bloco B no segundo arrayNo final do loop, tem-se o bloco B no segundoarray.

Algoritmo NL

Banco de Dados

Bloco A

Bloco B

Bloco C

Bloco D

Buffer

Bloco C

Bloco B

Ao final do loop são realizados2 acessos ao banco de dados: 1 para carregar o bloco A no segundo array e outro para carregar o bloco D no segundo arrayNo final do loop, tem-se o bloco D no segundoarray.

Algoritmo NL

Banco de Dados

Bloco A

Bloco B

Bloco C

Bloco D

Buffer

Bloco B

Bloco D

Algoritmo pára – D já apareceu no primeiro array

Total de acessos ao disco: 10Cada acesso: um bloco é varridoNúmero de blocos = 4Total de varridas = 10/4 = 2,5

Algoritmo NL - generalização Capacidade do buffer = K ( 0 < K < 1)

(=fração do BD)

No exemplo K = 0,5 Divide-se o buffer em duas partes B1 e B2 Divide-se o banco de dados em 2K blocos (no

exemplo número de blocos = 2/0.5 = 4

Algoritmo FindAllOutsM – baseado em células

Hipóteses simplificadoras Dados bi-dimensionais (número de atributos = 2). Dados cabem na memória primária (tanto o BD

quanto as células que serão construidas a partir dele)

Generalização A idéia pode ser generalizada para dados com

dimensões quaisquer. Uma extensão deste algoritmo para bancos de dados

armazenados em disco : ver referência

Estrutura de Células

Vizinhança de raio d

d

2 C2 = d2

C = d

√ 2

L = tamanho da célula = d 2√2

As vizinhanças L1 e L2 de cada objeto

Célula Cx,y

Objeto (x,y)

Vizinhança L1(Cx,y)

Vizinhança L2(Cx,y)

d

Prop1: Máxima distância entre objetos de uma mesma célula Objetos pertencentes a uma mesma célula tem

uma distância máxima de L √2 = d √2 = d

2√2 2

L

L L √2 = d/2

Logo : Toda d-vizinhança de um objeto em Cx,y contém a célula inteira Cx,y

Prop2: Máxima distância entre objetos de uma célula e objetos de sua vizinhança L1

Se p está na célula Cx,y e q está em L1(Cx,y)

então dist(p,q) ≤ d

d

Logo : Toda d-vizinhança de um objeto em Cx,y contém a célula inteira Cx,y e sua vizinhança L1

Prop3: Mínima distância entre objetos de uma célula e objetos fora da vizinhança L2

= 3L = 3 d 2√2

= 1,06 d > d

Logo, se q é um objeto dentro da d-vizinhança de um objetop de Cx,y então dist(q,p) ≤ d portanto q deve estar dentro de L2 U L1 U Cx,y

Logo a d-vizinhança de p está contida em L2 U L1 U Cx,y

Condição para objetos de uma célula não serem outliers Se número de objetos em Cx,y > M então

nenhum objeto de Cx,y é um outlier

De fato: Propriedade 1 Toda d-vizinhança de um objeto p em Cx,y

contém toda a célula Cx,y Portanto contém mais de M elementos

Portanto p não pode ser um outlier

Condição para objetos de uma célula não serem outliers Se o número de elementos em Cx,y junto com

sua vizinhança L1 é maior do que M então nenhum objeto de Cx,y é um outlier

De fato: Propriedade 2 Toda d-vizinhança de um objeto p em Cx,y

contém toda a célula Cx,y e sua vizinhança L1 Portanto contém mais de M elementos

Portanto p não pode ser um outlier

Condição para objetos de uma célula serem outliers Se o número de objetos em Cx,y U L1 U L2 é ≤ M

então TODO objeto p de Cx,y é um outlier.

De fato: a d-vizinhança de p está contida em Cx,y U L1 U

L2 Portanto, a d-vizinhança de qualquer objeto de Cx,y

não contém mais do que M objetos. Portanto, os objetos de Cx,y são todos outliers.

Algoritmo FindAllOutsM – baseado em células

Hipóteses simplificadoras Dados bi-dimensionais (número de atributos = 2). Dados cabem na memória primária (tanto o BD

quanto as células que serão construidas a partir dele)

Generalização A idéia pode ser generalizada para dados com

dimensões quaisquer. Uma extensão deste algoritmo para bancos de dados

armazenados em disco : ver referência

Algoritmo FindAllOutsMSeja m = número de células (calculado em

função de d e do tamanho do BD )

1. Para cada q = 1, ..., m Ct-q := 0 % (vai contar o número de objetos em cada célula)

2. Para cada objeto p do BD 1. Associe a p uma célula Cq (a célula em que está inserido)

2. Ct-q:= Ct-q + 1

Após estes dois passos, todas as células estão construidas e sabemos o número de elementos de cada célula.

Algoritmo FindAllOutsM – cont.Os passos seguintes vão determinar quais objetos

p do BD são outliers, verificando-se somente: O número de elementos de sua célula C O número de elementos da vizinhança L1 de C O número de elementos da vizinhança L2 de C

Algoritmo FindAllOutsM – cont.Idéia Células com mais de M elementos são

etiquetadas de Vermelho Células na vizinhança L1 de uma célula vermelha

são etiquetadas de Azul. Células coloridas não tem chance de conter

outliers

Algoritmo FindAllOutsM – cont.

Para cada célula branca, contamos o número de seus elementos e da vizinhança L1Se for > M, não tem chance nenhuma de conter outliers – é etiquetada de Azul

Para cada célula branca restante, calcula-se o númerode seus elementos junto com L1 e L2.

Se for ≤ M : com certeza todos os elementos desta célulaserão outliers.

IdéiaIdéia (continuação)

Algoritmo FindAllOutsM – cont.

Para as células brancas onde a soma total de seus elementos junto com as vizinhanças L1e L2 for > M, faz-se a checagem das vizinhanças para cada objeto da célula.

Idéia (continuação)

3. Para cada q=1,...,m se Ct-q > M etiqueta célula Cq ‘Vermelha’ Todas as outras células são etiquetadas ‘Branca’

4. Para cada célula vermelha, verifica as células em sua vizinhança que são brancas. Etiquete-as de Azul

Algoritmo FindAllOutsM – cont.

Algoritmo FindAllOutsM – cont.5. Para cada célula branca Cw

Ct-w1:= Ct-w + Σi ɛ L1(Cw) Ct-i

Se Ct-w1 > M então Cw é etiquetada de Azul Se Ct-w1 ≤ M

Ct-w2:= Ct-w1 + Σi ɛ L2(Cw) Ct-i Se Ct-w2 ≤ M, marque todos os elementos de Cw

como outliers Se Ct-w2 > M

Algoritmo FindAllOutsM – cont.Se Ct-w2 > M Para cada p ɛ Cw

Ct-p = Ct-w1 (pois toda d-vizinhança de p contém Cw U L1)

Para cada q ɛ L2(Cw) : Se dist(p,q) ≤ d : Ct-p = Ct-p + 1

Se Ct-p > M , p é etiquetado como “não-outlier” Se Ct-p ≤ M, p é etiquetado como “outlier”

Caso k-dimensional Algoritmo FindAllOutsM é baseado nas

propriedades 1, 2 e 3. Estas propriedades dão as condições suficientes

para que um objeto seja classificado como outlier ou não-outlier.

Precisamos determinar O valor de L (tamanho de cada célula) A espessura da vizinhança L2

para que as propriedades 1, 2 e 3 continuem valendo.

Caso k-dimensionalNo caso k =2

L = tamanho da célula = d 2√2 Diagonal de um hipercubo k-dimensional de lado L = L√k Quanto deve valer L em função de d para que as

propriedades 1 e 2 continuem valendo ?

L = d 2√k

Caso k-dimensionalNo caso bi-dimensional a espessura da vizinhança L2 é

2

Mostre que para que a propriedade 3 continue valendo (distância mínima entre um objeto de Cx,y e um objeto fora de L2 deve ser > d)

é suficiente que a espessura da vizinhança L2 deve ser o primeiro inteiro maior ou igual a 2√k - 1

Complexidade O(ck + N)

N = Tamanho do BD k = dimensão do BD

Para dimensões pequenas (≤ 4), complexidade é razoável.

Fixada a dimensão do BD, a complexidade é linear em função do tamanho do BD

A versão do algoritmo que trata o caso em que os dados são armazenados em disco: cada página de dados não é acessada mais do que 3 vezes.

Complexidade Resultados empíricos mostram que

Algoritmos baseados em estruturas de célula são superiores a outros algoritmos para k≤ 4.

Para k > 4, algoritmo NL é a melhor escolha.

ReferênciasAnálise comparativa de performance quando varia-se

N, p, d, k

Edwin M. Knorr, Raymond T. Ng: : Algorithms for Mining Distance-Based Outliers in Large Datasets. In Proc. 24th International Conference on Very Large Databases, VLDB 1998, New York, USA.

D.Hawkins: Identification of Outliers. Chapman and Hall, London, 1980.