Logo Passei Direto
Buscar
Material
páginas com resultados encontrados.
páginas com resultados encontrados.

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Prévia do material em texto

KDD, Mineração de Dados e
Algoritmo Apriori
Aluno: Rodrigo Moura J. Ayres 
Orientadora: Dra. Marilde T. P. Santos 
Área: Banco de Dados
Universidade Federal de São Carlos - UFSCar
Departamento de Computação - DC
Programa de Pós-Graduação em Ciência da Computação - PPGCC
Mineração de Dados
 Segundo o dicionário Aurélio (versão on-line)
 Minerar significa Extrair(minério) da mina.
 Portanto, Minerar dados significa extrair(conhecimento) 
dos dados.
Mineração de Dados
 Para (Elmasri e Navathe, 2005) mineração de dados se 
refere à descoberta de novas informações em função de 
padrões em grandes quantidades de dados.
Mineração de Dados
 (Han e Kamber, 2006) consideram o termo “mineração 
de dados” inadequado, pois o que se faz não é extração 
de dados, mas sim extração de conhecimento. 
 “Mineração de Conhecimento a Partir de Dados”.
O que é KDD?
 KDD - Discovery Knowledge from Data, ou seja, 
Descobrimento de Conhecimento a partir de Dados.
 Processo não trivial de extração de padrões válidos, 
novos, potencialmente úteis e compreensíveis a partir 
de dados.
(Frawley, Piatetsky-Shapiro et al., 1992)
KDD e Data Mining
 Os dois estão associados a questão de descoberta de 
conhecimento.
 Para muitos, KDD é sinônimo de Data Mining, ou seja, 
KDD e Data Mining são a mesma coisa.
 Outros afirmam que o KDD é um processo, e a 
mineração de dados é uma etapa desse processo.
KDD
 Segundo (Han e Kamber, 2006) esse processo pode ser 
sumarizado em sete passos principais:
 Limpeza dos Dados (para remover dados inconsistentes e ruídos);
 Integração dos Dados (onde múltiplas fontes de dados podem ser combinadas);
 Seleção dos Dados (onde dados relevantes para a tarefa de análise são 
recuperados do banco de dados);
KDD
 Transformação dos Dados (onde os dados são transformados ou consolidados em 
formas apropriadas para a mineração, por exemplo, fazendo um sumário ou 
agregando operações);
 Mineração de Dados (processo essencial onde métodos inteligentes são aplicados 
com o objetivo de extrair padrões de dados);
 Avaliação dos Dados (para identificar os verdadeiros padrões de interesse que 
representam o conhecimento baseado em alguma medida de interesse);
 Apresentação do Conhecimento (onde visualização e técnicas de representação 
de conhecimentos são utilizadas para representar o conhecimento minerado para o 
usuário).
KDD
 O KDD é um processo cujo objetivo é a descoberta de 
conhecimento útil.
 Esse conhecimento depende dos dados a serem 
analisados e do tipo de informação que será obtida, na 
etapa de MD.
 Essas informações estão relacionadas a duas 
categorias de padrões: descritivos e preditivos.
Tarefas de MD no KDD
 Sendo assim, é necessário que se defina o que se 
chama de “Tarefa de MD”.
 O tipo de tarefa deve ser definido logo no início do 
processo, devendo estar de acordo com o conhecimento 
que se queira obter.
Tarefas
 As tarefas podem ser classificadas em duas categorias: 
descritivas e preditivas.
 Descritivas: caracterizam as propriedades gerais dos dados na base 
de dados.
 Preditivas: fazem inferências nos dados presentes, para fazer 
predições sobre dados futuros.
Tarefas
 As principais tarefas são:
 Associação;
 Agrupamento;
 Classificação;
 Regressão.
Tarefas Preditivas: Regressão e Classificação;
Tarefas Descritivas: Associação e Agrupamento.
Regras de Associação
 A tarefa de associação consiste na descoberta de regras de 
associação.
 Uma regra de associação é uma implicação do tipo:
X Y
antecedente conseqüente
Regras de Associação
 O BD é tratado como uma coleção de transações, sendo 
