четверг, 26 сентября 2013 г.

Рекомендательный движок


Задача

Предположим есть такая задача. Группа пользователей, каждому показываются фотографии смартфонов и он нажимает кнопку like/dislike. Надо на основании цепочки оценок угадывать понравится ли следующая фотка или нет на основании оценок других пользователей которые на нее посмотрели.
Например: пользователи оценивают фото на основании критериев

  1. операционная система - Andriod/iOS
  2. цвет - черный/белый
есть 4 группы пользователей 
  1. те кто лайкают белый iOS
  2. те кто лайкают черный iOS
  3. те кто лайкают белый Andriod
  4. те кто лайкают черный Andriod
При это делают они это не со 100% вероятностью. Иногда промахиваются, иногда им нравится картинка на экране и они лайкают чуждый им цвет. 

Как можно решать

Простейшее решение схематически выглядит так
для множества всех картинок строим бинарный вектор
0100010101100010100001101110010100010101001010101000111111001001010
где 1 - картинка понравилась 0 - не понравилась.
Далее  ищем пользователя у которого меньше всего расхождений, но который уже оценил картинку мнение о которой мы хотим предсказать и далее берем его мнение как вероятный ответ. Для верности можно взять скажем не одного, а пятерых пользователей и пусть ответ будет их усредненной оценкой.
Такой метод очень хорош, но есть проблема - если картинок и пользователей много, а ответ надо давать быстро то посчитать это сразу либо тяжело, либо почти не возможно. Ситуация еще несколько осложняется если вкусы пользователей могут со временем меняться и нельзя скажем раз и навсегда подобрать группы людей с похожими вкусами и дальше просто "списывать" оценки.
Тут можно хитрить рассчитывая оценку заранее. Но на объемах скажем всего в 10000 картинок и 10000 пользователей требуется все равно довольно много вычислений. 

Вариант решения

Есть другой вариант решения. Я его алгоритмически не пробовал, но кажется что должно работать. 
На основе оценок выявляем шаблоны поведения пользователей. Т.е. группируем пользователей которые ставят одни и те же оценки одним и тем же картинкам и делаем предположение что эти пользователи любят определенное свойство картинки, (например черный цвет). Далее можно предположить, что если несколько пользователей из этой группы поставили лайк картинке то картинка этим свойством обладает и соответственно должна понравится другим пользователям которые картинку не видели, но тоже любят черный цвет. 
Чем этот алгоритм лучше - он требует сравнительно долгих вычислений только при определении групп пользователей - любителей свойства. Поскольку вкусы меняются не очень часто - пересчитывать можно не чаще чем раз в несколько дней. 
Что тут еще интересно - алгоритм позволяет выявлять свойства картинок и вкусы людей. Если скажем применить его к базе товаров - тех же смартфонов, то можно достаточно четко определить какими свойствами с точки зрения потребителя товар обладает. Останется только потом этим свойствам дать нормальные имена 
  1. красивый корпус вместо - id1
  2. большой экран - id2
  3. телефон держит в руке красивая девушка вместо - id3
Но понятно что давать названия должен уже человек.
Если верить википедии - это content-based рекомендательный движок где для определения типа контента используется реакция других пользователей.
При большом кол-ве свойств алгоритм очевидно работать не будет.
Но интересен алгоритм прежде всего выделением свойств объектов. Интересно было бы показать 1000 пользователей 1000 фотографий котиков и понять как эти фотографии кластеризуются.