Метод скользящего контроля для оценки качества рекомендательных интернет-сервисов

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

Метод скользящего контроля для оценки качества рекомендательных интернет-сервисов

Д.И. Игнатов

А.Ю. Каминская

Р.А. Магизов

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

Введение

Современному Интернет-пользователю довольно часто приходится сталкиваться с рекомендательными системами. Например, приобретая книгу X в Интернет-магазине, пользователь такой системы получает рекомендации вида "другие пользователи вместе с книгой X приобрели также книги Y и Z". Также существует множество сервисов для рекомендации пользователю интересных сайтов, известных как сервисы социальных закладок. Нетехнологичным способом получения рекомендаций можно назвать совет друзей и знакомых. С ростом числа вещей, для выбора которых вам нужна рекомендация, мнения знакомых становится недостаточно, они могут просто не знать о новинках. В этой затруднительной ситуации помогает так называемая коллаборативная фильтрация [Golberg et al., 1992]. Методы рекомендательных систем, основанные на коллаборативной фильтрации, часто работают по довольно простой схеме. Они просматривают большую группу людей, находят тех из них, предпочтения которых близки к вашим, а затем создают список выбранных ими вещей и ранжируют его, в итоге предлагая вам N верхних предметов такого списка. Другим менее очевидным, но востребованным приложением является рекомендация словосочетаний в системах контекстной рекламы, где фирмы приобретают рекламные словосочетания, по которым поисковые системы могут находить их и выдавать рекламу на такой запрос. алгоритм пользователь синтетический

Существующие модели рекомендательных систем

В нашей работе представлены две группы методов, ставших классическими в рассматриваемой области: user-based (основанные на сходстве пользователей) и item-based (основанные на сходстве признаков) (см. [Badrul et al., 2000]). Ключевым для работы этих методов является понятие сходства (математически это может быть мера Жаккара, корреляция Пирсона, мера косинусов и т.п.). Исходные данные представлены объектно-признаковыми матрицами, в которых столбцам соответствуют признаки (товары), а строкам объекты (пользователи). На пересечении строк и столбцов записаны 1 или 0, которые означают факт покупки или ее отсутствие. Также значениями ячеек таблицы могут быть рейтинги или оценки товаров, например, фильмов, поставленные пользователями.

Рекомендации, основанные на сходстве пользователей (User-based)

В методах группы user-based сходство ищется между пользователями и в качестве рекомендаций пользователю u0 выдается n самых часто покупаемых товаров k наиболее похожими на него покупателями. Введем обозначения: u0 - "целевой" пользователь, u0I - предметы, которые он оценивал, sim(u0, u)- сходство пользователя u0 с пользователем u. В нашей работе для подсчета сходства мы использовали коэффициент корреляции Пирсона. Определим множество ближайших соседей (соседство) для целевого пользователя по формуле:

.

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

.

Обозначив оценку предмета i пользователем u через rui, получаем итоговую формулу для предсказанной оценки:

.

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

Рекомендации, основанные на сходстве признаков (Item-based)

Идея метода item-based аналогична идее вышеописанного метода user-based, однако сходство уже ищется по признакам, то есть по предметам. Введем обозначения: u0 - "целевой" пользователь, u0I - предметы, которые он оценивал, sim(i,j) - сходство товара i с товаром j. Определим соседство для предмета i аналогично тому, как определяли его для целевого пользователя:

.

Это top-k ближайших к i товаров, top-k определяет . Чтобы предсказать оценку целевому пользователю, нужно сравнивать те предметы, которые он оценивал, с теми, которые нет. Поэтому "уточним" формулу для соседства в отношении к целевому пользователю:

.

Обозначим оценку предмета i пользователем u, таким образом, итоговая формула имеет вид:

.

Далее ранжируем оценки по убыванию и выдаем первые n в качестве рекомендаций.

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

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

Меры сходства

Чтобы определить сходство между объектами или признаками, используют различные меры (метрики) сходства. Обычно эти величины принимают значения от 0 до 1 (при абсолютном сходстве). Рассмотрим некоторые из таких метрик.

Сходство, основанное на расстоянии

Для определения сходства можно сначала вычислить расстояние одним из способов:

Евклидово расстояние.

Расстояние Хемминга.

Эта метрика применяется для бинарных данных. Расстояние в данном случае равно количеству разных значений координат двух векторов.

Для выбранного расстояния сходство часто ищется по формуле:

.

Вернемся к метрике Хемминга. Поскольку d может принимать только натуральные значения и 0, максимальное значение s равняется 1 (при нулевом расстоянии), но уже при d = 1 значение s = 1/2, что является очевидным недостатком: если имеется два 100-мерных бинарных вектора, у которых различие лишь в одной из координат, то согласно формуле получаем, что они сходны лишь наполовину. Такой "несглаженный" характер значений сходства можно видеть на графике (рис.1):

Рис.1. Зависимость сходства от расстояния Хемминга

Корреляции как сходства

Для определения сходства существует несколько десятков разных мер. Например, косинусная мера или коэффициент Жаккара.

Методика оценивания качества рекомендаций

