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

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

  • автор:

Русские Блоги

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

Базовая мысль

Основная идея локального чувствительного хеширования аналогична идее преобразования пространственного домена. Алгоритм LSH основан на гипотезе. Если два текста аналогичны в исходном пространстве данных, то после преобразования хешей.У них также есть высокое сходство; обратное, если они не похожи, у них все еще есть сходство после перехода.

Хаш-функция, все должны быть знакомы, то какую функцию хэша может иметь вышеуказанные функции, вы можете сохранить сходство до и после преобразования данных? Конечно, ответ является частичным чувствительным хэшем.

2. Частичный чувствительный хэш LSH

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

Предположим, что хеш-функция — это хэш (x) = x% 8, то теперь у нас есть три данных из 255, 257 и 1023, мы знаем, что 255 и 257 сам есть небольшой разрыв в ценностях, то есть они в трех похоже в более чем один. Мы преобразуем три данных, описанные выше через хеш-функцию:

Hash(255) = 255%8 = 7;

Hash(257) = 257%8 = 1;

Hash(1023) = 1023%8 = 7;

Мы можем видеть приведенные выше результаты преобразования, которые 255 и 257, которые очень похожи на преобразование, и 255 и 1023, которые очень разные, и получаются одинаковые результаты преобразования. Из этого примера мы можем видеть, что вышеупомянутая хеш-функция из численного угла сходства не является локальным чувствительным хэшем, потому что сходство данных после нее потеряно.

Мы говорим, что местные чувствительные хэшиные требования могут поддерживать сходство данных, поэтому многие люди подозревают, что такая функция хэша действительно существует. Давайте подумаем о таком экстремальном состоянии, при условии, что локальная чувствительная хэш-функция имеет 10 различных выходных значений, и теперь у нас есть 11 данных, которые полностью сходятся, тогда они должны иметь как минимум два в этой хеш-функции. Неподобные данные изменяется в аналогичные данные. Отказ Из этого предположения мы должны понимать, что локальный чувствительный хэшотносительноИ сходство данных о техническом обслуживании, которое мы сказали, не сохраняют 100% сходство, ноПоддерживать максимальную вероятность。

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

3. Расчет сходства документов

Используя LSH для реализации сходства документа, мы введем конкретное использование LSH.

Предположим, что есть 4 веб-страницы, мы используем их поглощение (сопоставление строки, чтобы запрашивать, отображать его в коллекцию, например, «aBCDeeee», сопоставлена ​​на коллекцию «(a, b, c, d, e ) «, Обратите внимание, что элементы в коллекции не являются повторением. Этот шаг называется поглощением, что означает, что коллекция коротких строк в документе, то есть коллекция шаги.), Получите следующую функцию MATRIX:

«1» представляет черепица в соответствующей позиции «0», «0», не появился.

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

Наша цель — найти такую ​​хеш-функцию. Если сходство JACCARD в документе высока, то их хеш-значение является той же вероятностью, если сходство Jaccard исходного документа низкая, то их значения хеш-сигнала не одинаковы Вероятность мы называем Min-Hashing (незначительный харц).

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

Минимальное значение хеша: H (S1) = 3, H (S2) = 5, H (S3) = 1, H (S4) = 2.

Почему определить минимальный хэш? На самом деле, наименее хэш-ценность двух колонн — это оценка двух столбцов сходства jaccard. Другими словами, вероятность двух столбцов равна их сходству, то есть p (h (Si) = h (Sj )) = SIM (Si, Sj). Почему это равно? Рассмотрим эти два столбца SI и SJ, все возможные результаты их линий можно разделить на следующие три категории:

(1) Класс A: значение двух столбцов составляет 1;

(2) Класс B: одно из значений 0, значение другого составляет 1;

(3) Класс C: значения двух столбцов 0.

