Data Mining - aula 01

Prévia do material em texto

Univ. Tecnológica Federal do Paraná 
Campus Medianeira 
 
Prof. M.Sc. Alan Gavioli 
alan@utfpr.edu.br 
DATA MINING 
 
AULA 01 
 
 
 
CONSIDERAÇÕES INICIAIS 
DEFINIÇÃO DE DATA MINING 
 O que é Data Mining: 
 
 É o processo não-trivial de identificar padrões 
válidos, novos, potencialmente úteis e 
compreensíveis em dados. 
 
 De acordo com Usama Fayyad, Data Mining 
consiste na aplicação de análise de dados e 
algoritmos de descobrimento para produzir uma 
enumeração de padrões sobre os dados. 
 
 Tradução mais comum: Mineração de Dados. 
DEFINIÇÃO DE DATA MINING 
 O que é Data Mining (continuação): 
 
 Segundo Holly Korab, Data Mining é um dos 
passos de um processo maior denominado 
Descoberta de Conhecimento em Bases de 
Dados - DCBD (Knowledge Discovery in 
Databases - KDD), que é realizado por 
ferramentas computacionais em 
desenvolvimento para crescentes volumes de 
dados. 
JUSTIFICATIVAS PARA UTILIZAÇÃO 
 O avanço tecnológico tem contribuído para o 
crescimento dos volumes de dados armazenados 
pelas organizações. 
 
 A enorme queda na taxa de custo/desempenho de 
sistemas para armazenamento e processamento é 
uma realidade. 
 
 Nota-se uma intensa competição de mercado, 
devido à saturação, o que torna necessário 
direcionar a manufatura, o mercado e a 
propaganda para segmentos pequenos e até 
indivíduos isoladamente. 
COMPARAÇÃO COM CONSULTAS 
TRADICIONAIS 
 Consultas tradicionais em bancos de dados: 
 
 “Quais foram as vendas de soja em março de 2010 
no Paraná?” 
 
 “Qual foi o total de veículos vendidos no Brasil pela 
montadora A, em outubro de 2009?” 
COMPARAÇÃO COM CONSULTAS 
TRADICIONAIS 
 Por outro lado, a Mineração de Dados, através do 
uso de algoritmos específicos ou mecanismos de 
busca, tenta descobrir padrões discerníveis e 
tendências nos dados, e inferir regras para os 
mesmos. 
 
 Com estas regras, o usuário está habilitado a: 
 Suportar, revisar e examinar decisões em alguma área 
comercial ou científica relacionada. 
 Prever dados, situações e comportamentos futuros, 
relacionadas ao setor em que ele atua. 
EVOLUÇÃO DA MINERAÇÃO DE 
DADOS 
Etapa 
Revolu- 
cionária 
Questão 
Comercial 
Tecnologias 
Disponíveis 
Fornece-
dores de 
Produtos 
Caracte-
rísticas 
Coleção 
de dados 
(anos 
60) 
"Qual foi a 
receita total 
nos últimos 
5 anos?" 
Computado-
res, fitas e 
discos 
IBM Retrospecti
va, distrib. 
de dados 
estática 
Acesso a 
dados 
(anos 
80) 
"Quais as 
vendas 
unitárias de 
São Paulo 
em março?" 
Bancos de 
dados 
relacionais, 
SQL 
Oracle, 
Sybase, 
Informix, 
IBM, 
Microsoft 
Retrospecti
va, distrib. 
de dados 
dinâmica 
(registros) 
EVOLUÇÃO DA MINERAÇÃO DE 
DADOS 
Etapa 
Revolu- 
cionária 
Questão 
Comercia
l 
Tecnologias 
Disponíveis 
Fornece-
dores de 
Produtos 
Caracte-
rísticas 
 
