Floresta de isolamento - Isolation forest

A floresta de isolamento é o primeiro algoritmo de detecção de anomalias que identifica anomalias usando o isolamento. Foi inicialmente proposto e desenvolvido por Fei Tony Liu, Kai Ming Ting e Zhi-Hua Zhou em 2008. A importância desta pesquisa reside em seu desvio da filosofia dominante subjacente aos detectores de anomalias existentes na época, onde instâncias normais são perfiladas antes das anomalias são identificados como instâncias que não estão em conformidade. A floresta de isolamento apresenta um método fundamentalmente diferente que isola explicitamente as anomalias usando árvores binárias, demonstrando a nova possibilidade de um detector de anomalias rápido que visa diretamente as anomalias sem o processo intensivo de recursos de criação de perfil de instância normal. O algoritmo possui uma complexidade de tempo linear com uma constante baixa e um baixo requisito de memória, que funciona bem em problemas dimensionais altos que possuem um grande número de atributos irrelevantes e em situações onde o conjunto de treinamento não contém nenhuma anomalia.

Fig. 1 - exemplo de tráfego da web com pontos potencialmente anômalos.

Em estatística , uma anomalia (também conhecida como outlier ) é uma observação ou evento que se desvia tanto de outros eventos para levantar suspeitas de que foi gerado por um meio diferente. Por exemplo, o gráfico da Fig.1 representa o tráfego de entrada para um servidor web, expresso como o número de solicitações em intervalos de 3 horas, por um período de um mês. É bastante evidente, simplesmente olhando para a imagem, que alguns pontos (marcados com um círculo vermelho) estão anormalmente altos, a ponto de induzir a suspeita de que o servidor web pode estar sob ataque naquele momento. Por outro lado, o segmento plano indicado pela seta vermelha também parece incomum e pode ser um sinal de que o servidor esteve inativo durante esse período.

As anomalias em um grande conjunto de dados podem seguir padrões muito complicados, que são difíceis de detectar visualmente na grande maioria dos casos. Esta é a razão pela qual o campo de detecção de anomalias é adequado para a aplicação de técnicas de aprendizado de máquina .

As técnicas mais comuns empregadas para detecção de anomalias baseiam-se na construção de um perfil do que é “normal”: as anomalias são relatadas como aquelas instâncias no conjunto de dados que não estão em conformidade com o perfil normal. Isolation Forest usa uma abordagem diferente: em vez de tentar construir um modelo de instâncias normais, ela isola explicitamente pontos anômalos no conjunto de dados. A principal vantagem dessa abordagem é a possibilidade de explorar as técnicas de amostragem em uma extensão que não é permitida nos métodos baseados em perfis, criando um algoritmo muito rápido e com baixa demanda de memória.

História

O algoritmo Isolation Forest (iForest) foi inicialmente proposto por Fei Tony Liu, Kai Ming Ting e Zhi-Hua Zhou em 2008. Os autores tiraram vantagem de duas propriedades quantitativas de pontos de dados anômalos em uma amostra:

Poucos - eles são a minoria consistindo em menos instâncias e
Diferentes - eles têm valores de atributos que são muito diferentes daqueles de instâncias normais

Uma vez que as anomalias são "poucas e diferentes", são mais fáceis de "isolar" em comparação com os pontos normais. Isolation Forest constrói um conjunto de “Árvores de Isolamento” (iTrees) para o conjunto de dados, e anomalias são os pontos que têm comprimentos médios de caminho mais curtos no iTrees.

Em um artigo posterior, publicado em 2012, os mesmos autores descreveram um conjunto de experimentos para provar que o iForest:

tem uma baixa complexidade de tempo linear e um pequeno requisito de memória
é capaz de lidar com dados dimensionais elevados com atributos irrelevantes
pode ser treinado com ou sem anomalias no conjunto de treinamento
pode fornecer resultados de detecção com diferentes níveis de granularidade sem novo treinamento

Em 2013, Zhiguo Ding e Minrui Fei propuseram uma estrutura baseada em iForest para resolver o problema de detecção de anomalias em dados de streaming. Mais aplicações do iForest para streaming de dados são descritas nos artigos de Tan et al., Susto et al. e Weng et al.

