Задача поиска ассоциативных правил предполагает отыскание частых наборов в большом числе наборов данных.
В контексте анализы рыночной корзины это поиск наборов товаров, которые наиболее часто покупаются вместе.
В задаче не учитывался такой атрибут транзакции как время. Тем не менее,
взаимосвязь событий во времени также представляет большой интерес.
Основываясь на том, какие события чаще всего следуют за другими, можно
заранее предсказывать их появление, что позволит принимать более
правильные решения.
Отличие поиска ассоциативных правил от секвенциального анализа (анализа
последовательностей) в том, что в первом случае ищется набор объектов в
рамках одной транзакции, т.е. такие товары, которые чаще всего
покупаются ВМЕСТЕ. В одно время, за одну транзакцию.
Во втором же случае ищутся не часто встречающиеся наборы, а часто встречающиеся последовательности.
Т.е. в какой последовательности покупаются товары или через какой промежуток времени после покупки товара "А", человек
наиболее склонен купить товар "Б". Т.е. данные по одному и тому же клиенту, но взятые из разных транзакций.
Получаемые закономерности в действиях покупателей можно
использовать для формирования более выгодного предложения,
стимулирования продаж определённых товаров, управления запасами и т.п.
Секвенциальный анализ актуален и для телекоммуникационных компаний.
Основная проблема, для решения которой он используется, - это анализ
данных об авариях на различных узлах телекоммуникационной сети.
Информация о последовательности совершения аварий может помочь в
обнаружении неполадок и предупреждении новых аварий.
Введём некоторые обозначения и определения.
- D - множество всех транзакций T, где каждая транзакция характеризуется уникальным идентификатором покупателя, временем транзакции и идентификатором объекта (id товара);
- I - множество всех объектов (товаров) общим числом m;
- si - набор, состоящий из элементов множества I;
- S - последовательность, состоящая из различных наборов si;
Шаблон последовательности - это последовательность наборов, которая часто встречается в транзакциях (в определённом порядке).
Последовательность < a1,a2,...,an > является входящей в последовательность < b1,b2,...,bn > , если существуют такие i1 < i2 < ... < in, при которых \(a_1 \subseteq b_{i1}, a_2 \subseteq b_{i2}, ... a_n \subseteq b_{in}\).
Например, последовательность <(3)(6,7,9)(7,9)> входит в <(2)(3)(6,7,8,9)(7)(7,9)>, поскольку \((3)\subseteq(3), (6,7,9) \subseteq (6,7,8,9), (7,9) \subseteq (7,9)\). Хотя последовательность <(2)(3)> не входит в <(2,3)>, так как исходная последовательность говорит о том, что "3" был куплен после "2", а вторая, что товары "2" и "3" были куплены вместе.
В приведённом примере цифрами обозначены идентификаторы товаров.
В ходе анализа последовательностей нас будут интересовать такие последовательности, которые не входят в более длинные последовательности.
Подержка последовательности - это отношение числа покупателей, в чьих транзакциях присутствует указанная последовательность к общему числу покупателей.
Также как и в задаче поиска ассоциативных правил применяется минимальная и максимальная поддержка. Минимальная поддержка позволяет исключить из рассмотрения последовательности, которые не являются частыми. Максимальная поддержка исключает очевидные закономерности в появлении последовательностей. Оба параметра задаются пользователем до начала работы алгоритма.
