Um Estudo Sobre A Mineração De Padrões Seqüenciais

Universidade Federal de Minas Gerais

Departamento de Ciência da Computação

Um estudo sobre a mineração de padrões seqüenciais

Danielle Santos da Silva e Patrícia Martins

1.Introdução

Com a grande quantidade de dados armazenados em bancos de dados e data warehouses, torna-se cada vez mais importante desenvolver ferramentas potentes para análise e extração de conhecimentos de interesse sobre os dados [1]. Data mining é um processo de inferência de conhecimento de grande quantidade de dados e um dos seus principais problemas é a descoberta de padrões que ocorrem freqüentemente em dados seqüenciais, e, para isso, utiliza a técnica de mineração de padrões seqüenciais [8], que foi introduzida em [7].

A tarefa da mineração de padrões seqüenciais é encontrar subseqüências freqüentes em um banco de dados de seqüências. Esta é uma atividade desafiadora, já que a busca pode exigir o exame de um número combinatorialmente explosivo de padrões de subseqüências possíveis [4]. Essa técnica possui diversas aplicações, incluindo a análise do comportamento de clientes, padrões de acesso a Web, análise do processo de experimentos científicos, previsão de desastres naturais, tratamento de doenças, teste de medicamentos, análise de DNA, etc [6].

A maioria dos métodos desenvolvidos para a mineração de padrões seqüenciais visa evitar a geração de todas as combinações possíveis de seqüências. Muitos estudos contribuíram para a mineração eficiente de padrões seqüenciais ou outros padrões freqüentes em dados relacionados com o tempo [4] e levaram ao desenvolvimento de diversos algoritmos, que podem ser classificados em duas categorias [5]: (1) Abordagem de geração e teste de candidatos, como o GSP e (2) Métodos de crescimento de padrões, que tem como um de seus representantes o FP-Growth A primeira categoria é baseada diretamente na propriedade Apriori: se um padrão com k itens não é freqüente, nenhum de seus super-padrões com (k+1) ou mais itens pode ser freqüente. São gerados candidatos iterarivamente e suas freqüências, checadas no banco de dados. A outra categoria de métodos foi proposta recentemente e também utiliza a propriedade Apriori, entretanto ao invés de gerar conjuntos de candidatos, particiona recursivamente o banco de dados em sub-bancos de acordo com os padrões freqüentes encontrados e busca por padrões freqüentes locais.

Nesse estudo, veremos as implicações do uso de ambas as abordagens, com o objetivo de analisar as suas características e aplicações em diferentes contextos. Na seção 2, é fornecida uma definição formal do problema de mineração de padrões seqüenciais. Na seção 3, é apresentado um estudo comparativo dos principais algoritmos pertencentes a cada classe. As conclusões são mostradas na seção 4.

2.Definição do Problema

Seja um conjunto de literais (itens). Um itemset é um conjunto não-vazio de itens. Uma seqüência é uma lista ordenada de itemsets. Denota-se uma seqüência s por , onde é um itemset. Diz também que é um elemento da seqüência. Denota-se um elemento de uma seqüência por , onde é um item. Um item pode ocorrer apenas uma vez em um elemento de uma seqüência, contudo, podem ocorrer múltiplas vezes em elementos diferentes. Um itemset pode ser considerado como uma seqüência com um único elemento. Assume-se, então, que itens em um elemento de uma seqüência estão em ordem lexicográfica [3].

O número de instâncias de itens em uma seqüência é denominado tamanho da seqüência. Uma seqüência de tamanho é chamada de -seqüência [4].

Então uma seqüência é uma subseqüência de outra seqüência se existir inteiros tal que . Por exemplo, a seqüência é uma subseqüência de , já que , e . Contudo, a seqüência não é uma subseqüência de e vice-versa. Assim, a seqüência é chamada super- seqüência de .

Um banco de dados de seqüências S é um conjunto de tuplas , onde é um identificador de seqüência e “s” é uma seqüência [4]. Uma tupla contém uma seqüência “α” se “α” é uma subseqüência de “s”. Então, é dado um banco de dados de seqüências D chamadas seqüências de dados. Cada seqüência de dados é uma lista de transações, ordenadas pelo aumento do tempo de transação. Uma transação possui os seguintes campos: identificação de seqüência, identificação de transação, tempo de transação e os itens presentes nessa transação. Espera-se que os itens em uma transação sejam folhas em T, porém isso não é necessariamente requerido.

Em [3], por questões de simplicidade, assume-se que nenhuma seqüência de dados possui mais de que uma transação com o mesmo tempo de transação e utiliza o tempo de transação como um identificador de transação. Também, não são consideradas quantidades de itens em uma transação.

Assim, o suporte para uma seqüência é definido como uma fração do total de seqüências de dados que “contêm” tal seqüência. Portanto, dado um inteiro positivo ξ como suporte limite, uma seqüência “α” é chamada de padrão seqüencial freqüente, no bancos de dados de seqüência S, se a seqüência é contida por pelo menos ξ tuplas no banco.

Portanto, para contextualizar o problema pode-se dizer que, dado um banco de dados de seqüências de dados e uma taxonomia T, o problema de minerar padrões seqüenciais é achar todas as seqüências cujo suporte é maior o suporte mínimo especificado pelo usuário. Cada uma dessas seqüências representa um padrão seqüencial também chamado de seqüência freqüente.

Dada uma seqüência freqüente , é útil saber a “relação de suporte” entre os elementos da seqüência, ou seja, qual fração das seqüências de dados que suportam suporta a seqüência “s” inteira.

3. Métodos para a Mineração de Padrões Seqüenciais

3.1 Geração e Teste de Candidatos

Algoritmos Apriori possuem estrutura baseada na execução de múltiplos passos sobre os dados. Em cada passo, começa-se com um conjunto semente de um número grande de seqüências, chamadas de seqüências candidatas. O suporte para essas seqüências candidatas é achado durante a passada sobre os dados. Ao final do passo, são determinadas as maiores seqüências candidatas. Tais seqüências