蚁群算法的贝叶斯网络结构学习
贝叶斯网络（BNs）是用来刻画随机变量独立或不独立关系的知识表达工具。基于数据学习贝叶斯网络结构的一种重要方法就是定义一种具有测量候选网络拟合性的得分指标，然后运用一种搜索过程去寻找候选网络的集合。本文基于蚁群优化(ACO)算法以及一种结合的最大最小蚁群优化(MMACO)算法提出了一种新型算法对贝叶斯网络进行学习。在MMACO中，MMPC用于构造网络骨架，ACO用于确定各边的方向，从而获得最终结构。将这些算法运用于一些基准网络下的数据集，并通过实验，比较本文提出的新型优化算法与ACO和MMACO算法的表现。关键词 贝叶斯网络，蚁群算法，结构学习
目 录
1 绪论 1
2 贝叶斯网络（BNs）结构学习 1
3 基于蚁群算法的贝叶斯网络结构学习 3
3.1 基于骨架的结构搜索MMPC算法 3
3.2 蚁群算法原理 5
3.3 蚁群算法在贝叶斯网络结构学习中的应用 5
4 MMACO算法的改进 10
4.1 部分MMACO方法（RMMACO） 11
4.2 随机MMACO方法（PMMACO） 11
5 算法评价 12
5.1 基准网络 12
5.2 实验参数设置 12
5.3 算法评价指标 13
6 实验结果 13
6.1 定性分析 21
6.2 定量分析 21
6.3 算法分析与BIC得分法改进 21
结 论 27
致 谢 28
参 考 文 献 29
1 绪论
本文通过对蚁群算法的研究，对数据进行贝叶斯网络结构学习，以达到改进蚁群智能算法在结构学习中的应用。贝叶斯网络(或称之为概率信度网络)是一种流行的图模型，它用概率的方式描述了一组随机变量的依赖关系[1]。其目标是提供一种一致而又直观的、可以刻画变量间更高阶统计量的图形表达。贝叶斯网络也可能用于提取变量间的定性依赖关系，在这种情况下，对贝叶斯网络的定量部分被省略。贝叶斯网络结构的学习过程是一个在未来若干年都非常重要的领域，并且现在不断普及。因为在学习贝 *好棒文|www.hbsrm.com +Q: ^351916072^
叶斯网络中对最优网络的搜索属于NP困难[23]，智能算法对于进行快速却高质量的网络结构学习非常有效。
一般来说,结构学习算法研究从两个观点出发:基于条件独立测试的方法[4]和基于评分指标优化的方法[1]。在那些基于评分优化算法种类中，被人熟知的元启发式算法就是模拟退火算法。另一个不断熟知的相同类型算法就是蚁群算法[5]（ACO），尽管其相关发展时间还很短，但是已经成功运用到大范围的问题中[6]。
最近,一种结合条件独立方法和评分标准优化的复杂算法被引入，并且证明出很强的竞争性[7,8]，该算法首先通过使用条件相关测试——MMPC算法(maxmin parent and child)）重构一个非指向性的贝叶斯网络的框架, 再用基于评分的ACO算法用于确定框架的方向，该种方法被称为MMACO[9].本文中，通过对这种新型复杂算法MMACO进行改进和优化，提高结构学习的质量，本文把改进的两种算法称为部分MMACO（RMMACO）和随机MMACO（PMMACO）。
2 贝叶斯网络（BNs）结构学习
贝叶斯网(BNs)是表示随机变量间依赖和独立关系的网络模型，也称为信念网络。贝叶斯网络的结构反映了节点间潜在的概率独立关系以及一系列的关于条件独立判断[8]。本质上讲，贝叶斯网络被用来刻画随机变量间的联合概率分布。
换句话说，贝叶斯网络可以被用来描述个随机变量的联合概率分布[10]。这种表示有两个部分：第一个部分是一个图示结构，或是更准确地讲——有向无环图(DAG)，将变量表示为节点，将变量之间的统计依赖关系表示为边。第二个部分是一个参数集，这个参数集合规定了随机变量的联合概率分布。在DAG中，将变量间不独立关系编码成联合概率分布分解为乘积形式
(1)
其中表示为DAG,中变量的父节点。对数据集进行贝叶斯网络结构和参数学习的问题就可以公式化，如下：给定一个有限数据集，有个不同的不独立观测值，每个数据点是个变量的一组观测值，寻找最佳匹配数据集的一个图形结构和一组参数。解决这类问题的最普遍方法是定义一个得分函数，其具有测量每一个关于被测数据的网络。并且然后根据分数寻找最佳的网络。被定义为如下
(2)
其中为结构的先验概率，是一个归一化常量，是给定模型图示下的边缘概率。
通过对所有可能的网络结构使用一致的先验概率，也就是说，对所有网络都是不变的。那么贝叶斯学习的问题就可以归结为仅根据最优边缘概率搜寻结构：
(3)
其中表示为在给定下，数据集的概率，代表贝叶斯网络的局部概率分布下，结构的先验概率。
BIC（贝叶斯信息准则，Bayesian information criterion）得分法[1]被用来用基准测量本文中元启发式算法优化策略。BIC评分函数是实际中最常用的函数，它是利用拉普拉斯近似（Laplace approximation）对边缘近似函数进行大样本数据下的近似，根据证明，BIC得分函数的误差随着样本量的增加不会增加，也说明了其在大样本时相对要更加精确。贝叶斯网络结构为的BIC得分定义为：
(4)
其中表示的独立参数个数，为关于的参数（不同网络结构参数集不同），为的最大似然估计。BIC得分公式中的前面一项的是测量贝叶斯网络结构的优参对数似然度，其表示的结构与数据集的拟合程度大小；后面一项是对有关网络模型复杂度的计算惩罚项，为样本量大小。简单来说，BIC得分是对拟合优度与复杂度的折中，由于附加一个惩罚项，BIC得分有效避免了过度拟合[1]。
BIC评分指标的一个重要属性就是它的可分解性属性。每个变量决定的分数可以分离,使得对网络结构中局部的变化计算出有效的分数，例如加边或减边。通过对数转化，总分可以分为局部分数之和。定义变量的家族BIC评分为：
(5)
则有：
目 录
1 绪论 1
2 贝叶斯网络（BNs）结构学习 1
3 基于蚁群算法的贝叶斯网络结构学习 3
3.1 基于骨架的结构搜索MMPC算法 3
3.2 蚁群算法原理 5
3.3 蚁群算法在贝叶斯网络结构学习中的应用 5
4 MMACO算法的改进 10
4.1 部分MMACO方法（RMMACO） 11
4.2 随机MMACO方法（PMMACO） 11
5 算法评价 12
5.1 基准网络 12
5.2 实验参数设置 12
5.3 算法评价指标 13
6 实验结果 13
6.1 定性分析 21
6.2 定量分析 21
6.3 算法分析与BIC得分法改进 21
结 论 27
致 谢 28
参 考 文 献 29
1 绪论
本文通过对蚁群算法的研究，对数据进行贝叶斯网络结构学习，以达到改进蚁群智能算法在结构学习中的应用。贝叶斯网络(或称之为概率信度网络)是一种流行的图模型，它用概率的方式描述了一组随机变量的依赖关系[1]。其目标是提供一种一致而又直观的、可以刻画变量间更高阶统计量的图形表达。贝叶斯网络也可能用于提取变量间的定性依赖关系，在这种情况下，对贝叶斯网络的定量部分被省略。贝叶斯网络结构的学习过程是一个在未来若干年都非常重要的领域，并且现在不断普及。因为在学习贝 *好棒文|www.hbsrm.com +Q: ^351916072^
叶斯网络中对最优网络的搜索属于NP困难[23]，智能算法对于进行快速却高质量的网络结构学习非常有效。
一般来说,结构学习算法研究从两个观点出发:基于条件独立测试的方法[4]和基于评分指标优化的方法[1]。在那些基于评分优化算法种类中，被人熟知的元启发式算法就是模拟退火算法。另一个不断熟知的相同类型算法就是蚁群算法[5]（ACO），尽管其相关发展时间还很短，但是已经成功运用到大范围的问题中[6]。
最近,一种结合条件独立方法和评分标准优化的复杂算法被引入，并且证明出很强的竞争性[7,8]，该算法首先通过使用条件相关测试——MMPC算法(maxmin parent and child)）重构一个非指向性的贝叶斯网络的框架, 再用基于评分的ACO算法用于确定框架的方向，该种方法被称为MMACO[9].本文中，通过对这种新型复杂算法MMACO进行改进和优化，提高结构学习的质量，本文把改进的两种算法称为部分MMACO（RMMACO）和随机MMACO（PMMACO）。
2 贝叶斯网络（BNs）结构学习
贝叶斯网(BNs)是表示随机变量间依赖和独立关系的网络模型，也称为信念网络。贝叶斯网络的结构反映了节点间潜在的概率独立关系以及一系列的关于条件独立判断[8]。本质上讲，贝叶斯网络被用来刻画随机变量间的联合概率分布。
换句话说，贝叶斯网络可以被用来描述个随机变量的联合概率分布[10]。这种表示有两个部分：第一个部分是一个图示结构，或是更准确地讲——有向无环图(DAG)，将变量表示为节点，将变量之间的统计依赖关系表示为边。第二个部分是一个参数集，这个参数集合规定了随机变量的联合概率分布。在DAG中，将变量间不独立关系编码成联合概率分布分解为乘积形式
(1)
其中表示为DAG,中变量的父节点。对数据集进行贝叶斯网络结构和参数学习的问题就可以公式化，如下：给定一个有限数据集，有个不同的不独立观测值，每个数据点是个变量的一组观测值，寻找最佳匹配数据集的一个图形结构和一组参数。解决这类问题的最普遍方法是定义一个得分函数，其具有测量每一个关于被测数据的网络。并且然后根据分数寻找最佳的网络。被定义为如下
(2)
其中为结构的先验概率，是一个归一化常量，是给定模型图示下的边缘概率。
通过对所有可能的网络结构使用一致的先验概率，也就是说，对所有网络都是不变的。那么贝叶斯学习的问题就可以归结为仅根据最优边缘概率搜寻结构：
(3)
其中表示为在给定下，数据集的概率，代表贝叶斯网络的局部概率分布下，结构的先验概率。
BIC（贝叶斯信息准则，Bayesian information criterion）得分法[1]被用来用基准测量本文中元启发式算法优化策略。BIC评分函数是实际中最常用的函数，它是利用拉普拉斯近似（Laplace approximation）对边缘近似函数进行大样本数据下的近似，根据证明，BIC得分函数的误差随着样本量的增加不会增加，也说明了其在大样本时相对要更加精确。贝叶斯网络结构为的BIC得分定义为：
(4)
其中表示的独立参数个数，为关于的参数（不同网络结构参数集不同），为的最大似然估计。BIC得分公式中的前面一项的是测量贝叶斯网络结构的优参对数似然度，其表示的结构与数据集的拟合程度大小；后面一项是对有关网络模型复杂度的计算惩罚项，为样本量大小。简单来说，BIC得分是对拟合优度与复杂度的折中，由于附加一个惩罚项，BIC得分有效避免了过度拟合[1]。
BIC评分指标的一个重要属性就是它的可分解性属性。每个变量决定的分数可以分离,使得对网络结构中局部的变化计算出有效的分数，例如加边或减边。通过对数转化，总分可以分为局部分数之和。定义变量的家族BIC评分为：
(5)
则有：
版权保护: 本文由 hbsrm.com编辑，转载请保留链接: www.hbsrm.com/jsj/jsjkxyjs/1229.html