DW & 
Suporte 
decisão 
(anos 90) 
"Quais as 
vendas 
unit. de Foz 
em março? 
Avalie 
também 
Cascavel" 
OLAP, bases 
de dados 
multidimen-
sionais, data 
warehouses 
Pilot, 
Comshare, 
Arbor, 
Cognos, 
Microstra-
tegy 
Retrospecti
va, distrib. 
Dinâmica 
em 
múltiplos 
níveis 
Mineração 
de dados 
(atual) 
"Qual a 
previsão de 
Cascavel no 
próximo 
mês? Por 
quê?" 
Algorit. avan 
çados, com 
putadores 
multiproc., 
BDs enormes 
Pilot, 
Lockheed, 
IBM, SGI, 
e outros 
Prospectiva 
MODELOS DE MINERAÇÃO DE 
DADOS 
 IBM diz que existem 2 tipos de modelos de 
operação que podem ser usados para identificar 
informações interessantes: 
 
 Modelo de verificação: 
• O usuário gera hipóteses e testa a validade. 
• Ex: mala direta convencional. 
 
 Modelo de descoberta: 
• Sistema faz descobertas automáticas. 
• São procurados padrões, tendências e 
generalizações sobre os dados. 
• Ex: análise de BD de uma operadora de cartões de 
crédito, para publicidade. 
DESCOBERTA DE CONHECIMENTO 
EM BASES DE DADOS (KDD) 
 Etapa 1 – Definição de metas: define-se o 
problema a ser resolvido. 
 Etapa 2 – Seleção: realiza-se a seleção dos dados 
apropriados para a análise, segundo algum critério. 
 Etapa 3 – Pré-processamento: eliminação de 
ruídos e erros, procedimentos para verificação da 
falta de dados, entre outros. 
 Etapa 4 – Transformação: redução dos dados 
através da busca por atributos relevantes. 
DESCOBERTA DE CONHECIMENTO 
EM BASES DE DADOS (KDD) 
 Etapa 5 – Mineração de Dados: aplicação dos 
algoritmos para descoberta de padrões nos dados; 
envolve a seleção de técnicas adequadas para 
cumprir as metas. 
 Etapa 6 – Interpretação/Avaliação: Os padrões 
identificados pelo sistema são interpretados em 
conhecimento, que pode então ser utilizado para 
suportar a tomada de decisão humana. 
DESCOBERTA DE CONHECIMENTO 
EM BASES DE DADOS (KDD) 
 
TAREFAS DE MINERAÇÃO DE DADOS 
 As principais são: 
 
 1) Associação: procura todas as associações 
em que a presença de um conjunto de itens em 
uma transação implica na presença de outros 
itens nessa mesma transação. 
 
 2) Classificação: permite prever valores de um 
atributo faltante (atributo-alvo) em dados 
incompletos ou dados futuros, usando regras de 
classificação descobertas a partir de um conjunto 
de dados completos. 
 
TAREFAS DE MINERAÇÃO DE DADOS 
 Continuação...: 
 
 3) Agrupamento: segmenta um conjunto de 
registros em subconjuntos ou grupos, de acordo 
com valores de atributos. 
 
 4) Regressão: tenta descobrir um modelo 
matemático a partir de um conjunto de dados 
que possa ser empregado para previsão de 
valores futuros. 
 
DATA WAREHOUSE 
 Relação com a Mineração de Dados: 
 
 Em um Data Warehouse, os dados são 
armazenados em diferentes níveis de 
detalhamento, permitindo acesso rápido aos 
mesmos. Além disso, os dados passam pelo 
processo de ETL, em que são realizadas 
atividades de integração, limpeza e 
transformação de dados. 
 
 Consequentemente, o potencial da Mineração de 
Dados pode ser melhorado se os dados 
apropriados tiverem sido coletados de um DW. 
APLICAÇÕES ATUAIS DA 
MINERAÇÃO DE DADOS 
 Comerciais: 
 Tem sido aplicada para achar respostas em 
