2016: Introdução à Mineração de Dados: Conceitos Básicos, Algoritmos e Aplicações

1

Introdução à Mineração de Dados: Conceitos Básicos,

Algoritmos e AplicaçõesLeandro Nunes de Castro; Daniel Gomes Ferrari

Editora Saraiva, 2016, 351 p. ISBN 978-85-472-0098-5

MATERIAL DE APOIO AO LIVRO

Capítulo 1Introdução à Mineração

de DadosLeandro Nunes de Castro

Daniel Gomes Ferrari

Sumário• Introdução• O que é mineração de dados?• As diferentes nomenclaturas• Paradigmas de aprendizagem• Exemplos de aplicação

1.1 Introdução

1.2 O que é Mineração de Dados?

O termo mineração de dados (MD) foi cunhado como uma alusão ao processo de

mineração descrito anteriormente, uma vez que se explora uma base de dados (mina)

usando algoritmos (ferramentas) adequados para se obter conhecimento (minerais

preciosos).

L. N. de Castro & D. G. Ferrari, Introdução à Mineração de Dados: Conceitos Básicos, Algoritmos e Aplicações, 1ª. Ed., Saraiva, 2016.

6



7



8


1.2.1 Principais tarefas do KDD• Análise descritiva de dados• Predição: classificação e estimação• Análise de grupos• Associação• Detecção de anomalias

1.2.2 Dicas para uma análise eficiente e eficaz• Estabelecer a significância da mineração• Reconhecer que as características da base de dados

influenciam todos os dados• Necessidade de conhecer os dados• Busca pela parcimônia• Verificar os erros• Validar seus resultados

1.3 As diferentes nomenclaturas• Inteligência artificial clássica: ciência e engenharia

de máquinas inteligentes (abordagens top-down).• Inteligência computacional: área criada para

englobar as redes neurais artificiais, os algoritmos evolutivos e os sistemas fuzzy (abordagens bottom-up).• Aprendizagem de máquina: visa desenvolver

programas computacionais capazes de melhorar seu desempenho por meio da experiência (abordagens bottom-up).

1.4 Paradigmas de aprendizagem• Aprendizado supervisionado: é baseado em um

conjunto de objetos para os quais as saídas desejadas são conhecidas, ou em algum outro tipo de informação que represente o comportamento que deve ser apresentado pelo sistema;• Aprendizado não supervisionado: é baseado

apenas nos objetos da base, cujos rótulos são desconhecidos. Basicamente, o algoritmo deve aprender a “categorizar” ou rotular os objetos.

1.5 Exemplos de aplicação• Predição de produtividade de grãos• Análise de sentimento em redes neurais• Detecção de fraudes em cartões de crédito• Combate a perdas não técnicas de energia elétrica• Segmentação de curvas de carga em sistemas de

energia elétrica• Modelagem de processos siderúrgicos


14

Capítulo 2Pré-Processamento de

DadosLeandro Nunes de Castro



15

Sumário• Introdução• O processo de preparação de bases de dados• Limpeza dos dados• Integração de dados• Redução dos dados• Transformação dos dados• Discretização• Exemplo do processo de preparação da base de

dados


16

2.1 Introdução• O que há de estranho nessa base?


17

2.1 Introdução


18

2.1 Introdução• Questões a serem respondidas:• Se existem dados ausentes, inconsistentes ou ruidosos,

como tratá-los?• É possível resumir a base de dados de forma a serem

obtidos resultados melhores no processo de mineração?• Existem atributos que são mais relevantes que outros,

ou até irrelevantes, para uma dada análise?• Quais são os tipos de atributos da base? É preciso

padronizá-los?• Há atributos naturalmente inter-relacionados?


19

2.1.1 Nomenclatura e tipos de dados• Estruturados: os dados residem em campos fixos em um arquivo – por

exemplo, uma tabela, uma planilha ou um banco de dados. Dependem da criação de um modelo de dados, o que inclui definir quais campos de dados serão utilizados (por exemplo, nome, idade, nível educacional, estado civil, gênero etc.).

• Semiestruturados: é um tipo de dado que não possui a estrutura completa de um modelo de dados, mas também não é totalmente desestruturado. Geralmente são usados marcadores (por exemplo, tags) para identificar certos elementos dos dados, mas a estrutura não é rígida. Exemplos conhecidos de dados semiestruturados são arquivos XML e e-mails.

• Não estruturados: é aquele que não possui um modelo de dados, que não está organizado de uma maneira pré-definida ou que não reside em locais definidos. Normalmente se refere a textos livres, imagens, vídeos, sons, páginas web, arquivos PDF, entre outros.


20

2.1.1 Tipos de atributos


21

2.2 Processo de preparação da base de dados


22

2.3.1 Limpeza dos dados: Valores ausentes• Ignorar o objeto: consiste em remover da base (ignorar) todos

aqueles objetos que possuem um ou mais valores ausentes. • Imputar manualmente os valores ausentes: consiste em escolher

de forma empírica um valor a ser imputado para cada valor ausente.

• Usar uma constante global para imputar o valor ausente: esse método corresponde a substituir todos os valores ausentes de certo atributo por uma constante única.

• Imputação do tipo hot-deck: neste método um valor ausente é imputado usando o valor do mesmo atributo de um objeto similar aleatoriamente selecionado. A similaridade entre os objetos pode ser calculada utilizando, por exemplo, uma medida de similaridade ou distância entre os objetos.


23

2.3.1 Limpeza dos dados: Valores ausentes• Imputar de acordo com a última observação (last observation carried

forward): envolve ordenar a base de dados seguindo um ou mais de seus atributos. Feito isso, o algoritmo busca cada valor ausente e usa aquele valor da célula imediatamente anterior para imputar o valor ausente.

• Usar a média ou moda de um atributo para imputar o valor ausente: o método consiste em substituir os valores ausentes de cada atributo pela média (no caso de atributos numéricos) ou moda (no caso de atributos nominais).

• Usar a média ou moda de todos os objetos da mesma classe para imputar o valor ausente: a média ou moda é tomada considerando apenas os objetos da mesma classe daquele que contém o valor ausente.

• Usar modelos preditivos para imputar o valor ausente: o atributo com valores ausentes é utilizado como atributo dependente, ao passo que os outros atributos são usados como independentes para se criar o modelo preditivo.


24

2.3.2 Limpeza dos dados: Ruídos


25

2.3.2 Limpeza dos dados: Ruídos• Encaixotamento• O objetivo dos métodos de encaixotamento é distribuir

os valores de um atributo em um conjunto de caixas (bins). • Há essencialmente dois tipos de métodos de

encaixotamento: de mesma largura e de mesma frequência. • No encaixotamento de mesma largura, o intervalo de

cada caixa tem o mesmo tamanho, ao passo que, no encaixotamento de mesma frequência, a quantidade de objetos em cada caixa é a mesma.


26

