Введение.
Распределенный анализ категориальных последовательностей для непрерывного производства
На рисунке 1 изображены графики зависимоссти времени выполнения алгоритма от значения параметра минимальной поддержки, характеризующего процент различия между последовательностью данных и входящей в нее подпоследовательностью. Из графиков видно, что наилучшей масштабируемостью обладает алгоритм PrefixSpan. Намного более пригодными для распараллеливания являются алгоритмы поиска… Читать ещё >
Введение. Распределенный анализ категориальных последовательностей для непрерывного производства (реферат, курсовая, диплом, контрольная)
В области анализа данных последовательностью называют упорядоченный набор элементов, каждый из которых может быть числовым, категориальным (состоящим из нескольких качественных значений), или смешанным [1, с. 1]. Расположение таких элементов в последовательности строго определено в зависимости от логического порядка их следования (категориальные последовательности) или от времени их появления (временные ряды). На сегодняшний день анализ последовательностей данных широко применяется во многих областях — медицине, биологии, производстве, однако существующие на данным момент подходы используют алгоритмы, работа которых существенно зависит от размерности входных данных. В данной статье представляется подход к анализу категориальных последовательностей с использованием технологии распределенной обработки, позволяющей эффективно работать с данными, размеры которых превышают доступную оперативную память.
Выбор алгоритма для анализа потоковых данных
При работе с потоковыми данными зачастую возникают трудности, которые можно разделить на следующие категории:
- 1. Проблема передачи данных на вход программы из-за высоких скоростей генерации новых данных;
- 2. Проблема выполнения операций вычисления сложных функций с использованием большого количества входных данных, которые быстро обновляются, что влечет за собой серьезные нагрузки на вычислительную инфраструктуру;
- 3. Проблема хранения данных (временно или в целях последующего использования их в долгосрочной перспективе).
Исследование литературы по вопросам выявления паттернов в категориальных последовательностях показало, что наиболее популярными методами являются подходы, разработанные группой исследователей IBM Research [2, 3], которые представили алгоритмы AprioriSome, AprioriAll, DynamicSome и SPADE. Однако применение указанных подходов не позволяет решить проблемы, специфичные для потоковых данных. В первую очередь это связано с использованием в данных алгоритмах чрезмерно сложных структур данных, а также с большим количеством запросов к базе данных. Таким образом, данные алгоритмы трудны для распараллеливания, что делает трудоемким создание распределенной системы на их основе.
Намного более пригодными для распараллеливания являются алгоритмы поиска подпоследовательностей FreeSpan, PrefixSpan и GSP. Сравнение масштабируемости этих алгоритмах на редуцированном наборе данных, включающем в себя 40 000 последовательностей, представлены на рисунках 1, 2.
На рисунке 1 изображены графики зависимоссти времени выполнения алгоритма от значения параметра минимальной поддержки, характеризующего процент различия между последовательностью данных и входящей в нее подпоследовательностью. Из графиков видно, что наилучшей масштабируемостью обладает алгоритм PrefixSpan [4, с. 3].
Рисунок 1. Проверка масштабируемости времени выполнения алгоритмов GSP, FreeSpan, PrefixSpan.
непрерывный распределенный паттерн На рисунке 2 представлено сравнение использования памяти алгоритмами GSP и PrefixSpan при различных значениях параметра минимальной поддержки. Из графиков видно, что PrefixSpan более стабилен в использовании памяти.
Рисунок 2. Проверка масштабируемости использования памяти алгоритмами GSP и PrefixSpan.