Skip to content

Latest commit

 

History

History
974 lines (885 loc) · 39.3 KB

notebook.org

File metadata and controls

974 lines (885 loc) · 39.3 KB

Aprendizado Descritivo

Definição

Aprendizado descritivo se enquadra na seguinte classificação dos métodos de aprendizado de máquina:

Aprendizado preditivo:
supervisionado ou não, tem como objetivo predizer dada característica (target).
Aprendizado descritivo:
supervisionado ou não, tem como objetivo obter uma descrição para os dados.

Contrastando, o aprendizado preditivo pretende prever dados futuros ou desconhecidos, enquando o apredizado descritivo prentende trazer uma instrospecção sobre os dados. Tal diferença pode se apresentar de forma tênue. Um exemplo são os algorítmos de agrupamento, que podem ser utilizados em ambas formas. Particularmente, o algorítmo K-means se apresenta:

Preditivo:
K-means: $P → C$
Descritivo:
K-means: $A → C$

Em aprendizado preditivo, o K-means possui como domínio toda a população, ainda que o treinamento seja realizado apenas com uma amostra. Já no aprendizado descritivo, nos limitamos à amostra, afinal ela constitui o alvo total de análise.

Mineração de itens frequentes

Define-se como itens frequentes um conjunto itens que são recorrentes em um conjunto de transações. Considera-se nos conjuntos de dados:

  1. Os itens são os elementos do conjunto de variáveis de análise $I$.
  2. Um conjunto $X \subseteq I$ é denominado itemset.
  3. O conjunto de todos k-/itemsets/ é denotado port $I(k)$.
  4. A amostra de transações é denominada por $T$.
  5. Cada transação é identificada unicamente por um tid.
  6. Um conjunto $Y \subseteq T$ é denominado tidset.
  7. Cada transação consiste de um identificador, e um conjunto de itens: $(\text{tid}, X),\> X \subseteq I$

Formalmente, um conjunto de dados será uma tripla $(T, I, D)$, onde $D \subseteq T × I$ é uma relação binária:

@@latex:\newpage@@

Uma transação pode conter um itemset, e tal relação é definida da seguinte forma:

O conjunto de transações que contém um itemset $X$ é denominado extensão ou cobertura de $X$.
Tal conjunto é definido pela seguinte operação:

Analogamente, o maior conjunto de itens comuns à um tidset $Y$ é chamado de intensão de $Y$.

Desta forma, podemos representar um conjunto de dados de duas formas:

Horizontal:
o conjunto de transações e suas intensões: $\big\{\big(t, i(\{t\})\big) \mid t ∈ T \big\}$
Vertical :
o conjunto de itens e suas coberturas: $\big\{\big(x, c(\{x\})\big) \mid x ∈ I \big\}$

Metodologia

A identificação de regras de associação, em geral, envolve duas etapas:

  1. Mineração de conjuntos de itens frequentes
  2. Descoberta de regras de associação

Devido à natureza computacionalmente intensa da primeira etapa, nossos estudos a focam.

O limiar que separa os itens frequentes dos infrequentes é chamado de suporte mínimo.
O suporte de um itemset é o tamanho de sua cobertura:

Admite-se também a definição de suporte relativo:

Algoritmos

O espaço de busca do problema é o conjunto potência do conjunto de itens. Se considerarmos a relação de subconjuntos como uma relação de ordem parcial, temos que o espaço de busca é estruturado como um reticulado. Este reticulado pode ser visualizado como um grafo, onde somente as relações diretas são representadas.

  • Se $A \subseteq B ∧ |A| = |B| - 1$, então existe uma aresta de $A$ para $B$.

Assim, a mineração de conjunto de itens frequentes é resolvida por uma busca neste reticulado, seja em largura ou em profundidade. De fato, existem abordagens baseadas em ambos métodos.

No entanto, a maioria das abordagens compartilham a mesma estrutura de busca:

  1. Identificam candidatos navegando o espaço de busca
  2. Computam o suporte desses candidatos, descartando os infrequentes