2.3.2 Limpeza dos dados: Ruídos• Encaixotamento: ExemploConsidere a base de dados de marketing bancário (Tabela 2.3). Na amostra o atributo “dia” possui os seguintes valores: 19, 11, 16, 3, 23, 14; e “duração” os valores 79, 220, 185, 199, 141, 341. Dados ordenados para o atributo “dia”: 3, 11, 14, 16, 19, 23.Dados ordenados para o atributo “duração”: 79, 141, 185, 199, 220, 341.

• Atributo “dia”Partição em caixas de Suavização pela médiamesma largura: da caixa:Caixa 1 [3,13]: 3, 11 7, 7Caixa 2 [13,23]: 14, 16, 19, 23 18, 18, 18, 18

• Atributo “duração”Partição em caixas de Suavização pelos extremosmesma frequência: da caixa:Caixa 1 [79,185]: 79, 141, 185 79, 185, 185Caixa 2 [199,341]: 199, 220, 341 199, 199, 341


27



28



29

2.4 Integração de dados• Redundância

• Existe um tipo de redundância muito relevante em mineração, que é a situação na qual um determinado objeto ou atributo pode ser obtido de um ou mais objetos ou atributos da base.

• Duplicidade• A duplicidade é um dos casos possíveis de redundância no

qual objetos e/ou atributos aparecem repetidos na base.

• Conflitos• Ocorrem quando, para a mesma entidade, diferentes valores

aparecem em diferentes fontes de dados. Os conflitos podem ser consequência de diferentes representações, escalas ou mecanismos de codificação.


30

2.5 Redução de dados


31

2.5 Redução de dados• Tipos de redução de dados:

• Seleção de atributos (ou características): efetua uma redução de dimensionalidade na qual atributos irrelevantes, pouco relevantes ou redundantes são detectados e removidos.

• Compressão de dados: também efetua uma redução da dimensionalidade, mas empregando algoritmos de codificação ou transformação de dados (atributos).

• Redução no número de dados: os dados são removidos, substituídos ou estimados por representações menores, como modelos paramétricos e métodos não paramétricos.

• Discretização: os valores de atributos são substituídos por intervalos ou níveis conceituais mais elevados, reduzindo a quantidade final de atributos.


32

2.5 Redução de dados• Redução do número de dados:

• Amostragem aleatória sem substituição: uma amostra com n objetos distintos (n < N) é retirada aleatoriamente da base de dados.

• Amostragem aleatória com substituição: similar ao caso anterior, mas cada objeto retirado da base é armazenado e devolvido à base.

• Amostragem sistemática: organiza a base de dados seguindo algum critério e seleciona objetos de forma sistemática.

• Amostragem por grupo: se uma base de dados está agrupada em M grupos disjuntos, então m grupos (m < M) podem ser escolhidos aleatoriamente.

• Amostragem estratificada: a proporção de dados de cada classe é mantida.


33

2.6 Transformação dos dados• Padronização:• Capitalização: é usual padronizar as fontes,

normalmente para maiúsculo.• Caracteres especiais: uma simples troca de letras em

valores nominais pode evitar eventuais problemas.• Padronização de formatos: observar e padronizar o

formato de cada atributo da base, principalmente quando diferentes bases precisam ser integradas.• Conversão de unidades: todos os dados devem ser

convertidos e padronizados em uma mesma unidade de medida.


34

2.6 Transformação dos dados• Normalização

• Max-Min

• Escore-z

• Escalonamento decimal

• Range interquartil


35

2.7 Discretização• A maneira mais óbvia de discretizar um dado

atributo é dividindo seu domínio em um número pré-determinado de intervalos iguais, o que normalmente é feito no momento da coleta dos dados. • Outros métodos de discretização são: • Encaixotamento (binning) • Análise de histograma • Agrupamento • Discretização baseada em entropia.


36

Capítulo 3Análise Descritiva de




37

Sumário• Introdução• O processo de análise descritiva de dados• Distribuições de frequência• Visualização dos dados• Medidas resumo


38

3.1 Introdução• A análise descritiva de dados (ADD) é utilizada para

descrever, simplificar ou sumarizar as principais características de uma base de dados, formando o princípio de qualquer análise quantitativa de dados. • A diferença entre a análise descritiva e a mineração

propriamente dita é que a ADD visa descrever e encontrar o que há nos dados, ao passo que os algoritmos de mineração buscam conclusões que extrapolam os dados e permitem inferir algo a partir deles.


39

3.2 O processo de ADD


40

3.2.1 Distribuições de frequência• Conceitos importantes:• Classes• Limites inferiores e superiores de classe• Fronteiras de classes• Pontos médios das classes• Amplitude de classes• Frequência absoluta e relativa (de uma classe)• Frequência acumulada


41

3.2.1 Construção de um distribuição de frequência• Escolha o número de classes desejado.• Calcule a amplitude de classe• Determine o ponto inicial• Liste os limites inferiores de classe• Preencha os limites superiores de classe• Rotule cada valor do atributo• Utilize os rótulos para encontrar a frequência

(absoluta, relativa e acumulada) para cada classe


42

3.2.2 Visualização dos dados• Histogramas• Polígonos de frequência• Ogivas• Gráficos de Pareto• Gráficos de setores• Gráfico de dispersão


43

3.2.2 Visualização dos dados: Histogramas


44

3.2.2 Visualização dos dados: Polígonos de frequência


45

3.2.2 Visualização dos dados: Ogiva


46

3.2.2 Visualização dos dados: Gráfico de Pareto


47

3.2.2 Visualização dos dados: Gráfico de setores


48

3.2.2 Visualização dos dados: Gráfico de dispersão


49

3.2.3 Medidas resumo• Algumas medidas podem ser usadas para resumir a

informação contida em uma distribuição de probabilidade de um atributo ou sumarizar a informação contida em uma base de dados. • Três tipos de medidas são importantes: • Medidas de tendência central • Medidas de dispersão • Medidas de forma da distribuição.


50

3.2.3 Medidas resumo: Tendência central


51

3.2.3 Medidas resumo: Dispersão• Enquanto as medidas de tendência central buscam

valores centrais, as medidas de dispersão ou espalhamento expressam quantitativamente a variabilidade, ou dispersão, dos dados. • Dito de outra forma, as medidas de dispersão

denotam o quanto uma distribuição está compacta ou alongada.


52

3.2.3 Medidas resumo: Dispersão• Amplitude: é a diferença entre o maior valor e o

menor valor de uma variável:

• Desvio padrão: é a medida de variação (ou medida de dispersão) mais importante e fornece uma medida da variação dos dados em relação à média, ou seja, uma espécie de desvio médio dos valores em relação à média:


53

3.2.3 Medidas resumo: Dispersão• Regra empírica da amplitude: baseia-se no princípio de que,

para muitos conjuntos de dados, a grande maioria (p. ex., 95%) dos valores amostrais se localiza a dois desvios padrões da média.• Regra empírica (68-95-99,7) para dados com distribuição

