基于约束的局部-全局LWF链图结构学习算法

LWF链图结构学习旨在发现链图中所有节点的父节点、子节点、邻居节点以及配偶节点.然而,目前最新的LWF链图结构学习算法是基于Growing-Shrinking(GS)思想得到节点的局部结构(即节点的马尔科夫毯)来学习全局网络结构,该类算法的条件独立测试是以整个马尔科夫毯为条件集的,为了保证条件独立测试的可靠性,算法要求样本数量是马尔科夫毯大小的指数级,从而使得算法的数据效率较差.针对该问题,本文提出了一种基于约束的局部-全局LWF链图结构学习算法.该算法通过迭代的学习邻接集和配偶集来降低对数据样本量的要求;与此同时,在学习邻接集时采用后向策略保障了条件独立测试的正确性.算法的基本思想如下:首先学习网络中每个节点的马尔科夫毯,将节点马尔科夫毯学习拆分为学习邻接集和学习配偶集;然后利用节点的马尔科夫毯信息恢复网络骨架,根据链图复合体有向边的特点,利用条件独立测试确定网络复合体有向边,从而恢复链图结构.理论分析证明了该算法的正确性,在仿真数据集和标准数据集上的实验测试验证了算法的有效性.