Алгоритмы ассоциативных правил

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Введение

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

Ассоциации - выявление закономерностей между связанными событиями. Примером такой закономерности служит правило, указывающее, что из события X следует событие Y. Такие правила называются ассоциативными.

Суть задачи заключается в определении часто встречающихся наборов объектов в большом множестве таких наборов. Данная задача является частным случаем задачи классификации. Первоначально она решалась при анализе тенденций в поведении покупателей в супермаркетах. Анализу подвергались данные о совершаемых ими покупках, которые покупатели складывают в корзину. Это послужило причиной второго часто встречающегося названия - анализ рыночных корзин.

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

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

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

1. Цель работы

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

- нахождение всех частых наборов объектов.

- генерация ассоциативных правил из найденных частых наборов объектов.

Каждая транзакция представляет собой бинарный вектор, где:

t * [k] = 1

Если i_k элемент присутствует в транзакции, иначе:

t * [k] = 0

Таким образом транзакция T содержит X, некоторый набор элементов из Е, если XT. Ассоциативным правилом называется импликация:

Правило XY имеет поддержку s (support), если s% транзакций из D, содержат:

Достоверность правила показывает какова вероятность того, что из X следует Y. Правило XY справедливо с достоверностью (confidence) c, если c% транзакций из D, содержащих X, также содержат:

В данной работе предлагается использовать алгоритм Apriori, ставший первым эффективным алгоритмом поиска частых множеств признаков, с учетом также принадлежности пользователя к заранее определенной группе. Алгоритм Apriori является поуровневым, использует стратегию поиска в ширину и осуществляет его снизу-вверх. В алгоритме используются две структуры данных: C_i - для хранения множества кандидатов в частые множества признаков длины i и F_i - для хранения частых множеств признаков длины i. Каждая структура имеет два поля - itemset, сохраняющее множество признаков, и support, которое хранит величину поддержки этого множества признаков.

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

2. Анализ алгоритмов ассоциативных правил для создания рекомендации пользователям информационного портала и постановка задачи

2.1 Анализ алгоритмов ассоциативных правил

Многие предприятия накапливают большие объемы данных из повседневных операций. Например, огромным количеством данных, собираемых ежедневно в кассах, является информация о покупках клиентов. Таблица 2.1 показывает пример таких данных, известный как анализ рыночной корзины. Каждая строка в таблице соответствует транзакции, которая содержит уникальный идентификатор TID и набор элементов купленных данным клиентом. Продавцы заинтересованы в анализе данных, чтобы узнать о покупательском поведении своих клиентов. Такая ценная информация может быть использована для поддержки различных бизнес-приложений, таких как рыночное развитие, управление товаром и взаимоотношение с клиентами. Это всё называется анализ ассоциаций, которые позволяют обнаруживать интересные отношения, скрытые в больших по объёму выборках данных. Обнаруженные отношения могут быть представлены в виде ассоциативных правил или наборов часто используемых элементов. Например, следующее правило может быть извлечено из набора данных, показанных в таблице 2.1.

Таблица 2.1 - Пример транзакций рыночной корзины:

TID	Приобретенные покупки
1	Хлеб, молоко, печенье
2	Молоко, сметана
3	Молоко, хлеб, сметана, печенье
4	Хлеб, молоко, сметана

Правило {} Молоко > {} хлеб поясняет, что существует тесная связь между продажей молока и хлеба, многие клиенты, которые покупают молоко, также покупают и хлеб. Продавец может использовать этот тип правил для определения новых возможностей в продаже своей продукции потребителям.

Помимо данных потребительской корзины, ассоциативный анализ применим также к другим областям, как биоинформатика, медицинская диагностика, 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 - Пример базы даннях транзакций:

Номер транзакции	Наименование элемента	Количество
1001	А	2
1001	D	3
1001	E	1
1002	А	2
1002	F	1
1003	B	2
1003	A	2
1003	C	2

Нормализованный вид изображён в таблице 2.3.

Таблица 2.3 - База данных после нормализации:

TID	A	B	C	D	E	F	G	H	I	K
1001	1	0	0	1	1	0	0	0	0	0
1002	1	0	0	0	0	1	0	0	0	0
1003	1	1	1	0	0	0	0	0	1	0

Количество столбцов в таблице равно количеству элементов, присутствующих в множестве транзакций D. Каждая запись соответствует транзакции, где в соответствующем столбце стоит 1, если элемент присутствует в транзакции, и 0 в противном случае. Заметим, что исходный вид таблицы может быть отличным от приведенного в таблице 2.3. Главное, чтобы данные были преобразованы к нормализованному виду, иначе алгоритм не применим. Кроме того, все элементы должны быть упорядочены в алфавитном порядке (если это числа, они должны быть упорядочены в числовом порядке).

Алгоритм Apriori работает в два этапа: на первом шаге необходимо найти часто встречающиеся наборы элементов, а затем, на втором, извлечь из них правила. Количество элементов в наборе будем называть размером набора, а набор, состоящий из k элементов, - k-элементным набором.

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

Описанный выше алгоритм можно записать в виде следующего псевдокода:

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

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

- объединение. Каждый кандидат C_k будет формироваться путем расширения часто встречающегося набора размера (k-1) добавлением элемента из другого (k-1)-элементного набора. Приведем алгоритм этой функции Apriorigen в виде небольшого SQL-подобного запроса:

