Организация распределенного хранилища, оптимизированного под статический анализ, страница 2

Map-Reduce (Hadoop)Вычислительная парадигма Map-Reduce, реализованная в системе Hadoop,не имеет ничего общего с СУБД и NoSQL в вопросе организации.Сам по себе Hadoop – это набор утилит, библиотек и фреймворк для разработки и выполнения распределенных программ, работающих на кластерахиз сотен и тысяч узлов. Состоит из четырех модулей: Hadoop Common (связующее ПО), HDFS (распределенная файловая система), YARN (система дляпланирования заданий и управления кластером) и Hadoop Map-Reduce(платформа для программирования и выполнения распределенных MapReduce вычислений).С помощью Hadoop организовывается распределенное хранилище. За хранение и доступ к данным отвечает HDFS, за анализ над данными Map-Reduce. Схема выполнения вычислений над данными для Hadoop приведенана рисунке 4.Рисунок 4.

Схема парадигмы Map-ReduceВычисления над данными разбиваются на два этапа.• Первый этап (Map): Базовый обработчик, реализованный разработчиком, преобразует исходные пары «ключ-значение» впромежуточный набор пар «ключ-значение» на каждом узле.• Второй этап (Reduce): Другой обработчик сводит промежуточный набор пар в окончательный.Рассмотрим пример: нам необходимо среди всех числовых данных на узлах посчитать среднее арифметическое.

В этом случае базовый обработчик подсчитывает среднее на каждом узле, а второй обработчик получаетрезультат среднего за счет вычисления на результатах работы первого обработчика.Отметим также, что Hadoop обладает свойством масштабируемости и способностью быстро и параллельно выполнять вычисления над всем массивом данных.1.2.Статистический анализСреди большого разнообразия видов и способов добывания знаний изданных (data mining) таких, как методы классификации, моделирования,прогнозирования, выделяются статистические методы анализа данных.Отличительной чертой статистического анализа является то, что он всегдапроизводится над некоторой выборкой данных. Предполагается, что данные – это наблюдения некоторых случайных величин или некоторые переменные со статистической ошибкой.

Это обстоятельство и позволяет рассматривать статистический анализ отдельно от всего data mining в рамкахобсуждения организации хранилища.1.2.1. Основные методы статистического анализаСуществует множество методов статистического анализа, как одномерного, так и многомерного. Рассмотрим некоторые из них.• Дескриптивный (описательный) анализДанный вид анализа производится путем составления частотных таблиц, вычисление статистических характеристик (математическое ожидание, дисперсия и другие) или графическое представление. Описательный анализ производится на одном измерении и «описывает» свойствафункции распределения случайной величины, над выборкой которойпроизводится анализ.• Корреляционный анализКорреляционный анализ используется при анализе тесноты связимежду двумя и более переменными.

Тесно связан с регрессионныманализом. Существуют следующие ограничения на проведение корреляционного анализа:• Применение возможно при наличии достаточного количестванаблюдений для изучения (должно в 5-6 раз превышать число факторов)• Необходимо, чтобы совокупность значений всех факторных и результативного признаков подчинялась многомерному нормальному распределению [9]• Исходная совокупность значений должна быть качественно однородной [10]Следует помнить, что сам по себе факт корреляционной зависимости неозначает, что одна из переменных предшествует или является причиной изменений, или то, что переменные вообще причинно связанымежду собой, а не наблюдается действие третьего фактора [10].• Регрессионный анализРегрессионный анализ – статистический метод исследования влиянияодной или нескольких независимых переменных на зависимую.

Цельюрегрессионного анализа является установление не самого факта зависимости, а его характера, так как для применения анализа уже необходимфакт наличия зависимости.• Факторный анализФакторный анализ – это своего рода обобщение регрессионного анализа, когда изучается взаимосвязь между значениями переменных.Предполагается, что известные переменные зависят от меньшего количества неизвестных переменных и случайно ошибки. Для выполненияфакторного анализа так же необходима однородность выборки.• Дисперсионный анализДисперсионный анализ используется для поиска зависимостей в экспериментальных данных путем исследования значимости различий всредних значениях.

