Classificadores Bayesianos
AULA 12
DATA MINING
Sandra de Amo
11/5/2015
Mestrado em Ciência da Computação
1
Classificadores Bayesianos



Classificadores estatísticos
Classificam um objeto numa determinada
classe C baseando-se na probabilidade do
objeto pertencer à classe C
Vantagens


11/5/2015
Processo de classificação rápido
Grande acurácia quando aplicados a grandes
volumes de dados.
Mestrado em Ciência da Computação
2
Classificador Bayesiano Simples

Hipótese: atributos não-classe são independentes


Valor de um atributo não influencia o valor de outros
atributos
Exemplo:



Idade, Profissão, Renda não são independentes. Um médico
tem uma probabilidade maior de ter uma renda alta do que um
porteiro.
Gênero, Cidade, Idade são independentes
Porque considerar atributos independentes ?

11/5/2015
Cálculos envolvidos no processo de classificação são
simplificados
Mestrado em Ciência da Computação
3
Como funciona um classificador
Bayesiano simples

Classificador Eager –


Constrói um modelo de classificação baseado em probabilidades
condicionais
Método geral



D = base de treinamento – (tuplas classificadas)
X = (a, b, c) : tupla não classificada
X pode ser vista como um evento conjunto


X é classificada na classe Ci se


11/5/2015
A=aeB=beC=c
P[Ci|X] > P[Cj|X] para todo j diferente de i
P[Ci|X] = probabilidade condicional do evento Classe= Ci acontecer
dado que o evento conjunto A = a e B = b e C = c acontece.
Mestrado em Ciência da Computação
4
Classificação de uma tupla X



Envolve o cálculo de todas as probabilidades
condicionais P[Ci|X] para todo i = 1,…,n,
onde n = número de classes
A probabilidade mais alta corresponde à
classe em que X será classificada
P[Ci|X] : Probabilidade Posterior
11/5/2015
Mestrado em Ciência da Computação
5
Como calcular as probabilidades posteriores ?
P[X ∩ C] = P[X|C] * P[C] = P[C|X] * P[X]
Teorema de Bayes P[C|X] = P[X|C] * P[C]
P[X]
P[X] é constante (pois X está fixa)
Para maximizar P[C|X] basta maximizar o numerador
P[X|C] * P[C]
11/5/2015
Mestrado em Ciência da Computação
6
Como maximizar P[X|C] * P[C]

P[C] é calculada através do banco de amostras

É preciso encontrar a classe C para a qual o produto
P[X|C] * P[C] é máximo

Como calcular P[X|C] ?

P[X|C] = P[A1=x1,A2=x2, ...,An = xn |C] onde X =
(x1, x2, ..., xn)
11/5/2015
Mestrado em Ciência da Computação
7
Classificador Bayesiano Naïve
Hipótese: Independência condicional dos atributos
A1,...,An dado C
A1, ..., An são ditos independentes dado C se
P[Ai=xi | A1=x1 ,..., Ai-1 =xi-1,...,An=xn,C] =
P[Ai=xi | C]
para todo i ϵ {1,...,n}
11/5/2015
Mestrado em Ciência da Computação
8
Corolário
A1, ..., An são independentes dado C se e somente se
P[A1=x1,A2=x2,... , An= xn |C] = P[A1=x1| C] * … * P[An=xn| C]
Prova: Aplicando o Teorema de Bayes para
P[A1=x1,A2=x2,... , An= xn,C] :
P[A1=x1,A2=x2,... , An= xn,C] = P[A1=x1,A2=x2,...,An = xn |C] . P[C]
P[A1=x1, A2=x2,... , An= xn,C] = P[A1=x1| A2=x2,...,An=xn, C]. P[A2=x2,...,An=xn,C]
Logo: P[A1=x1,A2=x2,...,An = xn |C] . P[C] = P[A1=x1| A2=x2,...,An=xn, C].
P[A2=x2,...,An=xn,C] =
P[A1=x1| A2=x2,...,An=xn, C]. P[A2=x2,...,An=xn|C]. P[C]
Logo: P[A1=x1,A2=x2,... An=xn |C] =
P[A1=x1| A2=x2,...,An=xn, C]. P[A2=x2, ...,An=xn|C] =
P[A1=x1| C]. P[A2=x2,..., An=xn|C]
(usando a condição de independência dos atributos A1, ...., An)
Repetindo o processo para P[A2=x2,...,An=xn|C] e assim por diante, concluimos a prova.
11/5/2015
Mestrado em Ciência da Computação
9
Cálculos
Cada P[Ai=xi | C ] é calculada da seguinte
maneira

Se Ai é atributo categórico
P[Ai=xi | C ] = P[Ai=xi,C ] / P[C] =
núm. de tuplas classificadas em C com Ai = xi
Total de tuplas classificadas em C
11/5/2015
Mestrado em Ciência da Computação
10
Cálculos

