Mineração de Redes Bayesianas a partir de Base de Dados Médicos: Proposta de Algoritmo

Mineração de Redes Bayesianas a partir de Base de Dados Médicos: Proposta de Algoritmo Cristiane Koehler1,2, Rosa Maria Vicari1, Cecília Dias Flores1, Sílvia Modesto Nassar3 1

Instituto de Informática (II), Universidade Federal do Rio Grande do Sul (UFRGS), Brasil 2 Departamento de Informática (DEIN), Universidade de Caxias do Sul (UCS), Brasil 3 Departamento de Informática e Estatística (INE), Universidade Federal de Santa Catarina (UFSC), Brasil

Resumo - Este artigo apresenta um algoritmo eficiente para aprendizagem de Redes Bayesianas a partir de base de dados. O algoritmo tem um banco de casos como entrada e constrói uma estrutura de Rede Bayesiana como saída. O processo de construção é baseado no cálculo de informação mútua dos pares de atributos. Dada um conjunto de dados volumoso, este algoritmo pode gerar a estrutura de uma Rede Bayesiana com 4 complexidade O(N ) em testes de independência condicional (IC). Para avaliar este algoritmo, são apresentados os resultados experimentais em três versões do banco de casos da rede ALARM, que tem 37 atributos e 10.000 registros e do banco de casos da rede Chest_Clinic. Os resultados mostram que este algoritmo é exato e eficiente. Os resultados mostram que o mesmo é exato e eficiente. No entanto, este algoritmo possui algumas limitações que são comentadas, e finalmente, é proposto uma nova versão do mesmo com o uso de abordagens estatísticas. Palavras-chave: Redes Bayesianas, Aprendizagem de Redes Bayesianas, Análise Multivariada. Abstract - This paper presents an efficient algorithm for learning Bayesian belief- networks from databases. The algorithm takes a database as input and constructs the belief network structure as output. The construction process is based on the computation of mutual information of attribute pairs. Given a data set that is large enough, this algorithm can generate a belief network very close to the underlying model, and at the same time, enjoys the time complexity of O(N4) on conditional independence (CI) tests. To evaluate this algorithm, we present the experimental results on three versions of the well-known ALARM network database, which has 37 attributes and 10,000 records and of the Chest_Clinic network database. The results show that this algorithm is accurate and efficient. In the however, this algorithm I possessed some limitations that are commented, and finally, is proposto a new version of the even with the use of approaches statistical. Key-Words: Bayesian Networks, Bayesian Networks Learning, Multivariate Analisis.

Introdução Atualmente, o uso de inferência probabilística para o desenvolvimento de sistemas inteligentes têm tido muito interesse pela comunidade acadêmica. Um dos objetivos mais importantes dos pesquisadores é o desenvolvimento de técnicas de inferência eficientes para o uso em sistemas inteligentes. No entanto, o seu uso pressupõe a disponibilidade de modelos de conhecimento válidos. Outros pesquisadores têm se preocupado com o desenvolvimento de técnicas capazes de combinar o conhecimento especialista com dados para serem usados no desenvolvimento e mais adiante, no refinamento desses modelos de conhecimento [1]. Nesse contexto, modelos gráficos têm emergido como um poderoso formalismo unificado para muitos modelos probabilísticos, os

quais são amplamente utilizados em estatística, aprendizagem de máquina e engenharia [2]. Surgem assim as técnicas de Data Mining e a descoberta de conhecimento baseado na tecnologia de Redes Bayesianas para extração de modelos de conhecimento válidos a partir de base de dados. A utilização da abordagem de Redes Bayesianas vem sendo utilizada para modelar conhecimento porque oferece uma estrutura unificada e intuitiva para representar modelos de seus dados. O seu caráter unificado torna possível comparar diferentes hipóteses sobre os dados e a natureza intuitiva do formalismo gráfico de Redes Bayesianas a torna um dos melhores métodos analíticos disponível para a tomada de decisão [4]. Muitos problemas são constatados na modelagem manual de uma Rede Bayesiana, entre eles, o processo de entrevistar o especialista real para extrair conhecimento apresentou várias

dificuldades. Os especialistas são surpreendentemente pouco claros quando se trata de mostrar como eles solucionam problemas, pois o ser humano demonstra uma certa dificuldade em associar números (dados estatísticos) sobre quanto ele crê em um determinado fato [5]. Além das entrevistas com o especialista exigirem um certo conhecimento da área de aplicação por parte do profissional de informática, este conhecimento é alcançado por meio de conversas com o próprio especialista, ou em pesquisas bibliográficas, o que é bem mais difícil. O processo de construção automática de modelos de conhecimento bayesianos parte de dois princípios básicos: a) o algoritmo deve considerar somente as variáveis mais relevantes para a tomada de decisão, isto é, deve delimitar ao máximo o número de variáveis sem perder as informações e b) o algoritmo deve realizar esta delimitação automaticamente, sem a intervenção do usuário. Isto porque, os algoritmos de aprendizagem bayesiana, atualmente existentes, geram modelos de conhecimento com todas as variáveis existentes nas bases de dados, o que nem sempre se faz necessário, é solicitado ao usuário para que informe ao algoritmo quais são as variáveis mais importantes e ainda a ordenação das mesmas. Por exemplo, considerando o processo de tomada de decisão na prática clínica médica , apenas os sintomas mais importantes são considerados necessários para a tomada de decisão sobre um determinado diagnóstico. Ou seja, o médico não elege um diagnóstico baseado em muitos sintomas, mas sim, a partir dos sintomas mais significativos para a tomada de decisão. Para gerar modelos de conhecimento bayesianos, muitos algoritmos encontrados na literatura científica, necessitam das seguintes informações: a) a relação de variáveis, b) a ordenação destas variáveis, e c) as relações de dependência e independência entre as mesmas, isto é, as relações de causalidade. Isto é, o software de aprendizagem parte do pressuposto que o usuário tem um profundo conhecimento sobre a rede a ser gerada, o que nem sempre é verdadeiro. Este artigo apresenta o algoritmo CBL dos autores Cheng, Bell e Liu [6] e são propostas algumas modificações importantes na tentativa de amenizar os problemas comentados acima. Na seção 2 serão abordados os problemas encontrados com a aprendizagem bayesiana. Na seção 3 é apresentada uma abordagem baseada na Teoria da Informação. A seção 4 apresenta o algoritmo CBL. O domínio de aplicação é apresentado na seção 5. A seção 6 apresenta a proposta da nova versão do algoritmo CBL chamada de CBL-K, e finalmente, algumas considerações finais são apresentadas.

A construção de modelos de conhecimento bayesianos envolve três aspectos: a aprendizagem da estrutura da rede, a aprendizagem das relações de causalidade e as probabilidades associadas. O foco deste artigo é a aprendizagem da estrutura da rede, porque a mesma é considerada a de maior importância pela literatura científica, devido a sua complexidade se comparada com a aprendizagem de parâmetros numéricos que é facilmente resolvida por meio de técnicas estatísticas. Isto porque, enquanto o aprendizado de parâmetros numéricos é relativamente simples, o aprendizado de estrutura é um assunto em geral muito complexo e ainda não está bem resolvido [7]. Nos últimos anos, muitos algoritmos de construção de Redes Bayesianas têm sido desenvolvidos. Geralmente, estes algoritmos podem ser agrupados em duas categorias: o de Busca e Pontuação e o de Análise de Dependência [8]. Ambas categorias têm vantagem e desvantagem: geralmente, a primeira categoria de algoritmos tem menos complexidade de tempo de processamento, mas não pode encontrar a melhor solução devido a sua natureza heurística. A segunda categoria está geralmente correta quando a distribuição de probabilidade dos dados satisfazem determinada suposição, os testes de Independência Condicional (IC) com muitos conjuntos de condições podem não ser confiáveis a menos que o volume de dados seja grande [9]. Na construção da estrutura, muitas Redes Bayesianas são geradas e comparadas a fim de decidir qual é a melhor estrutura. Utilizam-se medidas de qualidade para comparar as estruturas: quanto melhor a aderência da estrutura com a base de dados, maior a qualidade da mesma. A partir de uma determinada base de dados, pode -se gerar um espaço de estruturas. Após encontrar todas as estruturas com alta qualidade - o número de estruturas desses espaços cresce exponencialmente com o número de variáveis - é necessário selecionar uma destas estruturas. Algoritmos de busca são empregados para este fim, mas estes algoritmos, em geral, possuem um custo alto do ponto de vista de tempo de processamento. Aprendizagem de redes envolve a escolha de, possivelmente, um número exponencial de estruturas e de valores. Mas, onde está o problema ? Resultados básicos da teoria de aprendizagem computacional mostram a dificuldade deste processo, considerando o número de casos necessários para treinamento, e o tempo e espaço requerido para otimização. Estes dois aspectos são referenciados como sendo um exemplo da complexidade e, respectivamente, complexidade computacional. O processo de aprendizagem pode ser realizado com pequenas, médias ou grandes