@@latex:\newpage@@

Algoritmo ingênuo

Um algorítmo ingênuo é definido: enumerar cada itemset possível, e verificar no conjunto de dados quais transações contêm esse itemset.

  • A computação do suporte de um itemset requer uma passada sobre o conjunto de dados: $\mathcal{O}(|T|)$
  • Verificar se uma dada transação contém um itemset: $\mathcal{O}(|I|)$
  • Portanto, o custo total de computação do suporte é $\mathcal{O}(|I| ⋅ |T|)$
  • O espaço de busca, por sua vez, é o conjunto potência de $I$.

Logo, a complexidade do algoritmo ingênuo é $\mathcal{O}\big(2|I| ⋅ |I| ⋅ |T|\big)$.

Vale notar que, devido aos seus tamanhos, a memória principal tipicamente não comporta o conjunto de dados. Tal característica agrava fortemente a ineficiência deste algorítimo, onde o componente $\mathcal{O}(|I| ⋅ |T|)$ corresponde à passadas no conjunto de dados.

Apriori

O algoritmo Apriori é viabilizado pela propriedade de anti-monotonicidade da função suporte:

O Apriori utiliza busca em largura para minerar os padrões. A busca inicia com a identificação dos itens frequentes. Depois, os conjuntos de tamanho $k$ são explorados antes dos imediatamente maiores. Assim como o ingênuo, ele também opera em duas etapas:

  1. Geração de candidatos
  2. Cálculo do suporte e eliminação dos infrequentes.

Candidatos que diferem em apenas um item são combinados para gerar os próximos candidatos, de tamanho $k + 1$. Imediatamente, os que possuirem algum subconjunto infrequente são descartados. Utilizando este método, os suportes dos candidatos são atualizados com uma única passada no conjunto de dados.

No total, o número de passadas é drasticamente reduzido: $\mathcal{O}(|I|)$

Apesar disso, o algoritmo ainda apresenta problemas:

  • Nem sempre a memória primária comporta todos candidatos de um nível, demandados para busca em largura.
  • As operações de poda e cálculo do suporte podem ser consideravelmente custosas, mas podem ser atenuadas com estruturas de dados apropriadas.
  • A redução do suporte mínimo implica um grande impacto no custo computacional, pois quanto mais profundo o nível, seu tamanho cresce exponencialmente.
  • A densidade da base de dados também decorre em um custo maior: transações com mais itens implicam itemsets maiores, mais subconjuntos são gerados para a contagem do suporte.

@@latex:\newpage@@

Equivalence Class Transformation

O Eclat tem como proposta eliminar a necessidade de passadas no conjunto de dados para computar o suporte. Para isso, utiliza-se uma representação vertical dos dados, e o fato de que a cobertura da união de dois itemsets é a interseção de suas coberturas.

De forma equivalente, a ideia central do algoritmo é manter os tidsets em memória principal para computar o suporte dos itemsets através de interseções desses conjuntos. Contudo, a memória principal pode não comportar todos os tidsets. Assim, é necessário algum mecanismo que possibilite a divisão do espaço de busca em subproblemas independentes.

Esta divisão pode ser feita conforme uma relação de equivalência estabelecida sobre os candidatos. Seja $p: \mathcal{P}(I) × N → \mathcal{P}(I)$ uma função prefixo. A seguinte relação é uma relação de equivalência:

Dessa forma, induz-se uma partição dos conjuntos de itens em classes de equivalência, onde todos os elementos compartilham um certo prefixo.

Durante a busca em profundidade, o algoritmo particiona os conjuntos de itens conforme a relação de equivalência e o nível da árvore. O cálculo do suporte no algoritmo se restringe a calcular o tamanho do tidset.

Apesar disso, o algoritmo ainda apresenta problemas:

  • O tempo de execução depende do cálculo da interseção dos tidsets.
  • O custo computacional do algoritmo está diretamente relacionado ao tamanho dos tidsets.
  • O custo de espaço também depende do tamanho. Quanto mais denso o conjunto de dados, mais largos serão os tidsets.

