Universidade Federal do Pará
Programa de Pós Graduação em Engenharia
Elétrica - PPGEE
Mineração de Dados
Cláudio Alex Rocha
[email protected]
Sumário
Contextualização
Conceitos Básicos da Tarefa de Modelagens de
Dependências
Conceitos Básicos de Redes Bayesianas
Aprendizado de Redes Bayesianas
Inferência em Redes Bayesianas
Considerações Finais
Contextualização
As tarefas de MD podem ser divididas em duas
categorias:
– Atividades Preditivas
– Atividades Descritivas
Principais Tarefas de
Mineração de Dados
Mineração
de Dados
Atividades
Descritivas
Atividades
Preditivas
...
Classificação
Regressão
Associação
Modelagem
de Dependências
Clustering
Introdução
As Redes Bayesianas(RBs) são modelos
gráficos que codificam relacionamentos
probabilísticos entre variáveis de interesse
As principais motivações para o estudo e uso de
RBs para extração de conhecimento são:
– Aprendizado sobre relacionamento causais
– Manipulação efetiva de dados incompletos
– Combinação de conhecimento de fundo e o
conhecimento embutido nos dados
Manipulação de
Conhecimento Incerto
Problemas na manipulação de conhecimento incerto
– Dificuldade de manipular várias regras
– Ignorância teórica
– Ignorância prática
O conhecimento de um agente sobre determinado
domínio fornece apenas um grau de crença de uma
sentença
A principal ferramenta para manipular graus de crença é
a teoria da probabilidade, a qual associa um grau
numérico de crença entre 0 e 1 para as sentenças
Teoria da Probabilidade
A probabilidade fornece um meio de retratar a incerteza
advinda da dificuldade de manipular várias regras e das
ignorâncias teóricas e práticas
Uma probabilidade 0 de uma dada sentença
corresponde a inequívoca crença que ela é falsa.
Enquanto que probabilidade 1 corresponde a
inequívoca crença que ela é verdadeira
Probabilidades entre 0 e 1 corresponde a um grau de
crença intermediário de verdade da sentença
Teoria da Probabilidade (cont.)
Toda declaração probabilística deve indicar a evidência
que se refere a probabilidade que está sendo avaliada
Quando um agente recebe novas percepções, sua
avaliação probabilística deve ser atualizada para refletir
as novas evidências
Antes da evidência ser obtida, tem-se a probabilidade a
priori ou incondicional
Depois das evidências serem obtidas, tem-se a
probabilidade a posteriori ou condicional
Probabilidade a Priori
Notação: P(A)
A probabilidade a priori (P(A)), só deverá ser usada na
ausência de outra evidência
Ex: P(cárie) = 0.1 - significa que, como não há outra
informação, a probabilidade de um paciente ter cárie é
de 10%
Outro exemplo: tempo
P(tempo = chuvoso) = 0.28
P(tempo = ensolarado) = 0.7
P(tempo = frio) = 0.02
P(tempo) = (0.28, 0.7, 0.02) - distribuição probabilística
Probabilidade Condicional
Notação: P(A|B)
Quando se tem alguma evidência no domínio da
aplicação, a probabilidade condicional (P(A|B))
representa a probabilidade de A dado que tudo que se
conhece é B
Ex: P(cárie|dor_de_dente) = 0.8 - indica que se a única
evidência é que o paciente tem dor de dente, então a
probabilidade dele ter cárie será 0.8
P(A|B,C)
A probabilidade a priori é um caso especial da
probabilidade condicional - P(A|)
Probabilidade Condicional (cont.)
Probabilidade condicional pode ser definida em termos
da probabilidade a priori. Denotada pela equação:
P(A|B) = P(A,B) que pode ser escrita:
P(B)
P(A,B) = P(A|B) P(B) - regra do produto
“Para que A e B sejam verdadeiros é necessário B ser
verdadeiro e então A ser verdadeiro dado B”
A regra do produto também pode ser escrita:
P(A,B) = P(B|A) P(A)
Regra de Bayes
Dada as duas fórmulas da regra do produto:
P(A,B) = P(A|B) P(B)
P(A,B) = P(B|A) P(A)
Igualando e dividindo as equações por P(A), obtém-se:
P(B|A) = P(A|B) P(B)
P(A)
Esta equação é conhecida como Regra de Bayes (Lei de
Bayes ou Teorema de Bayes) que representa a base da
maioria dos sistemas de IA para inferência probabilística
Regra de Bayes (cont.)
Um caso simples: diagnóstico médico
– Suponha que a meningite cause, em 50% dos casos,
torcicolo em um paciente - P(T|M) = 0.5
– Suponha que a probabilidade de um paciente ter meningite P(M) = 1/50.000
– E a probabilidade de um paciente ter torcicolo - P(T) = 1/20
– Deseja saber P(M|T) ?
P(M|T) = P(T|M)P(M) = 0.5 x 1/50.000 = 0.0002
P(T)
1/20
Modelo de Representação
Para se efetuar inferências probabilísticas entre as variáveis
do domínio é necessário representar de alguma forma as
relações entre essas variáveis
Uma forma de representação é feita através da Distribuição
de Probabilidade Conjunta (DPC) das variáveis de interesse
=> P(X1,X2,...,Xn)
– Ex:
dor_de_dente ~dor_de_dente
cárie
~cárie
0,04
0,01
0,06
0,89
Modelo de Representação (cont.)
A representação via DPC se torna inviável quando há
um número elevado de variáveis a serem manipuladas
– Ex: para um domínio com 22 variáveis seria necessário
especificar (no mínimo) 222 entradas (parâmetros) para a
DPC.
As Redes Bayesianas provêem uma representação
concisa das dependências entre as variáveis do
domínio e proporcionam uma eficiente especificação da
DPC
Redes Bayesianas
Uma rede bayesiana é um grafo:
1) Que possui um conjunto de variáveis aleatórias que
representam os nós da rede
2) Que possui um conjunto de setas que ligam dois nós. Se
uma seta parte de um nó X para Y, diz-se que X
influencia diretamente Y
3) No qual cada nó possui uma Tabela de Probabilidade
Condicional (TPC) quantificando a dependência em
relação aos nós-pais
4) acíclico
Redes Bayesianas (cont.)
Exemplo de uma rede bayesiana para detecção de fraude
em compras com cartão de crédito:
p(i =<30) = 0,25
p(30<i<50) = 0,40
p(f=sim) = 0,0001
fraude
(f)
gasolina
(g)
p(g=sim|f=sim) = 0,2
p(g=sim|f=não) = 0,01
p(s=masculino) = 0,5
sexo
(s)
idade
(i)
jóias
(j)
p(j=sim|f=sim, i=*, s=*) = 0,05
p(j=sim|f=não, i<30,s=masculino) = 0,0001
p(j=sim|f=não, 30<i<50,s=masculino) = 0,0004
p(j=sim|f=não, i>=50,s=masculino) = 0,0002
p(j=sim|f=não, i=<30,s=feminino) = 0,0005
p(j=sim|f=não, 30<i<50,s=feminino) = 0,0002
p(j=sim|f=não, i>=50,s=feminino) = 0,001
Construção de Redes
Bayesianas (cont.)
Construção de RBs considerando apenas probabilidades
subjetivas:
1. Escolha um conjunto de variáveis relevantes
2. Escolha uma ordem para as variáveis
3. Enquanto existirem variáveis à esquerda:
3.1. Selecione uma variável Xi e adicione um nó correspondente a Xi para a rede
3.2. Fixe nós_pais(Xi) a partir de um conjunto mínimo de nós já contidos na rede,
tal que a independência condicional seja satisfeita
3.3. Defina a Tabela de Probabilidade Condicional para Xi
Ex: Hugin System desenvolvido por S. K. Andersen, K. G.
Olesen, F. V. Jensen e F. Jensen.
Aprendizado de Redes Bayesianas
O processo de aprendizado de RBs considera
dois fatores:
– Aprendizado (construção) da estrutura
– Aprendizado das probabilidades condicionais
Exs: Bayesian Knowledge Discoverer (BKD) e
Bayesware desenvolvidos por Marco Ramoni e
Paola Sebastiani da Open University.
Aprendizado de Redes Bayesianas (cont.)
Dados
+
Conhecimento
de Fundo
B
E
C
A
Indutor
D
B E P(A|B,E)
e b 0,90 0,10
e ~b 0,70 0,30
~e b 0,72 0,28
~e ~b 0,99 0,01
Inferência em
Redes Bayesianas
A tarefa básica de um sistema de inferência
probabilística é computar a distribuição da
probabilidade condicional para um conjunto de
variáveis de consulta, dado os valores de um conjunto
de variáveis de evidência .
P(variável_consulta|variável_evidência)
Ex: Qual a probabilidade de haver fraude (consulta)
dado sexo masculino e que houve compra de jóias
(evidências)
P(f = sim | s = masculino, j = sim)
Inferência em
Redes Bayesianas
A partir do Teorema de Bayes
P ( B | A) 
P ( A, B ) P ( A | B ) P ( B )