minimização de custos, gerenciamento de 
estoque, marketing e propaganda, logística e 
geração de novas ideias, em áreas como: vendas 
no atacado e varejo, seguros, manufatura, 
finanças (principalmente bancos e 
administradoras de cartões), saúde e 
telecomunicações. 
 Não comerciais: 
 Algumas áreas são: ciências, diagnóstico 
médico, prevenção de incêndios florestais e 
identificação de estruturas químicas. 
ALGUMAS EMPRESAS QUE USAM 
MINERAÇÃO DE DADOS 
 MasterCard International: 
• Processa mais de 30 milhões de transações/dia e utiliza 
Mineração de Dados para extrair todos os tipos de 
estatísticas possíveis sobre os portadores de cartões. 
 Wal-Mart: 
• Descobriu que o perfil do consumidor de cervejas era 
semelhante ao de fraldas nas sextas-feiras, usando 
algoritmos de associação. Resultado: aproximaram as 
prateleiras dos 2 itens e o consumo cresceu 30% às sextas. 
 McDonalds. 
 Visa. 
 Telefonia (Vivo, Telemig, Tim, Telefonica). 
 Bancos (Itau, Bradesco, etc). 
 Seguradoras (Mapfre, Liberty, etc). 
 Redes de varejo (Americanas, Submarino, Amazon, etc). 
 
 
 
TAREFAS DE MINERAÇÃO: 
ASSOCIAÇÃO 
ASSOCIAÇÃO 
 Tarefa introduzida por Agrawal et al. (1993). 
 
 Definição: 
• Dado um conjunto de transações, no qual cada 
transação corresponde a um conjunto de itens, 
uma regra de associação é uma expressão da 
forma X  Y (se X então Y), onde X e Y são 
conjuntos não vaziosde itens. 
• O significado de tal regra é que transações da 
base de dados que contêm X tendem a 
conter Y também. 
 
REGRAS DE ASSOCIAÇÃO 
 Exemplos: 
 compra (fraldas)  compra (cerveja) 
 compra (pão)  compra (leite, café) 
 venda (pão, presunto)  venda (leite) 
 pão, presunto  leite, café 
 pão, presunto, queijo  leite, café 
 
 Generalizando: 
 X  Y 
onde X e Y são conjuntos disjuntos de itens, podendo estes 
conjuntos conter o mesmo número de elementos ou não. 
 
SUPORTE E CONFIANÇA 
 A cada regra de associação, estão relacionados valores 
de 2 fatores: suporte e confiança, que indicam a 
relevância da regra. Considerando a regra X  Y: 
 
 Suporte: 
 Indica a porcentagem de registros em que aparecem juntos 
X e Y, sobre o total de registros. Isto é, o suporte é a 
porcentagem de transações que contêm todos os itens da 
união de X com Y. 
 
SUP = (nº transações com X e Y) / (nº total transações) 
SUPORTE E CONFIANÇA 
 Confiança: 
 Indica a porcentagem de transações que contêm os itens de 
X e Y juntos, sobre o total de transações que possuem os 
itens de X (sendo X o lado esquerdo da regra). 
 
CONF = (nº transações com X e Y) / (nº transações com X) 
 
 
 A meta da mineração de regras de associação é encontrar 
todas as regras que tenham valores de suporte e de 
confiança iguais ou superiores aos valores mínimos 
definidos pelo usuário. 
APLICAÇÕES DE 
REGRAS DE ASSOCIAÇÃO 
 Algumas das mais importantes: 
 Descobrir afinidades para análises de mercado; 
 Promover vendas conjuntas de determinados 
produtos, principalmente em supermercados, 
livrarias e outros tipos de empresas de varejo; 
 Análise de perda de liderança; 
 Definição de layout de lojas; 
 Projeto de catálogos; 
 Definição de promoções. 
EXEMPLO 1 SOBRE 
REGRAS DE ASSOCIAÇÃO 
 Dada a base de dados a seguir, com transações de compras 
