86
23/11/1 999 11/11/2 005 compsulmt 1 Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D ([email protected]) Departamento de Ciência da Computação Universidade de Brasília www.cic.unb.br/~mladeira I Congresso de Computação do Sul do Mato Grosso Rondonópolis/MT, 8 a 11/11/2005

11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D ([email protected])

Embed Size (px)

Citation preview

Page 1: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

23/11/199911/11/200

5

compsulmt 1

Construção e Avaliação de Modelos com o UnBMiner,

Ferramenta Aberta para Mineração de Dados

Marcelo Ladeira, Ph.D ([email protected])

Departamento de Ciência da Computação

Universidade de Brasília

www.cic.unb.br/~mladeira

I Congresso de Computação do Sul do Mato Grosso

Rondonópolis/MT, 8 a 11/11/2005

Page 2: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

2

Sumário

1. Conceituação de KDD Mineração de Dados Aprendizagem de Máquina

2. Tarefas de Mineração de Dados Exemplo Simples

3. Metodologia CRISP-DM

4. Visão Geral do UnBMiner

5. Estudo de Caso Lupa Digital (apoio a identificação de criminosos)

6. Conclusões

Page 3: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

Knowledge Discovery in Databases 3

1. Conceituação de KDD

Quanto ao resultado “Processo, não trivial, de extração de informações,

implícitas, previamente desconhecidas e úteis, a partir dos dados armazenados em um banco de dados.” [Frawley, Piatetsky-Shapiro & Matheus,1991]

Quanto ao processo “Tarefa de descoberta de conhecimento intensivo,

consistindo de interações complexas, feitas ao longo do tempo, entre o homem e uma grande base de dados, possivelmente suportada por um conjunto heterogêneo de ferramentas.” [Brachman & Anand,1995]

Page 4: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

4

1. KDD – Definição Formal Processo não trivial de identificação de padrões em conjunto de

dados que possuam as características de: validade

os padrões devem ser válidos para novos dados, com algum grau de certeza ou probabilidade.

novidade os padrões devem ser novos, ou seja, ainda não foram

detectados por nenhuma outra abordagem. utilidade potencial:

os padrões devem poder ser utilizados para a tomada de decisões úteis, medidas por alguma função ou critério.

assimiláveis: os padrões devem ser assimiláveis ao conhecimento humano.

• Fayyad, Piatetsky, Smyth & Uthurusamy. From Data Mining to Knowledge Discovery: An Overview. In: Advances in Knowledge Discovery and Data Mining, 1ed. AAAIPress, The MIT Press, 1996

Page 5: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

5

1. KDD – Áreas de Interação

Estatística Reconhecimento de padrões e aprendizagem de

máquina Extração de padrões e construção de modelos

Inteligência artificial (conhecimento simbólico) Representação e interpretação de conhecimento

Inteligência computacional (conhec. numérico) Aprendizagem e generalização

Banco de dados

Page 6: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

O processo é iterativo e cíclico e a saída de uma etapa pode requerer uma revisão em uma etapa anterior. 6

1. Etapas do Processo de KDD

Page 7: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

Forte relacionamento com a área de banco de dados, por exemplo, Intelligent Miner da IBM. 7

1. KDD 1.1 Mineração de Dados

Avaliação de dados eletrônicos com a ajuda de técnicas de aprendizagem para que se possa encontrar relações ou padrões entre eles, visando: descobrir novos fatos, regularidades, restrições ou

relacionamentos, a partir da análise dos dados. encontrar e descrever padrões estruturais (modelos) nos

dados, como uma ferramenta que ajuda a explicar e fazer previsões.

• Entrada: conjunto de treinamento (envolve algum conceito a ser aprendido).

• Saída: modelo (representa forma de predizer novos dados). Podem existir muitas descrições alternativas (modelos) que

explicam os dados: em geral, opte pelo mais simples. testar a validar de hipóteses (idéias pré-formuladas)

• Entrada: idéias e conjunto de treinamento que permita avaliá-las. É uma etapa do processo de KDD.

Page 8: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

Fortemente baseada no uso de técnicas estatísticas para análise de dados. 8

