二維K-S檢驗的并行算法

1、維K-S檢驗的并行算法K-S檢驗是一種常用的無參估計，用于檢驗兩種經(jīng)驗分布是否起源于同一分布。一維K-SK-S檢驗的做法比較簡單，也很常用。隨著數(shù)據(jù)處理的需要，人們類似地發(fā)展出了二維Cook提出的雙檢驗的算法，并將之廣泛用于天文、地理數(shù)據(jù)以及財政分析等領域。文章在樹結(jié)構算法的基礎上進行改進，提出了并行算法。隨著數(shù)據(jù)量的增大，這種算法的優(yōu)點更加突出。、K-S檢驗一維K-S檢驗：F, G是兩個樣本數(shù)分別為n, m的采樣，要判斷它們是否起源于同分布。統(tǒng)計量 D是這兩個樣本在統(tǒng)計分布函數(shù)（cdf）上的最大差異。則一維情況滿足:mn也+Jimx(耳仗)-Gm©) >D< 2已-22

2、二維K-S檢驗：與一維K-S檢驗有類似的統(tǒng)計關系，人們已通過蒙特卡羅方法證實了這一點。需要提出的是，這里的統(tǒng)計量D是一個象限中兩種分布的點數(shù)比例的最大差異值；也就是說，要檢查所有可能的象限劃分，找出兩個樣本分占自己總數(shù)量比例差別最大的 象限，這個最大差異值就是 D。類似的統(tǒng)計關系如下:PD > Zoo) < 2廠込2ZZocZ = D n1/2、以前的算法假設兩種樣本擁有 n個數(shù)據(jù)點:1考慮原點位于每個樣本點上，這樣的算法需要2n2量級的運算量。2、考慮原點的坐標是一個點的橫坐標和另一個點縱坐標的結(jié)合。如果采用這種算法,3計算量將達到 n3量級。對于大樣本的數(shù)據(jù)，這種算法計算量太大

3、，不適用。三、Cook的雙樹結(jié)構算法征對傳統(tǒng)算法計算量太大的問題，Cook （1999）提出了雙樹結(jié)構算法。這種算法只需 要O（nlogn）的運算量。先把數(shù)據(jù)按照y值的大小排序。對于一、二象限，沿y軸從上到下進行計算，構建出雙樹結(jié)構。在掃描中每遇到一個新的數(shù)據(jù)點就增加一個新節(jié)點。這樣構建出的雙樹形結(jié)構,總是滿足:(1)左子點x值 母點X值右子點x值(2)子點y值 母點y值無論y值如何，只要x1x2,貝y點1 一定在點2的左邊F面以第二象限為例，舉一個簡單的例子: (4,4) （r2）(1,2)方框代表一組樣本，圓圈代表另一組樣本Ns:方框數(shù)Nc:圓圈數(shù)（1）從最左邊的點（1 , 2）開始（注意

4、它沒有子點），原點在第一根線的位置t1= (1/ Ns-0 / Nc )7點（1 , 2）本身帶來的比例差異delta仁t17此時第2象限的比例差異D=delta17最大比例差(2,3)D (3J)（2）把原點移動到第二根線的位置，母點（2, 3）被包括進來t2= (0/ Ns-1/ Nc)7點（2, 3）本身帶來的比例差異Delta2= delta1+t27此時第2象限的比例差異D=max(abs(delta1),abs(delta2)7最大比例差D 'D(3)把原點移動到第三根線的位置，右子點(3，1)被包括進來T3= (0/ Ns-1/ Nc)Delta3= delta2+t3D

5、=max(abs(delta3),D 'D 'D如此連續(xù)移動，可以檢驗出所有可能的象限劃分中第二象限的最大差值其他三個象限的算法與第二象限類似，例如第一象限就從最左邊起算，然后逐步向右。而下面兩個象限則按y的降序排列重新建立雙樹結(jié)構進行計算。整個算法的計算量為O(nlogn)。四、并行算法Cook的算法是從上到下進行計算，每次加入一個新節(jié)點，不斷發(fā)展雙樹結(jié)構。最后在根部得到差異的最大值。 如果我們用多個處理器同時進行運算，會存在一些問題：每個處理器的運算時間不一樣，就會存在等待時間；而且如果A處理器下面的一個亞支是由B處理器計算的，B還未計算到此處的話， A就必須等待。而并行算

6、法的基本思路是首先建立整個雙樹結(jié)構，把整個樹分成平行的幾支，用多個處理器同時由下向上進行計算，在根部找出最大差異。 由于樹的結(jié)構是平行的， 處理器之間相 互等待的時間會大大減少。采用并行算法有兩個需要注意的問題：第一、每個處理器的運算量要基本一致；第二、盡量減少處理器中途的交流，也就是說匯合的節(jié)點盡量在根部。理想的情況如下圖:平衡處理器運算量的方法:假設現(xiàn)有N個處理器，我們需要在雙樹結(jié)構的根部附近把數(shù)據(jù)分成N等分，盡量使每個處理器中有相等的節(jié)點數(shù)。我們從數(shù)據(jù)點中隨機采樣1000個點，把它們按 X值得大小排序。每1000/N位置的X值大小作為劃分點， 把數(shù)據(jù)分為N等分。但這樣劃分其實默認數(shù)據(jù)的X，Y值是無關的，實際上的情況可能是X值小，丫值也小，X值大的位置，丫值也大。30%;就把原來劃所以，每計算2000個點，要檢查下每個處理器的負荷量，如果差異超過 分點的X值進行平均作為新的劃分點再進行計算。五、試驗結(jié)果000個樣本兩種情況(1)0，1之間的均勻分布，考慮有 20，000和200,IHIbZOWew-H 3Wj«n p.1| kmmqvqnn g仙"Woq1啊 里BKdEK<anrow-1410(2)標準正態(tài)分布，處理過程中平衡和不平衡數(shù)據(jù)量的差別六、結(jié)論(1 )并行算法的使