EVERTON
TAVARES
STELLA MARA CARVALHO
DATA MINING BASEADO
NO SISTEMA
CURITIBA
2002
SILVA
IMUNOLOGICO
ARTIFICIAL
EVERTON TAVARES
STELLA MARA CARVALHO
DATA MINING BASEADO
SILVA
NO SISTEMA IMUNOLOGICO
MQnog~fia
oorlclu~o
ARTIFICIAL
apre$entada.
como
00
Curso
de
Proceuamento de Oados d.,
re<luisilO pan:ial b
Tecnokloia
em
Unilo'l!irsidade
luiu!i
do Parana
Orjentooora:
CURITIBA
2002
ProP. Dr-. Deboolh
Ribeiro Carvalho
EVERTON TAVARES
STELLA MARA CARVALHO
DATA MINING BASEADO
Monografia
SILVA
NO SISTEMA IMUNOLOGICO
aprovada como requisi10 parcial a conclusao
ARTIFICIAL
do CurSD de Tecnologia
em Processamento de Dados da Universidade Tuiuti do Parana,
fannada pelos professares:
Orientadora:
ProF'.
Dr'.
Deborah Ribeiro Carvalho
Universidade
Tuiuti do Parana, UTP
Prof. Or. Eduardo Raul Hruschka
Universidade Tuiuti do Parana, UTP
Prof. Dr. Leandro dos Santos Coelho
Universidade
Tuiuti do Parana, UTP
ProfD. Elaini Simoni Angeletti
Universidade
Tuiuti do
Parana, UTP
Curitiba, 29 de novembro de
2002
pete comissao
AGRADECIMENTOS
A nossa orientadora ProP'. Dr-. Deborah Ribeiro
Carvalho, par sua competencia
e por ter acreditado em
nosso potencial.
A minha esposa, meu am or, per seu apoio e pacillncia.
A Deus, aos meus pais. e especialmente
a urn
amigo que me ajudou em hora5 dificeis, Sergio Martenetz, e
seu filho Marcelo Martenetz, meu companheiro,
meu am or.
~.s
"Tudo tem Jell t~I1WO 8 afi! Gsrtas rrniIJ;'e~t1J¢Je. trn'tis
tI Oliginnil enlrnm em vog.l au SOlJm de modtl. ,\11/11II
sabedorM rom umit Vflllt4!gem: ~ e/C!mtt."
BJliiu,."r Grl3cijn
SUMARIO
LlSTA DE FIGURAS
.
LlSTA DE TABELAS
.
.
vii
...................................................
viii
LlSTA DE ABREVIATURAS
ix
RESUMO
x
1. INTRODUc;:Ao
1
2. KDD - KNOWLEDGE
2.1
DISCOVERY
FROM DATABASES
ETA PAS DO KDD - KNOWLEDGE
2.1.1
DISCOVERY
SELEc;:AO DE DADOS
2.1.2
LlMPEZA OU PRE-PROCESSAMENTO
TRANSFORMAc;:AO
2.1.4
DATA MINING
2.1.5
INTERPRETAc;:AO
2.1.6
CONSOLlDAc;:AO
..
..
OU ENRIQUECIMENTO
5
DOS DADOS
6
7
E AVALlAc;:AO
8
DO CONHECIMENTO
DESCOBERTO
DE DATA MINING
8
10
3.1 CLUSTERING
10
3.2
DESCOBERTAS
3.3
CLASSIFICAc;:Ao
3.4
TECNICAS
DE REGRAS DE ASSOCIAc;:Ao
11
DE DADOS
12
DE CLASSIFICAc;:Ao
3.4.1
ARVORES
3.4.2
ALGORITMOS
3.4.3
SISTEMA
ARTIFICIAL
4
.4
2.1.3
3. TAREFAS
4
FROM DATABASES
14
DE DECISAO
14
GENETICOS
IMUNOL6GICO
...
E SISTEMA
..
16
IMUNOL6GICO
..
4. METODOLOGIA
DE DESENVOLVIMENTO
4.1
DA MODELAGEM
DEFINIc;:Ao
..
DO SIA
DO PROTOTIPO
20
27
27
4.1.1
ALGORITMO
IMUNOL6GICO
PARA PEQUENOS
4.2
4.3
PARA DESCOBERTA
DISJUNTOS
4.1.2
REPRESENTA<;;Ao
4.1.3
FUN<;;AO DE AVALlA<;;AO..
4.1.4
SELE<;;AO CLONAL..
4.1.5
DEFINI<;;AO DA BASE DE DADOS ORIGINAL
4.1.6
DEFINI<;;Ao DA BASE DE TREINAMENTO
4.1.7
DEFINI<;;AO DA BASE DE TESTES
4.1.8
ARQUIVO
4.1.9
DEFINI<;;AO DAS ESTATisTICAS
4.1.10
PSEUDOC6DIGO
REALlZA9AO
DE REGRAS
...................................
..
DO ANTICORPO..
27
.... 29
..31
.
31
.
34
.
.....................................................
NAMES ..
34
35
DA BASE DE DADOS
35
35
36
DOS EXPERIMENTOS
38
4.2.1
EXPERIMENTO
COM A BASE HOUSE-VOTES
4.2.2
EXPERIMENTO
COM A BASE HEPATITIS
41
4.2.3
EXPERIMENTO
COM A BASE CRX
41
ANALISE
DOS RESULTADOS
.40
46
5. CONCLUSAO
48
REFERENCIAS
49
vi
LlSTA DE FIGURAS
o PROCESSO
EXEMPLOS
KDD E SUAS ETAPAS
.4
DE CLUSTERING
11
TIPOS DE CRUZAMENTO
ESTRUTURA
DO ANTICORPO
19
(ANTECEDENTE
DA REGRA)
REGRA CRIADA ATRAVES DA BASE DE TREINAMENTO
30
43
LlSTA DE TABELAS
DISTRIBUI<;:AO DOS ATRIBUTOS
METAS DA BASE HOUSE-VOTES
DISTRIBUI<;:Ao
DOS ATRIBUTOS
METAS BASE HEPATITIS
.. 40
.41
DISTRIBUI<;:Ao
DOS ATRIBUTOS
METAS BASE CRX.
.42
ANALISE
DOS RESULTADOS
DO SIA COMPARADO
AO C4.5
.46
ANALISE
DOS RESULTADOS
DO SIA COMPARADO
AO C4.5/AI
.47
viii
USTA DE ABREVIATURAS
AG
ALGORITMO GENETICO
AGs
ALGORITMOS GENETICOS
AI
ALGORITMO IMUNOL6GICO
AIS
ARTIFICIAL
SIA
SISTEMA IMUNOL6GICO
IMMUNE SYSTEMS
ARTIFICIAL
;,
RESUMO
o foco deste trabalho esta centrado na tarefa de classifica9ao, cnde deseja-se
atribuir a urn exemplo (re9i5tro) urna dasse, dentre urn conjunto de classes predefinidas, com base nos valores de atributos daquele exemplo. No contexto da
tarera de classifica~o,
0 conhecimento
descoberto pode ser expresso atraves de
urn oonjunto de regras "se..<condiyao>..
entao ..<atyao> ..". Este tipo de
representa~o
tern a vantagem de ser intuitivamente compreensivel
para 0
usuario. Existem varios algoritmos que pod em construir classificadores a partir do
conhecimento implicito em urna base de dadas, entre eles, algoritmos de arvare
de decisao, algoritmos geneticos, algoritmos
imunol6gicos, etc. 0 sistema
imunologico biol6gico pode ser a base para a constru9Bo de algoritmos que
cumpram a tarefa de classificayao em Data Mining. Apesar de seu alto grau de
complexidade trata-se de uma "inspiray:.io" de grande interesse pela comunidade
cientifica da area de computayao.O objetivo principal deste trabalho e propor urn
novo algoritmo
que construa urn classificador
a partir da implementac;ao
computacional de alguns dos principais conceitos do Sistema Imunol6gico. Os
resultados obtidos a partir dos experimentos realizados no escopo deste projeto
poderao ser comparados com os resultados obtidos pelo C4.S e 0 C4.5/AI,
apresentado no artigo Urn Algoritrno Imunol6gico para descobrir regras para
pequenos disjuntos em Data Mining, da ProF'. Dr-. Deborah Ribeiro Carvalho e
Prof. Dr. Alex Alves Freitas.
1. INTRODUC;;AO
e
A atual "era da informaC;:8o"
caracterizada
clados que esta.o sendo gerados e armazenados
pelo aumento
(CARVALHO;
no volume
FREITAS,
Esta expansao deve-se a falares de baixo custo no arrnazenarnento
as novas tecnologias
maior
velocidade
armazenamenlo
armazenados,
desenvolvidas,
na
des
recuperayao
dados
t~111 crescido
extrac;ao de conhecimento
existe a necessidade
com maior capacidade
e
dados.
clestes
crescimento
0
a necessidade
de desenvolvimento
descoberta
e extrayao
de
tarnando-os
explicitos e objetivando
a
facilidade
expressivo
de ferramentas
destes
implicito
e
no
dados
que possibilitem
Devido
a
nestas
a
esla realidade,
de novas metodos e algoritmos
conhecimento
0
de dados e
de armazenamento
Com
destas bases de informa~6es.
de
2001).
bases
de
para a
dados,
auxflio na tomada de decisao.
As empresas. cada vez mais, necessitam de uma correta interpretac;ao das
informa¢es
para auxilia-Ias
crescimento
FAYYAD.
do
neg6cio
cilado
por
(i) a identificaqao
dados
de qual
decis6rios
empresa
(2001).
base
(iii} a transforrnoceo
(Data
disponibilizac;ao
e a etapa
GURECK
da
0
e, conseqOentemente,
(GURECK.
processo
de
2001).
no
Segundo
descoberta
de
em base de dados constitui um conjunto de eta pas Que 'lao desde:
conhecimento
envolvidos,
nos processos
principal
Mining),
(v)
a
do conhecimento.
sera
e
0
antllise
utilizada,
(ii) a sele~o
prc-processamento,
do
conhecimento
A etapa que "realmente·
de Data Mining {mineraya.o de dado.s}.
dos atributos
(iv) a minera~a.o de
extraido,
extrai
0
e
(vi)
conhecimento
a
Segundo FAYYAD et ai., citado por CARVALHO
larefas usuais de Data Mining
cJassificayao e
o
0
agrupamento
(registro) urna dasse,
com base nos valores
a
(clustering).
e a tarefa
foeo des!e trabalho
urn exemplo
(2002b), algumas das
sao a descoberta de regras de associa~o,
de atributos
de cIassifica<;ao, cnde deseja·se
dentre urn conjunto de classes
daquele
exemplo.
atribuir a
pre-definidas,
Cabe ressaltar
que e5sa
urn banco poderia
classificar
tarefa tern verias aplicac;6es em diversas areas.
Em urna aplicac;:lo financeira,
por exemplo,
seus clientes em duas classes, ~credito ruim" au ~credito born", Em urna aplicayao
na area da medicina, um medico poderia classificar
duas classes:
importantes
alguns de seus pacientes
"tern" au Knao tern" urna certa doen<;a. Assim,
do mundo real podem ser tralados
como tarefas
em
varias problemas
de classificac;.ao.
Essa tarefa e discutida de forma mais detalhada na seC;;ao3.3.
No contexto
ser
expresso
enlao ..<a~o> ..
intuitivamente
da larefa de dassificac;;ao, 0 conhecimento
atraves
M.
Este
de
tipo
compreensivel
urn
de
de
representa<;ao
regras
tern
a
descoberto
vantagem
que podem construir
classificadores
implicito em urna base de dados, entre eles, algoritmos
de decisao, algoritmos geneticos, algoritmos imunol6gicos,
Este trabalho
tern como objetivo
construa urn dassificador
pode
~se..<condic;ao> ..
de
ser
para 0 usuario.
Existem varios algoritmos
conhecimento
conjunlo
principal
a partir do
de arvore
etc.
propor urn novo algoritmo
a partir da implementac;;ao computacional
que
de alguns dos
princlpais conceitos do Sistema Imunol6gico Artificial.
A proposta
urna das pesquisas
deste trabalho de gradua~o
desenvolvidas
constitui
pela Universidade
urn desdobramento
de
Tuiuti do Parana, que tem
como pesquisadora
pesquisa
responsavel
aponta algumas
a Prof".
dire~s
Or-.
Deborah Ribeiro Carvalho.
de pesquisas
futuras,
Esta
sendo
uma delas
realizados
no escopo
desenvolvida no presente trabalho.
Os resultados
obtidos a partir dos experirnentos
deste projeto poder:lo ser cornparados nao apenas com as resultados obtidos
pel a pesquisa, bem como com os resultados obtidas a partir de um outro projeto
de graduaC;ao que foi desenvolvido
algoritrnos geneticos.
em para lela a este, que se bas.eia em
2. KDD - KNOWLEDGE
ADRIAANS,
de atividades
DISCOVERY
FROM DATABASES
citado par GURECK (2001), conceitua KOD como um conjunto
contlnuas que compartilham a conhecimento descoberto a partir de
bases de dad as. Segundo
FAYYAD,
composto de seis etapas:
selee;ao dos dadas, limpeza ou pre-processamento,
transformayao,
Data
Mining,
citado par GURECK
interpreta~o
e
avalia~o
(2001),
0
dos
conjunto
relat6rios
e
e
consolidaytio do conhecimento e.tescoberto (Figura 1).
FIGURA 1 - 0 PROCESSO
KDQ E Sl)AS ETAPAS (FAYYAD, c:i1iH:lopar GURECK, 2t101)
2.1
ETAPAS DO KDD - KNOWLEDGE
2.1.1
5ele<;1lo de Dados
DISCOVERY
FROM DATABASES
Urna vez definido 0 dominic sabre a qual se pretende
de descoberta,
0 proximo passo
variiweis necessarias.
nem
sempre
e seiecionar
executar
a processo
e coletar 0 conjunto de dados ou as
A maiaria das ernpresas passui a base de dedas, pOrB:m
lodos as dados necessarios
estao dispon[veis
nestas
bases.
ConseqOentemente,
neste contexto
e exigido
seja, os dados que sao necessarios,
um trabalho de compatibilizac;.ao, ou
os que ja esta.o disponiveis,
de obten9ao dos dados que nao estao disponiveis
Quando se dispOe de uma quantidade
sao importantes,
tenta-se
e/ou incansistentes
substituir
- par valares
0
consistentes
tenta~se eliminar
fazem-se
campos
necessarias
com
desconsidera-Ios
2.1.2
ruido
a
as dadas
e,
de
ao dominio
ruido.
de tecnicas
acordo
- dados estranhos
em questao
au ate
caSa em que a quanti dade de dados e
que contem
utilizayao
(GURECK,
0
1999).
de dados, onde todos os exemplos
ruido ou perturba90es
mesmo gerar dad os manual mente. Para
grande,
(CARVALHO,
e a possibilidade
com
a
Em ambos
estatisticas
para
conveni~ncia,
os casas,
detectar
substitui-Ios
os
ou
2001).
Limpeza ou Pre-Processamenta
Oepois
estabelecer
de coletar
as estrategias
os dados,
pas so seguinte
0
para resolver
0
problema
e tratar
da aus~ncia
os rufdos
causas que levam a situayao de aus~ncia de dados sao a nao disponibilidade
dado ou a inexistencia
do mesmo.
Uma situac;ao de nao disponibilidade
quando nao ha divulga<;ao do dado, como, par exemplo,
uma pessoa fisica em fun<;ao da obrigatoriedade
A
inexist~ncia
necessaries
dos
dados
pode
dades sobre determinados
de organizayao
ocorre
exemplo,
produtos de empresas
1999).
quando
sao
que, no momenta
e gerayAo da base original, ainda n~o haviam sido criados.
Os dad os devem ser relevantes
consistentes
per
do
os dados da renda de
do sigilo (CARVALHO,
ocorrer,
e
dos dados. As
e livres de excessivas
para as necessidades
nulidades (CRUZ, 2000).
do LJ5uario, limpos,
Quando existe limitac;tio computacional
dados,
e
recomendado
selecionar
obter uma ideja do que pode ser esperado.
grandes empresas
perspectiva
relacianada
algumas amostras
a fim de se
Quase todas as bases de dados ern
sao ~poluidas~, e quando comeyam
de Data Mining.
ao temanho da base de
aleatoriamente,
jdejas quanta
a
a ser olhadas atraves da
consist~ncia
dos dados
mUdam
(CRUZ, 2000), em rela9ao a05 conceitos cU.lssicos de banco de dados.
2.1.3
Transformavao
Ap6s
0
au Enriquecimento
dos Dados
dado do banco de dados ter sido pre-processado
fazer uma analise sobre a necessidade
podem enriquecer a base (MARATH;
Segundo ADRIAANS,
de dados adicionais,
MAYER, 2001).
citado por GURECK
acesso a outras bases de dados adicionais
comerciais
e pode prover
em diversos
(2001).
esM disponivel
informa\1Ao de uma grande
incluindo dados demogrilficos,
(filtrada), deve-se
que eventual mente
variedade
tipos de seguros que as pessoas
outros. 0 estudo de uma situa~o
ande companhias
paises, 0
em bases de dados
de assuntos,
possuem,
entre
trocam dados para coordenar
suas operayOes de marketing tem side urn segmento em desenvolvimento.
A privacidade
e
urn aspecto
nesta area, esta se desenvolvendo
nao
e
permitida
importante
neste contexto.
rapidamente,
a venda de dados individuais
A jurisprud~ncja,
e na maiaria dos paises onde
sem a permissao
do individuo,
e
perrnitida a venda de informac;Oes de grupos de pessaas, mesma nao sendo alga
desejflVel
(2001).
do ponto de vista eticQ, segundo
ADRIAANS,
citado
por GURECK
Exemplificando~se atraves de suposic;C5es,as conversOes de dados podem
ser realizadas na entrada de um illgoritmo de Data Mining que receba as idades
dos clientes de ullla empresa. Entretanto, se a base de dados de estudo possui
somente as datas de nascimento dos clientes, faz~se necessaria a realizagAo de
uma transformayao
sobre esses dados, adequando~os
a
entrada do algoritmo,
efetuando urn calculo da idade a partir da data de nascimento
2.1.4
(GURECK,
2001).
Data Mining
Data Mining
objelivo
consiste em um conjunto de conceitos
de encontrar
uma
padrC>ese regularidades
descriC;ao, preferencialmente
em um determinado
e metodos
com 0
compreensfvel,
de
conjunto de dados (CARVALHO,
2002b).
Nesta
etapa
do processo
se define
a escolha
do algoritmo
ou dos
algoritmos de Data Mining, de acordo corn IJm ou mars metodo(s} adequado(s) ao
tratamento dos dados do problema que se esta resolvendo.
Relativamente
as
eta pas anteriores mencionadas de 2.1.1 a 2.1.3, 0 tempo utilizado por esta etapa
~ substancialmente menor.
Data Mining
e uma
das fases. do processo de descoberta de conhecimento,
para a qual tern side descritos varios metod os. Dentre as metod os, destacam~se:
tecnicas
estatisticas,
visualizayao.
decis~o,
descoberta
de
geneticos (CARVALHO,
regras
baseado
em casas,
neurais
aNoreS
de
e algoritmos
1999).
Nesta etapa. as algoritmos
capacidade
raciocinio
de associac:;ao, redes
de Data Mining,
de e)(trair 0 conhecimento,
se bem projetados,
mesmo sem ter conhecimento
tl!m a
total ou
parcial da queslao.
sislemas de apoio
2.1.5
Esta capacidade
a decisM
faz com que Data Mining agregue valor aos
(GURECK, 2001).
Inlerprela<;ao e Avalia\'llo
Nesta etapa deve-se
saber se 0 conhecimento
gerado
e
util, relevante
e
valida, pais se nao for, sera necessaria repelir todo au parte do processo de KDD.
Esla descricaa
KDD. No entanla,
pade sugerir que exista uma trajet6ria
isla geralmente
pode ser identificada
anteriores.
Mining,
e
n~a se verifica,
a necessidade
Por exemplo,
identificado
de retorno para qualqlJer uma das eta pas
se na etapa
de transformayao
que as dados na.o estAo tolalmente
verificada a necessidade
dos dados (GURECK,
pelo especialista
2.1.6
do Conhecimento
Nesta elapa de conhecimento,
devell1 ser analisados,
forem satisfat6rios,
informac;ao
de Data
au se for
interpretados
e
au mesmo de
desempenhada
Descoberto
as resLlltados dos algoritmos
e bem avaliados.
de Data Mining
Se estes resultados
empresa (GURECK, 2001).
qLle auxilie
nao
para efetuar uma melhor
e limpeza dos dados. Este novo resultado
util e desconhecida,
e
em questao.
deve-se retornar as fases anteriores
sele<;a,o, enriquecimento
limpeza
2001). Lembrar que esla larefa
da area de contlecirnento
Consolida~o
au mesmo
consislentes,
de um dado que nao havia sido previsto anteriarmente,
isso pode levar ao retorno para a fase de consistllncia.
sele\'llo
linear do processo
uma vez que em cada elapa
nos processes
deve gerar
decis6rios
de uma
A realiza~o
qualquer
n:io deve ser seqLiencial, pais em cada etapa
das atividades
devem ser avaliados
os resultados,
e caso seja necessaria,
uma das eta pas anteriore-s, para recupera~o
para uma nova consist~ncia au limpeza dos dados (GURECK,
Segundo FAYYAD et aI., citado por CARVALHO
desenvolvidas
em Data Mining t~rn como objetiva
descric;aa de dadas
valares
e/ou sistemas.
futuros de uma au mais variaveis
contempla
a que foi descoberto
retarnar
a
2001).
(2002b), as varias tarefas
essencial
A predi<;aa llsa
deve-se
de dados nao previstos,
a
atributas
predi~a
e/au a
para preyer
{a1ributas) de interesse.
as
A descrivaa
nas dados sob a ponto de vista da interpretac;aa
humana.
As eta pas do processo
KDD nao sao
possuimos
as dad os a serem
Repository,
disponiveis
utilizados.
0
foeo deste trabalho.
Estes
dados
visto que ja
sao oriundos
do UCI
em: <http://I,WIW.ics.uGi.edu/-mlearn/MLRepository.html>.
A unica etilpa abordada neste trabalho
suas tarefas, a tarefa de classificaytio.
e a do
Data Mining, onde utiliza-sa
Ulna
de
3. TAREFAS
Para
DE DATA MINING
trabalhar
com
Data Mining
e
preciso
conhecer
suas
tarefes,
a
utilizac;ao de cada uma del as e selecionar a que mel her ira se adequar ao objetivo
em queslao (MARA TH; MAYER. 2001).
Segundo ADRIAANS,
o objetivQ da descri~o,
algumas
das
descoberta
o
tarefas
FAYYAD el.1. e FU, cilado por CARVALHO
bem como 0 da previsao,
principais
de
Data
sao atendidos
Mining:
(2002b),
atraves
classificac;Ao,
de
clustering,
de regras de associac;ao, etc.
foco deste Irabalho
ea
tarefa de classificaC;ao.
Esla tarefa
e detalhada
na subsec;:ao 3.3.
3.1 CLUSTERING
A tarefa de clustering oonsiste na identificactao de um conjunto finita de grupos
ou
dusters, baseada nos atributos de objelos
e
cluster
basicamente
um conjunto
as
previamente
naD
de objetos
agrupados
OOjetos sao agrupados
dassiftcados.
Urn
em fun~o
de sua
de tal forma
que as
similaridade
ou proximidade.
similaridades
intradusters
(dentro de um mesmo cluster) sao maximizadas
similaridades
interclusters
(entre clusters diferentes)
sao rninirnizadas.
e as
A Figura 2
mostra urn exemplo do resultado de uma tarefa de dusten·ng, onde quatro clusters
foram identificados (CARVALHO,
2002b).
Urna vez definidos os clusters, os objetos sao identificados
correspondente,
e as caracteristicas
surnarizadas para formar a descri~o
definido
como uma classe.
comuns
dos objetos
com seu cluster
no cluster podem ser
do grupo, que podera subseqOentemente
Por exemplo,
urn conjunto
de pacientes
ser
pede ser
11
agrupado em varias grupos (clus-te,~), bas.e.ado nas similaridades dos seus sintomas,
e as sintoll1as comuns
descrever
a
padentes de cada cluster podem ser usados para
aos
qual chisler urn novo paciente pertencer~. Assim, urn dado paciente
seria atribuido aD cluster cujos pacientes tt.!!m sintomas 0 mais similar posslvel com
as sintornas
resultado
e
daquele
dado paciente.
a identifica~o
processamento
Oessa forma,
de novas
dasses,
a tarefa de clustering,
pode
ser
realizada
como
cujo
pre-
it realizac;ao da tarefa de classificayao, segundo KUBAT et aI., citada
por CARVALHO
(2002b).
A,
A,
FIGURA 2- EXEMPLO DE CLUSTERING (CARVAlHO.
3.2
aD
DESCOBERTAS
DE REGRAS DE ASSOCIAi;l\O
Para exemplificar
as regras de associa~o,
supermercado
de um ctiente,
2OO2b)
imagine um consumidor
que vai
e compra varias produ1os. Uma compra indica as prefer~ncias
porem dillersas
consumidores
compras
as
outras
informa95es
mesmos,
e sendo
assim,
consumidor
compra produtos diferentes e em momentos
diferentes.
As regras de
associa~o
usam as informayoes
0
sao
diversas
Os
lentar mostrar quem sao
nao
possuem
relevantes.
sobre 0 que os consumidores
compraram
cada
para
porque oles com pram (BERRY; LIN OFF, 1997, p. 124).
12
Neste sentido, cada registro de urna venda no supermercado
transa<;ao efetuacta pelo consumidor,
falso, dependendo
se
0
consumidor
c6digo de barras (GURECK,
o algoritmo
comprou
(au na.o) aquele produto
e freqOentemente
transa9ao. Esse tipo de dado
corresponde
a urna
cnde cada item tern valor verdadeiro
ou
naquela
coletado atraves da tecnologia
de
2001).
para descoberla
de regras de associB930
idenlifica
afinidades
entre itens de urn subconjunto de dados. Essas afinidades
sao expressas na
forma de regras, por exemplo: 72% de lodes as registros que
contem as itens A,
Bee
tambem contem 0 e E. A porcentagem
representa
0
tend~ncias
algoritmo
dentro
fator de confian98
fracas,
voltado
mantendo
a
apenas
as regras
analise de mercado,
de urn grande
numero
de ocorr~ncia
da regra, e costuma
(72 neste exemplo),
ser usado
mais
fortes.
para eliminar
Trata-se
com a objetivo de encontrar
de registros.
Essas tend~ncjas
de urn
tendencias
pod em ajudar a
entender e explorar pad roes de compra naturais, e no exemplo citado de cornpras
em
urn
superrnercado,
propagandas,
3.3
podem
ser
CLASSIFICAI;AO
A classificayao
pertencente
a uma
para
e
prateleiras
(FIGUEIRA,
a tarefa de Data Mining estudada
determinada
0 principal objetivo
ou
1998).
cia sse
e descobrir
e a divisao
ao longo do tempo.
um item de dado (exemplo ou registro) como
dentre
varias
classes
previamenie
algum tipo de relayao entre os atributos
e as classes, conforme FREITAS, citado por CARVALHO
conceito dessa tarefa
modificar
especificas
DE DADOS
Essa larefa consiste em classificar
definidas.
usadas
e induzir atividades promocionais
(2002b). Um importante
dos dados em bases de treinamento
e de teste.
13
Inicialmente,
um conjunto de dados de treinamento
e um rl1odelo de classificayao
e
construido
modele construido
e
de teste, as quais
sao independentes
que
0
utilizado para classificar
e disponibilizado
QUtros dados, denominados
dos dados de treinamento.
modelo construido a partir dos dado5 de treinamento
born mode 1o, do ponto de vista de precisao
corretamente
uma alta porcentagelll
e analisado,
baseado nestes dados. Entao 0
preditiva,
e
Cabe ressaltar
considerado um
se 0 modele
dos exemplos (registros)
classificar
dos dodos de teste.
Em Qutres palavras, a modele deve representar conhecimento
que passa ser
generalizado para dados de teste e que nao tenham side utilizados
treinamento
(CARVALHO,
e
conhecimento
geralmente
do conhecimento
representado
na
satisfazem
preYista pel. regra" (CARVALHO,
de
regras
"se as valores
as condir;:Oes da regra entao a exemplo
petience
a
compreensibilidade
2002b).
Os dais criterias mais usadas sao precisao
do conhecimento
e
A precis2lo preditiva
de teste classificados
teste (CARVALHO,
Segundo
dos
classe
Existem varios criterios para avaliar a qualidade das regras descobetias
tarefa de classifica92lo.
0
descoberto,
forma
e:
~se..<condir;:oes:::... entao ..<cia sse> ..-", cuja interpretayao
atnbutos
durante
2002b).
A fim de contribuir para a compreensibilidade
esse
dadas
descoberto (CARVALHO,
normalmente
corretamente,
medida como
0
preditiva
na
e a
2002b).
numero de exemplos
dividido pela numero total de exemplos
de
2002b).
HAND, citado por CARVALHO
fannas rnais sofisticadas
descrita anterionnente
(2002b),
de se medir a precisao preditiva,
e, em
cabe ressaltar
que M
mas a forma simples
sua essencia, a forma mais usada na pratica.
14
A compreensibilidade,
geralmente,
e medida
em funyao
regras e do numero
de condic;:Oes por regra. Quanta
menos cornpreensivel
e a conjunto
estes
de regras ern questao (CARVALHO.
Essa forma de representay80
em virtude de ser intuitivamente
do numero
maiores
e
de conhecimento
compreensl\lel
para
0
adotada
de
numeros,
2002b).
neste trabalho,
usuario.
o algoritrno proposto cum pre a larefa de classificac;:ao,
e par iSSQ e utilizado
neste trabalho.
3.4
TECNICAS DE CLASSIFICAI;)\O
Denlre as hknicas
as arvores
trabalho,
posslveis que tratam da questao de classifica<;ao estao:
de decisao,
utiliza-se
0
algoritmos
sistema
geneticos
imunol6gico
e sistemas
artificial,
imunol6gicos.
conforme
Neste
exposto
na
introdu9Ao.
3.4.1
Arvores de Decisao
As arvores
de decis;'!.io sao meios de representar
os resultados
Mining na forma de arvores. Dado urn grupo de dados com numerosas
Hnhas, uma ferramenta
de arvore de decisao pede ao usuario para escolher uma
das colunas como objeto de saida (atributo meta), e entao mostra
importante
de Data
colunas e
tat~r correlacionado
0
(mica e mais
com aquele objeto de saida como primeiro ramo
(no) da arvore de decisao. Os outros fatores sao 5ubseqOentemente
como nos doCs) no{s) anterior(es).
Desta maneira
porqu~ do fator escolhido, e vai permitir que
0
0 usuario
classificados
pode entender
0
usuario explore a arvore de acordo
15
com a sua vontade, do mesmo modo como ele podera. encontrar grupos alv05. Os
usuarios
podem tambem
arvore, movendo-os
(MARATH;
selecionar
em qualquer
n6 da
MAYER, 2001).
Conforme QUINLAN
simples
as dados fundamentais
para uma planilha au outra ferrall1enta para posterior analise
(1993), uma "rvore
de um ciassificador
e
de decisao
utHizada par diversos
sistemas
uma representac;ao
de aprendizado
de
a partir de urn conjunto de exemplos
de
n1aquina, como par exempto, 0 C4.5.
e induzida
Urna arvore de decisao
treinamento
onde as classes
sao previamente conhecidas. A estrutura da arvore
organizada da seguinle forma (CARVALHO,
e
2002b):
cada 110interna (nao-folha) e rotulado com
0
nome de urn dos atributos
previsores;
os ramos (au arestas) saindo de urn n6 interno
sao rotulados
com
valores do atributo naquele n6:
e
cada folha
rotulada com uma cia sse, a qual
e
a classe prevista para
exemplos que perten<;am aquele n6 folha.
o
processo
de
classificac;ao
de
um
exemplo
ocorre
exemplo percorrer a arvore, a partir do n6 raiz, proeurando
fazendo
aquele
avaliar os arcos que
unem as nos, de acordo com as eondic;Oes que estes rnesrnos areas representam.
Ao atingir urn no folha, a classe que rotula aquele n6 folha
exemplo (CARVALHO,
2002b).
e
atribufda
aquele
16
3.4.2
Algoritmos
Geneticos
Na natureza, 0 processo de sele<;ao natural controla a evoluyao
vivos. Os organismos
suficiente para
S8
mais adaptados
reproduzirem,
ao seu ambiente
enquanto organismos
tendem
menes adaptados sao
mais propensos a morrer antes de sua reprodUl;lIo (CARVALHO,
Segundo
geneticos
FALKENAUER,
(AGs) sao algoritmos
natural e na genetiea.
candidata
para
normalmente
conjunto
individuos
de busca baseados
2002b).
(2002b),
urn determinado
representadas
e
problema.
par individuos.
criado
usanda
gera<;ao anterior, conforme
As
da
selec;ao
da melhor
soluc;ao
solu<;6es candidatas
A cada
nova
segmentos
avaliado
os algoritmos
no mecanismo
Os AGs se baseiam na sobreviv~ncia
de individuos
da
citado por CARVALHO
de seres
a viver tempo
gerayao
(partes)
urn novo
dos
por uma funyao
sao
melhores
de fitness
(funo;ao de avaliao;aolfuno;ao objetivo).
Um AG difere dos algoritmos
seguintes aspectos (GOLDBERG,
de buscas
tradicionais
principalmente
nos
1989):
AGs realizam uma busca usando uma popula(fao de solu(fao, e nao
uma unica solugao;
AGs
usam
deterministioos;
operadores
probabilisticos
AGs usam diretamente
a informa~o
nao
operadores
de uma funcao objetivo, e nao
dependem de derivadas ou conhecimento
A primeira
e
e
e a segunda
robustez dos AGs, ajudando-os
caracteristica
a escaparem
auxiliar sobre 0 problema.
mencionadas
contribuem
para a
de pontos de olimo locais, a tim de
alcanc;arem pontos de otimos globais. A lerceira
caracteristica
contribui
para a
17
generalidade
problemas
de AGs
que
de otimizayao,
pod em
busca
ser aplicados
em
e aprendizagem
urn largo
de maquina
espectro
de
(CARVALHO,
2002b).
Os principais mecanismos
pais envolvem
de urn AG convencional
apenas trocas parciais entre individuos
sao faceis de entender,
e pequenas
altera90es
de
elementos dos individuos (CARVALHO. 2002b).
Conforme
caracteristicas
BERSON.
citado
por
CARVALHO
(2002b).
usuais em sistemas que utilizam algoritmos
geneticos
algumas
sao as
seguintes:
(i)
Definir
0
problema
a ser resolvido
candidata em urn individuo artificial, e especificar
- codificar
uma solu~o
urna func;ao de avaliac;ao
(fltne ••):
(ii)
Inicializar
a
populacyao
aleatorios aos individuos da popula<;ao
-
lipicamente
atribuindo
valores
inicial;
(iii)
Permitir a selec;ao dos mais aptos
(iv)
Permitir
e extin<;ao dos menDS
aptos;
procedimentos
solu¢es
que uma nova gerac;.ao seja formada
(ou operadores)
(individuos) da gera~o
(v)
Parar
quando
de selec;ao, cruzamento
aplicando
e mutayao
os
das
anterior;
algum(ns)
do(s)
criterio(s)
mencionados
a
seguir forem atingidos:
-
A soluc;ao e suficientemenle
apropriada
para
° problema
em
questao;
- 0 sistema atingiu um numero de gerar;5es pre-determinado;
- 0 sistema nao consegue rnais evoluir (estagna'1ao);
18
-
Quando a valor media da funyao de avaliac;ao esta proximo
ao ll1elhor valor da funya.o de avaliac;:ao de urn individuo da populilr;ao;
-
Sen:io, retornar
aD
basicas:
cruzamenta
e muta~o
item (iii}.
e cor1stituido
Um algoritmo genetico simples
(GOLDBERG,
de dais operadores geneticos
1989). A seguir. serao descritas
algumas versOes desles operadores.
3.4.2.1
Cruzamento
Segundo
cruzamento
seus
BACK,
citado
por
permite a troca do material
indivfduos.
Urn cruze menlo
Primeiro
paSSDS.
{crossover)
individuos
sao
escolhidos
de
genes).
PAWLOWSKI
cruzamento
Dois
novos
11-1,
individuQs,
onde
um individua
descritos nesta sLlbse<;ao, assume-se
"filhos~, sao gerados
inclusive,
entre 1 e
que comp6em
opera~o
cham ados
11
(nos
e
0 nllmera
denominados
em ponto simples
(2000). Est.
au cruzamento
metoda
p e
operadores
e
de
de
tt§m 0
indivfduos
pels troca de todos os val ores entre a posi~o
(1995) e BOOKER
entre
uma posiyao
que ambos as individuos
individuos,
de
na populay:io
dais
como urn numero aleatorio
a
pode ser feito em dais
Segundo,
caracteristicas)
numero
disponfvei
simples
aleatoriarnente
selecionada
mesmo
(2002b).
para cruzarem.
genes
cruzamento
genetico
(crossover)
·pais" au antecessores,
(ou
CARVALHO
p+1 e n
denominado
em um ponto (ver Figura 3.(a})
(CARVALHO,2002b).
Outro tipa de cruzamento,
(2002b),
e
0 cruzamento
segundo
uniforme,
SYSWERDA,
onde
todos
as
citado par CARVALHO
genes
tem
a
mesma
19
probabilidade de serem trocados,
independentemente
genoma (ver Figura 3.(1))) (CARVALHO,
de suas posic;6es no
2002b).
Em geral existe uma ta)(a de cruzamento que centrola a freqU~ncia com
que as cruzamentos
3.4.2.2
ocorrerem (CARVALHO. 2002b).
Mutao;:;o
Conforme
BACK, citado par CARVALHO
(2002b), a operador
nlutac;ao introduz novo material genetico de forma aleat6ria
AGs existem varios modos de implementar
genetico de
na populayao.
Em
mutat;ao. Per exemplo, se
0 operador
o individllo consiste de genes binarios, a mutar;ao consiste em inverter 0 valor de
um bit (CARVALHO,
A muta~o
2002b).
pede introduzir material genetico que nao esta presente em
nenhum
individuo da populayao:
material
existente
entre
dais
aD contrario do cruzamento,
individuos.
Assim,
a
que apenas
l11utac;ao
aumentar a diversidade gen_tica da populaO;:;o (CARVALHO,
contribui
taxa de cruremento
Normalmente.
(CARVALHO,
a taxa de muta~
e
mfi\[][1
Llta1~~
FIGURA 3 TlPOS DE CRUZAME~nO(CARVALHO.
lClJ2b}
corn que
bern menor que a
2oo2b).
ltbj
para
2002b).
Em geral. e)(iste uma taxa de muta9ao que controla a freqOencia
as mutaQ6es ocorrerem.
treca
20
Os AGs tambem podem gerar as regras de conjuntos
seguem a induc;ao de protocolos
de dadas, mas nao
de regras de explosao orientada.
Ao contrario,
eles contarn com a ideia de "muta9aO~ para fazer trocas nos padr6es ale que uma
forma apropriada de modelo seja obtida via educa<;ao seletiva (POLITO,
Os AGs nada conhecem
sendo que a (mica informayao
a respeito
disponlvel
do problema
que estao
~ uma avalia<;ao de cada indiv;duo da
populayao. Esta infom1ac;.ao inf1uencia a seley:io dos cromassomos,
aqueles corn melhores avaJia¢es
tem maiores possibilidades
do que aquetes com piores avaliay6es.
conceber
condi¢es
natureza (GURECK,
3.4.3
de se reproduzirem
Com a utilizayao
nas quais a otimiza~o
de modo que
de AGs.
ocorre, inspirada
pode-se
ao que ocorre na
2001).
Sistema Irnunol6gico e Sistema Imunol6gico Artificial
o
sistema iOlunol6gico gera interesse pela pesquisa
processar
inforOla~o.
distribuida,
e possui a propriedade
DASGUPTA,
Rowe,
1997).
resolvendo,
0 sistema
armazenar
citado
processos
complexes
de forma
paralela,
de interagir localmente.
por CARVALHO
imunol6gico
as experi~ncia$
componentes
age
como
passadas,
(2002a),
menciona
urn ·segundo
fortalecer
que,
cerebro"
as interayees
segundo
pOis pode
de suas celulas
e gerar uma nova resposta para novos padrOes de antigenos.
o Sistema
hipermuta~o
Ele executa
dado 0 seu poder de
Imunol6gico
Artificial
(SIA)
e expansao clonal (CARVALHO;
o conceite de hipennutac;ao
e
constituldo
de dois operadores:
FREITAS, 2001).
consiste no fato de que 0 me sma anticorpo
pede gerar 50 clones, e que cada gene do clone pede ser mutado.
Na proxima
21
gera~o,
cada
urn destes
sucessivamente.
50 clones
Isto signifiea
podera gerar Qutros 50 clones,
que cada
gene
muta9llo diversas vezes entre a primeira
gerado a partir de clonagem,
samente se,
0
0
mecanisme
processo de hipermuta<;tlo,
anticorpo
e a ultima.
a popula~o
de avalia~o,
se, e
FREITAS, 2001).
de expansao
clonal pode prover a reguta<;ao do
a qual e dependente
a processo
soffer
Urn anticorpo,
de anticorpos
da afinidade
com baixo valor de avalia<;ao deve ser eliminado.
alto valor
e assim
pode
funr;ao de avaliaC;Bo for maior au igual ao
threshold de expansao clonal (CARVALHO;
Note que
itera~o
s6 e adicionado
valor da sua respectiva
de urn anticorpo
de seleC;Bo clonal
e
do anticorpo.
Em anticorpos
inidado
Urn
com
(CASTRO;
ZUBEN, 2000a).
o
valor de match
Algoritmo
match
e
Imunol6gico
e
importante
para 0 processo
(SIA), citado em CARVALHO
de expans30
obtido atraves da func;ao de avaliac;ao. Urn anticorpo
56
e
este anticorpo tern seu valor de avalia<;ao maior que pre-determinado
cada itera~o
do algoritmo de seleffao clonal, se urn anticorpo
da ex pan sao clonal, 0 sistema
submetidos
gera clones deste anticorpo.
ao processo de hipermuta<;~o (CARVALHO;
Aplica/fOes de sistemas imunol6gicos
o
sistema imunol6gico
complexidade
e pouco
e objeto
entendimento
0
valor de
cion ado se
threshold. A
obtem
° threshold
Estes
clones s~o
FREITAS,
numero de threshold quanto 0 numero de clones sao estabelecldos
3.4.3.1
clonal. No
e FREITAS (2001),
2001). Tanto
0
previamente.
na computac;ao
de grande interesse mesmo diante de sua
de
seu
mecanismo.
Entretanto.
suas
22
caracteristicas
gerais
prov~m um excelerlte
Que tanto operam a nivellocal
Trata-se
ende
de urn sistema evolutivo
nao se conhece
5uficientemente
exemplo,
principal
0
por complete
biol6gico
e
caracteristica
corpa e classifica-Ias
adaptativo
0 caminho
r1ada rnais
reconhecer
todas
soluc;ao de problemas
da solu~ao.
a diversos
e
para processes
2002a).
a
que se aplica
flexive1 para se adaptar
sistema
modele
quanto global (CARVALHO,
tipos
~ urn metoda
de problemas.
do que urn classificador,
as celulas
como sendo proprias au externas.
Por
pois sua
(au molekulas)
em seu
As celulas externas
sao
par sua vez identificadas
de forma a estimular a um au a outro sistema defensivo.
Desta forma, 0 sistema
imunol6gico
aprende,
atraves
da elloluyao,
entre antlgenos e celulas do proprio organismo (CARVALHO.
Segundo SOMPAYRAC,
citado por CARVALHO
a distinguir
200221).
(2002a), a arquitetura
sistema imune e corn posta de tr~s niveis. A primeira forma de preven~o
elementos
edernos
aos organismos
e
a barreira natural, a pele. A segunda
sistema imune inato, que consiste primariarnente
dos animais
vertebrados
sabrevivem
apenas com estes dais niveis de proteyaa.
varias tipos de celulas e moleculils:
adaptativo
adaptativamente
porque
e adquirida
A resposta
0
responsavel
primaria
quando
pela primeira vez e reage contra ele.
aprende
sobre
os antigenos
e
a qual
irnunidade
pas sui dais tipos de respostas:
ocorre
antigeno
resposta secundaria
Poram, os
e envolvendo
adaptativo,
pela
0
que
durante a tempo de vida do organismo.
sistema imune adaptativo
secundaria.
0 sistema imunol6gico
e
e
Cerca de 99%
possuem urn terceiro nivel de defesa, mais sofisticado
denominado
o
de macr6fagos.
do
contra
desenvolvendo
0
sistema
a primaria e a
imune
en contra
0
0 sistema imune gradualmente
anlicorpos
ocorre quando 0 mesmo antfgeno
cada
vez melhores.
e encontrado
A
novamente.
23
Eta e caracterizada
pela produ~o
de anticorpos
de forma rapida e abundante,
resullado da ativactao de anticorpos da resposla primaria (CARVALHO;
FREITAS,
2001).
Existem
baseadas
varias
no sistema
experi~ncias
de
desenvolvimento
imune. para tratar de problemas
de
metodologias,
complexos
(CARVALHO,
2002a). Alguns exemplos:
• ImunizB9aO contra fraudes
Conforme
organiza90es
HUNT
financeiras
et
aI.,
est:io
cHado
utilizando
por
CARVALHO
hknicas
(2oo2a),
de imuniza!fao
prevenir contra fraudes em processos de hipotecas e emprestimos.
mais critica
e extrair
conhecimento
para
A tarefa
a partir dos dados, au seja:
- identificar a fraude em novas aplica90es;
- explicar a fraude existente; e
visualization)
- possibilitar
uma visualizac;a.o
para auxiliar
0
especialista
169ica dos dad as (logical data
humane na descoberta
de padrOes
da fraude.
As potencialidades
do AIS (Arlificiallmmune
Systems) para identifica~o
de
fraudes sao:
que
0
usuario
explicitar os pad rOes aprendidos
examine
estes
no dados. Assim, permite
pad rOes a fim
de
tomar
as
atitudes
necessarias;
- gerar detectores
de fraudes.
novas aplica90es sejam automaticamente
Oesta forma,
processadas;
permitem
que
24
expJicitos
incorporar
denlro
do
domInies
padrao
de
de
conhecimento
reconhecimento
e
preexistentes
processos
de
aprendizado;
ser capaz de generalizar
as padraes que sejam similares
sem perde-Ios.
Detecyao de virus de computadores
Da mesma forma que
viral
e
no organismo,
detectar
a
presenc;a
0
sistema
passivel
de virus
desenvolver
apresentado
nao
(SOMAYAJI
e !lanseJf
e
Os virus,
capaz
de
em geral,
setores de boot e arquiyos em geral. A
problema
de prote~o
detecrraa self-nonself,
interpretado
e
semelhante
ao
onde self sao dados
como alguma alteray:io do self
et aI., 1997).
Processo de prote~o
o
0
nos organismos.
corrompidos
uma apljca~ao
em computadores.
infect8m programas de computador,
partir deste ponto de vista
imune pode prever uma infec<;<3o
atjva sabre um unico host
e constituido
sistema il11uneadaptativo
de celulas que monitoram
e interagem com outras celulas. Se cada processo ativo no computador for
como
executando
multiplos processos como um organismo
conjunto
uma
e
visualizado
celula,
de computadores
Tradicionalmente,
como
mecanismos
de
posslvel
imaginar
uma populayao
seguran<;a,
um
computador
multicelular,
e urn
de tais organismos.
tais
COmo senhas
e
25
permissOes a arquivos podem ser considerados
como barreiras
naturals e
o sistema imune inato, urna analogia ao sistema imune biol6gico.
Para
criar
implementar
estarao
a
0 conceito
habilitados
funcionando
de
sistema
de linf6citos,
a questionar
normalmente.
e
biol6gico,
nivel
assumido
imune
as quais com
Quiros
auxilio do Kernel,
processos,
Da mesma forma
preciso
adaptativD,
se
estao
esla ocorrendo
que se urn processo
au
que no sistema
nao
imune
de forma
anormal,
ele pode estar sendo objeto de urn alaque
momento
pode ser gerada urna res posta imune de forma a torna-Io lento,
suspende-Io,
aborta-Io
aleatoriamente,
podendo
gerar
au
reinicia-Io.
conjuntos
ser substituido
Cada
de detectores,
viral. A partir deste
"linf6cito·
devera,
sobrevida
limitada,
com
par outro tipo de Mlinf6cito~ (SOMAYAJI
et aI.,
1997).
Protec;ao a urna rede de cornputadores
e
Urna outra abordagem
irnaginar que cada computador
orgao em urn animal. Cada processo
celula, como
confiaveis.
seguranc;a
urn anticorpo
de urna rede de cornputadores
baseado
imune adaptativo
, PJlra
neCworh.
maier.,
e cornposto
Este modelo de sistema imune
em
servidor,
seguranC;8 de rede, tais como
oomputer
poderia ser considerado
pede ser implementado
in!onn"90u
IEEE Communiosliom
cornbinado
Kerberos
coruutLllr
B.C. Neuman
32 (~): 3J-.lJ,
M.l!}3~n •.
lind
1
de
mecanismos
de
0 nivel do sistema
par urn linfocito
T. Tso.
S.pllHTlOqr
Kerberos:
1 GOot.
rnutuarnente
de mecanisrnos
com
e firewall.
como urn
como urna
An
assistido
lIurhonlic1lioo
pelo
S1Qrvice lor
26
Kamel,
corn uma caracteristica
computadores,
seleciona
tornar,do-os
e propaga
adicional
de poderem
os linf6citos,
Segundo KIM, citado por CARVALHO
negativa, desempenhada
um servidor centralizado
conforme
necessaria,
coordenando
circulando
entre
as
de computadores
cada um com a responsabilidade
pesquisar urn padr~o especifico de anormalidade
de deteclftio
migrar
agentes m6veis. 0 conjunto
(SOMAYAJI
de
et aI., 1997).
(2002a), dada a caracteristiea
pelos linf6citos.
as respostas.
e replicando
nao
e necessario
ter
pois as linf6citos agem
a 5i proprios
em busca de
problemas em Qutros servidores.
Existe um grande numero de rnetodologias,
voltadas
Sistemas
a resolver
problemas.
Imunol6gicos
Computa«;ao Imullologica,
o
ocorreu
primeiro
Estes metodos
Artificiais,
recebem
Sistemas
entre outros (CARVALHO.
congresso
internacional
em 1996, onde se concluiu
atenc;ao dos pesquisadores
como
inspiradas
sistemas biol6gicos, segundo DASGUPTA,
distintas
Baseados
imune,
designa90es:
na
Imunologia,
2002a).
em Sistemas
que esta firea,
outras
no sistema
abordagens
Imunol6gicos
em breve
tambem
citado por CARVALHO
Artificiais
recebera
baseadas
[2002a).
tanta
em
4. METODOLOGIA
4.1
DE DESENVOLVIMENTO
DEFINI9AO
DA MODELAGEM
A metodologia
adotada
ulilizada em CARVALHO
para deixar
0
a
4.1.1
mas
metodologia
a abordagem
for relativo
DO SIA
para a desenvolvimento
e FREITAS
texlo autocontido,
a seguir se refere
DO PROTOTIPO
Imunol6gioo
SIA e a mesma
as ponlos comuns
sao refon;ados as pontcs diferentes. 0 texlo
citada. No entanto,
e
de pequeno disjunto, que nao
Algoritmo
deste
(2001). SerAo repelidos
para Descoberta
desconsiderado
e foco
tudo
0
que
deste trabalho.
de Regras
para Pequenos
Disjuntos
A arquitetura
do sistema
imune
natural
e composta
de
tres niveis de
defesa: pele e mucosa, sistema imune inato e resposta imune adaptativa
(SOMAYAJI
el aI., 1997).
No algoritmo
disjuntos
imunol6gico
a tarefa desempenhada
para descoberta
pelo sistema
de
imune
regras
inato
e
para
pequenos
executada
pela
arvore de decisao. 0 algoritmo imunol6gico
incorpora algumas das caracteristicas
da resposta imune adaptativa: a diversidade
- a qual melhora a robustez, tanto ao
nivel de popula9aO como ao nivel de anticorpo;
aprender a reconhecer
destes antigenos
para facilitar futuras respostas
Neste SIA, os antigenos
(CARVALHO;
e a adaptabilidade
e a responder a novos antigenos,
sao representados
FREITAS, 2001).
- ele pede
e a reter uma mem6ria
(HOFMEYR;
por exemplos
FORREST,
do pequeno
1999).
disjunto
26
que
o
reconhecimento
sao
representados
por
regras
·se .<>..
adaplativD passui dois tipos de respostas:
primaria ocorre quando
0
na popular;ao
e
vez
melhores
caracterizada
resultado
esla fase
criado e estes antioorpos
cobrir
quando
peta
as
e
antigeno
0
equivalente
do
pequeno
e
ant/gena
pela primeira vez e
da resposta
neste algoritmo.
anticorpos
disjunto.
encontrado
mais
dos ell:emplos de teste poderia ser comparada
rapida
prirmlria.
(regras),
previamente
descobertos
anticorpo.
prirneiro passo no projeto de
lim
No caso do SIA, cada anticorpo
Este estagio
resposta
(durante
Ela
e
nao tern
secundaria.
Embora,
0 sistema usa
a fase de treinamento),
FREITAS, 2001).
SIA, ~ decidir 0 que representa
representa
se) e de urn conseqOente de regra (parte entao).
de regra que maximizem
resposta
e abundanternente,
de regra (parte
0 objetivo do SIA
a precisao preditiva
um
uma regra de pequeno
disjunto. A estrutura deste anticorpo consiste de um antecedente
condi90es
cada
De certa forma, a classificayao
a
para classificac;ao de novas exemplos (CARVALHO;
o
A
nOl/amente.
neste momento nao exista uma produyao abundante de anticorpos,
anticorpos
imune
A resposta
lentam cobrir as antigen os. 0 sistema
de anticorpos
de antioorpos
sistema
simulada quando urn novo anticorpo
exemples
0 mesma
produyao
da ativay:lo
uma representaf,(iio
0
a prima ria e a secundaria.
aprende sabre as anUgenos desenvolvendo
para
secunda ria ocorre
entaO ..<>.,M,
sistema imune encontra
reage contra ele. No algoritmo,
imune graduatmente
sao executados par anticorpos
e a resposta ao antlgeno
e desenvolver
da regrat avaliada
pel a
funt;ao de avalia930 - descrita a seguir. 0 conseqQente da regra (parte enta.o), a
qual especifica
a classe predi1a, nao
fixe em cada eJ(ecu~o
e
representada
no anticorpo.
do SIA, desta forma todos os anticorpos
Esta parte
e
t~rn 0 mesmo
29
conseqOente
durante toda uma determinada
(CARVALHO;
execuc;ao
FREITAS.
2001).
Cada execUC;ao do algoritmo descobre uma (mica re9ra (a melhor da ultima
iterayao) prevendo uma determinada
determinado
cobrir
periencentes a urn
cia sse para os exemplos
pequeno disjunto. Dado que precisa·se
descobrir as regras para
lodos as exemplos de varias classes em varios
pequenos
disjunlos,
0
algoritmo precisa ser executado varias vezes para uma dada base de dad os. Mais
precisamente,
0
algoritmo
e
pequenos disjuntos e ceo
executado
pequeno disjunto, a k-esima execuyao
predizendo
a k-esima
d ••c vezes,
classe.
do SIA,
Pequenos
pequeno ntlmero de exemplos (CARVALHO;
Nas pr6ximas
subse¢es
k
sao descritas
irnunol6gico
de
uma regra
sao regras que oobrem
urn
de
as representa~6es
a
de seleyao clonal, utilizados no
regras
para
pequenos
disjuntos
FREITAS, 2001).
Relembrando
4.1.2
0 numero
Para urn dado
descobre
C,
em detalhes
algoritmo
descoberta
e
FREITAS, 2001).
a Funyao de Avalia~ao e a mecanismo
para
= 1, ... ,
disjuntos
Anticorpo,
(CARVALHO;
ende d
numero de classes a serem preditas.
que neste trabalho nao trataremos as pequenos disjuntos.
Representa~o
Para representaytlo
a mesma
metodologia
anticorpo
representa
do Anticorpo
do anticorpo na abordagern
adotada em CARVALHO
0 anlecedente
conjunt;;Ao de condic;Oes compondo
cada condi9C1o
e urn par atributo-valor.
de SIA adotada,
e FREITAS
(2001),
da regra. Cada anlicorpo
urn dado antecedente
utiliza-se
onde cada
represenla
uma
da regra, sendo que
o
antecedente
da regra contem urn numero variavel
que nao se sabe a priori quantas condiyaes
regra
de
boa
especificar
nao
qualidade.
sO
0
o
numero
on de m e
para
a implementaQ~o
numero
minimo.
mas
tambem
da regra (CARVALHO;
maximo
de condi96es
numero de atributos
maximo
previsores
longas,
0
que contra ria a inten~o
uma
aumentar
estrutura
tempo
0
longa
representar
de processamento
maximo
e rnais
comptexo
de
de ser
de condic;Ges poderia
(i) conduzir a descoberta
de descoberta
para
0 numero
ser m,
na base de dados. Entretanto,
valor de m pode acarretar duas desvantagens:
exigir
~ necessario
FREITAS, 2001).
na regra
esta numero
dado
para compor uma
pratica,
Em principio,
0
de condi90es,
necessaries
Na
condi<;6es do antecedente
determinado.
se~o
de regras compreenslveis,
os anticorpos,
do algoritmo
0 que
(CARVALHO;
este
de regras
e (il)
tende
a
FREITAS,
2001).
Na abordagem
representar
de SIA e utilizada
urn antecedente
para cada execuc;ao do SIA descobre
dados (CARVALHO:
Cada gene representa
atributo; Vij e
de tamanho
variavel.
uma regra associada
fixe para
Relembrando
a um dado grupo de
uma condicao de regra (Figura 4) na forma Ai Opi
i identifica a condi~o
0 j-esimo
da regra,
valor do dominic de Ai; e Op eo
i = 1,... , n; Ai e
0
i-esimo
0
operador 16gico/relacional
ao atributo Ai - Figura 4. A variavel Bi representa
urn bit a1lvo, 0 qual
pode assumir valor 1 au 0 para indicar se a i·~sima condic;ao esta presente
nao no antecedente
1 A,
Op,(v,.J
que
FREITAS, 2001).
Vij, onde 0 subscrito
compativel
uma estrutura
de regra de tamanho
da regra (CARVALHO:
•B,
I·..
ou
FREITAS, 2001).
1 Ai °Pi(V!l
FIGURA 4: ESTRUTURA DO ANTICORPO(ANTECEOENTE
•B,
1···1
A, Op,,(V,.j
•B"
1
DA REGRA) (CARVALHO; FREITAS. 1001)
31
4.1.3
Funy:io de AvaJiac;ao
Sera assumido
sendo rninerada.
C"-")
negativa
(CARVALHO;
que sxistirao
Classe positiva
qualquer
outra
duas classes
("+") a classe
classe
na base de dados
predita
a
distinta
que esta
pela re9ra, e a Classe
classe
predita
pela
regra
FREITAS. 2001).
Para avaliar a quaJidade de urn anticorpo, nasso SIA usara a fun9aO:
f
= (TP / (TP + FN)} •(TN I (FP + TN)}. onde:
TP (TIIN.!Poiitive)
FP (Hi'.
= n(U1l2ro d<::lwum;>lOJ
~+"que .aooorllMmer;l,&
oomo exernplo5 "+~;
cJM"ifi~
Pociril'fl) = r.urnelO de eJilflmpt05".~quI! do 'mQl1f!liHlM:!nl~claulflCllo;;sa:mo ~mp/()I
FN (Fl1llV1 ~ft-e)
'"
nCIl1'lMOdef!)'~pfl'»
TN(TrIA Ni!9ltj~) :: n(JTfleft)
de ~p1.»
Na formula
anterior.
observa que 0 termo (TP'
enquanto
"+" 'iU@ sc\O£rn)Ileli!mld1tedondiClKlc,w,wnlQ
A."
'I'.le Rlog::r~nient~
HAND.
(TP + FN))
tanto alta sensibilidade
relativamente
4.1.4
o
popula~o
c:cmoellImpq
par (CARVALHO;
e geralmente
0 termo (TN I (FP + TN)) ~ geralmente
Estes dais term os sao multiplicados
tenilam
citado
d"uifiCOldol
~-";
...w.
FREITAS.
denominado
denominado
2001).
de sensibilidade,
especificidade.
para foryar 0 SIA a descobrir
quanto alta especificidade.
"t";
~mDjOi
regras que
uma vel. que seria
simples maximizar urn dos termos pela reduyao do outro.
Sele<;~o Clonal
aprendizado
no sistema
de anticorpos
antlgeno (CASTRO;
imunol6gico
significa
e a afinidade destes anticorpos
ZUBEN. 2000b). No SIA.
0
aumentar
0 tamanilo
em reconhecer
aprendizado
da
qualquer
implica em descobrir
32
anticorpos
(regras)
que reconhecem
(cobrem)
antigenos
(conjuntos
de cladas)
(CARVALHO; FREITAS, 2001).
o
SIA pede ser considerado
como um tipo de algoritmo
evolutivo), baseado em principios da varia~o
(GOLDBERG,
SIA
1989). Entretanta,
e baseado
na
Segundo
procedimento
qual
e
ele nao inclui
genetica
0
(ou
natural
pois
0
selec;:ao clonal e seu mecanismo de hipermutac;ao.
SALAVOV,
citado
de seleQao clonal
influenciado
por
(CARVALHO:
e conduzido
pela concentrayfto
na iteraC;:lio, de forma que eles auto-regulam
evolul;ao
da resposta
da
2001).
0
popula~o
0
Os clones de anticorpos
pad roes.
A
FREITAS,
pele interat;ao anticorpo-antigeno,
de antigenos.
aprender
amadurecimento
e de seleyao
operador de cruzamento,
participam
media
evoilicionario
de
suas habilidades
anticorpos
imune, a qual e caracterizada
do valor de rnatch (valor medio do valor da funt;ao
para
conduz
aD
pelo aumento
de avalialt:io)
da
dos
antigenos.
o
e
valor de match
irnportante
para 0 processo
de expansao
clonal. No
SIA. 0 valor de match e obtido atraves de funyao de avaliac;:ao. Urn anticorpo s6 e
clonado se este anticorpo tern seu valor de avaliayao
maior que pre-determinado
tflreshold. A cada iterac;ao do algoritrno de seleyao clonal. 5e urn anticorpa abtam
o throshold da expansao clonal, 0 sistema gera 50 clones deste anticorpo.
estes
clones
FREITAS,
sao
submetidos
ao
processo
de
hipermutac;ao
Ap6s,
(CARVALHO;
2001). Tanto 0 numero de threslJold quanta 0 numero de clones s~o
parametros de projeto e sao estabelecidos
A tlipermutayAo
e
implementada
previamente.
atraves
de uma
relativa
alta taxa de
muta<;a.o (taxa de mutayao de 10%) sobre um anticorpo. Como dito anteriormente,
o conceito
de hipermuta~o
consiste
no fato de que 0 mesmo
anticorpo
pade
33
gerar 50 clones, e que cada gene do clone pade ser rnutado. Na proxima
gerac;ao,
cada
e
urn
destes
sucessivamente.
50
clones
podera
gerar
Qutros
50
clones.
Isto significa que cada gene de um anticorpo
muitas \lezes desde a primeira iterat;ao ate a ultima. Urn anticorpo,
de clonagem,
e
56
a
adicionado
valor da sua respectiva fun~o
expansao clonal (CARVALHO;
Note que
0
de avalia~o
alto valor
mecanismo
se, 0
for maior au igual ao tl1res/Jold
de
de
clonal pade prover a regula9ao
e)(panSaO
e
dependente da afinidade do anticorpo.
com baixo valor de ava1ia<;:aodeve ser eliminado.
de avaliayao.
gerado a partir
se e somente
FREITAS, 2001).
processo de hiperrl1ular;ao, que
anlicorpo
populaQBo de anticorpos,
assim
pade ser mutado
0 procesSD de seler;lio
clonal
Em anticorpos
e
iniciado
do
Um
com
(CASTRO;
ZUBEN. 2000a).
No SIA, tambem
algoritmos
e
evolucionarios.
utilizado a noryao de elitismo,
0 melhor anticorpo
proxima (elitismo cam fator 1 -
OU
seja,
0
e
em geral utilizada
mantido de uma jtera~o
melhor anticorpo
repassado inalterado para a pr6xima gerayao) (CARVALHO;
Alem dos operadores
operador
especialmente
imunol6gicoslevolucionarios
projetado
para
melhorar
regras. A ideia basica deste operador denominado
remover algumas
em
para a
e
de cada gera<;ao
FREITAS, 2001).
descritos,
e
utilizado um
a campreensibilidade
des
e
operador de peda de regra,
condic;Oes da regra para torna-Ia menor. Em um alto nivel de
abstra9aO, ao remover condi90es da regra pode-se torna-Ia mais compreensivel,
de acordo com a literatura
anticorpo
de Data Mining. 0 operador
da populac;ao. em seguida aD anticorpo
e
aplicado
para cada
ter sido gerado (CARVALHO;
FREITAS, 2001).
Conforme
QUINLAN
(1993),
este pracedimenta
de pada
e
baseada
na
34
teoria
da jnforma~o.
primeiramente,
Em geral
ele calcula
0
este
operador
trabalha
da seguinte
ganho de informar;ao de cada urna das
(gene) da regra, no genoma do anticorpo.
Entao
0
procedimento
iterativamente
tenta remover urna condic;ao por vez a partir da regra. As condi~oes
valor de ganho de informClc;:io
regra (CARVALHO;
4.1.5
Mm alta probabilidade
forma:
n condi<;Oes
de serem
de menor
removidas
da
FREITAS, 2001).
Definiy:1o da Base de Dados Original
e composta
A base de dados original
algoritl11o descobrir
regras.
Para que
dividida em base de treinamento
70% da base de dados original,
0
por todos as dados disponiveis
resultado
seja consistente,
e base de testes. A base de treinamento
para criar regras com um maior
registros. A base de testes consiste de 30% da base original,
com as regras
descobertas,
verificando
assim.
para
a base
0
e
pas sui
nDmero de
mas ~ executada
a consist~ncia
dos resultados
obtidos da base de treinamento.
4.1.6
Definiyao da Base de Treinamento
Para que a algoritmo
uma base
de dados.
descoberta
destas
contem os registros
regras.
COrTI
dados original, porem com
e
posse descobrir as regras
Este trabalho
Esta base esta descrita
os casos tratados.
lIm
necessario
testa-las em
utiliza uma base de treinamento
em
Esta base
e
Unl
arquivo
para a
.data que
uma c6pia da base de
volume menor de dados (cerca de 70%).
35
4.1.7
Oefini<;t\o da Base de Testes
Apos a descoberta
executada.
de regras na base de treinamento,
a base de testes
Como esla base possui as regras, ela verifica
resultados trazidos pela base de treinamento.
4.1.8
a consistl!ncia
e
dos
e gera uma matriz de confusao.
Arquiva Names
o arquivo names armazena as names dos atributos meta e previsores,
juntamente
com seus valores.
a serem observadas.
sao
arquivos texto. com caracteristicas
Tudo que aparece antes do caraetere
M
e
:"
importantes
atributo, e
que vern depois sao as valores destes atributos. Estes valores sao separados
0
por
virgulas e podem ser categ6ricos au continuos. Toda vez que 0 algoritmo for
executado
em uma nova base de dados,
e
necessaria
ler 0 arquivo names para
obler-se as novos alributos e seus valores, e desta forma, descobrir-se
4.1.9
Para
Defini9ao das Estatisticas da Base de Dados
0
algoritmo
descobrir
necessario criar uma fun~o
Na
as regras.
proxima
aleatoriamente
etapa
0
regras
a partir de uma
base
de dados,
e
que mostra 0 menor e 0 maior valor de cada atributo.
algoritmo
inicia
a
descoberta
os valores de cada atributo, respeitando
de
regras
buscando
os limites definidos.
36
4.1.10 Pseudoc6digo
E
a sintese do c6digo, e serve para facilitar a compreensao
do algoritmo.
FUNr;!i.O_PRINCIPAL_ ALGORI TMO_ GEAA_ REC.flAS~ Cl.A$~IFlCA.<;AO 0 {
CARREGA_AROUIVO_NAMES
It
CARAEGA_-'OOUVlO_DATA
0
GERA _EnATISTICA
(j
C-ER.A_PCPULA('.J..O_II4ICIAL
n
1/
Il
H
II
PflIlIlIJ::ir
il,twtura
qUfl c1i: Uill"09 1r.tIQr ea<lA urn QO:J atribut ••
Pf!i!jNii'a :l.,ll\Jlur,loom
Ol(\a!XJI os t~rt:lrMf'itoque '6r.l)c~uiflcad;Jll;
Gef;j Iffi4tit.lic;a dOl ""mlNlo. CCIOtin~ f9f.;10
Pcpul::t
0 'ri!kIor an!ic,cjrp.O oom $) J!rimei~.J ~J
Cie dlHosifl(411
!,
AVAWU-CPUU.cAQ
REPtTA
5cE_IIAO-'~J:ISTE_MntCOAPO_COM_VAlOR_DE_AVAlIAC;Ao "''' 1
FAr;A
REPlTA
E.XPAI'I$I\O ClONALtt
AVALIA
,M)Pul..ACAO{)
ITEAAClo"
\TE~O
+ 1;
FII!I-SE
~~~~i~
~~~~~
c N(Jti'~~~Ax~~~~r~J.ge)-s~
-FACA-
-
-
E {tJAo_EXISTE_AtmCORPO==
1))
--
SALV.••.•
_MElHOR_AIITlCORPO I)
ElIr'lltlA_LI~~HAS_CLASSIFICAOAS_CO"RETAACE'ITe_PElO_t.tElHORj,IITICORPO
SEHJ..o
EXECUcA.o_AlGORITMO_SEt.l_RESUlTAOO~+;
FtM-SE
EHQUAIITO
TAOO
(EltEcvcAo_AlGOOITI,K)_SEM_RESUL
EXPArlsAo_ClCUAlO
5)
<
{
ANTICORPO_IIAO_lERO
= PR,OCURA_ArmCORPO_
VAlOft_ A.VAlIAc;AQ_01FERErITEJ)E_ZEROO
SE_AI.TICORPO_r-lAO_lERO
== VEROADEIRO
FM;A
~AAA_CAOl\jVITlCORPO_c:o.\l_YAlOR_oe_AVAl.IACAOJGUAl_""_lERO
CR~
OUPUCATA
FIM-PARA
SEII..\O
PItRA CADI. AHTlCORPO
eRI"
DUI'UCATA
CRI"-OUPUCATA
FIM-PARA
FIM-.'iE
PARA_CAOA_ANTrCOOPO_OUE_EXl5TE
FAl_MUTM;Ao
FtM-PAAA
TESTA
~ROBAeILIOADE
SE_POSITIVO
TESTA
-
PA.AA "ERIFICAR
-
PROeABILlDr.l.DE
-
-
FOt ELII.mv.aO
TE.sTA_PRo8.AllIlIoAoeJiAAA_YERIFICAR_SE
EM
CASO
SE
-
fP,A.f1I.A E'SCOlHER
-
SE ATR16UTO AI/IDA ~I~
SE
(ORiGIIIAL....E_OUPUCATA)
seRA
--
ATRIBUTO
ATRllruTO
-
OUE
-
-
ElIMIN,tU)()
UM
!Jom
_ATRIIiUTO_SOFRE_'.IUTAeJ,o
oP€RAOOR
SEI~-ESCOlHE_UI·U.OVO_VA.lOR....EIITRE_OS_POSSI\IEI8_PARA_O_ATRIBUTO_CATEGORtCO
FIM -SE
FIM..sEFIM-Po\R.A
Pnlt»t!ilidJdtl
alit
10%
IfP<tr:.u.daarributo
I\FIRMATI\IO
-se':O_ATRTBUTOfOR_CONTlrIUO
GERA_UM_NOVO_
AlQR_(OEtmW_DO_lPITERVAlOI
GERA
1/
SERA~lIMlrlAOO
IIP"o:f&Mfumt:!\.Ilj,foi
elirt'liI'JlXumoulro.~ooor~mulo';olo
/I
P'robAbi1i~ dt 10,..
37
AYA.LIA_f'OPU!..ACAOO(
P"ARA_CAOA..,II/ITICORPO
YJliLOR_ AVALI.Af;AO '" AVAJ..tAj,t
ITlCORPO
(VAlOR_REfORli.4.00_00_META_',IAIS_FREOUEI4TEI
•••
AA_Ojl.rmCORPOll.:
PREENCHE_OS_VAlORES_RETOiUl,'Omu·
FIM-PARA
)
FLOAT_AVAUA.j.rmCQRPO
ICHAR 'Mi::::T.',._UAIS]REQUEIHEI
{
2ERA_MATRIZ_DE_C:()NFU$AO
X: PARA_CAOA_LlIIHA_OAJ!ASE_DE_TREIIL"MEUTO
SE_lII-<HAJV.O_FOI_ELlr~HNAOA_AIIIOA
PARA CADA ATRIBUTO
00 NntC(jRPO
SE_Oj\TRIBUTO_'I.(OjOU:::U'JIIIAOOII
Cemp..'ffl
c:om
Irt;rQtl\
nta,
lIfllitcrpl)
•
UNndo
'*
;;cIulla
QOrrUlJOfl!Jrtlll!il
IIi)
~1a'"..iO~1UKIt!
aP!f1ldOr
W~
(Ie
.:Hrit:lIl!)
rIO
FIM·SE
SEJLA.O_ClASSIFtCOU_CORRET_COMF.CA_,WAUAcAO_PftOXlMA._Ll'IH~.JRETORJIA]AAA_Xl
FIM-$E
FIM·PARA
SE lOCOS OS ATRlaUTOS
OA UIIH" Fow,M AVALIADOS CQRRETAME!lTE
GUARoA_OC-JAl_~_Oj.1ETA3;ESTA=UtiHA
t+au -,
Ftr.hSE
"ElO
--
A'lTICQRPO
FIM·SE
FIM·P ••••
RA
~~~=~~!~~:=~~~~*~~~i;a~~~:~~~~~~:B!~1~1;r.~ESTE_Ar'TICORPO
FALSE
0
NEGATIVE::
-
-
-
-
~~~~~~'6~~o~~~~~~~ci~t~~~~-~!~:~:~~:~~~~~u~~:~~r:'T~;~~
;)boldsldli
RETORNA_
VAl~DE-"'\VAlLA~'
-
-
1'0 Cipilulo
-
-
,(.1.3 tlHIe
Ir.llHlho.
j
ElIMII-U\CAO_OM_WIHAS_CUEf
RIo."I_CLASStFICAOAS_POR_UM-'\NTICORPOU~
)1;: PARA_CADA_LlNHA_OA_IJASE_DE_ TREI~IAMEI"lTO
SE_A_111IHAJIAO_F01_ClASSIFICAOA_CORRETAI.\E~lrE
P"~-~_~R~~~~~_~~~di'~~~~~
cc.nl
lf9in,mento..
II Compgrit
3 CQ4un\i("qtMplinOOnle
ut.iIDilo 0 oper;l:lor
r~iomI
~
b~
dele
d@
o:IlnbulO
110;ll1Uo:.rllO
SE
,",J.o CLASSIFICOIJ CORfltETAMEI4TE
CoMEt;A_AVAlIA<;..(U)/I·]ROJUfllA_UPIHA
(RETORNA?A.RA
X)
FIM.$e
FIr-.4iE
FtM-PA/VI
SE_TODOS_OS_ATRIBUT01_IM_LlIIH."JORAI,jj,\IAllAOOS_COR1tETAMEIITE_PELOjlNTICORPO
EUlllltlA A UtIH~
F1M.se
-
-
Ftl.1·PAR.\
FUNCo'O_PRI"CIPAL_
PROC.,RM,I,,_OUE_
TESTA...f<..5_REORAS_GERADA$
CARREGA_A_BASE_DE_TESTES
CARREGAJ
••
S_REGRAS_GERAMS
PAAA_CADA_LlIIHA._OA_BASE_DE_TESTE
PARA_CAOA_REGRA_GERAD
..••
flMtli50mel:l
QUill:; ~-ava(i"u
'¥ER1FtCA_s€_A_R£GRA_CLASSIFICA_A_lumA
SE-;~~~PA.RA_" _PRC»l:Il.lA _LltlHA _DA_aA.'E _ OE_ TESTE
FIM...sE
FIM·PARA
SE../.tA.o_EXISTEM_REGRAS_OUE_CLASSIFtCAM_ESTA_LlI4H
..••
ERRO DE CLASSIFIOIO ++
FtM-sE FtM-fJARA
TA.U,_DEj.CERTO"
ERRO_DE_C~SIFlCACJ,o
J IIUMEPD_
TOTAlJ}E_U~lrlA:!UI."_BASE_OE_
TESTE:
4.2
REALlZA9AO
Para
de
a
dados,
DOS EXPERIMENTOS
realizac;:ao dos
que
podem
ser
experil11entos
enoontradas
foram
no
<http://w.vw.ics.uci.edu/-mlearn/MLRepository.html>.
escolha destes bases fo;
outra equipe que tarnbem
0
utilizadas
reposit6rio
da
tres
UCI
bases
no
site
0 motivD que determinou a
de permit;r a compara<;ao
dos resultados obtidos per
esta desenvolvendo um algoritmo para constru9:io de
um classificador, bem como, com os resultados obtidos por outra versao
de urn
algoritmo de Data Mining atraves do Sistema Imunol6gico Artificial, desenvolvido
pel. Prof". Dr". Deborah Ribeiro Carvalho (CARVALHO:
FREITAS, 2001).
As bases usadas sao as seguintes:
(i)
Base l1ouse votes
M
Titulo:
1984.
Estados
Unidos.
Banco
de dados
de Registros
de Votac;ao
Congressional.
Fonte de Infonnac;ao: Almanaque Trimestral congressional, 980 Congresso,
211
sessao 1984, Volume XL: Congressional Quarterly Inc., Washington, D.C., 1985.
Doador: Jeff Schtimmer [email protected]}.
Data: 27 de abril de 1987.
Informa~o
Pertinente: Este conjunto de dad as inclui votos para cada Casa
Congressisla norte-americana representantes dos 16 votos chaves identificados
peto Congressional Quarterly Inc.
39
(ii)
Base hepatitis
Titulo: Dominic de hepatite.
Fonte de Informayao:
Oesconhecida.
Deader: G. Gong - Universidade
Informa<;:ao Pertinente:
Esle
de Carnegie-Mellon.
conjunto
de dados
trata as probabilidades
de
mortalidade em individuos que contrairam a doenc;.a hepatite.
(iii)
Base
crx
Titulo: Aprovac;:ao de eredilo.
Fonle de Informa<;:ao: Confidencial
Informa~o
Pertinente:
Esle
pertinentes a aprova<;ao de eredilo.
- Submetido par: [email protected]
conjunto
de
dados
Os valores fcram
contem
informayOes
alterados para proteger
confid~ncia dos dad os.
Para possibilitar
tralamentos,
o
dados
a uliliz8</aO das bases aeima, (oram necessarios
como elimina<;ao dos dados inconsistentes
criterio utilizado para elimina~o
foi a substituiyao
atributos
categ6ricos
dos mesmos.
foram substituidas
sendo escolhidos aleatoriamente;
continuos,
foram substituidas
alguns
nas bases (?, !, etc.).
dos dados inconsistentes
Para as inconsist~ncias
as inconsist~ncias
e para as inconsistencias
nas bases de
de dados
em
par urn dos atributos
de dados em atrlbutos
as inconsistE!Ocias par um valor obtido pela media
dos valores daquele atributo tentando ao maximo
nao descaracterizar
as bases
de dados utilizadas.
Para cada base de dad os, as seguintes constantes
alteradas nos algoritmos:
simb61icas deverao ser
numero de atributos, valores (quantidade
de valores que
40
urn atributo
categ6rico
pode
receber),
tamanho
(nO de caracteres
do maior
exemplo) e dados (quantidades de eX6mpios na base).
4.2. 1 Experimento
A base house-votes,
com a base house-votes
ap6s
0
tratamento
dos dad as, foi dividida
em dUBs
bases: IlOuse.data - que contem 70% dos exemplos da base original, e house. test
-
que
30% dos exemplos
contem
proporcionalmente
a
ORIGINAL
I
I
I
I
Democrat
267
Republican
168
Total
435
TA8ELA 1
da
base
A
divisao
foi
feita
TESTE
TREINAMENTO
187
80
118
50
305
130
DlSTRIBUICAO DOS ",TRIBUTOS METAS DA BASE HOUSE·I/OTES
Ap6s a divisao da base. foram executados
reg res, variando-se
original.
base original, conforme tabela a seguir:
tr~s processos
a semente aleatoria de cOl1struyao
de obteny:Jo de
do classificador
para cada
base de dadas.
Foram identificados
iniciar
0
PREVISORES
VALORES
0
016
3
TAMANHOo
DADOS
os seguintes
processo de criayao das regras:
0
305
12
valores das constantes
simb61icas para
41
4.2.2
Experimento com a base hepatitis
A bases hepatitis,
bases:
hepatiiis.dat8
-
ap6s
0
tratamento
que contem
dcs dados,
70% dos exemplos
foi dividida
da base
em duas
original,
e
IJspatitis. test - que contem 30% dos exemplos de base original. A divisao foi feita
proporcionalmente
a
base original, conforme tabela a seguir:
ORIGINAL
Die
32
Live
123
155
Tolal
I
I
I
I
TREINAMENTO
TESTE
22
10
86
37
108
47
TABELA 2 - DISTRI8UIy,AO DOS ATRIBUTOS METAS BASE HEPATITIS
Ap6s a divisao da base, fcram executados
regras, variando-se
tr~s processos
1
de obtenc:ao de
a semen1e aleatoria da oonstru~ao do classificador
para cada
base de dedos.
Foram identificados
iniciar
0
PREVISORES
3
TAMANHO;
12
108
4.2.3
Experimento
A base crJt, ap6s
crx.data
das Gonstantes simb61icas para
; 19
VALORES;
DADOS;
as seguintes valores
processo de criayao das regras:
com a base crx
0
tratamento
dos dados, foi dividida
- que contern 70% dos exemplos
da base original,
em duas bases:
e crx.test
- que
42
contem 30% dos exemplos da base original. A divisao fai feita proporcionalmenle
it base original, conforme tabela a seguir:
ORIGINAL
TREINAMENTO
TESTE
Classe +
307
215
92
Classe -
383
268
115
690
483
207
Total
TABELA 3 - DISTRIBUIc;AO DOS ATRIBUTOS METAS BASE CRX
Ap6s a divisilo da base, fcram executados
regras, variando-se
Ires processos
a semente aleat6ria da constru~o
de obtenyao
do classificador
de
para cada
base de dadas.
Foram identificados
iniciar
0
processo de
criac;ao das regras:
12
= 483
Ap6s a gerac;ao das regras, fai necessaria
mesmas.
simb61icas para
15
TAMANHO=
DADOS
valores das constantes
= 15
PREV/SORES
VALORES=
as seguintes
Para esla verifica<;<1o. foi executado
0
verificar
algoritmo
que
a qualidade
1~
contem as regras, e testa qual regra cobre qual exemplo, possibilitando
das estatisticas
(acertos e erras), e com isso, validando
geradas pelo algoritmo classificador
SIA.
das
0 arquivo que
a qualidade
a gera~o
das regras
43
As regras geradas foram gravadas em urn arquivo de lexto, conforme figura
a seguir:
0: ==:: b: 1;> =:15. 170000:2:
<:20. 930000:8:==:1.'
1 0: <."8. 580000:
11 :==:1.' 13:<: 191 IS.56D946;+.
FIGURA 5: REGRA CRIADA ATRAV S DA BASE DE TREINAMENTO
A figura 5 representa urna regra criada atraves da base de treinamento.
exemplo
mencionado,
formata de grava~o
foi utilizada urna regra criada atraves
da base
No
crx. Esle
das regras foi utitizado para (aeilitar a leitura no algoritmo
que testa as regras.
Para (acililar 0 entendimento,
-
descrevemos
a seguir a formata~o
0 primeiro caractere de cada linha representa
previsor que sera testado.
No casa des!e exemplo,
adotada:
a primeiro atributo
representa
a at rib uta
o caractere ":" divide a atributo previsor do operador,
que pade
previsor 0;
ser
"==" para atribulos previsores categ6rios, e ">=" au "<" para atributos
previsores continuos.
-
0 caractere ";" representa que 0 proximo conjunto de caracteres
o atributo meta da regra, eo caractere ".M delimita a final da regra.
A regra na figura 5 elida da seguinte forma:
Atributo -> 0
== b
Atributo -> 1 >= 6.170000
Atributo -> 2 < 20.930000
Atributo
->
8
== t
Atributo -> 10 < 8.580000
e
44
Atributo -> 11
t
=:;::;
Atributo -> 13 < 1916.569946
Atributo ->
meta == +
Teslando
sucesso,
esla
regra sobre a base
cnde urn exemplo
exemple da base
e coberto
nao e coberto
crx, pode-se obler duas situa~oes:
pela regra; e sem sucesso,
foi coberto por nenhuma das regras geradas, esle
A seguir
e
mostrado
0
quando
urn
pela regra. Na exist~ncia de urn exemplo que n~o
e considerado
como urn erro.
teste com sucesso de urna regra gerada,
de urn
exemplo da base de testes CRX.
A regra testada sabre a observaC;ao de numera 121 (Iinha 121 da base de
teste). obteve sucesso.
Exemple - Base CRX
Observa~ao de numera 121
b,32.08,4,u,g,m,v,2.5,t,f,O,t,9,360,O,+
(0 caractere
",M
atributos previsores, eo ultimo valor e 0 atributo meta)
Regra 05
Atributo -> 0
== b
At(ibuto -> 1 >= 6.170000
Atributo -> 2
<
Atributo
== t
->
8
20.930000
Atributo -> 10 < 8.580000
Atributo -> 11
== t
Atributo -> 13 < 1916.569946
Atributo
->
meta == +
separa
os
valores
dos
45
Onde
o
atributo previsor 0 do exemplo
e == 0
o
atributo previsor 1 do exemplo
e >=
o atributo
e < 20.930000
previsor 2 do exemplo
atribulo previsor 10 do exemplo
o atributo
(4)
e == t (t)
a atributo previsor 8 do exemplo
o
6.170000 (32.08)
e < 8.580000
(0)
previsor 11 do exemplo
e == t (I)
o atributo
previsor 13 do exemplo
e < 1916.569946
o
meta do exemplo e == + (+)
atributo
Nota-se na regra exemplificada
atributos
previsores
(0)
acima, que nao fcram utilizados
para validac;:ao, paiS seria praticamente
impassivel
de gerar as regras no perfodo planejado de conclusao deste trabalho.
algumas
cria~o
bases possuiam
16 atributos
previsores
lodes as
categ6ricos,
terminar
Islo porque
dificullando
a
de uma regra que cobrisse as 16 atributos e nao garantindo a qualidade
da regra.
Para avaliar qual atributo previsor deveria ser testado,
simular uma situac;ao de poda, onde para cada regra (anticorpo)
algoritmo
que aleatoriamente
estivesse
no intervalo
entre
gerava um valor entre
°
rodado nova mente 0 algoritmo
°
foi rodado um
e 100. Se este numero
e 10, esta regra poderia ser podada.
baseado em transic;Oes aleat6rias
previsor. Caso 0 valor aleat6r10 esteja no intervalo entre
podado.
foi necessaria
°
Entao, era
para 0 atributo
e 10, este atributo
e
46
4.3 ANALISE
DOS RESULTADOS
A seguir e demon strada
a tabela
5 com
as resultados
obtidos
pela
compara<;llo do SIA em rela<;llo ao C4.5.
Classilieador
Qtde.
C4.5
SIA (Media)
Qlde.
Taxa de
Erros
Acerto
18
3
97,43%
Crx
9
2
Hepatitis
15
3
Regras
House-votes
TABELA .(
Conforme
desenvolvido
ANAlISE
demonstrado
Otd •. Folhas
na
Acerto
14
97.69°/~
98,87';'
10
82,98%
91.49%
41
76,33%
DOS RESULTADOSOO SlA COMPARAOO
atraves da pesquisa
Taxa de
(Arvore Oecisao)
tabela
4,
0
deste trabalho
algoritmo
mostrou-se
MJ C",.5
classificador
eficaz em
SIA
relavao
aDs resultados obtidos no C4.S.
A (mica base que se rnostrou melhor classificada
votes. Fa! verificado
que lodes seus atributos
previsores
pelc C4.5 foi a housesao categ6ricos,
fater a
ser destacado.
o
rtumero de regras geradas foi na sua malaria equivalente.
apenas
0
destacando-se
numero de regras geradas pelo C4.5 para base IJepatitis, que foi quase
3 vezes
maior
dassificador
o classificador
em
rela~o
ao
numero
de
regras
SIA. Porem, 0 C4.5 cobriu uma quantidade
SIA.
geradas
pelo
algoritmo
inferior de exemplos
que
47
A
seguir
e
demonstrada
a tabela
com
as
resultados
obtidos
pela
compara<;ao do SIA em relac;ao ao C4.5/A1.
Classifieador
C4.S/AI
SIA (Media)
Taxa de Acerto
5=5
5=10
5=15
House.votes
97,43"~
89,90%
88,00%
88,69%
Crx
98,87%
77,07%
85,21%
86,83%
Hepatitis
91,490/.
80,58%
86,21%
85,34%
TABELA 5 -ANALISE
DOS RESULTADOS DO SLACOMPARADO AO C4.51Al
Conforme demon strada na tabela 5,
eficaz em relayao aos resultados
0
obtidos no C4.S/AI. 0 C4.S/AI
hibrido de awore de decisaolimunol6gico,
disjuntos.
algoritmo classificador
que trata do problema
SIA mostrou-se
e
um algoritmo
dos pequenos
Os pequenos disjunlos sao regras que cobrem urn pequeno numero de
exemplos.
o
C4.5/AI foi deserwolvido
pel a Profo, Or-. Deborah Ribeiro Carvalho - Data
Minmg atraves do Sistema Imunol6gico Artificial (CARVALHO;
Note que a taxa de acerto do SIA
do pequeno disjunto (valor de $).
e
independente
FREITAS, 2001).
da definic;ao do 1amanho
5. CONCLUSAO
No initio deste trabalho foi mostrado
lecnicas.
Mostrou·se
resultados,
principais
que
existem
atraves de varias hknicas
tarefas
Imunologico
(classifica~o)
Artificial.
obtidos mostraram
0 conceito
muitas
de
apresentar
bons
de Data Mining. A partir de uma de suas
propoo-se
urn algoritmo
Este algoritmo toi implementado
que a algoritmo
de Data Mining e suas
maneiras
baseado
no Sistema
e testado, e as resultados
proposto constitui-se
numa alternativa
eficaz
para a tarefa de cJassificac;~o. ~Eficiente~ nao apenas no quesito taxa de acerto,
mas tarnbem
na questao
conforme apresentado
Durante
0
da compreensibilidade
do conhecimento
descoberto
nas tabelas 4 e 5.
desenvolvimento
deste trabalho fcram encontradas
dificuldades,
lais como material de pesquisa escasso e de dificil obtenc;;ao.
PropOe-se
heuristicas
como
trabalhos
de poda elaboradas
de expansao
experimentos
clonal
futuros
nesta
area
a
implementa~o
como, par exemplo, a otimizayao
e hipermuta~o,
etc. Uma outra
sugestao,
de
dos parametros
seria
realizar
com outras bases de dados para validar a comparac;:ao, bern como
comparar os resultados deste trabalho com outros sirnilares.
49
REFERENCIAS
BERRY, M. J. A; LlNOFF, G.
and customer
support.
Data Mining
Techniques:
for marketing,
BOOKER, L. B.; FOGEL, O. 8.; WHITLEY, O. et at. Recombination.
Fogel,
sales,
USA: John Wiley & Sons, Inc. 1997.
D. B., Michalewicz
T. (Eds),
Evolutionary
Computer
I,
In: Back, T.,
Philadelphia:
Institute of Physics Publishing, 2000. p. 256-307.
CARVALHO,
Deborah Ribeiro.
Algoritmos
Geneticos.
Data Mining Atraves de Indw;;ao
1999.
Dissertat;;ao
para obten~o
de Regras
e
do grau Mestre -
PUCPR. Curitiba. 1999.
CARVALHO,
Debcrah
para Descobrir
Ribeiro; FREITAS,
Regras para Pequenos
Alex A
Um Algoritmo
Disjuntos
Imunol6gico
em Data Mining.
8intese do
Artigo - 2001.
CARVALHO, Deborah Ribeiro. 0 que sao Sistemas Imunol6gicos
suas Aplica-;oes.
CARVALHO,
Algoritmo
Artificiais e
Paper - 2002a.
Deborah Ribeiro.
Genetico
Urn Metoda
para Data Mining.
Hibrido
2002.
Arvore
de Decisao
Tese parcial para obtencao
I
do
titulo de Doutor - PUCPR, Curitiba, 2002b.
CASTRO,
for
Leandro N.: ZUBEN. Fernando J. An Evolutionary
Data
Aftificial
Clustering.
Neural
Networks,
Proc.
Rio
SBRN
de
2000,
Janeiro,
Brazilian
Brazil.
<http://WW\Y.dca.fee.unicamp.brJ-lnuneslimmune.htm/>.
2oo2a.
Immune Network
Symposium
Disponivel
on
em:
Acesso em: 06 out. 2002.
50
CASTRO,
Leandro N.; ZUBEN,
witll Engineering
Evolutionary
Program
2000b.
-
Applications,
Fernando
Computation
Conference.
WorkslJop Immune
Disponivel
em:
The Clonal Selection
J.
Algorithm
In: Wu, A S. (Ed.) Proc. of the 2000 Genetic and
Systems,
(GECCO-2000),
p. 36-37.
Workshop
Las Vegas, NV, USA. July
<http://www.dca.fee.unicamp.br/-lnunes/imrnune.html>.
Acesso em: 06 out. 2002.
CRUZ, Priscila Gomes Bast05.
Data Mining atraves de Regras
e Arvores
Monografia
de Decisao.
em Processamer'lto
FIGUEIRA,
2000.
de AssociaC;ao
do grau de Tecn61ogo
de Oados - UTP, Curitiba, 2000.
Rafael.
Minerac;:ao
a
Objetos.
Orientados
para obtenc;ao
de
Dados
Banco
1998.
Disponivel
<http://WW\v.cos.ufrj.br/-rafael/mestrado/bdnclMonografia.
html>.
de
Dados
em:
Acesso
em:
07
out. 2002.
GOLDBERG,
D. E. Genetic Algorithms
Learning. New York: Addison-Wesley,
GURECK,
Banco
Eleazar
de Dados.
Processamento
HOFMEYR,
Artificial
Lucas.
2001.
Data Mining - Aquisic;:ao
Monografia
Steven;
FORREST,
System.
Conference
MARATH. Alexandre;
Stephanie.
Sabine.
Immunity
of
Proc.
GECC099,
MAYER,
ao Vestibular.
Processamento
de Conhecimento
para obtenGao do grau de Tecn6logo
p.
<http://wvvw.cs.unm.eduf-forresVpapers.html>.
Candidatos
and Machine
em
em
de Dados - UTP, Curitiba, 2001.
Immune
Cornputation
in Search, Optimization,
1989.
the
Genetic
'1289-1296.
·f999.
by
Design:
and
An
Evolutionary
Disponivel
em:
Acessa em: 06 aut. 2002.
Perfil
de
Monografia para obtenGao do grau de Tecnologo
Data Mining
em
de Oados - UTP, Curitiba. 2001.
para
Avaliar
51
PAWLOWSKY,
Handbook
M. A.
of Genetic
Crossover Operators, In: Lance Chambers
Algorithms
Aplications
(Ed.), Praticat
I, Boca Raton: eRG Press. 1995,
p.101-114.
POLITO, M. Data Mining.
Monagrafia - UFRJ, Rio de Janeiro, 1997. Disponivel
em: <http://hps.infolink.com.br/mpolitolmining/mining.htm>.
Acesso em: 07 out.
2002.
QUINLAN,
J. R.
C4.5: Programs
for Machine Learning,
Morgan Kaufmann
Publisher, 1993.
SOMAYAJI,
Computer
ACM
-
Anil; HOFMEYR,
Immune
1998.
System.
Steven;
New
DisponiveJ em:
Acesso em: 06 out. 2002.
FORREST,
Stephanie.
Security Paradigms
Workshop,
Principles
of a
p. 75-82. 1997.
<http://YM'W.cs.unm.edu/-forresVpapers.html>.
quarta-feira,
20 de
Le concess
est
aisons
tre.
une
(BIR
recherche
07600130)
fiftHS
Transmission
quarta-feira,
#H##
novembro
pour
vers
de
20
Ie
groupe
de
Groupe
vers
2002
de
2002
SAID
-
Groupe
27 de novembro
de
par
expediteur
vers
PILOUNIXl
Groupe
10: 21: 23 a183908
###H
2002
10:35:28
SAlOl
quarta-feira.
27 de novembro
de 2002
TMA EW
merci
de voir
cela
svp.
Transmission
10:09:11
a183908
RENAULT_SITE####
par
####
PILOUNIXl
HH##
de 2002 10:22:40
la TMA si possible
#*HH
SAID
a183908
-
####
10: 36: 16 a183908
RENAULT_SITE~##H
Paqina
1
mas
concess
par MARTINS
10: 08: 56
2002
quarta-feira.
Reprise
Ie
ESI_UNIX##H#
de novembro
SAID!
LBOOl92
et region,
EXPL_PIL_UNIX
de
20 de novembro
celA
aupres de
Transmission
09,33,04
(CAHPINAS),
PILOUNIXl PlLOUNIX -
novembro
par
2002
territoire
ville
novembro
par
de
de
Ie fichier
vers
Acceptation
quarta-feira,
HErci
de voir
####
20
Transmission
quarta-feira,
H###
20
Acceptation
quarta-feira,
####
dans
quand
est
nous
pas
ELl1.o -
mon
##H#
f