Лучший способ найти наименьшее стандартное отклонение - PullRequest
Новая
       33

Лучший способ найти наименьшее стандартное отклонение

0 голосов
/ 26 октября 2018

У меня есть электронная таблица, в которую я положил числа, представляющие количество стихов в каждом абзаце книги.

Я вручную распределяю последовательные абзацы по количеству стихов, поэтому в электронной таблице у меня будет что-то вроде этого: 

Verses  Day
5       1
6       1
3       1
10      2
8       3
4       3
2       3
6       4
3       4
10      5
3       5
2       6
5       6
10      7
        = 2,7080128015

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

Вопрос в том, как лучше всего найти наименьшее стандартное отклонение?

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

РЕДАКТИРОВАТЬ: стандартное отклонение основано на общем количестве стихов каждого дня, которые определяются последовательно. В день 1 всего 14 стихов, день 2, 10 и т. Д. 

1   14
2   10
3   14
4   9
5   13
6   7
7   10
    = 2,7080128015

1 Ответ

0 голосов
/ 26 октября 2018

Поскольку общее количество стихов и количество дней постоянно, вы хотите минимизировать 

sum (avg verse count - verse count of day i)^2
 i

avg verse count - это константа и просто общее количество стихов, деленное на количество дней.

Эта проблема может быть решена с помощью динамической программы в течение нескольких дней.Давайте построим функцию частичного решения f(days, paragraph), которая дает нам минимальную сумму квадратов для распределения абзацев от 0 до paragraph в течение days дней.Нас интересует последнее значение этой функции.

Мы можем строить функцию постепенно.Вычислить f(1, p) для любого p просто, так как нам просто нужно вычислить разницу между средним и квадратом.Затем для всех остальных дней мы можем вычислить 

f(d, p) = min f(d - 1, i) + (avg verse count -  sum    verse count of paragraph j)^2
          i<p                                 j:i+1..p

Это означает, что мы проверяем решения на один день меньше и заполняем текущий день абзацами между заключительным абзацем предыдущего дня и p.Пока мы вычисляем эту функцию, мы сохраняем указатель на выбранный минимальный элемент (как обычно для динамической программы).Когда мы закончим вычисление всей функции, мы просто следуем указателям назад к началу, что даст нам разбиение.

Алгоритм имеет время выполнения O(d * p^2), где d - числодней и p - количество абзацев.

Пример кода

Вот пример кода C #, который реализует описанный выше алгоритм: 

struct Entry
{
    public double minCost;
    public int predecessor;
}

public static void Main()
{
    //input data
    int[] versesPerParagraph = { 5, 6, 3, 10, 8, 4, 2, 6, 3, 10, 3, 2, 5, 10 };
    int days = 7;

    //calculate constants
    double avgVerses = (double)versesPerParagraph.Sum() / days;

    //set up DP table (f(d,p))
    int paragraphs = versesPerParagraph.Length;
    Entry[,] dp = new Entry[days, paragraphs];

    //initialize table
    int verseCount = 0;
    for(int p = 0; p < paragraphs; ++p)
    {
        verseCount += versesPerParagraph[p];
        double diff = avgVerses - verseCount;
        dp[0, p].minCost = diff * diff;
        dp[0, p].predecessor = -1;
    }

    //run dynamic program
    for(int d = 1; d < days; ++d)
    {
        for(int p = d; p < paragraphs; ++p)
        {
            verseCount = 0;
            dp[d, p].minCost = double.MaxValue;
            for(int i = p; i >= d; --i)
            {
                verseCount += versesPerParagraph[i];
                double diff = avgVerses - verseCount;
                double cost = dp[d - 1, i - 1].minCost + diff * diff;
                if(cost < dp[d, p].minCost)
                {
                    dp[d, p].minCost = cost;
                    dp[d, p].predecessor = i - 1;
                }
            }
        }
    }

    //reconstruct the partitioning
    {
        int p = paragraphs - 1;
        for (int d = days - 1; d >= 0; --d)
        {
            int predecessor = dp[d, p].predecessor;
            //calculate number of verses, just to show them
            verseCount = 0;
            for (int i = predecessor + 1; i <= p; ++i)
                verseCount += versesPerParagraph[i];
            Console.WriteLine($"Day {d} ranges from paragraph {predecessor + 1} to {p} and has {verseCount} verses.");
            p = predecessor;
        }
    }
}

Вывод: 

Day 6 ranges from paragraph 13 to 13 and has 10 verses.
Day 5 ranges from paragraph 10 to 12 and has 10 verses.
Day 4 ranges from paragraph 9 to 9 and has 10 verses.
Day 3 ranges from paragraph 6 to 8 and has 11 verses.
Day 2 ranges from paragraph 4 to 5 and has 12 verses.
Day 1 ranges from paragraph 2 to 3 and has 13 verses.
Day 0 ranges from paragraph 0 to 1 and has 11 verses.

Это разбиение дает стандартное отклонение 1.15.

...