Aula - DABI v3.1.pdf

DABI - Data Warehouse e Business Intelligence

Profa. Claudia Martins

Prof. Nilton Takagi

Motivação?

...

Agenda

Nivelamento de conceitos Conceitos e etapas de Data Mining Técnicas de Data Mining

– Classificação● Árvores de Decisão● Aprendizado Bayesiano● Redes Neurais

– Regras de Associação● A priori

– Clustering● K-means

Aplicação usando o software Weka

Business Intelligence

Nivelamento de Conceitos

Por que Data Warehouse?

Repositório de várias fontes de dados Armazenamento de grandes volumes de dados Estrutura, conteúdo e uso diferente: dados históricos,

para suporte a decisão, fontes heterogêneas, várias dimensões

Os usuários são gerentes de alto nível e os responsáveis pela tomada de decisões

Consulta: Quais são os produtos vendidos no último quadrimestres e o total de vendas no Brasil?

Nivelamento de Conceitos

Por que Data Warehouse?

Data Warehouses (DW) generalizam e consolidam dados em um espaço multidimensional

A construção de DW envolve limpeza dos dados; integração dos dados e transformação dos dados (importante passo de pré-processamento para DM)

Data warehousing fornece arquitetura e ferramentas para executivos de negócios sistematicamente organizar, compreender e usar seus dados para fazer decisões estratégicas.

Última arma de marketing: “um modo de reter clientes por aprender mais sobre suas necessidades”

Nivelamento de Conceitos

Por que utilizar um Data Warehouse?

Várias plataformas de hardware e software;

Existência de sistemas de fornecedores diferentes;

Constantes alterações nos sistemas corporativos;

Machado, 2004

Conceitos DW

O que é um Data Warehouse?

“É uma coleção de dados orientados por assunto, integrado, variável com o tempo e não-volátil, que tem por objetivo dar suporte aos processos de tomada de decisão.” (Inmon)

Laudon, 2010

Conceitos DW

O que é um Data Warehouse?

Nivelamento de Conceitos

Por que Data Mining?

Crescimento explosivo de dados: de terabytes a petabytes

Coleção e disponibilidade de dados: ferramentas automatizadas para coleção de dados, sistemas de banco de dados, Web, sociedade computadorizada

Maiores fontes de dados: – Negócios (business): Web, e-commerce, transações,

estoques, … – Ciência: Sensoriamento Remoto, bioinformática,

simulação científica, … – Sociedade em geral: notícias, câmaras digital, YouTube

Laudon, 2010

Nivelamento de Conceitos

Por que Data Mining?

Estamos afogados em dados, mas sedentos por conhecimento!

“Necessidade é a mãe da invenção”—Data mining—Análise automática de massivos conjuntos de dados

Buscar padrão: Qual o perfil de clientes que compraram produtos eletrônicos?

Nivelamento de Conceitos

Data Warehouse vs Data Mining

Data Warehouse – Consulta: Quais clientes

compraram produtos eletrônicos? Qual o valor total das vendas no quadrimentre passado?

Data Mining – Padrão: Qual o perfil dos clientes que

compraram produtos eletrônicos? Os clientes que compraram produtos eletrônicos também compraram qual outro produto?

Nivelamento de Conceitos

Data Warehouse vs Data Mining

Data Warehouse – Consulta: Quais clientes compraram produtos eletrônicos?

Qual o valor total das vendas no quadrimestre passado?

Data Mining – Padrão: Qual o perfil dos clientes que compraram

produtos eletrônicos? Os clientes que compraram produtos eletrônicos também compraram qual outro produto?

Data Warehouse é a MEMÓRIA da empresaData Mining é a INTELIGÊNCIA empresa

Nivelamento de Conceitos

Agenda

Nivelamento de conceitos Conceitos e etapas de Data Mining Técnicas de Data Mining

– Classificação● Árvores de Decisão● Aprendizado Bayesiano● Redes Neurais

– Regras de Associação● A priori

– Clustering● K-means

Aplicação usando o software Weka

O que é Data Mining?

Data mining (descoberta de conhecimento de dados) – Extração de padrões ou conhecimento interessantes

