Detecção de Outliers: Quartis, Baseada em Distância, Baseada em Densidade

• Aplicar a regra do intervalo interquartil dizendo qual método de quartil usa, e mostrar que dois métodos marcam pontos diferentes no mesmo conjunto.
• Explicar o mascaramento (masking) e mostrar quando as regras de quartil e de z-score ficam cegas.
• Definir outliers baseados em distância e explicar por que uma distância global perde outliers locais.
• Calcular distância de alcançabilidade, densidade local de alcançabilidade e LOF à mão, e conferir com LocalOutlierFactor, inclusive sua convenção de sinal e o tratamento de empates e duplicatas.
• Explicar por que o LOF não tem limiar universal e decidir se um outlier é erro ou é o achado.

density-based-clustering-with-dbscan rotula pontos esparsos como ruído, como efeito colateral do agrupamento. A detecção de outliers faz desses pontos o alvo. Uma definição de Hawkins, citada por Breunig et al. (2000): "An outlier is an observation that deviates so much from other observations as to arouse suspicion that it was generated by a different mechanism." Cada método abaixo transforma esse desvio numa fórmula, e cada fórmula enxerga alguns desvios e perde outros. Marcar um ponto também é só o começo, porque a marca não diz se ele é um registro ruim ou o mais interessante dos dados.

A regra dos quartis, e qual quartil

Com primeiro e terceiro quartis $Q_1,Q_3$ e $\mathrm{IQR}=Q_3-Q_1$, marque $x$ fora de

O fator 1,5 é uma convenção, o coef padrão de boxplot.stats no R. O quartil em si tem várias definições. Para dados ordenados $x_{(1)}\le\dots\le x_{(n)}$, três comuns são:

Hyndman e Fan (1996) compararam as definições comuns, observaram que um mesmo pacote pode usar definições diferentes para quantis e para box plots e recomendaram o estimador não viesado para a mediana (tipo 8). O quantile() do R usa tipo 7 por padrão, enquanto seus box plots usam hinges. Os dois coincidem para $n$ ímpar e diferem para $n$ par. Então diga o método junto com a regra.

Mascaramento

A regra estima a dispersão a partir dos mesmos dados que examina. O mascaramento acontece quando outliers distorcem essa estimativa o bastante para se esconderem. A regra dos quartis resiste até certo ponto: se mais de cerca de um quarto dos dados fica de um lado, $Q_3$ cai entre eles e a cerca passa além deles.

A regra do z-score, $\lvert x-\bar x\rvert/s>3$, é bem mais frágil, e amostras pequenas podem torná-la impossível.

Propriedade. Com o desvio padrão amostral $s$ (divisor $n-1$), $\max_i\lvert x_i-\bar x\rvert/s\le(n-1)/\sqrt n$.

Para $n=10$ a cota é $2{,}846$, atingido por nove valores iguais e um diferente, por mais distante que esteja. A regra com limiar 3 não pode disparar para $n\le10$. Uma alternativa robusta troca média e $s$ pela mediana e pelo desvio absoluto mediano (MAD), que resistem até cerca de metade dos dados.

Outliers baseados em distância

Knorr e Ng (1998) definem outliers baseados em distância, e Breunig et al. reenunciam a definição: $p$ é um $DB(pct,dmin)$-outlier se pelo menos a porcentagem $pct$ dos objetos de $D$ está a mais de $dmin$ dele, isto é, se $\{q\in D\mid d(p,q)\le dmin\}$, que contém o próprio $p$, tem no máximo $(100-pct)\%$ do tamanho de $D$. Ramaswamy et al. (2000) ordenam os pontos pela distância ao $k$-ésimo vizinho mais próximo e reportam os primeiros. Ambos usam uma escala global. Breunig et al. mostram a falha: tome um cluster denso ao lado de um esparso, e um ponto mais perto do denso do que os pontos do esparso estão de seus vizinhos mais próximos. Então nenhum $(pct,dmin)$ marca esse ponto sem marcar também muitos pontos do cluster esparso.

LOF

