УДК 004.42

РАЗРАБОТКА ПРОГРАММНОЙ СИСТЕМЫ ПОИСКА АССОЦИАТИВНЫХ ПРАВИЛ НА ОСНОВЕ АЛГОРИТМА APRIORI

Сизых Анна Фаритовна1, Баженов Руслан Иванович2
1Приамурский государственный университет имени Шолом-Алейхема, студент
2Приамурский государственный университет имени Шолом-Алейхема, кандидат педагогических наук, доцент, заведующий кафедрой информатики и вычислительной техники

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

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


DEVELOPMENT OF A SOFTWARE SYSTEM SEARCH ASSOCIATION RULES BASED ON APRIORI ALGORITHM

Sizykh Anna Faritovna1, Bazhenov Ruslan Ivanovich2
1Sholom-Aleichem Priamursky State University, student
2Sholom-Aleichem Priamursky State University, candidate of pedagogical sciences, associate professor, Head of the Department of Computer Science

Abstract
The article presents the development of a software system that implements the search for Association rules. Shows the apriori algorithm and its implementation in theDelphienvironment. The study used real sales data. The developed program can be used for teaching courses in «Intelligent information systems», «Data mining».

Keywords: apriori algorithm, association rules, data mining


Рубрика: 05.00.00 ТЕХНИЧЕСКИЕ НАУКИ

Библиографическая ссылка на статью:
Сизых А.Ф., Баженов Р.И. Разработка программной системы поиска ассоциативных правил на основе алгоритма apriori // Современные научные исследования и инновации. 2014. № 10. Ч. 1 [Электронный ресурс]. URL: http://web.snauka.ru/issues/2014/10/38733 (дата обращения: 28.09.2017).

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

Проблемами поиска ассоциативных правил занимались различные ученые. А.Шахиди рассмотрел общие вопросы поиска ассоциативных правил [1]. М.Г.Асеев, В.А. Дюк [2] показали проблемы поиска if-then правил в данных. Систему нахождения бизнес-правил типа “if-then” в задачах транспортной логистики разработали И.А.Минаков, С.И.Вольман [3]. А.П.Корнилков, Т.В.Хабибулина показали реализацию поиска ассоциативных правил средствами языка программирования php [4]. Интерактивный анализ ассоциативных правил в базах данных изучался A.В.Бондаренко, А.С.Гудковым [5]. Е.В.Галкина исследовала ассоциативные правила в бизнес-анализе и контроле [6]. М.В.Терешонок применил поиск ассоциативных правил для анализа загрузки сетей сотовой связи [7]. Методику поиска ассоциативных правил при обработке данных в распределенных информационных системах показала Т.Ю.Горохова [8]. А.Ю.Краковецкий применял метод поиска ассоциативных правил на основе сильных наборов данных и fp-дерева [9]. А.Н.Шабельников, В.А.Шабельников исследовали поиск аномалий в технических базах данных временных рядов [10]. В.М.Гриняк и др. описали информационную технологию планирования сезонных продаж [11]. Р.И.Баженов, В.А.Векслер разработали конфигурацию для системы 1С: Предприятие по интеллектуальному анализу с поддержкой поиска ассоциативных правил [12-16]. Зарубежные ученые описывали применения метода в различных областях [17, 18]. 

Для реализации поиска ассоциативных правил был выбран достаточно простой алгоритм Apriori [1]. Опишем его.

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

Пусть I = {i1, i2, i3, …in} – множество (набор) товаров или элементов. Пусть D – множество транзакций, где каждая транзакция T представляет собой набор элементов из I, T  I. Каждая транзакция является бинарным вектором, где t[k]=1, если ik элемент присутствует в транзакции, иначе t[k]=0. Транзакция T содержит X, некоторый набор элементов из I, если X T. Будем называть ассоциативным правилом импликацию X Y, где X I, Y I и X Y =. Правило X  Y имеет поддержку s (support), если s% транзакций из D, содержат X Y, supp(X Y) = supp (X Y). Достоверность правила показывает какова вероятность того, что из X следует Y. Правило X Y справедливо с достоверностью (confidence) c, если c% транзакций из D, содержащих X, также содержат Y, conf(X Y) = supp(X  Y)/supp(X ) [1].

Была разработана программа, реализующая алгоритм Apriori на Delphi. Покажем основную процедуру.

function TForm1.gen(cand : TList) : TList;
var
  i, j, k : Integer;
  set_len : Integer; { Длина общей части наборов при объединении}
  tSet, tSet1, tSet_new : PProdSet;
  new_cand : TList;
  equal : Boolean;
