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

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

2、的统计关系，人们已通过蒙特卡罗方法证实了这一点。需要提出的是，这里的统计量D 是一个象限中两种分布的点数比例的最大差异值；也就是说， 要检查所有可能的象限划分，找出两个样本分占自己总数量比例差别最大的象限，这个最大差异值就是D。类似的统计关系如下：Z = D n1/2二、以前的算法假设两种样本拥有n 个数据点：1、考虑原点位于每个样本点上，这样的算法需要n2 量级的运算量。2、考虑原点的坐标是一个点的横坐标和另一个点纵坐标的结合。如果采用这种算法，计算量将达到n3 量级。对于大样本的数据，这种算法计算量太大，不适用。三、 Cook的双树结构算法征对传统算法计算量太大的问题，Cook （ 199

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

4、根线的位置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+t3D=max(abs(delta3),D )D =D如此连

5、续移动，可以检验出所有可能的象限划分中第二象限的最大差值其他三个象限的算法与第二象限类似，例如第一象限就从最左边起算，然后逐步向右。而下面两个象限则按 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）并行算法的使用，提