Python косинусное расстояние векторов

Дата публикации Oct 30, 2019

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

Давайте углубимся в это на примере. У вас есть веб-страница, и она требует некоторыхпользовательский ввод— допустим, по какой-то причине вы решили использовать текстовое поле вместо раскрывающегося меню для получения информации о местоположении. Существует вероятность того, что пользователь сделает опечатку, и вы не хотите, чтобы опечатки сохранялись в вашей базе данных. Вы хотите исправленную версию без опечаток.

Но как бы вы исправили строку?Я имею в виду, что вы можете жестко закодировать это, но вы действительно хотите это сделать? Вариантов опечаток так много, и жесткое кодирование обычно не очень хорошая идея.

Это цель этой статьи. Я хочу познакомить вас с моими двумя основными методами сопоставления строк или методов расчета сходства:

1. Расстояние Левенштейна
2. Косинус сходство

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

Прочитав эту статью, вы сможете сделать следующее:

• Определите, какой алгоритм сходства подходит для вашей ситуации
• Реализуйте это на Python

Хорошо, готов нырнуть?Пошли.

Видео:Косинусное сходство (расстояние) в Python. Cosine Similarity in Python. #python , #pythoncodeСкачать

Расстояние Левенштейна

Давайте начнем с основного определения:

В В теории информации, лингвистике и информатике расстояние Левенштейна представляет собой строковую метрику для измерения разницы между двумя последовательностями. Неформально расстояние Левенштейна между двумя словами — это минимальное количество односимвольных правок (вставок, удалений или подстановок), необходимых для замены одного слова на другое. [1]

В самых простых словах вы можете рассчитать, сколько преобразований нужно выполнить для строки сделать его равным строкеВ, Алгоритм также известен какИзменить расстояниетак что, возможно, этот термин вам более знаком.

Чтобы использовать его в Python, вам нужно установить его, скажем, череззернышко:

Вот и все. Давайте теперь посмотрим, как его использовать.

Потому что ‘Левенштейн’Так сложно набрать правильно, и я уже говорил ранее, что я использую его в основном для обнаружения опечаток, это будет отличный первый пример. Но, во-первых, импорт:

Теперь вы готовы рассчитать расстояние:

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

Ранее я также говорил, что не буду использовать этот алгоритм для длинных строк или целых документов, и вот почему:

Как видите, оба предложения передают практически одинаковую информацию, но для перехода от одного к другому необходимо 20 преобразований. Поэтому, если вы установили автоматическое сопоставление строк ниже некоторого порога, 20, вероятно, не будет этим порогом, потому что он слишком велик для простых и коротких предложений, подобных этим двум.

Вот где его косинус-брат приходит на помощь.

Видео:Семинар 3 - Косинусное расстояние и близостьСкачать

Косинус сходство

Как и прежде, давайте начнем с некоторого базового определения:

Косинусное сходство — это мера сходства между двумя ненулевыми векторами внутреннего пространства произведений, которое измеряет косинус угла между ними. [2]

Я знаю, что это не самое чистое из определений, но я нахожу это достаточно хорошим. Это требует некоторых математических знаний, поэтому, если у вас их нет, пожалуйста, обратитесь к следующей статье (векторы в линейной алгебре):

Видео:Линейная алгебра в Python: точечное произведение векторов, корреляция Пирсона, косинусное расстояниеСкачать

Основы линейной алгебры с Numpy (часть 1)

Изучите основные навыки линейной алгебры для Data Science — часть 1/2

towardsdatascience.com

Хорошо, давай отгоним это еще дальше.

В определении говорится, что вы должны рассчитатьугол между двумя векторамипервый. Но вы не можете представить какое-то предложение в виде вектора в n-мерном пространстве просто из коробки.

Вы захотите построить векторное пространство из всех «предложений», для которых вы хотите рассчитать сходство. Это векторное пространство будет иметьстолько измерений, сколько уникальных слов во всех предложениях вместе взятых,

Хорошо, давайте сначала сделаем импорт, и я объясню все на лету:

Вам понадобитсястрокамодуль для удаления знаков препинания со строки — ‘приговор‘ а также ‘приговор.По умолчанию разные, и вы хотите избежать этого CountVectorizerпозаботится о преобразовании строк в числовые векторы, что тоже аккуратно. Наконец, поскольку эта статья написана на английском языке, вы хотите удалить наиболее часто встречающиеся слова, которые не имеют смысла — они называютсяигнорируемые слова— такие слова, как ‘я’,‘меня’,‘себя‘, так далее.

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

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

Помните импорт?Мы импортировали довольно много, и пришло время использовать это. Я объявлю функцию, которая будет делать следующее:

1. Удалить знаки препинания из заданной строки
2. Строчная строка
3. Удалить стоп-слова

Теперь вам не нужен цикл для применения этих преобразований к каждому предложению, вы можете использовать встроенныйкартафункция:

Отлично, подготовка почти завершена. Теперь вы будете использовать силуCountVectorizerсовершить магию (на самом деле, нет). Это создастКвекторы вNпространство, гдеКэто количество предложений, иNколичество уникальных слов во всех предложениях вместе взятых. Тогда, если предложение содержит определенное слово, значение будет 1 и 0 в противном случае:

И это все для подготовки. Было много (Что-то вроде), но это стоило того. Если вы теперь вычислите косинусное сходство из полученных числовых векторов, вы получите следующую матрицу:

Диагональные элементы 1, что имеет смысл, предложениеИкссовершенно «похож» на предложениеИкс, Однако разрезать эту матрицу неудобно, поэтому я решил определить функцию, которая будет вычислять сходство для двух заданных векторов. Имейте в виду, чтоcosine_similarity ()ожидаем двухмерные массивы, а входные векторы по умолчанию являются одномерными, поэтому нам нужно изменить форму:

