A Systematic Approach for Inducing Reliable Classifiers From Data Mines David Moises Barreto dos Santos Universidade Federal de Campina Grande Programa

A Systematic Approach for Inducing Reliable Classifiers

From Data Mines

David Moises Barreto dos Santos

Universidade Federal de Campina GrandePrograma de Pós-Graduação em Informática

Mineração de DadosJulho 2003

RoteiroIntroduçãoConceitos BásicosCaracterização do ProblemaAlgoritmos

Naive_InducerExpert_Inducer

ConclusõesBibliografia

IntroduçãoBancos de dados têm se tornado minas de conhecimento

Mal exploradas pelas consultas rotineiras de usuáriosA mineração de dados (MD) é a área de pesquisa preocupada em explorar minas de uma forma melhor

Descoberta de padrõesNão-triviaisConfiáveisFacilmente assimiláveis

O agente de mineração é chamado Minerador

IntroduçãoModelos de representação de padrões modelos de conhecimento

Regras de AssociaçãoRegras de Classificação

if C then T

Um modelo de regras de classificação é

denominado classificador

conjunção de termos <atributo Θ valor>

único termo com o atributo pré-determinado (atributo de classificação) <atributo_classificação Θ classe>

IntroduçãoA literatura trata de diversos algoritmos de indução de regras de classificação, e aspectos pontuais do processo de MDO processo de MD é muito complexo

Não existe a melhor técnica de amostragemBanco de DadosTécnica de fragmentaçãoAlgoritmo de induçãoConhecimento instável

Técnicas de fragmentação geram diferentes pares Conjunto de treinamento-Conjunto de teste

Conclusão: Não existe uma técnica universal para MD, seja amostragem, fragmentação ou indução modelo de conhecimento

Motivação – O Problema do Processo de MD

Banco de DadosPlantação de Soja

Amostragem: ConvergenceFragmentação: K-fold Cross-ValidationIndução: NaiveBayes

Minerador 1

Amostragem: Adaptive Incremental FrameworkFragmentação: BootstrapIndução: ID3

Minerador 2

Classificador 1 Classificador 2Necessidade de uma ferramenta que garanta o

melhor classificador levando em conta a diversidade de técnicas

(talvez seja bastante!!!)

A Idéia Central da Ferramenta Proposta

Técnicas de amostragemTécnicas de fragmentação

Algoritmos de indução

Melhor Classificad

orProblema de Classificação

Utilização de heurísticas para reduzir o custo de exploração das diversas técnicas

Implementação de um framework orientado a objeto permitir que novas técnicas sejam incorporadas com o

mínimo de impacto sobre o restante do framework

Algoritmo que infere o melhor classificador

Fragmentação

XeXc

Xctr Xcts

X

Algoritmo de Fragmentação

Xc é um banco de dados classificado

Xe é um conjunto de execução, ou um

conjunto de instâncias não classificadas.

Xctr Xc

Xcts Xc

Xctr Xcts = Xc Xctr Xcts =

Xc Xe = Xc Xe = X

O Processo de MD

Extrair amostra

Xctr Xcts = Xc

Fragmentar amostraXctr , Xcts

Induzir classificado

rXctr C

Calcular acurácia de

testeC Xcts

Computar acurácia

estimada (Xe)

Processo de Mineração de Dados

Preparação dos dados

Técnicas de amostragemAdaptive Incremental Framework

Convergence

Técnicas de fragmentação

HoldoutBootstrap

Algoritmo de indução

PrismNaiveBayes

Tratamento de dados

DesconhecidosInexistentes

Sujos

O Processo de MD

Extrair amostra

Xctr Xcts = Xc



rXctr C


testeC Xcts

Computar acurácia

estimada (Xe)



O classificador deve ser testado com cada instância do conjunto de teste Xcts

O teste bem sucedido: quando o classificador mapeia a instância para uma classe que é a mesma classe da instância no conjunto de teste

