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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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