В этой работе мы предлагаем методику оценки качества рекомендаций, выдаваемых такими системами. Пусть исходные данные представлены объектно-признаковой таблицей, бинарное отношение T UЧI показывает, совершил ли пользователь uU покупку iI, что выражается как uTi. Для оценки качества рекомендаций в терминах точности и полноты можно применить подход, использующий разбиение исходной выборки (множество U) на два подмножества: тестовое Utest и обучающее Utraining. Размер тестового множества, как правило, меньше размера обучающего, например, 20% и 80% соответственно. Полнота и точность поиска оценивается на тестовой выборке. Каждый элемент u тестовой выборки Utest в свою очередь разбивается на две части, на оцененные признаки Ivisible и неоцененные Ihidden, т.е. такие, которые мы намеренно скрываем. Отметим, что в существующей научной литературе отношение размеров Ivisible и Ihidden не обсуждается. Далее, например, алгоритм рекомендаций по пользователям использует сходство объектов из тестовой и обучающей выборки для формирования рекомендаций. Каждый пользователь из Utest получает рекомендации в виде множества фиксированного размера rn(u)={i1,i2,…,in}. Далее точность и полнота вычисляются следующим образом:

,

,

где uI - множество всех купленных пользователем u товаров из I. Значения этих мер вычисляются для каждого посетителя и усредняются. Эксперимент проводится для разбиения исходной выборки на тестовое и обучающее множество несколько раз, например, 100. Значения мер вновь усредняются. Помимо этого существует возможность отбора признаков для множества Ihidden скрытых признаков, процедура разбиения выполняется случайным образом, но необходимо задавать их долю, например, 20%. Идея метода оценки позаимствована из машинного обучения, и носит название скользящего контроля (cross-validation), но в случае рекомендательных систем претерпевает ряд модификаций. Нами использована модификация метода, называемая m-кратный скользящий контроль, идея которого состоит в том, что искомая выборка разбивается на m подмножеств объектов, каждое из которых затем используется в качестве тестовой выборки, а оставшиеся - в качестве обучающей. В дополнение к стандартным способам вычисления точности и полноты мы предлагаем нетрадиционные варианты раскрытия неопределенностей, возникающих при их оценке. Если , то . Если и то , иначе

Эксперименты проведены на наборах данных MovieLens о рейтингах фильмов и синтетических наборах данных, сгенерированных нами.

Результаты экспериментов

Мы провели серию экспериментов на наборе данных рейтингов фильмов, в котором представлено 1682 фильма, 943 пользователя, каждый из которых оценил не менее 20 фильмов. Все эксперименты проведены на компьютере с процессором Intel Core 2 Duo 2.0 Гц, 3МБ ОП, под управлением Windows Vista. Алгоритмы реализованы на языке Python 2.6. Мы приводим результаты эксперимента по исследованию зависимости точности (рис.2) и полноты (рис.3) поиска от количества скрываемых признаков для указанных данных (применялся 10-кратный скользящий контроль при фиксированном количестве соседей 10).

Рис.2. Зависимость точности от числа скрытых признаков

Рис.3. Зависимость полноты от числа скрытых признаков

Как видим по точности поиска методы практически одинаково себя ведут, а по полноте в диапазоне от 1 до 10 скрытых признаков сходство по пользователям работает точнее. Также мы провели аналогичные эксперименты на наборе данных рейтингов фильмов, в которых поэтапно скрывали признаки от 1% до 20%. На графиках (рис.4, рис.5) для этих экспериментов метод Item-based показывает лучшие результаты только при скрывании малого количества признаков (~1%). В дальнейшем его показатели значительно ухудшаются, тогда как User-based ведет себя достаточно стабильно, более того, начиная с 6-7% полнота начинает возрастать.

Результаты по влиянию количества соседей и размера тестовой выборки мы приводим для синтетического набора данных состоящего из 20 объектов и 20 признаков по диагонали которого расположено четыре прямоугольника из единиц размером 5x5.

Рис.4. Зависимость точности от числа соседей

Рис.5. Зависимость полноты от числа соседей

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

Заключение

Предложенная методика оценки качества рекомендательных Интернет-сервисов позволяет сравнивать методы рекомендательных систем и настраивать их параметры. В ходе экспериментов было установлено, что классические методы группы user-based ведут себя лучше с точки зрения точности и полноты поиска при количестве скрытых признаков около 10 на реальных данных. Данная методика также позволяет сравнивать любые другие методы поиска рекомендаций, в том числе и основанные на алгоритмах бикластеризации [Ignatov et al., 2008], [Игнатов и др., 2008]. Сравнительные исследования этой группы методов представляют дальнейшее направление развития нашей работы.

Список литературы

1. [Игнатов и др., 2008] Игнатов Дмитрий Игоревич, Кузнецов Сергей Олегович. Методы разработки данных (Data Mining) для рекомендательной системы Интернет-рекламы.// Труды одиннадцатой национальной конференции по искусственному интеллекту с международным участием, 2008. Т. 2. № КИИ-2008.

2. [Сегаран, 2008] Тоби Сегаран. Программируем коллективный разум, СПб.: Символ-плюс, 2008.

3. [Badrul et al., 2000] Badrul M. Sarwar, George Karypis, Joseph A. Konstan, John Riedl, "Analysis of recommendation algorithms for e-commerce", ACM Conference on Electronic Commerce, 2000.

4. [Golberg et al., 1992] David Goldberg, David A. Nichols, Brian M. Oki, Douglas B. Terry. Using Collaborative Filtering to Weave an Information Tapestry. Communications of the ACM , volume 35(12), 1992.

5. [Ignatov et al., 2008] Ignatov, Dmitry I., Kuznecov, Sergey Olegovich. Concept-based Recommendations for Internet Advertisement. // Proceedings of the Sixth International Conference on Concept Lattices and Their Applications, 2008.

Размещено на Allbest.ru