Upload
internet
View
102
Download
0
Embed Size (px)
Citation preview
CLOSET: An Efficiet Algorithm for Mining Frequent Closed
ItemsetsJian Pei, Jiawei Han, and Runying MaoJian Pei, Jiawei Han, and Runying Mao
Augusto Klinger
RoteiroRoteiro
IntroduçãoIntrodução DefiniçõesDefinições CLOSETCLOSET
ExemploExemplo OtimizaçõesOtimizações AlgoritmoAlgoritmo EscalabilidadeEscalabilidade
PerformancePerformance ConclusãoConclusão
IntroduçãoIntrodução
Geralmente, mineração por regras de Geralmente, mineração por regras de associação resulta em muitos itemsets e associação resulta em muitos itemsets e regras.regras.
Solução:Solução: minerar somente itemsets minerar somente itemsets fechados frequentes (Pasquier et al.)fechados frequentes (Pasquier et al.)
Mesmo poderMesmo poderMenos redundânciaMenos redundânciaMais eficiênciaMais eficiência
IntroduçãoIntrodução
CLOSETCLOSET
1.1. Aplicação de um estrutura FP-tree para Aplicação de um estrutura FP-tree para minerar itemsets fechados frequentesminerar itemsets fechados frequentes
2.2. Tecnica de compressão de caminho Tecnica de compressão de caminho para identificar itemsets fechados para identificar itemsets fechados frequentes rapidamentefrequentes rapidamente
3.3. Mecanismo de projeção baseado em Mecanismo de projeção baseado em partição para escalabilidadepartição para escalabilidade
DefiniçõesDefinições
ProblemaProblemaAchar todos itemsets frequentesAchar todos itemsets frequentesPara cada itemset, gerar as regras de Para cada itemset, gerar as regras de
associaçãoassociação
DefiniçõesDefinições
Frequent Closed Itemset (FCI):Frequent Closed Itemset (FCI):Um Itemset X é fechado se não existir um Um Itemset X é fechado se não existir um
itemset X’ queitemset X’ queX’ é superconjunto próprio de XX’ é superconjunto próprio de XToda transação que contém X contém X’Toda transação que contém X contém X’X > X’ e sup(X) = sup(X’)X > X’ e sup(X) = sup(X’)
Itemset fechado é frequente se o suporte Itemset fechado é frequente se o suporte passa o suporte mínimo.passa o suporte mínimo.
DefiniçõesDefinições
Regras de associação em FCIRegras de associação em FCI XX→→YY
X e XX e XUUY são FCIY são FCI Não existir Z, tal que X<Z<(XNão existir Z, tal que X<Z<(XUUY)Y) Passar o nível de confiançaPassar o nível de confiança
Processo de Mineração é similarProcesso de Mineração é similar1.1. Minerar FCIs com min_supMinerar FCIs com min_sup
2.2. Gerar regras nos FCIs com min_confGerar regras nos FCIs com min_conf
DefiniçõesDefinições
ExemploExemploMin_sup = 2Min_sup = 2Min_conf = 50%Min_conf = 50%
R: FCI: acdf Não FCI: ac, f
CLOSETCLOSET
• Minera FCIs por um método de divisão e conquista
• Explora o conceito de projeção de base de dados
• Exemplo...
CLOSETCLOSET
1.1. Encontrar os itens frequentesEncontrar os itens frequentes F_list = [c:4, e:4, f:4, a:3, d:2]F_list = [c:4, e:4, f:4, a:3, d:2]
2.2. Dividir o espaço de buscaDividir o espaço de busca Baseado na f_list, 5 espaços contendo:Baseado na f_list, 5 espaços contendo:
1.1. dd
2.2. aa e não e não dd
3.3. ff e não e não a a nem nem dd
4.4. ee e não e não dd nem nem aa nem nem ff
5.5. Somente Somente cc
CLOSETCLOSET
CLOSETCLOSET
3.3. Encontrar subconjuntos de FCIsEncontrar subconjuntos de FCIs Construir e minerar Construir e minerar conditional databasesconditional databases
recursivamenterecursivamentea)a) FCIs com FCIs com dd
cc,, f f ee a a aparecem em todas transaçõesaparecem em todas transações e e é infrequenteé infrequente cfadcfad: 2 é um FCI: 2 é um FCI
CLOSETCLOSET
CLOSETCLOSET
b)b) FCIs com FCIs com aa e não e não dd Nenhum item em toda transaçãoNenhum item em toda transação aa: 3 é um FCI – mas pode ter mais: 3 é um FCI – mas pode ter mais
CLOSETCLOSET
CLOSETCLOSET
para achar os outros:para achar os outros:Local f_listLocal f_lista a = (c:2, e:2, f:2)= (c:2, e:2, f:2) Particionar o espaço de acordo com a Particionar o espaço de acordo com a f_listf_listaa
1)1) Contendo Contendo afaf mas não mas não dd
2)2) Contendo Contendo aeae mas não mas não dd ou ou ff
3)3) Contendo Contendo acac mas não mas não dd, , ee ou ou ff sup(af) = sup(cfad) = sup(ca)sup(af) = sup(cfad) = sup(ca) Tabela do Tabela do aeae não tem item frequente, então: não tem item frequente, então: eaea: 2 é um FCI: 2 é um FCI
CLOSETCLOSET
CLOSETCLOSET
c)c) FCIs com FCIs com ff e não e não a a nem nem dd cc aparece em todas transações aparece em todas transações sup(cf) != sup(cfad)sup(cf) != sup(cfad) cf:cf: 4 é um FCI 4 é um FCI cefcef não é subconjunto de ninguém não é subconjunto de ninguém cef:cef: 3 é um FCI 3 é um FCI
CLOSETCLOSET
CLOSETCLOSET
d)d) FCIs com FCIs com ee e não e não dd nem nem aa nem nem ff sup(ce) = sup(cef)sup(ce) = sup(cef) ee: 4 é um FCI: 4 é um FCI
e)e) FCIs com somente FCIs com somente cc Como não há FCI contendo Como não há FCI contendo cc e não e não ff, não há , não há
FCI somente com FCI somente com cc..
CLOSETCLOSET
CLOSET – Otimização 1CLOSET – Otimização 1
FP-treeFP-treeÁrvore de prefixosÁrvore de prefixosCompreçãoCompreção
Transações com mesmo prefixo compartilham Transações com mesmo prefixo compartilham uma parte do caminho a partir da raízuma parte do caminho a partir da raíz
Conditional databasesConditional databases podem ser derivadas podem ser derivadas eficientementeeficientementeA projeção de um caminho é equivalente a A projeção de um caminho é equivalente a
multiplas transaçõesmultiplas transações
CLOSET – Otimização 2CLOSET – Otimização 2
Extrair itens que aparecem em toda Extrair itens que aparecem em toda transação da transação da conditional databaseconditional databaseSe Y aparece em toda transação da Se Y aparece em toda transação da X-X-
conditional databaseconditional database, X, XUUY é um FCI, caso Y é um FCI, caso não seja subconjunto próprio de outro FCI não seja subconjunto próprio de outro FCI com mesmo suporte.com mesmo suporte.No exemplo, o itemset cfadNo exemplo, o itemset cfad
Excluir item extraído da local f_list e da Excluir item extraído da local f_list e da cconditional databaseonditional database
CLOSET – Otimização 2CLOSET – Otimização 2
Reduz o tamanho da FP-treeReduz o tamanho da FP-tree
Pode reduzir o nível de recursãoPode reduzir o nível de recursão
CLOSET – Otimização 3CLOSET – Otimização 3
Extrair FCIs diretamente da FP-treeExtrair FCIs diretamente da FP-treeSe existir um caminho único, alguns FCIs podem Se existir um caminho único, alguns FCIs podem
ser extraídos diretamente da ser extraídos diretamente da condicional databasecondicional database
Sendo Sendo ii um item frequente numa X- um item frequente numa X-condcondSó um nodo N contendo Só um nodo N contendo ii
Antecessores de N tem só um filhoAntecessores de N tem só um filhoN tem 0 ou mais filhosN tem 0 ou mais filhos
Então, a união de X, N e antecessores Então, a união de X, N e antecessores (menos a raíz) é um FCI (se obedecer as (menos a raíz) é um FCI (se obedecer as regras!)regras!)
CLOSET – Otimização 3CLOSET – Otimização 3
Exemplo:Exemplo:
•FP-tree tem só um caminho (c:4, e:3)•Pode-se enumerar diretamente cf:4 e cef: 3
c
e
CLOSET – Otimização 4CLOSET – Otimização 4
Podar galhosPodar galhosSe X e Y são itensets frequentesSe X e Y são itensets frequentessup(X) = sup(Y)sup(X) = sup(Y)X < YX < YY é FCIY é FCIEntão, não há necessidade de procurar na X-Então, não há necessidade de procurar na X-
cond!cond!Como no exemplo foi desconsiderada a C-Como no exemplo foi desconsiderada a C-
cond por cond por cc ser subconjunto de ser subconjunto de fc fc
CLOSET – Otimização 4CLOSET – Otimização 4
CLOSET – AlgoritmoCLOSET – Algoritmo
CLOSET – AlgoritmoCLOSET – Algoritmo
CLOSET – AlgoritmoCLOSET – Algoritmo
1.1. Inserir YInserir YUUX em FCI se Y aparece em X em FCI se Y aparece em todas as transações da DB(e respeita as todas as transações da DB(e respeita as regras) // regras) // Otimização 2Otimização 2
2.2. Contruir FP-tree da DB sem os itens já Contruir FP-tree da DB sem os itens já extraídos // extraídos // Otimização 1Otimização 1
3.3. Extraír FCIs se possível Extraír FCIs se possível // Otimização 3// Otimização 3
CLOSET – AlgoritmoCLOSET – Algoritmo
4.4. Montar Montar conditional databases conditional databases para ítens para ítens restantes da f_list e computar suas restantes da f_list e computar suas respectivas f_lists.respectivas f_lists.
5.5. Para cada ítem Para cada ítem ii restante na f_list, a restante na f_list, a partir do último, chamar CLOSET(iX, DBi, partir do último, chamar CLOSET(iX, DBi, f_listf_listii, FCI) SE iX não for subconjunto , FCI) SE iX não for subconjunto com mesmo suporte de algum FCI já com mesmo suporte de algum FCI já encontrado! // encontrado! // Otimização 4Otimização 4
CLOSET – EscalabilidadeCLOSET – Escalabilidade
Para grandes TDBs, FP-trees não cabem Para grandes TDBs, FP-trees não cabem na memóriana memória
Solução:Solução:Contruir primeiro Contruir primeiro conditional databases conditional databases sem sem
FP-treesFP-treesConstruir FP-trees baseadas em disco Construir FP-trees baseadas em disco
[[Mining frequent patterns without candidate Mining frequent patterns without candidate generationgeneration]]
CLOSET – EscalabilidadeCLOSET – Escalabilidade
Um método simples:Um método simples:Expandir todas Expandir todas conditional databasesconditional databases, uma , uma
por vezpor vezDuplicaria TDB L/2 vezesDuplicaria TDB L/2 vezesL é o numero médio de itens frequentes nas L é o numero médio de itens frequentes nas
transaçõestransaçõesConstrução de muitas Construção de muitas conditional databases conditional databases
pode ser uma operação custosapode ser uma operação custosa
CLOSET – EscalabilidadeCLOSET – Escalabilidade
Método baseado em partiçãoMétodo baseado em partiçãoPode reduzir drasticamente o espaçoPode reduzir drasticamente o espaçoConsiste em copiar uma transação somente Consiste em copiar uma transação somente
para a para a conditional database conditional database que contém o que contém o ultimo ítem da sua f_list.ultimo ítem da sua f_list.
CLOSET – EscalabilidadeCLOSET – Escalabilidade
Exemplo:Exemplo:d d é o ultimo ítem da f_list de é o ultimo ítem da f_list de cefadcefadAo invés de copiar para d- a- f- e- condAo invés de copiar para d- a- f- e- condSó copia para a d-condSó copia para a d-condDepois de processar a d-cond, a transação é Depois de processar a d-cond, a transação é
copiada para a próxima copiada para a próxima conditional database, conditional database, e assim por diante.e assim por diante.
CLOSET – EscalabilidadeCLOSET – Escalabilidade
CLOSET – EscalabilidadeCLOSET – Escalabilidade
Uma vez terminada a partição, a tabela Uma vez terminada a partição, a tabela original pode ser descartada.original pode ser descartada.
FP-trees são contruídas somente depois FP-trees são contruídas somente depois de algumas rodadas (quando as de algumas rodadas (quando as conditional databases conditional databases couberem na couberem na memória)memória)
PerformancePerformance
CLOSET x CHARM x A-closeCLOSET x CHARM x A-closePentium 233 MHzPentium 233 MHz
128 MB128 MBWindows NTWindows NTVisual C++Visual C++
Testado em 3 conjuntos de dadosTestado em 3 conjuntos de dados
PerformancePerformance
T25l20D100K (sintética)T25l20D100K (sintética)100.000 transações100.000 transaçõesTransações de tamanho 25Transações de tamanho 25 Itemsets frequentes de tamanho 20Itemsets frequentes de tamanho 20
Performance - T25l20D100KPerformance - T25l20D100K
PerformancePerformance
Connect-4 Connect-4 (real)(real)67.557 transações67.557 transações43 itens por transação43 itens por transação
Performance - Performance - Connect-4 Connect-4
Numero de itemsets frequentes pode ser reduzido em uma ordem de magnitude numa DB densa, se representados por FCIs
Performance - Performance - Connect-4 Connect-4
PerformancePerformance
Pumsb (real)Pumsb (real)49.046 transações49.046 transações74 itens por transação74 itens por transação
Performance - PumsbPerformance - Pumsb
Performance - EscalabilidadePerformance - Escalabilidade
ConclusãoConclusão
Minerar FCIs é uma alternativa Minerar FCIs é uma alternativa interessanteinteressanteMenos itemsetsMenos itemsetsMenos regras, e mais interessantesMenos regras, e mais interessantes
CLOSET é eficiente e escalávelCLOSET é eficiente e escalável
FIMFIM
Perguntas?Perguntas?