что такое косинусное расстояние

Коллаборативная фильтрация

В современном мире часто приходится сталкиваться с проблемой рекомендации товаров или услуг пользователям какой-либо информационной системы. В старые времена для формирования рекомендаций обходились сводкой наиболее популярных продуктов: это можно наблюдать и сейчас, открыв тот же Google Play. Но со временем такие рекомендации стали вытесняться таргетированными (целевыми) предложениями: пользователям рекомендуются не просто популярные продукты, а те продукты, которые наверняка понравятся именно им. Не так давно компания Netflix проводила конкурс с призовым фондом в 1 миллион долларов, задачей которого стояло улучшение алгоритма рекомендации фильмов (подробнее). Как же работают подобные алгоритмы?

В данной статье рассматривается алгоритм коллаборативной фильтрации по схожести пользователей, определяемой с использованием косинусной меры, а также его реализация на python.

Входные данные

Допустим, у нас имеется матрица оценок, выставленных пользователями продуктам, для простоты изложения продуктам присвоены номера 1-9:

Задать её можно при помощи csv-файла, в котором первым столбцом будет имя пользователя, вторым — идентификатор продукта, третьим — выставленная пользователем оценка. Таким образом, нам нужен csv-файл со следующим содержимым:

Для начала разработаем функцию, которая прочитает приведенный выше csv-файл. Для хранения рекомендаций будем использовать стандартную для python структуру данных dict: каждому пользователю ставится в соответствие справочник его оценок вида «продукт»:«оценка». Получится следующий код:

Мера схожести

При реализации был использован факт, что скалярное произведение вектора самого на себя дает квадрат длины вектора — это не лучшее решение с точки зрения производительности, но в нашем примере скорость работы не принципиальна.

Алгоритм коллаборативной фильтрации

Теперь осталось только написать соответствующий код

Для проверки его работоспособности можно выполнить следующую команду:

Что приведет к следующему результату:

Источник

Алгоритмы поиска схожих объектов в рекомендательных системах

«Досмотрю вот это видео на YouTube и пойду спать! Ой, в рекомендациях еще одно интересное. Сон, прости…». «Закажу в IKEA только стулья. Ах, сайт показал мне еще посуду, постельное белье и новую кухню в сборке. Когда там следующая зарплата?». «Бесконечный плейлист любимых музыкальных жанров в СберЗвуке заряжает меня позитивом! Как специалистам удается создавать выборку специально для меня?».

Согласитесь, вы сталкивались с подобными мыслями при использовании интернет сервисов. Магическим образом пользователю предлагают новые и новые объекты: видеоролики, музыку, товары. Никакого волшебства здесь нет — это рутинная работа рекомендательных систем. Алгоритмы поиска похожих объектов в больших массивах данных органично вплелись в нашу жизнь и помогают нам делать почти осознанный выбор в той или иной области повседневных дел.

Модели рекомендаций можно использовать для поиска похожих объектов вне контекста продаж. Например, выявлять однообразные ответы операторов в чатах, распознавать будущих злостных неплательщиков кредитных обязательств по косвенным признакам или находить различные группы сотрудников, которым требуется рекомендовать курсы повышения квалификации, в зависимости от текущих навыков. Не стоит забывать и о сайтах знакомств, где рекомендательные алгоритмы будут подбирать собеседника по указанным критериям.

Статья описывает основные подходы к поиску схожих объектов в наборе данных и содержит вводный курс в мир рекомендательных систем. Представлены варианты подготовки данных. Информация будет полезна аналитикам, которые изучают python, и начинающим data-scientist’ам. Мы не будем останавливаться на подробном описании каждого метода и разбирать отличия контентных и коллаборативных рекомендательных систем. Базовая теоретических часть находится здесь, здесь и здесь. Нас интересует применение алгоритмов матчинга (matching, англ. Поиск схожих объектов) в повседневных задачах. К статье прилагается ноутбук на платформе Kaggle с основным кодом, который рекомендуем запускать одновременно с изучением текста.

Коэффициенты корреляции

Самым простым способом вычисления схожести объектов по числовым характеристикам является расчет коэффициента корреляции. Этот метод работает в большинстве повседневных задач, когда у каждого объекта исследования присутствует одинаковый набор метрик. Такая последовательность числовых характеристик называется вектор. Например, мы ищем похожие квартиры в городе: можно банально сравнивать общую и жилые площади, высоту потолков и количество комнат. Для разбора кода возьмем датасет (dataset, англ. Набор данных), в котором содержится информация об объектах недвижимости Сиднея и Мельбурна. Каждая строка таблицы – это отдельный вектор с числовыми характеристиками.

