Mineração de dados
Classificação: outros algoritmos
Apresentação baseada:
no livro Introduction to Data Mining (Tan, Steinbach, Kumar) e
em apresentações do prof.
José Todesco (UFSC)
Naive Bayes

Abordagem estatística, baseada no teorema de
Bayes . Naïve (ingênuo) porque considera que os
atributos são independentes.
Naïve Bayes – visão geral
Seja o exemplo de dados:
Os objetos podem ser classificados em vermelho ou verde
Como há mais objetos verdes que vermelhos, a probabilidade a priori é que um
novo objeto seja verde
Probabilidade a priori de verde = número de objetos verdes/ número total de objetos =
40/60 = 4/6
Probabilidade a priori de vermelho = número de objetos vermelhos / número total de
objetos = 20/60 = 2/6
Naïve Bayes – visão geral

Queremos classificar um novo objeto X (ponto branco)

Como os objetos estão agrupados, é razoável considerar que quanto
mais objetos de uma classe houver “parecidos” com X, maior a
chance de X ser daquela classe.

Vamos considerar o “parecido” pelo círculo na figura (estar dentro do
círculo) e calcular a probabilidade:

Probabilidade de “parecido” dado que é verde = número de objetos
verdes no círculo/ número total de verdes= 1/40

Probabilidade de “parecido” dado que é vermelho = número de
objetos vermelhos no círculo/ número total de vermelhos= 3/20
Naïve Bayes – visão geral

Na análise Bayesiana, a classificação final é realizada considerando
estas duas informações usando a probabilidade condicional do
Teorema de Bayes:

A probabilidade condicional de X ser verde dado que é “parecido” =
probabilidade a priori de verde vezes Probabilidade de “parecido”
dado que é verde =
4/6 . 1/40 = 1/60

Analogamente,

A probabilidade condicional de X ser vermelho dado que é “parecido”
= 2/6 . 3/20 = 1/20

Portanto, a classe predita de X seria vermelho, pois é a maior
probabilidade
Mais tecnicamente….

Aprendizagem da classificação: qual é a probabilidade da classe dado
um exemplo?
– Evidência E = exemplo (registro, com os valores dos atributos)
– Hipótese H = valor da classe para o exemplo

Teorema de Bayes (1763):
P(E|H).P(H)
P( H| E) =
P(E)

Suposição do classificador bayesiano ingênuo: evidência pode ser
separada em partes independentes (os atributos do exemplo)
P(E1 ,E2 ,...,En | H) =P(E1 |H ).P( E2|H)... .P(En |H )
P( H| E) = P( E1 |H ).P( E2 | H)... .P(En | H).P(H )
P( E1 ).P( E2)... .P(En)
Exemplo:Naive Bayes
Dia
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Aspecto Temperatura Umidade
Sol
Quente
Alta
Sol
Quente
Alta
Nublado
Quente
Alta
Chuva
Agradável
Alta
Chuva
Fria
Normal
Chuva
Fria
Normal
Nublado
Fria
Normal
Sol
Agradável
Alta
Sol
Fria
Normal
Chuva
Agradável
Normal
Sol
Agradável
Normal
Nublado
Agradável
Alta
Nublado
Quente
Normal
Chuva
Agradável
Alta
Vento
Fraco
Forte
Fraco
Fraco
Fraco
Forte
Forte
Fraco
Fraco
Fraco
Forte
Forte
Fraco
Forte
7
Decisão
N
N
S
S
S
N
S
N
S
S
S
S
S
N
Exemplo: Naive Bayes
Qual será a decisão (valor da classe), se o dia
estiver com sol, a temperatura fria, a umidade
alta e o vento forte ?
P(Jogar = S | Aspecto = Sol, Temperatura = Fria,
Umidade = Alta e Vento = Forte) = ?
P(Jogar = N | Aspecto = Sol, Temperatura = Fria,
Umidade = Alta e Vento = Forte) = ?
8
Exemplo: Naive Bayes
P( H| E) =
P( E1 |H ).P( E2 | H)... .P(En | H).P(H )
P( E1 ).P( E2)... .P(En)
P(Jogar = S | Aspecto = Sol, Temperatura = Fria,
Umidade = Alta e Vento = Forte) =
P( Sol|S) * P( Fria|S) * P(Alta|S) * P(Forte|S) * P(S)
=
P( Sol) * P( Fria) * P(Alta)* P(Forte)
Exemplo: Naive Bayes
P(Jogar = S) = 9/14; P(Jogar = N) = 5/14;
P(Aspecto = Sol | Jogar = S) = 2/9;
P(Aspecto = Sol | Jogar = N) = 3/5;
P(Temperatura = Fria | Jogar = S) = 3/9;
P(Temperatura = Fria | Jogar = N) = 1/5;
P(Umidade = Alta | Jogar = S) = 3/9;
P(Umidade = Alta | Jogar = N) = 4/5;
P(Vento = Forte | Jogar = S) = 3/9;
P(Vento = Forte | Jogar = N) = 3/5;
10
Exemplo: Naive Bayes
P(Aspecto = Sol ) = 5/14
P(Temperatura = Fria) = 4/14
P(Umidade = Alta ) = 7/14
P(Vento = Forte ) = 6/14
11
Exemplo: Naive Bayes
P(Jogar = S | Aspecto = Sol, Temperatura = Fria,
Umidade = Alta e Vento = Forte) =
=
P( Sol|S) * P( Fria|S) * P(Alta|S) * P(Forte|S) * P(S)
P( Sol) * P( Fria) * P(Alta)* P(Forte)
=
= (2/9 * 3/9 * 3/9 * 3/9 * 9/14) / (5/14 * 4/14 * 7/14 * 6/14) =
= 0,0053 / 0,02186 = 0,242
12
Exemplo: Naive Bayes
P(Jogar = N | Aspecto = Sol, Temperatura = Fria, Umidade
= Alta e Vento = Forte) =
P( Sol|N) * P( Fria|N) * P(Alta|N) * P(Forte|N) * P(N)
=
=
P( Sol) * P( Fria) * P(Alta)* P(Forte)
= (3/5 * 1/5 * 4/5 * 3/5 * 5/14) / (5/14 * 4/14 * 7/14 * 6/14) =
= 0,0206 / 0,02186 = 0,942
Como (J=N) 0,942 > (J=S) 0,242 Então Jogar = Não
13
O problema da frequência zero
• Se um valor de atributo nunca ocorrer para uma classe
(como por exemplo Aspecto=nublado para a classe N)
– A probabilidade será zero! P(nublado | N) = 0
– A probabilidade a posteriori será zero,
independentemente dos outros valores! P(N | E) = 0
• Solução: Estimador de Laplace ⇒ somar 1 à contagem de
todas as combinações de classe e valor de atributo.
• Resultado: as probabilidades nunca serão zero!
Naïve Bayes

