Kolmogorov–Smirnov测试

今天看Apache Flink是怎么测试streaming data的random sampling的. 然后看到里面测试代码(https://github.com/apache/flink/blob/master/flink-java/src/test/java/org/apache/flink/api/java/sampling/RandomSamplerTest.java)用的是Kolmogorov–Smirnov测试, 就查了一下相关的文献, 发现这个测试真是好用.

首先, 这个测试有很多的用法, 我使用它的原因主要是用于测试sampling是否是随机的. 在分布式系统下的sampling, 不能紧紧通过观察结果就判断当前抽样函数是否是随机抽样, 这个测试可以快速的测试一个expected result(期待函数的抽样结果)和一个actual result(当前函数的实际抽样结果), 通过勾画两个生成抽样的函数, 找到其中排序后, 每个误差最大值, 然后累计相加, 取生成一个p值, 通过对比p值和d值(d值为一个固定量), 可以直到当前抽样是否接近于随机抽样. p如果小于d,则是类随机抽样, 反之则否.

p的公式很复杂, 但是代码很易懂,这里上下代码:

//x和y是两组抽样结果, 通过这个函数, 返回p值, 这个函数可以判断这两个结构是不是来自于同一个抽样函数
public double kolmogorovSmirnovStatistic(double[] x, double[] y) {
        this.checkArray(x);
        this.checkArray(y);
        double[] sx = MathArrays.copyOf(x);
        double[] sy = MathArrays.copyOf(y);
        Arrays.sort(sx);//排序
        Arrays.sort(sy);
        int n = sx.length;
        int m = sy.length;
        double supD = 0.0D;//初始化结果

        int i;
        double cdf_y;
        int xIndex;
        double cdf_x;
        double curD;
        for(i = 0; i < n; ++i) {//遍历x, 然后找x在y中的位置
            cdf_y = ((double)i + 1.0D) / (double)n;
            xIndex = Arrays.binarySearch(sy, sx[i]);
            cdf_x = xIndex >= 0?((double)xIndex + 1.0D) / (double)m:((double)(-xIndex) - 1.0D) / (double)m;//位置
            curD = FastMath.abs(cdf_y - cdf_x);
            if(curD > supD) {//取最大
                supD = curD;
            }
        }

        for(i = 0; i < m; ++i) {//遍历y, 找y在x中的位置
            cdf_y = ((double)i + 1.0D) / (double)m;
            xIndex = Arrays.binarySearch(sx, sy[i]);
            cdf_x = xIndex >= 0?((double)xIndex + 1.0D) / (double)n:((double)(-xIndex) - 1.0D) / (double)n;
            curD = FastMath.abs(cdf_x - cdf_y);
            if(curD > supD) {
                supD = curD;
            }
        }

        return supD;
    }

然后d值是一个固定值, 取决于两个样本集合的大小:

//m和n是样本集合的大小
private double getDValue(int m, int n) {
		Preconditions.checkArgument(m > 0, "input sample size should be positive.");
		Preconditions.checkArgument(n > 0, "input sample size should be positive.");
		double first = (double) m;
		double second = (double) n;
		return 1.63 * Math.sqrt((first + second) / (first * second));
	}

注意, 这里的1.63不是个常数!, 是需要查表: 表在

https://www.webdepot.umontreal.ca/Usagers/angers/MonDepotPublic/STT3500H10/Critical_KS.pdf

其中a是critical value