Normal: esta regra estabelece que para atributos com distribuição normal, aplicam-se as seguintes propriedades:• Cerca de 68% de todos os valores ficam a 1 desvio padrão da

média;• Cerca de 95% de todos os valores ficam a 2 desvios padrões da

média;• Cerca de 99,7% de todos os valores ficam a 3 desvios padrões da

média.


54

3.2.3 Medidas resumo: Dispersão• Teorema de Chebyshev: a proporção ou fração de qualquer conjunto de

dados que se situa a K desvios padrões da média é sempre, no mínimo, 1 1/K2, sendo K > 1. Exemplo: para K = 2 pode-se dizer que pelo menos 3/4 (75%) de todos os valores se localizam a dois desvios padrões da média.

• Variância: mede a dispersão de um conjunto de valores e é sempre não negativa. Uma variância pequena indica que os dados tendem a estar bem próximos à média e, portanto, uns aos outros. Valores grandes de variância indicam dados dispersos, ou seja, distantes da média e distantes uns dos outros:


55

3.2.3 Medidas resumo: Dispersão• Coeficiente de variação (CV): para um conjunto de dados

amostrais ou população, o CV é expresso como um percentual e descreve o desvio padrão relativo à média:


56

3.2.3 Medidas resumo: Dispersão


57

3.2.3 Medidas resumo: Forma• Para uma amostra de N valores o valor da assimetria é dado pela

expressão:

• onde é a média do atributo, m3 é o terceiro momento central do atributo, e s2 é a variância de x.


58

3.2.3 Medidas resumo: Forma• Para uma amostra com N valores a curtose é dada pela

equação:

• onde é a média do atributo, m4 é o quarto momento central do atributo, e s2 é a variância de x.


59

3.2.3 Medidas resumo: Posição relativa• Um escore z, ou escore padronizado, pode ser

encontrado convertendo-se um valor para uma escala padronizada e corresponde ao número de desvios padrões a que se situa determinado valor de x acima ou abaixo da média:


60

3.2.3 Medidas resumo: Posição relativa• Os quantis correspondem a pontos tomados em intervalos

regulares da distribuição de frequência cumulativa de um atributo.• Primeiro quartil (Q1): separa os 25% menores valores ordenados

dos demais 75%.• Segundo quartil (Q2): separa os 50% menores valores ordenados

dos demais 50%, ou seja, é o mesmo que a mediana.• Terceiro quartil (Q3): separa os 75% menores valores ordenados dos

demais 25%.


61

3.2.3 Medidas resumo: Posição relativa


62

3.2.3 Medidas resumo: Associação


63



64



65


Capítulo 4Análise de Grupos

Leandro Nunes de CastroDaniel Gomes Ferrari


67

Sumário• Introdução• O processo de agrupamento de dados• Medidas de similaridade• Métodos de agrupamento• Representação dos grupos• Avaliação do agrupamento

• Algoritmos de agrupamento• Algoritmo K-Médias• DBSCAN• Single-Linkage


68

4.1 Introdução• Uma das habilidades mais básicas dos organismos vivos é a

capacidade de agrupar objetos similares para produzir uma taxonomia, uma classificação, ou um agrupamento.

• Análise de grupos, também conhecida como agrupamento de dados, é um termo genérico usado para designar um amplo espectro de métodos numéricos de análise de dados multivariados com o objetivo de descobrir grupos homogêneos de objetos.

• A análise de grupos pode ser definida como a organização de um conjunto de objetos (normalmente representados por vetores de características, ou seja, pontos em um espaço multidimensional) em grupos baseada na similaridade entre eles.

• Intuitivamente, objetos pertencentes ao mesmo grupo são mais similares entre si do que a objetos pertencentes a grupos distintos.


69

4.2 O processo de agrupamento de dados


70

4.2.1 Medidas de similaridade• Os métodos de agrupamento visam agrupar objetos

similares entre si e dissimilares a objetos pertencentes a outros grupos.• É necessária uma medida de similaridade

(proximidade) ou dissimilaridade (distância) entre objetos, que será utilizada durante o agrupamento.• A matriz de dissimilaridade ou distância, D, com

dimensão n n, D nn, onde cada elemento da matriz corresponde a uma medida quantitativa da proximidade (ou equivalentemente da distância d(i,j) ou dij) entre pares de objetos:


71

4.2.1.2 Medidas de similaridade para dados binários• O tipo mais comum de dados categóricos ocorre

quando todas as variáveis são binárias e a medida de distância mais comumente utilizada para este tipo de dado é a chamada distância Hamming (H):


72

• Uma forma de calcular a dissimilaridade dij entre dois objetos i e j é fazendo uma comparação simples atributo a atributo:

• onde M é o número de casamentos (do inglês matches, ou seja, de atributos para os quais i e j possuem o mesmo valor) e m é o número total de atributos.

4.2.1.3 Medidas de similaridade para dados nominais


73

4.2.1.6 Medidas de similaridade para dados contínuos


74

4.2.1.6 Medidas de similaridade para dados contínuos


75

4.2.1.6 Medidas de similaridade para dados contínuos: distância Euclidiana• A distância Euclidiana (D1), também conhecida

como a norma l2, é a mais comumente utilizada, pois possui a propriedade de representar a distância física entre pontos em um espaço m-dimensional. • A Tabela 4.14 apresenta uma amostra da base de

dados Ruspini. A distância Euclidiana entre os objetos é calculada da seguinte forma:


76

4.2.2 Métodos de agrupamento• De forma abrangente os métodos de agrupamento podem ser divididos em:

• Hierárquicos: os métodos hierárquicos criam uma decomposição hierárquica dos dados. Estes métodos podem ser aglomerativos ou divisivos, baseado em como o processo de decomposição é efetuado. • Os métodos aglomerativos começam com cada objeto pertencendo a um grupo e unem

sucessivamente objetos em grupos de acordo com a proximidade entre eles até que um critério de parada seja atingido.

• Os métodos divisivos começam com todos os objetos fazendo parte do mesmo grupo e particionam sucessivamente os grupos em grupos menores, até que um critério de parada seja atingido.

• Particionais: dado um conjunto com n objetos, um método particional constrói k partições dos dados, sendo que cada partição representa um cluster (k n).

• Não exclusivos (tradução livre do inglês overlapping): dado um conjunto com n objetos, os métodos não exclusivos permitem que um objeto pertença completamente (métodos conhecidos como soft) ou parcialmente (métodos conhecidos como fuzzy) a mais de um grupo simultaneamente.


77

4.2.3 Representação dos grupos• Protótipos: correspondem a vetores representativos dos grupos, por exemplo, um

centroide (ponto médio) de um grupo.• Estruturas em grafo: neste contexto um grafo é um conjunto de nós e arcos no qual

os nós correspondem aos objetos da base e os arcos às conexões entre eles. Pode-se dizer que objetos conectados entre si formam um grupo, que corresponde a um subgrafo e, portanto, cada subgrafo representa um grupo e o conjunto de todos os subgrafos forma o grafo com todo o agrupamento proposto.

