#algorithm
#алгоритм
Вопрос:
Я читал о рекомендательных системах в Википедии, и раздел «Алгоритмы», похоже, предполагает, что K ближайшего соседа и пользовательский алгоритм на основе совместной фильтрации — это две разные вещи. Это правильно? Насколько я понимаю, разве они оба не одинаковы? Если нет, то в чем разница между ними? Спасибо.
Ответ №1:
Не совсем. Они похожи (они разделяют одни и те же идеи), но между ними есть несколько основных различий. Фактически, статья в Википедии описывает только 2 наиболее отличных способа реализации рекомендательных систем, но их гораздо больше, которые используют idea из обоих этих способов.
Итак, вот как я понял статью в Википедии.
1-й подход (сходство KNN / профилей)
Прежде всего, KNN не является основной особенностью первого подхода. Это просто алгоритм для поиска ближайших элементов среди всей коллекции, поэтому его можно использовать и для совместной фильтрации. Самая важная идея заключается в термине «сходство». Чтобы порекомендовать что-то соответствующему пользователю, вы находите людей из его района с похожим профилем. Например, вы хотите дать рекомендацию пользователю John на Facebook. Вы смотрите на его профиль в Fb, а затем на профили его друзей. Вы находите 10 человек с похожими профилями и проверяете, что им нравится. Если 8 из 10 человек с похожими профилями понравился новый фильм, скорее всего, Джону он тоже понравится.
Итак, здесь есть 2 важных момента:
- вы смотрите на окрестности пользователя
- вы измеряете сходство их профилей
В статье Википедии не рассматривается вопрос о том, как найти меру сходства, но есть много способов, включая поиск общих терминов в тексте профиля, поиск лучших друзей (мое количество сообщений между ними, анализ графа соединений и т. Д.) И многие другие.
2-й подход (совместная фильтрация)
Во втором подходе вам не нужно анализировать окрестности и находить похожие профили, но вам нужно собирать варианты пользователей. Давайте вспомним пример с пользователем Facebook Джоном. Представьте, что мы можем получить все «лайки» всех пользователей Fb, включая Джона. С их помощью вы можете построить очень большую корреляционную матрицу, где строки — это идентификаторы пользователей, а столбцы — все возможные элементы, которые им могут «понравиться». Если элемент действительно «понравился», ячейке для текущего пользователя и текущего элемента присваивается значение 1, в противном случае оно равно 0.
С такой матрицей (встроенной или абстрактной) вы можете использовать анализ ассоциаций для поиска наиболее сильных ассоциаций. Например, 10000 людям, которым понравились «Пираты Карибского моря 2», также понравились «Пираты Карибского моря 3», но только 500 из них понравилась «Пила». Таким образом, мы можем предположить, что связь между 2 эпизодами «Пиратов» намного сильнее. Обратите внимание, что мы не анализировали ни пользователей, ни сами фильмы (мы не учитывали названия фильмов, сюжеты, актеров или что-то в этом роде — только «лайки»). Это основное преимущество совместной фильтрации по сравнению с методами, основанными на сходстве.
Наконец, чтобы порекомендовать фильм пользователю John, вы просто перебираете его «лайки» и находите другие элементы, которые имеют самые сильные ассоциации с текущим.
Итак, важными моментами здесь являются:
- вы не используете окрестности, а вместо этого заполняете базу данных всех пользователей
- вы используете выбор людей и находите ассоциации
Оба подхода имеют свои сильные и слабые стороны. 1-й подход основан на каких-то связях между людьми (например, друзьями на Facebook) и вряд ли может использоваться для таких сервисов, как Amazon. В то же время 2-й подход основан на усредненных предпочтениях всех пользователей и, следовательно, не является хорошим вариантом для систем с очень разными предпочтениями.
Ответ №2:
Я собираюсь привести иллюстрацию двух методов:
Разница между двумя методами практически такая же, как если бы вы просили совета у своих соседей по сравнению с просьбой ваших друзей :
- Сходство между 2 людьми для совместной фильтрации определяется вашими общими предпочтениями
- Сходство для K-ближайшего соседа определяется расстоянием (но расстояние может быть таким же, как для совместной фильтрации)
Более того, в первом случае вы просматриваете K соседей (это фиксированное число), а во втором вы просматриваете весь свой набор данных.
В некоторых случаях on может дать лучший совет, чем другой :
Например:
Если я хочу купить телевизор и спрошу своего друга, который живет в большом доме, он посоветует мне большой экран. Но мой сосед, который живет в квартире рядом со мной, посоветует мне маленький, потому что большой не поместится в его квартире. (аналогично моему). Так что мой совет соседа лучше в этом случае.
Если я хочу купить фильм, мой лучший друг, очевидно, даст мне лучший совет, чем мой сосед.
Ответ №3:
Алгоритм k-ближайших соседей является более общим алгоритмом и не зависит от домена, тогда как пользовательские методы зависят от домена и могут рассматриваться как экземпляр метода k-ближайших соседей.
В методах k-Nearest Neighbors вы можете использовать определенную меру подобия для определения k-ближайших точек данных к определенной точке данных x. Затем вы можете использовать это локальное соседство, чтобы сделать некоторые прогнозы о некоторых (неизвестных) свойствах x, например, это метка класса (классификация) или определенное значение атрибута (регрессия). Близость между точками данных и x может быть измерена с помощью любой функции подобия, которую вы определяете (например, евклидово расстояние, косинусное подобие). Кроме того, точки, которые находятся дальше от x, могут оказывать меньшее влияние на прогноз интересующего значения x. Например, с помощью некоторой весовой функции, которую вы определяете, вы можете взвешивать точки данных в окрестности x обратно пропорционально их расстоянию от x. Интуиция заключается в том, что чем дальше точка x, тем меньше она влияет на прогноз для x, поскольку она менее похожа. Наконец, параметр k определяет, сколько точек данных вы хотите рассмотреть для построения этой локальной окрестности.
Ближайшие соседи на основе пользователя — это тип методов совместной фильтрации, исходящих из области поиска информации (IR). Тот факт, что вы использовали «Пользовательский» в своем вопросе, означает, что вы ссылаетесь на определенный домен, обычно основанный на некотором поведении пользователя, например, какие фильмы / продукты высоко оценил / купил пользователь и какие другие фильмы могли понравиться этому человеку на основе этого. В этой области гораздо чаще отсутствуют несколько значений, например, почти никто не оценил или не купил большинство продуктов / услуг. Однако вы можете реализовать пользовательский алгоритм ближайшего соседства таким образом, чтобы он был эквивалентен методу k-ближайших соседей. Еще раз вы можете вычислить сходство между x (пользователь) и всеми другими точками данных (пользователь) на основе некоторой функции подобия и взвесить его обратно пропорционально сходству с весовой функцией. Сходство x и других точек данных определяется только по не пропущенным значениям, и k может быть установлено так, чтобы включать все точки данных (но это не обязательно). Для ускорения вычислений при нахождении локальной окрестности x вы можете использовать такие методы, какХеширование с учетом местоположения и использование только подмножества окрестности, где k << общий размер набора данных. На практике вы можете захотеть предсказать недостающие значения в x, указывающие на то, что пользователь ранее не покупал / не пользовался услугой. Если на основе локальной окрестности x прогнозируется высокое значение для отсутствующего значения, вы можете использовать это для объявления этого элемента пользователю.
Короче говоря, пользовательские методы — это всего лишь экземпляр алгоритма k-ближайшего соседа, наиболее часто используемого в конкретной области поиска информации.