Breunig et al. comparam a densidade de um ponto com a de seus vizinhos. Fixe MinPts, aqui $k$, e exclua $p$ das próprias contagens de vizinhos.

• $k\text{-distance}(p)$: a distância de $p$ ao seu $k$-ésimo vizinho mais próximo.
• $N_k(p)$: todos os objetos, exceto $p$, a até $k$-distance de $p$. Com empates, $\lvert N_k(p)\rvert$ pode passar de $k$.
• Distância de alcançabilidade: $\text{reach-dist}_k(p,o)=\max\{k\text{-distance}(o),\,d(p,o)\}$. Ela suaviza as distâncias a vizinhos muito próximos.
• Densidade local de alcançabilidade e o fator:

Propriedade (Breunig et al., Lema 1). Seja $C$ um conjunto de objetos e $\varepsilon=\text{reach-dist-max}/\text{reach-dist-min}-1$ sobre $C$. Se $p\in C$, todos os $k$ vizinhos mais próximos $q$ de $p$ estão em $C$, e todos os $k$ vizinhos mais próximos desses $q$ estão em $C$, então $1/(1+\varepsilon)\le\mathrm{LOF}(p)\le1+\varepsilon$. Assim, objetos no interior de um cluster compacto ficam perto de 1. O lema não diz nada sobre um ponto fora de $C$: o Teorema 1 do artigo dá cotas separadas para qualquer objeto.

As convenções do scikit-learn

• n_neighbors é $k$ e exclui o ponto. O min_samples do DBSCAN, ao contrário, o inclui.
• negative_outlier_factor_ é $-\mathrm{LOF}$: maior significa mais normal.
• fit_predict devolve $-1$ para outliers e $+1$ para inliers, comparando com offset_.
• Com contamination='auto', offset_ é $-1{,}5$, então o corte é $\mathrm{LOF}>1{,}5$. Com um float, offset_ é um percentil dos escores, ou seja, você mesmo fixa a fração de outliers.
• Ele usa exatamente $k$ vizinhos, então não mantém os empates como $N_k(p)$ mantém.
• Ele soma $10^{-10}$ à distância média de alcançabilidade, o que evita divisão por zero.
• Com novelty=False, o padrão, só existem escores de treino: score_samples e decision_function não estão disponíveis. Com novelty=True, ele pontua dados novos e fit_predict não está disponível. É nesse modo que um limiar ajustado no treino é aplicado ao teste sem vazamento.

Erro ou achado?

Uma marca estatística não decide isso. Verifique a procedência do registro: o valor é impossível (idade negativa, um sentinela como $-999$), um erro de unidade, uma carga duplicada? Nesse caso é erro: corrija ou descarte, e diga que fez isso. Se o valor é possível, mantenha-o e procure um mecanismo, porque ele pode ser o achado: Breunig et al. relatam que seu outlier mais forte no futebol era o artilheiro da liga. Na dúvida, reporte os resultados com e sem ele. O Exemplo 1 mostra por quê: tirar o 57 move a média de $27{,}22$ para $23{,}5$ e a mediana de $24$ para $23{,}5$.

Exemplo 1: mesmos dados, marcas diferentes

Tome $11,17,21,23,24,25,27,40,57$ ($n=9$), rodado no NumPy 2.5.

text
método                 Q1      Q3      IQR     inferior superior marcados
linear (tipo 7)        21      27       6.0    12       36       11 40 57
hinges de Tukey        21      27       6.0    12       36       11 40 57
median_unbiased (8)    19.67   31.33   11.67    2.17    48.83    57
weibull (tipo 6)       19      33.5    14.5    -2.75    55.25    57

No tipo 7 as posições são 3 e 7, então $Q_1=x_{(3)}$ e $Q_3=x_{(7)}$. No tipo 6 são $2{,}5$ e $7{,}5$, então $Q_1=(17+21)/2$ e $Q_3=(27+40)/2$. Os pontos 11 e 40 são outliers numa definição e normais em outra. Com $n$ ímpar, hinges coincidem com o tipo 7. Acrescentar 31 faz $n=10$, e eles diferem: $(21{,}5;\ 30)$ no tipo 7 e $(21;\ 31)$ nas hinges.

