( PDF ) Descoberta de conhecimento em documentos XML

Download PDF

ads:

INSTITUTO MILITAR DE ENGENHARIA

MAURICIO COSTA REIS

DESCOBERTA DE CONHECIMENTO

EM DOCUMENTOS XML

Dissertação de Mestrado apresentada ao Curso de

Mestrado em Sistemas e Computação do Instituto

Militar de Engenharia, como requisito parcial para a

obtenção do título de Mestre em Ciências em Sistemas

e Computação.

Orientador: Ronaldo Ribeiro Goldschmidt - D. C.

Co-orientador: Emmanuel Piseces Lopes Passos - D.C.

Rio de Janeiro

2005

ads:

Livros Grátis

http://www.livrosgratis.com.br

Milhares de livros grátis para download.

2005

INSTITUTO MILITAR DE ENGENHARIA

Praça General Tibúrcio, 80 – Praia Vermelha

Rio de Janeiro - RJ CEP: 22290-270

Este exemplar é de propriedade do Instituto Militar de Engenharia, que poderá incluí-lo em

base de dados, armazenar em computador, microfilmar ou adotar qualquer forma de

arquivamento.

É permitida a menção, reprodução parcial ou integral e a transmissão entre bibliotecas

deste trabalho, sem modificação de seu texto, em qualquer meio que esteja ou venha a ser

fixado, para pesquisa acadêmica, comentários e citações, desde que sem finalidade comercial

e que seja feita a referência bibliográfica completa.

Os conceitos expressos neste trabalho são de responsabilidade do(s) autor(es) e do(s)

orientador(es).

R375 Reis, Mauricio Costa

Descoberta de Conhecimento em Documentos XML /

Mauricio Costa Reis. - Rio de Janeiro: Instituto Militar de

Engenharia, 2005.

148 p.: il., graf., tab.

Dissertação: (mestrado) - Instituto Militar de Engenharia -

Rio de Janeiro, 2005.

1. Banco de Dados - KDD. 2. Descoberta de Conhecimento -

KDD. 3. Sistemas Baseados em Aquisição de Conhecimento

- KDD. 4. XML. I. Título. II. Instituto Militar de Engenharia.

CDD 006.331

ads:

INSTITUTO MILITAR DE ENGENHARIA

MAURICIO COSTA REIS

DESCOBERTA DE CONHECIMENTO

EM DOCUMENTOS XML

Dissertação de Mestrado apresentada ao Curso de Mestrado em Sistemas e

Computação do Instituto Militar de Engenharia, como requisito parcial para a

obtenção do título de Mestre em Ciências em Sistemas e Computação.

Orientador:

prof. Ronaldo Ribeiro Goldschmidt, D.C.

Co-orientador:

prof. Emmanuel Piseces Lopes Passos, D.C.

Aprovada em 23 de fevereiro de 2005 pela seguinte Banca Examinadora:

___________________________________________________________

prof. Ronaldo Ribeiro Goldschmidt, D.C. do IME – Presidente.

___________________________________________________________

prof. Emmanuel Piseces Lopes Passos, D.C. da PUC/RJ.

___________________________________________________________

profª. Maria Cláudia Reis Cavalcanti, D.C. do IME.

___________________________________________________________

Alberto Sulaiman Sade Jr. - D.C. do Banco Central.

Rio de Janeiro

2005

À todas as formas de amor.

AGRADECIMENTOS

A meus pais, Léo e Luiza, pelos primeiros ensinamentos da vida.

Ao meu filho, Marcos Jorge, pela compreensão da ausência.

À minha esposa, Carmen, pelo apoio incondicional.

À todos, parentes e amigos, por me entenderem neste período especial de minha vida.

A todos que um dia foram meu professor, que, com sua sabedoria e humildade, souberam

adicionar um pouco de esperança no meu coração.

Aos colegas nesta jornada de mestrado, pelos belos e inesquecíveis momentos passados

juntos; ao Amorim, que não pode dar continuidade ao curso ainda no primeiro ano; aos

"eternos" parceiros, Handrick, Márcio, Leonardo e Gabriel; aos demais colegas, inclusive de

outros anos (turmas), pelo convívio e apoio sempre presentes.

Ao pessoal de apoio do IME, sempre prestativos para encontrar a solução para inevitáveis

(e evitáveis) problemas. Um agradecimento especial para a "tia" Deise, do IM/UFRJ onde

cursei algumas disciplinas, que me recebeu com a mesma dedicação, amor e carinho após

mais de vinte anos em que a conheci, na minha graduação.

Ao corpo docente do IME e IM/UFRJ, que compartilharam comigo um pouco de seus

vastos conhecimentos, em especial a profª. Ana Maria, pelo exemplo de dedicação, algumas

vezes mal compreendidos, que vai deixar marcas para sempre.

Ao Emmanuel, que me motivou a retomar o mestrado e sempre acreditou em mim e no

meu trabalho. Sem ele, certamente eu jamais estaria escrevendo estas palavras. E também por

me ter apresentado o Ronaldo!

Ao Ronaldo, orientador de palavras amáveis, de decisões firmes e de humildade

inconfundível. Sempre presente nesta minha jornada, soube contribuir de modo decisivo, com

seus conhecimentos, com sua amizade e com seu apoio, manifestado de vários modos, para

criar as condições mínimas necessárias para eu enfrentar as "tempestades" que encontrei pelo

caminho...

À CAPES, pelas condições que favoreceram o desenvolvimento deste trabalho.

Enfim, ao amor de todos, sem o qual, este trabalho não seria possível.

SUMÁRIO

LISTA DE ILUSTRAÇÕES .......................................................................................10

LISTA DE SIGLAS....................................................................................................13

1. INTRODUÇÃO ..........................................................................................17

1.1. Posicionamento e Justificativa...................................................................17

1.2. Objetivos ...................................................................................................21

1.3. Assuntos não Abordados ..........................................................................22

1.4. Organização do Trabalho..........................................................................22

2. FUNDAMENTAÇÃO TEÓRICA ................................................................24

2.1. XML...........................................................................................................24

2.1.1. Histórico ....................................................................................................24

2.1.2. Formato de Documento XML.....................................................................24

2.1.3. Esquemas..................................................................................................27

2.1.4. Modelo Formal de Dados em Documentos XML.......................................29

2.1.5. Tecnologias Relacionadas ........................................................................34

2.2. KDD e Mineração de Dados......................................................................37

2.2.1. Conceitos Básicos.....................................................................................37

2.2.2. Etapas Operacionais .................................................................................37

2.2.3. Tarefas Primárias de KDD.........................................................................40

2.2.4. Técnicas e métodos ..................................................................................43

2.3. Associação e Classificação .......................................................................45

2.3.1. Considerações Preliminares......................................................................45

2.3.2. Descoberta de Regras de Associação ......................................................46

2.3.3. Descoberta de Regras de Associação Generalizadas ..............................50

2.3.4. Classificação .............................................................................................53

2.3.5. Classificação Baseada em Regras de Associação....................................55

3. TRABALHOS RELACIONADOS..............................................................57

3.1. Visão Geral................................................................................................57

3.2. Descoberta de Regras de Associação ......................................................58

3.3. Descoberta de Regras de Associação em Documentos XML ...................61

3.4. Classificação em Documentos XML..........................................................62

4. ABORDAGENS ADOTADAS ...................................................................63

4.1. Considerações Gerais...............................................................................63

4.1.1. Simplificação do Modelo Formal de Documentos XML .............................63

4.1.2. Representação de Árvore..........................................................................66

4.1.3. Modelo da estrutura...................................................................................67

4.1.4. Pré-processamento ...................................................................................69

4.1.5. Definição dos Dados para Associação......................................................70

4.1.6. Processamento do Documento XML.........................................................74

4.1.7. Formato Basket .........................................................................................74

4.1.8. Parâmetros................................................................................................75

4.2. Mineração de Regras de Associação em Documentos XML - Abordagem

Clássica.....................................................................................................76

4.2.1. Considerações Iniciais...............................................................................76

4.2.2. Algoritmo Apriori........................................................................................77

4.2.3. Regras de Associação Generalizada ........................................................81

4.2.4. Comparação com outras Abordagens.......................................................84

4.2.5. Considerações Complementares ..............................................................85

4.3. Mineração de Regras de Associação em Documentos XML - Abordagem

Proposta....................................................................................................86

4.3.1. Considerações Iniciais...............................................................................86

4.3.2. Algoritmo ASCX-1P...................................................................................88

4.3.3. Algoritmo ASCX-2P...................................................................................93

4.3.4. Algoritmo ASCX-1PG ................................................................................98

4.3.5. Algoritmo ASCX-2PG ..............................................................................102

4.3.6. Comparação com outras Abordagens.....................................................107

4.3.7. Considerações Complementares ............................................................107

4.4. Classificação em Documentos XML........................................................108

4.4.1. Considerações Iniciais.............................................................................108

4.4.2. Algoritmos de Classificação ....................................................................109

4.4.3. Comparação com outras Abordagens.....................................................111

4.4.4. Considerações Complementares ............................................................112

5. PROTÓTIPOS, EXPERIMENTOS E RESULTADOS..............................113

5.1. Considerações Iniciais.............................................................................113

5.1.1. Ambiente de Desenvolvimento e de Testes ............................................113

5.1.2. Seleção dos Documentos........................................................................114

5.2. Descoberta de Regras de Associação em Documentos XML .................115

5.2.1. Metodologia de Testes ............................................................................115

5.2.2. Testes Realizados e Resultados Obtidos................................................116

5.2.3. Considerações Complementares ............................................................125

5.3. Descoberta de Regras de Associação Generalizadas em Documentos

XML.........................................................................................................126

5.3.1. Metodologia de Testes ............................................................................126

5.3.2. Testes Realizados e Resultados Obtidos................................................127

5.3.3. Considerações Complementares ............................................................132

5.4. Classificação em Documentos XML........................................................134

5.4.1. Metodologia de Testes ............................................................................134

5.4.2. Testes Realizados e Resultados Obtidos................................................134

5.4.3. Considerações Complementares ............................................................136

6. CONCLUSÕES .......................................................................................137

6.1. Retrospecto .............................................................................................137

6.2. Contribuições...........................................................................................137

6.3. Trabalhos Futuros ...................................................................................138

7. REFERÊNCIAS BIBLIOGRÁFICAS.......................................................140

8. ANEXOS .................................................................................................145

8.1. ANEXO 1: Roteiro para executar a implementação ................................146

8.2. ANEXO 2: Documentos XML...................................................................147

8.3. ANEXO 3: APIs utilizadas na implementação .........................................153

8.4. ANEXO 4: SQL usado na implementação do Algoritmo Apriori...............157

LISTA DE ILUSTRAÇÕES

FIG. 1.1: Hierarquia entre Dado, Informação e Conhecimento..........................18

FIG. 1.2: Exemplo de documento XML ..............................................................19

FIG. 1.3: Documento notas.xml .........................................................................20

FIG. 2.1: Representação gráfica do documento notas.xml ................................25

FIG. 2.2: DTD do documento notas.xml.............................................................27

FIG. 2.3: Arquivo notas.xsd................................................................................28

FIG. 2.4(a): Documento XML .................................................................................30

FIG. 2.4(b): Grafo da representação de documento XML ......................................31

FIG. 2.5: Grafo da representação simplificada...................................................32

FIG. 2.6: Etapas de KDD ...................................................................................38

FIG. 2.7: Exemplo de RNA.................................................................................43

FIG. 2.8: Exemplo de conjuntos Fuzzy ..............................................................45

FIG. 2.9: Taxonomia dos itens do exemplo........................................................52

FIG. 2.10: Dados para classificação ....................................................................54

FIG. 4.1: Alteração de atributo...........................................................................64

FIG. 4.2: Alteração de referência.......................................................................65

FIG. 4.3: Exemplo de documento XML ..............................................................68

FIG. 4.4: Modelo de estrutura do exemplo da FIG. 4.3......................................68

FIG. 4.5: Estrutura do documento XML gerado pela aplicação..........................69

FIG. 4.6: Representação esquemática de estruturas semelhantes ...................71

FIG. 4.7: Formato basket ...................................................................................75

FIG. 4.8: Processamento clássico de documentos XML....................................76

FIG. 4.9: Algoritmo Apriori..................................................................................77

FIG. 4.10(a): Avaliação do suporte das transações .................................................80

FIG. 4.10(b): Avaliação da confiança e geração de regras ......................................80

FIG. 4.11: Formato basket ...................................................................................81

FIG. 4.12(a): Avaliação do suporte das transações .................................................82

FIG. 4.12(b): Avaliação da confiança e geração das regras.....................................83

FIG. 4.13: Algoritmo ASCX-1P.............................................................................88

FIG. 4.14: Algoritmo ASCX-2P.............................................................................93

FIG. 4.15: Algoritmo ASCX-1PG..........................................................................99

FIG. 4.16: Algoritmo ASCX-2PG........................................................................103

FIG. 4.17: Esquema de classificação baseada em regras de associação .........109

FIG. 5.1: Testes dos algoritmos de geração de regras de associação em

documentos XML ..............................................................................118

FIG. 5.2: Tempos normalizados dos testes dos algoritmos de geração de

regras de associação em documentos XML .....................................121

FIG. 5.3: Gráficos dos testes dos algoritmos de geração de regras de

associação em documentos XML .....................................................123

FIG. 5.4(a): Tempos médios de processamento dos algoritmos de regra de

associação ........................................................................................124

FIG. 5.4(b): Gráfico comparativo dos tempos médios de processamento dos

algoritmos de regra de associação ...................................................125

FIG. 5.5: Testes dos algoritmos de geração de regras de associação

generalizadas em documentos XML.................................................128

FIG. 5.6: Tempos normalizados dos testes dos algoritmos de geração de

regras de associação generalizada em documentos XML................130

FIG. 5.7: Gráficos dos testes dos algoritmos de geração de regras de

associação generalizada em documentos XML................................131

FIG. 5.8(a): Tempos médios de processamento dos algoritmos de regra de

associação generalizada...................................................................132

FIG. 5.8(b): Gráfico comparativo dos tempos médios de processamento dos

algoritmos de regra de associação generalizada..............................133

FIG. 5.9: Resultados de classificação em documentos XML ...........................135

FIG. 8.1: Visão geral da implementação..........................................................146

LISTA DE SIGLAS

API Application Programming Interface

ASCX-1P Algoritmo de Mineração de Regras de Associação Sem geração de Candidatos

em documentos XML em 1 Passo

ASCX-2P Algoritmo de Mineração de Regras de Associação Sem geração de Candidatos

em documentos XML em 2 Passos

ASCX-1PG Algoritmo de Mineração de Regras Generalizada de Associação Sem geração

de Candidatos em documentos XML em 1 Passo

ASCX-2PG Algoritmo de Mineração de Regras de Associação Generalizada Sem geração

de Candidatos em documentos XML em 2 Passos

BI Business Intelligence

CApriori Classificação baseada no Algoritmo de classificação Apriori

CASCX-1P Classificação baseada no Algoritmo de Mineração de Regras de Associação

Sem geração de Candidatos em documentos XML em 1 Passo

CASCX-2P Classificação baseada no Algoritmo de Mineração de Regras de Associação

Sem geração de Candidatos em documentos XML em 2 Passos

CD com dado (elemento XML)

DOM Document Object Model

DTD Document Type Definition

KDD Knowledge Discovery in Databases

GML Generalized Markup Language

HTML Hyper Text Markup Language

MDL Minimum Description Length

MU múltiplo (elemento XML)

OB obrigatório (elemento XML)

OEM Object Exchange Model

OLAP On-Line Analytic Processing

OP opcional (elemento XML)

OWL Ontology Web Language

PCDATA Parsed Character Data

PMML Predictive Model Markup Language

RDF Resource Description Format

RDFS RDF Schema

RNA Rede Neural Artificial

SAX Simple API for XML

SD sem dado (elemento XML)

SGBD Sistemas Gerenciadores de Bancos de Dados

SGML Standard Generalized Markup Language

SI simples (elemento XML)

SQL Structured Query Language

W3C World Wide Web Consortium

XML eXtended Markup Language

XMLA XML for Analysis

XSL eXtensible Stylesheet Language

XSLT eXtensible Stylesheet Language Transformation

RESUMO

Esta dissertação propõe novos métodos para implementação das tarefas de associação e

classificação em documentos XML. Associação e classificação são duas importantes tarefas

de KDD (Knowledge Discovery in Databases), originalmente definidas para aplicação em

bancos de dados relacionais. XML é um padrão de representação para armazenamento e

intercâmbio de dados, que vem tendo grande disseminação pela sua aplicação na Internet e se

caracteriza por ser uma estrutura de dados semi-estruturados hierarquizada.

Estudos de descoberta de conhecimento em dados semi-estruturados se encontram em

estágio incipente e normalmente envolvem técnicas adaptadas de KDD para dados

estruturados, cujos estudos se encontram em estágio mais avançado. As técnicas tradicionais

de associação - baseados no algoritmo Apriori - envolvem a geração de conjuntos de itens

candidatos e apresentam baixo desempenho devido ao grande número de iterações necessárias

para obtenção dos resultados desejados. Os métodos propostos, além de mais adequados para

tratamento de dados semi-estruturados (como XML), não fazem a geração de conjuntos de

itens candidatos e, assim, mostra um desempenho superior quando comparado com a

implementação do algoritmo Apriori.

ABSTRACT

This dissertation considers new methods for implementation of the association and

classification tasks in XML documents. Association and classification are two importants

tasks of KDD (Knowledge Discovery in Databases), originally defined for application in

relational data bases. XML is a standard of representation for storage and interchange of data,

that come having great dissemination for its application in the Internet and characterizes for

being a structure of hierarchical semi-structured data.

Studies of discovery of knowledge in semi-structured data are in a very early stage and

normally they involve suitable techniques of KDD for structured data, whose studies are in

more advanced stage. The traditional techniques of association - based in Apriori algorithm -

involve the generation of candidate sets of itens and present overhead due to the great number

of iterations necessary to get the desired results. The considered methods, beyond more

adjusted for semi-structured data handling (as XML), do not make the generation of

candidates sets of itens and thus it shows when comparative a superior performance with the

implementation of the Apriori algorithm.

1. INTRODUÇÃO

1.1. POSICIONAMENTO E JUSTIFICATIVA

Os constantes avanços na área da Tecnologia da Informação têm viabilizado o

armazenamento de grandes volumes dados. Dispositivos de memória secundária com maior

capacidade de armazenamento e de menor custo, Sistemas Gerenciadores de Bancos de Dados

(SGBD) capazes de operar com bases de dados cada vez maiores e as modernas técnicas de

Datawarehouse (KIMBAL, 1998) são alguns exemplos de recursos que têm viabilizado a

proliferação e o crescimento de inúmeras bases de dados de natureza comercial,

administrativa, governamental e científica (GOLDSCHMIDT, 2003).

Essas bases de dados, antigamente processadas em ambientes restritos, dentro das

instituições ou então em computadores remotos conectados em redes dedicadas, agora vêem

expandir o seu alcance através da Internet, o que facilita em muito o seu manuseio por

diferentes tipos de usuários em diferentes partes do mundo.

A Internet também se mostra origem de grande quantidade de dados ao facilitar, por

exemplo, o comércio eletrônico, responsável por milhares de novas transações comerciais a

cada dia.

Diante deste grande volume de dados é natural surgir o interesse em analisá-lo e assim

poder utilizá-lo de maneira útil, num processo conhecido como "transformação de dados em

informação"

. A análise destes dados torna-se inviável com uso de técnicas tradicionais como

planilhas, relatórios, etc, onde o especialista normalmente precisa lidar com muitas

informações para poder chegar a algumas conclusões sobre o comportamento/tendência

daqueles dados (conhecimento implícito). Uma análise mais complexa destas grandes bases

de dados é praticamente inviável sem o auxílio de ferramentas computacionais apropriadas, o

que torna imprescindível o desenvolvimento de ferramentas que auxiliem o homem, de forma

mais adiante será mostrada a relação entre dados e informação.

automática e inteligente, na tarefa de analisar, interpretar e relacionar estes dados para que se

possa desenvolver e selecionar estratégias de ação em cada área de aplicação

(GOLDSCHMIDT, 2003).

O processo de descoberta de conhecimento em bancos de dados (Knowledge Discovery in

Databases – KDD) foi proposto em 1989 para descrever as etapas necessárias para abstração

de novos conhecimentos a partir dos dados e pode ser definido como:

“Um processo de várias etapas, não trivial, interativo e iterativo, para

identificação de padrões compreensíveis, válidos, novos e potencialmente úteis a

partir de um conjunto de dados” (FAYYAD, PIATETSKY-SHAPIRO, SMYTH,

1996)

FIG. 1.1: Hierarquia entre Dado, Informação e Conhecimento.

É importante neste ponto definir as diferenças entre dados, informação e conhecimento.

Os dados físicos (armazenados em meio físico) podem ser interpretados como itens

elementares. As informações representam dados processados, isto é, com significado próprio

conhecido e contexto bem definidos. Um padrão ou conjunto de padrões cuja formulação

pode envolver e relacionar dados e informações é denominado conhecimento. O

relacionamento entre os três, dados, informação e conhecimento, pode ser representado

através de uma pirâmide como mostra a FIG. 1.1, onde são apresentados alguns exemplos

ilustrativos.

Por sua vez, a Internet passa por uma grande evolução, onde, a cada instante, se percebe o

crescimento do número de pessoas que fazem acesso a várias páginas

existentes, que

oferecem os mais variados tipos de serviços. Tal sucesso se deve inegavelmente à facilidade,

à clareza e, muitas vezes, à beleza destas páginas, onde são utilizadas muitas tecnologias na

sua elaboração, como, por exemplo, Flash, Java, ASP, PHP, JavaScript, VBScript, etc. No

entanto todas têm um ponto em comum: HTML (Hyper Text Markup Language) [3], a

linguagem que define a sua estrutura básica.

Quando a Internet surgiu, as páginas eram bem simples, com poucos recursos e estáticas,

isto é, sempre exibiam o mesmo conteúdo quando solicitadas – até mesmo as ilustrações eram

formadas por desenhos “estáticos”. Algumas tecnologias surgiram para dar um certo

“dinamismo” às paginas, como por exemplo, GIF animados e Flash (para ilustrações),

JavaScript e VBScript (incorporados ao código HTML), ASP e PHP (executando nos

servidores, estas tecnologias fazem com que diferentes páginas sejam geradas para

solicitações idênticas, causando a impressão de paginas dinâmicas).

<?xml version="1.0" encoding="UTF-8"?>

<carta>

<nome> Sr. Carlos Silva </nome>

<rua> Rua Elevada 10 </rua>

<cidade> Rio de Janeiro </cidade>

</endereco>

</destinatario>

<assunto> Parecer </assunto>

<saudacao> Prezado Senhor, </saudacao>

Pela presente, solicitamos seu

parecer para o processo

encaminhado pelo Sr(a).

<cliente> Maria Souza </cliente>.

No aguardo.

</principal>

</carta>

FIG. 1.2: Exemplo de documento XML

A HTML, no entanto, se mostrava limitada para atender à complexidade cada vez

crescente das aplicações disponíveis na Internet, pois era voltada apenas para apresentação de

informações. A necessidade de separar a linguagem de controle da linguagem de apresentação

– HTML – dos dados propriamente ditos, motivou o surgimento da XML (eXtended Markup

Language) [11].

usaremos este termo como referência a homepage e site.

XML (ANDERSON, 2001), assim como a HTML, é uma linguagem baseada em

marcações (tags) para a definição da estrutura dos dados existentes num documento,

denominado documento XML. A FIG. 1.2 mostra um documento XML contendo os dados de

uma carta, onde é fácil identificar as suas várias partes.

Documentos XML apresentam duas características importantes: os dados possuem uma

estrutura hierárquica; e os atributos dos dados, inclusive a sua hierarquia, são definidos

explicitamente no próprio documento.

Apesar de utilizada em documentos contendo textos longos, como cartas, reportagens

(jornais), etc, a principal aplicação da XML é na descrição de dados estruturados, como no

documento notas.xml mostrado na FIG. 1.3, que descreve as notas dos alunos de uma

turma.

<?xml version="1.0"?>

<turma>

<notas>

</notas>

</aluno>

<nome>CARLOS</nome>

<notas>

</notas>

</aluno>

<nome>MARIA</nome>

<notas>

</notas>

</aluno>

</turma>

FIG. 1.3: Documento notas.xml

Podemos observar que documentos XML permitem uma representação estrutural

heterogênea, isto é, não são completamente não-estruturados, nem estritamente tipados, o que

os caracterizam como dados semi-estruturados (MELLO, DORNELLES, KADE,

BRAGANHOLO, HEUSER, 2000).

Atualmente se observa a utilização de XML como padrão de representação para

armazenamento e intercâmbio de dados, tanto pela Internet quanto por aplicações

convencionais, servindo inclusive como formato de armazenamento de dados.

Embora existam inúmeros estudos avançados no desenvolvimento e aplicação de técnicas

de KDD em dados estruturados (ver seção 3.2), o mesmo não se pode afirmar sobre os estudos

em descoberta de conhecimento em dados semi-estruturados (ver seções 3.3 e 3.4), muitos

dos quais se encontram ainda em estágio incipiente. Considerando-se o uso crescente de XML,

a pesquisa nesta área de aplicação de técnicas de KDD em documentos XML se mostra

bastante oportuna.

1.2. OBJETIVOS

Este trabalho tem como objetivos:

• pesquisar o estado da arte da descoberta de conhecimento em documentos XML e

elaborar um resumo das principais pesquisas na área;

• propor novos métodos para execução de tarefas de KDD em documentos XML,

adequados, portanto, para explorar suas características específicas – neste trabalho

estaremos nos limitando a novos métodos para as tarefas de classificação e associação,

de grande relevância na área; e

• implementar, avaliar e relatar os resultados obtidos a partir dos métodos propostos.

O modelo e implementação propostos para descoberta de conhecimento diretamente em

documentos XML, sem a necessidade de transformação dos dados em outro formato, é

inovador ao aplicar técnicas de descoberta de conhecimento em dados com a estrutura

hierarquizada (XML) (BÜCHNER, BAUMGARTEN, MULVENNA, BÖHM, ANAND,

2000), diferentemente das técnicas convencionais que são normalmente aplicadas a bases de

dados relacionais.

Neste texto serão estudadas as tarefas de associação (AGRAWAL, IMIELINSKI,

SWAMI, 1993) e de classificação (GOLDSCHMIDT, 2003) aplicadas a documentos XML,

que são certamente as tarefas de KDD mais utilizadas e por isso duas das mais importantes

entre as tarefas de KDD.

1.3. ASSUNTOS NÃO ABORDADOS

Descoberta de conhecimento e XML estão relacionadas, diretamente ou indiretamente,

em outras áreas de conhecimento ou tecnologias. Portanto, para definir com maior precisão o

escopo deste trabalho, seguem alguns assuntos que não são tratados.

• Text Mining (DORRE, GERRSTL, SEIFFERT, 1999): compreende a descoberta de

conhecimento em textos, que podem ou não existir em documentos XML;

• Web Mining (COOLEY, MOBASHER, SRIVASTAVA, 1997): descoberta e análise de

informações úteis disponíveis na Internet;

• XMLA (XML for Analysis) [12]: API (Application Programming Interface) criada com

a intenção de padronizar a interação entre um servidor de dados OLAP (On-Line

Analytic Processing) e uma aplicação cliente – principalmente de BI (Business

Intelligence) – através da Internet e se baseia em XML;

• PMML (Predictive Model Markup Language) [5]: linguagem de marcação para

modelos estatísticos e de mineração de dados (datamining) baseada em XML;

• Linguagem de consulta em documentos XML: este tipo de linguagem (p.e., [15])

normalmente retorna dados no formato XML, que não é considerado neste estudo; os

métodos propostos se aplicam ao documento XML como um todo e que podem assim

ser aplicados a determinados trechos selecionados através destas linguagens

1.4. ORGANIZAÇÃO DO TRABALHO

Este texto está organizado como descrito a seguir.

No CAPÍTULO 1 é feito o posicionamento deste trabalho em relação ao contexto das

técnicas envolvidas e apresenta os objetivos que se espera alcançar no final do trabalho.

Apenas para evitar dúvidas, são apresentados os assuntos que não são tratados neste trabalho.

todo o documento é percorrido sequencialmente.

O CAPÍTULO 2 é reservado à apresentação dos conceitos teóricos utilizados em todo o

trabalho, quando são resumidos os principais conceitos de XML e de KDD, com destaque para

regras de associação e classificação baseada em regras de associação.

O CAPÍTULO 3 apresenta as pesquisas estudadas para elaboração deste trabalho que

compreendeu desde textos que exploram os assuntos individualmente, que serviram para

fundamentar ainda mais os conceitos envolvidos, mas também alguns estudos que

relacionavam os dois assuntos abordados: XML e descoberta de conhecimento.

No CAPÍTULO 4, a abordagem conceitual dos métodos propostos neste trabalho é

descrita em detalhes, enquanto que o CAPÍTULO 5 relata a implementação do protótipo e a

sua utilização, quando são descritos os experimentos e os resultados obtidos.

As conclusões deste trabalho são apresentadas no CAPÍTULO 6.

2. FUNDAMENTAÇÃO TEÓRICA

2.1. XML

2.1.1. HISTÓRICO

A linguagem XML, assim como HTML

, se originou da linguagem de marcação SGML

(Standard Generalized Markup Language) [9]. A SGML surgiu em 1986 como evolução da

GML (Generalized Markup Language), cujos estudos iniciaram em 1969 na IBM. Logo a

SGML ganhou importância ao ser adotada pelos principais sistemas de documentação, pois

permitia um modo padronizado para criar, exibir e trocar documentos entre diferentes

usuários, independente do sistema utilizado. A sua grande complexidade motivou o uso de um

subconjunto de seus recursos voltados para apresentação, causando o desenvolvimento da

linguagem HTML.

Depois percebeu- se na HTML a ausência de recursos para descrição de dados, motivando

aí o surgimento do XML em 1996, a partir de definições já existentes na SGML.

O W3C (World Wide Web Consortium) [19] é o órgão responsável pela especificação da

HTML e da XML, que atualmente (2004) se encontra na sua versão 1.1.

2.1.2. FORMATO DE DOCUMENTO XML

Um documento XML é formado por elementos que contém dados ou outros elementos.

Cada elemento é de um determinado tipo e, dependendo do tipo, pode conter um ou mais

atributos. Cada elemento pode ser formado pela combinação de outros elementos

denominados sub-elementos ou elementos filho . Os sub-elementos de um elemento, também

um breve histórico da HTML foi apresentado na seção 1.1.

denominado elemento pai, são ordenados, ao contrário dos atributos, que não são ordenados.

Atributos somente podem conter dados, isto é, não podem conter elementos ou outros

atributos. Este mecanismo define uma hierarquia entre os elementos a partir de um elemento

raiz, o que possibilita que um documento XML seja representado por uma árvore

Por exemplo, a FIG. 2.1 ilustra a representação gráfica do documento notas.xml

exibido na FIG. 1.3., onde as “arestas” correspondem às marcações e os “nós” ao conteúdo

delimitado por estas marcações

FIG. 2.1: Representação gráfica do documento notas.xml

Num documento XML pode ser definido um atributo especial denominado ID, cujo valor

(dado) associado deve ser único em todo o documento, isto é, não existem dois IDs com o

mesmo valor num documento XML. É também possível definir o atributo especial IDREF,

cujo valor associado deve ser igual ao valor associado ao atributo ID de outro elemento

qualquer, bem como o atributo especial IDREFS, que pode ser usado para referenciar um

conjunto de elementos. Estes mecanismos permitem que um elemento referencie um outro

elemento dentro do mesmo documento, fazendo com que, na verdade a representação de um

veremos adiante que um documento XML é representado na verdade por um grafo.

a seção 2.1.4 apresenta a formalização de XML.

documento XML se assemelhe a um grafo, e não a uma árvore como comentado

anteriormente

nesta seção.

XML, assim como a HTML, é uma linguagem baseada em marcações (tags) que definem

a estrutura dos elementos existentes no documento, o documento XML.

As marcações em documentos XML são classificadas em dois tipos: inicial ou final. A

marcação final tem o mesmo identificador da marcação inicial, com a diferença que se inicia

por um “/”. Marcações delimitam um trecho do documento XML

, que pode ser formado por

dados (um conteúdo ou outro trecho delimitado por marcações). Os nomes dos identificadores

usados nas marcações em documentos XML podem ser criados livremente, ao contrário do