bases de dados. No entanto, com uma pequena base de dados, aprendizagem corresponde a uma aprendizagem parcial, e com uma grande base de dados, o processo de aprendizagem converge para um modelo mais válido, mais confiável. Esta confiabilidade é medida de acordo com alguns critérios de utilidade, tais como “Erro Quadrático Médio” ou “Distância de Kullback-Leibler” [16]. Um dos grandes problemas encontrados ao longo dos estudos realizados sobre os algoritmos de aprendizagem de Redes Bayesianas a partir de bases de dados, foi que os algoritmos existentes para “aprender” estruturas de redes levam em consideração todas as variáveis armazenadas nas bases de dados. E isto é que gera uma imensa explosão combinatorial de grande complexidade, sendo muitas vezes classificados como problemas com complexidade NP Completos [16]. Partindo do pressuposto que na prática clínica, o médico especialista decide sobre um determinado diagnóstico levando em conta apenas os sintomas mais importantes, foi que se considerou de grande relevância e necessidade, pesquisar, estudar e implementar técnicas e metodologias que possam, automaticamente, extrair conhecimento a partir de base de dados na forma de modelos de conhecimento bayesianos. Metodologia O objetivo desse artigo é analisar o algoritmo CBL e propor uma nova abordagem para tentar solucionar as questões comentadas acima. Este algoritmo faz parte da segunda categoria de algoritmos de aprendizagem bayesiana, foi desenvolvido pelos autores Cheng, Bell e Liu [6] que se basearam no Algoritmo IC de Pearl e Verma [17] para modelá-lo em duas versões A e B. Este algoritmo é apresentado e comentários sobre seus principais problemas e possíveis soluções são apresentados. O algoritmo CBL constrói redes analisando relacionamentos de Independência Condicional (IC) entre os nodos. Para compreender melhor esta abordagem, primeiramente, é necessário saber sobre o conceito de d-separation [18]. Usar informação mútua na construção de modelos probabilísticos pode ser observado em Chow and Liu’s [Chow 1968] no algoritmo de construção de árvores. Em 1987, Rebane and Pearl [19] estendem o algoritmo Chow-Liu para construção de causal polytree [18]. Posteriormente, os autores Cheng, Bell e Liu [6] estendem o algoritmo CBL para construção de Redes Bayesianas. Este algoritmo também faz as seguintes suposições: (1) os atributos da base de dados têm valores discretos, isto é, variáveis que assumem

valores num subconjunto dos números naturais, e que não há presença de valores ausentes em todos os registros; e (2) o volume de dados é grande o suficiente para suportar os testes de Independência Condicional (IC). Este algoritmo possui três fases: drafting, thickening e thinning. A primeira fase é essencialmente o algoritmo de construção da árvore de Chow e Liu’s; a segunda e terceira fase são projetadas para estender a construção da árvore à construção de uma Rede Bayesiana. Na primeira fase, o algoritmo calcula a informação mútua de cada par dos nodos como uma medida de “closeness”, e cria um esboço baseado nesta informação. O esboço é um simples grafo conectado (um grafo sem laços ). Especialmente, quando a Rede Bayesiana é uma árvore ou uma polytree, esta fase pode construir a rede corretamente e a segunda e terceira fases não mudam. Assim, o algoritmo do Chow e Liu’s e o algoritmo de Rebane e de Pearl’s podem ser vistos como casos especiais do algoritmo CBL. Na segunda fase, o algoritmo adiciona bordas quando os pares dos nodos não podem ser d-separated. O resultado da fase II tem a estrutura de um mapa de independência (I-map) [18] do modelo de dependência, dado que este modelo seja um DAG -Faithful normal. Na terceira fase, cada arco do I-map é examinado usando testes do Independência Condicional (IC) e será removido se os dois nodos do arco puderem ser d-separated. O resultado da fase III tem a estrutura de um mapa perfeito [18] quando o modelo é um DAG-Faithful normal. No fim da terceira fase, o algoritmo realiza também um procedimento para orientar os arcos do grafo. O resultado desta fase é um I-map mínimo. Segundo os autores [6] e [8], o algoritmo possui complexidade em número de testes de Independência Condicional (IC) da ordem de

