使用什么算法将数字序列分段为n个子集,以最小化每个子集中数字之和的标准偏差

Question

我正在寻找一种算法将一系列正数分段为n个子序列,这样每个子集中数字之和的标准偏差就会最小化.

每个子序列中的数字的排序需要与原始序列中的排序相同

例如:

假设我有一个序列{1,1,1,1,1,1,10,1},我想分成2个子序列.
我相信最优解是{1,1,1,1,1,1},{10,1}.

第一个子序列的总和是6,第二个子序列的总和是11
这两个数字的标准差是~3.5,我相信这是最低的.

假设我有一个序列{4,1,1,1,1,6},我想分成3个子序列.
我相信最优解是{4},{1,1,1,1},{6}子
序列的总和是4,4和6.
3个数的标准差是~1.15,我是相信是最低的.

我能够想出的最好的算法是找到序列中每个数字的累积和,并在[totalSum/numSubsequences]的每个间隔处对序列进行分段.

例如,给定序列{4,1,1,1,1,6},每个序列的数量的累积和是{4,5,6,7,8,14}.序列中所有数字的总和为14,因此,假设我想要3个子序列,我应该在总数达到14/3 = 4.66和2*14/3 = 9.333333时对序列进行分段.

但是,累计总数等于4.66的序列中没有实际位置 - 第一个累计总数为4,下一个累计总数为5.那么我应该向上舍入还是应该向下舍入？在这种情况下,向下舍入为4会给出最佳解决方案,但情况并非总是如此.我能想到的最好的方法是尝试向上和向下舍入的每个组合,但这会导致O(2 ^ numSubsequences)复杂度.

这似乎是一种可以应用预先存在的算法的东西,但是我的谷歌搜索让我失望了.我知道分区问题,它是NP完全的,但它处理的是无序集,而不是有序序列.

任何帮助,将不胜感激.

Answer 1

假设原始序列的长度是,子序列L的数量是N.

您可以简化为标准偏差的表达得到sqrt(E[X^2] - E[X]^2),其中E表示期望/平均X表示您的随机变量-在你的情况下,子序列的总和.(类似的公式适用于"样本标准偏差".)请注意,E[X]这不取决于您如何拆分序列,因为它总是总和除以N.因此,我们只想最小化E[X^2]或相当于X^2它们的总和(它们相差N平均值的因子).

在这一点上,我们可以看到这个问题可以通过动态编程来解决.让我们f(i,j),为i从0到M和j从1到N,从第一分割子序列的总和的平方之和最小i的序列的元素融入j序列.然后我们看到f(i,j)可以用所有的f(i',j')和i' <= i和来计算j < j'.更具体地说,如果您的序列a[k]索引0为M-1:

f(i,1) = sum( a[k] for 0 <= k < i )^2
f(i,j) = minimum of  f(l,j-1)+sum( a[k] for l < k < i )^2  for l from 0 to i

最小化后f(N,L),您可以使用标准动态编程技术来恢复分割.特别是,您可以存储l最小化f(i,j).

该解决方案的运行时间O(L^2 N),因为用户使用电脑时O(L N)的不同的价值观f和minimum结束O(L)的不同值l.

这是Perl中的简单实现:

#!/usr/bin/perl

use strict;
use warnings;

local $\ = $/;
print join ", ", map {"@$_"} best( 2, qw(1 1 1 1 1 1 10 1) );
# prints "1 1 1 1 1 1, 10 1"

print join ", ", map {"@$_"} best( 3, qw(4 1 1 1 1 6) );
# prints "4, 1 1 1 1, 6"

sub best {
    my( $N, @a ) = @_;

    my( @f, @g, $i, $j, $k, $sum );

    # DP base case
    $sum = 0;
    $f[0][1] = $g[0][1] = 0;
    for $i ( 1 .. @a ) {
        $sum += $a[$i-1];
        $f[$i][1] = $sum * $sum;
        $g[$i][1] = 0;
    }

    # DP recurrence
    for $j ( 2 .. $N ) {
        $f[0][$j] = $g[0][$j] = 0;
        for $i ( 1 .. @a ) {
            $sum = 0;
            $f[$i][$j] = $f[$i][$j-1];
            $g[$i][$j] = $i;
            for $k ( reverse 0 .. $i-1 ) {
                $sum += $a[$k];
                if( $f[$i][$j] > $f[$k][$j-1] + $sum * $sum ) {
                    $f[$i][$j] = $f[$k][$j-1] + $sum * $sum;
                    $g[$i][$j] = $k;
                }
            }
        }
    }

    # Extract best expansion
    my( @result );
    $i = @a; $j = $N;

    while( $j ) {
        $k = $g[$i][$j];
        unshift @result, [@a[$k .. $i-1]];
        $i = $k;
        $j--;
    }

    return @result;
}