Um dos principais problemas da aplicação do iForest para detecção de anomalias não estava no modelo em si, mas sim na forma como o “score de anomalia” era calculado. Este problema foi destacado por Sahand Hariri, Matias Carrasco Kind e Robert J. Brunner em um artigo de 2018, em que eles propuseram um modelo iForest aprimorado denominado Extended Isolation Forest (EIF). No mesmo artigo, os autores descrevem as melhorias feitas no modelo original e como elas são capazes de aumentar a consistência e a confiabilidade da pontuação de anomalia produzida para um determinado ponto de dados.

Algoritmo

Fig. 2 - um exemplo de isolamento de um ponto não anômalo em uma distribuição gaussiana 2D.

Com base no algoritmo Isolation Forest, existe a tendência de instâncias anômalas em um conjunto de dados serem mais fáceis de separar do resto da amostra (isolar), em comparação com pontos normais. Para isolar um ponto de dados, o algoritmo gera recursivamente partições na amostra ao selecionar aleatoriamente um atributo e, em seguida, selecionar aleatoriamente um valor de divisão para o atributo, entre os valores mínimo e máximo permitidos para aquele atributo.

Fig. 3 - um exemplo de isolamento de um ponto anômalo em uma distribuição gaussiana 2D.

Um exemplo de particionamento aleatório em um conjunto de dados 2D de pontos normalmente distribuídos é dado na Fig. 2 para um ponto não anômalo e na Fig. 3 para um ponto que é mais provável de ser uma anomalia. É evidente a partir das imagens como as anomalias requerem menos partições aleatórias para serem isoladas, em comparação com os pontos normais.

Do ponto de vista matemático, o particionamento recursivo pode ser representado por uma estrutura de árvore chamada Isolation Tree , enquanto o número de partições necessárias para isolar um ponto pode ser interpretado como o comprimento do caminho, dentro da árvore, para chegar a um nó de terminação começando da raiz. Por exemplo, o comprimento do caminho do ponto na Fig. 2 é maior do que o comprimento do caminho da Fig. 3. ${\ displaystyle x_ {i}}$ ${\ displaystyle x_ {j}}$