(listas de itens), encontrar todas as regras que relacionam a 
presença de um conjunto de itens com outro, possuindo 
valores mínimos de suporte e confiança de 50%. 
EXEMPLO 1 SOBRE 
REGRAS DE ASSOCIAÇÃO 
 Para suporte e confiança mínimos de 50%, obteremos as 
seguintes regras: 
 A  C com 50% de suporte (A e C aparecem em 50% do 
total de transações) e 66,7% de confiança (C aparece em 
66,7% das transações que contêm A). 
 C  A com 50% de suporte (A e C aparecem em 50% do 
total de transações) e 100% de confiança (A aparece em 
todas as transações que contêm C). 
 
 Note pelas 2 regras acima que o valor da confiança para uma 
regra X  Y não necessariamente será o mesmo para a regra 
Y  X. Na prática, o suporte é sempre o mesmo, mas o valor 
da confiança pode ser diferente para as 2 regras. 
EXEMPLO 2 SOBRE 
REGRAS DE ASSOCIAÇÃO 
 Considere que em uma loja de materiais para 
construção foram efetuadas as seguintes 
transações: 
 
 
 
 
 
 
 
 Que regras de associação podem ser extraídas 
deste conjunto, com grau de suporte >= 40% e 
confiança > 50%? 
EXEMPLO 2 SOBRE 
REGRAS DE ASSOCIAÇÃO 
 Algumas das regras desse exemplo são: 
 
 Areia  Cal (Sup = 40%, Conf = 100%) 
 Cal  Areia (Sup = 40%, Conf = 100%) 
 Areia  Cimento (Sup = 40%, Conf = 100%) 
 Mas note que Cimento  Areia NÃO É VÁLIDA, pois 
Conf=50% 
 Areia  Cal, Cimento (Sup = 40%, Conf = 100%) 
 Cal, Cimento  Areia (Sup = 40%, Conf = 100%) 
 Areia, Cal  Cimento (Sup = 40%, Conf = 100%) 
 Mas note que Cimento  Areia, Cal NÃO É VÁLIDA, pois 
Conf=50% 
 
ASSOCIAÇÕES BOOLEANAS 
 São regras que contêm o AND booleano entre ao 
menos 2 itens do lado esquerdo (antecedente). 
 
 Podem ser tão importantes quanto as regras que 
contêm apenas 1 item no antecedente e no 
consequente (lado direito). 
 
 Exemplo: 
 compra(“SQL Server”), compra(“Livro DM”)  
compra(“DBMiner”) 
REGRAS DE ASSOCIAÇÃO 
MULTI-NÍVEIS 
 Pressupõe uma hierarquia de regras. 
 
 Abordagem top-down progressiva: 
 Inicialmente: encontrar as regras “fortes” de alto nível: 
• Leite  pão [suporte: 40%, confiança: 60%] 
 Em seguida, regras “fracas” de mais baixo nível: 
• Leite  pão branco [suporte: 30%, confiança: 50%] 
 
 
 
MOMENTO DE PRATICAR! 
ALGORITMO PARA 
REGRAS DE ASSOCIAÇÃO 
 Algoritmo de Agrawal e Srikant: Apriori 
(AGRAWAL; SRIKANT, 1994). 
 
 Princípio: todo subconjunto de um conjunto 
frequente de itens deve ser frequente. 
 
 Várias otimizações para melhoria da performance 
computacional. 
 
 Baseado na mineração de conjuntos de itemsets 
frequentes; para isso, minera conjuntos Ck e Lk. 
 
 Os conjuntos Lk são usados para montar as regras 
de associação válidas. 
EXECUÇÃO DO 
ALGORITMO APRIORI 
APRIORI - PRUNE STEP 
 Uma rotina para reduzir o tempo de execução do 
Apriori é chamada de “prune step”, e consiste em 
excluir do conjunto de candidatos Ck todo conjunto 
de k itens que não apresentar pelo menos 1 de 
seus subconjuntos de k-1 itens em Lk-1. 
 
 Assim, o prune step pode reduzir o número de 
