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

1. МЕТОД СКОЛЬЗЯЩЕГО КОНТРОЛЯ ДЛЯ ОЦЕНКИ КАЧЕСТВА РЕКОМЕНДАТЕЛЬНЫХ ИНТЕРНЕТ-СЕРВИСОВ

МЕТОД СКОЛЬЗЯЩЕГО КОНТРОЛЯ
ДЛЯ ОЦЕНКИ КАЧЕСТВА
РЕКОМЕНДАТЕЛЬНЫХ ИНТЕРНЕТСЕРВИСОВ
А.Ю. Каминская, Р.А. Магизов
Научный руководитель – Д.И. Игнатов
Государственный университет – Высшая школа экономики, Москва,
Россия
2010

2. Содержание

• Постановка задачи
• Мотивация
• Примеры моделей рекомендательных систем
– User-based RS
– Item-based RS
Выбор меры (метрики) сходства
Методика сравнения
Данные MovieLens и Yahoo
Результаты
Выводы и дальнейшая работа

3. Постановка задачи

• Зная предпочтения конкретного
пользователя и остальных, выдать ему
релевантную рекомендацию
• Оценка (проверка) качества рекомендаций

4. Мотивация

• Существует огромное количество РС
• Требуются эффективные алгоритмы
– Время выполнения
– Качество рекомендаций
• Количество ошибок и полнота
рекомендаций

5. User-based RS

• целевой пользователь u0
I
• u0 - предметы, которые он оценивал
• sim u 0 , u - сходство с пользователем u
- top-n ближайших к
N u0 u | sim u0 , u
нему соседей, n определяет
• N u0 | i u | i u I & u N u0 - пользователи из N u0 ,
которые оценили предмет i
• rui - оценка предмета i пользователем u
• предсказанная системой оценка для целевого пользователя:
rˆu0i
u , u r
sim
u N u0 |i
0
ui
u , u
sim
u N u0 |i
0

6. Item-based RS

целевой пользователь u0
I
u0 - предметы, которые он оценивал
sim i, j - сходство товара i с товаром j
N i j | sim i, j - top-n ближайших к нему
товаров, top-n определяет
• N i | u0 j | j u0I & i u0I & j N i - для u0
• rui - оценка предмета i пользователем u
• предсказанная системой оценка для целевого
пользователя:
rˆu0i
i, j r
sim
j N i|u 0
u0 j
i, j
sim
j N i|u 0

7. Пример

V.M.
4.0
3.0
0.0
4.0
SKY
0.5
4.0
4.0
3.5
3.5×0.5=1.75
4.5
OLA
0.5
4.5
4.0
3.0
3.0×0.5=1.5
4.0
GRY
0.94
4.0
2.5
1.0
1.0×0.94=0.94
3.5
IDI
0.87
2.0
2.5
3.0
3.0×0.87=2.6
1.5
1.75 1.5 2.6 0.94
0.5 0.5 0.87 0.94
6.79
2 .4 2 .5
2.81
ВО «Планета»
«Планета»
Е. Гришковец.
Рассказы.
ВО Рей Бредбери.
Рассказы.
Рей Бредбери.
и наказание»
ВО Преступление
наказание»
«Преступление и
Маргарита»
ВО «Мастер и
Маргарита»
«Мастер и
Сходство
Пользователь
User-based RS

8. Выбор меры (метрики) сходства

• Сходство, основанное на расстоянии:
– Евклида
– Хемминга
d ( x, y)
x y
i
2
i
i
d ( x, y )
1
s
1
1 d
xi y i
• Корреляция как сходство:
– коэффициент Пирсона
• Косинусная мера cos( x, y)
• Коэффициент Жаккара
x, y
x y
J ( X ,Y )
X Y
X Y

9. Корреляция Пирсона

x x y y
• pearson
x x y y
i
i
i
2
2
i
i
i
i
• Недостатки
– не определена на векторах с постоянными
значениями: (4,4,4,...,4)
– теряются рекомендации
a=(0,5,5,4)
b=(0,4,5,0)