Рис. 1 Датасет с объектами недвижимости

Схожесть характеристик можно рассчитать несколькими способами. Если вы работаете с табличными данными – pandas.corr() является самым удобным. Сравним три объекта, выставленных на продажу.

Мы рассчитали схожесть двух пар объектов: нулевого с девятым и нулевого с шестым. Посмотрите на рисунок выше. Действительно, дома в первой паре подобны по характеристикам. У второй пары объектов заметно различаются общая площадь, год постройки и ренновации, количество спален.

По умолчанию pandas.corr() рассчитывает коэффициент корреляции Пирсона. Его можно сменить на метод Спирмена или Кендала. Для этого нужно ввести аттрибут method.

Для обработки нескольких строк можно создать матрицу корреляции, в которой будут отражены сразу все объекты, находящиеся в датасете. По опыту работы замечу, что метод визуализации хорошо работает с выборками до 100 строк. Далее график становится слабо читаемым. Тепловую матрицу можно рисовать с помощью специализированных библиотек или применить метод style.background_gradient() к таблице. Создадим матрицу корреляции с 10 записями. Чем темнее цвет ячейки – тем выше корреляция.

Рис. 2 Матрица корреляции 10 объектов недвижимости

Метод pandas.corr() сравнивает таблицу по столбцам. Обратите внимание, что для правильного рассчета корреляций между объектами недвижимости, исходную таблицу необходимо транспонировать — повернуть на 90*. Для этого применяется метод dataframe.T.

Сравнивать объекты парами интересно, но непродуктивно. Попробуем написать небольшую рекомендательную систему, которая подберет 10 объектов недвижимости, которые максимально похожи на образцовый. За эталон примем случайный дом, например, с порядковым номером 574.

Рис. 3 Результат работы простейшей рекомендательной системы

Алгоритм отобрал 10 наиболее похожих на образец домов. Все представленные объекты недвижимости имеют одинакое количество спален и ванных комнат, примерно равные жилые и общие площади, и занимают только один этаж. В дополнении на Kaggleпредставлен второй вариант решения задачи, который последовательно перебирает все строки таблицы.

Метод pandas.corr() может сравнивать векторы (объекты), у которых отсутствуют некоторые значения. Это свойство удобно применять, когда нет времени или смысла искать варианты заполнения пропусков.

Косинусное расстояние

Эту метрику схожести объектов в математике обычно относят к методам расчета корреляции и рассматривают вместе с коэффициентами корреляции. Мы выделили ее в отдельный пункт, так как схожесть векторов по косинусу помогаем в решении задач обработки естественного языка. Например, с помощью данного алгоритма можно находить и предлагать пользователю похожие новости. Косинусное расстояние так же часто называют конисусной схожестью, диапазон значений метрики лежит в пределах от 0 до 1.

Разберем простейший алгоритм поиска похожих текстов и начнем с предобработки. В статье приведем некоторые моменты, полный код находится здесь. Для расчета косинусного расстояния необходимо перевести слова в числа. Применим алгоритм токенизации. Для понимания этого термина представьте себе словарь, в котором каждому слову приставлен порядковый номер. Например: азбука – 1348, арбуз – 1349. В процессе токенизации заменяем слова нужными числами. Есть более современный и более удачный метод превращения текста в числовой вектор — создание эмбеддингов с помощью моделей-трансформеров. Не углубляясь в тему трансформаций, отметим, что в этом случае каждое предложение предложение преврящается в числовой вектор длиной до 512 символов. При этом числа отражают взаимодействие слов друг с другом. Звучит, как черная магия, но здесь работает чистая алгебра. Советуем ознакомиться с базовой теорией о трансформерах, эмбеддингах и механизме «внимания» здесь и здесь.

В процессе преобразования новостных статей в токены и эмбеддинги получаем следующие результаты.

После векторизации текста можно сравнивать схожесть заголовков. Рассмотрим работу метода cosine_similarityиз библиотеки sklearn. Выведем два заголовка и узнаем, насколько они похожи.

Новости из мира техники и футбола далеки друг от друга. Косинусная схожесть равна 0.24%. Действительно, южнокорейский IT гигант и туринский футбольный клуб идейно практически не пересекаются.

