Data Minig

Data Mining : 

Data Mining Prof. Jacques Schreiber UNISC – www.unisc.br

Roteiro : 

Roteiro Introdução Tecnologia de data mining Regras de Associação Classificação Clustering Aplicações de data mining Ferramentas Comerciais Conclusões

O que é Data Mining? : 

O que é Data Mining? É um processo de descobrir novas correlações significativas, padrões e tendências, para lidar com grandes quantidades de dados armazenados em repositorios (DataWarehouse), utilizando IA tecnologias de reconhecimento de padrões, bem como métodos matemáticos e estatísticos. Uma parte do processo de KDD- Knowledge Discovery in Data.

O que é Data Mining? : 

O que é Data Mining? Não é SQL nem OLAP, embora estas técnicas possam ser parte do processo.

Porquê Data Mining? : 

Porquê Data Mining? Crescimento explosivo na capacidade de gerar, coletar e armazenar dados O armazenamento de dados nos data warehouses A disponibilidade de acesso aos dados de navegação Web e Intranet  Nós temos que descobrir um meio mais efetivo para usar esses dados no processo de apoio a decisão ao invés de usar o tradicional SQL

Porquê Data Mining? : 

Porquê Data Mining? Mas o que é feito destes dados?– Localizar, filtrar é relativamente simples...– Indexar pode ser mais complicado. (http://tineye.com/) Como identificar..– Padrões (“X” acontece se...)– Exceções (isto é diferente de... por causa de...)– Tendências (ao longo do tempo, “Y” deve acontecer...)– Correlações (se “M” acontece, “N” também deve acontecer.) O que existe de interessante nestes dados? Como definir “interessante”? Informação, e não dados, valem dinheiro / tempo / conhecimento!

Aplicações preliminares : 

Aplicações preliminares HighMark: uma das maiores seguradoras de saúde dos EUA Recebe milhões de dados diariamente sobre seus clientes Objetivo: descobrir por que alguns dos seus pacientes adoecem ou por que alguns são + afetados por determinadas doenças do que outros Operadoras de Cartão de Crédito: visam conhecer padrões de compra dos clientes Análise de cesta de supermercado

Sobre que tipo de Dados? : 

Sobre que tipo de Dados? BDs Relacionais Data warehouses Logs de Transação BDs Avançados Objeto-Relacional Multimídia, textos… WWW …

Tecnologia de data mining : 

Tecnologia de data mining Data Mining vs. Data Warehousing Data Mining como parte do processo de KDD - Knowledge Discovery Process Objetivos do Data Mining e Knowledge Discovery Tipos de descoberta do conhecimento durante o Data Mining

Data Mining vs. Data Warehousing : 

Data Mining vs. Data Warehousing Um Data Warehouse é um repositório de informação integrado, disponível para consultas e análises. Os dados e as informações são extraídas de fontes heterogêneas, à medida que são gerados .... Isto torna muito mais fácil e mais eficiente executar consultas sobre os dados que originalmente vieram de diferentes fontes. O objetivo do DW é a de apoiar a tomada de decisões com dados!

Descoberta de Conhecimento em BDs e Data Mining : 

Descoberta de Conhecimento em BDs e Data Mining DM: extração não-trivial de informações implícitas, desconhecidas e potencialmente úteis a partir de Bancos de Dados.

Classes de Algoritmos de Data Mining : 

Classes de Algoritmos de Data Mining Regras de Associação Classificações Hierárquicas Descoberta de Sequências Padrões dentro de Séries Temporais Agrupamentos (Clustering)

Regras de Associação : 

Regras de Associação Fornecer as regras correlacionando a presença de um conjunto de itens com outro conjunto de itens

Regras de Associação : 

Regras de Associação Regras sobre relações e co-ocorrências em bases de dados: Se X ocorre na base de dados, então Y também ocorre (com alguma relação a X). Co-ocorrência: se X, Y e Z ocorrem na base de dados então A também ocorre (com alguma relação a X, Y e Z). X, Y e Z são os antecedentes da associação; A é o conseqüente. Ocorrências consideradas em escopo limitado: não queremos dizer que se X ocorre em qualquer “local” da base de dados, Y também ocorrerá em qualquer “local”. Muito usado para verificar associações em tabelas de transações (“carrinhos de compra”)

Regras de Associação : 

Regras de Associação

Regras de Associação : 

Regras de Associação Conclusões simples sobre a base de dados da tabela: Quem compra leite quase sempre compra ovos. Como definir “quase sempre”? Quantas vezes isso ocorre na base de dados? Quem compra ovos e açúcar sempre compra leite. Mas quantas compras contém ovos e açúcar? O que causa a compra de leite? – Quem compra cerveja sempre compra fraldas. Quantas vezes isso ocorre na base de dados? Isso é relevante?

Regras de Associação : 

Regras de Associação Muitos que compram café também compram açúcar. Ninguém compra só leite. Muitas outras associações negativas existem: quem compra fraldas não compra farinha, quem compra farinha não compra cerveja. Quais associações negativas são significativas?

Regras de Associação : 

Regras de Associação Métricas: Significância em uma associação: ela pode existir mas ser muito rara em uma base de dados (ex. cerveja → fraldas). Suporte X → Y: número de casos que contém X e Y dividido pelo número total de registros. Confiança em uma associação: o antecedente pode ocorrer várias vezes na base de dados mas nem sempre com o mesmo conseqüente associado. Confiança X → Y: número de registros que contém X e Y dividido pelo número de registros que contém X.

Algoritmo Apriori : 

Algoritmo Apriori Um dos algoritmos mais clássicos/tradicionais de busca de regras de associação, base para muitos outros. Definições necessárias: K-itemsets são conjuntos com K itens que podem aparecer na base de dados. Suporte mínimo é o valor mínimo do suporte para que um K-itemset seja considerado. Confiança mínima é um limite para filtragem das associações descobertas pelo algoritmo.

Algoritmo Apriori : 

Algoritmo Apriori Algumas propriedades são usadas pelo algoritmo Apriori para reduzir o espaço de busca: Consideramos que um K-itemset I é infreqüente se o seu suporte é menor que um suporte mínimo. Exemplo: para suporte mínimo 20%, [cerveja] é infreqüente. Considerando um itemset I e um item A, se I ou A forem infreqüentes, a adição de A a I manterá ou diminuirá a freqüência de I. Exemplo 1: [leite,ovos] tem suporte 50%, [manteiga] tem suporte 40%. Por definição o itemset [leite,ovos,manteiga] terá suporte 40% (tem 30%). Exemplo 2: [açúcar,manteiga] tem suporte 20%, [farinha] tem suporte 20%. Por definição o itemset [açúcar,manteiga,farinha] terá suporte 20%

Algoritmo Apriori : 

Algoritmo Apriori Passos (simplificados) do algoritmo Apriori 1. Dados de entrada: coleção de dados associados, suporte mínimo, confiança mínima (pode ser necessário transformar ou reorganizar os dados de entrada!). 2. Considerar K = 1 para criação de K-itemsets 3. Analisar os dados associados e criar uma tabela de K-itemsets com suporte acima do suporte mínimo. 4. Criar com os itemsets filtrados um conjunto de candidatos a (K +1) itemsets. Usar propriedades do Apriori para eliminar itemsets infreqüentes. 5. Repetir desde o passo 3 até que o conjunto gerado seja vazio. 6. Listar regras de associação (com permutações) e aplicar limite de confiança.

Algoritmo Apriori : 

Algoritmo Apriori Simulando o Apriori: consideremos o suporte mínimo como 25% e confiança mínima 75%.

Algoritmo Apriori : 

Algoritmo Apriori Primeiro criamos a tabela de 1-itemsets e verificamos seu suporte (linhas em negrito listam itemsets acima do suporte mínimo).

Algoritmo Apriori : 

Algoritmo Apriori Criamos então as combinações de 2-itemsets com os 1-itemsets acima do suporte mínimo.

Algoritmo Apriori : 

Algoritmo Apriori Novamente criamos combinações com os itens resultantes criando a tabela de 3-itemsets

Algoritmo Apriori : 

Algoritmo Apriori Finalmente criamos combinações com os itens resultantes criando a tabela de 4-itemsets.

Algoritmo Apriori : 

Algoritmo Apriori Não é possível criar mais combinações para os 5-itemsets. Com todas as associações com suporte mínimo listadas, vamos procurar as que tem confiança mínima = 75%. Precisaremos criar as permutações dos itens nos itemsets (http://www.infoescola.com/matematica/permutacao/) Devemos lembrar que o suporte de A → B é igual ao suporte de B → A, mas a confiança de A → B pode ser diferente da confiança de B → A.

Algoritmo Apriori – Regras de Associação com 1 antecedente : 

Algoritmo Apriori – Regras de Associação com 1 antecedente

Algoritmo Apriori – Regras de Associação com 2 antecedentes : 

Algoritmo Apriori – Regras de Associação com 2 antecedentes

Algoritmo Apriori – Regras de Associação com 2 antecedentes : 

Algoritmo Apriori – Regras de Associação com 2 antecedentes

Algoritmo Apriori – Regras de Associação com 3 antecedentes : 

Algoritmo Apriori – Regras de Associação com 3 antecedentes

Algoritmo Apriori : 

Algoritmo Apriori As regras ainda deveriam ser filtradas para evitar repetições de antecedentes e conseqüentes. Importante: neste exemplo não vimos casos de conseqüentes múltiplos (ex. [ovos, leite → café, açúcar] tem 60% de confiança). Também não calculamos associações negativas (ex.[açúcar → não cerveja], com suporte 50% e confiança 100%).

Classificações Hierárquicas : 

Classificações Hierárquicas Classificação é o processo de aprender um modelo que descreve classes diferentes de dados, as classes são pré-determinadas. O modelo produzido geralmente é apresentado na forma de uma árvore de decisão ou um conjunto de regras.

Classificações Hierárquicas : 

Classificações Hierárquicas Predição de uma categoria ou classe discreta. Como entrada, temos muitos dados para os quais as classes são conhecidas. Com isso criamos um classificador ou modelo (fase de treinamento). Como entrada em uma segunda fase, temos vários dados para os quais as classes não são conhecidas. Usamos o classificador para indicar classes para estes dados. Assumimos que dados desconhecidos “próximos” de dados conhecidos terão a mesma classe dos dados conhecidos. O processo pode ser avaliado se usarmos dados com classes conhecidas, fizermos a sua classificação e compararmos os resultados previstos com obtidos.

Classificações Hierárquicas : 

Classificações Hierárquicas As Árvores de Decisão (AD) são um dos métodos mais simples e de grande sucesso no campo do aprendizado indutivo. O aprendizado indutivo está baseado na indução de regras a partir de exemplos.

ID3 : 

ID3 O ID3 constrói uma árvore a partir de um conjunto fixo de exemplos. A futura árvore será utilizada para classificar futuros exemplos. Os nós folhas de uma AD contém valores de categorias enquanto os demais nós contém nós de decisão. O algoritmo ID3 usa um critério chamado ganho de informação (information gain) para decidir qual atributo deve ser associado a um nó de decisão

ID3 : 

ID3 Seleção de Atributo O objetivo aqui é decidir quais atributos da tabela serão nós decisão, lembrando que isto é feito usando o critério ganho de informação. O ganho de informação mede o quanto um atributo é capaz de separar um conjunto de exemplos em categorias. Para cada nível da AD o atributo que possuir o maior ganho é selecionado. Mas antes de continuar a definição de ganho, é necessário definir uma idéia oriunda da teoria da informação: a entropia. A entropia mede a quantidade de informação de um atributo,

ID3 : 

ID3 Entropia: O Ganho de Informação para um atributo A com respeito a um conjunto de registros S é dado por:

ID3 : 

ID3 O atributo “Decisão” é escolhido como o atributo categórico.

ID3 – 1º Passo : 

ID3 – 1º Passo Determinar qual o atributo deve ser o nó raiz da árvore. Entropia(S) = -pcinema log2(pcinema) – pkart log2(pkart) – pshopping log2(pshopping) – pficar em casa log2(pficar em casa ) Entropia(S) = - (6/10) * log2(6/10) - (2/10) * log2(2/10) - (1/10) * log2(1/10) - (1/10) * log2(1/10) Entropia(S) : 0.4422 + 0.4644 + 0.3322 + 0.3322 Entropia(S) : 1.571 Log2 de 0,6 = (log 10 de 0,6) / (log 10 de 2)

ID3 – 2º Passo : 

ID3 – 2º Passo Determinar qual o melhor atributo: Ganho(S,tempo) : 1.571 – (|SSol|/10) * Entropia(SSol) - (|SVento|/10) * Entropia(SVento) - (|SChuva|/10) * Entropia(SChuva) Ganho(S,tempo) : 1.571 – (0.3)*(0.918) – (0.4)*(0.81125) – (0.3)*(0.918) Ganho(S,tempo) : 0.70 Ganho(S,parentes) : 1.571 - (|SSim|/10) * Entropia(SSim) - (|SNão|/10) * Entropia(SNão) Ganho(S,parentes) : 1.571 – (0.5) * 0 – (0.5) * 1.922 Ganho(S,parentes) : 0.61 Ganho(S,dinheiro) : 1.571 - (|SMuito|/10) * Entropia(SMuito) - (|SPouco|/10) * Entropia(SPouco) Ganho(S,dinheiro) : 1.571 – (0.7) * (1.842) – (0.3) * 0 Ganho(S,dinheiro) : 0.2816 Como o atributo “Tempo” teve o maior ganho ele será o primeiro nó da árvore.

ID3 : 

ID3 Analisando os registros onde o tempo é “Sol”: SSol (F1, F2, F10) é verificado que as categorias pertencentes a estes exemplos não são do mesmo tipo, ou seja, a categoria de F1 é “Cinema” e a categoria de F2 e F10 é “Kart”. Desta forma cria-se um novo nó neste ramo. A mesma situação ocorre para o conjunto SVento (F3, F7, F8, F9) e SChuva (F4, F5, F6)

ID3 – 3º Passo : 

ID3 – 3º Passo Escolher o atributo que vai pertencer ao nó “A”. Lembrando que este não pode ser o atributo “Tempo” pois o mesmo já foi escolhido para outro nó. Desta forma é necessário calcular Ganho(SSol,Parentes) e Ganho(SSol, Dinheiro). Inicia-se calculando Entropia(SSol) , lembrando que SSol compreende somente as situações F1,F2 e F10. Ganho(SSol,parentes) : 0.918 – (|SSim|/3) * Entropia(SSim) - (|SNão|/3) * Entropia(SNão) Ganho(SSol,parentes) : 0.918 – (1/3)*0 – (2/3)*0 Ganho(SSol,parentes) : 0.918 Ganho(SSol,dinheiro) : 0.918 - (|SMuito|/3) * Entropia(SMuito) - (|SPouco|/3) * Entropia(SPouco) Ganho(SSol,dinheiro) : 0.918 – (3/3)*0.918 – (0/3)*0 Ganho(SSol,dinheiro) : 0

ID3 : 

ID3

ID3 : 

ID3

ID3 : 

ID3

ID3 : 

ID3

ID3 : 

ID3

ID3 : 

ID3

ID3 : 

ID3

ID3 : 

ID3

ID3 : 

ID3