que cada uma delas envolve um conjunto de itens.
 O significado dessas regras é que transações da base 
de dados que contém o antecedente tendem a conter o 
conseqüente também.
 Por exemplo:
 pão presunto, queijo
Regras de Associação
 Cada regra possui uma medida de suporte e confiança.
 Suporte: O suporte de uma regra é um valor que denota 
a quantidade de transações (registros) na base de 
dados em que antecedente e conseqüente aparecem 
juntos, ou seja, simultaneamente na transação, esse 
valor pode ser expresso percentualmente.
 Confiança: indica a porcentagem de registros que 
contém antecedente + conseqüente sobre a 
porcentagem de registros que possuem o antecedente, 
ou seja, seria: suporte da regra/suporte do antecedente
Regras de Associação
 pão presunto, queijo
 Se a regra tiver 20% de suporte, significa que em 20% 
de todas as transações da base de dados, os itens pão, 
presunto e queijo apareceram na mesma transação.
 Se a regra tiver 50% de confiança, significa que em 50% 
das vezes que o item pão apareceu em uma transação, 
também ocorreu a presença de presunto e queijo.
Itemset
 itemset: é um conjunto de itens.
 Suporte de um itemset: é a quantidade de transações 
que contém todos os itens do itemset, percentualmente 
seria: quantidade/número de transações.
 Itemset freqüente: é o itemset que possui valor de 
suporte maior ou igual a um valor de suporte pré-
estabelecido pelo usuário, chamado de minsup. 
Suporte Itemset
Suporte Regra
 I1 → I2
Mineração de Regras de Associação
 Tarefa:
 1. Encontrar todos os itemsets freqüentes.
 2. Gerar regras de associação a partir dos itemsets
freqüentes.
 Regra de associação relevante: possui grau de 
suporte e grau de confiança >= minsup e minconf.
 Obs. minconf é um grau de confiança estabelecido pelo usuário.
21
Apriori
 Algoritmo de mineração de regras de associação
 Objetivo: identificar os itemsets freqüentes e construir 
regras relevantes a partir deles.
 É dividido em duas etapas:
1. Geração de itemsets candidatos;
2. Geração das regras de associação, a partir dos itemsets frequentes.
22
Apriori - Exemplo
Considerando o minsup = 2
Apriori - Funcionamento
Varredura da 
Base para contar 
ocorrência de 
cada item
Compara o 
suporte do 
candidato com o 
minsup.
Conjunto de candidatos
Conjunto de itemsets freqüentes
Apriori - Funcionamento
Gerar os 
candidatos C2, a 
partir de L1.
Varredura da base 
para contar o 
suporte de cada 
candidato.
Compara o 
suporte do 
candidato com o 
minsup.
Conjunto de candidatos Conjunto de itemsets freqüentes
Apriori - Funcionamento
Gerar os 
candidatos C3, a 
partir de L2.
Varredura da base 
para contar o 
suporte de cada 
candidato.
Compara o 
suporte do 
candidato com o 
minsup.
Conjunto de candidatos Conjunto de itemsets freqüentes
Regras:
I2 → I3, I4 suporte = 2 confiança = 2/3
I3 → I2, I4 suporte = 2 confiança = 2/3
I4 → I2, I3 suporte = 2 confiança = 2/3
I2, I3 → I4 suporte = 2 confiança = 2/2
I2, I4 → I3 suporte = 2 confiança = 2/2
I3, I4 → I2 suporte = 2 confiança = 2/3
O suporte pode ser obtido 
pelo itemset da regra;
A confiança é o suporte da 
regra/suporte do antecedente
Referências
 ELMASRI, R.; NAVATHE, S. B. Sistemas de Banco de Dados. 4. 
ed. São Paulo: Pearson Addison Esley, 2005.
 HAN, J.; KAMBER, M. Data Mining: Concepts and Techiniques. 2. 
ed. San Francisco, CA: Morgan Kaufmann, 2006. (The Morgan 
Kaufmann Series in Data Management Systems).
 FRAWLEY, W. J. et al. Knowledge Discovery in Databases: An
Overview. AI Magazine [S.I.], v. 13, 1992.
Obrigado

Mais conteúdos dessa disciplina