Apostila de Mineração de Dados 2016

PONTIFÍCIA UNIVERSIDADE CATÓLICA DE MINAS GERAIS PRÓ-REITORIA DE PESQUISA E PÓS-GRADUAÇÃO

DIRETORIA DE EDUCAÇÃO CONTINUADA

PLANO DE ENSINO

DISCIPLINA: Mineração de Dados

CURSO: Curso de Especialização em Bancos de Dados Curso de Especialização em Business Intelligence

PROF (A): Hugo Bastos de Paula

CARGA HORÁRIA TOTAL (sala de aula + trabalho orientado): 24 h-a

OBJETIVOS: − Capacitar o aluno a realizar atividades de análise de dados com algoritmos de mineração de dados. − Definir critérios para avaliação de ferramentas de mineração de dados. − Possibilitar a análise de um problema com as técnicas estudadas.

MÉTODOS DIDÁTICOS: Aulas expositivas - exposição teórica dos tópicos da disciplina; trabalhos em grupo - aplicação prática dos conceitos; aulas práticas em laboratório - utilização de ferramenta de mineração para elaboração de exercícios e análise de problemas em bases de dados diversas.

EMENTA (Projeto Pedagógico): Apresentação da metodologia para descoberta de conhecimento em banco de dados. Exploração do espaço problema. Exploração do espaço solução. Técnicas de mineração de dados: regras de associação, clusterização, classificação. Algoritmos para mineração de dados. Ferramentas para mineração de dados.

UNIDADES DE ENSINO (Conteúdo Programático): UNIDADES DE ENSINO: HORAS-AULA Unidade 1: Identificação de Padrões 04 h/a 1.1 Contextualização Disciplina . 1.2 O processo de Descoberta de conhecimento em bancos de dados (KDD). 1.3 Preparação, seleção, melhoria e enriquecimento de dados. 1.4 Tipos de dados para mineração 1.5 Identificação de padrões. 1.6 O processo de mineração de dados. Unidade 2: Regras de Associação 04 h/a 2.1 Conjuntos de itens frequentes e regras de associação. 2.2 Algoritmo Apriori. 2.3 Algoritmo FP-Growth. 2.4 Aplicação do algoritmos. 2.5 Avaliação de graus de interesse de regras. Unidade 3: Classificação e predição 06 h/a 3.1 Conceitos de classificação e predição. 3.2 Tipos de algoritmos para classificação. 3.3 Indução por árvore de decisão. 3.4 Outras técnicas de classificação. 3.5 Aplicação e validação de modelos. 3.6 Algoritmos de predição. 3.7 Detalhamento e aplicações.

PONTIFÍCIA UNIVERSIDADE CATÓLICA DE MINAS GERAIS PRÓ-REITORIA DE PESQUISA E PÓS-GRADUAÇÃO

DIRETORIA DE EDUCAÇÃO CONTINUADA

Unidade 4: Clusterização 04 h/a 4.1 Estruturas de dados. 4.2 Medidas de similaridade e de distância. 4.3 Tipos de algoritmos. 4.4 Detalhamento de algoritmos. 4.5 Aplicação. Unidade 5: Detecção de outlier 02 h/a 5.1 Conceitos. 5.2 Algoritmo do DB-outlier. 5.3 Aplicação. Unidade 6: Trabalho Orientado 04 h/a

CRITÉRIOS DE AVALIAÇÃO (itens que serão considerados pelo professor na avaliação na disciplina): − Capacidade do aluno de identificar as diversas classes de problemas de mineração de dados. − Capacidade do aluno de modelar problemas de mineração de dados e preparar os dados para análise. − Aplicação de técnicas de mineração de dados utilizando bases de dados disponíveis (datasets).

TRABALHO ORIENTADO (descrição das atividades extracurriculares): Será desenvolvido um trabalho orientado durante o curso que demandará 4 horas-aula de atividades extraclasse. O trabalho orientado consistirá de um exercício de aplicação de uma técnica de data mining e será acompanhado pelo professor.

DISTRIBUIÇÃO DE PONTOS: 01 Exercícios 60 pontos 02 Trabalho Orientado 40 pontos

REFERÊNCIAS BIBLIOGRÁFICAS (indicação de livros, artigos e periódicos de acordo com o assunto): TAN, Pang-Ning, STEINBACH, Michael, KUMAR, Vipin. Introdução ao Data Mining – Mineração de dados. Ciência Moderna, 2012. ISBN 978-8573937619. HAN, J.W., KAMBER, M., Pei, J. Data Mining: Concepts and Techniques. 3rd edition, Morgan Kaufmann, 2011. ISBN 978-0123814791. KANTARDZIC, M. Data Mining: Concepts, Models, Methods, and Algorithms. 2nd edition, Wiley-IEEE Press, 2011. ISBN 978-0470890455.

Diretoria de Educação Continuada

1

1

MINERAÇÃO DE DADOS

Curso de especialização em Bancos de Dados

Curso de especialização em Business Intelligence

Prof. Hugo de Paula

TRABALHO ORIENTADO

INTRODUÇÃO