Характерная матрица довольно редкая, что приводит к большинству строк, принадлежащих к классу C, но только SIM-карту A и B (Si, Si), предположим, что категория A, B, B, SIM (SI, SI, SJ) = A / (A + B). Теперь нам нужно только доказать, что матричная строка случайно расположена, вероятность P (h (Si) = h (Sj)) = A / (A + B) удаляется, если мы удаляем класс C Oharid, затем первая строка Разве класс ряд — линия B-класса. Если первая строка представляет собой категорию, h (Si) = h (Sj), таким образом p (h (Si) = h (Sj)) = p (после класса Строка C удалена, первая строка — это класс A) = номер A / Количество строк / количество строк = A / (A + B), это самая маленькая магия хэш.

Конкретный подход Min-Hashing можно выразить следующим образом:

Вернуться к нашему экземпляру, мы сначала генерируем кучу случайной замены, замените каждую строку матрицы функций, а затем функция хеша определяется как значение столбца C HASHH: находится на замене Column C, номер строки ряд значения 1. Как показано ниже:

На рисунке показаны три замены, три из цветных, я теперь объясняю один из них, а остальные два. Например, теперь посмотрите на синюю версию, матрицу подписи после замены:

Затем посмотрите на первый столбец — первая строка — это первая строка. Это вторая строка. То же самое одинаково, а две или четыре столбца разделены. Они 1, 2, 1, поэтому эти четыре трека (четыре Документы) При этой замене он составляет 2, 1, 2, 1, что является синей частью на правой картинке, которая эквивалентна каждому документу составляет 1 размерность. Затем на два других замены, а затем имеют две строки справа, конечный результат заключается в том, что каждый документ упал с 7 до 3 дней. Давайте посмотрим на сходство после измерения, то есть таблица в правом нижнем углу дает сходство между двумя двумя двумя двумя двумя двумя двумя. Можно увидеть, все еще довольно точны, вспоминая только что говоря: я надеюсь, что JACCard оригинала документов высока, то их значение HASH является той же вероятностью, если JACCard оригинала документов аналогична, то их значения хеш-сигнала разные Высокая вероятность, как сделать вероятность гарантий? Мин-хеширование имеет удивительную природу:

То есть для двух документов,В методе Min-Hashing их хеш-значения равны сходством Jaccard, прежде чем они упали.

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

Архитектура децентрализованной рекомендующей системы, основанной на применении локально-чувствительного хеширования Текст научной статьи по специальности «Компьютерные и информационные науки»

Аннотация научной статьи по компьютерным и информационным наукам, автор научной работы — Пономарев Андрей Васильевич

Постановка проблемы: рекомендующие системы широко используются в современных системах электронной коммерции, помогая пользователям ориентироваться в многообразии предлагаемых товаров и услуг. Наибольшее распространение получили централизованные архитектуры построения таких систем. Однако централизация влечет за собой ряд недостатков, среди которых необходимость передачи пользователем сведений о предпочтениях стороне, осуществляющей эксплуатацию такой системы, и наличие единой точки отказа. Цель: построение децентрализованной рекомендующей системы , в которой для формирования рекомендаций используется сходство предпочтений пользователей ( коллаборативная фильтрация ), но полные сведения о предпочтениях хранятся только на узле, контролируемом самим пользователем, и не передаются другим узлам. Результаты: предложена архитектура децентрализованной рекомендующей системы , включающая структурированную одноранговую сеть , в которой каждый узел соответствует одному пользователю и хранит профиль его предпочтений, и специальный узел для информационного согласования участников сети. В качестве механизма, обеспечивающего, с одной стороны, поиск пользователей со схожими предпочтениями, а с другой стороны, ограниченное раскрытие информации о предпочтениях, используется локально-чувствительное хеширование . Для повышения уровня приватности пользователей в одноранговой сети применяется схема анонимизации. Практическая значимость: предложенный подход является достаточно универсальным и может быть использован для построения систем коллаборативной фильтрации в различных прикладных областях.

Похожие темы научных работ по компьютерным и информационным наукам , автор научной работы — Пономарев Андрей Васильевич

Decentralized Recommendation System Architecture Based on Locality-Sensitive Hashing