Se Ai é atributo contínuo (não categórico)
P[Ai=xi | C ] = g(Ai= xi, μ(C) , σ(C))
Onde g = função de distribuição de Gauss
μ(C) = média
σ(C) = desvio padrão
g(A= x, μ(C) , σ(C)) =
1
e
-(x- μ) 2
2
2σ
√2Π * σ
11/5/2015
Mestrado em Ciência da Computação
11
Resumo

Input:




um banco de tuplas classificadas
Uma tupla X a ser classificada
Output:
P[C1|X], P[C2|X], ..., P[Cn|X], onde C1,...,Cn
são todos os valores do atributo classe C

11/5/2015
A tupla X é classificada na classe Ci para a qual o
número P[Ci|X] é o maior.
Mestrado em Ciência da Computação
12
Compra-computador
Exemplo
ID
IDADE
RENDA
ESTUDANTE
CREDITO
CLASSE
1
≤ 30
Alta
Não
Bom
Não
2
≤ 30
Alta
Não
Bom
Não
3
31...40
Alta
Não
Bom
Sim
4
> 40
Média
Não
Bom
Sim
5
> 40
Baixa
Sim
Bom
Sim
6
> 40
Baixa
Sim
Excelente
Não
7
31...40
Baixa
Sim
Excelente
Sim
8
≤ 30
Média
Não
Bom
Não
9
≤ 30
Baixa
Sim
Bom
Sim
10
> 40
Média
Sim
Bom
Sim
11
≤ 30
Média
Sim
Excelente
Sim
12
31...40
Média
Não
Excelente
Sim
13
31...40
Alta
Sim
Bom
Sim
14
> 40
Média
Não
Excelente
Não
11/5/2015
Mestrado em Ciência da Computação
13
Exemplo









C1= sim, C2 = não
Tupla desconhecida X = (≤ 30, Média,Sim,Bom)
Precisamos maximizar P[X|Ci] * P[Ci] para i =1,2
P[C1] = 9/14 = 0.643
P[C2] = 5/14 = 0.357
P[Idade ≤ 30 | Compra = Sim ] = 2/9 = 0.222
P[Idade ≤ 30 | Compra = Não ] = 3/5 = 0.6
P[Renda = Média | Compra = Sim ] = 4/9 = 0.444
P[Renda = Média | Compra = Não ] = 2/5 = 0.4
11/5/2015
Mestrado em Ciência da Computação
14
Exemplo
P[Est = sim | Compra = Sim ] = 6/9 = 0.667
 P[Est = sim | Compra = Não ] = 1/5 = 0.2
 P[Crédito = bom| Compra = Sim ] = 6/9 = 0.667
 P[Crédito = bom | Compra = Não ] = 2/5 = 0.4
 P[X|C1] = 0.222*0.444*0.667*0.667 = 0.044
 P[X|C2] = 0.6*0.4*0.2*0.4 = 0.019
 P[X|C1]*P[C1] = 0.044*0.643 = 0.028
 P[X|C2]*P[C2] = 0.019*0.357 = 0.007
Tupla X classificada na classe C1 (compra computador = sim)

11/5/2015
Mestrado em Ciência da Computação
15
Redes Bayesianas de Crença
(Belief Bayesian Networks)


Utilizadas quando a probabilidade de um
atributo assumir um valor depende da
probabilidade de valores para os outros
atributos.
Não há independência entre os atributos
11/5/2015
Mestrado em Ciência da Computação
16
O que é uma rede bayesiana de crença ?

Um grafo dirigido acíclico
 Cada vértice representa um atributo
 Arestas ligando os vértices representam as dependências
entre os atributos.
y
x
X depende de Y

Y é pai de X
Tabela de Probabilidade Condicional (CPT) para cada
atributo Z
x
y
z
11/5/2015
P[Z |{X,Y}]
Mestrado em Ciência da Computação
CPT (Z)
17
Tabela CPT (Z)



Linhas : possíveis valores do atributo Z
Colunas : combinações possíveis de valores
dos pais de Z
Na posição (i,j) da tabela temos a
probabilidade condicional de Z ter o valor da
linha i e seus pais terem os valores
especificados na coluna j.
11/5/2015
Mestrado em Ciência da Computação
18
Tabela CPT(Z)
Valores de X = { 1, 3}
Valores de Y = {2,4}
Valores de Z = {5,6}
X
Y
Z
11/5/2015
X=1
Y=2
X=1
Y=4
X=3
Y=2
X=3
Y=4
Z=5
0.5
0.3
0.2
0.1
Z=6
0.5
0.7
0.8
0.9
Mestrado em Ciência da Computação
19
Como classificar usando uma Rede
Bayesiana de Crença

Input:




