二維k-s檢驗(yàn)的并行算法

1、二維KS檢驗(yàn)檢驗(yàn)的并行算法的并行算法KS檢驗(yàn)是一種常用的無(wú)參估計(jì)，用于檢驗(yàn)兩種經(jīng)驗(yàn)分布是否起源于同一分布。一維KS檢驗(yàn)的做法比較簡(jiǎn)單，也很常用。隨著數(shù)據(jù)處理的需要，人們類似地發(fā)展出了二維KS檢驗(yàn)的算法，并將之廣泛用于天文、地理數(shù)據(jù)以及財(cái)政分析等領(lǐng)域。文章在Cook提出的雙樹(shù)結(jié)構(gòu)算法的基礎(chǔ)上進(jìn)行改進(jìn)，提出了并行算法。隨著數(shù)據(jù)量的增大，這種算法的優(yōu)點(diǎn)更加突出。一、一、KSKS檢驗(yàn)檢驗(yàn)一維KS檢驗(yàn)：F，G是兩個(gè)樣本數(shù)分別為nm的采樣，要判斷它

2、們是否起源于同一分布。統(tǒng)計(jì)量D是這兩個(gè)樣本在統(tǒng)計(jì)分布函數(shù)（cdf）上的最大差異。則一維情況滿足：二維二維KSKS檢驗(yàn)：檢驗(yàn)：與一維KS檢驗(yàn)有類似的統(tǒng)計(jì)關(guān)系，人們已通過(guò)蒙特卡羅方法證實(shí)了這一點(diǎn)。需要提出的是，這里的統(tǒng)計(jì)量D是一個(gè)象限中兩種分布的點(diǎn)數(shù)比例的最大差異值；也就是說(shuō)，要檢查所有可能的象限劃分，找出兩個(gè)樣本分占自己總數(shù)量比例差別最大的象限，這個(gè)最大差異值就是D。類似的統(tǒng)計(jì)關(guān)系如下：Z=Dn12二、以前的算法二、以前的算法假設(shè)兩種樣本

3、擁有n個(gè)數(shù)據(jù)點(diǎn)：1、考慮原點(diǎn)位于每個(gè)樣本點(diǎn)上，這樣的算法需要n2量級(jí)的運(yùn)算量。2、考慮原點(diǎn)的坐標(biāo)是一個(gè)點(diǎn)的橫坐標(biāo)和另一個(gè)點(diǎn)縱坐標(biāo)的結(jié)合。如果采用這種算法，計(jì)算量將達(dá)到n3量級(jí)。對(duì)于大樣本的數(shù)據(jù)，這種算法計(jì)算量太大，不適用。（3）把原點(diǎn)移動(dòng)到第三根線的位置，右子點(diǎn)（3，1）被包括進(jìn)來(lái)T3=(0Ns1Nc)Delta3=delta2t3D=max(abs(delta3)D’)D’=D如此連續(xù)移動(dòng)，可以檢驗(yàn)出所有可能的象限劃分中第二象限的最大

4、差值其他三個(gè)象限的算法與第二象限類似，例如第一象限就從最左邊起算，然后逐步向右。而下面兩個(gè)象限則按y的降序排列重新建立雙樹(shù)結(jié)構(gòu)進(jìn)行計(jì)算。整個(gè)算法的計(jì)算量為O(nlogn)。四、并行算法四、并行算法Cook的算法是從上到下進(jìn)行計(jì)算，每次加入一個(gè)新節(jié)點(diǎn)，不斷發(fā)展雙樹(shù)結(jié)構(gòu)。最后在根部得到差異的最大值。如果我們用多個(gè)處理器同時(shí)進(jìn)行運(yùn)算，會(huì)存在一些問(wèn)題：每個(gè)處理器的運(yùn)算時(shí)間不一樣，就會(huì)存在等待時(shí)間；而且如果A處理器下面的一個(gè)亞支是由B處理器計(jì)算的

5、，B還未計(jì)算到此處的話，A就必須等待。而并行算法的基本思路是首先建立整個(gè)雙樹(shù)結(jié)構(gòu)，把整個(gè)樹(shù)分成平行的幾支，用多個(gè)處理器同時(shí)由下向上進(jìn)行計(jì)算，在根部找出最大差異。由于樹(shù)的結(jié)構(gòu)是平行的，處理器之間相互等待的時(shí)間會(huì)大大減少。采用并行算法有兩個(gè)需要注意的問(wèn)題:第一、每個(gè)處理器的運(yùn)算量要基本一致；第二、盡量減少處理器中途的交流，也就是說(shuō)匯合的節(jié)點(diǎn)盡量在根部。理想的情況如下圖：平衡處理器運(yùn)算量的方法：平衡處理器運(yùn)算量的方法：假設(shè)現(xiàn)有N個(gè)處理器，我們