Алгоритм поиска ассоциативных правил
Ассоциативные правила позволяют находить закономерности между связанными событиями. Примером такого правила служит утверждение, что покупатель, приобретающий «Хлеб», приобретет и «Молоко». Впервые эта задача была предложена для поиска ассоциативных правил для нахождения типичных шаблонов покупок, совершаемых в супермаркетах, поэтому иногда ее еще называют анализом рыночной корзины (market basket analysis).
Пусть имеется база данных, состоящая из покупательских транзакций. Каждая транзакция – это набор товаров, купленных покупателем за один визит. Такую транзакцию еще называют рыночной корзиной. Целью анализа является установление следующих зависимостей: если в транзакции встретился некоторый набор элементов X, то на основании этого можно сделать вывод о том, что другой набор элементов Y также должен появиться в этой транзакции. Установление таких зависимостей дает нам возможность находить очень простые и интуитивно понятные правила.
Ассоциативное правило состоит из двух наборов предметов, называемых условие (англ: antecedent) и следствие (англ: consequent), записываемых в виде X → Y, что читается «из X следует Y». Таким образом, ассоциативное правило формулируется в виде «Если условие, то следствие».
При поиске ассоциативных правил используют показатели, позволяющие оценить значимость правила. В этой связи можно выделить объективные и субъективные меры значимости правил. Объективными являются такие меры, как поддержка и достоверность, которые могут применяться независимо от конкретного приложения. Субъективные меры связаны со специальной информацией, определяемой пользователем в контексте решаемой задачи. Такими субъективными мерами являются лифт и левередж.
Ассоциативные правила описывают связь между наборами предметов, соответствующим условию и следствию. Эта связь характеризуется двумя показателями – поддержкой (s) и достоверностью (с).
Правило «Из Х следует Y» имеет поддержку s, если s % транзакций из всего набора содержат наборы элементов Х и Y.
Достоверность правила показывает, какова вероятность того, что из X
следует Y. Правило «Из X следует Y» справедливо с достоверностью с,
если c % транзакций из всего множества, содержащих набор элементов X,
также содержат набор элементов Y.
Покажем на конкретном примере: пусть 75 % транзакций, содержащих хлеб, также содержат молоко, а 3 % от общего числа всех транзакций содержат оба товара. 75 % – это достоверность правила, а 3 % – это поддержка.
Лифт (L) – это отношение частоты появления условия в транзакциях, которые также содержат и следствие, к частоте появления следствия в целом. Значения лифта большие, чем единица, показывают, что условие более часто появляется в транзакциях, содержащих и следствие, чем в остальных. Можно сказать, что лифт является обобщенной мерой связи двух предметных наборов: при значениях лифта >1 связь положительная, при 1 она отсутствует, а при значениях <1 – отрицательная.
Другой мерой значимости правила является левередж – это разность между наблюдаемой частотой, с которой условие и следствие появляются совместно (т.е. поддержкой ассоциации), и произведением частот появления (поддержек) условия и следствия по отдельности.
Такие меры, как лифт и левередж могут использоваться для последующего ограничения набора рассматриваемых ассоциаций путем установки порога значимости, ниже которого ассоциации отбрасываются.
Алгоритмы поиска ассоциативных правил предназначены для нахождения всех правил вида «Из X следует Y», причем поддержка и достоверность этих правил должны находиться в рамках некоторых, наперед заданных, границ, называемых соответственно минимальной и максимальной поддержкой и минимальной и максимальной достоверностью.
Границы значений параметров поддержки и достоверности выбираются таким образом, чтобы ограничить количество найденных правил. Если поддержка имеет большое значение, то алгоритмы будут находить правила, хорошо известные аналитикам или настолько очевидные, что нет никакого смысла проводить такой анализ. С другой стороны, низкое значение поддержки ведет к генерации огромного количества правил, что, конечно, требует существенных вычислительных ресурсов. Тем не менее, большинство интересных правил находится именно при низком значении порога поддержки, хотя слишком низкое значение поддержки ведет к генерации статистически необоснованных правил. Таким образом, необходимо найти компромисс, обеспечивающий, во-первых, интересность
правил и, во-вторых, их статистическую обоснованность. Поэтому значения этих границ напрямую зависят от характера анализируемых данных и подбираются индивидуально.
Простейший алгоритм поиска состоит в том, что для всех ассоциаций, которые могут быть построены на основе базы данных, определяется поддержка и достоверность, а затем отбираются те из них, для которых эти показатели превышают заданное пороговое значение. Однако в большинстве случаев такое элементарное решение неприемлемо, поскольку число ассоциаций, которое при этом придется анализировать, слишком велико. Так, если выборка содержит всего 100 предметов, количество образуемых ими ассоциаций будет порядка 1031, а в реальных ситуациях (например, при анализе покупок в супермаркете) номенклатура учитываемых продуктов может достигать нескольких тысяч и более. Очевидно, что никаких вычислительных мощностей на такой расчет не хватит.
Поэтому на практике при поиске ассоциативных правил используют различные приемы, которые позволяют уменьшить пространство поиска до размеров, обеспечивающих приемлемые затраты машинного времени. Сейчас одним из наиболее распространенных является алгоритм a priori, основанный на понятии популярного набора (часто встречающийся предметный набор). Этот термин обозначает предметный набор, частота появления которого в общей совокупности транзакций превышает некоторый заранее заданный уровень.
Таким образом, алгоритм a priori включает два этапа:
– поиск популярных наборов;
– формулировка ассоциативных правил, удовлетворяющих заданным ограничениям по уровням поддержки и достоверности.
В Deductor Studio для решения задач ассоциации используется обработчик Ассоциативные правила. В нем реализован алгоритм a priori. Обработчик требует на входе два поля: идентификатор транзакции и элемент транзакции.
Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:
Алгоритмы ассоциативных правил
Обзор подходов для генерации ассоциативных правил. Характеристика методов генерации рекомендаций. Анализ процесса разработки метода определения закономерностей с ассоциативными правилами для генерации рекомендаций пользователем информационного портала.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | дипломная работа |
| Язык | русский |
| Дата добавления | 27.05.2013 |
| Размер файла | 2,7 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
В последнее время неуклонно растет интерес к методам «обнаружения знаний» в базах данных. Современные базы данных имеют очень большие размеры, достигающие гига и терабайтов, и тенденцию к дальнейшему увеличению, что вызвало потребность в разработке эффективных масштабируемых алгоритмов, позволяющих решать поставленные задачи за приемлемое время. Одним из популярных методов обнаружения знаний стали алгоритмы ассоциативных правил для нахождения различного рода закономерной.
Ассоциации — выявление закономерностей между связанными событиями. Примером такой закономерности служит правило, указывающее, что из события X следует событие Y. Такие правила называются ассоциативными.
Суть задачи заключается в определении часто встречающихся наборов объектов в большом множестве таких наборов. Данная задача является частным случаем задачи классификации. Первоначально она решалась при анализе тенденций в поведении покупателей в супермаркетах. Анализу подвергались данные о совершаемых ими покупках, которые покупатели складывают в корзину. Это послужило причиной второго часто встречающегося названия — анализ рыночных корзин.
Таким образом, в постановке решаемой задачи выявления закономерностей для генерации рекомендаций пользователям информационного портала необходимо ввести, прежде всего, набор исходных значений и параметров, хранимых в базе данных: номер транзакции ID, наименование товара P и соответствующее количество проданных единиц Np.
Результаты, полученные с помощью анализа рыночной корзины, позволяют оптимизировать ассортимент товаров и запасы, увеличивать объемы продаж за счет предложения клиентам сопутствующих товаров, а также влияют на размещение их в презентационном блоке информационного портала. Например, если в результате анализа будет установлено, что совместная покупка макарон и кетчупа является типичным шаблоном, то разместив эти товары на одном уровне просмотра, можно «спровоцировать» покупателя на их совместное приобретение.
При анализе этих данных интерес прежде всего представляет информация о том, какие товары предпочитают, в какие периоды времени разные группы пользователей. Такая информация позволяет более эффективно планировать закупку товаров, проведение рекламной кампании, экономить время.
Одной из наиболее распространённых задач анализа данных является определение часто встречающихся наборов объектов в большом множестве наборов. Впервые эта задача была предложена как поиск ассоциативных правил для нахождения типичных шаблонов покупок, совершаемых в супермаркетах, поэтому иногда ее еще называют анализом рыночной корзины. Решение задачи поиска ассоциативных правил, как и любой задачи, сводится к обработке исходных данных и получению результатов. Результаты, получаемые при решении данной задачи принято представлять в виде ассоциативных правил. В связи с этим в их поиске выделяют два этапа:
— нахождение всех частых наборов объектов.
— генерация ассоциативных правил из найденных частых наборов объектов.
Каждая транзакция представляет собой бинарный вектор, где:
Если ik элемент присутствует в транзакции, иначе:
Таким образом транзакция T содержит X, некоторый набор элементов из Е, если XT. Ассоциативным правилом называется импликация:
Правило XY имеет поддержку s (support), если s% транзакций из D, содержат:
Достоверность правила показывает какова вероятность того, что из X следует Y. Правило XY справедливо с достоверностью (confidence) c, если c% транзакций из D, содержащих X, также содержат:
В данной работе предлагается использовать алгоритм Apriori, ставший первым эффективным алгоритмом поиска частых множеств признаков, с учетом также принадлежности пользователя к заранее определенной группе. Алгоритм Apriori является поуровневым, использует стратегию поиска в ширину и осуществляет его снизу-вверх. В алгоритме используются две структуры данных: Ci — для хранения множества кандидатов в частые множества признаков длины i и Fi — для хранения частых множеств признаков длины i. Каждая структура имеет два поля — itemset, сохраняющее множество признаков, и support, которое хранит величину поддержки этого множества признаков.
В данном случае необходимо учесть возможность отслеживания потребительских привычек всех покупателей и использовать собранную информацию, чтобы предложить товары, которые их могут заинтересовать. К примеру, предложить фильмы, которые потребителю, возможно, понравятся, хотя раньше он покупал только книги. Аналогично некоторые сайты по продаже билетов на концерты анализируют, что пользователи посещали раньше, и анонсируют предстоящие концерты, которые могут быть им интересны. Таким образом, выявление закономерностей с использованием ассоциативных правил для генерации рекомендаций пользователям информационного портала является достаточно актуальной задачей, что также подтверждается экспериментальными исследованиями.
2. Анализ алгоритмов ассоциативных правил для создания рекомендации пользователям информационного портала и постановка задачи
2.1 Анализ алгоритмов ассоциативных правил
Многие предприятия накапливают большие объемы данных из повседневных операций. Например, огромным количеством данных, собираемых ежедневно в кассах, является информация о покупках клиентов. Таблица 2.1 показывает пример таких данных, известный как анализ рыночной корзины. Каждая строка в таблице соответствует транзакции, которая содержит уникальный идентификатор TID и набор элементов купленных данным клиентом. Продавцы заинтересованы в анализе данных, чтобы узнать о покупательском поведении своих клиентов. Такая ценная информация может быть использована для поддержки различных бизнес-приложений, таких как рыночное развитие, управление товаром и взаимоотношение с клиентами. Это всё называется анализ ассоциаций, которые позволяют обнаруживать интересные отношения, скрытые в больших по объёму выборках данных. Обнаруженные отношения могут быть представлены в виде ассоциативных правил или наборов часто используемых элементов. Например, следующее правило может быть извлечено из набора данных, показанных в таблице 2.1.
Таблица 2.1 — Пример транзакций рыночной корзины:
Хлеб, молоко, печенье
Молоко, хлеб, сметана, печенье
Хлеб, молоко, сметана
Правило <> Молоко > <> хлеб поясняет, что существует тесная связь между продажей молока и хлеба, многие клиенты, которые покупают молоко, также покупают и хлеб. Продавец может использовать этот тип правил для определения новых возможностей в продаже своей продукции потребителям.
Помимо данных потребительской корзины, ассоциативный анализ применим также к другим областям, как биоинформатика, медицинская диагностика, Web-mining и научный анализ данных. При анализе данных Земли, например, ассоциация модели, может выявить интересные связи между океаном, землёй, и атмосферными процессами. Такая информация может помочь ученым добиться лучшего понимания того, как различные элементы Земли взаимодействуют друг с другом. Хотя такие методы, представленные здесь, как правило, применяются на более широком спектре наборов данных, в иллюстративных целях.
Есть два ключевых вопроса, которые необходимо учитывать при применении ассоциации анализа данных потребительской корзины. Во-первых, обнаружение моделей из большого набора данных транзакций может занять много времени на вычисления. Во-вторых, некоторые из обнаруженных закономерностей потенциально ложные, поскольку они могут происходить случайным образом. Далее рассмотрим разъяснение основных принципов объединения анализа и алгоритмов, используемых для эффективного поиска таких закономерностей. А также оценим обнаружение закономерностей с целью предотвращения образования ложных результатов.
Ассоциативное правило — это выражение вида:
Где: a и b — множества значений атрибутов базы даннях. Ассоциативные правила имеют следующий вид: если (условие), то (результат), где условие — обычно не логическое выражение, а набор объектов из множества I, с которым связаны (ассоциированы) объекты, включенные в результат данного правила. Например, ассоциативное правило: «если (молоко, масло), то (хлеб)» означает, что если потребитель покупает молоко и масло, то он покупает и хлеб. Основным достоинством ассоциативных правил является их лёгкое восприятие человеком и простая интерпретация языками программирования. Однако, они не всегда полезны. Выделяют три вида правил:
— полезные правила — содержат действительную информацию, которая ранее была неизвестна, но имеет логическое объяснение. Такие правила могут быть использованы для принятия решений, приносящих выгоду;
— тривиальные правила — содержат действительную и легко объяснимую информацию, которая уже известна. Такие правила не могут принести пользу, потому что отражают или известные законы в исследуемой области, или результаты прошлой деятельности. Иногда такие правила могут использоваться для проверки выполнения решений, принятых на основании предыдущего анализа;
— непонятные правила — содержат информацию, которая не может быть объяснена.
Такие правила могут быть получены на основе аномальных значений, или сугубо скрытых знаний. Напрямую такие правила нельзя использовать для принятия решений, их необъяснимость может привести к непредсказуемым результатам.
Для лучшего понимания требуется дополнительный анализ. Ассоциативные правила строятся на основе частых наборов. Так правила, построенные на основании набора F, являются возможными комбинациями объектов, входящих в него. Например, для набора <масло, вода, орехи>, могут быть построены следующие правила:
— если (масло), то (вода); если (масло), то (орехи); если (масло), то (вода, орехи);
— если (вода), то (масло); если (вода), то (орехи); если (вода), то (масло, орехи).
Таким образом, количество ассоциативных правил может быть очень большим и трудновоспринимаемым для человека. К тому же, не все из построенных правил несут в себе полезную информацию. Для оценки их полезности вводятся следующие величины.
Поддержка (support) — показывает, какой процент транзакций поддерживает данное правило. Так как правило строится на основании набора, то, значит, правило имеет поддержку, равную поддержке набора F, который составляют X и Y:
Очевидно, что правила, построенные на основании одного и того же набора, имеют одинаковую поддержку, например, поддержка Supp(если (вода, масло), то (орехи) Supp(вода, масло, орехи) = 0,5.
Достоверность (confidence) — показывает вероятность того, что из наличия в транзакции набора X следует наличие в ней набора Y. Достоверностью правила является отношение числа транзакций, содержащих X и Y, к числу транзакций, содержащих набор Х:
Чем больше достоверность, тем правило лучше, причем у правил, построенных на основании одного и того же набора, достоверность будет разная, например:
— Conf(если (вода), то (орехи)) = 2/3;
— Conf(если (орехи), то (вода)) = 2/3;
— Conf(если (вода, масло), то (орехи)) = 1;
— Conf(если (вода), то (орехи, масло)) = 2/3.
Достоверность не позволяет определить полезность правила. Если процент наличия в транзакциях набора Y при условии наличия в нем набора Х меньше, чем процент безусловного наличия набора Y:
Вероятность случайно угадать наличие в транзакции набора Y больше, чем предсказать это с помощью правила. Для исправления такой ситуации вводится мера — улучшение.
Улучшение (improvement) — показывает, полезнее ли правило случайного угадывания. Улучшение правила является отношением числа транзакций, содержащих наборы X и Y, к произведению количества транзакций, содержащих набор Х, и количества транзакций, содержащих набор Y:
Например, impr(если (вода, масло), то (орехи) = 0,5/(0,5*0,5) = 2.
Если улучшение больше единицы, то это значит, что с помощью правила предсказать наличие набора Y вероятнее, чем случайное угадывание, если меньше единицы, то наоборот.
В последнем случае можно использовать отрицательное правило, правило, которое предсказывает отсутствие:
2.1.1 Алгоритм Apriori
Современные базы данных имеют очень большие размеры, достигающие гига- и терабайтов, и тенденцию к дальнейшему увеличению. И поэтому, для нахождения ассоциативных правил требуются эффективные масштабируемые алгоритмы, позволяющие решить задачу за приемлемое время. Одним из таких алгоритмов является алгоритм Apriori.
Для того, чтобы было возможно применить алгоритм, необходимо провести предобработку данных: во-первых, привести все данные к бинарному виду; во-вторых, изменить структуру данных. Обычный вид базы данных транзакций изображён в таблице 2.2:
Таблица 2.2 — Пример базы даннях транзакций:
Нормализованный вид изображён в таблице 2.3.
Таблица 2.3 — База данных после нормализации:
Количество столбцов в таблице равно количеству элементов, присутствующих в множестве транзакций D. Каждая запись соответствует транзакции, где в соответствующем столбце стоит 1, если элемент присутствует в транзакции, и 0 в противном случае. Заметим, что исходный вид таблицы может быть отличным от приведенного в таблице 2.3. Главное, чтобы данные были преобразованы к нормализованному виду, иначе алгоритм не применим. Кроме того, все элементы должны быть упорядочены в алфавитном порядке (если это числа, они должны быть упорядочены в числовом порядке).
Алгоритм Apriori работает в два этапа: на первом шаге необходимо найти часто встречающиеся наборы элементов, а затем, на втором, извлечь из них правила. Количество элементов в наборе будем называть размером набора, а набор, состоящий из k элементов, — k-элементным набором.
На первом шаге алгоритма подсчитываются 1-элементные часто встречающиеся наборы. Для этого необходимо пройтись по всему набору данных и подсчитать для них поддержку, т.е. сколько раз встречается в базе. Следующие шаги будут состоять из двух частей: генерации потенциально часто встречающихся наборов элементов (их называют кандидатами) и подсчета поддержки для кандидатов.
Описанный выше алгоритм можно записать в виде следующего псевдокода:
Опишем функцию генерации кандидатов. На это раз нет никакой необходимости вновь обращаться к базе данных. Для того, чтобы получить k-элементные наборы, воспользуемся (k-1)-элементными наборами, которые были определены на предыдущем шаге и являются часто встречающимися.
Исходный набор хранится в упорядоченном виде. Генерация кандидатов также будет состоять из двух шагов:
— объединение. Каждый кандидат Ck будет формироваться путем расширения часто встречающегося набора размера (k-1) добавлением элемента из другого (k-1)-элементного набора. Приведем алгоритм этой функции Apriorigen в виде небольшого SQL-подобного запроса:
— удаление избыточных правил. На основании свойства антимонотонности, следует удалить все наборы c Ck если хотя бы одно из его (k-1) подмножеств не является часто встречающимся.
После генерации кандидатов следующей задачей является подсчет поддержки для каждого кандидата. Очевидно, что количество кандидатов может быть очень большим и нужен эффективный способ подсчета. Самый тривиальный способ — сравнить каждую транзакцию с каждым кандидатом. Но это далеко не лучшее решение. Гораздо быстрее и эффективнее использовать подход, основанный на хранении кандидатов в хэш-дереве. Внутренние узлы дерева содержат хэш-таблицы с указателями на потомков, а листья — на кандидатов. Это дерево нам пригодится для быстрого подсчета поддержки для кандидатов.
Хэш-дерево строится каждый раз, когда формируются кандидаты. Первоначально дерево состоит только из корня, который является листом, и не содержит никаких кандидатов-наборов. Каждый раз, когда формируется новый кандидат, он заносится в корень дерева и так до тех пор, пока количество кандидатов в корне-листе не превысит некоего порога. Как только количество кандидатов становится больше порога, корень преобразуется в хэш-таблицу, становится внутренним узлом, и для него создаются потомки-листья. И все примеры распределяются по узлам-потомкам согласно хэш-значениям элементов, входящих в набор, и т.д. Каждый новый кандидат хэшируется на внутренних узлах, пока он не достигнет первого узла-листа, где он и будет храниться, пока количество наборов опять же не превысит порога.
Хэш-дерево с кандидатами-наборами построено, теперь, используя хэш-дерево, легко подсчитать поддержку для каждого кандидата. Для этого нужно ‘пропустить’ каждую транзакцию через дерево и увеличить счетчики для тех кандидатов, чьи элементы также содержатся и в транзакции, т.е:
На корневом уровне хэш-функция применяется к каждому элементу из транзакции. Далее, на втором уровне, хэш-функция применяется ко вторым элементам. На k-уровне хэшируется k-элемент. И так до тех пор, пока не достигнем листа. Если кандидат, хранящийся в листе, является подмножеством рассматриваемой транзакции, тогда увеличиваем счетчик поддержки этого кандидата на единицу.
После того, как каждая транзакция из исходного набора данных ‘пропущена’ через дерево, можно проверить удовлетворяют ли значения поддержки кандидатов минимальному порогу. Кандидаты, для которых это условие выполняется, переносятся в разряд часто встречающихся. Кроме того, следует запомнить и поддержку набора, она нам пригодится при извлечении правил. Эти же действия применяются для нахождения элементных наборов и т.д. После того как найдены все часто встречающиеся наборы элементов, можно приступить непосредственно к генерации правил. Извлечение правил — менее трудоемкая задача. Во-первых, для подсчета достоверности правила достаточно знать поддержку самого набора и множества, лежащего в условии правила. Тогда легко можно подсчитать достоверность. Это избавляет от нежелательного просмотра базы транзакций, который потребовался в том случае, если бы это поддержка была неизвестна.
Чтобы извлечь правило из часто встречающегося набора F, следует найти все его непустые подмножества. И для каждого подмножества s можно сформулировать правило:
В том случае, если достоверность правила:
conf * (s (F — s)) = supp(F) / supp(s)
— не меньше порога minconf.
Заметим, что числитель остается постоянным. Тогда достоверность имеет минимальное значение, если знаменатель имеет максимальное значение, а это происходит в том случае, когда в условии правила имеется набор, состоящий из одного элемента.
Все супермножества данного множества имеют меньшую или равную поддержку и, соответственно, большее значение достоверности. Это свойство может быть использовано при извлечении правил.
Если начнем извлекать правила, рассматривая сначала только один элемент в условии правила, и это правило имеет необходимую поддержку, тогда все правила, где в условии стоят супермножества этого элемента, также имеют значение достоверности выше заданного порога.
Для того, чтобы извлечь все правила используется рекурсивная процедура.
Важное замечание: любое правило, составленное из часто встречающегося набора, должно содержать все элементы набора.
2.1.2 Алгоритм AIS
Первый алгоритм поиска ассоциативных правил, называвшийся AIS, (предложенный Agrawal, Imielinski and Swami) был разработан сотрудниками исследовательского центра IBM Almaden в 1993 году. С этой работы начался интерес к ассоциативным правилам.
Узким местом в алгоритме apriori является процесс генерации кандидатов в популярные предметные наборы. Например, если база данных (БД) транзакций содержит 100 предметов, то потребуется сгенерировать:
Таким образом, вычислительные и временные затраты, которые нужны на их обработку, могут быть неприемлемыми. Кроме этого, алгоритм apriori требует многократного сканирования базы данных транзакций, а именно столько раз, сколько предметов содержит самый длинный предметный набор. Поэтому был предложен ряд алгоритмов, которые позволяют избежать генерации кандидатов и сократить требуемое число сканирований набора данных.
В алгоритме AIS кандидаты множества наборов генерируются и подсчитываются «на лету», во время сканирования базы данных.
2.1.3 Алгоритм SETM
Создание этого алгоритма было мотивировано желанием использовать язык SQL для вычисления часто встречающихся наборов товаров. Как и алгоритм AIS, SETM также формирует кандидатов «на лету», основываясь на преобразованиях базы данных. Чтобы использовать стандартную операцию объединения языка SQL для формирования кандидата, SETM отделяет формирование кандидата от их подсчета. Недостаток алгоритмов AIS и SETM — излишнее генерирование и подсчет слишком многих кандидатов, которые в результате не оказываются часто встречающимися. Для улучшения их работы был предложен алгоритм Apriori.
Работа данного алгоритма состоит из нескольких этапов, каждый из этапов состоит из следующих шагов:
Формирование кандидатов (candidate generation) — этап, на котором алгоритм, сканируя базу данных, создает множество i-элементных кандидатов (i — номер этапа). На этом этапе поддержка кандидатов не рассчитывается.
Подсчет кандидатов (candidate counting) — этап, на котором вычисляется поддержка каждого i-элементного кандидата. Здесь же осуществляется отсечение кандидатов, поддержка которых меньше минимума, установленного пользователем (min_sup). Оставшиеся i-элементные наборы называем часто встречающимися.
Рассмотрим работу алгоритма Apriori на примере базы данных D. Иллюстрация работы алгоритма приведена на рисунке 2.1. Минимальный уровень поддержки равен 3.
На первом этапе происходит формирование одноэлементных кандидатов. Далее алгоритм подсчитывает поддержку одноэлементных наборов. Наборы с уровнем поддержки меньше установленного, то есть 3, отсекаются. В нашем примере это наборы e и f, которые имеют поддержку, равную 1.
Оставшиеся наборы товаров считаются часто встречающимися одноэлементными наборами товаров: это наборы a, b, c, d. Далее происходит формирование двухэлементных кандидатов, подсчет их поддержки и отсечение наборов с уровнем поддержки, меньшим 3. Оставшиеся двухэлементные наборы товаров, считающиеся часто встречающимися двухэлементными наборами ab, ac, bd, принимают участие в дальнейшей работе алгоритма.
Рисунок 2.1 — Работа алгоритма SITM:
Если смотреть на работу алгоритма прямолинейно, на последнем этапе алгоритм формирует трехэлементные наборы товаров: abc, abd, bcd, acd, подсчитывает их поддержку и отсекает наборы с уровнем поддержки, меньшим 3. Набор товаров abc может быть назван часто встречающимся. Однако алгоритм Apriori уменьшает количество кандидатов, отсекая, которые заведомо не могут стать часто встречающимися, на основе информации об отсеченных кандидатах на предыдущих этапах работы алгоритма.
Отсечение кандидатов происходит на основе предположения о том, что у часто встречающегося набора товаров все подмножества должны быть часто встречающимися. Если в наборе находится подмножество, которое на предыдущем этапе было определено как нечасто встречающееся, этот кандидат уже не включается в формирование и подсчет кандидатов.Так наборы товаров ad, bc, cd были отброшены как нечасто встречающиеся, алгоритм не рассматривал набор товаров abd, bcd, acd.
При рассмотрении этих наборов формирование трехэлементных кандидатов происходило бы по схеме, приведенной в верхнем пунктирном прямоугольнике. Поскольку алгоритм априори отбросил заведомо нечасто встречающиеся наборы, последний этап алгоритма сразу определил набор abc как единственный трехэлементный часто встречающийся набор (этап приведен в нижнем пунктирном прямоугольнике).
Алгоритм Apriori рассчитывает также поддержку наборов, которые не могут быть отсечены априори. Это так называемая негативная область (negative border), к ней принадлежат наборы-кандидаты, которые встречаются редко, их самих нельзя отнести к часто встречающимся, но все подмножества данных наборов являются часто встречающимися.
2.2 Анализ алгоритмов рекомендаций
На сегодняшний день системы рекомендаций завоевывают все большую популярность, помогая пользователям из всего обилия информационных ресурсов выбирать действительно нужные и интересные. Они являются альтернативой существующим поисковым системам, так как предоставляют пользователю возможность обнаружить объекты, которые не могут быть найдены с помощью традиционных поисковых алгоритмов.
Много современных веб-сайтов используют веб-рекомендации для увеличения удобства пользования, удовлетворенности потребителя и коммерческой прибыли. Много алгоритмов были разработаны для генерации рекомендаций, применяя различные подходы статистического анализа данных к некоторой доступной им информации, например на характеристиках текущей страницы, продукта, веб-пользователя. Однако, до сих пор никакой алгоритм не использует преимущества всех доступных источников знаний и никакой алгоритм не имеет превосходства над всеми другими. Поэтому, потребность в гибридных подходах, которые комбинируют преимущества разных алгоритмов очевидна.
Для получения рекомендаций пользователю необходимо создать свой профиль предпочтений в рекомендательной системе путем оценки ряда объектов. В дальнейшем система сравнивает однотипные данные в профилях пользователей и автоматически предоставляет набор потенциально интересных ресурсов для каждого участника сети.
Рисунок 2.2 — Рекомендательный сервис:
2.2.1 Алгоритм рекомендаций Фурье-анализа
Алгоритм рекомендаций, основывается на сравнении профилей пользователей рекомендательных систем с помощью Фурье-анализа. В общем случае профиль предпочтений пользователя можно представить в виде изображения, которое формируется на основе интегральных пользовательских оценок объектов, соответствующих определенным интересам. Графически профиль пользователя можно представить следующим образом:
Рисунок 3.2 — Профиль пользователя:
Лучи L1, L2,…,Ln обозначают однозначно определенные интересы пользователя, а M(L1), M(L2), …, M(Ln) — интегральные оценки всех объектов, относящихся к определенному интересу. Данное изображение может быть описано некоторой функцией g. Аналогичным образом можно описать профиль другого пользователя — обозначим его как h.
Для сравнения и выявления степени похожести профилей целесообразно воспользоваться прямым и обратным преобразованием Фурье.
В данном случае изображение представляет собой двумерный сигнал, спектром которого также будет являться двумерный сигнал.
На основе степени похожести профилей предпочтений целесообразно предоставить каждому конкретному пользователю определенный набор рекомендательных групп. Группа, члены которой имеют наиболее схожие профили предпочтений с профилем конкретного пользователя, будет являться первоочередной при формировании рекомендаций. Группа экспертов, чьи рекомендации будут учитываться во вторую очередь, будет отличаться меньшей степенью похожести профилей участников на профиль конкретного пользователя. Соответственно, при переходе к группе экспертов, степень похожести профилей предпочтений которых будет наименьшей по сравнению с другими рекомендательными группами, значимость предоставляемых рекомендаций также будет наименьшей. При составлении списка рекомендаций учитывается значимость каждой рекомендации на основании того, от участника какой группы экспертов она получена — от более значимой к менее значимой.
Поскольку оцениваемое пользователем суммарное количество объектов будет постепенно увеличиваться, будет меняться профиль предпочтений и, соответственно, его изображение. Поэтому необходимо обеспечить возможность их повторного сравнения, как только будет изменен профиль пользователя или профиль входящего в одну из групп эксперта. Таким образом, возможны изменения составов групп рекомендателей и получаемых рекомендаций. Механизм работы алгоритма рекомендаций представлен на рисунке 2.3
Рисунок 2.3 — Механизм работы алгоритма рекомендаций:
2.2.2 Алгоритм рекомендаций, использованный в дипломе
В этом разделе представлен новый подход, объединяющий многие проанализированные алгоритмы. Подход использует центральную базу данных рекомендаций для того, чтобы сохранить рекомендации, получаемые из различных алгоритмов, и применяет методы обучения, чтобы непрерывно оптимизировать сохраненные рекомендации.
Оптимизация рекомендаций основана на том, насколько они полезны пользователям и веб-сайту, то есть, как охотно пользователи щелкают по ним, или сколько прибыли они приносят. Необходимостью для оптимизационного подхода является то, что популярность и уместность отдельных рекомендаций не всегда хорошо предсказывается системами рекомендаций. Информация о веб-сайте и пользователях представляется в базе данных рекомендаций в форме графов онтологии. Это позволяет семантически обогащать рекомендации и вводить знание из дополнительных источников. Это также помогает для адаптации системы к различным типам веб-сайтов.
Рисунок 2.4 — Архитектура системы рекомендаций:
На рисунке 2.4 изображена архитектура системы рекомендаций. Веб-сайт взаимодействует с веб-пользователем, предоставляет рекомендации и учитывает ответную реакцию. Веб-хранилище данных хранит информацию о контенте веб-сайта (например, продукты и каталог продукции), пользователях и журналах использования, сгенерированных веб-сервером или сервером приложений. Это служит источником информации для системы рекомендации алгоритмов, генераторов онтологии и позволяет оценивать OLAP данные использования и эффективности рекомендаций. База данных рекомендации хранит семантическую информацию в форме трех направленных нециклических графиков онтологии (для контента веб-сайта, веб-пользователей и времени) и рекомендации в форме правил. Набор генераторов онтологии ответственен за генерирование графов онтологии. Набор алгоритмов генерирует рекомендации, используя данные от веб-хранилища данных.
Графы онтологии и правила рекомендации могут также быть созданы и отредактированы вручную. Оптимизатор совершенствует базу данных рекомендации, основанную на обратной связи, полученной от веб-сайта, используя обучение. В нашей системе рекомендации отличаем цикл генерации и цикл оптимизации. Цикл генерации выполняется равномерно. Это включает генерирование/обновление онтологии и правил рекомендации, использующих информацию о контенте и недавнюю информацию об использовании от веб-хранилища данных. Цикл оптимизации выполняется непрерывно, выбирает и представляет рекомендации из базы данных. Кроме того, учитывается обратная связь, то есть пользовательские реакции на представленные рекомендации. Оптимизатор использует эту информацию, чтобы совершенствовать рекомендации в базе данных и влиять на выбор будущих рекомендаций.
2.3 Постановка задачи
В данной работе рассматривается процесс выявления закономерностей с использованием ассоциативных правил для генерации рекомендаций пользователям информационного портала. В данной работе предлагается использовать алгоритм Apriori, ставший первым эффективным алгоритмом поиска частых множеств признаков, с учетом также принадлежности пользователя к заранее определенной группе.
Постановка задачи формулируется следующим образом: необходимо разработать метод определения закономерностей с использованием ассоциативных правил для генерации рекомендаций пользователям информационного портала.
Таким образом, для решения поставленной задачи необходимо:
— проанализировать существующие подходы для генерации ассоциативных правил;
— проанализировать методы генерации рекомендаций;
— разработать метод определения закономерностей с использованием ассоциативных правил для генерации рекомендаций пользователям информационного портала.
3. Теоретические исследования
При поиске ассоциативных правил предполагалось, что все анализируемые элементы однородны. Возвращаясь к анализу рыночной корзины, это товары, имеющие совершенно одинаковые атрибуты, за исключением названия.
Дополним транзакцию информацией о том, в какую товарную группу входит товар, и построим иерархию товаров. Приведем пример такой группировки в виде иерархической модели.
Рисунок 3.1 — Пример продуктов питания
Пусть нам дана база транзакций D и известно, в какие группы входят элементы.
Тогда можно извлекать из данных правила, связывающие группы с группами, отдельные элементы с группами.
Например, если Покупатель купил товар из группы ‘Безалкогольные напитки’, то он купит и товар из группы ‘Молочные продукты’ или ‘Сок’ — ‘Молочные продукты’.
Эти правила носят название обобщенных ассоциативных правил. Обобщенным ассоциативным правилом называется импликация:
Где ни один из элементов, входящих в набор Y, не является предком ни одного элемента, входящего в X. Поддержка и достоверность подсчитываются так же, как и в случае ассоциативных правил. Введение дополнительной информации о группировке элементов в виде иерархии даст следующие преимущества:
— это помогает установить ассоциативные правила не только между отдельными элементами, но и между различными уровнями иерархии (группами);
— отдельные элементы могут иметь недостаточную поддержку, но в целом группа может удовлетворять порогу minsupport.
Для нахождения таких правил можно использовать любой из вышеназванных алгоритмов. Для этого каждую транзакцию нужно дополнить всеми предками каждого элемента, входящего в транзакцию. Однако, применение напрямую этих алгоритмов неизбежно приведет к следующим проблемам:
— элементы на верхних уровнях иерархии стремятся к значительно большим значениям поддержки по сравнению с элементами на нижних уровнях.
— с добавлением в транзакции групп увеличилось количество атрибутов и соответственно размерность входного пространства. Это усложняет задачу, а также ведет к генерации большего количества правил;
— появление избыточных правил, противоречащих определению обобщенного ассоциативного правила, например, ‘Сок’ — ‘Прохладительные напитки’. Очевидно, что практическая ценность такого ‘открытия’ нулевая при 100% достоверности.
Следовательно, нужны специальные операторы, удаляющие подобные избыточные правила.
Для нахождения обобщенных ассоциативных правил в работе использован специализированный алгоритм вычисления обобщенных ассоциативных правил, который устраняет вышеописанные проблемы и к тому же работает в 2-5 раз быстрее, чем стандартный Apriori.
Группировать элементы можно не только по вхождению в определенную товарную группу, но и по другим характеристикам, например по цене, бренду, рекомендациям друзей.
3.1 Алгоритм вычисления обобщенных ассоциативных правил
Как и все алгоритмы класса Apriori алгоритм вычисления обобщенных ассоциативных правил имеет свойство априорности. Это свойство также носит название анти-монотонности и служит для снижения размерности пространства поиска. Не имей в наличии такого свойства, нахождение многоэлементных наборов было бы практически невыполнимой задачей в связи с экспоненциальным ростом вычислений.
Свойству анти-монотонности можно дать и другую формулировку: с ростом размера набора элементов поддержка уменьшается, либо остается такой же.
Из всего вышесказанного следует, что любой k-элементный набор будет часто встречающимся тогда и только тогда, когда все его (k-1)-элементные подмножества будут часто встречающимися.
Все возможные наборы элементов из I можно представить в виде решетки, начинающейся с пустого множества, затем на 1 уровне 1-элементные наборы, на 2-м — 2-элементные и так далее. На k уровне представлены k-элементные наборы, связанные со всеми своими (k-1)-элементными подмножествами.
Рисунок 3.2 — Иллюстрированный набор элементов:
Рассмотрим рисунок 3.2, иллюстрирующий набор элементов:
Предположим, что набор из элементов имеет поддержку ниже заданного порога и, соответственно, не является часто встречающимся. Тогда, согласно свойству анти-монотонности, все его супермножества также не являются часто встречающимися и отбрасываются. Вся эта ветвь, начиная с
Как может показаться с первого взгляда, для вычисления обобщенных ассоциативных правил можно использовать любой алгоритм выявления ассоциативных правил, дополнив каждую транзакцию предками каждого элемента, входящего в транзакцию.
Однако такой метод напрямую очень неэффективен и использование его влечет за собой следующие проблемы:
— размер каждой транзакции увеличивается в зависимости от глубины дерева от нескольких десятков процентов до нескольких раз, и как следствие, увеличение времени вычисления и количества правил;
— появление избыточных правил, в которых в условии и в следствии находятся элемент и его предок. Примером такого правила может бать. Если покупатель купил Кефир, то он, скорее всего, захочет купить Молочные продукты. Совершенно ясно, что практическая ценность этого правила равна нулю при достоверности равной 100%.
Для решения этой проблемы может быть использование специального алгоритма, учитывающего всю специфику обобщенных ассоциативных правил. Процесс вычисления обобщенных ассоциативных правил можно разбить на несколько этапов:
— поиск часто встречающихся множеств элементов, поддержка которых больше чем заданный порог поддержки (минимальная поддержка);
— вычисления правил на основе найденных на предыдущем этапе часто встречающихся множеств элементов. Основная идея вычисления правил на основе часто встречающихся множеств заключается в следующем:
Если ABCD — это часто встречающееся множество элементов, то на основе этого множества можно построить правила:
Поддержка правила равна поддержке часто встречающегося множества. Достоверность правила вычисляется по формуле:
conf(X Y) = supp(X Y) / supp(X)
Правило добавляется к результирующему списку правил, если достоверность этого правила больше порога minconf.
Из результирующего списка правил удаляются все ‘неинтересные’ правила. На первом шаге алгоритма подсчитываются 1-элементные часто встречающиеся наборы. При этом элементы могут находиться на любом уровне таксономии. Для этого необходимо ‘пройтись’ по всему набору данных и подсчитать для них поддержку, то есть сколько раз встречается в базе. Следующие шаги будут состоять из двух частей: генерации потенциально часто встречающихся наборов элементов (их называют кандидатами) и подсчета поддержки для кандидатов.
Описанный выше алгоритм можно записать в виде следующего псевдокода:
Опишем функцию генерации кандидатов. Для того чтобы получить k-элементные наборы, воспользуемся (k-1)-элементными наборами, которые были определены на предыдущем шаге и являются часто встречающимися. Алгоритм генерации кандидатов будет состоять из двух шагов:
— Объединение. Каждый кандидат Ck будет формироваться путем расширения часто встречающегося набора размера (k-1) добавлением элемента из другого (k-1)-элементного набора. Приведем алгоритм этой функции в виде небольшого SQL-подобного запроса:
— удаление избыточных правил. На основании свойства анти-монотонности, следует удалить все наборы c Ck, если хотя бы одно из его (k-1) подмножеств не является часто встречающимся.
Для эффективного подсчета поддержки кандидатов можно использовать хэш-дерево. Хеш-дерево строится каждый раз, когда формируются кандидаты. Первоначально дерево состоит только из корня, который является листом, и не содержит никаких кандидатов-наборов. Каждый раз, когда формируется новый кандидат, он заносится в корень дерева и так до тех пор, пока количество кандидатов в корне-листе не превысит некоего порога.
Как только количество кандидатов становится больше порога, корень преобразуется в хеш-таблицу, т.е. становится внутренним узлом, и для него создаются потомки-листья. И все примеры распределяются по узлам-потомкам согласно хеш-значениям элементов, входящих в набор, и т.д. Каждый новый кандидат хешируется на внутренних узлах, пока он не достигнет первого узла-листа, где он и будет храниться, пока количество наборов опять же не превысит порога.
К базовому алгоритму можно добавить несколько оптимизаций, которые увеличат скорость работы базового алгоритма:
— целесообразно единожды вычислить множества предков для каждого элемента иерархии как для элемента нижнего уровня таксономии (лист дерева), так и для элемента внутреннего уровня.
— необходимо удалять кандидаты, содержащие элемент и его предок. Для реализации этой оптимизации рассмотрим следующие два определения:
Поддержка множества X, содержащего и элемент x и его предок x вычисляется по формуле:
supp * (X) = supp * (X-x)
Принимая во внимание это определение, будем удалять кандидаты, содержащие и элемент и его предок из списка кандидатов до начала процесса подсчета поддержки. Если Lk — это список часто встречающихся множеств, не содержащий множеств, включающих и элемент и его предок в одном множестве, то Ck+1 (список кандидатов, получаемых из Lk) также не будет содержать множеств, включающих и элемент и его предок.
Учитывая утверждение, данное в этом определении, будем удалять кандидатов, включающих и элемент и его предок, из списка кандидатов только на первой итерации внешнего цикла:
— нет необходимости в добавлении всех предков всех элементов, входящих в транзакцию. Если кокой-то элемент, у которого есть предок, не находится в списке кандидатов, то в списке элементов с предками он помечается как удаленный. Следовательно, из транзакции удаляются элементы, помеченные как удаленные, или производится замена этих элементов на их предков. К транзакции добавляются только не удаленные предки;
— не «пропускать» транзакцию через хэш-дерево, если ее мощность меньше чем мощность элементов, расположенных в хэш-дереве;
— целесообразно помечать транзакции как удаленные и не использовать их при подсчете поддержки на следующих итерациях, если на текущей итерации в эту транзакцию не вошел ни один кандидат.
Учитывая указанное выше, получаем следующий алгоритм:
3.2 Интеграция алгоритма рекомендаций с алгоритмом поиска ассоциативных правил
Алгоритм взаимосвязей или ассоциативных правил позволяет выявить часто встречающиеся сочетания элементов данных и использовать обнаруженные закономерности для построения прогноза, на основе выявленных закономерностей становится возможной выдача рекомендаций друзей для предложения потребителю определённых товаров.
Пример набора правил, формируемых подобным, алгоритмом приведен на рисунке 3.3. Предметная область — торговля велосипедами и связанными спортивными товарами. Для примера, первое правило говорит о том, что если в заказе присутствует держатель для велосипедной фляги и кепка, с высокой вероятностью будет приобретена и сама фляга.
Рисунок 3.3 — Пример набора правил, формируемых алгоритмом:
Когда подобный набор правил сформирован, его можно использовать, например, для формирования рекомендаций на основе круга общения потребителя. Скажем, покупателю кепки и подставки для фляги, предложат обратить внимание и на имеющиеся фляги опрелённой фирмы. Вопрос заключается в том, как сформировать подобные правила. Для выявления часто встречающихся наборов объектов будет использоваться модифицированный алгоритм Apriori. С помощью алгоритма вычисления обобщенных ассоциативных правил выделяются все группы часто приобретающихся вместе товаров и на основе мнений друзей потребителя, рассчитывается сумма баллов, которая сравнивается с рекомендуемым пороговым значением, где порог рассчитывается из среднего значения мнений. Если значение выше «порога», то прогноз получает значение «истина» и потребителю предлагаются рекомендации брендов и фирм этих товаров.
Правила рекомендации сгенерированы алгоритмами системы рекомндаций после проведения ассоциативного анализа и сохранены в базе данных. Алгоритм рекомендации может также предоставить начальный вес для каждого сгенерированного правила рекомендации от интервала [0..1]. В прототипной реализации мы определяем рекомендации продукта:
— подобие контента. Этот алгоритм рекомендации определяет для каждого продукта (EC) или страницы HTML (EDU) (узел контента) подобных продуктов, используя текстовый счет подобия TF/IDF;
— образцы последовательности. Продукты (EC) или страницы HTML (EDU), чаще всего следующие за другими продуктами/страницами в тот же сеанс пользователя, рекомендуются им;
— от элемента к элементу совместная фильтрация. (EC) Продукты, которые чаще всего появляются вместе в одной пользовательской корзине, рекомендуются друг для друга.
Если алгоритмы рекомендации генерируют правило, которое уже существует в таблице правила рекомендаций с различным весом, вес в таблице берет предпочтение по весу, предоставленному данным алгоритмом.
В работе исследованы два подхода к установке начальных весов недавно сгенерированных правил рекомендаций. В первом подходе просто обнуляем все начальные веса (ZeroStart). Второй использованный подход нормализует рекомендованные специфичные веса или относительные приоритеты для соответствующих контекстов. Когда несколько алгоритмов рекомендаций генерируют ту же самую рекомендацию, используется максимум их весов. Начальные веса, как ожидание, будут важны прежде всего для новых рекомендаций, так как веса для представленных рекомендаций непрерывно адаптируются.
Цель оптимизации состоит в том, чтобы скорректировать веса правил рекомендации таким способом, что более полезные рекомендации показывают чаще, чем менее полезный.
Однако алгоритм оптимизации также в состоянии работать с утилитой, определенной иначе, например как оборот продаж или прибыль, принесенная рекомендацией.
Каждый раз, когда веб-пользователь запрашивает веб-страницу с рекомендациями, несколько правил рекомендаций из базы данных выбираются и показываются. Такое событие называется представлением.
После этого веб-пользователь может предпринять некоторые меры относительно представленных рекомендаций. Например, пользователь может щелкнуть по рекомендации, купить рекомендуемый продукт, или проигнорировать рекомендацию. Каждому из этих действий соотносится действительное значение с данным, названным обратной связью. Оптимизатор оценивает все представления и корректирует веса участвующих правил рекомендациий согласно полученной обратной связи. Новые правила рекомендаций могут быть добавлены в базу данных в любое время. И онлайновая и офлайновая оптимизация возможна.
Есть два ключевых аспекта, которые должны учитываться в нашем алгоритме оптимизации. Во-первых, утилита отдельных рекомендаций может измениться в течение долгого времени, из-за различных интересов веб-пользователей. Алгоритм оптимизации должен быстро реагировать на существенные изменения в пользовательских интересах, не слишком остро реагируя на краткосрочные колебания. Кроме того, стоит обратить внимание на исследование и использование. С одной стороны хотелось бы представить рекомендации, которые являются преимущественно полезными согласно нашим современным знаниям. С другой стороны, необходимо бы учесть насколько хороши другие рекомендации, для которых наших современных знаний недостаточно.
3.3 Сравнительная оценка алгоритмов
На рисунке 3.4 видно, что число щелчков на правило рекомендации распределяется согласно закону подобному Zipfian (на рисунке только рекомендации как минимум со 100 просмотрами).
Рисунок 3.4 — Небольшое количество рекомендаций покупки в результате приносит большинство щелчков (EC, EDU):
Данные показывают, что относительно небольшой процент правил рекомендации приносит большинство щелчков. Это поддерживает нашу эвристику оптимизации, так как она показывает, что можно достигнуть полного улучшения пропускной способности, представляя самые успешные рекомендации чаще.
Для веб-пользователей, которые щелкнули по рекомендации, значение потребительской скорости преобразования составляет 8.55 %, то есть больше чем в четыре раза. Ассоциативный анализ данных покупки также показал, что 3.04 % всех купленных продуктов был сразу куплен после щелчка по рекомендации, и 3.43 % всех купленных продуктов рекомендовался в том же самом сеансе. Рисунок 3.5 показывает эффекты алгоритма оптимизации с точки зрения покупательного поведения, в отличие от неоптимизированного выбора рекомендаций. Неоптимизированный алгоритм использует начальные веса, предоставленные алгоритмы рекомендаций, чтобы выбрать рекомендации, и не делает никакой основанной на обратной связи оптимизации.
Данные показывают, что оптимизированный подход приводит к значимому увеличению числа дополнений к покупкам.
Рисунок 3.5 — Дополнительные рекомендации (ЕС):
Чтобы оценить эффективность различных алгоритмов оптимизации, сравним производительность только для награды и алгоритмов оптимизации штрафа награды с выбором рекомендаций, основанных на начальном весе, предоставленном алгоритмом рекомендации. В течение испытательного срока алгоритм выбора был выбран с равной вероятностью из одного из следующих:
Рисунок 3.6 — Пропускная способность различных алгоритмов оптимизации (ЕС):
Рисунок 3.6 показывает, что оптимизированные алгоритмы достигают более высоких пропускных способностей чем алгоритмы без оптимизации.
Алгоритм, который использует штраф так же как награду, смог достигнуть более высоких пропускных способностей чем алгоритм, который использует только награду.
С некоторой вероятностью выбирает случайные правила рекомендации для исследования.
Слишком быстрое устаревание (в нашем случае T=200) может оказать негативное влияние на оптимизацию.
Относительно маленькое улучшение алгоритма штрафа награды может быть приписано факту, что в наших приложениях успешные и неудачные рекомендации могут быть отчетливо разделены даже более простыми алгоритмами.
Алгоритм, который использовал нуль в качестве начальных весов для правил рекомендации, был протестирован на веб-сайте EDU.
Его пропускная способность была только на 4 % ниже чем одного из алгоритмов, который использовал рекомендации специфичных начальных весов.
Рисунок 3.7 — Пропускная способность сеанса политик выбора правил (EDU):
Рисунок 3.7 показывает пропускные способности сеанса (число сеансов, где по крайней мере одна рекомендация была принята разделенна на общее количество сеансов) для различных политик выбора представленных рекомендаций. Протестированы пять политик. Случайная политика использовалась для сравнения. В дополнение к политикам протестировали политики, только наследование и только одноуровневые элементы, которые использовались, чтобы моделировать сценарии, когда никакие непосредственно соответствующие рекомендации не могут быть найдены. Политика только наследование, игнорирует прямые рекомендации соответствия и берет только рекомендации от более высоких уровней иерархии. Политика только одноуровневые элементы ищет рекомендации среди одноуровневых элементов иерархии (узлы, имеющие общего родителя с текущим узлом), также игнорируя прямые соответствия. Согласно результатам испытаний, политика прямого соответствия является лучшей, чем прямую + родители. Однако, прямая + родительская политика в состоянии найти рекомендации даже в случаях, когда никакие непосредственно соответствующие рекомендации не доступны.
Поддержка ассоциативного правила (Association Rule Support)
Показатель, характеризующий качество ассоциативного правила. Определяется как отношение числа транзакций, в которых появляется как условие A , так и следствие B правила, к общему числу транзакций базы данных N :
Значение поддержки меняется от 0 (когда условие и следствие не встречаются вместе ни в одной транзакции) до 1 (когда условие и следствие во всех транзакциях появляются совместно). Иногда поддержку выражают в процентах (0 — 100%).
В общем случае поддержка является мерой надежности, с которой ассоциативное правило выражает ассоциативную связь между условием и следствием. Если поддержка S > 0,8, то связь сильная, а само правило заслуживает доверия. В случае, когда 0,5 < S < 0,8, ассоциативная связь средняя, а правило следует использовать с осторожностью. При S < 0,5 связь слабая, а ассоциативное правило является сомнительным.
Кроме этого, поддержка используется в качестве параметра алгоритмов поиска ассоциативных правил на основе частых предметных наборов (например, алгоритм Apriori). Задается значение минимальной поддержки (обычно, достаточно большое). Затем ищутся все предметные наборы, поддержка которых (отношение числа транзакций, где присутствует набор, к общему их числу) превышает минимальную. Такие предметные наборы называют частыми, или популярными, и на их множестве производится дальнейший поиск ассоциативных правил.
Следует отметить, что поддержка не является исчерпывающей характеристикой «силы» ассоциативного правила, поскольку не учитывает, сколько раз условие и следствие появляются в транзакциях независимо друг от друга. Поэтому для оценки правил вместе с поддержкой используют другую меру — достоверность.
В Loginom существует отдельный обработчик ассоциативные правила, который выявляет ассоциативные правила в транзакционных данных.
Подробнее о преимуществах ассоциативных правил в поиске закономерностей между связанными событиями можно узнать в статье «Введение в анализ ассоциативных правил». А в статье «Выявление обобщенных ассоциативных правил» приведены два метода вычисления обобщенных ассоциативных правил: базовый и улучшенный алгоритмы.
Применение ассоциативных правил в для оценки выбора управленческих решений
Ассоциативные правила — установление закономерностей между связанными событиями.
Впервые эта задача была предложена для нахождения типичных шаблонов покупок, совершаемых в супермаркетах, поэтому ее еще называют анализом рыночной корзины (market basket analysis).
Ассоциация имеет место в том случае, если несколько событий связаны друг с другом. Например, исследование, проведенное в компьютерном супермаркете, может показать, что 55 % купивших компьютер берут также и принтер или сканер, а при наличии скидки за такой комплект принтер приобретают в 80 % случаев. Располагая сведениями о подобной ассоциации, менеджерам легко оценить, насколько действенна предоставляемая скидка.
Если существует цепочка связанных во времени событий, то говорят о последовательности. Так, например, после покупки дома в 45 % случаев в течение месяца приобретается и новая кухонная плита, а в пределах двух недель 60 % новоселов обзаводятся холодильником.
Примеры применения ассоциативных правил:
выявление наборов товаров, которые в супермаркетах часто покупаются вместе или никогда не покупаются вместе;
J определение доли клиентов, положительно относящихся к нововведениям в их обслуживании;
•S определение профиля посетителей веб-ресурса;
S определение доли случаев, в которых новое лекарство оказывает опасный побочный эффект.
Пусть имеется база данных, состоящая из покупательских транзакций. Каждая транзакция — это набор товаров, купленных покупателем за один визит. Предметный набор — это непустое множество предметов, появившихся в одной транзакции.
Целью анализа является установление следующих зависимостей: если в транзакции встретился некоторый набор элементов X, то на основании этого можно сделать вывод о том, что другой набор элементов Y также должен появиться в этой транзакции. Установление таких зависимостей дает возможность находить очень простые и понятные правила.
Ассоциативное правило состоит из двух наборов предметов: условие (antecedent) и следствие (consequent).
«Если условие, то следствие»; X—>Y; «Из X следует Y».
Условие и следствие часто называются соответственно левосторонним (left-hand side — LHS) и правосторонним (right-hand side — RHS) компонентами ассоциативного правила.
Объективными показателями значимости ассоциативных таких правил являются поддержка и достоверность.
Поддержка — количество или процент транзакций, содержащих как условие, так и следствие. Правило X —> Y имеет поддержку S (support), если:
% > _ количество транзакций, содержащих X и У
общее количество транзакций
Достоверность ассоциативного правила (confidence) С представляет собой меру точности правила и определяется, как отношение количества транзакций, содержащих условие и следствие, к количеству транзакций, содержащих только следствие:
количество транзакций, содержащих X и Y
общее количество транзакций, содержащих X
Пример. Пусть 75 % транзакций, содержащих хлеб, также содержат молоко, а 3 % от общего числа всех транзакций содержат оба товара, тогда 75 % -это достоверность правила, а 3 % — это поддержка.
Если поддержка и достоверность достаточно высоки, можно с большой вероятностью утверждать, что любая будущая транзакция, которая включает условие, будет также содержать и следствие.
Сильные правила — правила, для которых значения поддержки и достоверности превышают заданный порог.
Алгоритмы поиска ассоциативных правил предназначены для нахождения всех правил вида X —> Y, причем поддержка и достоверность этих правил должны находиться в рамках некоторых наперед заданных границ, называемых соответственно минимальной и максимальной поддержкой и минимальной и максимальной достоверностью.
Границы значений параметров поддержки и достоверности выбираются таким образом, чтобы ограничить количество найденных правил. Если поддержка имеет большое значение, то алгоритмы будут находить правила, хорошо известные аналитикам или настолько очевидные, что нет никакого смысла проводить такой анализ. С другой стороны, низкое значение поддержки ведет к генерации огромного количества часто статистически необоснованных правил. Тем не менее большинство интересных правил находится именно при низком значении порога поддержки. Еще одним параметром, ограничивающим количество найденных правил, является максимальная мощность часто встречающихся множеств. Если этот параметр указан, то при поиске правил будут рассмат риваться только множества, количество элементов которых будет не больше данного параметра к, следовательно, любое найденное правило будет состоять не больше чем из к элементов.
Субъективные показатели значимости ассоциативных правил: Лифт, Левередж, Улучшение также могут использоваться для последующего ограничения набора рассматриваемых ассоциаций путем установки порога значимости, ниже которого ассоциации отбрасываются.
Лифт (lift) — это отношение частоты появления условия в транзакциях, которые также содержат и следствие, к частоте появления следствия в целом:
L(A В) = С(А В) / S(B).
Лифт является обобщенной мерой связи двух предметных наборов: при значениях лифта > 1 связь положительная, при 1 она отсутствует, а при значениях В)- S(A)S(B).
(), то правило не значимо.
Улучшение (improvement) показывает, полезнее ли правило случайного
5(Х^У) угадывания. ЦХ —> У) = — ——.
Если /(X —> У) > 1, это значит, что вероятнее предсказать наличие набора В с помощью правила, чем угадать случайно.
Поиск ассоциативных правил алгоритм Apriori (1994 г.)
1. Следует найти частые наборы.
Частый предметный набор — предметный набор с поддержкой больше заданного порога либо равной ему. Этот порог называется минимальной поддержкой.
При поиске частых наборов используется свойство антимонотонности: Если предметный набор Z не является частым, то добавление некоторого нового предмета А к набору Z не делает его более частым. Другими словами, если Z не является частым набором, то и набор Z оА также не будет являться таковым.
Данное полезное свойство позволяет значительно уменьшить пространство поиска ассоциативных правил.
- 2. На основе найденных наборов необходимо сгенерировать ассоциативные правила, удовлетворяющие условиям минимальной поддержки и достоверности.
- — Генерируются все возможные поднаборы 5.
- — Если поднабор ss является непустым поднабором s, то рассматривается ассоциативное правило R: ss —> (s — ss), где s — ss представляет собой набор s без поднабора 55. R будет считаться ассоциативным правилом, если будет удовлетворять условию заданного минимума поддержки и достоверности.
Данная процедура повторяется для каждого подмножества ss из s. Пример. Пусть имеется база транзакций, представленная в табл. 12.