Exemplo 2: mascaramento

Tome $10,11,\dots,18$ e acrescente $m$ valores altos $95,96,\dots$, usando o tipo 7.

text
m   n    Q1      Q3      cerca sup.    regra IQR marca  z máx   regra MAD marca
1   10   12.25   16.75    23.5         95               2.832   95
2   11   12.5    17.5     25.0         95 96            2.032   95 96
3   12   12.75   37.25    74.0         95 96 97         1.682   95 96 97
4   13   13.0    95.0    218.0         nada             1.476   95 a 98
5   14   13.25   95.75   219.5         nada             1.339   95 a 99

Em $m=4$, 31% dos dados, $Q_3$ é ele próprio um outlier, então a regra não marca nada. A regra do z-score com limiar 3 nunca dispara, nem em $m=1$, onde $n=10$ a torna impossível. A coluna MAD marca $\lvert x-\mathrm{med}\rvert/(1{,}4826\,\mathrm{MAD})>3{,}5$, e ela marca todos os valores plantados em cada linha.

Exemplo 3: LOF à mão

Pontos numa reta, com $k=2$ e sem distâncias empatadas:

text
A=0  B=1  C=3  D=4.5  E=11

text
p   N2(p)   k-dist   reach-dist a cada vizinho      lrd      LOF
A   B C     3        2 (B), 3 (C)                   0.4      0.9545
B   A C     2        3 (A), 2 (C)                   0.4      0.9545
C   D B     2        3.5 (D), 2 (B)                 0.3636   1.05
D   C B     3.5      2 (C), 3.5 (B)                 0.3636   1.05
E   D C     8        6.5 (D), 8 (C)                 0.1379   2.6364

Acompanhe $E$. Seus vizinhos são $D$ a 6,5 e $C$ a 8. Então $\text{reach-dist}(E,D)=\max\{3{,}5;\ 6{,}5\}=6{,}5$ e $\text{reach-dist}(E,C)=\max\{2;\ 8\}=8$, logo $\mathrm{lrd}(E)=1/7{,}25=0{,}1379$. Depois $\mathrm{LOF}(E)=\tfrac12(0{,}3636+0{,}3636)/0{,}1379=2{,}6364$.

O Lema 1 se aplica a $C=\{A,B,C,D\}$: as distâncias de alcançabilidade vão de 2 a 4,5, então $\varepsilon=1{,}25$ e as cotas são $0{,}444$ e $2{,}25$. Os quatro pontos cabem. $E$, fora do conjunto, fica em $2{,}6364$, acima da cota.

Exemplo 4: conferindo com o scikit-learn

LocalOutlierFactor(n_neighbors=2).fit(X) dá

text
negative_outlier_factor_  [-0.9545 -0.9545 -1.05 -1.05 -2.6364]
offset_ -1.5     fit_predict  [ 1  1  1  1 -1]

A maior diferença em relação aos valores à mão é $6\times10^{-11}$, efeito do termo $10^{-10}$. Ajustado com novelty=True em $A$ a $D$, $E$ recebe score_samples $-2{,}6364$ e decision_function $-1{,}1364$ (o escore menos offset_).

Empates mudam o resultado. Para $(0,0),(1,0),(-1,0),(0,1),(3,0),(3{,}5;\ 1)$ com $k=2$, a origem tem três vizinhos à distância 1. Uma implementação do $N_k$ do artigo mantém os três e lhe dá $1{,}1504$, enquanto o scikit-learn mantém dois e dá $1{,}1716$.

Exemplo 5: duplicatas

O artigo supõe que não há duplicatas. Ele observa que $\mathrm{lrd}$ é infinita quando $p$ tem pelo menos MinPts duplicatas, e sugere uma vizinhança baseada em coordenadas distintas. No scikit-learn, para $0;\ 0;\ 0;\ 1;\ 2{,}5;\ 4{,}5$ com n_neighbors=2:

text
negative_outlier_factor_  [-1 -1 -1 -1e+10 -1.7045 -1.925]
UserWarning: Duplicate values are leading to incorrect results. ...