Fórmula para calcular a acurácia:, instância Xcts

)__()__(

)__(sucedidosbemtestessucedidosmaltestes

sucedidosbemtestesaccts

O Processo de MD

Extrair amostra

Xctr Xcts = Xc



rXctr C


testeC Xcts

Computar acurácia

estimada (Xe)



A acurácia de execução, acce, é calculada em função de accts, considerando um determinado grau de confiança z N é o número de instâncias utilizadas para o cálculo da acurácia de

teste accts

)(2442

2

222

zNaccNzaccNzaccN

acc tststse

)65,1(2465,1465,12

2

222

N

accNaccNaccNacc tststs

e

Para uma confiança de 90%, z=1,65

Algoritmo Naïve_InducerInvestiga exaustivamente todas as técnicas disponíveis, de todos os tipos (Ingênuo)Escolhe o melhor classificador

Melhor acurácia estimada de execução

A1

A2

F1

F2

F3

I1I2I3

Experimentos com Naïve_Inducer

BD Descrição Atributos Instâncias Classes acce (90%)

Letter Caracteres manuscritos 17 20000 26 77.20% 0.43% 75.77% 78.18%

Splice Seqüências de DNA 61 3100 3 92.55% 1.27% 89.79% 93.75%

Mushroom Espécies de cogumelos 22 8124 2 99.39% 0.32% 94.40% 99.82%

Soybean Cultivo de soja 35 683 19 92.03% 1.50% 86.73% 95.28%

Titanic Naufrágio do transatlântico Titanic 4 2201 2 99.58% 0.08% 97.99% 99.50%

Connect-4 Partidas de Connect-4 43 36991 3 100.00% 0.00% 99.79% 100.00%

Cmc Escolha do método anticoncepcional 10 1473 3 98.18% 5.45% 97.26% 98.54%

Kr-vs-Kp Partidas de Xadrez 36 3196 2 55.14% 0.84% 52.14% 57.82%

Cars Informações sobre automóveis 10 404 3 96.95% 0.98% 95.12% 96.72%


































Uma mesma pessoa pode escrever um caractere de várias formas, bem diferentes entre si

Caracteres iguais manuscritos por pessoas diferentes podem apresentar grandes diferenças

A indução de padrões genéricos torna-se difícil

Instâncias repetidas com classes diferentes – uma espécie de ruído


Baseado no ranking pode-se concluir que

As diversas combinações de técnicas tem uma forte influência nas acurácias dos classificadores

“O que é bom para um banco de dados não é necessariamente

bom para outro banco de dados”Desvantagem

Alto custo processamento

VantagemMelhor Classificador(matematicamente)

http://dsc.ufcg.edu.br/~david/mineracao/seminario.html

Algoritmo Expert_Inducer

80%82%84%86%88%90%92%94%96%98%

100%

AIF

- BS

- ID

3

Con

v - B

S - I

D3

AIF

- CV

- ID

3

Con

v - C

V - I

D3

AIF

- HO

- ID

3

Con

v - H

O -

ID3

AIF

- BS

- Nai

ve

Con

v - B

S - N

aive

AIF

- CV

- Nai

ve

Con

v - C

V - N

aive

AIF

- HO

- N

aive

Con

v - H

O -

Nai

ve

AIF

- BS

- One

R

Con

v - BS

- O

neR

AIF

- CV

- One

R

Con

v -

CV

- One

R

AIF

- HO

- O

neR

Con

v - H

O -

One

R

AIF

- BS

- Pris

m

Con

v - B

S - P

rism

AIF

- CV

- Pris

m

Con

v - C

V - P

rism

AIF

- HO

- Pr

ism

Con

v - H

O - P

rism

Banco de Dados: Mushroom


80%82%84%86%88%90%92%94%96%98%

100%

AIF

- BS

- ID

3

Con

v - B

S - I

D3

AIF

- CV

- ID

3

Con

v - C

V - I

D3

AIF

- HO

- ID

3

Con

v - H

O -

ID3

AIF

- BS

- Nai

ve

Con

v - B

S - N

aive

AIF

- CV

- Nai

ve

Con

v - C

V - N

aive

AIF

- HO

- N

aive

Con

v - H

O -

Nai

ve

AIF

- BS

- One

R

Con

v - BS

- O

neR

AIF

- CV

- One

R

Con

v -

CV

- One

R

AIF

- HO

- O

neR

Con

v - H

O -

One

R

AIF

- BS

- Pris

m

Con

v - B

S - P

rism

AIF

- CV

- Pris

m

Con

v - C

V - P

rism

AIF

- HO

- Pr

ism

Con

v - H

O - P

rism



80%82%84%86%88%90%92%94%96%98%

100%

AIF

- BS

- ID

3

Con

v - B

S - I

D3

AIF

- CV

- ID

3

Con

v - C

V - I

D3

AIF

- HO

- ID

3

Con

v - H

O -

ID3

AIF

- BS

- Nai

ve

Con

v - B

S - N

aive

AIF

- CV

- Nai

ve

Con

v - C

V - N

aive

AIF

- HO

- N

aive

Con

v - H

O -

Nai

ve

AIF

- BS

- One

R

Con

v - BS

- O

neR

AIF

- CV

- One

R

Con

v -

CV

- One

R

AIF

- HO

- O

neR

Con

v - H

O -

One

R

AIF

- BS

- Pris

m

Con

v - B

S - P

rism

AIF

- CV

- Pris

m

Con

v - C

V - P

rism

AIF

- HO

- Pr

ism

Con

v - H

O - P

rism



80%82%84%86%88%90%92%94%96%98%

100%

AIF

- BS

- ID

3

Con

v - B

S - I

D3

AIF

- CV

- ID

3

Con

v - C

V - I

D3

AIF

- HO

- ID

3

Con

v - H

O -

ID3

AIF

- BS

- Nai

ve

Con

v - B

S - N

aive

AIF

- CV

- Nai

ve

Con

v - C

V - N

aive

AIF

- HO

- N

aive

Con

v - H

O -

Nai

ve

AIF

- BS

- One

R

Con

v - BS

- O

neR

AIF

- CV

- One

R

Con

v -

CV

- One

R

AIF

- HO

- O

neR

Con

v - H

O -

One

R

AIF

- BS

- Pris

m

Con

v - B

S - P

rism

AIF

- CV

- Pris

m

Con

v - C

V - P

rism

AIF

- HO

- Pr

ism

Con

v - H

O - P

rism



80%82%84%86%88%90%92%94%96%98%

100%

AIF

- BS

- ID

3

Con

v - B

S - I

D3

AIF

- CV

- ID

3

Con

v - C

V - I

D3

AIF

- HO

- ID

3

Con

v - H

O -

ID3

AIF

- BS

- Nai

ve

Con

v - B

S - N

aive

AIF

- CV

- Nai

ve

Con

v - C

V - N

aive

AIF

- HO

- N

aive

Con

v - H

O -

Nai

ve

AIF

- BS

- One

R

Con

v - BS

- O

neR

AIF

- CV

- One

R

Con

v -

CV

- One

R

AIF

- HO

- O

neR

Con

v - H

O -

One

R

AIF

- BS

- Pris

m

Con

v - B

S - P

rism

AIF

- CV

- Pris

m

Con

v - C

V - P

rism

AIF

- HO

- Pr

ism

Con

v - H

O - P

rism


Heurística 1: Se a técnica de amostragem A1 tem resultados melhores que

as outras técnicas de amostragem para o banco de dados X em uma certa combinação de técnicas de fragmentação e indução, então a vantagem de A1 sobre as outras técnicas de amostragem pode ser assumida para X, independentemente das outras combinações com as demais técnicas de fragmentação e indução.


80%82%84%86%88%90%92%94%96%98%

100%

AIF

- BS

- ID

3

Con

v - B

S - I

D3

AIF

- CV

- ID

3

Con

v - C

V - I

D3

AIF

- HO

- ID

3

Con

v - H

O -

ID3

AIF

- BS

- Nai

ve

Con

v - B

S - N

aive

AIF

- CV

- Nai

ve

Con

v - C

V - N

aive

AIF

- HO

- N

aive

Con

v - H

O -

Nai

ve

AIF

- BS

- One

R

Con

v - BS

- O

neR

AIF

- CV

- One

R

Con

v -

CV

- One

R

AIF

- HO

- O

neR

Con

v - H

O -

One

R

AIF

- BS

- Pris

m

Con

v - B

S - P

rism

AIF

- CV

- Pris

m

Con

v - C

V - P

rism

AIF

- HO

- Pr

ism

Con

v - H

O - P

rism



80%82%84%86%88%90%92%94%96%98%

100%

AIF

- BS

- ID

3

Con

v - B

S - I

D3

AIF

- CV

- ID

3

Con

v - C

V - I

D3

AIF

- HO

- ID

3

Con

v - H

O -

ID3

AIF

- BS

- Nai

ve

Con

v - B

S - N

aive

AIF

- CV

- Nai

ve

Con

v - C

V - N

aive

AIF

- HO

- N

aive

Con

v - H

O -

Nai

ve

AIF

- BS

- One

R

Con

v - BS

- O

neR

AIF

- CV

- One

R

Con

v -

CV

- One

R

AIF

- HO

- O

neR

Con

v - H

O -

One

R

AIF

- BS

- Pris

m

Con

v - B

S - P

rism

AIF

- CV

- Pris

m

Con

v - C

V - P

rism

AIF

- HO

- Pr

ism

Con

v - H

O - P

rism



80%82%84%86%88%90%92%94%96%98%

100%

AIF

- BS

- ID

3

Con

v - B

S - I

D3

AIF

- CV

- ID

3

Con

v - C

V - I

D3

AIF

- HO

- ID

3

Con

v - H

O -

ID3

AIF

- BS

- Nai

ve

Con

v - B

S - N

aive

AIF

- CV

- Nai

ve

Con

v - C

V - N

aive

AIF

- HO

- N

aive

Con

v - H

O -

Nai

ve

AIF

- BS

- One

R

Con

v - BS

- O

neR

AIF

- CV

- One

R

Con

v -

CV

- One

R

AIF

- HO

- O

neR

Con

v - H

O -

One

R

AIF

- BS

- Pris

m

Con

v - B

S - P

rism

AIF

- CV

- Pris

m

Con

v - C

V - P

rism

AIF

- HO

- Pr

ism

Con

v - H

O - P

rism



80%82%84%86%88%90%92%94%96%98%

100%

AIF

- BS

- ID

3

Con

v - B

S - I

D3

AIF

- CV

- ID

3

Con

v - C

V - I

D3

AIF

- HO

- ID

3

Con

v - H

O -

ID3

AIF

- BS

- Nai

ve

Con

v - B

S - N

aive

AIF

- CV

- Nai

ve

Con

v - C

V - N

aive

AIF

- HO

- N

aive

Con

v - H

O -

Nai

ve

AIF

- BS

- One

R

Con

v - BS

- O

neR

AIF

- CV

- One

R

Con

v -

CV

- One

R

AIF

- HO

- O

neR

Con

v - H

O -

One

R

AIF

- BS

- Pris

m

Con

v - B

S - P

rism

AIF

- CV

- Pris

m

Con

v - C

V - P

rism

AIF

- HO

- Pr

ism

Con

v - H

O - P

rism


Heurística 2: Se a técnica de fragmentação F1 tem resultados melhores que

as outras técnicas de fragmentação para o banco de dados X em uma certa combinação que esteja presente a melhor técnica de amostragem para X, a vantagem de F1 sobre as outras técnicas de fragmentação pode ser assumida para X, independentemente dos algoritmos de indução.


80%82%84%86%88%90%92%94%96%98%

100%

AIF

- BS

- ID

3

Con

v - B

S - I

D3

AIF

- CV

- ID

3

Con

v - C

V - I

D3

AIF

- HO

- ID

3

Con

v - H

O -

ID3

AIF

- BS

- Nai

ve

Con

v - B

S - N

aive

AIF

- CV

- Nai

ve

Con

v - C

V - N

aive

AIF

- HO

- N

aive

Con

v - H

O -

Nai

ve

AIF

- BS

- One

R

Con

v - BS

- O

neR

AIF

- CV

- One

R

Con

v -

CV

- One

R

AIF

- HO

- O

neR

Con

v - H

O -

One

R

AIF

- BS

- Pris

m

Con

v - B

S - P

rism

AIF

- CV

- Pris

m

Con

v - C

V - P

rism

AIF

- HO

- Pr

ism

Con

v - H

O - P

rism



80%82%84%86%88%90%92%94%96%98%

100%

AIF

- BS

- ID

3

Con

v - B

S - I

D3

AIF

- CV

- ID

3

Con

v - C

V - I

D3

AIF

- HO

- ID

3

Con

v - H

O -

ID3

AIF

- BS

- Nai

ve

Con

v - B

S - N

aive

AIF

- CV

- Nai

ve

Con

v - C

V - N

aive

AIF

- HO

- N

aive

Con

v - H

O -

Nai

ve

AIF

- BS

- One

R

Con

v - BS

- O

neR

AIF

- CV

- One

R

Con

v -

CV

- One

R

AIF

- HO

- O

neR

Con

v - H

O -

One

R

AIF

- BS

- Pris

m

Con

v - B

S - P

rism

AIF

- CV

- Pris

m

Con

v - C

V - P

rism

AIF

- HO

- Pr

ism

Con

v - H

O - P

rism



80%82%84%86%88%90%92%94%96%98%

100%

AIF

- BS

- ID

3

Con

v - B

S - I

D3

AIF

- CV

- ID

3

Con

v - C

V - I

D3

AIF

- HO

- ID

3

Con

v - H

O -

ID3

AIF

- BS

- Nai

ve

Con

v - B

S - N

aive

AIF

- CV

- Nai

ve

Con

v - C

V - N

aive

AIF

- HO

- N

aive

Con

v - H

O -

Nai

ve

AIF

- BS

- One

R

Con

v - BS

- O

neR

AIF

- CV

- One

R

Con

v -

CV

- One

R

AIF

- HO

- O

neR

Con

v - H

O -

One

R

AIF

- BS

- Pris

m

Con

v - B

S - P

rism

AIF

- CV

- Pris

m

Con

v - C

V - P

rism

AIF

- HO

- Pr

ism

Con

v - H

O - P

rism


Heurística 3: Considerando a melhor técnica de amostragem (Heurística 1)

e a melhor técnica de fragmentação (Heurística 2). Se o algoritmo de indução I1 tem resultados melhores que os outros algoritmos de indução para o banco de dados X em uma certa combinação que esteja presente a melhor técnica de amostragem e a melhor técnica de fragmentação para X, então pode-se então assumir que I1 é o melhor algoritmo de indução para X.

Algoritmo Expert_InducerOutros oito bancos de dados foram testados

Foi utilizado o mesmo raciocínio

As conclusões foram similares a obtida no banco de dados Mushroom

Algoritmo Expert_InducerUtiliza as heurísticas

O Expert_Inducer executa A+F+I iterações

O Naïve_Inducer executa AxFxI iterações

BD Descrição Atributos Instâncias Classes

Cars-Evolution Avaliação de automóveis 8 1728 4

Nursery Escola Infantil 8 12960 5

Tic-tac-toe Jogo Tic-tac-toe 10 953 2

Experimentos com Expert_Inducer

Naïf-bestClassifier Expert-BestClassifier

O melhor classificador para

Melhores técnicas

- Tempo Melhores técnicas

- Tempo

Cars-Evolution AIF – BS – Prism

89,76% 1’56’’ AIF – CV – ID3 87,08 1’10’’

Nursery AIF – CV – ID3

90,56% 9’52 AIF – CV – ID3 89,89% 6’23’’

Tic-tac-toe AIF – CV - Prism

97,05% 2’56’’ AIF – CV – Prism

97,08% 1’49’’








Melhores técnicas


- Tempo


89,76% 1’56’’ AIF – CV – ID3 87,08 1’10’’


90,56% 9’52 AIF – CV – ID3 89,89% 6’23’’


97,05% 2’56’’ AIF – CV – Prism

97,08% 1’49’’

Ambos algoritmos possuem desempenhos similares








Melhores técnicas


- Tempo


89,76% 1’56’’ AIF – CV – ID3 87,08 1’10’’


90,56% 9’52 AIF – CV – ID3 89,89% 6’23’’


97,05% 2’56’’ AIF – CV – Prism

97,08% 1’49’’

Apesar de haver uma divergência quanto a melhor combinação em Cars-Evolution, isto não compromete o desempenho








Melhores técnicas


- Tempo


89,76% 1’56’’ AIF – CV – ID3 87,08 1’10’’


90,56% 9’52 AIF – CV – ID3 89,89% 6’23’’


97,05% 2’56’’ AIF – CV – Prism

97,08% 1’49’’

A técnica de fragmentação Cross-Validation seleciona aleatoriamente as instâncias da amostraPor isso, há uma diferença entre as acurácias dos classificadores induzidos por uma mesma combinação de técnicas








Melhores técnicas


- Tempo


89,76% 1’56’’ AIF – CV – ID3 87,08 1’10’’


90,56% 9’52 AIF – CV – ID3 89,89% 6’23’’


97,05% 2’56’’ AIF – CV – Prism

97,08% 1’49’’

O tempo de processamento de Expert_Inducer foi sempre menor que Naive_Inducer

ConclusãoAutomatização do processo de mineração de dadosNovas técnicas podem ser incorporadas ao framework com o mínimo de impacto sobre as outras partes do próprio frameworkAs heurísticas permitem uma boa performance da combinação de técnicas sem perda de qualidadeO trabalho não trata outros modelos de conhecimento como regras de associaçãoNão está integrado com SGBDs

BibliografiaTOEBE, Josué; SAMPAIO, Marcus. A Systematic Approach for Inducing Reliable Classifiers From Data Mines.

Documents

A Systematic Approach for Inducing Reliable Classifiers From Data Mines David Moises Barreto dos Santos Universidade Federal de Campina Grande Programa