Embed Size (px)
Citation preview
1
Descoberta de Conhecimento Descoberta de Conhecimento em Bases de Dados por em Bases de Dados por Algoritmos GenéticosAlgoritmos Genéticos
Prof. Marco Aurélio C. Pacheco
2
Descoberta do Conhecimento Descoberta do Conhecimento em Bases de Dadosem Bases de Dados
Processo Processo interativointerativo e e iterativoiterativo
para identificar padrões válidos, para identificar padrões válidos,
novos, potencialmente úteis e novos, potencialmente úteis e
interpretáveis em bases de dados.interpretáveis em bases de dados.
3
Descoberta do Conhecimento Descoberta do Conhecimento em Bancos de Dadosem Bancos de Dados
1.1. Empresas armazenam Empresas armazenam dados operacionaisdados operacionais
continuamente.continuamente.
2.2. Bases de Dados podem conter Bases de Dados podem conter informações informações
importantes e desconhecidasimportantes e desconhecidas..
3.3. O conhecimento útil normalmente está oculto O conhecimento útil normalmente está oculto
em em relações complexasrelações complexas, difíceis de ser , difíceis de ser
descobertas.descobertas.
4
Aplicações: Aplicações: Conhecendo o NegócioConhecendo o Negócio
• Conhecer Comportamento do ConsumidorConhecer Comportamento do Consumidor
• Enriquecimento de Bases de DadosEnriquecimento de Bases de Dados
• Segmentação de Mercado em Classes de Segmentação de Mercado em Classes de
Consumidores (cluster)Consumidores (cluster)
• Análise de VendasAnálise de Vendas
• Detecção de Fraude e de InadimplênciaDetecção de Fraude e de Inadimplência
• Conhecer um processo, um equipamento, um Conhecer um processo, um equipamento, um
fenômeno etc, a partir de dados observadosfenômeno etc, a partir de dados observados
5
BasesDados
Conhecimento
Seleção
Pré-Processamento
Transformação
Data Mining
Interpretação
Padrões
Processo de Descoberta do Processo de Descoberta do Conhecimento - FasesConhecimento - Fases
6
Fases do Processo de Fases do Processo de Descoberta do ConhecimentoDescoberta do Conhecimento
Identificação da tarefaIdentificação da tarefa - O que se deseja conhecer/extrair?
Seleção de dadosSeleção de dados - Dados e/ou atributos relacionados.
Limpeza, Pré-Processamento Limpeza, Pré-Processamento - Retirada de dados
ambíguos, duplicados, etc.
EnriquecimentoEnriquecimento - Agregar informação externa.
Mineração dos dadosMineração dos dados - Extrair regras, agrupar.
Relatório Relatório - Histórico, conclusões, informações relevantes, etc.
7
Principais Tarefas em Principais Tarefas em Mineração de DadosMineraçã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)
8
Regras de ProduçãoRegras de Produção
• Regras possuem:– antecedentes (condições) e – conseqüentes (classe, grupo ou cluster):
SE COND1 E COND2 E... ENTÃO CLASSE_A
SE salário>3000 E sexo=M ENTÃO Consumidor classe A
• Condições relacionam valores dos atributos:– Atributos Quantitativos: idade, salário, etc– Atributos Categóricos: Sexo, Estado Civil, etc– Relações: <, >, =. Exemplo:
9
MineraçãoMineraçã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
10
Detecção de FraudeDetecção de Fraude
• Regra que explica sinistros fraudados sinistros fraudados
SE 02:00hs< hora_sinistro < 05:30hs E oficina oficinas_suspeitas E prêmio_seguro < R$ 1300 E registro_policial = NÃO E . . . . . . . . . . . custo_sinistro > R$ 10.000,00
ENTÃO FRAUDE
11
Avaliação de uma RegraAvaliaçã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%
12
Medidas de DesempenhoMedidas 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
PCPC
PCAc
&&
&
PCPC
PCAb
&&
&
13
ExemploExemplo• 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:– 6060 Registros satisfazem a regra e são do G1 – 2020 Registros do G1 não satisfazem a regra– 1212 Registros do G2 satisfazem a regra
833.02106
60
Ac 75.0
0206
60
Ab
PC&
PC&
PC&
14
Classificação por Algoritmos Classificação por Algoritmos GenéticosGenéticos
Conhece-se a segmentação de um BD em n Grupos (clusters) Grupos (clusters) ; deseja-se descobrir
a(s) regra(s)regra(s) que melhor caracterizam cada Grupo.
As regras podem se usadas para classificar outros registrosclassificar outros registros que ainda
não tenham sido segmentados.
15
Modelagem do GAModelagem do GA
Deseja-se um GA que evolua Regras– Representação– Decodificação– Operadores– Medidas de Desempenho– Avaliação
16
Cromossoma representa Cromossoma representa uma Regrauma 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
17
RepresentaçãoRepresentação
Atributos podem ser: GeneGene
• Quantitativos (Quantitativos (faixas de valores)
• Categóricos Categóricos (código)
lim_inf lim_sup
código categoria
Cada Atributo é representado por um gene
GeneGene
............Atrib(1) Atrib(n)Atrib(2)
18
Um cromossoma representa uma regra que responde a uma pergunta:
Ex: O que caracteriza um estudante da PUC-Rio?
DecodificaçãoDecodificação
Atributos considerados: A(1): Idade {15; 90}, A(2) Renda Familiar {200;8000}, A(3): Sexo{M=01; F=10}
SeSe 1818 Idade Idade2525 ee 3000 3000 Renda Renda 80008000 ee Sexo = Sexo = MM ou ou FF
entãoentão Estuda na PUC Estuda na PUC
A(1) A(2) A(3)
300025 M ou F= 11800018
A(1), A(2) são Quantitativos e A(3) é Categórico
Exemplo de um cromossoma:
19
Exemplo: Classificação de Exemplo: Classificação de EmpresasEmpresas
• Deseja-se identificar padrões de empresas (já agrupadas) em um BD
• Exemplo: A regra abaixo esclarece qual o padrão das qual o padrão das empresas do Cluster 1 (Prioritárias)?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)
20
Cromossoma Cromossoma Regra Regra
Genes atributos do banco de dados cruzamento
Receita Serviço 11000<R$<2000
Receita Serviço 24000<R$<9000
COD_ATIV = 13 10<#_Filiais<50 Empregados>100
Receita Serviço 15000<R$<7000
Receita Serviço 27000<R$<8000
COD_ATIV = 14 30<#_Filiais<60 Empregados>300
P1
P2
F1Receita Serviço 1
1000<R$<2000Receita Serviço 2
4000<R$<9000COD_ATIV = 14 30<#_Filiais<60 Empregados>300
Receita Serviço 15000<R$<7000
Receita Serviço 27000<R$<8000
COD_ATIV = 13 10<#_Filiais<50 Empregados>100FF22
21
OperadoresOperadores
• CrossoverCrossover– Sobre Reais: 1 ponto; 2 pontos; Uniforme;
Aritmético– Sobre Binários (Lógicos): OU, E
• MutaçãoMutação– Troca gene por um número aleatório na faixa
do atributo escolhido na mutação– Sobre Binários (Lógicos): NOT
22
Codificação de Atributos Codificação de Atributos CategóricosCategóricos
- Ex: Residência: = {funcional, parente, alugada, própria}
- Cada posição indica ausência (0) ou presença (1) do símbolo correspondente
Não informada (Null)00000
própria ou alugada ou parente oufuncional (don’t care)
111115
………
própria ou alugada00113
alugada00102
própria00011
Tipo ResDecodificaçãoAlelo
23
F1 = P1 OU OU P2
F2 = P1 EE P2
Operadores Lógicos Operadores Lógicos E, OU, NOTE, OU, NOT
NOTNOT PP
0011
0110
P1
P2
0111
0010
F1
F2
0011 1100F
24
Função de AvaliaçãoFunçã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
25
Funções de AvaliaçãoFunções de Avaliação
• Número-Atributos
• Distância-Ótima
• Recompensa-Atributos
• CBayesianos
• Número-Registros
• FAcurácia
• FAbrangência
• Correlação-2-Grupos
• Rule-Interest[PIAT91]
• Chi-Square[RAD95]
26
Exemplo FunçãoExemplo FunçãoNúmero-AtributosNúmero-Atributos
Regra evoluída para classe 1
AtributosRegistros 1 2 3 4 5 CLASSE F(Núm_Atrib)
1 a b x d r 1 32 s w c d e 2 -33 q b c d e 1 44 x f g h e 1 15 a b c d r 2 -46 a t c y e 1 37 p b v d y 2 -28 x h j k u 2 09 a b c d e 1 5
10 a b z d q 1 3
REGRA a b c d e 1 12 Avaliação
27
Evolução de Regras porEvolução de Regras por Algoritmo Genético Algoritmo Genético
Planejamento Cromossoma Aptidão
Regra A 86%Regra B 44%Regra C 69%Regra D 7%
f( )=acerto%f( )=acerto%
Seleção
ReproduçãoFilhos
Avaliaçãodos Filhos
Cruzamento
Mutação
28
Otimização da Acurácia da Otimização da Acurácia da RegraRegra
Melhor Padrão
0
5000
10000
15000
20000
25000
300001 5 9
13
17
21
25
29
33
37
41
45
49
Cromossomas x 2000
Ac
urá
cia
Evolução Evolução
100%
50%
