Косинусная мера близости векторов (6 видео)

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

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

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

Содержание

Метрики сходства и расстояния для науки о данных и машинного обучения
Анализ методов определения текстовой близости документов
Аннотация
Общая постановка проблемы
Введение
Метод шинглов
Методы, основанные на векторной модели представления документов
📸 Видео

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Видео:18+ Математика без Ху!ни. Скалярное произведение векторов. Угол между векторами.Скачать

Метрики сходства и расстояния для науки о данных и машинного обучения

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

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

Примечание: помните, что вся моя работа, включая специальный репозиторий с применением всего этого контента и больше о Системах Рекомендаций, доступна в моемПрофиль GitHub,

В любом типе алгоритма наиболее распространенной мерой подобия является нахождение косинуса угла между векторами, то есть сходства косинусов. Предположим, что A — это список фильмов с рейтингом пользователя, а B — список фильмов с рейтингом пользователя B, тогда сходство между ними можно рассчитать как:

Математически косинусное сходство измеряет косинус угла между двумя векторами, спроецированными в многомерном пространстве. При построении в многомерном пространстве косинусное сходство фиксирует ориентацию (угол) каждого вектора, а не величину. Если вы хотите получить величину, вместо этого вычислите евклидово расстояние.

Сходство по косинусу выгодно, потому что даже если два одинаковых документа находятся далеко друг от друга на евклидовом расстоянии из-за размера (например, одно слово, появляющееся много раз в документе, или пользователь, часто видящий один фильм), они все равно могут иметь меньший угол между ними. Чем меньше угол, тем выше сходство.

На изображении выше показано количество появлений слов «sachin», «dhoni» и «cricket» в трех показанных документах. В соответствии с этим мы могли бы построить эти три вектора, чтобы легко увидеть разницу между измерением косинуса и евклидова расстояния для этих документов:

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

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

Предположим, пользователь дает оценки в 0

5 для двух фильмов.

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

Кстати, в нашемпредыдущая статья о Системах Рекомендациймы представили следующую функцию, чтобы найти скорректированное косинусное сходство:

И вы можете использовать эту функцию очень просто, просто кормя:

«Матрица»: это просто исходная матрица рейтингов, просмотров или того, что вы измеряете между пользователями и элементами вашего бизнеса
«Row_columns»: указывает 1, если вы будете измерять расстояния между столбцами, и 0 для расстояний между рядами
«Размер»: для желаемого размера результирующей матрицы. То есть при поиске сходства пользователей или элементов это будет просто количество пользователей или элементов. Таким образом, если у вас есть 500 уникальных пользователей, вы получите матрицу расстояний 500×500

Возьмите следующий пример в качестве ссылки:

Наконец, давайте кратко рассмотрим некоторые другие методы, которые можно использовать для вычисления подобия для систем рекомендаций, но также и для любого другого алгоритма на основе расстояния в машинном обучении:

Евклидово расстояние: похожие элементы будут лежать в непосредственной близости друг от друга, если они нанесены в n-мерном пространстве.

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

Анализ методов определения текстовой близости документов

Автор: Сторожук Н.О., Коломойцева И.А.
Источник: Материалы студенческой секции IX Международной научно-технической конференции «Информатика, управляющие системы, математическое и компьютерное моделирование» (ИУСМКМ-2018). – Донецк: ДонНТУ, 2018. – С. 43-47.

Аннотация

Сторожук Н.О., Коломойцева И.А. — Анализ методов определения текстовой близости документов В работе представлен обзор основных алгоритмов вычисления меры сходства документов, используемых в поисковых системах и анализаторах текстов. Приведен пример расчетов близости тестовых документов, на основе полученных данных сделаны выводы о возможности использования одного из методов в системе, определяющей жанр исследуемого текста.

Общая постановка проблемы

Поиск семантического сходства между текстами является серьёзной проблемой для автоматической обработки текста. Необходимость поиска расстояния между документами возникает в различных задачах, таких как обнаружение плагиата, определение авторства документа, поиск информации, машинный перевод, формирование тестов и задач, автоматическое построение рефератов и пр. Поиску семантической схожести текстов было уделено внимание в рамках многих международных и российских конференций такими авторами как Красников И.А., Керимова С.У., Ермоленко Т.В., Бермудес С.Х.Г. 1.

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

Введение

Автоматическая обработка текста – это преобразование текста на искусственном или естественном языке с помощью компьютера [4]. В настоящее время элементы обработки текста применяются повсеместно: переводчики, текстовые редакторы, программы для антиплагиата и автореферирования, анализаторы новостей, оптимизаторы программного кода и т.д. Следовательно, задачи эффективной автоматизированной обработки текстов остаются актуальными, стабильное увеличение объёма информации требует постоянного совершенствования алгоритмов и подходов.

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

метод шинглов;
скалярное произведение векторов;
евклидово расстояние;
манхэттенское расстояние;
метод косинусной меры сходства;
латентно – семантический анализ, основанный на разложении матрицы по методу сингулярного разложения (SVD — singular value decomposition).

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

Метод шинглов

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

приведение текста к единой нормальной форме;
разбиение на шинглы заданной длины;
вычисление хешей шинглов;
случайный выбор 84 значений контрольных сумм;
сравнение сумм, определение результата [5].

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

Шинглы – выделенные из статьи последовательности слов. Из сравниваемых текстов необходимо выделить определенное число слов (обычно используют 10 слов), идущих друг за другом. Выборка происходит внахлест, таким образом в результате получается набор шинглов для каждого исследуемого документа.

Принцип алгоритма шинглов заключается в сравнении случайной выборки контрольных сумм шинглов (подпоследовательностей) двух текстов между собой. Так как число шинглов каждого документа приближается к числу слов этого документа, основной проблемой использования алгоритма является низкая скорость. Увеличение исходных текстов характеризуется экспоненциальным ростом операций сравнения, что критически отразится на производительности [7].

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

Методы, основанные на векторной модели представления документов

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

Предположим, что каждую тему можно охарактеризовать определенным набором слов и частотой их появления. Если в тексте конкретный набор слов употребляется с определенными частотами, то текст принадлежит к определенной теме. На основании этой информации строится таблица «слово-документ», где строки соответствуют терминам, полученным после канонизации, а столбцы – исследуемым документам. В каждой ячейке может храниться булево значение, которое показывает наличие хотя бы одного вхождения термина в документ, частота слова в документе или вес термина. Такой способ представления текстов в виде таблицы (или матрицы) называется векторной моделью текста [8]. Теперь, для того чтобы сравнить два документа, нужно определить меру схожести двух столбцов таблицы.

Для анализа методов были выбраны исходные данные, представленные ниже (рис. 1). Здесь q – эталонный документ (запрос), а d1, d2, d3 – документы, которые надо проанализировать на схожесть с q. Размеры документов практически одинаковы, таким образом предварительную нормировку длины производить не требуется.

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

Таблица 1 — Показатели числа документов ( tf)