Purpose: Recommendation systems are widely used in modern e-commerce systems to help users make their ways in a vast variety of offered goods and services. Most of the modern recommendation system approaches are centralized. However, centralized recommendation have two primary disadvantages: the necessity for users to share their preferences and a single point of failure. The goal of this work is developing a decentralized recommendation system which employs user similarity ( collaborative filtering ) but holds all the user preferences only on the user’s network node. Results:An architecture is proposed for a decentralized recommendation system. It includes a structured peer-to-peer network in which each node corresponds to one user and stores this user’s preferences, and a special node used for the coordination of peer-to-peer nodes in some scenarios. To find users with similar interests and, in the same time, restrict the sharing of preferences, a locality-sensitive hashing is employed. For a higher level of privacy, the network uses an anonymization scheme. Practical relevance: The proposed approach is universal, as it relies only on ratings, and can be used to build collaborative filtering systems in various domains.

Текст научной работы на тему «Архитектура децентрализованной рекомендующей системы, основанной на применении локально-чувствительного хеширования»

АРХИТЕКТУРА ДЕЦЕНТРАЛИЗОВАННОЙ РЕКОМЕНДУЮЩЕЙ СИСТЕМЫ, ОСНОВАННОЙ НА ПРИМЕНЕНИИ ЛОКАЛЬНО-ЧУВСТВИТЕЛЬНОГО ХЕШИРОВАНИЯ

А. В. Пономарева, канд. техн. наук, старший научный сотрудник

аСанкт-Петербургский институт информатики и автоматизации РАН, Санкт-Петербург, РФ

Постановка проблемы: рекомендующие системы широко используются в современных системах электронной коммерции, помогая пользователям ориентироваться в многообразии предлагаемых товаров и услуг. Наибольшее распространение получили централизованные архитектуры построения таких систем. Однако централизация влечет за собой ряд недостатков, среди которых — необходимость передачи пользователем сведений о предпочтениях стороне, осуществляющей эксплуатацию такой системы, и наличие единой точки отказа. Цель: построение децентрализованной рекомендующей системы, в которой для формирования рекомендаций используется сходство предпочтений пользователей (коллаборативная фильтрация), но полные сведения о предпочтениях хранятся только на узле, контролируемом самим пользователем, и не передаются другим узлам. Результаты: предложена архитектура децентрализованной рекомендующей системы, включающая структурированную одноранговую сеть, в которой каждый узел соответствует одному пользователю и хранит профиль его предпочтений, и специальный узел для информационного согласования участников сети. В качестве механизма, обеспечивающего, с одной стороны, поиск пользователей со схожими предпочтениями, а с другой стороны, ограниченное раскрытие информации о предпочтениях, используется локально-чувствительное хеширование. Для повышения уровня приватности пользователей в одноранговой сети применяется схема анонимизации. Практическая значимость: предложенный подход является достаточно универсальным и может быть использован для построения систем коллаборативной фильтрации в различных прикладных областях.

Ключевые слова — локально-чувствительное хеширование, одноранговые сети, рекомендующие системы, коллаборативная фильтрация.

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

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

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

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

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

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

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

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

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

В данной статье предложена архитектура рекомендующей системы, включающая структурированную одноранговую (P2P) сеть, в которой каждый узел соответствует одному пользователю и хранит профиль его предпочтений, и специальный узел для информационного согласования участников сети. Такой подход может быть классифицирован как гибридная одноранговая сеть, в которой часть функций выполняется исключительно посредством взаимодействия между равноправными узлами, а часть функций требует наличия специального узла. Предлагаемая архитектура обеспечивает ограниченное раскрытие предпочтений — не существует способа одновременно получить оценки, которые пользователь присвоил объектам, и сетевой адрес пользователя без глобального контроля над сетью.

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

В системе P2Prec [1, 2] для распространения запросов и рекомендаций используется комбинация так называемого «дружеского» подхода к построению структуры сети (friend-of-a-friend), когда связи устанавливаются только между знакомыми пользователями, и лавинных алгоритмов распространения запросов.

