Поиск последовательных шаблонов. Часть 1

Введение

Во вводной статье раздела «Введение в анализ ассоциативных правил», рассказывалось, как ассоциативные правила применяются при анализе рыночной корзины. Целью такого анализа может быть поиск закономерностей в бизнес-процессах, выявление связей между продажами отдельных товаров и их групп, обнаружение типичных шаблонов покупок, прогнозирование объемов продаж и так далее.

Знания, полученные в процессе анализа, позволяют принимать решения, направленные на улучшение работы компании по самым разнообразным направлениям: оптимизация закупок, снижение издержек на доставку товаров, выявление целевых групп клиентов, определение ценовой политики и маркетинговой стратегии, стимулирование спроса и многое другое.

Одной из главных проблем, связанных с поиском ассоциативных правил, является необходимость обработки большого количества транзакций, каждая из которых содержит множество предметов (товаров). Если делать это с помощью прямого перебора, то на практике придется рассмотреть огромное количество возможных ассоциаций, что делает задачу неразрешимой. Для решения этой проблемы в 1994 г. Р. Агравал и Р. Шрикант предложили алгоритм поиска ассоциативных правил на транзакционных базах данных, получивший название Apriori. Алгоритм описан в статье «Apriori — масштабируемый алгоритм поиска ассоциативных правил».

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

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

Во-вторых, ассоциативные правила не являются клиентоориентированными, поскольку не связывают наборы предметов в транзакции с определенным клиентом. В то же время, с точки зрения анализа может представлять интерес исследование динамики продаж для отдельных клиентов. Для этого в транзакцию кроме предметного набора следует ввести идентификатор клиента. Такие транзакции называются клиентоориентированными (клиентскими) и образуют клиентоориентированные транзакционные базы данных, которые обязательно содержат поле идентификатора клиента. Возможность получения идентификаторов клиентов имеется, например, при торговле по кредитным картам, клиентским картам, дающим право на скидку.

Для расширения возможностей анализа транзакционных данных с учетом временного аспекта, последовательности появления предметов и ориентированности на конкретного клиента существует задача Data Mining под названием «последовательные шаблоны» (sequential pattern, time-serial sequential pattern).

Теория последовательных шаблонов во многом основана на теории ассоциативных правил и, по сути, является ее расширением. В частности, базовыми понятиями в ней также являются транзакция, предметный набор, частота набора, поддержка и т.д. Кроме этого, для поиска последовательных шаблонов широко используется адаптированный алгоритм Apriori и его модификации. Но при рассмотрении последовательных шаблонов необходимо учитывать ряд особенностей. Главная из них заключается в том, что если в ассоциативных правилах рассматривается только факт совместного появления товаров в одной транзакции, то последовательных шаблонах рассматривается последовательность появления товаров. Последовательный шаблон – это всегда последовательность появления предметов и их групп.

Интуитивно понятно, что типичной последовательностью (шаблоном) может быть только такая последовательность, которая встречается в базе данных достаточно часто. Поэтому при поиске последовательных шаблонов возникает та же проблема, что и при поиске ассоциативных правил. Большое число рассматриваемых предметов порождает огромное количество возможных последовательностей, что приводит к серьезным вычислительным затратам при использовании полного перебора. Но и здесь применим принцип антимонотонности — последовательности, содержащие редкие события, не могут быть частыми, что позволяет существенно снизить пространство поиска.

Применение последовательных шаблонов выходит за рамки анализа рыночной корзины. Они позволяют выявлять типичные последовательности событий в самых разнообразных предметных областях. Например, последовательность может содержать такие события, как покупку материалов для строительства дома: клиент покупает сначала материалы для фундамента, потом для стен, а затем для крыши.

При этом последовательность не обязательно должна быть непрерывной. В промежутке клиент может купить, например, окна, но типичная последовательность при этом сохранится. Анализ всех последовательностей покупок разными клиентами, позволит выявить наиболее типичные шаблоны. Знание таких последовательностей поможет стимулировать клиентов, предлагая им товары в порядке, установленном шаблоном.