dEclat

De forma a atacar o problema de espaço do Eclat, podemos substituir os tidsets pela diferença entre os mesmos e os prefixos que os definem para os membros de cada classe. Tal conjunto é denomidado diffset. Para um prefixo $P$ e um itemset $PX$, o diffset de $X$ é

Somente os diffsets são armazenados, portanto o suporte não é mais obtido como a cardinalidade desse conjunto. Calculamos o suporte de um itemset $PXY$, obtido a partir de $PX$ e $PY$, da seguinte forma:

Tal solução passa por computar o diffset de $PXY$:

Em outras palavras, podemos usar os diffsets dos conjuntos base para calcular o diffset do novo candidato.

Essa abordagem se mostra muito eficiente para conjuntos densos. Porém, em conjuntos esparsos, o algoritmo original é a melhor opção.

FP-Growth

O algoritmo FP-Growth procura atacar dois problemas presentes nas abordagens anteriores:

  • Repetidas passadas sobre a base de dados.
  • Geração de candidatos.

Para isso:

  1. Adota-se uma estratégia de busca em profundidade.
  2. Adota-se projeções dos dados para mantê-los em memória principal.
  3. Utiliza-se uma árvore especial de prefixos denominada FP-Tree.
  4. Busca-se os padrões inteiramente através desta árvore, sem necessidade de retorno aos dados.

A FP-Tree constitui uma árvore de prefixos tradicional, adicionada de uma tabela auxiliar de localização. Cada nó contém um item e sua frequência naquele prefixo. Portanto, um mesmo item pode constar em vários nós, caso ocorra em prefixos distintos. Já a tabela possui as seguintes colunas:

1. Item:
identificador do item, índice da tabela.
2. Frequência:
frequência individual de cada item (denota a ordem dos itens).
3. Nós:
coleção de referências para os nós da árvore referentes ao item.

Sua construção se dá em duas fases:

1. Computa-se a frequêcia individual dos itens:
(Uma passada nos dados)
Itens infrequentes são descartados, pois não podem formar padrões frequentes.
2. Insere-se cada transação, através dos seus itens ordenados:
(Outra passada)
Itens são ordenados em ordem decrescente de frequência, sendo os infrequentes filtrados.

Com a FP-Tree construída, inicia a mineração recursiva de padrões.

Para cada item em ordem crescente:

  1. Constrói-se uma nova FP-Tree a partir dos prefixos deste item, desconsiderando o item em questão. É importante calcular as frequências apenas nos prefixos considerados.
  2. Desta, descarta-se os itens cuja frequência na árvore é inferior ao suporte mínimo.
  3. Caso a árvore constitua um ramo, considera-se este ramo um conjunto, e deste extrai-se o conjunto potência. Caso contrário, repete-se o processo recursivamente para cada item da árvore.
  4. Finalmente, acresce-se aos conjuntos extraídos o item da iteração.

Exemplo: (suporte mínimo = 2)

tid a b c d e f
1 $✓$ $✓$ $✓$ $✓$
2 $✓$ $✓$
3 $✓$ $✓$ $✓$
4 $✓$ $✓$
5 $✓$ $✓$ $✓$
6 $✓$ $✓$ $✓$

Construção da FP-Tree:

  1. Cálculo da frequência: 
    graph g {
  graph [ bgcolor = transparent ]
  node [ shape=circle ]
  Ø;
  tbl [
    shape = plaintext
    label = <
      <table border='0' cellspacing='0'>
        <tr><td>Item</td><td>Frequência</td><td>Nós</td></tr>
        <tr><td>c</td><td>5</td><td>Ø</td></tr>
        <tr><td>f</td><td>4</td><td>Ø</td></tr>
        <tr><td>a</td><td>3</td><td>Ø</td></tr>
        <tr><td>b</td><td>2</td><td>Ø</td></tr>
        <tr><td>d</td><td>2</td><td>Ø</td></tr>
      </table>
    >
  ]
}