1. KDD 1.2 Aprendizagem de Máquina

Área de pesquisa em Inteligência Artificial. O aprendizado de máquina envolve a idéia de

aprendizagem (generalização ou especialização de conceitos) através de análise de dados.

Page 9: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

9

2. Tarefas de Mineração de Dados Os principais objetivos de alto nível são a previsão e a

descrição. A previsão envolve usar algumas variáveis ou campos da

base de dados para prever valores desconhecidos ou futuros de variáveis de interesse.

A descrição se concentra em encontrar padrões que descrevem os dados, que sejam interpretáveis pelos seres humanos. No contexto de KDD, a descrição tende a ser mais

importante que a previsão, ao contrário das aplicações de aprendizado de máquina e reconhecimento de padrões.

Os objetivos de previsão e descrição são alcançados através da realização das tarefas básicas de mineração.

Page 10: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

10

2. Tarefas de Mineração de Dados 2.1 Exemplo Simples Considere uma distribuição correspondendo aos

atributos renda e dívida de um correntista. Cada pessoa foi classificada como bom

pagador (o) ou mau pagador (x)

Page 11: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

Exemplo extraído de slides preparados pelo Prof. Paulo Martins Engel - UFRGS 11

2. Tarefas de Mineração de Dados 2.1 Classificação

Consiste em aprender uma função que mapeia (classifica) um item de dado para uma entre várias classes pré-definidas.Superfície de decisão linear

Se w1.renda + w2.dívida < t, então cliente não paga o empréstimo (x)

Possui erro associado.

Page 12: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

Exemplo extraído de slides preparados pelo Prof. Paulo Martins Engel - UFRGS 12

2. Tarefas de Mineração de Dados 2.1 Regressão Consiste em aprender uma função que

mapeia um item de dado para uma variável de previsão de valor real.

Page 13: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

Exemplo extraído de slides preparados pelo Prof. Paulo Martins Engel - UFRGS 13

2. Tarefas de Mineração de Dados 2.1 Agrupamento (clustering)

Tarefa descritiva onde se procura identificar um conjunto finito de categorias ou agrupamentos que descrevem os dados.

Page 14: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

14

2. Tarefas de Mineração de Dados 2.1 Sumarização Envolve métodos para encontrar uma

descrição compacta para um subconjunto de dados. Um exemplo simples seria a tabulação da

média e dos desvios padrões de todos os campos.

Métodos mais sofisticados envolvem derivar regras gerais, técnicas de visualização para múltiplas variáveis e a descoberta de relações funcionais entre variáveis. Estas técnicas são usadas na análise exploratória

interativa e na geração automática de relatórios.

Page 15: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

15

2. Tarefas de Mineração de Dados 2.1 Modelagem de Dependências

Consiste em encontrar um modelo que descreva dependências significativas entre variáveis. Modelos de dependências existem em dois níveis: o

nível estrutural do modelo especifica quais as variáveis são localmente dependentes entre si.

O nível quantitativo especifica as intensidades das dependências usando alguma escala numérica.

As redes probabilísticas são exemplo desta modelagem

Redes bayesianas, diagramas de influências, naive Bayes, TAN (Tree Augmented Naive Bayes), BAN (Bayesian Augmented Naive Bayes)

Page 16: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

Rede bayesiana, diagrama de influências, Naive Bayes, TAN e BAN 16

2. Tarefas de Mineração de Dados 2.1 Modelagem de Dependências

X3

C

X2 X1 X4

X3

C

X2 X1 X4

C

X2

X1 X4 X3

Page 17: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

17

2. Tarefas de Mineração de Dados 2.1 Detecção de Desvios Enfoca a descoberta das modificações mais

significativas nos dados em relação aos valores médios históricos. É utilizada, por exemplo, na identificação de fraudes.

Page 18: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

18

2. Tarefas de Mineração de Dados 2.1 Associação O problema da cesta de compras assume que

tenhamos um grande número de itens, p.ex., “pão”, “leite”, etc. Os clientes enchem as suas cestas de compras com um subconjunto desses itens e nós dispomos da informação sobre quais itens foram comprados juntos para cada cliente. Regras associativas: {X1, X2, ..., Xn} Y

