Параллельные вычисления в прикладной статистике Д.А. Насонов О.А. Комалева О.О. Рыбак НИИ НКТ СПбГУ ИТМО. - презентация

1 Параллельные вычисления в прикладной статистике Д.А. Насонов О.А. Комалева О.О. Рыбак НИИ НКТ СПбГУ ИТМО

2 Актуальность Факторы, определяющие рост объемов информационных массивов –Сверхбольшие измерительные комплексы –«Сертифицированные» модели и синтетические массивы данных Увеличение объемов хранимой информации 10% Me 150 Мб1 Гб Объемы информационных массивов, подвергаемых статистической обработке (бизнес-данные, Kdnuggets, 2006) Тенденции – Многомерность – Многомасштабность и неоднородность – Нелинейные статистические процедуры

3 Анализ подходов к оцениванию достоверности гидрометеорологической справочной информации Существуют справочники, содержащие данные гидрометеорологических наблюдений Справочники могут содержать как неполную, так и ошибочную информацию Необходимо определить достоверность информации, содержащейся в справочниках

4 Задачи вероятностного подхода Вероятностный биплот «Высота волн – распределение Вейбулла» Определение теоретического закона, описывающего распределение (проверка гипотезы соответствия) –метод спрямленных диаграмм Оценка параметров распределения и построение доверительных интервалов

5 Распределение групп волн 1.Одномерный случай все просто: высоты волн имеют распределение Вейбулла 2.Зависимость между волнами в группе многомерная функция распределения – ?

6 Вывод распределения 1.Представляем многомерное распределение в виде: 2.Находим распределение : 3.Приближаем совместное распределение Квантильный и вероятностный биплоты распределения h 0 Изолинии плотности распределения Регрессия распределения

7 Робастный регрессионный анализ Постановка задачи модель дана выборка требуется найти параметры Робастность – слабая чувствительность метода к отклонениям от стандартных условий регрессионный метод – задача оптимизации функции невязок –метод наименьших квадратов –метод наименьших усеченных квадратов задача глобальной оптимизации функции очень трудоемка метод рекурсивного случайного поиска Пример целевой функции Результаты работы неустойчивого регрессионного метода

8 Рекурсивный случайный поиск Вычисление f(x) – наиболее сложная операция (зависит от размера выборки). Процедура exploitation выполняет локальный поиск в окрестности точки x. Количество вызовов процедуры exploitation – случайная величина. Процедура exploitation вычисляет значение целевой функции Q раз, где Q – случайная величина. Суммарное время работы: R – случайная величина.

9 Параллельный алгоритм 1.Исходный алгоритм ускоряется до. Q >> K, ускорение близко к 1. 2.Можно параллельно вычислять значение целевой функции. плата за детализацию; целевых функций может быть несколько; вычисление функций сложно распараллелить. 3. Вынести вызовы процедуры exploitation.

10 Из графиков видно, что (дисбаланс нагрузки + время на создание потоков). Функцию распределения ускорения S можно выразить как: Модель производительности параллельного алгоритма R-Weibull Плотность вероятности распределения ускорения R-LogNormal Квантильные биплоты вычисление функции модифицированный алгоритм

11 Анализ и моделирование процессов спроса- потребления в сетях розничной торговли Все люди делают покупки, информация о них является ценным источником для получения важных статистических результатов. Эта многомерной случайная величина обладает определенными ритмиками. В нашем случаи – это сутки, недели, а так же сезоны. Используя низко- и высоко- частотный фильтр Баттерворда, эти ритмики были выделены следующим образом: 1. Имея 16 часовой рабочий день, для выделения суточной ритмики применялся высокочастотный фильтр с периодом 16 + d часов. 2. Недельную ритмику получили применением сначала высокочастотного фильтра с периодом 16 + d + 1, а затем низкочастотного с периодом w часов. 3. Выделяем оставшуюся сезонную ритмику низкочастотным фильтром с периодом w + 1 часов.

12 Результаты Ритмики покупки сока. d = 5, период суток = 21 часам; w = 34, период недели лежит между 22 и 146 часами; c 147 часов сезонная ритмика Исходные данные числа покупок сока

13 Расчеты дисперсий После получения ритмик оценим точность, а так же вклад каждой из них в частотный разброс. Сложим все три полученных временных ряда и сравнить с первоначальным. Расчётные формулы для оценки вклада: Результаты: Вклад ритмик и общая погрешность: дневнаянедельнаясезоннаяδ сумм.ряд 86.5 %,5.3%,6.8%.0.86 %.

14 Следующий шаг – это статистический анализ некоторых ритмик по отдельности. Речь идет о расчете дисперсии, ее квадрата и математического ожидания по каждому часу. Результаты суточной ритмики для сока: Суточная ритмика покупки сока. На 18:00 – резкий скачок вниз свидетельствует о стабильной покупательской корзине, т.е. люди, именно в это время, идут с работы за покупками. Расчеты по суточной ритмики

15 С 4-го квартала года в гипермаркете была введена скидка 25% на сыр по пятницам. Следует обратить внимание на пятницу – резкий скачок вверх – нестабильности покупательной корзины, казалось бы все должно быть наоборот – парадокс? Расчеты недельной ритмики

16 Алгоритм обработки данных спроса- потребления Общий алгоритм по блокам: Проблем с реализацией распределенных вычислений во всех блоках алгоритма не возникает. За исключением блока фильтрации.

17 Проблемы параллельной фильтрации Реализовать параллельный алгоритм фильтрации, без потери точности не возможно, в связи с рекуррентной зависимостью основы алгоритма: … for ( i:= 0; I < M; i++) { for ( j:= 2; I < N; j++) { } ; … Однако, учитывая особенности фильтра Баттерворда, мы можем оптимизировать процесс распараллеливания в зависимости от целей.

18 Параллельный алгоритм фильтрации Фильтру Баттерворда для достижения высокой точности необходимо расширение начальных данных на определенную длину, как правило – 3 периода фильтрации. Само расширение происходит благодаря отражению исходных данных. Предложенный метод разбивает данные на P частей, т.е. количество процессов с продлением каждой части предыдущими и последующими исходными данными. Здесь P = 7, синими линиями отмечены разбитые части данных. Красными отмечены продления для каждой из частей.

19 Результаты фильтраций и вычислений суммарного временного ряда для сока

20 Статистика – это комплекс взаимосвязанных методов –любая взаимосвязь приводит к проблемам при распараллеливании Различные подходы к распараллеливанию –анализ групп волн (эквивалентный алгоритм) –анализ спроса-потребления рыночной торговли (асимптотическое преобразование) Необходимость оценки производительности стохастических алгоритмов (то есть нужны статистические инструменты) Время работы параллельного алгоритма – случайная величина –Потоки –Ускорение (сравнение с последовательным алгоритмом…) –Сложность зафиксировать результат эксперимента Выводы