Постановка задачи

Рассмотрим постановку задачи поиска последовательных шаблонов, используя задачу анализа рыночной корзины. Именно так она была изначально сформулирована в основополагающей статье Р. Агравала и Р. Шриканта «Mining Sequential Patterns», что позволит провести аналогии с ассоциативными правилами и выявить наиболее существенные различия. При этом будем придерживаться терминологии первоисточника.

Пусть имеется база данных D, в которой каждая запись представляет собой клиентскую транзакцию. Каждая транзакция содержит следующие поля: идентификатор клиента, дата/время транзакции, и набор купленных товаров. Введем ограничение, что ни один клиент не имеет двух или более транзакций, совершенных одновременно.

Введем несколько основных понятий. Предметный набор – это непустой набор предметов (товаров), появившихся в одной транзакции. Последовательность – это упорядоченный список предметных наборов. Последовательность будем заключать в треугольные скобки, а предметный набор — в круглые. Тогда, если обозначать предметы целыми числами, то предметные наборы будут записаны в виде (2,4,5),(1,3), а последовательность, содержащая эти наборы <(2,4,5),(1,3)>. Если предметы появились в одном наборе, это значит, что они были приобретены одновременно.

Обозначим предметный набор I=(i_1,i_2,...,i_m) (от англ. itemset — предметный набор, набор элементов) где i_j — предмет. Введём в рассмотрение последовательность S=I_1,I_2,...,I_m , где I_i — предметный набор.

Последовательность S_1 содержится в другой последовательности S_2, если все предметные наборы из S_1 содержатся в предметных наборах S_2 . Например, последовательность <(3);(4;5);(8)> содержится в последовательности <(7);(3,8);(9);(4,5,6);(8)>, поскольку (3)⊆(3,8), (4,5)⊆(4,5,6) и (8)⊆(8). Однако, <(3);(5)> ⊈ <(3,5)> и наоборот, поскольку в первой последовательности предметы 3 и 5 были куплены один за другим, а во второй – куплены совместно.

Последовательность S называется максимальной, если она не содержится в какой-либо другой последовательности.

Все транзакции одного клиента могут быть показаны в виде последовательности, в которой они упорядочены по дате, времени или номеру визита. Такие последовательности будем называть клиентскими. Формально это записывается следующим образом.

Пусть клиент совершил несколько упорядоченных во времени транзакций  T_1,T_2,...,T_n . Тогда каждый предметный набор в транзакции T_i обозначим I(T_i) , а каждую клиентскую последовательность для данного клиента запишем как I(T_1),I(T_2),...,I(T_n) . Иными словами, клиентская последовательность – это последовательность предметных наборов, содержащихся во всех транзакциях, совершенных данным клиентом.

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

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

Рассмотрим базу данных, представленную в таблице 1.

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

Зададимся уровнем минимальной поддержки 25%. В нашем примере ему будет удовлетворять любая последовательность, поддерживаемая как минимум двумя клиентами. Этому уровню поддержки будут удовлетворять две последовательности <(3); (9)> и <(3); (4,7)>, которые также являются максимальными.

В данном примере они и будут искомыми последовательными шаблонами. Последовательный шаблон <(3); (9)> поддерживается клиентами 1 и 4. Клиент 4 купил предметы (4, 7) между предметами 3 и 9, но поддерживает шаблон <(3); (9)>, поскольку шаблоны не обязательно являются непрерывными последовательностями. Шаблон <(3); (4, 7)> поддерживается клиентами 2 и 4. Клиент 2 купил предмет 6 между 4 и 7, но поддерживает данный шаблон, поскольку набор (4,7) является подмножеством (4,6,7).