candidatos nos conjuntos Ck, agilizando o Apriori. 
APRIORI - PRUNE STEP 
 Ex: considere L3 = {{1 2 3}, {1 2 4}, {1 3 4}, 
{1 3 5}, {2 3 4}}: 
• Após o passo de junção, C4 = {{1 2 3 4}, 
{1 3 4 5}}. 
• Mas o prune step excluirá o conjunto {1 3 4 5} 
porque seu subconjunto {1 4 5} não está em L3. 
Assim, o algoritmo só calculará o suporte de 
{1 2 3 4}, reduzindo em 50% o tempo 
necessário para testar o suporte de C4. 
DESCOBRINDO REGRAS COM O 
ALGORITMO APRIORI 
 Agrawal e Srikant (1994) apresentaram um 
algoritmo eficiente para a descoberta de regras de 
associação válidas, a ser aplicado sobre os 
conjuntos Lk de itemsets frequentes. 
 
 O algoritmo pode ser aplicado a todos os conjuntos 
Lk em que k>=3. Portanto, para L2 deve-se gerar 
todas as possíveis regras com 2 itens e calcular as 
respectivas confianças, a fim de determinar as 
regras válidas. 
 
 Lembre-se: Os conjuntos Lk garantem suporte 
válido, mas nada afirmam sobre a confiança, que 
deverá ser calculada para cada possível regra. 
DESCOBRINDO REGRAS COM O 
ALGORITMO APRIORI 
 Algoritmo: Para cada conjunto Lk em que k >= 3: 
 Monte todas as possíveis regras de associação com k-1 
elementos do lado esquerdo (antecedente) e apenas 1 
elemento do lado direito (consequente) da regra. 
 Calcule a confiança de cada regra gerada no passo 
anterior e conclua: 
• Se uma regra deste tipo tiver confiança abaixo da exigida, 
não há necessidade de calcular a confiança de todas as 
regras com lado esquerdo que seja subconjunto dos k-1 
elementos da regra já testada – no caso, regras que teriam 
k-2 elementos no lado esquerdo, pois todas elas também 
terão confiança abaixo da mínima exigida. 
• Se uma regra deste tipo tiver confiança satisfatória, não 
pode-se afirmar nada sobre as regras cujo lado esquerdo seja 
subconjunto dos k-1 elementos da regra já testada. Neste 
caso, deve-se calcular as confianças das regras com k-2 
elementos do lado esquerdo para descobrir se são relevantes. 
DESCOBRINDO REGRAS COM O 
ALGORITMO APRIORI 
 Para exemplificar o algoritmo anterior, suponha 
que L4 = {{A B C D}}: 
 Assim, se, por exemplo, tomarmos o subconjunto com k-1 
elementos {A B C} para formar a regra R1: ABC  D e 
descobrirmos que o valor da confiança desta regra R1 é 
inferior ao mínimo exigido, então não precisaremos 
calcular a confiança das regras cujo lado esquerdo é 
subconjunto do lado esquerdo de R1, pois todas essas 
regras também terão confiança insatisfatória. 
 Portanto, assumindo que R1 é insatisfatória, não 
precisaríamos gastar tempo calculando a confiança das 
regras AB  CD, AC  BD e BC  AD. 
DESCOBRINDOREGRAS: UM 
ALGORITMO MAIS RÁPIDO 
 Ainda em seu artigo de 1994, Agrawal e Srikant 
propuseram um algoritmo mais eficiente do que o 
anteriormente explicado aqui para montar e 
descobrir regras de associação válidas. 
 
 Assim como o primeiro algoritmo apresentado, este 