que ocorre com HTML, onde só podem ser usados identificadores pré-estabelecidos.

O documento notas.xml, exibido na FIG. 1.3 como exemplo, apresenta as marcações

<turma> e </turma>, que delimitam os dados de vários alunos, enquanto que <faltas>

e </faltas> delimitam um número que representa a quantidade de faltas de um aluno

(conteúdo). As marcações podem delimitar um conteúdo vazio, como por exemplo em

<faltas></faltas>, o que também pode ser representado por um único identificador

com um caracter “/” no final da marcação, como por exemplo em <faltas/> - ou seja,

<faltas></faltas> e <faltas/> têm a mesma função.

Atributos são definidos no formato atributo=”valor”. No documento notas.xml

exibido na FIG. 1.3 cada elemento “aluno” tem um atributo identificado como “matrícula”

que indica a matricula do aluno. Por exemplo, é possível observar que matrícula do “JOSE” é

12345.

Documentos XML com estrutura que respeitam as regras de formação apresentadas são

denominados documentos bem formados.

Um documento XML pode se constituir de (BEECH, MALHOTRA, RYS, 1999):

extensões deste mecanismo permitem que elementos de outros documentos XML sejam referenciados; o

uso dos atributos IDREF e IDREFS como mecanismo de referência deve estar descrito no esquema associado

(ver seção 2.1.3).

XML permite ainda outros tipos de elementos, como comentários e instruções de processamento, que não

adicionam significado à sua estrutura, pois têm outros proósitos, e por isso não considerados neste trabalho; veja

[An01] para maiores detalhes sobre XML.

• um documento XML completo ou um conjunto de fragmentos de uma coleção de

documento, selecionados de acordo com um critério de seleção;

• um documento originalmente criado no formato XML ou uma visão XML sobre dados

existentes em outros formatos.

Para este trabalho consideraremos apenas um documento XML completo e único,

bastando que seja, bem formado, sem prejuízo para as técnicas apresentadas.

2.1.3. ESQUEMAS

<?xml version="1.0"?>

<!DOCTYPE turma [ 





<!ELEMENT turma (aluno+)> 





<!ELEMENT aluno (nome, notas, faltas?)> 



 D

<!ELEMENT notas (redes, compiladores)> 



 T

<!ELEMENT nome (#PCDATA)> 



 D

<!ELEMENT faltas (#PCDATA)> 





<!ELEMENT redes (#PCDATA)> 





<!ELEMENT compiladores (#PCDATA)> 





<!ATTLIST aluno matricula CDATA #REQUIRED> 





]> 





<turma>

<notas>

</notas>

</aluno>

...

FIG. 2.2: DTD do documento notas.xml

Na seção 2.1.2 foi apresentada a estrutura básica de um documento XML. No entanto,

muitas vezes é necessário garantir que diferentes documentos XML tenham a mesma

estrutura. Por exemplo, o arquivo notas.xml (FIG. 1.3) corresponde aos dados de alunos

de uma turma. Os dados de alunos de outras turmas precisam ter o mesmo formato para

permitir que sejam processados do mesmo modo pelas aplicações. Para que isso seja possível,

é necessário definir formalmente a estrutura dos documentos XML e associá-los aos

respectivos documentos. Esta estrutura formal, denominada esquema, pode ser definida de

dois modos: através de uma DTD (Document Type Definition) [2] ou XMLSchema [16].

A FIG. 2.2 exibe o trecho do documento notas.xml (FIG. 1.3), alterado de modo a

incluir a DTD no seu início.

A DTD pode, e deve, ser escrita em documento separado, o que permite, por exemplo,

que a DTD seja referenciada por diferentes documentos que têm a mesma estrutura.

A DTD apresenta algumas restrições. Por exemplo, não é possível definir com maior

precisão o tipo de dados – a DTD só permite definir o tipo PCDATA (Parsed Character

Data), ou seja, qualquer sequência de caracteres (string). É fácil observar que a sintaxe usada

na DTD não obedece ao padrão XML, o que obriga que as aplicações, ao processar

documentos XML com DTD, usem mais de um tipo de analisador (parser). Estas restrições

motivaram o desenvolvimento da XMLSchema, outra forma de definir um esquema, que tem

as seguintes características:

• possui sintaxe XML;

• permite a definição de tipos de elementos; e

• permite um amplo controle de restrições, como cardinalidade.

<?xml version="1.0"?>

<xsd:schema xmlns:xsd="http://www.w3.org/2001/XMLSchema">

<xsd:element name="turma">

<xsd:complexType>

<xsd:sequence >

<xsd:element name="aluno" type="Taluno"

maxOccurs="unbounded"/>

</xsd:sequence>

</xsd:complexType >

</xsd:element>

<xsd:complexType name="Taluno">

<xsd:sequence>

<xsd:element name="nome" type="xsd:string"/>

<xsd:element name="notas" type="Tnotas"/>

<xsd:element name="faltas" type="xsd:string"

minOccurs="0">

</xsd:element>

</xsd:sequence>

<xsd:attribute name="matricula" type="xsd:integer"/>

</xsd:complexType>

<xsd:complexType name="Tnotas">

<xsd:sequence>

<xsd:element name="redes" type="xsd:float"/>

<xsd:element name="compiladores" type="xsd:float"/>

</xsd:sequence>

</xsd:complexType>

</xsd:schema>

FIG. 2.3: Arquivo notas.xsd

A FIG. 2.3 mostra o esquema externo do arquivo notas.xml (FIG. 1.3) definido

através de XMLSchema.

Do mesmo modo como ocorre com a DTD, o XMLSchema também pode ser escrito no

interior do documento XML.

Documentos XML validados com relação ao esquema associado, seja através de DTD ou

de XMLSchema, são denominados documentos válidos.

2.1.4. MODELO FORMAL DE DADOS EM DOCUMENTOS XML

O modelo de dados em documentos XML é definido formalmente como o grafo

direcionado G=(V,E,A,R,O) (BEECH, MALHOTRA, RYS, 1999), onde: V representa o

conjunto dos vértices (ou nós); E, A e R representam o conjunto de arestas direcionadas no

grafo que unem os vértices de V; e O representa a ordem entre os elementos de um conjunto e

não possui representação gráfica.

a) Vértices V

O conjunto V contém vértices que representam os elementos e os dados do documento

XML. Formalmente temos que V=V

elemento

∪V

tipo1

∪V

tipo2

∪...∪V

tipon

, onde V

elemento

representa

o conjunto dos elementos do documento e V

tipoi

o conjunto de dados presentes no documento

de acordo com o tipo representado, sendo tipo

os tipos de dados (inteiro, string, etc).

Consideraremos que dados só são de um único tipo sem perda de compreensão do modelo, ou

seja, os dados são representados pelos vértices do conjunto V

tipo

. Portanto, temos que

V=V

elemento

∪V

tipo

Cada elemento XML é representado pelo vértice v∈V

elemento

, que possui identificador

abstrato (não pode ser acessado diretamente), único (funciona como chave), lógico

(independente do meio físico) e imutável. Vértices v∈V

elemento

possuem um nome que

corresponde ao nome do elemento no documento XML.

Cada valor do documento XML é representado pelo vértice v∈V

tipo

, que possui o valor do

vértice. Cada vértice v∈V

tipo

armazena dados de elementos, atributos, comentários e

instruções de processamento. Comentários e instruções de processamento são representados

como dados especiais, não recebendo outro tipo de tratamento no modelo.

b) Arestas E

Toda aresta e∈E é um relacionamento direcionado ligando um vértice v∈V

elemento

a um

vértice v'∈V e possui um nome. Quando v'∈V

elemento

, nome da aresta é o nome de v' e

corresponde ao nome de um elemento do documento XML. Quando v'∈V

tipo

, a aresta tem o

nome especial ~dados.

c) Arestas A

Toda aresta e∈A é um relacionamento direcionado ligando um vértice v∈V

elemento

a um

vértice v'∈V

tipo

e possui um nome, que corresponde ao nome do atributo no documento XML

e o valor de v' ao valor do atributo.

<?xml version="1.0" encoding="UTF-8"?>

<!DOCTYPE bd [

<!ELEMENT bd (filme+, ator+)>

<!ELEMENT filme (titulo, diretor, elenco)>

<!ATTLIST filme id ID #REQUIRED>

<!ELEMENT titulo (#PCDATA)>

<!ELEMENT diretor (#PCDATA)>

<!ELEMENT elenco EMPTY>

<!ATTLIST elenco idrefs IDREFS #REQUIRED>

<!ELEMENT ator (nome, atuou)>

<!ATTLIST ator id ID #REQUIRED>

<!ELEMENT nome (#PCDATA)>

<!ELEMENT atuou EMPTY>

<!ATTLIST atuou idrefs IDREFS #REQUIRED>

<bd>

</filme>

</filme>

</ator>

</ator>

</ator>

</bd>

FIG. 2.4(a): Documento XML

d) Arestas R

Toda aresta e∈R é um relacionamento direcionado ligando um vértice v∈V

elemento

a um

vértice v'∈V

elemento

correspondendo à ligação implícita estabelecida no documento XML pelo

atributo IDREF no elemento representado pelo vértice v' e pelo atributo ID no elemento

representado pelo vértice v. Podemos considerar que o vértice v' é o vértice de um sub-grafo,

conectado ao vértice v, pela aresta e∈R.

FIG. 2.4(b): Grafo da representação de documento XML

A FIG. 2.4(b) mostra um exemplo de representação através de um grafo do documento

XML exibido na FIG. 2.4(a).

As referências (arestas R) só têm efeito num documento XML se existir um esquema

associado, como neste exemplo, onde pode ser observada a definição de uma DTD (ver seção

2.1.3).

O nó RAIZ foi incluído, apesar de não constar na definição original (BEECH,

MALHOTRA, RYS, 1999), para facilitar a indicação do nó de acesso à estrutura (grafo).

Este modelo é o mais completo para representação da XML, e está sendo desenvolvido

pela W3C [19], órgão que vem regulamentando todos os assuntos relativos à Internet. No

entanto, XML também pode ser representada por um modelo mais simples, baseado no OEM

(Object Exchange Model) (SUCIU, 1998), modelo de dados semi-estruturados proposto por

(PAPAKONSTANTINOU, GARCIA-MOLINA, WIDOM, 1995). Este modelo simplificado

é utilizado no restante deste trabalho.

FIG. 2.5: Grafo da representação simplificada

As seguintes propriedades do modelo OEM são utilizadas para a simplificação:

• toda aresta a∈A tem o nome do vértice v∈V

elemento

; é eliminada esta redundância

tirando de V

elemento

a sua propriedade nome, que é assumida implicitamente pela aresta

a∈A que o acessa.

• todo vértice v∈V

elemento

associado a um elemento do documento XML com dado tem

uma aresta a∈A como nome ~data conectando a um vértice v∈V

tipo

que armazena o

dado; tanto a aresta a∈A, quanto o vértice v∈V

tipo

são excluídos, e o dado é associado

ao vértice v∈V

elemento

Então, o modelo simplificado do XML é idêntico ao proposto anteriormente, ou seja, é

definido formalmente como o grafo direcionado G=(V,E,A,R,O), onde: V representa o

conjunto dos vértices (ou nós); E, A e R representam o conjunto de arestas direcionadas no

grafo que unem os vértices de V; e O representa a ordem entre os elementos de um conjunto,

E, A ou R, e não possui representação gráfica. A diferença está na representação dos

elementos do documento XML, onde as arestas de A recebem o nome dos respectivos

elementos. O vértice em V ou tem um valor, o dado contido no elemento, ou é vazio, quando

o elemento também é vazio.

A FIG. 2.5 mostra a representação simplificada (modelo OEM) do documento XML da

FIG. 2.4(a).

Na FIG. 2.5 estão representadas as identificações abstratas de alguns vértices que

usaremos para exemplificar as propriedades caminho e valor dos vértices:

• caminho: definido como a sequência de arestas a partir da raiz; as arestas são

representadas pelo seu nome e são concatenadas por:

- uma barra ("/") se o vértice para onde converge é do tipo V

elemento

e a aresta ∈E

- uma seta ("→") se o vértice para onde converge é do tipo V

elemento

e a aresta ∈R

- uma arroba ("@") se o vértice é do tipo V

tipo

Por exemplo:

- caminho(v

) = bd

- caminho(v

) = bd/filme/titulo

- caminho(v

) = bd/ator/atuou→filme/titulo

- caminho(v

) = bd/filme@id

Como o nome do vértice é definido como o nome da aresta que converge para aquele

vértice, caminho também pode ser definido como a concatenação dos nomes dos

vértices.

O caminho também pode ser obtido com relação a um determinado vértice. Neste caso

o caminho informado compreende as arestas a partir do vértice informado, formando

assim um caminho relativo. O vértice de início do caminho pode ser fornecido de modo

inequívoco pelo seu caminho. Por exemplo

- caminho(v

, v

) = filme/titulo OU caminho(bd, v

) = filme/titulo

- caminho(v

, v

) = bd/filme@id OU caminho(bd, v

) = filme@id

• valor: definido como o conteúdo do vértice

por exemplo:

- valor(v

) = # (vazio)

- valor(v

) = "F1"

O vértice possui ainda a propriedade identificador

, que retorna o identificador abstrato

do vértice que, como descrito anteriormente, é único para cada vértice do grafo.

2.1.5. TECNOLOGIAS RELACIONADAS

A estrutura hierárquica dos documentos XML e a grande quantidade de marcações

dificultam a visualização e compreensão dos dados existentes em documentos XML. A

linguagem XSL

(eXtensible Stylesheet Language) [17] foi desenvolvida então com recursos

para formatar documentos XML para a exibição em tela (programas navegadores – browsers)

e até mesmo em papel (impressoras). Posteriormente a XSL foi dividida, originando a XSLT

(eXtensible Stylesheet Language Transformation) [18], contendo somente recursos para

transformação.

Um arquivo XSTL é um documento XML bem-formado pode ser aplicado em um arquivo

XML, gerando um outro arquivo qualquer, que pode ser, por exemplo, um arquivo XML ou

arquivo HTML.

Documentos XML armazenam dados, sendo então natural a existência de linguagens de

consultas para acesso e seleção de dados adequados à necessidades específicas. A linguagem

XPath (XML Path Language) [13] tem uma estrutura que permite a definição formal dos

elementos de um documento, o que acaba funcionando como uma verdadeira linguagem de

consulta.

neste trabalho consideraremos que a propriedade identificador retorna um número sequencial qualquer.

XSL funciona como uma folha de estilos, de modo semelhante ao CSS (Cascading

Style Sheets) , folha de estilos para páginas HTML.

XPath é uma forma poderosa de referenciar um ou mais elementos e/ou seus atributos

através de uma única expressão, sendo por isso utilizada por outras linguagens, como, por

exemplo, o XSLT e o XQuery (mostrada a seguir).

A linguagem de consulta em documentos XML mais utilizada atualmente é XQuery

(XML Query Language) [15], principalmente por ser um padrão proposto pelo W3C. A

XQuery (2001) se originou da consolidação de várias outras linguagens de consulta como

XML-QL (1998, AT&T), Lorel (1997), XQL (1999, Microsoft) e QUILT (2001, IBM) entre

várias outras e trata o documento XML como uma árvore de nós. Cada consulta em XQuery é

definida através de uma expressão e funcionalmente possui grande semelhança com a

linguagem SQL (Structured Query Language) amplamente utilizada em bancos de dados

relacionais.

Vários requisitos são considerados na especificação da XQuery pelo W3C. Entre eles

podemos destacar: é uma linguagem declarativa e independente de protocolo, tem suporte a

tipos simples e complexos, quantificadores universais e existenciais, possui operações sobre

hierarquias e sequências de documentos estruturados, combina informações a partir de

múltiplos documentos, oferece suporte à agregação de dados, além de ser capaz de

transformar e criar estruturas XML.

Dados no formato XML podem ser armazenados em bancos de dados relacionais (Oracle,

Microsoft SQL Server, DB2, etc) que disponibiliza interfaces adequadas para tratamento e

armazenamento de dados em XML, tornando o processamento nesta tecnologia totalmente

transparente para o usuário. Nestes casos, os bancos de dados armazenam dados de

documentos em XML em tabelas, sempre precisando executar um processamento extra para

conversão dos dados lidos/gravados. No entanto, já existem bancos de dados nativos em

XML, isto é, bancos de dados onde tanto o armazenamento quanto o processamento são

realizados usando a tecnologia XML. O mais conhecido atualmente é o banco de dados

TAMINO

. XQuery é a linguagem de consulta mais encontrada nestes tipos de banco de

dados.

Alguns estudos utilizam XML como formato para difusão de informações. Entre eles

podemos destacar XLink (XML Linking Language) [10], para definição de links em

desenvolvido pela Software AG

(http://www2.softwareag.com/Corporate/products/tamino/default.asp)

documentos XML, permitindo assim associar dois ou mais recursos; e XPointer (XML

Pointer Language) [14], utilizado para descrever como endereçar um recurso do documento

A estrutura de XML, pela sua natureza, motiva vários estudos na área de metadados, uma

área rica em pesquisas, mas onde existe muito a ser explorado. A definição de marcações no

interior do arquivo adiciona informações importantes aos dados lá existentes, formando um

primeiro nível de semântica dos dados.

RDF (Resource Description Format) [6] e RDFS (RDF Schema) [7] são padrões que

descrevem documentos XML, de modo que aumentam ainda mais o nível de descrição de seus

conteúdos. O objetivo é, por exemplo, auxiliar a busca de informações na Internet, atualmente

muito baseada somente no texto, com pouca ou nenhuma interpretação do contexto de

utilização da palavra procurada. Este problema fica claro quando uma mesma palavra tem

vários significados diferentes, como por exemplo, “manga”, que pode ser usada tanto no

contexto de vestuário, quanto no de alimentação: o resultado deveria conter somente

informações sobre a palavra dentro contexto desejado.

OWL (Ontology Web Language) [4] é uma linguagem para descrição formal de

ontologias

dos dados existentes. O grau de formalismo obtido procura criar mecanismos

automáticos que possibilitem buscas na Internet ainda mais complexas, que podem então ser

realizadas por agentes dedicados. Este é um grau de sofisticação desejado pela grande maioria

de usuários que realizam pesquisas na Internet, o que pode estar num futuro não muito

distante.

Com o objetivo de facilitar o acesso e a manipulação de dados XML diretamente por

qualquer linguagem de programação, foram desenvolvidas APIs

(Application Program

Interfaces) DOM e SAX.

DOM (Document Object Model) [1] é uma API proposta pelo W3C com recursos para

criar documentos completos ou parciais, navegar no documento, mover, copiar e remover

especificação formal e explícita de como representar objetos, conceitos e outras entidades que são

assumidas existirem em alguma área de interesse e as relações entre elas (BONIFÁCIO, 2002).

API são bibliotecas de rotinas que funcionam como interface entre a aplicação (programa) e um recurso

específico, facilitando assim o seu acesso, pois permite que a aplicação não se preocupe com problemas

específicos da implementação.

partes do documento e adicionar ou modificar atributos, valores e elementos XML. Para

permitir estes recursos, uma API DOM carrega todo o arquivo XML na memória, onde realiza

todas as operações. No final, é possível então, por exemplo, salvar o conteúdo da memória em

disco.

Tendo em vista a grande quantidade de recursos necessária para a utilização da API

DOM, foi desenvolvida a API SAX (Simple API for XML) [8]. Ao contrário da API DOM, o

documento não é armazenado na memória, o que reduz a quantidade de recursos para utilizar

esta API. A API SAX faz uma varredura sequencial do documento XML e dispara eventos

adequados para cada tipo de item encontrado: início e fim de marcação, atributo, instrução de

processamento, conteúdo, etc. O programa deve então definir métodos para tratamento de

cada evento informado pela API SAX.

Praticamente todas as linguagens disponíveis no mercado, como Java, Delphi, Visual

Basic, têm APIs DOM e/ou SAX disponíveis, que podem ser incorporadas ao ambiente de

trabalho, permitindo assim o fácil processamento de documentos XML.

2.2. KDD E MINERAÇÃO DE DADOS

2.2.1. CONCEITOS BÁSICOS

A Descoberta de Conhecimento em Bases de Dados, ou simplesmente, como é mais

conhecido, KDD, sua sigla em inglês (de Knowledge Discovery in Databases), é caracterizado

por ser um processo composto por várias etapas operacionais, com o objetivo final de abstrair

conhecimentos a partir de grandes conjuntos de dados (datasets)

2.2.2. ETAPAS OPERACIONAIS

a seção 1.1 mostra uma definição completa de KDD.

FIG. 2.6: Etapas de KDD

A FIG. 2.6 apresenta a organização esquemática das etapas operacionais executadas em

processos de KDD. A etapa de pré-processamento compreende as funções relacionadas à

captação, à organização e ao tratamento dos dados e tem como objetivo a preparação dos

dados para os algoritmos da etapa seguinte; a etapa de mineração de dados compreende a

busca efetiva por conhecimentos úteis no contexto da aplicação de KDD; a etapa de pós-

processamento abrange o tratamento do conhecimento obtido na etapa anterior, apresentando

este conhecimento em um formato mais claro (é comum que os resultados dos algoritmos de

mineração de dados sejam codificados, necessitando assim de uma transformação adequada

para que se tornem efetivamente úteis).

Mineração de dados

é a principal etapa do processo de KDD, sendo que alguns autores

se referem à ela como sinônimo de KDD, pois durante esta etapa é realizada a busca efetiva

por conhecimentos úteis (no contexto da aplicação de KDD) através da aplicação de

algoritmos específicos.

Em seguida cada uma das etapas citadas é descrita de forma resumida.

a) Pré-processamento

A etapa de pré-processamento compreende, entre outras, as seguintes funções sobre os

dados:

datamining em inglês.

Seleção de Dados – identificar as informações que devem ser efetivamente consideradas

durante o processo de KDD entre as bases de dados existentes; por exemplo, informações

existentes nas bases de dados, mas que não trazem, ou trazem minimamente, qualquer tipo de

contribuição aos cálculos de mineração de dados, podem ser descartadas e assim diminuir o

esforço computacional envolvido nas etapas seguintes; esta função pode ser feita através de

seleção de atributos/campos ou de registros da base de dados.

Limpeza dos Dados – executar operações sobre os dados selecionados de forma a

assegurar a qualidade (completude, veracidade, integridade, etc

) dos fatos por eles

representados; completar informações ausentes e corrigir informações errôneas ou

inconsistentes a partir de informações externas (de outras bases de dados) são exemplos de

operações de limpeza de dados.

Codificação dos Dados – codificar os dados de modo que possam ser usados de maneira

adequada como entrada dos algoritmos de mineração de dados; a codificação pode ser

numérico-categórica (transformar valores reais em categorias) ou categórico-numérica

(representar numericamente valores de atributos categóricos).

Enriquecimento dos Dados – adicionar aos dados existentes mais informações a partir de

outras bases de dados.

b) Mineração de dados

Nessa etapa são definidas as técnicas e os algoritmos a serem utilizados, como, por

exemplo, Redes Neurais (HAYKIN, 2001), Algoritmos Genéticos (DAVIS, 1990), Modelos

Estatísticos e Probabilísticos (MICHIE, SPIEGELHALTER, TAYLOR, 1994). A seção 2.2.4

apresenta resumidamente algumas destas técnicas.

A escolha da técnica depende, muitas vezes, do tipo de tarefa de KDD a ser realizada (a

seção 2.2.3 apresenta as principais tarefas de KDD).

c) Pós-Processamento

A etapa de pós-processamento, tem como objetivo facilitar a interpretação e a avaliação

pelo homem da utilidade do conhecimento descoberto (FAYYAD, PIATETSKY-SHAPIRO,

SMYTH, 1996), sendo muitas vezes desnecessária.

os atributos de qualidade podem variar de acordo com a aplicação.

Entre as principais funções desta etapa estão, por exemplo, elaboração de gráficos e

diagramas a partir dos resultados obtidos, pois são normalmente de mais fácil de interpretação

pelo homem.

2.2.3. TAREFAS PRIMÁRIAS DE KDD

A seguir encontram-se resumidas algumas das principais tarefas de KDD referentes à

etapa de mineração de dados. Estas tarefas estão associadas ao tipo de conhecimento a ser

abstraído a partir dos dados disponíveis.

Cada uma das tarefas citadas abaixo pode ser implementada através das técnicas

mencionadas. Algumas destas técnicas são descritas na seção 2.2.4.

a) Descoberta de Associação

A tarefa de descoberta de associação compreende a busca por uma relação entre itens que

frequentemente ocorram de forma simultânea em transações do banco de dados. Estas

relações são expressas através de regras conhecidas como regras de associação. Por exemplo,

a partir da análise dos registros de vendas de um supermercado, podemos obter a expressão

"92% dos clientes que compram pão e manteiga também compram leite" ou então, a partir do

registro de vendas de um site comercial na Internet, que "78% das vendas feitas a clientes do

sexo masculino com idade entre 35 e 38 anos envolvem sabonete" (os itens estão em

destaque). Pode-se perceber a importância destas afirmações no auxílio, por exemplo, de

estratégias de marketing, potencial área de aplicação de regras de associação. A simples troca

de itens nestas expressões não são necessariamente válidas. Por exemplo, pode não ser válido

que "92% dos clientes que compram pão e leite também compram manteiga".

Quando os itens podem ser classificados de acordo com uma taxonomia conhecida, as

técnicas de associação podem ser estendidas de modo a relacionar os vários níveis da

hierarquia, permitindo, por exemplo, obter expressões mais gerais como "60% dos clientes

que compram (alguma) fruta também compram pão". Estas regras são conhecidas como

regras de associação generalizada.

Os algoritmos Apriori, GSP e DHP são exemplos de implementações utilizadas na tarefa

de descoberta de associações (ZAKI, 2000).

Descoberta de regras de associação, regras de associação, regras associativas ou

simplesmente associação são sinônimos frequentemente encontrados na literatura para a tarefa

de descoberta de associação e são utilizadas indiscriminadamente ao longo deste trabalho.

b) Classificação

A classificação consiste em descobrir uma função que mapeia um conjunto de registros

em um conjunto de rótulos categóricos pré-definidos, denominados classes

(GOLDSCHMIDT, 2003). Uma vez descoberta, a função pode ser aplicada a novos registros

de forma a prever a classe em que tais registros se enquadram. Por exemplo, a análise de

registros médicos, tais como pressão sanguínea, altura, sexo, taxa de glicose no sangue, etc,

de pacientes durante estudo de uma determinada doença, e a informação de que desenvolveu

ou não a doença em questão, pode permitir a identificação de uma função que, aplicada aos

valores observados de um novo paciente, classifique-o quanto à propensão em desenvolver a

doença ou não. Esta função pode assim ser aplicada em valores observados em novos

pacientes, auxiliando no diagnóstico médico e na prescrição de tratamentos.

Regras de associação podem ser utilizadas para realizar a classificação. Neste caso, por

exemplo, é feita a associação entre os valores medidos e a informação sobre a doença,

permitindo obter expressões como "70% das pessoas com pressão alta (acima de 12/8), têm

enxaqueca".

Redes Neurais, Algoritmos Genéticos, Lógica Indutiva são outros exemplos de

tecnologias que podem ser aplicadas na implementação da tarefa de classificação (MICHIE,

SPIEGELHALTER, TAYLOR, 1994).

c) Regressão

Compreende a busca por uma função que mapeie os registros de um banco de dados em

valores reais. Esta tarefa é similar à tarefa de classificação, sendo restrita apenas a atributos

numéricos. Como exemplo de aplicações de regressão, pode-se citar: predição da soma da

biomassa presente em uma floresta; estimativa da probabilidade de um paciente sobreviver,

dado o resultado de um conjunto de diagnósticos de exames; predição do risco de

determinados investimentos, definição do limite do cartão de crédito para cada cliente em um

banco; dentre outros.

Estatística, Redes Neurais, dentre outros paradigmas, oferecem ferramentas para

implementação da tarefa de regressão (MICHIE, SPIEGELHALTER, TAYLOR, 1994).

d) Agrupamento (Clusterização)

Utilizada para separar os registros de uma base de dados em clusters (subconjuntos), de

tal forma que os elementos de um cluster compartilhem de propriedades comuns que os

distingam de elementos em outros clusters. O objetivo nesta tarefa é maximizar similaridade

de dados do mesmo cluster (intracluster) e minimizar similaridade de dados de cluster

diferentes (intercluster). Diferente da tarefa de classificação, que tem rótulos pré-definidos, a

clusterização precisa automaticamente identificar os grupos de dados aos quais o usuário

deverá atribuir rótulos (FAYYAD, PIATETSKY-SHAPIRO, SMYTH, 1996). Por exemplo:

uma empresa do ramo de telecomunicações pode realizar um processo de clusterização de sua

base de clientes de forma obter grupos de clientes que compartilhem o mesmo perfil de

compra de serviços.

Na implementação desta tarefa podem ser utilizados algoritmos como K-Means, K-

Modes, K-Prototypes, K-Medoids e Kohonen (GOLDSCHMIDT, 2003).

e) Sumarização

Consiste em procurar identificar e indicar características comuns entre conjuntos de

dados (WEISS, INDURKHYA, 1998). Como exemplo considere um banco de dados com

informações sobre clientes que assinam um determinado tipo de revista semanal. A tarefa de

sumarização deve buscar por características que sejam comuns a boa parte dos clientes. Por

exemplo: são assinantes da revista X, homens na faixa etária de 25 a 40 anos, com nível

superior e que trabalham na área de finanças. Tal informação poderia ser utilizada pela equipe

de marketing da revista para direcionar a oferta venda para novos assinantes. É comum aplicar

a tarefa de sumarização a cada um dos agrupamentos obtidos pela tarefa de clusterização.

Lógica Indutiva, Algoritmos Genéticos e Estatística são alguns exemplos de tecnologias

que podem ser aplicadas na implementação da tarefa de sumarização.

f) Detecção de Desvios

Esta tarefa consiste em procurar identificar registros do banco de dados cujas

características não atendam aos padrões considerados normais no contexto (WEISS,

INDURKHYA, 1998). Registros com estas características são denominados são denominados

“outliers”. Como exemplo considere um banco de dados com informações sobre compras de

clientes no cartão de crédito. A tarefa de detecção de desvios busca por compras cujas

características divirjam do perfil normal de compra do dono do cartão, permitindo, por

exemplo, detectar possível furto ou clonagem do mesmo

A Estatística fornece recursos para a implementação desta tarefa.

2.2.4. TÉCNICAS E MÉTODOS

A seguir são apresentadas algumas técnicas que podem ser utilizadas para implementar as

tarefas de KDD descritas na seção 2.2.3.

a) Rede Neural Artificial (RNA)

Rede Neural Artificial (HAYKIN, 2001), ou simplesmente Rede Neural, é uma técnica

computacional utilizada para a construção de um modelo matemático de um sistema neural

biológico simplificado. Este modelo, numa etapa inicial, tenta identificar através de repetidas

iterações, os padrões existentes nos dados disponíveis, que pode assim ser utilizado em novos

dados submetidos ao modelo posteriormente em outra etapa, quando é realizada a

classificação propriamente dita. Pelas suas características, a etapa inicial é denominada etapa

de aprendizado ou de treinamento, onde o modelo "aprende" sobre os dados submetidos ao

modelo.

FIG. 2.7: Exemplo de RNA

Uma RNA possui, simplificadamente, um sistema de nós e conexões ponderadas

semelhantes, respectivamente, aos neurônios e sinapses observados nos sistema neurais

biológicos. A FIG. 2.7 apresenta um exemplo de arquitetura de uma RNA simples. Os

círculos representam os nós e as linhas representam as conexões. A camada que recebe os

dados é chamada camada de entrada e a camada que mostra o resultado é chamada camada

de saída. A camada interna, onde se localiza o processamento interno, é denominada camada

escondida ou oculta. Uma RNA pode conter uma ou várias camadas escondidas, de acordo

com a complexidade do problema.

A etapa de treinamento compreende encontrar após várias iterações os valores de pesos

associados às conexões. Os valores dos pesos de uma RNA treinada representam o

conhecimento abstraído pela rede a partir dos dados utilizados na etapa de treinamento.

b) Algoritmos Genéticos

Algoritmos genéticos (DAVIS, 1990) são uma família de modelos computacionais

inspirados na teoria da evolução natural e na reprodução genética. Por isso também são

conhecidos como algoritmos evolutivos. Estes algoritmos modelam uma solução para um

problema específico em uma estrutura de dados similar a um cromossomo e aplicam

