Classificação
Redes Neurais
AULA 11
DATA MINING
Sandra de Amo
11/4/2015
Mestrado em Ciencia da Computacao
1
Redes Neurais
I1
Conjunto de unidades
I2
2
input
I3
3
w32
Camada de
Input
11/4/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.
2
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/4/2015
Mestrado em Ciencia da Computacao
3
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/4/2015
Mestrado em Ciencia da Computacao
4
Camadas de Input e de Output
Output



Número de neurônios = número de classes
Se número de classes = 2




11/4/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
5
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/4/2015
Mestrado em Ciencia da Computacao
6
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/4/2015
Mestrado em Ciencia da Computacao
7
Backpropagation – Fase de IDA
I1
C1
δ1
1?
I2
C2
δ2
0?
I3
C3
δ3
0?
Classe C1
11/4/2015
Mestrado em Ciencia da Computacao
8
Backpropagation – Fase de Volta
I1
I2
C1
ww1212
ww2222
ww3232
w12
w22
w32
I3
C3
Ajusta pesos
11/4/2015
C2
Ajusta pesos
Mestrado em Ciencia da Computacao
9
Condições de Parada

Epoca = tempo necessário para que todas as
amostras sejam analisadas.

Processo se repete até que:



11/4/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
10
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/4/2015
Mestrado em Ciencia da Computacao
11
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/4/2015
Mestrado em Ciencia da Computacao
12
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/4/2015
Mestrado em Ciencia da Computacao
δi Compara
com Ti =
classe
verdadeira
0, 1, 2 ..?
wi1
1
i wi2
2
wi3
3
13
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/4/2015
Mestrado em Ciencia da Computacao
14
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/4/2015
Mestrado em Ciencia da Computacao
15
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/4/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
16
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/4/2015
Mestrado em Ciencia da Computacao
17
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/4/2015
Mestrado em Ciencia da Computacao
18
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/4/2015
Mestrado em Ciencia da Computacao
19
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/4/2015
Mestrado em Ciencia da Computacao
20
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/4/2015
Mestrado em Ciencia da Computacao
21
Vantagens e Desvantagens





Fase de treinamento demorada
Muitos parâmetros, determinados empiricamente
Fraca interpretabilidade
Alta tolerância a ruídos
Resultados Confiáveis
11/4/2015
Mestrado em Ciencia da Computacao
22
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/4/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
23
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/4/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
24
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/4/2015
Mestrado em Ciência da Computação
25