Исследование и разработка алгоритмов рекомендательных систем на основе графовых моделей данных тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат наук Бритвина, Екатерина Васильевна

• Бритвина, Екатерина Васильевна
• кандидат наук
• 2015

Оглавление диссертации кандидат наук Бритвина, Екатерина Васильевна

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. АЛГОРИТМЫ ПОСТРОЕНИЯ РЕКОМЕНДАТЕЛЬНЫХ СИСТЕМЫ И ИХ ПРИЛОЖЕНИЯ

1.1 Что такое рекомендательные системы

1.2 Основные алгоритмы рекомендательных систем

1.3 Проблемы масштабируемости

1.4 Проблемы «холодного старта»

1.5 Некоторые известные рекомендательные системы

1.6 Замечания об оценивание качества рекомендательных систем

1.7 Основная идея разработанного подхода

ВЫВОДЫ ПО ГЛАВЕ 1

ГЛАВА 2. ГРАФОВЫЕ МОДЕЛИ ПРОСТРАНСТВА ПРЕДПОЧТЕНИЙ И РЕАЛИЗАЦИЯ АЛГОРИТМА ПОИСКА

2.1. Основные понятия навигации в пространствах с расстоянием и топологией

2.2. Модель пространства предпочтений и постановка задачи

2.2.1 Графовая модель пространства предпочтений с полностью неизвестной матрицей предпочтений («холодный старт»)

2.2.2 Графовая модель пространства сервисов с полностью известной матрицей предпочтений

2.2.3 Графовая модель пространства предпочтений с частично известной матрицей предпочтений

2.3. Алгоритм поиска максимальных элементов на графе предпочтений

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

ВЫВОДЫ ПО ГЛАВЕ 2

ГЛАВА 3. АЛГОРИТМЫ ПОИСКА МАКСИМАЛЬНО РЕЛЕВАНТНЫХ ЭЛЕМЕНТОВ НА ГРАФАХ

3.1. Метрическое отношение релевантности и его свойства

3.2. Постановка задачи поиска максимально релевантных элементов

3.3. Решение задачи релевантности методом локальной дискретной оптимизации со случайным поиском на графах

3.4. Построение функции внутреннего расстояния, индуцированного отношением релевантности

3.5. Численные эксперименты, по анализу работы системы релевантного выбора

Выводы по Главе 3

ГЛАВА 4. ПРИЛОЖЕНИЯ РАЗРАБОТАННЫХ АЛГОРИТМОВ В РЕКОМЕНДАТЕЛЬНЫХ СИСТЕМАХ

4.1 Самообучающийся интеллектуальный пульт управления телевизионным приемником ЗшаЛТУ

4.4 Защита 1Р подсетей от несанкционированного доступа и ООоБ атак методом псевдослучайной смены сетевых адресов

ВЫВОДЫ ПО ГЛАВЕ 4

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

Приложение

Введение диссертации (часть автореферата) на тему «Исследование и разработка алгоритмов рекомендательных систем на основе графовых моделей данных»

ВВЕДЕНИЕ

Актуальность работы. Одним из бурно развивающихся направлений совершенствования индустрии электронной коммерции является развертывание рекомендательных систем - инструментов автоматической генерации предложений по услугам на основе изучения персональных потребностей клиентов. Одними из первых рекомендательных систем были система Интернет-магазина Amazon и система компании Google. В 1992 г. в качестве основного алгоритма для рекомендательных систем был предложен метод коллаборативной фильтрации. Он основан на использовании в рекомендательной системе информации о доступных треках всех пользователей. Этот метод позволил решить задачу достаточно эффективно, оказался весьма совершенным и в настоящее время улучшение показателя качества рекомендательной системы на 10% оценивается в конкурсе Netflix Prize в 1 миллион долларов.

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

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

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

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

Предмет исследования. Структуры данных и алгоритмы выбора релевантных рекомендаций.

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

Для достижения поставленной цели, в работе решаются следующие научные и практические задачи.

1. Выбор и построение модели данных для выбора рекомендаций в условиях «холодного старта» и трансформирующейся в масштабируемую модель.