operadores que recombinam estas estruturas preservando informações do mesmo modo como

ocorrem combinações de cromossomos na natureza.

A execução de um algoritmo genético inicia com uma população, geralmente randômica,

de cromossomos representando a população inicial. Estas estruturas são então avaliadas para

gerar oportunidades reprodutivas - representada por "gerações" da população - de forma que

cromossomos que representam uma solução "melhor" tenham maiores chances de se

reproduzirem do que os que representam soluções "piores". Esta avaliação é implementada

através de uma função que verifica a qualidade das soluções geradas em relação ao problema

estudado.

São exemplos de operações nos algoritmos genéticos: seleção (seleção de indivíduos para

reprodução), crossover (troca de informação genética na reprodução), mutação (alteração

aleatória de um ou mais genes de um cromossomo).

c) Lógica Nebulosa (Fuzzy)

Sistemas fuzzy são baseados na teoria da lógica fuzzy e dos conjuntos fuzzy, propostos por

Zadeh (ZADEH, 1965). Enquanto a lógica booleana define as variáveis como sendo

verdadeiras ou falsas, 1 ou 0, na lógica fuzzy, as variáveis são mapeadas em graus de

pertinência que variam entre 0 e 1.

FIG. 2.8: Exemplo de conjuntos Fuzzy

Conjuntos fuzzy são funções que mapeiam um valor x em algum grau de pertinência no

intervalo [0,1]. Por exemplo, a FIG. 2.8 mostra a representação da temperatura de um

ambiente, que pode então ser utilizada por um controlador (área onde a lógica fuzzy é muito

utilizada), onde a temperatura de 17

C é considerada FRIA com grau de pertinência 0,3 (30%)

e NORMAL com grau de pertinência 0,7 (70%). Vemos que esta é uma forma mais adequada

para interpretar uma temperatura - pela lógica booleana, só teríamos a informação se a

temperatura é FRIA ou NORMAL, não aceitando resultados intermediários.

2.3. ASSOCIAÇÃO E CLASSIFICAÇÃO

2.3.1. CONSIDERAÇÕES PRELIMINARES

Nesta dissertação trataremos somente das tarefas de classificação e de descoberta de

associação aplicadas a documentos XML. Por este motivo, estas duas tarefas de KDD são

apresentadas mais formalmente nesta seção. A descoberta de regras de associação

generalizada também é descrita, pois é uma tarefa bastante adequada para tratamento de

documentos XML, que apresentam estruturas hierárquicas.

Apresentaremos também o método de classificação baseado em regras de associação

utilizado neste trabalho.

2.3.2. DESCOBERTA DE REGRAS DE ASSOCIAÇÃO

Regras de associação podem ser descritas formalmente como em (AGRAWAL,

IMIELINSKI, SWAMI, 1993).

Seja o conjunto de literais Ι

ΙΙ

Ι={i

... i

}, denominado itens, Τ

ΤΤ

Τ uma combinação de itens,

onde Τ

ΤΤ

Τ⊆Ι

ΙΙ

Ι, denominada transação, e







um conjunto de transações, onde cada transação Τ

ΤΤ

possui um identificador único denominado TID. Dizemos que uma transação Τ

ΤΤ

Τ contém Χ

ΧΧ

Χ,

onde Χ

ΧΧ

Χ é um conjunto qualquer de itens de Ι

ΙΙ

Ι, se Χ

ΧΧ

Χ⊆Τ

ΤΤ

Τ.

Uma regra de associação é uma implicação da forma Χ

ΧΧ

ΧΥ

ΥΥ

Υ, onde Χ

ΧΧ

Χ⊂Ι

ΙΙ

Ι, Υ

ΥΥ

Υ⊂Ι

ΙΙ

Ι e Χ

ΧΧ

Χ∩Υ

ΥΥ

Υ=∅.

ΧΧ

Χ é denominado antecedente e Υ

ΥΥ

Υ consequente da regra. Quando Χ

ΧΧ

Χ possui k itens, dizemos que

k é o tamanho de Χ

ΧΧ

Χ, expresso por |Χ

ΧΧ

Χ| e que Χ

ΧΧ

Χ é um k-conjunto.

Dizemos que Ε

ΕΕ

Ε é uma extensão de Χ

ΧΧ

Χ se Ε

ΕΕ

Ε-Χ

ΧΧ

Χ≠∅.

O suporte s% da regra Χ

ΧΧ

ΧΥ

ΥΥ

Υ em







é o percentual de transações de







que contém Χ

ΧΧ

Χ∪Υ

ΥΥ

Υ,

representado por sup(Χ

ΧΧ

Χ∪Υ

ΥΥ

Υ)=s%.

A confiança c% da regra é o percentual de transações de







que contém Χ

ΧΧ

Χ e que também

contém Υ

ΥΥ

Υ, representado por conf(Χ

ΧΧ

Χ,Υ

ΥΥ

Υ)=c%, sendo conf(Χ

ΧΧ

Χ,Υ

ΥΥ

Υ)=sup(Χ

ΧΧ

Χ∪Υ

ΥΥ

Υ)/sup(Χ

ΧΧ

Χ).

A regra Χ

ΧΧ

ΧΑ

ΑΑ

Α não necessariamente significa que Χ+Υ

Χ+ΥΧ+Υ

Χ+Υ

Α

ΑΑ

Α também seja verdade, pois

Υ Υ

Υ pode não ter suporte mínimo. Do mesmo modo, as regras Χ

ΧΧ

ΧΥ

ΥΥ

Υ e Υ

ΥΥ

ΥΖ

ΖΖ

Ζ não significam que

necessariamente Χ

ΧΧ

ΧΖ

ΖΖ

Ζ seja verdade, porque Ζ

ΖΖ

Ζ pode não possuir confiança mínima.

Por exemplo, considere o seguinte conjunto de dados







com 4 transações, onde Ι

ΙΙ

Ι={a b c

d e} (AGRAWAL, SRIKANT, 1994):

ΧΧ

Χ∪Υ

ΥΥ

Υ, sendo Χ

ΧΧ

Χ∩Υ

ΥΥ

Υ=∅

veremos adiante que estes dados não estão normalizados.

TID Itens

a b c d

b c e

a b c e

b e

Assumimos que itens em cada transação estão em ordem lexicográfica, isto é, se Τ

ΤΤ

Τ={t

... t

}, t

∈Ι

ΙΙ

Ι, então t

≤t

≤...≤t

A regra {b e}{c} tem suporte 50%, pois duas transações contêm {b c e} e, destas,

somente duas contém {c} e confiança 66.7% (2/3), pois três transações contêm {b e}. Se

desejarmos obter as regras de associação com suporte mínimo 40% e confiança mínima 60%,

esta regra seria considerada no resultado.

O problema de descoberta de regras de associação compreende obter regras de associação

ΧΧ

ΧΥ

ΥΥ

Υ cujos valores do suporte e confiança sejam iguais ou superiores, respectivamente, a

determinados valores minsup%, denominado suporte mínimo, e minconf%, denominado

confiança mínima. Isto é, obter regras da forma Χ

ΧΧ

ΧΥ

ΥΥ

Υ onde sup(Χ

ΧΧ

Χ∪Υ

ΥΥ

Υ)≥minsup% e

conf(Χ

ΧΧ

Χ∪Υ

ΥΥ

Υ)≥minconf%. Este problema pode ser estendido: definir os itens que devem

aparecer somente como antecedente e/ou consequente

Para obter as regras desejadas conhecendo-se minsup% e minconf%, o problema pode

ser decomposto em 2 subproblemas:

• definir os conjuntos de itens freqüentes: gerar todos conjuntos de itens e calcular o

suporte de cada um – eliminar os conjuntos cujo valor do suporte seja inferior ao

minsup%;

• definir as regras válidas: gerar as regras de associação com os conjuntos obtidos e

calcular a confiança de cada uma – eliminar as regras cujo valor da confiança seja

inferior à minconf%.

Para gerar todos os conjuntos de dados, fazemos: gerar todos os k-(sub)conjuntos de Ι

ΙΙ

Ι,

2≤k≤n, onde n é o número de itens em Ι

ΙΙ

Ι – estes conjuntos são denominados candidatos;

funciona como restrição das regras geradas, limitando assim o conjunto de soluções possíveis; útil

quando se conhece o problema estudado, pois evita a geração de regras que, embora corretas, não sejam

necessárias.

avaliar o suporte de cada conjunto candidato; eliminar os conjuntos cujo valor do suporte seja

menor que minsup% - estes conjuntos são denominados frequent itemsets.

Este é a solução proposta inicialmente por (AGRAWAL, IMIELINSKI, SWAMI, 1993),

onde se observa a grande quantidade de passos devido ao número de conjuntos gerados,

muitos sem necessidade. A seguinte propriedade se aplica aos resultados: se

sup(Χ

ΧΧ

Χ)<minsup%, então sup(Υ

ΥΥ

Υ)<minsup% para todo Υ

ΥΥ

Υ extensão de Χ

ΧΧ

Χ. Por isso temos que

não é necessário gerar as extensões Υ

ΥΥ

Υ de um conjunto Χ

ΧΧ

Χ onde sup(Χ

ΧΧ

Χ)<minsup%, pois sempre

temos sup(Υ

ΥΥ

Υ)<minsup%. Esta propriedade é utilizada por vários algoritmos, sendo utilizado

inicialmente pelo algoritmo Apriori (AGRAWAL, SRIKANT, 1994), que passou a ser um

algoritmo referência na descoberta de associações

O cálculo do suporte então pode ser feito com várias iterações como descrito a seguir:

• para k=1

• gerar o conjunto de itens (1-conjunto);

• avaliar o suporte de cada item (1-conjunto);

• eliminar os itens com suporte inferior ao suporte mínimo;

• para k=2

• gerar todos os 2-conjuntos a partir dos itens obtidos no passo anterior;

• avaliar o suporte de cada item dos novos 2-conjuntos gerados;

• eliminar os 2-conjuntos com suporte inferior à minsup%;

• para k≥3 (caso geral)

• repetir

• gerar todos os k-conjuntos a partir dos itens nos (k-1) conjuntos obtidos no

passo anterior

• avaliar o suporte de cada item dos novos k-conjuntos gerados;

• eliminar os k-conjuntos com suporte inferior à minsup%;

• até que nenhum novo conjunto seja gerado.

o algoritmo Apriori é determinístico, ou seja, sempre que aplicado a um mesmo conjunto de dados, com

os mesmos valores de suporte e confiança mínimos, produz os mesmos resultados.

A geração dos k-conjuntos é feita a partir pela inclusão dos itens dos 1-conjuntos (itens

simples com suporte ≥ minsup%) aos (k-1)-conjuntos.

Por exemplo: considere o banco de dados apresentado anteriormente. Desejamos gerar as

regras de associação onde minsup%=60% e minconf%=80%. Temos Ι

ΙΙ

Ι={a b c d e};

sup(a)=50% (2/4), sup(b)=100% (4/4), suc(c)=75% (3/4), sup(d)=25% (1/4) e sup(e)=75%

(3/4); eliminamos {a} e {d}, restando {a b c e}; geramos os 2-conjuntos com estes itens,

obtendo {(b c) (b e) (c e)}, que têm suporte, respectivamente 75%, 75% e 50%. {b c} e {b e}

atendem ao suporte mínimo, portanto devemos eliminar o conjunto {c e} na próxima iteração.

Geramos então os 3-conjuntos, adicionando os itens com suporte mínimo a este conjunto:

{(a c) (b c e) (a e)} que têm suporte 50%, que é inferior ao suporte mínimo. Como nenhum

novo conjunto foi gerado, o processo é interrompido, obtendo então somente dois conjuntos

que atendem ao suporte mínimo: {b c} e {b e}.

As seguintes regras são então geradas, com respectivos valores de confiança:

