Seminário
Mineração de Exceções
Erivan A. Andrade ([email protected])
Jacques Robin ([email protected])
1
UFPE-CIN 2002
Roteiro
Motivação
Métodos Baseados em Agrupamento
Métodos Baseados em Estatística
Métodos baseados em Distância
Métodos Baseados em Desvio
Conclusões
Referências
2
UFPE-CIN 2002
Motivação: definição
 O que é outlier?
 É uma observação, num conjunto de dados, que é
suficientemente dissimilar ou aberrante do restante dos dados
para levantar suspeita de ser causado por um mecanismo
diferenciado
 Equivalente a exceções
 Causa dos outliers: o que é esse mecanismo?
 Erro de medida
 Comportamento diferente do padrão
 Dilema: “o ruído de uns é o sinal dos outros”
 Mineração de outliers
 Detecção e análise de outliers
3
UFPE-CIN 2002
Motivação: aplicações práticas
4

Detecção de Fraudes

Comportamento de gastos de consumidores

Em análises médicas (resultados não esperados de
tratamentos )

Pesquisa farmacêutica

Marketing

Coaching (hey Felipão, Romário é um outlier! )

Etc.
UFPE-CIN 2002
Técnicas de Mineração de Exceções
 Classes de técnicas:
 Semi-automático:
Visualização
 Automático
Baseados
Clustering
Baseado
Estatística
Baseado
Desvio
Baseado
Distância
5
 Características desejáveis
em
em
em
em
UFPE-CIN 2002
 Escalável para alta
dimensionalidade
 Interpretabilidade dos
resultados
 Computacionalmente
eficiente
 Dá importância ao
comportamento local
dos dados
 Ordenação
dos
outliers
Roteiro
Motivação
Métodos Baseados em Agrupamento
Métodos Baseados em Estatística
Métodos baseados em Distância
Métodos Baseados em Desvio
Conclusões
Referências
6
UFPE-CIN 2002
Mineração de exceção
baseada em agrupamento
 Idéia:
 Formar grupos de dados
 Dados que não se encaixam em nenhum
grupos são considerados exceções
Inserir figura exemplo aqui
7
UFPE-CIN 2002
Mineração de exceção baseada em
agrupamento
 Vantagens
Reutiliza vasto
leque de métodos
de agrupamentos
Não requer
conhecimento
prévio de
distribuição
8
UFPE-CIN 2002
 Limitações
O que se busca é
otimizar
os
agrupamentos, não
a
detecção
de
exceções
O que é exceção
para
uma
configuração pode
não ser para outra
Roteiro
Motivação
Métodos baseados em Agrupamento
Métodos baseados em Estatística
Métodos baseados em Distância
Métodos Baseados em Desvio
Conclusões
Referências
9
UFPE-CIN 2002
Mineração de Outliers Baseada em
Estatística
 Assume distribuição ou modelo probabilístico para
um conjunto de dados
 Ex: distribuição normal
 Usa Teste de discordância (TD) → identifica os
outliers com respeito ao modelo escolhido
 Se um objeto for significativamente maior ou
menor que o modelo escolhido ele é uma exceção
 O TD examina 2 hipóteses:
 Uma hipótese de trabalho
 Uma hipótese alternativa
10
UFPE-CIN 2002
Mineração de Outliers Baseada em
Estatística
 Vantagens:
 Limitações:
 Pode ser avaliado o nível
de significância de uma
exceção
 Usa métodos estatístico
consolidados ao longo
dos tempos
O
modelo
escolhido
influencia a identificação
dos Outliers
 Testa aberração ao longo
de apenas uma única
dimensão
 Dificuldade na escolha
de uma distribuição
11
UFPE-CIN 2002
Roteiro
Motivação
Métodos baseados em Agrupamento
Métodos baseados em Estatística
Métodos Baseados em Desvio
Métodos baseados em Distância
Conclusões
Referências
12
UFPE-CIN 2002
Mineração de Outliers Baseada em Desvio
Não usa métodos estatísticos nem
medidas de distância
Define exceção como pontos cujo valor
desviam da maioria ao longo de
algumas ou todas as dimensões
Exceções são equivalentes a Desvios
de comportamento
13
UFPE-CIN 2002
Mineração de Outliers Baseada em
Densidade de Distribuição
Características
 Divide o espaço de dados em  classe equi-depth
 Cada classe contém uma fração f=1/  dos registros
 Diferentes localidades dos dados são densas com
respeito a diferentes subconjuntos de atributos
 Observa a densidade de distribuição da projeção dos
dados
 Gera projeções dos dados sobre k dimensões
 Identifica nessas projeções, regiões de densidade
