Какую задачу решает локально чувствительное хеширование документов

Shingling

На этом этапе мы конвертируем каждый документ внабор символов длиной k (также известный как k-черепица или k-грамм).Основная идея состоит в том, чтобы представлять каждый документ в нашей коллекции как набор k-черепиц.

Например: один из ваших документов (D): «Надаль». Теперь, если нас интересует 2-черепица, тогда наш набор: . Аналогично набор из 3-х черепиц: .

• Подобные документы имеют больше шансов
• Изменение порядка абзацев в документе с изменением слов не сильно влияет на опоясывающий лишай
• значение k 8–10обычно используется на практике. Небольшое значение приведет к множеству черепицы, которые присутствуют в большинстве документов (плохо для дифференциации документов)

Жакард Индекс

У нас есть представление каждого документа в виде черепицы. Теперь нам нужен показатель для измерения сходства между документами. Jaccard Index — хороший выбор для этого. Индекс Жакара между документами A и B можно определить как:

Это также известно какпересечение над объединением (IOU),

Предположим, что A: «Надаль» и B: «Надя», тогда представление с двумя черепицами будет:

Индекс Жакара = 2/6

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

Давайте обсудим 2 больших вопроса, которые нам нужно решить:

Сложность времени

Теперь вы можете думать, что мы можем остановиться здесь. Но если вы думаете о масштабируемости, выполнение только этого не сработает. Для сбора n документов необходимо сделатьп * (п-1) / 2сравнение, в основномO (N²), Представьте, что у вас есть 1 миллион документов, тогда число сравнений будет 5 * 10¹¹ (не масштабируется вообще!).

Пространство сложности

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

Идея хеширования состоит в том, чтобы преобразовать каждый документ в небольшую подпись, используя функцию хеширования.ЧАС,Предположим, что документ в нашем корпусе обозначается какд.Затем:

• H (d) — подпись, и она достаточно мала, чтобы уместиться в памяти
• ЕслиСходство (d1, d2)высокая тогдаВероятность (Н (d1) == Н (d2))в приоритете
• ЕслиСходство (d1, d2)то низкоВероятность (Н (d1) == Н (d2))низок

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

Минимальное перемешивание

Это критический и самый магический аспект этого алгоритма, поэтому обратите внимание:

Шаг 1:Случайная перестановка(Π)изиндекс строкиматрицы гальки документа

Шаг 2:Хеш-функция являетсяиндекс первой (в перестановочном порядке) строки, в которой столбец C имеет значение 1.Сделайте это несколько раз (используйте разные перестановки), чтобы создать подпись столбца.

Свойство Min-hash

Сходство сигнатур — это доля мин-хеш-функций (строк), в которых они согласуются. Таким образом, сходство подписи для C1 и C3 составляет 2/3, поскольку 1-я и 3-я строки одинаковы.

Ожидаемое сходство двух подписей равно схожести столбцов Жакара. Чем длиннее подписи, тем ниже ошибка

В приведенном ниже примере вы можете увидеть это в некоторой степени. Есть разница, так как у нас есть подписи только длины 3. Но если увеличить длину, 2 сходства будут ближе.

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

Локальное хеширование

Цель: найти документы со сходством Жакара, по крайней мере, t

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

Специально для минимальной хэш-матрицы подписи:

• Хеш столбцы матрицы подписиMиспользуя несколько хеш-функций
• Если 2 документа хэшируются в одно и то же ведро дляхотя бы одиниз хеш-функции мы можем взять 2 документа в качестве пары кандидатов

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

Ленточная перегородка

• Разделите матрицу подписи наб полосыкаждая группа имеетг строк
• Для каждой полосы, хэшируйте свою часть каждого столбца в хеш-таблицу сk ведер
• Пары столбцов-кандидатов — это те, которые хэшируют в одно и то же ведро длякак минимум 1 полоса
• Настройте b и r, чтобы поймать большинство похожих пар, но несколько не похожих пар

Здесь есть несколько соображений. В идеале для каждой полосы мы хотим принять k равным всем возможным комбинациям значений, которые столбец может принимать в пределах полосы. Это будет эквивалентно сопоставлению идентичности. Но в этом случае k будет огромным числом, которое вычислительно невозможно. Например: если для группы у нас есть 5 строк. Теперь, если элементы в сигнатуре являются 32-битными целыми числами, тогда k в этом случае будет (2³²) ⁵ ~ 1.4615016e + 48. Вы можете увидеть, в чем проблема здесь. Обычно k берется около 1 миллиона.

Идея состоит в том, что если 2 документа похожи, то они появятся как пара кандидатов, по крайней мере, в одной из полос.

Выбор B & R

Если мы возьмем b большое, то есть большее число хеш-функций, мы уменьшим r, так как b * r является константой (количество строк в матрице сигнатур). Интуитивно это означает, что мыувеличение вероятности нахождения пары кандидатов.Этот случай равносилент (порог сходства)

Допустим, ваша матрица подписи имеет 100 строк. Рассмотрим 2 случая:

Во 2-м случае выше вероятность того, что 2 документа появятся в одной корзине хотя бы один раз, поскольку они имеютбольше возможностей (20 против 10)а такжесравнивается меньше элементов подписи (5 против 10).

Чем выше б, тем нижеПорог сходства (выше ложных срабатываний), а более низкий b означает более высокий порог сходства (выше ложных срабатываний)

Давайте попробуем понять это на примере.

Настроить:

• 100к документов хранятся в виде подписи длиной 100
• Матрица подписи: 100 * 100000
• Сравнение подписей методом грубой силы приведет к сравнению 100C2 = 5 миллиардов (довольно много!)
• Давайте возьмем b = 20 → r = 5

порог сходства (т): 80%

Мы хотим, чтобы 2 документа (D1 и D2) со схожестью 80% хэшировались в одном и том же сегменте как минимум для одной из 20 полос.

P (D1 и D2 идентичны в определенной полосе) = (0,8) ⁵ = 0,328

P (D1 и D2 не одинаковы во всех 20 полосах) = (1–0,328) ^ 20 = 0,00035

Это означает, что в этом сценарии у нас есть ~ 0,035% вероятности ложного отрицания на 80% похожих документов.

Также мы хотим, чтобы 2 документа (D3 и D4) с 30% сходством не хэшировались в одном и том же сегменте ни для одной из 20 полос (порог = 80%).

P (D3 и D4 идентичны в определенной полосе) = (0,3) ⁵ = 0,00243

P (D3 и D4 похожи, по крайней мере, в одной из 20 полос) = 1 — (1–0,00243) ^ 20 = 0,0474

Это означает, что в этом сценарии у нас есть ~ 4,74% вероятности ложного срабатывания при 30% аналогичных документов.

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

То, что мы хотим здесь, это что-то вроде ниже Если у нас есть 2 документа, сходство которых превышает пороговое значение, то вероятность их совместного использования в одном и том же сегменте хотя бы в одной из полос должна составлять 1, иначе 0.

Наихудший случай будет, если у насb = количество строк в матрице подписикак показано ниже.

Обобщенный случай для любых b и r приведен ниже.

Выберите b и r, чтобы получить лучшую S-кривую, т.е. минимальный уровень ложных отрицательных и ложных положительных результатов.

Резюме по LSH

• мелодияМ, б, гполучить почти все пары документов с одинаковыми подписями, но исключить большинство пар, которые не имеют схожих подписей
• Проверьте в основной памяти, чтопары-кандидатыдействительно естьпохожие подписи

Вывод

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

Ссылки

1. http://joyceho.github.io/cs584_s16/slides/lsh-11.pdf
2. https://www.youtube.com/watch?v=96WOGPUgMfw
3. https://eng.uber.com/lsh/
4. https://medium.com/engineering-brainly/locality-sensitive-hashing-explained-304eb39291e4
5. http://www.mit.edu/~andoni/LSH/

Какую задачу решает локально чувствительное хеширование документов

Некоторые курсы, возможно, открыты для гостей

Войти с использованием учетной записи:

Universitatea de Stat „Alecu Russo” din Bălți este o instituție de învățământ superior fondată în anul 1945, cu o istorie bogată, tradiții și experiență, care își asumă rolul promotor al excelenței științifice, educaționale și culturale în societate.

Быстрые ссылки

Подписывайтесь на нас

Контакт

str.Puşkin 38, mun.Bălţi, Republica Moldova

Phone: (231) 52-382

Copyright © 2020 — 2021 Universitatea de Stat „Alecu Russo”. Dezvoltată de Moodle

Какую задачу решает локально чувствительное хеширование документов

Похожие документы

BIB onlayn kvantovyy

Добавить этот документ в коллекции

Вы можете добавить этот документ в свои учебные коллекции

Войти Доступно только авторизованным пользователям

Добавить этот документ в сохраненные

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

Войти Доступно только авторизованным пользователям

Разделы

Поддержка

© 2013 — 2024 studylib.net — Все товарные знаки и авторские материалы, находящиеся в документах, принадлежат их владельцам.

Предложить улучшение

Нашли ошибку в текстах или интерфейсе? Или знаете, как улучшить наши инструменты? Смело отправляте нам свои предложения! Это очень важно для нас!

ПРИКЛАДНАЯ МАТЕМАТИКА И ИНФОРМАТИКА: СОВРЕМЕННЫЕ ИССЛЕДОВАНИЯ В ОБЛАСТИ ЕСТЕСТВЕННЫХ И ТЕХНИЧЕСКИХ НАУК

Благодаря многим исследованиям в области проектирования СВЧ транзисторов, разработаны следующие популярные технологии их производства: sic, gaas, gan. Несмотря на достижения в областях sic и gaas технологий, которые уже несколько лет удовлетворяют всем потребностям военно-промышленного комплекса в области проектирования и разработки монолитных интегральных схем, растут потребности в более высокоэффективных технологиях, то есть технологиях на основе gan . Данные устройства обладают более высоким КПД (практически в 1,5 раза превышающим КПД устройств на основе sic и gaas), более широким спектром рабочих частот, высокой мощностью и линейностью характеристик.

