基于KCICPT算法的基因调控网络结构学习研究
发布时间：2019-07-14 11:57
【摘要】：随着智能时代的到来,各种各样的大数据信息系统相继建立,人类迫切需要在大数据背景下进行数据分析和决策。由于数据规模的膨胀,如何从大规模数据中挖掘出相关关系成为了一项重要的研究课题。如何解决维度爆炸带来的算法时间复杂度上升,也是一个重要的问题。贝叶斯网络(BayesianNetworks,BN)是概率统计与图论相结合的一种概率图模型(Probabilistic Graphical Models),是不确定知识表达和推理领域有效的理论模型之一。自1988年由Pearl提出该模型后,逐渐成为近几年研究的热点。贝叶斯网络清晰地表达了各个节点之间的因果关系,能够利用现有数据分析不确定事件发生的概率。条件独立性检验算法方面,Gary等人基于核方法的两样本分析(Kernel-based two-sample Test)的思想,利用最大平均差异(maximum mean discrepancy,下文用MMD表示)算法度量分布的差异性,进而利用统计假设检验设计了 一种检验条件独立性的算法KCIPT(Kernel Conditional Independence Permutation Test)。本文从Gary的KCIPT算法出发,利用贝叶斯网络相关理论,将核方法与统计假设检验相结合,通过大量的实验和模型改进,得到了新的算法KCICPT(Kernel Conditional Independence Cluster Permutation Test)。该算法解决了 KCIPT 算法不适用于大样本量数据的问题。本文的主要研究工作如下:(1)通过K-means聚类处理,降低了 KCIPT算法在高维度样本上进行置换优化的时间复杂度。我们将聚类后的结果按各个聚类分别进行置换,然后进行合并以得到整体的置换结果,从而整体上降低了置换优化的时间。将置换优化的时间复杂度由O(N3)降低到O(nm3)。其中n和m远远小于N,N为输入数据的样本个数,n为聚类后类别的个数,m是聚类后每个类内的样本个数上限。(2)通过矩阵分解处理Gram矩阵,从而得到了一个Gram矩阵的低秩表示,从而获取一个低时间复杂度的算法,降低了计算MMD的时间复杂度。时间复杂度由O(N2)降低到O(m2N),其中m为不完全Cholesky分解时进行低秩近似的维度,其值远远小于N 。N同样为输入数据的样本个数。(3)通过高斯分布计算P值,我们解决了 MMD值的时间复杂度之后,利用模拟样本的均值和方差直接计算P值,从而将原本需要随机扰乱的时间开销从O(MN)转化为O(m)。其中m远远小于M、N, M为蒙特卡洛迭代次数,N为输入数据的样本个数,m为实际进行的随机扰乱次数。综上所述,本文的创新点主要体现在三个部分,第一是利用聚类方法降低置换优化的时间复杂度。第二是利用矩阵分解构建Gram矩阵的低秩表示降低计算MMD表达式的时间复杂度。第三是通过高斯分布减少了计算P值所需要的时间复杂度。实验表明,在Sachs (2005)数据集上,进行连续类型数据的网络推断,该算法能够有效地推断网络结构,有向调控网络复现效果优于传统的非核方法的算法。
文内图片：
图片说明： 独立的假设。若条件独立不被拒绝，每一个属于的Ｘｉ与ｙｉ满足独立性关系，分逡逑别来自于Ｐｘ｜ｚ和Ｐｙ｜ｚ。对于ｉ与；不相同的部分样本，我们可以发现Ａ等于ｚｙ。离散逡逑条件下的置换过程如图４－１所示，置换Ｆ变量后判断条件独立的情况。逡逑Ｐｘｙｚ逦Ｐｘ｜ｚＰｙ｜ｚＰｚ逡逑Ｘ邋Ｙ邋Ｚ逦Ｘ邋Ｙ邋Ｚ逡逑■邋■逦■■逡逑？逦？逡逑■■■逦■■■逡逑■■■逦■■■逡逑■邋■逦■■逡逑■邋■逦■■逡逑■■■逦■■■逡逑■■■逦■■■逡逑Ｔｗｏ－Ｓａｍｐｌｅ邋Ｔｅｓｔ逡逑图４－１条件独立性检验１１６１逡逑Ｆｉｇｕｒｅ邋４－１邋Ｃｏｎｄｉｔｉｏｎａｌ邋Ｉｎｄｅｐｅｎｄｅｎｃｅ邋Ｔｅｓｔ１＇６＇逡逑离散的条件下，只要保证置换后的％与ｚｒ没有一一对应即可。连续的情况下，，逡逑每一次对ｚ的观测都是唯一的。这种情况下，我们只能近似地去构建一个相对独逡逑立的分布。我们可以按照样本的集合表示定义这个问题，设样本表示为逡逑／３邋＝邋0ｃ，ｙ，ｚ；｝，变量；ｃ、｝／、ｚ的维度为ｎ。设Ｐ为一个线性转换，其数学表示为只含逡逑０１元素的方阵。这样可以定义一个转换样本此处的Ｐｙ等于ｙ的逡逑线性变换。Ｐ中第ｉ项如下式表示：逡逑ＩｊＰｉｊｙｊ逦（４－７）逡逑为了更加严格地定义Ｐ矩阵，引入如下命题：逡逑令７１为关于Ｐ的线性转换集合，对于所有ｚ５邋ｅ邋７％满足ｍｅａｎ（Ｐｙ）邋＝邋ｍｅａｎ（ｙ），逡逑２４逡逑
文内图片：
图片说明： 该算法获取到指定节点ｘ、节点集ｚ后，第一步，将节点数据分割为两个逡逑部分，一部分／２⑴保留不变，另一个部分／２（２）进行置换优化，构建到一个Ｇｒａｍ逡逑矩阵当中，从而计算统计检验值（＾ａ沿ｆ／ｃ）。构建方法如图４－３所示，通过拼接样逡逑本／２⑴和巧２），统一到同一个Ｇｒａｍ矩阵当中。进而在该矩阵上进行第一步的最逡逑大平均差异（ＭＭＤ）的计算。逡逑２７逡逑
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：Q811.4;TP18
本文编号：2514371
文内图片：
图片说明： 独立的假设。若条件独立不被拒绝，每一个属于的Ｘｉ与ｙｉ满足独立性关系，分逡逑别来自于Ｐｘ｜ｚ和Ｐｙ｜ｚ。对于ｉ与；不相同的部分样本，我们可以发现Ａ等于ｚｙ。离散逡逑条件下的置换过程如图４－１所示，置换Ｆ变量后判断条件独立的情况。逡逑Ｐｘｙｚ逦Ｐｘ｜ｚＰｙ｜ｚＰｚ逡逑Ｘ邋Ｙ邋Ｚ逦Ｘ邋Ｙ邋Ｚ逡逑■邋■逦■■逡逑？逦？逡逑■■■逦■■■逡逑■■■逦■■■逡逑■邋■逦■■逡逑■邋■逦■■逡逑■■■逦■■■逡逑■■■逦■■■逡逑Ｔｗｏ－Ｓａｍｐｌｅ邋Ｔｅｓｔ逡逑图４－１条件独立性检验１１６１逡逑Ｆｉｇｕｒｅ邋４－１邋Ｃｏｎｄｉｔｉｏｎａｌ邋Ｉｎｄｅｐｅｎｄｅｎｃｅ邋Ｔｅｓｔ１＇６＇逡逑离散的条件下，只要保证置换后的％与ｚｒ没有一一对应即可。连续的情况下，，逡逑每一次对ｚ的观测都是唯一的。这种情况下，我们只能近似地去构建一个相对独逡逑立的分布。我们可以按照样本的集合表示定义这个问题，设样本表示为逡逑／３邋＝邋0ｃ，ｙ，ｚ；｝，变量；ｃ、｝／、ｚ的维度为ｎ。设Ｐ为一个线性转换，其数学表示为只含逡逑０１元素的方阵。这样可以定义一个转换样本此处的Ｐｙ等于ｙ的逡逑线性变换。Ｐ中第ｉ项如下式表示：逡逑ＩｊＰｉｊｙｊ逦（４－７）逡逑为了更加严格地定义Ｐ矩阵，引入如下命题：逡逑令７１为关于Ｐ的线性转换集合，对于所有ｚ５邋ｅ邋７％满足ｍｅａｎ（Ｐｙ）邋＝邋ｍｅａｎ（ｙ），逡逑２４逡逑
文内图片：
图片说明： 该算法获取到指定节点ｘ、节点集ｚ后，第一步，将节点数据分割为两个逡逑部分，一部分／２⑴保留不变，另一个部分／２（２）进行置换优化，构建到一个Ｇｒａｍ逡逑矩阵当中，从而计算统计检验值（＾ａ沿ｆ／ｃ）。构建方法如图４－３所示，通过拼接样逡逑本／２⑴和巧２），统一到同一个Ｇｒａｍ矩阵当中。进而在该矩阵上进行第一步的最逡逑大平均差异（ＭＭＤ）的计算。逡逑２７逡逑
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：Q811.4;TP18
【参考文献】
相关期刊论文 前1条
1 占爱瑶;罗培高;;DNA测序技术概述[J];生物技术通讯;2011年04期
本文编号：2514371
本文链接：https://www.wllwen.com/kejilunwen/jiyingongcheng/2514371.html
最近更新
教材专著