O ?N 2 ? no pior caso. No algoritmo A também é

utilizado um procedimento para encontrar conjuntos bloqueadores mínimos para compensar os testes de Independência Condicional (IC) em grandes conjuntos condição. Este procedimento usa um método de busca heurístico para encontrar o conjunto e, por ser um método de busca guloso, não garante que um conjunto mínimo será encontrado. Um algoritmo para encontrar conjuntos bloqueadores mínimos pode ser encontrado em [20]. Os autores [6] e [8] também desenvolveram um outro algoritmo, chamado algoritmo B, para conjunto de dados incompletos, cuja complexidade em número de testes de Independência Condicional

? ? nos piores casos. O algoritmo B é 4

(IC) é O N uma extensão uso de bases ausentes ou

do Algoritmo A de forma a permitir o de dados com variáveis ou valores omissos. Estes mesmos autores

implementaram ambos algoritmos (A e B) no ambiente BNPC - Belief Networks PowerConstructor [21]. Resultados Os autores realizaram inúmeros testes tendo a rede ALARM como parâmetro. Nos testes, o algoritmo foi executado em modo debugging para permitir monitoração dos resultados intermediários – o que provocou resultados ligeiramente superiores do que quando executado em modo normal. O equipamento utilizado foi um microcomputador Pentium 133 MHz, com 32 Mb de memória RAM, sob Windows NT 4.0 e os dados foram armazenados em um banco de dados MSAccess. Utilizando 10.000 casos o algoritmo A aprendeu a estrutura original com apenas um arco ausente (em relação à rede ideal), em menos de quinze minutos. Sendo que a maior parte deste processamento concentrou-se na primeira fase do algoritmo, quando foram gastos dez minutos e sete segundos. Reaplicando o teste em outro microcomputador (Dual Pentium 166 MHz, com Windows NT 4.0) obteve-se um ganho de performance de 13%. Já o algoritmo B, sob as mesmas condições do experimento acima, obteve uma Rede Bayesiana com dois arcos a menos do que a rede original em aproximadamente dezesseis minutos. Também foram feitos testes com a rede Chest_Clinic como parâmetro, e os resultados obtidos estão abaixo descritos. Esta base de dados exemplo é um arquivo do tipo MSAccess e possui 100 casos. Após submeter esta base de dados ao software BNPC, foi possível observar que, quando solicitado ao software a geração da rede com ordenação das variáveis (Algoritmo CBL-A), o mesmo gerou a rede sem nenhuma ligação faltando ou ligação excedente. E quando foi selecionado a opção sem ordenação das variáveis (Algoritmo CBL-B), o software gerou dois arcos de orientação da relação causal faltando. Nota-se que o resultado não foi tão bom quanto da primeira vez e que o ambiente ainda depende muito da ordenação das variáveis, isto é, do conhecimento prévio sobre o domínio de aplicação por parte do usuário. Discussões O AMPLIA é um ambiente multiagente destinado a apoiar o processo de ensinoaprendizagem de estudantes dos Cursos de Medicina. Para isto, este ambiente utiliza uma abordagem construtivi sta com recursos da Internet [22]. Este ambiente possui os seguintes critérios: primeiro, o aluno elabora seu próprio modelo de