se encontrarmos todos os itens X1, X2, ..., Xn na cesta de compras, então nós temos uma boa chance de encontrar também Y.

Page 19: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

3. Metodologia CRISP-DM Cross Industry Process Model for Data Mining

Modelo de processo hierárquico que parte de um conjunto de tarefas mais gerais para um conjunto de tarefas mais específicas, discriminadas em quatro níveis de abstração:

a) no topo da hierarquia, o processo de MD é organizado em fases;

b) as fases, por sua vez, são constituídas por diversas tarefas genéricas, que formam o segundo nível da hierarquia;

c) o terceiro nível, de tarefas especializadas, envolve a descrição de como as ações das tarefas genéricas são aplicadas em situações específicas. Por exemplo, uma tarefa genérica do segundo nível é a limpeza de

dados. No terceiro nível, essa tarefa seria descrita em diferentes situações, tais como limpeza de valores numéricos ou de valores categóricos.

d) o quarto nível, de instâncias do processo, é um registro das ações, decisões e resultados da mineração de dados de uma aplicação em particular.

Page 20: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

www.crisp-dm.org/CRISPWP-0800.pdf 20

3. Metodologia CRISP-DM Fases

Page 21: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

Também denominada entendimento do domínio 21

3. Metodologia CRISP-DM Entendimento do Negócio Foca o entendimento dos objetivos e

requerimentos do projeto, da perspectiva do domínio, a relevância do conhecimento prévio e os objetivos do usuário final.

Nessa etapa são elaborados o plano do projeto, especificando os passos a serem executados no resto do projeto e a definição do problema.

Page 22: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

22

3. CRISP-DM Entendimento dos Dados Seleção do conjunto de dados Análise dos dados

identificar problemas de qualidade descobrir os primeiros conhecimentos descrição dos dados

formato, quantidade de registros e campos distribuição dos atributos, relacionamentos entre pares de atributos, identificação de agrupamentos ou subconjuntos

existentes nos dados

Page 23: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

Pré-processamento dos dados 23

3. CRISP-DM Preparação dos Dados

Seleção de atributos, limpeza, construção, integração e formatação dos dados de entrada remoção de ruído ou de dados espúrios, estratégias para lidar com valores faltantes, formatação dos dados para a ferramenta a usar, criação de atributos derivados e de novos

registros, integração de tabelas, discretização dos dados numéricos, se

necessário.

Page 24: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

24

3. Metodologia CRISP-DM Modelagem Quais modelos e parâmetros usaremos?

função do tipo de dados (numéricos ou nominais). problema de mineração de dados.

Elaboração do plano de testes permitir avaliar os modelos gerados.

Divisão da massa de dados: conjunto de treinamento, conjunto de testes conjunto de validação.

Page 25: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

25

3. Metodologia CRISP-DM Avaliação Avaliar a qualidade dos modelos obtidos no

treinamento do ponto de vista de análise dos dados. critério para seleção entre modelos.

Classificadores• Matriz de confusão• Taxa de TP líquida

i TPi * (1-FPi)

Verificar se os objetivos do negócio foram atingidos de acordo com os critérios de sucesso adotados .

Page 26: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

26

3. Metodologia CRISP-DM Colocação em Uso Modelo selecionado

incorporado ao processo de tomada de decisão da organização

Plano de monitoração e manutenção previne uso incorreto dos resultados do

mineração, durante um longo período de tempo.

Page 27: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

27

3. Metodologia CRISP-DM Resumo

Page 28: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

28

4. Visão Geral do UnBMiner Framework e API para mineração de dados

Software aberto (licença GNU GPL) em Java. http://sourceforge.net/projects/unbbayes

Grupo de IA da Universidade de Brasília Suporte ao modelo CRISP-DM

Pré-processamento Modelagem

redes probabilísticas (Naive Bayes e redes bayesianas), árvores de decisão (algoritmos ID3 e C4.5), CNM (Modelo Neural Combinatório) redes neurais multi-camadas (backpropagation)

