二维K-S检验的并行算法

1、二维K-S检验的并行算法K-S检验是一种常用的无参估计，用于检验两种经验分布是否起源于同一分布。一维K-S检验的做法比较简单，也很常用。随着数据处理的需要，人们类似地发展出了二维K-S检验的算法，并将之广泛用于天文、地理数据以及财政分析等领域。文章在Cook提出的双树结构算法的基础上进行改进，提出了并行算法。随着数据量的增大，这种算法的优点更加突出。一、K-S检验一维K-S检验：F, G是两个样本数分别为 n, m的采样，要判断它们是否起源于同 一分布。统计量 D是这两个样本在统计分布函数( cdf)上的最大差异。则一维情况满足：皿x(6(f)>D)< 2-2/'二维K-S

2、检验：与一维K-S检验有类似的统计关系，人们已通过蒙特卡罗方法证实 了这一点。需要提出的是，这里的统计量 D是一个象限中两种分布的点数比例的最大差异 值；也就是说，要检查所有可能的象限划分， 找出两个样本分占自己总数量比例差别最大的 象限，这个最大差异值就是 D。类似的统计关系如下：P(D > Z-) < 2厂2Zg2弟=1-0.53-7 c 1/2Z = D n二、以前的算法假设两种样本拥有 n个数据点：一 2 、一一1、考虑原点位于每个样本点上，这样的算法需要n量级的运算量。2、考虑原点的坐标是一个点的横坐标和另一个点纵坐标的结合。如果采用这种算法，3计算量将达到 n3量级。对

3、于大样本的数据，这种算法计算量太大，不适用。三、Cook的双树结构算法征对传统算法计算量太大的问题，Cook (1999)提出了双树结构算法。这种算法只需要O(nlogn)的运算量。先把数据按照y值的大小排序。对于一、二象限，沿y轴从上到下进行计算，构建出双树结构。在扫描中每遇到一个新的数据点就增加一个新节点。这样构建出的双树形结构， 总是满足：(1)左子点x值母点x彳！<右子点x值(2)子点y值母点y值(3)无论y值如何，只要x1<x2,则点1 一定在点2的左边下面以第二象限为例，举一个简单的例子：方框代表一组样本，圆圈代表另一组样本Ns：方框数 Nc：圆圈数(1)从最左边的点(

4、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) 一最大比例差D'=D(3) 把原点移动到第三根线的位置，右子点(3, 1)被包括进来T3= (0/ Ns-1/ Nc)Delta3= delta2+

5、t3D=max(abs(delta3),D ')D'=D如此连续移动，可以检验出所有可能的象限划分中第二象限的最大差值其他三个象限的算法与第二象限类似，例如第一象限就从最左边起算，然后逐步向右。而下面两个象限则按y的降序排列重新建立双树结构进行计算。整个算法的计算量为O(nlogn)。四、并行算法Cook的算法是从上到下进行计算，每次加入一个新节点，不断发展双树结构。最后在根部得到差异的最大值。如果我们用多个处理器同时进行运算，会存在一些问题：每个处理器的运算时间不一样，就会存在等待时间；而且如果A处理器下面的一个亚支是由B处理器计算的，B还未计算到此处的话， A就必须等待。而

6、并行算法的基本思路是首先建立整个双树结构，把整个树分成平行的几支，用多个处理器同时由下向上进行计算，在根部找出最大差异。 由于树的结构是平行的，处理器之间相互等待的时间会大大减少。采用并行算法有两个需要注意的问题：第一、每个处理器的运算量要基本一致；第二、尽量减少处理器中途的交流，也就是说汇合的节点尽量在根部。平衡处理器运算量的方法：N等分，尽量使每假设现有N个处理器，我们需要在双树结构的根部附近把数据分成个处理器中有相等的节点数。我们从数据点中随机采样1000个点，把它们按X值得大小排序。每1000/N位置的X值大小作为划分点， 把数据分为N等分。但这样划分其实默认数据 的X, Y值是无关的，实际上的情况可能是X值小，Y值也小，X值大的位置，Y值也大。所以，每计算2000个点，要检查下每个处理器的负荷量，如果差异超过30%;就把原来划分点的X值进行平均作为新的划分点再进行计算。五、试验结果(1) 0, 1之间的均匀分布，考虑有20, 000和200, 000个样本两种情况(2)标准正态分布，处理过程中平衡和不平衡数据量的差别六、结论(1)并行算法的使用，提