Vantagens:
– rápido
– Bons resultados em dados reais

Desvantagens:
– Resultados não tão bons em problemas complexos

Mozilla Thunderbird e Microsoft Outlook usam
classificadores naive bayes para filtrar (marcar)
emails que seriam spam
Máquina de Vetores de Suporte [Vapnik et al, 1998]
Em inglês: Support Vector Machine (SVM)
 Método matemático, baseado no Teorema de
Lagrange

Conceitos de SVM

Qual o hiperplano ótimo para separar duas
classes
– Menor erro de classificação
– Maior margem
Distância
entre vetores de suporte e o hiperplano
Conceitos de SVM

Qual o hiperplano ótimo?
– Menor erro de classificação
– Maior margem
Distância
entre vetores de suporte e o hiperplano
SVM

Vantagens:
– Classificador não-linear poderoso

Desvantagens:
– Demorado para gerar o modelo e para executar
– sensível a ruídos
– a escolha dos parâmetros influencia muito o resultado
kNN: k - Nearest Neighbor

k vizinhos mais próximos

Método simples que consiste em procurar o (para
k=1) ou os (para k>1) registros mais próximos
(parecidos) com aquele para o qual se deseja
saber a classe
K- Nearest Neighbor (vizinho mais próximo)
Método antigo [Cover 1967] e muito difundido
 Instâncias são representadas por pontos num
espaço n dimensional n

instância x = <a1(x), a2(x), a3(x), ..., an(x)>
Onde ar(x) representa o valor do r-ésimo atributo
A distância entre as instâncias pode ser
calculada pela distância euclidiana ou outras

d ( xi , x j ) 
n
2
(
a
(
x
)

a
(
x
))
 r i r j
r 1
K- Nearest Neighbor (k-NN)

O resultado da classificação é aquele que
aparecer mais vezes entre os k vizinhos mais
próximos.
K- Nearest Neighbor (k-NN)
Exemplo:
A classificação de ?, (F(?)), será a classificação de
Xi (F(Xi)), onde Xi é a instancia mais próxima de ?.
Se k=1, na figura, ? seria classificado como
Se k=7, na figura, ? seria classificado como
K-NN: Exemplo
x = (idade(x), altura(x), peso(x), classe(x)), onde a classe pode ser “S” ou “N”



Dados classificados:
 josé = (30, 1.78, 72, S)
 maria = (25, 1.65, 60, S)
 anastácia = (28, 1.60, 68, N)
Dado a classificar:
 joão = (36, 1.80, 76, ???)
