AprioriHybrid
Анализ времени работы алгоритмов Apriori и AprioriTid показывает, что в более ранних проходах Apriori добивается большего успеха, чем AprioriTid; однако AprioriTid работает лучше Apriori в более поздних проходах. Кроме того, они используют одну и ту же процедуру формирования наборов-кандидатов. Основанный на этом наблюдении, алгоритм AprioriHybrid предложен, чтобы объединить лучшие свойства алгоритмов Apriori и AprioriTid. AprioriHybrid использует алгоритм Apriori в начальных проходах и переходит к алгоритму AprioriTid, когда ожидается, что закодированный набор первоначального множества в конце прохода будет соответствовать возможностям памяти. Однако, переключение от Apriori до AprioriTid требует вовлечения дополнительных ресурсов.
Некоторыми авторами были предложены другие алгоритмы поиска ассоциативных правил, целью которых также было усовершенствование алгоритма Apriori. Кратко изложим суть нескольких, для более подробной информации можно рекомендовать [31, 33].
Один из них - алгоритм DHP, также называемый алгоритмом хеширования (J. Park, M. Chen and P. Yu, 1995 год). В основе его работы - вероятностный подсчет наборов-кандидатов, осуществляемый для сокращения числа подсчитываемых кандидатов на каждом этапе выполнения алгоритма Apriori [63, 64]. Сокращение обеспечивается за счет того, что каждый из k-элементных наборов-кандидатов помимо шага сокращения проходит шаг хеширования. В алгоритме на k-1 этапе во время выбора кандидата создается так называемая хеш-таблица. Каждая запись хеш-таблицы является счетчиком всех поддержек k-элементных наборов, которые соответствуют этой записи в хеш-таблице. Алгоритм использует эту информацию на этапе k для сокращения множества k-элементных наборов-кандидатов. После сокращения подмножества, как это происходит в Apriori, алгоритм может удалить набор-кандидат, если его значение в хеш-таблице меньше порогового значения, установленного для обеспечения.
К другим усовершенствованным алгоритмам относятся: PARTITION, DIC, алгоритм "выборочного анализа".
PARTITION алгоритм (A. Savasere, E. Omiecinski and S. Navathe, 1995 год). Этот алгоритм разбиения (разделения) заключается в сканировании транзакционной базы данных путем разделения ее на непересекающиеся разделы, каждый из которых может уместиться в оперативной памяти [65]. На первом шаге в каждом из разделов при помощи алгоритма Apriori определяются "локальные" часто встречающиеся наборы данных. На втором подсчитывается поддержка каждого такого набора относительно всей базы данных. Таким образом, на втором этапе определяется множество всех потенциально встречающихся наборов данных.
Алгоритм DIC, Dynamic Itemset Counting (S. Brin R. Motwani, J. Ullman and S. Tsur, 1997 год). Алгоритм разбивает базу данных на несколько блоков, каждый из которых отмечается так называемыми "начальными точками" (start point), и затем циклически сканирует базу данных [64].
AprioriTid
Интересная особенность этого алгоритма - то, что база данных D не используется для подсчета поддержки кандидатов набора товаров после первого прохода.
С этой целью используется кодирование кандидатов, выполненное на предыдущих проходах. В последующих проходах размер закодированных наборов может быть намного меньше, чем база данных, и таким образом экономятся значительные ресурсы.
Часто встречающиеся приложения с применением ассоциативных правил:
розничная торговля: определение товаров, которые стоит продвигать совместно; выбор местоположения товара в магазине; анализ потребительской корзины; прогнозирование спроса;перекрестные продажи: если есть информация о том, что клиенты приобрели продукты A, Б и В, то какие из них вероятнее всего купят продукт Г?маркетинг: поиск рыночных сегментов, тенденций покупательского поведения;сегментация клиентов: выявление общих характеристик клиентов компании, выявление групп покупателей;оформление каталогов, анализ сбытовых кампаний фирмы, определение последовательностей покупок клиентов (какая покупка последует за покупкой товара А);анализ Web-логов.
Приведем простой пример ассоциативного правила: покупатель, приобретающий банку краски, приобретет кисточку для краски с вероятностью 50%.
Часто встречающиеся шаблоны или образцы
Допустим, имеется транзакционная база данных D. Присвоим значениям товаров переменные (таблица 15.2).
Хлеб = a
Молоко = b
Печенье = c
Сметана = d
Колбаса = e
Конфеты = f
 | TIDПриобретенные покупки|||