- удаление избыточных правил. На основании свойства антимонотонности, следует удалить все наборы c C_k если хотя бы одно из его (k-1) подмножеств не является часто встречающимся.

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

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

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

C_k T_i = C_k

На корневом уровне хэш-функция применяется к каждому элементу из транзакции. Далее, на втором уровне, хэш-функция применяется ко вторым элементам. На k-уровне хэшируется k-элемент. И так до тех пор, пока не достигнем листа. Если кандидат, хранящийся в листе, является подмножеством рассматриваемой транзакции, тогда увеличиваем счетчик поддержки этого кандидата на единицу.

После того, как каждая транзакция из исходного набора данных 'пропущена' через дерево, можно проверить удовлетворяют ли значения поддержки кандидатов минимальному порогу. Кандидаты, для которых это условие выполняется, переносятся в разряд часто встречающихся. Кроме того, следует запомнить и поддержку набора, она нам пригодится при извлечении правил. Эти же действия применяются для нахождения элементных наборов и т.д. После того как найдены все часто встречающиеся наборы элементов, можно приступить непосредственно к генерации правил. Извлечение правил - менее трудоемкая задача. Во-первых, для подсчета достоверности правила достаточно знать поддержку самого набора и множества, лежащего в условии правила. Тогда легко можно подсчитать достоверность. Это избавляет от нежелательного просмотра базы транзакций, который потребовался в том случае, если бы это поддержка была неизвестна.

Чтобы извлечь правило из часто встречающегося набора F, следует найти все его непустые подмножества. И для каждого подмножества s можно сформулировать правило:

s (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 - Профиль пользователя:

Лучи L₁, L₂,…,L_n обозначают однозначно определенные интересы пользователя, а M(L₁), M(L₂), …, M(L_n) - интегральные оценки всех объектов, относящихся к определенному интересу. Данное изображение может быть описано некоторой функцией 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, иллюстрирующий набор элементов:

I - {A, B, C, D}

Предположим, что набор из элементов имеет поддержку ниже заданного порога и, соответственно, не является часто встречающимся. Тогда, согласно свойству анти-монотонности, все его супермножества также не являются часто встречающимися и отбрасываются. Вся эта ветвь, начиная с {A, B}, отмечена желтым фоном. Использование этой эвристики позволяет существенно сократить пространство поиска.

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

Однако такой метод напрямую очень неэффективен и использование его влечет за собой следующие проблемы:

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

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

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

- поиск часто встречающихся множеств элементов, поддержка которых больше чем заданный порог поддержки (минимальная поддержка);

- вычисления правил на основе найденных на предыдущем этапе часто встречающихся множеств элементов. Основная идея вычисления правил на основе часто встречающихся множеств заключается в следующем:

Если ABCD - это часто встречающееся множество элементов, то на основе этого множества можно построить правила:

Поддержка правила равна поддержке часто встречающегося множества. Достоверность правила вычисляется по формуле:

conf(X Y) = supp(X Y) / supp(X)

Правило добавляется к результирующему списку правил, если достоверность этого правила больше порога minconf.

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

Описанный выше алгоритм можно записать в виде следующего псевдокода:

Опишем функцию генерации кандидатов. Для того чтобы получить k-элементные наборы, воспользуемся (k-1)-элементными наборами, которые были определены на предыдущем шаге и являются часто встречающимися. Алгоритм генерации кандидатов будет состоять из двух шагов:

- Объединение. Каждый кандидат C_k будет формироваться путем расширения часто встречающегося набора размера (k-1) добавлением элемента из другого (k-1)-элементного набора. Приведем алгоритм этой функции в виде небольшого SQL-подобного запроса:

- удаление избыточных правил. На основании свойства анти-монотонности, следует удалить все наборы c C_k, если хотя бы одно из его (k-1) подмножеств не является часто встречающимся.

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

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

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

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

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

Поддержка множества X, содержащего и элемент x и его предок x вычисляется по формуле:

supp * (X) = supp * (X-x)

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

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

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

- не «пропускать» транзакцию через хэш-дерево, если ее мощность меньше чем мощность элементов, расположенных в хэш-дереве;

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

Учитывая указанное выше, получаем следующий алгоритм:

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 показывает пропускные способности сеанса (число сеансов, где по крайней мере одна рекомендация была принята разделенна на общее количество сеансов) для различных политик выбора представленных рекомендаций. Протестированы пять политик. Случайная политика использовалась для сравнения. В дополнение к политикам протестировали политики, только наследование и только одноуровневые элементы, которые использовались, чтобы моделировать сценарии, когда никакие непосредственно соответствующие рекомендации не могут быть найдены. Политика только наследование, игнорирует прямые рекомендации соответствия и берет только рекомендации от более высоких уровней иерархии. Политика только одноуровневые элементы ищет рекомендации среди одноуровневых элементов иерархии (узлы, имеющие общего родителя с текущим узлом), также игнорируя прямые соответствия. Согласно результатам испытаний, политика прямого соответствия является лучшей, чем прямую + родители. Однако, прямая + родительская политика в состоянии найти рекомендации даже в случаях, когда никакие непосредственно соответствующие рекомендации не доступны.