Система коллаборативных рекомендаций туристических...
-
Upload
stone-kirk -
Category
Documents
-
view
56 -
download
6
description
Transcript of Система коллаборативных рекомендаций туристических...
1
Система коллаборативных рекомендаций туристических
достопримечательностей
Манаев Дмитрий Сергеевич, 545 группа
Научный руководитель:к.ф.-м.н., доцент каф. Информатики
Д.Ю. БугайченкоРецензент:
ст.преп. каф. Системного Программирования Н.A. Зонова
2
Цели работы
• Помочь пользователям запланировать путешествие , рекомендуя наиболее релевантные им туристические достопримечательности (места)
• Сервисы– Yelp– Facebook– Google Places
3
Описание сервисов
• Yelp, Facebook, TripAdvisor – много полезной информации, нет алгоритмов рекомендаций
• Foursquare – простые рекомендации по чекинам друзей
• Google Places - копия Yelp, рекомендации:– Социальный с Google +, мало используемая соц.
cеть, лучше Facebook и Twitter– По содержанию, на основе тэгов привязанных к
местам, громоздкий и не точный, не находит похожих “местных”
4
Постановка задач
• Проанализировать существующие решения и подходы к рекомендациям
• Провести анализ схожести – предложить подход к решению – построить матрицы схожести для пользователей и мест
• Реализовать генерацию рекомендации• Сравнить эффективность стандартных подходов с
нашим алгоритмом
5
Анализ схожести
Вычисление схожести User-User:• P - - мн во мест, U – - мн во пользователей• R = - матрица рейтингов• C - - мн во городов, где :• и -сравниваемые пользователи• - мн-во мест пользователя • - Евклидово расстояние• - Евклидова метрика• Расстояние между местными и путешественниками
уменьшено, благодаря уменьшению размерности пр-ва
6
Что такое Random Walk with Restart?
1*(1-a)
½ *(1-a)
½*(1-a)
1*(1-a)
t=0a
aпользователи, места
пользователь
a – вероятность вернуться в начальное состояние
7
Построение графа
• Связи в графе “Random Walk with Restart”– User Place (оценка пользователя)– User User (user-user similarity)– Place Place (item-item similarity)Формула итерации :
• - отражает вероятность перехода в элемент на шаге
• – это вектор нулей с единицией в элементе, с которого начинается алгоритм
• - матрица перехода
8
Особенности реализации• Метрики для расчета схожести пользователей и
мест:– Евклидова метрика– Корреляция Пирсона
• Метрики для оценки релевантности результатов– Precision and Recall
• Технологии – Java, Mahout (Taste) реализация системы
коллаборативных рекомендаций– С#, MSSQL Server 2008 сбор тестовых данных
9
Тестовые данные
• Два города– Лондон– Нью-Йорк
• ~ 102300 оценок • ~ 39000 жителей• ~ 5000 мест• ~ 370 путешественников
10
Методика оценки
Точность и охват (Precision and Recall) можно представить в виде следующих формул соответственно:
и • - это кол-во релевантных(рейтинг >= 3)
среди выбранных • - это кол-во всех выбранных • – это кол-во релевантных
11
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10
0.2
0.4
0.6
0.8
1
1.2
Precision/Recall
Item EuclideanItem PearsonUser EuclideanUser PearsonRWR EuclideanRWR Pearson
Recall
Prec
isio
n
12
Результаты
• Проанализированы существующие решения и подходы к рекомендациям
• Проведен анализ схожести• Реализована генерация рекомендаций• Сделано сравнение с стандартными
коллаборативными алгоритмами на собранных тестовых данных
13
Метрика оценки
1.00 0.97 0.93 0.90 0.86 0.830
102030405060708090
100
Recall 0,5
Precision
1 0.97 0.94 0.91 0.85 0.75 0.60
102030405060708090
100
Recall 0,6
Precision
10.96
0.940.92 0.9
0.880.85
0.83 0.8 0.70.66 0.4
0.120
1020304050607080
Recall 0,9
Precision
10,95
0,92 0,90,85
0,820,79
0,770,71
0,660,59
0,440,36 0,3
0,120,04 -
0
10
20
30
40
50
60
Recall 1,0
Precision