2. Разработка алгоритма выбора рекомендаций в условиях «холодного старта».

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

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

5. Разработка на основе разработанных методов архитектуры системы для выбора релевантных рекомендаций (рекламных сообщений) в телекоммуникационных системах.

Положения, выносимые на защиту:

1. Модель данных в виде графов тесного мира может использоваться как самоорганизующаяся структура данных для алгоритмов рекомендательных систем.

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

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

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

5. Способ выбора релевантных информационных сообщений в телекоммуникационных сетях и системы для его осуществления.

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

Научная новизна.

• Предложена и разработана новая модель данных в виде графа тесного мира для представления объектов рекомендательной системы, авторские права защищены патентами [35], [36].

Поставлена задача генерации релевантных рекомендаций как задачи дискретной оптимизации на паре графов, позволяющая использовать эвристические алгоритмы поиска на графах М8Ш — метризованного тесного мира, которая отличается от известных, основанных на матричных представлениях данных.

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

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

Практическая ценность. Работа выполнена при финансовой поддержке Министерства образования и науки РФ по федеральной целевой программе «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2014-2020 годы», Соглашение о предоставлении субсидии №14.574.21.0034 от 17.06.2014 «Разработка и исследование технологий и программного обеспечения программно-конфигурируемых сетей с целью противодействия распределенным атакам типа «отказ в обслуживании» и перехвату данных», уникальный идентификатор ПНИ RFMEFI57414X0034.

Результаты исследований, полученные автором в работе, использованы в проекте ООО «МераЛабс» «Ads-While-Waiting», получивший поддержку ФПИ Российской Венчурной Компании, в совместных работах с компанией -оператором связи стандарта 4G «Основа Телеком» и учебном процессе на кафедре «Информатики и систем управления» НГТУ им. P.E. Алексеева.

Апробация работы и внедрение результатов исследования. Основные результаты работы представлялись на третьей Всероссийской конференции «Нелинейная динамика в когнитивных исследованиях», Vl-fi Всероссийской научно-практической конференции «Нечеткие системы и мягкие вычисления-2014 городе Санкт-Петербурге, а также Международной

научной конференции «Информационные системы и технологии» 2012-2014гг (ИСТ-2012, ИСТ-2013, ИСТ-2014).

Публикации. По теме диссертационной работы опубликовано 10 научных работ, включая три публикации в изданиях из списка изданий, рекомендованных ВАК РФ, получены патент на изобретение и патент на полезную модель.

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

ГЛАВА 1. АЛГОРИТМЫ ПОСТРОЕНИЯ РЕКОМЕНДАТЕЛЬНЫХ СИСТЕМЫ И ИХ ПРИЛОЖЕНИЯ

1.1 Что такое рекомендательные системы

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

Рекомендательные системы предназначены для поиска объектов, которые понравятся пользователю или будут ему полезны. В типичных системах есть список пользователей и = (щ,и21ш-ит) и предметов 1 = (гЧ,г2)• В ходе взаимодействия с системой пользователи знакомятся с объектами, формируя матрицу рейтингов И, где гикрейтинг предмета I Е I у пользователя ик £ II. Как правило, матрица рейтингов неполная и разреженная, т.к. количество различных предметов в системе велико и уже известные г^предметы 1ик— I составляют лишь малую долю от общего числа. Задача рекомендательной системы обычно формулируется как вычисление предсказания и рекомендации. Пользователь, для которого они вычисляются, называют активным или меченым.

Предсказание - численное значение РПк1 ,выражающее предсказанную предпочтительность предмета 1 £ 1Пк для активного пользователя ик. Предсказанное значение лежит внутри заранее определенного интервала рейтинга, например от 1 до 5, или заданного уровня релевантности от 0 до 1. Рекомендация - список из N предметов /г с / , наиболее предпочтительных для активного пользователя, причем в него входят лишь незнакомые пользователю элементы 1Г П / = 0 Задачи в такой постановке также называют Тор-К рекомендацией.

1.2 Основные алгоритмы рекомендательных систем