anormalmente baixa
 Pontos nessas regiões são considerados outliers
 Suporta dados com alta dimensionalidade
14
UFPE-CIN 2002
Mineração de Outliers Baseada em
Densidade de Distribuição
Ideia
15
UFPE-CIN 2002
Mineração de Outliers Baseada em
Densidade de Distribuição
 O número de pontos em um cubo pode ser aproximando
por uma distribuição normal e então:
k
N.
f
Fração esperada
N . f k .(1  f k )
Desvio padrão
Coeficiente de dispersão de um cubo D
S ( D) 
n( D )  N . f
k
N . f k .(1  f k )
n(D) número de pontos em um cubo k-dimensional
N número de pontos no conjunto de dados
 S(D)<0 indica cubos com numero
significativamente abaixo do esperado
16
UFPE-CIN 2002
de
pontos
Mineração de Outliers Baseada em
Densidade de Distribuição
 Busca necessária para gerar as projeções
 Busca exaustiva: garante encontrar todas a
exceções mas com complexidade alta
 Busca genética com função de seleção,
crossover e mutação específica para o
problema permite encontrar, a um custo muito
menor, a maioria das exceções
Comparativo de resultado
17
UFPE-CIN 2002
Mineração de Outliers em Cubos OLAP
 Exploração dirigida a hipótese
 O usuário interativamente busca por regiões de anomalias
 As regiões de anomalias representam áreas de interesse
 A busca das anomalias é feita com o uso das operações de
cubo OLAP
Dril-down, roll-up, seleção
 Problemas da exploração dirigida a hipótese
 Espaço de busca muito grande
 As anomalias podem estar em níveis inferiores ao ponto de
partida da análise
 Grande quantidade de agregados
18
UFPE-CIN 2002
Mineração de Outliers em Cubos OLAP
 Exploração dirigida a descoberta
 O usuário busca por anomalias guiado por
indicadores pré-computados
 Os indicadores permitem a observação de padrões
anormais em qualquer nível de agregação
 Muito útil, especialmente, para grande numero de
dimensões
 Um valor é uma exceção se ele difere
significativamente do seu valor antecipado
Valor calculado por um modelo estatístico
Considera o contexto da posição da célula no cubo
Combina as tendências ao longo das diferentes dimensões a
que uma célula pertence
19
UFPE-CIN 2002
Mineração de Outliers em Cubos OLAP
 Exploração dirigida a descoberta
 Definição de exceção (yijk – ŷijk)/ ijk > ( = 2.5)
 Cálculo do valor antecipado ŷijk
(γ + γiA + γjB + γkC + γijAB + γjkBC + γikAC)
ŷijk = e
 Onde
 γ = l+...+ (média ao longo de todas as dimensões)
 γirAr = l+...+ir+...+ - γ(média ao longo de uma dimensão)
 γi isArAs = l+...+ir+...+ is+...+ - γirAr - γisAs – γ (Média ao longo de
r
duas dimensões)
20
UFPE-CIN 2002
Mineração de Outliers em Cubos OLAP
 Exploração dirigida a descoberta
 Equação iterativa para cálculo do  (desvio padrão)
2ijk = (ŷijk)
Onde  é calculado por

21
(yijk - ŷijk)2
(ŷijk)
log ŷijk
UFPE-CIN 2002
 log ŷijk
0
Mineração de Outliers em Cubos OLAP
Exploração dirigida a descoberta
 Os indicadores dão o grau de surpresa do valor da
célula
 Os indicadores são 3:
 SelfExp: valor surpresa da célula em relação a outras
células no mesmo nível de agregação
 InExp: Grau de surpresa em algum nível abaixo desta
célula
 PathExp: grau de surpresa para cada caminho de
drill-down a partir da célula.
22
UFPE-CIN 2002
Mineração de Outliers em Cubos OLAP
Exploração dirigida a descoberta (Exemplo)
Destacar Exceções
23
UFPE-CIN 2002
Mineração de Outliers em Cubos OLAP
Exploração dirigida a descoberta (Exemplo)
Exceção de Caminho
24
UFPE-CIN 2002
Mineração de Outliers em Cubos OLAP
Exploração dirigida a descoberta (Exemplo)
Drill-Down por produto (PathExp)
25
UFPE-CIN 2002
Mineração de Outliers em Cubos OLAP
Exploração dirigida a descoberta (Exemplo)
Drill-Drown para Diet-S (InExp)
26
UFPE-CIN 2002
Mineração de Outliers em Cubos OLAP
Exploração dirigida a descoberta (Exemplo)
27
UFPE-CIN 2002
Roteiro
Motivação
Métodos baseados em Agrupamento
Métodos baseados em Estatística
Métodos Baseados em Desvio
Métodos baseados em Distância
Conclusões
Referências
28
UFPE-CIN 2002
Mineração de Outliers Baseada em
Distância: Dk(p)
 Busca Resolver limitações do estatístico
 Um outlier é determinado baseado na distancia