| 100 | Хлеб, молоко, печенье | 100 | a, b, c |
| 200 | Молоко, сметана | 200 | b, d |
| 300 | Молоко, хлеб, сметана, печенье | 300 | b, a, d, c |
| 400 | Колбаса, сметана | 400 | e, d |
| 500 | Хлеб, молоко, печенье, сметана | 500 | a, b, c, d |
| 600 | Конфеты | 600 | f |
Рассмотрим набор товаров (Itemset), включающий, например, {Хлеб, молоко, печенье}. Выразим этот набор с помощью переменных:
abc={a,b,c}Границы поддержки и достоверности ассоциативного правила
При помощи использования алгоритмов поиска ассоциативных правил аналитик может получить все возможные правила вида "Из A следует B", с различными значениями поддержки и достоверности. Однако в большинстве случаев, количество правил необходимо ограничивать заранее установленными минимальными и максимальными значениями поддержки и достоверности.
Если значение поддержки правила слишком велико, то в результате работы алгоритма будут найдены правила очевидные и хорошо известные. Слишком низкое значение поддержки приведет к нахождению очень большого количества правил, которые, возможно, будут в большей части необоснованными, но не известными и не очевидными для аналитика. Таким образом, необходимо определить такой интервал, "золотую середину", который с одной стороны обеспечит нахождение неочевидных правил, а с другой - их обоснованность.
Если уровень достоверности слишком мал, то ценность правила вызывает серьезные сомнения. Например, правило с достоверностью в 3% только условно можно назвать правилом.
Характеристики ассоциативных правил
Ассоциативное правило имеет вид: "Из события A следует событие B".
В результате такого вида анализа мы устанавливаем закономерность следующего вида: "Если в таранзакции встретился набор товаров (или набор элементов) A, то можно сделать вывод, что в этой же транзакции должен появиться набор элементов B)" Установление таких закономерностей дает нам возможность находить очень простые и понятные правила, называемые ассоциативными.
Основными характеристиками ассоциативного правила являются поддержка и достоверность правила.
Рассмотрим правило "из покупки молока следует покупка печенья" для базы данных, которая была приведена выше в таблице 15.1. Понятие поддержки набора мы уже рассмотрели. Существует понятие поддержки правила.
Правило имеет поддержку s, если s% транзакций из всего набора содержат одновременно наборы элементов A и B или, другими словами, содержат оба товара.
Молоко - это товар A, печенье - это товар B. Поддержка правила "из покупки молока следует покупка печенья" равна 3, или 50%.
Достоверность правила показывает, какова вероятность того, что из события A следует событие B.
Правило "Из A следует B" справедливо с достоверностью с, если c% транзакций из всего множества, содержащих набор элементов A, также содержат набор элементов B.
Число транзакций, содержащих молоко, равно четырем, число транзакций, содержащих печенье, равно трем, достоверность правила равна (3/4)*100%, т.е. 75%.
Достоверность правила "из покупки молока следует покупка печенья" равна 75%, т.е. 75% транзакций, содержащих товар А, также содержат товар B.
Методы поиска ассоциативных правил
Алгоритм AIS. Первый алгоритм поиска ассоциативных правил, называвшийся AIS [62], (предложенный Agrawal, Imielinski and Swami) был разработан сотрудниками исследовательского центра IBM Almaden в 1993 году. С этой работы начался интерес к ассоциативным правилам; на середину 90-х годов прошлого века пришелся пик исследовательских работ в этой области, и с тех пор каждый год появляется несколько новых алгоритмов.
В алгоритме AIS кандидаты множества наборов генерируются и подсчитываются "на лету", во время сканирования базы данных.
Алгоритм SETM. Создание этого алгоритма было мотивировано желанием использовать язык SQL для вычисления часто встречающихся наборов товаров. Как и алгоритм AIS, SETM также формирует кандидатов "на лету", основываясь на преобразованиях базы данных. Чтобы использовать стандартную операцию объединения языка SQL для формирования кандидата, SETM отделяет формирование кандидата от их подсчета.
Неудобство алгоритмов AIS и SETM - излишнее генерирование и подсчет слишком многих кандидатов, которые в результате не оказываются часто встречающимися. Для улучшения их работы был предложен алгоритм Apriori [63].
Работа данного алгоритма состоит из нескольких этапов, каждый из этапов состоит из следующих шагов:
формирование кандидатов;подсчет кандидатов.Формирование кандидатов (candidate generation) - этап, на котором алгоритм, сканируя базу данных, создает множество i-элементных кандидатов (i - номер этапа). На этом этапе поддержка кандидатов не рассчитывается.
Подсчет кандидатов (candidate counting) - этап, на котором вычисляется поддержка каждого i-элементного кандидата. Здесь же осуществляется отсечение кандидатов, поддержка которых меньше минимума, установленного пользователем (min_sup). Оставшиеся i-элементные наборы называем часто встречающимися.
Рассмотрим работу алгоритма Apriori на примере базы данных D. Иллюстрация работы алгоритма приведена на рис. 15.1. Минимальный уровень поддержки равен 3.
Рис. 15.1. Алгоритм Apriori
На первом этапе происходит формирование одноэлементных кандидатов. Далее алгоритм подсчитывает поддержку одноэлементных наборов. Наборы с уровнем поддержки меньше установленного, то есть 3, отсекаются. В нашем примере это наборы e и f, которые имеют поддержку, равную 1. Оставшиеся наборы товаров считаются часто встречающимися одноэлементными наборами товаров: это наборы a, b, c, d.
Далее происходит формирование двухэлементных кандидатов, подсчет их поддержки и отсечение наборов с уровнем поддержки, меньшим 3. Оставшиеся двухэлементные наборы товаров, считающиеся часто встречающимися двухэлементными наборами ab, ac, bd, принимают участие в дальнейшей работе алгоритма.
Если смотреть на работу алгоритма прямолинейно, на последнем этапе алгоритм формирует трехэлементные наборы товаров: abc, abd, bcd, acd, подсчитывает их поддержку и отсекает наборы с уровнем поддержки, меньшим 3. Набор товаров abc может быть назван часто встречающимся.
Однако алгоритм Apriori уменьшает количество кандидатов, отсекая - априори - тех, которые заведомо не могут стать часто встречающимися, на основе информации об отсеченных кандидатах на предыдущих этапах работы алгоритма.
Отсечение кандидатов происходит на основе предположения о том, что у часто встречающегося набора товаров все подмножества должны быть часто встречающимися. Если в наборе находится подмножество, которое на предыдущем этапе было определено как нечасто встречающееся, этот кандидат уже не включается в формирование и подсчет кандидатов.
Так наборы товаров ad, bc, cd были отброшены как нечасто встречающиеся, алгоритм не рассматривал товаров abd, bcd, acd.
При рассмотрении этих наборов формирование трехэлементных кандидатов происходило бы по схеме, приведенной в верхнем пунктирном прямоугольнике. Поскольку алгоритм априори отбросил заведомо нечасто встречающиеся наборы, последний этап алгоритма сразу определил набор abc как единственный трехэлементный часто встречающийся набор (этап приведен в нижнем пунктирном прямоугольнике).
Алгоритм Apriori рассчитывает также поддержку наборов, которые не могут быть отсечены априори. Это так называемая негативная область (negative border), к ней принадлежат наборы-кандидаты, которые встречаются редко, их самих нельзя отнести к часто встречающимся, но все подмножества данных наборов являются часто встречающимися.
Поддержка
Этот набор товаров встречается в нашей базе данных три раза, т.е. поддержка этого набора товаров равна 3:
SUP(abc)=3.При минимальном уровне поддержки, равной трем, набор товаров abc является часто встречающимся шаблоном.
min_sup=3, {Хлеб, молоко, печенье} - часто встречающийся шаблон.
Поддержкой называют количество или процент транзакций, содержащих определенный набор данных.
Для данного набора товаров поддержка, выраженная в процентном отношении, равна 50%.
SUP(abc)=(3/6)*100%=50%Поддержку иногда также называют обеспечением набора.
Таким образом, набор представляет интерес, если его поддержка выше определенного пользователем минимального значения (min support). Эти наборы называют часто встречающимися (frequent).
Пример решения задачи поиска ассоциативных правил
Дана транзакционная база данных, необходимо найти наиболее часто встречающиеся наборы товаров и набор ассоциативных правил с определенными границами значений поддержки и доверия.
Рассмотрим процесс построения ассоциативных правил в аналитическом пакете Deductor.
Транзакционная база данных, которая содержит в каждой записи номер чека и товар, приобретенный по этому чеку, имеет формат MS Excel. Для начала импортируем данные из файла MS Excel в среду Deductor, этот процесс аналогичен тому, что был рассмотрен в лекции о нейронных сетях. Единственное отличие - в назначении столбцов. Для номера транзакции (обычно в базе данных - это поле "номер чека") указываем тип "идентификатор транзакции (ID)", а для наименований товара - тип "элемент". Результат импорта базы данных из файла MS Excel в среду Deductor видим на рис. 15.2. На рисунке приведен фрагмент базы данных, которая содержит более 140 записей.
Рис. 15.2. Транзакционная база данных, импортированная в Deductor из файла MS Excel
Далее вызываем мастер обработки и выбираем метод "Ассоциативные правила". На втором шаге мастера проверяем назначения исходных столбцов данных, они должны иметь тип "ID" и "элемент".
На третьем шаге, проиллюстрированном на рис. 15.3, необходимо настроить параметры поиска правил, т.е. установить минимальные и максимальные характеристики поддержки и достоверности. Это наиболее "ответственный" момент формирования набора правил, о важности выбора границ значений поддержки и достоверности уже говорилось в начале лекции. Выбор можно сделать на основе каких-либо соображений, имеющегося опыта анализа подобных данных, интуиции или же определить в ходе экспериментов.
Рис. 15.3. Настройка параметров построения ассоциативных правил
Мы установим такие границы для параметров поиска: минимальный и максимальный уровень поддержки равны 20% и 60% соответственно, минимальный и максимальный уровень значения достоверности равны 40% и 90% соответственно.
Эти значения были выявлены в ходе проведения нескольких экспериментов, и оказалось, что именно при таких значениях формируется требуемый набор правил. При указании некоторых значений, например, уровня поддержки от 30% до 50%, набор правил не формируется, поскольку ни одно правило по параметрам поддержки не входит в этот интервал.
На следующем шаге мастера запускается процесс поиска ассоциативных правил. В результате видим информацию о количестве множеств и найденных правил в виде гистограммы распределения часто встречающихся множеств по их мощности. Данный процесс проиллюстрирован на рис. 15.4.
Рис. 15.4. Процесс построения ассоциативных правил
Здесь мы видим, что количество сформированных множеств равно тринадцати - это популярные наборы, количество сформированных правил - пятнадцать.
На следующем шаге для просмотра полученных результатов предлагается выбрать визуализаторы из списка; мы выберем такие: "Популярные наборы", "Правила", "Дерево правил", "Что-если". Рассмотрим, что они из себя представляют.
Визуализатор "Популярные наборы". Популярные наборы или часто встречающиеся наборы - это наборы, состоящие из одного или нескольких товаров, которые в транзакциях наиболее часто встречаются одновременно. Характеристикой, насколько часто набор встречается в анализируемом наборе данных, является поддержка.
Популярные наборы нашего набора данных, найденные при заданных параметрах, приведены в таблице 15.3. Есть возможность отсортировать данную таблицу по разным ее характеристикам. Для определения наиболее популярных товаров и их наборов удобно отсортировать ее по уровню поддержки. Таким образом, мы видим, что наибольшей популярностью пользуются такие товары: хлеб и булки, масло, соки.
| 6 | ХЛЕБ И БУЛКИ | 54,55 | 24 |
| 3 | МАСЛО | 52,27 | 23 |
| 5 | СОКИ | 50,00 | 22 |
| 10 | МАСЛО И ХЛЕБ И БУЛКИ | 45,45 | 20 |
| 4 | МОЛОКО | 43,18 | 19 |
| 2 | КЕФИР | 31,82 | 14 |
| 1 | ЙОГУРТЫ | 31,82 | 14 |
| 12 | СОКИ И ХЛЕБ И БУЛКИ | 22,73 | 10 |
| 11 | МОЛОКО И ХЛЕБ И БУЛКИ | 22,73 | 10 |
| 8 | МАСЛО И МОЛОКО | 22,73 | 10 |
| 7 | ЙОГУРТЫ И КЕФИР | 22,73 | 10 |
| 13 | МАСЛО И МОЛОКО И ХЛЕБ И БУЛКИ | 20,45 | 9 |
| 9 | МАСЛО И СОКИ | 20,45 | 9 |
Разновидности алгоритма Apriori
В зависимости от размера самого длинного часто встречающегося набора алгоритм Apriori сканирует базу данных определенное количество раз. Разновидности алгоритма Apriori, являющиеся его оптимизацией, предложены для сокращения количества сканирований базы данных, количества наборов-кандидатов или того и другого [31]. Были предложены следующие разновидности алгоритма Apriori: AprioriTID и AprioriHybrid.
Визуализатор "Правила"
Правила в данном визуализаторе размещены в виде списка. Каждое правило, представленное как "условие-следствие", характеризуется значением поддержки в абсолютном и процентном выражении, а также достоверностью. Таким образом, аналитик видит поведение покупателей, описанное в виде набора правил. Набор правил для решаемой нами задачи приведен в таблице 15.4. Например, первое правило говорит о том, что если покупатель купил йогурт, то с достоверностью или вероятностью 71% он купит также кефир. Эта информация полезна с различных точек зрения. Она, например, помогает решить задачу расположения товаров в магазине.
| 1 | ЙОГУРТЫ | КЕФИР | 22,73 | 10 | 71,43 |
| 2 | КЕФИР | ЙОГУРТЫ | 22,73 | 10 | 71,43 |
| 3 | МАСЛО | МОЛОКО | 22,73 | 10 | 43,48 |
| 4 | МОЛОКО | МАСЛО | 22,73 | 10 | 52,63 |
| 5 | СОКИ | МАСЛО | 20,45 | 9 | 40,91 |
| 6 | МАСЛО | ХЛЕБ И БУЛКИ | 45,45 | 20 | 86,96 |
| 7 | ХЛЕБ И БУЛКИ | МАСЛО | 45,45 | 20 | 83,33 |
| 8 | МОЛОКО | ХЛЕБ И БУЛКИ | 22,73 | 10 | 52,63 |
| 9 | ХЛЕБ И БУЛКИ | МОЛОКО | 22,73 | 10 | 41,67 |
| 10 | СОКИ | ХЛЕБ И БУЛКИ | 22,73 | 10 | 45,45 |
| 11 | ХЛЕБ И БУЛКИ | СОКИ | 22,73 | 10 | 41,67 |
| 12 | МАСЛО И МОЛОКО | ХЛЕБ И БУЛКИ | 20,45 | 9 | 90,00 |
| 13 | МАСЛО И ХЛЕБ И БУЛКИ | МОЛОКО | 20,45 | 9 | 45,00 |
| 14 | МОЛОКО И ХЛЕБ И БУЛКИ | МАСЛО | 20,45 | 9 | 90,00 |
| 15 | МОЛОКО | МАСЛО И ХЛЕБ И БУЛКИ | 20,45 | 9 | 47,37 |
При большом количестве найденных правил и широком ассортименте товаров анализировать полученные правила достаточно сложно. Для удобства анализа таких наборов правил предлагаются визуализаторы "Дерево правил" и "Что-если".
Визуализатор "Дерево правил" представляет собой двухуровневое дерево, которое может быть построено по двум критериям: по условию и по следствию. Если дерево построено по условию, то вверху списка отображается условие правила, а список, прилагающийся к данному условию, состоит из его следствий. При выборе определенного условия, в правой части визуализатора отображаются следствия условия, уровень поддержки и достоверности.
В случае построения дерева по следствию, вверху списка отображается следствие правила, а список состоит из его условий. При выборе определенного следствия, в правой части визуализатора мы видим условия этого правила с указанием уровня поддержки и достоверности.
Визуализатор "что-если" удобен, если нам необходимо ответить на вопрос, какие следствия могут получиться из данного условия.
Например, выбрав условие "МОЛОКО", в левой части экрана получаем три следствия "МАСЛО", "ХЛЕБ И БУЛКИ", "МАСЛО И ХЛЕБ И БУЛКИ", для которых указаны уровень поддержки и достоверности. Этот визуализатор представлен на рис. 15.5.
Рис. 15.5. Визуализатор "Что-если"
Рассмотренный пример поиска ассоциативных правил является типичной иллюстрацией задачи анализа покупательской корзины. В результате ее решения определяются часто встречающиеся наборы товаров, а также наборы товаров, совместно приобретаемые покупателями. Найденные правила могут быть использованы для решения различных задач, в частности для размещения товаров на прилавках магазинов, предоставления скидок на пары товаров для повышения объема продаж и, следовательно, прибыли и других задач.
Введение в ассоциативные правила
Впервые задача поиска ассоциативных правил (association rule mining) была предложена для нахождения типичных шаблонов покупок, совершаемых в супермаркетах, поэтому иногда ее еще называют анализом рыночной корзины (market basket analysis).
Рыночная корзина - это набор товаров, приобретенных покупателем в рамках одной отдельно взятой транзакции.
Транзакции являются достаточно характерными операциями, ими, например, могут описываться результаты посещений различных магазинов.
Транзакция - это множество событий, которые произошли одновременно.
Регистрируя все бизнес-операции в течение всего времени своей деятельности, торговые компании накапливают огромные собрания транзакций. Каждая такая транзакция представляет собой набор товаров, купленных покупателем за один визит.
Полученные в результате анализа шаблоны включают перечень товаров и число транзакций, которые содержат данные наборы.
Транзакционная или операционная база данных (Transaction database) представляет собой двумерную таблицу, которая состоит из номера транзакции (TID) и перечня покупок, приобретенных во время этой транзакции.
TID - уникальный идентификатор, определяющий каждую сделку или транзакцию.
Пример транзакционной базы данных, состоящей из покупательских транзакций, приведен в таблице 15.1. В таблице первая колонка (TID) определяет номер транзакции, во второй колонке таблицы приведены товары, приобретенные во время определенной транзакции.
| 100 | Хлеб, молоко, печенье |
| 200 | Молоко, сметана |
| 300 | Молоко, хлеб, сметана, печенье |
| 400 | Колбаса, сметана |
| 500 | Хлеб, молоко, печенье, сметана |
На основе имеющейся базы данных нам нужно найти закономерности между событиями, то есть покупками.