Исследованиям в этой области посвящено немало работ, однако в российской литературе вопрос исследован пока неполно и чаще в плоскости практического программирования таких алгоритмов, чем разработкам новых. Из известных русскоязычных публикаций сразу упомянем работу [1], единственную защищенную диссертацию, которую удалось найти [2], несколько публикаций, в которых рассматриваются подходы к базовым алгоритмам [3]. Наиболее известной школой в области рекомендательных систем в России следует считать группу исследователей из Лаборатории

Интернет исследований (UNIS) НИУ ВШЭ под руководством С.И. Николенко. Ими была опубликована получившая резонанс работа под названием Semi-supervised Tag Extraction in a Web Recommender System [4],

[5].

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

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

При фильтрации содержимого создаются профили пользователей и объектов. Профили пользователей могут включать демографическую информацию или ответы на определённый набор вопросов. Профили объектов могут включать названия жанров, имена актёров, имена исполнителей и т.п. — в зависимости от типа объекта. Этот подход используется в проекте Music Genome Project: музыкальный аналитик оценивает каждую композицию по сотням различных музыкальных характеристик, которые могут использоваться для выявления музыкальных предпочтений пользователя.

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

Имеется: Пользователи (users, и EU) Объекты (items, i el) События (events, (rui, и, i,...) GD) Требуется:

Предсказать предпочтение:

r*ui = Predict(u, i,...)~ rui Персональные рекомендации:

и 7—> (il,..., iK) = RecontmendK(u,...) Похожие объекты:

i 7—► (il,..., iM) = SimilarM(i) Кластеризация: и eF(u),

F(u) состоит из пользователей, "похожих" на и.

Впервые термин «коллаборативная фильтрация» был использован в 1992 г. в работе Дэвида Гольдберга и др. [6].

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

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

Если имеется набор данных о рейтинге объектов из множества размером

d пользователями из множества размером п, то можно составить матрицу

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

ю

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

Япхп — ^пхй х Уйхп (О

Решение такой задачи может быть сведено к задаче оптимизации -нахождения минимума функционала

ттХиС^у-мГ^)2 (2)

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

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

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

1.3 Проблемы масштабируемости

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

В работе [8] были сформулированы математические основы коллаборативной фильтрации в пространствах большой раазмерности, основанной на методах поиска ближайшего соседа на основе функции похожести (similarity) с помощью методов линейной алгебры. Авторами были показано, что если для пользователя и объекта i ввести векторы хи и yt соответственно, называемые факторами пользователя и факторами объекта, то соответстветствующее предпочтение может быть вычислено как скалярное произведение рш- = х^уи. Такой подход напрминает методы факторизации матриц. Факторы могут быть найдены как решение следующей задачи оптимизации

™™lu,iCui(Pui -*1уд2 +Я(Еи1М2+1гЫ12) (3)

Xtyt

Здесь минимизируется первая сумма, для вычисления которой вводятся переменные pui, и cui которые выражают собой соответственно двоичное выражение соответствия и и i и уровень доверительности для этого соответствия. Второе слагаемое в приведенном выше выражении представляет собой регуляризатор Тихонова [9] позволяющий корректно решать некорректную (плохо обусловленную) задачу.

Решение найденное авторами позволяет найти искомые вектора

xu = (YTCUY + Д/)-1ГгСир(гг) (4)

yi = СXTCUX + AI)-1YXTCipC 0 12

Алгебраический подход стал основным при разработке алгоритмов, но плохо работающий при больших размерностях. В работе Hsiang-Fu Yu и др. авторы [10] показали, что несмотря на попытки свести задачу факторизации (1) к известному алгоритму разложения матриц по собственным числам SVD является неприемлемым, решение может быть наййдено близким алгоритмом ALS - alternating least squares - альтернирующих наименьших квадратов или SGD - stochastic gradient descent - случайного градиентного спуска. Алгоритм ALS имеет вычислительную сложность порядка 0(\С1\к2 + (т + п)к3, где m,n,k - число пользователей, число объектов и ранг матрицы факторизации соответственно. |П| — число надежных элементов матрицы соответствия. Метод SGD - обладает явными вычислительными преимуществами при работе с векторами большой размерности.

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

*u - ~ Rmyd (5)

Vityi ~ RuiXu)

