Я ищу эквивалент алгоритма Велфорда для полудисперсии онлайн-вычислений (недостаточная частичная дисперсия ). Кто-нибудь знает хорошую ссылку? Такой алгоритм вообще существует?
Изменить: случай, когда полудисперсия берется относительно фиксированной цели, тривиален. проблема заключается в вычислении полудисперсии по отношению к среднему
Я считаю, что ответа не существует, и я попытаюсь обрисовать доказательство того, почему это так.
Рассмотрим «полезный» онлайн-алгоритм, определяемый двумя критериями:
Это строже, чем буквальное определение последовательного/инкрементного/онлайн-алгоритма, который на самом деле просто требует, чтобы данные можно было передавать по частям за раз. Однако учтите, что если 1) или 2) неверны, то после обработки достаточно большого количества элементов требуемая память или время, необходимое для запуска алгоритма, в конечном итоге станут невозможными. Обычно одной из причин использования онлайн-алгоритмов является то, что их можно использовать постоянно, не опасаясь медленного ухудшения производительности. Также обратите внимание, что существуют онлайн-алгоритмы для вычисления среднего значения и дисперсии, которые удовлетворяют как 1, так и 2, и я думаю, что это то, чего мы стремимся достичь.
Теперь к поставленной проблеме. Во время обработки среднее значение будет меняться с каждым битом новых данных. Это, в свою очередь, означает, что набор наблюдений, значение которых ниже среднего, изменится. Когда это происходит, нам нужно скорректировать нашу текущую полудисперсию в соответствии с набором «дельта», определяемым как элементы, которые не входят в объединение между набором элементов ниже старого среднего и набором элементов ниже нового среднего. Мы должны будем вычислить эту дельту в процессе подгонки старой-полувариантности к новой-полувариантности при наличии новых данных.
Теперь давайте рассмотрим сложность вычисления этой дельты множества. Нам нужно будет найти все элементы, которые попадают между старым средним и новым средним. Мы всегда будем отслеживать старое среднее значение, в то время как новое среднее может быть вычислено постепенно за фиксированное время, поэтому они не создают проблем. Однако для вычисления самой дельты нет другого способа сделать это, кроме как отследить все предыдущие элементы в нашем наборе. Это немедленно нарушает состояние памяти онлайн-алгоритма. Во-вторых, даже если мы сохраним предыдущие элементы в нашем наборе отсортированными, наилучшая скорость, которую мы можем достичь, чтобы найти те, которые находятся между старым средним и новым средним значением, составляет O (log (количество элементов)), что хуже, чем фиксированное. Таким образом, в конечном итоге, с достаточным количеством элементов онлайн-алгоритму потребуется не только больше памяти, чем у нас есть, но и больше времени.
http://www3.sympatico.ca/jean-v.cote/computation_of_semi-variance.pdf P.S.: Это не инкрементное вычисление. У меня есть другая идея. Я буду держать вас в курсе.
Вот Адаптация метода Велфорда для вычисления полувариаций