Позволяет сравнивать средние значения трех и более групп.• Компонентный анализКомпонентный анализ - многомерный статистический метод сниженияразмерности, применяемый для изучения взаимосвязей между значениями количественных переменных. Задача компонентного анализа состоит в преобразовании исходной системы взаимосвязанных переменных в новую систему некоррелированных обобщенных показателей илиортогональных показателей [11].• Дискриминантный анализДискриминантный анализ – это целый набор методов статистическогоанализа для решения задач распознавания образов.

Используется дляпринятия решения о том, какие переменные разделяют возникающиенаборы данных. В отличие от кластерного анализа, здесь группы известны априори.• Временной рядВообще временной ряд – это собранный в разные моменты временистатистический материал о значении каких-либо параметров (в простейшем случае одного) исследуемого процесса. Каждая единица статистического материала называется измерением или отсчётом, также допустимо называть его уровнем на указанный с ним момент времени. Вовременном ряде для каждого отсчёта должно быть указано время измерения или номер измерения по порядку.

Временной ряд существенно отличается от простой выборки данных, так как при анализеучитывается взаимосвязь измерений со временем, а не только статистическое разнообразие и статистические характеристики выборки [12].Все виды статистического анализа объединяет одно важное свойство, которое будет описано в следующем параграфе.1.2.2. Репрезентативная выборка и статистический анализКогда речь идет о предмете математической статистики и, особенно, о статистическом анализе, важно правильно понимать основной предмет изучения – данные. В нашем случае важно точно определить, что подразумевается под словами «генеральная совокупность», «выборка» и «подвыборка».Генеральной совокупностью называется множество всех возможных значений или реализаций исследуемой случайной величины.

Выборка - эточасть генеральной совокупности. Репрезентативная выборка – это выборка из генеральной совокупности такая, что её все статистические свойства и признаки совпадают со статистическими свойствами и признакамигенеральной совокупности.Если вести речь о случайной величине, то репрезентативная выборка – этонабор данных, подчиняющийся тому же закону распределения, что и случайная величина.Подвыборкой называется часть выборки случайной величины.

Подвыбокабудет репрезентативной, когда её распределение совпадает с распределением выборки.Важнейшим свойством статистического анализа является то, что он проводится априори над некоторой выборкой, описывающей наблюдение случайной величины. Значит, можно взять репрезентативную подвыборкуэтой выборки и, проведя анализ над ней, получить аналогичные анализунад общей выборкой результаты. Это свойство и будет использоваться приорганизации распределенного хранилища.1.3.Статистический анализ в распределенном хранилище и постановказадачиВопрос статистического анализа в распределенном хранилище решаетсядвумя путями: либо производится анализ всех данных в хранилище (еслиметод анализа можно представить виде Map-Reduce парадигмы), либо изхранилища выделяется репрезентативная выборка, над которой и производятся все расчеты.

Если говорить о решении для распределенного хранилища Hadoop, то проводить статистический анализ можно с помощьюинструмента, основанного на языке анализа данных R, - RHIPE [16].Однако в данной работе предлагается применить иной подход к организации хранилища: формировать репрезентативную выборку в момент распределения данных, а не перед началом анализа.

Поэтому задача ставитсяследующим образом: организовать распределение данных в хранилищетаким образом, чтобы на выбранном узле сформировать репрезентатив-ную выборку для выбранного измерения. В процессе формирования выборки необходимо сохранить равномерность распределения данных поузлам хранилища.Таким образом, в организации распределенного хранилища, оптимизированного под статистический анализ, будет уделяться главное внимание вопросу распределения данных, нежели хранения, связи между узлами, отказоустойчивости и других моментов, которые в данном случае не играютбольшой роли в вопросе статистического анализа. Поэтому в ходе работынад этой темой была построена система распределения данных в хранилище и модуль для её тестирования и проверки итоговых результатов.Однако, прежде чем описывать реализованную модель, обратимся к математической модели поставленной задачи и формализуем требования к результатам работы.2.

Математическая модель2.1.Формализация задачиПуть у нас есть распределенное хранилище, состоящее из n (n > 1) уз-лов. Есть объем N записей (данных) известной природы и вида. Каждая за-пись имеет хотя бы одно измерение дискретного или непрерывного вида,известного многообразия или интервала min, max соответственно. Безограничений общности репрезентативная выборка будет создаваться напервом узле.Рассмотрим пример. Пусть у нас имеются показания термометра с различных метеостанций за различные даты. Каждая запись задается тремя параметрами: номер станции, дата, среднесуточная температура.