ОЦЕНКА ЭФФЕКТИВНОСТИ МЕТОДА ПОИСКА АССОЦИАТИВНЫХ ПРАВИЛ ДЛЯ ЗАДАЧ ОБРАБОТКИ БОЛЬШИХ ДАННЫХ

  • В.В. Бова Южный федеральный университет
  • Э.В. Кулиев Южный федеральный университет
  • С. Н. Щеглов Южный федеральный университет
Ключевые слова: Извлечение ассоциативных правил, неструктурированные данные, алгоритм, база ассоциативных правил, большие данные

Аннотация

Объемы современных баз данных имеют значительные объемы и содержат большие
массивы информации. Одним из популярных методов обнаружения знаний для задач обработки
и анализа больших данных стали алгоритмы поиска ассоциативных правил. В статье решается
задача построения баз ассоциативных правил для анализа представленной большими массива-
ми неструктурированных данных на основе поиска в них различных закономерностей с учетом
значимости их признаков. Предложен метод синтеза баз ассоциативных правил, в котором
выполняется построение транзакционной базы данных на основе вычисления пороговых значе-
ний поддержки и применением критериев оценивания косвенных ассоциаций, что позволяет
извлекать как частые, так и неявные наборы ассоциативных правил. С целью повышения вы-
числительной эффективности извлечения ассоциативных правил, применяется генетический
алгоритм оптимизации входных параметров признакового пространства поиска. Метод позво-
ляет улучшить время извлечения правил, сократить число сгенерированных обобщенных правил,
избежать затратной процедуры предобработки синтезированной базы правил. Разработан
программно-алгоритмический модуль, с помощью которого проведены экспериментальные
исследования метода синтеза ассоциативных правил на основе фильтрации входных парамет-
ров модели поиска для решения задач обработки неструктурированных данных. Проведенные
серии экспериментов на тестовых транзакционных базах данных позволили уточнить теоре-
тические оценки временной сложности метода, в котором для вычисления взвешенной под-
держки наборов правил с учетом оценки априорной информативности признаков, входящих в
данный набор применяется генетический алгоритм. Временная сложность разработанного
метода составляет  О(I2). Сравнительной анализ проводился на тестовых данных корпуса
Retail Data с алгоритмами Apriori и Frequent Pattern-Growth. Результаты исследований под-
твердили эффективность метода поиска на больших наборах транзакций, позволяющего более
чем на 40 % уменьшить мощность неизбыточного множества извлеченных ассоциативных
правил по сравнению с известными алгоритмами и показали перспективность его применения
для задачи обнаружения знаний при обработке данных большого объема.

Литература

1. Gaziev G.Z., Kurdyukova G.N., Kurdyukov V.V. Klasterizatsiya Big Data dlya ikh analiza i
obrabotki [Clusterization of Big Data for their analysis and processing], Sb. konferentsii
«Napravleniya i mekhanizmy razvitiya nauki novogo vremeni: ot teorii do vnedreniya
rezul'tatov» [Collection of the conference "Directions and mechanisms of modern science development:
from theory to implementation of results"], 2017, pp. 150-162.
2. Bova V.V., Shcheglov S.N., Leshchanov D.V. Modifitsirovannyy algoritm EM-klasterizatsii
dlya zadach integrirovannoy obrabotki bol'shikh dannykh [Modified EM clustering algorithm
for integrated big data processing], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU.
Engineering Sciences], 2018, No. 4 (165), pp. 197-211.
3. Bova V.V., Kureichik V.V., Scheglov S.N., Kureichik L.V. Multi-level ontological model of big
data processing, Advances in Intelligent Systems and Computing, 2019, Vol. 874, pp. 171-181.
4. Wu X., Zhu X., Wu G., Ding W. Data mining with big data, IEEE Transaction on Knowledge
and Data Engineering, 2014, Vol. 26, pp. 97-107.
5. Kravchenko Y.A., Kuliev E.V., Kursitys I.O. Information’s semantic search, classification,
structuring and integration objectives in the knowledge management context problems, 10th
IEEE International Conference on «Application of Information and Communication Technologies,
AICT 2016, pp. 136-141.
6. Wedyan S. Review and Comparison of Associative Classification Data Mining Approaches,
International Journal of Computer, Information, Systems and Control Engineering, 2014,
Vol. 8, pp. 34-45.
7. Zayko T.A., Oleynik A.A., Subbotin S.A. Izvlechenie chislennykh assotsiativnykh pravil s
uchetom znachimosti priznakov [Extracting numeric Association rules taking into account the
importance of the signs], Vostochno-Evropeyskiy zhurnal peredovykh tekhnologiy [East European
journal of advanced technologies], 2013, Vol. 5, No. 4 (65), pp. 28-34.
8. Ibrahim S., Chandran K.R. Compact Weighted Class Association Rule Mining using Information
Gain, International Journal of Data Mining and Knowledge Management Process,
2011, Vol. 1, pp. 1-13.
9. Muyeba M., Khan M. S., Coenen F. Fuzzy weighted association rule mining with weighted
support and confidence framework, New Frontiers in Applied Data Mining Lecture Notes in
Computer Science, 2009, Vol. 5433, pp. 312-320.
10. Zayko T.A., Oleynik A.A., Subbotin S.A. Assotsiativnye pravila v intellektual'nom analize
dannykh [Associative rules in data mining], Vestnik Natsional'nogo tekhnicheskogo
universiteta Khar'kovskiy politekhnicheskiy institut. Seriya: Informatika i modelirovanie [Bulletin
of the national technical University Kharkiv Polytechnic Institute. Series: computer Science
and modeling], 2013, No. 39 (1012), pp. 82-96.
11. Kravchenko Yu.A. Model' fil'tra znaniy dlya zadach semanticheskoy identifikatsii [Knowledge
filter model for semantic identification tasks], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya
SFedU. Engineering Sciences], 2018, No. 4 (165), pp. 197-211.
12. Subbotin S.A., Oleynik An.A., Gofman E.A. Intellektual'nye informatsionnye tekhnologii
proektirovaniya avtomatizirovannykh sistem diagnostirovaniya i raspoznavaniya obrazov:
monografiya [Intelligent information technologies of automated diagnosis and pattern recognition:
monograph], ed. by S.A. Subbotina. Khar'kov: OOO «Kompaniya Smit», 2012, 317 p.
13. Bova V.V., Shcheglov S.N., Leshchanov D.V. Primenenie metodov geneticheskogo poiska dlya
zadach obrabotki assotsiativnykh pravil [Application of genetic search methods for processing
associative rules], XXI Mezhdunarodnaya konferentsiya po myagkim vychisleniyam i
izmereniyam (SCM-2018) [XXI international conference on soft computing and measurement
(SCM-2018)]. Saint Petersburg: SPbGETU «LETI», 2018, Vol. 1, pp. 761-769.
14. Shcheglov S.N. Modifitsirovannyy algoritm obrabotki i analiza nestrukturirovannoy informatsii
na osnove poiska assotsiativnykh pravil [Modified algorithm for processing and analysis of
unstructured information based on search for associative rules], Tr. Kongressa po
intellektual'nym sistemam i informatsionnym tekhnologiyam – «IS&IT’18» [Proceedings of the
Congress on intelligent systems and information technologies – "IS&IT'18"]. Taganrog: Izd-vo
YuFU, 2018, Vol. 2, pp. 183-191.
15. Bova V.V., Scheglov S.N., Lemanov D.V. Modified Approach to Problems of Associative Rules
Processing based on Genetic Search, 2019 International Russian Automation Conference
(RusAutoCon). 10.1109/RUSAUTOCON, 2019, No. 8867675.
16. Lezhebokov A.A., Kuliev E.V. Tekhnologii vizualizatsii dlya prikladnykh zadach
intellektual'nogo analiza dannykh [Visualization technologies for data mining applications],
Izvestiya Kabardino-Balkarskogo nauchnogo tsentra RAN [Izvestiya Kabardino-Balkar scientific
center of the Russian Academy of Sciences], 2019, No. 4 (90), pp. 14-23.
17. Guo Z., Chi D., Wu J., Zhang W. A new wind speed forecasting strategy based on the chaotic
time series modelling technique and the Apriori algorithm, Energy Conversion and Management,
2014, No. 84, pp. 140-151.
18. Kumar B.S. Rukmani K.V. Implementation of web usage mining using Apriori and FP Growth
algorithms, International Journal of Advanced Networking and Applications, 2010, Vol. 400,
pp. 400-404.
19. Pal'mov S.V., Franuzova E.N. Algoritm poiska assotsiativnykh pravil FP-GROWTH [Search
algorithm for associative rules FP-GROWTH], Natsional'naya assotsiatsiya uchenykh [National
Association of scientists]. Moscow. Izd-vo: OOO «Evraziyskoe Nauchnoe
Sodruzhestvo», 2016, No. 10-1 (26), pp. 27-32.
20. Qureshi Z. Bansal S. Improving Apriori Algorithm to get better performance with Cloud
Computing, International Journal of Software and Hardware Research in Engineerin, 2014,
Vol. 2, pp. 33-37.
21. Singh J., Ram H. Improving Efficiency of Apriori Algorithm Using, International Journal of
Scientific and Research Publications, 2013, Vol. 3, pp. 1-4.
22. Yahya O., Hegazy O, Ezat E. An efficient implementation of Apriori algorithm based on Hadoop-
Mapreduce model, International Journal of Reviews in Computing, 2012, Vol. 12, pp. 59-67.
23. Frequent Itemset Mining Implementations Repository. Retail. Available at:
http://fimi.ua.ac.be/data/retail.dat/.
24. Zhao Y., Zhang C., Cao L. Post-mining of association rules: techniques for effective
knowledge extraction. New York: Information Science Reference. 2009, 372 p.
25. Gkoulalas-Divanis A., Verykios V.S. Association Rule Hiding for Data Mining. New York:
Springer-Verlag. 2010, 150 p.
Опубликован
2020-07-20
Выпуск
Раздел
РАЗДЕЛ I. ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