Содержание к диссертации
Введение
ГЛАВА 1. Алгоритмы построения рекомендательных системы и их приложения 7
1.1 Что такое рекомендательные системы 7
1.2 Основные алгоритмы рекомендательных систем 8
1.3 Проблемы масштабируемости 12
1.4 Проблемы «холодного старта» 15
1.5 Некоторые известные рекомендательные системы 18
1.6 Замечания об оценивание качества рекомендательных систем 21
1.7 Основная идея разработанного подхода 22
Выводы по главе 1 24
ГЛАВА 2. Графовые модели пространства предпочтений и реализация алгоритма поиска 25
2.1. Основные понятия навигации в пространствах с расстоянием и топологией 25
2.2. Модель пространства предпочтений и постановка задачи
2.2.1 Графовая модель пространства предпочтений с полностью неизвестной матрицей предпочтений («холодный старт»). 31
2.2.2 Графовая модель пространства сервисов с полностью известной матрицей предпочтений. 34
2.2.3 Графовая модель пространства предпочтений с частично известной матрицей предпочтений
2.3. Алгоритм поиска максимальных элементов на графе предпочтений 38
2.4. Параллельная реализация поиска максимальных элементов на графе предпочтений 43
Выводы по главе 2 50
ГЛАВА 3. Алгоритмы поиска максимально релевантных элементов на графах 52
3.1. Метрическое отношение релевантности и его свойства 52
3.2. Постановка задачи поиска максимально релевантных элементов 53
3.3. Решение задачи релевантности методом локальной дискретной оптимизации со случайным поиском на графах 56
3.4. Построение функции внутреннего расстояния, индуцированного отношением релевантности 58
3.5. Численные эксперименты, по анализу работы системы релевантного выбора 63
Выводы по Главе 3 67
ГЛАВА 4. Приложения разработанных алгоритмов в рекомендательных системах
4.1 Самообучающийся интеллектуальный пульт управления телевизионным приемником SmartTV 68
4.4 Защита IP подсетей от несанкционированного доступа и DDoS атак методом псевдослучайной смены сетевых адресов . 80
Выводы по главе 4 83
Заключение 84
Список литературы 85
- Основные алгоритмы рекомендательных систем
- Графовая модель пространства предпочтений с полностью неизвестной матрицей предпочтений («холодный старт»).
- Постановка задачи поиска максимально релевантных элементов
- Защита IP подсетей от несанкционированного доступа и DDoS атак методом псевдослучайной смены сетевых адресов
Основные алгоритмы рекомендательных систем
В этой работе описана система фильтрации документов, являющаяся частью экспериментальной почтовой системы Tapestry, разработанной компаией Ксерокс. Проблема было выбрать из огромного потока рассылки ежедневно растущего числа писем, содержащих гигантское число документов, только те, которые представляли интерес для каждого из подписчиков. Путь прямого выбора пользователем мэйл листов оказывался тупиковым из-за невозможности ограничиться лишь небольшим числом листов, поскольку необходимые документы могли оказаться в других. Тогда был выбран другой путь, когда все рассылки сканировались автоматически и осуществлялась фильтрация потока, специфичного для каждого пользователя. Такая система сканирования и фильтрации может рассматриваться как рекомендательная и разработанный в ее рамках алгоритм, лег в основу коммерческих рекомендательных систем.
Математическая модель, которая работает в качестве основной была сформулирована как задача факторизации матрицы предпочтений на произведение матриц факторов, определяющих индивидуальные предпочтения.
Если имеется набор данных о рейтинге объектов из множества размером d пользователями из множества размером n, то можно составить матрицу таких рейтингов, которая может быть специальным образом нормирована и рассматриваться как матрица предпочтений Rtj . Реально такая матрица не является полной и содержит множество ненадежных значений или отсутствующих вообще. Задачей основного алгоритма рекомендательной системы является получение значений для всех элементов для этой матрицы по известным. Решение находится как приближенное решение задачи факторизации
Таким образом была сформулирована математическая задача для рекомендательной системы, в наиболее простой форме опубликованная в [7]. Было получено немало вполне удовлетворительных результатов путем применения различных стандартных методов для минимизации выписанной квадратичной формы. Однако сразу стало ясно, что при недостаточном числе известных элементов в матрице предпочтений решение оказывается неустойчивым. Существенного прорыва удалось достигнуть применением методов регуляризации при нахождении точки минимума. Однако две проблемы требуют постоянного внимания и порождают все нове подходы к решению.
Первая из них связана с размерностью искомых фактор-векторов n и d, которые могут составлять миллионы и более. Кроме того эта размерность может эволюционировать по мере работы системы. Ту проблема получила название масштабируемости.
Вторая проблема связана с введением в систему пользователей или объектов о которых нет рейтинговой информации, что порождает нулевые строки или столбцы в матрице предпочтений. Эта проблема названа проблемой «холодного старта».
С увеличением количества пользователей в системе, появляется проблема масштабируемости. Например, имея 10 миллионов покупателей O и миллион предметов, алгоритм коллаборативной фильтрации со сложностью равной уже слишком сложен для расчётов. Также, многие системы должны моментально реагировать на онлайн запросы от всех пользователей, независимо от истории их покупок и оценок, что требует ещё большей масштабируемости.
В работе [8] были сформулированы математические основы коллаборативной фильтрации в пространствах большой раазмерности, основанной на методах поиска ближайшего соседа на основе функции похожести (similarity) c помощью методов линейной алгебры. Авторами были показано, что если для пользователя u объекта i ввести векторы хи и yt соответственно, называемые факторами пользователя и факторами объекта, то соответстветствующее предпочтение может быть вычислено как скалярное произведение pui = ХиУи. Такой подход напрминает методы факторизации матриц. Факторы могут быть найдены как решение следующей задачи оптимизации
Здесь минимизируется первая сумма, для вычисления которой вводятся переменные pui, и cui которые выражают собой соответственно двоичное выражение соответствия u и i и уровень доверительности для этого соответствия. Второе слагаемое в приведенном выше выражении представляет собой регуляризатор Тихонова [9] позволяющий корректно решать некорректную (плохо обусловленную) задачу.
Графовая модель пространства предпочтений с полностью неизвестной матрицей предпочтений («холодный старт»).
Задание графа на Y может осуществляться различными способами в зависимости от требований к эффективности построенных на графе алгоритмов жадного поиска. Как было указано выше, в состоянии “холодного старта”, когда алгоритм находится в зоне неопределенности, т.е. для указанного клиента не определено значение функции предпочтения на сервисе, топология на Y должна удовлетворять требованию быстрого перебора всех сервисов с вызовом внешнего алгоритма оценки значения этой функции. Нами было предложено использовать для этого графы тесного мира безмасштабного типа (ScaleFree).
Однако, в некоторых приложениях такая топология оказывается плохо приемлемой, в силу необходимости осуществления на каждом шаге движения разного числа шагов выбора в том числе значительного при большом размере графа. Рассмотрим возможность построения графа тесного мира с ограниченной заранее степенью вершины. В работе [23] было показано, что можно сконструировать графы с логарифмической зависимостью диаметра от размера графа, т.е. графы тесного мира, степень вершины которых не превышает заданного числа. Это разновидность так называемых графов Кэйли, относящихся к фрактальным графам, которые носят специальное название Limited Degree Fractal (LDF). Эти графы могут позволить ограничить число шагов выбора на каждом шаге движения, однако для значительной части вершин графа степень вершины окажется равной единице, что потребует реверсного движения при осуществлении поиска. Указанное свойство может ограничить применимость топологии LDF графов для ряда приложений.
Сконструируем граф, который обладал бы свойством тесного мира, т.е. логарифмической зависимостью диаметра от размера, ограниченной степенью вершины и минимальной дисперсией степени вершины. Лучший вариант здесь – нулевая дисперсия, то есть постоянная степень вершины для всех вершин. Графы такого типа называются регулярными. Нам необходимо рассматривать среди них только такие, которые имеют относительно малый по сравнению с размером диаметр графа. Известно, что для любого
регулярного графа из n вершин и степенью вершины k диаметр графа D ограничен следующими неравенствами [24]:
В этой формуле скобки [Х\ и \Х] означают наибольшее целое не превосходящее и наименьшее целое не превышающее X соответственно.
Как видно все регулярные графы обладают логарифмической связью диаметра с размером и поэтому пригодны для поставленной задачи. Для приложений интерес представляют топологии со степенью вершины 4 (движение вверх-вниз-вправо-влево). Графы такого типа называются 4-регулярными. На рис.2.1 приведены 4-регулярные графы для сравнительно небольшого числа вершин.
Для большого числа вершин графические изображения становятся малопригодными и описание графа матрицей смежности или таблицей соседей становится более приемлемым для практических целей. Генератор регулярных графов GENREG (M. Meringer) [25] позволяет эффективно получать необходимые таблицы для работы приложений.
Существует возможность построения и иных эффективных топологий на множестве сервисов в условиях нахождения аргументов в зоне неопределенности. В настоящей работе мы ограничимся описанными выше двумя случаями. 2.2.2 Графовая модель пространства сервисов с полностью известной матрицей предпочтений.
Сформулируем задачу построения окрестности произвольно выбранной точки в множестве Y для случая, когда все значения матрицы предпочтения известны. В этом случае эта матрица представляет собой числовую таблицу, число строк в которой равно числу элементов в множестве клиентов X, а число столбцов - число элементов множества объектов Y.
Каждый i-й столбец этой матрицы можно рассматривать как координатный вектор соответствующего этому столбцу объекта из Y. При таком рассмотрении множество Y оказывается погруженным в координатное пространством размерности, равной числу элементов m в множестве клиентов X. В координатном пространстве можно ввести различные метрики, которые могут быть использованы для построения графа на Y. Итак, ключевым моментом для построения окрестностей точек из множества сервисов в случае, когда известны значения функции предпочтений для всех клиентов, является рассмотрение каждого сервиса как точки, для которой известны координаты. В качестве координат служат значения функции предпочтения со стороны всех клиентов.
Выберем в качестве метрики известную метрику Ы. То есть для любой пары точек у (У) Є Y определим расстояние р через соответствующие элементы матрицы предпочтений следующим образом т (14) Для конструирования графа, с топологией, согласованной с введенной метрикой воспользуемся разработанным в [15,16,17] методом, названным построением графов метризованного тесного мира MSW (Metrized Small World). Как показано в этих работах, если на дискретном множестве существует функция расстояния, то на нем может быть построен граф, обладающий свойствами тесного мира (MSW граф). То есть расстояние между любыми вершинами такого графа в среднем оценивается логарифмической величиной от размера графа, числа его вершин. При этом существует простой алгоритм жадного поиска, приводящий в среднем за логарифмическое число шагов к отысканию ближайших соседей для любого вновь выбранного элемента y0 из множества (поглощающего), наделенного той же функцией расстояния. Выбрав произвольно начальную точку из Y можно найти в Y ближайших соседей для y0 совершив логарифмически связанное с размером Y число локальных поисков.
Таким образом, начиная с произвольной начальной точки на Y собирается граф MSW, в котором ближайшим в топологии графа (число ребер в пути) вершинам соответствуют точки с минимальным расстоянием в введенном пространстве с метрикой L1. Следует заметить, что максимальное число ближайших соседей для каждой из вершин, оказывается равным внутренней размерности пространства из столбцов матрицы предпочтений, которая, как правило, оказывается существенно меньше m. Этот важный факт может быть использован для существенного сокращения вычислительных затрат на построение графа. Вместо всех строк в матрице предпочтений можно использовать только некоторые, число которых определяет число существенно различимых категорий клиентов. В методах коллаборативной фильтрации для определения размерности пространства клиентов применяют обычно приведение матрицы предпочтений к главным осям (метод SVD разложения матриц) и пренебрегают компонентами с несущественными собственными числами. Мы не будем использовать столь ресурсоемкие при больших m и n алгоритмы, и ограничимся просто усечением матрицы по строкам, считая вероятность упустить существенные категории клиентов достаточно малой. Эта эвристика может быть подтверждена непосредственно на реальных данных, но мы сделаем это в иной форме в следующей главе. Таким образом построение на множестве сервисов графа с необходимыми навигационными свойствами для случая полностью известной матрицы предпочтений достигается вышеописанным алгоритмом
Постановка задачи поиска максимально релевантных элементов
Основной идеей этого раздела диссертации является попытка свести задачу на поиск релевантного ответа из Y на запрос из X при известной функции релевантности rel ( . , . ) к нескольким задачам локального поиска на множестве Y. В основу метода мы положим оснащение этого множества графом со специальными свойствами, известными как MSW (MetrizedSmallWorld) для поиска локального минимума [33]. Классический подход применения метода локальной оптимизации сводится к наделению множества Y любой произвольной метрикой, назначением начальной точки и радиуса окрестности локального поиска. Алгоритм поиска минимума в этом случае сводится к поиску локального минимума в выбранной окрестности и перехода к новой начальной точке, в качестве которой назначается найденная на предыдущем локальном шаге точка минимума.
Как показано в [34], если на дискретном множестве существует функция расстояния, то на нем может быть построен граф, обладающий свойствами тесного мира (MSW граф). То есть расстояние между любыми вершинами такого графа в среднем оценивается логарифмической величиной от размера графа, числа его вершин. При этом существует простой алгоритм жадного поиска, приводящий в среднем за логарифмическое число шагов к отысканию ближайших соседей для любого вновь выбранного элемента y0 из множества (поглощающего) Y с У, наделенного той же функцией расстояния. Выбрав произвольно начальную точку из Y можно найти в Y ближайших соседей для уо совершив логарифмически связанное с размером Y число локальных поисков. Сведем нашу задачу поиска элемента из множества ответов Y релевантного заданному запросу из X к задаче поиска на MSW графе.
Рассмотрим все вершины графа, являющиеся соседями y0, и найдем расстояния релевантности до них. Выберем ту вершину, расстояние релевантности до которой от x минимально. Сравним это расстояние с значением do: если найденное расстояние меньше, то выбираем новую соответствующую ему вершину за новую начальную точку поиска и повторяем поиск максимально релевантной точки среди ее соседей, если нет, то выбираем точку yо в качестве решения задачи - возвращаем как максимально релевантную запросу x в данном цикле поиска. После этого выбирается другая случайная точка yо в Y и процесс поиска повторяется. Число случайных поисков может быть выбрано заранее или определяться адаптивно в зависимости от разброса найденных. Среди всех найденных точек локального минимума выбираются те, которые имели минимальное расстояние релевантности и это подмножество объявляется решением. В большинстве случаев такое подмножество состоит из единственного элемента и в этом случае найденное решение строго соответствует поставленной задаче.
В приведенном выше подходе остается неизвестным и принципиально важным вопрос о построении MSW графа на множестве Y. Очевидно, что поскольку на этом множестве не задана функция метрики, то мы можем назначить ее произвольно. Выбор представляет из себя самостоятельную задачу, которая будет обсуждаться в других работах. Будем считать, что метрика фиксирована. Но также очевидно, что от ее выбора будет сильно зависеть эффективность работы алгоритма. Мы предлагаем здесь выбрать в качестве функции метрики некоторую функцию внутреннего расстояния на Y, индуцированного расстоянием релевантности.
Основная идея подхода состоит в том, что в множестве X некоторым образом выбирается подмножество из M “представительных” элементов, далее называемый базисом в X. Обозначим это подмножество Хв = {хВ1 ,хВ2,...хвм} (28) Определим для каждой точки из Y расстояния релевантности ук Є Y, d(yktхві) = dkit Vi = l,M (29) Назовем полученный для каждого k набор чисел координатами элемента уг в системе координат Xв. Таким образом на множестве Y индуцируется координатная сетка размерности M. Теперь определим функцию внутреннего расстояния на Y с помощью этой координатной системы, задавая ее значения, например, как классическую эвклидову метрику dY {УІ,УІ) = jlk=i(dik dJk)2 (ЗО)
Можно видеть, что такая функция удовлетворяет всем основным аксиомам расстояния, поскольку дает нулевое значение для совпадающих точек в Y и положительна для несовпадающих. Мы не будем давать здесь анализ выполнения неравенства треугольника для индуцированной функции расстояния, поскольку это не является существенным для дальнейшего, однако заметим, что при правильном выборе множества Xв введенная функция расстояния удовлетворит всем аксиомам метрики.
Разумеется, введенная выше эвклидова метрика в качестве индуцированной отношением релевантности не является единственной. Для ускорения вычислений может быть применена метрика L1:
Введенная таким образом индуцированная исходным отношением релевантности функция расстояния будет использоваться нами для построения необходимого для эффективного поиска решений графа MSW. На рис.3.1 приведена иллюстрация построения координатного пространства и графа на нем. Рис.3.1 Построение координатного пространства на Y.
Обсудим теперь выбор множества XB. Очевидно, что с вычислительной точки зрения следует выбирать базис в X минимально возможной мощности. Однако, понятно, что если число элементов базиса мало, то индуцированная им координатная сетка на Y будет плохо различать элементы, в том смысле, что координаты всех их окажутся весьма близкими, и порождаемая топология на Y окажется весьма слабой для построения качественных решений с помощью графа MSW. Число соседей в графе окажется значительным, что приведет к катастрофическому росту вычислительных затрат из-за трудностей нахождения глобального экстремума. В силу весьма слабых предположений о структуре множеств X и Y, а также матрицы релевантности, нахождение регулярных методов выбора базиса представляется маловероятным. На практике оказывается возможным получать неплохие результаты при просто случайном выборе M элементов из X, где M следует выбирать большим или равным внутренней размерности X.
Защита IP подсетей от несанкционированного доступа и DDoS атак методом псевдослучайной смены сетевых адресов
В общем случае разработанные способ и система предназначены для формирования и передачи (доставки) целевого рекламного контента (рекламного сообщения) с учетом предполагаемых потребительских предпочтений абонентов или любой иной информации оператором определенному абоненту и/или определенной группе абонентов инфокоммуникативных сетей во время запроса мульдимедийного сервиса, например, голосовой и/или видео связи, ресурсов IPV, обмена текстовыми сообщениями. В качестве инфокоммуникативных сетей могут быть использованы ресурсы и оборудование операторов телефонной (проводной или беспроводной) связи, провайдеров услуг доступа к Интернет, а также электронные средства массовой информации, электронные терминалы и т.д. Таким образом, наиболее востребованным техническое решение будет в мобильной и фиксированной телефонной и видеосвязях сетей поколений NGN, 3G, LTE, в компьютерных системах мультимедийной связи Skype, ooVoo, при обработке вызовов в call center.
Приведем здесь упрощенную разработанную функциональную схему запатентованной системы (рис.4.9).
Рекомендательная система реализуется в исполняемом алгоритме на сервере SCSC, используя данные об абонентах и рекламные сообщения, хранящиеся в соответствующих БД (блоки 116 и 17). Экспериментальная версия системы была развернута в ходе совместных работ с компанией НСС в телекоммуникационной сети UMTS и начаты работы по реализации экспериментальной системы в сети 4G LTE компании «Основа Телеком». Проект создания и развертывания системы такого типа прошел экспертизу Фонда посевных инвестиций Российской венчурной компании и получил решение на получение инвестиций. (Приложение 1). Как видно из функциональной схемы и в соответствии с общей структурой системы рекомендательная система должна включать в себя как базу данных рекламных сообщений, которая создается и поддерживается рекламными агентствами и партнерами, так и базу данных пользователей, которая является охраняемым объектом оператора связи. Размещение этих компонентов рекомендательной системы на одной площадке недопустимо и требует ее распределенного развертывания с объединением через каналы связи. Экономически выгодным здесь может быть только использование Интернет. Однако безопасность системы при сегментировании через Интернет, потребует использования VPN для каждого из партнеров, что практически невыполнимо. В диссертации для решения задачи сегментирования рекомендательной системы предлагается использовать новейший метод организации соединения клиент-сервер, основанный на программно-конфигурируемых сетях (ПКС) и применения протокола с быстрым перескоком IP адреса.
Рекомендательная система разбивается на два сегмента, один из которых представляет собой локальные сети партнеров, в которых создаются и хранятся в стандартных базах данных рекламные сообщения. Как правило такие сети подключены к Интернет через шлюзы оснащенные firewall. Другой сегмент рекомендательной системы развертывается на площадках оператором мобильной связи и содержит весьма чувствительные персональные данные пользователей. Для этого сегмента такое решение в области безопасности не представляется приемлемым, поскольку стандартные средства firewall не защищают систему от атак, которые могут сделать невозможным наполнение базы данных сообщений, с другой стороны чувствительной к перехвату.
Поэтому представляет большой интерес защита от несанкционированного доступа и DDoS – атак иными способами. В настоящей работе предлагается использовать технология прыгающего IP– адреса, а операторский сегмент рекомендательной систем разместить внутри программно-конфигурируемой сети (ПКС). Технологическая идея подобна тому, как она описана в патенте[37]. Развитие этой идеи было сделано в статье [38].
В рассматриваемой работе предлагается способ защиты от распределенных атак типа «отказ в обслуживании», основанный на механизмах защиты на уровне протоколов и отличающийся от упомянутого изобретения тем, что рассматривается не клиент-серверное взаимодействие, а межсетевое взаимодействие. Общий компьютерный кластер, решающий задачу, разделяется физически на два сегмента серверов. Каждый из сегментов может быть атакован на предмет несанкционированного доступа или отказа в обслуживании. Для обеспечения снижения нагрузки на каждый сервер от производящих атаку «ботов» и исключения блокировки пакетов от легитимного клиента, используется смена адреса сервера по расписанию, известному только авторизованному пользователю. Боты не получают достоверной информации о расписании смены адресов и не могут посылать запросы на адрес сервера, таким образом, теряя возможность создать значительную нагрузку, нарушающую нормальное функционирование ресурса.