conhecimento e o sistema irá questioná-lo sobre suas ações e decisões; segundo, feedback e informações adicionais estão disponíveis a todo o momento e, terceiro, se necessário, um processo de negociação entre os agentes e o aluno acontecerá como um meio de fazê-lo revisar seu modelo. Inicialmente, o aluno poderá elaborar um modelo de conhecimento bayesiano no AMPLIA, que o questionará sobre todas as suas ações perante o ambiente, isto é, desde quantas vezes o aluno redesenhou o modelo até o por quê de todas as suas decisões. Em paralelo, o aluno terá uma espécie de feedback e a disponibilização de informações adicionais a todo momento. Em seguida, será acionado o processo de negociação entre os agentes e o aluno, onde o aluno poderá revisar o seu modelo de conhecimento. O algoritmo de aprendizagem de Redes Bayesianas estará funcionando em paralelo ao ambiente AMPLIA. No momento em que for necessário a aquisição de um novo modelo de conhecimento para ser validado com os novos modelos do aluno, o AMPLIA acionará o algoritmo bayesiano que, por sua vez, deverá extrair modelos bayesianos de uma nova base de dados e disponibilizá-lo ao AMPLIA para que o mesmo possa incoroporá-lo a sua base de conhecimentos e validar o modelo do aluno com este novo modelo especialista. O processo de aprendizagem dar-se-á a partir da necessidade de agentes do ambiente externo, médicos e alunos do Curso de Medicina, em aprender novos modelos de conhecimento baseados em Redes Bayesianas. Como pôde ser observado nas seções anteriores, o Algoritmo CBL nas versões A e B não seriam úteis para resolver esse problema simplesmente pelo fato de que o usuário (o aluno de Medicina) teria que passar o seu conhecimento (conhecimento de “aprendiz”) sobre o domínio ao algoritmo, isto é, o aluno deveria informar as variáveis, a ordenação e a causalidade das relações das mesmas, pois o algoritmo CBL-A e CBL-B necessita destas informações para gerar a rede, o que não é o caso. Os algoritmos CBL-A e CBL-B não satisfazem as necessidades do ambiente AMPLIA. Por outro lado, foi constatado que o algoritmo CBL é um dos algoritmos mais eficientes e ágeis para aprender Redes Bayesianas a partir de dados. Por isso, propõe -se a modelagem de uma nova versão do Algoritmo CBL, chamada de CBL-K que deverá extrair, de uma forma totalmente automatizada, estruturas de Redes Bayesianas a partir de dados. Esta versão proposta deverá, automaticamente, identificar as variáveis mais relevantes, relações de dependências e relações de

causalidade entre as mesmas, sem informações vinda do usuário, apenas da análise dos dados. No entanto, para isso a versão CBL-K deverá tratar os problemas abaixo relacionados: a) a identificação das variáveis mais relevantes pode ser feita a partir de: análises estatísticas sobre os dados, isto é, serão utilizadas estruturas de correlação. Isto porque um dos problemas mais significativos do algoritmo CBL versões A e B é que os testes de Independência Condicional (IC) com uma quantidade muito grande de variáveis pode tornar-se inviável em função do problema da explosão combinatorial de variáveis [18] e b) a identificação das relações de causalidade poderão ser feitas com a utilização do critério d-separation [18] ou de recursos estatísticos. O problema da explosão combinatorial de variáveis é a geração de várias estruturas para a rede gerando um espaço exponencial de estruturas. Isto é um problema exponencial por causa do número de nodos (variáveis) do problema em questão. A fórmula de Robinson proposta em [24], determina o número de possíveis estruturas com n número de nodos. Por exemplo, para

n ? 2 , o número de possíveis

estruturas é três (3), para

n ? 3,

esse número aumenta para vinte e cinco (25), para n ? 5 , esse mesmo número aumenta para vinte e nove mil (29.000), e para 18

n ? 10 ,

o número explode para

