摘要：针对贪婪贝叶斯模式搜索算法(GB P S)在搜索最优贝叶斯网络结构时易陷入局部最优的不足，提出了一种改进的G B P S算法．在G B P S算法的邻域生成过程中引入了有向边的变向操作，并通过仿真实验研究了样本数量和网络节点的连接边数对算法寻优能力、结果准确度和计算量的影响．将该改进算法用于从中医临床诊断数据中辨识症状与辨证要素间的复杂关系．结果表明，该改进算法的学习结果优于GB P S算法和贪婪贝叶斯有向无环图搜索算法(G B D s)．所发现的症状一辨证要素间的相关关系与中医专家经验吻合较好，可用于从中医诊断数据中自动获取中医专家知识．

关键词：贝叶斯网络；混合学习；知识发现；中医

贝叶斯网络是用于不确定性推理的概率图模型…．它可直观地表达多个变量的联合概率分布，能表示变量时序关系、相关关系或因果关系等多种语义，其灵活的推理能力满足非单调推理和反向推理等多种合情推理模式．贝叶斯网络坚实的理论基础、直观的知识表达、灵活的推理能力以及方便的决策机制使其成为数据挖掘领域的新兴技术．

针对手工构建贝叶斯网络模型效率低下的缺陷，研究者们提出了一系列从数据中自动学习贝叶斯网络结构和参数的学习算法，尤其是贝叶斯网络结构学习算法．当前主要存在基于约束(c o n—s t r a i n t s—b a s e d)和基于得分函数(s c o r e—b a s e d)的贝叶斯网络结构学习算法．前者学习速度快，控制参数少，但在小样本情况下，由于高阶独立检验不可靠[4]学习结果误差较大．后者在小样本情况下学习结果慢，且学习结果易陷入局部最优．针对上述两类学习算法的特点，又提出了结合两者长处的杂交学习算法．贪婪贝叶斯模式搜索算法(g r e e d y b a y e s i a n p a t—t e r n s e a r c h a l g o r i t h m，G B P S)是最有效的杂交学习算法之一，它先用基于约束的P C[6 3算法得到初始网络，再采用贪婪搜索法从该初始网络出发在等价贝叶斯网络模式空间中搜索最优网络结构．在贪婪搜索过程中，邻域的产生方法存在缺陷，易陷入局部最优．

  本文针对G B P S算法的缺陷进行改进，并将该改进算法用于中医药数据挖掘口]，以发现症状与辨证要素间的相关关系为例，考察其用于中医知识发现的可行性．

1算法原理

1．1结构学习问题描述

贝叶斯网络结构是一个有向无环图(d i r e c t e da c y c l i c g r a p h，DAG)，由一系列V结构和候选V结构组成．对于网络中具有固定连接的3个节点a、b和c(a与c分别与b相连且a与c不相连，即3个节点的边连接形式为a—b—c)，若两条边的方向为a一6一c，则称此形式为V结构；若两条边的方向是除n一6一c之外的任意一种方向，则称此形为候选V结构．

两个D A G是观察等价的，当且仅当D A G对应的无向图相同，且具有相同的V结构．具有观察等价性质的得分函数，所有等价的D A G在相同样本集上都具有相同的得分．模式(p a t t e r n)是由有向边和无向边组成的网络结构，代表一个等价D A G集合．如果一条边在所有等价D A G中都具有相同的方向，那么这条边在模式中就用有向边表示，否则就用无向边表示．模式的得分定义为它的任意一个D A G的得分．基于模式空间的得分函数最优化就是从模式空间中进行搜索，找出全局最优的模式．

1．2算法步骤

G B P S算法在模式空间进行搜索，其算法步骤如F：

1)运行P C算法，其结果为初始网络模式P 0；

2)P—P0：

3)计算模式P的得分S；

4)生成模式P的邻域，计算邻域中每个模式的

得分，得到最大得分1及其对应的模式P 1；

5)如果1<，那么转到7)；