В ряде описанных методов происходит построение оверлейной структуры, соответствующей близости интересов пользователей, поверх одноранговой сети [3, 4]. Рекомендации формируются поиском по оверлейной структуре на определенную глубину. Одним из распространенных алгоритмов такого «выравнивания» структуры сети под отношения между узлами является T-Man [5]. В данной работе сами оценки пользователя не раскрываются узлом сети, поэтому напрямую использовать T-Man или какой-либо схожий алгоритм нельзя из-за невозможности определить сходство узлов.

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

Есть также работы, в которых авторы исследуют возможность применения структурированных одноранговых сетей для построения рекомендующих систем. Например, в работах [8, 9] оценки, присваиваемые объектам пользователями, сохраняются в распределенной хеш-таблице (Distributed Hash Table — DHT). Отличие предлагаемого в данной статье подхода заключается в том, что в распределенную хеш-таблицу помещаются не оценки, а сами узлы, и механизм быстрого поиска по этой таблице используется для поиска узлов, соответствующих пользователям со схожими интересами.

Формирование рекомендаций с помощью локально-чувствительного хеширования

(ЛЧХ) — это широко распространенный метод приближенного решения задачи поиска k ближайших соседей. Идея метода состоит в построении такой хеш-функции многомерных объектов, чтобы схожие объекты с высокой вероятностью получали одинаковое значение хеш-функции. Методы и алгоритмы поиска ближайших соседей находят широкое применение при построении

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

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

Описание базовых идей ЛЧХ приводится в соответствии с работой [10]. Пусть d1 < d2 — два значения расстояния в соответствии с некоторой мерой d. Семейство функций F называется (d1, d2, p1, р2)-чувствительным, если для каждой функции f в F:

— если d(a, b) < d1, то вероятность того, что f(a) = f(b), не меньше p1;

— если d(a, b) > d2, то вероятность того, что f(a) = f(b), не больше p2.

Важной идеей в теории ЛЧХ является усиление, в основе которого лежат понятия И-конструкции и ИЛИ-конструкции, определенные ниже.

Пусть задано (d1, d2, p1, р2)-чувствительное семейство функций F, новое семейство функций F' может быть получено посредством И-кон-струкции или ИЛИ-конструкции.

И-конструкция F' определяется следующим образом. Каждый член F' состоит из r членов F. Если f в F' и f получена из множества членов F, то f(x) = f(y) тогда и только тогда, когда ft(x) = ft(y) для всех i е <1, . r>. Поскольку члены F' независимо выбираются из F, F' является (d1, d2, p[, pr)-чувствительным семейством функций [10].

ИЛИ-конструкция F' определяется следующим образом. Каждый член F' состоит из b членов F. Если f в F' и f получена из множества членов F, то f(x) = f(y) тогда и только тогда, когда существует i е <1, . b>такой, что fi(x) = fi(y). Аналогично F' является (d1, d2, 1 — (1 — p1)b, 1 — (1 — p2)b)-чувствительным семейством.

Как правило, желательно, чтобы p1 было большим, насколько возможно, а p2 маленьким, насколько возможно. Если p1 < 1, то существует вероятность того, что схожие объекты будут иметь различные значения. С другой стороны, если p2 > 0, есть вероятность, что значительно различающиеся объекты получат одинаковое значение хеш-функции. Следовательно, семейство F следует выбирать таким образом, чтобы p1 было близко

к 1, а p2 близко к 0. Существует определенный набор хорошо изученных семейств локально-чувствительных функций, механизм усиления применяется в том случае, если только лишь средствами выбранного семейства не удается достичь желаемых вероятностей. Если семейство FAr получено И-конструкцией r функций из семейства F, а G затем получено ИЛИ-конструкцией b функций из семейства FAr, то G является (d1, d2, 1 — (1 — p1r)b, 1 — (1 — p2r)b)-чувствительным семейством. Неформально И-конструкция снижает изначально невысокую вероятность p2, а последующая ИЛИ-конструкция повышает изначально высокую вероятность p1.

