Detecção de anomalias

Detecção de anomalias
Sigla	DA
Aplicações	Processamento de dados, Análise de Dados
Conceitos relacionados	Dados, Anomalias, Mineração de Dados

Anomalias

A deteção de anomalias consiste na identificação de padrões em dados com um comportamento diferente do esperado. Estes padrões são muitas vezes referidos como anomalias, outliers, exceções, aberrações, observações discordantes, entre outros, variando de acordo com o contexto. Os termos anomalia e outlier são os mais utilizados no contexto de deteção de anomalias.

Vários fatores contribuem para a caracterização do problema, tais como a natureza dos dados de entrada, a disponibilidade de rótulos e as restrições e requisitos.

Natureza dos dados

Os atributos podem ser binários, categóricos ou contínuos. Um dado pode consistir em apenas um atributo (univariável) ou múltiplos atributos (multivariada). No caso de dados multivariados, todos os atributos podem ser do mesmo tipo ou pode ser uma mistura de diferentes tipos de dados.

A natureza dos atributos determina a aplicabilidade dos métodos de deteção de anomalias.

Os dados de entrada também podem ser categorizados com base na relação presente entre instâncias de dados. A maioria dos métodos de deteção de anomalias existentes lida com dados pontuais, em que nenhum relacionamento é assumido entre os tipos de dados.

Em geral, as instâncias de dados podem ser ligadas umas às outras. Alguns exemplos são dados sequenciais, dados espaciais, e dados gráficos. Em dados sequenciais, as instâncias dos dados são linearmente ordenáveis, por exemplo, as séries cronológicas, sequências do genoma ou sequências proteicas. Em dados espaciais, cada tipo de dados está relacionado com as suas instâncias vizinhas, por exemplo, os dados de tráfego de veículos ou dados ecológicos. Quando os dados espaciais têm uma componente temporal, são referidos como dados espaço-temporais, por exemplo, dados sobre o clima. Nos dados gráficos, instâncias de dados são representados como vértices de um grafo e ligados a outros vértices com arestas.

Tipos de anomalias

Anomalias pontuais

Figura 1 - Exemplo de anomalias em uma série de dados de duas dimensões.

Se um tipo de dado individual pode ser considerado como anormal relativamente ao resto dos dados, o tipo é designado por anomalia pontual. Esta classificação de anomalia é a mais simples e é o foco da maioria das pesquisas sobre deteção de anomalias. Por exemplo, na Figura 1, os pontos O₁ e O₂, bem como pontos na região O₃, estão fora o limite de regiões normais N₁ e N₂ e, portanto, são anomalias pontuais, uma vez que são diferentes dos dados normais.

Como exemplo real temos a deteção de fraude no uso do cartão de crédito. Suponhamos que o conjunto de dados corresponde às transações com o cartão de crédito de um indivíduo. Por uma questão de simplicidade, vamos supor que os dados são univariáveis, e são caraterizados como sendo o montante gasto. Se uma transação para a qual o montante gasto é muito elevado em comparação com o intervalo normal de despesas para esta pessoa, será uma anomalia pontual.

Anomalias contextuais

