Which algorithm? Or incorrect results?

[orbisvicis]

Which algorithm is this? The heuristics Jenks, the total minimum distance Jenks, or the optimized and total minimum distance Fischer-Jenks? Yours deviates from my pure-python Jenks implementation and I suspect off-by-one errors:

import statistics

def distance(l, m):
    if not l:
        raise ValueError
    return sum((i-m)**2 for i in l)

ls = [0, 1, -2]
b = 2
jpc = break_list(ls, jenkspy.jenks_breaks(ls, b))
jmc = jenks(ls, b)[1]
jpd = [distance(c, statistics.mean(c)) for c in jpc]
jmd = [distance(c, statistics.mean(c)) for c in jmc]
jps = sum(jpd)
jms = sum(jmd)

print("jenkspy:")
print(f"\tsum distance: {jps}")
print(f"\tdistances:    {jpd}")
print(f"\tclusters:     {[sorted(c) for c in jpc]}")
print()
print("pure-python:")
print(f"\tsum distance: {jms}")
print(f"\tdistances:    {jmd}")
print(f"\tclusters:     {[sorted(c) for c in jmc]}")

jenkspy:
        sum distance: 2
        distances:    [2, 0]
        clusters:     [[-2, 0], [1]]

pure-python:
        sum distance: 0.5
        distances:    [0, 0.5]
        clusters:     [[-2], [0, 1]]

Even intuitively the jenkspy result is incorrect. My implementation and unit tests are here, see jenks and test_jenks_breaks.

Resources:

[1] Is Jenks' Natural Breaks deterministic?
[2] Fisher's Natural Breaks Classification complexity proof
[3] Re: Jenk's Optimization for Natural Breaks Classification

[mthh]

Thanks a lot for the report, the links and the test cases.

I'm working on it and already fixed some errors in my implementation in 30abfe4 and 886c567 (as such my jenks_breaks function now returns the correct bounds for your example).

[mthh]

I updated the README, the docstrings and the package metadata to be more precise about the algorithm in use. The returned results should now be correct.

I am preparing a notebook with comparaison of various implementations, i will post the link here if you are interested.