Теория неточных, или грубых, множеств может быть использована для организации анализа больших объемов неточных данных, отличающихся противоречивостью, неполнотой или неопределенностью [1]. Например, теория позволяет упростить исходный массив сырых данных, построив его более простую модель или создав неточную модель базы данных, обладающую большей гибкостью по сравнению со стандартными, «точными» аналогами. Кроме того, принципы неточных множеств можно применить для построения масштабируемых аналитических систем, выделяя части данных, которые действительно необходимо обработать для выполнения SQL-запроса. Теорию неточных множеств (rough set theory) не стоит путать с теорией нечетких множеств (fuzzy set theory). Главная идея теории неточных множеств состоит в том, что каждое множество имеет верхнее и нижнее приближения, составляемые из классов эквивалентных описаний, а основное положение теории нечетких множеств в том, что принадлежность нечеткому множеству может иметь градации (например, с определенной вероятностью) в отличие от классической теории множеств. На примере аналитической системы обработки данных Infobright можно показать, как неточные множества помогают оптимизировать SQL-запросы за счет сокращения объемов обрабатываемых сырых данных, их разбиения и создания высокоуровневых описаний.

Платформа Infobright, созданная в 2005 году при поддержке ряда венчурных фондов и компании Sun Microsystems, предназначалась для анализа Больших Данных с помощью теории неточных множеств. В 2006 году компания стала партнером MySQL, а год спустя была выпущена открытая версия платформы. Впоследствии была создана коммерческая компания Infobright, которая стала сотрудничать с такими поставщиками решений бизнес-аналитики, как Pentaho, Jaspersoft и Informatica. Сегодня эта платформа оказалась удобной для работы с Интернетом вещей благодаря промышленной реализации неточно гранулированного (rough-granular) подхода к масштабируемому анализу.

Идея Infobright состоит в разбиении данных на блоки, составлении их описаний и проведении приближенных вычислений, что при выполнении SQL-запроса позволяет существенно сократить объем обрабатываемых данных. Например, если в запросе отбираются все строки (в Infobright данные хранятся по столбцам), в которых значение столбца А равно 15 и для каждого блока данных вычислены минимальное и максимальное значения в столбце А, то можно по мере выполнения запроса отбросить блоки, в которых минимальное значение больше 15 или максимальное меньше 15.

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

Во время загрузки данных в Infobright входные строки разбиваются на пакеты, каждый из которых представляет собой набор значений одного отдельно взятого признака, — например, блоком могут быть 100 строк со значениями столбца А. Пакеты данных сжимаются без потерь и хранятся на диске, однако до сжатия вычисляются различные математические характеристики и описания пакетов: максимальное и минимальное значения признака, сумма всех значений, число ненулевых значений, различные гистограммы распределений, карты встречаемости разных символов для строковых данных и т. д. Такие компактные описания пакетов данных и есть неточные данные.

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

В случае SQL-оператора BETWEEN для числового признака в запросе можно использовать минимальные и максимальные значения признака, чтобы сразу исключать пакеты, не удовлетворяющие этому условию. Подобным образом обработку можно проводить и другими SQL-фильтрами — например, LIKE для признаков типа VARCHAR (строковые данные переменной длины). Неточные описания могут применяться и при обработке прочих частей SQL-запроса: объединений запросов, подзапросов и т. д. Однако исключение данных — не единственное преимущество использования неточных описаний. Предположим, требуется посчитать число строк таблицы T, в которых значения признака A больше x и меньше y. Для пакета данных, у которого минимальное значение больше x, а максимальное меньше y, можно использовать информацию о числе элементов в этом пакете и о том, что все значения удовлетворяют рассматриваемому ограничению BETWEEN x AND y. На рисунке показана схема обработки SQL-запроса с условием равенства (WHERE), что аналогично рассматриваемой ситуации.

Классификация пакетов данных по релевантности обрабатываемому запросу
Классификация пакетов данных по релевантности обрабатываемому запросу

 

Выделяют три категории пакетов: релевантные запросу, в которых все значения удовлетворяют условию запроса и потому подходят для дальнейшей обработки; нерелевантные, в которых нет элементов, удовлетворяющих условию запроса; возможно релевантные, то есть пакеты, не классифицируемые как релевантные или нерелевантные. В теории неточных множеств для исследуемого свойства вводятся положительные, отрицательные и граничные области неточного множества — множества объектов, о которых известно, что они обладают данным свойством (положительная область), не обладают этим свойством (отрицательная область) или не известно, обладают ли они этим свойством (граничная область). Теория позволяет судить о понятиях в стиле, схожем с троичной логикой: «да — нет — не знаю», и применяется не только в Infobright. Однако именно в Infobright она была применена впервые для ускорения SQL-запросов и анализа данных в промышленных проектах для таких компаний, как Yahoo и Bwin.

Области неточного множества используются для аппроксимации исследуемых понятий (например, предопределенных классов решений или их объединений) в приложениях поддержки принятия решений и обнаружения знаний (knowledge discovery) [2]. В случае Infobright эти исследуемые понятия соответствуют подмножествам строк, удовлетворяющих некоторым условиям запроса, поэтому приближенные понятия могут быть совершенно разными при выполнении различных SQL-запросов. Более того, они могут изменяться по мере обработки запроса. Тем не менее фундаментальная идея построения неточных приближений на основе имеющейся на данный момент информации остается прежней.

При обработке как точных, так и приближенных запросов лучше использовать связи между неточными описаниями и конкретными слоями данных, а не только гранулированные таблицы. Покажем это на примере обработки запроса с условием WHERE для нескольких признаков. Допустим, имеется объединение двух условий, каждое наложено на один признак, и для определенного строкового пакета оба пакета данных, соответствующие признакам, были классифицированы как возможно релевантные. Однако такой пакет может не содержать релевантных значений, если неточное описание слишком общее, — например, для условия A = x, наложенного на целочисленный признак А, описание в виде гистограммы вместе с указанием минимальных и максимальных значений может привести к классификации пакета как возможно релевантного даже в том случае, когда в нем нет ни одного значения признака А, в точности равного x. Поэтому в таком случае классификация пакета на основе значений одного признака может измениться после обработки последующего условия на другой признак, то есть запрос адаптивен — план его исполнения строится на основе информации, получаемой уже по ходу обработки.

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

***

Создание блоков данных с неточными описаниями позволяет ускорить выполнение SQL-запросов типа SELECT, хотя до сих пор ведутся споры относительного того, должны ли аналитические запросы быть совершенно точными. Теория неточных множеств способна стать неплохой базой при создании промышленных аналитических приложений, а также приложений прогнозного и исследовательского анализа динамичных источников данных. Кроме того, в системах машинного обучения могут потребоваться масштабируемые алгоритмы, основанные на нерегламентированных запросах. Продвинутые методы неточных запросов будут особенно полезны при анализе больших объемов синтетических данных, где синхронизация информации может быть проведена за разумное время только на уровне неточных описаний.

Литература

  1. Z. Pawlak. Rough Sets // International Journal of Computer and Information Sciences — 1982. Vol. 11, N. 5 — P. 341–356. URL: https://wiki.eecs.yorku.ca/course_archive/2010-11/W/4403/_media/rough_sets.pdf (дата обращения: 15.12.2014).
  2. R.W. Swiniarski, A. Skowron. Rough Set Methods in Feature Selection and Recognition // Pattern Recognition Letters — 2003. Vol. 24, N. 6 — P. 833–849. URL: https://wiki.eecs.yorku.ca/course_archive/2013-14/F/4403/_media/roughsetmethods.pdf (дата обращения: 15.12.2014).
  3. W. Pedrycz. History and Development of Granular Computing // History of Mathematics, Encyclopedia of Life Support Systems (EOLSS). ISBN: 978-1-84826-671-1. URL: http://www.eolss.net/sample-chapters/c02/E6-132-45.pdf (дата обращения: 15.12.2014).

Доминик Слезак (slezak@mimuw.edu.pl) — профессор, Варшавский Университет; Юрий Кашницкий (ykashnitsky@hse.ru) — стажер-исследователь, Сергей Кузнецов (skuznetsov@hse.ru) — заведующий лабораторией, НИУ ВШЭ (Москва).