6)当P—P1，S—1时，转到4)；

7)将生成模式P的一个D A G作为输出，算法

结束．

其中步骤4)中生成模式P的邻域是该算法的

关键环节，其邻域生成方法具体描述如下：

①增加一条边到模式P，产生P的一个相邻；

②对新模式中新加入的边的两端节点，分别考

察其是否构成候选V结构，如果是，则改变此候选

V结构中边的方向，形成新的V结构，产生P的一

个邻居；

③从模式P中删除一条边，产生P的一个相

邻模式；

④考察新模式中是否存在V结构a一6一c，其中a和c是被删边的两端节点，如果存在，将此V结构改成候选V结构，产生P的一个邻居；

  上述G B P S算法的邻域生成方法所生成的邻域是原有模式加入或删除一条边之后形成的模式空间，忽略了不增删边时有向边变向也会导致V结构发生改变的情形，这使得它可能陷入局部最优点．如果加入这种情况，将可能提高搜索到全局最优的可能性，从而得到更好的学习结果．因此，改进算法在上述邻域生成方法中加入下面的操作步骤：

⑤考察模式P中的每条边，若翻转此边方向会改变模式P的V结构，那么执行此操作，产生P的一个邻居；

与G B P S算法类似，贪婪贝叶斯有向图搜索算法(g r e e d y b a y e s i a n DA G s e a r c h a l g o r i t h m，G B D S)_8也通过贪婪法进行寻优，不同的是它基于DAG空间而不是模式空间，其邻域生成方法为原D AG．

2仿真实验与结果

2．1仿真实验

    仿真数据集的产生步骤如下：

    1)随机生成一个DAG，此DAG的节点数为Ⅳ，每个节点的平均连接边数为E，并假设此D A G9 5 0浙江大学学报(工学版)第3 9卷上每个节点都是布尔变量；

    2)随机生成此D A G上每个节点的概率参数表，形成一个贝叶斯网络；

     3)在此贝叶斯网络上随机抽样M次，产生样本量为的一个样本集；

     本文中的仿真实验使用的节点数Ⅳ为1 0，节点平均连接边数E为2、3和4，样本量为1 0 0、2 5 0、5 0 0、1 0 0 0和2 5 0 0，这样共有1 5种组合情况，然后对于每种情况比较3种算法的性能，其中每种情况都重复2 0次并取均值，以减少抽样误差．3种算法都以P C算法的输出作为初始模式或DAG，其中P C算法的置信度水平取为0．0 5，且都使用B d e函数l_9作为得分函数，网络结构得分越高表明其与数据的拟合程度越高．

2．2算法性能评价

    用上述仿真实验比较G B D S、G B P S和改进算法在寻优能力、计算量、精度上的性能．下面给出这

3种算法性能评价指标的定义：

    对于一个样本集，3种算法分别得到3个模式或D A G及其得分．将这3个得分根据其大小进行排序，并赋予一个序号，如果两个得分相同，那么就取并列序号，如若三种算法的得分分别为1．0、2．0、3．0，则其相应的序号分分别为1、2、3；若得分别为1．0、20、1．0，则其序号分别为2、3、2；若得分分别为2．0、2．0、1．0，则序号分别为3、3、1．因此，对这2 0次结果中各算法序号取平均，可以作为算法寻优能力的得分．得分越高，算法寻优能力越强．

    学习算法在寻优时，需要计算邻域中D A G的得分，由于每个D A G与原D A G之间只有少数几个节点的父节点集合有所变化，只需要分别重新计算这些节点在原D AG和新D AG的得分，其得分差就是两个D A G的得分差．因此算法在寻优过程中计算过的节点得分的总数可反映算法的计算量，可以用多次比较结果的平均计算节点数作为此算法的计算量指标．

    学习算法得到的D A G与真实D A G之间存在偏差，错误的边包括：错误增加的边、错误删除的边和方向错误的边．对每一种组合情况，以多次比较结果的总错误边数的均值作为此算法结果的精度指标．

