Descoberta de Conhecimento
em Bases de Dados por
Algoritmos Genéticos
Prof. Marco Aurélio C. Pacheco
1
Descoberta do Conhecimento
em Bases de Dados
Processo interativo e iterativo
para identificar padrões válidos,
novos, potencialmente úteis e
interpretáveis em bases de dados.
2
Descoberta do Conhecimento
em Bancos de Dados
1. Empresas armazenam dados operacionais
continuamente.
2. Bases de Dados podem conter informações
importantes e desconhecidas.
3. O conhecimento útil normalmente está oculto
em relações complexas, difíceis de ser
descobertas.
3
Aplicações:
Conhecendo o Negócio
• Conhecer Comportamento do Consumidor
• Enriquecimento de Bases de Dados
• Segmentação de Mercado em Classes de
Consumidores (cluster)
• Análise de Vendas
• Detecção de Fraude e de Inadimplência
• Conhecer um processo, um equipamento, um
fenômeno etc, a partir de dados observados
4
Processo de Descoberta do
Conhecimento - Fases
Interpretação
Conhecimento
Data Mining
Padrões
Transformação
Pré-Processamento
Seleção
Bases
Dados
5
Fases do Processo de
Descoberta do Conhecimento
 Identificação da tarefa - O que se deseja conhecer/extrair?
 Seleção de dados - Dados e/ou atributos relacionados.
 Limpeza, Pré-Processamento - Retirada de dados
ambíguos, duplicados, etc.
 Enriquecimento - Agregar informação externa.
 Mineração dos dados - Extrair regras, agrupar.
 Relatório - Histórico, conclusões, informações relevantes, etc.
6
Principais Tarefas em
Mineração de Dados
• Clusterização
– Agrupamento: Segmentar registros de um BD em N clusters (grupos,
classes)
• Diferenciação
– Regras que diferenciam os registros de um cluster em relação a outros
clusters
• Classificação
– Identificar a priori o cluster (grupo) ao qual pertence um registro
(cliente) a partir de seus atributos
• Explicação
– Regras que explicam/caracterização um conjunto de registros
pertencentes a um cluster (classe)
7
Regras de Produção
• Regras possuem:
– antecedentes (condições) e
– conseqüentes (classe, grupo ou cluster):
SE COND1 E COND2 E... ENTÃO CLASSE_A
• Condições relacionam valores dos atributos:
– Atributos Quantitativos: idade, salário, etc
– Atributos Categóricos: Sexo, Estado Civil, etc
– Relações: <, >, =. Exemplo:
SE salário>3000 E sexo=M ENTÃO Consumidor classe A
8
Mineração
• Inferir uma Regra  descobrir condições (atributos,
valores/categorias) que satisfazem a uma classe
• Classificar um novo cliente  presumir a classe a
qual pertence um novo cliente
• Agrupar clientes  identificar classes por
semelhança de suas características
• Explicar  inferir regras com acurácia que abranjam
todos os elementos de uma classe
9
Detecção de Fraude
• Regra que explica sinistros fraudados
SE
02:00hs< hora_sinistro < 05:30hs
oficina  oficinas_suspeitas
E
prêmio_seguro < R$ 1300
E
registro_policial = NÃO E
...........
custo_sinistro > R$ 10.000,00
ENTÃO
FRAUDE
E
10
Avaliação de uma Regra
• Acurácia:
– mede grau de certeza (ou confiança) obtido ao
contrastar a regra com o conjunto de exemplos da
base que pertencem e não pertencem à classe;
– Ac Máx = 100%
• Abrangência:
– mede o grau de cobertura da regra: percentual
de registros da classe que satisfazem a regra;
– Ab Máx = 100%
11
Medidas de Desempenho
• A avaliação de cada regra envolve a leitura de toda a base.
• Numa base há:
– C: Registros que satisfazem a regra;
– P: Registros que pertencem à classe;
– C & P: número de registros que satisfazem a regra e são da classe P
Ac 
C&P
C & P  C & P 
Ab 
C&P
C & P  C & P 
12
Exemplo
• BD contém 100 Registros
• Registros estão segmentados em 2 Grupos:
– 80 regs. do G1 e 20 regs. do G2)
• Procura-se regras para G1 (P pertence a G1)
• Uma determinada regra encontrada, resulta em:
– 60 Registros satisfazem a regra e são do G1
– 20 Registros do G1 não satisfazem a regra
– 12 Registros do G2 satisfazem a regra
Ac 
60
 60  12 
 0.833
Ab 
60
 60  20 
C & P
C & P
C & P
 0.75
