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

View
434
Download
5
Category

Data & Analytics

Preview:

Citation preview

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.

1.2 O que é Mineração de Dados?

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

1.2 O que é Mineração de Dados?

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

1.2 O que é Mineração de Dados?

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

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

Capítulo 2Pré-Processamento de

DadosLeandro Nunes de Castro

Daniel Gomes Ferrari

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

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

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

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

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

2.1 Introdução

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

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?

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

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.

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

2.1.1 Tipos de atributos

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

2.2 Processo de preparação da base de dados

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

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.

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

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.

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

2.3.2 Limpeza dos dados: Ruídos

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

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.

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

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

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

2.3.2 Limpeza dos dados: Ruídos

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

2.3.2 Limpeza dos dados: Ruídos

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

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.

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

2.5 Redução de dados

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

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.

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

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.

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

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.

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

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

• Max-Min

• Escore-z

• Escalonamento decimal

• Range interquartil

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

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.

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

Capítulo 3Análise Descritiva de

DadosLeandro Nunes de Castro

Daniel Gomes Ferrari

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

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

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

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.

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

3.2 O processo de ADD

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

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

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

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

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

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

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

3.2.2 Visualização dos dados: Histogramas

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

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

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

3.2.2 Visualização dos dados: Ogiva

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

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

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

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

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

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

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

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.

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

3.2.3 Medidas resumo: Tendência central

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

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.

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

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:

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

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.

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

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:

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

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:

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

3.2.3 Medidas resumo: Dispersão

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

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.

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

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.

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

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:

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

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%.

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

3.2.3 Medidas resumo: Posição relativa

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

3.2.3 Medidas resumo: Associação

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

3.2.3 Medidas resumo: Associação

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

3.2.3 Medidas resumo: Associação

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

3.2.3 Medidas resumo: Associação

Capítulo 4Análise de Grupos

Leandro Nunes de CastroDaniel Gomes Ferrari

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

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

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

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.

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

4.2 O processo de agrupamento de dados

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

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:

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

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):

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

• 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

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

4.2.1.6 Medidas de similaridade para dados contínuos

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

4.2.1.6 Medidas de similaridade para dados contínuos

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

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:

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

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.

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

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.

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

4.2.3 Representação dos grupos

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

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.

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

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.

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

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.

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

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.

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

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.

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

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.

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

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.

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

Exemplo: DBSCAN

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

Exemplo: DBSCAN

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

Exemplo: DBSCAN

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

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.

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

Exemplo: Single-Linkage

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

Exemplo: Single-Linkage

Capítulo 5Classificação de

DadosLeandro Nunes de Castro

Daniel Gomes Ferrari

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

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

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

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.

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

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.

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

5.1 Introdução

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

5.2 O processo de predição de dados

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

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.

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

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.

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

100

5.2.1 Validação cruzada como estimativa de desempenho

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

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.

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

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.

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

103

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

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

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:

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

105

5.2.2 Avaliação de desempenho:Curva ROC

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

106

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

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

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.

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

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.

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

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.

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

110

5.3.2 Árvores de decisãoExemplo

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

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

Leandro Nunes de CastroDaniel Gomes Ferrari

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

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

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

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.

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

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.

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

116

6.1.1 Avaliação de desempenho

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

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.

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

118

6.2.1 Regressão linear

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

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.

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

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.

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

121

6.2.3 Rede neural do tipo Adaline

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

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.

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

123

6.2.3 Rede neural do tipo Multi-layer Perceptron

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

124

6.2.3 Rede neural do tipo Multi-layer Perceptron

• 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

Leandro Nunes de CastroDaniel Gomes Ferrari

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

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

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

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.

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

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,

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

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).

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

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.

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

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.

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

132

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

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

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.

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

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.

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

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.

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

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.

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

137

7.3.1 Algoritmo Apriori

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

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.

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

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.

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

140

7.3.3 Algoritmo FP-Growth

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

141

7.3.3 Algoritmo FP-Growth

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

142

7.3.3 Algoritmo FP-Growth

Capítulo 8Detecção de Anomalias

Leandro Nunes de CastroDaniel Gomes Ferrari

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

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

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

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

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

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 .

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

147

8.2 Processo de detecção de anomalias

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

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

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

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).

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

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

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

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

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

152

8.3.1 Métodos paramétricos

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

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.

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

154

8.3.2 Métodos não paramétricos

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

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.

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

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).

Recommended