novo algoritmo (que chamaremos de Algoritmo 2) 
pode ser aplicado a todos os conjuntos Lk em que 
k>=3. 
DESCOBRINDO REGRAS: UM 
ALGORITMO MAIS RÁPIDO 
 Algoritmo 2: Para cada conjunto Lk em que k >= 3: 
 Monte todas as possíveis regras de associação com k-1 
elementos do lado esquerdo (antecedente) e apenas 1 
elemento do lado direito (consequente) da regra. 
 Calcule a confiança de cada regra gerada no passo 
anterior e despreze todas as que tiverem confiança 
insuficiente. 
 Faça todas as combinações possíveis com os itens do lado 
direito das regras que sobraram, ou seja, das regras que 
têm apenas 1 item no consequente, produzindo portanto 
novas regras do tipo (k-2 itens)  (2 itens). 
 Calcule a confiança de cada uma das regras do tipo (k-2 
itens)  (2 itens) geradas no passo anterior, pois serão as 
únicas deste tipo com possibilidade de ter confiança 
satisfatória. 
 
DESCOBRINDO REGRAS: UM 
ALGORITMO MAIS RÁPIDO 
 Para exemplificar, suponha que L5 = {{A B C D E}} e que as 
únicas regras com k-1 itens à esquerda que têm confiança 
satisfatória são ACDE  B e ABCE  D. 
 
 Agrawal e Srikant provaram em seu artigo que a única regra 
com 2 itens no consequente que tem chance de ser válida é 
aquela cujo lado direito é formado pela combinação dos 
consequentes das regras válidas de 1 item citadas acima, ou 
seja, deve-se calcular a confiança apenas da regra ACE  BD, 
desprezando todas as outras possíveis regras com 2 itens no 
consequente. 
 
 Portanto, ACE  BD seria a única regra testada pelo 
algoritmo mais rápido (Algoritmo 2), enquanto o primeiro 
algoritmo explicado testaria muito mais regras. 
CONCLUSÕES SOBRE O APRIORI 
 É o algoritmo implementado em ferramentas de 
mineração de dados capazes de minerar regras de 
associação. 
 
 Atualmente possui algumas variações, como por 
exemplo o AprioriTid e o AprioriHybrid, que podem 
ser mais eficientes em configurações específicas do 
repositório de dados. 
RESUMO SOBRE REGRAS DE 
ASSOCIAÇÃO 
 A mineração de regras de associação é considerada por 
muitos como a contribuição mais significativa da 
comunidade de BD para a área de Data Mining. 
 
 Há uma quantidade enorme de trabalhos publicados a 
respeito. 
 
 Direções de pesquisa: 
 Análise de associações em outros tipos de dados: 
espaciais, multimídia, temporais, etc. 
REFERÊNCIAS BIBLIOGRÁFICAS 
 AGRAWAL, R.; SRIKANT, R. Fast Algorithms for Mining Association 
Rules. In: Proceedings of the 20th International Conference on Very Large 
Data Bases. 1994. San Francisco: Morgan Kauffman, 1994. 
 AGRAWAL, R.; IMIELINSKI, T.; SWAMI, A. Mining Association Rules 
between Set of Itens in Large Databases. In: ACM SIGMOD INT'L 
CONFERENCE ON MANAGEMENT OF DATA, 1993. Proceedings. 
 ELMASRI, R.; NAVATHE, S. Fundamentals of Database Systems. 4 ed. 
New York: Addison-Wesley, 2003. 
 HAN, J.; KAMBER, M. Data Mining: Concepts and Techniques. 2 ed. San 
Francisco: Morgan Kaufmann, 2006. 
 VERCELLIS, C. Business Intelligence: Data Mining and Optimization for 
Decision Making. New York: Wiley, 2009. 
 WILLIAMS, G.; HEGLAND, M.; ROBERTS, S. A Data Mining Tutorial. In: 
2nd IASTED International Conference on Parallel and Distributed Computing 
and Networks (PDCN’98). 1998. 
 http://dms.irb.hr/tutorial/tut_main.php 
 http://www.information-management.com