PARALLEL METHODS FOR DERIVING ASSOCIATIVE RULES WITH THE USAGE IN- DATABASE AND IN-MEMORY TECHNOLOGIES

Abstract

В статье предложен подход к разработке параллельного программного обеспечения для решения задач data mining. Рассмотрена задача подготовки данных для вывода ассоциативных правил. Большинство современных алгоритмов для этой задачи имеют экспоненциальную сложность. Дополнительную сложность создает необходимость обработки больших данных. Сам вывод ассоциативных правил на основе полученных данных реализуется полиномиальным алгоритмом на малом объеме полученных данных. Доказано, что использование теоретико-множественной (файловой) и многомерно-матричной моделей данных позволяет разработать для ее решения полиномиальные алгоритмы. Предложены методы реализации этих алгоритмов в технологиях in-database и in-memory. В технологии in-database приведены схема базы данных и совокупность запросов к базе данных, с помощью которых формируются данные, необходимые для этапа вывода ассоциативных правил. Предложен метод ускорения обработки за счет использования принципа симметричного горизонтального распределения таблиц и параллельного полиномиального алгоритма реализации операции Join. В технологии in-memory предложен метод решения задачи подготовки данных на основе алгебры многомерных матриц. Показано, что эта задача может быть решена последовательностью (0, 1)- и (1, 0)-свернутых произведений многомерных матриц. Эти операции могут быть распараллелены аналогично распараллеливанию операции умножения обычных матриц. Приведены результаты вычислительного эксперимента, в котором предложенные методы сравнивались с алгоритмом Apriory. Результаты эксперимента подтвердили эффективность предложенных методов.

-

the symmetric horizontal distribution of tables and the parallel polynomial algorithm for implementing the Join operation is proposed. In-memory technology offers a method for solving the problem of data preparation, which is based on the algebra of multidimensional matrices. It is shown that this problem can be solved by the sequence of (0, 1)- and (1, 0)-converted products of multidimensional matrices. These operations can be parallelized in the same way as the parallelized of the ordinary matrices multiplication. The results of a computational experiment in which the proposed methods were compared with the algorithm Apriory are presented. The results of the experiment confirmed the effectiveness of the proposed methods.

Associative rules, parallel programming, big data. случаях и нкаонкретных предприятиях эти задачи решались эффективно, разрабатываются индивидуальные аналитические информационные системы. В этом случае пр-роагзрраамбмоитчстик имеет возможность добиваться высокой эффективности за счет построения -аппрпоагрраатмнмогноо комплекса, ориентированного на конкретный класс задач. Далее рассматриваются методы достиже этой цели, основанные на теор-метниокжоественной (файловой) и многом-емранторичной моделях данных. Обе эти модели изоморфны реляционной модели данных.

Известны арзличные варианты реализации алгориAтмprаiori средствами языкаSQL [ 9, 10 ]. В дальнейшем рассматривается реализация, основанная на построении на каждой итерац промежуточной таблицы, которая используется на следующей итерации.

База данных для решенияачизадвывода ассоциативных правил, как правило содержит следующий набор таблиц:

R0(I, P1) – исходные данные, каждая строка содержит идентификатор объекта и одно из его сво CopyR0(I, P1) – копия таблицыR0, она не обязательна и может использовасткьосярендиляя пуроцесса обработки данных;

R1(I, P1, P2), …, Rk-1(I, P1, …, Pk) – таблицы, получаемые на итерациях и содержащие данные для выво ассоциативных правил на очередной итерации и используемые на следующей итерации как ис данные.

Запрос, исполнямеый нlа-той итерации имеет, следующий общий вид: Ql = INSERT INTO Rl (I, P1, …, Pl+1) SELECT Rl1.I, R l1.P1, …, R l1.P l, R0.P1 AS Pl+1 FROM R l1 INNER JOIN R0 [на первой итерации вмRесlт1оиспользуется CopyR0 ] ON R l1.I = R0.I AND (R l1.I, R l1.P1, …, R l1.P l, R0.P). (Ri l1.I, R l1.P1, …, R l1.Pl, R0.P) – предикат, запрещающий дублирование комбинаций свойств. Таким образом, если для построения ассоциативных правил необходимо знать количества объектов, содержащих комбинации свойсоттв одного доk  s, выполняются запросы Q1, …, Qk-1. Из таблRи0ц, …, Rk-1, исходной и полученных в результате запросов, на втором этапе выво ассоциативные правила.

Ускорение подготовки данных возможно за счет того, что современные СУБД оисмтьеют возмо параллельного выполнения запросов, в том числе, и запросов, содержащиJOхIN.опеФрайцлиоювая модель данных обеспечивает возможность применения симметричного горизонтального распределения [ 11 ] таблицыR0 по ключуIмежду несколькими базами даннысхп,олрожаенными на физически разных серверах. Это усилит эффект ускорения за счет существенного, практически кратного числу се уменьшения объемов фрагментов таблRи0,ц…, Rk-1. Следует отметить, что для решаемой задачи целесообразно использовать одноопхродный алгоритм операцJиOиIN, который основан на вычислении декартовых произведений классов эквивалентности фрагментов тRа0блииц Rl1, которые обрабатываются наl-той итерации. Каждый такой класс эквивалентности содержит строки таблиц одинаковыми знчаениями идентификатора объекта. Для реализации алгоритма требуется упорядоченность таблицR0 и Rl1 по ключу идентификатор объекта. Это незначительно повлияет на е производительность, так как таблRи0 цуапорядочивается один раз при ее создании, аRl1тваблэитцома случае создается упорядоченной. Для выполнения алгоритма в оперативной памяти выделяются буферные области, в которые будут считываться из базы данных классы эквивалентности фраг таблиц R0 и Rl1. Размер буферных областей определкяоелтисчяеством доступных процессоров (ядер) и объемом доступной оперативной памяти. Считывание классов эквивалентности осуществляется дву параллельными потоками, которые взаимодействуют друг с другом для того, чтобы заполнить бу области соответствующими друг другу классами эквивалентности. После заполнения буферных област запускаются параллельные потоки, вычисляющие декартовы произведени-япоток(иД)П соответствующих пар классов эквивалентности, свертку и вывод результатов в базу данных в ф таблицы Rl, которая будет использоваться на следующей итерации. На практике, количество по может оказаться значительно меньше пар классов эквивалентности, обрабатываемых этими потокам этом случае распределение пар классов эквивалентности межамдуи пмоотжонко сдел,атиьспользуя алгоритм бустрофедона [ 12 ]. Програ м-ампнпоаратный комплекс для реализации этого алгоритма приведен на рисунке 1. RЗ0дi,еRсьli – фрагменты таблицR0 и Rl1 R0i j , Rlij , ( j  1, ..., s) – совокупности соответствующих классов эквивалентностей в буферных областях.

Вычислительная сложность обработки буферных областей определяется временем считывания классов эквивалентности из базы данных и сложностью вычисления декартовых произведений кл эквивалентности. В общем случае, когда число пар классов эквивалоленьштнеостичислба s ns обрабатывающих их процессоров (ядер), сложность определяется знMачaеxние(мR0i jk  Rlijk ). j1 k1 количество классов эквивалентности, обрабатываеjм-тыыхм потоком.

Рис. 1. Программно-аппаратный комплекс для вывода ассоциативных правил Кроме того, дополнительного эффекта можно достигнуть за счет применения конвейерного м для цепочки операциJйOIN, которые реализуют вычисления на итерациях [ 13 ]. Это потребу дополнительных усилийпрограммиста-разработчика, но обеспечит существенное ускорение этапа подготовки данных, особенно в сочетании с симметричным горизонтальным распределенRи0е.м таблиц Применение многомерн-оматричной модели позволяет существенно улучшить временные характеристики этапа подготовки данных. Если номера объектов и свойств использовать в ка индексов, то исходные данные в этой– ммаотдреилциа M 0  mi0j , i  1,..., n, j  1,..., s. При условии, что mi0j  1, если объектIi обладает свойствомPj и 0 в противном случае, мMа0трвизцаиамно однозначно соответствует таблицRе0. ОперацииJOIN в алгебре многомерных матриц соответствует опер,ац)-ия ( свернутого произведения, которая позволяет умножать матрицы с произвольным числом измере получая многомерные матрицы. В рассматриваемом случаеi, иснодоетквтсествующий идентификатору объекта, выполняет две функции: • при вычислении матрицы для следующей итерации он используется как скоттов индек совмещения умножаемых элементов матриц, то есть реали0з)у-ествсеярну(т1о,е произведение; • при вычислении матрицдлыя вывода ассоциативных правил он используется как кэлиев инде для совмещения умножаемых элементов матриц и суммирования произведений, то е реализуется (01,)-свернутое произведение.

Алгоритм, основанный на умножении многомерных матриц, такалгжоериткма,к оиснованный на операции JOIN, состоит из последовательности итераций.

На первой итерации вычисляется трехмерная мMат1ри1ц,0а(M 0  М 0 )  mi1jj , i  1,..., n, j  1,..., s, где mi1jj  mi0j  mi0j и двумерная матриTц1а0,1 (M 0  М 0 )  t1jj , j  1,..., s, где t1jj  mi0j  mi0j . Матрица n i1 T1 также может быть получена из матMр1иоцпыерацией свертки, однако, обе матроижцныо мвычислять одновременно.

На l-той итерации вычисляются l+1-мерная матрица M l 1,0 (M l1  М 0 )   mil j... j , mil j... j  mil j.1.. j  mi0j , которая будет использована на следующей итерации, и  l  l l1 матрица Tl 0,1 (M l1  М 0 )   tlj..l. j , tlj..l. j  i1 mil jl.1..1j  mi0j , которая будет использована для вывода n ассоциативных правил. Так, жкеак и при использовании реляционной молдяелип, олудчения всех возможных комбинаций свойств отk н1еобдхоодимо выполнитkь итераций. На последней итерации нет необходимости в построении матрMиkц+ы1.

При последовательной реализации алгоритма методом умножения многомерных вычислительная слонжость определяется значениеkм: (n  n2  ...  nk ) , n – количество объектовk, – матриц количество свойств.

Таким образом, можно сложность.

утверждать, что оба рассмотренных алгоритма имеют

полиномиаль Для ускорения решения задачи вывода ассоциативных правил можно ипсапроалльлзеолвьантьый алгоритм умножения многомерных матриц [ 14 ]. Кро м,е симтмоегторичное горизонтальное распределение в данном случае применимо для реализации рассматриваемой задачи - в многом матричной модели данных.

Для оценки рассмотренных в статье мбеытлодопвроведен вычислительный эксперимент. Анализу были подвергнуты три алгоритма вывода ассоциативных правил: • алгоритм Apriory, взятый из пакAеpтrаior"i 1.1.1", который находится в центральном репозитарии модулей языка Pyth–oPnython Package Index [ 15 ]; • алгоритм, реализованный средствами СMУiБcДrosoft Sql Server 2016 (на основе операJOциINи); • алгоритм на основе умножения многомерных матриц.

Программное обеспечение разрабатывалосьMicrвosoft Visual Studio 2017. Для алгоритма 1 исходные данные преобразовлаись из текстового файла в списковую структуру в оперативной пам необходимую для работы алгоритма. Для алгоритма 2 исходные данные располагалRи0сьа в табли подготовка к работе заключалась в удалении всех строк из промежуточных и резуилць.тирующих Для алгоритма 3 исходные данные преобразовывались изR0 втабмлаитцрыицMу0 в оперативной памяти. Программа подготовки данных и вызова алгоритма 1 написанPаytoнnа. Аялзыгокреитм 2 реализован хранимыми процедурами, написанными на Tяrзaыnкsеact Sql и вызываемыми из программы, написанной на языкCе#. Алгоритм 3 реализован как процедура динамической библиотекCи++,наподязгыоткоевка данных для которой и ее вызов осуществляются программCо#й. на язык

Эксперимент производился на исходном наборе дсоадненрыжха,щем миллион объектов, каждому из которых соответствовал набор от одного до пяти свойстRв0. соТдаебрлжиацлаа последовательно от одного до пяти миллионов строк. Алгоритмы 1 и 3 были реализованinы-meвmoтryех,нотлоогиеисть использовали исходныеданные, загруженные в оперативную память, промежуточные данные и результаты вычислений сохранялись там же. Алгоритм 2 был реализован iвn-daтtеaхbнasоeл,огии причем использовался стандартный алгоритм опеJрOаIцNи,и реализованный в СMУiБcДrosoft Sql Server 2016.

Для алгоритмов 2 и 3 было выполнено симметричное горизонтальное распределение данных четырьмя серверами для алгоритма 2 и таким же количеством потоков для алгоритма 3. С уче распределения и сбора результатов были получены ыре,зуплрьитавтеденные в таблице 1.

Таблица 1. Временные характеристики алгоритмов подготовки данных Таблица R0 Алгоритм (миллионы строк) Apriory Алгоритм на осноJOвеIN

Многомерно-матричный алгоритм последовательно параллельно последовательно параллельно 1 2 3 4 5 29,87 56,12 84,79 130,54 209,56 23,61 40,69 54,96 74,95 105,19 7,44 12,82 17,31 23,61 33,14 5,05 11,27 18,35 23,42 33,49 1,09 2,43 3,96 5,05 7,22 На рисунке 2 приведены графики, отражающие соотношения времени подготовки данных для ассоциативных правил алгоритмоAмpriory, реализованном в технолоiгnи-mиemory, и алгоритмом, реализованном в технологiиnи-database, последовательно и параллельно.

Рис. 2. Сравнение алгоритма Apriory и алгоритма на основе операции JOIN Рис. 3. Сравнение алгоритма Apriory и алгоритма на основе умножения многомерных матриц На рисунке 3 приведены графики, отражающие соотношения времени подготовки данных для ассоциативных правил алгоритмоAмpriory, реализованном в технолоiгnи-mиemory, и алгоритмом основанном на умножении многомерных матриц, также реализованном в iтnе-mхнeоmлoоrгyи,и последовательно и параллельно.

Из сказанного можно сделать следующие выводы: В том случае, когда объемы данных настолько велики, что их невозможно разместить в оп памяти целесообразно использовать алгоритмы подобные алгоритму 2. Время решения задачи в ассоциативных правил таким способом сопоставимо с временем широко используемых в настоящее алгоритмов типа алгоритмAаpriory, а при использовании симметричгнооргиозонтального распределения данных существенно меньше.

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

Предложенные в статье методы могут быть эффективно использованы при разработке програм обеспечения аналитических информационных систем. памяти алгоритмы, основанные на умнож и гораздо проще распараллеливаются, Об авторах: Захаров Виктор Николаевич, доктор технических унк,а доцент,ученый секретар,ьФедеральный исследовательский центр "Информатика и управление" vzРaАkhНa, [e-mail] Мунерман Виктор Иосифович, кандидат технических н,адуокцент кафедры информат и,кСимоленский государственный университет, [e-mail] Самойлова Татьяна Аркадьевна, кандидат технических н,аукдоцент кафедры Смоленский государственный университет, [e-mail] информат и,ки

References

1. Самойлова Т .А. Разработка аналитических информационных систем средсвтрвеаммеиннысхо баз данных. Системы компьютерной математики и их приложения: материалы XVIII Международной научной -кСомнфолеернеснкц:ииИ, з-дво СмолГУ , 2017 , Вып. - с1.8 . 11 - 1114 .

2. Houtsma M. , Swami A . Set-oriented mining of association rules . Research Report RJ 9567 , IBM Almaden Research Center, San Jose, California, October 1993 .

3. Salim M , Yao X . Evolving SQL Queries for Data Mining. - Lecture Notes in Computer Science , 2002 , 2412 . - p. 62 - 67 .

4. R. Agrawal , T. Imielinski , A. Swami . 1993 . Mining Associations between Sets of Items in Massive Databases . In Proc. of the 1993 ACMSIGMOD Int'l Conf. on Management of -2D1a6t.a, 207

5. Agrawal R. , Srikant R . "Fast Discovery of Association Rules" . - Proc. of the 20th International Conference on VLDB, Santiago , Chile, September 1994 .

6. Srikant R. , Agrawal R . "Mining Generalized Association Rules" . - Proc. of the 21th International Conference on VLDB, Zurich, Switzerland , 1995 .

7. R. Srikant , R. Agrawal . "Mining quantitative association rules in large relational tables" . In Proceedings of the ACM SIGMOD Conference on Management of Data , Montreal, Canada, June 1996 .

8. Pol U . Design and Development of Apriori Algorithm for Sequential to concurrent mining using MPI / U . Pol // International journal of Computers & Technology. - 2013 . - Т . 10 . - № 7 -. C. 1785 - 1790 .

10. Sidló , C.I. , Lukács , A. Shapi-nbgaseSdQfLrequent pattern mining algorithms (Revised Selected and Invited Papers) . - Knowledge Discovery in Inductive Databases: 4th International Workshop , KDID 2005, Springer, Heidelberg. - p. 188 - 201 .

15. https://pypi.python.org/pypi.

1. Samojlova T.A. Razrabotka analiticheskih informacionnyh sistem sredstvami sovremennyh baz dannyh. Sistemy komp'juternoj matematiki i ih prilozhenija: materialy XVIII Mezhdunarodnoj nauchnoj konferencii, - Smolensk: Izd-vo SmolGU , 2017 , Vyp. 18 . - s. 111 - 114 .

2. Houtsma M. , Swami A . Set-oriented mining of association rules . Research Report RJ 9567 , IBM Almaden Research Center, San Jose, California, October 1993 .

3. Salim M , Yao X . Evolving SQL Queries for Data Mining. - Lecture Notes in Computer Science , 2002 , 2412 . - p. 62 - 67 .

4. R. Agrawal , T. Imielinski , A. Swami . 1993 . Mining Associations between Sets of Items in Massive Databases . In Proc. of the 1993 ACMSIGMOD Int'l Conf. on Management of -2D1a6t.a, 207

5. Agrawal R. , Srikant R . "Fast Discovery of Association Rules" . - Proc. of the 20th International Conference on VLDB, Santiago , Chile, September 1994 .

6. Srikant R. , Agrawal R . "Mining Generalized Association Rules" . - Proc. of the 21th International Conference on VLDB, Zurich, Switzerland , 1995 .

7. R. Srikant , R. Agrawal . "Mining quantitative association rules in large relational tables" . In Proceedings of the ACM SIGMOD Conference on Management of Data , Montreal, Canada, June 1996 .

8. Pol U . Design and Development of Apriori Algorithm for Sequential to concurrent mining using MPI / U . Pol // International journal of Computers & Technology. - 2013 . - Т . 10 . - № 7 -. C. 1785 - 1790 .

9. Rechkalov T.V . Podhod k integracii intellektual'nogo analiza dannyh v reljacionnuju SUBD na osnove generacii tekstov hranimyh procedur. - Vestnik Juzhno-Ural'skogo gosudarstvennogo universiteta . Serija «Vychislitel'naja timkatemiainformatika» , tom 2 , # 1, izdatel'stvo: Juzhno-Ural'skij gosudarstvennyj universitet (nacional'nyj issledovatel'skij universitet) (Cheljabinsk ), 2013 . - s. 114 - 121 .Sidló, C.I. , Lukács , A. Shapi-nbgaseSdQfLrequent pattern mining algorithms (Revised Selected and Invited Papers) . - Knowledge Discovery in Inductive Databases: 4th International Workshop , KDID 2005, Springer, Heidelberg. - p. 188 - 201 .

10. Sidló , C.I. , Lukács , A. Shapi-nbgaseSdQfLrequent pattern mining algorithms (Revised Selected and Invited Papers) . - Knowledge Discovery in Inductive Databases: 4th International Workshop , KDID 2005, Springer, Heidelberg. - p. 188 - 201 .

11. Munerman V.I. Modeli obrabotki bol'shih ob"emov dannyh v sistemah massovogo parallelizma . - M.: Sistemy vysokoj dostupnosti, 2013 , T. 9 , #1. - S. 35 - 43 .

12. Makarov D.I. , Munerman V.I. Parallel'naja realizacii operacii soedinenija dlja massovoj obrabotki dannyh Sistemy vysokoj dostupnosti . 2012 . T. 8 . # 3. S. 26 - 28 .

13. Munerman V.I. , Munerman D .V. Algebraicheskij podhod k postroeniju programmno-apparatnyh kompleksov dlja povyshenija jeffektivnosti massovoj obrabotki dannyh. Sovremennye informacionnye tehnologii i IT-obrazovanie . 2015 . T. 2 . # 11. - S. 391 - 396 .

14. Zakharov V.N. , Munerman V.I. Parallel'nyj algoritm umnozhenija mnogomernyh matric Sovremennye informacionnye tehnologii i IT-obrazovanie . 2015 . T. 2 . # 11. S. 384 - 39 .

15. https://pypi.python.org/pypi.