(não-trivial, implícitos, previamente desconhecidos e potencialmente úteis) de grandes volumes de dados

– Data mining: um termo errôneo? Nomes alternativos

– Knowledge discovery (mining) in databases (KDD), extração de conhecimento, análise de dados/padrões, arqueologia de dados, dragagem de dados, colheita de informação, business intelligence, etc.

Atenção: tudo é “data mining”? – Simples busca e processamento de consulta – Sistemas especialistas (Dedutivo)

Nivelamento de Conceitos

Processo de Descoberta de Conhecimento (KDD)

Laudon, 2010

Nivelamento de Conceitos

Ponto de vista típico de comunidades de sistemas de banco de dados e data warehousing

Data mining tem uma função essencial no processo de descoberta de conhecimento

Processo KDD: Técnicas de ML e Estatística

Laudon, 2010

Nivelamento de Conceitos

Data Mining: Interação de Múltiplas Áreas

Laudon, 2010

Nivelamento de Conceitos

Porque Múltiplas Áreas?

Enorme quantidade de dados– Algoritmos devem ser altamente escaláveis para

manipular tera-bytes de dados Alta dimensionalidade dos dados

– Micro-array com milhares de dimensões Alta complexidade de dados

– Cadeias de dados e dados de sensores– Dados de séries temporais, dados de sequências – Dados estruturais, grafos, redes sociais – Banco de dados heterogêneos e legados– Dados espacial, espaço-temporal, multimídia, textual, Web – Programas de software, simulações científicas– Novas e sofisticadas aplicações

Laudon, 2010

Nivelamento de Conceitos

Multi-Dimensionalidade e Data Mining

Conhecimento a ser minerado (ou: funções Data mining)– Caracterização, discriminação, associação, classificação,

agrupamento (clustering), tendências, análise de outliers, etc.

– Data mining descritiva vs. preditiva – Funções múltiplas/integradas e mineração em múltiplos

níveis Dados a serem minerados

– Banco de Dados (relacional-extendido, orientado a objeto, heterogêneos, legados), data warehouse, dados transacionais, espaço-temporal, série temporial, sequência, textual e web, multimídia, grafos, redes sociais e de informação

Sezões

Nivelamento de Conceitos

Multi-Dimensionalidade e Data Mining

Técnicas utilizadas– data warehouse (OLAP), machine learning,

estatísticas, reconhecimento de padrões, visualização, alto desempenho, etc.

Aplicações apropriadas– Varejo, telecomunicação, bancos, análise de fraude,

bio-dados, análise de estoque de mercado, mineração textos, mineração Web, etc.

Laudon, 2010

Nivelamento de Conceitos

Data Mining: quais tipos de dados?

Conjunto de dados e aplicações orientados ao banco de dados – Banco de dados relacional, data warehouse, transacional

Conjunto de dados e aplicações avançadas – Dados streams e dados de sensor– Dados de séries temporais – Dados estruturais, grafos, redes sociais– Banco de dados objeto-relacional – Banco de dados legados e heterogêneos – Dados espaciais e espaço-temporal– Banco de dados multimídia – Banco de dados textuais– Dados da World-Wide Web

Machado, 2004

Conceitos DW

Avaliação do Conhecimento

Todo conhecimento descoberto é interessante?– Podem enconrtar muitos “padrões” e conhecimento– Podem preencher apenas certas dimensões (tempo, locação, …)– Podem não ser representativos, podem ser transitórios, …

Avaliação do conhecimento minerado → como minerar apenas conhecimento interessante?– Descritivo vs. preditivo– Cobertura– Típico vs. novidade– Precisão– Ocasião/conveniência – ..

Machado, 2004

Conceitos DW

Maiores Desafios em Data Mining

Eficiência e escalabilidade dos algoritmos de data mining Métodos de mineração paralelos, distribuídos, stream, e

incrementais Manipulação de alta-dimensionalidade Manipulação de ruídos, incerteza e imperfeições dos dados Incorporação de restrições, conhecimento especialista e

conhecimento de fundo em data mining Avaliação de padrões e integração de conhecimento Mineração de diversas e heterogêneos tipos de dados: p.e.,