Avaliação

Page 29: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

http://www.cs.waikato.ac.nz/~ml/weka/ 29

4. Visão Geral do UnBMiner Arquivos Arff e Texto@relation weather.symbolic@attribute outlook {sunny, overcast, rainy}@attribute temperature {hot, mild, cool}@attribute humidity {high, normal}@attribute windy {TRUE, FALSE}@attribute play {yes, no}@datasunny,hot,high,FALSE,nosunny,hot,high,TRUE,noovercast,hot,high,FALSE,yesrainy,mild,high,FALSE,yesrainy,cool,normal,FALSE,yesrainy,cool,normal,TRUE,noovercast,cool,normal,TRUE,yessunny,mild,high,FALSE,nosunny,cool,normal,FALSE,yesrainy,mild,normal,FALSE,yessunny,mild,normal,TRUE,yesovercast,mild,high,TRUE,yesovercast,hot,normal,FALSE,yesrainy,mild,high,TRUE,no

outlook temperature humidity windy play sunny hot high FALSE nosunny hot high TRUE noovercast hot high FALSE yesrainy mild high FALSE yesrainy cool normal FALSE yesrainy cool normal TRUE noovercast cool normal TRUE yessunny mild high FALSE nosunny cool normal FALSE yesrainy mild normal FALSE yessunny mild normal TRUE yesovercast mild high TRUE yesovercast hot normal FALSE yesrainy mild high TRUE no

Page 30: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

30

4. Visão Geral do UnBMiner Janela de Abertura

Page 31: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

31

4. Visão Geral do UnBMiner Ferramentas Disponíveis

Page 32: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

32

4. Visão Geral do UnBMiner Pré-processador

Page 33: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

http://sourceforge.net/projects/nntk 33

4. UnBMiner Tarefas de Mineração de Dados Associação

CNM Classificação

ID3, C4.5, Naive Bayes e redes neurais TAN e BAN estão em desenvolvimento.

Novas facilidades estão disponíveis no NNTK – Neural Network Toolkit Rede Levenberg-Marquardt Rede RBF

Page 34: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

4. Visão Geral do UnBMiner Problema de Classificação

Diversas variáveis de atributo Única variável de classe Banco de dados histórico

Construir modelo de classificação Inferir o valor da classe a partir do conhecimento

atributos.

Page 35: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

35

4. Visão Geral do UnBMiner Base de Dados Categóricos

outlook temperature humidity windy playsunny hot high FALSE nosunny hot high TRUE noovercast hot high FALSE yesrainy mild high FALSE yesrainy cool normal FALSE yesrainy cool normal TRUE noovercast cool normal TRUE yessunny mild high FALSE nosunny cool normal FALSE yesrainy mild normal FALSE yessunny mild normal TRUE yesovercast mild high TRUE yesovercast hot normal FALSE yesrainy mild high TRUE no

Page 36: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

36

4. Visão Geral do UnBMiner Base de Dados Numéricos

outlook temperature humidity windy playsunny 85 85 FALSE nosunny 80 90 TRUE noovercast 83 86 FALSE yesrainy 70 96 FALSE yesrainy 68 80 FALSE yesrainy 65 70 TRUE noovercast 64 65 TRUE yessunny 72 95 FALSE nosunny 69 70 FALSE yesrainy 75 80 FALSE yessunny 75 70 TRUE yesovercast 72 90 TRUE yesovercast 81 75 FALSE yesrainy 71 91 TRUE no

Page 37: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

37

4. Visão Geral do UnBMiner Árvore de Decisão

Page 38: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

Classificador probabilístico 38

4. Visão Geral do UnBMiner Naive Bayes

Page 39: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

Podemos derivar regras de associação a partir dessa topologia. 39

• Machado, R.J. & Rocha, A.F. da, (1989). “Handling Knowledge in High Order Neural Networks: The Combinatorial Neural Model”. In: International Joint Conference on Neural Networks. Washington. TR CCR076

4. Visão Geral do UnBMiner CNM Modelo Neural Combinatório

x1 x2 x3

