автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Средства создания параллельных алгоритмов интеллектуального анализа данных

На правах рукописи

005531291

Каршиев Зайнидин Абдувалиевич

СРЕДСТВА СОЗДАНИЯ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ ИНТЕЛЛЕКТУАЛЬНОГО АНАЛИЗА ДАННЫХ

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

4 \т 2013

Санкт-Петербург - 2013

005531291

Работа выполнена в федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В.И. Ульянова (Ленина)» (СПбГЭТУ) на кафедре вычислительной техники

Научный руководитель - доктор технических наук, профессор

Куприянов Михаил Степанович

Официальные оппоненты:

доктор технических наук, профессор Яковлев Сергей Алексеевич, Санкт-Петербургский государственный электротехнический университет «ЛЭТИ», профессор кафедры «Автоматизированных систем обработки информации и управления»

кандидат технических наук, Смирнов Александр Николаевич, ЗАО «Моторола Солюшнз», ведущий инженер

Ведущая организация - Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Санкт-Петербургский государственный университет аэрокосмического приборостроения»

Защита состоится 2013 г. в /£/¿7 час, на заседании

диссертационного совета Д 212.238.01 Санкт-Петербургского государственного электротехнического университета «ЛЭТИ» им. В.И. Ульянова (Ленина) по адресу: 197376, Санкт-Петербург, ул. Проф. Попова, 5.

С диссертацией можно ознакомиться в библиотеке университета.

Автореферат разослан « » 2013 г.

Ученый секретарь совета по защите докторских и кандидатских диссертаций Д 212.238.01, к.т.н.

Общая характеристика работы

Актуальность работы

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

• производительность - анализ больших объемов (измеряемых терабайтами) требует больших вычислительных ресурсов и может выполняться за неприемлемое для аналитика время;

• распределенность - в связи с большим объемом данных хранение информации может быть реализовано в распределенном хранилище, кроме того в силу природы данных они могут храниться в разных источниках.

Обе проблемы могут решаться за счет параллельного и/или распределенного выполнения интеллектуального анализа данных.

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

Не являются исключением и алгоритмы интеллектуального анализа данных. В настоящее время проводится достаточно большое количество исследований в этой области. Выделены отдельные направления в области ИАД (в зарубежной литературе данная область имеет название Data Mining): параллельный ИАД (Parallel Data Mining) и распределенный ИАД (Distributed Data Mining). Большинство усилий исследователей в области параллельных алгоритмов ИАД направлено на распараллеливание отдельных алгоритмов анализа и их дальнейшую оптимизацию. Как правило, получаемы решения ориентированы на определенную среду вычисления и при переносе такого решения в другие условия оно становится не эффективным. В связи с этим, исследование в области общих подходов к распараллеливанию существующих алгоритмов интеллектуального анализа является актуальной задачей.

Целью диссертационной работы является разработка средств построения параллельных алгоритмов ИАД для выполнения в распределенной среде. Для достижения заявленной цели в работе решаются следующие задачи:

- анализ существующих подходов к созданию параллельных алгоритмов ИАД;

- разработка формальной модели алгоритма ИАД;

- разработка метода создания параллельных алгоритмов ИАД на основе потоко-безопасных функциональных блоков;

- разработка методики построения параллельных алгоритмов ИАД для выполнения в распределенной среде;

- разработка программных шаблонов для реализации последовательных и параллельных алгоритмов ИАД из потокобезопасных функциональных блоков;

- проведение экспериментов по выполнению алгоритмов, построенных в соответствии с предложенной методикой.

Объектом исследования являются алгоритмы ИАД.

Предметом исследования являются методы распараллеливания алгоритмов ИАД.

Методы исследования. Методы теории множеств, методы распараллеливания алгоритмов, методы проектирования программного обеспечения.

Научная новизна работы заключается в следующем:

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

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

3. Предложена методика распараллеливания алгоритмов ИАД, которая отличается от известных тем, что к последовательным алгоритмам анализа применяется предложенный метод создания параллельных алгоритмов ИАД с учетом характеристик распределенной среды.

Практическая значимость:

1. Для создания параллельных алгоритмов ИАД предложены программные шаблоны, построенные на основе формальной модели и отделяющие реализацию алгоритма от средств распределенного выполнения.

2. Разработана библиотека параллельных алгоритмов ИАД для выполнения в распределенной среде, включающая в себя предложенные шаблоны.

Положения, выносимые на защиту:

1. Формальная модель алгоритмов ИАД.

2. Метод создания параллельных алгоритмов ИАД из потокобезопасных функциональных блоков.

4. Методика распараллеливания алгоритмов ИАД для выполнения в распределенной среде.

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на международных конференциях по мягким вычислениям и измерениям 8СМ'2010, 8СМ'2011 и 5СМ'2012, Санкт-Петербург, 2010-2012 гг, конференциях профессорско-преподавательского состава СПбГЭТУ «ЛЭТИ», Санкт-Петербург, 2011 -2013 гг.

Внедрение результатов работы. Результаты работы были использованы при выполнении НИР и в учебном процессе СПбГЭТУ на кафедре вычислительной техники.

Достоверность результатов исследования. Достоверность результатов диссертационной работы подтверждается корректным применением математического аппарата и результатами машинного моделирования на гетерогенном кластере в ресурсном центре СПбГЭТУ.

