A Decomposition Algorithm for Learning Bayesian Networks Based on Scoring Function
Learning Bayesian network (BN) structure from data is a typical NP-hard problem. But almost existing algorithms have the very high complexity when the number of variables is large. In order to solve this problem(s), we present an algorithm that integrates with a decomposition-based approach and a sc...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2012-01-01
|
| Series: | Journal of Applied Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2012/974063 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832545952339066880 |
|---|---|
| author | Mingmin Zhu Sanyang Liu |
| author_facet | Mingmin Zhu Sanyang Liu |
| author_sort | Mingmin Zhu |
| collection | DOAJ |
| description | Learning Bayesian network (BN) structure from data is a typical NP-hard problem. But almost existing algorithms have the very high complexity when the number of variables is large. In order to solve this problem(s), we present an algorithm that integrates with a decomposition-based approach and a scoring-function-based approach for learning BN structures. Firstly, the proposed algorithm decomposes the moral graph of BN into its maximal prime subgraphs. Then it orientates the local edges in each subgraph by the K2-scoring greedy searching. The last step is combining directed subgraphs to obtain final BN structure. The theoretical and experimental results show that our algorithm can efficiently and accurately identify complex network structures from small data set. |
| format | Article |
| id | doaj-art-d407e4c3b0094600ad75a80cc041cc80 |
| institution | Kabale University |
| issn | 1110-757X 1687-0042 |
| language | English |
| publishDate | 2012-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Applied Mathematics |
| spelling | doaj-art-d407e4c3b0094600ad75a80cc041cc802025-02-03T07:24:20ZengWileyJournal of Applied Mathematics1110-757X1687-00422012-01-01201210.1155/2012/974063974063A Decomposition Algorithm for Learning Bayesian Networks Based on Scoring FunctionMingmin Zhu0Sanyang Liu1Department of Mathematics, Xidian University, Xi'an 710071, ChinaDepartment of Mathematics, Xidian University, Xi'an 710071, ChinaLearning Bayesian network (BN) structure from data is a typical NP-hard problem. But almost existing algorithms have the very high complexity when the number of variables is large. In order to solve this problem(s), we present an algorithm that integrates with a decomposition-based approach and a scoring-function-based approach for learning BN structures. Firstly, the proposed algorithm decomposes the moral graph of BN into its maximal prime subgraphs. Then it orientates the local edges in each subgraph by the K2-scoring greedy searching. The last step is combining directed subgraphs to obtain final BN structure. The theoretical and experimental results show that our algorithm can efficiently and accurately identify complex network structures from small data set.http://dx.doi.org/10.1155/2012/974063 |
| spellingShingle | Mingmin Zhu Sanyang Liu A Decomposition Algorithm for Learning Bayesian Networks Based on Scoring Function Journal of Applied Mathematics |
| title | A Decomposition Algorithm for Learning Bayesian Networks Based on Scoring Function |
| title_full | A Decomposition Algorithm for Learning Bayesian Networks Based on Scoring Function |
| title_fullStr | A Decomposition Algorithm for Learning Bayesian Networks Based on Scoring Function |
| title_full_unstemmed | A Decomposition Algorithm for Learning Bayesian Networks Based on Scoring Function |
| title_short | A Decomposition Algorithm for Learning Bayesian Networks Based on Scoring Function |
| title_sort | decomposition algorithm for learning bayesian networks based on scoring function |
| url | http://dx.doi.org/10.1155/2012/974063 |
| work_keys_str_mv | AT mingminzhu adecompositionalgorithmforlearningbayesiannetworksbasedonscoringfunction AT sanyangliu adecompositionalgorithmforlearningbayesiannetworksbasedonscoringfunction AT mingminzhu decompositionalgorithmforlearningbayesiannetworksbasedonscoringfunction AT sanyangliu decompositionalgorithmforlearningbayesiannetworksbasedonscoringfunction |