P ( A)
P ( A)
É possível visualizarmos, a partir da equação
abaixo, a situação em que A possua dois
valores(estados) possíveis:
Inferência em
Redes Bayesianas
Generalizando para os casos em A possua n
estados possíveis:
Exemplo de Inferência em
Redes Bayesianas
Exemplo de Inferência em
Redes Bayesianas
Aplicando o Teorema de Bayes:
P ( A^ B )
P ( B | A) 
P ( B | A) P ( A)  P ( B |~ A) P (~ A)
Exemplo de Inferência em
Redes Bayesianas
Para calcularmos a inferência anterior, é
necessário calcularmos as probabilidades a
partir da distribuição de probabilidade conjunta
das variáveis que compõem esta inferência e
considerando a independência condicional.
Por exemplo: cálculo de P(R ^ T ^ ~S)
Exemplo de Inferência em
Redes Bayesianas
Por exemplo: cálculo de P(R ^ T ^ ~S)
Tipos de Inferência em
Redes Bayesianas
Exemplo simples de uma rede bayesiana: sistema de alarme
contra arrombamento residencial (Los Angeles)
Arrombamento
P(ARR)
0,001
Alarme
Viz1-chama
A P(V1)
T 0,90
F 0,05
P(T)
0,002
Terremoto
ARR T
T T
T F
F T
F F
P(A)
0,95
0,94
0,29
0,001
Viz2-chama
A
P(V2)
T
F
0,70
0,01
Tipos de Inferência em
Redes Bayesianas (cont.)
Inferência por Diagnóstico (de efeito para causas)
– Ex.: P(Arrombamento|Viz1chama)
Inferência Causal (de causas para efeitos)
– Ex.: P(Viz1chama | Arrombamento)
Tipos de Inferência em
Redes Bayesianas (cont.)
Inferência Intercausal (entre causas de um efeito
comum)
Ex.: P(Arrombamento|Alarme,Terremoto)
Inferências Associadas (combina 2 ou mais inferências
já citadas)
Ex. 1: Uso simultâneo de inferência por diagnóstico e causal:
P(Alarme|Viz1chama,~Terremoto)
Ex. 2: Uso simultâneo de inferência intercausal e por
diagnóstico: P(Arrombamento|viz1chama,Terremoto)
Tipos de Inferência em
Redes Bayesianas (cont.)
C é uma variável de consulta e E uma variável de evidência
C
E
C
E
E
C
E
C
Diagnóstico
Causal
E
Intercausal
Associados
Considerações Finais
As RBs representam eficientemente as distribuições de
probabilidades via independência condicional
As RBs oferecem:
– Mecanismo de manipulação de bases de dados incompletas
– Representação e aprendizado via relacionamento causal
– Facilitam a combinação do conhecimento do domínio (ou a
priori) e o conhecimento embutido nos dados
Considerações Finais (cont.)
B
E
C
A
D
Aspectos Qualitativos
+
Independência
condicional (causalidade)
Grafo acíclico
• nós: variáveis randômicas (estados
mutuamente exclusivos e coletivamente
exaustivos)
• setas: influência direta (causal)
B E P(A|B,E)
e b 0,90 0,10
e ~b 0,70 0,30
~e b 0,72 0,28
~e ~b 0,99 0,01
Aspectos Quantitativos
Tabelas de Probabilidades
Condicionais
=
Distribuição de
Probabilidade
Conjunta
Considerações Finais (cont.)
Aprendizado de Redes Bayesianas
– Objetos não são associados para classes absolutamente
– Todos os atributos são potencialmente relevantes
– Geralmente requerem o conhecimento prévio de muitas
probabilidades
Inferência Bayesiana
– Auxilia o processo de tomada de decisões baseadas em
probabilidades da rede, quantificando, em termos
probabilísticos, os efeitos de determinados eventos.
– Realiza análises sensitivas para entender qual aspecto do
modelo tem maior impacto nas probabilidades das variáveis
de consulta
Sites de Interesse
http://www.kdnuggets.com
http://www.aic.nrl.navy.mil/~aha/research/machinelearning.html
http://www.ai.univie.ac.at/oefai/ml/ml-resources.html
http://www.hugin.dk/hugintro/
http://kmi.open.ac.uk/projects/bkd/
http://research.microsoft.com/scripts/pubdb/pubsasp.asp?
recordID=63
http://research.microsoft.com/scripts/pubdb/pubsasp.asp?
recordID=81