Técnicas de Amostragem : como avaliar a acurácia de um classificador AULA 8 – Parte I Data Mining Sandra de Amo

Técnicas de Amostragem : como avaliar a acurácia de

um classificador

AULA 8 – Parte I

Data Mining

Sandra de Amo

Holdout Método Holdout

Considera-se um banco de dados de amostras Divide-se em 2 partes : D1 e D2 D1 é 2 vezes maior do que D2 Acurácia= número de tuplas de D2 bem classificadas

dividido pelo total de tuplas de D2 Subamostragem Randômica

Variação do método Holdout Método Holdout é repetido k vezes Acurácia geral = média das acurácias em cada rodada

Cross-Validation Validação Cruzada (k-fold Cross-validation)

Dados iniciais são particionados em k partes D1,..., Dk de tamanhos aproximados

Treinamento e testes são executados k vezes. Em cada iteração i (i=1...k) Di é escolhido para teste e o restante das

partições são utilizadas como treinamento. Cada tupla de amostra é utilizada o mesmo número de vezes como

tupla de treinamento e uma única vez como tupla de teste. Acurácia de um classificador = número total de tuplas bem

classificadas nas k iterações dividido pelo total de tuplas no banco de dados original.

Acurácia de um preditor = Soma dos erros dividido nas k iterações dividido pelo total de tuplas no banco de dados original.

Variantes do Cross-validation Leave-one-out

Caso especial de k-fold cross validation Cada Di tem um único elemento Em cada iteração somente 1 tupla é utilizada para teste.

Cross-validation estratificada As “folhas” D1, ... , Dk são tais que a distribuição das

classes em cada folha é aproximadamente igual à distribuição nos dados iniciais.

Ex: se em D a proporção de tuplas das classes C1 e C2 é de 2 para 1 então esta proporção é mantida em cada “folha” Di.

Bootstrap A cada vez que uma tupla é selecionada para

participar do grupo de treinamento, ela volta novamente para o banco inicial, podendo ser novamente selecionada na próxima vez.

Bancos de treinamento e testes podem conter tuplas repetidas.

.632 Bootstrap Banco de dados original com d tuplas Os sorteios de tuplas são realizados d vezes. Ao final de d sorteios temos um banco D1 de

treinamento (boostrap sample) e um banco D2 de testes.

A amostra de treinamento D1 tem exatamente d elementos.

.632 Bootstrap É bem provável que alguma tupla t do banco original

ocorre repetida em D1. Qual a probabilidade de uma tupla não estar no

banco de treinamento D1 no final dos d sorteios ? (1 – 1/d)d

lim (1 – 1/d)d = 1/e (para d infinito) e = 2.718 1/e = 0,368 36,8% das tuplas não são escolhidas: formam o conj. D2 63,2% das tuplas são escolhidas: formam o boostrap D1

Acurácia medida com o Boostrap Repete-se o processo de amostragem k vezes Em cada vez construimos D1 e D2 e medimos a acurácia do

classificador (ou preditor) M Acc(Mi)test-set = acurácia de M calculada na iteração i, com D2

como teste e D1 como treinamento Acc(Mi)train-set = acurácia de M calculada na iteração i, com

dados originais como teste e D1 como treinamento. Acurácia(M) =

Σ (0.632*Acc(Mi)test-set + 0.368*Acc(Mi)train-set )i = 1

k

Um outro classificador Eager: Redes Neurais

AULA 8 – Parte II

Data Mining

Sandra de Amo

04/11/23 Mestrado em Ciencia da Computacao 10

Redes Neurais

2

I1

I3

I2

Camada Intermediária

Camada de Output

Camada de Input

w323

Conjunto de unidades

input output

Conceito de Neurônio Artificial

Cada vértice de uma camada éligado a todos os vértices da camada seguinte.


Como definir a topologia da rede ? Topologia: número de camadas intermediárias, número de

neurônios nas camadas intermediárias e inicialização dos pesos e tendências.

Topologia ideal : Processo de tentativa e erro Número de camadas intermediárias pode ser maior do que 1 Mais comum: uma única camada intermediária Se a rede treinada é julgada não confiável, repete-se o

processo de treinamento com outra topologia e outros pesos e tendências iniciais

Diversas técnicas automáticas foram propostas para se encontrar a topologia ideal da rede (produzindo os resultados com maior acuracia).


Camadas de Input e de Output Input

Se atributos não são categorizados Um neurônio para cada atributo Valores dos atributos são normalizados entre 0 e 1.

