Привет.
Читаю книгу Mahout in Action. Столкнулся с эффектом “смотрю в книгу – вижу фигу”. Для его устранения решил конспектировать.
Apache Mahout – это библиотека для работы с алгоритмами машинного обучения, которая может быть использована как надстройка к Hadoop или самостоятельно. В библиотеке реализованы методы коллаборативной фильтрации, кластеризации и классификации.
Рассматриваем рекомендательную систему на основе коллаборатвной фильтрации. Она может быть пользователе-ориентированной (user-based) или свойство-ориентированной (item-based).
Коллаборативная фильтрация — это один из методов построения прогнозов, использующий известные предпочтения (оценки) группы пользователей для прогнозирования неизвестных предпочтений другого пользователя. Его основное допущение состоит в следующем: те, кто одинаково оценивали какие-либо предметы в прошлом, склонны давать похожие оценки другим предметам и в будущем. (из википедии)
Одно из основных понятий пользователе-ориентированных рекомендательных систем это метрика для определения схожести пользователей. Предположим что мы имеем данные по просмотрам и оценкам фильмов разными пользователями. Будем сравнивать двух пользователей: X и Y. Они выставили оценки фильмам X(x1, x2, ..., xn) и Y(y1, y2, ..., ym), где n, m – количество оценок поставленных первым и вторым пользователем соответственно. N – количество оценок, которые были поставленны обоими пользователями одним и тем же фильмам (пересечение множеств фильмов посмотренных первым и вторым). Будем считать что (xi, yi) – это пара оценок выставленная пользователями одному фильму.
В Mahout реализованы метрики на основании нескольких алгоритмов. Описываю сами алгоритмы, а не их реализации в Mahout.
Коэффициент корреляции Пирсона (4.3.1)
В скобках буду помечать главу в книге “Mahout in Action” Owen, Anil, Dunning, Friedman.
Реализация в Mahout – PearsonCorrelationSimilarity.
Коэффициент корреляции Пирсона это число K (-1 ≤ K ≤ 1), которое показывает тенденцию двух множеств чисел, идущих попарно, быть схожими. Т.е. образовывать почти линейную зависимость между числами первого и второго множества. xi = Byi (для всех i B будет примерно одинаковым). Если зависимость линейная, то коэффициент корреляции равен 1, если обратная то -1, если нет зависимости, то 0.
Вычисляется по формуле: 
Справа векторная запись. 
— среднее арифметическое. Таким образом мы центрируем данные. При рассчете вручную это нужно учитывать, но реализация корреляции в Mahout заботиться об этом самостоятельно.
Проблемы метрики по корреляции Пирсона (4.3.2)
Логично предположить, что два пользователя, посмотревшие 200 одинаковых фильмов больше похожи даже если они выставили разные оценки, чем два пользователя посмотревшие три одинаковых фильма и поставившие им одинаковые оценки. Но из формулы мы получим противоположный результат.
Второй недостаток – это невозможность рассчета корреляции для пользователей у которых выставлена только одна оценка (т.к. знаменатель будет равен нулю).
Коэффициент также не определен для тех случаев, когда один из пользователей поставил одну и ту же оценку всем фильмам. Например пользователь посмотрел 3 фильма и выставил им всем оценку 5. Опять же знаменятель равен нулю.
Вес корреляции (4.3.3)
Для того, чтобы устранить первый недостаток ввели понятие веса корреляции. Если для подсчета используется много параметров, то положительную корреляцию умножают на 1, а отрицательную на -1. Т.о. Если было просмотрено большое количество одинаковых фильмов но выставлены противоположные оценки, то корреляция будет положительной.
Можно также умножать на число, меньшее 1, в случае если для подсчета коэффициента было использовано мало параметров, таким образом уменьшая схожесть пользователей.
Евклидова метрика (4.3.4)
Реализация в Mahout – EuclideanDistanceSimilarity.
Реализация заключается в нахождении расстояния между пользователями. Пользователи выступают в роли точек в многомерном пространстве с координатами-оценками. Учитываются только оценки, выставленные обоими пользователями по фильму.
Чем меньше расстояние, тем вкусы пользователей более схожи. Поэтому реализованная в Mahout метрика возвращает K=1/(1+d). В отличие от предыдущей метрики эта принимает значение от 0 до 1. Чем больше коэффициент, тем более сходны вкусы пользователей.
Недостаток этой метрики в том, что пользователи оценившие один фильм одинаково (других общих фильмов нет) будут более схожи, чем оценившие сотню фильмов почти одинаково.
Косинусный коэффициент (4.3.5)
Реализация в Mahout – с помощью PearsonCorrelationSimilarity.
Представляет собой косинус угла между двумя прямыми, образованными точкой O(0,0,...) и точками-пользователями X(x1, x2, ...), Y(y1, y2, ...).
-1 ≤ cos A ≤ 1. Если угол A=0 (cos A = 1), то пользователи похожи. Если угол A=180 (cos A = -1), то вкусы пользователей противоположны. Если угол близок к 90 градусам – зависимости между предпочтениями этих двух пользователей нет. Подробнее о косинусном коэффициенте ...
В Mahout нет специальной реализации для этой метрики, для вычисления используется метрика корреляции Пирсона. Вручную рассчет можно произвести по формуле ниже. Векторная запись справа отличается от корреляции Пирсона лишь тем, что не центрируем координаты.
Коэффициент корреляции Спирмана (4.3.6)
Реализация в Mahout – SpearmanCorrelationSimilarity.
Коэффициент корреляции Спирмана определяют как коэффициент корреляции Пирсона между ранкированными переменными (ranked variables). Наименее предпочитаемому фильму выставляется оценка 1, следующему 2 и т.д. После выставления всех оценок вычисляется коэффициент корреляции Пирсона.
Недостаток этой метрики в медленной работе. Ведь перед вычислением коэффициента корреляции нужно провести ранкирование. Кроме того, метрика имеет недостатки метрики Пирсона.
Коэффициент Танимото (4.3.7)
Реализация в Mahout – TanimotoCoefficientSimilarity.
Коэффициент Танимото – это отношение числа заполненных и первым, и вторым пользователями (пересечение), к числу всех свойств первого и второго (объединение): K = I/U. Эту метрику рекомендуют использовать в случаях когда значения предпочтений булевы.
Логарифмическое правдоподобие (4.3.8)
Реализация в Mahout – LogLikelihoodSimilarity.
Алгоритм вычисления метрики не совсем понятен интуитивно, в отличие от предыдущих.
Пусть n фильмов посмотрел первый пользователь, m – второй, p – посмотрели два пользователя в сумме (объединение).
* — фильм не оценен пользователем (или не просмотрен). равны 1 если оценка фильму выставлена, равны 0 в противном случае.
LLR = 2 (H(k) — H(rowSums(k)) — H(colSums(k))) — коэффициент логарифмического правдоподобия.
Подробнее про этот алгоритм: формулы, реализация.
Буду рад если, кому-то пригодится. Об ошибках пишем в личку, а троллим в коментариях.
Автор: grinCo