bioinformática, Web, engenharia de software/sistema, redes de informação

Data mining orientada a aplicação e específica do domínio Data mining invisível (embutido em outros módulos

funcionais) Proteção de segurança, integridade e privacidade em

Machado, 2004

Conceitos DW

Resumo

MD: inteligência x DW: memória Mineração de Dados: Descobrindo padrões interessantes

de grandes volumes de dados Um processo KDD inclui limpeza dos dados, integração

dos dados, seleção dos dados, transformação, data mining, avaliação de padrões e apresentação do conhecimento

Mineração por ser aplicado em uma variedade de repositórios de informação

Mineração de Dados: uma etapa do processo de Business Intelligence? Um conceito fuzzy!!!!

Machado, 2004

Atividade!

Qual a diferença entre BI, KDD, DM, DW e AM?

Nivelamento de Conceitos

Agenda

Nivelamento de conceitos Conceitos e etapas de Data Mining Tarefas e técnicas de Data Mining

– Classificação● Árvores de Decisão● Aprendizado Bayesiano● Redes Neurais

– Regras de Associação● A priori

– Clustering● K-means

Aplicação usando o software Weka

Tarefas de Aprendizado

Aprendizado Indutivo– É essencial, pois é necessário a projeção em janelas

de tempo;

Machado, 2004

Conceitos DW

Tarefas de Aprendizado

Aprendizado por exemplos

Machado, 2004

Conceitos DW

O que é uma Hipótese?

Aprendizado Supervisionado vs. Não Supervisionado

Aprendizado Supervisionado (classificação)– Supervisão: os dados de treinamento (observações,

medidas, etc.) são acompanhadas por rótulos (labels) indicando a classe das observações

– Novos dados são classificados baseados no conjunto de treinamento

Machado, 2004

Conceitos DW

Aprendizado Supervisionado vs. Não Supervisionado

Aprendizado Não Supervisionado (clustering)– Os rótulos das classes dos dados de treinamento são

desconhecidos– Dado um conjunto de medidas, observações, etc. a

meta é estabelecer a existência de classes ou clusters nos dados

Machado, 2004

Conceitos DW

Problemas de Predição: Classificação vs. Predição Numérica

Classificação – Prediz classes categóricas (discreta ou nominal)– Classifica dados (constrói um modelo) baseado no

conjunto de treinamento e nos valores (classes) na classificação de atributos para classificar novos dados

Machado, 2004

Arquitetura DW

Problemas de Predição: Classificação vs. Predição Numérica

Predição Numérica – Modela funções de valores contínuos, i.e., prediz

valores desconhecidos ou ausentes Aplicações Típicas

– Aprovação Crédito/empréstimo– Diagnóstico Médico: se um tumor é canceroso ou

benigno– Detecção de Fraude: se uma transação é

fraudulenta – Categorização de página Web: qual categoria

pertence

Machado, 2004

Carga inicial e novos dados Consultas orientadas ao usuário finalArquitetura DW

Classificação:Árvores de Decisão

Exemplo: Robôs Amigos e Inimigos

Machado, 2004

Exemplo: Robôs Amigos e Inimigos

Conceito/modelo extraído – árvore de decisão e regras:– Se sorri = não então inimigo

– Se sorri = sim e segura = espada então inimigo

– Se sorri = sim esegura = balão ou bandeira

então inimigo

Machado, Sezões

Arquitetura DW

Classificação: Exemplo 2

Machado, 2004

Classificação: Exemplo 2

Machado, 2004

Classificação: Exemplo 2

Machado, 2004

Classificação: Exemplo 2

Machado, 2004

Classificação: Exemplo 2

Machado, 2004

Classificação: Exemplo 2

Machado, 2004

Classificação: Exemplo 2

Machado, 2004

Classificação: Exemplo 2

Machado, 2004

Classificação—Processo de Dois Passos

Construção do Modelo: descrição de um conjunto predeterminado de classes – Cada tupla/amostra pertence a uma classe

predefinida, como determinada por um atributo classe

– O conjunto de tuplas usado para construção do modelo é o conjunto de treinamento

