【摘要】：隨著智能時代的到來,各種各樣的大數(shù)據(jù)信息系統(tǒng)相繼建立,人類迫切需要在大數(shù)據(jù)背景下進行數(shù)據(jù)分析和決策。由于數(shù)據(jù)規(guī)模的膨脹,如何從大規(guī)模數(shù)據(jù)中挖掘出相關關系成為了一項重要的研究課題。如何解決維度爆炸帶來的算法時間復雜度上升,也是一個重要的問題。貝葉斯網(wǎng)絡(BayesianNetworks,BN)是概率統(tǒng)計與圖論相結(jié)合的一種概率圖模型(Probabilistic Graphical Models),是不確定知識表達和推理領域有效的理論模型之一。自1988年由Pearl提出該模型后,逐漸成為近幾年研究的熱點。貝葉斯網(wǎng)絡清晰地表達了各個節(jié)點之間的因果關系,能夠利用現(xiàn)有數(shù)據(jù)分析不確定事件發(fā)生的概率。條件獨立性檢驗算法方面,Gary等人基于核方法的兩樣本分析(Kernel-based two-sample Test)的思想,利用最大平均差異(maximum mean discrepancy,下文用MMD表示)算法度量分布的差異性,進而利用統(tǒng)計假設檢驗設計了 一種檢驗條件獨立性的算法KCIPT(Kernel Conditional Independence Permutation Test)。本文從Gary的KCIPT算法出發(fā),利用貝葉斯網(wǎng)絡相關理論,將核方法與統(tǒng)計假設檢驗相結(jié)合,通過大量的實驗和模型改進,得到了新的算法KCICPT(Kernel Conditional Independence Cluster Permutation Test)。該算法解決了 KCIPT 算法不適用于大樣本量數(shù)據(jù)的問題。本文的主要研究工作如下:(1)通過K-means聚類處理,降低了 KCIPT算法在高維度樣本上進行置換優(yōu)化的時間復雜度。我們將聚類后的結(jié)果按各個聚類分別進行置換,然后進行合并以得到整體的置換結(jié)果,從而整體上降低了置換優(yōu)化的時間。將置換優(yōu)化的時間復雜度由O(N3)降低到O(nm3)。其中n和m遠遠小于N,N為輸入數(shù)據(jù)的樣本個數(shù),n為聚類后類別的個數(shù),m是聚類后每個類內(nèi)的樣本個數(shù)上限。(2)通過矩陣分解處理Gram矩陣,從而得到了一個Gram矩陣的低秩表示,從而獲取一個低時間復雜度的算法,降低了計算MMD的時間復雜度。時間復雜度由O(N2)降低到O(m2N),其中m為不完全Cholesky分解時進行低秩近似的維度,其值遠遠小于N 。N同樣為輸入數(shù)據(jù)的樣本個數(shù)。(3)通過高斯分布計算P值,我們解決了 MMD值的時間復雜度之后,利用模擬樣本的均值和方差直接計算P值,從而將原本需要隨機擾亂的時間開銷從O(MN)轉(zhuǎn)化為O(m)。其中m遠遠小于M、N, M為蒙特卡洛迭代次數(shù),N為輸入數(shù)據(jù)的樣本個數(shù),m為實際進行的隨機擾亂次數(shù)。綜上所述,本文的創(chuàng)新點主要體現(xiàn)在三個部分,第一是利用聚類方法降低置換優(yōu)化的時間復雜度。第二是利用矩陣分解構(gòu)建Gram矩陣的低秩表示降低計算MMD表達式的時間復雜度。第三是通過高斯分布減少了計算P值所需要的時間復雜度。實驗表明,在Sachs (2005)數(shù)據(jù)集上,進行連續(xù)類型數(shù)據(jù)的網(wǎng)絡推斷,該算法能夠有效地推斷網(wǎng)絡結(jié)構(gòu),有向調(diào)控網(wǎng)絡復現(xiàn)效果優(yōu)于傳統(tǒng)的非核方法的算法。
文內(nèi)圖片：
圖片說明： 獨立的假設。若條件獨立不被拒絕，每一個屬于的Ｘｉ與ｙｉ滿足獨立性關系，分逡逑別來自于Ｐｘ｜ｚ和Ｐｙ｜ｚ。對于ｉ與；不相同的部分樣本，我們可以發(fā)現(xiàn)Ａ等于ｚｙ。離散逡逑條件下的置換過程如圖４－１所示，置換Ｆ變量后判斷條件獨立的情況。逡逑Ｐｘｙｚ邐Ｐｘ｜ｚＰｙ｜ｚＰｚ逡逑Ｘ邋Ｙ邋Ｚ邐Ｘ邋Ｙ邋Ｚ逡逑■邋■邐■■逡逑？邐？逡逑■■■邐■■■逡逑■■■邐■■■逡逑■邋■邐■■逡逑■邋■邐■■逡逑■■■邐■■■逡逑■■■邐■■■逡逑Ｔｗｏ－Ｓａｍｐｌｅ邋Ｔｅｓｔ逡逑圖４－１條件獨立性檢驗１１６１逡逑Ｆｉｇｕｒｅ邋４－１邋Ｃｏｎｄｉｔｉｏｎａｌ邋Ｉｎｄｅｐｅｎｄｅｎｃｅ邋Ｔｅｓｔ１＇６＇逡逑離散的條件下，只要保證置換后的％與ｚｒ沒有一一對應即可。連續(xù)的情況下，，逡逑每一次對ｚ的觀測都是唯一的。這種情況下，我們只能近似地去構(gòu)建一個相對獨逡逑立的分布。我們可以按照樣本的集合表示定義這個問題，設樣本表示為逡逑／３邋＝邋0ｃ，ｙ，ｚ；｝，變量；ｃ、｝／、ｚ的維度為ｎ。設Ｐ為一個線性轉(zhuǎn)換，其數(shù)學表示為只含逡逑０１元素的方陣。這樣可以定義一個轉(zhuǎn)換樣本此處的Ｐｙ等于ｙ的逡逑線性變換。Ｐ中第ｉ項如下式表示：逡逑ＩｊＰｉｊｙｊ邐（４－７）逡逑為了更加嚴格地定義Ｐ矩陣，引入如下命題：逡逑令７１為關于Ｐ的線性轉(zhuǎn)換集合，對于所有ｚ５邋ｅ邋７％滿足ｍｅａｎ（Ｐｙ）邋＝邋ｍｅａｎ（ｙ），逡逑２４逡逑
文內(nèi)圖片：
圖片說明： 該算法獲取到指定節(jié)點ｘ、節(jié)點集ｚ后，第一步，將節(jié)點數(shù)據(jù)分割為兩個逡逑部分，一部分／２⑴保留不變，另一個部分／２（２）進行置換優(yōu)化，構(gòu)建到一個Ｇｒａｍ逡逑矩陣當中，從而計算統(tǒng)計檢驗值（＾ａ沿ｆ／ｃ）。構(gòu)建方法如圖４－３所示，通過拼接樣逡逑本／２⑴和巧２），統(tǒng)一到同一個Ｇｒａｍ矩陣當中。進而在該矩陣上進行第一步的最逡逑大平均差異（ＭＭＤ）的計算。逡逑２７逡逑
【學位授予單位】：北京交通大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：Q811.4;TP18

【參考文獻】

相關期刊論文 前1條

1 占愛瑤;羅培高;;DNA測序技術概述[J];生物技術通訊;2011年04期

本文編號：2514371