Universidade Federal de Uberlândia - Mestrado em Ciência da Computação
Lista de Exercı́cios n0 2 - Data Mining : SEQUÊNCIAS
10 Semestre de 2003
Profa. Sandra A. de Amo
Exercı́cios muito fáceis, simples aplicação de algoritmos vistos em aula, cujo
objetivo é rever e testar se a matéria dada em aula foi bem assimilada.
1. Considere o seguinte banco de dados de sequências de transações de clientes:
IdCl
c1
c2
c3
c4
c5
c6
c7
c8
c9
c10
Itemsets
< {1, 2, 7}, {3, 9, 10}, {4, 7, 8} >
< {2, 9, 10}, {1, 6}, {7, 5} >
< {1}, {4, 8}, {2, 9}, {3, 10} >
< {2}, {2, 8}, {7, 9} >
< {10}, {5, 7} >
< {5, 8}, {1, 3}, {2, 7} >
< {1, 2, 7, 5}, {3, 9, 10, 8} >
< {9}, {2}, {4} >
< {8}, {10}, {11, 12} >
< {2, 9}, {1, 2, 6}, {7, 10} >
Supondo um limite mı́nimo de suporte de 20%, aplique o algoritmo Apriori-All sobre
este banco de dados e exiba todas as k-sequências de itemsets frequentes.
2. Considere o mesmo input do problema anterior. Resolva o problema aplicando o
algoritmo GSP.
3. Considere o seguinte banco de dados de sequência de compras de clientes (onde em
cada compra, só um item foi comprado).
IdCl
c1
c2
c3
c4
c5
c6
c7
c8
c9
c10
Itemsets
< a, c, d, e >
< a, e, f, g >
< b, f, e >
< c, f, e, h, i >
< a, e, f, g >
< g, h, a, f, e >
< a, g, g, a, f, h >
< g, h, h, f, e >
< f, e, a >
< g, f, f, f, a >
Considere um nı́vel mı́nimo de suporte de 20% e uma expressão regular R =
aE ∗ e + gE ∗ f (o usuário só está interessado em sequências que iniciam com a e
terminam com e ou em sequências que iniciam com a g terminam com f). A expressão E é dada por E = (a + b + c + d + e + f + g + h + i).
Resolva o problema aplicando o algoritmo SPIRIT(V) e SPIRIT(N). Repare que
ambos devem dar os mesmos resultados. Complete o seguinte quadro estatı́stico
abaixo :
Algoritmo
Total de Candidatos Gerados
Número de Iterações
SPIRIT(N)
SPIRIT(V)
4. Dê um exemplo que justifique por que, na fase da podagem dos algoritmos SPIRIT,
para que uma k-sequência s seja podada é necessário verificar a existência de uma
subsequência s0 de tamanho menor do que k que satisfaça a restrição R e não seja
frequente, isto é, que s0 6∈ L. Isto é : você deve exibir uma s de tamanho k (por
exemplo, 3) tal que toda subsequência de tamanho 2 é frequente e satisfaz R, mas
existe uma de tamanho 1 que não satisfaz R. Isto seria possı́vel se a restrição fosse
antimonotônica ?
Exercı́cios razoavelmente fáceis e que exigem um mı́nimo de raciocı́nio
5. Suponha que um usuário de um sistema de Data Mining esteja interessado em
minerar sequências de itemsets, mas deseja interagir com o mesmo propondo certas
condições sobre as sequências a serem mineradas. Para cada uma das propostas
abaixo, classifique-a em Restrições de Geração ou Restrições de Validação, justificando muito bem sua resposta :
(a) Só estou interessado em sequências de compras semanais, isto é, que ocorrem
a cada perı́odo de 7 dias.
(b) Só estou interessado em sequências de compras que possuem items que se
repetem a cada compra.
(c) Só estou interessado em sequências de compras semanais, isto é, que ocorrem
a cada perı́odo de 7 dias e onde em cada compra consta o item ”cerveja”.
(d) Só estou interessado em sequências de compras que ocorrem em dias de jogo da
selecao brasileira de futebol e onde em cada compra consta o item ”cerveja”.
(e) Só estou interessado em sequências de compras que ocorrem num intervalo de
30 dias.
(f) Só estou interessado em sequências de compras que ocorrem num intervalo de
30 dias e tais que o intervalo entre uma compra e outra não excede 2 dias.
(g) Só estou interessado em sequências de compras que ocorrem num intervalo de
30 dias e tais que o intervalo entre uma compra e outra é de pelo menos 3 dias.
(h) Só estou interessado em sequências de compras que ocorrem num intervalo de
30 dias e que contenham, no total dos items comprados durante este perı́odo,
todos os itens que constam da “cesta básica”
(i) Só estou interessado em sequências de compras onde pelo menos uma das compras contenha o itemset “cerveja” e onde pelo menos uma das compras contenha
o itemset “vinho” (estas compras respectivas podem ou não corresponderem à
mesma compra).
6. Considere o seguinte problema de mineração de dados : o banco de dados D é constituı́do de três tabelas :
Cliente(IdCl,Cidade,Telefone)
Loja(IdLoja,NomeL,Cidade)
Compra(IdCl,IdLoja,Itemset,Data)
Suponha que o seu cliente (usuário do seu sistema de mineração de dados) esteja
interessado em :
(*) : Conhecer a evolução das compras dos clientes que moram numa
cidade A, e tais que as compras foram efetuadas numa certa rede
de lojas B, numa filial que fica na cidade C.
Repare que A, B, C são parâmetros fornecidos pelo usuário. O seu problema de
mineração consiste pois no seguinte :
Input : D, um nı́vel mı́nimo de suporte α, um valor para A, um valor para B e um
valor para C.
Output : todas as sequências frequentes satisfazendo a condição (*) requerida pelo
usuário.
Pede-se : adapte o algoritmo GSP para resolver este problema.
Sugestão: O requisito do usuário (*) consiste em considerar a seguinte visão materializada (ou data warehouse) sobre os dados:
SELECT Cliente.IdCl,Cliente.Itemset, Cliente.Data
FROM Cliente, Loja, Compra
WHERE Compra.IdCl = Cliente.IdCl AND Loja.IdLoja = Compra.IdLoja
AND NomeL = A AND Cliente.Cidade = B AND Loja.Cidade = C
Exercı́cios razoavelmente difı́ceis (não muito, perfeitamente dentro do
que se espera de um mestrando), que exigem um pouco de raciocı́nio e
criatividade
7. Adapte o algoritmo GSP para minerar sequências satisfazendo uma restrição de
MIN-MAX (m,M) dada.(Não se exige que o algoritmo que você dê seja o mais
eficiente possı́vel, mas seria importante que você tentasse raciocinar no sentido de
propor uma maneira eficiente de resolver o problema).
8. Adapte o algoritmo GSP para minerar sequências satisfazendo uma restrição de
TIME-WINDOW W dada. (Não se exige que o algoritmo que você dê seja o mais
eficiente possı́vel, mas seria importante que você tentasse raciocinar no sentido de
propor uma maneira eficiente de resolver o problema).
9. Desenvolva um método para armazenar sequências numa árvore-hash de modo a
ser utilizado nas etapas de cálculo do suporte e poda no algoritmo Apriori-All.
Lembre-se que neste algoritmo, os itemsets frequentes são calculados logo no inı́cio
e enumerados. A partir daı́, os padrões sequenciais são sequências de números.
Lembre-se também que o Apriori-All transforma o banco de dados de input num
banco de dados de sequências de conjuntos de números( onde cada número corresponde a um itemset frequente na ordenação estabelecida). Veja portanto que, ao
contrário do que acontece em GSP, no algoritmo Apriori-All os padrões sequenciais e
as sequências do cliente são objetos de natureza distinta: o primeiro é um sequência
de números (representando itemset frequentes), o segundo é uma sequência de conjuntos de números (cada número representando um itemset frequente).
10. Mostre que no algoritmo SPIRIT(L), se L0q0 = ∅ (o conjunto das sequências frequentes e legais com respeito ao estado incial do autômato e que têm comprimento
igual a k) então o algoritmo SPIRIT(L) pára.
11. Suponha que uma cadeia de pizzarias esteja interessada em minerar o comportamento de consumo de seus clientes, relacionado a grandes eventos esportivos. Coisas
do tipo “Toda vez que é transmitido um jogo da seleção de futebol brasileira pela
TV, as vendas de pizza sobem de 20% uma hora antes do inı́cio do jogo”.
(a) Formalize o problema : quais são os padrões sequenciais ? Como é o banco de
dados de input ? O que é um padrão frequente ?
(b) Proponha um método para resolver este problema.