• Estruturas em árvore: esse tipo de estrutura, como os dendrogramas, é um caso particular dos grafos que fornece uma representação hierárquica das relações entre os objetos e os grupos encontrados. Em uma estrutura em árvore normalmente se escolhe um ponto da árvore para se realizar a partição dos grupos.

• Rotulação: há casos em que não se usa uma representação explícita dos grupos. Em vez disso, os objetos da base são simplesmente rotulados de forma a identificar a qual grupo cada objeto pertence. • No caso da base Ruspini, os objetos de 1 a 20 receberiam o rótulo de grupo 1 (ou A), os

objetos 21 a 35 receberiam o rótulo 2 (ou B), os objetos 36 a 58 receberiam o rótulo 3 (ou C), e os objetos de 59 a 75 o rótulo 4 (ou D), como apresentado na Tabela 4.2.


78

4.2.3 Representação dos grupos


79

4.2.4 Avaliação do agrupamento• As medidas de avaliação de desempenho, também conhecidas como índices de

avaliação, são responsáveis por aferir quantitativamente o agrupamento resultante de um algoritmo para uma base de dados.

• Existem dois critérios para avaliação e seleção de um agrupamento de qualidade:• Compactação: os objetos de cada grupo devem estar o mais próximo possível um dos

outros. As medidas utilizadas para calcular a compactação de um grupo são geralmente denominadas de intragrupo.

• Separação: os grupos devem estar o mais distante possível uns dos outros. As medidas para cálculo da separação entre grupos são normalmente denominadas intergrupos.

• Os grupos formados pelos objetos de uma base de dados podem ser avaliados por dois tipos de medidas:• Internas: são medidas que utilizam apenas informações intrínsecas aos objetos do

agrupamento, baseando-se em medidas de similaridade e avaliando as distâncias intragrupos e/ou intergrupos.

• Externas: são medidas que avaliam o quão correto está um agrupamento dado um agrupamento ideal que se deseja alcançar. O cálculo dessas medidas requer o conhecimento prévio do grupo ao qual cada objeto pertence.


80

4.2.4.1 Medidas internas• Índice de Dunn

• O índice proposto por Dunn utiliza medidas intragrupo e intergrupos para determinar a compactação e separação do agrupamento.

• O índice tem valores melhores para agrupamentos nos quais os grupos são mais coesos e bem separados, dado pela razão entre as distâncias intra- e intergrupos.

• O índice de Dunn, DU, assume valores no intervalo [0;∞], sendo que, quanto maior o valor, melhor é o agrupamento correspondentes, deve ser maximizado e é calculado como:

• onde g é o agrupamento resultante; k é o número de grupos; gi, gj, gl são grupos da base de dados; e Intra(.) e Inter(.) são as medidas intragrupo e intergrupo, respectivamente.

• onde |gi| e |gj| é a quantidade de objetos nos grupos i e j, respectivamente; x e y são objetos da base; e d(x,y) é a distância entre os objetos.


81

4.2.4.2 Medidas externas• Entropia

• A entropia define a homogeneidade dos grupos encontrados, ou seja, de que forma as classes dos objetos estão distribuídas nos grupos, sendo que baixa entropia indica grupos mais homogêneos. Dado um determinado grupo obtido gi de tamanho ni, a entropia E(gi) deste grupo pode ser medida da seguinte forma:

• onde r é o número de classes, e nij é o número de objetos com a j-ésima classe que estão presentes no grupo gi.

• A entropia global pode então ser calculada como o somatório das entropias calculadas para cada grupo, ponderada pelo tamanho de cada grupo, da seguinte forma:

• Uma solução de agrupamento próxima da ideal será aquela que apresenta objetos de uma única classe dentro de cada grupo, fazendo com que a entropia global seja igual à zero.


82

4.2.4.2 Medidas externas• Pureza

• A pureza fornece a razão da classe dominante no grupo em relação ao tamanho do próprio grupo e pode ser calculada da seguinte maneira:

• Analogamente ao cálculo da entropia global, a pureza global pode ser calculada por:

• Cada grupo obtido pode conter objetos de diferentes classes. Valores de pureza próximos a 1 indicam um subconjunto puro da classe dominante no grupo obtido.


83

4.3.1 Algoritmo k-Médias• O algoritmo k-Médias toma como entrada o parâmetro k, correspondente ao número

de grupos desejados, e particiona o conjunto de n objetos em k grupos, de forma que a similaridade intragrupo seja alta e a similaridade intergrupo seja baixa.

• A similaridade intragrupo é avaliada considerando o valor médio dos objetos em um grupo, que pode ser visto como o seu centro de gravidade ou o centroide. No particionamento realizado pelo k-médias, cada objeto pertence ao grupo do centroide mais próximo a ele.

• O algoritmo padrão do k-Médias opera por meio de uma técnica de refinamento iterativo da seguinte forma:• os k centroides iniciais dos grupos são determinados aleatoriamente ou selecionando

aleatoriamente alguns dos objetos da própria base de dados;• calcula-se a distância entre os objetos da base e cada um dos centroides e atribui-se cada

objeto ao centroide mais próximo; • os novos centroides são calculados tomando-se a média dos objetos pertencentes a cada

centroide, o que pode promover um reposicionamento dos centroides e uma nova alocação de objetos a grupos;

• O algoritmo o converge quando não há mais alterações nos centroides e mudanças nas alocações de objetos aos grupos.


84

Exemplo: k-Médias•A alocação iterativa de cada objeto ao grupo cujo centroide está mais próximo a ele juntamente com a atualização dos valores dos centroides é equivalente a um processo iterativo de otimização de uma função de custo que calcula a soma dos erros quadráticos intragrupos, ou seja, a soma da distância de cada objeto ao centroide do grupo ao qual pertence:

•onde fc é a função de custo da base, x é um objeto qualquer da base, ci é o centroide do grupo gi, e d(x,ci) é a distância entre o objeto e o centroide do grupo.


85

4.3.5 DBSCAN• O algoritmo DBSCAN (do inglês Density Based Spatial Clustering of Applications with

Noise) foi desenvolvido para encontrar agrupamentos de diferentes formatos, e ruído nas bases de dados, baseando-se na densidade de objetos no espaço.

• A noção de densidade está relacionada à quantidade de objetos dentro de um raio de vizinhança (ε), sendo que a vizinhança de um objeto pode ser definida como:

• onde x e y são objetos da base de dados; e d(x,y) é a distância entre os objetos.• O número de grupos é definido automaticamente pelo algoritmo, sendo que cada

grupo possui pelo menos um objeto de núcleo. • O objeto de núcleo é definido como um objeto com uma quantidade mínima

(minPts) de objetos em seu raio de vizinhança. • O grupo é formando agregando os objetos da vizinhança do objeto de núcleo.

Partindo dos novos objetos adicionados seus vizinhos também serão agregados ao grupo, até que não haja mais objetos na vizinhança.


86