Идея поиска ближайших соседей с помощью ЛЧХ описана, например, в работах [10, 11]. В первую очередь выбирается семейство F и создаются b обычных хеш-таблиц. Каждая таблица соответствует одной хеш-функции fAr, i = 1, . b, где fAi r — И-конструкция r случайных функций из F. Каждый объект x помещается в каждую из b хеш-таблиц. Ключом является значение функции fiAr(x), а значением — идентификатор объекта x или сам объект, в зависимости от задачи. При поиске ближайших соседей объекта y вычисляются fJAr(y), i = 1, . b; все объекты, извлеченные из хеш-таблиц по полученным ключам, образуют множество кандидатов. Реальная близость оценивается уже с применением строгой меры, и происходит отсев ложно-положительных соседей из множества кандидатов.

Выбор семейства хеш-функций зависит от представления данных и функции расстояния d. Для хеммингова расстояния, например, часто применяется хеш-функция, осуществляющая выборку отдельных битов [12], для косинусной меры — метод случайных проекций [13].

В данной работе используется метод случайных проекций, т. е. функция f из семейства F соответствует одной случайной гиперплоскости; функция принимает значение 1, если хешируе-мая точка находится над гиперплоскостью, и 0 в противном случае.

В системах коллаборативной фильтрации, основанных на сходстве пользователей (user-based collaborative filtering), рекомендации формируются с учетом того, в какой мере совпадают оценки пользователей, присвоенные одним и тем же объектам.

Формально, пусть ruj — оценка, присвоенная объекту j пользователем u и выражающая степень того, насколько пользователю u интересен объект j или какова субъективная ценность объекта j для пользователя u. Пусть U — множество пользователей; I — множество объектов; Iu — множество объектов, оцененных пользователем u;

1и1) — множество объектов, оцененных как пользователем и, так и пользователем V. Методы, основанные на сходстве, используют меру близости между пользователями, определяемую посредством сопоставления оценок, присвоенных пользователями одним и тем же объектам: (в1ш(и, V) = ^(<ги, ] е !ии>)), и пытаются предсказать неизвестную оценку ги на основе известных оценок г^ и сходства между пользователями

В данной статье используется косинусная мера сходства между пользователями:

Оценки пользователей нормализуются таким образом, что гиу = 1 соответствует строго положительному отношению пользователя и к объекту у, а гиу = -1 — строго отрицательному.

Рекомендующая система, использующая ЛЧХ, реализует поиск ближайших соседей. По известному набору значений хеш-функций для некоторого пользователя и система проверяет соответствующие хеш-таблицы и извлекает из них идентификаторы всех пользователей, чьи предпочтения вероятно похожи (в силу свойства хеш-функции) на предпочтения пользователя и. Затем может быть оценено точное сходство между пользователями, и объекты, высоко оцененные пользователями, похожими на и, будут рекомендованы и.

В предлагаемой системе точное значение сходства не вычисляется, поскольку это привело бы к раскрытию профиля пользователя. Вместо этого вводится приближенная мера сходства в'(и, V), определяемая как количество локально-чувствительных хеш-функций, чьи значения совпали для пользователей и и V. Алгоритм рекомендации, во-первых, осуществляет поиск всех пользователей Qu, которые могут быть соседями пользователя и, и вычисляет в'(и, V) (где V е Qu). Каждому из кандидатов V е Qu посылается запрос на список рекомендаций Яи. Предлагаемый алгоритм и система в целом предсказывают неизвестные оценки г^, вместо этого проводится ранжирование всех объектов, которые были рекомендованы кандидатами в соответствии с оценкой аи1 объекта I для пользователя и, определяемой выражением

Здесь Р.^ — индикаторная функция, осуществляющая проверку того, есть ли объект I в мно-

жестве объектов, рекомендованных пользователем V:

Таким образом, в предлагаемой архитектуре профиль пользователя и представляется множеством пар (¿, ги^), где I — идентификаторы объектов. Каждая из Ь локально-чувствительных хеш-функций представлена г векторами размерности (|/|). После применения всех этих хеш-функций получается Ь г-мерных бинарных векторов. Полученные векторы сохраняются в хеш-таблице. Во время формирования рекомендаций производится Ь операций поиска в хеш-таблице, а затем каждому «кандидату», извлеченному из хеш-таблицы, посылается запрос на формирование рекомендаций. Список рекомендаций упорядочивается по значению аи1 ■

