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) =
k
Σ (0.632*Acc(Mi)test-set + 0.368*Acc(Mi)train-set )
i=1
Um outro classificador Eager:
Redes Neurais
AULA 8 – Parte II
Data Mining
Sandra de Amo
Redes Neurais
I1
Conjunto de unidades
I2
2
input
I3
3
w32
Camada de
Input
11/5/2015
output
Camada
Camada de
Intermediária Output
Mestrado em Ciencia da Computacao
Conceito de Neurônio
Artificial
Cada vértice de uma camada é
ligado a todos os vértices da
camada seguinte.
10
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).
11/5/2015
Mestrado em Ciencia da Computacao
11
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

11/5/2015
Mestrado em Ciencia da Computacao
12
Camadas de Input e de Output
Output



Número de neurônios = número de classes
Se número de classes = 2




11/5/2015
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.
Mestrado em Ciencia da Computacao
13
Rede Neural e Classificação
x0
x1
w0j
w1j
∑
+ θj
tendência
w2j
INPUT Ij
na unidade j
x2
Pesos
Outputs da
Camada precedente
Média ponderada
dos outputs recebidos
Função de Ativação
Output Oj
11/5/2015
Mestrado em Ciencia da Computacao
14
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))
11/5/2015
Mestrado em Ciencia da Computacao
15
Backpropagation – Fase de IDA
I1
C1
δ1
1?
I2
C2
δ2
0?
I3
C3
δ3
0?
Classe C1
11/5/2015
Mestrado em Ciencia da Computacao
16
Backpropagation – Fase de Volta
I1
I2
C1
ww1212
ww2222
ww3232
w12
w22
w32
I3
C3
Ajusta pesos
11/5/2015
C2
Ajusta pesos
Mestrado em Ciencia da Computacao
17
Condições de Parada

Epoca = tempo necessário para que todas as
amostras sejam analisadas.

Processo se repete até que:



11/5/2015
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.
Mestrado em Ciencia da Computacao
18
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.
11/5/2015
Mestrado em Ciencia da Computacao
19
Ida : Como são calculados os outputs
I1
I2
w1i
w2i
i
Oi
w3i
I3
Oi = F( w1i*I1 + w2i*I2 + w3i*I3 + θi )
F(x) = 1/(1+e-x)
11/5/2015
Mestrado em Ciencia da Computacao
20
Volta: Cálculo dos Erros
 Erro em unidade da última camada
i
Ei = δi(1- δi)(Ti – δi)
 Erro em unidade da camada intermediária
E’i = Oi(1- Oi)(E1*wi1+E2*wi2+E3wi3)
11/5/2015
Mestrado em Ciencia da Computacao
δi Compara
com Ti =
classe
verdadeira
0, 1, 2 ..?
wi1
1
i wi2
2
wi3
3
21
Reajustes dos pesos e tendências
Novo peso wij
wij
i
j
Novo-wij = Velho-wij + λ EjOi
Nova Tendência θj
Novo-θj = Velho- θj + λ Ej
λ = Taxa de Aprendizado
λ(t) = 1/t
t = iteração atual
Evita que o processo fique parado num “mínimo local”
11/5/2015
Mestrado em Ciencia da Computacao
22
Exemplo
1
1
w14
4
w24
0
W14
w46
6
2
w34
1
Amostra classificada na classe C = 1
3
W15
5 w56
w14
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
11/5/2015
Mestrado em Ciencia da Computacao
23
Exemplo

Ida
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
Volta
11/5/2015
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
Mestrado em Ciencia da Computacao
24
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
11/5/2015
Mestrado em Ciencia da Computacao
25
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
11/5/2015
Mestrado em Ciencia da Computacao
26
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.
11/5/2015
Mestrado em Ciencia da Computacao
27
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.
11/5/2015
Mestrado em Ciencia da Computacao
28
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 ?
11/5/2015
Mestrado em Ciencia da Computacao
29
Vantagens e Desvantagens





Fase de treinamento demorada
Muitos parâmetros, determinados empiricamente
Fraca interpretabilidade
Alta tolerância a ruídos
Resultados Confiáveis
11/5/2015
Mestrado em Ciencia da Computacao
30
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.


11/5/2015
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.
Mestrado em Ciência da Computação
31
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


11/5/2015
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.
Mestrado em Ciência da Computação
32
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
11/5/2015
Mestrado em Ciência da Computação
33