ALGORITMO CBL-B
Para utilizar o algoritmo CBL-B seleciona a opcao IC->CBL-B
Este algoritmo aprende uma rede Bayesiana a partir da distribuição de probabilidades P derivada da amostra e usa a informação mútua,
marginal e condicional para mensurar a dependência entre variáveis.
A diferença entre o CBL-A e o CBL-B, é que o primeiro necessita que seja feita uma ordenação a priori das variáveis, e o segundo infere tal
ordenação dos dados. Ambos assumem que os dados não possuem valores ausentes. O algoritmo CBL-A é o seguinte:
Algoritmo:
|
Esboçar:
P1. Inicializa n<- |X| ; Vs <- {0,1,2,3,...,n-1}; Es<-← {} ; Leia o limite ε; P2. Ms Ms<- {(m,a,b) | a,bЄV, a<b, m <- I(a,b), m>ε} Ls<- Ordenação(Ms, >, m); P3. Para cada (m,a,b) em Ls, faça Se não há Caminhos(a, b, Es,"n"), então { Es<← {{a,b}}UEs ; e, Ls <- Ls – {(m,a,b)} }; |
Alargar:
P4. Para cada (m,a,b) em Ls, Faça Se PrecisaConectar(a,b,Es,"n"), então Es<- {{a,b}}UEs ; |
Refinar:
P5. Para cada {a, b} em Es, faça Es <- Es –{{a, b}}; Se há Caminhos(a, b, Esx,"n") e não PrecisaConectar(a,b,Es,"n"), então Es<-Esx; |
Orientar:
P6. Para cada a,b,c em Vs, faça % Acha as estruturas-v Se ({a,b},Z)<-Separadores e c.Z, Ou ({a,b},Z).Separadores,então Es <- (Es - {{a,c},{b,c}}) ∪ {(a,c),(b,c)}; P7. Para cada a,b,c em Vs, faça % aplica a regra 1-CBL Se (a,b)<- Es, {b,c}<-Es, a e c não são adjacentes, então Es<- (Es - {{b,c}}) ∪ {(b,c)} ; P8. Para cada {a, b} em Es, faça % Aplique a regra 2-CBL Se há um caminho(a, b, Es, "o"), então Es<- (Es - {{a, b}}) ∪ {(a, b)} P9. Para cada {a,b} em Es, faça Es<-← (Es - {{a, b}}) ∪ {OrientaçãoUsuário(a,b)}; |
Precisa Conectar:
Função PrecisaConectar(a, b, Es, tipo) Global: Separadores 1) Z<- MenorSeparador(a, b, Es, tipo); 2) m <- I(a, b|Z) ; % informação mútua, equação (4). 3) Se m < ε, então { Separadores <- Separadores ∪ {({a, b}, Z)}; Retorna (False) }; % não precisa conectar a e b 4) Enquanto |Z| > 1, faça a. { Para i de 0 a |Z|-1, faça { Zi <- Z – {i-ésimo nó de Z}; mi <- I(a, b|Zi) }; b. k <- arg mini {m0,m1, …m|Z|-1} c. <-e mk < ε, então % mk = min {m0,m1, …m|Z|-1} { Separadores<- Separadores ∪ {({a, b}, Zk)}; Retorna (False) }; % não precisa conectar a e b Senão Se mk > ε, então Retorna(True) % precisa conectar Senão { m <- mk; Z<- Zk; } ; 5) Retorna(True). % precisa conectar. |