Mais formalmente, seja um conjunto de pontos d-dimensionais e . Uma árvore de isolamento (iTree) é definida como uma estrutura de dados com as seguintes propriedades: ${\ displaystyle X = \ {x_ {1}, \ dots, x_ {n} \}}$ ${\ displaystyle X '\ subconjunto X}$

para cada nó na Árvore, é um nó externo sem filho ou um nó interno com um "teste" e exatamente dois nós filhos ( e ) ${\ displaystyle T}$ ${\ displaystyle T}$ ${\ displaystyle T_ {l}}$ ${\ displaystyle T_ {r}}$
um teste no nó consiste em um atributo e um valor de divisão de forma que o teste determine a passagem de um ponto de dados para ou . ${\ displaystyle T}$ ${\ displaystyle q}$ ${\ displaystyle p}$ ${\ displaystyle q <p}$ ${\ displaystyle T_ {l}}$ ${\ displaystyle T_ {r}}$

Para construir um iTree, o algoritmo divide recursivamente , selecionando aleatoriamente um atributo e um valor de divisão , até que ${\ displaystyle X '}$ ${\ displaystyle q}$ ${\ displaystyle p}$

o nó tem apenas uma instância, ou
todos os dados no nó têm os mesmos valores.

Quando o iTree está totalmente desenvolvido, cada ponto é isolado em um dos nós externos. Intuitivamente, os pontos anômalos são aqueles (mais fáceis de isolar, portanto) com o menor comprimento do caminho na árvore, onde o comprimento do caminho do ponto é definido como o número de arestas que atravessa do nó raiz para chegar a um nó externo. ${\ displaystyle X}$ ${\ displaystyle h (x_ {i})}$ ${\ displaystyle x_ {i} \ in X}$ ${\ displaystyle x_ {i}}$

Uma explicação probabilística de iTree é fornecida no artigo original do iForest.

Propriedades da floresta de isolamento

Sub-amostragem : desde iForest não precisa isolar todos os casos normais, pode frequentemente ignorar a grande maioria da amostra de treinamento. Como consequência, o iForest funciona muito bem quando o tamanho da amostra é mantido pequeno, uma propriedade que está em contraste com a grande maioria dos métodos existentes, onde o tamanho da amostra grande é geralmente desejável.
Swamping : quando as instâncias normais estão muito próximas de anomalias, o número de partições necessárias para separar as anomalias aumenta, um fenômeno conhecido como swamping , que torna mais difícil para o iForest discriminar entre anomalias e pontos normais. Um dos principais motivos do alagamento é a presença de muitos dados para fins de detecção de anomalias, o que implica que uma possível solução para o problema seja a subamostragem. Visto que o iForest responde muito bem à subamostragem em termos de desempenho, a redução do número de pontos na amostra também é uma boa maneira de reduzir o efeito do alagamento.
Mascaramento : quando o número de anomalias é alto é possível que algumas delas se agreguem em um aglomerado denso e grande, dificultando a separação das anomalias isoladas e, por sua vez, a detecção de pontos como anômalos. Da mesma forma que o alagamento, esse fenômeno (conhecido como “ mascaramento ”) também é mais provável quando o número de pontos na amostra é grande e pode ser amenizado por meio de subamostragem.
Dados de alta dimensão : uma das principais limitações dos métodos padrão baseados em distância é sua ineficiência em lidar com conjuntos de dados de alta dimensão :. A principal razão para isso é que, em um espaço de alta dimensão, cada ponto é igualmente esparso, então usar uma medida de separação baseada na distância é bastante ineficaz. Infelizmente, os dados de alta dimensão também afetam o desempenho de detecção do iForest, mas o desempenho pode ser amplamente melhorado com a adição de um teste de seleção de recursos como a curtose para reduzir a dimensionalidade do espaço de amostra.
Somente instâncias normais : o iForest tem um bom desempenho, mesmo se o conjunto de treinamento não contiver nenhum ponto anômalo, o motivo é que o iForest descreve as distribuições de dados de forma que altos valores do comprimento do caminho correspondam à presença de pontos de dados. Como consequência, a presença de anomalias é bastante irrelevante para o desempenho de detecção do iForest. ${\ displaystyle h (x_ {i})}$

Detecção de anomalias com floresta de isolamento

A detecção de anomalias com a floresta de isolamento é um processo composto por duas etapas principais:

no primeiro estágio, um conjunto de dados de treinamento é usado para construir o iTrees conforme descrito nas seções anteriores.
no segundo estágio, cada instância no conjunto de teste é passada pelo build do iTrees no estágio anterior, e uma "pontuação de anomalia" adequada é atribuída à instância usando o algoritmo descrito abaixo

Uma vez que todas as instâncias no conjunto de teste tenham sido atribuídas a uma pontuação de anomalia, é possível marcar como “anomalia” qualquer ponto cuja pontuação seja maior do que um limite predefinido, que depende do domínio ao qual a análise está sendo aplicada.

Pontuação de anomalia

O algoritmo para calcular a pontuação de anomalia de um ponto de dados é baseado na observação de que a estrutura do iTrees é equivalente à das Árvores de Busca Binárias (BST): uma terminação em um nó externo do iTree corresponde a uma busca malsucedida no BST . Como consequência, a estimativa da média para terminações de nós externos é a mesma das pesquisas sem sucesso no BST, ou seja, ${\ displaystyle h (x)}$

${\ displaystyle c (m) = {\ begin {cases} 2H (m-1) - {\ frac {2 (m-1)} {n}} & {\ text {for}} m> 2 \\ 1 & {\ text {for}} m = 2 \\ 0 & {\ text {caso contrário}} \ end {cases}}}$

onde é o tamanho dos dados de teste, é o tamanho do conjunto de amostra e é o número harmônico, que pode ser estimado por , onde é a constante de Euler-Mascheroni . ${\ displaystyle n}$ ${\ displaystyle m}$ ${\ displaystyle H}$ ${\ displaystyle H (i) = ln (i) + \ gamma}$ ${\ displaystyle \ gamma = 0,5772156649}$

O valor de c (m) acima representa a média de dado , então podemos usá-lo para normalizar e obter uma estimativa da pontuação da anomalia para uma determinada instância x: ${\ displaystyle h (x)}$ ${\ displaystyle m}$ ${\ displaystyle h (x)}$

${\ displaystyle s (x, m) = 2 ^ {\ frac {-E (h (x))} {c (m)}}}$

onde é o valor médio de de uma coleção de iTrees. É interessante notar que, para qualquer instância : ${\ displaystyle E (h (x))}$ ${\ displaystyle h (x)}$ ${\ displaystyle x}$

se está próximo de então é muito provável que seja uma anomalia ${\ displaystyle s}$ ${\ displaystyle 1}$ ${\ displaystyle x}$
se for menor que então é provável que seja um valor normal ${\ displaystyle s}$ ${\ displaystyle 0,5}$ ${\ displaystyle x}$
se para uma determinada amostra todas as instâncias são atribuídas a uma pontuação de anomalia de cerca , então é seguro assumir que a amostra não tem nenhuma anomalia ${\ displaystyle 0,5}$

Floresta de isolamento estendido

Conforme descrito nas seções anteriores, o algoritmo Isolation Forest tem um desempenho muito bom tanto do ponto de vista computacional quanto do consumo de memória. O principal problema com o algoritmo original é que a maneira como a ramificação das árvores ocorre introduz um viés, o que provavelmente reduzirá a confiabilidade dos escores de anomalias para classificar os dados. Esta é a principal motivação por trás da introdução do algoritmo Extended Isolation Forest (EIF) por Hariri et al.

Fig. 4 - pontos bidimensionais normalmente distribuídos com média zero e matriz de covariância unitária

Para entender por que a Floresta de Isolamento original sofre desse viés, os autores fornecem um exemplo prático baseado em um conjunto de dados aleatório retirado de uma distribuição normal 2-D com média zero e covariância dada pela matriz de identidade. Um exemplo de tal conjunto de dados é mostrado na Fig. 4.

É fácil entender, olhando para a imagem, que os pontos que caem perto de (0, 0) são provavelmente pontos normais, enquanto um ponto que está longe de (0, 0) é provavelmente anômalo. Como consequência, a pontuação de anomalia de um ponto deve aumentar com um padrão quase circular e simétrico conforme o ponto se move radialmente para fora do “centro” da distribuição. Este não é o caso na prática, como os autores demonstram ao gerar o mapa de pontuação de anomalia produzido para a distribuição pelo algoritmo Isolation Forest. Embora as pontuações de anomalia aumentem corretamente à medida que os pontos se movem radialmente para fora, eles também geram regiões retangulares de pontuação de anomalia inferior nas direções xey, em comparação com outros pontos que caem aproximadamente na mesma distância radial do centro.

Fig. 5 - particionamento aleatório com EIF

É possível demonstrar que essas regiões retangulares inesperadas no mapa de pontuação de anomalia são de fato um artefato introduzido pelo algoritmo e se devem principalmente ao fato de que os limites de decisão da Floresta de Isolamento são limitados a serem verticais ou horizontais (ver Fig. 2 e Fig. 3).

Esta é a razão pela qual em seu artigo, Hariri et al. propõem melhorar a Floresta de Isolamento original da seguinte maneira: em vez de selecionar uma característica e valor aleatórios dentro da faixa de dados, eles selecionam um corte de galho que tem uma “inclinação” aleatória. Um exemplo de particionamento aleatório com EIF é mostrado na Fig. 5.

Os autores mostram como a nova abordagem é capaz de superar os limites da Floresta de Isolamento original, levando a um mapa de pontuação de anomalia aprimorado.

Implementações de código aberto

Implementação original:

Isolamento Floresta , um algoritmo que detecta dados-anomalias usando árvores binárias escritos em R . Lançado pelo primeiro autor do jornal, Liu, Fei Tony em 2009.

Outras implementações (em ordem alfabética):

EIF - Uma implementação de Floresta de Isolamento Estendido para Detecção de Anomalias por Sahand Hariri .
Extended Isolation Forest by H2O-3 - Uma implementação de Extended Isolation Forest for Anomaly Detection by H2O-3.
Isolation Forest - Uma implementação Spark / Scala, criada por James Verbus da equipe de AI Anti-Abuse do LinkedIn.
Isolation Forest by H2O-3 - Uma implementação de Isolation Forest for Anomaly Detection by H2O-3.
Implementação do pacote solitude em R por Srikanth Komala Sheshachala .
Implementação de Python com exemplos em scikit-learn .
Spark iForest - Uma implementação distribuída em Scala e Python, que é executada no Apache Spark . Escrito por Yang, Fangzhou .

Languages

In other projects