5
\$\begingroup\$

I'm trying to compare two lists of floating point data and see if they might have come from different underlying distributions. The two samples are a before and after, so by comparing the two I thought I could detect whether any change occurred between the two timeframes.

To do this I'm using the two-sample Kolmogorov-Smirnov test. I have the following function which calculates the core statistic used in the test:

def kolmogorov_smirnov(data1, data2):
    """
    Given two lists of data, finds the two-sample Kolmogorov–Smirnov statistic
    """
    data1 = sorted(data1)
    data2 = sorted(data2)

    index1 = 0
    index2 = 0

    ks_stat = 0

    while index1 < len(data1) and index2 < len(data2):
        if data1[index1] == data2[index2]:
            index1 += 1
            index2 += 1

        elif data1[index1] < data2[index2]:
            index1 += 1

        elif data1[index1] > data2[index2]:
            index2 += 1

        ks_stat = max(ks_stat, abs(index1/len(data1) - index2/len(data2)))

    return ks_stat

I realise that I can also shorten the while loop like so:

while index1 < len(data1) and index2 < len(data2):
    if data1[index1] <= data2[index2]:
        index1 += 1

    if data1[index1] >= data2[index2]:
        index2 += 1

    ks_stat = max(ks_stat, abs(index1/len(data1) - index2/len(data2)))

Which version should I use? Also, is there anything worth pointing out about the main code?

\$\endgroup\$
4
\$\begingroup\$
  • The shorter version seemed better to me at first sight (because it is simpler), but actually it is incorrect. Both if statements intend to compare the same two values, but incrementing index1 changes data1[index1] for the second statement. You could fix this by assigning the values to variables:

    while index1 < len(data1) and index2 < len(data2):
        value1, value2 = data1[index1], data2[index2]
        if value1 <= value2:
            index1 += 1
        if value1 >= value2:
            index2 += 1
    
  • Updating ks_stat one value at a time feels a bit awkward to me. You could collect all the absolute differences in a list and take max() of it in the end. Or, extract the loop into a generator to avoid the list.

\$\endgroup\$
  • \$\begingroup\$ Ah, that would have been a very annoying bug to find! I think I'll stick to the first one, because it seems clearer to me now that you've pointed this out. Thanks! \$\endgroup\$ – Sp3000 Feb 5 '15 at 0:03
1
\$\begingroup\$

Disclaimer: I am not an expert in statistics.

That said, it doesn't look right to throw away the tail of the longer sample (the loop iterates min(len(data1), len(data2)) times) and at the same time use its length (as in index1/len(data1)). For a true K-S test I would expect some sort of interpolation to equalize sample lengths.

Once it is done, you may just reduce the list of absolute differences, along the lines of

reduce(lambda x,y: max(x, y), [abs(a - b) for (a,b) in zip(sample1, sample2)], 0)
\$\endgroup\$
  • \$\begingroup\$ Isn't that the same as max(abs(a - b) for (a,b) in zip(sample1, sample2))? \$\endgroup\$ – Janne Karila Feb 4 '15 at 7:35
  • \$\begingroup\$ Sorry about leaving out the last line of the while loop - that was a mistake on my part. I'm not sure I quite follow though - the number of times the loop iterates is dependent on the elements themselves (in the worst case, almost as many iterations as there are elements, e.g. [0, 0, 0, 0, 0, 9] and [5, 5, 5, 5, 5]). Also, as far as I can tell, the KS test does need both data lists to be equal lengths, which is quite beneficial actually. \$\endgroup\$ – Sp3000 Feb 4 '15 at 7:58
  • \$\begingroup\$ K-S may indeed work with unequal samples, yet it requires interpolation - in other words, where the delta is sampled? \$\endgroup\$ – vnp Feb 4 '15 at 8:16
  • \$\begingroup\$ The tail can be ignored because the maximum absolute difference can't be there. index1/len(data1) already equals 1 and index2/len(data2) would approach 1 if the iteration went on. \$\endgroup\$ – Janne Karila Feb 4 '15 at 8:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.