Вернемся к первичной задаче раздела – поиску схожих статей для пользователя новостного сайта. Рассчитываем косинусное расстояние между векторизированными заголовками и показываем те, где коэффициент максимальный. В результате для новости под индексом 18 получаем следующие рекомендации.

Рис. 4 Результат работы рекомендательного алгоритма заголовков новостей

С высокой вероятностью пользователю, прочитавшему про восстанавливающийся рынок Европы будет интересно узнать про мировой кризис, рост цен и проблемы с валютой в азиатском регионе. Задача выполнена, переходим к заключительному алгоритму поиска схожих объектов.

Кластеризация

Третьим эффективным методом матчинга в большом объеме данных является кластеризация. Алгоритм разделяет записи по установленному количеству групп – кластеров. Задача кластеризации сводится к поиску идеального расположения центров групп — центроидов. Так, чтобы эти центры как бы группировали вокруг себя определенные объекты. Дистанция объекта от центра кластера рассчитывается целевой функцией. Подробнее о ней рекомендуем прочитать здесь. Алгоритм кластеризации представлен фукцией kMeans (англ, к-Средних) библиотеки sklearn.

Для примера алгоритма кластеризации возьмем 300 домов из первичного датасета с австралийской недвижимостью.

Первый шаг метода – поиск оптимального количества кластеров. Последовательно перебираем группы в диапазоне от 1 до 20 и рассчитываем значение целевой функции.

Отрисовываем значения целевой функции, получаем, так называемый, «локтевой график». Нас интересует точка, в которой происходит самый сильный изгиб. На рисунке 5 представлен искомый узел. При увеличении числа кластеров больше 4, значительного улучшения целевой функции не происходит.

Рис. 5 Поиск оптимального числа кластеров для группировки объектов недвижимости

Заново обучаем модель kMeans с необходимым числом кластеров. Для каждого объекта устанавливаем причастность к группе и сохраняем ее номер. Выбираем объекты одной группы.

Посмотрим на количество домов в группах.

«Нулевая» группа самая многочисленная и содержит типовые дома. В группы «один» и «два» попали объекты с громадной жилой площадью (столбец sqft_lot). Выборки представлены на рисунке 6.

Рис. 6 Объекты недвижимости с увеличенной площадью

Задача группировки объектов недвижимости с помощью алгоритма kMeans выполнена. Переходим к итогам.

Заключение

Мы рассмотрели три метода поиска схожих объектов в данных: коэффициенты корреляции, косинусное расстояние и метод k-средних. С помощью представленных инструментов можно решить большинство повседневных задач: найти схожие объекты с числовыми характеристиками, обработать текстовые записи или разбить массив данных на кластеры. Мы изучили основы матчинга и рекомендательных алгоритмов. В заключение отметим, что самые современные системы YouTube и TikTok в своей основе используют комбинации и улучшения указанных методов. Как видите, никакой магии в подборе любимых песен и роликов. Только чистая математика!

Источник

Эти ограничения применимы для любого количества измерений, а косинусное подобие чаще всего используется в многомерных положительных пространствах. Например, при поиске информации и интеллектуальном анализе текста каждому термину условно назначается другое измерение, а документ характеризуется вектором, где значение в каждом измерении соответствует количеству раз, когда термин появляется в документе. Таким образом, косинусное сходство дает полезную меру того, насколько похожими могут быть два документа с точки зрения их предмета.

СОДЕРЖАНИЕ

Определение

Косинус двух ненулевых векторов может быть получен с помощью формулы евклидова скалярного произведения :

Для сопоставления текста векторы атрибутов A и B обычно являются векторами частотности терминов документов. Косинусное сходство можно рассматривать как метод нормализации длины документа во время сравнения.

Угловое расстояние и подобие

Термин «косинусное подобие» иногда используется для обозначения другого определения подобия, приведенного ниже. Однако наиболее распространенное использование «косинусного подобия» определено выше, а показатели подобия и расстояния, определенные ниже, называются «угловым сходством» и «угловым расстоянием» соответственно. Нормализованный угол между векторами является формальной метрикой расстояния и может быть рассчитан на основе оценки подобия, определенной выше. Затем эту метрику углового расстояния можно использовать для вычисления функции подобия, ограниченной от 0 до 1 включительно.

Когда элементы вектора могут быть положительными или отрицательными:

Или, если элементы вектора всегда положительны:

L 2 <\ displaystyle L_ <2>> -нормированное евклидово расстояние