Не удовлетворяет уровню минимальной поддержки последовательность <(1,2); (3)>, поскольку она поддерживается только клиентом 2. Последовательности <(3)>, <(4)>, <(7)>, <(9)>, <(3); (4)>, <(3); (7)> и <(4, 7)>, хотя и удовлетворяют минимальной поддержке, но не являются максимальными, поскольку содержатся в более длинных последовательностях.

Поиск последовательных шаблонов

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

Напомним, что в ассоциативных правилах предметный набор, удовлетворяющий уровню минимальной поддержки, называется частым или популярным. Обратим внимание, что любой предметный набор в частой последовательности также должен быть частым, на что указывает свойство антимонотонности. Следовательно, любая частая последовательность будет состоять только из частых предметных наборов.

Частые предметные наборы из таблицы 2 представлены в таблице 3.

Таблица 3 — Частые предметные наборы

Таким образом, процесс поиска последовательных шаблонов содержит следующие шаги.

Сортировка. Транзакции исходной базы данных сортируются по кодам клиентов, а транзакции каждого клиента — по дате, времени или номеру визита. Таким образом, исходная база данных преобразуется в базу данных клиентских последовательностей.

Поиск частых предметных наборов. Ищется множество всех частых предметных наборов F . Одновременно ищется множество всех частых 1-последовательностей, поскольку оно содержится в F .

Задача поиска частых предметных наборов на множестве клиентских транзакций использует несколько другое определение поддержки, а именно — число транзакций, в которых представлен данный предметный набор. В то время как в задаче поиска последовательных шаблонов — это число клиентов, купивших данный набор хотя бы в одной из транзакций.

Затем множество частых предметных наборов преобразуется в альтернативное представление в виде букв, целых чисел или двоичных последовательностей. Ранее мы установили, что частыми предметными наборами будут (3), (4), (7), (4,7) и (9), а возможное представление показано ниже в таблице 4. Использование такого представления в виде отдельных значений, позволяет упростить алгоритмическую реализацию задачи.

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

Если клиентская последовательность не содержит ни одного частого предметного набора, то вся эта последовательность также исключается. После преобразования каждая клиентская последовательность будет представлена в виде множества частых предметных наборов (f_1, f_2,..., f_n) . В зависимости от объема доступной памяти преобразование может быть выполнено полностью над всеми данными, или выполняться «на лету» при чтении каждой клиентской последовательность в процессе прохода базы данных. Преобразование данных из таблицы 2 представлено в таблице 4.

Таблица 4 — Преобразование базы данных клиентских последовательностей

Например, в процессе преобразования клиентской последовательности 2, набор (1,2) был исключен, поскольку не является частым, а набор (4,6,7) был заменен множеством частых предметных наборов {(4);(7);(4,7)}.

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

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

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

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

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

Кроме этого, мы рассмотрим два алгоритма частичного поиска AprioriSome и DynamicSome. Эти алгоритмы работают только с максимальными последовательностями, что позволяет избежать обработки немаксимальных последовательностей.

Оба частичных алгоритма содержат две фазы: прямую и обратную. На прямой фазе находятся все частые последовательности определенных длин, а на обратной — все оставшиеся частые последовательности. Основное различие между алгоритмами заключается в процедуре, которую они используют для формирования последовательностей-кандидатов на прямой фазе. Алгоритм AprioriSome формирует кандидаты, используя только частые последовательности, найденные на предыдущем проходе, а затем делает проход для вычисления их поддержки.

Алгоритм DynamicSome генерирует кандидатов «на лету», используя частые последовательности, найденные на предыдущих проходах и клиентские последовательности, прочитанные из базы данных.

Эти алгоритмы подробно рассматриваются во второй части статьи.

Литература

Другие материалы по теме:

Поиск последовательных шаблонов. Часть 2

Введение в анализ ассоциативных правил 

Выявление обобщенных ассоциативных правил

Apriori - масштабируемый алгоритм поиска ассоциативных правил