Exemplo: DBSCAN


87

Exemplo: DBSCAN


88

Exemplo: DBSCAN


89

4.3.6 Single-Linkage• É um método aglomerativo de agrupamento hierárquico no qual novos

grupos são criados unindo os grupos mais semelhantes. • O agrupamento inicial é formado apenas por singletons e a cada iteração do

método um novo grupo é formado por meio da união dos dois grupos mais similares da iteração anterior.

• Neste método a distância (proximidade) entre o novo grupo aos demais é determinada como a menor distância entre os elementos do novo grupo e os grupos remanescentes.

• Matematicamente, a função de ligação, a distância D(g1,g2) entre os grupos g1 e g2, é descrita pela expressão:

• onde d(x,y) é a distância entre os elementos x e y, e g1 e g2 são dois grupos.


90

Exemplo: Single-Linkage


91

Exemplo: Single-Linkage

Capítulo 5Classificação de




93

Sumário• Introdução• O processo de predição de dados• Validação cruzada como estimativa de desempenho• Avaliação de desempenho

• Algoritmos de classificação• Classificador K-NN• Árvores de decisão• Classificador Naïve Bayes


94

5.1 Introdução• Muitos problemas práticos possuem registros históricos relacionando

situações específicas com determinados resultados. Por exemplo:• administradoras de cartões de crédito possuem registros de transações

passadas e a informação se foram fraudulentas ou não.• empresas possuem registros de funcionários com seu perfil e desempenho no

trabalho.

• Quando cada registro possui um rótulo de classe ou um valor de saída associado que representa o resultado histórico de registros passados, o objetivo da análise é, quase invariavelmente, construir um modelo que possa ser usado para predizer qual seria essa saída para novos registros, ou seja, registros cuja classe ou valor de saída é desconhecido.

• Esse tipo de tarefa é chamado genericamente de predição e pode ser de dois tipos: discreta, denominada classificação; ou contínua, denominada estimação.


95

5.1 Introdução• Dois tipos importantes de erro são importantes em aprendizagem supervisionada :

• Erro de Representação: considere o caso em que todo o conjunto amostral está disponível e, também, que a base de dados completa permita encontrar um conjunto ótimo de parâmetros do modelo. Neste caso, o erro vai depender da adequação e do nível de flexibilidade do modelo preditivo em relação aos dados de treinamento, pois nem sempre ele é suficientemente adequado para representar os dados. Este erro é também conhecido como erro de aproximação, ou efeito bias.

• Erro de Generalização: em aplicações de mundo real, somente um número finito de dados (uma amostra da base) está disponível ou pode ser usado simultaneamente para análise. Além disso, os dados podem conter ruído ou outras inconsistências. Portanto, a resposta de um algoritmo para dados não usados no treinamento precisa ser aproximada. Devido a estes fatores pode ocorrer um erro de generalização, também conhecido como erro de estimação, ou variância, mesmo quando técnicas de pré-processamento de dados são bem aplicadas. Esse erro surge, por exemplo, quando o modelo é treinado em excesso e absorve os ruídos dos dados de treinamento, sofrendo de uma sobregeneralização dos resultados.


96

5.1 Introdução


97

5.2 O processo de predição de dados


98

5.2 O processo de predição de dados• Separação dos dados em conjuntos de treinamento e de teste

• uma parte dos dados disponíveis é usada na geração do modelo preditivo (conjunto de treinamento), enquanto a outra parte é usada para avaliar a qualidade do modelo gerado (conjunto de teste).

• Treinamento e teste• o treinamento consiste em usar os dados de treinamento para ajustar

os parâmetros livres do modelo, de tal forma que o seu desempenho atinja um determinado nível de qualidade, avaliado pela aplicação do modelo gerado aos dados de teste.

• O teste consiste em avaliar o desempenho o modelo quando aplicado a dados não usados no processo de treinamento. O desempenho do modelo, quando aplicado a dados de teste, oferece uma estimativa de sua capacidade de generalização, ou seja, sua capacidade de responder corretamente a dados não usados no processo de treinamento.


99

5.2.1 Validação cruzada como estimativa de desempenho• O objetivo da validação cruzada é, de forma sistemática, particionar a

base de dados em conjuntos de treinamento e teste.• Em cada rodada da validação cruzada é gerado um conjunto de

treinamento e um de teste, sendo que múltiplas rodadas são normalmente executadas para reduzir a variabilidade nos resultados e de maneira a permitir que todos os dados sejam usados para treinamento e teste, mas em diferentes rodadas.

• Uma forma bastante comum de validação cruzada em mineração de dados é a chamada validação cruzada em k-pastas (k-fold cross-validation), que consiste em dividir a base de dados em k subconjuntos, sendo k1 pastas para treinamento e 1 pasta para teste.

• Esse processo de treinamento e teste é repetido com todos os k subconjuntos, e a média dos desempenhos para as bases de treinamento e as bases de teste é adotada como indicador de qualidade do modelo.


100

5.2.1 Validação cruzada como estimativa de desempenho


101

5.2.2 Avaliação de desempenho• O desempenho do classificador depende fortemente de sua

flexibilidade (bias) e da qualidade de seu treinamento (variância).• Entretanto, não existe um classificador que seja melhor que todos

os outros para todos os problemas de classificação.• As medidas de avaliação de desempenho de classificadores

normalmente trazem informações sobre algum tipo de taxa de acerto ou de erro do classificador para um ou mais conjuntos de dados.

• A forma mais comum de avaliar o desempenho de um classificador é simplesmente calcular o percentual de classificação correta, também conhecido como acurácia (preditiva), ou seu complemento, o percentual de classificação incorreta.


102

5.2.2 Avaliação de desempenho: Classificação binária• Geralmente, nos problemas de classificação binária existe uma classe alvo,

ou seja, a classe cujo valor se deseja predizer. Por exemplo, na classificação de spam, a classe alvo é spam. Essa classe alvo é também chamada de classe positiva e, consequentemente, leva ao surgimento da classe negativa.

• As classes positiva e negativa permitem a definição de medidas específicas relacionadas a cada uma delas:• VP (verdadeiro positivo): objeto da classe positiva classificado como positivo – por

exemplo, um spam classificado como spam.• VN (verdadeiro negativo): objeto da classe negativa classificado como negativo –

por exemplo, uma mensagem normal classificada como normal.• FP (falso positivo): objeto da classe negativa classificado como positivo – por

exemplo, uma mensagem normal classificada como spam. É também conhecido como alarme falso ou Erro Tipo 1;

• FN (falso negativo): objeto da classe positiva classificado como negativo – por exemplo, spam classificado como mensagem normal. É também conhecido como Erro Tipo 2.


103

5.2.2 Avaliação de desempenho: Classificação binária


104

5.2.2 Avaliação de desempenho: Classificação binária• Com base nos valores apresentados na matriz de confusão do problema

binário, introduzem-se duas importantes taxas, normalmente expressas em valores percentuais: a taxa de verdadeiros positivos (TVP) e a taxa de falsos positivos (TFP):

• A taxa de verdadeiros positivos corresponde ao percentual de objetos positivos classificados corretamente, ao passo que a taxa de falsos positivos corresponde ao percentual de objetos negativos classificados como positivos.

• A taxa global de sucesso do algoritmo, conhecida como acurácia (ACC), é o número de classificações corretas dividido pelo número total de classificações:


105

5.2.2 Avaliação de desempenho:Curva ROC


106

5.2.2 Avaliação de desempenho: Múltiplas classes


107

5.3.1 Classificador k-NN• O método dos k-vizinhos mais próximos (k-nearest neighbors – k-NN)

é um dos classificadores não paramétricos baseados em distância mais simples e conhecidos da literatura.

• O k-NN opera da seguinte maneira: • dado um objeto x0 cuja classe se deseja inferir, • encontram-se os k objetos xi, i = 1, ... , k da base que estejam mais próximos

a x0 e, depois, • se classifica o objeto x0 como pertencente à classe da maioria dos k vizinhos. • Empates são decididos aleatoriamente.

• Apesar da simplicidade, o método k-NN apresenta bons resultados em diversos cenários e normalmente se comporta bem quando cada classe possui diversos objetos e a superfície de decisão é irregular.


108

5.3.2 Árvores de decisão• Uma árvore de decisão (decision tree) é uma estrutura em forma de

árvore na qual cada nó interno corresponde a um teste de um atributo, cada ramo representa um resultado do teste e os nós folhas representam classes ou distribuições de classes. O nó mais elevado da árvore é conhecido como nó raiz, e cada caminho da raiz até um nó folha corresponde a uma regra de classificação.

• Uma vez construída a árvore, ela pode ser usada para classificar um objeto de classe desconhecida. Para isso, basta testar os valores dos atributos na árvore e percorrê-la até se atingir um nó folha, que corresponde à classe predita para aquele objeto.

• As árvores de decisão possuem as vantagens de serem normalmente concisas, de fácil visualização e compreensão.


109

5.3.2 Árvores de decisão• A tarefa de indução de árvores de decisão corresponde ao

processo de construção da árvore de forma que ela possa ser usada para determinar a classe de um novo objeto a partir dos valores de seus atributos.

• A indução de uma árvore de decisão pode ser expressa recursivamente:• Selecione um atributo, coloque-o na raiz da árvore e faça uma

ramificação para cada valor possível, o que divide a base de dados em subconjuntos (um para cada valor do atributo);

• Repita o processo recursivamente para cada ramo, usando somente aqueles objetos que alcançam o ramo;

• Se todos os objetos em um nó possuem a mesma classificação, pare de desenvolver essa parte da árvore.


110

5.3.2 Árvores de decisãoExemplo


111

5.3.5 Classificador Naïve Bayes• Classificadores bayesianos são classificadores estatísticos

fundamentados no Teorema de Bayes e usados para predizer a probabilidade de pertinência de um objeto a uma determinada classe.

• Estudos indicam que os algoritmos simples de classificação bayesiana, conhecidos como naïve Bayes, possuem desempenho comparável a redes neurais artificiais e árvores de decisão para alguns problemas.

• Eles também apresentam alta acurácia e velocidade de processamento quando aplicados a grandes bases de dados.

• Os classificadores naïve Bayes assumem que o efeito do valor de um atributo em uma dada classe é independente dos valores dos outros atributos. Essa premissa, denominada independência condicional da classe tem como objetivo simplificar os cálculos e, por causa dela, o algoritmo é denominado naïve.

Capítulo 6Estimação



113

Sumário• Introdução• Avaliação de desempenho

• Algoritmos de estimação• Regressão Linear• Regressão Polinomial• Rede neural do tipo Adaline• Rede neural do tipo Multi-layer Perceptron


114

6.1 Introdução• A tarefa de predizer um valor contínuo de uma variável dá-se o nome de

estimação, a qual também é do tipo aprendizagem supervisionada e, portanto, requer pares entrada-saída desejada para a construção do estimador e possui muitas características e processos em comum com a classificação.

• A preparação da base de dados, a separação dos dados em treinamento e teste, a definição dos critérios de parada do algoritmo e o treinamento e teste são feitos de forma equivalente.

• Uma diferença importante entre essas tarefas, entretanto, encontra-se na avaliação da saída. • No caso dos classificadores, essa avaliação é baseada em alguma medida de

acurácia do classificador, ou seja, a quantidade de objetos classificados corretamente.

• No caso dos estimadores, a qualidade é normalmente medida calculando-se uma distância ou erro entre a saída do estimador e a saída desejada.


115

6.1.1 Avaliação de desempenho• A saída de um estimador é um valor numérico contínuo que deve ser

o mais próximo possível do valor desejado, e a diferença entre esses valores fornece uma medida de erro de estimação do algoritmo.

• Considere a seguinte formalização do processo de aprendizagem supervisionada:• Seja dj, j = 1, ... e n, a resposta desejada para o objeto j e yj a resposta

estimada (predita) do algoritmo, obtida a partir de uma entrada xj apresentada ao algoritmo.

• O conjunto {(xj,dj)}j = 1,...,n, onde xj e dj j são os vetores de entrada e as respectivas saídas desejadas, é formado pelos pares estímulo-resposta (ou entrada-saída) apresentados ao algoritmo, possivelmente extraídos de um ambiente ruidoso cujas distribuições de probabilidade são desconhecidas.

• Assim, ej = dj yj é o sinal de erro observado na saída do sistema para o objeto j.


116

6.1.1 Avaliação de desempenho


117

6.2.1 Regressão linear• A regressão modela a relação entre uma ou mais

variáveis de resposta e os preditores. • Em linhas gerais, regressão corresponde ao

problema de estimar uma função a partir de pares entrada-saída e, se há mais de uma variável de resposta, a regressão é chamada de multivariada.• Os modelos de regressão linear são métodos

estatísticos capazes de modelar a relação entre uma variável dependente e uma ou mais variáveis independentes.


118

6.2.1 Regressão linear


119

6.2.2 Regressão polinomial• A regressão polinomial é um modelo de regressão

no qual a relação entre as variáveis independentes e a variável dependente pode ser não linear e tem a forma de um polinômio de grau n.• Assim, embora o polinômio de aproximação seja

não linear, o problema de estimação dos parâmetros do modelo é linear e o método também é considerado uma forma de regressão linear.


120

6.2.3 Rede neural do tipo Adaline• Rosenblatt introduziu o Perceptron como a arquitetura mais

simples de rede neural capaz de classificar padrões linearmente separáveis.• Praticamente ao mesmo tempo, Widrow e Hoff

desenvolveram o algoritmo dos quadrados mínimos ou regra delta, mecanismo central na derivação do algoritmo de treinamento de uma rede neural simples com saída linear.• Eles introduziram a rede Adaline (Adaptive Linear Element),

muito similar ao Perceptron, porém com neurônios usando função de ativação linear em vez de função sinal.


121

6.2.3 Rede neural do tipo Adaline


122

6.2.3 Rede neural do tipo Multi-layer Perceptron

• O Perceptron de múltiplas camadas (multi-layer Perceptron – MLP) é uma rede do tipo Perceptron com pelo menos uma camada intermediária. Trata-se de uma generalização do Perceptron simples e da rede Adaline.

• O treinamento da rede MLP foi feito originalmente utilizando-se um algoritmo denominado retropropagação do erro, conhecido como backpropagation, que ganhou notoriedade com o trabalho de Rumelhart e McLelland.

• Esse algoritmo consiste basicamente em dois passos: • propagação positiva do sinal funcional, durante a qual todos os pesos

da rede são mantidos fixos; e • retropropagação do erro, durante a qual os pesos da rede são

ajustados com base no erro.


123



124


• Uma rede MLP típica possui três características principais:• os neurônios das camadas intermediárias (e de saída)

possuem uma função de ativação não linear do tipo sigmoidal • a rede possui uma ou mais camadas intermediárias• a rede possui altos graus de conectividade

• Uma rede neural do tipo MLP pode ser vista como uma ferramenta prática geral para fazer um mapeamento não linear de entrada-saída.

Capítulo 7Regras de Associação



126

Sumário• Introdução• Definição do problema

• Processo de mineração de regras de associação• Avaliação de desempenho

• Algoritmos para mineração de regras de associação• Conceitos básicos• Algoritmo Apriori• Algoritmo FP-Growth


127

7.1 Introdução• As bases de dados apresentadas até agora compartilham uma

propriedade comum: todas elas são compostas por um conjunto de objetos caracterizados por um conjunto de características (atributos). • Existe outro tipo de base de dados, muito comum em alguns

ambientes empresariais, que relaciona conjuntos de itens que ocorrem em transações. • Esses dados são muito valiosos para os negócios, pois permitem

que sejam extraídas informações sobre o comportamento de compras de cada cliente, podendo ser usados na realização de promoções e campanhas de marketing, gestão de estoques, definição de catálogos, análise de perdas, relacionamento com clientes e muitas outras ações.


128

7.1 Introdução• O exemplo típico é o do carrinho de supermercado. • Quando alguém vai ao supermercado, faz uma

compra e passa na caixa registradora, as informações de quais produtos foram comprados, a quantidade e os preços pagos ficam armazenados no banco de dados do supermercado. Cada registro desses é chamado de transação e, por isso, tais bases de dados são denominadas transacionais,


129

7.1.1 Definição do problema• Para que seja feita a mineração das regras de

associação, as bases de dados transacionais normalmente são representadas seguindo o mesmo padrão das bases de dados convencionais, ou seja, com os objetos nas linhas e os atributos nas colunas. • A diferença é que os atributos das bases transacionais

são os itens que aparecem nas transações, o que faz com que tais bases de dados facilmente apresentem alta dimensionalidade, da ordem de centenas e até milhares de itens (atributos).


130

7.1.1 Definição do problema• Dado um conjunto de transações, onde cada transação

é composta por um conjunto de itens, uma regra de associação é uma regra X Y, na qual X e Y são conjuntos de itens.• O significado intuitivo de uma regra de associação é

que as transações em uma base de dados que contêm itens em X também contêm itens em Y. • Assim, as regras de associação podem ser vistas como

padrões descritivos que representam a probabilidade de que um conjunto de itens apareça em uma transação, dado que outro conjunto está presente.


131

7.1.1 Definição do problema• Como uma grande quantidade de regras de associação pode

ser derivada a partir de uma base de dados, mesmo que pequena, normalmente se objetiva a derivação de regras que suportem um grande número de transações e que possuam uma confiança razoável para as transações às quais elas são aplicáveis. • Suporte: o suporte, ou cobertura, de uma regra de associação é o

número de transações para as quais ela faz a predição correta. Também pode ser entendida como a utilidade de uma dada regra.

• Confiança: a confiança, ou acurácia, de uma regra é o número de transações que ela prediz corretamente proporcionalmente às transações para as quais ela se aplica. Também pode ser entendida como a certeza de uma dada regra.


132

7.2 Processo de mineração de regras de associação


133

7.2.1 Avaliação de desempenho• Regras que envolvem itens mutuamente exclusivos ou que cubram

um número muito pequeno de transações são pouco relevantes.• Suporte

• O suporte, ou cobertura, de uma regra é uma medida importante, pois regras com valores muito baixos de suporte ocorrem apenas ocasionalmente.

• O suporte de uma regra de associação, A → C, indica a frequência de ocorrência da regra:

• onde (AB) é a contagem do suporte da regra, que corresponde ao número de transações que contêm um determinado conjunto de itens, e n é o número total de transações da base.


134

7.2.1 Avaliação de desempenho• Confiança

• A confiança, também chamada de acurácia, verifica a ocorrência da parte consequente da regra em relação ao antecedente, determinando o grau de confiança entre os itens, ou seja, aquilo que os une formando a regra de associação:

• onde (A) é a contagem do suporte do antecedente da regra.

• Enquanto a confiança é uma medida da acurácia da regra, o suporte corresponde à sua significância estatística.

• Juntas, essas são as medidas de interesse mais usadas na literatura de mineração de regras de associação.


135

7.3 Algoritmos para mineração de regras de associação: Conceitos básicos

• Conjunto de itens: = {i1, i2, ... , im}; • Conjunto de transações da base de dados: T = {t1, t2,..., tN}, no qual cada

transação ti é um conjunto de itens tal que ti ; • Conjunto com k itens: a frequência de ocorrência de um conjunto de itens é

conhecida por contagem do suporte ou contagem do conjunto de itens, e corresponde ao número de transações que contêm o conjunto de itens.

• Conjunto de itens frequentes de tamanho k: os itens frequentes com suporte maior que o mínimo, minsup, formam o conjunto Fk.

• Padrão frequente: um conjunto-k é chamado de padrão frequente se seu suporte for maior ou igual ao minsup.

• Conjunto de itens candidatos de tamanho k: o conjunto de itens potencialmente frequentes é denominado Ck.

• Contagem do suporte mínimo: número de transações necessárias para que o conjunto de itens satisfaça o suporte mínimo.


136

7.3.1 Algoritmo Apriori• Uma estratégia comum adotada pelos algoritmos de mineração de regras

de associação consiste em decompor o problema em duas subtarefas:• Geração do conjunto de itens frequentes: encontre todos os conjuntos de itens

frequentes, ou seja, aqueles cujo suporte seja maior que o minsup especificado.• Geração das regras: use os conjuntos de itens frequentes para gerar as regras

desejadas. A ideia geral é que se, por exemplo, ABCD e AB são frequentes, então é possível determinar se a regra AB CD é válida calculando a razão confiança = suporte(ABCD)/suporte(AB). Se a confiança for maior ou igual a minconf, então a regra é válida.