• bc, conf(b,c)=sup({b c}/sup({b})=75%/100%=75% - descartada

• cb, conf(c,b)=sup({b c}/sup({c})=75%/75%=100%

• be, conf(b,e)=sup({b e}/sup({b})=75%/75%=75% - descartada

• eb, conf(b,e)=sup({b e}/sup({e})=75%/75%=100%

Portanto, as regras obtidas, de acordo com os parâmetros fornecidos, são cb e eb. Se

tivermos a restrição “somente b, c e d podem ser antecedente”, então a regra eb seria

descartada, isto é, o resultado compreenderia somente a regra cb.

Observa-se que neste exemplo os dados não estão normalizados

. Na prática os

algoritmos para obtenção de regras de associação trabalham com os dados normalizados, com

o TID funcionando com identificador dos itens da mesma transação, num formato conhecido

como basket (AGRAWAL, IMIELINSKI, SWAMI, 1993) (AGRAWAL, SRIKANT, 1994).

Por exemplo, os dados do exemplo no formato basket seria organizado na seguinte relação {(1

a) (1 b) (1 c) (1 d) (2 b) (2 c) (2 e) (3 a) (3 b) (3 c) (3 e) (4 b) (4 e)}, ou seja,

Neste contexto, o termo normalização refere-se à normalização funcional de dados e não à normalização

de dados em escalas.

TID Item

A geração de regras de associação se baseia fortemente no conceito de contagem e se

utiliza da geração de conjuntos candidatos para obter os resultados desejados, o que

normalmente envolve um grande número de iterações, sendo então a preocupação com

desempenho comum entre todos eles.

Atualmente existem algoritmos otimizados que obtém os resultados desejados sem a

geração de conjuntos candidatos (HAN, PEI, YIN, 2000) (CHEUNG, ZAIANE, 2003). Este é

o caso do método proposto neste trabalho (ver seção 4.3).

2.3.3. DESCOBERTA DE REGRAS DE ASSOCIAÇÃO GENERALIZADAS

Quando os dados apresentam uma taxonomia, as regras de associação podem ser

estendidas de modo a considerar a classificação dos itens de dados de acordo com esta

taxonomia. São chamadas Regras de Associação Generalizadas (SRIKANT, AGRAWAL,

1995).

Um exemplo que ilustra bem a importância desta técnica pode ser obtido na área de

marketing: o registro de vendas de produtos é feito com base em suas características

específicas, como fabricante, modelo, peso, cor, etc. Portanto, itens semelhantes, mas, por

exemplo, de fabricantes diferentes, não são tratados adequadamente pelas técnicas de regras

de associação. No entanto, ao identificar a semelhança entre os produtos, sempre presente

numa taxonomia, técnicas de regras de associação generalizada podem então considerar as

vendas de produtos de uma mesma "família de produtos"!

Formalmente, precisamos então estender o modelo apresentado na seção 2.3.2 (Regras de

Associação), adicionando o grafo direcionado acíclico Γ

ΓΓ

Γ sobre os literais do conjunto Ι

ΙΙ

Ι={i

... i

}, onde as arestas de Γ

ΓΓ

Γ representam um relacionamento entre os literais e Γ

ΓΓ

Γ representa

uma conjunto de taxonomias.

Se Γ

ΓΓ

Γ contém uma aresta de i

para i

, representada por i

→i

, i

∈Γ

ΓΓ

Γ e i

,∈Γ

ΓΓ

Γ, dizemos i

é pai

de i

e que i

é filho de i

. Considerando Ε

ΕΕ

Ε o conjunto de itens de Ι

ΙΙ

Ι que não têm filhos

, Ε

ΕΕ

Ε≠

≠≠

≠∅

∅∅

∅, temos

ΡΡ

Ρ=Ι

ΙΙ

Ι−Ε

ΕΕ

Ε, Ρ

ΡΡ

Ρ≠∅

∅∅

∅, o conjunto de itens que são pais de algum item em Ι

ΙΙ

Ι.

Um caminho entre dois itens i

e i

, i

∈Γ

ΓΓ

Γ e i

,∈Γ

ΓΓ

Γ, é formado pelas arestas existentes que unem

e i

. Dizemos que i

(início do caminho) atinge ou alcança i

(fim do caminho) e que i

ancestral

de i

e, de modo análogo, i

é descendente de i

. Consideramos que o ancestral de item é

uma generalização daquele item.

Temos da seção 2.3.2 que







é um conjunto de transações Τ

ΤΤ

Τ⊆Ι

ΙΙ

Ι. No entanto, observamos que

somente os itens de Ε

ΕΕ

Ε⊂Ι

ΙΙ

Ι formam as transações Τ

ΤΤ

Τ. Por isso, na verdade, temos que







é um conjunto

de transações Τ

ΤΤ

Τ⊆Ε

ΕΕ

Uma regra de associação generalizada é uma implicação da forma Χ

ΧΧ

ΧΥ

ΥΥ

Υ, onde Χ

ΧΧ

Χ⊂Ι

ΙΙ

Ι, Υ

ΥΥ

Υ⊂Ι

ΙΙ

Ι,

ΧΧ

Χ∩Υ

ΥΥ

Υ=∅, e nenhum item i

∈Υ

ΥΥ

Υ é um ancestral de algum item i

∈Χ

ΧΧ

Χ. Como algum item de Χ

ΧΧ

Χ e

Y pode ser generalização (ancestral), as regras podem conter itens que não existem em







sendo esta a principal diferença em relação à regras de associação (seção 2.3.2).

O suporte s% da regra Χ

ΧΧ

ΧΥ

ΥΥ

Υ em







é o percentual de transações de







que contém Χ

ΧΧ

Χ∪Υ

ΥΥ

Υ,

representado por sup(Χ

ΧΧ

Χ∪Υ

ΥΥ

Υ)=s%. A confiança c% da regra é o percentual de transações de







que contém Χ

ΧΧ

Χ e que também contém Υ

ΥΥ

Υ, representado por conf(Χ

ΧΧ

Χ,Υ

ΥΥ

Υ)=c%, sendo

conf(Χ

ΧΧ

Χ,Υ

ΥΥ

Υ)=sup(Χ

ΧΧ

Χ∪Υ

ΥΥ

Υ)/sup(Χ

ΧΧ

Χ).

A restrição de que nenhum item i

∈Υ

ΥΥ

Υ é ancestral de algum item i

∈Χ

ΧΧ

Χ impede que

tenhamos regras redundantes e, por isso, com confiança c%=100%.

nós folha.

um item não pode ser ancestral (nem descendente) dele mesmo, pois o grafo é acíclico.

consideramos que esta restrição representa mais fielmente a realidade.

FIG. 2.9: Taxonomia dos itens do exemplo

Por exemplo, considere o seguinte conjunto de dados







com 6 transações

, onde Ι

ΙΙ

Ι={a b c

d e f g h} e Γ

ΓΓ

Γ o grafo onde f→a, g→f, g→c, h→d e h→e (representados na FIG. 2.9)

(SRIKANT, AGRAWAL, 1995):

TID Item

a e

b e

Cada item em







de cada transação em Τ

ΤΤ

Τ pode ser substituído pela sua generalização com

base na taxonomia definida pelo grafo Γ

ΓΓ

Γ, onde temos então:

TID

Itens

c ou g

a e ou a h

ou f e ou g e

ou f h ou g h

b e ou b h

ou f e ou g e

ou f h ou g h

d ou h

a ou f ou g

Temos que {a}{e} é um exemplo de regra obtida a partir destes dados, com suporte

16,7% (1/6), pois somente uma transação contém {a e}. Como f e g são ancestrais de a, e h é

ancestral de e, a transação {a e} tem as seguintes generalizações: {f e},{g e},{f h} e {g h}. Podemos

então gerar as regras {f}{e} e {g}{e}. A regra {f}{e}, por exemplo, tem suporte 33,3%

(2/6), pois o conjunto {f e} ocorre em duas das seis transações (generalizações) do exemplo.

Podemos observar que a regra {f}{h}, que também tem suporte 33,3% (2/6), contém

elementos que não estão em







, como afirmado anteriormente. A regra {f}{a} tem suporte

observe que somente os itens sem filhos participam das transações.

16,7% (1/6), mas podemos observar que não tem efeito prático, pois é redundante (confiança

= 100%). Por isso a regra não é considerada, como também visto anteriormente.

O problema de descoberta de regras de associação generalizada é então uma extensão do

problema da descoberta de regras de associação e compreende obter regras de associação

ΧΧ

ΧΥ

ΥΥ

Υ que atendam valores mínimos de suporte e confiança, mas onde os elementos de Χ

ΧΧ

Χ e Υ

ΥΥ

podem ser generalizações de outros elementos de acordo com uma taxonomia definida através

de relacionamentos e representados por um grafo direcionado acíclico.

Para obter as regras desejadas devemos proceder de modo semelhante ao apresentado na

seção 2.3.2. Como o conjunto Ι

ΙΙ

Ι contém generalizações dos elementos das transações Τ

ΤΤ

Τ (em







), ao gerar todos os conjuntos de itens - e calcular o suporte de cada um - poderemos gerar

grupos que contenham algum item que não esteja presente em Τ

ΤΤ

Τ.

2.3.4. CLASSIFICAÇÃO

A classificação pode ser definida formalmente como descrito a seguir (GOLDSCHMIDT,

2003).

A classificação é um caso particular de inferência indutiva, ou simplesmente indução, que

procura uma função h(x), onde x é um vetor de entrada n-dimensional, que aproxime uma

função f(x) desconhecida, onde são conhecidos apenas alguns pares ordenados (x, f(x)). A

função h é denominada hipótese ou modelo de f. Nos casos em que a imagem de f é formada

por rótulos de classes, a tarefa de inferência indutiva é denominada classificação e toda

hipótese h é denominada classificador.

A identificação da função h consiste do processo de busca no espaço de hipóteses H pela

função que mais se aproxime da função f desconhecida, num processo denominado

aprendizado. Todo algoritmo que possa ser utilizado no processo de aprendizado é

denominado algoritmo de aprendizado. O conjunto de todas as hipóteses que podem ser

obtidas a partir de um algoritmo de aprendizado L é representado por H

e cada hipótese

pertencente à H

é representada por h

O conjunto de pares (x,f(x)) utilizado para identificar a função h é denominado conjunto

de treinamento, enquanto que o conjunto de pares (x,f(x)) utilizado para avaliar a acurácia de

h é denominada conjunto de testes.

A qualidade ou precisão da função h em mapear corretamente cada vetor de entradas x

em f(x) determina a sua acurácia. Uma medida da acurácia de h pode ser obtida como:

acurácia = 1 – taxa de erro

onde taxa de erro compreende o percentual de erros de predição em relação ao total de pares

ordenados da entrada, isto é, dado o vetor x, temos e⊆

⊆⊆

⊆x, onde f(e

)≠

≠≠

≠h(e

), e

∈

∈∈

∈e, então:

taxa de erro = |e|

/ |x|

ou seja, a relação entre a quantidade de vetores que originam um resultado da aplicação de h

diferente do valor observado.

x F(x) h(x)

= a 1 1

= b c 2 2

= a d 1 1

= a b 2 1

= b c d 2 2

FIG. 2.10: Dados para classificação

Por exemplo, considere o conjunto de dados da FIG. 2.10.

Observamos que o conjunto x possui 5 (cinco) elementos, sendo que somente para um de

seus elementos x

, os valores de f e h aplicadas a este elemento são diferentes. Então a taxa

de erro de h é 1/5, ou 20%, e, consequentemente, a acurácia de h é de 80%.

A taxa de erro pode ser calculada tanto para o conjunto de treinamento quanto para o

conjunto de testes de modo a definir se o modelo obtido (função h) atende a algum requisito

pré-estabelecido. Por exemplo, se definirmos que o valor máximo desejado para a taxa de erro

é de 10%, a função h vista anteriormente não seria aceita, pois a taxa de erro é igual a 20%.

notação: |e| representa a quantidade de elementos do conjunto e.

2.3.5. CLASSIFICAÇÃO BASEADA EM REGRAS DE ASSOCIAÇÃO

Conforme comentado anteriormente, existem diversos métodos para a construção de

modelos de classificação. Por exemplo, Redes Neurais, Lógica Indutiva e Algoritmos

Genéticos, dentre outros.

No escopo desta dissertação, optamos por utilizar o método de classificação por regras de

associação, por ser um método adequado à estrutura de documentos XML e por isso utilizado

em trabalhos semelhantes (ZAKI, AGGARRWAL, 2003). Este método encontra-se descrito

nesta seção.

Regras de associação podem ser utilizadas de modo a gerar classificadores como descrito

na seção 2.3.4 (LIU, HSU, MA, 1998), sendo esta técnica empregada na abstração/produção

de classificadores a partir de documentos XML (ZAKI, AGGARRWAL, 2003).

Um classificador gerado por este método consiste de regras de associação no formato

xclasse obtidas sobre um conjunto de treinamento, onde x é um vetor de entrada n-

dimensional obtido com as técnicas de geração de regras de associação, onde as regras têm as

seguintes restrições: os antecedentes das regras são os elementos de x, enquanto que os

consequentes são qualquer uma das classes possíveis. As regras obtidas são então ordenadas

de modo a determinar a ordem de prioridade de sua aplicação sobre o conjunto de teste. Se

não for possível aplicar nenhuma regra, então é assumida uma classe default (padrão),

geralmente a classe mais frequente. Portanto esta fase compreende obter as regras de

associação e definir a classe default que serão utilizadas para a classificação propriamente

dita.

A classificação consiste em encontrar a primeira regra no conjunto de regras de

associação geradas que consegue classificar x é então aplicada.

Por exemplo, considere o classificador composto das seguintes regras de associação (na

ordem), sendo a classe default = 2:

• regra 1: b,c2

• regra 2: a1

veremos adiante que a ordenação das regras é um processo importante na definição do classificador.

• regra 3: c,d2

Estas regras podem ser aplicadas sobre os dados da FIG. 2.10. Por exemplo, a regra 1 não

pode ser aplicada sobre x

. No entanto a regra 2 pode ser aplicada sobre este conjunto,

resultando na classe "1". A regra 1 pode ser aplicada sobre x

, resultando a classe "2", e

assim por diante. Para os dados deste exemplo, a regra 3 não é utilizada, pois as regras

anteriores são aplicadas antes dela ser avaliada. Observamos ainda que, neste exemplo, todos

os elementos são classificados por uma regra, não sendo necessária a aplicação da classe

default. Vemos que estas regras formam um classificador semelhante ao utilizado na FIG.

2.10 (h(x)).

3. TRABALHOS RELACIONADOS

3.1. VISÃO GERAL

XML é um formato que vem motivando os estudos de dados semi-estruturados (SUCIU,

1998), que podem ser formalmente descritos através de OEM (Object Exchange Model)

proposto inicialmente por (PAPAKONSTANTINOU, GARCIA-MOLINA, WIDOM, 1995).

Este modelo é a base para a descrição do modelo que define a XML (BEECH, MALHOTRA,

RYS, 1999).

Neste trabalho estaremos nos limitando somente às tarefas de classificação e associação

aplicadas em documentos XML. Estas tarefas foram definidas na seção 2.2.3. Por este motivo

esta seção somente apresentará trabalhos recentes que consideram estas duas tarefas,

destacando os estudos que aplicam estas técnicas em documentos XML.

Inicialmente são apresentados estudos sobre mineração de regras de associação aplicadas

a bancos de dados convencionais, pois são responsáveis pelos principais algoritmos existentes

atualmente. Em seguidas são descritos estudos sobre mineração de regras associação em

documentos XML, que buscam explorar as características deste tipo de documento.

Não faremos um levantamento sobre a tarefa de classificação em particular, pois os

estudos que abordam classificação em documentos XML consideram que esta técnica pode ser

obtida pela extensão da aplicação de regras de associação em documentos XML, como é

descrito adiante.

Veremos que a maioria dos estudos sobre classificação e associação é aplicada em banco

de dados convencionais (relacionais) e que por isso não consideram as principais

características que diferenciam estes tipos de dados dos existentes em documentos XML, ou

seja:

 hierarquia dos dados em documentos XML, que podem armazenar dados semi-

estruturados;

 os dados não podem ser acessados diretamente em documentos XML, ao contrário do

que ocorrem em bancos de dados convencionais, que permite a implementação de

estruturas auxiliares para otimização do acesso aos dados, p.e., índices.

O que se verifica, no entanto, em estudos envolvendo a aplicação de tarefas de

classificação e associação em documentos XML, é a transformação dos dados existentes nos

documentos XML em estruturas adequadas que podem ser manipuladas por algoritmos

tradicionais disponíveis para bancos de dados relacionais. No entanto, esta transformação

pode levar à perda de algumas características importantes dos dados existentes nos

documentos XML, sobretudo referente à hierarquia entre os dados.

Este estudo, ao contrário, desenvolve técnicas adequadas à manipulação direta de

documentos XML, que assim podem manter as características existentes em seus dados.

(ZAKI, 1999) apresenta um bom resumo sobre algoritmos de processamento paralelo

para geração de regras de associação, que buscam aproveitar a grande capacidade de

processamento destes algoritmos, e que normalmente requerem grande disponibilidade de

recursos computacionais - (SOUZA, 1998) apresenta o uso de banco de dados paralelo na

mineração de dados - , enquanto (OTEY et ali, 2003) descreve os principais conceitos

envolvidos na mineração de regras de associação em bases de dados distribuídas

3.2. DESCOBERTA DE REGRAS DE ASSOCIAÇÃO

O conceito de descoberta de regras de associação foi introduzido em (AGRAWAL,

IMIELINSKI, SWAMI, 1993), que propõe o algoritmo AIS

para geração de regras de

associação em bases de dados relacionais. Este estudo já destacava a importância de restringir

os itens antecedentes e consequentes nas regras de associação geradas, com grande impacto

nas estratégias de marketing, principal área de aplicação desta técnica.

processamento paralelo e bases de dados distribuídas não são consideradas no escopo deste trabalho.

iniciais dos autores (Agrawal, Imielinski e Swami).

O algoritmo Apriori, extensão do algoritmo AIS, foi proposto em (AGRAWAL,

SRIKANT, 1994) e é utilizado como referência em vários estudos recentes, que apresentam

algumas melhorias. O Apriori se baseia na extração de conjuntos de itens frequentes

gerados

a partir de conjuntos candidatos de itens do conjunto de dados da aplicação. Conjunto de itens

frequentes é a denominação dada ao conjunto de itens cujo suporte é maior que um valor

definido pela aplicação, o suporte mínimo

. Conjunto candidato de itens compreende o

conjunto que pode ser formado pela combinação de todos os itens que formam as transações

da base de dados e cujo valor do suporte ainda não foi calculado. O grande número de

conjuntos candidatos que podem ser gerados é reduzido pela seguinte propriedade (anti-

monotocidade do suporte): se algum subconjunto de um conjunto candidato não é um

conjunto frequente, então o conjunto candidato não é um conjunto frequente.

Novos algoritmos surgiram como evolução do Apriori. O algoritmo Partition

(SAVASERE, OMIECINSKI, NAVATHE, 1995) otimiza o acesso a disco ao realizar a

partição da base de dados original em blocos menores cujo tamanho permita que sejam

processados diretamente na memória. Deste modo a base de dados é lida (varredura) somente

duas vezes durante o processamento. O algoritmo DHP (PARK, CHEN, YU, 1995)

implementa técnicas de hash para reduzir significativamente a quantidade de conjuntos

candidatos com dois itens e assim diminuir a quantidade de conjuntos candidatos gerados com

mais de dois itens, o que melhora o desempenho do algoritmo como um todo. (CHEN,

HAAS, SCHEUERMANN, 2002) propõe a extração de uma amostragem

da base de dados

original, com tamanho significativamente menor, sobre a qual são geradas as regras de

associação. O algoritmo DIC particiona a base de dados em blocos com tamanho adequado

para que caibam na memória principal. A otimização ocorre no modo como os blocos são

processados, quando os conjuntos de itens frequentes de um bloco são utilizados para

encontrar os conjuntos de itens frequentes com mais itens no outro conjunto.

A geração de regras de associação generalizada foi proposta inicialmente em (SRIKANT,

AGRAWAL, 1995), que apresenta os algoritmos Basic, Cumulate e EstMerge, e em (HAN,

FU, 1995), onde é apresentada como descoberta de regras de associação multi-nível. Todos os

frequent itemsets.

ver seção 2.3.2.

mantendo as características estatísticas da base de dados original.

algoritmos consideram a existência de uma base de dados e de uma taxonomia sobre estes

dados definida externamente. O algoritmo Basic adiciona à transação todos os ancestrais dos

itens presentes na transação e considera esta nova base de dados modificada para gerar as

regras de associação. Os algoritmos Cumulate e EstMerge otimizam o algoritmo Basic,

diminuindo o esforço na geração de conjunto de itens candidatos e evitando a geração de

regras pouco significativas

, o mesmo ocorrendo com os algoritmos ML_T2L1, ML_T1La,

ML_TML1 e ML_T2LA

propostos em (HAN, FU, 1995), e o algoritmo Prutax em (HIPP,

MYKA, WIRT, GÜNTZER, 1998).

Alguns trabalhos realizam avaliação estatística para determinar regras significativas

(ZHANG, PADMANABHAN, TUZHILIN, 2004).

A determinação de conjuntos de itens candidatos normalmente envolve um grande

número de iterações sobre a base de dados, sendo que esta característica é comum aos

algoritmos vistos, tanto de regras de associação, quanto de regras de associação generalizada.

Os trabalhos (HAN, PEI, YIN, 2000) e (CHEUNG, ZAIANE, 2003) propõem novos tipos

de algoritmos de regras de associação sem a geração de conjuntos de itens candidatos. Ambos

algoritmos propõem a implementação de uma estrutura em árvore com os itens presentes e

que é criada durante uma única passagem sobre a base de dados. Ao final, a árvore criada

contém informações suficientes para determinar os conjuntos de itens frequentes.

Esta característica também está presente no algoritmo apresentado neste trabalho, que se

mostra bastante vantajosa quando se trata de processamento de dados com estrutura

heterogênea como é o caso de documentos XML.

regras que não agregam, ou agregam pouca, informação à demais regras, sendo muitas vezes

redundantes.

regra de associação generalizada também é conhecida como regra de associação multi-nível, multi-level

association em inglês, daí os algoritmos serem preficados pelas iniciais "ML" (multi-level).

3.3. DESCOBERTA DE REGRAS DE ASSOCIAÇÃO EM DOCUMENTOS XML

Alguns trabalhos recentes sobre mineração de regras de associação aplicadas em

documentos XML (BRAGA, CAMPI, KLEMETTINEN, LANZI, 2002) (BRAGA, CAMPI,

STEFANO, KLEMETTINEN, LANZI, 2002a) (DING, RICORDS, LUMPKIN, 2003)

descrevem na verdade a implementação de um novo comando, MINE RULE, para a

linguagem de consulta XQuery [15], estendendo assim a sua utilização para aplicações de

descoberta de conhecimento - mais especificamente, geração de regras de associação - em

documentos XML.

Estes trabalhos implementam um pré-processamento implícito onde os dados de entrada

(documentos XML) são inicialmente convertidos para o formato basket (ver seção 2.3.2), o

que permite então ser processado por algoritmos tradicionais de regras de associação.

O comando MINE RULE necessita da definição dos seguintes parâmetros:

 ROOT: expressão XPath que define a raiz de um trecho (sub-árvore) na estrutura do

documento XML associada aos dados que serão analisados para a geração das regras de

associação;

 BODY: expressão XPath que define o elemento da estrutura que aparecerá como

antecedente nas regras de associação geradas;

 HEAD: expressão XPath que define o elemento da estrutura que aparecerá como

consequente nas regras de associação geradas;

 SUPPORT: valor do suporte mínimo;

 CONFIDENCE: valor da confiança mínima.

 A definição de ROOT tem uma importância fundamental na implementação ao definir

o escopo de atuação do algoritmo, pois define de modo inequívoco quais dados serão

processados pelo algoritmo. Este conceito também é utilizado pelo algoritmo

implementado neste trabalho (ver seção 4.3).

Algumas características do XQuery são mantidas neste trabalho, como: a) possibilidade

de definição de restrições com base nos dados encontrados (semelhante, por exemplo, à

cláusula WHERE do comando SELECT da linguagem de consulta SQL de banco de dados

relacionais); e b) cláusulas de agrupamento.

Em (WAN, DOBBIE, 2003), ao contrário dos demais trabalhos, é apresentada uma

solução para obtenção de regra de associação usando os recursos disponíveis atualmente em

XQuery, implementada através de rotinas internas da própria XQuery.

Embora existam trabalhos envolvendo a geração de regras de associação sem geração de

conjuntos candidatos a partir de bancos de dados relacionais (HAN, PEI, YIN, 2000)

(CHEUNG, ZAIANE, 2003), não foi possível observar nenhum trabalho desta natureza

aplicado a documentos XML.

3.4. CLASSIFICAÇÃO EM DOCUMENTOS XML

A classificação, importante tarefa de KDD (ver seção 2.2.3) pode ser obtida aplicando

diferentes técnicas, como, por exemplo, redes neurais, análise discriminante e árvores de

decisão (GOLDSCHMIDT, 2003).

A descoberta de regras de associação é uma abordagem que pode ser utilizada para

implementar a tarefa de classificação (ALI, MANGANARIS, SRIKANT, 1997) (DONG,

ZHANG, WONG, LI, 1999) (LI, HAN, PEI, 2001) (LIU, HSU, MA, 1998) (WANG, ZHOU,

HE, 2000), podendo ser empregada também na geração de classificadores a partir de

documentos XML (ZAKI, AGGARRWAL, 2003).

O algoritmo CMAR (LI, HAN, PEI, 2001) se destaca, pois usa o método de regras de

associação sem geração de candidatos (FP-tree (HAN, PEI, YIN, 2000)) e pode ser utilizado

para classificação em dados com estrutura hierárquica, sendo por isso adequado para

aplicação em documentos XML.

4. ABORDAGENS ADOTADAS

4.1. CONSIDERAÇÕES GERAIS

4.1.1. SIMPLIFICAÇÃO DO MODELO FORMAL DE DOCUMENTOS XML

Vimos na seção 2.1.4 o modelo formal de documentos XML. Neste trabalho faremos uma

redução do modelo com o único objetivo de simplificar a implementação e, como veremos,

sem prejuízo para a aplicação dos métodos de mineração de dados propostos em qualquer tipo

de documento XML (de acordo com o modelo formal completo).

Um documento XML pode ser escrito de diferentes formas, sem perda de informação

representada pelo documento. Inicialmente vamos considerar a situação onde os atributos

podem ser reescritos como sub-elementos do elemento onde foram inicialmente declarados

A FIG. 4.1(a) mostra um exemplo de um trecho de documento XML onde aparece um atributo

declarado em destaque, enquanto que a FIG. 4.1(b) mostra o mesmo trecho com o mesmo

atributo escrito agora como um novo elemento.

A alteração da representação do atributo como elemento causa uma pequena modificação

quanto ao acesso à informação. Por exemplo, na FIG. 4.1(a) o caminho do atributo é

"bd/filme@id", enquanto que a sua nova representação observada na FIG. 4.1(b) é

"bd/filme/id". Isto ocorre porque o vértice que representa o atributo originalmente pertencia

ao conjunto A e na nova representação pertence ao conjunto E.

Vamos agora considerar a representação de referências (arestas R), que partem de um

vértice para outro, onde este último é a raiz de uma sub-árvore. Deste modo, podemos

considerar que as referências ligam um vértice a uma ou mais sub-árvores, dando acesso aos

com as alterações de forma propostas, há evidente perda de semântica nos dados representados no

documento XML; no entanto, para este trabalho, só é considerada a sintaxe dos documentos.

vértices que a formam. O grafo poderia ser reescrito com a cópia das sub-árvores

referenciadas, o que, no entanto, acarretaria redundância dos dados. A FIG. 4.2(a) mostra o

trecho de documento XML com uma referência, enquanto que a FIG. 4.2(b) mostra o mesmo

documento reescrito com a substituição da referência pela cópia do trecho referenciado

associado ao vértice de onde parte a referência

...

<elenco idrefs="a1

a2"/>

</filme>

...

(a.1) atributo

...

<filme>

<elenco idrefs="a1

a2"/>

</filme>

...

(b.1) elemento

(a.2) grafo

(b.2) grafo

FIG. 4.1: Alteração de atributo

A alteração da representação da referência com a cópia da sub-árvore referenciada

também causa uma modificação quanto à forma de acesso à informação. Por exemplo, na

FIG. 4.2(a) o caminho do título do filme referenciado é "bd/ator/atuou→filme/titulo" e a sua

nova representação observada na FIG. 4.2(b) é "bd/ator/atuou/filme/titulo". Isto ocorre porque

o vértice que representa a referência pertencia a R e é substituído pela sub-árvore

referenciada, criando assim novos itens em A e E.

como podem existir novas referências nos trechos referenciados podendo levar a um ciclo infinito, é

necessário definir quando parar a substituição; este problema existe no documento do exemplo (ver FIG. 2.5),

onde existem referências para indicar os filmes em que um ator atuou e para indicar os atores que atuaram num

filme; este problema de referência infinita não é considerado neste trabalho.

...

<elenco idrefs="a1

a2"/>

</filme>

...

</ator>

...

(a.1) referência

...

</filme>

...

<atuou>

<filme>

<elenco idrefs="a1

a2"/>

</filme>

</atuou>

</ator>

...

(b.1) elemento

(a.2) grafo

(b.2) grafo

FIG. 4.2: Alteração de referência

Portanto, como queremos demonstrar, as arestas A e R podem ser removidas sem perda

de informação, ou seja, o modelo completo será simplificado para o grafo (árvore)

G=(V,E,O), onde V, E, O são definidos como descrito na seção 2.1.4.

A remoção das arestas e∈R elimina a possibilidade de ciclos no grafo, tornando-o um

grafo direcionado acíclico, isto é, uma árvore.

4.1.2. REPRESENTAÇÃO DE ÁRVORE

Uma árvore pode ser representada por dados hierarquizados em níveis adequadamente

numerados, onde o vértice acessado pela raiz (correspondente ao elemento mais externo do

documento XML) não é numerado e cada vértice recebe uma numeração em função de sua

posição relativa dentro da estrutura. Os atributos são identificados através de letras para

diferenciá-los dos elementos. Por exemplo, o documento apresentado na FIG. 2.4(a) pode ser

representado por:

1- filme

1.a- id:"f2"

1.1- titulo: F1

1.2- diretor: D

1.3- elenco

1.3.a- idrefs:"a1 a2"

2- filme

2.a- id:"f2"

2.1- titulo: F2

2.2- diretor: D

2.3- elenco

2.3.a- idrefs:"a1 a3"

3- ator

3.a- id:"a1"

3.1- nome: A

3.2- atuou

3.2.a- idrefs:"f1 f2"

4- ator

4.a- id:"a2"

4.1- nome: B

4.2- atuou

4.2.a- idrefs:"f1"

5- ator

5.a- id:"a3"

5.1- nome: C

5.2- atuou

5.2.a- idrefs:"f2"

Esta notação facilita a visualização da organização do documento e é utilizada pelos

algoritmos implementados neste trabalho em lugar do grafo correspondente.

4.1.3. MODELO DA ESTRUTURA

Assim como é possível representar os dados de um documento XML através de um grafo,

também podemos representar a sua estrutura através de um grafo. Vimos que na seção 4.1.2

que nos limitaremos a considerar a árvore que representa os dados do documento. Do mesmo

modo, veremos que a estrutura do documento XML também pode ser representada por uma

árvore.

O grafo que representa a estrutura (esquema, ver seção 2.1.3) é obtido através da

representação das estruturas comuns presentes no documento, onde os vértices, que são

associados aos elementos do documento XML, podem ser classificados em relação à sua

existência nas subestruturas e à quantidade de vezes que aparecem, ou seja, os vértices podem

ser classificados:

• em relação à sua ocorrência dentro da estrutura na qual está inserida:

• obrigatório (OB): o elemento está presente em todas as ocorrências da estrutura

(sub-árvore) onde aparece;

• opcional (OP): o elemento não aparece em todas as ocorrências da estrutura (sub-

árvore) onde foi definido

• em relação à quantidade de ocorrências os elementos:

• simples (SI): o elemento só ocorre uma única vez em todas as subestruturas onde

está definido;

• múltiplo (MU): existe mais de uma ocorrência do elemento dentro da subestrutura

onde está definido.

• em relação à existência de dados associados:

• sem dado (SD): não existem dados (valor) delimitados pelo elemento;

• com dado (CD): o elemento define um dado (valor); poderia haver a classificação

em relação ao tipo de dado representado, o que não é considerado aqui, por não ser

necessário aos objetivos deste trabalho.

Esta definição é capaz de classificar qualquer item dos esquemas em XML, isto é, DTD e

XMLSchema

(ver seção 2.1.3). A FIG. 4.4 mostra o modelo proposto para representar a

estrutura do documento XML apresentado na FIG. 4.3.

não será feita a demonstração.

1<mercado>

2 <transacao>

3 <comida>

4 arroz

5 </comida>

6 </transacao>

7 <transacao>

8 <bebida>

9 cafe

10 </bebida>

11 <lanche>

12 manteiga

13 </lanche>

14 <lanche>

15 pao

16 </lanche>

17 </transacao>

18 <transacao>

19 <lanche>

20 manteiga

21 </lanche>

22 <lanche>

23 pao

24 </lanche>

25 <bebida>

26 cerveja

27 </bebida>

28 <bebida>

29 leite

30 </bebida>

31 </transacao>

32 <transacao>

33 <bebida>

34 cafe

35 </bebida>

36 <lanche>

37 manteiga

37 </lanche>

39 <lanche>

40 pao

41 </lanche>

42 </transacao>

43 <transacao>

44 <bebida>

45 cafe

46 </bebida>

47 <lanche>

48 manteiga

49 </lanche>

50 <lanche>

51 pao

52 </lanche>

53 <bebida>

54 leite

55 </bebida>

56 </transacao>

57 <transacao>

58 <bebida>

59 cerveja

60 </bebida>

61 </transacao>

62 <transacao>

63 <lanche>

64 manteiga

65 </lanche>

66 </transacao>

67 <transacao>

68 <lanche>

69 pao

70 </lanche>

71 </transacao>

72 <transacao>

73 <comida>

74 feijao

75 </comida>

76 </transacao>

77 <transacao>

78 <comida>

79 feijao

80 </comida>

81 <comida>

82 arroz

83 </comida>

84 </transacao>

85</mercado>

FIG. 4.3: Exemplo de documento XML

mercado SD OB SI

1 transacao SD OB MU

1.1 comida CD OP MU

1.2 bebida CD OP MU

1.3 lanche CD OP MU

FIG. 4.4: Modelo de estrutura do exemplo da FIG. 4.3

Seguem as classificações de cada item da estrutura da FIG. 4.4 - as linhas, quando

aparecem, se referem à FIG. 4.3:

• mercado - SD: não delimita nenhum dado; OB: ocorre sempre; SI: só ocorre uma

vez.

• transação - SD: não delimita nenhum dado; OB: ocorre em todas as ocorrências

do item a que está subordinado (mercado); MU: ocorre mais de uma vez (linhas

2, 7, 18, etc).

• comida - CD: delimita pelo menos um dado (linhas 4, 74, 79 e 82); OP: não

ocorre em todas as ocorrências do item a que está subordinado (transação), por

exemplo a transação delimitada pelas linhas 7 e 17; MU: ocorre uma ou mais

vezes em cada item a que está subordinado (transação), por exemplo a transação

delimitada pelas linhas 77 e 84 tem "comida" ocorrendo nas linhas 78 e 81.

• bebida e lanche - semelhante à "comida".

4.1.4. PRÉ-PROCESSAMENTO

Este trabalho pressupõe que o documento XML a ser processado possa não dispor

de esquema associado, DTD ou XMLSchema (ver seção 2.1.3). Isto equivale a dizer

que não é necessário que o documento XML seja correto, bastando que seja bem

formado

Este trabalho requer um pré-processamento do documento XML de forma a obter a

estrutura do documento. Este requisito decorre do fato de que a escolha de parâmetros

para a execução dos algoritmos se baseia na estrutura do documento XML analisado.

A FIG. 4.5 apresenta a estrutura do documento XML (exibido na FIG. 4.3) gerado

pela função de pré-processamento implementada neste trabalho, que pode ser

comparada com a estrutura mostrada na FIG. 4.4.

1 mercado (obrigatório, simples)

2 - 1 transacao (obrigatório, múltiplo)

3 - - 1.1 [comida] (opcional, múltiplo)

4 - - 1.2 [bebida] (opcional, múltiplo)

5 - - 1.3 [lanche] (opcional, múltiplo)

FIG. 4.5: Estrutura do documento XML gerado pela aplicação

A implementação da função de pré-processamento utiliza a seguinte notação:

• em relação à existência de dado associados: o nome do elemento com dado

aparece delimitado entre colchetes ("[" e "]"); por exemplo, a linha 3 mostra que

documento XML correto é um documento que esteja de acordo com um esquema associado;

documento XML bem formado é um documento que esteja escrito de acordo com as regras de formação

definidas para o XML (ver seção 2.1.2).

o elemento "comida" apresenta dados, pois está entre colchetes, enquanto que na

linha 2 vemos que o elemento "transação" não tem dados associados;

• em relação à quantidade de ocorrências: o elemento é classificado em simples ou

múltiplo; por exemplo, na linha 1 vemos que o elemento "mercado" é simples,

enquanto que os demais elementos são múltiplos;

• em relação à sua ocorrência: o elemento é classificado em obrigatório ou

opcional; por exemplo, na linha 2 vemos que o elemento "transacao" é

obrigatório, enquanto que o elemento "comida" na linha 3 é opcional.

Foram feitas análises de vários documentos e foi observada a correção de todas as

estruturas geradas. O ANEXO 2 mostra um outro exemplo de documento XML mais

complexo, onde a estrutura gerada pode ser observada.

4.1.5. DEFINIÇÃO DOS DADOS PARA ASSOCIAÇÃO

Para a geração de regras de associação e a classificação em documentos XML é

necessária uma definição precisa dos dados que serão processados, o que pode não ser

trivial pelas características da estrutura de dados em documentos XML (ver seção 2.1.2).

As técnicas de geração de regras de associação e de classificação convencionais,

isto é, aplicadas em bancos de dados relacionais (AGRAWAL, IMIELINSKI, SWAMI,

1993) (GOLDSCHMIDT, 2003), se baseiam fortemente no conceito de

registros/transações, ou seja:

• associação: descobrir regras que associem dados de diferentes transações, como,

por exemplo, itens adquiridos por um cliente numa compra no supermercado

(AGRAWAL, IMIELINSKI, SWAMI, 1993);

• classificação: descobrir uma função que relacione um determinado atributo

(atributo objetivo ou classe) da transação aos demais atributos (atributos

preditivos) da mesma transação.

O modelo para definição dos dados descrito ao longo desta seção então se baseia

em identificar uma estrutura que se repete no documento XML, mantendo assim uma

similaridade com as estruturas existentes em bancos de dados relacionais. Este modelo

está baseado em trabalhos semelhantes (BRAGA, CAMPI, KLEMETTINEN, LANZI,

2002) (DING, RICORDS, LUMPKIN, 2003), onde se pode observar a necessidade de

sua definição.

Na análise da estrutura do documento XML, pode-se perceber a repetição de sub-

árvores com estruturas semelhantes cujos dados (vértices) podem ser planificados e

assim se obter uma organização como desejado.

FIG. 4.6: Representação esquemática de estruturas semelhantes

Por exemplo, a FIG. 4.6 mostra a representação esquemática de um documento

XML onde as estruturas semelhantes são representadas por triângulos semelhantes.

Na FIG. 4.6 as arestas não estão nomeadas apenas para facilitar a visualização da

figura. Vamos assumir que a aresta e

dá acesso ao vértice v

, a aresta e

ao vértice v

e assim por diante.

Observamos na FIG. 4.6 dois tipos de agrupamentos semelhantes:

• TIPO 1: sub-árvores com raízes marcadas por uma círculo grande (), que são

acessadas a partir do vértice v

• sub-árvore 1: v

, v

;

• sub-árvore 2: v

, v

;

• sub-árvore 3: v

, v

• TIPO 2: sub-árvores com raízes marcadas por uma quadrado (), que são

acessadas a partir dos vértice marcados por um círculo grande ():

• sub-árvore 1: v

, v

;

• sub-árvore 2: v

, v

;

• sub-árvore 3: v

, v

Pode-se observar então na FIG. 4.6 que as estruturas semelhantes (sub-árvores) têm

o mesmo tipo de vértice raiz: vértices marcados por "" (grupo tipo 1) ou por ""

(grupo tipo 2). Portanto, a definição dos dados que serão processados (geração de regras

de associação e classificação) se faz inicialmente pela identificação do vértice que

representa a raiz das sub-árvores semelhantes cujos dados serão processados (vértice de

acesso). Pode-se observar que é condição necessária que um vértice de acesso seja

classificado como múltiplo (MU) (ver seção 4.1.3).

O passo seguinte compreende a seleção dos elementos que serão processados, que

(a) devem pertencer às sub-árvores definidas anteriormente e (b) devem ter dados

associados (elementos/nós classificados como "CD" como descrito na seção 4.1.3).

A restrição (b) foi introduzida, pois as implementações dos métodos de descoberta

de associação e de classificação não podem considerar dados ausentes.

Os vértices selecionados para processamento podem ser identificados de dois

modos:

• identificação absoluta: formada pelo nome do vértice, isto é, a propriedade nome

do vértice (nome(v

)); por exemplo, na FIG. 2.5, a identificação absoluta do

vértice v

(nome(v

)) é "titulo";

• identificação relativa: formada pelo caminho do vértice em relação ao vértice raiz

da sub-árvore e o seu nome, no formato "caminho/nome", isto é, as

propriedades caminho e nome do vértice (caminho(v

)/nome(v

));

exemplos:

- na FIG. 4.6, a identificação relativa do vértice v

em relação à sub-árvore

com raiz v

é caminho(v

)/nome(v

) = nome(v

)/nome(v

);

- na FIG. 2.5, a identificação relativa do vértice v

em relação à sub-árvore

com raiz v

é caminho(v

)/nome(v

) = nome(v

)/nome(v

) =

"filme/titulo";

- na FIG. 2.5, a identificação relativa do vértice v

em relação à sub-árvore

com raiz v

é caminho(v

)/nome(v

) = nome(v

) = "titulo".

Os dados que são processados então estão no formato identificação:valor, onde a

identificação pode ser absoluta ou relativa como descrito no parágrafo anterior, e valor

corresponde ao dado definido no vértice (ver seção 2.1.4). Por exemplo, a representação

do dado no vértice v

pode ser:

- "titulo:F1" na representação absoluta; ou

- "filme/titulo:F1" na representação relativa em relação ao vértice v

Temos então que a definição dos dados para associação ocorre quando os

seguintes itens são identificados na estrutura apresentada do documento XML:

• raiz: elemento que representa a raiz da sub-árvore de elementos semelhantes; é

necessário que este elemento seja múltiplo - MU - como definido na seção 4.1.4.

• dado: elemento que será utilizado para a geração das regras; é necessário que seja

um elemento pertencente à estrutura do elemento raiz como definido acima e que

tenha dados associados - CD - como definido na seção 4.1.4.

Vale destacar que o elemento selecionado para associação, apesar de classificado

como CD (com dado associado) pode ocorrer uma ou mais vezes no documento XML

com o conteúdo vazio - por exemplo, <X/> ou <X></X>. Quando isto ocorre o

elemento não é selecionado para associação.

As definições de dados para associação apresentadas nesta seção também são

válidas para a classificação, com a diferença somente de que nesta, como veremos, os

dados são definidos como atributos (antecedentes) e classe (consequente).

Para a classificação, outra restrição é necessária: o elemento selecionado como

classe não pode ser sub-elemento de um elemento múltiplo (MU). Esta restrição impede

que o elemento ocorra mais de uma vez na transação.

4.1.6. PROCESSAMENTO DO DOCUMENTO XML

O acesso aos dados do documento XML é feito percorrendo sequencialmente os

seus vários elementos, que mantêm uma similaridade com a estrutura identificada no

pré-processamento (ver seção 4.1.4.), quando são identificados três tipos de dados:

• início de elemento (tag inicial) - acesso ao filho do elemento corrente na estrutura

definida;

• fim de elemento (tag final) - acesso ao pai do elemento corrente na estrutura

definida;

• valor - acesso ao valor do elemento corrente

Portanto, a implementação utiliza a estrutura identificada no pré-processamento

para controlar o processamento dos elementos do documento XML selecionado, quando

somente estes três tipos de dados são identificados

4.1.7. FORMATO BASKET

Neste trabalho, como veremos adiante, em alguns processamentos é necessário

realizar a transformação do documento XML no formato basket, que compreende

relacionar numa lista todos os vértices selecionados para processamento (ver seção

4.1.5) em relação ao vértice definido como raiz da sub-árvore (ver seção 4.1.5). Esta

lista é formada por duas colunas, que podem, por exemplo, ser armazenadas num banco

de dados relacional. São elas:

• primeira coluna (C1): propriedade identificador do vértice raiz da sub-árvore

(ver seção 4.1.5); e

• segunda coluna (C2): identificação e valor do vértice selecionado para

processamento como descrito na seção 4.1.5.

na seção 2.1.2 vemos que um documento XML possui vários outros tipos de elementos, mas

somente estes três são considerados para associação e classificação no escopo deste trabalho.

Por exemplo, a FIG. 4.7 apresenta o documento XML exibido na FIG. 4.3 após

transformação para o formato basket.

C1 C2

1 comida:arroz

2 bebida:cafe

2 lanche:manteiga

2 lanche:pao

3 lanche:manteiga

3 lanche:pao

3 bebida:cerveja

3 bebida:leite

4 bebida:cafe

4 lanche:manteiga

4 lanche:pao

5 bebida:cafe

5 lanche:manteiga

5 lanche:pao

5 bebida:leite

6 bebida:cerveja

7 lanche:manteiga

8 lanche:pao

9 comida:feijao

10 comida:feijao

10 comida:arroz

FIG. 4.7: Formato basket

4.1.8. PARÂMETROS

A geração das regras de associação é baseada nos seguintes parâmetros:

• minsup: suporte mínimo (ver seção 2.3.2)

• minconf: confiança mínima (ver seção 2.3.2); e

• maxitens: número máximo de itens que formarão as regras de associação.

• O parâmetro maxitens tem o único objetivo de limitar o número de itens que

serão considerados na geração de combinações de conjunto de itens processados.

Também são identificados o elemento raiz e os dados selecionados para associação

como descrito na seção 4.1.5. Estas opções caracterizam uma interface interativa onde

os dados podem ser selecionados diretamente sobre uma representação gráfica da

estrutura do documento, o que é diferente de muitos trabalhos semelhantes, que definem

a operação de associação através de extensões da linguagem de consulta XQuery (ver

seção2.1.6).

4.2. MINERAÇÃO DE REGRAS DE ASSOCIAÇÃO EM DOCUMENTOS XML

- ABORDAGEM CLÁSSICA

4.2.1. CONSIDERAÇÕES INICIAIS

Os estudos para o desenvolvimento deste trabalho se iniciaram com a

implementação do algoritmo Apriori (AGRAWAL, SRIKANT, 1994) para

processamento de bancos de dados relacionais, com o objetivo inicial de adquirir

conhecimentos específicos sobre este tipo de algoritmo

FIG. 4.8: Processamento clássico de documentos XML

O Apriori então foi estendido para processamento de documentos XML. Para tanto,

utilizou-se uma abordagem clássica (BRAGA, CAMPI, STEFANO, KLEMETTINEN,

LANZI, 2002a) (DING, RICORDS, LUMPKIN, 2003) na qual o documento XML passa

por um pré-processamento de conversão dos seus dados para o formato basket

armazenado em banco de dados relacional. O diagrama da FIG. 4.8 resume o

processamento clássico de descoberta de associações em documentos XML.

o algoritmo Apriori está implementado na ferramenta Bramining (GOLDSCHMIDT,

NOGUEIRA, PASSOS, VELLASCO, 2002).

A função de transformação indicada na FIG. 4.8 é feita como descrito na seção

4.1.7 e os dados selecionados (sobre os quais serão geradas as regras de associação)

como descrito na seção 4.1.5. Os dados são armazenados numa tabela auxiliar contendo

dois campos:

• transacao: corresponde à primeira coluna (C1) da tabela;

• item: corresponde à segunda coluna (C2) da tabela;

4.2.2. ALGORITMO APRIORI

A descrição do algoritmo Apriori foi apresentada formalmente na seção 2.3.2. A

implementação do Apriori utilizada neste trabalho encontra-se descrita na FIG. 4.9.

APriori (IN docXML, restrições, minsup, minconf, maxitens; OUT

regras)

1 B = BASKET(docXML)

2 L

= LISTA_SIMPLES

3 se L

= ∅ então FIM //não existem regras

4 para (k = 2, L

k-1

≠ ∅ ∨ k=maxitens, k++)

5 C

= CANDIDATOS(L

k-1

)

6 se C

= ∅ então FIM //não existem mais regras

7 CONTAR(C

); L

= C

8 regras = MONTAREGRAS(L

, i > 1)

FIG. 4.9: Algoritmo Apriori

O algoritmo tem os seguintes parâmetros de entrada:

• docXML: identificação do documento XML que será processado;

• restrições: estrutura do documento (docXML), incluindo o elemento raiz, com

as restrições de cada elemento:

- sem restrição

- só antecedente da regra

- só consequente da regra

• minsup: suporte mínimo;

• minconf: confiança mínima;

• maxitens: número máximo de itens que formarão as regras de associação; este

número limita o tempo de processamento, pois evita o processamento de

conjuntos com um número excessivo de elementos;

O algoritmo tem como saída o conjunto de regras geradas (regras).

A seguir é apresentada a descrição de cada passo do algoritmo, onde L

representa o

conjunto de itens com i elementos (implementado na tabela SYS_ITENS) e C

conjunto de itens candidatos com i elementos.

1 o documento XML a ser processado é inicialmente convertido para o formato

basket como descrito na seção 4.1.7; a tabela SYS_BASKET é representada por

B; as restrições são utilizadas para definir os elementos que serão convertidos.

2 rotina LISTA_SIMPLES: é obtida a lista C

de elementos simples (1-elementos),

que formam a lista de itens candidatos, e respectivo número de ocorrências n; é

feito L

= C

para elementos em que n ≥ minsup.

3 verifica se existem elementos suficientes para geração das regras.

4 inicia um loop variando o índice k com valor inicial 2, incremento de 1 a cada

iteração do loop, até que o conjunto de itens gerados na iteração anterior (L

k-1

)

seja vazio ou k tenha atingido o limite estabelecido.

5 geração dos candidatos C

a partir itens L

k-1

da iteração anterior, obtidos pela

inclusão dos itens de L

6 verifica se foram gerados novos candidatos na iteração.

7 cálculo do número n de ocorrências de C

em B; os elementos de C

com n

≥minsup são armazenados em L

8 os elementos de L

, i>1 contêm os itens com suporte ≥ minsup; os elementos de

são distribuídos em 2 grupos, que poderão formar o antecedente e o

consequente da regra; é calculada a confiança de cada regra gerada pelas

combinações de antecedente e consequente que podem ser formados; as

restrições informadas são obedecidas para a formação das regras.

A rotina LISTA_SIMPLES (linha 2) obtém a lista de 1-elementos realizando uma

varredura completa na base de dados e identificando os elementos simples que têm

suporte igual ou superior ao suporte mínimo definido. Esta lista é usada pela rotina

CANDIDATOS (linha 5), para inicialmente criar a lista de 2-elementos pela

combinação dos 1-elementos. Nos passos seguintes a rotina CANDIDATOS obtém a

lista de k elementos de itens candidatos pela adição de um elementos da lista de 1-

elementos à cada item de (k-1)-elementos de itens.

A rotina CONTAR (linha 7) varre a base de dados para apurar o número de

ocorrências do conjunto de k-candidatos e avaliar se o suporte de cada um atingiu o

valor definido pelo suporte mínimo. Os conjuntos que não atingem o suporte mínimo

são então removidos da lista de candidatos e são então armazenados na lista de itens C

Ao final do processamento, a lista L contém todos os itens com valor do suporte

igual ou superior ao suporte mínimo. A rotina MONTAREGRAS (linha 8) cria as regras

para cada conjunto de L, obedecendo ao critérios:

• verifica se os itens têm restrições quanto à posição que ocuparão na regra

(antecedente e/ou consequente)

• verifica se a confiança da regra é igual ou superior à confiança mínima definida;

caso não seja, a regra é descartada; observe que a confiança é calculada com base

no suporte de cada subconjunto estabelecido como antecedente e consequente

calculado nos passos anteriores (candidatos de k-elementos)

A FIG. 4.10 mostra os resultados obtidos pela aplicação do algoritmo sobre o

documento XML da FIG. 4.3 (cuja estrutura está descrita na FIG. 4.5 e a transformação

no formato basket na FIG. 4.7), considerando os seguintes parâmetros:

• raiz: mercado

• elementos para associação:

- mercado/bebida: antecedente e consequente

- mercado/comida: antecedente e consequente

- mercado/lanche: antecedente e consequente

• minsup=30% (3 transações)

• minconf=80%

• maxitens: 3

LINHA

PASSO k

CANDIDATOS C

ITENS L

2 1

√{bebida:cafe}s:3

{bebida:cerveja}s:2

{bebida:leite}s:2

{comida:arroz}s:2

{comida:feijao}s:2

√{lanche:manteiga}s:5

√{lanche:pao}s:5

{bebida:cafe}

{lanche:manteiga}

{lanche:pao}

5/7 2

√{bebida:cafe,lanche:manteiga}s:3

√{bebida:cafe,lanche:pao}s:3

√{lanche:manteiga,lanche:pao}s:4

{bebida:cafe,lanche:manteiga}

{bebida:cafe,lanche:pao}

{lanche:manteiga,lanche:pao}

5/7 3

√{bebida:cafe,lanche:manteiga,

lanche:pao}s:3

{bebida:cafe,lanche:manteiga,

lanche:pao}

FIG. 4.10(a): Avaliação do suporte das transações

ITENS L

REGRAS

{bebida:cafe,

lanche:manteiga}

bebida:cafe >> lanche:manteiga c:1,0

lanche:manteiga >> bebida:cafe c:0,6

{bebida:cafe, lanche:pao} bebida:cafe >> lanche:pao c:1,0

lanche:pao >> bebida:cafe c:0,6

{lanche:manteiga,

lanche:pao}

lanche:manteiga >> lanche:pao c:0,8

lanche:pao >> lanche:manteiga c:0,8

{bebida:cafe,

lanche:manteiga,

lanche:pao}

bebida:cafe >> lanche:manteiga, lanche:pao c:1,0

bebida:cafe, lanche:manteiga >> lanche:pao c:1,0

bebida:cafe, lanche:pao >> lanche:manteiga c:1,0

lanche:manteiga, lanche:pao >> bebida:cafe c:0,75

lanche:manteiga >> bebida:cafe, lanche:pao c:0,6

lanche:pao >> bebida:cafe, lanche:manteiga c:0,6

FIG. 4.10(b): Avaliação da confiança e geração de regras

Observe que foi mantida a ordem lexicográfica dos itens, o que também é feito na

implementação.

Na FIG. 4.10(b), na coluna REGRAS, aparecem todas as regras que podem ser

geradas a partir dos conjuntos apresentados na coluna ITENS L

, sendo que as regras

com confiança maior ou igual à confiança mínima definida para este problema (0,8)

aparecem em destaque (negrito).

O ANEXO 1 mostra como executar a implementação deste método.

4.2.3. REGRAS DE ASSOCIAÇÃO GENERALIZADA

C1 C2

1 comida:arroz

1 comida:

2 bebida:cafe

2 lanche:manteiga

2 lanche:pao

2 bebida:

2 lanche:

3 lanche:manteiga

3 lanche:pao

3 bebida:cerveja

3 bebida:leite

3 bebida:

3 lanche:

4 bebida:cafe

4 lanche:manteiga

4 lanche:pao

4 bebida:

4 lanche:

5 bebida:cafe

5 lanche:manteiga

5 lanche:pao

5 bebida:leite

5 bebida:

5 lanche:

6 bebida:cerveja

6 bebida:

7 lanche:manteiga

7 lanche:

8 lanche:pao

8 lanche:

9 comida:feijao

9 comida:

10 comida:feijao

10 comida:arroz

10 comida:

FIG. 4.11: Formato basket

A geração de regras de associação generalizada a partir de documentos XML não

sofre nenhuma alteração na estrutura básica do algoritmo Apriori em relação ao definido

na seção 4.2.2. A única modificação realizada é na conversão dos dados no formato

basket (passo 1 do algoritmo da FIG. 4.10(a)), que inclui os caminhos dos elementos

selecionados para associação considerando a taxonomia implícita dos itens no

documento XML

. Neste trabalho denominaremos AprioriG o algoritmo Apriori

modificado para geração de regras de associação generalizada.

LINHA

PASSO k

CANDIDATOS C

ITENS L

2 1

√{bebida:}s:5

√{bebida:cafe}s:3

{bebida:cerveja}s:2

{bebida:leite}s:2

{comida:feijao}s:2

√{comida:}s:3

{comida:arroz}s:2

√{lanche:}s:6

√{lanche:manteiga}s:5

√{lanche:pao}s:5

{bebida:}

{bebida:cafe}

{comida:}

{lanche:}

{lanche:manteiga}

{lanche:pao}

5/7 2

√{bebida:,lanche:}s:4

√{bebida:,lanche:manteiga}s:4

√{bebida:,lanche:pao}s:4

√{bebida:cafe,lanche:}s:3

√{bebida:cafe,lanche:manteiga}s:3

√{bebida:cafe,lanche:pao}s:3

√{lanche:manteiga,lanche:pao}s:4

{bebida:,lanche:}

{bebida:,lanche:manteiga}

{bebida:,lanche:pao}

{bebida:cafe,lanche:}

{bebida:cafe,lanche:manteiga}

{bebida:cafe,lanche:pao}

{lanche:manteiga,lanche:pao}

5/7 3 {bebida:,comida:,lanche:}s:0

{bebida:,comida:,

lanche:manteiga}s:0

{bebida:,comida:,lanche:pao}s:0

√{bebida:,lanche:manteiga,

lanche:pao}s:4

{bebida:cafe,comida:,lanche:}s:0

{bebida:cafe,comida:,

lanche:manteiga}s:0

{bebida:cafe,comida:,lanche:pao}

s:0

√{bebida:cafe,lanche:manteiga,

lanche:pao}s:3

{comida:,lanche:manteiga,

lanche:pao}s:0

{bebida:,lanche:manteiga,

lanche:pao}

{bebida:cafe,lanche:manteiga,

lanche:pao}

FIG. 4.12(a): Avaliação do suporte das transações

A execução da rotina BASKET (linha 1 do algoritmo da FIG. 4.9) cria a tabela

correspondente como mostrada na FIG. 4.11, que se diferencia da tabela mostrada na

FIG. 4.7 pelos itens em destaque (itálico) que correspondem aos caminhos adicionados

à transação.

outra modificação é feita na geração de regras, quando as regras redundantes não são geradas (ver

seção 2.3.3).

Com os mesmos parâmetros definidos na seção 4.2.2 são obtidos os resultados

mostrados na FIG. 4.12.

ITENS L

REGRAS

{bebida:,lanche:} bebida: >> lanche: c:0,8

lanche: >> bebida: c:0,67

{bebida:,lanche:manteiga} bebida: >> lanche:manteiga c:0,8

lanche:manteiga >> bebida: c:0,8

{bebida:,lanche:pao} bebida: >> lanche:pao c:0,8

lanche:pao >> bebida: c:0,8

{bebida:cafe,lanche:} bebida:cafe >> lanche: c:1,0

lanche: >> bebida:cafe c:0,5

{bebida:cafe,lanche:manteiga} bebida:cafe >> lanche:manteiga c:1,0

lanche:manteiga >> bebida:cafe c:0,6

{bebida:cafe,lanche:pao} bebida:cafe >> lanche: pao c:1,0

lanche:pao >> bebida:cafe c:0,6

{lanche:manteiga,lanche:pao} lanche:manteiga >> lanche:pao c:0,8

lanche:pao >> lanche:manteiga c:0,8

{bebida:,lanche:manteiga,

lanche:pao}

bebida: >> lanche:manteiga,

lanche:pao c:0,8

bebida:, lanche:manteiga >>

lanche:pao c:1,0

bebida:, lanche:pao >>

lanche:manteiga c:1,0

lanche:manteiga, lanche:pao >>

bebida: c:1,0

lanche:manteiga >> bebida:,

lanche:pao c:0,8

lanche:pao >> bebida:,

lanche:manteiga c:0,8

{bebida:cafe,lanche:manteiga,

lanche:pao}

bebida:cafe >> lanche:manteiga,

lanche:pao c:1,0

bebida:cafe, lanche:manteiga >>

lanche:pao c:1,0

bebida:cafe, lanche:pao >>

lanche:manteiga c:1,0

lanche:manteiga, lanche:pao >>

bebida:cafe c:0,75

lanche:manteiga >> bebida:cafe,

lanche:pao c:0,6

lanche:pao >> bebida:cafe,

lanche:manteiga c:0,6

FIG. 4.12(b): Avaliação da confiança e geração das regras

Na FIG. 4.12(b), na coluna REGRAS, aparecem todas as regras que podem ser

geradas a partir dos conjuntos apresentados na coluna ITENS L

, sendo que as regras

com confiança maior ou igual à confiança mínima definida para este problema (0,8)

aparecem em destaque (negrito).

Ao comparar as regras geradas das FIG.S 4.10(b) e 4.12(b), observamos que as

seguintes regras forma adicionadas:

• bebida:cafe >> lanche:

• lanche: >> bebida:cafe

• bebida:, lanche:manteiga >> lanche:pao

• lanche:pao >> bebida:, lanche:manteiga

• lanche:manteiga >> bebida:, lanche:pao

• bebida:, lanche:pao >> lanche:manteiga

• bebida: >> lanche:manteiga, lanche:pao

• lanche:manteiga, lanche:pao >> bebida:

• bebida: >> lanche:pao

• lanche:pao >> bebida:

• bebida: >> lanche:

• lanche: >> bebida:

• bebida: >> lanche:manteiga

• lanche:manteiga >> bebida:

4.2.4. COMPARAÇÃO COM OUTRAS ABORDAGENS

Percebeu-se que os trabalhos sobre geração de regras de associação em documentos

XML (BRAGA, CAMPI, STEFANO, KLEMETTINEN, LANZI, 2002a) (DING,

RICORDS, LUMPKIN, 2003) envolviam a transformação (pré-processamento) do

documento XML em base de dados relacionais no formato basket para então serem

processadas pelo algoritmo Apriori ou um algoritmo derivado, que serviu então como

base para os estudos iniciais deste trabalho como descrito na seção 4.2.1.

Os trabalhos de (BRAGA, CAMPI, STEFANO, KLEMETTINEN, LANZI, 2002a)

(DING, RICORDS, LUMPKIN, 2003) se baseiam na extensão da linguagem de

consulta XQuery (ver seção 2.1.6) com a adição de um operador específico para

geração de regras de associação, o que permite uma grande flexibilidade de uso, muito

embora utilizem os mesmos conceitos teóricos utilizados neste trabalho - definição de

raiz de sub-árvore para processamento (ROOT) e dos elementos que serão utilizados

(BODY e HEAD).

Por sua vez, este trabalho apresenta uma interface gráfica para interação com o

usuário, o que pode significar perda de flexibilidade se comparada com o uso de

XQuery. Por outro lado apresenta a grande vantagem de facilitar a interação, que pode

assim desfrutar de um meio mais amigável para trabalho.

4.2.5. CONSIDERAÇÕES COMPLEMENTARES

Uma vez que os dados dos documentos XML podem ser convertidos para o formato

basket em bancos de dados relacionais, os métodos tradicionais de geração de regras de

associação, que são desenvolvidos para operarem sobre dados no formato basket,

podem então ser utilizados. O algoritmo Partition (SAVASERE, OMIECINSKI,

NAVATHE, 1995) e o algoritmo DHP (PAPAKONSTANTINOU, GARCIA-

MOLINA, WIDOM, 1995) são exemplos de algoritmos que poderiam ser então

utilizados sobre os dados armazenados.

4.3. MINERAÇÃO DE REGRAS DE ASSOCIAÇÃO EM DOCUMENTOS XML

- ABORDAGEM PROPOSTA

4.3.1. CONSIDERAÇÕES INICIAIS

A aplicação do algoritmo Apriori está baseada em dois conceitos:

• os dados devem estar no formato basket; no caso de documentos XML deve

ser feito um pré-processamento para a sua transformação no formato

basket

• a geração de conjuntos candidatos que devem ter o suporte calculado, o que

exige várias iterações sobre a base de dados de entrada.

Entre várias características da geração de conjuntos candidatos

, uma chamou a

atenção em particular: muitos conjuntos candidatos não existem na base de dados e

acabam provocando processamento desnecessário para calcular o seu suporte (que é

igual a zero!).

Foram iniciados estudos visando desenvolver um algoritmo que suprisse estas

deficiências, ou seja:

• permitisse o processamento diretamente sobre o documento XML sem

necessidade de transformação no formato dos dados;

• o suporte fosse calculado somente para conjuntos existentes, o que implicaria

em que não fossem gerados conjuntos candidatos.

na verdade este pré-processamento também é condição para a execução do algoritmo sobre bancos

de dados relacionais que não estejam no formato basket.

o estudo completo sobre o algoritmo Apriori e a geração de conjuntos candidatos encontra-se

descrito na seção 4.2.2; a seção 3.2 mostra estudos relacionados, onde são apresentados trabalhos que

desenvolvem melhorias do algoritmo Apriori.

O primeiro algoritmo proposto, ASCX-1P (Associação Sem geração de Candidatos

em documentos XML em 1 Passo), faz a geração de regras de associação a partir de um

único passo de leitura sobre o documento XML de entrada. Os conjuntos de itens

obtidos, relativos às transações como definido na seção 4.1.5, são armazenados numa

tabela hash em memória

. Como os dados lidos são armazenados sem nenhum tipo de

processamento, a tabela hash criada desta forma praticamente possui uma cópia do

documento original. Esta forma de uso acaba por provocar um gasto excessivo de

memória e pode necessitar de um tempo igualmente alto de processamento, pois a tabela

armazena muitos dados que não têm qualquer utilidade para a geração das regras, o que

acaba gerando a necessidade de tempo de processamento adicional.

O algoritmo ASCX-1P foi então modificado para o algoritmo ASCX-2P

(Associação Sem geração de Candidatos em documentos XML em 2 Passos

) de modo

a executar um passo adicional para inicialmente identificar os conjuntos de itens

elementares (com um único elemento) cujo suporte seja inferior ao suporte mínimo

definido. Estes itens são então usados no processamento seguinte para evitar o

armazenamento de conjuntos de itens que certamente não serão úteis na geração de

regras de associação, otimizando o processamento e economizando recursos de

memória. O capítulo 5 mostra alguns detalhes da implementação, incluindo a avaliação

do desempenho dos algoritmos.

Como mencionado, não é feita a geração de conjuntos de itens candidatos, principal

característica do algoritmo Apriori (AGRAWAL, SRIKANT, 1994) e suas variantes.

Na seção 4.2.3 vimos que o algoritmo Apriori foi modificado para geração de

regras de associação generalizada (ver seção 2.3.3), originando o algoritmo AprioriG.

De modo semelhante, os algoritmos ASCX-1P e ASCX-2P foram adaptados para

geração de regras de associação generalizada, originando, respectivamente, os

algoritmos ASCX-1PG (Associação Sem geração de Candidatos em documentos XML

em 1 Passo - regras Generalizadas) e ASCX-2PG (Associação Sem geração de

Candidatos em documentos XML em 2 Passos - regras Generalizadas).

ver seção 4.1.8

aqui, talvez inconscientemente, prestei uma homenagem ao prof. Emmanuel, um dos meus

orientadores.

Não foi possível perceber a existência de trabalhos similares, isto é, sobre regras de

associação sem geração de conjuntos candidatos aplicados a documentos XML, apesar

da existência de trabalhos semelhantes aplicados a bancos de dados relacionais (HAN,

PEI, YIN, 2000) (CHEUNG, ZAIANE, 2003).

4.3.2. ALGORITMO ASCX-1P

ASCX-1P (IN docXML, restrições, minsup, minconf, maxitens; OUT regras)

1 P = parserXML(docXML)

2 enquanto existe I = P.proximoItem //passo sobre o documento

3 caso I.tipo = tagInicial

4 se I definido como raiz da transação

5 incrementa n. de transações

6 C = ∅

7 caso I.tipo = conteúdo

8 se I definido para associação

9 C = C + I //insere elemento no conjunto

10 caso I.tipo = tagFinal

11 TabHash.inserir (C) // armazena conjunto na tabela hash

12 Calcular transações de suporte mínimo

13 enquanto existe C = TabHash.proximoConjunto

14 TabHash.inserir (c

∈ C) // armazena itens elementares

15 EXPANDIR (C)

16 enquanto existe C = TabHash.proximoConjunto

17 se SUPORTE(C) ≥ minSup

18 regras = MONTAREGRAS(C)

FIG. 4.13: Algoritmo ASCX-1P

A FIG. 4.13 exibe o algoritmo ASCX-1P (Associação Sem geração de Candidatos

em documentos XML em 1 Passo) para a geração de regras de associação.

Os parâmetros de entrada são os mesmos como definidos na seção 4.2.2.

A seguir é apresentada a descrição de cada passo do algoritmo, onde P representa o

objeto criado pelo parser XML que realiza a leitura do documento XML, I cada um dos

itens lidos no documento XML, C o conjunto de elementos definidos para associação e

que são armazenados na tabela hash TabHash.

1 o objeto P do parser XML é inicializado para acesso ao documento XML a ser

processado.

2 armazena o próximo item de P (documento XML) no item I enquanto existir

item disponível (fim do documento).

3 identifica se o item I é uma marcação (tag) inicial.

4 verifica se I foi selecionado como raiz da associação.

5 incrementa o número de transações.

6 inicializa o conjunto C de elementos como vazio.

7 identifica se o item I é um conteúdo delimitado (valor).

8 verifica se o item I está definido para associação.

9 insere o elemento do documento (armazenado no item I) no conjunto C de

elementos da transação.

10 identifica se o item I é uma marcação (tag) final.

11 insere o conjunto C na tabela hash TabHash e incrementa o contador

correspondente de uma unidade (que forma o suporte do conjunto).

12 calcula o número de transações que correspondem ao suporte mínimo, fazendo o

cálculo do percentual de minsup sobre o número de transações calculados na

linha 5.

13 acesso sequencial a cada conjunto C armazenado na tabela hash TabHash.

14 insere na tabela hash TabHash cada item elementar c

de C e adiciona o

contador associado a C ao contador do item c

inserido.

15 expandir o conjunto C nos seus vários subconjuntos, que são então adicionados à

tabela hash TabHash.

16 acesso sequencial a cada conjunto C armazenado na tabela hash TabHash.

17 verifica se o suporte do conjunto C é maior ou igual ao número de transações

associado ao suporte mínimo (calculado na linha 12).

18 os elementos de C são distribuídos em dois grupos, que poderão formar o

antecedente e o consequente da regra; é calculada a confiança de cada regra

gerada pelas combinações de antecedente e consequente que podem ser

formados; as restrições informadas são obedecidas para a formação das regras.

A rotina EXPANDIR (linha 15) obtém todos os subconjuntos de C com mais de um

elemento e armazena na tabela hash TabHash, adicionando o suporte de C a cada

elemento armazenado.

A rotina MONTAREGRAS (linha 18) cria as regras para cada conjunto C da tabela

hash TabHash, obedecendo aos critérios:

• verifica se os itens têm restrições quanto à posição que ocuparão na regra

(antecedente e/ou consequente)

• verifica se a confiança da regra é igual ou superior à confiança mínima definida;

caso não seja, a regra é descartada; a confiança é calculada com base no suporte

de cada subconjunto estabelecido como antecedente e consequente armazenados

na tabela hash TabHash.

Um exemplo de execução do algoritmo ASCX-1P é apresentado a seguir. Os

resultados são obtidos pela aplicação do algoritmo sobre o documento XML da FIG. 4.3,

cuja estrutura está descrita na FIG. 4.5, considerando os seguintes parâmetros:

• raiz: mercado

• elementos para associação:

- mercado/bebida: antecedente e consequente

- mercado/comida: antecedente e consequente

- mercado/lanche: antecedente e consequente

• minsup=30% (3 transações)

• minconf=80%

• maxitens: 3

Observe que é mantida a ordem lexicográfica dos itens, o que também é feito na

implementação.

A tabela hash após a execução das linhas 2 a 11 é:

bebida:cafe;bebida:leite;lanche:manteiga;lanche:pao; sup:1

bebida:cafe;lanche:manteiga;lanche:pao; sup:2

bebida:cerveja; bebida:leite;lanche:manteiga;lanche:pao; sup:1

bebida:cerveja; sup:1

comida:arroz; sup:1

comida:arroz;comida:feijao; sup:1

comida:feijao; sup:1

lanche:manteiga; sup:1

lanche:pao; sup:1

Os conjuntos armazenados correspondem às transações no documento XML. Pode-

se observar que a soma dos valores do suporte das transações corresponde à quantidade

total de transações, no caso 10 (dez).

Nas linhas 13 a 15 é feita a expansão das transações em conjuntos menores

formados por todas as combinações de seus elementos com um ou mais elementos. Por

exemplo, a transação

bebida:cafe;bebida:leite;lanche:manteiga;lanche:pao; sup:1

contém quatro elementos e gerará os seguintes conjuntos:

• com um elemento (quatro conjuntos

bebida:cafe; sup:1

bebida:leite; sup:1

lanche:manteiga; sup:1

lanche:pao; sup:1

• com dois elementos (seis conjuntos):

bebida:cafe;bebida:leite; sup:1

bebida:cafe; lanche:manteiga; sup:1

bebida:cafe; lanche:pao; sup:1

bebida:leite;lanche:manteiga; sup:1

bebida:leite; lanche:pao; sup:1

lanche:manteiga;lanche:pao; sup:1

Combinação de n elementos p a p = n! / p! / (n-p)!

• com três elementos (quatro conjuntos):

bebida:cafe;bebida:leite;lanche:manteiga; sup:1

bebida:cafe;bebida:leite; lanche:pao; sup:1

bebida:cafe; lanche:manteiga;lanche:pao; sup:1

bebida:leite;lanche:manteiga;lanche:pao; sup:1

Portanto, após a execução das linhas 13 a 15, a tabela hash conterá a expansão de

todos os conjuntos existentes, ou seja, conterá os seguintes dados:

bebida:cafe; sup:3

bebida:cafe;bebida:leite; sup:1

bebida:cafe;bebida:leite;lanche:manteiga; sup:1

bebida:cafe;bebida:leite;lanche:manteiga;lanche:pao; sup:1

bebida:cafe;bebida:leite;lanche:pao; sup:1

bebida:cafe;lanche:manteiga; sup:3

bebida:cafe;lanche:manteiga;lanche:pao; sup:3

bebida:cafe;lanche:pao; sup:3

bebida:cerveja; sup:2

bebida:cerveja;bebida:leite; sup:1

bebida:cerveja;bebida:leite;lanche:manteiga; sup:1

bebida:cerveja;bebida:leite;lanche:manteiga;lanche:pao; sup:1

bebida:cerveja;bebida:leite;lanche:pao; sup:1

bebida:cerveja;lanche:manteiga; sup:1

bebida:cerveja;lanche:manteiga;lanche:pao; sup:1

bebida:cerveja;lanche:pao; sup:1

bebida:leite; sup:2

bebida:leite;lanche:manteiga; sup:2

bebida:leite;lanche:manteiga;lanche:pao; sup:2

bebida:leite;lanche:pao; sup:2

comida:arroz; sup:2

comida:arroz;comida:feijao; sup:1

comida:feijao; sup:2

lanche:manteiga; sup:5

lanche:manteiga;lanche:pao; sup:4

lanche:pao; sup:5

Os itens com mais de um elemento e que tenham suporte igual ou maior que o

suporte mínimo definido para este problema estão em destaque. São eles:

bebida:cafe;lanche:pao; sup:3

bebida:cafe;lanche:manteiga; sup:3

bebida:cafe;lanche:manteiga;lanche:pao; sup:3

lanche:manteiga;lanche:pao; sup:4

Estes conjuntos são os mesmos que aparecem na FIG. 4.10(b), coluna ITENS L

Estes são os itens selecionados pela linha 17, fazendo com que sejam passados como

parâmetro para a rotina MONTAREGRAS (linha 18), fazendo com que o resultado seja

o mesmo do obtido na execução do algoritmo Apriori (ver seção 4.2.2).

4.3.3. ALGORITMO ASCX-2P

ASCX-2P (IN docXML, restrições, minsup, minconf, maxitens; OUT regras)

1 P = parserXML(docXML)

2 enquanto existe I = P.proximoItem // passo preliminar sobre o

documento

3 caso I.tipo = tagInicial

4 se I definido com raiz da transação

5 incrementa n. de transações

6 caso I.tipo = conteúdo

7 se I selecionado para associação

8 TabHash.inserir (I) // armazena item na tabela hash

9 Calcular transações de suporte mínimo

10 enquanto existe C = TabHash.proximoConjunto

11 marcar conjuntos com item simples que não atendam

suporte mínimo

12 enquanto existe I = P.proximoItem // passo sobre o documento

13 caso I.tipo = tagInicial

14 se I definido como raiz da transação

15 C = ∅

16 caso I.tipo = conteúdo

17 se I selecionado para associação

18 se SUPORTE (I) ≥ minSup

19 C = C + I // insere elemento no conjunto

20 caso I.tipo = tagFinal

21 TabHash.inserir (C) // armazena conjunto na tabela hash

22 enquanto existe C = TabHash.proximoConjunto

23 EXPANDIR (C)

24 enquanto existe C = TabHash.proximoConjunto

25 se SUPORTE(C) ≥ minSup

26 regras = MONTAREGRAS(C)

FIG. 4.14: Algoritmo ASCX-2P

No desenvolvimento do algoritmo ASCX-1P, percebe-se que o único passo sobre o

documento XML acaba por armazenar praticamente uma cópia do documento original

na tabela hash, que, por estar implementada em memória, acaba por otimizar o tempo

de processamento se comparado como o algoritmo Apriori, que realiza várias iterações

sobre os dados em disco.

Pensou-se então em otimizar este algoritmo, realizando um passo preliminar para

determinar os itens elementares cujo suporte atenda ao suporte mínimo definido, e que

serão utilizados no passo seguinte. Neste passo o documento XML original é percorrido,

desta vez só armazenando na tabela hash os conjuntos de itens cujos itens elementares

sejam adequados, isto é, que tenham o valor do suporte igual ou superior ao suporte

mínimo. Este é o conceito principal para o desenvolvimento do algoritmo ASCX-2P

(Associação Sem geração de Candidatos em documentos XML em 2 Passos) exibido na

FIG. 4.14 e descrito com detalhes adiante. Com exceção do passo preliminar, os dois

algoritmos, ASCX-1P e ASCX-2P, são bastante semelhantes.

Os parâmetros de entrada são os mesmos como definidos na seção 4.2.2.

A seguir é apresentada a descrição de cada passo do algoritmo, onde P representa o

objeto criado pelo parser XML que realiza a leitura do documento XML, I cada um dos

itens lidos no documento XML, C o conjunto de elementos definidos para associação e

que são armazenados na tabela hash TabHash.

1 o objeto P do parser XML é inicializado para acesso ao documento XML a ser

processado.

2 PASSO 1: armazena o próximo item de P (documento XML) no item I enquanto

existir item disponível (fim do documento).

3 identifica se o item I é uma marcação (tag) inicial.

4 verifica se I foi selecionado como raiz da associação.

5 incrementa o número de transações.

6 identifica se o item I é um conteúdo delimitado (valor).

7 verifica se o item I está definido para associação.

8 insere o elemento do documento (armazenado no item I) na tabela hash

TabHash e incrementa o contador correspondente de uma unidade (que forma o

suporte do item).

9 calcula o número de transações que correspondem ao suporte mínimo, fazendo o

cálculo do percentual de minsup sobre o número de transações calculados na

linha 5.

10 acesso sequencial a cada conjunto C armazenado na tabela hash TabHash.

11 se o suporte do conjunto C (que só possui elementos simples) é menor que o

suporte mínimo definido, então o valor do suporte é tornado negativo, marcando

assim o conjunto, que não deve mais ser tratado.

12 PASSO 2: armazena o próximo item de P (documento XML) no item I enquanto

existir item disponível (fim do documento).

13 identifica se o item I é uma marcação (tag) inicial.

14 verifica se I foi selecionado como raiz da associação.

15 inicializa o conjunto C de elementos como vazio.

16 identifica se o item I é um conteúdo delimitado (valor).

17 verifica se o item I está definido para associação.

18 verifica se o suporte do conjunto C é maior ou igual ao número de transações

associado ao suporte mínimo (calculado na linha 9).

19 insere o elemento do documento (armazenado no item I) no conjunto C de

elementos da transação.

20 identifica se o item I é uma marcação (tag) final.

21 insere o conjunto C na tabela hash TabHash e incrementa o contador

correspondente de uma unidade (que forma o suporte do conjunto).

22 acesso sequencial a cada conjunto C armazenado na tabela hash TabHash.

23 expandir o conjunto C nos seus vários subconjuntos, que são então adicionados à

tabela hash TabHash.

24 acesso sequencial a cada conjunto C armazenado na tabela hash TabHash.

25 verifica se o suporte do conjunto C é maior ou igual ao número de transações

associado ao suporte mínimo (calculado na linha 9).

26 os elementos de C são distribuídos em dois grupos, que poderão formar o

antecedente e o consequente da regra; é calculada a confiança de cada regra

gerada pelas combinações de antecedente e consequente que podem ser

formados; as restrições informadas são obedecidas para a formação das regras.

A rotina EXPANDIR (linha 23) obtém todos os subconjuntos de C com mais de um

elemento e armazena na tabela hash TabHash, adicionando o suporte de C a cada

elemento armazenado.

A rotina MONTAREGRAS (linha 26) cria as regras para cada conjunto C da tabela

hash TabHash, obedecendo aos critérios:

• verifica se os itens têm restrições quanto à posição que ocuparão na regra

(antecedente e/ou consequente)

• verifica se a confiança da regra é igual ou superior à confiança mínima definida;

caso não seja, a regra é descartada; a confiança é calculada com base no suporte

de cada subconjunto estabelecido como antecedente e consequente armazenados

na tabela hash TabHash.

Um exemplo de execução do algoritmo ASCX-2P é apresentado a seguir. Os

resultados são obtidos pela aplicação do algoritmo sobre o documento XML da FIG. 4.3,

cuja estrutura está descrita na FIG. 4.5, considerando os seguintes parâmetros:

• raiz: mercado

• elementos para associação:

- mercado/bebida: antecedente e consequente

- mercado/comida: antecedente e consequente

- mercado/lanche: antecedente e consequente

• minsup=30% (3 transações)

• minconf=80%

• maxitens: 3

Observe que é mantida a ordem lexicográfica dos itens, o que também é feito na

implementação.

A tabela hash após a execução das linhas 2 a 8, que correspondem ao PASSO 1,

apresenta os seguinte conteúdo:

bebida:cafe; sup:3

bebida:cerveja; sup:2

bebida:leite; sup:2

comida:arroz; sup:2

comida:feijao; sup:2

lanche:manteiga; sup:5

lanche:pao; sup:5

Estes itens correspondem a todos os itens existentes no documento XML e o suporte

corresponde ao número de ocorrências de cada um deles.

A tabela hash após a execução das linhas 10 e 11 é:

bebida:cafe; sup:3

bebida:cerveja; sup:-1 

bebida:leite; sup:-1 

comida:arroz; sup:-1 

comida:feijao; sup:-1 

lanche:manteiga; sup:5

lanche:pao; sup:5

Pode-se observar que o suporte dos itens que não atendem o suporte mínimo são

alterados para "-1", marcando assim os itens que não devem ser tratados no restante do

algoritmo.

A tabela hash após a execução das linhas 12 a 21, que correspondem ao PASSO 2,

apresenta os seguinte conteúdo:

bebida:cafe; sup:3

bebida:cafe;lanche:manteiga;lanche:pao; sup:3

bebida:cerveja; sup:-1

bebida:leite; sup:-1

comida:arroz; sup:-1

comida:feijao; sup:-1

lanche:manteiga; sup:5

lanche:manteiga;lanche:pao; sup:1

lanche:pao; sup:5

Os itens em destaque (negrito) correspondem aos conjuntos associados às

transações observadas no documento XML, mas somente com itens que atendam ao

suporte mínimo, onde podemos observar que existem três transações com um tipo de

combinação de itens e apenas uma transação com uma outra combinação. Somente estes

dois conjuntos serão tratados pelo algoritmo nas linhas 22 e 23, gerando a tabela hash

TabHash com o seguinte conteúdo:

bebida:cafe; sup:3

bebida:cafe;lanche:manteiga; sup:3 

bebida:cafe;lanche:manteiga;lanche:pao; sup:3 

bebida:cafe;lanche:pao; sup:3 

bebida:cerveja; sup:-1

bebida:leite; sup:-1

comida:arroz; sup:-1

comida:feijao; sup:-1

lanche:manteiga; sup:5

lanche:manteiga;lanche:pao; sup:4 

lanche:pao; sup:5

Podemos observar que a rotina EXPANDIR (linha 23) acabou por incluir dois

novos conjuntos à tabela hash TabHash (destaque em negrito) - cujos suportes

atendem ao suporte mínimo definido! - e alterar o suporte de um outro conjunto já

existente (também em negrito).

Temos então quatro conjuntos com mais de um elemento e que têm o valor do

suporte que atendem ao suporte mínimo. São eles:

bebida:cafe;lanche:manteiga; sup:3

bebida:cafe;lanche:manteiga;lanche:pao; sup:3

bebida:cafe;lanche:pao; sup:3

lanche:manteiga;lanche:pao; sup:4

Estes conjuntos são os mesmos encontrados na execução do algoritmo Apriori e do

algoritmo ASCX-1P e que são passados como parâmetros para a rotina

MONTAREGRAS (linha 26) durante a execução das linhas 24 a 26. Deste modo, temos

que as regras geradas são as mesmas que as geradas por aqueles algoritmos.

4.3.4. ALGORITMO ASCX-1PG

O algoritmo ASCX-1PG (Associação Sem geração de Candidatos em documentos

XML - 1 Passo - regras Generalizadas) é uma extensão do algoritmo ASCX-1P (ver

seção 4.3.2) para geração de regras de associação generalizada.

As alterações feitas no algoritmo ASCX-1PG em relação ao algoritmo ASCX-1P

são destacadas na FIG. 4.15 (negrito): adição das linhas 12a e 12b e alteração na rotina

EXPANDIR (linha 15).

ASCX-1PG (IN docXML, restrições, minsup, minconf, maxitens; OUT regras)

1 P = parserXML(docXML)

2 enquanto existe I = P.proximoItem //passo sobre o documento

3 caso I.tipo = tagInicial

4 se I definido como raiz da transação

5 incrementa n. de transações

6 C = ∅

7 caso I.tipo = conteúdo

8 se I definido para associação

9 C = C + I //insere elemento no conjunto

10 caso I.tipo = tagFinal

11 TabHash.inserir (C) // armazena conjunto na tabela hash

12 Calcular transações de suporte mínimo

12a enquanto existe C = TabHash.proximoConjunto

12b adiciona a C os caminhos de (ci ∈

∈∈

∈ C)

13 enquanto existe C = TabHash.proximoConjunto

14 TabHash.inserir (ci ∈ C) // armazena itens elementares

15 EXPANDIR (C)

16 enquanto existe C = TabHash.proximoConjunto

17 se SUPORTE(C) ≥ minSup

18 regras = MONTAREGRAS(C)

FIG. 4.15: Algoritmo ASCX-1PG

Como as demais linhas do algoritmo permanecem inalteradas, segue uma descrição

somente das linhas que foram modificadas:

12a acesso sequencial a cada conjunto C armazenado na tabela hash TabHash.

12b adição dos caminhos dos itens ao conjunto C, sem duplicidade (considerando a

taxonomia definida implicitamente no documento XML).

15 a rotina EXPANDIR foi alterada de modo a não gerar conjuntos que contenha

algum item que seja o caminho de qualquer outro item do mesmo conjunto

;

por exemplo, o conjunto contendo bebida e bebida:café não é gerado, pois o primeiro item é

um caminho do segundo.

100

esta condição evita a criação de conjuntos que não sejam úteis para a geração de

regras.

Um exemplo de execução do algoritmo ASCX-1PG é apresentado a seguir. Os

resultados são obtidos pela aplicação do algoritmo sobre o documento XML da FIG.

4.15, cuja estrutura está descrita na FIG. 4.5, considerando os seguintes parâmetros:

• raiz: mercado

• elementos para associação:

- mercado/bebida: antecedente e consequente

- mercado/comida: antecedente e consequente

- mercado/lanche: antecedente e consequente

• minsup=30% (3 transações)

• minconf=80%

• maxitens: 3

Observe que é mantida a ordem lexicográfica dos itens, o que também é feito na

implementação.

A tabela hash após a execução das linhas 2 a 11 é:

bebida:cafe;bebida:leite;lanche:manteiga;lanche:pao; sup:1

bebida:cafe;lanche:manteiga;lanche:pao; sup:2

bebida:cerveja; bebida:leite;lanche:manteiga;lanche:pao; sup:1

bebida:cerveja; sup:1

comida:arroz; sup:1

comida:arroz;comida:feijao; sup:1

comida:feijao; sup:1

lanche:manteiga; sup:1

lanche:pao; sup:1

Os conjuntos armazenados correspondem às transações no documento XML, sendo

que a soma dos suportes é igual ao total de transações, do mesmo modo como ocorre na

execução do algoritmo ASCX-1P.

Após a execução das linhas 12a e 12b, a principal alteração do algoritmo ASCX-

1PG em relação ao algoritmo ASCX-1P, a tabela hash apresenta os seguintes itens:

101

bebida;bebida:cafe;bebida:leite;lanche;lanche:manteiga;

lanche:pao; sup:1

bebida;bebida:cafe;lanche;lanche:manteiga;lanche:pao; sup:2

bebida;bebida:cerveja; sup:1

bebida;bebida:cerveja;bebida:leite;lanche;lanche:manteiga;

lanche:pao; sup:1

comida;comida:arroz; sup:1

comida;comida:arroz;comida:feijao; sup:1

comida;comida:feijao; sup:1

lanche;lanche:manteiga; sup:1

lanche;lanche:pao; sup:1

Podemos perceber que os caminhos dos itens (destacados em negrito) foram

adicionados aos itens da tabela hash.

Após a execução das linhas 13 a 15, a tabela hash contém os seguintes dados:

bebida:cafe; sup:3

bebida:cafe;bebida:leite; sup:1

bebida:cafe;bebida:leite;lanche:manteiga; sup:1

bebida:cafe;bebida:leite;lanche:manteiga;lanche:pao; sup:1

bebida:cafe;bebida:leite;lanche:pao; sup:1

bebida:cafe;bebida:leite;lanche; sup:1

bebida:cafe;lanche:manteiga; sup:3

bebida:cafe;lanche:manteiga;lanche:pao; sup:3

bebida:cafe;lanche:pao; sup:3

bebida:cafe;lanche; sup:3

bebida:cerveja; sup:2

bebida:cerveja;bebida:leite; sup:1

bebida:cerveja;bebida:leite;lanche:manteiga; sup:1

bebida:cerveja;bebida:leite;lanche:manteiga;lanche:pao; sup:1

bebida:cerveja;bebida:leite;lanche:pao; sup:1

bebida:cerveja;bebida:leite;lanche; sup:1

bebida:cerveja;lanche:manteiga; sup:1

bebida:cerveja;lanche:manteiga;lanche:pao; sup:1

bebida:cerveja;lanche:pao; sup:1

bebida:cerveja;lanche; sup:1

bebida:leite; sup:2

bebida:leite;lanche:manteiga; sup:2

bebida:leite;lanche:manteiga;lanche:pao; sup:2

bebida:leite;lanche:pao; sup:2

bebida:leite;lanche; sup:2

bebida; sup:5

bebida;bebida:cafe;bebida:leite;lanche;lanche:manteiga;

lanche:pao; sup:1

bebida;bebida:cafe;lanche;lanche:manteiga;lanche:pao; sup:2

bebida;bebida:cerveja; sup:1

bebida;bebida:cerveja;bebida:leite;lanche;lanche:manteiga;

lanche:pao; sup:1

bebida;lanche:manteiga; sup:4

bebida;lanche:manteiga;lanche:pao; sup:4

bebida;lanche:pao; sup:4

bebida;lanche; sup:4

comida:arroz; sup:2

(CONTINUA)

102

(CONTINUAÇÃO)

comida:arroz;comida:feijao; sup:1

comida:feijao; sup:2

comida; sup:3

comida;comida:arroz; sup:1

comida;comida:arroz;comida:feijao; sup:1

comida;comida:feijao; sup:1

lanche:manteiga; sup:5

lanche:manteiga;lanche:pao; sup:4

lanche:pao; sup:5

lanche; sup:6

lanche;lanche:manteiga; sup:1

lanche;lanche:pao; sup:1

Os itens com mais de um elemento e que tenham suporte igual ou maior que o

suporte mínimo definido para este problema estão em destaque. São eles:

bebida:cafe;lanche:manteiga; sup:3

bebida:cafe;lanche:manteiga;lanche:pao; sup:3

bebida:cafe;lanche:pao; sup:3

bebida:cafe;lanche; sup:3

bebida;lanche:manteiga; sup:4

bebida;lanche:manteiga;lanche:pao; sup:4

bebida;lanche:pao; sup:4

bebida;lanche; sup:4

lanche:manteiga;lanche:pao; sup:4

Estes conjuntos são os mesmos que aparecem na FIG. 4.12(b), coluna ITENS L

Estes são os itens selecionados pela linha 17, que são passados como parâmetro para a

rotina MONTAREGRAS (linha 18), fazendo com que o resultado seja o mesmo do

obtido na execução do algoritmo AprioriG (ver seção 4.2.3).

4.3.5. ALGORITMO ASCX-2PG

O algoritmo ASCX-2PG (Associação Sem geração de Candidatos em documentos

XML - 2 Passos - regras Generalizadas) é uma extensão do algoritmo ASCX-2P (ver

seção 4.3.3) para geração de regras de associação generalizada.

As alterações feitas no algoritmo ASCX-2PG em relação ao algoritmo ASCX-2P

são destacadas na FIG. 4.16 (em negrito): alteração da linha 8, adição das linhas 8a, 8b e

20a e alteração na rotina EXPANDIR (linha 26).

103

ASCX-2PG (IN docXML, restrições, minsup, minconf, maxitens; OUT regras)

1 P = parserXML(docXML)

2 enquanto existe I = P.proximoItem //passo preliminar sobre o

documento

3 caso I.tipo = tagInicial

4 se I definido com raiz da transação

5 incrementa n. de transações

6 caso I.tipo = conteúdo

7 se I selecionado para associação

8 C = C + I //insere elemento no conjunto

8a caso I.tipo = tagFinal

8b EXPANDIR (C)

9 Calcular transações de suporte mínimo

10 enquanto existe C = TabHash.proximoConjunto

11 marcar conjuntos com item simples que não atendam

suporte mínimo

12 enquanto existe I = P.proximoItem // passo sobre o documento

13 caso I.tipo = tagInicial

14 se I definido como raiz da transação

15 C = ∅

16 caso I.tipo = conteúdo

17 se I selecionado para associação

18 se SUPORTE (I) ≥ minSup

19 C = C + I //insere elemento no conjunto

19a C = C + caminhos de I //insere caminhos no conj.

20 caso I.tipo = tagFinal

21 TabHash.inserir (C) // armazena conjunto na tabela hash

22 enquanto existe C = TabHash.proximoConjunto

23 EXPANDIR (C)

24 enquanto existe C = TabHash.proximoConjunto

25 se SUPORTE(C) ≥ minSup

26 regras = MONTAREGRAS(C)

FIG. 4.16: Algoritmo ASCX-2PG

Como as demais linhas do algoritmo permanecem inalteradas, segue uma descrição

somente das linhas que foram modificadas:

104

8 insere o elemento do documento (armazenado no item I) no conjunto C de

elementos da transação.

8a identifica se o item I é uma marcação (tag) final.

8b expande o conjunto C nos seus vários subconjuntos, que são então adicionados à

tabela hash TabHash.

19a insere os caminhos do elemento do documento (armazenado no item I) no

conjunto C de elementos da transação.

23 a rotina EXPANDIR foi alterada de modo a não gerar conjuntos que contenha

algum item que seja o caminho de qualquer outro item do mesmo conjunto

;

esta condição evita a criação de conjuntos que não sejam úteis para a geração de

regras

Um exemplo de execução do algoritmo ASCX-2PG é apresentado a seguir. Os

resultados são obtidos pela aplicação do algoritmo sobre o documento XML da FIG. 4.3,

cuja estrutura está descrita na FIG. 4.5, considerando os seguintes parâmetros:

• raiz: mercado

• elementos para associação:

- mercado/bebida: antecedente e consequente

- mercado/comida: antecedente e consequente

- mercado/lanche: antecedente e consequente

• minsup=30% (3 transações)

• minconf=80%

• maxitens: 3

Observe que é mantida a ordem lexicográfica dos itens, o que também é feito na

implementação.

A tabela hash após a execução das linhas 2 a 8b, que correspondem ao PASSO 1,

apresenta o seguinte conteúdo:

ver nota 47 na pág. 99

105

bebida; sup:5

bebida:cafe; sup:3

bebida:cerveja; sup:2

bebida:leite; sup:2

comida; sup:3

comida:arroz; sup:2

comida:feijao; sup:2

lanche; sup:6

lanche:manteiga; sup:5

lanche:pao; sup:5

Estes itens correspondem a todos itens existentes no documento XML com

respectivos caminhos e o suporte corresponde ao número de ocorrências de cada um

deles.

A tabela hash após a execução das linhas 11 e 12 é:

bebida; sup:5

bebida:cafe; sup:3

bebida:cerveja; sup:-1

bebida:leite; sup:-1

comida; sup:3

comida:arroz; sup:-1

comida:feijao; sup:-1

lanche; sup:6

lanche:manteiga; sup:5

lanche:pao; sup:5

Pode-se observar que o suporte dos itens que não atendem o suporte mínimo são

alterados para "-1", marcando assim os itens que não devem ser tratados no restante do

algoritmo.

A tabela hash após a execução das linhas 12 a 21, que correspondem ao PASSO 2,

apresenta os seguinte conteúdo:

bebida; sup:5

bebida:cafe; sup:3

bebida:cafe;lanche:manteiga;lanche:pao; sup:3

bebida:cerveja; sup:-1

bebida:leite; sup:-1

bebida;lanche:manteiga;lanche:pao; sup:1

comida; sup:3

comida:arroz; sup:-1

comida:feijao; sup:-1

lanche; sup:6

lanche:manteiga; sup:5

lanche:pao; sup:5

Os itens em destaque (negrito) correspondem aos conjuntos associados às

transações observadas no documento XML, mas somente com itens que atendam ao

suporte mínimo, onde podemos observar que existem três transações com um tipo de

106

combinação de itens e apenas uma transação com uma outra combinação - neste grupo é

considerado apenas o caminho (taxonomia) de um dos itens que atendem ao suporte

mínimo. Somente estes dois conjuntos serão tratados pelo algoritmo nas linhas 22 e 23,

gerando a tabela hash TabHash com o seguinte conteúdo:

bebida; sup:5

bebida;lanche; sup:4

bebida;lanche:manteiga; sup:4

bebida;lanche:manteiga;lanche:pao; sup:4

bebida;lanche:pao; sup:4

bebida:cafe; sup:3

bebida:cafe;lanche; sup:3

bebida:cafe;lanche:manteiga; sup:3

bebida:cafe;lanche:manteiga;lanche:pao; sup:3

bebida:cafe;lanche:pao; sup:3

bebida:cerveja; sup:-1

bebida:leite; sup:-1

comida; sup:3

comida:arroz; sup:-1

comida:feijao; sup:-1

lanche; sup:6

lanche:manteiga; sup:5

lanche:manteiga;lanche:pao; sup:4

lanche:pao; sup:5

Podemos observar que a rotina EXPANDIR (linha 23) acabou por incluir seis

novos conjuntos à tabela hash TabHash (em negrito) - cujos suportes atendem ao

suporte mínimo definido! - e alterar o suporte de um outro conjunto já existente

(também em negrito).

Considerando os dois itens existentes e que não foram alterados, temos nove

conjuntos com mais de um elemento e que têm o valor do suporte que atendem ao

suporte mínimo. São eles:

bebida;lanche; sup:4

bebida;lanche:manteiga; sup:4

bebida;lanche:manteiga;lanche:pao; sup:4

bebida;lanche:pao; sup:4

bebida:cafe;lanche; sup:3

bebida:cafe;lanche:manteiga; sup:3

bebida:cafe;lanche:manteiga;lanche:pao; sup:3

bebida:cafe;lanche:pao; sup:3

lanche:manteiga;lanche:pao; sup:4

Estes conjuntos são os mesmos encontrados na execução do algoritmo AprioriG e

do algoritmo ASCX-1PG e que são passados como parâmetros para a rotina

MONTAREGRAS (linha 26) durante a execução das linhas 24 a 26. Deste modo, temos

que as regras geradas são as mesmas que as geradas por aqueles algoritmos.

107

4.3.6. COMPARAÇÃO COM OUTRAS ABORDAGENS

Os trabalhos de geração de regras de associação em documentos XML observados

(BRAGA, CAMPI, KLEMETTINEN, LANZI, 2002) (BRAGA, CAMPI, STEFANO,

KLEMETTINEN, LANZI, 2002a) (DING, RICORDS, LUMPKIN, 2003) se baseiam

no pré-processamento do documento XML, quando os seus dados são transformados no

formato basket (armazenado num banco de dados relacional), sobre os quais é então

aplicado o algoritmo Apriori. Este procedimento é o mesmo adotado na implementação

neste trabalho de regras de associação em documento XML, abordagem clássica (ver

seção 4.2).

Como é conhecido, o algoritmo Apriori se baseia na geração de conjuntos

candidatos para determinar o valor do suporte e confiança dos conjuntos de dados, o que

é um processo que demanda muito processamento.

Por sua vez, os trabalhos sobre regras de associação sem geração de conjuntos

candidatos são todos aplicados a bancos de dados relacionais (HAN, PEI, YIN, 2000)

(CHEUNG, ZAIANE, 2003), e, até onde nos foi possível perceber, não existem

trabalhos similares para descoberta de associação em documentos XML.

No capítulo 5 são apresentados os experimentos comparativos, onde se percebe que

a abordagem proposta (algoritmo ASCX-2P) apresenta desempenho superior quando

comparada com a abordagem tradicional.

4.3.7. CONSIDERAÇÕES COMPLEMENTARES

Observamos que o conceito comum aos novos algoritmos para associação em

documentos XML, isto é, o processamento em um ou dois passos sobre os dados, pode

ser estendido para aplicação em bancos de dados relacionais, bastando para isso serem

adaptadas as partes dos algoritmos que se referem à obtenção dos dados propriamente

dita, o que é feito neste trabalho pelas APIs específicas para processamento de

documentos XML (LibXmlParser, ver ANEXO 3 seção 1).

108

4.4. CLASSIFICAÇÃO EM DOCUMENTOS XML

4.4.1. CONSIDERAÇÕES INICIAIS

Em geral, a classificação de dados compreende duas etapas distintas (ver seção

2.3.4): na primeira, denominada aprendizado, é identificada uma função que aproxime

uma função (desconhecida) que mapeie os dados de um conjunto de treinamento em

classes pré-definidas. Na segunda etapa, denominada etapa de testes, a função

identificada é aplicada sobre os dados que se deseja classificar. Existem diferentes

técnicas para identificação da função de classificação. Uma delas é a técnica de

classificação baseada em regras de associação, onde a função identificada é

representada pelas regras de associação geradas sobre o mesmo conjunto de treinamento

(ver seção 2.3.5).

A função identificada como descrito acima pode ser representada por regras de

associação obtidas sobre um conjunto de treinamento, em que os atributos que

funcionarão como classe são definidos com restrição do algoritmo de geração como

somente consequente das regras, enquanto os demais atributos só podem aparecer como

antecedentes nestas mesmas regras, ou seja:

(classificação → associação)

classe → consequente

atributos → antecedentes

A classificação em documentos XML adotada neste trabalho é feita então pela

geração de regras de associação a partir de um documento XML (conjunto de

treinamento), obtendo assim o classificador como conceituado na seção 2.3.4. Este

classificador pode então ser aplicado sobre novas transações armazenadas num novo

documento XML, classificando-as. Durante a geração das regras que formarão o

classificador, o algoritmo considera um único atributo identificado como consequente

da regra, enquanto que os demais atributos são definidos como antecedentes das regras a

serem geradas (ver seção 4.1.5).

109

4.4.2. ALGORITMOS DE CLASSIFICAÇÃO

Os algoritmos de classificação em documentos XML implementados neste trabalho

são adaptações dos algoritmos de descoberta de associação descritos anteriormente,

executados a partir das seguintes restrições (ver seção 4.1.5):

• definição de elementos somente como antecedentes das regras; e

• definição de um único elemento como consequente da regra; este elemento

corresponde ao atributo objetivo (classe) da tarefa de classificação existente no

documento XML.

Adicionalmente é necessário identificar a classe default (ver seção 2.3.5), que é a

classe mais frequente no conjunto de treinamento.

FIG. 4.17: Esquema de classificação baseada em regras de associação

Com o conjunto de regras obtido com o algoritmo de geração de regras de

associação, a classificação de uma transação (seção 4.1.5) de um documento XML

selecionada compreende identificar a melhor regra cujos elementos (selecionados como

antecedentes) são contemplados na regra. Para isso, as regras são ordenadas de acordo

com um critério definido mais à frente. Caso nenhuma regra seja selecionada, então a

classe default é atribuída à transação.

O esquema do processo completo de classificação é descrito na FIG. 4.17.

110

É importante enfatizar que o componente "algoritmo de associação" da FIG. 4.17

pode assumir qualquer uma das seguintes implementações:

a) Apriori: caracteriza-se, neste caso, a abordagem tradicional de classificação em

documentos XML baseada em regras de associação; a este método

denominaremos CApriori.

b) ASCX-1P: caracteriza-se, neste caso, a abordagem proposta de classificação em

documentos XML baseada em regras de associação sem geração de candidatos

em 1 passo; a esta abordagem denominaremos CASCX-1P.

c) ASCX-2P: caracteriza-se, neste caso, a abordagem proposta de classificação em