Se atributos são categorizados NAi = número de valores do atributo Ai Total de neurônios da camada inicial =

NA1 + NA2 + NA3 + ... + NAm

onde {A1, A2, ..., Am} = conjunto dos atributos


Camadas de Input e de Output Output

Número de neurônios = número de classes Se número de classes = 2

número de neurônios = 1 Basta um único neurônio na camada de output para o

treinamento da rede. Supõe-se que este neurônio corresponde à classe 1 Se a amostra está na classe 0, então o output correto

deveria ser 0. Se a amostra está na classe 1, o output correto deveria ser 1.


Rede Neural e Classificação

∑ INPUT Ij na unidade j

+ θj

w0j

w1j

w2j

x0

x2

x1

Output Oj

Função de AtivaçãoOutputs da Camada precedente

Pesos Média ponderadados outputs recebidos

tendência


Função de Ativação Serve para normalizar os outputs que são

calculados em cada neurônio. É uma função não-linear, diferenciável. Normalmente, utiliza-se a função:

f(x) = 1/(1+ex)

cuja derivada satisfaz

f ’(x) = f(x) (1 – f(x))


Backpropagation – Fase de IDA

I1

I3

I2

C1

C2

C3

Classe C1

δ1

δ2

δ3

1 ?

0 ?

0 ?


Backpropagation – Fase de Volta

I1

I3

I2

C1

C2

C3

Ajusta pesos

w22

w32

w12w12

w32

w22

Ajusta pesos

w22

w32

w12w12

w32

w22


Condições de Parada Epoca = tempo necessário para que todas

as amostras sejam analisadas.

Processo se repete até que: Os reajustes dos pesos são “muito pequenos”. Só uma “pequena” porcentagem de amostras foi

mal classificada pela rede. Um número “máximo” de épocas foi atingido.


Backpropagation Objetivo: obter uma rede neural treinada

Centenas de milhares de épocas são necessárias

para a convergência dos pesos.

Teoricamente, convergência não é garantida.

Na prática, os pesos convergem depois de um grande número de épocas.


Ida : Como são calculados os outputs

I1

I2

I3

iw2i

w3i

w1i

Oi = F( w1i*I1 + w2i*I2 + w3i*I3 + θi )

Oi

F(x) = 1/(1+e-x)


Volta: Cálculo dos Erros

δi Erro em unidade da última camada Comparacom Ti = classeverdadeira0, 1, 2 ..?

Ei = δi(1- δi)(Ti – δi)

i

i2

3

wi1

wi2

wi3

E’i = Oi(1- Oi)(E1*wi1+E2*wi2+E3wi3)

Erro em unidade da camada intermediária1


Reajustes dos pesos e tendências Novo peso wij

wiji j

Novo-wij = Velho-wij + λ EjOi

Nova Tendência θj

λ = Taxa de Aprendizado λ(t) = 1/t

Evita que o processo fique parado num “mínimo local”

Novo-θj = Velho- θj + λ Ej

t = iteração atual


Exemplo1

0

1

1

2

3

4

5

6

w14

w24

w34

w46

w56

w14

Amostra classificada na classe C = 1

W14 W15 W24 W25 W34 W35 W46 W56 θ4 θ5 θ6

0.2 -0.3 0.4 0.1 -0.5 0.2 -0.3 -0.2 -0.4 0.2 0.1


Exemplo Ida

Volta

Unidade Input Output

4 0.2 + 0 – 0.5 – 0.4 = - 0.7 1/1+e0.7 = 0.332

5 -0.3 + 0 + 0.2 + 0.2 = 0.1 1/1+e-0.1 = 0.525

6 (-0.3)(0.332) – (0.2)(0.525) + 0.1 = - 0.105 1/1+e0.105 = 0.474

Unidade Erro

6 (0.474)(1 - 0.474)(1 - 0.474) = 0.1311

5 (0.525)(1 - 0.525)( 0.1311)(-0.2) = -0.0065

4 (0.332)(1 - 0.332)( 0.1311)(-0.3) = -0.0087


Exemplo : Erros E6 = (0.474)(1-0.474)(1-0.474) = 0.1311

E5 = (0.525)(1-0.525)(0.1311)(-0.2) = -0.0065

E4 = (0.332)(1-0.332)(0.1311)(-0.3) = -0.0087


Ex: Ajustes dos Pesos e Tendênciasλ = 0.90

Antigo Valor Reajustado

