基于有向图的树形贝叶斯网络研究

《基于有向图的树形贝叶斯网络研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、北京交通大学硕士学位论文基于有向图的树形贝叶斯网络研究姓名：邵鲁杰申请学位级别：硕士专业：计算机科学与技术指导教师：王志海20090601摘要在数据挖掘领域中，分类是一种非常重要的技术．限制性贝叶斯分类器是在贝叶斯分类器的基础上加上相应的限制条件，解决了学习一个最优化的贝叶斯网络是NP难的问题，限制性贝叶斯分类器一直是分类技术研究领域的热点之一．其中，树形增强朴素贝叶斯分类器是一种典型学习方法，它的结构学习比较简单并且具有良好的分类表现．本文首先介绍分类的概念以及重要技术．其次，叙述了限制性贝叶斯分类器的相关算法，重点分析了朴素贝叶斯

2、分类器、TAN分类器、爬山法分类器和SP分类器的理论基础和分类器结构，并比较各个算法的优缺点．另一方面，由于树形分类器的构造过程中要涉及到生成树的问题，所以随后本文阐述了图的最优生成树的相关算法及其在树形贝叶斯分类器中的可能的应用．在这些研究工作的基础上，本文提出了一种新的构建树形增强朴素贝叶斯分类器的算法DTAN．该算法首先从信息论的角度出发，分析反映属性问依赖关系的方法，介绍互信息的产生原理并且在互信息的基础上提出了一种新的非对称的依赖关系函数．然后利用上述属性间的依赖关系函数构建一个完全有向图，并根据Edmonds算法得到其最大

3、生成树作为DTAN分类器树形结构的雏形．最后本文提出一种启发式搜索算法IP去修『F得到的树形结构，详细介绍了这种算法的核心思想，并且计算其时间复杂度．最后，本文新建了两个分类器：只应用新依赖关系函数的MTAN和在MTAN基础上应用IP算法得到的DTAN．在分析实验结果的过程中通过MTAN与标准TAN的比较证明新的依赖关系的可行性，通过DTAN与SP相比得出新的启发式搜索算法的优越性．关键词：数据挖掘；分类器；限制性贝叶斯网络；生成树；启发式搜索分类号：TP301．6本文得到国家自然科学基金项目资助(基金项目编号：60673089)=i

4、匕塞銮垣太堂亟±堂位i佥塞△旦墨至B△g：rABSTRACTInthedomainofDataMining，classificationisaveryimportanttechnology．RestrictedBayesianclassifiersin．easecorrespondingrestrictedconditionsfornormalBayesianclassifierstosolvetheproblemthatlearninganoptimalBayesiannetworkisNP．hard．Treeaugmentedna

5、iveBayesclassifierisatypicallearningmethod，andhasgoodclassificationperformationeventhoughitslearningstructureissimple．RestrictedBayesianclassifiershavebeenoneofthemosthotspotsinclassificationtechnologyresearcharea．Thispaperfirstintroducestheconceptofclassificationandrel

6、evanttechnologies，thendescribessomealgorithmsofrestrictedBayesianclassifiers，especiallyanalysesthetheoreticalbasisandclassifier’SstructureofNaiveBayes，TAN，HCSandSP．Ontheotherhand，inthecourseofbuildingtheTANclassifier,theproblemaboutoptimalspanningtreeshasbeeninvolved．So

7、weexpoundthealgorithmsforoptimalspanningtreesofagraphandtheirpossibleapplicationsinBayesianclassifier．Basedontheworksabove，weproposeanewmethodtobuildTANclassifier．Firstly,accordingtotheinformationtheory,weanalysethemeanstoreflectthedependencerelationbetweenattributes，in

8、troducetheproductionofmutualinformationandproposedanewunsymmetricalfunctiontoreflectthedependencerelation．Seco