Usar k=1
Cálculo das distâncias:

d(joão,josé) = [(36-30)2 + (1.80-1.78)2 + (76-72)2]1/2 = (36+0.0004+16)1/2 = 7,21

d(joão,maria) = (121+0.0225+256)1/2 = 19,41

d(joão, anastácia) = (64+0.04+64)1/2 = 11,32
Portanto a classe de João é S, pois é a classe de José, que é o mais
“próximo” de João
K-NN
 Problema
da dimensionalidade (muitos atributos)
 Para calcular a distância entre os pontos, o
método utiliza todos os atributos da instância
 Conseqüências:
 pode custar caro
 atributos irrelevantes podem deturpar a
classificação
 Como não gera um modelo e sim compara
sempre com todos os registros, pode ser lento
Redes Neurais
Exemplo de perceptron
+1
w0 = -1,5
x1
w1 = +1
S
x2
+1
u
w2 = +1
y=
prof. Luis Otavio Alvares
1 se u > 0
0 se u  0
y
Perceptron (cont.)
perceptron computa uma função binária de
suas entradas
 vários perceptrons podem ser combinados
para computar funções mais complexas
 o perceptron pode aprender a computar tudo
o que ele computa

prof. Luis Otavio Alvares
Perceptron (cont.)

pode-se descrever um algoritmo de
aprendizagem como:
– se o perceptron dispara quando não deve
disparar, diminua cada wi de um número
proporcional a xi;
– se o perceptron deixa de disparar quando
deveria, aumente cada wi de um número
proporcional a xi.
prof. Luis Otavio Alvares
Regra de aprendizagem do perceptron
W(n+1) = W(n) + η * (D(n)-Y(n)).X(n)
–
–
–
–
–
onde:
η é a constante de correção do erro
D é a saída desejada
Y é a saída fornecida
X é o vetor de entrada
W é o vetor de pesos
prof. Luis Otavio Alvares
Características das RNA





grande número de elementos de
processamento muito simples, inspirados nos
neurônios biológicos
um grande número de conexões ponderadas
entre os elementos (neurônios artificiais)
os pesos das conexões codificam o
conhecimento de uma rede neural;
controle altamente distribuído e paralelo;
ênfase na aprendizagem automática.
prof. Luis Otavio Alvares
Elementos de processamento (neurônios)
Os elementos de processamento das redes
neurais artificiais são os neurônios artificiais
 Cada neurônio recebe um padrão de entrada e
produz um único valor de saída (necessita
apenas de informações locais)
 A saída é função apenas das entradas e dos
pesos das conexões

prof. Luis Otavio Alvares
Organização em camadas
As redes neurais são formadas por um
conjunto de neurônios organizados em três
camadas:
– camada de entrada - onde os padrões são
apresentados à rede (dados de entrada da rede)
– camadas intermediárias ou escondidas - onde é
realizada a maior parte do processamento.
– camada de saída - onde o resultado final é
concluído e apresentado.
prof. Luis Otavio Alvares
Organização em camadas
prof. Luis Otavio Alvares
Processamento da informação: entrada

cada entrada corresponde a um atributo simples

o valor de um atributo é a entrada na rede.

redes neurais
números

atributos qualitativos ou imagens, por exemplo,
precisam antes ser transformados em valores
numéricos
artificiais
processam
prof. Luis Otavio Alvares
apenas
Processamento da informação: saída
a saída da rede é a solução do problema
 por exemplo, se o resultado deve ser “sim” ou
“não”, a rede atribui valores numéricos, por
exemplo 1 para sim e 0 para não

prof. Luis Otavio Alvares
Processamento da informação: conexão

liga dois neurônios e possui um peso

o peso expressa a importância relativa dada à
entrada antes do processamento:
 Se o peso for positivo a conexão é dita
excitatória
 se for negativo é dita inibitória
 Se o peso for zero é como se a conexão não
existisse.
prof. Luis Otavio Alvares
Processamento da informação: função de limiar

é a responsável pela determinação da forma e
da intensidade de alteração dos valores de saída
prof. Luis Otavio Alvares
Aprendizagem

Uma das principais características das redes neurais
é a capacidade de aprendizagem automática

processo de aprendizagem = treinamento da rede

função de aprendizado: modelo matemático utilizado
no treinamento da rede

