I have a weight function f that outputs a numeric weighting for a sample s. I also have an ordered set of samples S where the weight of each sample s in set S varies greatly.
How can I create n splitting points so that each split is weighted approximately the same? What kind of methodology, algorithms or models could I use to achieve this?
A classic optimization problem! You can use Linear Programming/Optimization to find a good split. Every of the n samples s $\in S$ has weight f(s) and we want to divide them into m folds. You can use a trick to linearize the L1 objective or you can use Quadratic Programming for a L2 objective function. The Quadratic Programming model is easier to define in this case. Let's define $x_{ij}$ as a binary decision to put sample i in fold j and $\mu$ is the ideal, mean weight per fold. Then this is our objective function:
min $\sum_{j=1}^m(\sum_{i=1}^nx_{ij}f(i)-\mu)^2$
Under the following constraints:
$\sum_{j=1}^mx_{ij}=1$ for all $i\in \{1..n\}$ to ensure exactly one assignment per sample
$x_{ij} \in \{0, 1\}$ to turn it into binary decision varibales
Depending on the size of your dataset and the solver you use this can be a heavy optimization, but there are a lot of greedy heuristics that will get you close fairly fast.