И просто для подтверждения все работает:

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

Видео:6.1 Манхэттенское расстояние. "Поколение Python": курс для начинающих. Курс StepikСкачать

Прежде чем ты уйдешь

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

В качестве упражнения было бы неплохо найти набор данных некоторых немеченых электронных писем или другого текста и попытаться использовать метрики сходства, чтобы как-то сгруппировать их. Это также может быть хорошей идеей для вас, чтобы посмотреть наTF-IDFкак я не объяснил в этой статье.

В любом случае, спасибо за чтение, надеюсь, вам удалось извлечь из этого что-то полезное.

Видео:косинусное расстояниеСкачать

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

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

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

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

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

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

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

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

Интуитивно понятно, что для рекомендации пользователю №1 какого-либо продукта, выбирать нужно из продуктов, которые нравятся каким-то пользователям 2-3-4-etc., которые наиболее похожи по своим оценкам на пользователя №1. Как же получить численное выражение этой «похожести» пользователей? Допустим, у нас есть M продуктов. Оценки, выставленные отдельно взятым пользователем, представляют собой вектор в M-мерном пространстве продуктов, а сравнивать вектора мы умеем. Среди возможных мер можно выделить следующие:

1. Косинусная мера
2. Коэффициент корреляции Пирсона
3. Евклидово расстояние
4. Коэффициент Танимото
5. Манхэттенское расстояние и т.д.

Более подробно различные меры и аспекты их применения я собираюсь рассмотреть в отдельной статье. Пока же достаточно сказать, что в рекомендательных системах наиболее часто используются косинусная мера и коэффициент корреляции Танимото. Рассмотрим более подробно косинусную меру, которую мы и собираемся реализовать. Косинусная мера для двух векторов — это косинус угла между ними. Из школьного курса математики мы помним, что косинус угла между двумя векторами — это их скалярное произведение, деленное на длину каждого из двух векторов:

Реализуем вычисление этой меры, не забывая о том, что у нас множество оценок пользователя представлено в виде dict «продукт»:«оценка»

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

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

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

1. Выбрать L пользователей, вкусы которых больше всего похожи на вкусы рассматриваемого. Для этого для каждого из пользователей нужно вычислить выбранную меру (в нашем случае косинусную) в отношении рассматриваемого пользователя, и выбрать L наибольших. Для Ивана из таблицы, приведенной выше, мы получим следующие значения:
   
2. Для каждого из пользователей умножить его оценки на вычисленную величину меры, таким образом оценки более «похожих» пользователей будут сильнее влиять на итоговую позицию продукта, что можно увидеть в таблице на иллюстрации ниже
3. Для каждого из продуктов посчитать сумму калиброванных оценок L наиболее близких пользователей, полученную сумму разделить на сумму мер L выбранных пользователей. Сумма представлена на иллюстрации в строке «sum», итоговое значение в строке «result»
   
   Серым цветом отмечены столбцы продуктов, которые уже были оценены рассматриваемым пользователем и повторно предлагать их ему не имеет смысла

В виде формулы этот алгоритм может быть представлен как

где функция sim — выбранная нами мера схожести двух пользователей, U — множество пользователей, r — выставленная оценка, k — нормировочный коэффициент:

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

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

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

Видео:А.5.9 Евклидово расстояние между точками (длина отрезка)Скачать

Косинусное сходство в Python

Сходство косинуса измеряет сходство между списками векторов путем вычисления угла косинуса между двумя списками векторов. Если вы рассматриваете функцию косинуса, ее значение при 0 градусах равно 1 и -1 при 180 градусах. Это означает, что для двух перекрывающихся векторов значение косинуса будет максимальным и минимальным для двух точно противоположных векторов.

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

Видео:Евклидово расстояние на пальцах. Как определить расстояние между двумя точками.Скачать

Используйте модуль scipy для вычисления косинусного сходства между двумя списками в Python

Функция spatial.cosine.distance() из модуля scipy вычисляет расстояние вместо косинусного подобия, но для этого мы можем вычесть значение расстояния из 1.

Видео:6.3 Евклидово расстояние. "Поколение Python": курс для начинающих. Курс StepikСкачать

Используйте модуль NumPy для вычисления косинусного сходства между двумя списками в Python

Функция numpy.dot() вычисляет скалярное произведение двух векторов, переданных в качестве параметров. Функция numpy.norm() возвращает векторную норму.

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

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

Видео:Рассчитываем контекстную близость слов с помощью библиотеки Word2vecСкачать

Используйте модуль sklearn для вычисления косинусного сходства между двумя списками в Python

В модуле sklearn есть встроенная функция под названием cosine_similarity() для вычисления косинусного сходства.

Видео:Определение расстояния между двумя точками на Земле (Между координатами) с помощью pythonСкачать

Используйте модуль torch для вычисления косинусного сходства между двумя списками в Python

Когда мы имеем дело с N-мерными тензорами, имеющими формы (m, n), мы можем использовать функцию consine_similarity() из модуля torch , чтобы найти косинусное подобие.

💥 Видео

Скалярное произведение векторов. 9 класс.Скачать

Информатика. Вычисление расстояния Левенштейна. Центр онлайн-обучения «Фоксфорд»Скачать

Косинус угла между векторами. Коллинеарность векторовСкачать

Какую метрику выбрать? Евклидово расстояние, косинус или скалярное произведение?Скачать

Основы SciPy | Научные И Математические Вычисления На PythonСкачать

Лекция. Контестные эмбеддинги. Word2Vec.Скачать

A.7.38 Расстояние МахаланобисаСкачать

Математика это не ИсламСкачать