o problema
Detectar anomalia sempre foi feito pelo avesso. Métodos estatísticos, de classificação e de clusterização constroem um perfil do que é normal e chamam de anomalia tudo que não cabe nele. O paper aponta dois defeitos nisso. O primeiro é conceitual: o detector é otimizado para descrever a maioria, não para encontrar a minoria, então o que ele entrega são sobras — e sobra costuma virar falso alarme em excesso ou anomalia não detectada. O segundo é de custo: métodos baseados em distância e em densidade precisam comparar pontos entre si, e comparação par a par não escala. ORCA, o melhor da época segundo os autores, corta o O(n²) para tempo quase linear com randomização e uma regra de poda; Random Forests em modo não supervisionado exige memória de (2n)² para montar a matriz de proximidade.
Há ainda dois problemas antigos que dado demais agrava. Swamping é quando pontos normais colados na anomalia aumentam o número de partições necessárias para separá-la, e o detector acaba marcando os normais junto. Masking é quando as anomalias formam um cluster grande e denso e escondem umas às outras. Nos dois casos, o sinal se dilui à medida que a amostra cresce.
a ideia
Anomalias são poucas e diferentes. Poucas significa que ocupam pouca área do espaço; diferentes significa que seus valores caem longe dos demais. As duas propriedades juntas dizem que elas são fáceis de separar do resto — e o paper faz disso a medida, em vez de fazer da distância.
Corte o espaço com uma linha aleatória. Corte de novo o lado onde o ponto está. Repita até esse ponto ficar sozinho. Um ponto no meio da massa exige muitos cortes; um ponto isolado no canto sai em poucos. A quantidade de cortes é a profundidade numa árvore, e é isso que vira o escore. Na figura de abertura do paper, um ponto normal precisa de doze partições e um anômalo de quatro; com mil árvores, as médias convergem para 12,82 e 4,02.
A consequência estrutural é o que faz o método ser barato. Como só interessam os caminhos curtos, a parte da árvore que isola os pontos normais não precisa ser construída. O modelo é parcial de propósito.
como funciona
Uma iTree é construída sobre uma sub-amostra de ψ instâncias sorteadas sem reposição:
iTree(X, e, l):
se e >= l ou |X| <= 1: retorna folha{tamanho: |X|}
q <- atributo sorteado
p <- valor sorteado entre min(X[q]) e max(X[q])
retorna nó{ esq: iTree(X[q < p], e+1, l),
dir: iTree(X[q >= p], e+1, l), q, p }O limite de altura é l = ceiling(log2 ψ), aproximadamente a altura média da árvore — mais fundo que isso só há ponto normal, que não interessa. A floresta são t árvores, cada uma com sua sub-amostra. Os padrões do paper: ψ = 256 e t = 100.
Na avaliação, h(x) é o número de arestas percorridas até a folha, somado a um ajuste c(tamanho da folha) que estima a subárvore que não foi construída. O escore é s(x, n) = 2^(−E(h(x))/c(n)), onde c(n) = 2H(n−1) − 2(n−1)/n e H(i) ≈ ln(i) + 0,5772156649 — a profundidade média de uma busca malsucedida em árvore binária de busca, que é exatamente a estrutura equivalente à iTree. Perto de 1, anomalia; bem abaixo de 0,5, normal; tudo em torno de 0,5 significa que a amostra não tem anomalia distinta.
o que isso custou
O paper só trata de atributos contínuos: nominais e binários foram removidos de todas as bases avaliadas. O método também não escapa da maldição da dimensionalidade, e os autores admitem isso; a saída proposta é um seletor de atributos por sub-amostra usando Kurtosis, e mesmo assim a AUC só chega perto do resultado com os atributos originais quando o subespaço escolhido tem tamanho próximo ao número original de atributos.
Aumentar a amostra piora a detecção, o que inverte o reflexo de todo mundo: não dá para melhorar o detector jogando mais dado nele. E o que sai é um ranking, não uma decisão. Onde cortar a lista continua sendo escolha de quem opera — no exemplo do contorno o paper usa s ≥ 0,6 como indicação visual, sem derivar um limiar.
A comparação com ORCA depende de parâmetros que os próprios autores escolheram (k = 5, N = n/8), e eles registram que, com o padrão original de ORCA, toda base acima de mil pontos cai para AUC próxima de 0,5.
onde isso aparece hoje
iForest virou o baseline de detecção de anomalia não supervisionada em bibliotecas de uso geral — scikit-learn traz uma implementação com o mesmo nome e os mesmos dois botões, número de árvores e tamanho da sub-amostra. A razão é operacional antes de ser estatística: o paper já mostrava um modelo com ψ = 256 cabendo em no máximo 511 nós por árvore, o que permite manter o detector em memória ao lado do serviço que ele vigia, em vez de rodar em lote sobre a base inteira. Fraude em transação, tráfego de rede e telemetria — os três exemplos que abrem o artigo — são justamente os casos em que a base é grande, o rótulo é raro e a resposta precisa sair rápido.