Mineração de padrões a partir do item $d$:

  1. Projeção dos prefixos: 
    graph g {
  graph [ bgcolor = transparent ]
  node [ shape=circle, margin = 0 ]

  root [ label = Ø ];
  c1 [ label = "c(1)", color = violet ]
  f1 [ label = "f(1)", color = orange ]
  a1 [ label = "a(1)", color = lightgreen ]
  a2 [ label = "a(1)", color = lightgreen ]

  tbl [
    shape = plaintext
    label = <
      <table border='0' cellspacing='0'>
        <tr><td>Item</td><td>Frequência</td><td>Nós</td></tr>
        <tr><td>a</td><td>2</td><td bgcolor='lightgreen'>2</td></tr>
        <tr><td>c</td><td>1</td><td bgcolor='violet'>1</td></tr>
        <tr><td>f</td><td>1</td><td bgcolor='orange'>1</td></tr>
      </table>
    >
  ]

  root -- c1
  c1 -- f1
  f1 -- a1
  root -- a2
}

Mineração de padrões a partir do item $b$:

  1. Projeção dos prefixos: 
    graph g {
  graph [ bgcolor = transparent ]
  node [ shape=circle, margin = 0 ]

  root [ label = Ø ];
  c1 [ label = "c(2)", color = violet ]
  f1 [ label = "f(1)", color = orange ]

  tbl [
    shape = plaintext
    label = <
      <table border='0' cellspacing='0'>
        <tr><td>Item</td><td>Frequência</td><td>Nós</td></tr>
        <tr><td>c</td><td>2</td><td bgcolor='violet'>1</td></tr>
        <tr><td>f</td><td>1</td><td bgcolor='orange'>1</td></tr>
      </table>
    >
  ]

  root -- c1
  c1 -- f1
}

Mineração de padrões a partir do item $a$:

  1. Projeção dos prefixos: 
    graph g {
  graph [ bgcolor = transparent ]
  node [ shape=circle, margin = 0 ]

  root [ label = Ø ];
  c1 [ label = "c(2)", color = violet ]
  f1 [ label = "f(2)", color = orange ]

  tbl [
    shape = plaintext
    label = <
      <table border='0' cellspacing='0'>
        <tr><td>Item</td><td>Frequência</td><td>Nós</td></tr>
        <tr><td>c</td><td>2</td><td bgcolor='violet'>1</td></tr>
        <tr><td>f</td><td>2</td><td bgcolor='orange'>1</td></tr>
      </table>
    >
  ]

  root -- c1
  c1 -- f1
}

    2. Padrões extraídos: $\{a\}, \{c,a\}, \{a,f\}, \{c,f,a\}$

Mineração de padrões a partir do item $f$:

  1. Projeção dos prefixos: 
    graph g {
  graph [ bgcolor = transparent ]
  node [ shape=circle, margin = 0 ]

  root [ label = Ø ];
  c1 [ label = "c(4)", color = violet ]

  tbl [
    shape = plaintext
    label = <
      <table border='0' cellspacing='0'>
        <tr><td>Item</td><td>Frequência</td><td>Nós</td></tr>
        <tr><td>c</td><td>4</td><td bgcolor='violet'>1</td></tr>
      </table>
    >
  ]

  root -- c1
}

    2. Padrões extraídos: $\{f\}, \{c,f\}$

Mineração de padrões a partir do item $f$:

  1. Projeção dos prefixos: 
    graph g {
  graph [ bgcolor = transparent ]
  node [ shape=circle, margin = 0 ]

  root [ label = Ø ];

  tbl [
    shape = plaintext
    label = <
      <table border='0' cellspacing='0'>
        <tr><td>Item</td><td>Frequência</td><td>Nós</td></tr>
        <tr><td>-</td><td>-</td><td>-</td></tr>
      </table>
    >
  ]
}

    2. Padrões extraídos: $\{c\}$

Representações compactas

Considerande uma base de dados contendo apenas duas transações:

Ao considerar um suporte mínimo igual a 2, essa base apresenta uma quantidade exorbitante de itemsets frequentes:

Apesar de ser um caso extremo, é comum encontrar pequenas ocorrências deste padrão em bases de dados maiores. Isso inviabiliza a computação utilizando os métodos descritos anteriormente.

De forma a mitigar este problema, utilizamos representações compactas dos itemsets frequentes.

Fronteira da frequência

Uma forma de representação compacta denominada Itemsets máximos é obtida ao se considerar o limiar entre os itemsets frequentes e infrequentes. Os Itemsets máximos são os itemsets frequentes que não possuem superconjuntos frequentes.

graph G {
  graph [bgcolor = transparent, rankdir = "TD"]

  subgraph lvl0 {
    rank = same
    ∅ [label = "Ø\n1,2,3,4,5,6", fillcolor = ivory, style = filled]
  }
  subgraph lvl1 {
    rank = same
    "{a}" [label = "{a}\n1,4,6", fillcolor = ivory, style = filled]
    "{b}" [label = "{b}\n2,5", fillcolor = ivory, style = filled]
    "{c}" [label = "{c}\n1,2,3,5,6", fillcolor = ivory, style = filled]
    "{d}" [label = "{d}\n1,4", fillcolor = ivory, style = filled]
  }
  subgraph lvl2 {
    rank = same
    "{a,b}" [label = "{a,b}\nØ"]
    "{a,c}" [label = "{a,c}\n1,6", fillcolor = ivory, style = filled]
    "{a,d}" [label = "{a,d}\n1,4", fillcolor = ivory, style = filled]
    "{b,c}" [label = "{b,c}\n2,5", color = crimson, fillcolor = ivory, style = filled]
    "{b,d}" [label = "{b,d}\nØ"]
    "{c,d}" [label = "{c,d}\nØ"]
  }
  subgraph lvl3 {
    rank = same
    "{a,b,c}" [label = "{a,b,c}\nØ"]
    "{a,b,d}" [label = "{a,b,d}\nØ"]
    "{a,c,d}" [label = "{a,c,d}\n1", color = crimson, fillcolor = ivory, style = filled]
    "{b,c,d}" [label = "{b,c,d}\nØ"]
  }
  subgraph lvl4 {
    rank = same
    "{a,b,c,d}" [label = "{a,b,c,d}\nØ"]
  }
  subgraph lvl5 {
    rank = same
  }

  ∅ -- "{a}"
  ∅ -- "{b}"
  ∅ -- "{c}"
  ∅ -- "{d}"

  "{a}" -- "{a,b}"
  "{a}" -- "{a,c}"
  "{a}" -- "{a,d}"
  "{b}" -- "{a,b}"
  "{b}" -- "{b,c}"
  "{b}" -- "{b,d}"
  "{c}" -- "{a,c}"
  "{c}" -- "{b,c}"
  "{c}" -- "{c,d}"
  "{d}" -- "{a,d}"
  "{d}" -- "{b,d}"
  "{d}" -- "{c,d}"

  "{a,b}" -- "{a,b,c}"
  "{a,b}" -- "{a,b,d}"
  "{a,c}" -- "{a,b,c}"
  "{a,c}" -- "{a,c,d}"
  "{a,d}" -- "{a,b,d}"
  "{a,d}" -- "{a,c,d}"
  "{b,c}" -- "{a,b,c}"
  "{b,c}" -- "{b,c,d}"
  "{b,d}" -- "{a,b,d}"
  "{b,d}" -- "{b,c,d}"
  "{c,d}" -- "{a,c,d}"
  "{c,d}" -- "{b,c,d}"

  "{a,b,c}" -- "{a,b,c,d}"
  "{a,b,d}" -- "{a,b,c,d}"
  "{a,c,d}" -- "{a,b,c,d}"
  "{b,c,d}" -- "{a,b,c,d}"
}

Apesar de ser uma represetação bastante compacta, o cálculo do suporte para os itemsets derivados dessa representação não é viável de forma direta, sendo necessária uma nova passada na base de dados.

Classes de equivalência

Uma outra forma de obter representações compactas é particionar os itemsets em classes de equivalência, definidas pela cobertura.

graph G {
  graph [bgcolor = transparent, rankdir = "TD"]

  subgraph lvl0 {
    rank = same
    ∅ [label = "Ø\n1,2,3,4,5,6", color = gray]
  }
  subgraph lvl1 {
    rank = same
    "{a}" [label = "{a}\n1,4,6", color = green]
    "{b}" [label = "{b}\n2,5", color = crimson]
    "{c}" [label = "{c}\n1,2,3,5,6", color = cyan]
    "{d}" [label = "{d}\n1,4", color = purple]
  }
  subgraph lvl2 {
    rank = same
    "{a,b}" [label = "{a,b}\nØ"]
    "{a,c}" [label = "{a,c}\n1,6", color = blue]
    "{a,d}" [label = "{a,d}\n1,4", color = purple]
    "{b,c}" [label = "{b,c}\n2,5", color = crimson]
    "{b,d}" [label = "{b,d}\nØ"]
    "{c,d}" [label = "{c,d}\n1", color = orange]
  }
  subgraph lvl3 {
    rank = same
    "{a,b,c}" [label = "{a,b,c}\nØ"]
    "{a,b,d}" [label = "{a,b,d}\nØ"]
    "{a,c,d}" [label = "{a,c,d}\n1", color = orange]
    "{b,c,d}" [label = "{b,c,d}\nØ"]
  }
  subgraph lvl4 {
    rank = same
    "{a,b,c,d}" [label = "{a,b,c,d}\nØ"]
  }
  subgraph lvl5 {
    rank = same
  }

  ∅ -- "{a}"
  ∅ -- "{b}"
  ∅ -- "{c}"
  ∅ -- "{d}"

  "{a}" -- "{a,b}"
  "{a}" -- "{a,c}"
  "{a}" -- "{a,d}"
  "{b}" -- "{a,b}"
  "{b}" -- "{b,c}"
  "{b}" -- "{b,d}"
  "{c}" -- "{a,c}"
  "{c}" -- "{b,c}"
  "{c}" -- "{c,d}"
  "{d}" -- "{a,d}"
  "{d}" -- "{b,d}"
  "{d}" -- "{c,d}"

  "{a,b}" -- "{a,b,c}"
  "{a,b}" -- "{a,b,d}"
  "{a,c}" -- "{a,b,c}"
  "{a,c}" -- "{a,c,d}"
  "{a,d}" -- "{a,b,d}"
  "{a,d}" -- "{a,c,d}"
  "{b,c}" -- "{a,b,c}"
  "{b,c}" -- "{b,c,d}"
  "{b,d}" -- "{a,b,d}"
  "{b,d}" -- "{b,c,d}"
  "{c,d}" -- "{a,c,d}"
  "{c,d}" -- "{b,c,d}"

  "{a,b,c}" -- "{a,b,c,d}"
  "{a,b,d}" -- "{a,b,c,d}"
  "{a,c,d}" -- "{a,b,c,d}"
  "{b,c,d}" -- "{a,b,c,d}"
}

Tal consideração permite duas formas de representações compactas:

Itemsets fechados:
são os maiores itemsets das classes de equivalência.
No exemplo:
  • $\{a\}$
  • $\{c\}$
  • $\{a,d\}$
  • $\{b,c\}$
  • $\{a,c\}$
  • $\{a,c,d\}$
Itemsets geradores mínimos:
são os menores itemsets das classes de equivalência.
No exemplo:
  • $\{a\}$
  • $\{b\}$
  • $\{c\}$
  • $\{d\}$
  • $\{a,c\}$
  • $\{c,d\}$