13
Classificação por Algoritmos
Genéticos
Conhece-se a segmentação de um BD em
n Grupos (clusters) ; deseja-se descobrir
a(s) regra(s) que melhor caracterizam
cada Grupo.
As regras podem se usadas para
classificar outros registros que ainda
não tenham sido segmentados.
14
Modelagem do GA
Deseja-se um GA que evolua Regras
– Representação
– Decodificação
– Operadores
– Medidas de Desempenho
– Avaliação
15
Cromossoma representa
uma Regra
• Regras :=antecedentes + consequentes
Se COND1 ^ COND2 ^...ENTÃO CLASSE_A
Exemplo:
Se 200<salário<3000 ^ sexo=M ENTÃO Bom-Pagador
• Evoluir Regra  Encontrar regra com alta Ac e Ab
– Escolher atributos que farão parte da regra
– Descobrir faixa de valores para atributos quantitativos
– Descobrir conjunto de categorias para os categóricos
16
Representação
Atrib(1)
Atrib(n)
Atrib(2)
............
Gene
Cada Atributo é representado por um gene
Atributos podem ser:
Gene
• Quantitativos (faixas de valores) lim_inf
• Categóricos (código)
lim_sup
código categoria
17
Decodificação
Um cromossoma representa uma regra que
responde a uma pergunta:
Ex: O que caracteriza um estudante da PUC-Rio?
Atributos considerados:
A(1): Idade {15; 90}, A(2) Renda Familiar {200;8000}, A(3): Sexo{M=01; F=10}
Exemplo de um
cromossoma:
A(1)
18
25
A(2)
3000
A(3)
8000 M ou F= 11
A(1), A(2) são Quantitativos e A(3) é Categórico
Se 18  Idade25 e 3000  Renda  8000 e Sexo = M ou F
então Estuda na PUC
18
Exemplo: Classificação de
Empresas
• Deseja-se identificar padrões de empresas (já agrupadas)
em um BD
• Exemplo: A regra abaixo esclarece qual o padrão das
empresas do Cluster 1 (Prioritárias)?
Se receita_serviço 1 (Instalação) = 5000<R$<7000 &
receita_serviço 2 (Manutenção) = 7000<R$<8000 &
código_atividade = 13 (Ind. Mat.Elétrico Eletrônico e Comunicação) &
10 < #_Filiais < 50 &
...........
#_Empregados > 100
Então Empresa pertence ao Cluster 1(Prioritárias)
19
Cromossoma  Regra
Genes  atributos do banco de dados
cruzamento
P1
Receita Serviço 1 Receita Serviço 2
COD_ATIV = 13
1000<R$<2000
4000<R$<9000
10<#_Filiais<50
Empregados>100
P2
Receita Serviço 1 Receita Serviço 2
COD_ATIV = 14
5000<R$<7000
7000<R$<8000
30<#_Filiais<60
Empregados>300
F1
Receita Serviço 1 Receita Serviço 2
COD_ATIV = 14
1000<R$<2000
4000<R$<9000
30<#_Filiais<60
Empregados>300
Receita Serviço 1 Receita Serviço 2
COD_ATIV = 13
5000<R$<7000
7000<R$<8000
10<#_Filiais<50
Empregados>100
20
F2
Operadores
• Crossover
– Sobre Reais: 1 ponto; 2 pontos; Uniforme;
Aritmético
– Sobre Binários (Lógicos): OU, E
• Mutação
– Troca gene por um número aleatório na faixa
do atributo escolhido na mutação
– Sobre Binários (Lógicos): NOT
21
Codificação de Atributos
Categóricos
- Ex: Residência: = {funcional, parente, alugada, própria}
- Cada posição indica ausência (0) ou presença (1) do
símbolo correspondente
Alelo
1
2
3
…
15
Decodificação
0001
0010
0011
…
1111
0
0000
Tipo Res
própria
alugada
própria ou alugada
…
própria ou alugada ou parente ou
funcional (don’t care)
22
Não informada (Null)
Operadores Lógicos
E, OU, NOT
P1
0011
F1
0111
F1 = P1 OU P2
P2
0110
F2
0010
F2 = P1 E P2
P
0011
F
1100
NOT P
23
Função de Avaliação
• Data Mining: regras com alta acurácia e abrangência.
• Acurácia (Ac) e Abrangência (Ab), quando usadas
como funções de avaliação, podem prejudicar a
evolução se regras aleatórias na primeira população
apresentam Ac=Ab=0
• É preciso definir funções que forneçam avaliações
diferentes de 0 (zero) quando Ac=Ab=0
• Existem várias funções propostas, cujo o desempenho
varia com a aplicação (problema)
• Ac e Ab podem recompensar avaliação quando
diferentes de zero
24
Funções de Avaliação
• Número-Atributos
• Distância-Ótima
• RecompensaAtributos
• CBayesianos
• Número-Registros
•
•
•
•
•
FAcurácia
FAbrangência
Correlação-2-Grupos
Rule-Interest[PIAT91]
Chi-Square[RAD95]
25
Exemplo Função
Número-Atributos
Registros
1
2
3
4
5
6
7
8
9
10
REGRA
Atributos
1
a
s
q
x
a
a
p
x
a
a
a
2
b
w
b
f
b
t
b
h
b
b
3
x
c
c
g
c
c
v
j
c
z
4
d
d
d
h
d
y
d
k
d
d
5
r
e
e
e
r
e
y
u
e
q
b
c
d
e
CLASSE F(Núm_Atrib)
1
3
2
-3
1
4
1
1
2
-4
1
3
2
-2
2
0
1
5
1
3
1
12 Avaliação
Regra evoluída para classe 1
26
Evolução de Regras por
Algoritmo Genético
Avaliação
dos Filhos
Planejamento Cromossoma Aptidão
Regra A
Regra B
Regra C
Regra D
86%
44%
69%
7%
Seleção
f( )=acerto%
Cruzamento
Filhos
Mutação
Reprodução
27
Otimização da Acurácia da
Regra
30000
100%
25000
20000
50%
15000
10000
5000
Evolução 
49
45
41
37
33
29
25
21
17
13
9
5
0
1
Acurácia
Melhor Padrão
Cromossomas x 2000
28