Публикации. Основные теоретические и практические результаты диссертации опубликованы в 12 работах, среди которых 4 работы в ведущих рецензируемых изданиях, рекомендуемых в действующем перечне ВАК, 2 раздела в 2-х монографиях, 4 работы - в материалах международных научно-технических конференций, 2 свидетельства о регистрации программ для ЭВМ.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав с выводами по каждой из них, заключения, списка литературы, включающего 77 наименований. Основная часть работы изложена на 178 страницах машинописного текста. Работа содержит 55 рисунка, 8 таблиц и 1 приложение общим объемом 5 страниц.

Основное содержание работы

Во введении дано обоснование актуальности темы диссертационного исследования, сформулированы цели и задачи работы, ее научная новизна и практическая значимость, представлены положения, выносимые на защиту.

В первой главе дается общий обзор существующих подходов к параллельному выполнению алгоритмов ИАД. В результате анализа существующих направлений исследований в области разработки параллельных алгоритмов ИАД можно выделить два основных подхода:

— декомпозиция алгоритма для возможной параллелизации - обобщенный подход к алгоритму ИАД, предполагающий разделения его на некоторые части, которые могут выполняться параллельно;

- индивидуальное распараллеливание алгоритмов - индивидуальный подход к каждому алгоритму ИАД и выбор наиболее эффективной параллельной структуры для заданных условий.

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

В рамках первого подхода можно выделить коммерческий проект NIMBLE компании IBM. Данный проект направлен на разработку инфраструктуры, позволяющей осуществлять параллельное выполнение алгоритмов ИАД на средствах, реализующих концепцию MapReduce. Она предполагает, что алгоритм декомпозирован на отдельные части (части шар и reduce) которые могут выполняться параллельно. Данный проект, во-первых, ограничен концепцией MapReduce, а во-вторых не содержит методики декомпозиции алгоритма ИАД.

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

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

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

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

Во второй главе описана блочная структура алгоритма ИАД и его формальное описание.

Проведенный анализ алгоритмов ИАД позволил выделить ряд особенностей таких алгоритмов:

1) итерационная обработка больших объемов данных;

2) наличие в алгоритмах типовых блоков (циклы по векторам и атрибутам и др.);

3) формирование на основе входных данных (набора данных, настроек выполнения и начальной модели знаний) результата в виде модели знаний.

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

Л/ = ^(Д5',М0).

Набор данных (О) опишем формально, как набор из трех элементов:

П(А,Г,1Г),

где:

А - независимые атрибуты набора данных: А = {а1,...,а1,...,ат},

где а, -атрибут набора данных;

Т - множество целевых атрибутов определяемых, как и атрибуты выше:

Т = {ат+и...,ак,...,а,}.

Пара (А,Г) представляет собой метаданные набора данных.

ТУ = {щ,...,м>г,...,м>1\ - множество векторов данных представляющих собой наборы значений соответствующих атрибутов:

"V = К,,-, V,угаг,ут+1г,...,у4ут+,г},

где у1Г гД(а,) - значение атрибута а, вектора уи.

Модель знаний (М) формально можно описать следующим образом:

где

Л = {г,,...,/;,...,гя} - множество правил;

..........

где кр = : и<г е Иг,у1г = р || - количество векторов, у которых целевой атрибут а, имеет значение у1р, при этом = Д(/).

Модель знаний (М) может дискретно принимать одно из состояний:

• М„ - начальное состояние модели знаний;

• М, -модель после 1-го изменения;

•............

• М — завершенная модель знаний.

Под дискретным состоянием понимается состояние модели знаний, при которой она является целостной, т.е. удовлетворяет всем ограничениям, которые на нее накладываются.

Настройки алгоритма можно представить как набор пар: параметр и его значение:

^((■П'А).....(^Л).-.(^-Л)).

где ^ - у-й параметр настройки алгоритма, а р — значение у-ого параметра настройки выполнения алгоритма.

Алгоритм ИАД (Р) можно представить как набор последовательно выполняющихся операций:

Р={о1,....ор....,оя},

где Ор - операция, изменяющая модель знаний от одного дискретного состояния в другое на основании преданных ей данных и настроек. Таким образом, аргументами операции должны быть данные Д, настройки 5 и модель знаний до изменений М„ а ее результатом модель знаний после изменения М-1+1\

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

В соответствии с этим, алгоритм ИАД можно представить как последовательность (упорядоченное множество) операций, результат каждой из которых передается следующей в последовательности операции в качестве аргумента:

При этом каждую такую операцию можно также декомпозировать на отдельные операции (функциональные блоки), выполняющиеся последовательно:

= О,, (Д Мр) = \ор , (А Л/„), Ор2 ( ДМр,).....0рм{0,8,Мри),...,0ру{0,3,Мру)\

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

Условный оператор представим как элемент следующего вида:

Мм =D(D,S,Mi) = {d{D,S,Mi),О, (D,S,M,),Of (D,S,Mt )},

где:

d(p,S,Mi) - условная функция, возвращающая значение истина или ложь, на основании анализа данных D и текущей модели М,, но не меняющая их; 0,(D,S,Mj) - операция, выполняющаяся при значении - истина, возвращаемом функцией d(D,S,Mt)\

Of(D,S,Ml) - операция, выполняющаяся при значении - ложь, возвращаемом

функцией d(D,S,Mi);

Цикл представим следующим образом:

Мм =C(D,S,M,) = {d (D, S, М, ),Oc{D,S, М,)},

где Oc{D,S,Mj) - операция, выполняющаяся пока условная функция d(D,S,Mt) возвращает значение — истина.

Таким образом, в алгоритме могут присутствовать как операции, так и структурные элементы. Обобщим их в понятие функционального блока алгоритма:

1Ъ(Д S.M,) 6 \ош (D,S,Mi),Odel (D,S,M,),Och (D.S.M,)} b,(D,S,M,) = \ (1)

[e(d,s,m,)s{d(d,s,m,),c{d,s,m,)}

Описанные таким образом функциональные блоки обладают двумя свойствами:

• детерминизм - при одних и тех же входных аргументах (данных, настройках и начальном состоянии модели знаний) возвращаемая модель знаний будет одна и та же;

• не имеет побочных эффектов - т.е. при выполнении функциональных блоков изменение внешних элементов не происходит.

Алгоритм ИАД может быть представлен как упорядоченная последовательность функциональных блоков:

Mg=F(M0,S,D) = (b0(D,S,M0),-A{D,S,Mt),.:,bq( D.S.M^))-Таким образом, сам алгоритм ИАД также не имеет побочных эффектов и обладает свойством детерминизма.

Для описания с помощью формальной модели параллельно выполняющихся ветвей алгоритма добавим в нее следующий структурный элемент:

Мм = P(D,S,M,) = {s(D,S,M,),bd (D,S,M,)A (D.S.M,).....hx (D.S.M,).....bz (D,S,M,)j{D,S,M,)}

где s(D,S,Mi) - операция split, выполняющая подготовительные действия для параллельного выполнения операций; j(D,S,M,) - операция join, выполняющая объединяющие действия после параллельного выполнения операций; bd(D,S,Mi) - блок, являющийся диспетчером для остальных блоков, если bd(D,S,Ml) = 0, то имеет место параллелизация без диспетчера.

Если параллельно выполняемые блоки одинаковы {1\=... = ЪХ=... = Ь:), то имеет место параллелизм по данным, иначе (если i\ *bx имеет место паралле-

лизм по задачам.

В случае параллелизма по данным должно выполняться условие:

т.е. все данные, обрабатываемые параллельными блоками, должны быть разными и их объединение должно составлять полный набор данных.

В случае параллелизма по задачам должно выполняться условие:

А =А =■•■ = «, =-=А.

т.е. все наборы данных, обрабатываемые параллельными блоками, представляют собой полные наборы данных.

Для взаимодействия параллельно выполняющихся последовательностей добавим в модель еще два структурных элемента:

- блок отправки данных:

5 (Д М,) = {0( Д 5, М;), х (т)), где 0(Д5',М1) - операция выполняемая, перед отправкой сообщения (например, подготовку сообщения); 5(т) - операция, выполняющая отправку сообщения т;

- блок получения данных:

Л (Д"£, М,) = {г (т), 0( А, М1)}, где г(т) - выполняющая прием сообщения ш; 0(ДХД,) - операция выполняющая обработку полученного сообщения.

Таким образом, окончательный вид формальной модели алгоритма ИАД (1) для параллельного выполнения будет следующий:

6,.(Д5,М,)= >)] (2)

[Е(А 5, А/,.) е {£) (А Я, Л/,.),С(Д 5, М1),Р(й, 5, М,),5(0,8, М,),Я (Д 5, М,)}

В соответствии с формальной моделью, алгоритм ИАД и блоки его составляющие не имеют побочных эффектов и обладают свойством детерминизма. Эти свойства гарантируют потокобезопастность таких блоков, следовательно, они могут быть выполнены параллельно.

В соответствии с формальной моделью, при разбиении на блоки необходимо соблюдать следующие требования:

• алгоритм является упорядоченной последовательностью функциональных блоков (1), которые удовлетворяют условиям описанным ниже;

• каждый блок может представлять собой или некоторую операцию, выполняемую над моделью или некоторый структурный элемент, характерный для алгоритма ИАД (2);

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

• внутри функционального блока не должно происходить обращений к внешним переменным, вся работа должна выполняться на основании: набора данных Б, настроек 8 и исходной модели знаний Мм, переданных в функциональный блок.

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

В результате алгоритм ИАД можно представить как иерархию вложенных пото-кобезопасных функциональных блоков (рисунок 3). При этом сам алгоритм, как отдельный функциональный блок также является потокобезопасным.

Рисунок 3. Блочная структура алгоритма

На основе выделенных в формальной модели блоков определены базовые пото-кобезопасные функциональные блоки для построения алгоритмов НАД:

-блокрешения 0(р,8,М,)\

- блок цикл С {О,Б, М^) и характерные для алгоритмов НАД:

■ блок цикл по векторам

■ блок цикл по атрибутам С4а(Д5',Л/1);

- блок параллельного выполнения />(£>,М,) и его разновидности:

■ блок параллелизации по данным Рм (£>,5, А/,);

■ блок параллелизации по задачам

- блок отправитель

- блок получатель Л(Д5,М,).

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

• декомпозировать алгоритм НАД на элементарные действия;

• сгруппировать элементарные действия в функциональные блоки, выполняющие дискретное изменение модели знаний;

• выделить структурные элементы и вложенные в них последовательности функциональных блоков;

• добавить в структуру алгоритма НАД функциональные блоки для параллельного выполнения.

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

- с параллелизацией по задачам/данным;

-с/без взаимодействия между параллельными ветвями для систем с распределенной памятью;

- с/без диспетчера.

Настройка блоков параллельного выполнения позволяет реализовать следующие типы параллельных алгоритмов ИАД:

• с одним источником данных и одной моделью знаний (SDSM) - в этом случае параллельные последовательности функциональных блоков работают с одним источником данных и одной моделью знаний;

• с несколькими источниками и одной моделью знаний (MDSM) - в этом случае каждая последовательность работает с отдельным источником, но с одной моделью знаний;

• с одним источником и несколькими моделями знаний (SDMM) - в этом случае каждая последовательность работает с общим источником данных, но строит каждая свою модель знаний, которые впоследствии объединяются в одну;

• с несколькими источниками и несколькими моделями знаний (MDMM) - в этом случае каждая последовательность работает со своим источником данных и строит каждая свою модель знаний, которые впоследствии объединяются в одну.

В третьей главе описаны программные шаблоны в виде классов для построения алгоритмов ИАД из отдельных блоков. Классы определяют, как операции, так и блоки соответствующие структурным элементам: блоки решения и циклы. Кроме того, предложены классы для реализации параллельных алгоритмов ИАД.

Рассмотрим каждый из классов подробнее.

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

Класс SequenceOfSteps - класс, реализующий упорядоченную последовательность блоков. Класс хранит последовательность объектов класса Step и переопределяет метод execute() таким образом, что он последовательно запускает все блоки на выполнение и обеспечивает передачу модели знаний измененной предыдущим блоком следующему блоку.

Класс CyclicStep - абстрактный класс для реализации цикла. Он хранит последовательность блоков (как объект класса SequenceOfSteps). На каждой итерации цикла выполняется хранящаяся последовательность блоков.

Класс DecisionStep - абстрактный класс проверки условия. Включает в себя две последовательности блоков (объектов класса SequenceOfSteps) и абстрактную функцию condition(), возвращающую значения «истина» или «ложь». В зависимости от результата данной функции выполняется одна или другая последовательность блоков.

Класс CycleByVectors - класс, реализующий цикл по векторам. Данный класс расширяет класс CyclicStep и осуществляет цикл по элементам (векторам) входных данных.

Класс MiningAlgorithm — класс, реализующий сам алгоритм как упорядоченную последовательность функциональных блоков. Абстрактный класс MiningAlgorithm содержит основную последовательность блоков алгоритма (как объект класса SequenceOfSteps). Он производит необходимые действия по инициализации модели знаний и объектов класса Step, после чего запускает выполнение основной последовательности блоков.

Класс ParallelStep является абстрактным (он не реализует описанный в классе Step метод execute()) и содержит в себе массив обработчиков параллельного выполнения ветвей алгоритма - handlers (и методы доступа к ним), а также настройки параллельного выполнения paralellAlgSettings.

Класс ParallelBlock отвечает за выполнение параллельных ветвей алгоритма и наследуется от класса ParallelStep. В классе ParallelBlock кроме унаследованных методов определены еще два метода - split() и join(). В методе split() выполняются операции по запуску параллельных ветвей алгоритма. В методе join() объединяются потоки и результаты работы отдельных ветвей.

Для реализации параллелизации по данным и по задачам от класса ParallelBlock наследуются два класса ParallelByData и ParallelByTask.

Класс ParallelByData реализует параллелизацию по данным. Он содержит параметр branche - последовательность шагов параллельных ветвей алгоритма, которая клонируется при запуске алгоритма для каждого доступного обработчика параллельной ветви. Для работы с этим параметром в классе определены: метод getBranche() — для получения последовательности и метод setBranche() — для формирования последовательности шагов.

Класс ParallelByTask реализует параллелизацию по задачам. Он, в отличие от класса ParallelByData, содержит массив последовательностей шагов для каждой ветви параллельного алгоритма - branches. Для работы с этим параметром в классе определены: метод getBranches() - для получения списка последовательностей и метод addBranche() - для добавления новой последовательности шагов.

Класс SenderStep - класс, реализующий блок отправителя. Он в методе execute() рассылает сообщения посредством обработчиков handlers всем параллельно выполняющимся ветвям алгоритма ИАД. Алгоритм формирования сообщения, как и само сообщение, зависит от алгоритма ИАД и реализуется в классе, наследуемом от SenderStep и реализующем соответствующий функциональный блок алгоритма.

Класс ReceiverStep — класс, реализующий блок получателя. Он определяет переменную message, содержащую получаемое сообщение. В методе execute() данного класса выполняется непосредственное получение сообщения и инициализация переменной message. Получение сообщения выполняется в цикле ожидания, т. е. выход из цикла осуществляется только после получения сообщения. Переменная message доступна дочерним классам и может быть в дальнейшем обработана в соответствии с алгоритмом ИАД.

Описанные классы позволяют реализовать любую структуру параллельного алгоритма из приведенных во второй главе.

Реализация операций split и join в классе параллельного блока позволяет выполнять параллелизацию вида SDSM, SDMM, MDSM и MDMM без изменения структуры алгоритма. Изменение поведения алгоритма выполняется за счет настройки его выполнения.

Существующие в классе ParallelStep ссылки на обработчики handlers, являются экземплярами класса ExecutionHandler - общего для всех средств распределенного вы-

полнения. В настоящее время широко используются средства выполнения распределенных вычислений: многопоточное выполнение, сервис-ориентированное выполнение, модель акторов, выполнение на основе концепции МарКеёисе, мультиагентное выполнение И др.

Для того, чтобы реализация алгоритма и его параллельная структура не зависели от средства выполнения, используется шаблон проектирования «Адаптер». В качестве адаптера используются классы, наследуемые от класса ЕхесЩюпНапсПег (на который ссылается класс РагаПеШер) для каждого средства реализации.

а) Среда выполнения

в) Возможность объединения модели знаний

Рисунок 4. Исходные данные для методики распараллеливания алгоритмов ИАД.

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

- среда выполнения параллельного алгоритма (рисунок 4. а);

- вид хранения данных (рисунок 4. б);

- вид функции ИАД (рисунок 4. в).

Методика состоит из двух основных этапов:

I. определение структуры параллельного алгоритма ИАД;

П. настройка параллельного алгоритма ИАД.

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

Для определения структуры параллельного алгоритма необходимо выполнить следующие действия:

1.1. декомпозировать алгоритм ИАД на элементарные операции;

1.2. сгруппировать в функциональные блоки действия, выполняющие дискретное изменение модели;

1.3. выполнить программную реализацию блочной структуры последовательного алгоритма;

1.4. выполнить анализ полученной структуры с учетом оставшихся циклов и условных переходов и определить структуру параллельного алгоритма;

1.5. выполнить программную реализацию параллельной структуры алгоритма ИАД на основе ранее реализованных функциональных блоков.

Первые два шага выполняются в соответствии с предложенным методом построения параллельного алгоритма ИАД, описанного выше.

На втором этапе распараллеливания алгоритма производится настройка выполнения параллельного алгоритма и анализ его эффективности с последующей отладкой. Этап включает в себя следующие шаги:

П.1. настройка выполнения параллельного алгоритма ИАД в соответствии с параметрами среды и типом распределения данных;

П.2. анализ параллельного выполнения алгоритма ИАД на тестовых данных, путем оценки эффективности и ускорения;

a. возврат на шаг П.1. в случае если результаты неудовлетворительны и не все настройки были испытаны;

b. возврат на шаг 1.4. в случае если результаты неудовлетворительны и все настройки были испытаны.

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

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

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

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

Для выполнения полного цикла анализа в библиотеку кроме классов для реализации алгоритмов добавлены классы, описывающие: исходные данные и их метаданные; модель знаний; настройки уровня алгоритма и функции ИАД.

Библиотека алгоритмов ИАД разделена на компоненты:

- CMW Classes - классы стандарта CWM;

- Library Core - базовые классы библиотеки;

- Parallel Core - классы для параллельного выполнения;

- Clustering Algorithms - алгоритмы кластеризации;

- Classification Algorithms - алгоритмы классификации и регрессии;

- Association Algorithms - алгоритмы поиска ассоциативных правил.

Для проверки выносимых на защиту результатов с использованием библиотеки было выполнено распараллеливание алгоритмов кластеризации и классификации — k-means и 1R в соответствии с предложенной методикой.

При распараллеливании алгоритма k-means первая структура параллельного алгоритма (предполагающая частичное распараллеливание) была признана не эффективной для всех типов параллельного выполнения алгоритма ИАД (Таблица 1).

Таблица 1

Количество векторов 150 1500 3000 6000

Последовательный алгоритм 27,834 мс 36,918 мс 553,274 мс 1035,382 мс

Параллельный алгоритм

SDSM 40,893 мс 118,984 мс 1219,746 мс 2760,848 мс

SDMM 68,804 мс 112,436 мс 1451,084 мс 3783,674 мс

MDSM 35,516 мс 45,218 мс 619,356 мс 1466,711 мс

MDMM 49,449 мс 77,365 мс 811,494 мс 2138,980 мс

Для повышения эффективности в соответствии с методикой было принято решение о реструктуризации алгоритма и параллельном выполнении всего алгоритма. Реструктуризация была выполнена за счет незначительного изменения кода. Этот алгоритм реализован в 528 строках кода и для изменения структуры алгоритма были изменены только четыре из них, то есть 0,75 % кода. Повторные эксперименты показали эффективность новой структуры при всех типах параллельного выполнения кроме SDMM для данных с количеством векторов 150 и 1500 (Таблица 2).

Таблица 2

Количество векторов 150 1500 3000 6000

Последовательный алгоритм 27,834 мс 36,918 мс 553,274 мс 1035,382 мс

Параллельный алгоритм

SDSM 19,445 мс 27,182 мс 341,904 мс 676,175 мс

SDMM 27,327 мс 41,651 мс 372,165 мс 722,527 мс

MDSM 15,669 мс 20,612 мс 303,576 мс 587,922 мс

MDMM 15,585 мс 21,106 мс 289,781 мс 613,402 мс

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

При распараллеливании алгоритма 1Я также были экспериментально проверены две параллельные структуры: с частичным распараллеливанием и с параллельным выполнением всего алгоритма. Первая структура алгоритма дает эффективные результа-

ты при всех типах параллельного выполнения кроме SDMM и SDSM для данных с количеством векторов 150 (Таблица 3). Вторая структура алгоритма дает эффективные результаты при всех типах параллельного выполнения кроме SDMM (Таблица 4). Реструктуризация параллельного алгоритма 1R также не потребовала больших усилий и была выполнена за счет незначительного изменения кода. Этот алгоритм реализован в 613 строках кода и для изменения структуры алгоритма были изменены только четыре из них, то есть 0,65 % кода.

Таблица 3

Количество векторов 150 1500 3000 6000

Последовательный алгоритм 18,114 мс 33,668 мс 42,704 мс 60,97 мс

Параллельный алгоритм

SDSM 18,665 мс 31,919 мс 41,446 мс 58,316

SDMM 19,005 мс 35,365 мс 44,428 мс 63,674

MDSM 13,238 мс 27,103 мс 33,795 мс 47,813

MDMM 13,719 мс 26,762 мс 33,902 мс 46,265

Таблица 4

Количество векторов 150 1500 3000 6000

Последовательный алгоритм 18,114 мс 33,668 мс 42,704 мс 60,97 мс

Параллельный алгоритм

SDSM 11,789 мс 20,803 мс 41,512 мс 58,789 мс

SDMM 18,258 мс 34,917 мс 44,014 мс 60,632 мс

MDSM 13,706 мс 27,983 мс 35,569 мс 47,812 мс

MDMM 13,506 мс 26,883 мс 32,352 мс 43,917 мс

Модели, полученные в результате выполнения последовательного и параллельных алгоритмов Ж, тоже не отличаются, то есть при распараллеливании алгоритма результат его работы не изменился.

Проведенные эксперименты доказали эффективность предложенных решений и подтвердили их правильность.

В заключении сформулированы основные научные и практические результаты работы:

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

2. Предложен метод построения алгоритмов ИАД на основе потокобезопасных функциональных блоков, позволяющий выполнять распараллеливание, как на структурном уровне, так и на уровне настройки без необходимости изменения таких блоков.

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

4. Предложена методика декомпозиции и построения параллельных алгоритмов ИАД из потокобезопасных функциональных блоков для выполнения в распределенной среде, которая позволяет не повторять наиболее трудоемкие шаги при оптимизации алго-

ритма. Все изменения алгоритма в данном направлении связаны или с реструктуризацией алгоритма без изменения функциональных блоков или с его перенастройкой.

5. Построена библиотека алгоритмов ИАД для выполнения в распределенной среде.

Публикации в журналах, входящих в перечень ВАК

1. Каршиев З.А. Обзор параллельных алгоритмов построения деревьев решений // Известия СПбГЭТУ «ЛЭТИ», № 9, Санкт-Петербург 2011. С. 43-48.

2. Куприянов М.С., Каршиев З.А. Формальная модель выполнения алгоритмов интеллектуального анализа // Известия СПбГЭТУ «ЛЭТИ», № 9, Санкт-Петербург

2012. С. 60-68.

3. Каршиев 3. А., Голубев И. А., Прохоренко К. А. Оценка ускорения и эффективности параллельного выполнения алгоритмов интеллектуального анализа данных // Известия СПбГЭТУ «ЛЭТИ», № 10, Санкт-Петербург2012. С. 46-52

4. Холод И.И., Каршиев З.А. Методика распараллеливания алгоритмов интеллектуального анализа данных // Известия СПбГЭТУ «ЛЭТИ», № 3, Санкт-Петербург

2013. С. 38-45.

Другие статьи и материалы конференций

5. Куприянов М.С., Каршиев З.А., Громов И.А., Серебрянский Д.А., Холод И.И., Павлухин И.С. Восстановление моделей бизнес процессов в информационных системах // Сборник докладов XIV Международной конференции по мягким вычислениям и измерениям, Санкт-Петербург, 23-25 июня, 2010 г., Том 1, С. 114-117.

6. Холод И.И., Каршиев З.А. Анализ распределенных данных: обзор методов объединение моделей // Сборник докладов XIV Международной конференции по мягким вычислениям и измерениям SCM'2011, Санкт-Петербург, 23-25 июня, 2011 г., Том 1, С. 163-166.

7. Холод И.И., Каршиев З.А., Школьный P.E. Виды распределения данных и возможности их интеллектуального анализа // Сборник докладов XIV Международной конференции по мягким вычислениям и измерениям SCM'2011, Санкт-Петербург, 23-25 июня, 2011 г., Том 1, С. 255-258.

8. Холод И.И., Каршиев З.А. Параллелизация алгоритма Naïve Bayes на основе блочной структуры. // Сборник докладов XV Международной конференции по мягким вычислениям и измерениям SCM'2012, Санкт-Петербург, 25-27 июня, 2012 г., Том 1,С. 182-185.

9. Куприянов М.С., Холод И.И, Каршиев З.А. и др. Интеллектуальный анализ распределенных данных на базе облачных вычислений (монография). СПб.: Изд-во СПбГЭТУ "ЛЭТИ", 2011. - 148 с.

10. Куприянов М.С., Холод И.И, Каршиев З.А. и др. Интеллектуальный анализ данных в распределенных системах (монография). СПб.: Изд-во СПбГЭТУ "ЛЭТИ", 2012.-110 с.

11. Каршиев З.А. Автоматическое построение графа структуры лексических единиц (слов). № 2012610985, Федеральная служба по интеллектуальной собственности. Зарегистрировано в Реестре программ для ЭВМ 23 января 2012 г.

12. Холод И.И., Каршиев З.А. Блоковая структура выполнения алгоритма классификации Naïve Bayes. № 2012660852, Федеральная служба по интеллектуальной собственности. Зарегистрировано в Реестре программ для ЭВМ 29 ноября 2012 г.

Подписано в печать 20.05.13. Формат 60*84 1/16. Бумага офсетная. Печать офсетная. Печ. л. 1,0. Тираж 100 экз. Заказ 45.

Отпечатано с готового.оригинал-макета в типографии Издательства СПбГЭТУ "ЛЭТИ"

Издательство СПбГЭТУ "ЛЭТИ" 197376, С.-Петербург, ул. Проф. Попова, 5

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В.И. Ульянова (Ленина)» (СПбГЭТУ)

На правах рукописи

0420135*5638

Каршиев Зайнидин Абдувалиевич

Средства создания параллельных алгоритмов интеллектуального анализа данных

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель доктор технических наук, профессор

Куприянов Михаил Степанович Санкт-Петербург - 2013

Оглавление

ВВЕДЕНИЕ......................................................................................................................5

ГЛАВА 1 АЛГОРИТМЫ ПАРАЛЛЕЛЬНОГО И РАСПРЕДЕЛЕННОГО ИНТЕЛЛЕКТУАЛЬНОГО АНАЛИЗА ДАННЫХ.......................................................9

1.1 Интеллектуальный анализ данных и решаемые ею задачи........................9

1.2 Существующие подходы к распараллеливанию алгоритмов

анализа данных........................................................................................................11

1.2.1 Методы распараллеливания алгоритмов....................................................11

1.2.2 Параллельный и распределенный интеллектуальный анализ данных ... 15

1.2.3 Существующие стратегии распараллеливания алгоритмов интеллектуального анализа данных.....................................................................18

1.2.4 Проект NIMBLE как обобщенный подход к параллельному выполнению алгоритмов интеллектуального анализа данных.........................20

1.3 Существующие параллельные алгоритмы интеллектуального анализа данных........................................................................................................23

1.3.1 Параллельные алгоритмы классификации.................................................23

1.3.2 Параллельные алгоритмы кластеризации..................................................32

1.3.3 Параллельные алгоритмы ассоциативных правил....................................40

1.4 Методы представления алгоритмов..............................................................49

1.5 Методика распараллеливания........................................................................52

1.6 Выводы.................................................................................................................54

ГЛАВА 2 ФОРМАЛЬНАЯ МОДЕЛЬ И БЛОЧНАЯ СТРУКТУРА АЛГОРИТМОВ ИНТЕЛЛЕКТУАЛЬНОГО АНАЛИЗА ДАННЫХ........................57

2.1. Особенности алгоритмов hi 1теллектуального анализа данных.............57

2.2 Формальная модель алгоритма интеллектуального анализа данных .... 60

2.3 Особенности параллельного выполнения алгоритмов интеллектуального анализа данных...................................................................67

2.3.1. Работа алгоритма интеллектуального анализа при распараллеливании по данным и по задачам........................................................................................67

2.3.2. Параллельная работа алгоритма интеллектуального анализа

с диспетчером и без диспетчера...........................................................................69

2.3.3 Взаимодействие в параллельных алгоритмах

интеллектуального анализа..................................................................................71

2.4 Расширение формальной модели параллельных алгоритмов

интеллектуального анализа..................................................................................77

2.5 Метод построения параллельных алгоритмов интеллектуального

анализа из потоконезависимых функциональных блоков.............................78

2.5.1 Основная идея метода..................................................................................78

2.5.2 Типы функциональных блоков...................................................................80

2.5.3. Описание метода..........................................................................................82

2.5.4 Типы параллельных структур алгоритмов интеллектуального анализа создаваемых методом............................................................................................87

2.6 Выводы.................................................................................................................90

ГЛАВА 3 ШАБЛОНЫ И МЕТОДИКА ПОСТРОЕНИЯ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ ИНТЕЛЛЕКТУАЛЬНОГО АНАЛИЗА ДАННЫХ.......................93

3.1 Реализация блочной структуры алгоритмов интеллектуального анализа данных........................................................................................................93

3.1.1 Реализация базовых блоков алгоритмов интеллектуального

анализа данных......................................................................................................93

3.1.2 Реализация блоков для параллельного выполнения

алгоритмов анализа...............................................................................................96

3.1.3 Работа параллельного блока при разных видах параллелизма алгоритмов интеллектуального анализа данных..............................................100

3.2 Адаптеры к средствам выполнения параллельных вычислений............107

3.2.1 Существующие концепции выполнения параллельных

и распределенных вычислений..........................................................................107

3.2.2 Интеграция алгоритмов интеллектуального анализа данных

со средствами выполнения распределенных вычислений..............................109

3.3 Методика распараллеливания алгоритмов интеллектуального

анализа данных......................................................................................................112

3.4 Выводы...............................................................................................................125

ГЛАВА 4 РАСПАРАЛЛЕЛИВАНИЕ АЛГОРИТМОВ КЛАССИФИКАЦИИ

И КЛАСТЕРИЗАЦИИ.................................................................................................127

4.1 Библиотека распределенного анализа данных..........................................127

4.1.1 Структура проекта......................................................................................127

4.1.2 Место стандартов Data mining в библиотеке распределенного анализа данных....................................................................................................133

4.2 Экспериментальная проверка полученных результатов.........................135

4.2.1 Результаты выполнения алгоритма k-means............................................135

4.2.2 Результаты выполнения алгоритма 1R.....................................................152

4.3 выводы...............................................................................................................167

ЗАКЛЮЧЕНИЕ............................................................................................................169

СПИСОК ЛИТЕРАТУРЫ...........................................................................................170

ПРИЛОЖЕНИЕ 1.........................................................................................................178

Введение

Актуальность работы

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

• производительность - анализ больших объемов (измеряемых терабайтами) требует больших вычислительных ресурсов и может выполняться за неприемлемое для аналитика время;

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

Обе проблемы могут решаться за счет параллельного и/или распределенного выполнения интеллектуального анализа данных (ИАД).

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

К сожалению, исключением не являются и алгоритмы ИАД. В настоящее время проводится достаточно большое количество исследований в этой области. Выделены отдельные направления в области ИАД (в зарубежной литературе данная область имеет название Data Mining): параллельный ИАД (Parallel Data Mining) и распределенный ИАД (Distributed Data Mining). Большинство усилий исследователей в области параллельных алгоритмов ИАД тратятся на распараллеливание отдельных алгоритмов анализа и их дальнейшую оптимизацию.

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

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

- анализ существующих подходов к созданию параллельных алгоритмов

ИАД;

- разработка формальной модели алгоритма ИАД;

- разработка метода создания параллельных алгоритмов ИАД на основе по-токобезопасных функциональных блоков;

- разработка методики построения параллельных алгоритмов ИАД для выполнения в распределенной среде;

- разработка программных шаблонов для реализации последовательных и параллельных алгоритмов ИАД из потокобезопасных функциональных блоков;

- проведение экспериментов по выполнению алгоритмов, построенных в соответствии с предложенной методикой.

Объектом исследования являются алгоритмы ИАД.

Предметом исследования являются методы построения параллельных алгоритмов ИАД.

Методы исследования. Методы теории множеств, методы построения параллельных алгоритмов, методы проектирования программного обеспечения.

Научная новизна работы заключается в следующем:

1. Предложена формальная модель алгоритма ИАД, отличающаяся представлением алгоритма в виде набора независимых операций, выполняющих изме-

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

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

3. Предложена методика распараллеливания алгоритмов ИАД, которая отличается от известных тем, что к последовательным алгоритмам анализа применяется предложенный метод создания параллельных алгоритмов ИАД с учетом характеристик распределенной среды.

Практическая значимость:

1. Для создания параллельных алгоритмов ИАД предложены программные шаблоны, построенные на основе формальной модели и отделяющие реализацию алгоритма от средств распределенного выполнения.

2. Разработана библиотека параллельных алгоритмов ИАД для выполнения в распределенной среде, включающая в себя предложенные шаблоны.

Положения, выносимые на защиту:

1. Формальная модель алгоритмов интеллектуального анализа данных.

2. Метод создания параллельных алгоритмов интеллектуального анализа данных из потокобезопасных функциональных блоков.

4. Методика распараллеливания алгоритмов интеллектуального анализа данных для выполнения в распределенной среде.

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на международных конференциях по мягким вычислениям и измерениям 8СМ'2010, 8СМ'2011 и 8СМ'2012, Санкт-Петербург, 2010-2012 г.г, конференциях профессорско-преподавательского состава СПбГЭТУ «ЛЭТИ», Санкт-Петербург, 2011-2013 г.г.

Внедрение результатов работы. Результаты работы были использованы при выполнении НИР и в учебном процессе СПбГЭТУ на кафедре вычислительной техники.

Достоверность результатов исследования. Достоверность результатов диссертационной работы подтверждается корректным применением математического аппарата и результатами экспериментов на гетерогенном кластере в ресурсном центре СПбГЭТУ.

Публикации. Основные теоретические и практические результаты диссертации опубликованы в 12 работах, среди которых 4 работы в ведущих рецензируемых изданиях, рекомендуемых в действующем перечне ВАК, 2 раздела в 2-х монографиях, 4 работы - в материалах международных научно-технических конференций, 2 свидетельства о регистрации программ для ЭВМ.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав с выводами по каждой из них, заключения, списка литературы, включающего 77 наименований. Основная часть работы изложена на 178 страницах машинописного текста. Работа содержит 55 рисунка, 8 таблиц и 1 приложение общим объемом 5 страниц.

ГЛАВА 1 АЛГОРИТМЫ ПАРАЛЛЕЛЬНОГО И РАСПРЕДЕЛЕННОГО ИНТЕЛЛЕКТУАЛЬНОГО АНАЛИЗА ДАННЫХ

1.1 Интеллектуальный анализ данных и решаемые ею задачи

Интеллектуальный анализ данных (ИАД1) - это процесс обнаружения в «сырых» данных ранее неизвестных нетривиальных практически полезных и доступных интерпретации знаний, необходимых для принятия решений в различных сферах человеческой деятельности [1]. ИАД лежит на пересечении нескольких наук, главные из которых - это системы баз данных, статистика и искусственный интеллект.

ИАД позволяет решить разные задачи, с которыми сталкивается аналитик. Из них основными являются [2]:

• классификация - определение класса объекта по его характеристикам (множество классов, к которым может быть отнесен объект, заранее известно);

• регрессия - определение по известным характеристикам объекта значения некоторого его параметра. В отличие от задачи классификации значением параметра является не конечное множество классов, а множество действительных чисел;

• поиск ассоциативных правил - нахождение частых зависимостей (ассоциаций) между объектами или событиями;

• кластеризация - поиск независимых групп (кластеров) и их характеристик во всем множестве анализируемых данных.

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

1 В англоязычной литературе для интеллектуального анализа данных используется термин Data Mining.

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

Предсказательные (predictive) модели строятся на основании набора данных с известными результатами, определенными экспертом (учителем). Поэтому в литературе построение такого вида моделей называют обучением с учителем (supervised learning), или машинным обучением (machine learning). Они используются для предсказания результатов на основании других наборов данных. При этом, естественно, требуется, чтобы модель работала максимально точно, была статистически значима и оправданна и т. д.

К таким моделям относятся модели, строящиеся в результате решения задач классификации и регрессии.

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

К описательному виду относятся модели, строящиеся в результате решения задач поиска ассоциативных правил и кластеризации.

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

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

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

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