Реклама

Существенное различие задач оперативной и аналитической обработки данных стало проявляться еще на заре развития технологий баз данных. Термин хранилища данных (Data Warehouse) был предложен Биллом Инмоном еще в 70-х годах, однако всплеск интереса к этим технологиям произошел лишь 20 лет спустя, когда, во-первых, возникла реальная потребность в подобных системах и, во-вторых, стали доступны необходимые вычислительные мощности.

Цикл обработки данных в информационном хранилище включает в себя сбор, очистку, загрузку, анализ и, наконец, представление результатов анализа. Здесь нет смысла подробно останавливаться на этих этапах, но необходимо четко обозначить главный тезис — если пытаться применить технологии информационных хранилищ для анализа Больших Данных, то следует обратить внимание не только на алгоритмы анализа, но и на все этапы работы с данными.

Сбор

В русле информационных хранилищ предполагается, что информация извлекается из оперативных баз данных, преобразуется к необходимому виду, проверяется и только затем загружается в систему. Перечисленные операции выполняются с некоторой периодичностью, и здесь сразу же возникает вопрос: всегда ли возможна такая «периодичность» при работе с Большими Данными, которые потоком поступают на вход и должны быть доступны для анализа как можно раньше? Может оказаться, что промежуток времени между появлением информации и ее доступностью для анализа меньше, чем время, необходимое для выполнения операций по построению информационного хранилища. Примером такой задачи является мониторинг социальных сетей на предмет выявления негативных высказываний или фактов утечек конфиденциальной информации — все эти события должны быть выявлены и нейтрализованы как можно раньше. Однако здесь мы имеем дело с неформализованным представлением данных, для переработки которых требуются алгоритмы интеллектуального анализа текста, изначально не отличающиеся пока высоким быстродействием.

 

Мониторинг социальных сетей

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

 

В информационных хранилищах неявно подразумевается, что при предварительной обработке данных (например, при поиске несоответствий) может использоваться ранее накопленное содержимое хранилища, что трудновыполнимо при работе с Большими Данными. Проблема заключается прежде всего в том, что они всегда распределены, причем не так, как было бы удобно для анализа, а так, как было удобно их собирать — например, если речь идет о телекоммуникационных системах, то данные «складываются» на региональных серверах (рис. 1). С точки зрения анализа более удобно распределять данные не по территориальному, а по временному признаку (каждый сервер отвечает за конкретный промежуток времени) и т. п. Однако опять же информация станет доступной для анализа только после того, как будет перенесена на необходимые серверы.

Рис. 1. Сбор данных
Рис. 1. Сбор данных

 

Итак, в традиционных информационных хранилищах все данные всегда проходят через единый логический блок, отвечающий за их конвертацию, проверку, очистку, загрузку, и время выполнения этих операций редко бывает критичным для всей остальной системы. Однако при обработке Больших Данных такого единого блока быть не может. Cправедливости ради стоит отметить, что пока существует еще не так много задач с интенсивным входным потоком данных и еще возможно реализовать блок сбора, очистки, преобразования и загрузки в виде распределенной, но логически единой системы.

 

Мониторинг массовых рассылок

Одним из способов борьбы с нежелательными рассылками является определение факта массовых рассылок одного и того же или немного откорректированного письма. Эта задача выполняется обычно почтовым сервером, однако для ее точного решения требуется еще учитывать статистику с других серверов. Возникает задача анализа больших потоков входящих писем, сбора необходимой статистики, обмена статистикой с другими серверами и принятия решения о том, является ли каждое полученное письмо массовым. Допустимое время на принятие решения по каждому письму составляет примерно одну-две минуты — в противном случае полезные письма будут доходить до адресата с задержкой. Если исходить из того, что на почтовый сервер приходит примерно 500 писем в секунду, то получается, что в оперативной обработке сервера будет находиться примерно 60 тыс. писем (500 писем х 60 секунд х 2 минуты). Если средний размер одного письма составляет 5 Кбайт, то потребуется примерно 300 Мбайт памяти. Вместе с тем одно и то же спам-сообщение может рассылаться многократно в течение продолжительного периода времени (например, в течение 20 дней). В этом случае серверу необходимо хранить статистику о 850 млн писем (500 писем * 60 секунд х 60 минут х 24 часа х 20 дней). Если по каждому письму хранить хотя бы 1 Кбайт данных, то вместе с индексами получается уже больше 1 Тбайт постоянно обновляющихся данных на каждом сервере. А если учитывать общее количество почтовых серверов, то итоговая сумма получается внушительной.

 