В этом алгоритме вычислительная сложность пропорциональна |ü|k для каждого шага вычисления фактор-векторов, а зависимость числа шагов не поддается оценке заранее.

Авторы работы предлагают методыы уссовершенствования алгоритма случайного градиентного спуска, позволяющие уменьшить вычислительную сложность до гарантированных значений. Ими предложен алгоритм CCD -cyclic coordinate descent - циклического координатного спуска. Этот алгоритм может быть записан в виде псевдокода: Algorithm 1 CCD

Input: Initial R=A,W=0,H, X, and к for iter = 1,2,..., T do

for I = 1, 2,..., m do

for t = 1, 2,..., к do

Obtain z* using (6). Update R and wit using (7) and (8). end for end for

for j = 1, 2,..., n do

for t = 1, 2,..., к do

Obtain s* using (12). Update R and hjt using (9) and (10). end for end for

end for

В работе [11] предлагается усовершенствованный алгоритм CCD+ в котором используются особенности исполнения на кластере из 64 процессоров, что повышает скорость исполненияя алгоритма в 49 раз по сравнению с традиционным SGD в 20 раз быстрее ALS.

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

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

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

108) и не требовать модернизации достаточно долгое время.

14

В последнее время учет этого фактора привел к ряду работ, в которых используются различные децентрализованные алгоритмы нахождения решения. Одна из наиболее глубоких, по-нашему мнению, работ - это исследование выполненное под руководством профессора Анны-Марии Кермарек (Anne-Marie Kermarrec) из университета Рене, Франция. Работа называется Application of Random Walks to Decentralized Recommender Systems - приложение случайного блуждания к децентрализованным рекомендательным системам [14]. Авторы показали, что применяя gossip protocols, часто называемые эпидемическими, можно получить эффективное нахождение решений задачи поиска фактор-векторов используя чисто случайный поиск на каждом из подмножеств пользователей и объектов. Оценка сложности при этом может быть оценена как 0(S2N +53/

В работе A.A. Дзюбы «Рекомендации треков в социальных сетях» [15] было выполнено экспериментальное исследование метода случайного блуждания с рестартом для решения задачи коллаборативной фильтрации и получен ряд результатов по оценке точности и надежности получаемых результатов.

1.4 Проблемы «холодного старта»

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

Наиболее распространенный подход [16] здесь основывается на косвенных методах кластеризации пользователей и использования в качестве начальных групповых оценок предпочтений (рейтингов). Различают

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

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

После того, как кластеры пользователей получены и для каждого нового пользователя, указавшего свои демографические данные, мы знаем кластер, к которому он относится, можно улучшить рекомендации на «холодном старте» с помощью групповых рекомендаций или фильтр-ботов. Наиболее естественным является метод групповых рекомендаций (group recommendation to individual user), в котором новому пользователю

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

Существует ряд различных стратегий, как агрегировать рейтинги разных пользователей в групповую рекомендацию. Например, групповой рейтинг можно рассчитывать так: где г~ рейтинг /-го пользователя, wt- вес /-го пользователя. Произведение берется по всем пользователям или по выделенной группе по какому-то критерию (например, возраст-пол). Весам м^для пользователей с тем же возрастом, полом и местоположением дается большее значение, остальным меньшее (подбираются вручную).

Альтернативным подходом являются фильтр-боты (filterbots), которые генерируют дефолтные рейтинги для нового пользователя. То есть при регистрации фильтр-боты автоматически сгенерируют несколько рейтингов для пользователя на основе его демографических данных, которые будут использованы алгоритмами коллаборативной фильтрации на «холодном старте». Плюсом такого подхода является простота реализации и отсутствие необходимости менять существующие алгоритмы. Кроме того, фильтр-боты и групповые рекомендации можно использовать совместно: тогда за дефолтные рейтинги фильтр-ботов берутся групповые рейтинги. «Холодный старт» для объектов осуществляется путем введения расстояния на множестве объектов и превращения его в метрическое пространство. Например, для решения проблемы холодного старта для новых веб-страниц применяются различные методы анализа текста и другого контента страницы (картинки, видео, flash, ссылки и т.д.).

Основные методы семантического анализа текста, на которых можно остановиться - это линейный дискриминантный анализ LDA - Linear discriminant analysis и релевантных обратных связей - relevance feedback. Общая схема рекомендаций на основе текстового контента страницы приблизительно такова. Сначала по всем сайтам собирается полезный контент (отбрасывается реклама, меню и т.д.). Слова в тексте проходят

предварительную обработку, то есть отбрасываются стоп-слова и производится лемматизация. Далее составляется единый словарь слов и таблица встречаемости слов в текстах веб-страниц (контент-профили страниц). Слова взвешиваются по TF-IDF и для слишком длинных текстов оставляется только top N самых весомых слов. Алгоритм relevance feedback составляет профиль тегов (то есть ключевых слов) для каждого пользователя по контент-профилям страниц, которые отмечал лайками этот пользователь. Новые сайты рекомендуются тем пользователям, профили тегов которых наиболее коррелируют с контент-профилем вновь добавленной страницы.

Список литературы диссертационного исследования кандидат наук Бритвина, Екатерина Васильевна, 2015 год

СПИСОК ЛИТЕРАТУРЫ

1. Федоровский, А.Н. Архитектура рекомендательной системы, работающей на основе неявных пользовательских оценок / А.Н. Федоровский, В.К. Логачева // Труды 13й Всероссийской научной конференции «Электронные библиотеки: перспективные методы и технологии, электронные коллекции» - RCDL'2011, Воронеж, Россия, 2011

2. Правиков, А.А. Разработка и применение метода формализации проектирования рекомендательных систем с естественно-языковым интерфейсом: дис.... канд. технических наук, Москва, 2011. С. 160

3. Нефедова, Ю. С. Архитектура гибридной рекомендательной системы GEFEST (Generation-Expansion-Filtering-Sorting-Truncation, Системы и средства информ.). 2012. Том 22. Вып 2. С. 176-196

4. Vasily, A. Supervised Tag Extraction in a Web Recommender System, Similarity Search and Applications/ A. Vasily, S. Leksin, I. Nikolenko //Semi Lecture Notes in Computer Science Volume 8199. 2013. P. 206-212

5. Ignatov, D. I. Online Recommender System for Radio Station Hosting: Experimental Results Revisited, in: Proceedings of The 2014 /S. Nikolenko, А. Таймураз, N. Konstantinova //IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology, WI-IAT 2014, 11-14 August 2014 Warsaw, Poland / Науч. ред.: D. Slezak, H. S. Nguyen, M. Reformat, S. J. Eugene. Los Alamitos, California/Washington/Tokyo: IEEE Computer Society Conference Publishing Services (CPS), 2014. P. 229-236.

6. Goldberg, David. Douglas Trry Using collaborative filtering to weave an information Tapestry/ David Goldberg, David Nichols, Brian M. Oki, //Communication ofthe ACM, Dec. 1992. V/35. N. 12. P. 61-71.

7. Koren Y. Matrix factorization techniques for recommender systems/ Y. Koren, R. M. Bell, C. Volinsky // Computer.V. 42. P. 30-37. 2009.

8. Yifan Hu. Collaborative filtering for Implicit Feedback Datasets/ Yifan Ни, Yehuda Koren, Chris Volinsky//Proceedings IEEE International Conference on Data Mining (ICDM 2008).P. 263-272.

9. Тихонов, A.H. Методы решения некорректных задач/ А.Н. Тихонов, В.Я. Арсенин // Наука, -М. 1979.

10.Hsiang-Fu Yu. Inderjit Dhillon Scalable Coordinate Descent Approaches to Parallel Matrix Factorization for Recommender Systems/ Hsiang-Fu Yu, Cho-Jui Hsien, Si Si. // IEEE 12th International Conference on Data Mining (ICDM). 2012.

11.Hsiang-Fu Yu. Inderjit Dhillon Parallel Matrix Factorization for Recommender Systems/ Hsiang-Fu Yu, Cho-Jui Hsien Si Si //Knowledge and Information Systems(KAIS), May 2013.

12.Recht, B. Parallel stochastic gradient algorithms for large-scale matrix completion/ B. Recht, C. Re, and S. J. Wright. //Mathematical Programming Computation. V. 5. N. 2. P.. 201-226. 2013.

13. Yong, Zhuang. A fast parallel sgd for matrix factorization in shared memory systems/ Yong Zhuang, Wei-Sheng Chin, Yu-Chin Juan, Chih-Jen Lin. //In Proceedings of the 7th ACM conference on Recommender systems. P. 249256. ACM. 2013.

14. Kermarrec, Anne-Marie. Application of Random Walks to Decentralized Recommender Systems, Principles of Distributed Systems/ Anne-Marie Kermarrec, Vincent Leroy, Afshin Moin, Christopher Thraves // Lecture Notes in Computer Science. V. 6490, 2010. P. 48-63.

15. Дзюбы, A.A. Рекомендации треков в социальных сетях// Магистерская диссертация, Санкт-Петербургский Государственный Университет, Математико-механический факультет, Кафедра системного программирования. 2012.

16. Blerina, Lika. Facing the cold start problem in recommender systems/ Blerina Lika , Kostas Kolomvatsos, , Stathes Hadjiefthymiades // Expert Systems

with Applications. V. 41.1. 4. P. 2. M. 2014. P. 2065-2073.

86

17. Basiri, J. Alleviating the cold-start problem of recommender systems using a new hybrid approach/ J. Basiri, A. Shakery, B. Moshiri, M. Hayat//Telecommunications (1ST), 2010 5th International Symposium on, 46 Dec. 2010. P. 962-967.

18. Koren Y. The bellkor solution to the netflix grand prize // Netflix prize documentation. 2009.

19.Witology. [Электронный ресурс]. / Режим доступа: http://witology.com/, свободный. —Загл. с экрана. — Яз. рус., англ.

20.Krylov, V. Approximate Nearest Neighbor Search Small World Approach/ Vladimir Krylov, Andrey Logvinov, Alexander Ponomarenko, Yury Malkov// International Conference on Information and Communication Technologies and Applications ICTA 2011, November 29th - December 2nd, 2011 -Orlando, Florida, USA

21. Krylov, V. Metrized Small World Approach for Nearest Neighbor Search in High Dimensional General Metric Spaces/ Vladimir Krylov, Andrey Logvinov, Alexander Ponomarenko, Yury Malkov //Similarity Search and Applications, 5th International Confference6, SISAP2012, Toronto, ON, Canada, August, 2012,Proceedings, Springer, ISBN 978-3-642-32153-5

22. Malkov, Y. Approximate nearest neighbor algorithm based on navigable small world graphs/ Y. Malkov, A. Ponomarenko, A. Logvinov, V. Krylov//

• Information Systems, 2014, pp. 61-68

23. Жаринов,И. В. Конструирование графов с минимальной средней длиной пути/ И.В. Жаринов,В.В. Крылов// Вестник ИжГТУ. 2008. № 4

24.Анисимов, А.А. Управление отказами в децентрализованных гридах, обладающих свойствами тесного мира//Вестник Нижегородского Университета им. Н.И. Лобачевского.2011. №6-1

25. Генератор регулярных графов GENREG. [Электронный ресурс]. -Режим flocTyna:http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html, свободный. — Загл. с экрана. — Яз. рус., англ.

26.Метрика Хаус дорфа. [Электронный ресурс]. - Режим доступа: http://stu.sernam.ru/book_fah.php?id=25, свободный. —Загл. с экрана. — Яз. рус., англ.

27.Malkov, Y. Scalable distributed algorithm for approximate nearest neighbor search problem in high dimensional general metric spaces/ Y. Malkov, A. Ponomarenko, A. Logvinov, V. Krylov//Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7404 LNCS,2012, pp. 132-147

28.Logvinov, A.A. Scalable Distributed Algorithm for Approximate Nearest Neighbor Search Problem in High Dimensional General Metric Spaces Similarity Search and Applications/ A.A. Logvinov,A.A. Ponomaremko, V.V. Krylov, Y.A. Malkov//5th International Conference Proceedings, SISAP2012, Toronto, ON, Canada, August, 2012

29. Математические модели и алгоритмы принятия релевантных решений, Передерий В.И., Еременко А.П. Автоматика, автоматизация, электротехнические комплексы и системы (ААЭКС), №2(22), 2008

30.Ковалев, М.М. Дискретная оптимизация. Целочисленное программирование. М., Едиториал УРСС, 2003, 192 с.

31. Similarity Search: The Metric Space Approach, Pavel Zezula, 2005, New York, NY 10013, USA: Springer, 220 pp.

32. Malkov, Y. Approximate nearest neighbor algorithm based on navigable small world graphs /Y. Malkov, A. Ponomarenko, A. Logvinov, V. Krylov //Information Systems, 2014, pp. 61-68

33. Пономаренко, A.A. Структура со свойствами тесного мира для решения задачи поиска ближайшего соседа в метрическом пространстве/ А.А. Пономаренко, Ю.А. Мальков, А.А. Логвинов, В.В. Крылов. Вестник Нижегородского университета им. Н.И. Лобачевского. 2012. № 5-2. С. 409-41

34. Система доставки целевой рекламы и/или информации абоненту посредством инфокоммуникативных сетей//Пономарев Д.М., Крылов В.В., Бритвина Е.В., патент на полезную модель RUS 112466 29.04.2011

35. Пат. 2461879 Российская федерация, МПК G06Q30/02 Способ доставки целевой рекламы и/или информации абоненту посредством инфокоммуникативных сетей и система для его осуществления/ Е.В. Бритвина, В.В. Крылов, Д.М. Пономарев; 2011117023/08, заявл. 29.04.2011, опубл. 20.09.2012

36. Крылов В. В., Пономарев Д. М. Способ взаимодействия терминального устройства клиента с сервером по сети интернет с повышенным уровнем защиты от DDoS-атак и система для реализации способа. Пат. РФ 2496136, 20 Октября 2013

37. Крылов, В.В. Защита IP-подсетей от DDoS-атак и несанкционированного доступа методом псевдослучайной смены сетевых адресов /В.В. Крылов, К.Н. Кравцов //Вопросы защиты информации. 2014. № 3. С. 24-31

38.Бритвина, Е.В. Алгоритм поиска максимально релевантных элементов на основе метризованного графа тесного мира /Е.В. Бритвина, В.В. Крылов //Вестник ННГУ №4, Нижний Новгород, стр. 178-181

39.Бритвина, Е.В. Алгоритм самоорганизации пространства поиска в больших системах с нечетким выбором/ Е.В. Бритвина// Электронный научный журнал «Современные проблемы науки и образования», ISSN 2070-7428, №6, 2014

40.Бритвина, Е.В. Сегментирование рекомендательной системы с использованием метода организации соединения клиент-сервер, основанного на программно-конфигурируемых сетях и применении протокола с быстрым перескоком IP адреса/ Е.В. Бритвина// Электронный научный журнал «Современные проблемы науки и образования», ISSN 2070-7428, №6, 2014

41.Бритвина, Е.В. Алгоритм максимизации релевантности, использующий графовые модели данных / Е.В. Бритвина, В.В. Крылов, Ю.А. Мальков // Труды НГТУ № 2, 2013- с.75-83

42.Бритвина, Е.В. Самоорганизация пространства поиска в больших системах с нечетким выбором/ Е.В. Бритвина, В.В. Крылов//У1 Всероссийская научно-практическая конференция «Нечеткие системы и мягкие вычисления-2014»

43. Бритвина, Е.В. Самоорганизация пространства поиска в больших системах с нечетким выбором/Е.В. Бритвина, В.В. Крылов, Ю.А. Мальков//Труды III Всероссийской конференции «Нелинейная динамика в когнитивных исследованиях», ИПФ РАН, Нижний Новгород, 2013 с. 20-21