documentos XML baseada em regras de associação sem geração de candidatos

em 2 passos; a esta abordagem denominaremos CASCX-2P.

As regras do classificador são ordenadas do seguinte modo:

• caso não seja selecionada a opção de regras de associação generalizadas:

• as regras são ordenadas de acordo com o valor da confiança;

• caso os valores das confianças sejam idênticos, as regras são ordenadas de

acordo com o valor do suporte;

• caso ambos valores de confiança e suporte sejam idênticos, então as regras

são ordenadas de acordo com o número de itens que a formam (a regra com

um número menor de elementos fica à frente da outra) - Princípio da Menor

Descrição (MDL - Minimum Description Length).

• caso nenhuma condição seja atendida, é mantida a ordem em que a regra foi

gerada.

• caso seja selecionada a opção de regras de associação generalizadas:

• as regras são classificadas de acordo com o número de "caminhos" existentes

na regra, tanto como antecedente quanto como consequente; deste modo as

regras generalizadas são posicionadas no fim da lista de regras a serem

avaliadas pelo classificador.

• caso as regras tenham a mesma quantidade de "caminhos", elas são ordenadas

de acordo com os mesmos critérios definidos anteriormente, ou seja, de

acordo com:

111

• valor da confiança;

• valor do suporte;

• número de itens da regra;