10. Методика сравнения

• Метрики качества: точность и полнота
рекомендаций
• Скользящий контроль (кросс-валидация)

11. Точность и полнота

• Полнота – число релевантных
рекомендаций к числу всех выбранных
пользователем товаров
recall
| rn (u ) u I |
uI
• Точность – число релевантных к числу всех
рекомендаций
I
| rn (u ) u |
precision
rn (u )

12. Скользящий контроль

• Разбиение на тестовую и обучающую выборки:
U Utraining Utest , где Utraining Utest
• Сокрытие признаков для тестирования рекомендаций: I hidden I
• Вычисление точности и полноты для u U test
на признаках i I hidden :
recall
| rn (u ) u I I hidden |
u I I hidden
80%
| rn (u ) u I I hidden |
precision
rn (u ) I hidden
20%

13. Точность и полнота: раскрытие неопределенностей

recall
| rn (u ) u I I hidden |
u I I hidden 0 recall 1
u I I hidden
| rn (u ) u I I hidden |
precision
rn (u ) I hidden
rn (u) I hidden 0 :
u I 0 precision 1
else
precision 0

14. Алгоритм

• Параметры:
– test% - размер тестового множества
– hidden% - размер скрытого множества признаков
– p – число повторений разбиения на тестовое и обучающее
множество
– q – число повторений разбиения на оцененное и неоцененное
множества признаков
• Выход: средние значения точности и
полноты по множеству Utest и Ihidden

15. Данные MovieLens и Yahoo

• MovieLens 100K dataset:
– 943 пользователя
– 1,682 фильма
– Каждый оценил как минимум 20 фильмов,
всего 100,000 оценок
• Yahoo binary dataset:
– 2,000 фирм
– 3,000 рекламных словосочетаний
– 92,345 ненулевых ячеек

16. Результаты

Зависимость точности от количества скрытых признаков
0,6
0,5
Точность
0,4
0,3
User-based
Item-based
0,2
0,1
0
0
2
4
6
8
10
12
Количество скрытых признаков,%
14
16
18
20

17. Результаты

Зависимость полноты от количества скрытых
признаков
0,7
0,6
Полнота
0,5
0,4
User-based
0,3
Item-based
0,2
0,1
0
0
2
4
6
8
10
12
14
Количество скрытых признаков,%
16
18
20

18. Результаты

Зависимость точности и полноты от числа соседей
0,7
0,6
0,5
0,4
Точность
0,3
Полнота
0,2
0,1
0
0
10
20
30
40
число соседей
50
60
70
80

19. Результаты

Зависимость точности и полноты от размера
тестового множества для метода user-based
0,7
0,6
Меры качества
0,5
0,4
Precision
0,3
Recall
0,2
0,1
0
0
10
20
30
40
50
60
Размер тестового множества, %
70
80
90

20. Результаты

Зависимость точности и полноты от количества
скрытых признаков для метода user-based
0,6
0,5
Меры качества
0,4
0,3
Precision
Recall
0,2
0,1
0
0
10
20
30
40
Количество скрытых признаков, %
50
60

21. Результаты

Зависимость точности и полноты от размера
тестового множества для метода item-based
0,7
0,6
Мера качества
0,5
0,4
Precision
0,3
Recall
0,2
0,1
0
0
10
20
30
40
50
60
Размер тестового множества, %
70
80
90

22. Результаты

Зависимость точности и полноты от количества
скрытых признаков для метода Item based
0,6
Меры качества
0,5
0,4
0,3
Precision
Recall
0,2
0,1
0
0
10
20
30
40
Количество скрытых признаков, %
50
60

23. Выводы и дальнейшая работа

• Предложенная методика позволяет оценить
качество работы рекомендательной системы вне
зависимости от выбора метода
• По-видимому, впервые в экспериментах
исследуется точность и полнота в зависимости от
количества скрытых признаков
• Для сравнения методов необходимо проведение
аналогичных экспериментов для более
совершенных моделей РС, например, основанных
на бикластеризации

24. Спасибо за внимание!