begin
  { Новый список наборов}
  new_cand := TList.Create;
  if cand = nil then
  begin
    { Одноэлементные наборы}
    for i := 0 to tovars.Count – 1 do
    begin
      { Новый кандидат}
      New(tSet);
      SetLength(tSet^.Items, 1);
      tSet^.Items[0] := i;
      tSet^.podder := 0;
      new_cand.Add(tSet);
    end;
  end
  else
  begin
    { Много элементные наборы}
    { Если в списке больше одного набора}
    if cand.Count > 1 then
    begin
      for i := 0 to cand.count – 1 do
      begin
        { Первый набор для объединения}
        tSet := cand.Items[i];
        { Длина общей части}
        set_len := High(tSet^.items);
        for j := i + 1 to cand.count – 1 do
        begin
          { Второй набор для объединения}
          tSet1 := cand.Items[j];
          if set_len < 1 then
            equal := true
          else
          begin
            { Сравниваем общие части наборов}
            equal := true;
            for k := 0 to set_len - 1 do
              if tSet^.Items[k] <> tSet1^.Items[k] then
                equal := false;
          end;
          if equal then
          begin
            { Новый набор}
            New(tSet_new);
            tSet_New^.podder := 0;
            { Длина нового набора}
            SetLength(tSet_new^.Items, set_len + 2);
            { Копируем первый набор}
            for k := 0 to High(tSet^.items) do
            begin
                tSet_new^.Items[k] := tSet^.items[k];
            end;
            { Добавляем остаток второго набора}
            tSet_new^.Items[set_len + 1] := tSet1^.items[set_len];
            { Добавляем новый набор в список кандидатов}
            new_cand.Add(tSet_new);
          end;
        end;
      end;
    end;

Данные предоставлены компанией, находящейся в г.Биробиджан. Они были выгружены из системы 1С:Предприятие 8, и представляют собой отчет по продажам за I квартал 2014 года. Данные были обработаны и представлены в формате .csv (рис. 1).

Рисунок 1 – Входные данные для анализа

Основное окно программы показано на рис.2.


Рисунок 2 – Окно программы с загруженными данными

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


Рисунок 3 – Окно для выбора показателей

После проведения анализа, полученные правила выводятся в специальную область (рис. 4).

Рисунок 4 – Окно программы после обработки данных

Результаты анализа можно сохранить в текстовом файле (рис. 5).


Рисунок 5 – Текстовый файл с результатами

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

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


Библиографический список
  1. Шахиди А. Введение в анализ ассоциативных правил. URL: http://www.basegroup.ru/library/analysis/association_rules/intro/ (дата обращения 29.09.2014)
  2. Асеев М.Г., Дюк В.А. Поиск if-then правил в данных: проблемы и перспективы // Труды СПИИРАН. 2005. Т. 2. № 2. С. 76-85.
  3. Минаков И.А., Вольман С.И. Система нахождения бизнес-правил типа “if-then” в задачах транспортной логистики // Информационные технологии. 2007. № 12. С. 35-42
  4. Корнилков А.П., Хабибулина Т.В. О реализации поиска ассоциативных правил средствами языка программирования php // Современная техника и технологии. 2014. № 5 (33). С. 13.
  5. Бондаренко A.В., Гудков А.С. Интерактивный анализ ассоциативных правил в базах данных // Вестник компьютерных и информационных технологий. 2006. № 10. С. 42-45.
  6. Галкина Е.В. Ассоциативные правила в бизнес-анализе и контроле // Российское предпринимательство. 2013. № 9 (231). С. 111-117.
  7. Терешонок М.В. Поиск ассоциативных правил при анализе загрузки сетей сотовой связи // Электросвязь. 2008. № 6. С. 32-33.
  8. Горохова Т.Ю. Методика поиска ассоциативных правил при обработке данных в распределенных информационных системах // В мире научных открытий. 2010. № 4-11. С. 107-109.
  9. Краковецкий А.Ю. Метод поиска ассоциативных правил на основе сильных наборов данных и fp-дерева // Научные труды Винницкого национального технического университета. 2008. № 1. С. 2.
  10. Шабельников А.Н., Шабельников В.А. Поиск аномалий в технических базах данных временных рядов // Известия Южного федерального университета. Технические науки. 2008. Т. 81. № 4. С. 167-173.
  11. Гриняк В.М., Когай Е.И., Семенов С.М. Информационная технология планирования сезонных продаж // Территория новых возможностей. Вестник Владивостокского государственного университета экономики и сервиса. 2010. № 2. С. 191-198
  12. Баженов Р. И. Интеллектуальные информационные технологии. Биробиджан: ПГУ им. Шолом-Алейхема, 2011. 176 с.
  13. Векслер В.А., Баженов Р.И. Определение взаимосвязи номенклатурных позиций средствами 1С:Предприятие 8.3 // Современные научные исследования и инновации. 2014. № 7 (39). С. 45-49.
  14. Баженов Р.И., Векслер В.А. Анализ потребительских корзин в 1С:Предприятие на примере ABC-анализа // Информатизация и связь. 2013. № 5. С. 117-123.
  15. Баженов Р.И., Векслер В.А. Реализация XYZ-анализа в программном коде внутреннего языка программирования 1С:Предприятие 8.3 // Информатизация и связь. 2014. № 1. С. 37-42.
  16. Баженов Р.И., Векслер В.А., Гринкруг Л.С. RFM-анализ клиентской базы в прикладном решении 1С:Предприятие 8.3 // Информатизация и связь. 2014. № 2. С. 51-54.
  17. Xiao F., Fan C. Data mining in building automation system for improving building operational performance // Energy and Buildings. 2014. №75. С. 109-118.
  18. 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.  №84. С.140-151.


Все статьи автора «Баженов Руслан Иванович»


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

Связь с автором (комментарии/рецензии к статье)

Оставить комментарий

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

Если Вы еще не зарегистрированы на сайте, то Вам необходимо зарегистрироваться: