Local Outlier Factor (LOF)
- Proposto por
- Breunig, M. M.; Kriegel, H.-P.; Ng, R. T.; Sander, J.
- Ano
- 2000
- Tipo
- Density-based anomaly detection (unsupervised)
Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês
O que ele faz?
Local Outlier Factor (LOF) é um algoritmo de detecção de anomalias não supervisionado e baseado em densidade, introduzido por Breunig, Kriegel, Ng e Sander em 2000.
Ele atribui a cada ponto de dados uma pontuação de outlier contínua que quantifica o quão isolado esse ponto está em relação à sua vizinhança local, permitindo a detecção de anomalias que métodos globais perdem porque elas se misturam a agrupamentos densos em outras partes do espaço.
A intuição por trás do método
Imagine um mapa de cidade onde a maioria das pessoas vive em distritos urbanos densos. Uma casa isolada no campo é obviamente isolada. Mas o LOF vai além: ele também pode sinalizar uma casa que fica em um subúrbio moderadamente denso quando todos os seus vizinhos imediatos estão agrupados em um agrupamento ainda mais denso. Em vez de perguntar 'este ponto está longe de tudo?', o LOF pergunta 'a vizinhança deste ponto é muito mais esparsa do que as vizinhanças de seus próprios vizinhos?' Um ponto cujos vizinhos vivem todos mais juntos do que o próprio ponto recebe uma alta pontuação LOF — sinalizando que é um outlier local, mesmo que globalmente não esteja em uma região vazia.
História
O LOF foi introduzido por Markus Breunig, Hans-Peter Kriegel, Raymond Ng e Jörg Sander na conferência ACM SIGMOD 2000. Ele abordou uma limitação reconhecida dos métodos de outlier existentes — que eles dependiam de limiares de distância globais e, portanto, confundiam anomalias locais com pontos normais em regiões menos densas. O artigo introduziu o conceito de densidade local de alcançabilidade e a pontuação LOF, que rapidamente se tornou uma referência fundamental em detecção de anomalias. Desde então, foi estendido por inúmeras variantes, incluindo LoOP (probabilidades de outlier local), LOCI e COF, e está incluído nas principais bibliotecas de aprendizado de máquina. O artigo da ACM SIGMOD 2000 acumulou milhares de citações e é tratado como um dos trabalhos fundamentais em mineração de dados baseada em densidade.
Quando usar
O LOF é apropriado quando se espera que anomalias ocorram em agrupamentos de densidade variável e quando um limiar de distância global perderia outliers escondidos em regiões esparsas ou sinalizaria incorretamente pontos em agrupamentos legitimamente esparsos, mas consistentes. Ele funciona em qualquer espaço de características contínuas com uma métrica de distância significativa e não requer exemplos de anomalias rotulados (totalmente não supervisionado). Ele se adequa a aplicações como detecção de fraudes, detecção de intrusão em redes, controle de qualidade de fabricação e triagem de anomalias médicas. As principais suposições são que os inliers formam vizinhanças locais razoavelmente coesas e que distâncias par a par significativas podem ser calculadas. O LOF tem melhor desempenho quando n é pelo menos dezenas a poucas centenas; para dados de alta dimensionalidade (a maldição da dimensionalidade), as distâncias se tornam menos discriminativas e a redução de dimensionalidade ou seleção de características é aconselhável primeiro.
Limitações e considerações
- Complexidade de tempo quadrática na implementação ingênua o torna lento em grandes conjuntos de dados sem indexação de vizinhos mais próximos aproximados.
- Sensível à escolha de k: um k muito pequeno produz pontuações ruidosas; um k muito grande borra a estrutura local.
- O desempenho degrada em espaços de muito alta dimensionalidade devido à maldição da dimensionalidade.
- Não escala naturalmente para dados de streaming ou online sem recálculo.
- Não fornece um modelo que possa ser aplicado diretamente para pontuar novos pontos sem acesso ao conjunto de treinamento.
As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.
Pontos fortes
- Detecta outliers locais em conjuntos de dados com agrupamentos de densidade variável, onde métodos globais falham.
- Produz uma pontuação contínua e interpretável em vez de um rótulo binário rígido, permitindo escolha flexível de limiar.
- Totalmente não supervisionado: nenhum dado de anomalia rotulado é necessário.
- Aplicável a qualquer espaço de características com uma métrica de distância computável, incluindo distâncias não euclidianas.
- Robusto à escala de características individuais quando as distâncias são calculadas em dados padronizados.
Aplicações
- Detecção de fraudes em transações financeiras onde a atividade fraudulenta cria padrões localmente esparsos.
- Detecção de intrusão em redes, sinalizando registros de tráfego cujo vizinhança local é muito mais esparsa do que seus arredores.
- Controle de qualidade de fabricação para identificar itens defeituosos em dados de produção ricos em sensores.
- Triagem de anomalias médicas — detectando perfis de pacientes incomuns em relação a coortes de pacientes semelhantes.
- Detecção de anomalias espaciais em dados geográficos e ambientais com densidade heterogênea.
Como funciona
Como funciona
Para cada ponto p, o algoritmo primeiro calcula a k-distância: a distância até o k-ésimo vizinho mais próximo de p. Isso define o alcance da vizinhança local de p. Todos os pontos dentro dessa distância formam a k-vizinhança N_k(p). A escolha de k controla a escala na qual a localidade é avaliada — um k pequeno captura a estrutura local granular, um k maior a suaviza.
Fórmula
k\text{-dist}(p) = \text{distance to the } k\text{-th nearest neighbor of } pA distância de alcançabilidade de p para um vizinho o é definida como o máximo da k-distância de o e a distância Euclidiana real (ou outra métrica) entre p e o. Essa suavização evita instabilidade quando dois pontos estão extremamente próximos um do outro: ela substitui distâncias minúsculas pela pegada mais ampla da própria vizinhança de o, tornando as estimativas de densidade mais robustas.
Fórmula
\text{reach-dist}_k(p, o) = \max\{k\text{-dist}(o),\, d(p, o)\}A densidade local de alcançabilidade de p (lrd) é o inverso da distância média de alcançabilidade de p a todos os seus k vizinhos. Um ponto cercado por vizinhos densamente agrupados tem uma pequena distância média de alcançabilidade e, portanto, um lrd alto. Um ponto em uma região esparsa tem uma grande distância média de alcançabilidade e um lrd baixo.
Fórmula
\text{lrd}_k(p) = \left(\frac{\sum_{o \in N_k(p)} \text{reach-dist}_k(p,o)}{|N_k(p)|}\right)^{-1}A pontuação LOF de p é a razão média dos valores de lrd de seus vizinhos para o próprio lrd de p. Se os vizinhos de p tiverem todos lrd substancialmente maiores do que o próprio p — significando que eles vivem em sub-regiões mais densas — a razão excede 1, indicando que p é um outlier local. Uma pontuação próxima a 1 indica que p tem aproximadamente a mesma densidade que seus arredores. Pontuações muito maiores que 1 sinalizam pontos cada vez mais anômalos. Essa comparação consciente da localidade é o que distingue o LOF de métodos baseados apenas em distância.
Fórmula
\text{LOF}_k(p) = \frac{\sum_{o \in N_k(p)} \frac{\text{lrd}_k(o)}{\text{lrd}_k(p)}}{|N_k(p)|}Erros comuns
- Esquecer de padronizar ou normalizar características antes de calcular distâncias, fazendo com que características de alta variância dominem.
- Usar um único valor de k sem análise de sensibilidade; a melhor prática é avaliar vários valores de k.
- Tratar a pontuação LOF como uma probabilidade — é uma medida relativa sem interpretação probabilística fixa.
- Ignorar a maldição da dimensionalidade em dados de alta dimensionalidade e esperar que o LOF funcione sem redução de dimensionalidade prévia.
- Definir um limiar LOF arbitrário (por exemplo, pontuação > 1.5) sem inspecionar a distribuição de pontuações para o conjunto de dados específico.
Perguntas frequentes
Como escolho o valor correto de k?
Não existe um k universalmente ótimo. A prática comum é avaliar uma faixa de valores — tipicamente de 5 a 50 — e inspecionar como a distribuição de pontuações e os outliers sinalizados mudam. Uma análise de sensibilidade entre os valores de k dá confiança de que as anomalias detectadas são robustas à escolha. O conhecimento do domínio sobre o tamanho mínimo esperado do agrupamento também pode guiar o limite inferior.
O que significa uma pontuação LOF de 1 versus 3?
Uma pontuação próxima a 1 significa que o ponto tem aproximadamente a mesma densidade local que seus vizinhos e é considerado um inlier. Uma pontuação significativamente maior que 1 — frequentemente interpretada como acima de 1.5 ou 2, dependendo do conjunto de dados — indica que a vizinhança do ponto é muito mais esparsa do que as vizinhanças de seus vizinhos. Não há um corte universal; o limiar deve ser escolhido inspecionando a distribuição das pontuações LOF para o conjunto de dados específico.
O LOF pode pontuar novos pontos, nunca vistos, sem retreinamento?
O LOF é um método transdutivo: ele requer que o conjunto de treinamento esteja presente para calcular vizinhanças e densidades para qualquer novo ponto. Para pontuar novas observações, o conjunto de treinamento deve ser retido e cada novo ponto deve ser inserido para recalcular sua k-vizinhança contra os pontos de treinamento armazenados. Algumas implementações oferecem essa funcionalidade, mas ela difere fundamentalmente de modelos paramétricos que aprendem uma função de pontuação compacta.
Como o LOF se compara ao Isolation Forest para detecção de anomalias?
O LOF usa estimativa de densidade baseada em vizinhanças locais e é mais forte quando anomalias se agrupam em regiões localmente esparsas de um espaço heterogêneo. O Isolation Forest usa particionamento aleatório e tende a ser mais rápido e escalável para grandes conjuntos de dados. Para conjuntos de dados de alta dimensionalidade ou muito grandes, o Isolation Forest é frequentemente preferido; para dados de dimensionalidade moderada com variação de densidade, o LOF frequentemente oferece discriminação mais fina.
Métodos relacionados
Fontes
Breunig, M. M., Kriegel, H.-P., Ng, R. T., & Sander, J. (2000). LOF: Identifying density-based local outliers. Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, 93–104.
Abrir referência DOICopiado.Aggarwal, C. C. (2017). Outlier Analysis (2nd ed., Ch. 4). Springer.
ISBN: 978-3-319-47577-6Copiado.Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed., Ch. 14). Springer.
ISBN: 978-0-387-84857-0Copiado.