Анализ

Традиционно информационные хранилища предоставляют примерно одинаковый набор инструментов анализа данных: многомерный анализ (OLAP), регрессия, классификация, кластеризация и поиск закономерностей. Сегодня появились и продукты — например, SAP HANA, Greenplum Chorus, Aster Data nCluster, — позволяющие запускать перечисленные методы и на Больших Данных.

Для понимания потенциальных возможностей таких решений необходимо рассмотреть лежащие в их основе алгоритмы, а также проанализировать пути для их возможного распараллеливания — ключа к обработке Больших Данных. При этом важно не привязываться к конкретным технологиям распределенной обработки данных (например, MapReduce), а лишь учитывать ключевые параметры, характерные для Больших Данных (интенсивность сетевого взаимодействия и объемы).

Важным фактором, влияющим на скорость работы любой СУБД, является количество операций ввода/вывода и эффективность построенных индексов. Для работы с Большими Данными применимы все уже существующие методы, начиная от классических B-деревьев и заканчивая сложными структурами для оперирования многомерной информацией.

Многомерный анализ

Суть метода заключается в построении многомерного куба и получении его различных срезов. Результатом анализа, как правило, является таблица, в ячейках которой содержатся агрегированные показатели (количество, среднее, минимальное или максимальное значение и так далее). В зависимости от реализации, системы многомерного анализа делятся на MOLAP, ROLAP и HOLAP. Среди них ROLAP-системы являются наиболее прозрачными и изученными, поскольку основываются на широко распространенных реляционных СУБД, в то время как внутреннее устройство MOLAP и HOLAP обычно более закрыто и относится к области «ноу-хау» конкретных коммерческих продуктов.

MOLAP представляет информацию в виде «честной» многомерной модели, но внутри используются те же подходы, что и в ROLAP: схемы «звезда» и «снежинка». С точки зрения СУБД база данных ROLAP — это обыкновенная реляционная база, и для нее необходимо поддерживать весь перечень операций. Однако это не позволяет, во-первых, жестко контролировать этапы ввода данных. Во-вторых, собирать статистику и подбирать оптимальные структуры для хранения индексов. В-третьих, оптимизировать размещение данных на диске для обеспечения высокой скорости ввода/вывода. В-четвертых, нет возможности для кэширования промежуточных агрегатных значений. В-пятых, при выполнении аналитических запросов из-за высоких требований к быстродействию нет возможности произвести глубокий статистический анализ и выработать оптимальный план выполнения. В ROLAP используются «родные» реляционные оптимизаторы запроса, которые никак не учитывают «многомерность» базы данных. Технологии MOLAP лишены перечисленных недостатков и благодаря этому позволяют добиться большей скорости анализа.

Выбор технологии MOLAP/ROLAP/HOLAP при анализе Больших Данных зависит от частоты обновления базы данных. С точки зрения распараллеливания обработки, на первый взгляд, все просто — любой многомерный куб может быть «разрезан» по делениям одного из измерений и распределен между несколькими серверами. Например, можно разделить куб на временные периоды (по годам и месяцам), по территориальному признаку (каждый сервер отвечает за свой регион) и так далее. Критерием для разделения куба является следующий принцип: выполнение многомерного запроса должно ложиться не на один сервер, а на несколько, после чего полученные результаты собираются в единое целое. Например, если пользователь запрашивает статистику продаж по стране за указанный промежуток времени, а данные распределены по нескольким региональным OLAP-серверам, то каждый сервер возвращает свой собственный ответ, которые затем собираются воедино. Если же данные будут распределены по временному критерию, то при выполнении рассматриваемого примера запроса вся нагрузка ляжет на один сервер.