4 .2 * 10 . Por esta razão, alguns algoritmos [24] utilizam métodos heurísticos que reduzem a complexidade exponencial e polinomial. Mas, como pode ser visto em [10], [13], [14], [15], [16] e [18], ainda não foi desenvolvido um algoritmo que resolva o problema da complexidade exponencial. Por isso, está sendo proposto a utilização de recursos Estatísticos para minimizar o problema em questão. A proposta de modelar uma nova versão do Algoritmo CBL que analise os nodos (variáveis) mais importantes tem como principal objetivo tentar minimizar o problema da complexidade computacional. Este problema poderá ser tratado utilizando recursos estatísticos como a Análise Multivariada. Em quase todas as áreas de aplicação pesquisas são realizadas e varias características (variáveis) são observadas. Essas variáveis, em geral, não são independentes, e por isso, devem ser analisados conjuntamente. A Análise Multivariada é a área da Estatística que trata desse tipo de análise. Várias são as técnicas que podem ser aplicadas aos dados. Sua utilização depende do tipo de dado que se deseja analisar e dos objetivos do estudo. Algumas técnicas multivariadas são: Análise de Agrupamentos, Análise de Componentes Principais, Análise de Correlação Canônica e Análise de Variância Multivariada (MANOVA).

Conclusões O algoritmo CBL, implementado no software BNPC é um algoritmo muito eficiente e ágil. No entanto, o seu funcionamento correto ainda está condicionado a um conhecimento profundo da área de aplicação, isto é, para gerar a Rede Bayesiana o usuário necessita informar muitos dados que somente o especialista no domínio de aplicação poderia fazê-lo. Tais dados como, por exemplo, quais são as variáveis necessárias; quais são os relacionamentos entre estas variáveis; qual a ordenação destas variáveis, entre outros dados. Foi possível constatar que este algoritmo, realmente gera Redes Bayesianas fidedignas ao domínio de aplicação, no entanto, a principal desvantagem deste algoritmo é que o mesmo necessita que o usuário tenha um conhecimento profundo da área para poder informar todos os dados necessários para a geração da rede. Isto é, os algoritmos partem do pressuposto que o usuário deve ter o conhecimento sobre quais são as variáveis mais importantes para a tomada de decisão, qual é a ordenação destas variáveis, e quais são as relações de causalidade. Em outras palavras, pode-se afirmar que os algoritmos CBL-A e CBL-B não são inteligentes a ponto de, dada uma base de casos reais qualquer, identificar todas estas informações sobre o modelo de conhecimento bayesiano e gerá-lo sem a intervenção do usuário. Finalmente, após uma análise minuciosa do algoritmo CBL proposto pelos autores [6] e [8], uma das principais conclusões a que se pode chegar é que o algoritmo CBL é o que mais atende a necessidade de se extrair modelos de conhecimento de base de dados, na forma de estruturas de Redes Bayesianas. No entanto, o funcionamento correto deste algoritmo está condicionado a um conhecimento profundo da rede que será gerada. A sua aplicação em casos reais, onde não se conhece a estrutura da rede, ainda está longe de uma correção desejável. Além disso, o seu desempenho em bases de dados com grande quantidade de registros fica muito comprometido. Por isso, da proposta em remodelar o Algoritmo CBL em uma nova versão utilizando uma abordagem Estatística para solucionar os problemas da identificação das variáveis mais relevantes, suas relações de causalidade e o problema da explosão combinatorial. A aplicação da nova versão do algoritmo CBL, o algoritmo CBL-K será implementada e testada juntamente ao ambiente multiagente AMPLIA. Atualmente, o algoritmo CBL versão K está sendo implementado na linguagem CBuilder da Borland, com acesso a rotinas do pacote de software Matlab chamado Bayes Net Toolbox (BNT) de código fonte livre [26]. No momento, estão sendo

implementadas rotinas que utilizam estruturas de correlação para análise das variáveis. Posteriormente, estas rotinas serão testadas com as bases de dados Alarm e Chest_Clinic. Referências [1] Krause, P.J. Learning Probabilistic Networks. Philips Research Laboratories Tech. Report., 1998. [2] Jordan, M.I. Learning in Graphical Models. MIT Press, 1999. [3] Rezende, S. O. Sistemas Inteligentes: fundamentos e aplicações. Barueri: São Paulo: Manole, 2003. [4] Documento on-line disponÍvel em no web-site: http://www.igce.unesp.br/igce/grad/computacao/cin tiab/datamine/introducao.html, em Fevereiro de 2004. [5] Pearl, J. Fusion, Propagation and Structuring in Belief Networks. Artificial Intelligence, vol 29(3):241-288. 1986. [6] Cheng, J., Bell, D. A. e Liu, W. Learning belief networks from data: An efficient approach based on information theory. (report98.ps.gz ) Technical Report, 1998. [7] Silva, W. T., e Ladeira, M. Mineração de Dados com Redes Bayesianas. XXI JAI – Jornada de Atualização em Informática. Anais do XXII Congresso da Sociedade Brasileira de Computação, vol. 2, pg. 235-286, 2002. [8] Cheng, J., Bell, D.A. e Liu, W. An Algorithm for Bayesian Belief Networks construction from data. In Proceedings of AI & STAT'97, pp. 83-90, Flórida, 1997. [9] Cooper, G. and Herskovits, E. A Bayesian method for the induction of probabilistic networks from data. Machine Learning, 9:309--347, 1992. [10] Heckerman, D., Geiger, D., Chickering, D. M. Learning Bayesian networks: The combination of knowledge and statistical data. Technical Report MSR-TR-94-09, Microsoft Research, Advanced Technology Division, July 1994. [11] Herskovits, E. H. Computer-based probabilistic network construction. Doctoral Dissertation. Medical Information Sciences, Stanford University, Stanford, CA, 1991. [12] Suzuki, J. Learning bayesian belief networks based on the MDL principle: an efficient algorithm using the branch and bound technique. In: Proceedings of the International Conference on Machine Learning, Bally, Italy, 1996. [13] Spirtes, P., Glymour, C. e Scheines, R. An algorithm for fast recovery of sparse causal graphs, Social Science Computer Review, 9, 6272, 1991. [14] Wermuth, N. e Lauritzen, S. Graphical and recursive models for contingency tables. Biometrika, 72, 537552, 1983. [15] Srinivas, S., Russel, S. e Agogino, A. Automated construction of sparse Bayesian networks from unstructured probabilistic models and domain information. In Henrion, M. Schachter, R.D., Kanal, L.N. and Lemmer, J.F. (Eds.), Uncertainty in

artificial intelligence 5, Amsterdam: North-Holland, p. 295-308, 1990. [16] Buntine, W. A guide to the literature on learning probabilistic networks from data. IEEE Transactions on Knowledge and Data Engineering, 8:195—210, 1996. [17] Verma, T.S. e Pearl, J. Equivalence and synthesis of causal models. Proceedings of the sixth international conference on uncertainty in artificial inteligence, 1990. [18] Pearl, J. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. San Mateo, Calif.: Morgan Kaufmann, 1988. [19] Rebane, G., Pearl, J. The recovery of causal polytrees from statistical data. Proceedings of UAI'87, pp 222-228, Seattle, 1987. [20] Acid, S. e Campos, L.M. An Algorithm for Finding Minimum d-Separating Sets in Belief Networks, Proceedings of UAI'96, 003010, E. Horvitz, F. Jensen (eds), MorganKaufmann, 1996. [21] BNPC 2004. Documento disponível em http://www.cs.ualberta.ca/~jcheng/bnpc.htm, em Março de 2004. [22] Vicari, R. M.; Flores, C. D.; Seixas, L.; Silvestre, A.; Ladeira, M.; Coelho, H., 2003. A Multi-Agent Intelligent Environment for Medical Knowledge. In: Journal of Artificial Intelligence in Medicine, Elsevier Science, Volume 27, Issue 3 , 335-366, 2003. [23] Bouckaert, R. R. Bayesian Belief Networks: from inference to construction. PhD Thesis, Faculteit Winskunde en Informatica, Utrech Universiteit, June 1995. [24] [Cooper 1992] Cooper, G. and Herskovits, E. A Bayesian method for the induction of probabilistic networks from data. Machine Learning, 9:309--347, 1992. [25] Regazzi, A.J. Análise multivariada. Notas de Aula. Viçosa, MG: UFV, DPI, 1997. [26] Murphy, K. P. The Bayes Net Toolbox for Matlab. Department of Computer Science, University of Califórnia, Berkeley, CA, 2001. Contato Cristiane Koehler Universidade de Caxias do Sul Departamento de Informática Av. Francisco Getúlio Vargas, 1130 Bairro Petrópolis Caxias do Sul - RS, Brasil mailto:[email protected]