论文部分内容阅读
马尔可夫毯在分类任务中的特征选择与贝叶斯网络的结构学习中发挥着重要作用。马尔可夫毯发现算法用于从实际的数据集中学习和发现目标变量的马尔可夫毯。目前马尔可夫毯发现算法可分为两类，这两类算法的原理是不一样的。第一类算法以IAMB为代表，该类算法的速度很快，但是准确率较低；第二类算法以IPC-MB为代表，该类算法的准确率很高，但是速度较慢，因此这两种算法都具有工程实用价值。贝叶斯网络是一种统计模型，它能够有效地表达随机变量之间的联合概率分布。本文将基于贝叶斯网络研究和设计马尔可夫毯发现算法，主要工作如下：(1)改进了IPC-MB算法，提出了新算法DOS（Dynamic Ordering-based SearchAlgorithm）。DOS算法弥补了IPC-MB的缺点与不足，通过综合运用三种新颖的策略：“排序”、“过滤”、“优化对称原则”，极大地减少了条件独立性测试的次数，提高了发现马尔可夫毯的速度和准确率。本文首先详细介绍了DOS算法发现马尔可夫毯的原理与过程，并分析了DOS算法的主要特点。然后从理论上证明了DOS算法的正确性，并对比分析了DOS与IPC-MB的时间复杂度。最后通过大量、反复的实验显示出DOS的优秀性能。(2)改进了IAMB算法，提出了新算法Improve-IAMB。Improve-IAMB算法最大的特点在于“组进”策略，该策略不仅可以减少条件独立性测试的次数，提高了算法的速度，而且抑制了数据噪声带来的负面影响，提高了算法的准确率。本文首先详细分析了Improve-IAMB算法发现马尔可夫毯的原理，并结合实例描述了Improve-IAMB算法的执行过程。然后对比分析了IAMB与Improve-IAMB的时间复杂度。最后从实验结果中验证Improve-IAMB算法比IAMB算法具有更好的性能。