Dk(p)
 Dk(p)= distância de p ao seu k-esimo vizinho
 Evita suposição sobre distribuição dos dados
 Menor custo computacional
 Pode, ás vezes, convergir para os métodos
estatísticos
 Desvantagem
Não é escalável para mais que 5 dimensões
29
UFPE-CIN 2002
Detecção de Outliers Baseada em
k
Distâncias: D (p)
Algoritmo Loop aninhado
 Para cada ponto p no conjunto de dados calcula
Dk(p)
 Para calcular cada Dk(p) varre todos os dados
 Mantém uma lista de k vizinhos mais próximo
para cada ponto p
 Os n pontos com maior valor de Dk(p) são os n
outliers
 Para melhorar a eficiência pode-se considerar
blocos de pontos ao invés de pontos individuais
30
UFPE-CIN 2002
Detecção de Outliers Baseada em
k
Distâncias: D (p)
Algoritmo baseado em índice
 O uso de estruturas de índices espaciais pode
diminuir substancialmente o calculo de
distâncias (R*-tree, por exemplo)
 É possível podar sub-arvores cujos nós não
podem conter outlier
A cada passo guarda-se os n outliers
encontrados
Dnmin menor Dk entre os outlier
Dk(p)< Dnmin P não pode ser um outlier
31
UFPE-CIN 2002
Detecção de Outliers Baseada em
k
Distâncias: D (p)
Algoritmo Baseado em partições
 Detecta os n outliers mais fortes
Os outliers são ordenados pela distância Dk(p)
 Baseia se na distância dos vizinhos mais próximos
 O conjunto de dados é divididos em partições por
meio de algoritmos de agrupamento
 Poda partições que não são candidatas a conter
outlier
Acelera a identificação pois diminui a quantidade
de pontos
32
UFPE-CIN 2002
Detecção de Outliers Baseada em
k
Distâncias : D (p)
Algoritmo Baseado em partições (passos)
 Gerar partições
 Através de clustering
 Calcular limites Dk para os pontos em cada partição
 P.upper=max(Dk) e P.lower=min(Dk) dos pontos da
partição P
 Identificar partições candidatas a conter exceções
 P.upperminDkDist=min{Pi.lower:1 i  l}
 Pi.lower>Pj.lower>..>Pl.lower e o número de pontos seja
pelo menos n
 Computar exceções com os pontos nas partições candidatas
 P.neighbors denota as partições vizinhas de P a uma
distância de P.upper
33
UFPE-CIN 2002
Detecção de Outliers Baseada em
k
Distâncias : D (p)
Algoritmo Baseado em partições (passos)
O número total de pontos a ser examinado para calcular outlier
é o das partições candidatas+os de suas vizinhas
34
UFPE-CIN 2002
Detecção de Outliers Baseada em
k
Distâncias : D (p)
Algoritmo Baseado em partições
35
UFPE-CIN 2002
Detecção de Outliers Baseada em
k
Distâncias : D (p)
Comparativo de desempenho
36
UFPE-CIN 2002
Detecção de Outliers Baseada em
k
Distâncias : D (p)
Comparativo de desempenho
37
UFPE-CIN 2002
Roteiro
Motivação
Métodos baseados em Agrupamento
Métodos baseados em Estatística
Métodos Baseados em Desvio
Métodos baseados em Distância
Conclusões
Referências
38
UFPE-CIN 2002
Conclusões
Mineração de exceções
É de grande interesse
É
custosa
computacionalmente,
principalmente para grande quantidade
de dimensões
Necessita de métodos robustos
39
UFPE-CIN 2002
Referências
 Data Mining: concepts and techniques, de Han, J. &
Kamber, M., 2001, Morgan Kaufmann
 Discovery-driven Exploration of OLAP Data Cubes, de
Sunita Sarawagi, Rakesh Agrawal, Nimrod Megiddo,
IBM Research Division
 Efficient Algoritms for Mining Outliers from Data sets.
Sridhar Ramaswamy, Rajeev Ratogi e Kyuseok
Shim. 2000
 Outlier Detection for High Dimensional Data. Charu C.
Aggarwal e Philip S. Yu. 2001
40
UFPE-CIN 2002
Visão de Outliers
41
UFPE-CIN 2002
Comparativo: Força bruta x algorotimo
Evolutivo
42
UFPE-CIN 2002