Enquanto os itemsets fechados são únicos, os geradores mínimos não necessariamente são. Portanto, a representação utilizando geradores mínimos pode apresentar redundância, não sendo muito compacta em casos extremos.

Algoritmos

Apesar de ser possível embutir tais representações nos algoritmos descritos anteriormente, isso apenas auxiliaria na digestão dos resultados, não apresentado ganho de desempenho computacional algum. De forma a explorar tal possibilidade de ganho computacional, algoritmos específicos se fazem necessários.

MAFIA:
Maximal Frequent Itemset Algorithm
O algoritmo utiliza uma abordagem best-first/branch-and-bound para navegar o reticulado, adotando uma representação vertical dos dados. Além disso, explora a ordem lexicográfica dos itens, bem como a relação de ordem parcial de subconjuntos entre os itemsets.

Duas podas são realizadas:

  • Reordenamento dinâmico: Ao visitar cada nó na busca em profundidade, seus filhos imediatos são verificados, e os itens que causam infrequência são desconsiderados para a subárvore atual.
  • Parent Equivalence Pruning (PEP): Caso a cobertura de um dos itens candidatos seja superior à do itemset atual, ele é imediatamente adicionado a este itemset, restringindo buscas adicionais relativas à este item.
DCI Closed:
@@latex:\hfill@@
O algoritmo utiliza uma abordagem de divisão e conquista no reticulado, adotano uma representação vertical dos dados. Tal abordagem se mostra extremamente interessante na medida que permite a paralelização da execução do algoritmo. Além disso, também explora uma ordem lexicográfica sobre os itens, e sua extensão sobre os itemsets.

A ideia central do algoritmo é escalar o reticulado, visitando cada classe de equivalência uma única vez. Somente um candidato de cada classe é avaliado, e novos candidatos são gerados estendendo os conjuntos fechados com itens ainda não investigados.

Mineração de sequências frequentes

Define-se sequências como uma lista ordenada de itemsets entre transações. Desta forma, enquanto itemsets são padrões intra-transações, sequências são padrões inter-transações.

Inicialmente, considera-se o conjunto de dados como um conjunto de transações compostas por:

  • Identificador de cliente
  • Timestamp da transação
  • Conjunto de itens

Uma sequência de itemsets $α = \langle a_1, \hdots, a_n \rangle$ é subsequência de $β = \langle b_1, \hdots, b_m \rangle$, denotado por $α \sqsubseteq β$, se:

  1. Existe uma mapeamento $\varphi: α → β$ @@latex:\hfill@@ Todos itemsets de $α$ estão associados à $itemsets$ de $β$.
  2. $∀\, a ∈ α, b = \varphi(a): a \subseteq b$ @@latex:\hfill@@ Tal associação apresenta uma relação de subconjunto.
  3. $∀\, i &lt; j, b_k = \varphi(a_i), b_l = \varphi(b_j): k &lt; l$ @@latex:\hfill@@ A ordem relativa entre $α$ e $β$ é mantida.

A partir da definição de sequência, redefine-se a base de dados como um conjunto dos clientes e suas respectivas sequências de transações. Tal definição constitui uma representação horizontal da base de dados.

<c> <c>
Cliente Transações
$c_1$ $s_1 = \langle t1, 1, \hdots, t1, i \rangle$
$\vdots$ $\vdots$
$c_n$ $s_n = \langle tn, 1, \hdots, tn, j \rangle$

Onde $tk,i$ é o itemset da $i\text{-ésima}$ transação do cliente $k$.

Vale notar que tal representação abdica da informação precisa do timestamp de cada transação, mantendo apenas a ordem temporal relativa dos itemsets.

Em seguida, definse-se a função suporte, mantendo-se a propriedade do Apriori:

Ou seja, um cliente $c_k$ suporta uma sequência $α$ se $α$ é uma subsequência da sequência de transações $s_k$.