Значения Ь и г являются параметрами алгоритма формирования рекомендаций. В разделе «Экспериментальное исследование» производится экспериментальная оценка того, как значения этих параметров влияют на качество рекомендаций.

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

Предлагаемая система рассчитана на обеспечение двух вариантов использования: а) оценка потенциальной привлекательности объекта (или группы объектов) для данного пользователя; б) запрос рекомендаций.

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

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

В соответствии с предлагаемым подходом рекомендующая система состоит из двух частей: одноранговой (Р2Р) сети рекомендаций и узла

■ Рис. 1. Связи между узлами в предлагаемой архитектуре

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

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

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

Одноранговая сеть основана на использовании БНТ [14] — распространенном подходе к построению так называемых структурированных одноранговых сетей. БИТ — это класс систем, обеспечивающих хранение коллекции пар ключ — значение, распределенной по различным узлам сети, с учетом миграции фрагментов при выходе узла из состава сети.

Классические реализации подхода БИТ обладают рядом уязвимостей. Для их преодоления разработано несколько анонимизированных реализаций БИТ. Предлагаемая архитектура основывается на Окорив [15] — одной из таких ано-нимизированных реализаций. В основе таких реализаций, как правило, лежит идея построения цепочек анонимизации вместо непосредственного обращения к другому узлу сети, причем каждый узел, лежащий в такой цепочке, имеет

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

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

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

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

2. Узел координации. Распределенный характер предлагаемой системы является причиной следующей технической сложности. Для корректного вычисления локально-чувствительных хеш-функций необходимо, чтобы сами хеш-функции (т. е. гиперплоскости, которыми они представляются) были одинаковы на всех узлах. Для согласования параметров этих функций все узлы сети должны использовать один и тот же порядок следования объектов, поскольку размерность гиперплоскостей совпадает с количеством объектов и с длиной вектора пользовательских оценок. Задача поддержания глобального состояния в одноранговой сети является нетривиальной [16-18]. В предлагаемой системе для ее решения используется подход, схожий с предложенным

в статье [19] и заключающийся в отказе от чисто однорангового устройства сети. Задачей узла координации является сбор всех объектов (о которых сообщают пользователи), поддержка отношения порядка между их идентификаторами и генерация локально-чувствительных функций. Таким образом, каждый узел должен соединиться с узлом координации для двух целей: во-первых, для регистрации нового, ранее неизвестного объекта; во-вторых, для получения нового набора локально-чувствительных хеш-функций. Следует заметить, что нет необходимости генерировать новый набор хеш-функций после обнаружения каждого нового объекта. При использовании «устаревшего» набора функций получение рекомендаций оказывается возможным, но их качество постепенно ухудшается с ростом расхождения между используемым и актуальным наборами. Таким образом, каждый узел накапливает новые объекты, посылает накопленный пакет объектов узлу координации, а в ответ получает обновленный набор хеш-функций.

Экспериментальное исследование предлагаемого подхода было произведено с использованием набора данных MovieLens 100k, выложенного в открытый доступ исследовательской лабораторией GroupLens Research [20]. Этот набор содержит 100 000 оценок, присвоенных 943 пользователями 1682 фильмам.

В ходе экспериментального исследования преследовались две цели. Во-первых, получить практическую информацию о количественных характеристиках подхода и оценить временную и пространственную сложность рекомендующих систем, основанных на ЛЧХ в DHT-сетях. Во-вторых, оценить качество рекомендаций по сравнению с широко распространенными альтернативными алгоритмами.

Временная и пространственная сложность

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

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

Поиск ближайших соседей требует b операций извлечения из хеш-таблицы, а значит, требует O(b log(N)) взаимодействий между узлами.

Хеширование с учетом местоположения — Locality-sensitive hashing

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

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

Содержание

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *