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

Исследованиями в рассматриваемой области занимались различные ученые. В.В.Глазкова, В.А.Масляков, И.В.Машечкин, М.И.Петровский представили систему фильтрации интернет-трафика на основе методов data mining [1]. Использование kpi, технологий olap и data-mining при обработке данных показал А.Р.Вахитов [2]. В.В.Платонов,  П.О.Семёнов изучали применение методов data mining в задаче обнаружения сетевых атак [3].  Н.Е.Елов разработал методику анализа архивных данных автоматизированных систем управления и возможности ее практического применения на объектах топливно-энергетического комплекса [4]. Разработку семантического ядра сайта с динамическим контентом на основе ассоциативных правил представили Е.А.Арсирий,  О.А.Игнатенко,  А.А.Леус [5]. М.Л.Гарусев применил методы data mining в автоматизированном построении профиля пользователя защищаемой автоматизированной системы [6]. Р.И.Баженов, В.А.Векслер  реализовывали методы  интеллектуального анализа на платформе программной системы 1С: Предприятие [7, 8]. А.П.Корнилков, Д.К.Лопатин рассмотрели реализация методов анализа данных с использованием веб-технологий [9, 10]. Проблемы реализации алгоритмов поиска если-то правил осветили М.Г.Асеев, В.А.Дюк [11].  И.А.Минаков, С.И.Вольман представили систему нахождения бизнес-правил типа “if-then” в задачах транспортной логистики [12]. Использование интеллектуального анализа данных в электронных обучающих системах применили В.В.Белоус, А.С.Домников [13]. Зарубежные исследователи также уделяют внимание технологиям data mining в своих работах [14, 15, 16].

Изначально  поиск ассоциативных правил (association rule mining) применялся для нахождения типичных шаблонов покупок, совершаемых в супермаркетах, отсюда второе название данного метода – анализ потребительской корзины (market basket analysis) [17].

Одним из наиболее распространенных алгоритмов поиска ассоциативных правил является алгоритм Apriori. Разновидности алгоритма Apriori, которые являются его оптимизацией, предложены для сокращения количества сканирований базы данных, количества наборов-кандидатов или того и другого. Были предложены различные модификации алгоритма Apriori – это алгоритмы AprioriTID и AprioriHybrid. Также существует еще множество различных «авторских» модификаций алгоритмов Apriori – алгоритм DHP, PARTITION алгоритм, алгоритм DIC [18].

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

Приведем описание алгоритма [19].

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

Следующие шаги будут состоять из двух частей: генерации потенциально часто встречающихся наборов элементов (их называют кандидатами) и подсчета поддержки для кандидатов. Подробное описание на псевдокоде представлено в [19].

Покажем результаты реализации поставленной задачи.

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

Рассмотрим процесс построения ассоциативных правил средствами PHP.

Допустим, совершаются покупки в интернет–магазине. На рис.1 представлена упрощенная модель подобного магазина.

Рисунок 1 – Упрощенная форма (макет) для покупок в интернет-магазине

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

Рисунок 2 – База данных покупок в магазине

Далее программа анализирует все возможные связи: одноэлементные, двухэлементные и т.д. (рис. 3).

Рисунок 3 – Результат анализа алгоритмом  Apriori

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

1. Глазкова В.В., Масляков В.А., Машечкин И.В., Петровский М.И. Система фильтрации интернет-трафика на основе методов data mining // Программные продукты и системы. 2008. № 2. С. 22-25.
2. Вахитов А.Р. Использование kpi, технологий olap и data-mining при обработке данных // Известия Томского политехнического университета. 2009. Т. 314. № 5. С. 175-179.
3. Платонов В.В., Семёнов П.О. Применение методов data mining в задаче обнаружения сетевых атак // Проблемы информационной безопасности. Компьютерные системы. 2013. № 4. С. 40-44.
4. Елов Н.Е.  Методика анализа архивных данных автоматизированных систем управления и возможности ее практического применения на объектах топливно-энергетического комплекса // Автоматизация, телемеханизация и связь в нефтяной промышленности. 2010. № 1. С. 19-23.
5. Арсирий Е.А., Игнатенко О.А., Леус А.А. Разработка семантического ядра сайта с динамическим контентом на основе ассоциативных правил // Информатика и математические методы в моделировании. 2012. Т. 2. № 1. С. 77-86.
6. Гарусев М.Л. Методы data mining в автоматизированном построении профиля пользователя защищаемой автоматизированной системы // Научно-технический вестник информационных технологий, механики и оптики. 2006. № 25. С. 127-134.
7. Баженов Р. И., Векслер В. А. Анализ потребительских корзин в 1С: Предприятие на примере АВС-анализа // Информатизация и связь. 2013. №5. С. 117-123.
8. Баженов Р. И., Векслер В. А. Реализация XYZ-анализа в программном коде внутреннего языка программирования 1С: Предприятие 8.3 // Информатизация и связь. 2014. №1. С. 35-40.
9. Баженов Р.И., Корнилков А.П., Лопатин Д.К. Проектирование web-ориентированной информационной системы университета на основе клиент-серверных технологий // Актуальные проблемы гуманитарных и естественных наук. 2014. №4.
10. Баженов Р.И., Лопатин Д.К. О применении современных технологий в разработке интеллектуальных систем // Журнал научных публикаций аспирантов и докторантов. 2014. № 3 (93). С. 263-264.
11. Асеев М.Г., Дюк В.А. Поиск if-then правил в данных: проблемы и перспективы // Труды СПИИРАН. 2005. Т. 2. № 2. С. 76-85.
12. Минаков И.А., Вольман С.И. Система нахождения бизнес-правил типа “if-then” в задачах транспортной логистики // Информационные технологии. 2007. № 12. С. 35-42.
13. Белоус В.В., Домников А.С. Интеллектуальный анализ данных в электронных обучающих системах // Инженерный вестник. 2013. № 12. С. 6.
14. Xiao F., Fan C. Data mining in building automation system for improving building operational performance // Energy and Buildings. 2014. Vol. 75. P. 109-118.
15. Sawicki P., Żak J. The Application of Dominance-based Rough Sets Theory to Evaluation of Transportation Systems // Procedia – Social and Behavioral Sciences. 2014.  Vol. 111. P. 1142-1154.
16. 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.  Vol. 84. P. 140-151.
17. Баженов Р. И. Интеллектуальные информационные технологии. Биробиджан: ПГУ им. Шолом-Алейхема, 2011. 176 с.
18. Разновидности алгоритма Apriori. URL: http://www.intuit.ru/studies/courses/6/6/lecture/186?page=4
19. Apriori – масштабируемый алгоритм поиска ассоциативных правил. URL: http://www.basegroup.ru/library/analysis/association_rules/apriori/

Все статьи автора «Корнилков Алексей Петрович»