O Instituto de Pesquisa Econômica Aplicada (Ipea) é uma fundação pública federal vinculada ao Ministério do Planejamento, Orçamento e Gestão. Suas atividades de pesquisa fornecem suporte técnico e institucional às ações governamentais para a formulação e reformulação de políticas públicas e programas de desenvolvimento brasileiros. Os trabalhos do Ipea são disponibilizados para a sociedade por meio de inúmeras e regulares publicações eletrônicas e impressas, eventos e via programa semanal de TV em canal fechado. O Ipeadata (http://www.ipeadata.gov.br/) provê dados econômicos e financeiros do Brasil em séries anuais, mensais e diárias na mesma unidade monetária. A busca das séries estatísticas pode ser feita por "Palavras-chave" na sua descrição, "Temas" ou assuntos de interesse, "Fontes" de publicação ou pelo "Nível geográfico" para o qual é possível agregar os dados. Os níveis geográficos disponíveis no Ipeadata são município, área metropolitana, micro e mesorregião geográfica, estado, região administrativa (como Amazônia Legal, Sudene, Fome Zero, entre outras), bacia e sub-bacia hidrográfica, grandes regiões. Devido às mudanças no número e área dos municípios ao longo do tempo, os dados municipais são também apresentados de acordo com as áreas mínimas comparáveis (AMC), permitindo análises intertemporais consistentes. O Ipeadata disponibiliza os dados de AMC nos períodos 1872-2000, 1920-2000, 1940-2000, 1960-2000, 1970-2000 e 1991-2000, bem como os arquivos georreferenciados necessários à construção de mapas para cada uma dessas agregações. As unidades de medida são padronizadas e consistentes, sendo as séries em valores nominais e, sempre que possível, expressas em uma mesma moeda - reais (R$) para séries correntes, mil-réis para séries históricas e dólares ou libras esterlinas para séries em moedas estrangeiras - e em valores reais ou deflacionados expressos a preços do período mais recente ou atual, exceto quando há indicação explícita. Para valores em termos reais, utiliza-se geralmente o deflator implícito do PIB em todas as agregações geográficas. Por meio dos recursos disponíveis no Ipeadata, é possível extrair os dados nos vários níveis geográficos em formato de tabelas ou mapas editáveis (em formato JPEG).

http://www.ipeadata.gov.br/

Diretoria de Educação Continuada

2

2

A proposta deste trabalho é aplicar técnicas de mineração de dados e extrair conhecimento das bases do IPEADATA para identificar padrões interessantes que possam ser úteis para a compreensão do cenário brasileiro atual. ATIVIDADES

1- Será utilizada como fonte primária de dados as informações fornecidas, de forma livre e gratuita, pelo Ipeadata (http://www.ipeadata.gov.br/).

2- Cada grupo (máximo 4 componentes) deverá, a partir dessa base de dados, aplicar o processo CRISP-DM, para extrair informação relevante sobre um problema diverso.

3- Poderá ser utilizada qualquer ferramenta de mineração de dados, não sendo necessário se limitar ao uso do RapidMiner.

4- O grupo deverá:

a. Identificar e detalhar o problema que será abordado;

i. Sugere-se que o problema possua escopo bem delimitado, centrado em apenas um tópico e em uma unidade da federação.

ii. Entre os problemas que podem ser abordados estão: previsão de eleição, identificação padrões ou tendências de consumo, caracterização ou previsão de desemprego e renda, produção industrial, etc.

b. Compreender os dados e como eles podem ser utilizados para resolver o problema;

c. Realizar a seleção dos dados relevantes (registros e atributos);

d. Enriquecer e melhorar os dados;

e. Preparar os dados de acordo com os algoritmos;

f. Aplicar os algoritmos de mineração de dados (no mínimo dois);

g. Explicar o motivo e uso de cada técnica;

h. Fazer análise dos resultados.

5- Deve ser entregue o seguinte:

a. Tabelas com os dados pré-processados;

b. Arquivos contendo os códigos utilizados;

c. Documentação contendo:

i. Análise dos dados;

ii. Relatórios dos algoritmos;

iii. Motivos de uso de cada técnica;

iv. Apresentação e análise dos resultados alcançados.

6- Data entrega: 06/06/2016

http://www.ipeadata.gov.br/

Mineração de Dados

Prof. Hugo de Paula

Informações da disciplina

Apresentação da metodologia para descoberta de conhecimentoem banco de dados. Exploração do espaço problema. Exploraçãodo espaço solução. Técnicas de mineração de dados: regras deassociação, clusterização, classificação. Algoritmos paramineração de dados. Ferramentas para mineração de dados.

DISTRIBUIÇÃO DE PONTOS:

– 01 Exercícios 60 pontos

– 02 Apresentação estudo de caso (trabalho orientado) 40 pontos

Bibliografia

TAN, Pang-Ning, STEINBACH, Michael, KUMAR, Vipin. Introdução

ao Data Mining – Mineração de dados. Ciência Moderna, 2012. ISBN 978-8573937619.

HAN, J.W., KAMBER, M., Pei, J. Data Mining: Concepts and Techniques. 3rd edition, Morgan Kaufmann, 2011. ISBN 978-0123814791.

KANTARDZIC, M. Data Mining: Concepts, Models, Methods, and Algorithms. 2nd edition, Wiley-IEEE Press, 2011. ISBN 978-0470890455.

Programa

Unidade 1: Introdução ao KDD e a padrões

Unidade 2: Regras de associação

Unidade 3: Classificação e predição

Unidade 4: Clusterização

Unidade 5: Detecção de outliers

Unidade 6: Conclusão

KDD – Knowledge Discovery in Database

Descoberta de Conhecimento em Bancos de Dados

• Processo não trivial de identificar em grandes conjuntos de dados padrões que sejam validos, novos, úteis e compreensíveis, buscando melhorar o entendimento de um problema ou um procedimento de tomada de decisão.

– Advances in Knowledge Discovery and Data Mining, Fayyad, Piatetsky-Shapiro, Smyth, and Uthurusamy, (Chapter 1), AAAI/MIT Press 1996

Etapas do KDD proposta por Adriaans e Zantinge (1996)

Mineração de Dados

• Data mining (mineração de dados) é a etapa do KDD que consiste no processo de extração de conhecimento de grandes bases de dados, convencionais ou não.

• Utiliza técnicas de inteligência artificial que procuram relações de similaridade ou discordância entre dados.

• Seu objetivo é encontrar, automaticamente, padrões, anomalias e regras com o propósito de transformar dados, aparentemente ocultos, em informações úteis para a tomada de decisão e/ou avaliação de resultados.

– Fernando S. Goulart Júnior & Robson do Nascimento Fidalgo (1998)

Data Mining e Business Intelligence

Aumento do potencialpara apoio à tomadade decisão empresarial Usuário final

Analista de negócios

Analista de dados

DBA

TomadaDe decisão

Apresentação de dadosTécnicas de visualização

Mineração de dadosDescoberta de padrões

Exploração de dados (análises)sumários estatísticos, consultas, relatórios

Pré-processamento/Integração, DW

Fonte dos dadospapel, Arquivos, documentos Web, banco de dados, experimentos científicos

www.kdnuggets.com

www.kdnuggets.com

Etapas do KDD

Análise de necessidades

Tratamento de dados (seleção, limpeza, enriquecimento e codificação)

Mineração de dados

Identificação de padrões

Regras de associação

Classificação e predição

Clusterização

Detecção de outliers

Exibição dos resultados

Etapa inicial: análise de necessidades e definição do problema

Caso 1:– Era uma vez um rei que estava interessado em realizar

casamentos em massa em sua comunidade. Mais de 50.000 pessoas seriam beneficiadas (suponha distribuição igual de homens e mulheres). O Rei solicitou ao Ministro do Interior que fossem identificados todos os (25.000) potenciais pares para o casamento.

Caso 2: – Uma companhia estava tendo boas vendas nos últimos anos. Em

um ano eles observaram que as vendas começaram a cair a cada trimestre. O diretor da empresa queria saber como melhorar as vendas de modo a voltar à tendência de alta de receita anterior.

Etapa inicial: análise de necessidades e definição do problema

Problema: – como limitar o número de variáveis; delimitar escopo → elaboração da

estrutura do DW.

Solução:– Caso 1: pode ser delimitado com casamento baseado em horóscopo.

Nova definição: Identificar todos os casamentos possíveis da população de 50.000 habitantes utilizando compatibilidade por horóscopo.

– Caso 2: pode ser delimitado com alinhamento de variáveis. Por exemplo: redução das vendas está alinhada com redução da produção, baixos estoques?

Nova definição: Análise da disponibilidade de produtos nas lojas que está causando a queda nas vendas.

Etapa inicial: redefinição precisa do problema

Problema:– um problema não pode ser definido com precisão se somente é dado

atenção aos dados que mostram diretamente o problema. É necessário uma análise de fatos e julgamentos.

Fatos:– Circunstâncias que causam diretamente o problema.

Julgamentos:– Observações a serem disputadas ou decididos.

Fatos e Julgamentos

Caso 3: análise de risco para acidente de carro

Imprudência

Efeito de álcool

Excessiva velocidade

Falha mecânica

Qual é o perfil do motorista de cada veículo?

Quais os perfis dos acompanhantes dos veículos?

Violaram alguma lei de trânsito?

Defeito na envoltura

Fora da validade

Produto estragado

Fora de especificação

Quem fabrica a envoltura?

Quem comercializa o produto?

Como o produto foi estocado?

Como o produto é embalado?

Como o produto é transportado?

Caso 4: devolução de Produtos

Etapas do KDD







Clusterização



Seleção: fonte e origem dos dados

Informações limitadasPor exemplo, não se podediagnosticar malária se basede dados de pacientes nãopossuir a contagem deglóbulos vermelhos.

Tipos de dados

Dados discretos podem ser:

– Binomiais / binários:

• Sintoma de febre: sim/não.

• Decisão: Comprou/não comprou.

– Polinomiais/Nominais/Categóricos não ordinais:

• Região: centro, sul, centro-sul, leste, ...

• Setor: limpeza, laticínios, farináceos, cosméticos, ...

– Categóricos ordinais:

• Faixa etária: criança, jovem, adulto, idoso.

• Temperatura: baixa, média-baixa,

Tipos de dados

Dados contínuos podem ser:

– Normalizados: [0..1]

• Capacidade ociosa: 70% ociosa (0.7)

• Andamento da operação: 30% concluída (0.3)

– Não normalizados: [min..max]

• Idade: [0..120] anos

• Temperatura: [10 .. 40] graus celsius

Tratamento dos dados: limpeza, enriquecimento e codificação

Dados omissos

– Podemos tratar dados omissos como:• dados podem ser desconsiderados;

• registros imperfeitos podem ser removidos;

• valores podem ser inferidos a partir de valores conhecidos;

• valores omissos podem ser tratados como valores especiais;

• Valores podem receber valores aproximados por técnicas de probabilidade bayesiana.


Dados ruidosos

– Podem ser inconsistentes, inexatos ou incompletos.• Aplicar técnicas estatísticas para identificar e separar os diferentes

tipos de ruídos.

Pessoa Física Estado Civil Data Nasc. Idade Dependente Escola/Salário Telefone

Zé da Silva Casado 25/07/1966 55 20% (XX) 4368-9668

inconsistente

não identificável

omisso

inexato

incompleto


• Importante identificar como a precisão dos dados está sendo afetada pela omissão e ruído.

Exemplos: – João e Joao podem ser consideradas entradas iguais ou diferentes.

– Diferentes entidades representadas pelo mesmo nome em diferentes sistemas:

• Sistema folha de pagamento: Empregado é quem recebe salário (pode ser terceirizado).

• Sistema de RH: empregado é quem possui número de pessoa.


• Importante garantir padronização e aplicar técnicas estatísticas para analisar consistência dos modelos encontrados.

Exemplos: – Nem todos usam o mesmo formato.

– Datas podem ser especialmente problemáticas:

• 25/12/15

• 25/dez/2015

• 25-12-2015

• 25 de dezembro de 2015

– Preços em moedas diferentes: R$ versus US$• Câmbio pode variar

• Possibilidade: armazenar na moeda de origem e converter no momento da análise


• Campos podem ser irrelevantes, duplicados ou redundantes.– podem produzir conhecimento falso.

– podem aumentar o tempo de execução dos algoritmos de data mining.

Exemplos:– código postal é fundamental para construir relações geográficas.

– cpf não está relacionado com perfil (idade, sexo, cor, etc).

– data de nascimento e idade correspondem à informação duplicada.

– preço total = preço unitário * quantidade (dados redundantes)


• Dados podem ser conflitantes.

Exemplo: – DB1 pode informar que João mora no Rio de Janeiro e DB2 informa que

João mora em São Paulo.

• Pode-se usar ambos (vive no Rio e em São Paulo).

• Pode-se usar o mais recentemente atualizado.

• Pode-se usar a fonte mais confiável.

• Pode-se sinalizar o registro para ser investigado manualmente.

• Pode-se descartar registros conflitantes.

Etapas do KDD







Clusterização



Identificação de padrões: a significância das respostas

• Um grande risco da mineração de dados é que você pode descobrir padrões que não significam nada.

• Princípio de Bonferroni: – Para qualquer evento que se busca em um conjunto de dados, deve-se

esperar que esse evento ocorra, mesmo que os dados sejam completamente aleatórios. O volume destas ocorrências aumenta com o volume dos dados.

• Deve-se estimar o número esperado de ocorrências de um evento, assumindo que ele é aleatório.

• Se esse número for significativamente maior que o número real de ocorrências esperado, então muitos eventos encontrados serão falsos.

Princípio de Bonferroni

Exemplo“Professor de Stanford prova que Rastrear Terroristas é Impossível” (LA

Times)

Prof. Jeffrey D. Ullman, Stanford, 2006.

– A meta do TIA (Total Information Awareness) é procurar por tantas conexões tão vagas, que em algum momento teremos certeza de termos encontrado uma informação equivocada que poderá violar a privacidade de um inocente.

– Suponha que nós acreditamos que malfeitores estão se encontrandoocasionalmente em hotéis para planejar um atentado. Nós desejamosencontrar pessoas (não relacionadas) que, pelo menos duas vezes,estiveram no mesmo hotel no mesmo dia.

TIA – detalhes do problema

Pessoas sendo rastreadas: 1 bilhão (109).

Período de observação: 1000 (103) dias.

Cada pessoa se hospeda em um hotel por 1% do seu tempo (10 dias em 1000).

Capacidade dos hotéis : 100 pessoas (102).

hotéis monitorados: 10 mil (105).

Se cada pessoa se comportar aleatoriamente (ou seja, não há malfeitores), o Data Mining irá detectar alguma coisa suspeita?

TIA: cálculos

Probabilidade que duas pessoas p e q estarão num mesmo hotel no dia d:

– 1/100 × 1/100 × 10-5 = 10-9

Probabilidade que p e q estarão no mesmo hotel nos dias d1 e d2:– 10-9 × 10-9 = 10-18

Pares de dias: – (103 × 103 ) / 2 = 5 × 105

Probabilidade que p e q estarão no mesmo hotel em algum dos pares de dias:

– 5×105 × 10-18 = 5 × 10-13

TIA: cálculos

Pares de pessoas:– (109 × 109 ) / 2 = 5 × 1017

Número esperado de pares de pessoas “suspeitas”:– 5×1017 × 5×10-13 = 250.000.

Conclusão:– Suponha que haja 10 pares de malfeitores que definitivamente

estiveram no mesmo hotel duas vezes.

– Analistas deverão vasculhar a vida de 250.000 candidatos para encontrar 10 casos reais.

Padrões – fundamento da mineração de dados

Padrões são unidades de informação que se repetem, ouentão são sequências de informações que dispõem deuma estrutura que se repete

• Localizando padrões

– Seja uma sequência original:

ABCXYABCZKABDKCABCTUABEWLABCWO

– Observe atentamente essa sequência de letras e tente encontrar alguma coisa relevante.

Localizando padrões

ABCXYABCZKABDKCABCTUABEWLABCWO

Passo 1: – Encontrar sequências de letras que se repetem bastante. As sequências

AB e ABC ocorrem com frequência superior à das outras sequências.

Passo 2: – Verificamos que as sequências ABC e AB segmentam o padrão original

em unidades independentes:

ABCXY, ABCZK, ABDKC, ABCTU, ABEWL, ABCWO


Passo 3: – Induções geram algumas representações genéricas dessas unidades:

ABC??, ABD??, ABE??, e AB???,

– onde ? representa qualquer letra.

– No final do processo, a sequência original foi substituída por regras genéricas indutivas que simplificaram (reduziu) a informação original a algumas expressões simples.

– Inferimos que a sequência AB inicia um “padrão” que é completado com mais três letras.


• Suponha que uma sequência representa um registro comercial. Por exemplo, uma transação de supermercado:

– A letra A poderia significar aquisição de pão.

– A letra B poderia, por exemplo, significar aquisição de leite.

– A letra C indica que o leite que foi adquirido é do tipo desnatado.

• A regra com as letras AB quer dizer, na prática, que toda vez que alguém comprou pão, também comprou leite. Esses dois atributos estão associados e isto foi revelado pelo processo de descoberta de padrões.


• Suponha que a letra X queira dizer manteiga sem sal, e a letra Zsignifique manteiga com sal e a letra T signifique margarina.

• Pode-se tentar unificar todas essas letras através de um único conceito, uma ideia que resuma uma característica essencial de todos esses itens (generalização).

• Introduzimos a letra V, que significaria manteiga/margarina, ou coisas que passamos no pão.

• Fizemos uma indução orientada a atributos, substituímos uma série de valores distintos (mas similares) por um nome só.


• Basta codificar nossa sequência original substituindo a letra Vem todos os lugares devidos:

ABCXY ABCZK ABDKC ABCTU ABEWL ABCWO (original)

ABCVY ABCVK ABDKC ABCVU ABEWL ABCVO (transformada)

• Nosso sistema de data mining irá extrair a expressão ABCV, que nos irá revelar:“A maioria dos usuários que adquiriram pão e leite desnatado também

adquiriram manteiga ou margarina”.

Medidas de interesse de padrões

• Nem todos os padrões obtidos pela mineração de dados são “interessantes”.

• Um padrão interessante precisa:– ser facilmente compreendido

– ser válido sobre novos dados com algum grau de certeza

– ser potencialmente útil

– ser algo novo, desconhecido anteriormente

– validar alguma hipótese cuja confirmação é desejada

• Existem medidas de interesse objetivas e subjetivas– Objetivas: baseadas em estatísticas e na estrutura dos padrões

– Subjetivas: baseadas em crenças/hipóteses do usuário sobre os dados

Tarefas da mineração de dados

Descrição de dados:

– Caracterização e comparação

Associação:

– Descobrimento de regras.

– Correlação para causalidade.

Classificação e predição:

– Classificação baseada em valores.

– Estimação de valores ou classes a partir de atributos.

Clusterização ou segmentação:

– Agrupar os dados por semelhança.

Análise de tendências e desvios em séries temporais:

– Encontrar e caracterizar tendências, definir padrões ao longo do tempo, encontrar desvios de dados (controle de estoque).

Processo de mineração de dados:Metodologia SEMMA (SAS)

• Sample from data sets

– Particionar em conjunto de Treinamento, Validação e Teste

• Explore data set

– Explorar estatisticamente e graficamente

• Modify

– Transformar variáveis e completar valores omissos

• Model

– Ajustar modelo p. ex. regressão, classificação, redes neurais

• Assess:– Comparar modelos utilizando partições, bases de teste

Processo de mineração de dados: CRISP-DMCRoss Industry Standard Process for Data Mining

Etapas do KDD







Clusterização



Algoritmo de mineração de dados:Regras de associação

Extraído de Temporal association rules.

Nam et al. BMC Bioinformatics 2009 10(Suppl 3):S6


Objetivo:– Encontrar padrões frequentes, associações, correlações entre conjunto

de itens ou objetos de um banco de dados transacional, banco de dados relacional ou outro repositório de informação.

Aplicações:– Análise de cestas de compras, marketing, projeto de catálogos, etc.

• Quais subsequentes compras após ter comprado um PC?

• Qual tipo de DNA é sensitivo a uma nova droga?

• Como classificar documentos WEB?

Exemplos:– Forma regra: “corpo → cabeça [suporte, confiança]”.

– compra(x, “fraldas”) → compra(x, “cerveja”) [0.5%, 60%]

Regras de associação: definições

• Itens I = {i1, ..., im} um conjunto de literais denotando itens

• Itens possuem valores binomiais: { ∈,∉ ; �,� }

• Itemset X: Conjunto de itens X contido em I

• Database D: Conjunto de transações T, cada transação é um conjunto de itens T que contém I

• T contém X → X está contido em T• Os itens na transação são ordenados:

– itemset X = (x1, x2, ..., xk ), onde x1 ≤ x2 ≤ ... ≤ xk

• Tamanho de um itemset: número de elementos em um itemset

• k-itemset: itemset de tamanho k

Regras de associação: definições

• Uma regra de associação X → Y é um relacionamento do tipo:

SE (X) ENTÃO (Y)

onde X e Y são conjuntos de itens

Suporte:

Outra notação:

Confiança:�� → � =�� (� ∪ �)��

�� → � =�� → � = �(� ∪ �) (probabilidade)


Suponha que um gerente de um supermercado esteja interessado em conhecer os hábitos de compra de seus clientes, por exemplo:

Produto Núm. do Produto

Pão 1

Leite 2

Açúcar 3

Papel Higiênico 4

Manteiga 5

Fralda 6

Cerveja 7

Refrigerante 8

Iogurte 9

Suco 10

Num transação Itens comprados

T1 {1,3,5}

T2 {2,1,3,7,5}

T3 {4,9,2,1}

T4 {5,2,1,3,9}

T5 {1,8,6,4,3,5}

T6 {9,2,8}

Exemplo itens de produto

Exemplo BD transações


• Suponha que um Itemset que apareça em pelos menos 50% das transações seja considerado frequente

• Os Itemsets frequentes são considerados interessantes

ItemSet Suporte

{1,3} 0,6666

{2,3} 0,3333

{1,2,7} 0,1666

{2,9} 0,5

Suporte de alguns

Itemsets


• Regras X & Y → Z– suporte = probabilidade de uma transação conter {X U Y U Z}

– confiança = probabilidade condicional de uma transação ter {X U Y} também conter Z

A → C (50%, 66.6%)

C → A (50%, 100%)

Cliente

compra

fraldas

Cliente compra

ambos

Cliente compra cerveja

ID Transação Itens das compras

2000 A, B, C

1000 A, C

4000 A, D

5000 B, E, F

Usando suporte mínimo de 50%

Regras de associação : exemplo

# Tran. Leite Café Cerveja Pão Manteiga Arroz Feijão1 N S N S S N N2 S N S S S N N3 N S N S S N N4 S S N S S N N5 N N S N N N N6 N N N N S N N7 N N N S N N N8 N N N N N N S9 N N N N N S S

10 N N N N N S N

Regras de associação: Exemplo

Conjunto de itens frequentes : café, pão Sup = 0,3Regra : SE (café) ENTÃO (pão) Conf. = 1

Conjunto de itens frequentes : café, manteiga Sup = 0,3Regra : SE (café) ENTÃO (manteiga) Conf. = 1

Conjunto de itens frequentes : pão, manteiga Sup = 0,4Regra : SE (pão) ENTÃO (manteiga) Conf. = 0,8Regra : SE (manteiga) ENTÃO (pão) Conf. = 0,8

Conjunto de itens frequentes : café, pão, manteiga Sup = 0,3Regra : SE (café E pão) ENTÃO (manteiga) Conf. = 1Regra : SE (café E manteiga) ENTÃO (pão) Conf. = 1Regra : SE (café) ENTÃO (manteiga E pão) Conf. = 1

Regras de associação: algoritmo Apriori

• Baseado na ideia de usar conhecimento já obtido dos itemsets anteriores.

Fase I:Descobrir todos os conjuntos de itens com suporte maior ou igual ao mínimo suporte especificado pelo usuário.– Um subset de um itemset frequente também é um itemset frequente

• P. ex., se {AB} é um itemset frequente, ambos {A} e {B} devem ser um itemset frequente

Fase II:A partir dos conjuntos de itens frequentes, descobrir regras de associação com fator de confiança maior ou igual ao especificado pelo usuário.

Regras de associação: algoritmo Apriori

Database D

Scan D

C1L1

L2

C2 C2

Scan D

C3

L3

TID Itens

100 1 3 4

200 2 3 5

300 1 2 3 5

400 2 5

itemset Sup.

{1} 2

{2} 3

{3} 3

{4} 1

{5} 3

Itemset Sup.

{1} 2

{2} 3

{3} 3

{5} 3

itemset

{1 2}

{1 3}

{1 5}

{2 3}

{2 5}

{3 5}

itemset Sup.

{1 2} 1

{1 3} 2

{1 5} 1

{2 3} 2

{2 5} 3

{3 5} 2

itemset Sup.

{1 3} 2

{2 3} 2

{2 5} 3

{3 5} 2

itemset

{2 3 5}

Scan D itemset Sup.

{2 3 5} 2

L3

Regras de associação: algoritmo FP-growth

• Método de geração de padrões frequentes de itens sem a geração de candidatos.

• Mais eficiente e mais escalável que o algoritmo Apriori.

• Percorre o banco de dados apenas duas vezes.

Fase I:Construir uma estrutura de dados compacta chamada FP-tree.

Fase II:Extrair itemsets frequentes diretamente da FP-tree.

Regras de associação: comparação

Medida de interesse: Lift

• Suporte e confiança podem ser altos e a regra não ser útil.

Exemplo:

– Clientes que compraram leite também compraram pão. (sup. 30%, conf. 75%)

Entretanto:

– Clientes sempre compram pão. (sup. 90%)

• Lift indica a força de uma regra sobre a coocorrência aleatória de seus antecedentes e consequentes.

• Valores inferiores a 1 indicam que a regra não aumentou a probabilidade de se prever uma compra cruzada.

– Supondo que 40% dos clientes compram leite, então lift é 0,83.

�� → � =��(� → �)�� × ��(�)

Outras medida de interesse

Convicção: Assim como a confiança, é sensível à direção da regra. �� → � = �1− sup(�)1− conf(� → �)

Ganho: Ganho é calculado baseado em um valor theta (�) dado. Usualmente � = �.� �� → � = sup � ∪ � − � ∗ sup(�)Laplace: Laplace é calculado baseado em um parâmetro �. Usualmente � = 1.0.�� → � = �sup � ∪ � + 1

sup � + �Piatesky-Shaprio (P-S): �� → � = sup � ∪ � − sup � ∗ sup(�)

Etapas do KDD







Clusterização



Algoritmo de mineração de dados: Classificação e predição

Amostras

VEG_I≤ 27,262

VEG_I> 27,262

Tmin_V≤ 20,34º C

BLUE_V≤ 0,02024

BLUE_V> 0,02024

SOMB_V≤ 27,976

SAN6≤ 63,86%

SAN6> 63,86%

EVI_V≤ 0,5573

EVI_V> 0,5573

SOMB_V> 27,976

SOMB_V≤ 31,95

SOMB_V> 31,95

Tmin_V> 20,34º C

DEM≤ 376,377

DEM> 376,377

Tmax_I≤ 30,02º C

Tmax_I> 30,02º C

IDHL_2000≤ 69,75%

IDHL_2000> 69,75%Extraído de Uso de árvore de decisão para

predição da prevalência de esquistossomose

no Estado de Minas Gerais, Brasil. Anais XIII

Simpósio Brasileiro de Sensoriamento

Remoto, Florianópolis, Brasil, 21-26 abril

2007, INPE, p. 2841-2848.


Objetivo:– Extrair modelos que descrevem importantes classes de dados e também

para predizer tendências dos dados.

– Construir ou prever atributos categóricos a partir de um conjunto de outros dados.

Aplicações:– Aprovação de crédito, marketing direcionado, diagnóstico médico,

análise de efetividade.

Exemplos:– Classificação: se FEBRE e DIFICULDADE_RESP e FALTA_DE_APETITE

então AMIGDALITE

– Previsão: dados NUM_QUARTOS, ÁREA, NUM_VAGAS, ELEVADORES, REGIAO, IDADE então VALOR PROVÁVEL DO IMÓVEL

Classificação e predição: processo

Etapa 1:

– Criação do modelo de classificação: • etapa de Aprendizado : modelo é criado a partir da base de

treinamento.

• modelo é constituído de regras classificam registros da base em um conjunto de classes pré-determinado.

Exemplo:

Nome Idade Renda ProfissãoCompra

EletrônicoDaniel <= 30 média estudante SJoão 31..60 média-alta professor SCarlos 31..60 média-alta engenheiro SMaria 31..61 baixa vendedora NPaulo <= 30 baixa porteiro NOtávio > 60 média-alta aposentado N

Base de treinamento Regras do modelo

(a) SE idade = 31..60 e Renda = Média-AltaENTÃO Compra Eletrônico = Sim.

(b) SE Renda = Baixa ENTÃO Compra Eletrônico = Não.


Etapa 2:

– Verificação do modelo ou Classificação: • regras são testadas sobre outra base, independente da base de

treinamento, chamado de banco de dados de testes.

• qualidade do modelo é medida em termos da porcentagem corretamente classificada.

Exemplo:

Nome Idade Renda ProfissãoCompra

EletrônicoPedro 31..60 média-alta ecologista N

José 31..60 média-alta professor N

Luiza 31..60 média-alta assistente NCarla <= 30 baixa vendedora NWanda <= 30 baixa faxineira N

Felipe > 60 média-alta aposentado N

Base de testes Regras do modelo

(a) (1), (2), (3) não são corretamente

classificadas pelo modelo.

(b) (4),(5), (6) classificadas

corretamente.Precisão/acurácia: 50%


Etapa 3:

– Utilização do modelo: • modelo é implantado e utilizado sobre novos dados.

Exemplo:

– Dada a base de dados de clientes de uma loja de eletrônicos:

• enviar marketing direcionado àqueles com maior propensão a consumir eletrônicos, mas que ainda não o fizeram.

Nome Idade Renda ProfissãoJéssica <= 30 média-alta vendedoraLucas <= 30 baixa professorRenata 31..60 baixa engenheiraBernardo > 60 média-alta aposentado


Métodos de classificação:

– Indução de árvore de decisão.

– Classificação Bayesiana.

– Classificação baseada em regras.

– Classificação por propagação reversa (redes neurais).

– Classificação associativa: por análise de regras de associação.

Métodos de predição:

– Regressão linear / polinomial

– Regressão não-linear

Indução de árvore de decisão

Estrutura da árvore de decisão– cada nó é um atributo da base de dados.

– nós folha são do tipo do atributo-classe (ou rótulo, label),

– cada ramo ligando um nó-filho a um nó-pai é etiquetado com um valor do atributo contido no nó-pai.

– um atributo que aparece num nó não pode aparecer em seus nós descendentes.

Algoritmos de indução da árvore– ID3 (final dos anos 1970) - Iterative Dichotomiser

– C45 (sucessor do ID3)

– CART (1984) - Classification and Regression Trees

– J48

Árvore de decisão: exemplo

Exemplo de Quinlan’s ID3

– Base de treinamento

idade renda estuda créditocompra

computador

<=30 alta não razoável não

<=30 alta não excelente não

31…40 alta não razoável sim

>40 média não razoável sim

>40 baixa sim razoável sim

>40 baixa sim excelente não

31…40 baixa sim excelente sim

<=30 média não razoável não

<=30 baixa sim razoável sim

>40 média sim razoável sim

<=30 média sim excelente sim

31…40 média não excelente sim

31…40 alta sim razoável sim

>40 média não excelente não


Uma possível árvore de decisão criada pelo algoritmo: o usuário é um potencial

comprador ou não

idade

<= 30 estuda

não não

sim sim

30..40 sim

> 40 crédito

excelente não

razoável sim

Indução de árvore de decisão

Tipos de dados:– ID3: dados categóricos.

– C4.5: dados contínuos, suporta omissões).

Parâmetros de entrada:– base de dados (B).

– lista de atributos candidatos (CAND).

– um atributo-classe (rótulo): sempre categórico.

Métodos de seleção de atributos– Ganho de informação (ID3).

– Taxa de ganho (C4.5, J48).

– Índice GINI - impureza (CART).

Visão geral do algoritmo de ID3 (C4.5)

1. Crie um nó N associado à base de dados B– SE todos os registros de B pertencem à mesma classe C

ENTÃO transforme em nó folha rotulado por C.

– SENÃO SE CAND = {} ENTÃO transforme N numa folha etiquetada com o valor C = max(count(atributo-classe(A))

– SENÃO seleciona atributo-teste A = max(Ganho(CAND)) e rotule N com o nome de atributo-teste A

2. Partição das amostras de B– PARA cada valor si do atributo-teste FAÇA:

– Crie um nó-filho Ni, ligado a N por um ramo rotulado pelo valor si e associe a este nó uma sub-base Bi tal que o atributo-teste = si

– SE Bi = {} ENTÃO transforme o nó Ni numa folha etiquetada com o valor C = max(count(atributo-Classe(A))

– SENÃO calcule Arvore(Bi , CAND – (atributo-teste)) e associe ao nó Ni

Métodos de seleção de atributos

• Ganho de informação (ID3)– Dados categóricos (número de categorias = v)

– Entropia: � �,� = − �� + � log2 �� + � − �� + � log2 �� + �– Usando o atributo A, a base de dados B será particionada em conjuntos

Si. A quantidade de informação final será: � � = ��=1� �� + �� + � �(�� ,��)– Ganho de informação: � � = � �,� − �(�)

• Taxa de ganho (C4.5)– Dados categóricos ou contínuos

Métodos de seleção de atributos

• Índice Gini (IBM IntelligentMiner)

– Dados contínuos

– Se uma base B contém amostras de N classes:�� = 1 − ��=1� ��2onde �� é a frequência relativa da classe j em B.

– Se B é particionada em duas subclasses B1 e B2 com tamanhos N1 e N2 , então:�� =

�1� �� 1 +�2� �� 2


• Considere a base abaixo. O objetivo é identificar quais as condições ideais para se jogar um determinado jogo.

Aparência Temperatura Umidade Vento Jogar

Ensolarado Quente Alta Não Não

Ensolarado Quente Alta Sim Não

Nublado Quente Alta Não Sim

Chuvoso Moderado Alta Não Sim

Chuvoso Frio Normal Não Sim

Chuvoso Frio Normal Sim Não

Nublado Frio Normal Sim Sim

Ensolarado Moderado Alta Não Não

Ensolarado Frio Normal Não Sim

Chuvoso Moderado Normal Não Sim

Ensolarado Moderado Normal Sim Sim

Nublado Moderado Alta Sim Sim

Nublado Quente Normal Não Sim

Chuvoso Moderado Alta Sim Não


As quatro possibilidades

para o atributo

do nó raiz.

Critério de escolha

intuitivo:

atributo que produz

os nós mais puros.


Entropia do atributo Aparência:� �� =5

14� ��1 +

4

14� ��2 +

5

14� ��3� ��1 =

25 log2 25 + 35 log2 35 = 0.971� ��2 = 44 log2 44 + 04 log2 04 = 0� ��3 =

35 log2 35 + 25 log2 25 = 0.971

logo � �� =5

140.971 +

4

140 +

5

140.971 = 0.693

Como decidir qual o melhor atributo para dividir as amostras

Entropia do atributo Temperatura:� �� =4

14� ��1 +

6

14� ��2 +

4

14� ��3 = 0.911

Entropia do atributo Humidade:� �� =7

14� ��1 +

7

14� ��2 = 0.788.

Ganho da informação:� � = 914 log2 914 + 514 log2 514 = 0.940

� �� = �.�� − �.�� = �.�� = 0.940 − 0.911 = 0.029� �� = 0.940 − 0.788 = 0.152� �� = 0.940 − 0.892 = 0.020

Classificação Bayesiana (Naive Bayes)

• Este método é baseado em classificador estatístico.

• Trabalha com probabilidades de ocorrência de cada classe para cada valor de atributo.

• Supõe que variáveis são independentes.

• P(C|X) probabilidade do registro X ser da classe C

P C X = P C ��=1� � �� • Seleciona P(C|X) máximo

Classificação Bayesiana: exemploAparência

P(sol| sim) = 2/9 P(sol| não) = 3/5

P(nublado| sim) = 4/9 P(nublado| não) = 0

P(chuvoso| sim) = 3/9 P(chuvoso| não) = 2/5

Temperatura

P(quente| sim) = 2/9 P(quente| não) = 2/5

P(moderado| sim) = 4/9 P(moderado| não) = 2/5

P(frio| sim) = 3/9 P(frio| não) = 1/5

Humidade

P(alta| sim) = 3/9 P(alta| não) = 4/5

P(normal| sim) = 6/9 P(normal| não) = 2/5

Vento

P(sim| sim) = 3/9 P(sim| não) = 3/5

P(não| sim) = 6/9 P(não| não) = 2/5

Jogar

P(sim) = 9/14

P(não) = 5/14

Classificação Bayesiana: exemplo

Dado X = <chuvoso, quente, alta, não>

P(X|sim)·P(sim) = P(chuvoso|sim)·P(quente|sim)·P(alta|sim)·P(não|sim)·P(sim) = 3/9·2/9·3/9·6/9·9/14 = 0.010582

P(X|não)·P(não) = P(chuvoso|não)·P(quente|não)·P(alta|não)·P(não|não)·P(nao) = 2/5·2/5·4/5·2/5·5/14 = 0.018286

Amostra classificada como não jogar

Classificação por retropropagação(redes neurais artificiais)

• Método bioinspirado baseado em redes de neurônios artificiais interconectados.

• Vantagens:

– Alta acurácia e robusto à bases com erros

– Saída pode ser discreta (classificação) ou contínua (predição) ou multivalorada.

• Críticas:

– Treinamento demorado e sensível a diversos parâmetros tais como topologia da rede, número de neurônios, taxa de aprendizado, número de épocas utilizadas.

– Difícil de compreender a função aprendida (pesos).

Classificação por retropropagação(redes neurais artificiais)

Treinamento

– Inicia com pesos aleatórios

– Calcula o erro na saída do neurônio:� = �� − ��

– Atualiza pesos:�� + 1 = �� + � � �� TxAp é taxa de aprendizado (ex. 0.05)

ent é entrada

Neurônio Artificial (perceptron)

� = ��=1� �� = �1 , �� ≥ �0, �� < �

Classificação por retropropagação(redes neurais artificiais): exemplo

saída: 1 – feliz, 0 – infeliz Treinamento– Parou quando atingiu � = 0.0001

– Durou 30 épocas (ou 300 iterações)

– TxAp = 0.01

– Limiar da função de ativação � =0.5

– Pesos finais: W0 = 0.416882

W1= 0.507391

– Tempo de treinamento < 1 s.

Calorias Horas Sono Estado

0.9 0.25 0

0.66 0.15 0

0.83 0.55 1

0.86 0.63 1

0.16 0.2 0

0.1 0.65 0

0.33 0.8 1

0.53 0.87 1

0.6 0.46 0

0.23 1 1

Classificação por retropropagação(redes neurais artificiais): exemplo

Desvantagem: só resolve problemas linearmente separáveis

Classificação por retropropagação:redes perceptron muticamadas (MLP)

• Dado um número suficiente de neurônios escondidos, uma MLP com uma camada escondida aproxima qualquer função contínua (Cybenko, 1989).

• Overfitting: uma rede hipertreinada, ou possui mais neurônios do que precisa, se ajusta a grupo específico de dados, diminuindo sua generalização.

Critérios para avaliação dos métodos de classificação

• Velocidade

– refere ao custo e velocidade para gerar e usar os modelos de dados.

• Robustez

– habilidade do método em detectar e resolver questões relativas a valores omissos (ausentes) ou ruidosos.

• Escalabilidade

– capacidade de construir eficientemente modelos com grandes volumes de dados.

• Interpretabilidade

– refere ao nível de entendimento provido pelo modelo.

• Acurácia

– refere a capacidade do modelo representar bem os dados analisados e também novos dados.

Considerações entre associação e classificação

Associação Classificação

Problema simétrico: todos podem ser antecedente ou consequente de uma regra.

Problema assimétrico: um único atributo classe a ser previsto.

Qualidade de uma regra avaliada por fatores de CONF e SUP definidos pelo usuário.

Qualidade é mais difícil de ser avaliada; normalmente avalia-se acurácia.

Definição do problema é clara, determinística: encontrar regras com suporte e confiança especificados.

Regras são avaliadas em dados de teste não vistos na fase de treinamento (prever futuro).

A grande preocupação é em projetar algoritmos eficientes.

A principal preocupação é com o projeto de algoritmos eficazes.

Predição

• Modelam funções contínuas.

• Regressão linear: � = �� + �• Regressão não linear: � = �(�,�), onde �(�,�) é não linear.

Exemplos:

– função exponencial

– função polinomial

• Estimação de parâmetros: métodos dos mínimos quadrados.

• Algumas aplicações não lineares: modelos de crescimento, modelos de rendimentos.

Predição: Regressão Linear

Tamanho da casa

Custo da casa

Lotes custam em média R$25.000,00

Como os custos se comportam de forma imprevisível, existe uma componente aleatória

Tamanho da casa

Custo da casa

Etapas do KDD







Clusterização



Algoritmo de mineração de dados:Análise de agrupamento (Clustering)

Extraído de Dzwinel, et. al. Cluster Analysis, Data-Mining, Multi-dimensional Visualization of

Earthquakes over Space, Time and Feature Space, Earth and Planetary Sci. Letters, August, 2003

Análise de agrupamento: Clustering

Cluster– Coleção de objetos que são similares uns aos outros (de acordo

com algum critério de similaridade pré-fixado) e dissimilares a objetos pertencentes a outros clusters.

Análise de cluster (clustering)– Separa os objetos em grupos com base na similaridade, e em

seguida atribuir rótulos a cada grupo.

Aplicações– Distribuição e pré-processamento de dados.

– Proc. de imagens (segmentação); economia; marketing.

– WWW (Classificação de documentos, padrões de acesso)

– Agricultura (áreas de uso de terra); planejamento de cidades (agrupar casas de acordo com tipos, valores e localização).

Análise de agrupamento: Clustering

• Qualidade do resultado depende da medida da similaridade usada pelo método.

• Requisitos desejáveis:

– Escalabilidade.

– Trata diferentes tipos de atributos.

– Clusters com forma arbitrárias.

– Mínimo conhecimento do domínio.

– Resiliência: valores extremos; ruídos; ordem de processamento.

– Interpretabilidade

Análise de agrupamento:medidas de similaridade e distância

• Algoritmos de agrupamento dependem de uma medida de similaridade ou de distância.

Similaridade– Medida numérica que identifica o quanto dois objetos são parecidos

– O valor é mais alto quanto mais semelhantes os objetos são

– É comum estar entre a faixa de valores [0,1] (normalizado)

Distância (ex., dissimilaridade)– Medida numérica que identifica o quanto dois objetos são diferentes

– Valores menores indicam objetos mais semelhantes

– Dissimilaridade mínima é normalmente 0

– Limite superior pode variar.


• Dados são representados como um vetor de características (“feature

vectors”)

Vetor de características do Empregado 2:

<M, 51, 64000.0>

Vetor de características do Doc 4:

<0, 1, 0, 3, 0, 0>

ID Gênero Idade Salário

1 F 27 19.000

2 M 51 64.000

3 M 52 100.000

4 F 33 55.000

5 M 45 45.000

Tabela de empregados Frequência de termos num Documento

T1 T2 T3 T4 T5 T6

Doc1 0 4 0 0 0 2

Doc2 3 1 4 3 1 2

Doc3 3 0 0 0 3 0

Doc4 0 1 0 3 0 0

Doc5 2 2 2 3 1 4


• Condições para função de distância métrica d para quaisquer objetos i; j; k:– d(i,j) ≥ 0 (1)

– d(i,i) = 0 (2)

– d(i,j) = d(j,i) (simetria) (3)

– d(i,j) ≤ d(i,k) + d(k,j) (desigualdade triangular) (4)

onde:– (1) todos os elementos da matriz de dissimilaridade são não-negativos.

– (2) diagonal da matriz de dissimilaridade é formada por zeros.

– (3) matriz de dissimilaridade é simétrica em relação à diagonal. Existem distâncias assimétricas (exemplo: problema do caixeiro viajante).

– (4) requisito para espaços métricos; existem espaços não métricos (exemplo: julgamentos subjetivos)

Análise de agrupamento: estruturas de dados

Matriz de dados

– Colunas são atributos.

– Linhas são objetos.

– Cada linha é a representação vetorial de um registro.

– N registros e P atributos: matriz N x P

Matriz de distância (simétrica)– N registros: matriz N x N

– distância entre 2 elementos

– Matriz triangular

npx...nfx...n1x

...............

ipx...ifx...i1x

...............

1px...1fx...11x

0...)2,()1,(

:::

)2,3()

...ndnd

0dd(3,1

0d(2,1)

0

Medidas de similaridade: variáveis binomiais ou binárias

• Atributos de tipo binário ou booleano só têm dois valores : 1 ou 0, sim ou não, alto ou baixo.

• Tratar como valores numéricos pode levar a análises errôneas.

– a é o número de atributos com valor 1 para i e j

– b é o número de atributos com valor 1 para i e 0 para j

– c é o número de atributos com valor 0 para i e 1 para j

– d é o número de atributos com valor 0 para i e 0 para j

Amostra Objeto j

Objeto i

Valor 1 0

1 a b

0 c d


• Valores casados: a + d

• Valores distintos: b + c

• Numero de atributos: a + b + c + d

• Medida de distância (atributos simétricos)– Exemplo: gênero, faixa etária

• Medida de distância (atributos assimétricos)– Exemplo: compra de produto, resultado de teste

• Coeficiente de Jaccard (similaridade para variáveis binárias assimétricas)

dcbacb jid

++++=),(

cbacb jid++

+=),(

c+b+a

a=j)(i,simJaccard


Exemplo:

– Gênero é um atributo simétrico

– Os outros atributos são assimétricos

– Seja S = 1, e N = 0

Nome Gênero Febre Tosse Teste 1 Teste 2 Teste 3 Teste 4

João M S N S N N N

Maria F S N S N S N

José M S S N N N N

� ��,�� =0 + 1

2 + 0 + 1= 0.33� ��, �� =

1 + 1

1 + 1 + 1= 0.67� ��, �� =

1 + 2

1 + 1 + 2= 0.75


Distância Fórmula Propriedade

Hamming (Manhattan) b+c não normalizada

Euclidiana sqrt(b+c) não normalizada

Chebyshev discreto max(b; c) não normalizada

Soergel (b+c)/(b+c+d) normalizada

Hamming média (b+c)/(a+b+c+d) normalizada

Euclidiana média sqrt((b+c)/(a+b+c+d)) normalizada


Similaridade Fórmula Propriedade

Russel & Rao a/(a+b+c+d) normalizada

Jaccard a/(a+b+c) normalizada

Rogers & Tanimoto (a+d)/(a+2*(b+c)+d) normalizada

Hamann (a (b + c) + d)=(a + b + c + d) normalizada

Dice 2*a/(2*a+b+c) normalizada

Match simples (a+d)/(a+b+c+d) normalizada

McConnoughy (a*a - b*c) / sqrt((a+b)*(a+c)) normalizada

Medidas de similaridade: variáveis nominais ou categóricas

• Generalização de uma variável binária em que ela pode ter mais de dois valores.– Exemplo: Temperatura = {alta, média, baixa}.

Método 1: Casamento (matching) Simples– m: num de matches, p: num total de variáveis

Método 2: Converter para o formato de planilha binomial– Para cada atributo A, criar P atributos binários para os P estados

nominais (categorias) de A

– Exemplo: A1: Temp = alta; A2: Temp = média; A3: Temp = baixa

pmp

jid−=),(

Medidas de similaridade: variáveis categóricas ordinais

• A ordem é importante, exemplo: rank

• Pode ser tratada como interval-scaled

• Trocar xif pelo seu rank

– mapear a faixa (range) de cada variável em um intervalo [0, 1]

– Computar a dissimilaridade usando método para variáveis contínuas comuns

1

1

−−

=f

if

if M

rz

},...,1{fif

Mr ∈

Medidas de similaridade: variáveis contínuas

• Qualquer distância métrica pode ser utilizada.

• Mais importantes são classes de distâncias de Minkowski:

• Se q = 1, d é a distância de Manhattan

• Se q = 2, d é a distância Euclidiana

qq

pp

qq

jx

ix

jx

ix

jx

ixjid )||...|||(|),(

2211−++−+−=

)||...|||(|),( 22

22

2

11 pp jx

ix

jx

ix

jx

ixjid −++−+−=

Z-score: – x: valor, μ: média, σ: desvio padrão

– Distância entre o dado e a população em termos do desvio padrão

– Negativo quando abaixo da média, e positivo caso acima

Normalização Min-Max:�� = �� −min ��max �� −min �� −�� +��

Medidas de similaridade: Normalização e padronização de dados numéricos

σµ−= x

z

ID Gênero Idade Salário1 F 27 19.0002 M 51 64.0003 M 52 100.0004 F 33 55.0005 M 45 45.000

ID Gênero Idade Salário1 1 0.00 0.002 0 0.96 0.563 0 1.00 1.004 1 0.24 0.445 0 0.72 0.32

• Em alguns casos, medidas de distância provêm visão distorcida– Ex. Quando o dado é muito esparso e 0´s no vetor não são significativos

– Nesses casos, melhor utilizar medidas de distância baseada em vetor

Similaridade de cosseno (produto escalar normalizado)– Produto escalar de dois vetores:

– A norma do vetor X é:

– A similaridade de cosseno é:

Medidas de similaridade baseadas em vetor

∑ ×=•=i

ii yxYXYXsim ),(

∑=i

ixX2

∑∑

∑×

×=

×•

=

i

i

i

i

i

ii

yx

yx

yX

YXYXsim

22

)(

),(

1 2, , ,n

X x x x= 1 2, , ,

nY y y y=

Medidas de similaridade baseadas em vetor

• Exemplo:X = <2, 0, 3, 2, 1, 4>

||X|| = SQRT(4+0+9+4+1+16) = 5.83

X* = X / ||X|| = <0.343, 0, 0.514, 0.343, 0.171, 0.686>

– Note que ||X*|| = 1

– Dividir pela norma torna o vetor de comprimento unitário

– Similaridade de cosseno mede o ângulo de dois vetores de comprimento unitário (ex., a magnitude dos vetores é ignorada).

∑=i

ixX2

Exemplo: Similaridade entre documentos

• Considere a seguinte matriz documento-termo

T1 T2 T3 T4 T5 T6 T7 T8

Doc1 0 4 0 0 0 2 1 3

Doc2 3 1 4 3 1 2 0 1

Doc3 3 0 0 0 3 0 3 0

Doc4 0 1 0 3 0 0 2 0

Doc5 2 2 2 3 1 4 0 2

ProdutoEscalar(Doc2,Doc4) = <3,1,4,3,1,2,0,1> * <0,1,0,3,0,0,2,0>

0 + 1 + 0 + 9 + 0 + 0 + 0 + 0 = 10

Norma(Doc2) = SQRT(9+1+16+9+1+4+0+1) = 6.4

Norma(Doc4) = SQRT(0+1+0+9+0+0+4+0) = 3.74

Cosseno(Doc2, Doc4) = 10 / (6.4 * 3.74) = 0.42

Medidas de similaridade:Correlação

• Em casos onde pode haver uma variância média alta entre os dados (ex. avaliação de filmes), o coeficiente de correlação de Pearson é a melhor opção

Correlação de Pearson

• Normalmente usado em sistemas de recomendação baseados em filtragem colaborativa

�� , � =��(�,�)��(�) � ��(�)

108

Principais métodos de clusterização

Métodos baseados em particionamento:• Dada uma base de dados de n elementos e um número de clusters

k <= n.

Procedimento:– cria-se uma partição inicial aleatória de k partes

– num processo iterativo, os elementos das partes são realocados para outras partes de tal modo a melhorar o particionamento.

Métodos baseados em densidade: • Adequados para descobrir clusters de formato arbitrário.

– clusters são regiões densas de objetos no espaço de dados separadas por regiões de baixa densidade (representando ruídos).

– região densa possui uma x-vizinhança de cada ponto (onde x é um parâmetro dado) contém pelo menos x pontos.

Principais métodos de clusterização

Métodos Hierárquicos aglomerativos:– inicialmente, cada elemento da base forma um cluster.

– a cada iteração pares de clusters mais próximos são aglutinados num único cluster.

– termina quando número de clusters k é atingido.

– Exemplo: AGNES (AGlomerative NESting).

Métodos Hierárquicos divisórios:– inicialmente, cria-se um único cluster composto por toda a

base.

– a cada iteração os clusters são subdivididos em duas partes.

– termina quando número de clusters k é atingido.

– Exemplo: DIANA (DIvisive ANAlysis).

Algoritmo de Particionamento: K-means

Algoritmo k-means (MacQueen’67) (ou K-médias) é um dos mais usados

– cada cluster é representado por um ponto central

– informa-se a quantidade (K) de clusters desejada

– variações: k-medóides, k-modas, k-medianas

– requer uma medida de distância, e a possibilidade de se calcular médias entre os objetos

– pode encontrar mínimos locais: solução é o random restart

– pode entrar em loop infinito: solução é limitar número de iterações

Algoritmo de Particionamento: K-means

Procedimento:(1) Escolhe-se arbitrariamente k objetos {p1;:::;pk} da base.

– Estes objetos serão os centros de k clusters

(2) Para cada objeto O diferente da base calcula-se a distância entre O e cada um dos pi’s

– O objeto O passa a integrar o cluster representado por pi com menor distância

(3) Calcula-se a média dos elementos de cada cluster, isto é, o seu centro de gravidade. Este ponto será o novo representante do cluster.

(4) Em seguida, volta para o passo 2 até que nenhuma mudança ocorra, isto é, nenhum objeto é realocado para outro cluster.

Algoritmo de Particionamento: K-meansExemplo (loop infinito)

0

1

2

3

4

5

6

7

8

9

10

0 1 2 3 4 5 6 7 8 9 10

K= 2

Escolhe-se

arbitrariamente K

elementos para

serem os clusters

iniciais

0

1

2

3

4

5

6

7

8

9

10

0 1 2 3 4 5 6 7 8 9 10

Aloca

cada

objeto

ao

cluster

mais

similar

0

1

2

3

4

5

6

7

8

9

10

0 1 2 3 4 5 6 7 8 9 10

Atualiza

os

centros

dos

clusters

0

1

2

3

4

5

6

7

8

9

10

0 1 2 3 4 5 6 7 8 9 10

Atualiza

os

centros

dos

clusters

0

1

2

3

4

5

6

7

8

9

10

0 1 2 3 4 5 6 7 8 9 10

RealocaRealoca

Algoritmo de Particionamento: K-meansExemplo

Base de dados = {2,4,10,12,3,20,30,11,25}, k=2

Centros iniciais, escolhidos aleatoriamente: m1 = 3, m2 = 4

Primeira iteração

– K1 = {2, 3}; m1 = 2.5; K2 = {4, 10, 12, 20, 30, 11, 25}; m2 = 16

Segunda iteração

– K1 = {2, 3, 4}; m1 = 3; K2 = {10, 12, 20, 30, 11, 25}; m2 = 18

Terceira iteração

– K1 = {2, 3, 4, 10}; m1 = 4.75; K2 = {12, 20, 30, 11, 25}; m2 = 19.6

Quarta iteração

– K1 = {2, 3, 4, 10, 11, 12}; m1 = 7; K2 = {20, 30, 25}; m2 = 25

Quinta iteração

– K1 = {2, 3, 4, 10, 11, 12}; m1 = 7; K2 = {20, 30, 25}; m2 = 25

– Sem alteração em relação à quarta iteração, fim do processamento

Algoritmos hieráquicos aglomerativos:vizinho mais próximo

• “Nearest Neighbour” ou Distância do Vizinho Mais Próximo

• Também conhecido como “Single Linkage Method”.

(1) Clusters inicialmente consistindo de um indivíduo.

(2) Grupos são fundidos de acordo com a distância entre os membros mais próximos.

(3) Cada fusão decrementa por um o número de clusters.


• Suponha que cinco indivíduos devem ser classificados. Para tal, segue a matriz de distância D1, entre os indivíduos

• Os indivíduos 1 e 2 são fundidos (menor distância) e formam um cluster.

=

03589

304910

54056

89502

910620

5

4

3

2

1

54321

1D


• A distância entre este cluster (1,2) e os três indivíduos restantes (3, 4 e 5) são obtidos da matriz da seguinte forma:

{ } 8,min 5,25,25,15)2,1( === dddd

{ } 5,min 3,23,23,13)2,1( === dddd

{ } 9,min 4,24,24,14)2,1( === dddd

0358

3049

5405

8950

5

4

3

(1,2)

543)2,1(___2 =D


• Na nova matriz, a menor distância é 3, em (4,5) e, portanto serão fundidos para formar um segundo grupo.

• Podemos representar os valores obtidos na matriz .

{ } 8,,,min 5,25,24,25,14,1)5,4)(2,1( === dddddd

{ } 4,min 4,35,34,33)5,4( === dddd

=

048

405

850

)5,4(

3

)2,1(

3D


• A menor distância agora é do individuo 3, que é adicionado ao cluster contendo os indivíduos 4 e 5.

• Finalmente, a fusão dos dois grupos ocorre e um único cluster contendo os cinco indivíduos é gerado.

• A seguir o dendrograma detalhando estas fusões

Considerações entre classificação e cluterização

Classificação Clusterização

Há um atributo alvo e os demais são previsores.

Não há atributos especiais.

Parte do problema consiste em determinar automaticamente a importância dos atributos previsores.

A importância de cada atributo é geralmente considerada equivalente à dos demais.

Há medidas objetivas para medir a qualidade da classificação (exemplo: taxa de acerto).

Ë difícil medir a qualidade de clustering.

Classificação é usada principalmente para previsão e controles.

Clustering é usado principalmente para exploração, descrição e sumarização de dados.

Existem várias técnicas e combinações de algoritmos.

Existem várias técnicas e combinações de algoritmos.

Análise de outlier

Outliers (valores extremos)

– “Um outlier é um fato que desvia tanto de outros fatos a ponto de gerar suspeitas de que foi gerado por um mecanismo diferente”.

• A identificação de outliers pode levar à descoberta de conhecimento inesperado em aplicações como:

– Fraude telecomunicação

– Fraude cartões de créditos

– Segmentação de clientes

– performance de atletas profissionais (casos de dopagem, por exemplo).

Análise de outlier

Definição:– Um objeto O de um banco de dados D é dito um DB(p,d)-outlier se pelo

menos uma fração p (0 < p < 1) dos objetos de D estão a uma distância maior do que d de O.

objeto marcado é um DB(p,d)-

outlier, para p = 2/3 e d > d’

(8 dos 12 objetos de D estão a uma distância maior do que d’

deste objeto).

Análise de outlier

Processo:– Sejam uma base D com N elementos, p um número entre 0 e 1 e d > 0. – Considere dist() a função distância considerada. – d-vizinhança(O) é o conjunto de pontos cuja distância a O é no máximo

d. – p é a fração mínima de objetos de D que devem ficar fora da d-

vizinhança de um outlier. – O número máximo de objetos dentro da vizinhança de um outlier, M é:

M = N(1 - p).

• Encontrar todos os DB(p; d)–outliers se reduz a encontrar, para cada objeto O de D, uma vizinhança contendo no máximo Melementos. – Executa-se uma busca dentro de um raio d para cada objeto O. – Se M + 1 elementos são encontrados nesta vizinhança, a busca termina

e O é declarado um não-outlier. Os objetos que sobram são os outliers.

Análise de outlier

Se considerarmos M=2 e d=3

Nos dados abaixo, as linhas 6 e 7 são outliers

L1 L2 L3 L4 L5 L6 L7

L1 0 1 3 2 5 2,5 6

L2 1 0 4 3 2 6 1

L3 3 4 0 2 3 4 5

L4 2 3 2 0 7 8 5

L5 5 2 3 7 0 8 9

L6 2,5 6 4 8 8 0 9

L7 6 1 5 5 9 9 0

Conclusão: 10 erros comuns de mineração de dados para se evitar

The Handbook of Statistical Analysis and Data Mining

0 - Não tem os dados "adequados" (clientes sem dinheiro e sem dados).

1 - Focar no treinamento (nos resultados do treinamento).

2 - Apoiar-se em um única técnica - é necessário um toolkit, comparar seu método com um método convencional (ex. linear

regression e LDA).

3 - Perguntar a pergunta errada.

4 - Ouvir apenas os dados (o computador não possui senso comum).

Conclusão: 10 erros comuns de mineração de dados para se evitar

5 - Aceitar influências do futuro (informação que não estava disponível no

momento).

6 - Eliminar casos estranhos (eliminar os outliers).

7 - Extrapolar (crenças, ignora evidências de que algo que você acredita não irá

funcionar, busca racionalizar uma escolha emocional). Extrapolar dimensões

(aquilo que funciona num plano pode não funcionar em dimensões mais altas).

8 - Responder toda pergunta (em alguns casos, seu dado simplesmente não é

bom o suficiente para responder esta pergunta).

9 - Amostrar os dados casualmente.

10 - Acreditar no melhor modelo.

Aviso legal

O material presente nesta apresentação foi produzido a partir de informações próprias e coletadas de documentos obtidospublicamente a partir da Internet. Este material contém ilustrações adquiridas de bancos de imagens de origem privada ou pública,não possuindo a intenção de violar qualquer direito pertencente à terceiros e sendo voltado para fins acadêmicos ou meramenteilustrativos. Portanto, os textos, fotografias, imagens, logomarcas e sons presentes nesta apresentação se encontram protegidos pordireitos autorais ou outros direitos de propriedade intelectual.

Ao usar este material, o usuário deverá respeitar todos os direitos de propriedade intelectual e industrial, os decorrentes daproteção de marcas registradas da mesma, bem como todos os direitos referentes a terceiros que por ventura estejam, ouestiveram, de alguma forma disponíveis nos slides. O simples acesso a este conteúdo não confere ao usuário qualquer direito de usodos nomes, títulos, palavras, frases, marcas, dentre outras, que nele estejam, ou estiveram, disponíveis.

É vedada sua utilização para finalidades comerciais, publicitárias ou qualquer outra que contrarie a realidade para o qual foiconcebido. Sendo que é proibida sua reprodução, distribuição, transmissão, exibição, publicação ou divulgação, total ou parcial, dostextos, figuras, gráficos e demais conteúdos descritos anteriormente, que compõem o presente material, sem prévia e expressaautorização de seu titular, sendo permitida somente a impressão de cópias para uso acadêmico e arquivo pessoal, sem que sejamseparadas as partes, permitindo dar o fiel e real entendimento de seu conteúdo e objetivo. Em hipótese alguma o usuário adquiriráquaisquer direitos sobre os mesmos.

O usuário assume toda e qualquer responsabilidade, de caráter civil e/ou criminal, pela utilização indevida das informações, textos,gráficos, marcas, enfim, todo e qualquer direito de propriedade intelectual ou industrial deste material.

Documents

Apostila de Mineração de Dados 2016