Uma Rede Bayesiana de Crença
Um atributo da rede selecionado como sendo o
atributo classe (pode haver diversos atributosclasse na rede)
Uma tupla X a ser classificada.
Output: P[C1|X], P[C2|X], ..., P[Cn|X]
11/5/2015
Mestrado em Ciência da Computação
20
Cálculo das probabilidades P[C|X]
Teorema de Bayes P[C|X] = P[X|C] * P[C]
P[X]
P[X] é constante (pois X está fixa)
Para maximizar P[C|X] basta maximizar o numerador
P[X|C] * P[C]
Como calcular P[X|C] quando existe dependência entre
os atributos da tupla X ?
11/5/2015
Mestrado em Ciência da Computação
21
Cálculos
P[X|C=Ci] * P[C=Ci] = P[X ∩ (C=Ci)] =
P[A1=x1 | pais(A1) ] * P[A2=x2 | pais(A2) ] * ...
* P[An = xn | pais(An) ]* P[C=Ci | pais(C) ]


Prova (Exercicio em aula)
Cada probabilidade conditional P[Ai=xi | pais(Ai) ] é
fornecida na CPT(Ai), presente no grafo da rede bayesiana de
input.
11/5/2015
Mestrado em Ciência da Computação
22
Exemplo
CPT(HF)
CPT(CP)
HF
CP
F
E
HF= 1
F=1
HF= 1
F=0
HF= 0
F=1
1
0.8
0.5
0.7
0.1
0
0.2
0.5
0.3
0.9
CPT(E)
RX+
D
HF =história familiar
F = fumante
CP = câncer de pulmão
11/5/2015
F= 0
1
0.03
0.2
0
0.97
0.8
1
0.05
0
0.95
CPT(F)
CPT(RX+)
F=1
E = Efisema
D = Dispnéia
RX+ = raio X +
HF
HF= 0
F=0
F
CP=1
CP=0
1
0.9
0.02
0
0.1
0.98
1
0.35
0
0.65
CPT(D)
E=1, CP=1 E=1, CP=0 E=0, CP=1 E=0, CP=0
1
0
0.99
0.2
0.3
0.01
0.01
0.8
0.7
0.99
Mestrado em Ciência da Computação
23
Cálculos
X = (HF=1, F=1, E = 0, RX+ = 1, D=0)
P[X|CP=i] * P[CP=i] =
P[HF=1] * P[F=1] * P[E=0 | F=1] * P[RX=1 |CP=i]*
P[D=0 |CP=i, E=0] * P[CP=i | HF = 1, F=1).
Para maximizar P[X|CP=i] * P[CP=i] basta maximizar
P[RX=1 |CP=i]* P[D=0 |CP=i, E=0] * P[CP=i | HF = 1, F=1)
11/5/2015
Mestrado em Ciência da Computação
24
Problema de Classificação

Input:

Um conjunto de amostras classificadas
Output: Uma rede bayesiana de crença
é preciso descobrir :



a topologia da rede e
as tabelas de probabilidade CPT
Classificador = Rede Bayesiana
11/5/2015
Mestrado em Ciência da Computação
25
Exercício
HF
F
E
D
RX+
CP
1
1
0
0
1
1
1
0
0
1
1
0
0
1
0
1
1
1
1
1
1
0
0
1
0
0
1
0
0
0
0
1
0
0
1
0
0
0
0
0
1
1
0
0
1
1
0
1
0
1
0
1
1
0
1
1
1
0
1
0
Considere a rede bayesiana do
slide 23 e os casos reais à esquerda.
Pede-se a curva ROC deste
classificador.
26
11/5/2015
Mestrado em Ciência da Computação
Treinamento de uma Rede Bayesiana

Se a topologia da rede é conhecida e dispõe-se de um banco
de dados de amostras, então o treinamento consiste em
computar as tabelas CPT(Z) para cada atributo Z.

Como descobrir a topologia da rede ?



Especialistas no domínio: especificam as dependências e as
probabilidades condicionais.
Métodos automáticos: algoritmos extraem (aprendem) uma rede de
crença a partir de um banco de dados de amostras.
Técnicas de aprendizagem da topologia da rede:


11/5/2015
Algoritmo K2 (um dos pioneiros)
Algoritmos genéticos, MDL, etc
Mestrado em Ciência da Computação
27
Referências

Uma introdução
D. Heckerman. Bayesian Networks for Knowledge Discovery. In U. M. Fayyad,
G. Piatetsky-Shapiro, P. Smyth, R. Uthurusamy Editors. Advances in
Knowledge Discovery and Data Mining, pages 273-305. MIT Press, 1996.

Treinamento de Rede de Crença
G. F. Cooper, E. Herskovits. A Bayesian Method for the Induction of Probabilistic
Networks from Data. Machine Learning, 9, 309-347 (1992).
Livro: Finn V. Jensen, Thomas D. Nielsen: Bayesian Networks and Decision
Graphs. 2nd Edition. Springer, 2007. Capítulo 7: Learning the Structure of
Bayesian Networks.
11/5/2015
Mestrado em Ciência da Computação
28