Se uma instância de dados é anômala num contexto específico, mas não de outra forma é denominado por anomalia contextual (também é referida como anomalia condicional. A noção de um contexto é induzida pela estrutura do conjunto de dados e tem de ser especificada como parte da formulação do problema. Cada instância de dados é definida usando os dois seguintes conjuntos de atributos:

Atributos contextuais

São usados para determinar o contexto para essa instância. Por exemplo, em conjuntos de dados geográficos, a longitude e latitude de um local são os atributos do contexto. Em dados de séries temporais, o tempo é um atributo contextual que determina a posição de uma instância em toda a sequência.

Atributos comportamentais

Figura 2 - Anomalia contextual t₂ em uma série de dados temporal de temperaturas.

Definem as características não contextuais de uma instância. Por exemplo, num conjunto de dados geográficos descrevendo a precipitação média de todo o mundo, a quantidade de precipitação em qualquer local é um atributo comportamental.

A Figura 2 mostra um exemplo de uma série de tempo-temperatura que indica a temperatura mensal de uma área ao longo dos últimos anos. Uma temperatura de 35°F pode ser normal durante o inverno (no momento t₁) naquele local, mas o mesmo valor durante o verão (no tempo t₂) seria uma anomalia. Um exemplo semelhante pode ser encontrado no domínio de deteção de fraude no cartão de crédito. Um atributo contextual no domínio do cartão de crédito pode ser o momento da compra. Suponha que um indivíduo geralmente tem um gasta em regra 100 euros por semana exceto durante a semana do Natal, quando se chega 1000 euros. Uma nova compra de 1000 numa semana em julho será considerada uma anomalia contextual, uma vez que não se conforma com o comportamento normal do indivíduo no contexto de tempo, embora o mesmo valor gasto durante a semana do Natal será considerado normal.

Anomalia coletiva

Figura 3 - Anomalia coletiva correspondente a Contração Atrial Prematura em um eletrocardiograma humano.

Se uma coleção de instâncias de dados relacionados é anómala no que diz respeito a todo o conjunto de dados é denominado por anomalia coletiva. As instâncias de dados individuais numa anomalia coletiva podem não ser anomalias por si mesmos, mas a sua instância num conjunto, como uma coleção é anômalo. A Figura 3 é um exemplo que mostra uma saída de eletrocardiograma humano. A região em destaque indica uma anomalia, pois existe o mesmo valor baixo para um tempo anormalmente longo (correspondente a uma contração prematura atrial). Nota-se que o baixo valor por si só não é uma anomalia.

Rótulos de dados

Os rótulos associados a um tipo de dados vão informar se este é normal ou anormal. A rotulagem dos dados normalmente é feita por um expert, e, portanto, é necessário um grande esforço para se obter dados rotulados.

Com base na disponibilidade de dados rotulados, os métodos de deteção de anomalias podem operar das seguintes formas:

Deteção de anomalias supervisionada

Estes métodos assumem que existe uma série de dados de treino com instancias rotuladas como normais e anormais. A abordagem típica nestes casos, é construir um modelo preditivo para classes normais vs. anomalia. Há duas grandes questões que surgem na deteção de anomalias supervisionadas. Em primeiro lugar, os exemplos de anomalias são muito menos em comparação com os casos normais nos dados de treino. Em segundo lugar, a obtenção de rótulos precisos e representativos, especialmente para a classe anomalia é um desafio. Alguns métodos foram propostos introduzindo anomalias artificiais num conjunto de dados normais para obter um conjunto de dados de treino rotulado. Para além destas duas questões, o problema de deteção de anomalias supervisionado é semelhante à construção de modelos preditivos.

Deteção de anomalias semi-supervisionada

Assume-se que os dados de treino só têm tipos de dados da classe normal. Uma vez que estas não necessitam de rótulos para as classes de anomalias. Por exemplo, na deteção de falhas em naves espaciais, um cenário de anomalia significaria um acidente grave, o que não é fácil de modelar. A abordagem típica usada em tais métodos é a construção de um modelo para a classe correspondente ao comportamento normal, e utilizar o modelo para identificar anomalias nos dados de teste.

Deteção de anomalias não-supervisionada

Estes métodos não requerem dados de treino pelo que são amplamente aplicáveis. Os métodos nesta categoria fazem a suposição implícita de que os tipos normais são muito mais frequentes do que as anomalias nos dados de teste. Se esta hipótese não for verdadeira, então tais métodos sofrem com uma taxa elevada de falsos alarmes. Muitos métodos semi-supervisionados podem ser adaptados para operar num modo sem supervisão utilizando uma amostra dos dados não marcados criados como dados de treino. Esta adaptação assume que os dados de teste contêm muito poucas anomalias e o modelo aprendido durante o treino é robusto para estas poucas anomalias.

Resultados da Deteção de anomalias:

Os resultados produzidos pelos métodos de deteção de anomalias são de um dos dois tipos seguintes:

• Pontuações: os métodos de pontuação atribuem uma pontuação de anomalia para cada instância no teste de dados, dependendo do grau da anomalia. O analista pode optar por analisar as anomalias mais “pontuadas” ou usar um ponto de corte para as selecionar.

• Rótulos: os métodos usados atribuem um rótulo (normal ou anormal) para cada instância de teste.

Exemplos de aplicação das métodos de deteção de anomalias

Para cada aplicação é importante perceber o significado da anomalia, a natureza, os desafios/obstáculos associados à sua deteção e quais os métodos de deteção mais apropriados.

Alguns exemplos de aplicações e métodos mais utilizadas:

Deteção de intrusos

Os métodos de deteção semi-supervisionada e não-supervisionadas são as mais utilizadas. Nestes casos, estão geralmente disponíveis dados rotulados correspondentes ao comportamento normal/esperado, mas não existem dados rotulados para as intrusões. Ex.: Aplicações num contexto de segurança.

Em 1987 Denning classificou os sistemas de deteção de intrusos em host-based (no hospedeiro) e network-based (na rede).

Deteção de fraudes

Um exemplo concreto é a deteção de fraudes a cartões de crédito.

Neste domínio os dados são geralmente compostos por registos de várias dimensões, tais como a identificação do cliente (ID), o valor gasto, o tempo entre transações, entre outras. As fraudes representam tipicamente transações, correspondentes a anomalias pontuais, onde se verificam pagamentos de valores elevados, compra de produtos nunca antes adquiridos pelo utilizador, elevadas taxas de compras, entre outros. Para a sua deteção as organizações baseiam-se na monitorização e no comportamento “padrão” do cliente em questão, rotulando-o. Cada cliente é associado a um “perfil”, permitindo a utilização de métodos de agrupamento. Existem duas abordagens para a resolução deste problema. A primeira é conhecida por by-owner, e consiste na rotulagem de cada cliente consoante o histórico de transações. Esta abordagem é geralmente cara, pois implica a consulta de um repositório central de dados a cada transação, para a comparação de comportamentos. A segunda, conhecida por by-operation, deteta transações invulgares com base na localização geográfica. Estes, são métodos de deteção contextuais em que na primeira o contexto é o utilizador, e na segunda o contexto é a localização geográfica.

O conceito de monitorização de atividade como uma abordagem geral para a deteção de fraudes nestes domínios foi introduzido por Fawcett e Provost (1999).

Na tabela 1 esta representados alguns exemplos de métodos utilizadas para a deteção de fraudes a cartão de crédito.

Tabela 1 - Exemplos de métodos de detecção de anomalias utilizadas em detecção de fraudes a cartões de crédito (adaptada de Chandola et al., 2009)

Método	Referência
Neural Networks	Cardwatch [Aleskerov et al. 1997], Ghosh and Reilly [1994], Brause et al. [1999], Dorronsoro et al. [1997]
Rule-Based System	Brause et al. [1999]
Clustering	Bolton and Hand [1999]

Deteção de anomalias médicas e de saúde publica

A deteção de anomalias no domínio médico e de saúde publica trabalha normalmente com registos de pacientes. Os dados podem ter anomalias com diferentes origens, tais como a condição anormal do paciente, erros de instrumentação ou erros de registo. Vários métodos têm também sido desenvolvidas para a deteção de surtos de doenças em locais específicos. A natureza dos dados e as consequências que as anomalias nesta área podem representar exigem um alto grau de precisão nos métodos de deteção utilizados.

Os dados consistem habitualmente em registos de diversos tipos de características, tais como a idade, o grupo sanguíneo e o peso, e podem ter um carácter temporal ou espacial. A maioria dos métodos de deteção de anomalias nesta área pretendem detetar registos invulgares (anomalias pontuais), com o auxilio de dados rotulados de indivíduos saudáveis - deteção semi-supervisionada. Os dados de series temporais, como os Eletrocardiogramas (ECG) e Eletroencefalogramas (EEG), são também suscetíveis da aplicação de métodos de deteção de anomalias. Alguns métodos de deteção de anomalias coletivas têm sido utilizados neste tipo de dados.

O grande desafio da deteção de anomalias em medicina prende-se com o facto de a classificação de uma anomalia como um evento normal poder acarretar custos e consequências muito significativas.

Na tabela 2 estão representados alguns métodos utilizados nesta área.

Tabela 2 - Exemplos de métodos de deteção de anomalias utilizadas em medicina e saúde pública (adaptada de )

Método	Referência
Parametric Statistical Modeling	Horn et al. (2001), Laurikkala et al. [2000], Solberg and Lahti [2005], Roberts [2002], Suzuki et al. [2003]
Neural Networks	Campbell and Bennett [2001]
Bayesian Networks	Wong et al. [2003]
Rule-Based Systems	Aggarwal [2005]
Nearest Neighbor Based Techniques	Lin et al. [2005]

Deteção de danos industriais

Os dados neste domínio são geralmente de carácter temporal, possibilitando a aplicação de métodos com base na análise de series temporais [Keogh et al. 2002, 2006; Basu and Meckesheimer 2007]. Os dados relativos aos componentes “normais”, sem defeitos, estão disponíveis permitindo a utilização de métodos semi-supervisionadas. Ex.: Monitorização dos sistemas industriais a nível de estruturas mecânicas e de performance.

Deteção de anomalias em processamento de imagem

Os dados têm características temporais e espaciais. As anomalias de interesse neste domínio podem ser pontuais ou contextuais. Ex.: análise de imagens de satélite, imagiologia médica e vigilância de vídeo.

Deteção de anomalias de texto

Os dados podem ter um carácter temporal, uma vez que os documentos são recolhidos ao longo do tempo. São geralmente dados de grandes dimensões, e um dos grandes desafios referentes a este domínio é a grande variação de dados e dos documentos em si. Ex.: deteção de eventos, noticias ou tópicos específicos em coleções de documentos.

Redes de sensores

Os dados são geralmente transmitidos por streaming. Permite a deteção de falhas, defeitos e intrusões nos sistemas. Os métodos de deteção de anomalias neste domínio representam um grande desafio devido à natureza, às características e ao contexto dos dados. Estes métodos operam normalmente em ambiente online. Ex.: rede composta por diversos sensores com diferentes tipos de dados (binário, contínuo, discreto, áudio, vídeo, entre outros).

Deteção de anomalias por Classificação

Figura 4 - Deteção de anomalias com métodos de classificação (imagem adaptada de Chandola et al., 2009).

Estes métodos compreendem duas fases:

1. Fase de treino: construção de um classificador com dados de treino previamente rotulados
2. Fase de teste: Classificação dos objetos de teste como “normal” ou “anómalo”.

Com base nos rótulos disponíveis para a fase de treino, os métodos de deteção de anomalias podem ser divididos em duas categorias:

1. Multi-classe: assume que os dados de treino contêm objetos rotulados pertencentes a várias classes normais. O objeto de teste é considerado anómalo se não pertencer a nenhuma das classes normais (Figura 4a). Alguns métodos associam uma pontuação de confiança à previsão do classificador.
2. Classe única: assume que todos os objetos de treino pertencem apenas a uma classe, rotulada de normal. Qualquer objeto de teste que não se encontre dentro do limite da classe de treino é declarado anómalo. Estes métodos utilizam algoritmos que definem um limite discriminativo em torno dos casos normais (Figura 4b). Alguns exemplos são o Support Vector Machines (SVMs) e o discriminante de Núcleo de Fisher.

Alguns métodos de deteção de anomalias que utilizam algoritmos de classificação são:

Redes Neuronais (Neural Networks-Based)

Este método é aplicado tanto numa abordagem multi-classe, como em classe única.

A deteção de anomalias com um método básico de multi-classe através de redes neuronais divide-se em dois passos. No primeiro, a rede neuronal é “ensinada” com os dados de treino para identificar as classes normais. No segundo, cada objeto de teste é fornecido como input à rede neuronal. Se a rede aceitar o input, o objeto é normal, se por outro lado o rejeitar o objeto é considerado anómalo (De Stefano et al. 2000) [Stefano et al. 2000; Odin and Addison 2000].

O método Replicator Neural Networks é utilizado para a deteção de anomalias com uma única classe.

Redes Bayesianas

As redes bayesianas são utilizadas na deteção de anomalias em situações com mais de uma classe (multi-classe). Calculam a probabilidade posterior de se observar uma determinada classe, no objeto de teste, baseando-se num conjunto de dados rotulados como normais e anómalos.

O método básico para uma série de dados categóricos univariados consiste em estimar a probabilidade posterior de uma classe em comparação com a probabilidade das outras classes e da “classe” rotulada como anomalia. A classe com maior probabilidade é selecionada. As probabilidades zero, em especial para a classe anomalia, são suavizadas com o método de Laplace Smoothing. Este método pode ser generalizado para dados categóricos multivariados agregando-se a probabilidade posterior por atributo, utilizando este novo valor para se atribuir a classe.

Muitas variantes deste método tem sido propostas para deteção de intrusos, anomalia textual [Baker et al., 1999] e surtos de doenças.

Support Vector Machines (classe única)

As Support Vector Machines têm sido utilizadas em deteção de anomalias com uma classe. Este algoritmo aprende as fronteiras dos dados normais. Os algoritmos Kernel podem ser utilizados para delimitar regiões complexas.

O método básico determina se uma instância cai dentro da região definida como normal. Se cair fora dela, é classificada como anomalia.

Variantes deste método básico foram propostas para a deteção de anomalias em áudio, deteção de intrusos e anomalias temporais em estações de geração de energia. REFERENCIA?

Rule-Based

Os métodos de deteção baseados em regras “aprendem” as regras que caracterizam um comportamento normal num sistema. Um objeto de teste que não cumpra nenhuma das regras é considerado anómalo. Estes métodos são aplicados em dados com características multi-classe e de classe única.

Vantagens dos métodos de deteção de anomalias por classificação:

• Os métodos de classificação, especialmente as de multi-classe, podem utilizar poderosos algoritmos para distinguir objetos de diferentes classes.
• A fase de teste é rápida, desde que os objetos de teste sejam comparados com um modelo previamente construído.

Desvantagens dos métodos de deteção de anomalias por classificação:

• Os métodos de classificação em múltiplas classes dependem da disponibilidade de rótulos precisos para as várias classes normais, o que muitas vezes não é possível.

• Os métodos de classificação atribuem um rótulo a cada objeto de teste, o que também é uma desvantagem quando se é desejado um valor de anormalidade para as instâncias alguns métodos de classificação que obtém uma predição probabilística podem ser utilizados para resolver esta questão [Platt 2000].

Deteção de anomalias pela distância do vizinho mais próximo (k-NN)

Figura 5 - Distância de p₁ e p₂ para k=4. (imagem adaptada de Breunig et al., 2000).

Figura 6 - Ilustração do teorema. (imagem adaptada de Breunig et al., 2000).

Figura 7 - Vantagem dos métodos de densidade local vs. densidade global. (imagem adaptada de Breunig et al., 2000).

Inicialmente proposto por Knorr & Ng (1997), tem como pressupostos que os dados normais tem uma vizinhança densa, e que as anomalias estão afastados dos seus vizinhos.

O modelo básico de Knorr & Ng considera que a instância é definida como uma anomalia (baseada em distância) se ao menos uma fração β das observações da série de dados está afastada para além de r. Tal definição está baseada em um único critério global, determinado pelos parâmetros r e β. Esta definição levanta algumas dificuldades como a determinação do valor de r e a falta de um ranking para as anomalias. Sua complexidade computacional é de O(pn²), onde p é o número de atributos e n o tamanho da amostra, sendo, portanto, inadequado para grandes séries de dados.

Perspetiva global vs. perspetiva local: um objeto pode parecer anómalo em relação a todos os objetos, mas não em relação aos objetos vizinhos. Por exemplo, uma pessoa com 1,95m de altura é anormalmente alto em relação a população geral, mas não em relação a jogadores de basketball profissionais. Desta forma, os métodos atuais baseados em distância procuram abordar ambas as situações.

k-Vizinho mais próximo (k-Nearest Neighbor: k-NN)

Proposta por Ramaswamy (2000), é uma abordagem global, que considera que as anomalias são as n observações que possuem as maiores distâncias ao seu k-ésimo vizinho mais próximo. Uma deficiência deste método é que ele só considera a distância do k-ésimo vizinho e ignora a informação das observações mais próximas. Uma alternativa também utilizada é obter a distância média dos k vizinhos mais próximos, com a vantagem de ser mais robusto a flutuações estatísticas, e a desvantagem de levar mais tempo para ser calculado. Possui uma complexidade computacional variável dependendo do algoritmo de procura do vizinho mais próximo.

Fator de Anomalia Local (Local Outlier Factor: LOF)

Foi o primeiro algoritmo baseado em densidade, proposto em 2000 por Breunig et al., e é provavelmente o método atualmente mais utilizado.

Este método compara a densidade local de uma instância com a densidade dos seus vizinhos, dado que a densidade é inversamente proporcional a média das distâncias dos k-vizinhos mais próximos. O valor LOF atribuído à instância é dado pela razão da densidade local desta observação pela média das densidades dos seus vizinhos. A Figura 5 demonstra a ideia da "distância de acessibilidade" com k = 4. Intuitivamente, se o objeto p está longe de o (ex.: p₂ na figura), então a "distância de acessibilidade" entre os dois é simplesmente a sua distância. Entretanto se estiverem suficientemente perto (ex.: p₁ na figura), a "distância de acessibilidade" é representada por k-distance de o. A Figura 6 ilustra de forma mais global o teorema.

Isto resulta em que as observações normais tem LOF próximo de 1, e as anomalias um valor maior que 1. Para série de dados suficientemente grandes, um LOF de até 2 pode ser considerado normal.

As vantagens deste algoritmo são a facilidade da interpretação dos valores de LOF e sua habilidade em detetar anomalias previamente não detetadas pela abordagem global. Na Figura 7 podemos verificar que a abordagem global detetaria apenas o ponto p₂ como anomalia, enquanto que na abordagem local, ambos os pontos p₁ e p₂ são identificados. Sua complexidade computacional depende do método de k-NN escolhido, sendo dado por O(n*tempo k-NN)

Deteção de anomalias por Clustering

Figura 8 - Método de deteção de anomalias Cluster-Based Local Outlier Factor (CBLOF) (imagem adaptada de Amer and Goldstein, 2012).

Figura 9 - Comparação do CBLOF com o unweighted-CBLOF. O unweighed-CBLOF (b) é uma variante do algoritmo de (a). O segundo pretende corrigir a discriminação resultante da multiplicação pelo número de objetos do cluster do ponto de teste (imagem adaptada de Amer and Goldstein, 2012).

Os métodos de deteção de anomalias por Clustering assumem que os objetos anómalos estão agrupados em clusters pequenos e dispersos, longe do cluster centroide, ou que não pertencem a qualquer cluster. Dois dos métodos utilizados são o Cluster-Based Local Outlier Factor (CBLOF) e o Local Density Cluster-Based Outlier Factor (LDCOF). O passo inicial destes algoritmos é a classificação dos clusters em: cluster de grandes dimensões (large cluster) e cluster de pequenas dimensões (small cluster) [21] .

O método Cluster-Based Local Outlier Factor (CBLOF) atribui um score de anomalia com base na distância ao cluster de maior dimensão mais próximo, multiplicada pelo tamanho do cluster ao qual o objeto pertence.

Na figura 8 podemos ver uma imagem ilustrativa onde:

O ponto p se situa no cluster de pequenas dimensões C2. Assim, o score de anomalia é igual à distância do ponto central do cluster C1, cluster grande mais próximo, a multiplicar por 5, que é o tamanho do C2. Neste exemplo são identificados dois clusters de grandes dimensões C1 e C3 [21].

Não há consenso quanto ao facto de este ser um método local uma vez que a quantidade de objetos de um cluster não está necessariamente relacionada com a sua densidade [22][21].

Na Figura 9 podemos ver o ponto A e o ponto B. O ponto A é claramente mais outlier que o B, no entanto, o tamanho da bolha (score de anomalia) é maior em B do que em A. Isto é explicado pelo facto de o ponto B ser multiplicado pelo tamanho do cluster branco. Assim os outliers pertencentes a clusters mais pequenos são discriminados, mesmo quando são indubitavelmente mais anómalos. Desta forma, Amer and Goldstein (2012) propuseram uma variante para o algoritmo existente, unweighed-CBLOF:

O método Local Density Cluster-Based Outlier Factor (LDCOF) baseia-se na densidade local, sendo que o score de anomalia é normalizado relativamente aos objetos vizinhos. Neste caso, o score de anomalia tem um threshold que indica se o objeto é o outlier ou não. O score LDCOF é definido pela distância do objeto de teste ao ponto central do cluster mais próximo de maior dimensão, a dividir pela distância média dos objetos do cluster grande ao seu ponto central [21] .

Deteção de anomalias por métodos estatísticos

O princípio subjacente para qualquer método estatística de deteção de anomalia é: “An anomaly is an observation which is suspected of being partially or wholly irrelevant because it is not generated by the stochastic model assumed” [23].

Esta deteção baseia-se na seguinte premissa: as instâncias de dados normais aparecem em regiões de alta probabilidade de um modelo estocástico, enquanto que as anomalias ocorrem nas regiões de baixa probabilidade.

Métodos Paramétricos

Alternativamente, os testes de hipóteses (referido como teste de discordância na literatura deteção outlier [24] podem ser utilizados. A hipótese nula (H0) para esses testes é que a instância dos dados x foi gerada com a distribuição estimada (com parâmetrosΩ). Se o teste estatístico rejeita H0, x é declarado ser anomalia. Um teste de hipótese está associado a um teste estatístico, o qual pode ser utilizado para se obter uma pontuação de anomalia probabilística para a instância de dados x.

Modelo baseado na distribuição normal:

Assume-se que os dados são gerados por uma distribuição normal, os parâmetros são estimados usando estimativas de máxima verossimilhança. A distância de uma instância de dados para a média estimada é a pontuação anomalia para essa instância. É aplicado um valor limite para a pontuação da anomalia para assim se determinar as anomalias.

Existem diferentes métodos para determinar esta distância.

Um método simples de deteção de outliers, muitas vezes utilizado no domínio do processo de controle de qualidade [25], é assumir que todas as instâncias de dados que estão a um a distância da média μ ,superior a 3σ , onde σ é o desvio padrão para a distribuição, são outliers. A região μ ± 3σ contém 99,7% das instâncias de dados.

A regra da plot-box (Figura 9) é o método estatística mais simples que tem sido aplicada

para detetar anomalias uni e multivariadas em dados do domínio médico [26][27]. A plot-box representa graficamente os dados usando um resumo de atributos, como a menor observação não-anomalia (min), o primeiro quartil (Q1), a mediana, o terceiro quartil (Q3), e maior instância não-anomalia (máx). A amplitude interquartil (AIQ), isto é, Q3 - Q1. O limite inferior da plot-box é m=Q1-1,5 * AIQ e limite superior é M=Q3-+1,5 * AIQ. Assim, as instâncias que se encontrem foram do intervalo [m,M] são tratadas como anomalias, este intervalo contém 99,3% de observações e, consequentemente, a escolha destes limites faz com que a plot-box seja equivalente a usar método baseada na distribuição normal.

O teste de Grubbs é usado para detetar anomalias em dados univariáveis [28], [29], sob a suposição de que os dados são gerados por uma distribuição normal Para cada testar a instância x, é calculada a sua pontuação z da seguinte forma:

Ficheiro:Media/image14.png onde Ficheiro:Media/image15.png e s são a média e o desvio padrão da amostra, respetivamente. A instância é anómala seFicheiro:Media/image16.png , onde N é o tamanho da amostra e Ficheiro:Media/image17.pngé o limite usado para declarar que uma instância é anormal ou normal. O limite é calculado com a t-distribuição com um nível de significância de Ficheiro:Media/image18.png. O nível de significância reflete a confiança associada ao limite e indiretamente controla o número de observações que são consideradas anómalas.

Modelo baseado na regressão:

A deteção de anomalias baseada em regressão tem sido investigada para dados de séries temporais [30], [31], [32].

O método básico para deteção de anomalias baseada em regressão consiste de duas partes. Na primeira, um modelo de regressão é ajustado para os dados. Na segunda parte, para cada instância de teste, o resíduo para a instância é usado para calcular a ranking da anomalia. O resíduo é a parte da instância que não é explicado pelo modelo de regressão. A magnitude deste resíduo pode ser usada como o próprio ranking da anomalia para a instância de teste, embora haja testes estatísticos propostos para determinar objetos fora do padrão com certa confiança [23], [33], [34], [35].

A presença de anomalias nos dados de treino pode influenciar os parâmetros da regressão e, portanto, o modelo pode não produzir resultados precisos, como se fossem ruídos. Um método popular para manipular esse ruído é chamado de regressão robusta [36]. Um outro método similar para uma abordagem mais robusta é chamada de Autoregressive Integrated Moving Avarage (ARIMA) [37], [38]. O modelo Autoregressive Moving Avarage (ARMA) é uma outra variante que deteta anomalias em base de dados multivariados [39].

Distribuição baseada em parâmetros mistos:

Tais métodos usam a mistura de parâmetros de distribuição estatística para modelar os dados. Elas podem ser agrupadas em duas subcategorias. A primeira modela observações normais e as anormais como distribuições paramétricas separadas, enquanto que a segunda modela somente as instancias normais como uma distribuição de parâmetros mistos.

A respeito da primeira subcategoria, a fase de teste envolve determinar a qual distribuição, normal ou anormal, a instância de teste pertence. Em [31] é determinado que a instância normal é gerada a partir de uma distribuição normal com os parâmetros e os dados anormais também são gerados por uma normal, porém com uma variância maior.

A segunda subcategoria de métodos modela as observações normais como uma mistura de parâmetros de distribuição. Uma instância de teste que não pertence a nenhum dos modelos aprendidos é declarada como anomalia.

Métodos Não Paramétricos

O método não paramétrico mais simples é usar histogramas para preservar o perfil dos dados normais. Tais métodos também são referenciados como baseados na frequência relativa ou absoluta. Os métodos baseados em histogramas são particularmente populares na comunidade de deteção de intrusão e fraudes, uma vez que o comportamento dos dados é gerido por determinados perfis (utilizadores ou softwares) que podem ser capturados usando um histograma.

O método básico de deteção de anomalias baseada em histograma para dados univariáveis consiste de duas etapas. O primeiro passo implica construir um histograma baseado nos diferentes valores contidos nos atributos para os dados de treino. No segundo passo, o método verifica se uma instância de teste pertence a qualquer um dos bins do histograma. Em caso afirmativo, a instância é considerada normal, caso contrário não é. Uma variação desse método básico é atribuir um ranking à anomalia a cada instância de teste baseada na frequência dos bins à qual ela pertence.

O tamanho do bin usado na construção do histograma é a chave para a identificação da anomalia. Se os bins forem curtos, muitas observações de teste normais irão pertencer a bins vazios ou raros, resultando numa taxa alta de falsos positivos. Se os bins forem largos, muitos testes de observações anormais irão pertencer a bins frequentes, gerando uma alta taxa de falsos negativos. Então o desafio derradeiro para os métodos baseados em histogramas é determinar o tamanho ótimo dos bins para construir os histogramas que mantém uma taxa baixa de falsos positivos e de falsos negativos.

Para dados multivariados, o método básico é construir histogramas de atributos moderados. Durante o teste, para cada instância, o ranking da anomalia para cada valor de atributo é calculado como a altura do bin que contém o atributo. Os rankings da anomalia por atributo são agrupados para obter um ranking de anomalia global para a instância de teste.

Outro método não-paramétrico de deteção de anomalias é a baseada em funções Kernel, que são similares aos métodos paramétricos descritas anteriormente. A única diferença está na utilização do método de estimativas de densidade. Propôs, por [40] um método de deteção de anomalias semi-supervisionado, que usa as funções Kernel para calcular a função de distribuição de probabilidade para os dados normais. Uma nova instância, que corresponde a uma pequena área de probabilidade dessa função de distribuição de probabilidade é considerada como sendo uma anomalia.

Vantagens e desvantagens de métodos estatísticas:

As vantagens de métodos estatísticas são:

• Se os pressupostos sobre a distribuição de dados subjacente forem verdadeiros os métodos estatísticas fornecem uma solução estatisticamente justificável para a deteção de anomalias.
• A pontuação da anomalia fornecida por um método estatístico está associada a um intervalo de confiança, a qual pode ser utilizado como informação adicional para tomar uma decisão em relação àquela instância testada.
• Se a etapa da estimativa de distribuição é robusta para a deteção de anomalias nos dados, os métodos estatísticas pode operar num ambiente sem vigilância, sem qualquer necessidade de dados de treino rotulados.

As desvantagens de métodos estatísticas são:

• Baseiam-se na suposição de que os dados são gerados a partir de uma distribuição específica. Esta suposição, muitas vezes não é verdadeira, especialmente para dados reais de grandes dimensões.

• Mesmo quando o pressuposto estatístico pode ser razoavelmente justificado, existem vários testes de hipóteses que podem ser aplicadas para deteção de anomalias; escolher o melhor muitas vezes não é uma tarefa simples [41].

• os métodos baseados em histograma são relativamente simples de implementar, mas para dados multivariados não são capazes de capturar as interações entre diferentes atributos. Uma anomalia pode ter valores de atributo que são individualmente muito frequentes, mas cuja combinação é muito rara, não sendo possível detetá-la usando a método do histograma

Deteção de anomalias por métodos de teoria da informação

Para analisar o conteúdo de informação de um conjunto de dados usa-se teorias diferentes, tais como:

• Complexidade de Kolmogorov;
• Entropia;
• Entropia relativa.

Esses métodos baseiam-se na suposição seguinte:

Suposição.

Num conjunto de dados as anomalias induzem irregularidades no conteúdo da informação.

C(D). Seja C a complexidade de um dado conjunto de dados, D.

Uma informação teórica método básica pode ser descrita como se segue.

Dado um conjunto de dados D, encontrar o subconjunto mínimo de casos, I, tal que C(D) - C(D-I) é máxima.

Todas as instâncias do subconjunto assim obtido, são consideradas como anômalas.

O problema abordado por este método básico é para encontrar uma solução ótima de Pareto, a qual não tem uma única solução, uma vez que são dois objetivas diferentes que precisam de ser otimizados.

Neste método, a complexidade de um conjunto de dados (C) pode ser medida de diferentes maneiras.

Segundo Arning et al. (1996) usa o tamanho da expressão regular para medir a complexidade de Kolmogorov dos dados (representada como uma expressão) para a deteção de anomalias.

Keogh et al. (2004) usa o tamanho do ficheiro de dados comprimido (usando qualquer algoritmo de compressão padrão), como uma medida do conjunto de dados da complexidade de Kolmogorov.

Outras medidas das teorias da informação, tais como: a entropia; a incerteza relativa; e assim por diante, têm também sido usadas para medir a complexidade de um conjunto de dados categóricos.

Este método básico envolve a otimização dupla para minimizar o tamanho do subconjunto de dados enquanto maximiza a redução da complexidade do conjunto de dados.

Assim, numa abordagem exaustiva em que cada subconjunto possível do conjunto de dados fosse considerado seria executado em tempo exponencial. Vários métodos têm sido propostos para executar uma busca aproximada ao subconjunto mais anômalo.

He et al. (2006) usa um algoritmo de aproximação chamado de Local Search Algorithm (LSA), para determinar aproximadamente tal subconjunto de uma forma linear, utilizando a entropia como medida de complexidade.

Um método semelhante que usa uma medida de informação gargalo foi proposta por Ando (2007).

Métodos da teoria de informação também têm sido utilizadas em conjuntos de dados, em que os dados instâncias são naturalmente ordenados, por exemplo, dados sequenciais e dados espaciais.

Em tais casos, os dados são divididos em subestruturas (segmentos de sequências, subgraphs para gráficos, etc.), e o método de deteção de anomalias encontra a subestrutura, I, tal que C(D)-C(D-I) é máxima.

Este método tem sido aplicado a sequências, dados gráficos e dados espaciais.

Um dos principais desafios de tais métodos é encontrar o tamanho ótimo da subestrutura que resultaria na deteção de anomalias.

Complexidade computacional.

Como mencionado anteriormente, a informação básica teórica de método de deteção de anomalias tem complexidade de tempo exponencial, contudo métodos aproximados têm sido propostos que têm complexidade de tempo linear.

Vantagens e desvantagens de métodos de informação teóricos.

As vantagens são as seguintes:

• Podem operar em um ambiente sem supervisão.
• Não fazem quaisquer suposições sobre a distribuição estatística subjacente para os dados.

As desvantagens são as seguintes:

• O desempenho de tais métodos é muito dependente da escolha das medidas de informação teórica. Muitas vezes, essas medidas podem detetar a presença de anomalias apenas quando existe um número significativamente grande de anomalias presente nos dados.

• Métodos de informação teórica aplicadas a sequências e conjuntos de dados espaciais dependem do tamanho da subestrutura, o que não é muitas vezes trivial de se obter.

• É difícil associar uma pontuação de anomalias a uma instância de teste usando uma informação método teórica.

Deteção de anomalias por métodos espectrais

Tentam encontrar uma aproximação dos dados usando uma combinação de atributos que captura a maior parte da variabilidade dos dados.

Suposição:

Os dados podem ser incorporados num subespaço dimensional inferior em que casos normais e anomalias aparecem significativamente diferentes.

Assim, a abordagem adotada pelos métodos de deteção de anomalias espectrais é determinar tais subespaços (incorporações, projeções, etc.) em que as instâncias anômalas podem ser facilmente identificadas Agovic et al. [2007]. Esses métodos podem trabalhar num ambiente sem vigilância, bem como num supervisionado.

Vários métodos usam Principal Component Analysis (PCA) Jolliffe [2002] para projetar dados num espaço dimensional mais baixo. Um tal método [Parra et al. 1996] analisa a projeção de cada instância de dados ao longo das principais componentes com baixa variância. Um exemplo normal que satisfaz a estrutura de correlação dos dados terá um valor baixo para essas projeções enquanto uma instância anômala que se desvia da estrutura de correlação terá um grande valor.

Dutta et al. [2007] adotou esta abordagem para detetar anomalias em catálogos de astronomia.

Ide e Kashima [2004] propõem um método espectral para detetar anomalias num momento numa série de gráficos. Cada gráfico é representado como uma matriz de adjacência para um dado tempo. Em cada instante de tempo, o componente principal da matriz é escolhido como o vetor de atividade para o gráfico dado.

A série temporal dos vetores de atividade é considerada como uma matriz e o principal vetor singular esquerdo é obtido para capturar as dependências normais ao longo do tempo nos dados. Para um novo gráfico de teste, o ângulo entre o vetor de atividade e o principal vetor singular esquerdo obtidos a partir dos gráficos anteriores é calculado e utilizado para determinar a pontuação de anomalia do gráfico de teste.

Numa abordagem semelhante, Sun et al. [2007] propõem um método de deteção de anomalias numa sequência de gráficos executando Compact Matrix Decomposition (CMD) sobre a matriz de adjacência para cada gráfico e obtendo-se assim uma aproximação da matriz original.

Para cada gráfico na sequência, os autores realizam CMD e calculam o erro de aproximação entre matriz original de adjacência e a matriz aproximada. Os autores construem uma série temporal dos erros de aproximação e das anomalias detetadas numa série de erros no tempo; o gráfico correspondente ao erro de aproximação de anomalias é declarado ser anômalo. Shyu et al. [2003] apresentam um método de deteção de anomalias onde os autores realizam robusto PCA [Huber 1974] para estimar os componentes principais da matriz covariância dos dados de treino normal.

A fase de testes consiste em comparar cada ponto com os componentes e atribuir uma pontuação às anomalias baseada na distância do ponto a partir dos componentes principais. Assim, se a projeção de x sobre os componentes principais é Y1, Y2,. . . , Yp e os valores eigen correspondentes são λ1, λ2,. . . , Λp, então,

tem uma distribuição chi-square [Hawkins 1974]. Usando este resultado, os autores propõem que, para um dado nível de significância α, a instância de X é uma anomalia se

Pode-se mostrar que a quantidade calculada na 1ª Equação é igual a distância de Mahalanobis da instância x da média da amostra quando q=p Shyu

et al. [2003]. O robusto método PCA-based foi aplicada ao domínio da deteção de intrusão de rede Shyu et al. [2003]; Lakhina et al. [2005]; Thottan e Ji [2003] e para a deteção de anomalias em componentes artesanais espaciais Fujimaki et al. [2005].

Complexidade computacional

Métodos baseados no PCA padrão são tipicamente lineares no tamanho dos dados, mas muitas vezes quadráticas no número de dimensões.

Métodos não-lineares podem melhorar a complexidade de tempo para serem lineares no número de dimensões, mas polinomiais no número de componentes principais Gunter et al. [2007]. Os métodos que realizam SVD sobre os dados são tipicamente quadráticas no tamanho dos dados.

Vantagens e desvantagens dos métodos espectrais

As vantagens são:

• Métodos de espectrometria realizam automaticamente a redução da dimensionalidade e, portanto, são adequadas para lidar com altos conjuntos de dados dimensionais. Além disso, elas também podem ser utilizadas como uma etapa de pré-processamento, seguido pela aplicação de qualquer método de deteção de anomalias existente no espaço transformado.
• Os métodos espectrais podem ser utilizados num ambiente sem supervisão.

As desvantagens são:

• Métodos espectrais são úteis apenas se as instâncias normais e anormais são separáveis na incorporação dimensional inferior dos dados.
• Métodos espectrais normalmente têm alta complexidade computacional.