C1 C2 C3 C4 C5 C6 C7 C8

y1 y2

Page 40: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

Regra se X então Y. 40

4. Visão Geral do UnBMiner CNM Modelo Neural Combinatório

Page 41: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

41

4. Visão Geral do UnBMiner Redes Neurais Backpropagation

Camada de entrada

Camada oculta

Camada de saída

Page 42: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

42

4. Visão Geral do UnBMiner Redes Neurais Backpropagation

Page 43: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

43

4. Visão Geral do UnBMiner Avaliação === Run information ===

Scheme: NeuralNetworkRelation: weather.symbolicInstances: 14Attributes: 5 outlook temperature humidity windy playClassAttribute: playTest mode: === Classifier model ===Learning Rate: 0.3Momentum: 0.2Hidden Layer Size: 3Training Time: 400Activation Function: SigmoidLearning Rate Decay: falseNumerical Input Normalization: No normalizationActivation Function Steep: 1.0Class Attribute: play=== Summary ===Correctly Classified Instances 14 100 %Incorrectly Classified Instances 0 0 %Quadratic loss function 0 Total Number of Instances 14 === Detailed Accuracy By Class ===TP Rate FP Rate TN Rate FN Rate Class 1 0 1 0 yes 1 0 1 0 no=== Confusion Matrix === a b <-- classified as 9 0 | a = yes 0 5 | b = no

Page 44: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

44

5. Estudo de Caso

Detecção de fraudes em cartões de crédito Busca decadactilar de impressões digitais

Lupa Digital Diagnóstico médico

Cardiopatias congênitas Pedotransferência de água

Page 45: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

45

5.1 Estudo de Caso – Lupa Digital Atribuições do INI/DPF Analisar, classificar, pesquisar e arquivar

individuais datiloscópicas. Proceder à busca e comparações de individuais

datiloscópicas. Prestar informações com base no arquivo

datiloscópico e prontuários criminais. Efetuar confronto dos processos de reincidentes

para fins de confirmação de registro.

Page 46: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

Tipo primário e fórmula. 46

5.1 Problema ?

Tarefa “impossível” se formos utilizar métodos manuais.

Page 47: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

47

5.2 Datiloscopia Processo de identificação das pessoas por meio

do estudo dos seus desenhos digitais. "daktilos" - (dedos) e

"skopêin" - (examinar). Extrema variabilidade,

imutabilidade e perenidade dos desenhos digitais.

Existência e localização do“delta”.

Page 48: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

48

5.2 Sistema de Vucetich

Definiu 4 classes: Arco: 1 ou A Presilha interna: 2 ou I Presilha externa: 3 ou E Verticilo: 4 ou V

Foram acrescentadas: Anômalo: 5 Cicatriz: 6 Amputação (ou falta): 7

N

N

Page 49: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

49

5.2 Sistema de Vucetich

Baseado no número e localização do delta

Page 50: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

50

5.2 Sistema de Vucetich

Classificação dos Datilogramas:

Arco suas linhas correm de um lado a

outro, normalmente não apresenta delta.

Verticilo apresenta dois deltas e um círculo.

Page 51: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

51

5.2 Sistema de Vucetich

Classificação dos Datilogramas

Presilha interna laçada central e delta à direita do

observador. Presilha externa

laçada central e delta à esquerda do observador.

Page 52: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

52

5.2 Sistema de Vucetich

Classificação dos Datilogramas:

Anômalos constituídos pela combinação dos

tipos anteriores. Cicatriz

deformidade causada por doença ou acidente que impede a sua classificação.

Amputação total ou parcial.

Page 53: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

53

5.2 Sistema de Vucetich

Fórmula datiloscópica:1 - 3 3 4 3 Mão direita

2 - 2 1 4 2 Mão esquerda Existem 710 = 282.475.249 fórmulas possíveis.

Existem sub-tipos para cada tipo fundamental.

Page 54: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

54

5.3 Organização do arquivo

