ads:
M´arcio Fuckner
Combina¸c˜ao de Classificadores usando
IAD
Disserta¸c˜ao apresentada ao Programa de
P´os-Gradua¸c˜ao em Inform´atica da Pontif´ıcia
Universidade Cat´olica do Paran´a como requi-
sito parcial para obten¸c˜ao do t´ıtulo de Mes-
tre em Inform´atica.
Curitiba
2008
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
M´arcio Fuckner
Combina¸c˜ao de Classificadores
usando IAD
Disserta¸c˜ao apresentada ao Programa de
P´os-Gradua¸c˜ao em Inform´atica da Pontif´ıcia
Universidade Cat´olica do Paran´a como requi-
sito parcial para obten¸c˜ao do t´ıtulo de Mes-
tre em Inform´atica.
´
Area de Concentra¸c˜ao: Sistemas Inteligentes
Orientador: Prof. Dr. Fabr´ıcio Enembreck
Curitiba
2008
ads:
4
Para Ana Maria, com amor.
i
Agradecimentos
`
A minha mulher Ana Maria, por ser minha for¸ca e fonte de inspira¸c˜ao di´aria e
por ter compreendido a minha ausˆencia em tantas ocasi˜oes em que precisei me dedicar
integralmente ao trabalho.
Ao me u orientador Prof. Dr. Fabr´ıcio Enembreck por ser uma fonte de conhecimento
e incentivo ao longo da minha pesquisa, o que faz dele um modelo a ser seguido.
`
A Pontif´ıcia Universidade Cat´olica do Paran´a, aos professores do curso de P´os-Gradua¸c˜ao
em Inform´atica, em especial aos professores Dr. Edson Em´ılio Scalabrin e Dr. Br´aulio
Coelho
´
Avila pelas valiosas discuss˜oes e sugest˜oes dadas ao longo deste trabalho.
Ao meu grande amigo Daniel Pavelec, pela amizade duradoura e constante incentivo
na caminhada acadˆemica.
Ao grande amigo Lian pelo carinho e for¸ca que sempre me passou.
Ao parceiro acadˆemico e amigo Emerson Romanhuki pe lo esp´ırito de equipe e compa-
nheirismo que se manteve at´e os ´ultimos momentos de nossos trabalhos.
Ao meu irm˜ao Rodrigo, que acompanhou grande parte das etapas do meu trabalho.
ii
Sum´ario
Agradecimentos ii
Sum´ario iii
Lista de Figuras vi
Lista de Tabelas vii
Lista de Algoritmos viii
Lista de Abrevia¸c˜oes ix
Resumo xi
Abstract xii
Cap´ıtulo 1 - Introdu¸c˜ao
1.1 Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Motiva¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Organiza¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Cap´ıtulo 2 - Minera¸c˜ao de Dados
2.1 Defini¸c˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Aprendizagem Simb´olica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Aprendizagem a partir de
´
Arvores de Decis˜ao . . . . . . . . . . . . . . . . 6
2.4 Aprendizagem a partir de Regras . . . . . . . . . . . . . . . . . . . . . . . 10
2.4.1 Medidas de Avalia¸c˜ao de Regras . . . . . . . . . . . . . . . . . . . . 11
2.4.2 Interpreta¸c˜ao de Regras . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4.3 Classifica¸c˜ao e Sele¸c˜ao de Regras . . . . . . . . . . . . . . . . . . . 15
2.4.4 Codifica¸c˜ao de Regras Usando MDL . . . . . . . . . . . . . . . . . 17
2.5 Considera¸c˜oes Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Cap´ıtulo 3 - Minera¸c˜ao Distribu´ıda de Dados
3.1 Defini¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
iii
3.2 Voto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3 Multi-esquema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.4 Meta-aprendizagem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.5 Combina¸c˜ao de Classificadores Simb´olicos . . . . . . . . . . . . . . . . . . 23
3.6 Considera¸c˜oes Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Cap´ıtulo 4 - Inteligˆencia Artificial Distribu´ıda
4.1 Defini¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.2 Agentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.3 Sistemas Multi-Agente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.4 Resolu¸c˜ao Distribu´ıda de Problemas . . . . . . . . . . . . . . . . . . . . . . 30
4.4.1 Contract-net . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.4.2 Planejamento Distribu´ıdo . . . . . . . . . . . . . . . . . . . . . . . 33
4.4.3 Eco-resolu¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.5 Considera¸c˜oes Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Cap´ıtulo 5 - SDICCS - Um Sistema Distribu´ıdo para Combina¸c˜ao de Classifica-
dores Simb´olicos
5.1 Defini¸c˜oes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.2 Descri¸c˜ao do Conjunto de Exemplos Ilustrativo . . . . . . . . . . . . . . . 39
5.3 Prepara¸c˜ao dos Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.4 Etapa de Aprendizagem Local . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.4.1 Execu¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.5 Combina¸c˜ao dos Classificadores . . . . . . . . . . . . . . . . . . . . . . . . 45
5.5.1 Compartilhamento das Hip´oteses Distribu´ıdas (Hip) . . . . . . . . 45
5.5.2 Cria¸c˜ao da Hip´otese Hip
. . . . . . . . . . . . . . . . . . . . . . . . 47
5.5.3 Compartilhamento da Hip´otese Hip
. . . . . . . . . . . . . . . . . 53
5.6 Classifica¸c˜ao de Novos Exemplos . . . . . . . . . . . . . . . . . . . . . . . 53
5.7 Implementa¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.8 Trabalhos Relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.9 Considera¸c˜oes Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Cap´ıtulo 6 - Experimentos e Resultados
6.1 Prepara¸c˜ao dos Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
6.2 An´alise dos Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
iv
Lista de Figuras
2.1 Uma
´
Arvore de Decis˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Regras de Classifica¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Interpreta¸c˜ao Geom´etrica para uma
´
Arvore de Decis˜ao [PBM02] . . . . . . 14
2.4 Interpreta¸c˜ao Geom´etrica para um Conjunto de Regras n˜ao Ordenadas
[PBM02] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.1 A Estrutura B´asica de uma Minera¸c˜ao Distribu´ıda de Dados [FL98] . . . . 20
5.1 Fun¸c˜ao Objetivo f . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.2 Prepara¸c˜ao dos Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.3 Fun¸c˜ao Verdadeira f Ag
i
(x1, x2) para os 3 Agentes de Aprendizagem . . . . 42
5.4 Processo de Aprendizagem Local . . . . . . . . . . . . . . . . . . . . . . . 43
5.5 Regras Geradas pelos Agentes a
1
, a
2
e a
3
. . . . . . . . . . . . . . . . . . . 45
5.6 Processo de Combina¸c ˜ao dos Classificadores . . . . . . . . . . . . . . . . . 50
5.7 Combina¸c˜ao de Regras Conflitantes . . . . . . . . . . . . . . . . . . . . . . 51
5.8 Hip´otese Combinada (Hip
) . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5.9 Arquitetura do Sistema SDICCS . . . . . . . . . . . . . . . . . . . . . . . . 55
5.10 Registro no Ambiente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.11 Etapa de Classifica¸c˜ao Local . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.12 Avalia¸c˜ao de Regras em Hip
(Hip´oteses distribu´ıdas) . . . . . . . . . . . . 58
5.13 Etapa de Combina¸c˜ao dos Classificadores em Hip para obter Hip
. . . . . 59
5.14 Inferˆencia Usando o SDICCS . . . . . . . . . . . . . . . . . . . . . . . . . . 60
6.1 Compara¸c˜ao Gr´afica dos Resultados . . . . . . . . . . . . . . . . . . . . . . 66
6.2 Regras da Base Segment com Intersec ¸c˜ao . . . . . . . . . . . . . . . . . . . 68
vi
Lista de Tabelas
2.1 Uma Base de Treinamento [QUI93] . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Matriz de Contingˆencia de uma Regra R: B → H . . . . . . . . . . . . . . 11
2.3 Matriz de Contingˆencia com Freq¨uˆencias Relativas para uma Regra R: B
→ H . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
6.1 Caracter´ısticas das Bases Utilizadas nos Experimentos . . . . . . . . . . . 63
6.2 Quantidade de Exemplos de Treinamento por Agente . . . . . . . . . . . . 64
6.3 Taxas M´edias de Acerto . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
6.4 Grau de Cobertura do Conjunto Hip
e da Regra Default Local . . . . . . . 66
6.5 Quantidade M´edia de Regras Geradas . . . . . . . . . . . . . . . . . . . . . 67
6.6 Cobertura dos classificadores locais (Hip) e SDDICS (Hip
) . . . . . . . . 68
6.7 Complexidade M´edia das Regras Selecionadas . . . . . . . . . . . . . . . . 68
vii
Lista de Algoritmos
1 Busca de Satisfa¸c˜ao de um Eco-agente [FER03] . . . . . . . . . . . . . . . 35
2 Tentativa de Fuga de um Eco-agente [FER03] . . . . . . . . . . . . . . . . 35
3 Compartilhamento das Hip´oteses Distribu´ıdas entre os Agentes . . . . . . . 46
4 Algoritmo de Combina¸c˜ao de Hip´oteses . . . . . . . . . . . . . . . . . . . . 48
5 Algoritmo de Expans˜ao de Arestas . . . . . . . . . . . . . . . . . . . . . . 49
6 Classifica¸c˜ao de Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
viii
Lista de Abrevia¸c˜oes
PKD Descoberta de Conhecimentos em Paralelo / Parallel Knowledge Discovery
DKD Descoberta Distribu´ıda de Conhecimentos / Distributed Knowledge Disco-
very
KDD Descoberta de Conhecimentos a partir de Dados / Knowledge Data Disco-
very
MDL Menor Tamanho de uma Descri¸c˜ao / Minimum Description Length
DDM Minera¸c˜ao Distribu´ıda de Dados / Distributed Data Mining
IAD Inteligˆencia Artificial Distribu´ıda
IA Inteligˆencia Artificial
RDP Resolu¸c˜ao Distribu´ıda de Problemas
SMA Sistemas Multi-Agente
FIPA Organiza¸c˜ao para Agentes Inteligentes F´ısicos / Foundation for Intelligent
Physical Agents
JADE Ambiente de Desenvolvimento de Agentes em Java / Java Agent Develop-
ment Environment
PGP Planejamento Global Parcial / Partial Global Planning
GPGP Planejamento Global Parcial Generalizado / Generalized Partial Global
Planning
DCOP Satisfa¸c˜ao Distribu´ıda de Restri¸c˜oes / Distributed Constraint Optimization
Problems
SBB Divis˜ao e Conquista S´ıncrona / Synchronous Branch and Bound
ix
WEKA Ambiente para An´alise de Conhecimentos Waikato / Waikato Environment
for Knowledge Analysis
DF Facilitador de Diret´orios / Directory Facilitator
MTS Servi¸co de Transporte de Mensagens / Message Transport Service
UML Linguagem Unificada de Modelagem / Unified Modeling Language
ROC Receiver Operating Characteristic
x
Resumo
A execu¸c˜ao de algoritmos de aprendizagem de m´aquina para identifica¸c˜ao de
padr˜oes ou realiza¸c˜ao de predi¸c˜ao ´e uma etapa importante da minera¸c˜ao de dados. A
fus˜ao das t´ecnicas de minera¸c˜ao de dados e computa¸c˜ao distribu´ıda viabiliza a execu¸c˜ao
de algoritmos de aprendizagem de m´aquina em grandes bases de dados atrav´es da com-
bina¸c˜ao ou integra¸c˜ao de classificadores, sem que isso comprometa a confiabilidade das
predi¸c˜oes. Al´em disso, esta abordagem pode favorecer a descoberta de vis˜oes alternativas,
quando diferentes algoritmos s˜ao utilizados na mesma amostra. Algumas abordagens de
combina¸c˜ao de classificadores possuem baixa capacidade de explica¸c˜ao das inferˆencias,
uma vez que as decis˜oes dos combinadores em geral ocorrem em tempo de inferˆencia,
funcionando como uma caixa preta ou prejudicando a representa¸c˜ao final do modelo de-
vido a quantidade, complexidade ou grau de inconsistˆencia entre as regras. Este trabalho
apresenta uma proposta de gera¸c˜ao de um modelo unificado de regras geradas por agentes
de software a partir de bases de dados distribu´ıdas. Neste processo, uma base de dados ´e
dividida em N partes, que s˜ao utilizadas por agentes de software que geram N conjuntos
de hip´oteses, sob a forma de regras de classifica¸c˜ao ordenadas. Agentes reativos intera-
tivos alcan¸cam seus objetivos solicitando a valida¸c˜ao de seus conceitos a outros agentes
que avaliam as regras enviadas atrav´es de uma heur´ıstica proposta. A intera¸c˜ao entre
os agentes ´e capaz de produzir um conjunto de regras unificado e livre de conflitos. Os
indicadores de desempenho deste modelo distribu´ıdo de busca e as t´ecnicas utilizadas
para mensurar o conhecimento se mostram adequados quando comparados com outras
abordagens distribu´ıdas sobre bases de dados conhecidas da literatura.
Palavras-chave: Minera¸c˜ao Distribu´ıda de Dados, Combina¸c˜ao de Regras, Aprendi-
zagem Simb´olica, Resolu¸c˜ao Distribu´ıda de Problemas
xi
Abstract
The execution of machine learning algorithms in order to identify trends or pre-
diction purposes is an important step in the data mining context. The fusion of data
mining techniques and distributed computing leverages the execution of machine le arning
algorithms in large datasets through the classifier combination or integration causing po-
sitive effects on prediction reliability. Moreover, these approaches allow the discovery of
alternative visions, when different algorithms are used in the same dataset. Some classi-
fier combination approaches produces low level inference explanatory capabilities thanks
to the decision process made during the inf erence process, working as a “black box” or
generating poor quality models in terms of represe ntation (quantity, complexity or incon-
sistency level of rules). This work presents an unified ruleset generation process through
software agents using distributed datasets. In this process a dataset is splitted into N
subsets, which are used by s oftware agents. They generate N hipothesys, in the form of an
ordered classification ruleset. Interactive reactive agents reach their objectives validating
their concepts with others, which will use a proposed heuristic. The agent interaction
approach is capable of producing an unified ruleset free of conflicts. The performance me-
trics of the distributed search model and the techniques used to evaluate the knowledge
in well known literature databases are reasonable when compared with other approaches.
Keywords: Distributed Data Mining, Ruleset Combination, Symbolic Learning, Dis-
tributed Problem Solving
xii
Cap´ıtulo 1
Introdu¸c˜ao
Muitas das t´ecnicas de minera¸c˜ao de dados foram criadas para serem aplicadas
em bases de dados centralizadas e precisam de altera¸c˜oes para que sejam vi´aveis em um
ambiente distribu´ıdo. A de manda crescente para permitir a minera¸c˜ao de dados massivos
e distribu´ıdos em redes com limita¸c˜oes de banda e recursos computacionais motivaram o
desenvolvimento de m´etodos de PKD (Descoberta de Conhecimentos em Paralelo / Paral-
lel Knowledge Discovery) e DKD (Descoberta Distribu´ıda de Conhecimentos / Distributed
Knowledge Discovery) [KLM03] [KPHJ00].
Certas caracter´ısticas tornam invi´avel a execu¸c˜ao de algoritmos centralizados para
descoberta de conhecimentos. A quantidade e volume das bases de dados crescem a
cada dia e mais rapidamente do que as melhorias aplicadas em recursos computacionais
e t´ecnicas de aprendizagem indutiva [PC00]. Os motivos para criar modelos distribu´ıdos
de minera¸c˜ao de dados s˜ao diversos: privacidade, problemas inerentes `a localiza¸c˜ao f´ısica,
custo de transmiss˜ao de dados, limita¸c˜ao de algoritmos de aprendizagem de m´aquina ou
desempenho.
Analisar bases de dados com milhares de registros pode demandar muito tempo
e poder computacional se o algoritmo for aplicado de forma seq¨uencial. Este trabalho
prop˜oe um m´etodo que viabiliza a minera¸c˜ao distribu´ıda e descentralizada de dados,
gerando regras de classifica¸c˜ao consistentes sem que haja perda da confiabilidade. Este
trabalho mostra que o uso de agentes, mecanismos de coopera¸c˜ao e decomposi¸c˜ao de
tarefas contribui para a constru¸c˜ao de um modelo unificado de conhecimento extra´ıdo de
conjuntos particionados de dados.
2
1.1 Objetivo
O objetivo deste trabalho ´e a cria¸c˜ao de um framework baseado em agentes para
permitir que a atividade de descoberta de conhecimentos ocorra de forma distribu´ıda. A
solu¸c˜ao ´e composta por quatro etapas b´asicas:
• aquisi¸c˜ao de dados distribu´ıdos em N parti¸c˜oes;
• execu¸c˜ao de N agentes dotados de algoritmos de aprendizagem simb´olica sobre as
bases locais;
• intera¸c˜ao entre os agentes para combinar os classificadores gerados na etapa anterior
por meio de uma t´ecnica de resolu¸c˜ao de conflitos e busca em espa¸co de estados;
• classifica¸c˜ao de novos exemplos usando o conhecimento unificado e consensual.
Como resultado esperado, deve-se gerar um ´unico conjunto de regras reduzido,
por´em consistente e livre de conflitos. As regras dever˜ao apresentar um bom desempe-
nho sobre as parti¸c˜oes utilizadas para treinamento. A concentra¸c˜ao dos esfor¸cos ´e na
obten¸c˜ao de um modelo compreens´ıvel e com boa taxa de acerto. Uma vez comprovada
a eficiˆencia do framework, ele poder´a ser utilizado para integrar os c onhecimentos exis-
tentes e m aplica¸c˜oes distribu´ıdas, nos casos onde n˜ao ´e permitida a tomada de decis˜oes
contradit´orias, al´em do desenvolvimento de aplica¸c˜oes de minera¸c˜ao distribu´ıda de dados.
1.2 Motiva¸c˜ao
A utiliza¸c˜ao de agentes de software nas atividades de minera¸c˜ao de dados est´a
sendo amplamente aplicada e discutida [SPT
+
97] [SB02] [GA04] [SB05] [PASE06]. Os
agentes possuem caracter´ısticas intr´ınsecas de processamento paralelo, colabora¸c˜ao e ne-
gocia¸c˜ao. Neste cen´ario cada agente tem embutido em seu comportamento um algoritmo
de aprendizagem de m´aquina. Cada um est´a associado a um conjunto de treinamento
e valida¸c˜ao em alguns casos. Os agentes s˜ao dotados de caracter´ısticas que permitem o
planejamento e a colabora¸c˜ao com outros agentes, tendo como objetivo coletivo a cria¸c˜ao
de um classificador comum.
Uma quest˜ao importante e que vem sendo alvo desses estudos ´e como esses clas-
sificadores devem ser integrados. Existem diversas iniciativas explorando t´ecnicas de
minera¸c˜ao distribu´ıda de dados e compartilhamento de conhecimento. O trabalho apre-
sentado por [
PC00] aplica o conceito de Meta-aprendizagem, no qual classificadores s˜ao
3
combinados para aumentar o poder de predi¸c˜ao. Em [SB05] ´e apresentado um modelo
de negocia¸c˜ao cooperativa entre agentes. Podemos perceber que a integra¸c˜ao de conheci-
mento entre agentes ´e um assunto recente e que n˜ao possui uma solu¸c˜ao universal. Este
trabalho vem portanto ajudar a preencher esta lacuna deixada pelas t´ecnicas existentes
na literatura.
Outro aspecto motivador que deve ser levado em considera¸c˜ao s˜ao os ganhos ob-
tidos ao usar agentes para a resolu¸c˜ao de um problema: robustez, escalabilidade e na
ado¸c˜ao de um modelo de decomposi¸c˜ao de tarefas. A distribui¸c˜ao auxilia na decom-
posi¸c˜ao do problema, o que influencia positivamente na tratabilidade do problema. Por
outro lado, sob a ´otica de desenvolvimento, a complexidade ´e substancialmente maior,
uma vez que ´e necess´ario prover uma arquitetura que permita a coordena¸c˜ao, coopera¸c˜ao
e interoperabilidade semˆantica entre os agentes.
1.3 Organiza¸c˜ao
Este trabalho est´a organizado em 7 cap´ıtulos. O primeiro cap´ıtulo cont´em uma
breve introdu¸c˜ao. Os cap´ıtulos 2 a 4 cont´em a fundamenta¸c˜ao te´orica, necess´aria para o
desenvolvimento da pesquisa. No cap´ıtulo 5 ´e apresentada a metodologia para a solu¸c˜ao
do problema. O cap´ıtulo 6 apresenta os experimentos realizados e resultados obtidos. O
trabalho ´e conclu´ıdo com o cap´ıtulo 7.
4
Cap´ıtulo 2
Minera¸c˜ao de Dados
Nos ´ultimos anos tem se observado um crescimento acentuado das bases de dados
em diversas ´areas de aplica¸c˜ao [KLM03]. Estes dados podem ser transformados em conhe-
cimentos ´uteis, seja para explicar padr˜oes de comportamento ou para realizar predi¸c˜oes.
A an´alise tradicional dos dados aplicada por seres humanos ´e uma atividade
invi´avel, sendo imprescind´ıvel a cria¸c˜ao de m´etodos computacionais para a realiza¸c˜ao
desta tarefa. A KDD (Descoberta de Conhecimentos a partir de Dados / Knowledge Data
Discovery) ´e uma ´area de pesquisa focada no desenvolvimento de m´etodos e t´ecnicas para
transformar dados em informa¸c˜oes ´uteis. A Minera¸c˜ao de Dados ´e uma etapa impor-
tante do processo de KDD, que faz uso de algoritmos de aprendizagem de m´aquina e tem
como objetivo identificar padr˜oes em bases de dados, seja para descobrir comportamentos
relevantes, seja para a realiza¸c˜ao de predi¸c˜oes.
Neste cap´ıtulo s˜ao apresentados alguns conceitos sobre minera¸c˜ao de dados ne-
cess´arios para a compreens˜ao das principais dificuldades envolvidas nesta ´area de pesquisa.
O foco da pesquisa est´a voltado para aprendizagem indutiva, mais especificamente sobre
regras de classifica¸c˜ao. Os demais m´etodos de minera¸c˜ao s˜ao discutidos superficialmente.
2.1 Defini¸c˜oes
A minera¸c˜ao de dados em um contexto de KDD utiliza t´ecnicas conhecidas de
aprendizagem de m´aquina, reconhecimento de padr˜oes e m´etodos estat´ısticos para extrair
padr˜oes nos dados [FPSS96]. Diversas ´areas aplicam as t´ecnicas de minera¸c˜ao de dados
para extra¸c˜ao de padr˜oes relevantes. O tipo do problema e a natureza da informa¸c˜ao
desejada define qual t´ecnica de minera¸c˜ao ´e a mais adequada. Dentre as t´ecnicas existentes
´e poss´ıvel citar:
5
• Classifica¸c˜ao: ´e a descoberta de relacionamentos entre atributos de predi¸c˜ao e um
atributo meta, tamb´em conhecido como classe. O obj etivo neste caso ´e criar uma
fun¸c˜ao f
(x) que se aproxime de f(x), dado um conjunto de exemplos de treinamento
contendo os atributos previsores e a classe alvo;
• Associa¸c˜ao: consiste em identificar relacionamentos entre itens que ocorrem com
determinada freq ¨uˆencia em uma base de dados. Uma de suas t´ıpicas utiliza¸c˜oes ´e a
an´alise de transa¸c˜oes de compra (Market Basket Analysis);
• Regress˜ao: similar a classifica¸c˜ao, mas com o objetivo de encontrar uma fun¸c˜ao
f
(x) que se aproxime de f(x) para um atributo meta cont´ınuo;
• Agrupamento: Descob erta de grup os/classes formados por elementos com carac-
ter´ısticas comuns.
Como citado anteriormente, este trabalho concentra os esfor¸cos na descoberta do
conhecimento compreens´ıvel e na forma de regras de classifica¸c˜ao. Essa t´ecnica de apren-
dizagem de m´aquina ´e conhecida como aprendizagem simb´olica. A pr´oxima se¸c˜ao aborda
este tema.
2.2 Aprendizagem Simb´olica
Um sistema de aprendizagem de m´aquina supervisionado ´e um programa (indu-
tor) capaz de induzir uma descri¸c˜ao de conceitos (classificador) usando um conjunto de
exemplos conhecidos e previamente rotulados com as suas resp ectivas classes [PBM02].
Um algoritmo recebe como entrada o valor correto da fun¸c˜ao desconhecida para entradas
espec´ıficas e deve tentar descobrir a fun¸c˜ao desconhecida ou algo pr´oximo disso.
Formalmente ´e poss´ıvel definir que um exemplo ´e um par (x, f (x)), onde x ´e a
entrada e f (x) ´e a sa´ıda da fun¸c˜ao aplicada a x [RN04]. A vari´avel x pode ser interpretada
como um dado hist´orico ou tupla. Os atributos presentes em cada tupla podem ser do tipo
num´erico ou discreto. Baseado no conte´udo desses atributos, ´e poss´ıvel criar um modelo
para predi¸c˜ao de outro. Por exemplo, a partir de informa¸c˜oes sobre condi¸c˜oes do mercado
em diferentes per´ıodos, ´e poss´ıvel predizer como as a¸c˜oes de determinado mercado se
comportar˜ao. Quando o objetivo da predi¸c˜ao ´e um dado discreto, a tarefa de predi¸c˜ao ´e
chamada de classifica¸c˜ao. Por outro lado, quando o alvo ´e um dado cont´ınuo, a t´ecnica ´e
chamada de regress˜ao [AW97]. As solu¸c˜oes s˜ao consideradas fun¸c˜oes de aproxima¸c˜ao que
descrevem resumidamente um espa¸co de atributos.
6
Sistemas de aprendizagem simb´olica s˜ao utilizados em situa¸c˜oes onde ´e necess´ario,
al´em da capacidade de predi¸c˜ao, apresentar um modelo compreens´ıvel para seres humanos.
´
Arvores de decis˜ao e regras de classifica¸c˜ao s˜ao representa¸c˜oes de aprendizagem simb´olica
e s˜ao usadas como mecanismos para descoberta de padr˜oes e predi¸c˜ao. Tanto ´arvores de
decis˜ao quanto regras de classifica¸c˜ao tˆem se mostrado extremamente competitivas em
termos de precis˜ao se comparadas a outros m´etodos de predi¸c˜ao como por exemplo, redes
neurais [AW97].
No caso de ´arvores de decis˜ao, o conhecimento ´e representado atrav´es de uma
´arvore, sendo que cada n´o da ´arvore corresponde a um atributo e as arestas correspondem
a condi¸c˜oes sobre os atributos. A folha corresponde ao conceito alvo ou classe associada
aos testes. J´a as regras de classifica¸c˜ao, s˜ao representa¸c˜oes no formado se < cond > ent˜ao
< alvo >. Elas podem ser entendidas analogamente a ´arvores de decis˜ao como se fossem
o caminho completo do n´o raiz de uma ´arvore at´e um conceito alvo.
A avalia¸c˜ao do desempenho dos modelos gerados ´e um passo importante do pro-
cesso de descoberta. Certos modelos apresentam alto desempenho na base de treinamento,
por´em podem ser menos precisos em dados n˜ao conhecidos. Ru´ıdos e novos padr˜oes di-
minuem a capacidade de predi¸c˜ao do modelo. Uma avalia¸c˜ao em duas etapas se faz
necess´aria: Divis˜ao da base de exemplos em base de treinamento e base de teste. Na
primeira fase, o modelo ´e gerado a partir da base de treinamento. Na segunda, os dados
n˜ao conhecidos pelo modelo s˜ao apresentados para avalia¸c˜ao do desempenho. T´ecnicas
como a valida¸c˜ao cruzada podem ser usadas para avaliar o modelo atrav´es de sucessivas
itera¸c˜oes. Na valida¸c˜ao cruzada, os dados s˜ao divididos em k subconjuntos com tamanhos
aproximadamente iguais. Os subconjuntos s˜ao treinados k vezes. Em cada itera¸c˜ao, um
dos subconjuntos ´e deixado de lado, sendo usando posteriormente para a fase de testes.
2.3 Aprendizagem a partir de
´
Arvores de Decis˜ao
´
Arvores de decis˜ao s˜ao utilizadas em diferentes ´areas para realiza¸c˜ao de inferˆencia
indutiva, atrav´es da execu¸c˜ao de algoritmos de aprendizagem de m´aquina. Uma ´arvore de
decis˜ao ´e gerada a partir de uma base de exemplos de treinamento, os quais s˜ao descritos
utilizando um n´umero finito de atributos. Esses atributos s˜ao utilizados para predi¸c˜ao de
um atributo meta. Uma ´arvore de decis˜ao ´e comp osta pelos seguintes elementos:
• um n´o de decis˜ao, que repres enta um atributo a ser utilizado na predi¸c˜ao;
• N arestas contendo testes relativos ao atributo, sendo que cada aresta ´e ligada a
outro n´o. O n´o subseq¨uente pode ser um outro n´o de decis˜ao ou um n´o folha;
7
• um n´o folha, que ´e a representa¸c˜ao do final do caminho da ´arvore e cont´em o valor
do atributo meta.
A ´arvore de decis˜ao pode ser usada para classificar um exemplo, iniciando no n´o
raiz da ´arvore e movendo-se atrav´es dos n´os de decis˜ao at´e chegar a uma folha. A Tabela
2.1 apresenta um conjunto de exemplos usado para a constru¸c˜ao da ´arvore mostrada na
Figura 2.1
1
.
Tabela 2.1: Uma Base de Treinamento [QUI93]
Outlook Temperature Humidity Windy Play
sunny 85 85 FALSE no
sunny 80 90 TRUE no
overcast 83 86 FALSE yes
rainy 70 96 FALSE yes
rainy 68 80 FALSE yes
rainy 65 70 TRUE no
overcast 64 65 TRUE yes
sunny 72 95 FALSE no
sunny 69 70 FALSE yes
rainy 75 80 FALSE yes
sunny 75 70 TRUE yes
overcast 72 90 TRUE yes
overcast 81 75 FALSE yes
rainy 71 91 TRUE no
Figura 2.1: Uma
´
Arvore de Decis˜ao
Uma ´arvore de decis˜ao ´e constru´ıda recursivamente atrav´es da estrat´egia dividir-
para-conquistar, onde um problema complexo ´e dividido em problemas menores. Inicial-
mente, um atributo ´e selecionado como n´o e uma divis˜ao dos dados ´e criada para cada
valor do atributo. O processo ´e repetido recursivamente para cada divis˜ao de dados at´e
1
Figura Extra´ıda do Aplicativo Weka (Waikato Environment for Knowledge Analysis)
8
que todas as instˆancias do subconjunto gerado tenham a mes ma classe alvo. Devido a
essa caracter´ıstica de particionamento, uma ´arvore ´e essencialmente uma conjun¸c˜ao de
disjun¸c˜oes, onde cada caminho ´e uma conjun¸c˜ao dos atributos e seus testes e a ´arvore
como um todo ´e uma disjun¸c˜ao de todas essas conjun¸c˜oes [SHA00]. O seguinte algoritmo
descreve a sequˆencia de passos para a cria¸c˜ao de uma ´arvore de decis˜ao:
1. Quando todos ou a maioria dos exemplos no conjunto pertencerem a uma ´unica
classe, declare o n´o como sendo uma folha, representando a classe;
2. Selecione o melhor atributo usando alguma heur´ıstica e crie uma divis˜ao do conjunto,
gerando novos v´ertices, sendo que para cada v´ertice deve ser atribu´ıdo um valor.
Para dados cont´ınuos os valores devem ser atribu´ıdos no formato a ≤ v e a > v,
onde v ´e o valor do atributo a;
3. Continue o processo de crescimento dos n´os at´e que todas as instˆancias sejam dire-
cionadas em alguma folha.
Para que o algoritmo gere uma ´arvore compacta, ´e necess´ario usar algum crit´erio
estat´ıstico que determine qual ser´a o atributo ideal para descrever o dado. O algoritmo
C4.5 [QUI93], usa uma heur´ıstica baseada na teoria da informa¸c˜ao para identificar o
atributo que apresenta maior ganho. A escolha do atributo que ser´a utilizado para divis˜ao
´e baseado em uma propriedade estat´ıstica chamada ganho de informa¸c˜ao, que estabelece
o seguinte princ´ıpio: a informa¸c˜ao presente em uma mensagem depende da probabilidade
da sua ocorrˆencia e pode ser mensurada em bits. Em outras palavras, antes de adicionar
um n´o e arestas que particionam o conjunto de exemplos, ´e necess´ario medir a entropia (ou
desordem) dos dados antes e depois do particionamento. Se a quantidade de informa¸c˜ao
necess´aria para a classifica¸c˜ao for menor ap´os a ramifica¸c˜ao, e nt˜ao o n´ıvel de entropia ou
desordem foi reduzido, sendo o particionamento bem sucedido.
Em um primeiro momento ´e necess´ario calcular a entropia dos dados antes do
particionamento. Portanto, dado um conjunto de K exemplos em um n´o, C sendo a
quantidade de classes e p(K, j) a propor¸c˜ao de casos em K que pertencem a j-´esima
classe, a informa¸c˜ao ´e obtida a partir da f´ormula apresentada em 2.1.
info(K) =
C−1
j=0
−p(K, j) ∗ log
2
(p(K, j)) (2.1)
O ganho da informa¸c˜ao para cada atributo a ser testado (f´ormula 2.2) ´e a diferen¸ca
entre a quantidade de informa¸c˜ao antes da divis˜ao e a quantidade de informa¸c˜ao ap´os a
divis˜ao, sendo que m ´e a quantidade de subconjuntos gerados, |T i| ´e a quantidade de
9
exemplos positivos do subconjunto, |T | ´e a quantidade de exemplos do subconjunto e K
´e a quantidade de exemplos da base de treinamento.
ganho(K) = info(K) −
m
i=1
|T i|
|T |
∗ Inf o(Ki) (2.2)
Em certas situa¸c˜oes a f´ormula de ganho de informa¸c˜ao ´e ineficiente. O problema
ocorre nos casos onde o atributo possui valores ´unicos para os particionamentos poss´ıveis,
como por exemplo um c´odigo de produto ou a representa¸c˜ao extra´ıda da impress˜ao digital
de uma pessoa. O valor m´aximo do ganho de informa¸c˜ao ´e gerado para esses atributos,
fazendo com que a base seja dividida em v´arios segmentos contendo apenas um exemplo no
pior caso. Para corrigir esse problema, o crit´erio de taxa de ganho usa o grau de entropia
gerado pela divis˜ao da base de exemplos para normalizar o valor do ganho. Essa t´ecnica
´e chamada de ganho m´edio. Primeiramente ´e calculado o ganho da divis˜ao (f´ormula 2.3)
ganho da divisao(X) = −
m
i=1
|T i|
|T |
∗ log
2
(
|T i|
|T |
) (2.3)
Finalmente, para obter o ganho m´edio ´e usada a f´ormula 2.4.
ganho medio(X) =
ganho(X)
ganho da divisao(X)
(2.4)
Para classificar perfeitamente os dados de treinamento, uma ´arvore pode pro duzir
um efeito de superadapta¸c˜ao. A ´arvore pode ficar demasiadamente ajustada aos exemplos
de treinamento e ineficiente na predi¸c˜ao de dados desconhecidos. Faz-se necess´ario uma
t´ecnica de generaliza¸c˜ao para aumentar o poder de predi¸c˜ao do modelo. A poda ´e uma
t´ecnica utilizada para minimizar es se problema. A poda consiste em transformar um n´o
candidato em uma folha, sendo que este corresponde `a classe mais comum encontrada
nos e xemplos de treinamento cobertos pelo n´o. E la pode ocorrer basicamente de duas
maneiras:
• Pr´e-poda: ocorre em tempo de constru¸c˜ao do classificador e utiliza algum crit´erio
para evitar a subdivis˜ao desnecess´aria do conjunto;
• P´os-poda: ´e aplicada ap´os a cria¸c˜ao da ´arvore completa. Consiste em simplificar a
´arvore, transformando n´os de decis˜ao em folhas, baseado na classe mais freq¨uente.
A pr´e-poda apresenta melhor desempenho j´a que evita o crescimento da ´arvore
com ramos desnecess´arios. Por´em a t´ecnica de p´os-poda ´e a mais utilizada e trabalhos
mostram que ela apresenta melhores resultados [QUI93].
10
2.4 Aprendizagem a partir de Regras
Apesar das ´arvores de decis˜ao se apresentarem compreens´ıveis por seres humanos
como um conjunto de hip´oteses, o tamanho da ´arvore ´e decisivo para a extra¸c˜ao de
informa¸c˜oes relevantes sobre o modelo. Como o ´ultimo n´o de um caminho completo da
´arvore ´e uma f olha e depende do caminhamento pelos diversos n´os adjacentes, a leitura
pode ficar prejudicada. Regras de classifica¸c˜ao, tornam-se visivelme nte mais atraentes
por se apresentarem em um formato se < cond > ent˜ao < alvo >, onde < cond > ´e uma
conjun¸c˜ao de atributos e testes e < alvo > ´e a classe correspondente ao padr˜ao. Al´em
disso os sistemas de indu¸c˜ao de regras tem alto valor para aplica¸c˜oes que necessitam de
precis˜ao e compreensibilidade dos modelos gerados [LS95]. A Figura 2.2 apresenta um
conjunto de regras gerado a partir dos exemplos apresentados na Tabela 2.1.
R1 =
se outlook = sunny
e humidity ≤ 75 → play = yes
R2 =
se outlook = sunny
e humidity > 75 → play = no
R3 =
se outlook = overcast → play = yes
R4 =
se outlook = rainy
e windy = true → play = no
R5 =
se outlook = rainy
e windy = f alse → play = yes
Figura 2.2: Regras de Classifica¸c˜ao
Com o objetivo de padroniza¸c˜ao, ser´a adotada a representa¸c˜ao Body → Head ou
resumidamente B → H para uma regra de classifica¸c˜ao. Onde B ´e a conjun¸c˜ao de pares
de atributos e valores e H ´e a classe associada. Quando as regras de classifica¸c˜ao s˜ao
geradas a partir de ´arvores de decis˜ao, B ´e todo o caminho percorrido do n´o ra´ız da
´arvore at´e a folha, onde os n´os s˜ao convertidos em atributos, as arestas em testes e H ´e
a folha (a classe correspondente ao padr˜ao especificado nas condi¸c˜oes). As regras obtidas
diretamente a partir de uma ´arvore de decis˜ao s˜ao mutuamente exclus ivas, j´a que um
caminho da ´arvore de decis˜ao ´e uma disjun¸c˜ao de uma conjun¸c˜ao. A vantagem dessa
t´ecnica ´e que uma regra pode ser avaliada de forma independente e n˜ao haver´a conflito
entre regras. Entende-se por conflito, regi˜oes de dados que s˜ao cobertas por regras que
prevˆeem valores diferentes para o atributo meta. A desvantagem desta t´ecnica ´e que
pode ser gerado um conjunto extenso de regras dependendo do espa¸co de dados a ser
11
percorrido. Para reduzir esse efeito, algoritmos executam otimiza¸c˜oes e podas nas regras
com o objetivo de generaliza¸c˜ao.
A maneira pela qual um algoritmo avalia novos dados vai depender da maneira
que as regras foram geradas. Se foram geradas diretamente a partir de uma ´arvore de
decis˜ao, a avalia¸c˜ao ´e an´aloga ao estilo top-down da ´arvore: as regras podem ser avaliadas
em qualquer ordem, j´a que podem ser entendidas como um caminho completo da ´arvore.
Certos tipos de regras devem obedecer um crit´erio de ordena¸c˜ao pr´e-estabelecido. E ssa
heur´ıstica depende do algoritmo que gerou a regra. Com o objetivo de aprofundar o
conhecimento sobre regras de classifica¸c˜ao, a pr´oxima se¸c˜ao apresenta algumas medidas
de avalia¸c˜ao, crit´erios de sele¸c˜ao e ordena¸c˜ao de regras.
2.4.1 Medidas de Avalia¸c˜ao de Regras
Como o objetivo da pesquisa ´e a integra¸c˜ao de conjuntos de regras, h´a uma neces-
sidade de adotar t´ecnicas para avaliar as regras. As medidas devem fornecer informa¸c˜oes
sobre precis˜ao, qualidade e grau de interesse do conhecimento induzido. V´arias medidas
de avalia¸c˜ao de regras foram pesquisadas com o objetivo de auxiliar a compreens˜ao e
poder de predi¸c˜ao dos modelos simb´olicos. O trabalho de Nada Lavrac et. al. [LFZ99]
apresenta uma compila¸c˜ao de diversas medidas de avalia¸c˜ao de regras, que ser´a apresen-
tado adiante. Antes, ´e importante apresentar a matriz de contingˆencia, a qual produz as
informa¸c˜oes necess´arias para obten¸c˜ao das medidas de avalia¸c˜ao.
A matriz de contingˆencia ´e uma generaliza¸c˜ao da matriz de confus˜ao, que ´e a base
padr˜ao para calcular medidas de avalia¸c˜ao de hip´oteses em problemas de classific a¸c˜ao
[PBM02]. A diferen¸ca fundamental ´e que a matriz de contingˆencia tem uma rela¸c˜ao de
1 : 1 com as regras, enquanto que a matriz de confus˜ao tem uma rela¸c˜ao 1 : N, sendo
que N ´e a quantidade de regras do classificador, funcionando como uma caixa preta para
todo o modelo. A Tab ela 2.2 apresenta uma matriz de contingˆencia para uma regra R no
formato B → H.
Tabela 2.2: Matriz de Contingˆencia de uma Regra R: B → H
B ¬B
H hb h¬b h
¬H ¬hb ¬h¬b ¬h
b ¬b n
Da matriz de contingˆencia ´e poss´ıvel extrair as seguintes informa¸c˜oes:
• hb ´e a quantidade de exemplos onde tanto H quanto B s˜ao verdadeiros;
12
• h¬b ´e a quantidade de exemplos onde H ´e verdadeiro e B ´e falso;
• ¬hb ´e a quantidade de exemplos onde H ´e falso e B ´e verdadeiro;
• ¬h¬b ´e a quantidade de exemplos onde H e B s˜ao falsos;
• b ´e a quantidade de exemplos onde B ´e verdadeiro;
• ¬b ´e a quantidade de exemplos onde B ´e falso;
• h ´e a quantidade de exemplos onde H ´e verdadeiro;
• ¬h ´e a quantidade de exemplos onde H ´e falso;
• n ´e a quantidade total de exemplos.
Tamb´em ´e poss´ıvel criar uma matriz de contingˆencia com freq¨uˆencias relativas,
onde h´a uma normaliza¸c˜ao dos exemplos atrav´es de n, funcionando como uma probabili-
dade da ocorrˆencia do evento f(e) =
e
n
tamb´em denotado fe. Na Tabela 2.3 ´e apresen-
tada a matriz de contingˆencia com freq¨uˆencias relativas. Com a matriz de contingˆencia
´e poss´ıvel obter os dados necess´arios para realizar a maioria das medidas propostas na
literatura.
Tabela 2.3: Matriz de Contingˆencia com Freq¨uˆencias Relativas para uma Regra R: B →
H
B ¬B
H fhb fh¬b f h
¬H f ¬hb f¬h¬b f¬h
b ¬b 1
Abaixo, est˜ao relacionadas algumas medidas de avalia¸c˜ao de regras presentes em
[LFZ99].
• Precis˜ao (2.5): ´e a medida que indica a probabilidade de H e B serem verdadeiras.
P rec(R) = P (H|B) =
P (HB)
P (B)
=
fhb
fb
(2.5)
• Erro (2.6): ´e obtido atrav´es de 1 − P rec(R). Quanto maior o erro, menos precisa
´e a regra.
Err(R) = 1 − P rec(r) = P (¬H|B) =
f¬hb
fb
(2.6)
13
• Confian¸ca Negativa (2.7): corresponde `a medida de precis˜ao para exemplos n˜ao
cobertos pela regra.
NegRel (R) = P (¬H|¬B) =
P (¬H¬B)
P (¬B)
=
f¬h¬b
f¬h
(2.7)
• Sensitividade (2.8): ´e a probabilidade condicional de B ser verdade dado que H ´e
verdade. Quanto maior a sensitividade, mais exemplos s˜ao cobertos pela regra.
Sens(R) = P (B|H) =
P (HB)
P (H)
=
fhb
fh
(2.8)
• Especificidade (2.9): ´e a probabilidade condicional de B ser falso dado que H ´e
falso.
Spec(R) = P (¬B|¬H) =
P (¬H¬B)
P (¬H)
=
f¬h¬b
f¬h
(2.9)
• Cobertura (2.10): ´e a probabilidade de B ser verdade. Quanto maior a cobertura,
maior a quantidade de exemplos cobertos pela regra.
Cov(R) = P (B) = f b (2.10)
• Suporte (2.11): ´e a probabilidade de H e B serem verdade. Quanto maior o suporte,
maior a quantidade de exemplos da classe ser˜ao cobertas pela regra.
Sup(R) = P (HB) = fhb (2.11)
• Novidade (2.12): ´e a probabilidade de B e H serem estatisticamente dependentes.
Nov(R) = P (HB) − P (H)P (B) = f hb − f h.f b (2.12)
• Satisfa¸c˜ao (2.13): ´e uma medida que indica se h´a aumento relativo na precis˜ao
entre a verdade da regra B e a regra B → H.
´
E uma medida indicada para tarefas
voltadas `a descoberta de conhecimentos, sendo capaz de promover um equil´ıbrio
entre regras com diferentes condi¸c˜oes e conclus˜oes.
Sat(R) =
P (¬H) − P (¬H|B)
P ¬H
=
f¬h −
f¬hb
fb
f¬h
(2.13)
14
• Precis˜ao Relativa (2.14): mede o ganho de precis˜ao em rela¸c˜ao a uma regra default.
RP rec(R) = P (H|B) − P (H) =
fhb
fb
− f h (2.14)
• Confian¸ca Negativa Relativa (2.15): ´e similar `a precis˜ao relativa, mas usa uma regra
default falsa.
RNegRel(R) = P (¬H|¬B) − P (¬H) =
f¬h¬b
f¬b
− f ¬h (2.15)
• Sensitividade Relativa (2.16): mede o ganho de sensitividade em rela¸c˜ao a uma
regra default.
RP rec(R) = P (B|H) − P (B) =
fhb
fh
− f b (2.16)
• Especificidade Relativa (2.17): ´e similar `a sensitividade relativa, mas usa uma regra
default falsa.
RSpec(R) = P (¬B|¬H) − P (¬B) =
¬h¬b
f¬h
− f ¬b (2.17)
2.4.2 Interpreta¸c˜ao de Regras
´
Arvores de decis˜ao dividem o espa¸co de exemplos em regi˜oes dis juntas. Cada
exemplo ´e classificado por apenas um ´unico ramo da ´arvore [PBM02]. Transformar uma
´arvore em regras s em que ocorra um processo de generaliza¸c˜ao ou otimiza¸c˜ao tem o
mesmo efeito. A ordem das regras ´e irrelevante. A Figura 2.3 apresenta uma ´arvore de
decis˜ao de duas classes (+ e −) e dois atributos (x1 e x2) e a interpreta¸c˜ao geom´etrica
correspondente.
Figura 2.3: Interpreta¸c˜ao Geom´etrica para uma
´
Arvore de Decis˜ao [PBM02]
J´a em regras de classifica¸c˜ao, a forma de aplica¸c˜ao das regras vai depender da
maneira com que as mesmas foram constru´ıdas.
´
E poss´ıvel classificar as regras em dois
tipos:
15
• Regras n˜ao ordenadas: Regras mutuamente exclusivas s˜ao chamadas de regras n˜ao
ordenadas, porque apenas uma delas cobrir´a um dado exemplo. Todas as regras
podem ser utilizadas na avalia¸c˜ao de um exemplo. Regras geradas diretamente a
partir de uma ´arvore de decis˜ao se enquadram ne ssa classifica¸c˜ao;
• Regras ordenadas: Regras que n˜ao s˜ao mutuamente exclusivas e podem apresentar
conflitos, ou seja, mais de uma regra pode cobrir o exemplo. Neste caso a ordem
de avalia¸c˜ao das regras ´e fundamental, j´a que algum crit´erio de ordena¸c˜ao, baseado
na especificidade ou desempenho, por exemplo, pode ter sido utilizado durante a
gera¸c˜ao das regras.
Na Figura 2.4 ´e apresentada uma interpreta¸c˜ao geom´etrica, para um conjunto de
trˆes regras n˜ao ordenadas e duas classes, + e ◦.
Figura 2.4: Interpreta¸c˜ao Geom´etrica para um Conjunto de Regras n˜ao Ordenadas
[PBM02]
2.4.3 Classifica¸c˜ao e Sele¸c˜ao de Regras
Regras ordenadas dependem diretamente do mecanismo de ordena¸c˜ao e sele¸c˜ao,
j´a que n˜ao s˜ao mutuamente exclusivas. Coenen e Leng [CL04] apresentam 5 crit´erios de
ordena¸c˜ao de regras, a saber:
• CSA (Confian¸ca, Suporte e Antecedentes): As regras s˜ao ordenadas de acordo com
os indicativos de confian¸ca, suporte e quantidade de antecedentes da regra. Baseado
na matriz de contingˆencia, a medida de confian¸ca pode ser obtida a partir da f´ormula
fhb
b
. A medida de suporte ´e dada pelo indicador fhb da matriz de contingˆencia e
finalmente, a medida do antecedente ´e obtida a partir da quantidade de condi¸c˜oes
16
presentes em B ou as condi¸c˜oes da regra. Coenen e Leng [CL04] mencionam que
a probabilidade do fator de confian¸ca ser igual para duas regras ´e muito baixo.
Portanto, os indicativos de suporte e quantidade de antecedentes raramente s˜ao
utilizados;
• WRA (Precis˜ao Relativa com Peso): ´e um mecanismo unificado para medir regras.
O termo “relativo” indica que a e xpectativa do suporte ´e utilizada para normalizar
o valor desta medida. Esta medida foi criada especificamente para mecanismos de
ordena¸c˜ao de regras que refletem v´arias medidas de avalia¸c˜ao em uma s´o. A id´eia ´e
que WRA seja uma s´ıntese da “interessabilidade” de uma regra. Usando a matriz
de contingˆencia, ´e poss´ıvel obter WRA com a f´ormula fb(
fhb
fb
− f h);
• Medida de precis˜ao de Laplace: ´e utilizada por alguns algoritmos para ordena¸c˜ao
de regras. Esta medida leva em considera¸c˜ao os exemplos, corretos, incorretos e a
quantidade de classes presentes no problema. Quanto maior ´e a precis˜ao de Laplace,
melhor ´e a regra. Utilizando a matriz de contingˆencia, a f´ormula para a obten¸c˜ao
da medida de Laplace ´e
fbh+1
fbh+fb¬h+k
, onde k ´e o n´umero de classes;
• X
2
ou Chi quadrado: ´e uma medida estat´ıstica usada para determinar se duas
vari´aveis s˜ao independentes atrav´es da compara¸c˜ao de valores observados e espera-
dos. A f´ormula ´e obtida a partir de x
2
=
n
i=1
(Oi−Ei)
2
Ei
, onde n ´e o n´umero de valores
observados/esperados. Se o valor resultante for menor do que um limiar estipulado,
ent˜ao pode se afirmar que h´a uma rela¸c˜ao entre os valores esperados e observados,
caso contr´ario n˜ao h´a. Quanto maior o valor, maior o grau de independˆencia da
regra;
• ACS (Antecedentes, Confian¸ca e Suporte): A proposta ´e uma alternativa a CSA,
uma vez que d´a prioridade a regras mais espec´ıficas.
Adicionalmente, os autores [CL04] apresentam 3 formas de sele¸c˜ao de regras (fi-
ring):
• Melhor regra: Parte do princ´ıpio de que apenas uma regra pode classificar um
exemplo. Dado um exemplo, o algoritmo percorrer´a o conjunto de regras e aquela
que se ajustar aos atributos do exemplo ser´a utilizada e as demais regras ser˜ao
desprezadas;
• Melhores K regras: O algoritmo selecionar´a as K “melhores” regras do c lassificador
que satisfa¸cam a condi¸c˜ao apresentada, onde K ´e um parˆametro estipulado. Atrav´es
de um crit´erio de vota¸c˜ao, a classe vencedora ser´a selecionada;
17
• Todas as regras: O algoritmo selecionar´a todas as regras do classificador que
satisfa¸cam a condi¸c˜ao apresentada e um crit´erio de desempate baseado em X
2
´e
utilizado.
Os testes realizados no trabalho de Coenen e Leng [CL04] utilizando combina¸c˜oes
dos diferentes crit´erios de ordena¸c˜ao e sele¸c˜ao indicaram que n˜ao houve um crit´erio de
ordena¸c˜ao que se sobressai em rela¸c˜ao aos outros. Quanto `a sele¸c˜ao, o crit´erio “melhor
regra” apresentou melhor desempenho.
O algoritmo C4.5rules [QUI93], que gera regras de classifica¸c˜ao a partir de uma
´arvore de decis˜ao usa um m´etodo de ordena¸c˜ao de regras baseado no princ´ıpio MDL
(Menor Tamanho de uma Descri¸c˜ao / Minimum Description Length). Este princ´ıpio
ser´a descrito na pr´oxima se¸c˜ao.
2.4.4 Codifica¸c˜ao de Regras Usando MDL
O princ´ıpio MDL po de ser explicado como um modelo de comunica¸c˜ao no qual
um processo emissor transmite para um receptor a descri¸c˜ao de uma teoria T e o dado
D do qual ele ´e derivado [
QR89]. A descri¸c˜ao do tamanho da mensagem obtida consiste
no custo necess´ario para desc rever um dado. O princ´ıpio MDL diz que a melhor teoria
derivada de um conjunto de exemplos vai minimizar a quantidade de bits necess´arios para
codificar a mensagem completa, que consiste na teoria juntamente com suas exce¸c˜oes
[QUI95]. Trazendo o c onceito MDL para o problema de avalia¸c˜ao do conjunto de regras,
uma teoria ´e representada pelo conjunto de regras, o dado ´e representado pela base de
treinamento e a mensagem ´e a regra propriamente dita. Da mes ma forma que o algoritmo
C4.5 [QUI93], as regras s˜ao agrupadas pela cabe¸c a da regra (H) ou a classe, sendo criado
k subc onjuntos de regras. A quantidade de informa¸c˜ao ent˜ao ´e calculada para cada regra
pertencente `a classe. Ao final ´e poss´ıvel calcular a quantidade de informa¸c˜ao para o
subconjunto todo. Nos par´agrafos a seguir s˜ao apresentadas as etapas para realizar o
c´alculo da quantidade da informa¸c˜ao do subconjunto.
• Para codificar uma regra, ´e necess´ario especificar cada condi¸c˜ao presente no corpo
da regra (B). A cabe¸ca da regra n˜ao precisa ser codificada j´a que todas as regras no
subconjunto pertencem a mesma classe. A quantidade de informa¸c˜ao em bits para
um determinado conjunto de regras ´e log
2
(prob) onde prob ´e a probabilidade dos
atributos se adequarem a regra;
• Codificar um conjunto de regras significa somar a quantidade de bits de cada regra,
subtraindo um cr´edito similar para a ordena¸c˜ao das regras;
18
• As exce¸c˜oes s˜ao codificadas indicando quais dos casos cobertos pela regra S s˜ao falsos
positivos e aqueles que n˜ao s˜ao cobertos s˜ao os falsos negativos. Se as regras cobrem
r dos n casos de treinamento, com fp (falsos positivos) e f n (falsos negativos), o
n´umero de bits necess´arios para codificar as exce¸c˜oes ´e dada pela f´ormula 2.18.
excecao = log
2
(
r
fp
) + log
2
(
n − r
fn
) (2.18)
O primeiro termo refere-se `a quantidade de bits necess´arios para indicar os falsos
positivos entre os casos cobertos pela regra e o segundo termo ´e uma express˜ao
similar, indicando os falsos negativos entre os casos n˜ao cobertos;
• O custo de um subconjunto ´e mensurado pela soma da codifica¸c˜ao das regras e suas
exce¸c˜oes. Quanto menor a soma, melhor a teoria representada por S.
2.5 Considera¸c˜oes Finais
Neste cap´ıtulo foram apresentados alguns conceitos de minera¸c˜ao de dados e apren-
dizagem simb´olica, com ˆenfase nos m´etodos de avalia¸c˜ao, classifica¸c˜ao e sele¸c˜ao de regras.
A maioria dos conceitos pode ser aplicada em qualquer conjunto de regras, desde que se
obede¸ca a caracter´ıstica principal dos classificadores.
´
E importante questionar: o con-
junto de regras ´e ordenado ou n˜ao? Qual ´e o mecanismo de classifica¸c˜ao (best-first, voto,
best-k-first)? Uma vez que o trabalho proposto n˜ao ´e voltado para nenhum algoritmo
em especial, estes conceitos formaram uma base importante para o desenvolvimento do
trabalho.
19
Cap´ıtulo 3
Minera¸c˜ao Distribu´ıda de Dados
Muitos algoritmos estat´ısticos de minera¸c˜ao de dados, reconhecimento de padr˜oes
e aprendizagem de m´aquina requerem que todos os dados a serem analisados estejam
em mem´oria, podendo falhar j´a que nem sempre o espa¸co de mem´oria ´e suficiente. A
minera¸c˜ao distribu´ıda de dados ´e uma fus˜ao das t´ecnicas de minera¸c˜ao de dados e sis-
temas distribu´ıdos que viabiliza a aplica¸c˜ao de mine ra¸c˜ao em diversas ´areas. Aplica¸c˜oes
das mais diversas naturezas usam t´ecnicas de minera¸c˜ao distribu´ıdas, tais como fus˜ao de
informa¸c˜ao, minera¸c˜ao de dados, detec¸c˜ao de intrus˜ao e descoberta de padr˜oes. Es peci-
almente a atividade de classifica¸c˜ao tem recebido diversas contribui¸c˜oes [DIE97] [TD00]
[PC00] [HK00] [OCA01] [PASE06] [BMP06] [BGB07].
Neste cap´ıtulo ser´a apresentada uma defini¸c˜ao sobre minera¸c˜ao distribu´ıda de da-
dos e mecanismos de combina¸c˜ao de classificadores simb´olicos s˜ao discutidos.
3.1 Defini¸c˜ao
DDM (Minera¸c˜ao Distribu´ıda de Dados / Distributed Data Mining) ´e a associa¸c˜ao
de t´ecnicas de minera¸c˜ao de dados com sistemas distribu´ıdos que permite o uso do parale-
lismo e distribui¸c˜ao de tarefas entre diversos processadores. Segundo Freitas e Lavington
[FL98], a atividade de minera¸c˜ao distribu´ıda de dados pode ser dividida em trˆes fases:
1. Dividir a base de exemplos em p subconjuntos, onde p ´e o n´umero de processadores.
Cada subconjunto ´e enviado para um processador;
2. Executar em cada processador um algoritmo de minera¸c˜ao de dados em seu ambiente
local; os processadores podem executar o mesmo algoritmo de minera¸c˜ao de dados
ou diferentes algoritmos;
20
3. Combinar o conhecimento local descoberto por cada algoritmo de minera¸c˜ao de
dados em um modelo global e consistente.
Os autores ainda discutem que esse conhecimento global ´e diferente do conheci-
mento descoberto se o algoritmo for aplicado no conjunto inteiro formado pela uni˜ao dos
subconjuntos de dados individuais. O classificador tende a ficar menos preciso a medida
que a quantidade de classificadores aumenta e a quantidade de dados em cada subconjunto
diminui.
A Figura 3.1 ilustra o processo, onde os dados s˜ao representados por retˆangulos,
os algoritmos por elipses e o conhecimento obtido por triˆangulos.
Figura 3.1: A Estrutura B´asica de uma Minera¸c˜ao Distribu´ıda de Dados [FL98]
Na terceira fase do DDM, citada acima, o conhecimento local descoberto pelos
processadores pode ser combinado de diferentes maneiras. Uma das maneiras mais triviais
´e atrav´es da t´ecnica de vota¸c˜ao simples. Esse processo pode ser utilizado para resolver
diferentes tipos de problemas, como por exemplo:
• Extensibilidade: Suportam a inclus˜ao de novas tecnologias de minera¸c˜ao;
• Portabilidade: Capacidade de operar em diferentes ambientes ou plataformas;
• Escalabilidade: Eficiˆencia em minerar grandes volumes de dados sem perda de
qualidade;
• Eficiˆencia: Determina a capacidade de utilizar corretamente os recursos dispon´ıveis;
• Compatibilidade: Integra¸c˜ao de informa¸c˜oes para bases de dados similares, mas
com diferentes esquemas, para gerar modelos de dados mais precisos.
Muitas pesquisas tˆem sido feitas no desenvolvimento de algoritmos com o objetivo
de se produzir t´ecnicas escal´aveis e computacionalmente mais eficientes de minera¸c˜ao de
grandes conjuntos de dados. A seguir s˜ao apresentados alguns algoritmos de minera¸c˜ao
distribu´ıda de dados dese nvolvidos com esse objetivo.
21
3.2 Voto
Um m´etodo dinˆamico de combina¸c˜ao e resolu¸c˜ao de conflitos ´e a estrat´egia de voto.
Esta t´ecnica consiste em aplicar um exemplo desconhecido em diferentes classificadores.
A classe associada a esse exemplo ser´a aquela apontada pela maioria dos classificadores
em tempo de exec u¸c˜ao [PC00].
De acordo com Chan e Stolfo [CS95a], uma das varia¸c˜oes da t´ecnica de voto ´e o voto
ponderado, que assoc ia um peso determinado pela precis˜ao do classificador sobre a base
de treinamento. Os pesos dos votos s˜ao somados e uma instˆancia de teste ´e classificada
de acordo com a classe com maior peso obtido.
Shawla [SHA00] apresenta alguns experimentos usando a t´ecnica de voto simples e
ponderado aplicado diretamente a regras de classifica¸c˜ao. Duas medidas foram associadas
`as regras: O fator de certeza e a precis˜ao. Os resultados apresentaram melhora sens´ıvel
na predi¸c˜ao, utilizando o voto ponderado em rela¸c˜ao ao voto simples.
3.3 Multi-esquema
Segundo Enembreck e
´
Avila [EV06], uma estrat´egia simples de combina¸c˜ao ´e a
sele¸c˜ao de um classificador dentre diversos. O desempenho de um classificador pode ser
medido no conjunto de dados a partir do percentual de classifica¸c˜ao considerada correta.
Esta t´ecnica consiste na escolha de um classificador que possui a melhor qualidade dentre
um conjunto de classificadores que usam amostras do conjunto completo. Essa t´ecnica ´e
demasiadamente suscet´ıvel a resultados de baixa qualidade, pois a constru¸c˜ao de classi-
ficadores simb´olicos ´e fortemente influenciada pelo m´etodo de amostragem, mesmo que
as distribui¸c˜oes sejam semelhantes. Isso favorece a superadapta¸c˜ao do modelo a uma
amostra espec´ıfica.
3.4 Meta-aprendizagem
O conceito de meta-aprendizagem ´e inspirado na estrat´egia de stacking, criada por
Wolpert em [WOL90]. A id´eia geral ´e minimizar a taxa de erro de classificadores, trans-
formando as predi¸c˜oes dos classificadores em instˆancias de treinamento, utilizadas para a
gera¸c˜ao de um novo classificador. Chan e Stolfo [CS95a] [CS95b] propuseram t´ecnicas de
meta-aprendizagem inspiradas na estrat´egia de stacking. As t´ecnicas consistem em com-
binar N classificadores e utiliz´a-los como elemento de entrada para outro classificador.
Cada algoritmo de aprendizagem local ´e tratado como uma caixa preta sendo poss´ıvel
22
combinar diferentes algoritmos de aprendizagem. Os c lassificadores locais s˜ao chamados
de classificadores base. A tarefa de combina¸c˜ao consiste em utilizar as predi¸c˜oes dos clas-
sificadores base e transform´a-las em uma base de treinamento meta-n´ıvel. Esses dados s˜ao
utilizados para a gera¸c˜ao de um meta-classificador, que representa um modelo unificado.
A constru¸c˜ao de meta-classificadores pode ocorrer diversas vezes sendo poss´ıvel
criar uma hierarquia de classificadores. A meta-aprendizagem p ode ser resumida em 4
etapas:
• classificadores base s˜ao treinados usando bases de exemplos locais;
• as predi¸c˜oes s˜ao geradas pelos classificadores em uma base de valida¸c˜ao separada;
• uma base de meta-treinamento ´e montada a partir das predi¸c˜oes dos classificadores
base;
• um meta-classificador ´e treinado usando a base de meta-treinamento.
Chan e Stolfo [CS95a] apresentaram duas t´ecnicas para combinar as predi¸c˜oes dos
classificadores base, chamadas ´arbitro e combinador.
Na t´ecnica do ´arbitro, ´e criado um classific ador especial, chamado ´arbitro, que ir´a
decidir a classe final de predi¸c˜oes para uma dada entrada. O ´arbitro gera um classificador
executando um algoritmo de aprendizagem sobre instˆancias dif´ıceis de classificar com os
classificadores base. A classifica¸c˜ao ´e feita sobre a predi¸c˜ao dos algoritmos de aprendiza-
gem locais e a predi¸c˜ao do ´arbitro. Estas predi¸c˜oes s˜ao combinadas, retornando a maioria
de ocorrˆencias, com preferˆencia dada `as predi¸c˜oes do ´arbitro em caso de empate.
J´a no caso do combinador, o meta-classificador recebe como entrada as predi¸c˜oes
realizadas por cada um dos classificadores base juntamente com as predi¸c˜oes corretas
presentes em cada base de treinamento local. Outras informa¸c˜oes tais como os valores dos
atributos, tamb´em podem ser adicionadas ao conjunto de dados a ser utilizado na meta-
classifica¸c˜ao, dependendo da estrat´egia adotada na implementa¸c˜ao da meta-aprendizagem.
A meta-aprendizagem us a estes dados para descobrir a rela¸c˜ao entre as predi¸c˜oes feitas
pelos algoritmos locais e as predi¸c˜oes corretas.
Enembreck e
´
Avila [EV06] apresentam um modelo de meta-aprendizagem para
integra¸c˜ao de classificadores simb´olicos chamado KNOMA. O processo consiste em usar
como entrada N classificadores base gerados a partir de bases distribu´ıdas. Os conjuntos
de regras s˜ao unificados gerando um ´unico conjunto de regras. Baseado nesse conjunto,
´e gerada uma meta-base de treinamento em uma etapa preliminar, sendo que cada meta-
instˆancia ´e a representa¸c˜ao de uma regra e os atributos deste conjunto s˜ao os antecedentes
23
(B) da regra. A classe da meta-instˆancia ´e dada pela classe ou cabe¸ca (H) da regra. Um
meta-classificador definitivo ´e gerado usando essa base.
Segundo Chan e Stolfo [CS95a], o uso de classificadores com diferentes tendˆencias
criam um classificador mais preciso. A combina¸c˜ao de classificadores considerados me-
lhores em um meta-classificador podem, provavelmente, formar classificadores com maior
precis˜ao e eficiˆencia, sem utilizar buscas exaustivas em um espa¸co inteiro de possibilidades.
No entanto, Freitas e Lavington [FL98] afirmam que a precis˜ao da predi¸c˜ao conseguida
com t´ecnicas de meta-aprendizagem tende a diminuir quando o n´umero de subconjuntos
de dados aumentar, a menos que ocorra um aumento na quantidade de dados contidos
em cada subconjunto. Al´em disso, t´ecnicas de meta-aprendizagem podem reduzir a com-
preensibilidade do conhecimento des coberto.
3.5 Combina¸c˜ao de Classificadores Simb´olicos
A combina¸c˜ao de classificadores consiste na unifica¸c˜ao de classificadores aprendidos
a partir de bases de dados disjuntas, gerando um modelo consistente. Muitas pesquisas
tem sido realizadas, com o objetivo de criar t´ecnicas de unifica¸c˜ao de classificadores.
Provost e Hennessy [PH96] demonstraram que qualquer regra que tenha um de-
sempenho aceit´avel em uma base de exemplos integral, ter´a um desempenho aceit´avel em
pelo menos um fragmento da mesma base. A esse fenˆomeno ´e dado o nome de “Proprie-
dade de invariˆancia de particionamento”. Isto sugere que um conjunto de regras gerado
atrav´es de classificadores em bases disjuntas conter´a as mesmas regras presentes no con-
junto completo. Em um trabalho de Provost e Hennessy [PH96] foram identificadas as
mesmas regras presentes no conjunto de regras gerado a partir da base integral, al´em de
outras novas regras. Entretanto no trabalho de Hall et. al. [HCBK99] ´e apresentado
um cen´ario onde foram utilizados trˆes classificadores: um classificador para uma base
de exemplos integral e dois classificadores na base dividida. Como resultado, as bases
disjuntas n˜ao apresentaram nenhuma das regras presentes na base completa. Isto ocorreu
porque o classificador (C4.5) utiliza o ganho de informa¸c˜ao para escolha do atributo de
testes e ´e altamente dependente da base de treinamento (algoritmo inst´avel). Portanto, o
algoritmo utilizado no classificador tem forte influˆencia na t´ecnica utilizada para a inte-
gra¸c˜ao e resolu¸c˜ao dos conflitos. Al´em disso, cada algoritmo cont´em um bias expl´ıcito ou
impl´ıcito que tende a favorecer certas generaliza¸c˜oes em detrimento de outras: o ponto
forte de um pode ser o fraco de outro [DIE89] [SB02]. Em geral, a combina¸c˜ao de indutores
incrementa a precis˜ao reduzindo o bias. O objetivo da integra¸c˜ao ´e diminuir as limita¸c˜oes
de t´ecnicas individuais, atrav´es da hibridiza¸c˜ao ou fus˜ao de v´arias t´ecnicas [SB05].
24
Hall et. al [HCBK99] prop˜oem um m´etodo de integra¸c˜ao de conjuntos de regras
geradas a partir de bases de dados disjuntas. Dados N conjuntos de treinamento, s˜ao
gerados N conjuntos de regras em processadores distintos. Ao final, ´e gerado um modelo
livre de conflitos e com confiabilidade equivalente a um conjunto de regras geradas a
partir da base de treinamento. Cada regra ter´a uma medida de desempenho, baseada na
precis˜ao e quantidade de exemplos cobertos pela regra. Regras que tenham desempenho
menor do que um limiar s˜ao descartadas. Algumas caracter´ısticas relevantes da t´ecnica:
• nenhuma regra ´e eliminada sem ter sido avaliada por todos os subconjuntos;
• regras que indicam a mesma classe s˜ao simplificadas, eliminando uma das regras e
mantendo a mais abrangente;
• regras que se apresentarem muito pr´oximas de um limiar s˜ao especializadas. A
especializa¸c˜ao consiste em recuperar os exemplos cobertos pela regra e prolongar a
´arvore criando uma regra especializada.
O m´etodo apresentado por Hall mostrou desempenho compar´avel em termos de
confiabilidade em rela¸c˜ao ao classificador obtido a partir da base de dados integral.
No trabalho de Bernardini [BER02], foi desenvolvido um m´etodo de combina¸c˜ao de
classificadores simb´olicos, que consiste em selecionar regras de classificadores previamente
constru´ıdos por algoritmos de aprendizagem e compor um classificador final. O crit´erio
de sele¸c˜ao das regras ´e baseado em medidas de avalia¸c˜ao de regras. Apesar de identificar
boas regras dentro do conjunto, de acordo com um especialista, as taxas de erro ficaram
altas quando comparadas com os classificadores base.
O trabalho de Hamberger e Lavrac [GL00] [GLK02] introduz uma abordagem de
tomada de decis˜oes baseada em consenso. Basicamente ´e composta pelas seguintes etapas:
• ´e gerado um conjunto de regras que apontam para a mesma classe, sendo mais
pr´oxima do processo de decis˜ao feito por humanos;
• para que a regra seja inclu´ıda ´e necess´ario um valor m´ınimo de suporte;
• ´e apresentado um modelo de decis˜ao no qual diferentes regras podem se r incorpo-
radas. Estas regras podem ser geradas por diferentes classificadores ou codificadas
por seres humanos;
• o classificador recusa-se a classificar um exemplo se as regras entram em conflito ou
nenhuma regra for disparada.
Este modelo ´e recomendado nas situa¸c˜oes onde o erro de uma previs˜ao n˜ao ´e
permitido. Por outro lado perde na completeza j´a que alguns exemplos n˜ao s˜ao cobertos.
25
3.6 Considera¸c˜oes Finais
Neste cap´ıtulo foram apresentados alguns conceitos sobre minera¸c˜ao distribu´ıda de
dados e t´ecnicas de integra¸c˜ao de conhecimentos. No pr´oximo cap´ıtulo ser´a apresentada
uma defini¸c˜ao de inteligˆencia artificial distribu´ıda, suas subdivis˜oes e t´ecnicas de resolu¸c˜ao
distribu´ıda de problemas. Os conceitos de IAD (Inteligˆencia Artificial Distribu´ıda) s˜ao
elementos importantes para o trabalho, considerando que o problema apresentado ocorre
em um ambiente distribu´ıdo e a metodologia ´e inspirada em modelos de resolu¸c˜ao dis-
tribu´ıda de problemas.
26
Cap´ıtulo 4
Inteligˆencia Artificial Distribu´ıda
Nas pr´oximas se¸c˜oes s˜ao apresentados alguns conceitos sobre inteligˆencia artificial
distribu´ıda, agentes de software, sistemas multi-agente, resolu¸c˜ao distribu´ıda de problemas
e alguns mecanismos de coordena¸c˜ao e resolu¸c˜ao de conflitos. As t´ec nicas de IAD formam
a base para o desenvolvimento do m´etodo de combina¸c˜ao de modelos em um ambiente
distribu´ıdo discutido nos cap´ıtulo
5.
4.1 Defini¸c˜ao
IAD ´e um ramo da IA (Inteligˆencia Artificial) focada no desenvolvimento de
princ´ıpios computacionais e modelos para construir, descrever, implementar e analisar
os padr˜oes de intera¸c˜ao e coordena¸c˜ao, tanto para pequenas quanto grandes sociedades
de agentes [LES99a].
Segundo Bond e Gasser [BG88], a IAD pode ser dividida em duas ´areas fun-
damentais de pesquisa: RDP (Resolu¸c˜ao Distribu´ıda de Problemas) e SMA (Sistemas
Multi-Agente). Segundo Jennings et. al. ([JSW98]), a RDP descreve como um pro-
blema em particular pode ser resolvido por um grupo de m´odulos (n´os), que cooperam
atrav´es da divis˜ao e compartilhamento do conhecimento acerca de um problema e da sua
solu¸c˜ao. Em um sistema RDP puro, todas as estrat´egias de intera¸c˜ao s˜ao incorporadas
como parte integral do sistema. Por outro lado, a pesquisa em SMA est´a concentrada no
comportamento individual de uma cole¸c˜ao de agentes em um ambiente, com o objetivo
de resolver um certo problema. Sob uma perspectiva reativa, um SMA pode ser definido
como uma rede de solucionadores de problemas com baixo acoplamento, que trabalham
juntos para resolver problemas que est˜ao acima das capacidades ou conhecimento de cada
solucionador [DL89].
Bond e Gasser [BG89] enumeram v´arios benef´ıcios ao utilizar IAD para a resolu¸c˜ao
27
de problemas:
• Adaptabilidade: sistemas modelados em IAD se encaixam com a realidade de
problemas distribu´ıdos em termos espaciais, l´ogicos, temporais ou semˆanticos;
• Custo: pequenas unidades computacionais podem ser mais eficientes quando os
custos de comunica¸c˜ao n˜ao s˜ao relevantes;
• Desenvolvimento e Gerenciamento: a inerente modularidade do sistema permite o
desenvolvimento das partes do mesmo de forma separada e paralela;
• Eficiˆencia e Velocidade: a concorrˆencia e a distribui¸c˜ao dos processos em diferentes
m´aquinas pode aumentar a velocidade de process amento haja visto o paralelismo
na execu¸c˜ao das tarefas.
• Integra¸c˜ao: a integra¸c˜ao de recursos distribu´ıdos e at´e mesmo heterogˆeneos tais
como hardware e software de diferentes plataformas;
• Isolamento/Autonomia: o controle de processos locais pode ser interpretado como
uma maneira de prote¸c˜ao ou de aumento da seguran¸ca do sistema;
• Naturalidade: alguns problemas s˜ao naturalmente melhor resolvidos atrav´es de
uma configura¸c˜ao distribu´ıda;
• Confiabilidade: os sistemas distribu´ıdos podem exibir um grau maior de confiabi-
lidade e de seguran¸ca quando comparados aos sistemas centralizados, pois podem
prover redundˆancia de dados e m´ultiplas verifica¸c˜oes.
• Limita¸c˜oes de Recursos: os agentes computacionais individuais ligados a recursos
escassos podem, atrav´es da coopera¸c˜ao, superar limites t´ecnicos;
• Especializa¸c˜ao: cada agente pode ter um papel bem definido na resolu¸c˜ao do
problema.
As duas principais ´areas da IAD (SMA e RDP) diferem na forma de constru¸c˜ao da
solu¸c˜ao do problema, mas que tˆem em comum entidades chamadas agentes. A Resolu¸c˜ao
Distribu´ıda de Problemas adota uma vis˜ao top-down, dividindo o problema em partes que
corresponder˜ao a m´odulos computacionais, sendo o processo de co ordena¸c˜ao das a¸c˜oes
definido ainda em tempo de projeto. Os sistemas multi-agente s˜ao compostos por entida-
des computacionais, denominadas agentes, com capacidades e objetivos individuais que,
uma vez agrupados em sociedade, trabalham juntos visando atingir o objetivo do sistema,
28
sendo que os agentes devem raciocinar a respeito das a¸c˜oes e do pro ces so de coordena¸c˜ao
em si.
Quanto ao termo autonomia citado como uns dos benef´ıcios da IAD, Castelfranchi
e Facone em [CF98] detectam v´arios n´ıveis de autonomia, uma vez que este ´e um conceito
que est´a diretamente associado a rela¸c˜ao que um agente tem com os outros agentes. Ele
pode ter n´ıveis de influˆencia sobre os outros.
Segundo os autores, os seguintes itens devem ser satisfeitos para que o agente seja
completamente autˆonomo:
• O agente tem os seus pr´oprios objetivos e n˜ao s˜ao derivados dos objetivos dos outros;
• O agente ´e capaz de tomar decis˜oes sobre objetivos que est˜ao em conflito;
• O agente pode adotar objetivos de outros agentes de forma deliberada, para atingir
seus objetivos;
4.2 Agentes
Wooldrige e Jennings [WJ95] propuseram duas maneiras de visualizar um agente:
uma no¸c˜ao forte e uma no¸c˜ao fraca. A no¸c˜ao fraca define um agente como um sistema
baseado em hardware ou mais especificamente em software dotado das propriedades de
autonomia, habilidade social, reatividade e pr´o-atividade. J´a a no¸c˜ao forte de agente o
caracteriza como uma entidade que al´em das propriedades acima possui caracter´ısticas
ou conceitos aplicados usualmente em seres humanos tais como cren¸cas, conhecimento,
inten¸c˜ao, emo¸c˜ao e uma interface que representa o estado desses agentes visualmente.
Coletivamente, agentes podem ser considerados elementos de software que exibem
um comportamento autˆonomo e orientado a objetivos. Um agente pode desempenhar ati-
vidades integralmente atuando como um sistema standalone. No entanto, na maioria dos
casos, esse elemento ´e modelado em um contexto multi-agente, onde um comportamento
global depende da intera¸c˜ao entre os agentes.
Zambonelli e Jennings [ZJW01] criam duas categorias de sistemas multi-agente:
• sistemas de resolu¸c˜ao distribu´ıda de problemas, onde o agente foi desenvolvido es-
pecificamente para trabalhar em grupo para atingir um objetivo comum;
• sistemas abertos, onde agentes n˜ao necessariamente tˆem um objetivo em comum e
podem apresentar um comportamento competitivo.
29
Em sistemas abertos, o agente nem sempre ´e dotado das capacidades para realizar
todas as a¸c˜oes necess´arias, tornando-se dependente de outros agentes, podendo ou n˜ao ser
atendido. Segundo Castelfranchi e outros autores [CdRFP98], duas teorias proporcionam
n´ıveis razo´aveis de colabora¸c˜ao e organiza¸c˜ao: (i) A delega¸c˜ao e (ii) a ado¸c˜ao. Em (i), a
colabora¸c˜ao entre agentes ocorre atrav´es da aloca¸c˜ao de tarefas de um dado agente para
outro agente, atrav´es de um compromisso. Quando um agente A precisa de uma a¸c˜ao de
um agente B, a inten¸c˜ao ´e registrada no seu plano. Em (ii) um agente B tem um objetivo
que tamb´em ´e objetivo de outro agente. Tanto (i) quanto (ii) podem ser unilaterais: B
pode ignorar a dele ga¸c˜ao de A, assim como A pode ignorar a ado¸c˜ao de B.
No cen´ario proposto de minera¸c˜ao distribu´ıda, um agente pode englobar todas as
capacidades necess´arias para um classificador local: comunica¸c˜ao, coopera¸c˜ao, m´ultiplos
comportamentos (ora um agente pode solicitar a avalia¸c˜ao de um conjunto de hip´oteses
por outros agentes, ora ser revisor das hip´oteses). Neste trabalho, ser´a dado um maior
enfoque no estudo de t´ecnicas de resolu¸c˜ao distribu´ıda de problemas j´a que a atividade
caracteriza-se mais com a tarefa de coopera¸c˜ao de agentes que poss uem objetivos comuns
e pap´eis bem definidos.
4.3 Sistemas Multi-Agente
SMA ´e uma sub-area da IAD e se concentra na modelagem e classifica¸c˜ao de agentes
individuais em um universo multi-agente. Em um SMA n˜ao ´e necess´ario que o agente
seja individualmente inteligente para alcan¸car um objetivo globalmente inteligente. De
acordo com Ferber [FER03], um SMA pode ser definido como uma aplica¸c˜ao distribu´ıda
composta de indiv´ıduos independentes, heterogˆeneos, distribu´ıdos e inteligentes chamados
agentes, que podem cooperar entre si para a resolu¸c˜ao de problemas complexos. De acordo
com Lesser [LES99b], um sistema multi-agente ´e um sistema computacional no qual dois
ou mais agentes interagem ou trabalham juntos para realizar uma tarefa ou para satisfazer
um conjunto de objetivos.
A principal caracter´ıstica de um SMA ´e prover mecanismos para a cria¸c˜ao de sis-
temas computacionais a partir de entidades independentes de software chamados agentes,
os quais interagem dentro de um ambiente compartilhado entre todos os membros da
sociedade, a qual provˆe altera¸c˜oes no estado deste ambiente. De acordo com Wooldrige
e Jennings [WJ95], ´e necess´ario prover um mecanismo de intera¸c˜ao e coordena¸c˜ao des-
sas entidades, j´a que cada uma delas possui capacidades distintas, bem como diferentes
objetivos em rela¸c˜ao aos estados esperados do ambiente em que est˜ao inseridos. Apesar
da caracter´ıstica de baixo acoplamento e inde pendˆencia dos agentes ´e necess´ario padro-
30
nizar o seu desenvolvimento para permitir um ambiente comum de compatibilidade e
interoperabilidade no ambiente. A FIPA (Organiza¸c˜ao para Agentes Inteligentes F´ısicos
/ Foundation for Intelligent Physical Agents) ´e um ´org˜ao que tem por objetivo facilitar a
comunica¸c˜ao entre agentes f´ısicos.
´
E respons´avel pela padroniza¸c˜ao da arquitetura, pro-
tocolos de comunica¸c˜ao e intera¸c˜ao e representa¸c˜ao dos conhecimentos [FIP07]. V´arios
frameworks de desenvolvimento de agentes s˜ao compat´ıveis com a espe cifica¸c˜ao FIPA,
como por exemplo JADE (Ambiente de Desenvolvimento de Agentes em Java / Java
Agent Development Environment) [BCPR03] e JACK [YOS03] .
4.4 Resolu¸c˜ao Distribu´ıda de Problemas
RDP ´e uma sub-´area da IA D com ˆenfase na utiliza¸c˜ao de grupos de agentes para
resolver um problema complexo. Al´em das caracter´ısticas de conhecimento, capacidade,
informa¸c˜ao e e specializa¸c˜ao, um agente ´e um sistema resolvedor de problemas que n˜ao ´e
capaz de realizar suas tarefas sozinho ou pelo menos n˜ao consegue fazˆe-lo de forma t˜ao
precisa em compara¸c˜ao ao que conseguiria trabalhando junto com outros agentes [DUR99].
Resolver problemas distribu´ıdos requer coerˆencia e competˆencia dos agentes. Em
outras palavras, um agente pode ter um incentivo para trabalhar em grupo e deve sa-
ber desempenhar sua atividade. Problemas que utilizam RDP j´a possuem um grau de
coerˆencia intr´ınseco, j´a que ´e esperado que os agentes desenvolvidos desempenhem suas
tarefas com o objetivo de um resultado comum. Portanto, as t´ecnicas de RDP s˜ao concen-
tradas no item competˆencia. RDP presume a existˆencia de um problema a ser resolvido
e as expectativas de como a solu¸c˜ao dever´a ocorrer. De forma geral, os agentes desig-
nados para a solu¸c˜ao do problema dever˜ao formular as solu¸c˜oes de cada sub-problema e
sintetiz´a-las em uma solu¸c˜ao comum. Al´em da compe tˆencia necess´aria para resolver um
sub-problema, o agente precisa da competˆencia para planejar como a resolu¸c˜ao ocorrer´a,
ou seja, como os agentes far˜ao a decomposi¸c˜ao dos problemas em sub-problemas, aloc´a-
los para outros agentes, compartilhar solu¸c˜oes dos sub-problemas e sintetiz´a-las em uma
´unica solu¸c˜ao. Portanto, a atividade de planejamento distribu´ıdo ´e fortemente interligada
a RDP.
Segundo Durfee e Lesser [DL91], existem v´arias raz˜oes para construir sistemas
baseados em RDP: (i) Uso do paralelismo com o objetivo de maximizar a utiliza¸c˜ao
de recursos. (ii) Em certas situa¸c˜oes, a caracter´ıstica do problema ´e originalmente dis-
tribu´ıda. Nesse tipo de sistema, a maior dificuldade ´e criar diversas capacidades para
resolver sub-problemas que al´em de serem complexos dependem de capacidades distintas.
Outra motiva¸c˜ao ´e a disposi¸c˜ao f´ısica dos elementos envolvidos em um problema. Um
31
exemplo pode ser a tarefa de minera¸c˜ao distribu´ıda aonde ´e invi´avel centralizar dados
geograficamente dispersos. (iii) As cren¸cas dos agentes envolvidos no problema tamb´em
podem ser distribu´ıdas, ou seja, ´e poss´ıvel encapsular um grau de inteligˆencia no com-
portamento do agente para resolver o problema, sem que seja necess´ario criar uma figura
de agente centralizador. (iv) O resultado da resolu¸c˜ao do problema deve ser distribu´ıdo,
viabilizando a execu¸c˜ao por diversos agentes. A centraliza¸c˜ao deve ser evitada por uma
s´erie de motivos (paralelismo, disponibilidade do coordenador, latˆencia de comunica¸c˜ao).
´
E prefer´ıvel que os agentes atualizem seus planos de forma unilateral ou com um baixo
n´ıvel de comunica¸c˜ao quando isto n˜ao for poss´ıve l.
O compartilhamento de tarefas entre agentes compreende os seguintes passos:
• Decomposi¸c˜ao de tarefas: Gerar o conjunto de tarefas que podem ser potenci-
almente repassadas para outros. Nesta etapa uma grande tarefa ´e dividida em
sub-tarefas que podem ser executadas em agentes diferentes;
• Aloca¸c˜ao das tarefas: Consiste em associar tarefas a agentes com as competˆencias
necess´arias para a realiza¸c˜ao da tarefa;
• Realiza¸c˜ao da tarefa: Os agentes apropriados realizam cada sub-tarefa, o que pode
incluir nova decomposi¸c˜ao e aloca¸c˜ao de tarefas recursivamente at´e encontrar uma
atividade atˆomica;
• Agrupamento dos resultados: Quando um agente finaliza sua tarefa e passa o
resultado para um agente apropriado que conhece as raz˜oes da decomposi¸c˜ao e sabe
como compor o resultado em um resultado global.
Segundo Gatti e Amigoni [GA04], na negocia¸c˜ao cooperativa, cada agente tem
uma vis˜ao parcial do problema e os resultados s˜ao compartilhados utilizando negocia¸c˜ao,
na tentativa de resolver conflitos, resultantes das vis˜oes parciais. O protocolo Contract-
net proposto por Smith [SD83] pode ser utilizado como uma estrat´egia de coordena¸c˜ao
eficiente entre agentes. A se¸c˜ao 4.4.1 apresenta uma defini¸c˜ao deste protocolo, voltado
para o compartilhamento de tarefas.
Existem diversas outras abordagens sofisticadas para coordena¸c˜ao de sistemas dis-
tribu´ıdos cooperativos como por exemplo o PGP (Planejamento Global Parcial / Partial
Global Planning) e o GPGP (Planejamento Global Parcial Generalizado / Generalized
Partial Global Planning) apresentado por Decker e Lesser em [DL95] e t´ecnicas de DCOP
(Satisfa¸c˜ao Distribu´ıda de Restri¸c˜oes / Distributed Constraint Optimization Problems),
tais como SBB (Divis˜ao e Conquista S´ıncrona / Synchronous Branch and Bound) [HY97]
32
e Adopt [PJMY02] . Neste trabalho s˜ao desc ritas apenas as t´ecnicas mais relevantes para
a cria¸c˜ao do m´etodo proposto.
4.4.1 Contract-net
Baseado em protocolos de mercado p´ublico, o Contract-net [SD83] destina-se a
permitir a aloca¸c˜ao eficiente de tarefas para agentes capazes de efetuar a resolu¸c˜ao de
um problema e spec´ıfico. Este protocolo pode ser considerado como um processo de con-
trata¸c˜ao, iniciado por um agente que pretende solicitar algum servi¸co ou tarefa. O pro-
tocolo ´e composto de quatro etapas: an´uncio da tarefa, encaminhamento das propostas,
an´alise das propostas e emiss˜ao do contrato. Durfee [DUR99], cita o Contract-net como
um protocolo eficiente para decomposi¸c˜ao de tarefas. Al´em disso o processo de negocia¸c˜ao
cooperativa tem sido usado nas ´areas de pesquisa de aloc a¸c˜ao de tarefas e minera¸c˜ao dis-
tribu´ıda [SB02] [GA04] [BD03] [MLH03] [ZLP05].
A modelagem de agentes para resolu¸c˜ao distribu´ıda de problemas, gera um con-
junto de agentes com diferentes capacidades de resolu¸c˜ao. Portanto, para que um agente
receba uma determinada tarefa e fa¸ca a decomposi¸c˜ao em sub-tarefas, ´e necess´ario aloc´a-
las para agentes apropriados. Conceitualmente ´e poss´ıvel que um agente tenha uma tabela
contendo as suas capacidades, sendo simples selecionar o agente apropriado para aquela
tarefa. Por´em, certas decis˜oes ocorrem de maneira dinˆamica. O Contract-net estabelece
uma forma de comunica¸c˜ao entre agentes para a aloca¸c˜ao de tarefas. Um agente, que
no protocolo Contract-net ´e chamado de solicitante, decomp˜oe um problema maior em
uma s´erie de sub-problemas e anuncia cada sub-problema na rede, juntamente com as
especifica¸c˜oes de quais agentes s˜ao eleg´ıves para o sub-problema e instru¸c˜oes de como eles
devem retornar uma proposta para o sub-problema. O receptor do an´uncio decide se ´e
eleg´ıvel e ent˜ao formula uma proposta. O solicitante coleta as propostas e repassa a espe-
cifica¸c˜ao do sub- problema para o(s) agente(s) contratado(s) (aqueles que apresentaram as
melhores propostas). O contratado recebe os detalhes do sub-problema, resolve-o (talvez
quebrando-o em outros sub-problemas menores e contratando outros) e ao final retorna a
solu¸c˜ao para o solicitante.
Uma poss´ıvel situa¸c˜ao ´e a inexistˆencia de agentes adequados para uma determi-
nada tarefa no ambiente. Uma alternativa simples ´e reenviar o an´uncio periodicamente,
assumindo que os respondentes podem estar ocupados ou em breve estar˜ao dispon´ıveis
no ambiente. O intervalo entre os reenvios pode ser um parˆametro perigoso: Se o reenvio
acontece em intervalos muito longos, pode ser que alguns agentes fiquem parados por
muito tempo sem necessidade. Por outro lado se o intervalo entre os reenvios for muito
33
r´apido, a rede pode ficar congestionada devido ao excesso de troca de mensagens. Uma
estrat´egia para dominar essa situa¸c˜ao ´e inverter o uso do protocolo. Ao inv´es de anunciar
tarefas e coletar propostas, o que implica que podem existir muitos respondentes para
cada tarefa, o protocolo pode ser usado pelos respondentes para anunciar a disponibili-
dade, e os solicitantes podem responder para os anunciantes propondo suas tarefas. Ainda
´e poss´ıvel mesclar as duas maneiras de utiliza¸c˜ao do protocolo dependendo de onde estiver
o gargalo.
Uma alternativa ao reenvio, esp ecialmente quando n˜ao existem agentes respon-
dentes eleg´ıveis na rede ´e o solicitante ajustar os an´uncios a cada itera¸c˜ao, relaxando os
requisitos at´e come¸car a receber as propostas. Um aspecto a ressaltar deste processo de
relaxamento ´e que a especifica¸c˜ao da elegibilidade refletir´a nas preferˆencias sobre dife-
rentes classes de resp ondentes, ou mais especificamente, sobre a qualidade dos servi¸cos
que diferentes contratados disponibilizam. Outra dificuldade que um solicitante pode
ter ´e quando nenhum agente tem a capacidade de resolver o problema especificado. O
solicitante pode decompor o problema em outros menores, para que os agentes possam
resolvˆe-lo.
4.4.2 Planejamento Distribu´ıdo
Segundo Durfee [DUR99], o planejamento distribu´ıdo po de ser entendido com a
especializa¸c˜ao de uma resolu¸c˜ao distribu´ıda de problemas, sendo que o problema a ser
resolvido ´e desenvolver um plano. O planejamento ´e uma forma de coordena¸c˜ao entre
agentes, com o objetivo de coordenar as a¸c˜oes dos agentes para alcan¸car um objetivo
comum e evitar rela¸c˜oes negativas entre os agentes. As rela¸c˜oes negativas podem ser
entendidas como obstru¸c˜oes para o objetivo final do agente, como por exemplo, a escassez
de um determinado recurso ou a incompatibilidade de objetivos. Ferber [FER03] apresenta
uma classifica¸c˜ao da atividade de cria¸c˜ao e planejamento de tarefas entre agentes:
• Planejamento Centralizado para M´ultiplos Agentes
Neste contexto, apenas um agente ´e designado para criar os planos, que cont´em
as a¸c˜oes para os demais agentes. O agente planejador deve inicialmente mapear
um plano geral, identificar pontos onde ´e poss´ıvel paralelizar as atividades, sendo
poss´ıvel a cria¸c˜ao de sub-planos. Esses sub-planos podem ser alocados por outros
agentes que ser˜ao respons´aveis pelo gerenciamento do sub-plano. Os demais agentes
ser˜ao meros executores de atividades.
• Coordena¸c˜ao Centralizada para Planos Parciais
34
A figura do agente centralizador existe apenas para coordenar as a¸c˜oes dos planos
criados por outros agentes. Esse agente tem a tarefa de identificar regi˜oes de conflito
e dependˆencias entre os planos. As medidas podem ser a cria¸c˜ao de sem´aforos ou
ordena¸c˜ao de a¸c˜oes.
• Coordena¸c˜ao Distribu´ıda para Planos Parciais
Nesta situa¸c˜ao n˜ao existe uma figura que elabora e coordena os planos. Os agentes
s˜ao respons´aveis por identificar situa¸c˜oes de conflito de recursos ou dependˆencias
entre suas a¸c˜oes atrav´es de trocas de mensagens.
4.4.3 Eco-resolu¸c˜ao
A Eco-resolu¸c˜ao ´e uma abordagem distribu´ıda para a resolu¸c˜ao de conflitos e busca
em espa¸cos de estados para a solu¸c˜ao de um problema. Um eco-problema ´e composto
por uma popula¸c˜ao de agentes chamados eco-agentes, que tˆem por objetivo alcan¸car um
estado de estabiliza¸c˜ao, chamado de solu¸c˜ao do problema [FER03]. Esta t´ecnica parte
do pressuposto que um agente simples n˜ao faz planejamento e apenas reage no seu meio.
Transformando a met´afora da natureza para um problema real, o princ´ıpio ´e modelar
o problema em pequenas partes, modelar as fun¸c˜oes que s˜ao disparadas pelos est´ımulos
externos e deixar que as partes alcancem a estabiliza¸c˜ao.
Cada eco-agente tenta atingir seu objetivo individualmente. As percep¸c˜oes locais
s˜ao transformadas em a¸c˜oes que tendem a alterar o ambiente e permitir que outros agentes
tenham a chance de alterar seus estados.
Segundo Ferber, um eco-agente pode ter um dentre os quatro estados mentais:
satisfeito, em busca de satisfa¸c˜ao, em fuga ou em busca de fuga. A necessidade de sa-
tisfa¸c˜ao, far´a o eco-agente agir em seu ambiente. O ambiente recebe diversas intera¸c˜oes
dos agentes, como num jogo de sobrevivˆencia. Abaixo ´e apresentado um cen´ario comum
entre eco-agentes:
• o eco-agente pode perceber que outros eco-agentes s ˜ao obst´aculos para s ua meta
pessoal;
• o agente intruso tem a obriga¸c˜ao de es capar;
• o agente que sofreu o ataque tenta fugir, sendo que seu estado ´e alterado;
• o agente que est´a fugindo pode atacar um outro agente durante a fuga;
• esta corrente de ataque ´e quebrada assim que houver um eco-agente que possa atingir
o estado de satisfa¸c˜ao sem atacar um outro eco-agente.
35
O desejo de satisfa¸c˜ao do eco-agente pode ser descrito atrav´es de um simples algo-
ritmo. O Algoritmo 1 ´e chamado p eriodicamente por todos os agentes. Esta periodicidade
vai depender do problema que est´a sendo modelado. Isto permite definir dependˆencias e
sucess˜oes de satisfa¸c˜oes de todos os eco-agentes.
Algoritmo 1 Busca de Satisfa¸c˜ao de um Eco-agente [FER03]
Pr´e-requisito: x: um agente; y: obstrutores;
1: fun¸c˜ao TentarSatisfazer(x, y)
2: se objetivo( x ) satisfeito e x n˜ao est´a satisfeito ent˜ao
3: para todos os y obstrutores fa¸ca
4: TentarEscapar( y , x)
5: Satisfazer( x )
6: fim para
7: fim se
A fun¸c˜ao Satisfazer(agente) ´e dependente do dom´ınio do problema e deve checar
se o estado atual atende suas expectativas. J´a o Algoritmo 2 (T entarEscapar(x, y)),
representa o comportamento de fuga, o qual abrir´a espa¸co para que os outros agentes
percorram seus espa¸cos de busca.
Algoritmo 2 Tentativa de Fuga de um Eco-agente [FER03]
1: fun¸c˜ao TentarEscapar(x, y)
2: se x n˜ao estiver satisfeito ent˜ao
3: obstrutor torna-se insatisfeito
4: fim se
5: p = EncontrarLocalParaFuga(x, y)
6: se p n˜ao foi encontrado ent˜ao
7: solu¸c˜ao n˜ao encontrada
8: parar de buscar solu¸c˜ao
9: sair
10: else
11: para todas as possibilidades de fuga z do obstruidor x fa¸ca
12: TentarEscapar(z, x)
13: fim para
14: fim se
15: Escapar(x, p)
A fun¸c˜ao Escapar(x, p) tamb´em ´e dependente do problema que est´a sendo mode-
lado e representa a tentativa de mudar seu estado, permitindo que outros agentes atinjam
a satisfa¸c˜ao.
A eco-resolu¸c˜ao ´e um mecanismo eficiente de resolu¸c˜ao de conflitos e de busca em
espa¸cos de estados e atenua problemas NP-hard. No entanto modelar um eco-problema
(eco-agentes, estado inicial, objetivos e crit´erios de parada) n˜ao ´e uma atividade trivial
pois uma modelagem incorreta pode gerar situa¸c˜oes de impasse (deadlock).
36
4.5 Considera¸c˜oes Finais
Neste cap´ıtulo foram apresentados os principais mecanismos de decomposi¸c˜ao de
tarefas, colabora¸c˜ao e resolu¸c˜ao de problemas utilizados em sistemas IAD. Uma vez que
a heur´ıstica para a combina¸c˜ao de classificadores deve permitir a fragmenta¸c˜ao do pro-
blema em pequenas partes, a distribui¸c˜ao de tarefas requer um mecanismo formal de co-
munica¸c˜ao. Os conceitos abordados, como por exemplo, Contract-net, RDP e eco-agentes,
foram elementos fundamentais para a cria¸c˜ao do m´etodo.
37
Cap´ıtulo 5
SDICCS - Um Sistema Distribu´ıdo para Com-
bina¸c˜ao de Classificadores Simb´olicos
Neste cap´ıtulo, ´e descrito o sistema de combina¸c˜ao de classificadores simb´olicos, o
SDICCS, respons´avel por:
1. Construir um classificador simb´olico us ando diversos classificadores gerados a partir
de diferentes amostras de dados. O classificador deve extrair as “melhores” regras
das hip´oteses distribu´ıdas, desde que n˜ao existam regras conflitantes entre os agentes
cooperativos;
2. Usar um ensemble de classificadores nas situa¸c˜oes onde o classificador combinado
n˜ao tenha cobertura suficiente. Um ensemble ´e um conjunto de classificadores cujas
decis˜oes individuais s˜ao combinadas de alguma forma para classificar um exemplo
ainda n˜ao classificado [FS97]. Neste caso, atrav´es de voto simples;
3. Fornecer ao usu´ario um m´odulo de classifica¸c˜ao de exemplos n˜ao conhecidos, que
explicar´a qual ou quais regras foram disparadas.
O m´etodo compreende as fases de: (i) prepara¸c˜ao dos dados, a qual determina
como ocorre a divis˜ao dos exemplos de treinamento e teste, (ii) aprendizagem dos agentes
classificadores, (iii) combina¸c˜ao das hip´oteses distribu´ıdas e finalmente (iv) a classifica¸c˜ao
de novos exemplos. Em (iii), o foco ´e a obten¸c˜ao de um conhecimento unificado, sendo
que o resultado final ´e de um conjunto de regras ordenadas c apaz de descrever padr˜oes n˜ao
divergentes entre os agentes. Em (iv), al´em do objetivo de explicar porque um exemplo
n˜ao conhecido foi classificado, ´e necess´ario garantir a completeza do classificador: uma vez
que o modelo unificado deixa de cobrir certas regi˜oes do espa¸co de tuplas, um ensemble ´e
usado.
Antes de descrever as fases (i) a (iv), s˜ao apresentadas duas se¸c˜oes: A primeira
apresenta um conjunto de defini¸c˜oes que ´e us ado no restante do documento e a segunda
38
descreve uma base de exemplos, que ´e usada para fins de ilustra¸c˜ao da abordagem. Ap´os
descrever as fases citadas anteriormente, a se¸c˜ao de implementa¸c˜ao ´e apresentada, a qual
detalha a arquitetura do sistema e o mecanismo de coopera¸c˜ao entre os agentes, uma vez
que as se¸c˜oes anteriores mencionam as trocas de mensagens entre os agentes em alto n´ıvel.
Ao final, s˜ao apresentados trabalhos com caracter´ısticas comuns e considera¸c˜oes finais.
5.1 Defini¸c˜oes
As defini¸c˜oes a seguir s˜ao utilizadas no decorrer do texto para facilitar a compre-
ens˜ao da abordagem.
Uma base de exemplos S ´e dividida em duas partes, resultando nas bases de
exemplo T e V , treinamento e teste respectivamente. A base T ´e dividida em n partes,
resultando nas bases distribu´ıdas t
1
, t
2
, ..., t
n
, onde n ´e a quantidade de fragmentos que
ser´a usada. Cada t
ji
´e um conjunto de j instˆancias {(x
1
, y
1
), (x
2
, y
2
), ..., (x
j
, y
j
)}, para
alguma fun¸c˜ao desconhecida y = f (x). Cada instˆancia x
j
´e tipicamente um vetor na forma
(xj
1
, xj
2
, ...xj
w
), sendo que seus componentes s˜ao chamados de atributos ou caracter´ısticas
e w ´e a quantidade de atributos. Para classifica¸c˜ao, os valores de y s˜ao representados por
um conjunto discreto contendo N cl classes; y ∈ {C
1
, C
2
, ..., C
Ncl
}.
Um conjunto de agentes A = {a
1
, a
2
, ..., a
n
} ´e associado a T , formando uma rela¸c˜ao
A ⊗ T = {(a
1
, t
1
), (a
2
, t
2
), ..., (a
n
, t
n
)}, onde n ´e a quantidade de fragmentos da base de
exemplos T . Dados os conjuntos de exemplos t, cada agente executa um algoritmo de
aprendizagem, que induz um classificador chamado hip, sendo uma hip´otese da fun¸c˜ao
objetivo e desconhecida f (x). Dados novos valores x, o classificador hip prediz o valor
correspondente de y. Ao final temos um conjunto Hip de hip´oteses {hip
1
, hip
2
, ..., hip
n
},
cada uma pertencente ao respectivo agente (a
1
, a
2
, ..., a
n
).
Neste trabalho cada hip´otese hip ´e um conjunto de regras ordenadas, ex. hip
i
=
{R
1
, R
2
, ..., R
j
}, onde ji ´e a quantidade de regras do classificador. Uma regra R pode ser
considerada um conjunto de testes no formato < x
i
op valor >, onde x
i
´e um atributo ou
caracter´ıstica, op ´e um operador pertencente ao conjunto {=, =, ≥, ≤, >, <} e valor ´e um
dado cont´ınuo ou discreto. Portanto, uma regra R assume simbolicamente o formato B
→ H, onde B ´e a conjun¸c˜ao de testes atributo-valor (body) e H (head) ´e a classe associada
C
i
, sendo que C
i
∈ {C
1
, C
2
, ..., C
Ncl
}.
Os processos de combina¸c˜ao e classifica¸c˜ao s˜ao realizados por dois tipos de agentes,
sendo que cada um tem um papel bem definido.
• Agente de aprendizagem ou a
i
:
´
E respons´avel por realizar a etapa de aprendizagem,
39
enviar o conjunto de regras, avaliar conjuntos de regras e classificar novos exemplos
quando solicitado.
• Agente coordenador ou a
coord
:
´
E respons´avel por solicitar os conjuntos de regras
de c ada agente de aprendizagem, solicitar a avalia¸c˜ao das regras para cada agente,
montar a fila de avalia¸c˜ao de regras e usar um algoritmo de busca em espa¸cos de
estado para encontrar a melhor regra. Ao final deve enviar a hip´otese combinada
Hip
para os agentes de aprendizagem.
O agente a
coord
cria uma ´arvore de combina¸c˜ao de regras durante a etapa de com-
bina¸c˜ao que ´e detalhado adiante. Esta ´arvore ´e composta por v´ertices e arestas. Por
conven¸c˜ao, um v´ertice ´e chamado V
l
, sendo que l ´e o n´ıvel o qual o v´ertice pertence e V
0
´e o v´ertice raiz.
5.2 Descri¸c˜ao do Conjunto de Exemplos Ilustrativo
Para ilustrar o funcionamento do combinador de classificadores e o mecanismo de
classifica¸c˜ao nas pr´oximas se¸c˜oes, ´e utilizada uma base de exemplos hipot´etica contendo
dois atributos (x
1
e x
2
) e uma classes alvo composta de dois poss´ıveis valores (a e b).
Isso permite que o conjunto de exemplos e as regras sejam representados em um plano
cartesiano. A fun¸c˜ao objetivo f ´e definida na f´ormula 5.1.
f(x
1
, x
2
) =
a, se 10 ≤ x ≤ 50, 30 < y ≤ 50
a, se 50 < x ≤ 90, 10 ≤ y ≤ 30
b, se 10 ≤ x ≤ 50, 10 ≤ y ≤ 30
b, se 50 < x ≤ 90, 30 < y ≤ 50
(5.1)
A Figura 5.1 apresenta a fun¸c˜ao objetivo f no plano cartesiano.
Dada a fun¸c˜ao objetivo f, v´arios exemplos ilustrativos podem ser gerados nas
pr´oximas se¸c˜oes. O objetivo ´e criar um ambiente que reproduza a incerteza e vis˜ao
parcial t´ıpica de classificadores distribu´ıdos.
5.3 Prepara¸c˜ao dos Dados
Com o objetivo de simular um ambiente distribu´ıdo, uma base de exemplos S ´e
utilizada para a montagem das bases distribu´ıdas de treinamento. Essa base de exemplos
´e dividida da seguinte forma: 20% dos exemplos ´e reservado para a avalia¸c˜ao final (V )
do classificador SDICCS. Os 80% restantes (T ) s˜ao divididos em n partes, onde n ´e a
40
Figura 5.1: Fun¸c˜ao Objetivo f
quantidade de agentes de aprendizagem dispon´ıveis no ambiente. A Figura 5.2 ilustra o
processo de prepara¸c˜ao da base de exemplos. Por tratar-se de um ambiente de simula¸c˜ao, a
quantidade de exemplos de testes ´e relativamente menor do que a quantidade de exemplos
de treinamento, o que ´e o inverso de um ambiente real.
Figura 5.2: Prepara¸c˜ao dos Dados
A divis˜ao da base de exemplos naturalmente reduz a capacidade de predi¸c˜ao do
classificador, uma vez que a quantidade de exemplos de treinamento ´e menor e muitas
vezes insuficiente para criar um conjunto de hip´oteses que cubra todos os casos. Para
simular uma situa¸c˜ao na qual os agentes tˆem vis˜oes incompletas sobre um determinado
problema, s˜ao gerados como exemplo 3 conjuntos de dados utilizados por 3 agentes. Os
conjuntos t
i
obedecem `as fun¸c˜oes fAg
i
(x
1
, x
2
), onde Ag
i
´e um agente e as fun¸c˜oes podem
41
ser interpretadas como vis˜oes parciais da fun¸c˜ao objetivo f(x
1
, x
2
) (f´ormulas 5.2, 5.3 e
5.4).
fAg
1
(x
1
, x
2
) =
a, se 10 ≤ x ≤ 50, 30 ≤ y ≤ 50
a, se 50 < x ≤ 90, 10 < y ≤ 20
b, se 10 ≤ x ≤ 50, 10 < y ≤ 20
b, se 50 < x ≤ 90, 30 ≤ y ≤ 50
(5.2)
fAg
2
(x
1
, x
2
) =
a, se 10 ≤ x ≤ 50, 40 ≤ y ≤ 50
a, se 50 < x ≤ 90, 10 ≤ y ≤ 30
b, se 10 ≤ x ≤ 50, 10 < y ≤ 30
b, se 50 < x ≤ 90, 40 ≤ y ≤ 50
(5.3)
fAg
3
(x
1
, x
2
) =
a, se 10 ≤ x ≤ 40, 30 ≤ y ≤ 50
a, se 50 < x ≤ 90, 10 < y ≤ 30
b, se 10 ≤ x ≤ 50, 10 < y ≤ 30
b, se 60 < x ≤ 90, 30 ≤ y ≤ 50
(5.4)
Estes conjuntos foram denominados t
1
, t
2
e t
3
. O ´ultimo conjunto (V ) ´e usado
para teste e apresenta distribui¸c˜ao de acordo com a fun¸c˜ao objetivo apresentada na se¸c˜ao
anterior. Cada conjunto tem um total de 100 exemplos gerados aleatoriamente.
A Figura 5.3 apresenta como os agentes interpretam a fun¸c˜ao objetivo f (x
1
, x
2
).
Os trˆes agentes n˜ao conseguem representar completamente o problema, sendo necess´ario
combin´a-los ou us´a-los em conjunto para a realiza¸c˜ao da predi¸c˜ao. Al´em dos classificadores
terem vis˜oes parciais ´e prov´avel a ocorrˆencia de divergˆencias em uma suposta uni˜ao de
regras sem crit´erios, uma vez que:
• regras ordenadas n˜ao podem ser usadas isoladamente. Elas possuem um else impl´ıcito
como elemento de liga¸c˜ao. Sendo assim, uma regra pode se r complemento de outra,
causando uma dependˆencia estat´ıstica. Us´a-las isoladamente aumentar´a a taxa de
erros;
• a otimiza¸c˜ao de certos algoritmos generaliza o conhecimento atrav´es de regras de-
fault, baseado no conjunto de treinamento dispon´ıvel. De acordo Bacardit e Gold-
berg [BGB07], regras default s˜ao criadas na maioria das vezes baseadas na distri-
bui¸c˜ao das classes (maioria ou minoria). Em certas bases de dados esta alternativa
produz altas taxas de erros.
Uma vez que a base foi particionada, o pr´oximo passo ´e a realiza¸c˜ao da aprendi-
zagem pelos agentes.
42
Figura 5.3: Fun¸c˜ao Verdadeira fAg
i
(x1, x2) para os 3 Agentes de Aprendizagem
5.4 Etapa de Aprendizagem Local
Segundo Prati e Flach [PF05], a maioria dos classificadores pertencem a uma
de duas fam´ılias chamadas remover-para-conquistar e dividir-para-conquistar. As duas
fam´ılias c ompartilham diversas caracter´ısticas, sendo que a mais representativa ´e que o
espa¸co de exemplos cont´em grandes regi˜oes que pertencem `a mesma classe.
Nos algoritmos que pertencem `a fam´ılia remover-para-conquistar [FUR99], o pro-
cesso de busca ´e geralmente implementado atrav´es de um algoritmo “guloso”, sendo que
em cada itera¸c˜ao ele busca a melhor regra (de acordo com algum crit´erio) e remove os
exemplos cobertos (a parte remover). Este processo se repete usando os exemplos que
sobraram at´e que todos os exemplos tenham sido cobertos ou algum crit´erio de parada
tenha sido disparado (a parte conquistar). Alguns desses algoritmos induzem regras que
obedecem uma s eq¨uˆencia, formando um conjunto ordenado ou uma lista de decis˜ao, como
´e muitas vezes chamado. Este conjunto de regras deve ser usado na seq¨uˆencia especi-
ficada. A classifica¸c˜ao de novos exemplos ´e dada a partir da primeira regra disparada.
Caso nenhuma regra atenda a especifica¸c˜ao do corpo da regra, ent˜ao a regra default ´e
43
disparada. A regra default ´e um tipo espe cial de regra que n˜ao possui condi¸c˜oes, apenas a
classe alvo e muitos algoritmos a definem baseados na distribui¸c˜ao das classes no c onjunto
de treinamento.
J´a no caso de algoritmos que pertencem a fam´ılia dividir-para-conquistar [QUI93],
o classificador ´e obtido usando uma estrat´e gia top-down, com refinamentos consecutivos.
O resultado ´e geralmente uma ´arvore de decis˜ao, que divide o espa¸co de exemplos em
hiper-retˆangulos, sem sobreposi¸c˜ao. A representa¸c˜ao da ´arvore em forma de regras nada
mais ´e do que percorrer os n´os da ´arvore at´e as folhas. Sendo assim, as regras geradas
s˜ao mutuamente exclusivas, tamb´em chamadas de regras n˜ao ordenadas.
Para a realiza¸c˜ao dos experimentos, o algoritmo RIPPER [COH95] apresentado
por Cohen, foi selecionado por tratar-se de um algoritmo que pertence a fam´ılia remover-
para-conquistar ou set-covering algorithm, foco deste trabalho. Al´em disso, este algoritmo
tem desempenho compar´avel aos algoritmos de ´arvore de decis˜ao C4.5 e C4.5rules [QUI93],
tendo melhor desempenho do que C4.5rules em bases ruidosas [COH95].
5.4.1 Execu¸c˜ao
Cada agente a
i
induz um classificador usando o algoritmo RIPPER [COH95], for-
mando uma hip´otese h
i
= {R
1
, R
2
, ..., R
j
}, composta de ji regras ordenadas. A Figura
5.4 ilustra este processo de aprendizagem local.
Figura 5.4: Processo de Aprendizagem Local
44
Geralmente os algoritmos de indu¸c˜ao de regras criam uma regra default, com o
objetivo de classificar exemplos que n˜ao foram cob ertos devido ao processo de otimiza¸c˜ao
de regras. Esse tipo de regra que apresenta apenas a c lasse H e nenhum antecedente
funciona como um else impl´ıcito dentro do conjunto de regras. Devido a dificuldade de
mensura¸c˜ao da qualidade e capacidade de explica¸c˜ao nula, esse tipo de regra ´e eliminado do
conjunto h
i
. Para suprir a elimina¸c˜ao da regra default, al´em do mecanismo de combina¸c˜ao
de hip´oteses, ´e utilizado o m´odulo de ensemble que ser´a detalhado posteriormente.
Regras n˜ao ordenadas podem ser avaliadas isoladamente. Existem v´arias propostas
de mecanismos de avalia¸c˜ao destas regras, sendo poss´ıvel estabele cer thresholds e selecionar
aquelas com a caracter´ıstica desejada, como por exemplo: grau de suporte, precis˜ao e
novidade. V´arios trabalhos usam t´ec nicas de sele¸c˜ao e ordena¸c˜ao de regras usando medidas
para sele¸c˜ao e combina¸c˜ao de regras [SHA00] [GL00] [BER02] [HCBK99] [CL04] [PASE06]
[SEN06]. A abordagem proposta foi desenvolvida para manipular regras ordenadas, as
quais tornam a opera¸c˜ao de combina¸c˜ao mais complexa. Existem poucas propostas para
combina¸c˜ao de regras ordenadas na literatura. O fato de cada parti¸c˜ao ter um bias e o
mecanismo de gera¸c˜ao de regras ser muitas vezes inst´avel pode agravar a combina¸c˜ao.
Al´em disso esse tipo de regra n˜ao pode ser avaliada isoladamente, pois uma regra pode
ser o complemento de outra. Portanto, encontrar a melhor combina¸c˜ao ´e um processo
exaustivo e demanda poder de processamento dos agentes. Segundo Furnkranz e Flach
[
FF03], enquanto medimos a precis˜ao ao classific ar exemplos desconhecidos para regras
individuais, a avalia¸c˜ao de uma regra incompleta ou ordenada deve capturar o potencial
para ser refinada.
A Figura 5.5 apresenta as regras geradas pelos trˆes classificadores usando a base
de ilustra¸c˜ao com o algoritmo RIPPER. A ´area pontilhada representa a fun¸c˜ao obje tivo
f(x
1
, x
2
). Nesta figura ´e percept´ıvel a existˆencia de ´areas de divergˆencias entre os classi-
ficadores, mesmo que o conjunto de exemplos n˜ao apresente nenhum ru´ıdo. Por exemplo:
Os agentes 1 e 2 n˜ao conseguem descrever qual ´e o padr˜ao correto para a classe A. O
contr´ario acontece para o agente 3 que n˜ao consegue descrever a classe B, apesar de ser o
classificador que melhor representa a fun¸c˜ao objetivo. Parte do conhecimento ´e perdido
devido a utiliza¸c˜ao da regra default.
Uma vez que os agentes finalizaram o processo de aprendizagem ´e poss´ıvel ir para
a pr´oxima etapa, respons´avel pela combina¸c˜ao dos classificadores.
45
Figura 5.5: Regras Geradas pelos Agentes a
1
, a
2
e a
3
5.5 Combina¸c˜ao dos Classificadores
Dado um conjunto de hip´oteses Hip = {hip
1
, hip
2
, ..., hip
n
} e um conjunto de
treinamento com N exemplos, T = {(x
i
, y
i
), i = 1, ..., N}, pertencentes a um agente do
conjunto A = {a
1
, a
2
, ..., a
n
}, o processo de combina¸c˜ao de classificadores cria uma nova
hip´otese Hip
, contendo l regras R ∈ Hip, atrav´es da coopera¸c˜ao entre os agentes, onde
l ´e a quantidade de regras selecionadas pelo processo.
A etapa de combina¸c˜ao de classificadores pode ser dividida em:
• compartilhamento das hip´oteses distribu´ıdas (Hip);
• cria¸c˜ao da hip´otese combinada (Hip
);
• compartilhamento da hip´otese combinada (Hip
).
5.5.1 Compartilhamento das Hip´oteses Distribu´ıdas (Hip)
A etapa de compartilhamento das hip´oteses distribu´ıdas ocorre a partir do mo-
mento em que o agente coordenador solicita aos agentes de aprendizagem para que en-
viem suas hip´oteses ao grupo. O objetivo do compartilhamento ´e permitir que o agente
46
coordenador monte seu plano de execu¸c˜oes e os agentes de aprendizagem usem o conhe-
cimento comum formando um ensemble nas situa¸c˜oes onde o classificador unificado n˜ao
cobre algum exemplo. O Algoritmo 3 apresenta a etapa de compartilhamento.
Algoritmo 3 Compartilhamento das Hip´oteses Distribu´ıdas entre os Agentes
Pr´e-requisito: A = {a
1
, ..., a
n
}: conjunto de agentes; H = {h
1
, ..., h
n
}:conjunto de
hip´oteses
1: fun¸c˜ao compartilharHipoteses(A,H)
2:
3: // Comportamento para envio da hip´otese para cada agente
4: para cada agente de aprendizagem a
i
∈ A fa¸ca
5: enviar h
i
para A
vizinhos
= {a ∈ A|a = a
i
}
6: fim para
7:
8: // Comportamento para recebimento e avalia¸c˜ao das hip´oteses
9: para cada agente de aprendizagem a
i
∈ A fa¸ca
10: receber h
i
dos agentes vizinhos
11: avaliar cada regra em h
i
usando t
i
e atualizar T P e F P
12: criar uma lista de conflito (Conf litos) para cada regra em h
i
13:
14: // Envia a lista de conflitos e cobertura e suporte de cada regra
15: enviar Conf litos,h
i
atualizado
para agente coordenador (a
coord
)
16: fim para
17:
18: // Coordenador: Receber as regras e criar a fila de combina¸c˜ao
19: coordenador ← {agente ∈ A|agente = coordenador}
20: Criar uma fila (Q) de regras ordenada por
T P
T P +F P
21: Armazenar a fila Q para combina¸c˜ao posterior
• Uma vez que os agentes de aprendizagem (a
i
) entram no ambiente, o agente co-
ordenador (a
coord
) envia uma mensagem para que o processo de compartilhamento
inicie;
• Cada agente a
i
envia seu conjunto de regras para os demais agentes;
• Uma vez recebidas as regras, os agentes de aprendizagem realizam a avalia¸c˜ao das
regras individualmente em suas bases de treinamento. O agente identifica qual ´e
a quantidade de exemplos cobertos correta (T P ) e incorretamente (F P ) para cada
regra tomada isoladamente. Esse processo se repete para todas as regras de todos os
agentes. Estes valores s˜ao usados posteriormente pelo agente a
coord
para determinar
a precis˜ao de cada regra e conseq¨uentemente a ordem da fila de avalia¸c˜ao Q.
• Cada agente de aprendizagem (a
i
) devolve as regras avaliadas juntamente com os
valores respectivos de T P e F P para o agente a
coord
;
47
• O agente de aprendizagem (a
i
) tamb´em envia para o agente coordenador (a
coord
)
uma lista de regras conflitantes para cada regra. Entende-se por conflito entre duas
regras a cobertura simultˆanea de e xemplos, sendo que as regras prevˆeem classes
diferentes. O agente a
i
chega a esta conclus˜ao validando as coberturas das regras
em sua base de treinamento t
i
;
• O agente coordenador recebe a rela¸c˜ao de regras avaliadas, soma todos os valores de
T P e F P p or regra e cria uma fila Q, que ´e usada posteriormente para o processo de
combina¸c˜ao de regras. A fila ´e ordenada da maior para a menor medida de precis˜ao,
que ´e dada pe la f´ormula
T P
T P +F P
. Esta medida permite avaliar o n´ıvel individual
da precis˜ao da regra, o que favorece a avalia¸c˜ao antecipada de regras mais precisas,
dada a ordem da fila.
5.5.2 Cria¸c˜ao da Hip´otese Hip
Nesta etapa, uma fila c ontendo a lista de regras Q = {r
1
, ..., r
n
}, ordenada pela
medida de precis˜ao individual (
T P
T P +F P
), ´e usada como entrada para a cria¸c˜ao de uma
´arvore, chamado ´arvore de combina¸c˜ao, que ´e composta por:
• V´ertices: Pode ser um v´ertice raiz, intermedi´ario ou folha. Por conven¸c˜ao ´e cha-
mado de V
l
, sendo que l representa o n´ıvel da ´arvore. O v´ertice raiz possui um
conjunto de regras vazio (∅), denominado V
0
. Um v´ertice intermedi´ario ou folha
´e composto por um conjunto de regras, resultante da etapa de busca e assume a
nota¸c˜ao V
l
.
• Arestas: As arestas unem dois v´ertices e armazenam o ganho obtido na passagem
de um v´ertice para outro. O ganho ´e a subtra¸c˜ao da medida de suporte do v´ertice
filho pela medida de suporte do v´ertice pai, como apresentado na f´ormula 5.5.
ganho
V
l
= suporte(V
l
) − suporte(V
l−1
) (5.5)
A medida de suporte ´e obtida pela f´ormula 5.6.
suporte(V ) =
T P
N
(5.6)
onde T P ´e a quantidade de exemplos cob ertos corretamente e N ´e a quantidade
total de exemplos, considerando as amostras de todas as bases distribu´ıdas.
48
Para expandir a ´arvore de combina¸c˜ao, foi criado um algoritmo inspirado na solu¸c˜ao
de Dijkstra [DIJ59], que resolve o problema do menor caminho em grafos, dado um v´ertice
inicial e final. Foi necess´aria uma adapta¸c˜ao no algoritmo original, uma vez que o v´ertice
final n˜ao ´e conhecido. O crit´erio de parada neste caso ´e a inexistˆencia de regras a avaliar
na fila Q.
Com este algoritmo ´e poss´ıvel avaliar cada combina¸c˜ao de regras e o ganho obtido
ao adicionar, remover ou trocar uma regra de posi¸c˜ao. Al´em disso ´e caracter´ıstica do
algoritmo permitir backtracking, uma vez que ´e poss´ıvel retomar a expans˜ao de arestas
anteriormente descartadas devido ao baixo ganho em um certo momento, por´em conveni-
entes em outro.
Algoritmo 4 Algoritmo de Combina¸c˜ao de Hip´oteses
Pr´e-requisito: Q = r
1
, r
2
, ..., r
n
: fila de regras
1: fun¸c˜ao combinarHipoteses(Q)
2: O ← ∅ {inicializar a lista aberta}
3: D ← ∅ {inicializar a lista fechada}
4: raiz ← vertice(∅) {iniciar com um v´ertice vazio}
5: raiz.ganho ← 0
6: adicionarVertice(O,raiz)
7: // continuar enquanto houverem v´ertices
8: // e n˜ao tenha atingido o n´ıvel m´aximo da ´arvore
9: enquanto O = ∅ e nivelArvore(maximaP recisao(O)) = Q.tamanho fa¸ca
10: verticeV isitado ← maximaP recisao(O)
11: remove verticeVisitado de O
12: D.adicionar(verticeV isitado)
13: expandir(verticeV isitado)
14: para cada aresta e pertencente ao verticeVisitado fa¸ca
15: // realizar o relaxamento das arestas
16: se e.f ilho.ganho < verticeV isitado.gan ho + e.ganho ent˜ao
17: e.filho.ganho ← verticeV isitado.ganho + e.ganho
18: e.pai = verticeV isitado
19: adicionarVertice(O,e.filho)
20: fim se
21: fim para
22: fim enquanto
23: maiorGanho ← maximaP recisao(O)
24: retornar maiorGanho.classificador
O Algoritmo 4 mostra como a hip´otese ´e constru´ıda. A partir do recebimento dos
parˆametros de entrada o algoritmo segue os seguintes passos:
1. A ´arvore inicia com um v´ertice V
0
, que cont´em um conjunto de hip´oteses vazio
(Hip
= ∅);
2. As listas aberta e fechada s˜ao inicializadas;
49
Algoritmo 5 Algoritmo de Expans˜ao de Arestas
Pr´e-requisito: V : v´ertice contendo a hip´otese Q = r
1
, r
2
, ..., r
n
: fila de regras
1: fun¸c˜ao expandir(V,Q)
2: se V.nivel = tamanho(Q) ent˜ao
3: retornar
4: fim se
5:
6: criar um v´ertice com a nova regra (final do classificador)
7: se precisao(V.classificador) < 0.50 ent˜ao
8: descartar v´ertice
9: fim se
10: criar um v´ertice descartando a nova regra
11: se precisao(V.classificador) < 0.50 ent˜ao
12: descartar v´ertice
13: fim se
14: para cada regra em conflito com a nova regra fa¸ca
15: criar um v´ertice V com a nova regra antes da regra em conflito
16: se precisao(V.classif icador) < 0.50 ent˜ao
17: descartar v´ertice
18: fim se
19: criar um v´ertice V com a nova regra sobrepondo a regra e m conflito
20: se precisao(V.classif icador) < 0.50 ent˜ao
21: descartar v´ertice
22: fim se
23: fim para
24: retornar
3. O la¸co principal executa enquanto houverem v´ertices na lista aberta e existam ele-
mentos a processar na fila Q;
4.
´
E recuperada a regra com maior medida de precis˜ao da fila Q;
5.
´
E removida a regra em avalia¸c˜ao da lista aberta;
6. As arestas s˜ao expandidas para a regra em avalia¸c˜ao (Ver algoritmo 5);
7. Uma aresta ´e criada apontando para um v´ertice (V
1
) que cont´em a primeira regra da
fila Q. Relembrando, a fila Q est´a ordenada pela medida de precis˜ao, da maior para
a menor. A primeira regra desta fila ´e a que tem menor independˆencia estat´ıstica;
8. Cada agente a
i
realiza a avalia¸c˜ao da hip´otese contida no v´ertice, usando sua base de
treinamento e devolve os valores T P e F P do conjunto para o agente coordenador;
9. O agente coordenador, ap´os receber as avalia¸c˜oes dos n agentes, soma os valores T P
e F P obtidos dos agentes a
i
e calcula o suporte do conjunto (ver f´ormula 5.6);
50
10. A diferen¸ca entre o suporte do v´ertice anterior e do v´ertice atual ´e usada para
atribuir o peso da aresta. No caso do primeiro v´ertice, ´e computado apenas o valor
do suporte (ver f´ormula 5.5);
Figura 5.6: Processo de Combina¸c˜ao dos Classificadores
11. Na expans˜ao de v´ertices candidatos, o agente coordenador (a
coord
) lˆe a pr´oxima regra
da fila Q e cria duas possibilidades: Uma onde consta o conjunto de regras anterior
acrescido da regra obtida da fila e outra onde consta apenas o conjunto anterior,
desprezando a regra da fila. Isto permite descartar regras com baixa precis˜ao ou
muito espec´ıficas para a parti¸c˜ao onde foi criada. A Figura 5.6 ilustra uma expans˜ao
de v´ertices. A partir do v´ertice V
1
que cont´em a regra R
1
, o algoritmo expande os
v´ertices V
2.1
e V
2.2
, sendo que o v´ertice V
2.1
cont´em apenas a regra R1 e o ganho
para passar de um v´ertice para outro ´e nulo;
12. No caso do v´ertice V
2.2
h´a um ganho de 0.22. Relembrando: O ganho de cada
aresta ´e obtido a partir da subtra¸c˜ao do ganho do v´ertice anterior pelo ganho do
v´ertice corrente (ver f´ormula 5.5). Por exemplo: Se o conjunto apresentasse mau
51
desempenho ao adicionar a regra R2, seu ganho seria negativo, o que comprometeria
as pr´oximas expans˜oes, uma vez que o algoritmo s´o expande v´ertices com melhor
desempenho;
13. Durante a expans˜ao, caso a cobertura da regra seja menor do que a cobertura
original, significa que parte dos exemplos que ela cobriria est´a sendo coberta por
outra. Se faz necess´ario investigar se ela ter´a melhor desempenho que a conflitante
ou se funcionar´a melhor se a outra regra for complemento desta.
Figura 5.7: Combina¸c˜ao de Regras Conflitantes
Portanto, para cada regra conflitante, o algoritmo criar´a dois novos v´ertices: um
contendo a regra conflitante ap´os a regra da fila e outro substituindo a regra confli-
tante pela regra da fila.
´
E o caso da regra R3 da Figura 5.6:
´
E poss´ıvel visualizar
uma prov´avel intersec¸c˜ao ou conflito entre a regra R3 e R2. Na pr´oxima com-
52
bina¸c˜ao, possivelmente R3 n˜ao cobrir´a todos os exemplos “potenciais” uma vez que
os exemplos da base de treinamento cobertos pela regra R2 n˜ao est˜ao mais vis´ıveis
(estrat´egia de classifica¸c˜ao best first). Por esta raz˜ao ´e necess´ario: (i) combinar as
regras R3 e R2: pode ser que as duas tenham melhor desempenho combinadas ou
(ii) substituir a regra R3 pela regra R2: pode ser que na combina¸c˜ao deste v´ertice a
regra R2 tenha melhor desempenho que a R3. A Figura 5.7 apresenta uma situa¸c˜ao
de conflito entre regras e a resolu¸c˜ao correspondente na ´arvore. Esse processo se
repete para todas as regras conflitantes;
14. Para evitar expans˜oes de v´ertices desnecess´arias, foi estabe lecido um threshold emp´ırico:
regras com medida de precis˜ao inferiores a 50% s˜ao descartadas da ´arvore;
15. As expans˜oes ocorrem sucessivamente at´e que o n´ıvel da ´arvore atinja a quantidade
de regras da fila, considerando que houve chance para que as combina¸c˜oes tenham
sido realizadas;
16.
´
E escolhido o v´ertice que apresentar o melhor custo. Este v´ertice cont´em o conjunto
de hip´oteses que tem o maior ganho durante a fase de busca.
Figura 5.8: Hip´otese Combinada (Hip
)
A Figura 5.8 apresenta a hip´otese combinada para o conjunto de exemplos de ilus-
tra¸c˜ao (x
1
, x
2
).
´
E poss´ıvel perceber que regras conflitantes foram removidas e a ´area co-
53
berta “com explica¸c˜ao” aumentou. Isto significa que houve aumento no poder de predi¸c˜ao
e explica¸c˜ao do classificador e inconsistˆencias foram removidas.
5.5.3 Compartilhamento da Hip´otese Hip
A partir da finaliza¸c˜ao do processo de busca apresentado na se¸c˜ao anterior, o
agente coordenador (a
coord
) envia a hip´otese Hip
para os agentes pertencentes ao conjunto
A = {a
1
, a
2
, ..., a
n
}. A hip´otese Hip
´e obtida a partir do v´ertice que tem o classificador
com a “melhor” combina¸c˜ao.
Assim que os agentes recebem o conjunto de regras, os mesmos est˜ao aptos a criar
o mecanismo de inferˆencia.
´
E poss´ıvel que a hip´otese Hip
n˜ao cubra todos os exemplos,
devido a ausˆencia da regra default e a elimina¸c˜ao natural de regras incompat´ıveis . Por esta
raz˜ao, os agentes criam um classificador h´ıbrido composto pela hip´otese Hip
, priorit´aria
e um mecanismo de voto simples, composto pelos classificadores de todos os agentes. A
pr´oxima se¸c˜ao detalha a classifica¸c˜ao de novos exemplos pelos agentes.
5.6 Classifica¸c˜ao de Novos Exemplos
Os agentes envolvidos no processo de combina¸c˜ao s˜ao dotados de capacidades dis-
tintas: coordena¸c˜ao, para o agente que produz a ´arvore de combina¸c˜ao (a
coord
) e apren-
dizagem para os n agentes que criam os classificadores locais (a
i
). J´a a capacidade de
classifica¸c˜ao e explica¸c˜ao de novos exemplos est´a presente em qualquer agente, uma vez
que eles compartilham suas hip´oteses em dois momentos:
• Antes de iniciar a combina¸c˜ao: Os agentes de aprendizagem enviam suas hip´oteses
para os demais, com o objetivo de utiliz´a-las na classifica¸c˜ao por voto, quando a
hip´otese combinada n˜ao cobrir um novo exemplo;
• Ao final do proc esso de combina¸c˜ao, quando o agente coordenador envia a hip´otese
combinada Hip
.
Dado um exemplo x, submetido para consulta a qualquer agente a
i
pertencente
ao conjunto A, o agente realiza a inferˆencia e devolve a predi¸c˜ao da classe e a regra
disparada ou o conjunto de regras do ensemble que foi disparado. O algoritmo 6 mostra
como a inferˆencia ´e realizada. Cada agente armazena a hip´otese combinada Hip
=
{R
1
, R
2
, ..., R
N
} e o conjunto de hip´oteses H = {h
1
, h
2
, h
N
}, sendo que cada um cont´em
um conjunto de regras ordenadas assim como descrito para Hip
.
54
Algoritmo 6 Classifica¸c˜ao de Exemplos
Pr´e-requisito: Hip
= {R
1
, R
2
, ..., R
n
}:hip´otese combinada, H = {h
1
, h
2
, ..., h
n
}:hip´oteses
dos agentes, X: exemplo a ser classificado
1: fun¸c˜ao classificar(Hip’,H,x)
2:
3: // Modo consensual usando Hip
4: regraEscolhida ← falso
5: i ← 1
6: enquanto nega¸c˜ao(regraEscolhida) e i ≤ n fa¸ca
7: R = Hip
[i]
8: se cobertura(corpo(R), x) ent˜ao
9: regraEscol hida ← verdadeiro
10: else
11: i ← i + 1
12: fim se
13: se regraEscolhida ent˜ao
14: classe ← cabeca(R)
15: retornar [R,classe]
16: fim se
17: fim enquanto
18:
19: // Modo vota¸c˜ao
20: regrasEscolhidas ← ∅
21: para cada h ∈ H fa¸ca
22: para cada r ∈ h fa¸ca
23: se cobertura(corpo(r), x) ent˜ao
24: regrasEscolhidas.adicionar(r)
25: fim se
26: fim para
27: fim para
28: se regrasEsc olhidas = ∅ ent˜ao
29: cl ass e ← cabeca(maioria(regrasEscolhidas))
30: retornar [regrasEscolhidas,classe]
31: fim se
Inicialmente o algoritmo usa a hip´otese Hip
e a estrat´egia best-first para predizer
a classe de X. Esta hip´otese ´e priorit´aria, uma vez que pode ser entendida como um
“consenso” entre os agentes de aprendizagem. Este consenso ´e obtido a partir das diversas
avalia¸c˜oes que s˜ao realizadas `a medida que a ´arvore de busca do melhor conjunto cresce.
Sendo assim, do ponto de vista de explica¸c˜ao da predi¸c˜ao ´e desej´avel que o novo exemplo
seja coberto por e sta hip´otese. No entanto n˜ao h´a como garantir uma cob ertura total, pois
algumas regras conflitantes podem ter sido eliminadas durante a combina¸c˜ao. Al´em disso
muitos classificadores usam uma regra default para exemplos n˜ao cobertos sendo usada
normalmente a classe com a maior distribui¸c˜ao no conjunto de treinamento. Por n˜ao ter
55
validade do ponto de vista de explica¸c˜ao esta regra ´e eliminada assim que o processo de
combina¸c˜ao inicia.
Para garantir a completeza do classificador nas situa¸c˜oes onde n˜ao h´a cobertura,
foi adotado uma t´ecnica simples de constru¸c˜ao de ensembles chamada voto [BMP06].
O processo de voto consiste em realizar N classifica¸c˜oes, sendo que N ´e a quantidade de
classificadores.
´
E selecionada a classe que recebe o maior n´umero de votos. Mesmo usando
o mecanismo de voto, cada classificador utiliza a estrat´egia best-first para classificar o
exemplo. O voto acontece a partir do momento em que todos os classificadores realizaram
suas inferˆencias.
5.7 Implementa¸c˜ao
Para testar a viabilidade do modelo, a realiza¸c˜ao dos experimentos e obten¸c˜ao dos
resultados, o sistema SDICCS foi desenvolvido usando a linguagem de programa¸c˜ao Java,
o framework de desenvolvimento de agentes JADE [BCPR03], compat´ıvel com a espe-
cifica¸c˜ao FIPA [FIP07] e a plataforma aberta de mine ra¸c˜ao de dados WEKA (Ambiente
para An´alise de Conhecimentos Waikato / Waikato Environment for Knowledge Analysis)
[WF05]. A Figura 5.9 apresenta a arquitetura do sistema (os agentes e suas capacidades).
Figura 5.9: Arquitetura do Sistema SDICCS
O pro cess o ´e iniciado no momento em que um agente, que pode ser um coordenador
(A
coord
) ou de aprendizagem (a
i
) se registra na plataforma e torna-se conhecido. Segundo
Liu e Williams [LW04], para que os agentes tenham capacidades sociais e de coopera¸c˜ao
´e necess´ario que o agente tenha uma base de rela¸c˜oes ou acquaintance base. Os autores
enumeram poss´ıveis formas de um agente se tornar conhecido:
56
1. Registrando-se no servi¸co de p´aginas amarelas, como ´e conhecido na especifica¸c˜ao
FIPA [FIP07] ou DF (Facilitador de Diret´orios / Directory Facilitator) como ´e
conhecido no ambiente JADE;
2. Enviando uma mensagem para todos os agentes da plataforma (broadcast);
3. Registrando-se diretamente na lista de endere¸cos do agente alvo da coop era¸c˜ao.
Neste caso, o agente precisa ter essa capacidade implementada.
Nesta implementa¸c˜ao, a op¸c˜ao 1 foi escolhida: O agente registra-se no DF assim
que ele inicia seu ciclo de vida. Se for um agente do tipo coordenador, ele ficar´a esperando
at´e que todos os agentes de aprendizagem entrem no ambiente. Para evitar situa¸c˜oes de
busy-wait
1
, o que consome recursos de m´aquina e polling
2
, o que desperdi¸caria recursos
de rede e do servi¸co de troca de mensagens MTS (Servi¸co de Transporte de Mensagens
/ Message Transport Service), o agente coordenador fica em estado de espera (sleeping),
aguardando uma mensagem inform, com o objetivo de notificar que o agente est´a pronto.
O agente coordenador n˜ao inicia o processo de combina¸c˜ao at´e que todos os n agentes
avisem. Quando o agente coordenador precisar enviar alguma mensagem para os agentes
aprendizes ele utiliza o agente DF e busca agentes com as capacidades de “aprendizes”. O
DF retorna uma mensagem com a performativa inform, retornando a lista de agentes deste
tipo. A Figura
5.10 apresenta um diagrama de sequˆencia do padr˜ao UML (Linguagem
Unificada de Modelagem / Unified Modeling Language) [OMG07] ilus trando a etapa de
registro no ambiente.
Uma vez que todos os agentes de aprendizagem se registram no DF e enviam
uma mensagem com a performativa inform para o agente coordenador, o processo de
classifica¸c˜ao local para os agentes ´e iniciado. A Figura 5.11 apresenta um diagrama de
sequˆencia com as trocas de mensagens realizadas para classifica¸c˜ao local.
1. O agente coordenador envia uma mensagem com a performativa request solicitando
ao DF a lista de agentes de aprendizagem;
2. O agente DF retorna uma lista de endere¸cos dos agentes de aprendizagem;
3. Para cada agente de aprendizagem, o agente coordenador envia uma mensagem com
a performativa request solicitando que os agentes iniciem as classifica¸c˜oes locais;
1
O termo busy-wait ´e usado para descrever processos que aguardam a mudan¸ca de estado de al-
gum dispositivo por um certo tempo e n˜ao liberam recursos de processamento para os demais processos
concorrentes.
2
O termo Polling ´e freq¨uentemente usado para descrever pro ces sos que consultam o estado de um
dispositivo de tempos em tempos. O dispositivo neste caso pode ser, por exemplo, uma fila de mensagens
ou um servidor de e-mail.
57
Figura 5.10: Registro no Ambiente
4. O agente co ordenador fica em estado de espera at´e que todas as mensagens inform
sejam recebidas;
5. Ao final, as hip´oteses dos classificadores hip
i
s˜ao unidas e o conjunto Hip ´e criado;
Figura 5.11: Etapa de Classifica¸c˜ao Local
58
Agora que o conjunto Hip est´a criado o pr´oximo passo ´e enviar o conjunto para
os agentes de aprendizagem. O conjunto ser´a usado para as seguintes finalidades:
• Contar a quantidade de exemplos cobertos correta e incorretamente para cada regra
usando a base de treinamento;
• Identificar regras com conflito em potencial;
• Armazenar este conjunto para ser usado na etapa de c lassifica¸c˜ao (Hip
+ensemble)
A Figura 5.12 apresenta um diagrama de sequˆencia com as trocas de mensagens
realizadas para a etapa de avalia¸c˜ao.
Figura 5.12: Avalia¸c˜ao de Regras em Hip
(Hip´oteses distribu´ıdas)
1. Usando o protocolo Contract-net, o agente coordenador envia as regras para os
agentes avaliarem individualmente nas bases de treinamento;
2. Cada agente de aprendizagem envia a hip´otese com as quantidades de exemplos
cobertos correta e incorretamente para o coordenador e os conflitos usando a per-
formativa propose;
59
3. O agente coordenador envia uma mensagem inform para finalizar o ciclo;
4. Ap´os enviar todos os conjuntos, o agente coordenador soma as informa¸c˜oes de co-
bertura e suporte enviados pelos agentes e cria a fila Q.
O agente coordenador ordena a fila de regras Q pela precis˜ao obtida a partir
da f´ormula
T P
T P +F P
e inicia a otimiza¸c˜ao usando o algoritmo do menor caminho para a
montagem da ´arvore de combina¸c˜ao. A Figura 5.13 apresenta um diagrama de sequˆencia
com as trocas de mensagens realizadas para a etapa de otimiza¸c˜ao.
Figura 5.13: Etapa de Combina¸c˜ao dos Classificadores em Hip para obter Hip
1. Continuar at´e que a fila Q esteja vazia (ver algoritmo 4);
2. Expandir as arestas (ver algoritmo 5);
60
3. Usando o protocolo Contract-net, o agente coordenador envia as regras obtidas pelo
v´ertice com o melhor ganho para os agentes de aprendizagem avaliar;
4. Cada agente de aprendizagem envia a cobertura e o suporte do conjunto de regras
atrav´es de uma mensagem propose;
5. O agente coordenador envia uma mensagem inform para finalizar o ciclo
6. Ap´os sair do la¸co de busca, o agente seleciona o v´ertice com o maior ganho e extrai
o conjunto combinado Hip
. Este conjunto ´e posteriormente enviado aos agentes de
aprendizagem.
Ap´os a finaliza¸c˜ao do processo de combina¸c˜ao, todos os agentes tˆem armazenado
em sua base de conhecimento dois conjuntos de regras: um conjunto combinado e um
ensemble contendo os classificadores de todo o ambiente para vota¸c˜ao quando o conjunto
combinado n˜ao cobrir um novo exemplo.
Qualquer agente, tanto coordenador quanto aprendiz possui a capacidade de clas-
sificar um novo exemplo x. Uma vez que um agente qualquer envia um request com o
exemplo a ser classificado, o agente envia um inform com a predi¸c˜ao da classe e a regra
ou o conjunto de regras disparadas. A Figura 5.14 apresenta um diagrama de sequˆencia
com as trocas de mensagens realizadas.
Figura 5.14: Inferˆencia Usando o SDICCS
61
5.8 Trabalhos Relacionados
Existem poucos trabalhos que realizam a combina¸c˜ao de classificadores simb´olicos
ordenados. Este n´umero ainda ´e menor quando o crit´erio ´e a escolha de sistemas que
usam t´ecnicas de IAD. Acredita-se que a causa ´e a explos˜ao combinat´oria gerada para
combinar regras e descobrir dependˆencias estat´ısticas, inviabilizando em muitos casos o
processamento paralelo, distribu´ıdo e descentralizado. A necessidade de combina¸c˜ao leva
pesquisadores a bus car heur´ısticas que abreviem este espa¸co de busca, encontrando uma
solu¸c˜ao, n˜ao necessariamente ideal, mas muito pr´oxima dela.
O trabalho de Prati e Flach [PF05], apresenta uma alternativa para reduzir a
quantidade de regras ordenadas atrav´es da an´alise de curvas ROC (Receiver Operating
Characteristic). Apesar de n˜ao ser um algoritmo voltado para a minera¸c˜ao distribu´ıda,
busca uma combina¸c˜ao de regras ordenadas onde a ´area da curva ROC n˜ao tenha desn´ıveis.
Os resultados s˜ao encorajadores pois s˜ao compar´aveis aos resultados obtidos por ´arvores
C4.5 sem poda. Se comparado `a nossa abordagem, o trabalho de Prati e Flach traz um
modelo exaustivo que maximiza o ganho atrav´es das combina¸c˜oes. Por´em a falta de uma
heur´ıstica prejudica o desempenho do algoritmo e o inviabiliza em um sistema distribu´ıdo
por gerar muitas trocas de mensagens. J´a o trabalho proposto, apesar de n˜ao retornar o
melhor resultado, abrevia a busca exaustiva favorecendo o desempenho.
O trabalho de Ana Bazzan [SB02] apresenta um trabalho de combina¸c˜ao de c las-
sificadores s imb´olicos atrav´es da coopera¸c˜ao entre agentes. Os agentes avaliam as regras
usando a medida de Laplace para medir a qualidade individual das regras. O meca-
nismo de identifica¸c˜ao de intersec¸c˜oes ´e baseado na an´alise dos antecedentes das regras.
A ausˆencia de um processo centralizador ´e um aspecto relevante, uma vez que impede
gargalos de processamento. Por outro lado, a an´alise do antecedente da regra em bases
com atributos cont´ınuos pode levar a um alto grau de intersec¸c˜ao e perda de ´areas de
cobertura. Al´em disso n˜ao h´a garantia que todas as regras conflitantes sejam encontra-
das, uma vez que o conflito pode existir mesmo que com antecedentes apontando para
diferentes atributos.
O trabalho de Ana Carolina Pilatti [PASE06] apresenta um modelo de integra¸c˜ao
de classificadores simb´olicos independente do mecanismo de ordena¸c˜ao de regras. O mo-
delo usa um agente que coordena as valida¸c˜oes dos conjuntos de regras dos agentes. Cada
agente necessita que suas regras sejam avaliadas pelos outros do grupo. Caso o outro
agente aceite a regra, esta ´e incorporada no seu modelo, caso contr´ario ´e descartada.
´
E
usada uma f´ormula baseada no grau de precis˜ao, cobertura e intersec¸c˜ao da regra, usando
pesos baseados em dados emp´ıricos. Apesar do algoritmo mostrar bons resultados, ´e
62
apresentado um alto grau de instabilidade, uma vez que a regras ordenadas s˜ao usadas
individualmente.
O trabalho de Hall [HCBK99] apresenta um mecanismo de minera¸c˜ao de dados
distribu´ıda que combina regras n˜ao ordenadas atrav´es da an´alise e reconstru¸c˜ao dos an-
tecedentes da regra. Caso exista s obreposi¸c˜ao, o algoritmo altera as regras conflitantes
para suavizar ou remover o conflito e os exemplos n˜ao cobertos s˜ao suprimidos por uma
regra default. Os erros aumentam `a medida que a base de dados cresce. A raz˜ao ´e que os
conflitos v˜ao aumentando `a medida que mais exemplos s˜ao cobertos pela regra.
Apesar de todos estes trabalhos se preocuparem com a privacidade dos dados,
uma vez que n˜ao h´a nec essidade de tr´afego de dados privados pela rede, somente os
classificadores, alguns possue m estrat´egias de busca exaustiva e outros usam diferentes
medidas de avalia¸c˜ao de regras, o que pode comprometer a aplica¸c˜ao da abordagem quando
as regras s˜ao ordenadas. Al´em disso n˜ao h´a uma solu¸c˜ao ´unica para os exemplos n˜ao
cobertos, sendo usada uma regra default em muitos casos. O trabalho apresentado usa
uma heur´ıstica para minimizar a quantidade de combina¸c˜oes de regras e tenta chegar a
uma solu¸c˜ao pr´oxima da “melhor”. Mesmo assim, ´e necess´ario realizar diversas buscas e
conseq¨uentemente diversas trocas de mensagens e avalia¸c˜oes parciais.
5.9 Considera¸c˜oes Finais
Neste cap´ıtulo foi apresentada a metodologia para combina¸c˜ao de classificadores,
detalhando os procedimentos realizados por esta fase. Tamb´em foi apresentado o meca-
nismo de coopera¸c˜ao utilizado pelos agentes na se¸c˜ao de implementa¸c˜ao al´em da discuss˜ao
apresentando trabalhos com caracter´ısticas comuns a este. No pr´oximo cap´ıtulo s˜ao apre-
sentados os experimentos realizados e considera¸c˜oes sobre os resultados obtidos.
63
Cap´ıtulo 6
Experimentos e Resultados
Neste cap´ıtulo ´e apresentada uma avalia¸c˜ao experimental da proposta com o ob-
jetivo de comprovar sua adequabilidade na constru¸c˜ao de um conjunto de regras que
aumenta o poder descritivo de v´arios classificadores e tamb´em apresenta um dese mpenho
superior ao desempenho apresentado pelos classificadores locais e compar´avel ao desem-
penho do m´etodo de voto.
Os conjuntos foram selecionados do reposit´orio de dados da UCI [MMA97]. Bases
com diferentes caracter´ısticas foram selecionadas tais como: quantidade de atributos,
quantidade de exemplos, quantidade de atributos cont´ınuos e discretos, quantidade de
classes e distribui¸c˜ao de classes. O objetivo ´e avaliar a qualidade das regras em termos de
precis˜ao, complexidade baseada na quantidade de antecedentes da regra e o percentual
de cobertura da hip´otese final. Na Tabela 6.1 s˜ao apresentadas as caracter´ısticas dos
conjuntos de dados utilizados nos experimentos. A coluna “Qtd Atributos” n˜ao inclui o
atributo-meta. A distribui¸c˜ao das classes que usa o termo “desbalanceada” diz respeito
`a distribui¸c˜ao n˜ao uniforme dos exemplos em fun¸c˜ao das classes.
Tabela 6.1: Caracter´ısticas das Bases Utilizadas nos Experimentos
Base Qtd
Exemplos
Valores
Faltantes
Qtd Atri-
butos
Atributos
Nominais
Atributos
Num´ericos
Qtd Clas-
ses
Distribui¸c˜ao
Audiology 226 sim 69 69 - 24 desbalanceada
Car 1728 n˜ao 6 6 - 4 desbalanceada
Iris 150 n˜ao 4 - 4 3 balanceada
Monk 1
124 n˜ao 6 6 - 2 desbalanceada
Monk 2 169 n˜ao 6 6 - 2 desbalanceada
Segment 2310 n˜ao 19 - 19 7 balanceada
Soyb ean 683 sim 35 35 - 19 desbalanceada
Tic-Tac-Toe 958 n˜ao 9 9 - 2 desbalanceada
Vehicle 846 n˜ao 18 - 18 4 desbalanceada
Vowel 990
n˜ao 13 3 10 11 balanceada
64
6.1 Prepara¸c˜ao dos Dados
´
E importante relembrar as fases do m´etodo proposto: (i) prepara¸c˜ao dos dados,
(ii) a etapa de aprendizagem local dos agentes classificadores, (iii) a etapa de combina¸c˜ao
das hip´oteses distribu´ıdas e (iv) classifica¸c˜ao de novos exemplos.
Em (i) os processos descritos a seguir foram executados 10 vezes, com o objetivo
de permitir 10 itera¸c˜oes das etapas seguintes:
• Os exemplos foram embaralhados usando uma semente associada a cada itera¸c˜ao;
• As bases foram divididas em duas partes, usando amostragens estratificadas sem
reposi¸c˜ao: a primeira com 80% dos exemplos foi destinada ao treinamento pelos
agentes. Os 20% restantes foram reservados para testar as hip´oteses;
• A base de treinamento foi divida em 10 partes, cada uma com 10% da base de
treinamento, usando amostragens estratificadas com reposi¸c˜ao, sendo que cada parte
foi destinada a um agente de aprendizagem, que por sua vez criou um conjunto de
hip´oteses. Isso significa que cada agente utilizou apenas 80 × 0.1 = 8% dos dados
originais.
Um aspecto que deve ser observado ´e que a quantidade de exemplos para cada
agente em certos casos ´e muito pequena e afeta diretamente a etapa (iii). Por exemplo:
as bases Audiology, Iris, Monk 1 e Monk 2 receberam menos de 20 exemplos treinamento.
O objetivo da divis˜ao ´e criar um cen´ario pr´oximo da realidade, onde os dados est˜ao
distribu´ıdos e n˜ao h´a como realizar uma prepara¸c˜ao preliminar, introduzindo espa¸cos de
tuplas incompletos e possivelmente conflitantes. A Tabela 6.2 apresenta a distribui¸c˜ao de
exemplos por agente para cada conjunto.
Tabela 6.2: Quantidade de Exemplos de Treinamento por Agente
Base Qtd Ori-
ginal
Qtd por
Agente
Audiology 226 18
Car 1728 138
Iris 150 12
Monk 1 124 10
Monk 2 169 13
Segment 2310 184
Soyb ean 683 54
Tic-Tac-Toe 958 76
Vehicle 846 67
Vowel 990 79
65
6.2 An´alise dos Resultados
Todos os experimentos foram realizados usando 10 itera¸c˜oes das bases de dados
dispon´ıveis conforme mencionado na se¸c˜ao anterior. Para avaliar o algoritmo, os experi-
mentos foram comparados com os resultados obtidos nas mesmas bases de dados para os
classificadores locais usando o classificador RIPPER e o m´etodo de voto simples.
Como o objetivo do m´etodo ´e gerar um classificador que seja compreens´ıvel e com
boa taxa de acerto, as compara¸c˜oes se deram sob as perspectivas de: (i) compreensibi-
lidade do modelo e (ii) taxa de acerto. Em (i) foram avaliadas a quantidade de regras
geradas, complexidade e grau de suporte do classificador. Em (ii) foram avaliadas as taxas
m´edias de acerto. Al´em da m´edia dos resultados ´e apresentado o valor de desvio padr˜ao.
Na avalia¸c˜ao dos resultados ´e considerado que um resultado i ´e estatisticamente melhor
que um resultado j , se a m´edia e o desvio padr˜ao de i tem valor superior a m´edia e o
desvio padr˜ao de j.
A Tabela
6.3 apresenta as taxas m´edias de acerto obtidas nas 10 itera¸c˜oes para
os classificadores SDICCS, voto simples e a m´edia dos classificadores locais. Nesta com-
para¸c˜ao o objetivo ´e avaliar a taxa de acerto para o classificador global, que ´e composto da
hip´otese combinada (Hip
) e do ensemble usando vota¸c˜ao simples. Os melhores resultados
obtidos est˜ao destacados em negrito.
Tabela 6.3: Taxas M´edias de Acerto
Base SDICCS Voto Local
Audiology 57.25 ± 8.88 41.74 ± 10.69 35.24 ± 4.70
Car 78.32 ± 2.72 79.57 ± 1.73 73.64 ± 1.43
Iris 94.67 ± 3.58 91.00 ± 7.38 71.50 ± 4.46
Monk 1 75.38 ± 9.96 66.92 ± 13.35 56.62 ± 4.15
Monk 2 65.29 ± 3.87 62.65 ± 3.41 58.35 ± 2.97
Segment 95.48 ± 1.13 93.70 ± 1.67 83.00 ± 1.76
Soyb ean 85.72 ± 3.60 70.07 ± 4.71 50.63 ± 2.75
Tic-Tac-Toe 72.34 ± 4.04 73.33 ± 2.76 67.82 ± 2.01
Vehicle 73.00 ± 2.81 68.53 ± 4.76 53.78 ± 1.66
Vowel 63.08 ± 1.95 55.00 ± 3.68 33.59 ± 1.78
Sob a perspectiva de predi¸c˜ao, as taxas m´edias de acerto se mostraram significati-
vamente acima das execu¸c˜oes individuais e compar´aveis com o m´etodo de voto, inclusive
no grau de estabilidade apontado pelo desvio padr˜ao.
A Tabela 6.4 apresenta os resultados m´edios obtidos sob a perspectiva de cobertura
nas bases de teste para o conjunto de regras Hip
. Na etapa de classifica¸c˜ao este conjunto
´e usado antes do voto por tratar-se de um conjunto est´atico e de consenso entre os agentes
de aprendizagem em bases disjuntas. Al´em de apresentar o grau de cobertura, a tabela
apresenta o percentual de exemplos cobertos pela regra default dos classificadores locais.
66
Figura 6.1: Compara¸c ˜ao Gr´afica dos Resultados
Tabela 6.4: Grau de Cobertura do Conjunto Hip
e da Regra Default Local
Base SDICCS Local
Cobertura (%) 100 - Cober-
tura (%)
Cobertura Regra
default (%)
Audiology 73, 48 ± 15, 40 26, 52 70, 37 ± 7, 05
Car 37, 28 ± 4, 86 62, 72 74, 01 ± 2, 31
Iris 98, 33 ± 4, 23 1, 67 49, 27 ± 2, 16
Monk 1 89, 23 ± 9, 73 10, 77 76, 46 ± 8, 32
Monk 2 50, 29 ± 36, 72 49, 71 78, 59 ± 8, 21
Segment 99, 70 ± 0, 61 0, 30 20, 09 ± 1, 13
Soybean 97, 17 ± 3, 01 2, 83 37, 72 ± 3, 36
Tic-Tac-Toe 55, 57 ± 4, 39 44, 43 68, 45 ± 5, 38
Vehicle 97, 94 ± 2, 19 2, 06 42, 84 ± 3, 52
Vowel 92, 32 ± 6, 22 7, 68 42, 44 ± 3, 18
Para todos os casos ´e poss´ıvel perceber que a regra default ´e constantemente usada
no classificador local. Isto ocorre porque o modelo ´e adaptado de acordo com as carac-
ter´ısticas e distribui¸c˜ao da base de treinamento. Quando as regras n˜ao s˜ao disparadas ao
classificar um novo exemplo, a regra default ´e disparada.
O conjunto de regras Hip
n˜ao possui regras default, uma vez que h´a uma e tapa de
elimina¸c˜ao destas regras antes do processo de combina¸c˜ao. Esta a¸c˜ao reduz automatica-
mente o grau de cobertura deste conjunto. A etapa de combina¸c˜ao pode eliminar regras
com baixo desempenho, reduzindo novamente o grau de cobertura. Em algumas bases, o
classificador RIPPER gerou conjuntos que s´o tinham a regra default. Conseq¨uentemente,
a etapa de elimina¸c˜ao de regras default desprezou o conhecimento obtido daquela base
67
disjunta. Este efeito reduz o grau de cobertura e aumenta a instabilidade do classificador.
O sintoma pode ser observado no conjunto monk2 e audiology. Por exemplo: Na base
monk2, a itera¸c˜ao 4 produziu 6 classificadores deste tipo. Na base audiology esse n´umero
chegou a 4 na sexta itera¸c˜ao. Isto tamb´em ocorreu nas bases monk1 e tic-tac-toe.
Houve um aumento do grau de cobertura em todas as bases. A coluna (100 -
cobertura) apresenta os pe rcentuais onde o classificador Hip
n˜ao atuou. Sob a perspectiva
de capacidade de predi¸c˜ao ´e desej´avel que este n´umero seja sempre menor do que cobertura
da regra default. Nos casos onde este n´umero ´e muito pr´oximo da cobertura da regra
default os agentes combinaram regras com forte independˆencia estat´ıstica. Isto pode
ser verificado na base Car. J´a no outro extremo, onde a quantidade de exemplos n˜ao
cobertos pelo conjunto Hip
´e pequeno, o algoritmo expandiu a cobertura atrav´es de
regras inseridas. Foram observados casos com grau de intersec¸c˜ao positivo. Entende-se
por grau de intersec¸c˜ao positivo as regras que cobrem ´areas comuns e apontam para a
mesma classe alvo. Com exce¸c˜ao da base Car, este comportamento foi percebido em todas
as outras bases.
Tabela 6.5: Quantidade M´edia de Regras Geradas
Base SDICCS Local
Audiology 7, 90 ± 3, 41 2, 74 ± 0, 44
Car 13, 20 ± 3, 55 6, 53 ± 0, 55
Iris 7, 70 ± 1, 77 2, 81 ± 0, 10
Monk 1 4, 70 ± 1, 25 1, 74 ± 0, 21
Monk 2 2, 90 ± 2, 18 1, 77 ± 0, 25
Segment
36, 50 ± 4, 43 9, 23 ± 0, 42
Soyb ean 29, 20 ± 2, 90 9, 89 ± 0, 47
Tic-Tac-Toe 8, 30 ± 2, 00 3, 63 ± 0, 31
Vehicle 22, 60 ± 2, 80 5, 33 ± 0, 33
Vowel 44, 10 ± 5, 95 9, 53 ± 0, 50
A Tabela 6.5 apresenta a quantidade m´edia de regras do conjunto Hip
. Foi ve-
rificado que as bases que apresentaram maior quantidade de regras possuem atributos
cont´ınuos. Algumas regras descobertas, apesar de consistentes possuem um certo grau de
intersec¸c˜ao com outras. As regras apresentadas na figura 6.2, foram extra´ıdas do conjunto
Hip
da base Segment na primeira itera¸c˜ao. Como pode ser observado, essas regras podem
ter intersec¸c˜ao para a primeira condi¸c˜ao de ambas, que usam o atributo intensity mean,
caso sejam tratadas como n˜ao ordenadas. Por tratarem-se de regras ordenadas, a segunda
regra funciona como um complemento da primeira: nas situa¸c˜oes onde a regra 1 n˜ao for
disparada, a regra 2 poder´a ser. Elas s˜ao complementares e al´em disso apontam para a
mesma classe alvo window. Este grau de intersec¸c˜ao ´e considerado positivo pois a classe
alvo ´e a mesma.
Em geral, ´e poss´ıvel perceber um aumento na quantidade de regras. Esse aumento
68
R1
ag9
=
se in tensity mean ≤ 22, 6667
e exred mean ≤ −10, 4444
e hedge mean ≤ 1, 05556 → class = window
R2
ag1
=
se in tensity mean ≤ 2, 96296
e rawred m ean ≥ 0, 777778 → class = window
Figura 6.2: Regras da Base Segment com Intersec¸c˜ao
pode ser explicado pela substitui¸c˜ao da regra default em muitos casos e descoberta de
novas regras complementares. Entende-se por regras complementares aquelas regras que
possuem conflito com outras e apresentam desempenho melhor quando combinadas, antes
ou depois do conflito.
Tabela 6.6: Cobertura dos classificadores locais (Hip) e SDDICS (Hip
)
A tabela 6.6 apresenta gr´aficos que comparam a cobertura dos classificadores locais
(Hip) e o classificador gerado pelo SDDICS (Hip
). Em todas as bases houve acr´esc imo
na cobertura.
Tabela 6.7: Complexidade M´edia das Regras Selecionadas
Base SDICCS Local
Audiology 1, 41 ± 0, 10 0, 73 ± 0, 14
Car 2, 94 ± 0, 16 2, 21 ± 0, 11
Iris
1, 13 ± 0, 11 0, 68 ± 0, 04
Monk 1 1, 09 ± 0, 13 0, 39 ± 0, 11
Monk 2 1, 30 ± 0, 59 0, 42 ± 0, 12
Segment 1, 87 ± 0, 11 1, 44 ± 0, 07
Soyb ean 1, 57 ± 0, 05 1, 18 ± 0, 02
Tic-Tac-Toe 2, 23 ± 0, 16 1, 35 ± 0, 13
Vehicle
1, 72 ± 0, 13 1, 32 ± 0, 09
Vowel 1, 79 ± 0, 08 1, 44 ± 0, 05
A Tabela 6.7 apresenta a complexidade m´edia das regras nos classificadores SDICCS
e Local. Entende-se por complexidade de regra, a quantidade de antecedentes.
69
´
E poss´ıvel perceber que nas bases Audiology, Iris, Monk1 e Monk2, a complexidade
m´edia ´e inferior a 1 para o modelo local, indicando que ce rtos conjuntos tinham apenas
a regra default. A complexidade das regras geradas pelo SDICCS foi maior em todos os
casos basicamente por duas raz˜oes: (i) A regra default ´e substitu´ıda por conhecimento
obtido em outras bases e (ii) regras gen´ericas geradas por classificadores disjuntos n˜ao
ter˜ao mesma performance no conjunto completo pois h´a uma tendˆencia de permanecer
apenas regras mais espec´ıficas com alto grau de suporte.
A partir dos resultados acima relacionados, leva-se a crer que o sistema SDICCS,
o qual usa um mecanismo de combina¸c˜ao de classificadores e de inferˆencia baseado em
um conjunto de regras combinadas e voto, resulta em valores compar´aveis `a t´ecnica de
voto, com a vantagem de aumentar o poder descritivo do classificador. Al´em disso, se
mostrou significativamente superior aos modelos locais sob as perspectivas de predi¸c˜ao e
poder descritivo.
70
Cap´ıtulo 7
Conclus˜oes
A utiliza¸c˜ao de t´ecnicas de Inteligˆencia Artificial Distribu´ıda (IAD), uma sub-´area
de Inteligˆencia Artificial (IA) que estuda t´ecnicas de resolu¸c˜ao distribu´ıda de problemas
(RDP) pode contribuir para aplica¸c˜oes em Minera¸c˜ao de Dados Distribu´ıda (DDM) vi-
sando melhorar a escalabilidade, taxa de acerto, po de r de predi¸c˜ao e compreensibilidade
atrav´es da coopera¸c˜ao entre agentes capazes de combinar classificadores e classificar novos
exemplos.
O presente trabalho apresentou um sistema distribu´ıdo para minera¸c˜ao de dados
distribu´ıdos simulando um ambiente onde as bases de dados est˜ao particionadas. Em
cada subconjunto agentes realizaram a aprendizagem local sendo os resultados avaliados
para se chegar a um conjunto de hip´oteses combinado. O sistema usa coopera¸c˜ao para
classificar novos exemplos quando o conjunto combinado n˜ao tiver cobertura.
A compara¸c˜ao com os m´etodos de classifica¸c˜ao por voto e classifica¸c˜ao local per-
mitiu avaliar o modelo sob duas perspectivas:
• Predi¸c˜ao:
O modelo se mostrou compar´avel ao modelo de voto, sendo que em alguns casos, com
melhores resultados. Al´em disso o modelo se mostrou significativamente superior se
comparado aos classificadores locais.
• Poder descritivo:
Quando comparamos com os modelos locais ´e poss´ıvel perceber que o m´etodo preen-
che a lacuna gerada por regras default, trazendo maior legibilidade e p oder descritivo
ao classificador, al´em de expandir o conhecimento sobre bases de treinamento n˜ao
conhecidas. N˜ao h´a como usar esse crit´erio de compara¸c˜ao com o modelo de voto,
j´a que este modelo tem um poder de descri¸c˜ao baixo por n˜ao ser est´atico e de dif´ıcil
avalia¸c˜ao, uma vez que o conhecimento est´a distribu´ıdo.
71
Foi observado que a quantidade de regras aumenta nas bases onde h´a presen¸ca
de atributos cont´ınuos. Isto ocorre devido `a intersec¸c˜ao nos intervalos dos testes dos
atributos presentes nos antecedentes da regra. Futuramente, dever´a ser investigada uma
abordagem para reduzir a complexidade das regras, atrav´es da altera¸c˜ao dos antecedentes
da regra. O trabalho de [SHA00] apresenta um m´etodo com essa caracter´ıstica.
A principal contribui¸c˜ao deste trabalho foi o desenvolvimento de uma metodolo-
gia que pode ser aplicada em ambientes distribu´ıdos para a cria¸c˜ao de um classificador
consistente e unificado, que tem poder de predi¸c˜ao compar´avel ao modelo de voto e signifi-
cativamente melhor do que os modelos locais. O modelo tamb´em se destaca nas situa¸c˜oes
onde ´e necess´ario uma explica¸c˜ao sobre a decis˜ao tomada pelo classificador, uma vez que
usa parte do conhecimento de um classificador consensual. Al´em disso expande a ´area de
cobertura da regra sendo uma solu¸c˜ao para a regra default.
Este trabalho traz contribui¸c˜oes para as ´areas de algoritmos de aprendizagem
simb´olica, t´ecnicas de resolu¸c˜ao distribu´ıda de problemas e minera¸c˜ao distribu´ıda de da-
dos.
7.1 Trabalhos Futuros
Diversas extens˜oes deste trabalho podem ser exploradas e podem s˜ao divididas em
cinco perspectivas:
• Mecanismos de Avalia¸c˜ao de Regras: atualmente o modelo est´a baseado nas medi-
das de precis˜ao e suporte. No entanto abordagens que exploram, c omo por exemplo,
as caracter´ısticas de novidade e interessabilidade devem ser avaliadas;
• Estrat´egias de Busca: outras estrat´egias de busca heur´ıstica podem ser testadas,
com enfoque na diminui¸c˜ao das combina¸c˜oes e maximiza¸c˜ao do ganho;
• Dados: diferentes distribui¸c˜oes do conjunto de treinamento e teste devem ser
realizadas;
• Crit´erio de Compara¸c˜ao: uma vez que o m´etodo se mostrou compar´avel ao modelo
de voto, deve m ser adicionadas outras abordagens de classifica¸c˜ao para compara¸c˜ao.
• Mecanismos de aprendizagem: Explorar a possibilidade de usar exemplos n˜ao
cobertos pelo conjunto de regras unificado como dados de treinamento para a cria¸c˜ao
de novas regras.
72
Como pode ser percebido, existem diversas possibilidades promissoras que certa-
mente v˜ao aprimorar o modelo em es tudos futuros. Nesta etapa, a concentra¸c˜ao dos
esfor¸cos foram na obten¸c˜ao de um modelo com taxas de acerto compar´aveis ao modelo de
voto e ganho no poder de compreensibilidade.
73
Referˆencias Bibliogr´aficas
[AW97] C. APT
´
E and S. WEISS. Data mining with decision trees and decision rules.
pages 197–210. Elsevier Science, 1997.
[BCPR03] F. BELLIFEMINE, G. CAIRE, A. POGGI, and G. RIMASSA. Jade, a white
paper. Exp - Volume 3 - n. 3, 2003.
[BD03] J. BIGHAM and L. DU. Cooperative negotiation in a multi-agent system for
realtime load balancing of a mobile cellular network. In Proceedings of the
Second International Joint Conference on Autonomous agents and multiagent
systems, pages 568–575, 2003.
[BER02] F. C. BERNARDINI. Combina¸c˜ao de classificadores simb´olicos para melhorar
o poder preditivo e descritivo de ensembles. Master’s thesis, ICMC/USP,
2002.
[BG88] A. H. BOND and L. GASSER. Readings in Distributed Artificial Intelligence.
Morgan Kaufmann Publishers: San Mateo, CA, 1988, 1st edition, 1988.
[BG89] A. H. BOND and L. GASSER. A comparison of atms and csp techniques.
pages 367–384. Morgan Kaufmann P ublishers, 1989.
[BGB07] J. BACARDIT, E. GOLDBERG, and M. V. BUTZ. Improving the perfor-
mance of a pittsburgh learning classifier system using a default rule. Lecture
Notes in Computer Science, 4399:291–307, June 2007.
[BMP06] F. C. BERNARDINI, M. C. MONARD, and R. C. PRATI. Constructing
ensembles of symbolic classifiers. International Journal on Hybrid Intelligent
Systems (IJHIS), 3(3):159–167, 2006.
[CdRFP98] Cristiano Castelfranchi, Fiorella de Rosis, Rino Falcone, and Sebastiano Piz-
zutilo. Personality traits and social attitudes in multiagent cooperation. Ap-
plied Artificial Intelligence, 12(7-8):649–675, 1998.
74
[CF98] Cristiano Castelfranchi and Rino Falcone. Towards a theory of delegation for
agent-based systems. Robotics and Autonomous Systems, 24(3-4):141–157,
1998.
[CL04] F. COENEN and P. LENG . An evaluation of approaches to classification rules
selection. Fourth IEEE International Conference on Data Mining (ICDM’04),
pages 359–362, 2004.
[COH95] W. W. COHEN. Fast effective rule induction. Proceedings of the 12th Inter-
national Conference on Machine Learning (ICML’95), pages 115–123, 1995.
[CS95a] P. K. CHAN and S. J. STOLFO. A comparative evaluation of voting and
meta-learning on partitioned data. In International Conference on Machine
Learning, pages 90–98, 1995.
[CS95b] P. K. CHAN and S. J. STOLFO. Learning arbiter and combiner trees from
partitioned data for scaling machine learning. In Knowledge Discovery and
Data Mining, pages 39–44, 1995.
[DIE89] T. DIETTERICH. Limitations on inductive learning. In Proceedings of the
Sixth International Workshop on Machine Learning, pages 124–128, 1989.
[DIE97] T. DIETTERICH. Machine learning res earch: Four current directions. AI
magazine, pages 97–136, 1997.
[DIJ59] E W. DIJKSTRA. A note on two problems in connexion with graphs. In
Numerische Mathematik, pages 269–271, 1959.
[DL89] E. H. DURFEE and V. R. LESSER. Negotiating task decomposition and
allocation using partial global planning. Pitman Publishing: London and
Morgan Kaufmann: San Mateo, CA, 1st edition, 1989.
[DL91] E. H. DURFEE and V. R. LESSER. Partial Global Planning: A Coordination
Framework for Distributed Hypothesis Formation. IEEE Transactions on
Systems, Man and Cybernetics, 21(5):1167–1183, Septembe r 1991.
[DL95] K. S. DECKER and V. R. LESSER. Designing a family of coordination algo-
rithms. Proceedings of the Thirteenth International Workshop on Distributed
AI, pages 65–84, 1995.
[DUR99] E. H. DURFEE. Distributed problem solving and planning. Lecture Notes
in Computer Science, pages 121–164, chapter 3, 1999.
75
[EV06] F. ENEMBRECK and B. C.
´
AVILA. Knoma: A new approach for knowledge
integration. In 11th IEEE Symposium on Computers and Communications,
pages 898–903, 2006.
[FER03] J. FERBER. Multi-Agent Systems: An Introduction to Distributed Artificial
Intelligence. Addison-Wesley, 1st edition, 2003.
[FF03] J. FURNKRANZ and P. A. FLACH. An analysis of rule evaluation metrics.
Proc. 20th International Conference on Machine Learning (ICML 03), pages
202–209, 2003.
[FIP07] FIPA. Foundation for intelligent physical agents. http://www.fipa.org,
2007. Data de Acesso: 12/10/2007.
[FL98] A. FREITAS and S. H. LAVINGTON. Mining Very Large Databases with
Parallel Processing. Kluwer Academic Publishers, 1st edition, 1998.
[FPSS96] U. M. FAYYAD, G. PIATETSKY-SHAPIRO, and P. SMYTH. From data
mining to knowledge discovery: an overview. pages 1–34, Menlo Park, CA,
USA, 1996. American Association for Artificial Intelligence.
[FS97] Y. FREUND and R. SCHAPIRE. A decision-theoretic generalization of on-
line learning and an application to boosting. Journal of Computer and System
Sciences, 55(1):119–139, 1997.
[FUR99] J. FURNKRANZ. Separate-and-conquer rule learning. Artificial Intelligence
Review, 13(1):3–54, 1999.
[GA04] N. GATTI and F. AMIGONI. A cooperative negotiation protocol for phy-
siological model combination. In Proceedings of the Third Internation Joint
Conference on Automomous Agents and Multi-Agent Systems, pages 665–662,
2004.
[GL00] D. GAMBERGER and N. LAVRAC. Confirmation rule sets. 4th European
Conference on Principles of Data Mining and Knowledge, 1:34–43, 2000.
[GLK02] D. GAMBERGER, N. LAVRAC, and KRSTACIC. Confirmation rule induc-
tion and its applications to coronary heart disease diagnosis and risk group
discovering. Journal of Intelligent and Fuzzy Systems: Applications in Engi-
neering and Technology, 12:35–48, 2002.
76
[HCBK99] L. O. HALL, N. CHAWLA, K. W. BOWYER, and W. P. KEGELMEYER.
Learning rules f rom distributed data. In Large-Scale Parallel Data Mining,
pages 211–220, 1999.
[HK00] J. HAN and M. KAMBER. Data mining. concept and techniques. Morgan
Kaufman Publishers, 2000.
[HY97] K. HIRAYAMA and M. YOKOO. Distributed partial constraint satisfaction
problem. Principles and Practice of Constraint Programming CP97, pages
222–236, 1997.
[JSW98] N. R. JENNINGS, K. SYCARA, and M. WOOLDRIDGE. A roadmap of
agent research and development. Autonomous Agents and Multi-Agent Sys-
tems, pages 7–38, 1998.
[KLM03] M. KLUSCH, S. LODI, and G. MORO. Agent-based distributed data mining:
The kdec scheme. Lecture Notes in Computer Science, 2586:104–122, 2003.
[KPHJ00] H. KARGUPTA, B. PARK, D. HERSHBERGER, and E. JOHNSON. Col-
lective data mining: A new perspective toward distributed data mining. Ad-
vances in Distributed and Parallel Knowledge Discovery. AAAI/MIT Press,
pages 131–178, 2000.
[LES99a] V. R. LESSER. Cooperative multiagent systems: a personal view of the state
of the art. Transactions on Knowledge and Data Engineering, 11(1):133–142,
1999.
[LES99b] V. R. LESSER. Cooperative multiagent systems: A personal view of the
state of the art. Knowledge and Data Engineering, 11(1):133–142, 1999.
[LFZ99] N. LAVRAC, P. FLACH, and B. ZUPAN. Rule evaluation measures: A
unifying view. In S. Dzeroski and P. Flach, editors, Ninth Internatio-
nal Workshop on Inductive Logic Programming (ILP’99), pages 174–185.
Springer-Verlag, June 1999.
[LS95] P. LANGLEY and P. SIMON. Applications of machine learning and rule
induction. Communications of the ACM, 38:55–64, 1995.
[LW04] W. LIU and M. WILLIAMS. A framework for multi-agent belief revision.
Studia Logica, pages 291–312, 2004.
77
[MLH03] M. MAILLER, V. R. LESSER, and B. HORLING. Cooperative negotiation
for soft real-time distributed resource allocation. In Proceedings of the second
international joint conference on Autonomous agents and multiagent systems,
pages 5–40, 2003.
[MMA97] C. MERZ, P. MURPHY, and D. AHA. Uci repository of machine learning da-
tabases. Dispon´ıvel em: http://www.ics.uci.edu/mlearn/MLRepository.
html, 1997.
[OCA01] J. ORTEGA, M. COPPEL, and S. ARGAMON. Arbitraining among compe-
ting classifiers using learned referees. Knowledge and Information Systems,
pages 470–490, 2001.
[OMG07] OMG. Unified modeling language (uml) specification. http://www.omg.org/
technology/documents/formal/uml, 2007. Data de Acesso: 12/10/2007.
[PASE06] A.C.M. PILATTI, B. C. AVILA, E. SCALABRIN, and F. ENEM-
BRECK. Multiagent-based model integration. Proceedings of the 2006 IEE-
E/WIC/ACM International Conference on Web Intelligence and Intelligent
Agent Technology (WI-IAT 2006 Workshops)(WI-IATW’06), pages 11–14,
December 2006.
[PBM02] R. C. PRATI, J. A. BARANAUSKAS, and M. C. MONARD. Padroniza¸c˜ao
da sintaxe e informa¸c˜oes sobre regras induzidas a partir de algoritmos de
aprendizado de m´aquina simb´olico. Revista Eletrˆonica de Inicia¸c˜ao Cient´ıfica
- Sociedade Brasileira de Computa¸c˜ao, 2002.
[PC00] A. PRODOMIDIS and P. K. CHAN. Meta-learning in distributed data mining
systems: Issues and Approaches. AAAI press, 2000. Book on Advances of
Distributed Data Mining.
[PF05] R. C. PRATI and P. A. FLACH. Roccer: an algorithm for rule learning based
on roc analysis. Proceedings of the 19th International Joint Conference on
Artificial Intelligence (IJCAI’05), pages 823–828, August 2005.
[PH96] F. J. PROVOST and D. HENNESSY. Scaling up: Distributed machine lear-
ning with cooperation. In Proceedings of the Thirteenth National Conference
on Artificial Intelligence, pages 74–79, Portland, OR, 1996.
78
[PJMY02] M. Tambe P. J. MODI, W. SHEN and M. YOKOO. An asynchronous com-
plete method for distributed constraint optimization. Proceedings of the se-
cond international joint conference on Autonomous agents and multiagent
systems, pages 161–168, 2002.
[QR89] J. R. QUINLAN and R. L. RIVEST. Inferring decision trees using the mi-
nimum description length principle. Information and Computation, 80:227–
248, 1989.
[QUI93] J. R. QUINLAN. C4.5: Programs for Machine Learning. Morgan Kaufmann,
1st edition, 1993.
[QUI95] J. R. QUINLAN. MDL and categorial theories (continued). In International
Conference on Machine Learning, pages 464–470, 1995.
[RN04] S. RUSSEL and P. NORVIG. Inteligˆencia Artificial. Elsevier Editora, 2nd
edition, 2004.
[SB02] L.F. SCHROEDER and A. L. C. BAZZAN. A multi-agent system to facilitate
knowledge discovery: an application to bioinformatics. In Proceedings of the
Workshop on Bioinformatics and Multi-Agent Systems, Bologna, Italy, pages
44–50, 2002.
[SB05] C. T. SANTOS and A. BAZZAN. Integrating knowledge through cooperative
negotiation - a case study in bioinformatics. Int. Workshop on Autonomous
Intelligent Agents: Agents and Data Mining, 2005.
[SD83] R. SMITH and R. DAVIS. Negotiation as a metaphor for distributed problem
solving. Artificial Intelligence, 20:63–109, 1983.
[SEN06] L. G. M. SENKO. Um m´etodo baseado em l´ogica paraconsistente para de-
tec¸c˜ao de inconsistˆencias em classificadores `a base de regras. Master’s thesis,
PPGIA/PUCPR, 2006.
[SHA00] N. SHAWLA. Ride: Rule learning in a distributed environment. Master’s
thesis, University of South Florida, 2000.
[SPT
+
97] S. STOLFO, A. PRODOMIDIS, S. TSELEPIS, W. LEE, and D. FAN. Jam:
Java agents for meta-learning over distributed databases. In Proceedings of
the Third Internation Conference on Knowledge Discovery and Data Mining,
pages 74–81, 1997.
79
[TD00] L. TODOROVSKI and S. DZEROSKI. Combining classifiers with meta de-
cision trees. Proceedings of 4th European Conference on Principles of Data
Mining and Knowledge Discovery (PKDD-00), Springer Verlag, pages 54–64,
2000.
[WF05] I. H. WITTEN and E. FRANK. Data mining: Practical machine learning
tools and techniques. Morgan Kaufmann, pages 131–178, 2005.
[WJ95] M. WOOLDRIDGE and N. R. JENNINGS. Intelligent agents: Theory and
practice. Knowledge Engineering Review, 10(2):115–152, 1995.
[WOL90] D. H. WOLPERT. Stacked generalization. Technical Report LA-UR-90-3460,
Los Alamos, NM, 1990.
[YOS03] K. YOSHIMURA. Ipa jack: A plugin for jack intelligent agents. School of
Computer Science and Information Technology, 2003.
[ZJW01] F. ZAMBONELLI, N. R. JENNINGS, and M. WOOLDRIDGE. Organisati-
onal abstractions for the analysis and design of multi-agent systems. Lecture
Notes in Computer Science, 1957, 2001.
[ZLP05] X. ZHANG, V. R. LESSER, and R. PODOROZHNY. Multi-dimensional,
multistep negoriation for task allocation in a cooperative system. Autonomous
Agents and Multi-Agent Systems, pages 5–40, 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