– O modelo é representado como regras de classificação, árvores de decisão ou fórmula matemática

Machado, 2004

Classificação—Processo de Dois Passos

Uso do Modelo: para classificação futura de objetos desconhecidos – Acurácia Estimada do modelo

● As classes do conjunto de teste é comparado com o resultado classificado pelo modelo

● Acurácia é a porcentagem da amostra do conjunto de teste que são corretamente classificadas pelo modelo

● Conjunto de Teste é um conjunto de treinamento independente

– Se a acurácia é aceitável, usa-se o modelo para classificar dados cujas classes são desconhecidas

Machado, 2004

Passo (1): Construção do Modelo

Passo (2): Usando o Modelo na Predição

Indução de Árvores de Decisão: Dados de Treinamento

Sezões

Análise OLAP

Output: Uma Árvore de Decisão para “buys_computer”

Sezões

Algoritmo para Indução de Árvores de Decisão

Algoritmo Básico – A árvore é construída de forma recursiva top-down dividir-e-conquistar– No início, todos os exemplos de treinamento estão na raiz – Atributos são categóricos (os valores contínuos são discretizados)– Exemplos são particionados recursivamente baseados nos exemplos

selecionados – Atributos teste são selecionados de acordo com uma medida heurística ou

estatística (p.e., ganho de informação) Condições para parar o particionamento

– Todos os exemplos para um dado nó pertencem à mesma classe – Não existe atributos remanescentes para particionamento – a classe

majoritária é escolhida para classificar a folha – Não existe exemplos na folha

Machado, Sezões

Análise OLAP

Medida de Seleção de Atributo: Ganho de Informação (ID3/C4.5)

Machado

Análise OLAP

Seleção de Atributo: Ganho de Informação

Machado

Análise OLAP

Overfitting e Poda da Árvore

Overfitting: uma árvore induzida pode “overfit” os dados de treinamento – Muitos ramos, alguns podem refletir anomalias

devido a ruídos ou outliers– Pobre acurácia para exemplos não vistos

Duas abordagens para evitar overfitting – Prépoda: Construção da árvore para cedo ̵ não

divide um nó se este pode resultar em uma boa medida de acordo com threshold● Difícil escolher um threshold apropriado

– Póspoda: Remove ramos de uma árvore “totalmente crescida” —pega uma sequência progressivamente de poda da árvore● Usa um conjunto de dados diferente do treinamento

para decidir qual a “melhor poda da árvore” Análise OLAP

Sezões

Método de Poda Redução do Erro

O conjunto de teste é classificado no modelo gerado com o conjunto de treinamento contando, para cada nó da árvore de decisão original, o número de exemplos em cada classe:– Conta o nº de exemplos dos nós folhas não

classificados (ds)– Conta o nº de exemplos que não seriam

classificados se a subárvore (S) em questão fosse substituída por sua melhor folha (dps)

– Se gs = ds – dps >= 0 então PODA

Extração de Regras de uma Árvore de Decisão

Regras são mais fáceis de compreender do que grandes árvores

Uma regra é criada para cada

caminho da raiz até a folha Cada para atributo-valor ao longo do

caminho forma uma conjunção: as folhas predizem classe

Regras são mutuamente exclusivas e exaustivas

Example: extração de

regras da árvore de decisão

buys_computer

Análise OLAP

Sezões

Classificação em Grandes Databases Classificação – um problema clássico extensivamente

estudado por estatísticos e pesquisadores de AM Escalabilidade: Classificando dados com milhões de

exemplos e centenas de atributos com velocidade razoável

Por que indução de árvores de decisão em data mining?– Relativamente aprendizado mais rápido (do que outros

métodos de classificação)– Conversão simples e fácil para compreensão de regras de

classificação – Pode usar consultas SQL para acesso ao banco de dados – A acurácia comparável com outros métodos

Machado, Inmon

Modelagem

Atividade!

Qual a árvore de decisão usando o ganho de informação, para o conjunto de dados abaixo.

Qual a classe do exemplo (Sim, Frango, Sim, Não)?

Nivelamento de Conceitos