MD 1-1111, 1111, 1111, ... , 1111, 1111, ... , 1111, 1111,ME 1-1111 1112 1113 1117 1121 7776 7777 MD 1-1112, 1112, 1112, ... , 1112, 1112, ... , 1112, 1112,ME 1-1111 1112 1113 1117 1121 7776 7777...... MD 7-7777, 7777, 7777, ... , 7777, 7777, ... , 7777, 7777,ME 7-1111 1112 1113 1117 1121 7776 7777

Page 55: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

55

5.4. Objetivos

Modelar o domínio impressões digitais utilizando algoritmos de mineração de dados.

Projeto e implementação de uma ferramenta para uso na Polícia Federal (AIM ou Lupa Digital).

Geração de bibliografia técnica sobre a aplicação de mineração de dados no domínio de datiloscopia.

Page 56: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

* Automatic Fingerprint Information System 56

5.5 Hipótese de Pesquisa

Obter um, ou mais, modelos de classificador que gerasse (complementasse) os códigos Vucetich para as impressões digitais dos dedos faltantes e, desta forma, reduzisse o espaço de busca em pesquisa manual ou automatizada (AFIS*) de identificação de impressões digitais.

Page 57: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

Arquivo fornecido por Marcos Elias, DPF/INI. 57

5.6 Entendimento dos Dados

Arquivo Base O arquivo base foi extraído em novembro de

2000, na forma de documento texto (.txt) com: 53,26MB de tamanho. total de 606.993 registros.

MECA-Sinic: base com 502.052 registros, devido Constituição de 1988. Estrangeiros. Fórmulas não digitadas no Sinic.

Page 58: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

Embora use codificação numérica, os dados não categóricos. 58

5.6 Entendimento dos Dados

Análise Estatística Descritiva 36.175 fórmulas amostra de 502.052 de ID. Resto das fórmulas 88,74%.

Page 59: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

59

5.6 Entendimento dos Dados

Análise Estatística Descritiva Freqüência = 1 4,75% Freqüência = 2 2,01% Freqüência = 3 1,38% Freqüência = 4 1,13% Freqüência = 5 0,95% Percentual de fórmulas com distribuição de

freqüência menor que 1% = 90,72%

Page 60: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

60

5.6 Entendimento dos Dados

TIPOS FUNDAMENTAIS

7,26%

30,96%

28,85%

31,60%

0,05%1,09%

0,19%

9,58%

29,37%

32,05%

28,14%

0,05%0,75%

0,06%

7,49%

30,80%

29,16%

31,25%

0,05%1,06%

0,18%

0,00%

5,00%

10,00%

15,00%

20,00%

25,00%

30,00%

35,00%

ARCO PRESILHAINTERNA

PRESILHAEXTERNA

VERTICILO ANÔMALO CICATRIZ AMPUTAÇÃO

Per

cen

tag

ens

HomensMulheresTotal

Page 61: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

61

5.6 Entendimento dos Dados

TIPOS FUNDAMENTAIS / HOMEM

0,00%

10,00%

20,00%

30,00%

40,00%

50,00%

60,00%

70,00%

80,00%

90,00%

POLEGAR INDICADOR MÉDIO ANULAR MÍNIMO POLEGAR INDICADOR MÉDIO ANULAR MÍNIMO

DEDOS

PE

RC

EN

TA

GE

M

Arco

Presilha Interna

Presilha Externa

Verticilo

Anômalo

Cicatriz

Amputação

Page 62: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

62

5.6 Entendimento dos Dados

TIPOS FUNDAMENTAIS / MULHER

0,00%

10,00%

20,00%

30,00%

40,00%

50,00%

60,00%

70,00%

80,00%

90,00%

POLEGAR INDICADOR MÉDIO ANULAR MÍNIMO POLEGAR INDICADOR MÉDIO ANULAR MÍNIMO

DEDOS

PE

RC

EN

TA

GE

M

Arco

Presilha Interna

Presilha Externa

Verticilo

Anômalo

Cicatriz

Amputação

Page 63: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

63

5.6 Entendimento dos Dados

13,4%

68,6%

7,7%

10,3%

Arquivo 'A'

Arquivo 'B'

Arquivo 'C'

Arquivo 'D'

Page 64: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

Arquivo B 64

5.6 Entendimento dos Dados

Page 65: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

Arquivo C 65

5.6 Entendimento dos Dados

Page 66: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

66

5.7 Pré-processamento dos Dados Limpeza

Preenchimento de atributos. Registros duplicados. Valores faltantes (padronizar).

Seleção Excluir código de sub-classificação e dados de estrangeiros. Arquivos de treinamento e avaliação.

Enriquecimento Arquivo com cútis.

Formatação Adequação ao formato ARFF. Geração de MV (missing values) para avaliação.

em procedimento de complementação de dados faltantes.

Page 67: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

67

5.8 Avaliação

Formalismos Avaliados 10 classificadores (um para cada dedo)

Árvores de decisão; Redes bayesianas; Naive Bayes; Rede neural de retropropagação; CNM (modelo neural combinatório).

Page 68: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

68

5.8 Avaliação Seleção de Modelos

Page 69: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

69

5.8 Avaliação Arquivo A

Page 70: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

70

5.8 Avaliação Arquivo B

Page 71: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

71

5.8 Avaliação

Redes Neurais de Retropropagação Definição do número de épocas. Definição das taxas de aprendizagem () e

momento (). Definição do tamanho da camada oculta. Validação do número de épocas. Geração dos modelos para cada dedo.

Page 72: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

72

5.8 Avaliação Redes Neurais de Retropropagação

Page 73: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

73

5.8 Avaliação Redes Neurais de Retropropagação

Page 74: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

74

5.8 Avaliação Redes Neurais de Retropropagação

Page 75: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

Complementa valores faltantes apenas para casos mais óbvios! 75

5.8 Avaliação (Arquivo A) Complementação com 7 MV

Page 76: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

Falha ao complementar valores faltantes para casos não triviais. 76

5.8 Avaliação (Arquivo B) Complementação com 7 MV

Page 77: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

Melhora o desempenho se tem que complementar menos dados faltantes. 77

5.8 Avaliação (Arquivos A e B) Complementação com 3 MV

Page 78: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

78

5.9 Sistema Lupa Digital

Page 79: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

79

5.9 Sistema Lupa Digital Pesquisa “Não Conhece Mão”

Page 80: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

80

5.9 Sistema Lupa Digital Pesquisa “Conhece Mão”

Page 81: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

81

5.9 Sistema Lupa Digital Resultado de 4-33?? / ?-223?

Page 82: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

82

5.9 Sistema Lupa Digital Associação com Registros Federais

Page 83: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

83

5.9 Sistema Lupa Digital

Gera lista de RFs Pode ser utilizada pela solução AFIS para otimizar

a busca automatizada. Facilita o processo de conferência visual das

digitais. Gera lista de fórmulas ordenadas decrescente de

probabilidade. Orienta a busca manual.

Colhe estatísticas imediatas sobre as pesquisas requeridas.

Page 84: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

84

6. Conclusões e Resultados

Gera conhecimento no domínio. Divisão do MECA-Sinic nos grupos (A, B, C e D) Documentação do processo de mineração. Baixo desempenho da complementação de dedos

hipótese inicial refutada. adoção de solução “ad hoc” para o Lupa Digital

• Utilização dos atributos sexo, cútis e idade como filtros.• Busca com ordenação baseada no Teorema de Bayes.• Atende ao propósito inicial da pesquisa (otimização do

espaço de busca manual e automatizada).

Page 85: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

85

6. Conclusões e Resultados

Contribuição científica e social Aplicabilidade imediata dos benefícios da

ferramenta Lupa Digital no ambiente do DPF/INI. Disponibilização do UnBMiner, UnBBayes e

NNTK Contribui para solidar a comunidade brasileira de

pesquisadores em Inteligência Artificial e Incerteza Disponível via licença GNU GPL em

• http://sourceforge.net/projects/unbbayes

Page 86: 11/11/2005compsulmt 1 Construção e Avaliação de Modelos com o UnBMiner, Ferramenta Aberta para Mineração de Dados Marcelo Ladeira, Ph.D (mladeira@unb.br)

86