Одной из основных проблем при применении методов коллаборативной фильтрации является временная сложность формирования одноранговых групп. Обычно вы вычисляете попарное сходство для каждого пользователя в системе, основанной на пользователях, и используете k ближайших соседей, чтобы найти k самых похожих пользователей. Если у нас есть m элементов, этот процесс будет O (m ^ 2) соответственно. Это не годится, когда m порядка десятков миллионов; это было бы слишком дорого.
Альтернативный метод формирования одноранговых групп состоит в использовании модифицированной кластеризации k-средних для поиска ближайших пользователей/элементов для каждого пользователя/элемента. Это сформирует меньше одноранговых групп, поскольку мы не формируем одноранговую группу для каждого возможного целевого пользователя. Когда у нас есть эти новые группы одноранговых узлов, мы можем вычислить топ-k ближайших пользователей так же, как методы ближайших соседей.
Теперь давайте более подробно рассмотрим, как k-средние вписываются в совместную фильтрацию и как нужно модифицировать k-средние для работы с разреженными входными данными.
K-средние
Во-первых, краткий концептуальный обзор k-средних.
K-средние работают, находя самую центральную точку для каждого из k кластеров, выбирая ближайшую точку данных к этому центру, реконструируя новые кластеры на основе этих центроидов и повторяя эти шаги до сходимости.
При совместной фильтрации на основе пользователей эти выборочные точки данных будут иметь n измерений, поскольку каждый пользователь представлен в виде строки в матрице mx n. Процесс формирования кластеров выглядит так:
- Для всех строк u матрицы m x n (пользователи) мы назначаем u ближайшему центроиду, используя функция расстояния (например, манхэттенское расстояние и евклидово расстояние).
- Переназначьте каждый из k центроидов в центры их вновь сформированных кластеров.
- Повторение.
Работа с разреженностью
Основной способ размещения разреженного ввода — использовать только указанные рейтинги. Мы можем найти среднее значение каждого кластера, используя только указанные рейтинги в этих кластерах. Мы также можем найти расстояние между каждым пользователем и каждым центроидом, используя только общие указанные рейтинги для каждой пары.
(Обратите внимание, что все вышеперечисленное работает для совместной фильтрации на основе элементов, когда мы группируем столбцы, а не строки.)
Теперь предположим, что мы реализовали это правильно, и теперь у нас есть k кластеров пользователей. Теперь каждый раз, когда нам нужно вычислить попарное сходство для какого-либо пользователя, мы вычисляем это сходство только между пользователями в одном кластере!
Это значительно улучшит время выполнения, особенно если кластер является мелкозернистым. Имейте в виду, что за эту эффективность, как всегда, приходится платить — на этот раз за точность.
Отсюда мы золотые. Когда у нас есть группа сверстников, все становится так же, как и раньше. Мы можем использовать ту же функцию предсказания соседства из пользовательской совместной фильтрации, которую мы уже видели, и вуаля: горячие прогнозируемые рейтинги.
Кластеризация — не единственный способ эффективного поиска одноранговых групп для методов, основанных на соседстве. Вы также можете улучшить этап обучения совместной фильтрации с уменьшением размерности, о котором я рассказываю в этой статье.
