Мы с вами убедились в том, что у двух случайных товаров пересечения в среднем больше, чем у двух случайных пользователей. Поэтому, кажется, настало время посмотреть на item-based коллаборативную фильтрацию. Как она работает? Вот у нас есть пользователь, и у него есть в истории какие-то оценки. Давайте для фильмов, которые ему понравились, попробуем найти похожие на эти фильмы и тоже порекомендовать ему. Скорее всего, так как эти фильмы похожи, а первый из них пользователю понравился, то и второй ему тоже зайдет. Например, здесь мы видим пользователя, которому понравился фильм "Супермен". Фильм "Супермен" похож на "Человека-паука", "Мстителей" и "Бэтмена" — мы эти похожести можем просто вычислить. И теперь, по нашей логике, мы просто порекомендуем ему, например, посмотреть "Человека-паука" — это тоже фильм про супергероев, и (почему бы и нет?) это выглядит нормальной логичной рекомендацией. Теперь вопрос: как эти похожести товаров считать? На самом деле можно действовать точно так же: можно считать корреляцию Пирсона; только для пользователей мы считали похожести двух строк, а здесь мы будем считать похожести двух столбцов — во всем остальном формулы точно такие же. Можно так и делать, но люди придумали еще и другие похожести, которые на практике могут работать лучше. Одна из них — это косинусная мера. Мы можем взять два столбца (это два наших товара) из матрицы, и мы можем посчитать между ними просто косинус: мы рассматриваем эти два столбца как векторы в многомерном пространстве и считаем косинус угла между ними, косинус, прямо честно, по формуле: скалярное произведение поделить на нормы. Здесь единственное отличие от той формулы из линейной алгебры, что мы берем только тех пользователей, которые общие для этих двух фильмов, то есть это пользователи из пересечения этих двух фильмов или двух товаров — это единственное отличие. Но в этой формулке тоже есть нюансы; если ее применять просто втупую и не задумываясь о том, какие там могут быть какие-то крайние случаи или какие-то частные случаи, могут быть проблемы. Давайте посмотрим на плохие моменты этой метрики. Возьмем два товара, например, это "Шерлок" и "Карточный домик". И у нас есть два общих пользователя, которые смотрели и первый фильм, и второй. И, например, нашим пользователям первый фильм не понравился, а второй прямо очень понравился, то есть у каждого из них в строчке один, пять — один, пять. Тогда, если мы посмотрим на похожесть двух наших столбцов просто как двух векторов в двумерном пространстве (это, соответственно, вектор (1,1) и (5,5)), то вы заметите на картинке, которая на слайде, что эти векторы сонаправлены — угол между ними ноль, а поэтому косинус у нас будет ровно единичкой, то есть получается по нашей формуле, что эти фильмы наиболее похожи. Но как-то это странно, ведь мы видим, что одному пользователю фильм A нравится, а фильм B не нравится, — странно считать их очень похожими. Конечно же, люди это заметили и придумали, как это можно поправить. Ввели новую метрику, которая называется adjusted cosine similarity, то есть такая косинусная похожесть, но немножко доработанная. Что здесь добавили? По аналогии с тем, как мы считаем корреляцию Пирсона, здесь вычли средний рейтинг юзера. Но если бы мы считали корреляцию Пирсона, мы бы здесь вычитали средний рейтинг item; а здесь мы вычитаем средний рейтинг юзера ru, соответственно. И все точно так же, как и в обычной косинусной похожести, в остальном — мы считаем все эти суммы только по общим пользователям. Давайте посмотрим, как изменится ситуация в нашем игрушечном примере, на котором все было плохо. Если мы сделаем такую предобработку и для каждого пользователя из его оценок вычтем его средний рейтинг, то среднее для обоих пользователей здесь один плюс пять пополам — это три; если троечку вычесть построчно, то мы получим вот такие строки: минус два, два; и минус два, два для второго пользователя тоже. Почему это лучше? Потому что теперь, если мы посмотрим на похожесть двух столбцов, а это наши фильмы, у них общих пользователей всего два, поэтому мы на такие векторы и будем смотреть, то мы давайте просто нарисуем эти векторы и убедимся, что теперь они совсем не похожи: у нас есть вектор (минус 2, минус 2) — это красный, который тащит вниз, и есть (2, 2), который торчит по диагонали вверх. Теперь эти векторы совсем не сонаправлены, и косинус между ними будет минус единичкой, то есть минимальное значение. Классно, вроде бы эту проблему мы решили. Вообще, у item-based есть куча плюсов, и один из них — это то, что те похожести, которые мы насчитываем, в среднем более уверенны, потому что в реальности так получается на практике, что у двух товаров пересечения в среднем больше, чем у двух случайных пользователей. Поэтому все наши похожести, которые мы считаем, будь то косинусная похожесть или adjusted cosine similarity, они все более уверенны. И еще есть такой момент, что у товаров, как правило, в среднем и рейтингов много. Есть какой-то товар, его купили 1000 человек — это, конечно, сильно больше, чем в среднем количество оценок у какого-то пользователя: очень мало таких пользователей, которые в среднем понаставили 1000 оценок, — это очень долго нужно пользоваться сервисом и очень быть неленивым, чтобы 1000 оценок расставить для фильмов. Поэтому, если у нас к этой 1000 рейтингам, которые есть для фиксированного товара, добавится еще, скажем, 10, то это особо ни на что не повлияет; даже если добавится 100, это тоже не так много, и вряд ли похожести изменятся прямо так сильно. Поэтому мы эти похожести можем рассчитывать с каким-то запозданием: у нас здесь есть какой-то запас по времени, который мы можем потратить на расчет этих похожестей. Давайте посмотрим на алгоритм, который является, наверное, оптимальным для расчета всех item-item похожестей. Он действует следующим образом: представьте, что матрицу оценок, которая у нас есть, мы храним по строчкам (сейчас мы поймем, зачем мы так делаем). Давайте посмотрим, например, на вторую строку (она выделена в красную рамку): от этого пользователя у нас будет вклады в похожести вот таких трех пар товаров. Заметьте, что, когда мы будем рассматривать, например, первый товар и третий, то этот пользователь будет как бы в их пересечении; и по нему в эти наши суммы будет следующий вклад: оценка 5 минус его среднее умножить на оценку 4 для третьего фильма минус его среднее — в метрику adjusted cosine similarity у нас будет вот такой вклад. Круто. Давайте тогда мы возьмем и во все пары товаров, которые есть у этого пользователя, сразу эти вклады посчитаем. И здесь вы заметите, какие пары есть у этого пользователя: первый и третий товар, первый и шестой, и третий и шестой; и все их вклады считаются прямо здесь же, когда мы видим всего этого пользователя, когда мы видим всю эту строчку. Теперь, если мы эти все вклады будем где-то накапливать (или в памяти, или на диске, или где-нибудь еще), а затем сагрегируем, то мы получим как раз все похожести ненулевые, которые у нас есть между всеми парами товаров. Этот алгоритм довольно быстрый, и если вы будете когда-то считать эти похожести, то используйте его. Еще один момент, которого мы пока не касались, — это неявные рейтинги. Давайте посмотрим на примере item-based коллаборативной фильтрации, как можно использовать неявные рейтинги. Одним из таких рейтингов является, например, факт покупки: вы купили, и непонятно, оно вам понравилось или нет, — мы только знаем, что вы это купили, поэтому это неявный рейтинг. Если зайти на более или менее любой интернет-магазин, там рисуют такой блок "С этим товаром часто покупают": пишут через плюсики, рисуют там какую-нибудь скидку и предлагают вам купить прямо тот же самый набор. Откуда они взяли эти тройки, эти пары товаров, которые часто покупают вместе? Сейчас нам нужно ответить на вопрос, что такое "часто покупают вместе"? Оказывается, что даже в такой простой задаче есть свои нюансы. Давайте посмотрим, что какое-то наивное количество просто общих пользователей, которые купили и товар A, и товар B, — так делать не очень хорошо; мы не можем просто посчитать, сколько для каждой пары товаров есть общих пользователей, которые купили и первый, и второй. Почему это плохо? Потому что обычно неважно, это товары, или это фильмы, или это музыкальные треки — есть очень популярные какие-то товары, которые купили более или менее все. Если мы говорим про интернет-магазин, пусть это будет, например, книжка "Гарри Поттер" (любая книжка из этой серии): скорее всего, ее купило просто очень много людей. Это означает, что она в истории покупок много у кого есть; и если мы просто будем смотреть, как часто "Гарри Поттер" покупают с какой-то еще книжкой, то оказывается, что "Гарри Поттер" похож вообще на все, потому что "Гарри Поттер" есть у всех в покупках, там есть какие-то еще другие товары, и получится, что чаще всего со всеми остальными товарами покупают "Гарри Поттер" — просто по счетчику, сколько общих пользователей у какого-то товара и у "Гарри Поттера": оно будет большое, потому что "Гарри Поттер" есть у всех. Черт, как-то это не очень круто, потому что это какая-то плохая рекомендация. Представьте себе интернет-магазин: вы там смотрите разные книжки, а к любой книге вам рекомендуют купить "Гарри Поттера", потому что мы так глупо считаем их похожесть (просто по количеству пользователей). Нехорошо. Нужно с этим что-то сделать. И решение есть. В теории множеств есть такая метрика, как мера Жаккара. Она пытается сравнить два множества — в нашем случае это множества пользователей. Представьте, что A здесь — это множество пользователей, которые купили товар A; B — это множество пользователей, которые купили товар B; и на самом деле мы хотим для двух товаров сравнить, насколько их аудитория похожа. И здесь эта метрика чем хороша, что она учитывает не только пересечение, по которому мы пытались на предыдущем слайде найти похожие товары, но она учитывает и мощность объединения этих двух множеств, то есть общих пользователей, которые купили и A, и B (это слева пересечение), должно быть много по отношению ко всем пользователям, которые купили A или B. И здесь, конечно же, "Гарри Поттер" проиграет, потому что окажется, что, например, множество A будет таким огромным (это "Гарри Поттер"), а множество B (какая-нибудь "Как слепить что-нибудь из пластилина") будет маленьким; и в пересечении хоть и много, но в объединении тоже будет много, и "Гарри Поттер" здесь "пойдет ко дну". Давайте посмотрим на каком-то конкретном примере. Вот это из датасета Last.fm: там прослушивания различных исполнителей для большого количества пользователей (там, по-моему, 300000 пользователей), и мы можем по ним просто посчитать, насколько два исполнителя похожи, насколько их часто слушают одни и те же люди. Если вы возьмете и по-простому будете считать просто счетчик (мощность пересечения), то оказывается, что Coldplay — очень популярный исполнитель, его много кто послушал, и Coldplay похож на все. Вот вы берете там какого-то Kanye West, который рэп какой-нибудь читает, и оказывается, что он похож на эту попсу, на этот Coldplay, хотя по музыке это вообще разные стили; но просто Coldplay слушают все, поэтому, будь добр, и ты тоже Coldplay послушай. Какая-то не очень хорошая логика. Давайте посмотрим, что будет, если мы на этом же наборе данных будем ранжировать наших похожих исполнителей не по мощности пересечения, а по мере Жаккара. По мере Жаккара окажется, что Coldplay будет дискаунтирован из-за его огромного размера, и окажется, что по мере Жаккара выгоднее находить большие пересечения для таких исполнителей, которые примерно той же популярности. То есть вот эти шарики должны быть примерно одинакового размера и иметь много в пересечении, тогда мера Жаккара будет большой. И здесь мы видим, что к Kanye West нам порекомендовали Jay-Z и других каких-то еще людей, которые тоже в этом же стиле исполняют музыку (это все из рэп-музыки, например). То есть эти рекомендации более осмысленны — они хотя бы из одного и того же жанра, и мы это получили, просто посчитав меру Жаккара. Давайте резюмируем. Мы посмотрели с вами два подхода к коллаборативной фильтрации: item-based и user-based. Вообще говоря, это какие-то классические алгоритмы, которые придуманы давным-давно, и они дают неплохие рекомендации, если у вас реально очень много оценок. То есть если матрица заполнена сильно оценками, пропусков условно 98-99 процентов, то это хороший сетап для решения этой задачи при помощи коллаборативной фильтрации. Плохо они работают, когда этих пропусков очень много. Представьте, что у вас есть матрица "юзер-товар" и пропусков 99.9 процентов. Вот тогда это все не очень работает, потому что в среднем два пользователя или два товара будут в пересечении иметь очень мало общего, и тогда все наши метрики, насколько бы они классные ни были (метрики похожести), они будут плохими, они будут неуверенными, — поэтому это работает не очень хорошо. И самый большой минус, от которого в этом алгоритме вообще не избавишься, следующий: представьте, что у нас есть два пользователя, у которых в пересечении прямо тех же самых фильмов нету, но, вообще говоря, представьте, что один из них любит фильм "Терминатор", а другой — "Терминатор 2"; и условно это два разных столбца, эти фильмы разные по наименованию, но эти фильмы прямо очень похожи — это прямо про одно и то же практически; но мы не сможем эту похожесть учесть, потому что эту похожесть фильмов, когда мы считаем похожесть двух пользователей, мы не учитываем. То есть эти алгоритмы по своей природе просто не могут это сделать — они не могут засчитать пересечение по очень похожим фильмам. Это, конечно, их минус, но мы придумаем, чего с этим делать дальше.