Jenks
Produces the contiguous partition of sorted data that minimizes the total within-group sum of squared deviations, by the exact dynamic program of Fisher (1958), popularized in cartography as Jenks natural breaks.
With prefix sums the sum of squared deviations of any index range is available in constant time, so the recursion
D(i, g) = min over t of { D(t, g-1) + SS(t, i) }is evaluated in O(n^2 k) time using O(n k) space. The tables are built once for the largest requested number of groups and reused for every smaller number, because the recursion for g groups is a prefix of the recursion for more.
Two departures from the prototype this replaces are deliberate. There is no optimize function that selects a number of groups by minimizing the objective: the total within-group sum of squares is non-increasing in the number of groups, so such a function always returns the largest number offered, which is not a model selection procedure. Choosing the number of components is a model selection question addressed by the scoring layer. Second, cuts are restricted to positions that do not split a run of equal values, so the result is always a partition by value rather than by index.
Parameters
the observations in non-decreasing order, must not be empty
the largest number of groups the tables should support, must be positive
Properties
Functions
The unconstrained optimal partition into the supplied number of groups. Cuts may fall anywhere, including inside a run of equal values, so this is the classical Jenks result rather than a partition by value. Use generate for a partition that respects ties and the group requirements.
The optimal partition into the supplied number of groups subject to the certificate: cuts fall only at value-block boundaries, and every group meets the size and distinct-value requirements. Returns null when no such partition exists.
The sum of squared deviations from the mean of the observations in the index range from start until end, computed in constant time from prefix sums. An empty range has zero sum of squares.
The minimal total within-group sum of squares achievable with the supplied number of groups, ignoring the structural constraints of a certificate. Non-increasing in the number of groups, which is why it must not be used to select that number.