Проблема в том, что, во-первых, очень трудно заранее определить оптимальное распределение данных по серверам, а во-вторых, для части аналитических запросов может быть заранее неизвестно, какие данные и с каких серверов понадобятся.

Применительно к Большим Данным это означает, что существующие подходы для многомерного анализа могут хорошо масштабироваться и что они допускают распределенный сбор информации (рис. 1)  —  каждый сервер может самостоятельно собирать информацию, осуществлять ее очистку и загрузку в локальную базу.

Регрессия

Под регрессией понимают построение параметрической функции, описывающей изменение указанной числовой величины в указанный промежуток времени. Эта функция строится на основе известных данных, а затем используется для предсказания дальнейших значений этой же величины. На вход метода поступает последовательность пар вида «время — значение», описывающая поведение этой величины при заданных условиях, например количество продаж конкретного вида товара в конкретном регионе. На выходе — параметры функции, описывающей поведение исследуемой величины.

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

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

Если регрессионный анализ сводится к вычислению взвешенных сумм, то он обладает примерно той же степенью применимости и при работе с Большими Данными, что и многомерный анализ. То есть системы регрессионного анализа волне могут масштабироваться и работать в условиях распределенного сбора информации.

Классификация

Задача классификации отчасти похожа на задачу регрессии и заключается в попытке построения и использования зависимости одной переменной от нескольких других. Например, имея базу данных о цене объектов недвижимости, можно построить систему правил, позволяющую на основе параметров нового объекта предсказать его примерную цену. Отличие классификации от регрессии состоит в том, что анализируется не временной ряд  —  подаваемые на вход значения никак не могут быть упорядочены.

На текущий момент разработано множество методов классификации (функции Байеса, нейронные сети, машины поддерживающих векторов, деревья решений и т. д.), каждый из которых имеет под собой хорошо проработанную научную теорию (самообучающиеся системы, метод обучения с учителем). Вместе с тем все методы классификации строятся по одной и той же схеме. Сначала производится обучение алгоритма на сравнительно небольшой выборке, а затем  —  применение полученных правил к остальной выборке. На первом этапе возможно копирование массива данных на один сервер для запуска «классического» алгоритма обучения без распараллеливания работы. Однако на втором этапе данные могут обрабатываться независимо  —  система правил, полученная по итогам самообучения, копируется на каждый сервер, и через нее прогоняется весь массив данных, хранящийся на этом сервере. Полученные результаты могут либо сохраняться там же на сервере, либо отправляться для дальнейшей обработки.

Таким образом, на этапе обучения классификаторов о работе с Большими Данными пока речи не идет — не существует выборок такого объема, подготовленных для обучения систем, а на этапе классификации отдельные порции данных обрабатываются независимо друг от друга. Это означает, что существующие методы классификации также применимы для работы с Большими Данными.

Кластеризация

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

Проблема кластеризации Больших Данных состоит в том, что имеющиеся алгоритмы предполагают возможность непосредственного обращения к любой информационной сущности в исходных данных (заранее невозможно предугадать, какие именно сущности понадобятся алгоритму). В свою очередь, исходные данные могут быть распределены по разным серверам, и при этом не гарантируется, что каждый кластер хранится строго на одном сервере. Если распределение данных по серверам делать прозрачным для алгоритма кластеризации (он считает, что данные расположены в некоторой распределенной виртуальной памяти), то это неизбежно приведет к копированию больших объемов с одного сервера на другой.

Решение проблемы может быть следующим. На каждом сервере запускается свой алгоритм, который оперирует только данными этого сервера, а на выходе дает параметры найденных кластеров и их веса, оцениваемые исходя из количества элементов внутри кластера. Затем полученная информация собирается на центральном сервере и производится метакластеризация  —  выделение групп близко расположенных кластеров с учетом их весов. Этот метод универсален, хорошо распараллеливается и может использовать любые другие алгоритмы кластеризации, однако он требует проведения серьезных научных исследований, тестирования на реальных данных и сравнения полученных результатов с другими «локальными» методами.

