Какой алгоритм использовать, чтобы сегментировать последовательность чисел на n подмножества, минимизировать стандартное отклонение суммы чисел в каждом подмножестве
Я ищу алгоритм для сегментации последовательности положительных чисел в n подпоследовательности, такие, что стандартное отклонение суммы чисел в каждом подмножестве минимизировано.
Упорядочивание чисел в каждой подпоследовательности должно совпасть с упорядочиванием в исходной последовательности
Например:
Предположим, что у меня есть последовательность {1,1,1,1,1,1,10,1}, что я хотел сегментироваться на 2 подпоследовательности.
Я полагаю, что оптимальное решение было бы {1,1,1,1,1,1}, {10,1}.
Сумма 1-й подпоследовательности равняется 6, сумма 2-й подпоследовательности равняется 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) сложность.
Это, кажется, тип вещи, которая имела бы существующий ранее алгоритм для применения, однако мой поиск с помощью Google привел меня к сбою. Я знаю о проблеме Раздела, которая полна NP, но это имеет дело с незаказанными наборами, и не заказанное последовательности.
Любая справка ценилась бы.
4 ответа
Предположим, что длина исходной последовательности - 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, а минимальное значение превышает 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;
}
Вы думаете не на достаточно высоком уровне. Хорошо, построитель терпит неудачу. Атрибут остается неопределенным. Но что вы делаете с кодом, который вызывает метод доступа? В контракте класса указано, что вызов метода всегда возвращает IO:: File. Но теперь он возвращается undef. (Контракт был IO:: File , а не Может быть [IO:: File] , верно?)
Поэтому в следующей строке кода вызывающий абонент умрет («Не может вызвать метод 'readline' для неопределенного значения в the_caller.pl line 42».), потому что он ожидает, что ваш класс будет следовать контракту, который он определил. Неудача не была чем-то, что должен был сделать ваш класс, но теперь она сделала. Как вызывающий абонент может сделать что-либо, чтобы исправить эту проблему?
Если он может обработать undef , вызывающий абонент фактически не нуждается в filehandle для начала с... Поэтому почему он попросил у вас одного из них?
С учетом этого единственное разумное решение - умереть. Вы не можете выполнить контракт, на который согласились, и умереть - это единственный способ выйти из этой ситуации. Так что просто сделайте это; смерть - это факт жизни.
Теперь, если вы не готовы умереть при запуске построителя, вам нужно будет изменить при запуске кода, который может завершиться сбоем. Это можно сделать во время построения объекта, сделав его незатейливым или явно оживив атрибут в BUILD ( BUILD {$ self- > file _ name} ).
Лучший вариант - вообще не выставлять дескриптор файла внешнему миру, а вместо этого сделать что-то вроде:
# dies when it can't write to the log file
method write_log {
use autodie ':file'; # you want "say" to die when the disk runs out of space, right?
my $fh = $self->file_handle;
say {$fh} $_ for $self->log_messages;
}
Теперь вы знаете, когда программа умрет; в new или в write _ регистрация . Ты знаешь, потому что документы так говорят.
Второй способ делает ваш код намного чище; потребитель не должен знать о реализации вашего класса, он просто должен знать, что он может сказать ему, чтобы он написал некоторые сообщения журнала. Теперь вызывающий абонент не заинтересован в деталях внедрения; он просто говорит классу, что он действительно хотел, чтобы он сделал.
И, умирая в write _ регистрация может быть даже то, от чего вы можете оправиться (в блоке catch), в то время как «не мог открыть эту случайную непрозрачную вещь, о которой вы не должны знать в любом случае» гораздо труднее для вызывающего.
В основном, разработайте код правильно, и исключения являются единственным ответом.
(Я все равно не понимаю все «они - клюдж». Они работают точно так же путь на C++ и очень аналогично на Java и Haskell и любом другом языке. Действительно ли слово die так страшно или что?)
Да. Вы пишете свой код в tinypy (который ограничен Python), затем использовать tinypy, чтобы конвертировать его в C++, и, наконец, компилировать это с XCode в родной iPhone app. Фил Хасси опубликовал игру под названием Слоны! с использованием этого подхода. Вот более подробности,
http://www.philhassey.com/blog/2009/12/23/elephants-is-free-on-the-app-store/
-121--785590-Я думаю, вы имеете в виду разделить на смежные куски, или другими словами найти n-1 место для разрезания последовательности на части. (Если вы действительно хотите разрешить подпоследовательности, которые перемежаются для создания главной последовательности, вы, вероятно, могли бы просто сортировать последовательность, решить проблему порций, а затем отслеживать, откуда пришли отдельные числа, чтобы обеспечить перемежающиеся подпоследовательности).
Я думаю, что вы можете решить это за время, пропорциональное n-кратной длине последовательности, используя динамическое программирование. Работа слева направо для заполнения массивов bestCost [i] [j] и lastCut [i] [j], где i проходит вдоль последовательности, а j - от 0 до n-1. bestCost [i] [j] - это стоимость наилучшего способа разрезания последовательности от 0 до i на j порций. lastCut [i] [j] - позиция последнего погона для погона, который производит bestCost [i] [j]. bestCost [я + 1] [j] = min_k отклонение станд. (я + 1 к k) + bestCost [k - 1] [j - 1]. и затем lastCut [i + 1] [j] = k. В конце вы отрабатываете стоимость наилучшего ответа для n сокращений таким же образом, а затем используйте lastCut [] [], чтобы отследить свой путь назад, чтобы найти другие сокращения.
Одна из идей, которая приходит мне в голову - использовать алгоритм поиска A*.
Больше об этом:
http://en.wikipedia.org/wiki/A*_search_algorithm
Хорошая книга для чтения:
Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig
Некоторые вещи можно использовать для A*:
- Начального состояния: Разделите последовательность на n равных (насколько это возможно) подпоследовательностей
- Next State: Для каждого подмножества прибавить к нему левое или правое число (последнее число подмножества i-1 (если i != 0) или первое число подмножества i+1 (если i != n)) (для создания всех нисходящих узлов узла текущего состояния)
- Эвристика: Оптимальным значением будет среднее всех значений. Оно допустимо, поэтому может быть использовано с A*.
Я не уверен, что это действительно поможет вам с вашей проблемой, так как я не решил эту проблему снова, но я думаю, что это может быть неплохо. Это также может быть не самым сложным решением для этой конкретной проблемы, но это, безусловно, лучше, чем любой подход "попробовать все комбинации". Он также хорош и полон (из-за допустимой эвристики).
Если у вас есть еще вопросы по этому поводу, я постараюсь вам помочь.
Согласен, что динамическое программирование может быть лучшим подходом - одна из техник, которую я бы исключил, это нелинейная оптимизация. У вас есть нелинейная объективная функция, независимо от того, минимизируете ли вы квадратный корень или просто сумму квадратных разностей. У вас также есть целочисленные переменные как часть вашего набора ограничений - присвоение членов множествам требует некоторых целочисленных переменных независимо от вашей формулировки. Нелинейная оптимизация с помощью целочисленных переменных, как правило, очень сложна, если не невозможна. Если вам нужны только приблизительные решения, то хорошим подходом может быть генетический алгоритм, при котором генетическая строка представляет собой представление о назначении члена множества.
Поскольку все это делается менее чем за секунду..... Удачи!