Другой эффективный прокси для косинусного расстояния может быть получен путем нормализации векторов с последующим применением нормального евклидова расстояния. Используя этот метод, каждый член в каждом векторе сначала делится на величину вектора, в результате чего получается вектор единичной длины. Тогда ясно, что евклидово расстояние по конечным точкам любых двух векторов является правильной метрикой, которая дает тот же порядок, что и косинусное расстояние для любого сравнения векторов, и, кроме того, позволяет избежать потенциально дорогостоящих тригонометрических операций, необходимых для получения правильного метрическая. После нормализации векторное пространство можно использовать с полным набором методов, доступных для любого евклидова пространства, в частности, стандартными методами уменьшения размерности. Это нормализованное расстояние формы, в частности, используется во многих алгоритмах глубокого обучения. L 2 <\ displaystyle L_ <2>>

Коэффициент Оцука-Очиай

Характеристики

Евклидово расстояние называется хордовым расстоянием (потому что это длина хорды на единичной окружности), и это евклидово расстояние между векторами, которые были нормированы на единичную сумму квадратов значений внутри них.

Мягкая косинусная мера

Мягкий косинус или («мягкое» сходство) между двумя векторами учитывает сходство между парами объектов. Традиционное косинусное сходство рассматривает функции модели векторного пространства (VSM) как независимые или совершенно разные, в то время как мягкая косинусная мера предлагает учитывать сходство функций в VSM, что помогает обобщить концепцию косинуса (и мягкого косинуса), а также идею (мягкого) сходства.

Источник

Векторная модель и косинусное сходство (Cosine similarity)

В это статье я хочу ознакомить вас с примером использования векторной модели и рассказать как используется косинусное сходство — Cosine similarity в информационном поиске.

Документ в векторной модели рассматривается как неупорядоченное множество термов. Термами в информационном поиске называют слова, из которых состоит текст, а также такие элементы текста, как, например, 2010, II-5 или Тянь-Шань.

Различными способами можно определить вес терма в документе — «важность» слова для идентификации данного текста. Например, можно просто подсчитать количество употреблений терма в документе, так называемую частоту терма, — чем чаще слово встречается в документе, тем больший у него будет вес. Если терм не встречается в документе, то его вес в этом документе равен нулю.

Хорошее описание представлено в wiki (на русском, на английском).

Как рассчитать косинусное сходство? (Cosine similarity)

Рассмотрим небольшую коллекцию C, которая содержит следующие три документа:

Некоторые термы встречаются в двух документах, некоторые только в одном. Общее количество документов N=3.

Рассчитаем значения idf (функции от величины, обратной количеству документов коллекции, в которых встречается этот терм) для термов:

Для всех документов, мы вычислим значения tf (отношение числа вхождений некоторого слова к общему числу слов документа) для всех термов из коллекции. Предположим, что слова в векторе упорядочены по алфавиту.

Теперь мы умножим значения tf на значения idf для каждого терма, получаем следующую матрицу: (Все термы встречаются только один раз в каждом документе в нашей небольшой коллекции, так что максимальное значение для нормализации будет 1.)

Для заданного поискового запроса: “new new times”, мы вычислим tf-idf вектор для запроса, и вычислим схожесть каждого документа из коллекции с заданным запросом, используя измерение косинусной схожести (cosine similarity). При вычислении tf-idf значений для термов из запроса мы разделим частоту на максимальную частоту (2) и умножим на значения idf.

Рассчитаем длину каждого документа и запроса:

Length of d1 = sqrt(0.584^2+0.584^2+0.584^2)=1.011

Length of d2 = sqrt(0.584^2+1.584^2+0.584^2)=1.786

Length of d3 = sqrt(1.584^2+1.584^2+0.584^2)=2.316

Length of q = sqrt(0.584^2+0.292^2)=0.652

Затем рассчитаем схожесть пл формуле

:

cosSim(d1,q) = (0*0+0*0+0.584*0.584+0*0+0.584*0.292+0.584*0) / (1.011*0.652) = 0.776

cosSim(d2,q) = (0*0+0*0+0.584*0.584+1.584*0+0*0.292+0.584*0) / (1.786*0.652) = 0.292

cosSim(d3,q) = (1.584*0+1.584*0+0*0.584+0*0+0.584*0.292+0*0) / (2.316*0.652) = 0.112

Согласно полученным значениям схожести, конечный порядок в котором документы будут представлены как результат запроса будет: d1, d2, d3.

Источник