See Full PDF
See Full PDF

Related Papers

Вестник СПбГУ. Сер. 17

В статье рассматривается одна из наиболее интенсивно развивающихся сегодня отраслей искусства, существующая на стыке науки, техники и современной культуры,-science-art. В статье анализируется роль информационных технологий в эстетике научного искусства. Предпринята попытка охарактеризовать science-art с точки зрения, во-первых, актуальных эстетических исследований и, во-вторых, актуальных научно-технических разработок. Ста-вится вопрос о месте принципов классического эстетического анализа в современной техно-генной и техноцентричной цивилизации. Библиогр. 26 назв. Ключевые слова: science-art, классический эстетический анализ, эстетический субъект, IT-технологии. A. A. Lvov SCIENCE-ART: MODERN TECHNOLOGIES IN THE CONTEXT OF THE CONTEMPORARY AESTHETICS Th e paper considers one of the most intensively developing genre in the modern art that exists in the interdisciplinary fi eld of modern science, technology and cultural studies. We mean the science-art. One of the main objectives here is to study how technology is involved in the creative and artistic process. In addition, it is necessary to make and ground the attempt to characterize science-art in terms of, fi rstly, the current aesthetical studies, and secondly, the current scientifi c and technical movements. Hereby we face with the question of existence of the classical aesthetical analysis in the modern tech-nogenic and technocentric civilization. Refs 26.

Download Free PDF View PDF

SHRINES AND HOLY PLACES ASSOCIATED WITH ORNAMENTAL NAQSHBANDI-MUJADDID

Download Free PDF View PDF

Education in the modern world gains new value. Educational institutions seek to use new technologies in educational process. Practice proves that the most effective way is a combination of traditional and innovative methods of training. Evolution of traditional methods of training is connected with integration process. Integration is shown in all fields of activity of educational institution. It is integration in the sphere of exchange of experience, joint investment of educational programs, and also integration of methods of training. Integration of traditional and innovative methods of training is actual for mathematical, public and economic disciplines. Traditional technologies, being integrated with innovative, allow to keep order and working creative climate in audience, as much as possible to realize the set competences

Download Free PDF View PDF

Download Free PDF View PDF

Тенденции развития легкой промышленности в Республике Узбекистан: проблемы, анализ и пути решения

Download Free PDF View PDF

Nowadays, the innovative activities are considered as the mechanism of implementation of public policy to increase effectiveness of public health system on the basis of achievements of modern medicine and technical sciences. The development, elaboration and implementation of products being in line with corresponding to criteria of innovation, promote the concurrency of medical institutions at the medical services market. The administrators of health departments and medical science professionals are to become aware about the problems of implementation of innovations into medical practice to develop the mechanisms of overcoming these issues.

Download Free PDF View PDF

Download Free PDF View PDF

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

Download Free PDF View PDF

Монографията „СЪВРЕМЕННИ МЕТОДИ И ИНФОРМАЦИОННО-КОМУНИКАЦИОННИ ТЕХНОЛОГИИ В ОБУЧЕНИЕТО ПО ЧУЖД ЕЗИК“ е посветена на методите и информационно-комуникационните технологии, използвани в чуждоезиковото обучение. Разгледани са техните особености, историята на възникването и развитието им. Представени са и примери за конкретно приложение на съвременните методи и технологии в чуждоезиковото обучение в Колежа по туризъм – Варна. Настоящата монография е част от научноизследователски проект № НП-47 на тема „Изграждане на Мултимедийна езикова лаборатория – теоретични и практически предпоставки“, одобрен от Икономически университет – Варна.

Download Free PDF View PDF

В настоящее время мировая экономика и общество сталкиваются с множеством глобальных вызовов. К таким вызовам относятся: обеспечение водными ресурсами, энергетическая безопасность, обеспечение здоровья и благосостояния населения, устойчивое развитие и изменение климата, старение населения и демографические проблемы, продовольственная безопасность и др. Решение многих экономических, социальных, экологических и других проблем выходит за рамки отдельных государств и становится возможным лишь на региональном или международном уровне [Silberglitt et al., 2006, p. 19]. Процесс глобализации науки нашел отражение в бурном росте научно-технического потенциала Китая, а также быстром развитии некоторых сфер науки и технологий Индии и Бразилии. Новые игроки появляются на Ближнем Востоке и в Юго-Восточной Азии, малые европейские страны укрепляют свои позиции. Тем не менее наиболее крупными инвесторами остаются США, государства Западной Европы и Япония, в то время как менее развитые страны борются за улучшение своих позиций. Формируется многополярный научный мир, базирующийся на продолжающемся укреплении лидерства традиционных научных центров и возникновении новых игроков, таких как страны БРИК [ICSU, 2011, p. 8]. Международное сотрудничество должно способствовать модернизации экономики России, выходу на мировой уровень научных результатов по направлениям, связанным с национальными научно-технологическими приоритетами и критическими технологиями.

Download Free PDF View PDF