Таким образом, для анализа Больших Данных подавляющая часть методов кластеризации неприменима в чистом виде и необходимы дполнительные исследования.

Поиск закономерностей

Суть метода заключается в нахождении правил, описывающих взаимозависимости между внутренними элементами данных. Классическим примером является анализ покупок в супермаркете и выявление правил вида «если человек покупает пельмени, то обычно он покупает еще и сметану». На вход задачи поиска закономерностей поступает неупорядоченное множество сущностей, для каждой из которых известен набор присутствующих информационных признаков: например, такими сущностями могут быть чеки на покупки, а признаками  —  купленные товары. Задача поиска закономерностей сводится к выявлению правил вида «если присутствуют признаки A1, A2, ..., AN, то присутствуют и признаки B1,B2,…, BM», при этом каждое правило характеризуется двумя параметрами: вероятностью срабатывания и поддержкой. Первый параметр показывает, как часто выполняется данное правило, а второй — как часто применимо данное правило, то есть как часто встречается сочетание признаков A1, A2, ..., AN. С практической точки зрения аналитика интересуют правила с высокой поддержкой и вероятностью срабатывания, но каков должен быть баланс между этими показателями — это вопрос конкретной практической задачи.

Задача поиска закономерностей решается с помощью алгоритма Apriori, и очевидно, что с точки зрения обработки Больших Данных ключевой операцией здесь является вычисление агрегирующих функций (значений F(D1,…, Dk)), что выполняется средствами многомерного анализа. Другим важным моментом алгоритма Apriori, препятствующим обработке именно Больших Данных, может показаться работа с наборами информационных признаков, но тут необходимо учесть следующее обстоятельство: количество рассматриваемых наборов зависит от количества информационных признаков, то есть от концептуальной модели данных, а не от их объема.

 

Алгоритм Apriori

Пусть C1…Ck  —  это множество всех анализируемых признаков, тогда каждое искомое правило представимо в виде «если присутствуют A1…An, то присутствуют и B1…Bm», где множества A и B не имеют общих элементов и входят в множество C. Обозначим F(X1…Xp) — количество информационных сущностей, у которых присутствуют признаки X1…Xp. Тогда поддержка правила определяется значением F(A1…An), а вероятность срабатывания — отношением F(A1,…, An, B1,…Bm)/F(A1…An). Таким образом, задачу оценки каждого правила можно свести к вычислению значений функции F. Остается открытым вопрос, связанный с нахождением множеств A и B, дающих правила с высокой поддержкой и вероятностью срабатывания. Для этого итеративно рассматриваются наборы признаков D1,…, Dk. На каждом шаге берется уже построенный набор с максимальным значением F(D1,…, Dk), в него добавляются новые признаки и, таким образом, получаются наборы F(D1,…, Dk, Dk+1), которые помещаются в множество уже построенных наборов и далее обрабатываются точно таким же образом.

Важно сделать два замечания. Во-первых, наборы рассматриваются в порядке убывания значения функции F(D1,…, Dk). Во-вторых, на каждой итерации в уже существующий набор добавляется новый признак, в результате чего значение функции F() либо убывает, либо (в лучше случае) остается таким же. В-третьих, элементы внутри набора D оказываются как бы отсортированы и сначала идут более частые, а затем — менее частые. Построение правила вида «если присутствуют A1…An,то присутствуют B1…Bm» на основе набора D состоит в следующем: стоящие в начале набора элементы помещаются в условие правила, а остальные элементы — в заключение правила. Иными словами, набор может быть преобразован в правило «если присутствуют D1…Dq, то присутствуют Dq+1…Dk». Выбор значения q, дающего оптимальный баланс поддержки и вероятности срабатывания правила, осуществляется перебором, но на практике предполагается значение m=1, то есть q=k-1.

 

Изменение алгоритма Apriori для обработки Больших Данных состоит в способе вычислении функции F(), а для этого могут быть задействованы уже рассмотренные способы распараллеливания алгоритмов многомерного анализа.

Итак, существующие алгоритмы анализа данных вполне могут распараллеливаться и, следовательно, потенциально применимы для анализа Больших Данных.

Визуализация результатов

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

Во-вторых, значительно усложняется концептуальная модель выходной информации. Если в информационных хранилищах типичный отчет имел не более десятка входных параметров (например, временной срез, регион и т.д.), а более точная параметризация была не нужна, поскольку отчет банально становился вырожденным и состоящим из пустых строк и нулей, то для Больших Данных такая вырожденность исчезает.

 

Рис. 2. Обобщенная схема оценки необходимых методов анализа
Рис. 2. Обобщенная схема оценки необходимых методов анализа

Задачи анализа данных можно представить в виде равнобедренного треугольника (рис. 2), в основании которого объем исходных данных, а любая горизонтальная прямая, проведенная на некотором уровне, показывает, как много результатов будут давать соответствующие методы анализа. По мере роста объема исходных данных вершина треугольника сначала проходит уровень простого поиска и просмотра данных, затем многомерного и статистического анализа, и лишь затем выходит на уровень Data Mining. Однако по мере роста объемов исходных данных и на уровне Data Mining становится слишком много выходной информации. Получается, что если раньше для принятия решений необходимо было просмотреть всего несколько листов отчета, то в случае Больших Данных это не так. На человека, отвечающего за принятие решений, сваливается груда данных, из которой необходимо выделить наиболее важные. Эту проблему можно решить двумя способами.

Первый заключается в использовании автоматизированных средств, позволяющих выбрать наиболее важные отчеты, — например, в случае мониторинга динамики продаж отбирать отчеты, в которых наблюдается наиболее резкое изменение показателей по сравнению с предыдущим периодом. Такой метод применим не всегда, поскольку изменение показателей может просто объясняться внешними факторами, неизвестными системе: например, резкий рост спроса на газированную воду может объясняться жарой и совсем не говорит о том, что на следующий период необходимо планировать такие же объемы продаж.

Второй способ борьбы с большим количеством отчетов заключается в реорганизации работы — выделяются отдельные люди, в обязанности которых входит просмотр отчетов и формирование резюме, направляемых лицам, принимающим решения (рис. 3). Формирование таких резюме в значительной мере отличается от существующих средств генерации отчетов по следующим причинам. Во-первых, в резюме может входить самая разнородная информация. То есть один и тот же документ может включать в себя и показатели продаж, и динамику роста цен, и изменения в штатном расписании, и что угодно еще, вплоть до фотографий торговых залов. Во-вторых, все резюме уникальны и даже могут не иметь общего формата. В-третьих, резюме всегда готовятся для конкретного человека по конкретному случаю, а следовательно, учитывают и специфику случая, и особенности этого человека. Когда-то может быть удобен распечатанный текстовый документ, когда-то — презентация в формате для выступления перед аудиторией, а когда-то —аудиозапись или видео. Одним словом, резюме должно позволять максимально быстро и наглядно получить всю информацию, необходимую для принятия решений.

 

Рис. 3. Реорганизация схемы использования средств анализа
Рис. 3. Реорганизация схемы использования средств анализа

 

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

На данный момент подобные системы кажутся излишествами, но по мере роста числа практических задач, связанных с анализом Больших Данных, быстрая и удобная подготовка отчетов станет жизненно необходима. В противном случае принимающий решения персонал может попросту захлебнуться в океане отчетов и результатах анализа.

***

Для работы с Большими Данными в ряде случаев применимы методы, разработанные в информационных хранилищах и на деле доказавшие свою эффективность, — некоторые из существующих алгоритмов могут быть адаптированы для обработки больших распределенных информационных массивов. Вместе с тем серьезные затруднения могут возникнуть при наглядном представлении полученных результатов — из-за огромных объемов информации, поступающей на вход, резко возрастает количество разнородных отчетов на выходе. Для их удобного представления необходимы новые программные средства, принципиально отличающиеся от генераторов отчетов, используемых для традиционных хранилищ.

Константин Селезнев (skostik@relex.ru) — старший инженер-программист компании «РЕЛЭКС» (Воронеж).

Купить номер с этой статьей в PDF