A acurácia do classificador assim construído é obtida submetendo-se um

documento XML (conjunto de teste) com classes conhecidas, que são então comparadas

com as classes identificadas (ou inferidas) pelo classificador (ver seção 2.3.5).

4.4.3. COMPARAÇÃO COM OUTRAS ABORDAGENS

O único trabalho de classificação de documentos XML que nos foi possível

perceber (ZAKI, AGGARRWAL, 2003) utiliza a abordagem do método CApriori e, na

verdade compreende a classificação de transações que registram a sequência de sites

visitados por um usuário, o que é feito num histórico (log) no formato XML. Esta

sequência pode ser representada por uma árvore, que se assemelha à representação de

uma estrutura hierárquica. (ZAKI, AGGARRWAL, 2003) utiliza uma lista dos "nós" da

árvore obtida percorrendo-a em pré-ordem, sendo os sites identificados por números.

Por exemplo (ZAKI, 2002):

• a sequência 0, 1, 3, 1, -1, 2, -1, -1, 2, -1, -1, 2, -1 compreende o acesso, na ordem,

aos sites 0, 1, 3, 1, 3, 2, 1, 2, 0, 2 o que pode ser representado pela seguinte

árvore:

_0_

/ \

1 2

/ \ /

3 2

/ \ /

1 2

/ /

112

• a sequência 0, 1, -1, 2, -1, 2, -1, 2, -1 compreende o acesso, na ordem, aos sites 0,

1, 0, 2, 0, 2, 0, 2, o que pode ser representado pela seguinte árvore:

__0__

/ / \ \

1 2 2 2

/ / / /

Nestes exemplos, as classes correspondem a usuários associados a sites estudantis

(classe 0) e de sites "não-estudantis" (classe 1).

Convém ressaltar que a aplicação exposta em (ZAKI, AGGARRWAL, 2003)

também pode ser tratada pelas abordagens dos algoritmos CApriori, CASCX-1P ou

CASCX-2P.

Os métodos CASCX-1P e CASCX-2P, semelhante aos seus duais ASCX-1P e

ASCX-2P, procuram otimizar o desempenho das respectivas abordagens clássicas,

CApriori e Apriori.

4.4.4. CONSIDERAÇÕES COMPLEMENTARES

A classificação baseada em regras de associação consegue explicitar o

conhecimento gerado de uma forma legível, se assemelhando, por exemplo, à

classificação por árvores de decisão (QUINLAN , 1993), ao contrário de redes neurais,

uma das técnicas mais aplicadas na tarefa de classificação, onde o conhecimento obtido

é expresso através de uma função (representada pelos pesos atribuídos às "sinapses" do

modelo), quando não fica claro o conhecimento representado. Por este motivo, a

classificação baseada em regras de associação se mostra bastante útil.

Este trabalho não aprofunda os estudos sobre a aplicação de geração de regras de

associação generalizada para uso em classificação, o que, certamente, pode ser feito em

estudos futuros.

113

5. PROTÓTIPOS, EXPERIMENTOS E RESULTADOS

5.1. CONSIDERAÇÕES INICIAIS

5.1.1. AMBIENTE DE DESENVOLVIMENTO E DE TESTES

As implementações deste trabalho foram feitas utilizando o ambiente de