• O algoritmo Apriori é o método mais conhecido para a mineração de regras de associação e emprega busca em profundidade e gera conjuntos de itens candidatos de k elementos a partir de conjuntos de itens com k 1 elementos.


137

7.3.1 Algoritmo Apriori


138

7.3.3 Algoritmo FP-Growth• O algoritmo Apriori pode sofrer dois problemas:

• dificuldade para tratar uma grande quantidade de conjuntos candidatos,

• execução de repetidas passagens pela base de dados.

• Para mitigar tais problemas o algoritmo FP-Growth (Frequent Pattern Growth) é baseado em uma estrutura em árvore de prefixos para os padrões frequentes, denominada FP-Tree (Frequent Pattern Tree), a qual armazena de forma comprimida a informação sobre os padrões frequentes. • O algoritmo FP-Growth extrai o conjunto completo de

padrões frequentes.


139

7.3.3 Algoritmo FP-Growth• A essência do algoritmo proposto está baseada em três

aspectos centrais: • A compressão da base de dados em uma estrutura em árvore

(FP-Tree) cujos nós possuem apenas itens frequentes de comprimento unitário (F1) e organizada de modo que aqueles nós que ocorrem mais frequentemente terão maiores chances de compartilhar nós do que os de baixa frequência.

• O uso de um algoritmo de mineração da árvore que evita a geração de uma grande quantidade de conjuntos candidatos.

• O uso de um método particional para decompor a tarefa de mineração em subtarefas menores, reduzindo significativamente o espaço de busca.


140

7.3.3 Algoritmo FP-Growth


141



142


Capítulo 8Detecção de Anomalias



144

Sumário• Introdução• Processo de detecção de anomalias• Abordagens para detecção de anomalias• Avaliação de desempenho

• Métodos estatísticos• Métodos paramétricos• Métodos não paramétricos

• Métodos algorítmicos• Métodos baseados em proximidade


145

8.1 Introdução• A detecção de anomalias tem sido usada há séculos para detectar e,

quando apropriado, executar alguma tomada de decisão sobre objetos anômalos da base de dados.

• Várias nomenclaturas são usadas quase indistintamente para detecção de anomalias, como detecção de novidades, detecção de ruídos, detecção de desvios, detecção de falhas, detecção de exceções, e mineração de exceções.

• O que é uma anomalia (outlier):• Uma anomalia é um objeto que parece desviar fortemente de outros

membros da amostra a qual ele pertence• Uma anomalia é um objeto ou subconjunto de objetos que parece

inconsistente com o restante da base de dados• Anomalias são padrões nos dados que não estão de acordo com uma

noção bem definida de comportamento normal


146

8.1 Introdução• A importância da detecção de anomalias deve-se ao fato de que

elas normalmente correspondem a dados significativos, às vezes críticos, para a análise.

• Por exemplo, uma fraude em uma transação de cartão de crédito, um intruso em uma rede de computadores ou uma falha na operação de uma turbina de avião, todas essas anomalias causam algum tipo de prejuízo, risco ou dano ao sistema.

• As principais aplicações de detecção de anomalias incluem: • Detecção de fraudes: em transações de cartões de crédito, em uso de

telefones celulares, em medição de consumo de energia.• Análise de crédito: identificação de clientes potencialmente

problemáticos, inadimplentes ou fraudulentos.• Análise de textos: identificação de novas estórias, riscos, situações .


147

8.2 Processo de detecção de anomalias


148

8.2.1 Abordagens para detecção de anomalias• Há duas abordagens principais para detecção de anomalias:

• Tipo 1 – não supervisionada: nesta categoria, não se assume nenhuma premissa sobre o rótulo dos dados, ou seja, as anomalias devem ser identificadas sem conhecimento prévio das classes normal e anômala. Há duas abordagens do Tipo 1 comumente empregadas:• Diagnóstico: uma vez detectadas as anomalias, o sistema as remove da base e

readéqua o modelo ao restante dos dados até que não sobrem anomalias.• Acomodação: esta metodologia incorpora as anomalias ao modelo gerado e,

posteriormente, emprega um método robusto de classificação, induzindo uma fronteira de normalidade ao redor da maioria dos dados que representam o comportamento normal

• Tipo 2 – Supervisionada: tanto os objetos normais quanto as anomalias são modelados, assim como os métodos de classificação baseada em aprendizagem supervisionada, e, em muitos casos, a classe normal é subdividida em várias classes para melhorar a acurácia de classificação


149

8.2.3 Avaliação de desempenho• A tarefa de detecção de anomalias é um caso

particular de problema de classificação binária• A quantidade de objetos da classe alvo (anomalia) é

muito inferior à quantidade de objetos da classe normal • O custo da não detecção de uma anomalia (falso

negativo) é normalmente muito maior do que identificar um objeto normal como uma anomalia (falso positivo).


150

8.3 Métodos estatísticos• Os métodos estatísticos para detecção de

anomalias normalmente geram um modelo probabilístico dos dados e testam se determinado objeto foi gerado por tal modelo ou não.• Se a probabilidade de certo objeto ter sido gerado

por este modelo for muito baixa, então ele é rotulado como uma anomalia.• Os métodos estatísticos foram os primeiros a serem

utilizados para detecção de anomalias e muitos deles operam com dados unidimensionais


151

8.3.1 Métodos paramétricos• Os métodos paramétricos assumem que os dados

são gerados por uma distribuição conhecida.• A fase de treinamento envolve estimar os

parâmetros do modelo para uma base de dados.

• Diagrama de Caixa• Uma das técnicas mais simples para se detectar

anomalias e visualmente indicar as anomalias


152

8.3.1 Métodos paramétricos


153

8.3.2 Métodos não paramétricos• Métodos que não assumem uma distribuição pré-

definida dos dados e nem um modelo específico que deverá ser ajustado aos dados.

• Análise de Histograma• Um dos métodos estatísticos não paramétricos mais

usados.• A técnica funciona por meio da contagem da frequência

de ocorrência dos objetos, e estimar a probabilidade de ocorrência de cada objeto.


154

8.3.2 Métodos não paramétricos


155

8.4 Métodos algorítmicos• Os métodos algorítmicos para detecção de

anomalias são normalmente baseados em algoritmos de mineração de dados.

• Os algoritmos são aplicados às bases de dados e seus resultados são analisados à procura de indícios de objetos anômalos.


156

8.4.1 Métodos baseados em proximidade• Os métodos baseados em proximidade são normalmente

simples de implementar e não assumem premissa alguma sobre a distribuição dos objetos da base.

• O princípio básico da operação desses métodos é o cálculo de alguma medida de similaridade ou distância entre pares de objetos da base.

• O principal problema dos métodos baseados em proximidade é o elevado custo computacional, que depende tanto da dimensionalidade dos dados, m, quanto do número de objetos na base, n: O(m.n2).

Data & Analytics

2016: Introdução à Mineração de Dados: Conceitos Básicos, Algoritmos e Aplicações