A tarefa de mineração considerada básica para o problema de mineração proposto nesta dissertação será apresentada logo abaixo. Na seção 4.2 será apresentada a tarefa de mineração principal, incluindo restrições de expressões regulares.
• Dado: Um banco de dados temporal BD e um limiar mínimo de suporte α. • Encontrar: Todos os pth freqüentes com relação a BD e α.
3.2 Considerações Finais do Capítulo
Neste capítulo o problema de mineração de padrões temporais híbridos foi amplamente detalhado. Inicialmente foi de nida a Lógica Temporal de Intervalos de Allen e as adap- tações realizadas para ela servir de formalismo para especi car o novo padrão temporal. A LTI adaptada considera casos onde o tempo é representado em termos de pontos e intervalos, uma vez que a LTI original considera somente tempo intervalar.
Posteriormente foi de nido o banco de dados temporal onde os pth's podem ser mine- rados e em seguida o padrão temporal híbrido. Um extenso trabalho foi realizado so- bre o conjunto de átomos temporais com o objetivo de simpli car a representação e, conseqüentemente, o entendimento dos pth's. Para isso, foram desenvolvidas técnicas para visualizá-lo como uma seqüência de átomos de dados, permitindo também que ele seja especializado inserindo um novo átomo de dados no m da seqüência.
Após a apresentação formal do pth foram de nidos os conceitos de suporte e pth freqüente sobre bancos de dados temporais. Finalmente, o capítulo foi encerrado com a apresentação da tarefa básica deste problema de mineração.
Capítulo 4
Restrições no Processo de Mineração
Neste capítulo serão apresentadas as restrições que foram introduzidas no processo de mineração com o objetivo de otimizar a busca por novos pth's. A primeira restrição é especi cada por expressões regulares similares às utilizadas nos algoritmos da família SPIRIT [12] e SPIRIT-Log [14]. Esse tipo de restrição reduz o espaço de busca dos pth's e permite que o usuário controle do processo de mineração. Além das restrições de expressões regulares serão apresentadas também restrições especi cadas por operadores de especialização. Esses operadores possuem propriedades especiais para controlar a geração de novos pth's, garantindo a e ciência e e cácia do método.
4.1 Expressões Regulares sobre os PTH's
Os sistemas convencionais de mineração permitem ao usuário apenas de nir o suporte mínimo como mecanismo de restringir os padrões a serem minerados. Com isso, ele é sobrecarregado com uma enorme quantidade de padrões que não o interessam. Os algoritmos da família SPIRIT [12] e SPIRIT-Log [14], além do suporte mínimo, permitem o uso de expressões regulares como uma ferramenta para incorporar o foco do usuário ao processo de mineração, promovendo assim a redução do espaço de busca dos padrões. Nesta dissertação são de nidas expressões regulares sobre um conjunto de modos chamado alfabeto, e todo pth gerado deve satisfazer uma determinada expressão regular. Portanto, a expressão regular considerada tem a função de restringir o formato dos pth's. É impor-
tante salientar que os algoritmos da família SPIRIT e SPIRIT-Log mineram padrões seqüenciais. Portanto, as restrições de expressões regulares são de nidas considerando o tempo como pontual. Neste trabalho está sendo proposto um método de utilizar tais restrições de expressões regulares na mineração de padrões temporais híbridos, onde o tempo é pontual e/ou intervalar.
De nição 4.1.1 (Modo) Um modo sobre um esquema R é uma expressão da forma
p(u1, ..., un, #), onde p é um predicado pertencente a R com aridade n + 1, ui ∈ Var ou ui é um símbolo $, e # é um novo símbolo. Um modo caracteriza e identi ca os atributos das relações de R e serve de certa forma como um molde para a construção de um átomo. Um átomo A é de acordo com um modo p(u1, ..., un, #) (A foi gerado a partir de p(u1, ..., un, #)) se A = p(x1, ..., xn, τ ) e para cada i = 1, ..., n, temos:
• Se ui ∈ Var, então xi = ui;
• Se ui = $, então xi ∈ Var ou xi ∈ Const;
• # é substituído por τ ∈ Vtemp, ou seja, τ ∈ Vit ou τ ∈ Vpt.
Exemplo 4.1.1 Considere o esquema R = {P aciente(NomeP ac), Birads(NomeP ac, Categoria, Tpt), F umo(NomeP ac, Qtde, Tit), Hormˆonio(NomeP ac, NomeHorm, Tit)}, onde P aciente(NomeP ac) é uma tabela de referência e portanto, NomeP ac é um atribu- to de referência. Assim, um possível alfabeto de modos sobre este esquema poderia ser {P aciente(x), Birads(x, $, #), F umo(x, $, #), Hormˆonio(x, $, #)}. Note que a variá- vel x é uma variável de referência, portanto, estes modos informam que o primeiro atributo de cada tabela é de referência e os valores armazenados nestas colunas per- tencem a um mesmo domínio, neste caso, nome de pacientes. Considere agora os átomos Hormˆonio(x, progesterona, e) e Hormˆonio(y, progesterona, e). O primeiro é de acordo com o modo Hormˆonio(x, $, #). Em contrapartida, o segundo não é de acordo com o modo, pois, como x é uma variável no modo, ela deve ser mantida no átomo.
Um alfabeto de modos sobre R é denotado pelo símbolo Σ. São consideradas linguagens especi cadas por expressões regulares sobre o alfabeto Σ com o objetivo de reduzir o
tamanho do espaço de busca dos pth's. Relembrando, uma linguagem sobre um alfabeto Σ é um conjunto de símbolos ou strings sobre Σ.
De nição 4.1.2 (Expressão regular) Uma expressão regular R sobre um alfa-
beto de modos Σ = {p1(u1, . . . , un, #), p2(u1, . . . , un, #), . . . , pk(u1, . . . , un, #)} pode ter a forma p1(u1, . . . , un, #)* p2(u1, . . . , un, #), que neste caso especi ca uma linguagem, onde, * signi ca que o predicado p1 pode não ocorrer ou ocorrer uma ou mais vezes, e obrigatoriamente deve terminar com o predicado p2.
Exemplo 4.1.2 Considere o alfabeto de modos Σ = {Hormˆonio(x, $, #), F umo(x, $, #), Birads(x, $, #)}, e a expressão regular R = Hormˆonio(x, $, #)∗F umo(x, $, #)Birads(x, $, #) sobre Σ. Uma linguagem especi cada pela restrição R pode ser Hormˆonio(x, $, #) Hormˆonio(x, $, #)F umo(x, $, #)Birads(x, $, #).
Para facilitar a representação de uma expressão regular cada modo é rotulado com uma letra, por exemplo, wi = pi(u1, . . . , un, #), signi ca que wi representa pi. Por motivos de simpli cação, a mesma notação R é considerada para denotar a expressão regular e a linguagem associada a ela. Assim, dada uma expressão regular R sobre um alfabeto Σ, um pth (K, E, T ) satisfaz R se: E é uma seqüência de átomos de dados < p1, . . . , pn > e existe uma string w1, . . . , wn ∈ R, onde pi é de acordo com wi para cada i = 1, . . . , n. O conjunto de strings que veri cam a expressão regular R e denotado por W (R) e o conjunto de pre xos de strings em W (R) é denotado por Pref(R), ou seja, Pref(R) = {w | ww′ ∈ R para algum w′}. Essas notações serão importantes a seguir.
De nição 4.1.3 (Espaço de busca) Seja um esquema de banco de dados R = {K, R1, . . . , Rn}, um alfabeto de modos Σ sobre R e uma expressão regular R sobre Σ. O espaço de busca de nido por R é um conjunto de pth's (K, E, T ), tal que, E = < p1(t1
1, . . . , t1
l, τ1), . . . , pn(tn1, . . . , tnl, τn) > satisfaz as seguintes propriedades:
1. Deve existir uma string w1. . . wn ∈ W (R)tal que pi é de acordo com wi, para cada i = 1, . . . , n. A string w1. . . wn é chamada de palavra associada ao pth.
2. Para todo átomo de dados pi(ti1, . . . , ti
l, τi) ∈ E de acordo com um modo wi = pi(ui1, . . . , ui
É denotado por W(R) o espaço de busca dos pth's especi cado por R, e por Pref(R), o conjunto de pth's de nidos de modo similar a W(R), por considerar strings w1. . . wn ∈ P (R)ao invés de W (R) na condição (1). Os pth's pertencentes a W(R) são chamados de válidos, e os pth's pertencentes a Pref(R) de pre xos-válidos ou simplesmente p-válidos. Como será visto no próximo capítulo, na fase da geração do algoritmo MILPRIT* somente pth's pertencentes a Pref(R) são gerados. A razão pela qual são gerados pth's p-válidos ao invés de válidos cará clara na seção 5.1.
Proposição 4.1.1 Seja W(R) e Pref(R) dois espaços de busca, onde R é uma expressão regular sobre Σ. Então W(R) ⊆ Pref(R).
A prova desta proposição foi dada na de nição anterior, ou seja, para computar os pth's que pertencem a W(R) é su ciente computar os que pertencem a Pref(R).
Exemplo 4.1.3 Considere a expressão regular R = Hormˆonio(x, $, #)∗F umo(x, $, #) Birads(x, $, #) e os pth's P1, P2 e P3 de nidos por:
P1 = (P aciente(x), {Hormˆonio(x, estradiol, e1), F umo(x, 10, f2), Birads(x, 3, s3)}, {during(e1, f2),before(e1, s3),before(f2, s3)})
P2 = (P aciente(x), {Hormˆonio(x, estradiol, e1), F umo(x, 10, f2)}, {before(e1, f2)}) P3 = (P aciente(x), {Hormˆonio(x, y, e1), Hormˆonio(x, y, e2)}, {before(e1, e2)}) O pth P1 pertence a W(R) e o pth P2 pertence a Pref(R). Entretanto, o pth P3 não pertence a Pref(R) pois a propriedade (2) da de nição 4.1.3 não é veri cada.