Какой алгоритм использовать для сегментации чисел чисел в n подмножеств, чтобы минимизировать стандартное отклонение суммы чисел в каждом подмножестве

Ответ 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;
}

Ответ 2

Одна идея, которая приходит мне на ум, - использовать алгоритм поиска A *.

Подробнее об этом:

http://en.wikipedia.org/wiki/A*_search_algorithm

Хорошая книга, чтобы прочитать о ней:

Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig

Некоторые вещи, которые вы могли бы использовать для A *:

• Начальное состояние: разделите последовательность на n, равную (насколько это возможно) подпоследовательности
• Следующее состояние: для каждого подмножества добавить левое или правое число (последнее число подмножества i-1 (если я!= 0) или первое число подмножества я + 1 (если я!= n)) к нему (для создания всех нисходящих узлов текущего состояния node)
• Эвристика: оптимальным значением будет среднее значение всех значений. Его допустимо, поэтому его можно использовать с A *.

Я не уверен, что действительно поможет вам в решении вашей проблемы, так как я еще не решил эту проблему, но думаю, что это может быть очень хорошо. Это также может быть не самое сложное решение для этой конкретной проблемы, но это, безусловно, лучше, чем любой подход "попробуйте все комбинации". Он также звучит и дополняется (из-за допустимой эвристики).

Если у вас больше вопросов по этому поводу, и я постараюсь помочь вам.

Ответ 3

Я думаю, вы имеете в виду разделить на смежные куски, или, другими словами, найти n-1 места, на которых вырезать последовательность на куски. (Если вы действительно хотите разрешить подпоследовательности, которые чередуются, чтобы создать основную последовательность, вы могли бы просто отсортировать последовательность, решить проблему куска, а затем отслеживать, откуда пришли отдельные номера, чтобы обеспечить чередующиеся подпоследовательности).

Я думаю, вы можете решить это во времени пропорционально n раз длины последовательности, используя динамическое программирование. Работайте слева направо, чтобы заполнить массивы bestCost [i] [j] и lastCut [i] [j], где я пробегает последовательность, а j пробегает от 0 до n-1. bestCost [i] [j] - это стоимость наилучшего способа отрезать последовательность от 0 до я до j кусков. lastCut [i] [j] - это позиция самого последнего разреза для разреза, который производит bestCost [i] [j]. bestCost [i + 1] [j] = min_k std отклонение (i + 1 до k) + bestCost [k - 1] [j - 1]. а затем lastCut [i + 1] [j] = k. В конце вы точно рассчитаете стоимость наилучшего ответа для n разрезов, а затем используйте lastCut [] [], чтобы проследить путь назад, чтобы найти другие сокращения.

Ответ 4

Я согласен с тем, что динамическое программирование может быть лучшим подходом - один из тех методов, который я бы исключал, - это нелинейная оптимизация. У вас есть нелинейная целевая функция, минимизируете ли вы квадратный корень или просто сумму квадратов различий. У вас также есть целочисленные переменные как часть вашего набора ограничений. Назначение членов наборам требует целочисленных переменных независимо от вашей формулировки. Нелинейная оптимизация с целыми переменными, как правило, очень трудно, если не невозможно, оптимально решить. Если вам нужны только приблизительные решения, генетический алгоритм может быть хорошим подходом, когда генетическая строка представляет собой представление назначения члена в набор.

Что касается всего этого менее чем за секунду... Удачи!