separação dos dados existentes sobre o problema
em dois conjuntos.
– um para treinar a rede (ajustar os seus pesos)
– outro para validação.
prof. Luis Otavio Alvares
O número de características (variáveis, atributos)
Quanto maior o número de variáveis de entrada, maior deverá ser a rede
neural, aumentando o risco de supertreinamento da rede e necessidade
de maior número de registros de treinamento.
O tempo necessário para treinar uma rede está diretamente relacionado
com o número de variáveis de entrada usadas na mesma; quanto mais
características (variáveis) são usadas, maior é o tempo para a rede
convergir.
Um grande problema é que quanto mais aumenta o número de variáveis de
entrada, a chance da rede convergir para uma solução de qualidade
inferior aumenta.
Descartar características que não tenham poder preditivo ajuda a aumentar
o poder preditivo da rede neural. Tente outras variáveis e verifique quais
delas melhora a rede. Em muitos casos é necessário calcular novas
variáveis que representam aspectos particulares do problema. Por
exemplo, R$/m2.
Pode-se usar outras técnicas para determinar quais características são
importantes para o propósito de predição. Pode-se usar, por exemplo:
40
correlações ou árvores de decisão.
O número de exemplos de treinamento
Geralmente, quanto mais características há na rede
neural, mais exemplos de treinamento são necessários
para abranger os padrões nos dados.
Geralmente um mínimo de poucas centenas de
exemplos são necessários para cada característica.
Quando o tamanho do arquivo de treinamento não é
grande o suficiente, a rede tende a decorar os dados.
41
O número de saídas
Por exemplo, se a rede neural vai ser usada para detectar eventos
(saídas) raros e caros, tais como: falhas de turbinas de avião, uso
fraudulento do cartão de crédito; então é preciso ter certeza que o
arquivo de treinamento tem um número suficiente de exemplos
desses eventos raros.
Uma amostra aleatória dos dados disponíveis não é suficiente, pois
os exemplos não raros (comuns) vão “afundar” os exemplos raros.
Para contornar este problema, o arquivo de teste precisa ter muitos
exemplos raros. Por exemplo, tomar 10.000 “bons” exemplos e
10.000 “maus” exemplos.
42
Preparando os dados
Preparar os dados de entrada é freqüentemente a parte mais complicada
do uso de uma rede neural.
Uma parte do problema é a transformação das variáveis de tal forma que
os seus valores fiquem normalizados.
43
Rede Neural Backpropagation (MLP)

Este classificador é uma rede neural que realiza
a aprendizagem (determinação dos pesos dos
neurônios) com o algoritmo backpropagation

Algumas características:
–
–
–
–
–
Todas as entradas devem ser numéricas
Tempo de geração do modelo longo
Rápido para classificar uma instância
Tolerante a ruídos
Método não linear poderoso
Figura obtida em http://blog.peltarion.com/2006/07/10/classifier-showdown/
Figura obtida em http://blog.peltarion.com/2006/07/10/classifier-showdown/
Figura obtida em http://blog.peltarion.com/2006/07/10/classifier-showdown/
Figura obtida em http://blog.peltarion.com/2006/07/10/classifier-showdown/
Referências

Tan,P-N;Steimbach, M; Kumar,V. Introduction to Data Mining.
Boston: Addison Wesley, 2006. 769p.

Vapnik, V. Statistical LearningTheory. Wiley, 1998.

George H. John and Pat Langley. Estimating Continuous
Distributions in Bayesian Classifiers. Proceedings of the Eleventh
Conference on Uncertainty in Artificial Intelligence. pp. 338-345.
Morgan Kaufmann, San Mateo, 1995.

Cover T.M., Hart P.E. Nearest neighbor pattern classification. IEEE
Transactions on Information Theory. 13 (1): 21–27, 1967.
Exercício
Considerando os dados de treinamento abaixo, realizar os cálculos de
probabilidade e aplicar o classificador Naive-Bayes, para atribuir a classe para o
registro:
Id
Casa
própria
1
S
Solteiro
alto
NÃO
2
N
Casado
médio
NÃO
3
N
Solteiro
baixo
NÃO
4
S
Casado
alto
NÃO
5
N
Divorc.
médio
SIM
6
N
Casado
baixo
NÃO
7
S
Divorc.
alto
NÃO
8
N
Solteiro
médio
SIM
9
N
Casado
baixo
NÃO
10
N
Solteiro
médio
SIM
Mau
EstCivil Rendim. Pagador
Casa
Própria
Estado
Civil
Rendim.
Mau
pagador
N
Divorc.
médio
?
10
P( H| E) =
P( E1 |H ).P( E2 | H)... .P(En | H). P(H)
P( E1 ).P( E2)... .P(En)
10
50
Exercício

Considerando os dados de treinamento abaixo, realizar os cálculos e
aplicar o classificador k-NN, para atribuir a classe para o registro,
considerando k=1 e k=3:
atrib1
atrib2
classe
atrib1
atrib2
classe
11
20
S
8
18
?
12
21
S
9
19
S
5
18
N
6
19
N
6
20
N