As cópias recebem $\mathrm{lrd}=10^{10}$, só por causa do termo $10^{-10}$, então o ponto em 1 fica com $10^{10}$, número sem significado. Com duas cópias de 0 em vez de três, ou com n_neighbors=3, todos os escores são finitos e o ponto em 1 fica com 1. Remova duplicatas ou aumente n_neighbors antes de ler o LOF em dados com repetições.

Exemplo 6: distância global perde um outlier local

Este conjunto não vem do artigo, embora siga a ideia de sua Figura 1. Com um só rng = numpy.random.default_rng(3), sorteie nesta ordem rng.normal([0, 0], 1.0, (400, 2)) e rng.normal([10, 0], 0.1, (100, 2)), depois acrescente $o_1=(0,9)$ e $o_2=(10,1)$, num total de 502 objetos. Com $k=10$, a coluna de distância exclui o próprio ponto:

text
              posição de o1  posição de o2  escore o1  escore o2
dist. 10-NN   1              18             6.98       0.86
LOF           2              1              8.48       8.87

Dezesseis pontos do cluster esparso ficam acima de $o_2$ pela distância, enquanto o LOF o coloca em primeiro. Com $pct=99$, um objeto é marcado quando no máximo 5 dos 502 objetos, ele incluído, estão a até $dmin$. Isso marca $o_2$ em $dmin=0{,}5$ junto com 34 pontos do cluster esparso, ainda o marca em $dmin=0{,}8$ junto com 10, e o perde a partir de $dmin=0{,}829$. Aqui $o_2$ está a 0,71 do cluster denso, mais longe do que 99% dos pontos esparsos estão de seu vizinho mais próximo, então a condição do artigo não vale e o dano é parcial, mas nunca some: numa grade de passo 0,001, todo $dmin$ que marca $o_2$ marca também pelo menos 7 pontos esparsos.

Exemplo 7: não há limiar universal

O artigo nunca fixa um corte para o LOF. Ele propõe ordenar pelo LOF máximo numa faixa de MinPts, com cota inferior de pelo menos 10. Seus experimentos mostram escores máximos de 2,4 e 6,0 em dois testes com dados de hóquei, e ele discute jogadores de futebol com LOF acima de 1,5 como uma escolha para aquele conjunto. A documentação do scikit-learn diz que 'auto' segue o artigo original, mas no artigo o 1,5 só aparece como corte para relatar os resultados do futebol. Em 500 pontos de rng = numpy.random.default_rng(5), sem outliers plantados, sorteados como rng.normal(0, 1, (500, 2)) e depois rng.random((500, 2)):

text
dados              k=5    k=10   k=20   k=50
Gaussiana: LOF>1.5 11     10     15     24
Gaussiana: máx     2.355  2.111  2.100  2.260
Uniforme:  LOF>1.5 3      0      0      0
Uniforme:  máx     1.561  1.315  1.359  1.342

O mesmo corte marca até 4,8% de uma gaussiana comum, e a contagem muda com $k$. Leia o LOF como uma ordenação, e escolha o corte pelo custo de revisar cada marca.

• "Três sigmas sempre pegam valores extremos." Isso não pode disparar para $n\le10$ com o desvio padrão amostral.
• "LOF acima de 1 significa outlier." Valores perto de 1 são normais, e não há corte fixo.
• "Marcado significa apagar." A média do Exemplo 1 se move 3,7 por causa de um ponto. Removê-lo exige um motivo vindo da origem dos dados.

A regra dos quartis depende da definição de quartil e falha quando os outliers de um lado passam de cerca de um quarto dos dados, e a regra do z-score pode falhar bem antes. Regras baseadas em distância usam uma escala global, então perdem pontos que só são atípicos em relação a uma vizinhança densa. O LOF compara densidades locais por meio da distância de alcançabilidade, com valores perto de 1 dentro de clusters compactos. O escore do scikit-learn é $-\mathrm{LOF}$, usa exatamente $k$ vizinhos sem contar o ponto e pede cuidado com empates e duplicatas. Nenhum limiar é universal, e só a origem dos dados decide entre erro e achado.