Feijão Carne Frutas Queijo Resultado

1 Sim Peixe Sim Sim Sim

2 Não Gado Não Não Não

3 Sim Peixe Sim Sim Sim

4 Não Frango Sim Não Sim

5 Não Gado Sim Não Não

Classificação:Aprendizado Bayesiano

Classificação Bayesiana: Por que?

Classificador estatístico: realiza predição probabilística, i.e., prediz a probabilidade dos membros das classes

Fundamento: Baseado no Teorema de Bayes. Performance: Um simples classificador Bayesiano, naïve

Bayesiano classificador, tem performance comparável com árvores de decisão e classificadores de redes neurais

Incremental: Cada exemplo de treinamento pode incrementalmente aumentar/diminuir a probabilidade que uma hipótese está correta — conhecimento anterior pode ser combinada com dados observados

Escala: Até quando métodos Bayesianos são intratáveis computacionalmente, podem fornecer uma escala de decisões ótimas contra outros métodos que podem ser medidos

Machado, Inmon

Modelagem

Teorema Bayesiano: Básico

Faça X ser uma amostra de dados (“evidência”): classe é desconhecida

Faça H ser uma hipótese que X pertence a classe C Classificação: determinar P(H|X) (probabilidade a

posteriori), probabilidade da hipótese dado a amostra X P(H) (priobabilidade a priori), a probabilidade inicial

– p. e., X comprará computador, independente da idade, rendimento, …

P(X): probabilidade que a amostra de dados é observada P(X|H) (likelihood), a probabilidade de observar a

amostra X, dado a hipótese – p.e., dado que X comprará computador, a prob. Que X é

31..40, rendimento médio

Machado, Inmon

Modelagem

Teorema Bayesiano

Dado os dados de treinamento X, probabilidade a posteriori da hipótese H, P(H|X), segue o teorema de Bayes

P(H|X) = P(X|H)P(H) / P(X) Informalmente, isto pode se escrito como

posteriori = likelihood x prior/evidence Prediz X pertencer a C2 sss a probabilidade

P(Ci|X) é o mais alto entre todos os P(Ck|X) para todos as k classes

Dificuldade prática: requer conhecimento inicial de muitas probabilidades, significando custo computacional

Machado, Inmon

Modelagem

Classificador Naïve Bayesiano: Dados de Treinamento

Machado, Inmon

Modelagem

Classificador Naïve Bayesiano: um Exemplo

Machado, Inmon

Modelagem

Evitando o problema da probabilidade 0 Predição Naïve Bayesiano requer que cada prob.

condicional ser não-zero. Caso contrário, a prob. predita será zero

Ex. Suponha um conjunto de dados com 1000 tuplas, income=low (0), income= medium (990), e income = high (10),

Use Laplaciano correção (ou Laplacian estimator)– Adicionado 1 a cada caso

● Prob(income = low) = 1/1003● Prob(income = medium) = 991/1003● Prob(income = high) = 11/1003

A prob. “corrigida” estimada são mais próximas do que “não corrigidas”

Machado, Inmon, Sezões

Modelagem

Naïve Bayesian Classificador: Comentários

Vantagens – Fácil implementar – Bons resultados obtidos na maioria dos casos

Desvantagens – Suposição: independência condicional da classe, portanto

perda de acurácia – Praticamente, dependências existe entre variáveis

● p.e., hospitais: pacientes: Perfil: idade, família, histórico, etc. ● Sintomas: febre, tosse etc., Doença: cancer, diabetes, etc.

– Dependências entre estes não podem ser modelados pelo Classificador Naïve Bayesian

Como tratar com essas dependências?– Redes de Crenças Bayesianas

Atividade!

Calcule as probabilidades usando o aprendizado Bayesiano para o conjunto de dados abaixo.

Qual a classe do exemplo (Sim, Frango, Sim, Não)?

Nivelamento de Conceitos

Feijão Carne Frutas Queijo Resultado

1 Sim Peixe Sim Sim Sim

2 Não Gado Não Não Não

3 Sim Peixe Sim Sim Sim

4 Não Frango Sim Não Sim

5 Não Gado Sim Não Não