Detecção de Outliers com Floresta de Isolamento
Allan Moraes Ferraz de Araujo
27 de julho de 2019
Introdução
Regularmente em vários problemas necessitamos saber quais pontos de um conjunto de dados apresentam comportamento diferente dos outros, como é o caso na detecção de fraudes. Neste artigo introduziremos uma técnica muito interessante para identificar tais pontos, chamada “floresta de isolamento” e mostraremos sua implementação em R. Seu algoritmo é baseado em árvores de decisão aleatória e consiste basicamente em escolher aleatoriamente uma variável do conjunto de dados e executar uma cisão aleatória que tem como vantagem sobre outros algoritmos de detccção de anomalias suportar variáveis categóricas. O tamanho do caminho que um ponto tem são quanto passos são necessários para sair do nó inicial até o nó final.
Os pontos anômalos serão aqueles com caminho curto, pois estarão isolados, e os pontos “normais” terão um caminho mais longo, pois terão uma densidade maior, por exemplo imagine uma descrição do endereço de uma casa na Zona Oeste de São Paulo. “Pegue a primeira direita na Rua Clélia, depois contorne a esquerda em direção do Shopping Bourbon, etc…”. Existe bastante informação, pois a casa está em um lugar densamente habitado perto de outras casas. Agora imagine uma casa em uma ilha no litoral. “É a única casa naquela ilha”. Pois essa casa está isolada de outras. Similarmente pontos que podem ser descritos suscintamente podem ser classficados como outliers.
Exemplo - Aeroportos
Para exemplificar o funcionamento de floresta aleatória vamos trabalhar com a base de dados de aeroportos do site https://openflights.org/data.html.
Primeiro carregaremos os pacotes necessários para nossa análise.
library(isofor)
library(data.table)
library(ggplot2)
library(MASS)
library(viridis)## Loading required package: viridisLitelibrary(GGally)
library(metR)Leitura dos dados
theurl <- "https://raw.githubusercontent.com/jpatokal/openflights/master/data/airports.dat"
aeroportos <- fread(theurl, na.strings = "")
setnames(aeroportos, c("airport_id", "nome", "cidade","pais", "iata", "iacao", "latitude", "longitude", "altitude",
"timezone", "dst", "tz_database_time", "type", "source"))
head(aeroportos)## airport_id nome cidade
## 1: 1 Goroka Airport Goroka
## 2: 2 Madang Airport Madang
## 3: 3 Mount Hagen Kagamuga Airport Mount Hagen
## 4: 4 Nadzab Airport Nadzab
## 5: 5 Port Moresby Jacksons International Airport Port Moresby
## 6: 6 Wewak International Airport Wewak
## pais iata iacao latitude longitude altitude timezone dst
## 1: Papua New Guinea GKA AYGA -6.081690 145.392 5282 10 U
## 2: Papua New Guinea MAG AYMD -5.207080 145.789 20 10 U
## 3: Papua New Guinea HGU AYMH -5.826790 144.296 5388 10 U
## 4: Papua New Guinea LAE AYNZ -6.569803 146.726 239 10 U
## 5: Papua New Guinea POM AYPY -9.443380 147.220 146 10 U
## 6: Papua New Guinea WWK AYWK -3.583830 143.669 19 10 U
## tz_database_time type source
## 1: Pacific/Port_Moresby airport OurAirports
## 2: Pacific/Port_Moresby airport OurAirports
## 3: Pacific/Port_Moresby airport OurAirports
## 4: Pacific/Port_Moresby airport OurAirports
## 5: Pacific/Port_Moresby airport OurAirports
## 6: Pacific/Port_Moresby airport OurAirportsVamos ver onde estão os aeroportos pelo mundo. O gráfico que faremos não é 100% preciso (pois para isso precisaríamos levar em conta a curvatura da terra), mas para o objetivo do tutorial será suficiente.
ggplot(aeroportos, aes(x = longitude, y = latitude)) + geom_point(size = 0.5) + ggtitle("Aeroportos do Mundo")
Como esperado observamos mais aeroportos nos países ricos, e há também em algumas ilhas perdidas nos oceanos. Para ter erro vamos fazer um gráfico levando em conta a densidade dos pontos
get_density <- function(x, y, ...) {
dens <- MASS::kde2d(x, y, ...)
ix <- findInterval(x, dens$x)
iy <- findInterval(y, dens$y)
ii <- cbind(ix, iy)
return(dens$z[ii])
}
aeroportos[, den := get_density(longitude, latitude)]
ggplot(aeroportos, aes(x = longitude, y = latitude, color = den)) + geom_point(size=0.5)+ scale_color_viridis() + ggtitle("Densidade dos Aeroportos do Mundo")
confirmadas com mais aeroportos nos EUA e Europa e há bastantes aeroportos nas costas dos países. Há poucos em alguns lugares, como em ilhas, o que é razoável, assim como nos pólos norte e sul e no deserto do Saara. Esses esperamos que nosso algoritmo detecte como outliers.
Treinando o algoritmo
Agora faremos o algoritmo de facto, vamos analisar apenas as coordenadas longitude e latitude dos dados.Vamos começar simples usando apenas uma árvore
aeroportos2 <- aeroportos[, .(longitude, latitude)]
floresta <- iForest(aeroportos2, nt = 1, seed = 0)Os argumentos “nt” é o número de árvores que nosso algoritmo usará, e “seed” é a semente aleatória para reprodutibilidade. Analisemos os resultados que nossa floresta deu:
score <- predict(floresta, aeroportos2)
aeroportos2[, score := score]
ggplot(aeroportos2, aes(x = score)) + geom_histogram() + ggtitle("Histograma do Score com 1 Árvore")## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.
Quanto mais próximo de 1 é o score mais provável que o ponto seja um outlier. Para a floresta de isolamento o score é dado por: \[ s(x,n) = 2 ^{-\frac{E(h(x))}{c(n)}}\]
Onde \(h(x)\) é tamanho do caminho até o ponto \(x\), \(c(n)\) é o tamanho médio do caminho que não alcança o ponto na árvore de decisão e \(n\) é número de nós externos. Intuitivamente é \(2\) elevado a menos o tamanho médio do caminho normalizado, quanto maior mais passos na árvore mais próximo de \(0\), quantos menos passos mais próximo de \(1\).
Vamos considerar mais que 0.7 um outlier
aeroportos2[, outlier := score > 0.7]
ggplot(aeroportos2, aes(x = longitude, y = latitude, fill = outlier, col = outlier)) + geom_point(size=0.5)+ ggtitle("Outliers com 1 Árvore")
Com esse corte a árvore separou aeroportos no extremos sul e norte do mundo, assim como bem ao oeste, como outliers, o que já é um bom começo.
Agora vamos checar a convergência da nossa floresta, quanto mais árvores, melhor, mas demorará mais para treinar o modelo, então é interessante achar um número ótimo. Para isso, vamos testar vários números de florestas
fazer_floresta_n_arvores <- function(x){
floresta <- iForest(aeroportos2[, .(longitude, latitude)], nt = x, seed = 0)
predict(floresta, aeroportos2[,.(longitude, latitude)])
}
aeroportos2[, flor_1 := fazer_floresta_n_arvores(1)]
aeroportos2[, flor_10 := fazer_floresta_n_arvores(10)]
aeroportos2[, flor_100 := fazer_floresta_n_arvores(100)]
aeroportos2[, flor_200 := fazer_floresta_n_arvores(200)]
aeroportos2[, flor_500 := fazer_floresta_n_arvores(500)]
aeroportos2[, flor_1000 := fazer_floresta_n_arvores(1000)]
aeroportos2[, flor_2000 := fazer_floresta_n_arvores(2000)]ggpairs(aeroportos2[, .(flor_1, flor_10, flor_100, flor_200, flor_500, flor_1000, flor_2000)])
Com esse gráfico podemos ver que com 100 árvores já o suficiente.
aeroportos2 <- aeroportos[, .(longitude, latitude)]
floresta100 <- iForest(aeroportos2[, .(longitude, latitude)], nt = 100, seed = 0)score <- predict(floresta100, aeroportos2)
aeroportos2[, score := score]
ggplot(aeroportos2, aes(x = score)) + geom_histogram() + ggtitle("Histograma do Score com 100 Árvores")## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.
E vamos considerar outlier os com score do 95 percentil
aeroportos2[, outlier := score > quantile(score, 0.95)]
ggplot(aeroportos2, aes(x = longitude, y = latitude, fill = outlier, col = outlier)) + geom_point(size=0.5)+ ggtitle("Outliers com 100 Árvores")
Os outliers são parecidos com os com apenas uma árvore, somando mais alguns ao leste do mundo.
Comportamento global do algoritmo
Agora vamos ver como o algoritmo se comporta em todo o globo
globo <- data.table(expand.grid(longitude = -200:200, latitude = -100:100))globo[ , score := predict(floresta100, globo[, .(longitude, latitude)])]Vamos normalizar o score para que o grafico fique mais expressivo
globo[, score2 := (score-mean(score))/sd(score)]
aeroportos2[, score2 := (score-mean(score))/sd(score)]ggplot(globo, aes(longitude, latitude, z = score2))+ geom_contour_fill() + scale_fill_divergent() +geom_contour_tanaka() +geom_point(data=aeroportos2, size = 0.5) + theme(legend.position="none") + ggtitle("Comportamento Global da Floresta com 100 Árvores")
Assim podemos ver que as áreas que a floresta escolheu para ser os pontos mais normais são na América do Norte e Europa e subindo para América do Sul e Ásia e depois pra as regiões mais remotas com mais Oceano.
Melhorias
Outro parâmetro que poderíamos tunar é o “phi” que o número de pontos que são escolhidos para criar as árvores de decisão da floresta aleatória.