2．3实验结果及讨论

    仿真实验比较3种算法的结果如表1所示，可知节点的平均连接边数和样本量对算法寻优能力的影响趋势不明显，但可以看到GB D S、GB P S和改进算法三者的寻优能力依次上升，而且改进算法的优势较为明显．节点平均连接边数的增加会显著增加算法的计算量，而随着样本量增加，每种算法的计算量都有逐渐增加的趋势，但并不显著．当节点平均连接函数和样本是相同时，G B D S、G B P S和改进算法三者的计算量依次上升，这是因为贝叶斯网络得分越高，需要搜索的贝叶斯网络空间就越大．GB DS、GB P S和改进算法三者的总错误边数随样本量的增加呈下降趋势，这反映了贝叶斯网络学习算法具有渐进一致性，即样本量越大，贝叶斯网络的学习结果越准确；样本量较小，改进算法的精度略优于另外两种算法，但没有显著差别，这是因为样本量小时，基于相关性分析的P C算法学习结果不可；随着样本量增加，改进算法的优势越来越显著．总而言之，改进算法所发现的贝叶斯网络的准确程度要高于GB P S和GB D S算法．

3在中医知识发现中的应用

     为探讨在中医知识发现中的可行性，本文以“辨证统一体系”l_】。。的诊断思维为例，应用该改进算法发现症状与辨证要素的相关关系．

   “辨证统一体系”是一种以辨别病位和病性为基本要求的辨证方法，其核心内容在于提出了辨证要素概念，主要包括病性要素和病位要素．病性要素反映疾病的性质和状态(如热、寒和湿等)，病位要素反映疾病发生的部位(如心、肺和脾等)．该方法针对中医内科应用，在总结以往诸种中医辨证方法主要内容的基础上，总结出了1 0 0 0多种症状和6 1种辨证．每个要素和一部分症状存在正相关或负相关，每个症状和一部分要素存在相关关系，症状之间、要素之间也存在相关关系．通过揭示这些相关关系，可有效地分析、提取并总结中医专家的诊断知识．

实验用的症状一辨证要素数据库包括8 0 6个临床病例，每个病例中的症状和辨证要素都是布尔变量，只有“出现”和“不出现”两种状态．

表2中的4组症状一辨证要素集合由中医专家给出，用于考察算法发现中医知识的能力．每组集合包括某个常见肺系证候对应的一组辨证要素，以及辨证要素集的相关症状和不相关的干扰症状．

相关症状与干扰症状都是专家手工挑选的，并且专家已经透彻了解这些症状与辨证要素之间的确切关系．因此，将算法得到的结果交给专家评判，就可以评估该算法用于症状一辨证要素相关关系发现的可行性．算法从临床病例中学习得到了各组症状与辨证要素

集合的相关关系图，见图1(a)～(d)．根据专家意见，这4张图很好地反映了辨证要素与症状之间的相关关系，准确区分了相关症状与干扰症状，并且直观地提供了与每个辨证要素直接相关的症状和间接相关的症状等更细致的信息，甚至识别出了容易被专家都忽略的相关关系，如图4中症状“尿少”与要素“饮”具有很强的负相关关系．因此，贝叶斯网络可有效地用于发现症状与辨证要素间的相关关系．

4结语

    本文针对贝叶斯网络杂交学习算法G B P S的缺陷提出了相应的改进算法，其寻优能力相对于G B P S算法和GB D S算法具有较大的优势，准确性也有一定程度的提高．应用该改进算法发现中医症状一辨证要素之间的相关关系的结果与专家经验吻合很好，不仅能发现变量问的直接相关关系和更细致的间接相关关系，还能发现专家可能忽略的知识．算法能直接从数据出发获取知识，这类高效率的数据驱动方法有望克服当前规则基中医专家系统知识

获取效率低下的不足．下一步拟将其应用于中医诊断领域，构建具有自学习功能的中医专家系统，并致力于提高中医诊断的客观性和准确性．