W46 = -0.3 -0.3 + (0.90)(0.1311)(0.332) = -0.261

w56 = -0.2 -0.2 + (0.90)(0.1311)(0.525) = -1.138

w14 = 0.2 0.2 + (0.90)(-0.0087)(1) = 0.192

w15 = -0.3 -0.3 + (0.90)(-0.0065)(1) = -0.306

w24 = 0.4 0.4 + (0.90)(-0.0087)(0) = 0.4

w25 = 0.1 0.1 + (0.90)(-0.0065)(0) = 0.1

w34 = -0.5 -0.5 + (0.90)(-0.0087)(1) = -0.508

w35 = 0.2 0.2 + (0.90)(-0.0065)(1) = 0.194

θ6 = 0.1 0.1 + (0.90)(1.1311) = 0.218

θ5 = 0.2 0.2 + (0.90)(-0.0065) = 0.194

θ4 = -0.4 -0.4 + (0.90)(-0.0087) = -0.408


Ajustes dos pesos e tendências : Modo Padrão

Modo Padrão (ou case updating) A cada nova amostra analisada é feito o ajuste dos pesos e

tendências na fase de volta. Os pesos e tendências atualizados são utilizados na fase

da ida para a amostra seguinte. Em cada época os pesos e tendências são ajustados N

vezes, onde N = total de amostras.

Ajustes dos pesos e tendências : Modo Batch Modo Batch (ou epoch updating)

Para cada amostra armazena-se os erros Ej obtidos na fase da volta, para cada neurônio Nj (das camadas de output e intermediárias).

No final da época (quando todas as amostras foram analisadas), calcula-se para cada neurônio intermediário ou da camada de output a média dos erros calculados em cada iteração.

Utiliza-se estes erros médios dos neurônios para ajustar os pesos e tendências no final da época.

Assim em cada época os pesos e tendências são ajustados uma única vez.

Análise: O modo padrão é o mais utilizado na prática, produz resultados mais acurados do que o modo batch.



Classificação por Backpropagation Input: um banco de dados de treinamento

(amostras) Output: uma rede neural treinada

Problema: Como extrair “regras de classificação” de uma rede neural treinada ?


Vantagens e Desvantagens Fase de treinamento demorada Muitos parâmetros, determinados empiricamente Fraca interpretabilidade

Alta tolerância a ruídos Resultados Confiáveis

04/11/23 Mestrado em Ciência da Computação 31

Redes Neurais como classificadores Classificadores robustos – boa acurácia mesmo em

presença de ruídos. Acurácia muito superior à acurácia de classificadores

baseados em árvores de decisão. Problemas

Processo lento, exige diversas tentativas para encontrar topologia adequada.

Resultados da classificação = uma rede treinada. Pouca utilidade num ambiente de grande volume de dados Importante que o resultado seja em forma de regras Busca de tuplas satisfazendo as condições de uma regra pode ser

feita usando SQL.


Poda de um rede neural – por que ? Uma rede treinada é totalmente conectada Muitos nós e muitos links ! Impossível de extrair regras concisas que

sejam úteis e significativas para os usuários possam facilmente ser transformadas em consultas de

uma linguagem de banco de dados Fase da Poda: Objetivos

remoção de links e nós sem afetar a taxa de erro da rede. obtenção de uma rede com um número pequeno de nós e

links, dos quais é possível extrair-se regras concisas e compreensíveis para o usuário final.


Referências S.M.Weiss, C.A. Kulikowski: Computer Systems that Learn: Classification and Prediction

Methods from Statistics, Neural Nets, Machine Learning and Expert Systems. San Mateo, CA, Morgan Kaufmann, 1991.

H. Lu, R. Setiono, H. Liu: NeuroRule: A Connectionist Approach to Data Mining. VLDB 1995, pp. 478-489.

http://www.vldb.org/conf/1995/P478.PDF

Rudy Setiono - A Penalty-function Approach for Pruning Feedforward Neural Networks (1997). Neural Computation, 1997, Vol. 9, pages 185-204.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.5249

Leitura interessante: Rede Neural simula o modelo de aprendizagem do cérebro humano ?? Asin Roy: Artificial Neural Networks: A Science in Trouble. SIGKDD Explorations, Vol. 1,

Issue 2, Jan. 2000, 33-38.

http://www.sigkdd.org/explorations/issues/1-2-2000-01/roy.pdf

Documents

Técnicas de Amostragem : como avaliar a acurácia de um classificador AULA 8 – Parte I Data Mining Sandra de Amo