论文部分内容阅读
挖掘数据中蕴含的因果关系是自然科学研究的一个基本问题.近年来,尽管很多研究者致力于从可观测数据中寻找其中可能存在的因果关系,但是在高维数据集下,现时的因果发现算法依然面对着两大困难:1)高维数据下算法的准确率低;2)高维数据下的时间复杂度太高.因而,这些方法很难高效地应用到高维数据集进行因果关系挖掘.在本文的工作中,我们提出了一种三阶段因果发现算法.该第一阶段,利用基于最大相关性和最小冗余度的贪婪搜索方法寻找因果候选网络骨架;第二阶段,利用基于条件独立性测试的方法精炼因果候选网络骨架,得到精确的因果网络骨架;第三阶段,利用信息-几何模型对网络骨架中结点间边的方向进行推断,最终得到一个完整的因果网络结构图.具体来说,本论文的主要工作及创新点有:(1)高维数据下因果网络结构主要面对的是准确率低和时间复杂度高的问题.为了解决这一问题,引入了数据挖掘中特征选择方法,提出一种基于最大相关性和最小冗余度的能够快速且有效地寻找到一个候选因果网络骨架的方法,并从理论上和实验中证实其的可靠性.(2)基于上一步的结果,通过基于条件独立性测试的算法,在较低维的候选因果网络骨架下学习出精确的因果网络骨架.为了能在非线性数据下依然能学习出较好的因果骨架,算法采用了Kun Zhang等人提出的核条件独立测试方法代替传统的独立测试方法,其能够在样本量规模较小的非线性数据集中得到良好的结果.(3)根据数据的非线性属性,采用Janzing等人提出的信息-几何模型进行方向推断.该模型打破了变量间的对称关系,能从信息-几何角度上识别出变量间的因果关系,解决了传统因果网络方法无法处理马尔可夫等价类的不足.结合上一步得到的精确的因果网络骨架,可以在高维数据下更好地识别变量间的因果关系.我们从理论上分析了算法的有效性,然后分别在虚拟数据,真实网络结构和真实的高维数据集下进行了实验,并与两种主流的因果推断算法进行比较,实验结果表明了提出的算法在解决高维数据集因果关系识别这一问题上的有效性和稳定性.