Ademais, extende-se os conceitos que temos na mineração de itens frequentes:

Ordem:
A ordem de uma sequência $α$ é $k$ ($α$ é uma $k\text{-sequência}$) onde $k = ∑\limits∀ a ∈ α |a|$
Frequente:
Uma sequência $α$ é frequente se seu suporte é maior ou igual ao suporte mínimo.
Máxima:
Uma sequência frequente é máxima quando não há supersequências frequentes.
Fechada:
Uma sequência frequente é fechada quando não há uma supersequência de mesmo suporte.

Algoritmos

Os algoritmos tradicionais para mineração de sequências frequentes se baseiam nos algoritmos vistos anteriormente, em particular o Apriori, Eclat e FP-Growth.

Generalized Sequential Patterns

Baseado no Apriori, o GSP adota a mesma estratégia de busca em largura, utilizando as sequências de ordem $k-1$ para gerar candidatas de tamanho $k$. Além disso, utiliza-se a propriedade de anti-monotonicidade da função suporte para executar podas no espaço de busca.

Bem como no Apriori, são executadas diversas passadas na base de dados:

  1. Inicialmente, verifica-se o suporte das sequêcias unitárias, descartando-se as infrequentes.
  2. Cada par $\langle x \rangle$ e $\langle y \rangle$ de $1\text{-sequências}$ dá origem a duas $2\text{-supersequências}$:
    1. $\langle xy \rangle$
    2. $\langle x, y \rangle$

    Exceto quando $x = y$, onde apenas a segunda é considerada.

  3. Para as sequências não unitárias, gera-se os candidatos da seguinte forma:
    1. Sejam $s_1 = \left\langle \{i \mid x\} \mid s \right\rangle$ e $s_2 = \left\langle s \mid \{y \mid j\} \right\rangle$ sequências, onde $\left\langle x \mid s \right\rangle = \left\langle s \mid y \right\rangle$ e $i ≠ j$.
      • $s_1$ e $s_2$ são sequências de ordem $k &gt; 1$.
      • $s$ é uma subsequência em comum, possivelmente vazia.
      • $x$ e $y$ são itemsets, possivelmente vazios.
      • $i$ e $j$ são ítens.

      De forma equivalente, $s_1$ e $s_2$ diferem respectivamente no primeiro item do primeiro elemento de $s_1$ e no último item do último elemento de $s_2$.

    2. Gera-se uma nova sequência:
      • se $|s| = 0$: $\langle \{i \mid x \mid j \} \rangle$ @@latex:\hfill@@ Note que $x = y$ neste caso.
      • se $|s| &gt; 0$: $\langle \{i \mid x\} \mid s \mid \{y \mid j \} \rangle$
  4. Após a geração de novos candidatos, seus suportes são calculados e os infrequentes descartados.
  5. O algoritmo encerra quando não há mais candidatos frequentes.

Sequential Pattern Discorvery using Equivalence classes

Baseado no Eclat, o Spade utiliza também uma representação vertical da base de dados, e opera dividindo o espaço de busca pelo prefixo das sequências.

Primeiramente, define-se como index-set de um item o conjunto de clientes e índices em que este item ocorre na respectiva sequência:

A partir desta definição, apresenta-se uma representação vertical da base de dados como o conjunto de itens e suas index-set:

Onde o suporte de um item é trivialmente calculado por:

Define-se as classes de equivalência como as $k\text{-sequências}$ que compartilham um prefixo de tamanho $k-1$.

A partir de tais definições, o algoritmo opera gerando novas sequências a partir da junção temporal de duas sequências que pertençam à mesma classe de equivalência.

O index-set de uma nova sequência pode ser convenientemente calculado como a interseção dos index-sets das sequências geradoras, e desta forma extende-se sua definição para sequências. Considerando que o suporte é definido como a cardinalidade do index-set, sua definição também é extendida por consequência.

Utilizando tal método de forma iterativa, o algoritmo encerra quando não houver mais sequências a serem geradas.