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

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

2、以前的算法假設兩種樣本擁有n個數(shù)據(jù)點：.一2、一一1、考慮原點位于每個樣本點上，這樣的算法需要n量級的運算量。2、考慮原點的坐標是一個點的橫坐標和另一個點縱坐標的結合。如果采用這種算法，3計算量將達到n3量級。對于大樣本的數(shù)據(jù)，這種算法計算量太大，不適用。三、Cook的雙樹結構算法征對傳統(tǒng)算法計算量太大的問題，Cook(1999)提出了雙樹結構算法。這種算法只需要O(nlogn)的運算量。先把數(shù)據(jù)按照y值的大小排序。對于一、二象限，沿y軸從上到下進行計算，構建出雙樹結構。在掃描中每遇到一個新的數(shù)據(jù)點就增加一個新節(jié)點。這樣構建出的雙樹形結構，總是滿足：(1)左子點x值母點x彳！右子點x值(2)子

3、點y值母點y值(3)無論y值如何，只要x1x2,則點1一定在點2的左邊下面以第二象限為例，舉一個簡單的例子：方框代表一組樣本，圓圈代表另一組樣本Ns：方框數(shù)Nc：圓圈數(shù)(1)從最左邊的點(1,2)開始(注意它沒有子點)，原點在第一根線的位置t1=(1/Ns-0/Nc)一點(1,2)本身帶來的比例差異delta1=t1一此時第2象限的比例差異D=delta1一最大比例差(2)把原點移動到第二根線的位置，母點(2,3)被包括進來t2=(0/Ns-1/Nc)一點(2,3)本身帶來的比例差異Delta2=delta1+t2一此時第2象限的比例差異D=max(abs(delta1),abs(delta2

4、)一最大比例差D=D(3)把原點移動到第三根線的位置，右子點(3,1)被包括進來T3=(0/Ns-1/Nc)Delta3=delta2+t3D=max(abs(delta3),D)D=D如此連續(xù)移動，可以檢驗出所有可能的象限劃分中第二象限的最大差值其他三個象限的算法與第二象限類似，例如第一象限就從最左邊起算，然后逐步向右。而下面兩個象限則按y的降序排列重新建立雙樹結構進行計算。整個算法的計算量為O(nlogn)。四、并行算法Cook的算法是從上到下進行計算，每次加入一個新節(jié)點，不斷發(fā)展雙樹結構。最后在根部得到差異的最大值。如果我們用多個處理器同時進行運算，會存在一些問題：每個處理器的運算時間不

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