desenvolvimento Delphi versão 5, da Borland (http://www.borland.com/delphi) no

ambiente Windows, da Microsoft (http://www.microsoft.com/windows).

Para o tipo de processamento proposto neste trabalho mostrou ser viável a

utilização de API SAX (ver seção 2.1.6), sendo escolhida a implementação

LibXmlParser, desenvolvida por Stefan Heymann e disponibilizada para uso gratuito

(http://www.destructor.de). O procedimento completo para instalação e uso deste

ambiente está descrito no ANEXO 3.

Nos algoritmos propostos foi utilizada uma tabela hash, implementada através de

uma API disponível para uso gratuito (http://www.softcomplete.com) denominada

HASHTRIE. Esta API implementa uma tabela hash com estrutura em árvore, cujos

procedimentos para instalação e uso também estão descritos no ANEXO 3.

Como a implementação do algoritmo Apriori considera os dados armazenados no

formato basket numa tabela armazenada num banco de dados relacional, a eficiência do

algoritmo depende da eficiência do banco de dados utilizado. No trabalho foram

utilizados dois tipos de bancos de dados:

• Paradox: banco de dados simples, instalado juntamente com o Delphi;

armazena os dados em arquivos que são armazenados num diretório, tendo este

diretório o tratamento de banco de dados (por armazenar um conjunto de tabelas).

• Interbase: banco de dados completo, que é fornecido no pacote de instalação

do Delphi, mas que deve ser instalado separadamente (versão local).

114

O acesso ao banco de dados Paradox foi utilizado apenas por se tratar de uma

opção mais simples, permitindo assim que o protótipo possa ser utilizado em ambientes

com menos recursos, o que pode ser uma opção interessante. No entanto, nos testes,

somente foi feita a avaliação do algoritmo Apriori utilizando o banco de dados

Interbase, que apresenta um desempenho geral bem superior ao Paradox.

Utilizou-se para os testes um microcomputador HP-Pavilion ze4600 com a

seguinte configuração:

• processador AMD Athlon 2.0 GHz.

• memória RAM: 512 Mbytes; e

• disco rígido de 40 Gbytes;

• Windows XP.

5.1.2. SELEÇÃO DOS DOCUMENTOS

Uma dificuldade encontrada na escolha dos documentos XML a serem utilizados na

avaliação dos algoritmos, foi a ausência de documentos de referência (benchmark) para

este objetivo. Os documentos utilizados neste trabalho estão disponíveis no site

XMLData Repository (http://www.cs.washington.edu/research/xmldatasets),

mantido pelo Database Group da University of Washington

(http://www.cs.washington.edu e http://data.cs.washington.edu/).

As seguintes características foram consideradas na escolha dos documentos:

• número de transações: número total de transações em relação ao elemento

definido como raiz (ver seção 4.1.5);

• quantidade de valores diferentes nos itens do documento

• número médio de atributos por transação.

O número de itens por transação pode variar quando o documento contém algum

item selecionado para associação que seja múltiplo (ver seção 4.1.3) ou sub-elemento de

algum item múltiplo. Em caso contrário este valor é fixo e igual ao número de itens

selecionados para associação.

115

A estrutura geral documento (esquema) não foi considerada relevante, pois os

algoritmos conseguem trabalhar sobre qualquer estrutura de documento XML.

Para os testes de classificação foram selecionados alguns documentos entre os

utilizados nos testes de associação, onde é necessária a existência de pelo menos um

elemento categórico que foi então utilizado nos testes como classe (atributo categórico).

5.2. DESCOBERTA DE REGRAS DE ASSOCIAÇÃO EM DOCUMENTOS

XML

5.2.1. METODOLOGIA DE TESTES

Os seguintes algoritmos para descoberta de regras de associação em documentos

XML foram avaliados:

• Apriori: implementação clássica para descoberta de regras de associação (ver

seção 4.2.2);

• ASCX-1P: implementação do algoritmo proposto neste trabalho para geração de

regras de associação em 1 passagem sobre o documento XML (ver seção 4.3.2);

• ASCX-2P: implementação do algoritmo proposto neste trabalho para geração de

regras de associação em 2 passagens sobre o documento XML (ver seção 4.3.3).

Como os algoritmos são todos determinísticos e produzem os mesmos resultados

quando utilizados sob as mesmas condições, procurou-se comparar o desempenho deles,

medido em termos de tempo de processamento.

Os seguintes parâmetros foram configurados para a execução dos algoritmos:

• suporte mínimo (%): foram utilizados dois valores diferentes para cada conjunto

de dados, referenciados como "suporte mínimo baixo" (SB) e "suporte mínimo

alto" (SA);

116

• confiança mínima (%): foram utilizados os valores de 70% e 90% para todas as

bases de dados, referenciados como "confiança mínima baixa" (CB) e "confiança

mínima alta" (CA);

• número máximo de itens: valor fixado em 3 para todas as bases de dados.

Cada base de dados foi então testada com um dado algoritmo em quatro situações

diferentes, correspondendo às combinações possíveis dos valores diferentes que os

parâmetros acima podem assumir (dois valores de suporte mínimo e dois de confiança

mínima).

O número máximo de itens tem como objetivo evitar o processamento para geração

de regras a partir de um conjunto com uma quantidade elevada de itens, o que

normalmente gera regras pouco importantes. Por este motivo, optou-se em definir um

valor pequeno para este parâmetro.

5.2.2. TESTES REALIZADOS E RESULTADOS OBTIDOS

Os seguintes documentos XML foram utilizados nos testes (ver seção 5.1.2):

• orders.xml: descrição de pedidos

(http://www.cs.washington.edu/research/xmldatasets/ data/tpc-h/orders.xml)

• _orders.xml: documento orders.xml com tamanho reduzido

• ebay.xml: dados de operações realizadas no site de leilões EBay

(http://www.cs.washington.edu/research/xmldatasets/data/auctions/ebay.xml)

• part.xml: descrição de partes de pedidos (http://www.cs.washington.edu/research/

xmldatasets/data/tpc-h/part.xml)

• _part.xml: documento part.xml com tamanho reduzido

• SigmodRecord.xml: versão em XML do índice de artigos da ACM SIGMOD

(Association Computing Machinery - Special Interest Group on Management of

Data) (http://www.cs.washington.edu/research/xmldatasets/data/sigmod-record/

SigmodRecord.xml)

• _SigmodRecord.xml: documento SigmodRecord.xml com tamanho reduzido

117

• uwm.xml: cursos oferecidos pela University of Wisconsin-Milwaukee (UWM)

(http://www.cs.washington.edu/research/xmldatasets/data/courses/uwm.xml)

• _uwm.xml: documento uwm.xml com tamanho reduzido

• mercado.xml: arquivo criado para utilização nos exemplos deste trabalho - ver

FIG. 4.3

Segue-se uma estatística das propriedades destes arquivos:

documento A B C

1 orders.xml

15.000 34.414 8

2 _orders.xml

152 738 8

3 ebay.xml

5 36 10

4 part.xml

2.000 6.788 9

5 _part.xml

133 722 9

6 SigmodRecord.xml

67 1.029 46,9

7 _SigmodRecord.xml

22 389 27,6

8 uwm.xml

2.112 2.619 10,9

9 _uwm.xml

90 257 14

10 mercado.xml

10 7 2,1

Onde:

A - número de transações;

B - quantidade de valores diferentes que aparecem combinados nas transações;

C - número médio de atributos por transação

Estas características foram escolhidas por retratarem, de um modo geral, o tamanho

dos documentos.

Como descrito anteriormente (ver seção 5.2.1), para cada documento foram

utilizados dois valores de confiança mínima diferentes:

o tamanho do documento foi reduzido aleatoriamente para gerar outros com características

diferentes.

118

Documento

Suporte

mínimo

1 orders.xml

5% 10%

2 _orders.xml

5% 10%

3 ebay.xml

40%

50%

4 part.xml

2% 4%

5 _part.xml

3% 5%

6 SigmodRecord.xml

15%

20%

7 _SigmodRecord.xml

15%

20%

8 uwm.xml

8% 12%

9 _uwm.xml

15%

20%

10 mercado.xml

20%

30%

Os valores de suporte mínimo utilizados nos testes foram definidos de modo a

fornecerem resultados razoáveis (tempo de processamento e número de regras geradas).

Vale lembrar que foram considerados os valores de confiança mínima de 70% e

90% em todos os testes.

A avaliação dos tempos não levou em consideração o pré-processamento. Por

exemplo, na avaliação do algoritmo Apriori, a contagem do tempo de execução só

começou após a transformação do documento XML no formato basket no banco de

dados relacional.

A FIG. 5.1 mostra uma visão analítica dos resultados obtidos.

FIG. 5.1: Testes dos algoritmos de geração de regras de associação em documentos

XML

Obs.: (1) tempo superior a 1000 s.

; (2) erro causado pelo banco de dados

parâmetros resultados

tempos (s.)

suporte

mínimo

confiança

mínima

total de

regras

geradas

Apriori ASCX-1P ASCX-2P

5% 70% 17 708,0 (1) 2,70

5% 90% 17 728,0 (1) 3,12

10% 70% 8 723,0 (1) 3,16

10% 90% 8 648,0 (1) 3,42

FIG. 5.1(a): Processamento do documento orders.xml

os testes foram interrompidos sempre que o tempo de processamento atingisse 1000 s., tempo que

inviabiliza o algoritmo se comparado com os demais.

erro interno do banco de dados; possivelmente erro causado por necessidade de mais espaço em

memória, mas indiponível (apesar de ser utilizado um micro com 512 Mbytes de memória RAM).

119

parâmetros resultados

tempos (s.)

suporte

mínimo

confiança

mínima

total de

regras

geradas

Apriori ASCX-1P ASCX-2P

5% 70% 17 1,70 1,03 0,11

5% 90% 17 2,00 0,76 0,03

10% 70% 11 3,25 1,09 0,30

10% 90% 11 1,57 1,01 0,08

FIG. 5.1(b): Processamento do documento _orders.xml

parâmetros resultados

tempos (s.)

suporte

mínimo

confiança

mínima

total de

regras

geradas

Apriori ASCX-1P ASCX-2P

40% 70% 185 1,15 0,23 0,06

40% 90% 185 0,36 0,23 0,11

50% 70% 9 1,19 0,23 0,05

50% 90% 9 0,15 0,25 0,05

FIG. 5.1(c): Processamento do documento ebay.xml

parâmetros resultados

tempos (s.)

suporte

mínimo

confiança

mínima

total de

regras

geradas

Apriori ASCX-1P ASCX-2P

2% 70% 25 (2) (1) 0,57

2% 90% 25 418,0 (1) 0,57

4% 70% 13 13,8 (1) 0,40

4% 90% 13 29,6 (1) 0,56

FIG. 5.1(d): Processamento do documento part.xml

parâmetros resultados

tempos (s.)

suporte

mínimo

confiança

mínima

total de

regras

geradas

Apriori ASCX-1P ASCX-2P

3% 70% 18 5,92 1,50 0,05

3% 90% 18 6,21 1,53 0,05

5% 70% 6 2,71 1,56 0,03

5% 90% 6 4,06 1,56 0,02

FIG. 5.1(e): Processamento do documento _part.xml

parâmetros resultados

tempos (s.)

suporte

mínimo

confiança

mínima

total de

regras

geradas

Apriori ASCX-1P ASCX-2P

15% 70% 108 (2) (1) 55,30

15% 90% 60 (2) (1) 22,70

20% 70% 25 (2) (1) 0,57

20% 90% 13 (2) (1) 0,95

FIG. 5.1(f): Processamento do documento SigmodRecord.xml

120

parâmetros resultados

tempos (s.)

suporte

mínimo

confiança

mínima

total de

regras

geradas

Apriori ASCX-1P ASCX-2P

15% 70% 121 83,9 (1) 16,1

15% 90% 80 76,8 (1) 16,9

20% 70% 43 77,0 (1) 0,59

20% 90% 26 75,3 (1) 0,55

FIG. 5.1(g): Processamento do documento _SigmodRecord.xml

parâmetros resultados

tempos (s.)

suporte

mínimo

confiança

mínima

total de

regras

geradas

Apriori ASCX-1P ASCX-2P

8% 70% 42 614,0 (1) 101,0

8% 90% 9 684,0 (1) 148,0

12% 70% 12 598,0 (1) 8,3

12% 90% 2 631,0 (1) 7,8

FIG. 5.1(h): Processamento do documento uwm.xml

parâmetros resultados

tempos (s.)

suporte

mínimo

confiança

mínima

total de

regras

geradas

Apriori ASCX-1P ASCX-2P

15% 70% 23 39,4 (1) 9,78

15% 90% 9 38,2 (1) 9,80

20% 70% 10 37,6 (1) 0,57

20% 90% 2 37,6 (1) 0,60

FIG. 5.1(i): Processamento do documento _uwm.xml

parâmetros resultados

tempos (s.)

suporte

mínimo

confiança

mínima

total de

regras

geradas

Apriori ASCX-1P ASCX-2P

20% 70% 13 0,070 0,050 0,0

20% 90% 10 0,050 0,010 0,0

30% 70% 8 0,040 0,010 0,0

30% 90% 5 0,040 0,0 0,0

FIG. 5.1(j): Processamento do documento mercado.xml

Os tempos observados na execução do algoritmo ASCX-1P foram muito superiores

aos demais na maioria dos experimentos. Nos casos em que foram obtidos valores

razoáveis no tempo de processamento, o algoritmo ASCX-1P mostrou um desempenho

melhor que o algoritmo Apriori, mas pior que o algoritmo ASCX-2P, sendo, no entanto,

casos pouco importantes no ponto de vista prático. Por este motivo, o algoritmo ASCX-

121

1P não se mostrou viável na prática. Assim sendo, o algoritmo ASCX-1P não foi

considerado no restante deste trabalho.

Alguns experimentos provocaram erro de execução e não foi possível determinar o

tempo de execução, mas foi possível observar que os erros ocorreram quando já haviam

decorridos vários minutos depois de iniciado o experimento, o que significa dizer que os

tempos nestes casos seriam altos.

Os resultados foram então tabulados de modo que permitisse uma interpretação das

tendências observadas. Os principais resultados são apresentados a seguir.

Percebeu-se uma relação entre o número médio de atributos por transação e o

aumento do tempo de processamento, o que mostra que os algoritmos são sensíveis a

esta característica dos documentos, em função do grande número de combinações que

têm que fazer.

Para facilitar a interpretação, os tempos de processamento foram divididos pelo

número de transações do documento, obtendo-se assim o tempo de processamento

médio por transação, que são apresentados na FIG. 5.2, onde os valores de suporte

mínimo e confiança mínima utilizados nos testes são substituídos pelas siglas SB/SA

(suporte baixo/suporte alto) e CB/CA (confiança baixa/confiança alta).

FIG. 5.2: Tempos normalizados dos testes dos algoritmos de geração de regras de

associação em documentos XML

Obs.: (1) erro causado pelo banco de dados

tempos (s.) suporte

mínimo

confiança

mínima

Apriori ASCX-2P

SB CB 0,04720 0,00018

SB CA 0,04853 0,00021

SA CB 0,04820 0,00021

SA CA 0,04321 0,00023

FIG. 5.2(a): Processamento do documento orders.xml

tempos (s.) suporte

mínimo

confiança

mínima

Apriori ASCX-2P

SB CB 0,01118 0,00072

SB CA 0,11184 0,00020

SA CB 0,02138 0,00197

SA CA 0,01033 0,00053

FIG. 5.2(b): Processamento do documento _orders.xml

ver nota 51 na pág. 118

122

tempos (s.) suporte

mínimo

confiança

mínima

Apriori ASCX-2P

SB CB 0,23000 0,01200

SB CA 0,07200 0,02200

SA CB 0,23800 0,01000

SA CA 0,03000 0,01000

FIG. 5.2(c): Processamento do documento ebay.xml

tempos (s.) suporte

mínimo

confiança

mínima

Apriori ASCX-2P

SB CB (1) 0,00029

SB CA 0,20900 0,00029

SA CB 0,00690 0,00020

SA CA 0,01480 0,00028

FIG. 5.2(d): Processamento do documento part.xml

tempos (s.) suporte

mínimo

confiança

mínima

Apriori ASCX-2P

SB CB 0,04451 0,00038

SB CA 0,04669 0,00038

SA CB 0,02038 0,00023

SA CA 0,03053 0,00015

FIG. 5.2(e): Processamento do documento _part.xml

tempos (s.) suporte

mínimo

confiança

mínima

Apriori ASCX-2P

SB CB (1) 0,82537

SB CA (1) 0,33881

SA CB (1) 0,00851

SA CA (1) 0,01418

FIG. 5.2(f): Processamento do documento SigmodRecord.xml

tempos (s.) suporte

mínimo

confiança

mínima

Apriori ASCX-2P

SB CB 3,81364 0,73182

SB CA 3,49091 0,76818

SA CB 3,50000 0,02682

SA CA 3,42273 0,02500

FIG. 5.2(g): Processamento do documento _SigmodRecord.xml

tempos (s.) suporte

mínimo

confiança

mínima

Apriori ASCX-2P

SB CB 0,29072 0,04782

SB CA 0,32386 0,07008

SA CB 0,28314 0,00393

SA CA 0,29877 0,00369

FIG. 5.2(h): Processamento do documento uwm.xml

123

tempos (s.) suporte

mínimo

confiança

mínima

Apriori ASCX-2P

SB CB 0,43778 0,10867

SB CA 0,42444 0,10889

SA CB 0,41778 0,00633

SA CA 0,41778 0,00667

FIG. 5.2(i): Processamento do documento _uwm.xml

tempos (s.) suporte

mínimo

confiança

mínima

Apriori ASCX-2P

SB CB 0,0070 0.0

SB CA 0,0050 0.0

SA CB 0,0040 0.0

SA CA 0,0040 0.0

FIG. 5.2(j): Processamento do documento mercado.xml

FIG. 5.3: Gráficos dos testes dos algoritmos de geração de regras de associação em

documentos XML

FIG. 5.3(a): Tempos do algoritmo Apriori

Apriori

0,0

0,5

1,0

1,5

2,0

2,5

3,0

3,5

4,0

4,5

2,1 8 8 9 9 10 10,9 14 27,6 46,7

n. médio de atributos

tempo médio po r transação (s.)

SB CB

SB CA

SA CB

SA CA

124

FIG. 5.3(b): Tempos do algoritmo ASCX-2P

Os valores observados na FIG. 5.2 foram então utilizados nos gráficos da FIG. 5.3,

que mostra a relação entre o número médio de atributos por transação e o tempo médio

por transação.

tempo (s)

n. médio de

atributos

algoritmo

Apriori

algoritmo

ASCX-1P

2,1 0,00500 0.0

8 0,03868 0,00086

8 0,04679 0,00021

9 0,03553 0,00028

9 0,07690 0,00026

10 0,14250 0,01350

10,9 0,29912 0,03138

14 0,42444 0,05764

27,6 3,55682 0,38795

46,7 - 0,29672

FIG. 5.4(a): Tempos médios de processamento dos algoritmos de regra de associação

Pode-se observar na FIG. 5.3(b) que o algoritmo ASCX-2P, ao contrário do

algoritmo Apriori, sofre influência do valor de suporte mínimo, pois as curvas com os

valores baixos de suporte mínimo (SB/CB e SB/CA) apresentam a mesma tendência,

mas bem diferente das curvas com valores altos de suporte mínimo (SA/CB e SA/CA),

que, por sua vez, apresentam a mesma tendência.

A S C X -2 P

0 ,0

0 ,1

0 ,2

0 ,3

0 ,4

0 ,5

0 ,6

0 ,7

0 ,8

0 ,9

2 ,1 8 8 9 9 1 0 1 0 ,9 14 2 7 ,6 4 6 ,7

n . m é d io d e a t r ib u to s

tempo médio po r transação (s.)

S B CB

S B CA

S A CB

S A CA

125

FIG. 5.4(b): Gráfico comparativo dos tempos médios de processamento dos algoritmos

de regra de associação

A FIG. 5.4(b) apresenta um gráfico comparativo com os tempos médios dos dois

algoritmos.

Pode-se observar que os algoritmos apresentam a mesma tendência, isto é, o tempo

de processamento médio aumenta na medida em que aumenta o número médio de

atributos por transação.

Também se pode observar que os tempos de processamento são praticamente

idênticos para um valor pequeno do número médio de atributos. Para valores maiores

desta característica, o algoritmo ASCX-2P se mostra bem superior ao algoritmo

Apriori, com valores de tempos equivalentes a um décimo deste.

5.2.3. CONSIDERAÇÕES COMPLEMENTARES

O algoritmo ASCX-1P se mostrou viável apenas para documentos pequenos, pois o

tempo de processamento para documentos com tamanhos que são mais comumente

encontrados se mostra excessivamente alto. Isto se deve certamente ao grande número

de combinações realizadas entre todos os elementos do documento. Pode-se perceber

Comparação entre algoritmos

0,0

0,5

1,0

1,5

2,0

2,5

3,0

3,5

4,0

2,1 8 8 9 9 10 10,9 14 27,6 46,7

n. médio de atributos

tempo médio por transação (s.)

Apriori

ASC X-2P

126

que a otimização sobre este algoritmo, que gera então o algoritmo ASCX-2P, acaba

reduzindo bastante o tempo de processamento global e, com isso, apresentando um bom

desempenho.

A possibilidade de uso de restrições sobre os atributos, que podem ser definidos

como somente antecedente ou somente consequente nas regras geradas, foram testadas,

mas não trouxeram impacto significativo nos resultados observados e, por isso, não

foram destacados.

5.3. DESCOBERTA DE REGRAS DE ASSOCIAÇÃO GENERALIZADAS EM

DOCUMENTOS XML

5.3.1. METODOLOGIA DE TESTES

A metodologia de testes para avaliação dos algoritmos de regras de associação

generalizadas em documentos XML obedeceu a critérios análogos aos descritos na seção

5.2.1. Os seguintes algoritmos foram avaliados:

• AprioriG: implementação clássica para descoberta de regras de associação

generalizadas (ver seção 4.2.3);

• ASCX-1PG: implementação do algoritmo proposto neste trabalho para geração

de regras de associação generalizadas em 1 passagem sobre o documento XML

(ver seção 4.3.4);

• ASCX-2PG: implementação do algoritmo proposto neste trabalho para geração

de regras de associação generalizada em 2 passagens sobre o documento XML

(ver seção 4.3.5).

Do mesmo modo como descrito na seção 5.2.1, procurou-se comparar o

desempenho dos algoritmos, medido em termos de tempo de processamento, uma vez

que os algoritmos são todos determinísticos e produzem os mesmos resultados quando

utilizados sob as mesmas condições.

127

Os seguintes parâmetros foram configurados para a execução dos algoritmos:

• suporte mínimo (%): foram utilizados 2 valores diferentes para cada conjunto de

dados;

• confiança mínima (%); foram utilizados os valores de 70% e 90% para todas as

bases de dados;

• número máximo de itens: valor fixado em 3 para todas as bases de dados.

Cada base de dados foi testada com um dado algoritmo em quatro situações

diferentes, correspondendo às combinações possíveis dos valores diferentes que os

parâmetros acima podem assumir (dois valores de suporte mínimo e dois de confiança

mínima).

5.3.2. TESTES REALIZADOS E RESULTADOS OBTIDOS

Para testes dos algoritmos de geração de regras de associações generalizadas foram

utilizados alguns documentos XML entre os utilizados nos testes descritos na seção

5.2.2. São eles:

• SigmodRecord.xml

• _SigmodRecord.xml

• uwm.xml

• _uwm.xml

• mercado.xml

Os documentos que apresentavam estrutura invariante, isto é, todas as transações

possuem exatamente a mesma estrutura, não foram utilizados (orders.xml,

_orders.xml, ebay.xml, part.xml e _part.xml), pois acabariam gerando regras

generalizadas sem utilidade prática (uma vez que todos os caminhos estariam presentes

em todas as regras, com todas as combinações possíveis).

Como descrito anteriormente, para cada documento foram utilizados dois valores

de suporte mínimo diferentes:

128

Documento

Suporte

mínimo

1 SigmodRecord.xml

30%

40%

2 _SigmodRecord.xml

30%

40%

3 uwm.xml

30%

40%

4 _uwm.xml

30%

40%

5 mercado.xml

20%

30%

Os valores de suporte mínimo utilizados nos testes foram definidos de modo a

fornecerem resultados razoáveis (tempo de processamento e número de regras geradas).

Assim como foi feito nos testes de regras de associação (ver seção 5.2.2), a

avaliação dos tempos na geração de regras generalizadas não levou em consideração o

tempo necessário ao pré-processamento dos dados.

A FIG. 5.5 mostra uma visão analítica dos resultados obtidos.

FIG. 5.5: Testes dos algoritmos de geração de regras de associação generalizadas em

documentos XML

Obs.: (1) tempo superior a 1000 s.

; (2) erro causado pelo banco de dados

parâmetros resultados

tempos (s.)

suporte

mínimo

confiança

mínima

total de

regras

geradas

AprioriG ASCX-1PG ASCX-2PG

30% 70% 163 (2) (1) 0,28

30% 90% 137 (2) (1) 0,28

40% 70% 80 (2) (1) 0,28

40% 90% 80 (2) (1) 0,25

FIG. 5.5(a): Processamento do documento SigmodRecord.xml

parâmetros resultados

tempos (s.)

suporte

mínimo

confiança

mínima

total de

regras

geradas

AprioriG ASCX-1PG ASCX-2PG

30% 70% 80 81,8 (1) 0,05

30% 90% 80 81,8 (1) 0,05

40% 70% 68 83,7 (1) 0,04

40% 90% 68 82,1 (1) 0,11

FIG. 5.2(b): Processamento do documento _SigmodRecord.xml

ver nota 50 na pag. 118.

ver nota 51 na pág. 118.

129

parâmetros resultados

tempos (s.)

suporte

mínimo

confiança

mínima

total de

regras

geradas

AprioriG ASCX-1PG ASCX-2PG

30% 70% 495 (2) (1) 1,94

30% 90% 388 (2) (1) 2,06

40% 70% 378 (2) (1) 1,43

40% 90% 299 (2) (1) 1,56

FIG. 5.2(c): Processamento do documento uwm.xml

parâmetros resultados

tempos (s.)

suporte

mínimo

confiança

mínima

total de

regras

geradas

AprioriG ASCX-1PG ASCX-2PG

30% 70% 1.019 108,0 (1) 1,79

30% 90% 869 111,0 (1) 1,64

40% 70% 784 104,0 (1) 0,34

40% 90% 639 130,0 (1) 0,34

FIG. 5.2(d): Processamento do documento _uwm.xml

parâmetros resultados

tempos (s.)

suporte

mínimo

confiança

mínima

total de

regras

geradas

AprioriG ASCX-1PG ASCX-2PG

20% 70% 26 1,30 0,05 0,0

20% 90% 15 0,18 0,0 0,0

30% 70% 20 0,06 0,06 0,0

30% 90% 9 0,06 0,0 0,0

FIG. 5.2(e): Processamento do documento mercado.xml

Os tempos observados na execução do algoritmo ASCX-1PG foram muito

superiores aos demais na maioria dos experimentos e por isso não se mostrou viável na

prática, assim como já havia ocorrido com o algoritmo ASCX-1P (ver seção 5.2.2).

Deste modo, o algoritmo ASCX-1PG não foi considerado no restante deste trabalho.

O algoritmo AprioriG acabou provocando erro durante a execução de experimentos

com documentos com um número muito grande de transações, o que mostra que o

ambiente utilizado pode não ser adequado para esta situação. No entanto, foi possível

observar que já haviam decorrido vários minutos depois de iniciado estes experimentos,

o que pode significar que os tempos de execução destes experimentos seriam altos.

Os resultados foram então tabulados de modo que permitisse uma interpretação das

tendências observadas. Os principais resultados são apresentados a seguir.

130

Para facilitar a interpretação, os tempos de processamento foram divididos pelo

número de transações do documento, obtendo-se assim o tempo de processamento

médio por transação, que são apresentados na FIG. 5.6, onde os valores de suporte

mínimo e confiança mínima utilizados nos testes são substituídos pelas siglas SB/SA

(suporte baixo/suporte alto) e CB/CA (confiança baixa/confiança alta).

FIG. 5.6: Tempos normalizados dos testes dos algoritmos de geração de regras de

associação generalizada em documentos XML

Obs.: (1) erro causado pelo banco de dados

tempos (s.) suporte

mínimo

confiança

mínima

AprioriG ASCX-2PG

SB CB (1) 0,00418

SB CA (1) 0,00418

SA CB (1) 0,00418

SA CA (1) 0,00373

FIG. 5.6(a): Processamento do documento SigmodRecord.xml

tempos (s.) suporte

mínimo

confiança

mínima

AprioriG ASCX-2PG

SB CB 3,71818 0,00227

SB CA 3,71818 0,00227

SA CB 3,80455 0,00182

SA CA 3,73182 0,00500

FIG. 5.6(b): Processamento do documento _SigmodRecord.xml

tempos (s.) suporte

mínimo

confiança

mínima

AprioriG ASCX-2PG

SB CB (1) 0,00092

SB CA (1) 0,00098

SA CB (1) 0,00068

SA CA (1) 0,00074

FIG. 5.6(c): Processamento do documento uwm.xml

tempos (s.) suporte

mínimo

confiança

mínima

AprioriG ASCX-2PG

SB CB 1,20000 0,01989

SB CA 1,23333 0,01822

SA CB 1,15556 0,00378

SA CA 1,44444 0,00378

FIG. 5.6(d): Processamento do documento _uwm.xml

ver nota 51 na pág. 118.

131

tempos (s.) suporte

mínimo

confiança

mínima

AprioriG ASCX-2PG

SB CB 0,13000 0,0

SB CA 0,01800 0,0

SA CB 0,00600 0,0

SA CA 0,00600 0,0

FIG. 5.6(e): Processamento do documento mercado.xml

FIG. 5.7: Gráficos dos testes dos algoritmos de geração de regras de associação

generalizada em documentos XML

FIG. 5.7(a): Tempos do algoritmo AprioriG

Os valores observados na FIG. 5.6 foram então utilizados para a construção dos

gráficos da FIG. 5.7, que mostra a relação entre o número médio de atributos por

transação e o tempo médio por transação.

A FIG. 5.8 apresenta um gráfico comparativo com os tempos médios dos dois

algoritmos.

Pode-se observar que os tempos de processamento do algoritmo AprioriG são bem

superiores aos tempos do algoritmo ASCX-2PG, que foram sempre bem baixos.

AprioriG

0,0

0,5

1,0

1,5

2,0

2,5

3,0

3,5

4,0

2,1 10,9 14 27,6 46,7

n. médio de atributos

tempo médio po r transação (s.)

SB CB

SB CA

SA CB

SA CA

132

FIG. 5.7(b): Tempos do algoritmo ASCX-2PG

No valores exibidos na FIG. 5.8 pode-se perceber que o processamento do

algoritmo ASCX-2PG pouco se altera de acordo com a variação do número médio de

atributos por transação que caracteriza os documentos utilizados, ao contrário do que

ocorre com o algoritmo AprioriG.

tempo (s)

n. médio de

atributos

algoritmo

AprioriG

algoritmo

ASCX-1PG

2,1 0,04000 0,00000

10,9 - 0,00083

14,0 1,25833 0,01142

27,6 3,74318 0,00284

46,7 - 0,00407

FIG. 5.8(a): Tempos médios de processamento dos algoritmos de regra de associação

generalizada

A S C X -2 P G

0,0 0 0

0,0 0 5

0,0 1 0

0,0 1 5

0,0 2 0

0,0 2 5

2 ,1 1 0,9 1 4 2 7,6 46 ,7

n. m éd io de a tributo s

tempo médio po r transação (s.)

S B C B

S B C A

S A C B

S A C A

133

FIG. 5.8(b): Gráfico comparativo dos tempos médios de processamento dos algoritmos

de regra de associação generalizada

5.3.3. CONSIDERAÇÕES COMPLEMENTARES

Na execução dos algoritmos de associação generalizada foram utilizados valores

altos para os valores de suporte mínimo utilizados nos experimentos se comparados com

os mesmos documentos utilizados no experimentos de regras de associação (ver seção

5.2.3), pois nos testes em que foram utilizados os mesmos valores, percebeu-se um

número muito elevado de regras geradas (em média mais de 500, chegando em alguns

casos a mais de 1000), que normalmente não são úteis.

A possibilidade de uso de restrições nos atributos, que podem ser definidos como

somente antecedente ou somente consequente nas regras geradas, foram testadas, mas

não trouxeram impacto significativo nos resultados observados e, por isso, não foram

destacados.

Comparação entre algoritmos

0,0

0,5

1,0

1,5

2,0

2,5

3,0

3,5

4,0

2,1 10,9 14 27,6 46,7

n. médio de atributos

tempo médio por transação (s.)

AprioriG

ASCX-2PG

134

5.4. CLASSIFICAÇÃO EM DOCUMENTOS XML

5.4.1. METODOLOGIA DE TESTES

Nos teste de classificação de documentos XML foi utilizado somente o algoritmo

ASCX-2P, que apresentou o melhor desempenho estre os algoritmos de regras de

associação avaliados, que geram, todos eles, os mesmos resultados, isto é, as mesmas

regras de associação quando utilizados os mesmos parâmetros de entrada.

Nos testes procurou-se avaliar a acurácia das regras obtidas a partir de documentos

XML (treinamento - ver seção 2.3.5) e utilizadas para classificar transações do mesmo

documento e/ou documentos diferentes (testes - ver seção 2.3.5). É importante destacar

que os documentos utilizados nos treinamentos e testes têm que ter a mesma estrutura

(ver seção 2.1.3), de modo a permitir aplicar corretamente as regras obtidas. Foram

utilizados diferentes valores de suporte mínimo, mas mantido fixo o valor de confiança

mínima nos experimentos, pois, como o próprio nome já diz (ver seção 2.3.2), a

alteração do valor da confiança mínima afeta diretamente a qualidade das regras

geradas, que acabariam assim afetando a qualidade do classificador criado com estas

regras.

5.4.2. TESTES REALIZADOS E RESULTADOS OBTIDOS

Para os testes de classificação baseada em regras de associação foram utilizados os

documentos já utilizados nos experimentos de regras de associação. São eles:

• orders.xml

• _orders.xml

• ebay.xml

• part.xml

• _part.xml

135

• SigmodRecord.xml

• _SigmodRecord.xml

• uwm.xml

• _uwm.xml

A FIG. 5.9 apresenta um quadro com os resultados obtidos nos experimentos.

Treino Testes Regras

Tempo SM / CM

Acurácia

_orders.xml

orders.xml

18 0,33 / 0,11

1 / 90 46 / 152 (30,3%)

_orders.xml

orders.xml

18 0,38 / 0,17

1 / 70 46 / 152 (30,3%)

ebay.xml ebay.xml

3 0,17 / 0,16

60 / 90 5 / 5 (100%)

_parts.xml parts.xml

6 0,28 / 0,17

5 / 90 63 / 133 (47,4%)

_parts.xml parts.xml

18 0,49 / 0,37

3 / 90 121 / 133 (91,0%)

parts.xml _parts.xml

25 4,18 / 2,48

3 / 90 2000 / 2000 (100%)

_Sigmod

Record.xml

Sigmod

Record.xml

1 23,1 / 0,06

15 / 90 7 / 22 (31,8)

_uwm.xml uwm.xml

1 0,61 / 0,33

20 / 90 56 / 90 (62,2%)

_uwm.xml uwm.xml

2 5,0 / 0,31 15 / 90 56 / 90 (62,2%)

FIG. 5.9: Resultados de classificação em documentos XML

Onde:

• Treino: documento utilizado no treino, isto é, na geração da regras de associação

utilizadas pelo classificador;

• Testes: documento utilizado no teste, isto é, sobre o qual é executado o

classificador obtido a partir das regras geradas no treino;

• Regras: número de regras geradas no treino e utilizadas pelo classificador;

• Tempo: tempos de execução do treinamento e do teste;

• SM / CM: valores de suporte mínimo (SM) e confiança mínima (CM) utilizados

para geração das regras no treinamento;

• Acurácia: valores dos acertos em relação ao total de transações do documento

utilizado nos teste.

Pode-se observar que o valor da acurácia aumenta para valores menores de suporte

mínimo definido como parâmetro para a geração das regras de associação.

136

5.4.3. CONSIDERAÇÕES COMPLEMENTARES

Durante os testes de classificação em documentos XML, foram definidos vários

valores para os parâmetros do algoritmo de associação, suporte mínimo e confiança

mínima, sendo que pensou em usar valores bem pequenos para o suporte mínimo. No

entanto, neste caso, observou-se que os tempos de execução do algoritmo ASCX-2P

mostraram-se surpreendentemente alto. Após a análise do problema, verificou-se que o

algoritmo ASCX-2P tende a ter um comportamento semelhante ao do algoritmo

ASCX-1P à medida que o valor definido para o suporte mínimo se aproxima de zero.

Na verdade, pode-se ver que o algoritmo ASCX-1P corresponde ao algoritmo ASCX-

2P com o valor do suporte mínimo igual a zero: neste caso o primeiro passo do

algoritmo ASCX-2P acaba não "cortando" nenhum elemento para o passo seguinte,

principal característica que distingue os dois algoritmos!

137

6. CONCLUSÕES

6.1. RETROSPECTO

Os estudos de regras de associação e de classificação se iniciaram com a

implementação de algoritmos tradicionais que realizam estas tarefas, que tinham como

objetivo de entender os problemas intrínsicos de implementação destes tipos de

algoritmos, ao mesmo em tempo que se observava a aplicação das técnicas. Inicialmente

os algoritmos foram desenvolvidos para utilização em bancos de dados relacionais.

Em paralelo, iniciou-se o estudo de rotinas para manipulação de documentos XML,

mais especificamente com a API SAX. A escolha desta API, e não pela DOM, se deveu

ao fato que, desde o início, era objetivo desenvolver um algoritmo que gerasse os

resultados desejados a partir da leitura sequencial do documento XML, o que a API

SAX realiza com mais eficiência que a API DOM.

Durante a implementação deste trabalho, observou-se que a estrutura do documento

XML mantida em estruturas de dados internamente nos programas poderia gerar

resultados interessantes. Um destes resultados é apresentação textual da estrutura, que é

de fácil compreensão. Um outro resultado é a geração de comandos SQL para criação

de tabelas num banco de dados relacional para armazenar o documento XML

integralmente, sem perda de suas características.

6.2. CONTRIBUIÇÕES

A principal contribuição deste trabalho é certamente o desenvolvimento dos

algoritmos ASCX-2P e ASCX-2PG para geração de regras de associação e de regras

de associação generalizada que se mostraram bastante eficientes. Estes algoritmos

podem, certamente, ser utilizados em bancos de dados relacionais com poucas

alterações

138

A sistemática de processamento de documentos XML através da API SAX também

se mostrou bastante eficiente, quando não se esperava obter este resultado como

ambiente de processamento escolhido.

A interface gráfica para interação com o usuário na escolha dos dados para

processamento merece destaque, facilitando o uso do protótipo implementado.

6.3. TRABALHOS FUTUROS

Durante o desenvolvimento deste trabalho, foram feitas muitas anotações para

melhorias que podiam ser feitas. Muitas delas se tinha desejo de implementar ainda

neste trabalho, mas ficaram prejudicadas pelo pouco tempo disponível.

O algoritmo ASCX-2P pode ser alterado para utilização em banco de dados

relacionais, o que, certamente, poderá mostrar bons resultados.

Os estudos de classificação com regras de associação podem se aprofundar mais,

inclusive explorando mais o uso de regras de associação generalizada para uso na

classificação.

Como a estrutura do documento XML é importante para o controle da execução dos

algoritmos propostos, optou-se por gerá-la no próprio programa, antes do

processamento do algoritmo propriamente dito. Duas melhorias podem ser feitas:

armazenamento da estrutura, para uso posterior pelo programa e geração desta estrutura

a partir do esquema associado ao documento XML, DTD ou XMLSchema, o que pode

ser bastante interessante.

O desempenho do algoritmo Apriori pode ser avaliada em outros tipos de bancos de

dados relacionais, como, por exemplo, Oracle, retirando-se assim o overhead

provocado pelo uso de bancos de dados pouco eficientes. Vale destacar que o

desempenho observado na execução dos algoritmos propostos não é afetado por este

problema, pois os dados estão armazenados em documentos textos e a leitura sobre eles

é feita sequencialmente.

Uma extensão interessante para este trabalho seria a possibilidade de acesso a

documentos XML direto na Internet, o que aumentaria muito a versatilidade de sua

139

utilização, pois atualmente eles têm que ser copiados para o disco para poderem ser

processados.

140

7. REFERÊNCIAS BIBLIOGRÁFICAS

AGRAWAL, R., IMIELINSKI, T. e SWAMI, A. Mining Association Rules Between

Sets of Items in Large Databases. ACM SIGMOD International Conference on

Management of Data, Washington DC, USA, 1993.

AGRAWAL, R. e SRIKANT, R. Fast Algorithms for Mining Association Rules. 20th

VLDB Conference, Santiago, Chile, 1994.

ALI, K., MANGANARIS, S. e SRIKANT, R. Partial Classification Using

Association Rules. Third International Conference on Knowledge Discovery and

Data Mining (KDD'97), Newport Beach, California, EUA, 1997.

ANDERSON, R. Professional XML. Ed. Ciência Moderna, 2001.

BEECH, D., MALHOTRA, A. e RYS, M. A Formal Data Model and Algebra for

XML. W3C XML Query Working Group Note, 1999.

BONIFÁCIO, A. Ontologias e Consulta Semântica: uma Aplicação ao Caso Lattes.

Tese de Mestrado, Programa de Pós-Graduação em Computação do Instituto de

Matemática, UFRGS, 2002.

BRAGA, D., CAMPI, A., KLEMETTINEN, M. e LANZI, P. Mining Association

Rules from XML Data. 4th International Conference on Data Warehousing and

Knowledge Discovery (DaWaK 2002), Provence, França, 2002.

BRAGA, D., CAMPI, A., STEFANO, C., KLEMETTINEN, M., LANZI, P. A Tool for

Extracting XML Association Rules from XML Documents. 14th IEEE-ICTAI,

Washington DC, EUA, 2002a.

BRIN, S., MOTWANI, R., ULLMAN, J. e TSUR, S. Dynamic Itemset Counting and

Implication Rules for Market Basket Data. ACM DIGMOD International

Conference on Management of Data (SIGMOD'97), Arizona, EUA, 1997.

BÜCHNER, A., BAUMGARTEN, M., MULVENNA, M., BÖHM, R., e ANAND, S.

Data Mining and XML: Current and Future Issues. 1st International

Conference on Web Information Systems Engineering (WISE'00), Hong Kong,

2000.

CHEN, B., HAAS, P. e SCHEUERMANN, P. A New Two-Phase Sampling Based

Algorithm for Discovering Association Rules.ACM SIGKDD'02, Edmonton,

Alberta, Canada, 2002.

CHEUNG, W. e ZAIANE, O. Incremental Mining of Frequent Patterns without

Candidate Generation or Support Constraint. 17th International Database

Engineering and Applications Symposium (IDEAS'03), Hong Kong, China, 2003.

141

COOLEY, R., MOBASHER, B. e SRIVASTAVA, J. Web Mining: Information and

Pattern Discovery on the World Wide Web. 9th IEEE International Conference

on Tools with Artificial Intelligence (ICTAI’97), Newport Beach, California,

EUA, 1997.

DAVIS, L. Handbook of Genetic Algorithms. VNR Comp. Library, 1990.

DING, Q., RICORDS, K. e LUMPKIN, J. Deriving General Association Rules from

XML Data. International Conference on Software Engineering, Artifical

Intelligence, Networking and Parallel/Distributed Computing, Lübeck, Germany,

2003.

DONG, G., ZHANG, X., WONG, L. e LI, J. CAEP: Classification by Aggregating

Emerging Patterns. Discovery Science: 2nd International Conference, LNCS

1721 (DSs'99), Tokyo, Japão, 1999.

DORRE, J., GERRSTL, P. e SEIFFERT, R. Text Mining: Finding Nuggets in

Mountains of Textual Data. 5th ACM International Conference on Knowledge

Discovery and Data Mining (KDD-99), San Diego, EUA, 1999.

FAYYAD, U., PIATETSKY-SHAPIRO, G. e SMYTH, P. From Data Mining to

Knowledge Discovery: An Overview. Advances in Knowledge Discovery and

Data Mining, editado por U. Fayyad, G. Piatetsky-Shapiro, P. Smyth e R.

Uthurusamy, AAAI Press/MIT Press, p. 1-34, 1996.

GOLDSCHMIDT, R., NOGUEIRA, D., PASSOS, E. e VELLASCO, M. Bramining:

um Ambiente Integrado para Descoberta de Conhecimento em Bases de

Dados. III Congresso de Lógica Aplicada à Tecnologia, São Paulo: SENAC,

2002.

GOLDSCHMIDT, R. Assistência Inteligente à Orientação do Processo de

Descoberta de Conhecimento em Bases de Dados. Tese de Doutorado, Dep. de

Eng. Elétrica, PUC-RJ, 2003.

HAN, J., PEI, J. e YIN, Y. Mining Frequent Patterns without Candidate

Generation. ACM-SIGMOD, Dalas, Texas, EUA, 2000.

HAYKIN, S. Redes Neurais: Princípios e Prática. Ed. Bookman, 2001.

HAN, J. e FU, Y. Discovery of Multiple-Level Association Rules from Large

Databases. 21th VLDB Conference, Zurich, Suiça, 1995.

HIPP, J., MYKA, A., WIRT, R. e GÜNTZER, U. A New Algorithm for Faster

Mining of Generalized Association Rules. 2nd European Symposium on PKDD,

Nantes, França, 1998.

KIMBAL, R. Data Warehouse Toolkit. Ed. Makron Books, 1998.

142

LI, W., HAN, J. e PEI, J. CMAR: Accurate and Efficient Classification Based on

Multiple Class-Association Rules. 2001 IEEE International Conference on Data

Mining (ICDM'01), San Jose, California, EUA, 2001.

LIU, B., HSU, B. e MA, Y. Integranting Classification and Association Rule

Mining. 4th International Conference on Knowledge Discovery anda Data Mining

(KDD'98), Nova York, EUA, 1998.

MELLO, R., DORNELLES, C., KADE, A., BRAGANHOLO, V. e HEUSER, C.

Dados Semi-Estruturados (tutorial). SBBD XV Brazilian Database Symposium,

João Pessoa, Paraíba, Brasil, 2000.

MICHIE, D., SPIEGELHALTER, D. e TAYLOR, C. Machine Learning, Neural and

Statistical Classification. Ellis Horwood, 1994.

OTEY, M. et ali Mining Frequent Itemsets in Distributed and Dynamic Databases.

IEEE 3th Conference on Data Mining (ICDM 2003), Melbourne, USA, 2003.

PAPAKONSTANTINOU, Y., GARCIA-MOLINA, H. e WIDOM, J. Object Exchange

Across Heterogeneous Information Sources. IEEE 11th International

Conference on Data Engineering, Taipei, Taiwan, 1995.

PARK, J., CHEN, M. e YU, P. An Effective Hash-Based Algorithm for Mining

Association Rules. ACM-SIGMOD International Conference Management of

Data, San Jose, California, EUA, 1995.

QUINLAN, J. C4.5: Programs for Machine Learning. San Mateo, CA: Morgan

Kaufmann, 1993.

SAVASERE, A., OMIECINSKI, E. e NAVATHE, S. An Efficient Algorithm for

Mining Association Rules in Large Databases. 21th VLDB Conference,

Zurique, Suiça, 1995.

SOUZA, M. Mineração de Dados: Uma Implementação Fortemente Acoplada a um

Sistema Gerenciador de Banco de Dados Paralelo. Dissertação. Programa de

Engenharia de Sistemas e Computação, COPPE/UFRJ, 1998.

SRIKANT, R. e AGRAWAL, R. Mining Generalized Association Rules. Proceedings

of the 21

VLDB Conference, Zurique, Suiça, 1995.

SUCIU, D. Semistructured Data and XML. 5th International Conference on

Foundation of Data Organization (FODO'98), Kobe, Japão, 1998.

WAN, J. e DOBBIE, G. Extracting Association Rules from XML Documents using

Xquery. 15th International Workshop on WIDM, New Orleans, Louisiana, EUA,

2003.

WANG, K., ZHOU, S. e HE, Y. Growing Decision Trees on Support-Less

Association Rules. ACM-SIGKDD'00, Boston, Massachusetts, EUA, 2000.

143

WEISS, S. e INDURKHYA, N. Predictive Data Mining: a Practical Guide. San

Francisco: Morgan Kaufmann, 1998.

ZADEH, L. Fuzzy Sets. Information and Control (vol. 8), Nova York, EUA, 1965.

ZAKI, M. Parallel and distributed association mining: A survey. IEEE Concurrency,

Special Issue on Parallel Mechanisms for Data Mining, 7(4):14-25,

Dezembro/1999.

ZAKI, M. Parallel and Distributed Data Mining: An Introduction. Large-Scale

Parallel Data Mining. Berlin: Springer-Verlag, 2000.

ZAKI, M. Efficiently Mining Frequent Trees in a Forest. Proceedings of ACM

SIGMOD International Conference on Management of Data, Alberta, Canadá,

2002.

ZAKI, M. e AGGARRWAL, C. XRules: an Effective Structural Classifier for XML

Data. ACM-SIGKDD’03, Washington DC, EUA, 2003.

ZHANG, H., PADMANABHAN, B. e TUZHILIN, A. On the Discovery of

Significant Statistical Quantitative Rules. KDD'04, Seatle, Washington, EUA,

2004.

Sites na Internet, referências válidas em janeiro/2005:

[1]-World Wide Web Consortium. DOM (Document Object Model)

http://www.w3c.org/DOM

[2]-World Wide Web Consortium. DTD (Document Type Definition)

http://www.w3c.org/XML/1998/06/xmlspec-report-v21.htm

[3]-World Wide Web Consortium. HTML (Hyper Text Markup Language)

http://www.w3c.org/MarkUp

[4]-World Wide Web Consortium. OWL (Ontology Web Language)

http://www.w3c.org/2003/05/owl-xml

[5]-Data Mining Group. PMML (Predictive Model Markup Language)

http://www.dmg.org/pmml-v2-0.html

[6]-World Wide Web Consortium. RDF (Resource Description Format)

http://www.w3c.org/TR/rdf-syntax-grammar

[7]-World Wide Web Consortium. RDFS (RDF Schema) http://www.w3c.org/TR/rdf-

schema

[8]-SourceForge. SAX (Simple API for XML) http://sax.sourceforge.net

144

[9]-World Wide Web Consortium. SGML (Standard Generalized Markup Language)

http://www.w3c.org/TR/REC-html40/intro/sgmltut.html

[10]-World Wide Web Consortium. XLink (XML Linking Language)

http://www.w3c.org/TR/xlink/

[11]-World Wide Web Consortium. XML (eXtended Markup Language)

http://www.w3c.org/TR/xml11

[12]-XML for Analysis (XMLA) Advisory Council. XMLA (XML for Analysis)

http://www.xmla.org/download.asp?id=50

[13]-World Wide Web Consortium. XPath (XML Path Language) http://www.w3c.org/

TR/xpath

[14]-World Wide Web Consortium. XPointer (XML Pointer Language)

http://www.w3c.org/TR/WD-xptr

[15]-World Wide Web Consortium. XQuery (XML Query Language)

http://www.w3c.org/TR/xquery

[16]-World Wide Web Consortium. XMLSchema http://www.w3c.org/

TR/xmlschema-0

[17]-World Wide Web Consortium. XSL (eXtensible Stylesheet Language)

http://www.w3c.org/TR/xsl

[18]-World Wide Web Consortium. XSLT (eXtensible Stylesheet Language

Transformation) http://www.w3c.org/TR/xslt

[19]-World Wide Web Consortium. http://www.w3c.org

145

8. ANEXOS

146

8.1. ANEXO 1: ROTEIRO PARA EXECUTAR A IMPLEMENTAÇÃO

A FIG. 8.1 apresenta uma visão geral da implementação deste trabalho.

FIG. 8.1: Visão geral da implementação

A interface da implementação considera as seguintes etapas:

• definição do documento XML a ser processado;

• seleção da operação sobre o documento XML;

• entrada dos parâmetros;

• seleção dos elementos que serão utilizados na operação;

• seleção do tipo de associação para geração de regras;

• seleção do algoritmo de associação a ser utilizado;

• execução do algoritmo; e

• visualização dos resultados.

147

8.2. ANEXO 2: DOCUMENTOS XML

8.2.1. Localização

O site XMLData Repository

(http://www.cs.washington.edu/research/xmldatasets/) possui uma lista de

documentos XML que podem ser utilizados para testes, além de vários links para outros

sites com documentos XML disponíveis.

8.2.3. Documento uwm.xml

A seguir é exibido um trecho do documento uwm.xml

(http://www.cs.washington.edu /research/xmldatasets/data/courses/uwm.xml). O

conteúdo de elementos com textos longos são simplificados na transcrição abaixo, pois

não são considerados na associação. A implementação inclusive limita os textos para

associação para somente os que tenham tamanho (número de caracteres) igual ou

inferior a 50.

<?xml version='1.0' ?>

<!DOCTYPE root SYSTEM "http://www.cs.washington.edu/research/

projects/xmltk/xmldata/data/auctions/ubid.dtd">

<root>

<seller_info>

<seller_name> </seller_name>

<seller_rating> </seller_rating>

</seller_info>

<payment_types>

</payment_types>

<shipping_info>

</shipping_info>

<buyer_protection_info>

</buyer_protection_info>

<auction_info>

<current_bid> </current_bid>

<time_left> </time_left>

<high_bidder>

<bidder_name> MH of San Francisco, </bidder_name>

<bidder_rating> </bidder_rating>

</high_bidder>

<num_items> 8 </num_items>

<num_bids> </num_bids>

<started_at>$9 </started_at>

<bid_increment>$10 </bid_increment>

<id_num> 3699803 </id_num>

</auction_info>

<bid_history>

<highest_bid_amount> $2459 </highest_bid_amount>

</bid_history>

<item_info>

148

<hard_drive> </hard_drive>

<brand>HP Pavilion </brand>

The Pavilion 9780C ... not included.

</description>

</item_info>

</listing>

<seller_info>

<seller_name> </seller_name>

<seller_rating> </seller_rating>

</seller_info>

<payment_types> </payment_types>

<shipping_info> </shipping_info>

<buyer_protection_info> </buyer_protection_info>

<auction_info>

<current_bid> </current_bid>

<time_left> </time_left>

<high_bidder>

<bidder_name> </bidder_name>

<bidder_rating> </bidder_rating>

</high_bidder>

<num_items> </num_items>

<num_bids> </num_bids>

<started_at> </started_at>

<bid_increment> </bid_increment>

<id_num> </id_num>

</auction_info>

<bid_history>

<highest_bid_amount> </highest_bid_amount>

</bid_history>

<item_info>

<hard_drive> </hard_drive>

</item_info>

</listing>

<seller_info>

<seller_name> </seller_name>

<seller_rating> </seller_rating>

</seller_info>

<payment_types> </payment_types>

<shipping_info> </shipping_info>

<buyer_protection_info> </buyer_protection_info>

<auction_info>

<current_bid> </current_bid>

<time_left> </time_left>

<high_bidder>

<bidder_name> </bidder_name>

<bidder_rating> </bidder_rating>

</high_bidder>

<num_items> </num_items>

<num_bids> </num_bids>

<started_at> </started_at>

<bid_increment> </bid_increment>

149

<id_num> </id_num>

</auction_info>

<bid_history>

<highest_bid_amount>

</highest_bid_amount>

</bid_history>

<item_info>

<hard_drive> </hard_drive>

</item_info>

</listing>

<seller_info>

<seller_name>tx of Santa Clara </seller_name>

<seller_rating> </seller_rating>

</seller_info>

<payment_types> </payment_types>

<shipping_info> </shipping_info>

<buyer_protection_info> </buyer_protection_info>

<auction_info>

<current_bid> </current_bid>

<time_left> </time_left>

<high_bidder>

<bidder_name> </bidder_name>

<bidder_rating> </bidder_rating>

</high_bidder>

<num_items>2 </num_items>

<num_bids> </num_bids>

<started_at> </started_at>

<bid_increment> </bid_increment>

<id_num> 3699948 </id_num>

</auction_info>

<bid_history>

<highest_bid_amount> $3837 </highest_bid_amount>

</bid_history>

<item_info>

128MB high-performance PC133 ECC SDRAM Maximum: 4GB

memory capacity (3.3GB maximum usable memory)

</memory>

<hard_drive>

Open bay ... SCSI disk drives

</hard_drive>

<cpu>Intel Pentium III 800MHz </cpu>

<brand>

Hewlett Packard NetServer LH3000 Pentium III 800MHz

128MB RAM/Open Bay/32X CD/No OS

</brand>

HP NetServer LH 3000 ... factor version.

</description>

</item_info>

</listing>

...

</root>

8.2.4. Estrutura dos documentos

150

A seguir são apresentadas as estruturas dos documentos utilizados neste trabalho.

• order.xml e _order.xml:

table (obrigatório, simples)

- 1 T (obrigatório, múltiplo)

- - 1.1 [O_ORDERKEY] (obrigatório, simples)

- - 1.2 [O_CUSTKEY] (obrigatório, simples)

- - 1.3 [O_ORDERSTATUS] (obrigatório, simples)

- - 1.4 [O_TOTALPRICE] (obrigatório, simples)

- - 1.5 [O_ORDERDATE] (obrigatório, simples)

- - 1.6 [O_ORDER-PRIORITY] (obrigatório, simples)

- - 1.7 [O_CLERK] (obrigatório, simples)

- - 1.8 [O_SHIP-PRIORITY] (obrigatório, simples)

- - 1.9 [O_COMMENT] (obrigatório, simples)

151

• ebay.xml:

root (obrigatório, simples)

- 1 listing (obrigatório, múltiplo)

- - 1.1 seller_info (obrigatório, simples)

- - - 1.1.1 [seller_name] (obrigatório, simples)

- - - 1.1.2 [seller_rating] (obrigatório, simples)

- - 1.2 [payment_types] (obrigatório, simples)

- - 1.3 [shipping_info] (obrigatório, simples)

- - 1.4 buyer_protection_info (obrigatório, simples)

- - 1.5 auction_info (obrigatório, simples)

- - - 1.5.1 [current_bid] (obrigatório, simples)

- - - 1.5.2 [time_left] (obrigatório, simples)

- - - 1.5.3 high_bidder (obrigatório, simples)

- - - - 1.5.3.1 [bidder_name] (obrigatório, simples)

- - - - 1.5.3.2 [bidder_rating] (obrigatório, simples)

- - - 1.5.4 [num_items] (obrigatório, simples)

- - - 1.5.5 [num_bids] (obrigatório, simples)

- - - 1.5.6 [started_at] (obrigatório, simples)

- - - 1.5.7 bid_increment (obrigatório, simples)

- - - 1.5.8 [location] (obrigatório, simples)

- - - 1.5.9 [opened] (obrigatório, simples)

- - - 1.5.10 [closed] (obrigatório, simples)

- - - 1.5.11 [id_num] (obrigatório, simples)

- - - 1.5.12 notes (obrigatório, simples)

- - 1.6 bid_history (obrigatório, simples)

- - - 1.6.1 [highest_bid_amount] (obrigatório, simples)

- - - 1.6.2 [quantity] (obrigatório, simples)

- - 1.7 item_info (obrigatório, simples)

- - - 1.7.1 [memory] (obrigatório, simples)

- - - 1.7.2 [hard_drive] (obrigatório, simples)

- - - 1.7.3 [cpu] (obrigatório, simples)

- - - 1.7.4 [brand] (obrigatório, simples)

- - - 1.7.5 [description] (obrigatório, simples)

• part.xml e _part.xml:

table (obrigatório, simples)

- 1 T (obrigatório, múltiplo)

- - 1.1 [P_PARTKEY] (obrigatório, simples)

- - 1.2 [P_NAME] (obrigatório, simples)

- - 1.3 [P_MFGR] (obrigatório, simples)

- - 1.4 [P_BRAND] (obrigatório, simples)

- - 1.5 [P_TYPE] (obrigatório, simples)

- - 1.6 [P_SIZE] (obrigatório, simples)

- - 1.7 [P_CONTAINER] (obrigatório, simples)

- - 1.8 [P_RETAILPRICE] (obrigatório, simples)

- - 1.9 [P_COMMENT] (obrigatório, simples)

• SigmodRecord.xml e _SigmodRecord.xml:

SigmodRecord (obrigatório, simples)

- 1 issue (obrigatório, múltiplo)

- - 1.1 [volume] (obrigatório, simples)

- - 1.2 [number] (obrigatório, simples)

- - 1.3 articles (obrigatório, simples)

- - - 1.3.1 article (obrigatório, múltiplo)

- - - - 1.3.1.1 [title] (obrigatório, simples)

- - - - 1.3.1.2 [initPage] (obrigatório, simples)

- - - - 1.3.1.3 [endPage] (obrigatório, simples)

- - - - 1.3.1.4 authors (obrigatório, simples)

- - - - - 1.3.1.4.1 [author] (obrigatório, múltiplo)

152

• uwm.xml e _uwm.xml:

root (obrigatório, simples)

- 1 listing (obrigatório, múltiplo)

- - 1.1 seller_info (obrigatório, simples)

- - - 1.1.1 [seller_name] (obrigatório, simples)

- - - 1.1.2 seller_rating (obrigatório, simples)

- - 1.2 payment_types (obrigatório, simples)

- - 1.3 shipping_info (obrigatório, simples)

- - 1.4 buyer_protection_info (obrigatório, simples)

- - 1.5 auction_info (obrigatório, simples)

- - - 1.5.1 current_bid (obrigatório, simples)

- - - 1.5.2 time_left (obrigatório, simples)

- - - 1.5.3 high_bidder (obrigatório, simples)

- - - - 1.5.3.1 [bidder_name] (obrigatório, simples)

- - - - 1.5.3.2 bidder_rating (obrigatório, simples)

- - - 1.5.4 [num_items] (obrigatório, simples)

- - - 1.5.5 num_bids (obrigatório, simples)

- - - 1.5.6 [started_at] (obrigatório, simples)

- - - 1.5.7 [bid_increment] (obrigatório, simples)

- - - 1.5.8 location (obrigatório, simples)

- - - 1.5.9 opened (obrigatório, simples)

- - - 1.5.10 [closed] (obrigatório, simples)

- - - 1.5.11 [id_num] (obrigatório, simples)

- - - 1.5.12 notes (obrigatório, simples)

- - 1.6 bid_history (obrigatório, simples)

- - - 1.6.1 [highest_bid_amount] (obrigatório, simples)

- - - 1.6.2 [quantity] (obrigatório, simples)

- - 1.7 item_info (obrigatório, simples)

- - - 1.7.1 [memory] (obrigatório, simples)

- - - 1.7.2 [hard_drive] (obrigatório, simples)

- - - 1.7.3 [cpu] (obrigatório, simples)

- - - 1.7.4 [brand] (obrigatório, simples)

- - - 1.7.5 [description] (obrigatório, simples)

153

8.3. ANEXO 3: APIS UTILIZADAS NA IMPLEMENTAÇÃO

8.3.1. API SAX LibXmlParser

Para obter a API LibXmlParser é necessário acessar o site Stefan Heymann's.Free

Delphi Site (http://www.destructor.de/xmlparser/download.htm) e selecionar o link

XML Parser (http://www.destructor.de/xmlparser/xmlparser.zip). Em seguida

seguir as instruções contidas no arquivo delphi-installation.htm contido no arquivo de

instalação, que está transcrito a seguir:

Installation in Delphi

Borland Delphi Versions 4 and 5

• Download the parser archive

• Unpack the ZIP file (xmlparser.zip) to a directory

• Add the name of this directory to your Library Path (in Delphi: Tools |

Environment Options | Library | Library Path)

• Open Package file:

• Delphi 4: Open XmlComponents_D4.dpk file with File | Open

• Delphi 5: Open XmlComponents_D5.dpk file with File | Open

• Click on 'Compile'. Ignore messages regarding .res files.

• Click on 'Install'

• A new tab 'XML' will appear on the Delphi toolbar with the TXmlScanner

component inside

• The TXmlParser class resides in the LibXmlParser unit which is a part of the ZIP

file.

O uso desta API está descrito no arquivo LibXmlParser.pas, cujo trecho se encontra

transcrito abaixo:

154

Scanning the XML document

-------------------------

- Create TXmlParser Instance MyXml := TXmlParser.Create;

- Load XML Document MyXml.LoadFromFile

(Filename);

- Start Scanning MyXml.StartScan;

- Scan Loop WHILE MyXml.Scan DO

- Test for Part Type CASE MyXml.CurPartType OF

- Handle Parts ... : ;;;

END;

- Destroy MyXml.Free;

8.3.2. API HashTrie

Para obter obter a API HashTrie basta acessar o site Soft Complete

(http://www.softcomplete.com/download.asp) e selecionar o link HashTrie

(http://www.softcomplete.com/download/hashtrie.zip) para copiar o arquivo

hashtrie.zip.

O arquivo HashTrie.pas existente no arquivo hashtrie.zip deve ser copiado para o

mesmo diretório da aplicação e em seguida adicionado ao projeto. Este arquivo contém

o seguinte cabeçalho, onde se vê instruções para divulgação do código:

155

unit HashTrie;

{

Delphi implementation of HashTrie dynamic hashing method

Full description available on www.softlab.od.ua

Delphi 2,3,4,5

Freware with source.

Web: http://www.softcomplete.com

Email: [email protected]

THIS SOFTWARE AND THE ACCOMPANYING FILES ARE DISTRIBUTED

"AS IS" AND WITHOUT WARRANTIES AS TO PERFORMANCE OF MERCHANTABILITY OR

ANY OTHER WARRANTIES WHETHER EXPRESSED OR IMPLIED.

NO WARRANTY OF FITNESS FOR A PARTICULAR PURPOSE IS OFFERED.

THE USER MUST ASSUME THE ENTIRE RISK OF USING THE ACCOMPANYING CODE.

Permission is granted to anyone to use this software for any purpose,

including commercial applications, and to alter it and redistribute it

freely, subject to the following restrictions:

1. The origin of this software must not be misrepresented, you must

not claim that you wrote the original software. If you use this

software in a product, an acknowledgment in the product

documentation would be appreciated but is not required.

2. Altered source versions must be plainly marked as such, and must not

be misrepresented as being the original software.

3. Original copyright may not be removed or altered from any source

distribution.

4. All copyright of HashTrie dynamic hashing method belongs to Andre N

Belokon, SoftLab MIL-TEC Ltd.

}

O arquivo hashtrie.zip contém um exemplo completo de utilização da API, que

pode ser utilizado para teste da instalação.

Para utilizar a API é necessário criar uma classe que define o elemento que será

armazenado.

Tcontador = class

protected

nSup1, nSup2: Longint;

public

constructor Create(p1, p2: integer);

function nSup: integer;

end;

Constructor Tcontador.Create(p1, p2: integer);

begin

nSup1 := p1; nSup2 := p2;

end;

function Tcontador.nSup: integer;

begin

nSup := nSup1 + nSup2;

end;

A chave da árvore é formada pelo conjunto de elementos (string).

O seguinte trecho mostra a definição o objeto

156

var

ht: TStringHashTrie; define o objeto

...

ht := TStringHashTrie.Create; cria o objeto

...

ht.Free; libera o objeto

A seguinte rotina mostra a utilização dos métodos Find (localiza um elemento) e

Add (insere um elemento).

procedure incluirTabelaHash(s: string; pn1, pn2:

LongInt);

var D: Tcontador;

begin

if ht.Find(s, TObject(D)) then begin

inc(D.nSup1, pn1);

inc(D.nSup2, pn2);

end

else begin

D := Tcontador.Create(pn1, pn2);

ht.Add(s, D);

end;

...

incluirTabelaHash('casa', 0, 1);

A tabela pode ser percorrida sequencialmente bastando criar uma rotina que é

passada como parâmetro para o método Traverse. Este método varre a tabela e ativa a

rotina para tratar cada elemento existente na tabela.

procedure mostraTabelaHash(UserData: Pointer;

const Value: string; chave

Data: TObject; elemento

var Done: Boolean);

begin

writeln(F, Value, Tcontador(Data).nSup1:5,

Tcontador(Data).nSup2:5);

end;

...

ht.Traverse(NIL, mostraTabelaHash)

157

8.4. ANEXO 4: SQL USADO NA IMPLEMENTAÇÃO DO ALGORITMO

APRIORI

Este anexo apresenta detalhes da implementação do algoritmo Apriori descrito na

seção 4.2.2, que é repetido a seguir para melhor referência.

APriori (IN docXML, minsup, minconf, maxitens; OUT regras)

1 B = BASKET(docXML)

2 L

= LISTA_SIMPLES

3 se L

= ∅ então FIM //não existem regras

4 para (k = 2, L

k-1

≠ ∅ ∨ k=maxitens, k++)

5 C

= CANDIDATOS(L

k-1

)

6 se C

= ∅ então FIM //não existem mais regras

7 CONTAR(C

); L

= C

8 regras = MONTAREGRAS(L

, i > 1)

Técnica utilizada na codificação dos passos 2 (para 1 elemento) e 7 (para k

elementos) acima: a cada passo são executados dois comandos SQL para determinar o

suporte de cada conjunto de itens no formato basket (mantidos na tabela

SYS_BASKET), onde é utilizada uma tabela para armazenar os k-conjuntos frequentes

(mantidos na tabela auxiliar SYS_ITENS).

A tabela SYS_ITENS tem a coluna NIVEL que armazena a quantidade de itens do

conjunto (valor de k) e tantas colunas quantos forem o número de itens máximos

definidos (a tabela é criada dinamicamente, sempre considerando este número máximo).

O primeiro comando SQL determina os k-conjuntos, gerados a partir dos (k-1)-

conjuntos como definido na seção 2.3.2 e é executado para inserir cada novo k-

conjunto. Este comando trabalha somente sobre a tabela SYS_ITENS, que é pequena,

sendo por isso rápida a sua execução.

O segundo percorre todo o arquivo armazenado no formato basket (SYS_BASKET)

para avaliar o suporte de cada um dos k-conjuntos determinado pelo primeiro comando

SQL.

158

Estes comandos SQL são gerados dinamicamente, se adequando a cada k-passo

do algoritmo, podendo assim ser executado para qualquer quantidade de níveis definido.

159

INSTITUTO MILITAR DE ENGENHARIA

EXÉRCITO BRASILEIRO

SECRETARIA DE CIÊNCIA E TECNOLOGIA

INSTITUTO MILITAR DE ENGENHARIA

CURSO DE MESTRADO EM SISTEMAS E

COMPUTAÇÃO

MAURICIO COSTA REIS

DESCOBERTA DE CONHECIMENTO

EM DOCUMENTOS XML

Rio de Janeiro

2005

Livros Grátis
( http://www.livrosgratis.com.br )
 
Milhares de Livros para Download:
 
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas

Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
 
 