Методы и программные средства анализа поведения пользователей при работе с текстовыми данными для решения задач информационной безопасности
 Скачать 4.32 Mb.
|
|
Предложенный метод вычисления релевантности фрагментов текста Автором данной работы был предложен новый метод вычисления релевантности фрагментов текста, основанный на оценке весов тематик в нормализированном пространстве тематик, получаемом с помощью неотрицательной матричной факторизации. Первый этап предложенного метода состоит в нормировке пространства k тематик, т.е. в приведении длин вектор-столбцов матрицы W k к единице. Этот шаг обусловлен тем, что используемый мультипликативный алгоритм неотрицательной матричной факторизации даёт не единственное решение. Если матрицы W k и H k являются решением, то матрицы W k ·D и D -1 ·H k также будут решением, где матрица D — любая диагональная матрица размерности k×k с положительными диагональными элементами. Таким образом, используя разные значения диагональных элементов в D, можно получать преобладание различных тематик в тематическом представлении фрагментов H k . Для решения данной проблемы корректной оценки весов получаемых тематик во фрагментах производится нормировка матрицы W k , с использованием нормы L 2 для вычисления длин вектор-столбцов матрицы W k : A k = W k ·H k = Wn k ·Hn k , где Wn k = W k · diag(||w 1 || -1 , …, ||w k || -1 ), Hn k = diag(||w 1 ||, …, ||w k ||) · H k , m p pl l w w 1 2 , 1 ≤ l ≤ k. Второй этап заключается в оценке глобального веса во всём документе каждой полученной тематики. В отличие от сингулярного разложения при неотрицательной матричной факторизации отсутствует диагональная матрица, элементы которой оценивают веса выделенных тематик. Так в рассмотренном выше методе общей релевантности для этого используется относительная релевантность тематик. В предлагаемом методе глобальные веса 49 тематик оцениваются уже в нормализированном пространстве тематик. Столбцы матрицы Hn k =[hn ij ]соответствуют n фрагментам в нормированном пространстве k тематик. Каждая из k строк Hn k соответствует вектору, показывающему, насколько сильно представлена соответствующая тематика в каждом из n предложений. Тем самым, чем больше длина вектор- строки матрицы Hn k , тем соответствующая тематика «больше» представлена во всём документе. Исходя из этого, глобальный вес тематики l оценивается как длина l-ой вектор-строки матрицы Hn k (используется L 2 норма): l l n q lq l n q lq l h w h w hn hn 1 2 1 2 , 1 ≤ l ≤ k. Заключительным третьим этапом предложенного метода является расчёт релевантности фрагментов текста. Релевантность j-ого фрагмента вычисляется как L 1 норма вектора, являющегося результатом поэлементного умножение вектора глобальных весов тематик и вектора весов тематик в рассматриваемом фрагменте: k i ij i i k i ij i i i j h h w h w h w R 1 2 1 ) ( Для составления аннотации документа выбирается необходимое число предложений с наибольшими значениями релевантности, рассчитанными предложенным алгоритмом. При проведении экспериментальных исследований предложенный метод будем обозначать «NMF». 2.4.3 Экспериментальное исследование В настоящем подразделе были рассмотрены методы оценки значимости (релевантности) фрагментов текста документа. Анализируя данные методы можно утверждать, что все они так или иначе выполняют три шага (см. Таблицу 1): 1. Выделение основных тематик документа и оценка представленности (веса) каждой тематики в каждом фрагменте. Для выделения основных тематик текста используется метод латентно- семантического анализа, в качестве матричного разложения для которого применяется либо сингулярное разложение, либо неотрицательная матричная факторизация. 2. Оценка значимости выделенных тематик в документе (расчёт глобальных весов тематик). 3. Расчёт релевантности фрагмента текста как нормы вектора, являющегося результатом поэлементного умножение вектора глобальных весов тематик и вектора весов тематик в рассматриваемом фрагменте. 50 Вычисление релевантности фрагментов. Метод Вес i-ой тематики в документе (глобальный вес i-ой тематики) Вес i-ой тематики в j-ом фрагменте SVD-Square 2 i T j i V , NMF-Generic k p n q q p n q q i H H 1 1 , 1 , j i H , NMF i i h w 2 j i H , Для оценки качества алгоритмов вычисления релевантности фрагментов текста была рассмотрена задача автоматического аннотирования, которая заключалась в составлении аннотаций из наиболее релевантных предложений документа. Таким образом, оценка алгоритмов вычисления релевантности фрагментов текста сводилась к задаче оценки качества соответствующих алгоритмов автоматического аннотирования. В свою очередь, для оценки качества алгоритмов аннотирования используются эталонные наборы данных, которые включают в себя текстовые документы и модельные аннотации к ним, которые обычно строятся человеком. Причем для одного документа может быть построено несколько модельных аннотаций, т.к., вообще говоря, одна аннотация может быть хорошей для одного человека и, в тоже время, быть плохой для другого. Наборы данных могут различаться в зависимости от вида задачи аннотирования. Для оценки методов однодокументного аннотирования, в которых аннотации строятся к каждому документу из коллекции, используются наборы данных DUC 2001 и DUC 2002 [91-93]. Самым распространенным средством для оценки качества алгоритмов аннотирования является полностью автоматизированная утилита ROUGE (аббревиатура для Recall-Oriented Understudy for Gisting Evaluation) [85, 86, 91-92]. На вход подается множество построенных алгоритмом аннотаций и на каждую такую аннотацию одна (или более) модельная аннотация. Далее с помощью специальных метрик аннотации сравниваются, и алгоритму присваивается некоторая оценка (средняя по всем аннотациям) [93]. В работе [93] проводится анализ применимости различных метрик для различных задач аннотирования, в частности, для оценки алгоритмов однодокументного аннотирования на наборах DUC 2001 и DUC 2002 рекомендуется использовать метрики ROUGE-2, ROUGE-L, ROUGE-S, ROUGE-W. Также одним из результатов работы [93] является вывод, что наборы DUC 2001 и DUC 2002 обладают достаточным количеством модельных аннотаций для объективной оценки качества рассматриваемых алгоритмов (см. Таблицу 2). 51 Эталонные наборы данных DUC. Название набора данных Число документов Число модельных аннотаций DUC 2001 297 925 DUC 2002 533 1112 Для оценки качества алгоритмов аннотирования был выбран набор DUC 2002, т.к. он обладает большим числом документов и модельных аннотаций, чем набор DUC 2001. Для сравнения аннотаций использовалась утилита ROUGE с метриками ROUGE-2, ROUGE-L, ROUGE-S, ROUGE-W. При тестировании всех методов для каждого документа выделенные предложения перемешивались в случайном порядке. Это было сделано потому, что самые информативные предложения в документах из наборов DUC 2001 и DUC 2002, как правило, стоят в начале текста. Эталонные тестовые наборы документов DUC 2001 и DUC 2002 являются полностью англоязычными и состоят из новостных статей, поэтому для формирования списка термов использовались такие методы предварительной обработки текста, как удаление стоп-слов и приведение слов к нормализованной форме (стемминг). Кроме того, для проведения сравнений методов автоматического аннотирования на наборе DUC 2002 результирующие аннотации должны состоять из 100 слов, поэтому в качестве фрагментов текста выбирались его предложения. Все рассматриваемые алгоритмы последовательно выбирали предложения текста для аннотации в порядке убывания их релевантности до тех пор, пока суммарное количество слов в выбранных предложениях не превысит 100. Затем выбранные предложения упорядочивались в порядке появления их в тексте, и получаемая таким образом аннотация подавалась на вход утилите ROUGE, которая, в свою очередь, оставляла только первые 100 слов 3 Далее приводятся данные сравнительных экспериментов с рассмотренными алгоритмами автоматического аннотирования: SVD-Square, NMF-Generic и NMF. В дополнение к выбранными алгоритмам также демонстрируются результаты при случайном выборе предложений — RANDOM, при выборе самых длинных по числу слов предложений — WORD COUNT и при выборе первых предложений документа — FIRST K. В тематических моделях число тематик k выбирается существенно меньшим, чем размерности исходной матрицы текста A ℝ mn , т.е. k << min(m, n). Для набора DUC 2002 среднее число строк матриц документов составляло 239, а среднее число столбцов — 37. Поэтому на диаграмме (см. Рисунок 12), показывающей изменение качества получаемых аннотаций в 3 Параметры ROUGE: ROUGE-1.5.5.pl -e /duc2002 -m -l 100 -2 4 -n 2 -w 1.2 -s -a duc2002.xml 52 зависимости от числа выбираемых тематик, приводятся данные для числа тематик от 1 до 20. Из- за схожести результатов при использовании различных метрик сравнения аннотаций, на диаграмме приводятся данные для метрики ROUGE-2. Соответственно, чем выше значение ROUGE-2-F, тем выше качество полученных алгоритмом аннотаций. Сравнение методов автоматического аннотирования. В Таблице 3 показаны значения различных метрик ROUGE для рассмотренных методов аннотирования. В методах, основанных на латентно-семантическом анализе (SVD-Square, NMF- Generic, NMF), число тематик выбирается исходя из соотношения длины аннотации (100 слов) к длине самого текста. Для документа подсчитывается число его слов и определяется, какой процент p% от всего текста должна составлять аннотация. Тогда если исходная матрица документа имеет размерность m×n, то число тематик подсчитывается как ) , min( 100 n m p k Сравнение методов автоматического аннотирования. Метрики (ROUGE) SVD-Square NMF-Generic NMF RANDOM WORD COUNT FIRST K ROUGE-2-F 0.18933 0.18385 0.19251 0.12364 0.14727 0.16308 ROUGE-L-F 0.36799 0.36467 0.37230 0.29483 0.31329 0.33034 ROUGE-S4-F 0.15091 0.14636 0.15358 0.09503 0.11441 0.12923 ROUGE-W-F 0.20874 0.20405 0.21066 0.16227 0.17510 0.19312 53 Полученные экспериментальные данные, приведенные на Рисунке 12 и в Таблице 3, показывают, что предложенный метод вычисления релевантности фрагментов текста, использующий неотрицательную матричную факторизацию для тематического моделирования, превосходит существующие популярные методы по качеству получаемых аннотаций. 2.5 Выводы Предложен новый подход к анализу и моделированию поведения пользователя, состоящий в представлении информации о потоке документов, с которыми работал пользователь, в виде многомерного тематического временного ряда. Временные ряды показывают изменение весов тематик (тематическую направленность) во времени, при этом рассматриваются характерные тематики анализируемого пользователя, получаемые с использованием ортонормированной неотрицательной матричной факторизации. Проведено исследование методов вычисления релевантности фрагментов текста для задачи удаления информационного шума из документа. В рамках данного исследования был предложен новый метод, использующий неотрицательную матричную факторизацию для тематического моделирования. Удаление нерелевантных фрагментов текста позволит выделять тематики, наиболее точно описывающие контент, с которым работают пользователи, и приведёт к уменьшению анализируемых данных. Экспериментальные исследования с применением удаления информационного шума из документов при определении фактов работы пользователя с несвойственными ему текстовыми документами будут проведены в следующем разделе. 54 3 МЕТОДЫ ОБНАРУЖЕНИЯ АНОМАЛЬНОГО ПОВЕДЕНИЯ ПОЛЬЗОВАТЕЛЯ Настоящий раздел посвящён исследованию и разработке методов обнаружения аномального поведения пользователя при работе с текстовыми данными. Для представления поведенческой информации пользователя будет использоваться предложенная в предыдущем разделе модель поведения, которая отображает поток документов, с которыми работал пользователь, в многомерный тематический временной ряд. Одной из специфик решаемой задачи является то, что корпоративный пользователь за относительно длительные промежутки времени (например, 12 или 24 часа, рабочее/нерабочее время) обычно успевает интересоваться всем характерным для себя текстовым контентом — рабочие документы, новости и т.п. Если рассмотреть короткие интервалы времени (например, 15 или 30 минут), то очерёдность обращения пользователя к документам определённых тематик зачастую трудно предугадать. Например, за день пользователь успевает поработать с рабочими документами определённых категорий, а также прочитать характерные для себя новости, но нельзя спрогнозировать в какой последовательности в течение дня он будет обращаться к различным категориям рабочих документов и новостей. Далее в подразделе 3.3 это утверждение также будет наглядно продемонстрировано на примере сформированной модели поведения реального корпоративного пользователя. Исходя из указанной специфики было предложено два подхода к обнаружению аномального поведения пользователя: 1. Прогнозирование тематической направленности пользователя по «длительным» интервалам времени на основе сложившихся в прошлом тенденций работы пользователя с текстовым контентом. 2. Оценка принадлежности документа, с которым работает пользователь, к характерным тематикам анализируемого пользователя. Первый подход позволит оценивать общую аномальность поведения пользователя за «длительное» время, а второй необходим для оценки аномальности каждого обращения пользователя документам. Более формально задачу обнаружения аномального поведения пользователя можно сформулировать следующим образом: по заданному потоку текстовых документов x = {(d, t)} X требуется построить функцию f: (d, t) ℝ, называемую решающей функцией, такую, что для анализируемого объекта (d, t) X ставится в соответствие значение аномальности a ℝ, которое зависит от того, насколько объект (d, t) «похож» на элементы множества x. 55 Очевидно, что такая постановка задачи является интуитивной, поскольку не определяет понятие «сходства» на множестве X, и, вообще говоря, не даёт формального определения самого понятия аномальности. Таким образом, для решения задачи обнаружения аномалии требуется решить две подзадачи: Формально определить понятие аномалии, то есть задать критерии, по которым объект из исходного множества может быть определен как аномальный. Разработать метод поиска таких аномалий в исходном множестве. В первом подходе рассматривается пользовательский поток документов x = {(d, t)}, где документ d представляет объединённые текстовые данные пользователя, к которым он обращался за время [t, t+t), при этом t выбирается достаточно «длительным». По потоку x строится тематическая модель поведения пользователя (L m , W k , H k , T n ). Тогда поток x можно представить в виде множества упорядоченных пар F = ((H 1 , t 1 ), …, (H n , t n )), где t 1 t 2 … t n , H i соответствует тематическому представлению документа d i (1 i n) в пространстве k тематик. Данная обучающая выборка F рассматривается как k-мерный временной ряд, по которому строится прогноз на следующие p шагов: ((𝐻 𝑓 𝑛+1 , t n+1 ), …, ( 𝐻 𝑓 𝑛+𝑝 , t n+p )). После чего строится решающая функция: f ((d, t n+j ), (L m , W k )) = || 𝐻 𝑓 𝑛+𝑗 -h|| 1 = a j , где h — представление документа d в тематическом пространстве (L m , W k ), a j ℝ — уровень аномальности обращения анализируемого пользователя к контенту d за время [t n+j , t n+j +t), 1 j p. Здесь уровень аномальности соответствует отклонению тематической направленности пользователя от ожидаемых значений, поэтому чем меньше значение a j , тем менее аномально поведение пользователя. Во втором подходе рассматривается поток документов x = {(d, t)}, где документ d соответствует тексту документа, к которому пользователь обратился в момент времени t. По потоку x строится тематическая модель поведения пользователя (L m , W k , H k , T n ). Тогда цель данного подхода состоит в нахождении решающей функции f (d, (L m , W k )) = b, где b является оценкой степени принадлежности документа d к тематикам пользователя, задаваемым тематическим пространством (L m , W k ). Чем сильнее документ соответствует характерным тематикам анализируемого пользователя, тем менее аномально обращение данного пользователя к документу. Исходя из этого, оценку аномальности a можно вычислить как 𝑓(𝑏), где f — функция, задающая противоположную зависимость между величинами a и b, примером такой функции может служить отрицание. Перед детальным рассмотрением предложенных подходов к обнаружению аномального поведения пользователей приведём описание базового сценария проведения экспериментальных 56 исследований, который используется в современных научных работах, также посвящённых выявлению внутренних угроз. 3.1 Базовый сценарий проведения экспериментальных исследований Как уже было отмечено во введении, на сегодняшний день не существует разработанных подходов к обнаружению аномального поведения пользователей на основе анализа содержимого обрабатываемых текстовых данных с использованием методов машинного обучения. Однако есть работы, посвящённые обнаружению внутренних угроз на основе анализа структурированных данных, описывающих активность корпоративных пользователей [14-16]. В Таблице 4 приведены примеры признаков, на основе которых выявляется аномальное поведение пользователя в данных работах. Примеры поведенческих признаков пользователя. Тип источника информации Пример поведенческого признака пользователя Электронная почта Число прикреплённых файлов в отправленных письмах Файловая активность Число файловых операций со съёмными устройствами События авторизации Число авторизаций на различных машинах сети Посещение web-страниц Число заблокированных страниц Вычисляемые соотношения Отношение числа операций с файлами на съёмных устройствах к общему числу операций с файлами Отношение объёма загруженных и скаченных данных с web-ресурсов Общей практикой при проведении экспериментальных исследований в области обнаружения внутренних угроз является следующий сценарий: 1. Все реальные собранные поведенческие данные считаются легитимными. 2. К собранным поведенческим данным добавляются данные, моделирующие заранее специфицированные внутренние угрозы. 3. Анализируется суточная активность пользователей и рассматривается задача бинарной классификации: требуется определить дни с аномальной активностью пользователей, которая соответствует специфицированным угрозам. Результатом работы большинства известных бинарных классификаторов является численная оценка a ℝ, показывающая принадлежность анализируемого объекта к одному из 57 двух классов. Далее итоговый класс c {0, 1} анализируемого объекта определяется исходя из выбираемого порога w ℝ: w a если w a если c , 1 , 0 Для оценки качества бинарного классификатора обычно используют ROC-кривую — графическая характеристика, показывающая зависимость доли верных положительных классификаций от доли ложных положительных классификаций при варьировании порога решающего правила (оценки аномальности) [94]. Для сравнения нескольких моделей классификации используют значение AUC (англ. Area Under Curve), которое вычисляется как площадь под ROC-кривой и является агрегированной характеристикой качества классификации, не зависящей от соотношения цен ошибок [94]. Чем больше значение AUC, тем лучше модель классификации. Если проводится серия экспериментов, то для оценки полученного множества значений AUC для каждого алгоритма классификации используются устойчивые (робастные) оценки центральной тенденции (медиана) и разброса (интерквартильный размах, ИКР) [95]. Интерквартильным размахом (англ. Interquartile Range) называется разность между третьим и первым квартилями множества значений AUC. Несмотря на то, что в работах [14-16] сценарии внутренних угроз и соответствующие поведенческие признаки формируются вручную, средняя точность обнаружения их методов составила 0.8-0.9 AUC. Кроме того, анализ литературы [96-98] показал, что в современных методах решения задач в области анализа поведения пользователей (в частности распознавание пользователей по динамике их работы с клавиатурой и «мышью») значения AUC также находятся на уровне 0.9. Для проведения экспериментальных исследований разрабатываемых методов обнаружения аномального поведения пользователя требуются данные о фактах работы пользователя с текстовой информацией и о её содержании. Были предъявлены следующие критерии к набору экспериментальных данных: текстовая информация из корпоративной среды; возможность сопоставления текстовых данных с пользователями; возможность определения времени операций с текстовыми данными. По сформулированным выше критериям для проведения дальнейших экспериментальных исследований за основу был выбран набор реальной корпоративной переписки Enron [99]. Набор Enron содержит электронную почту 150 сотрудников (около 0.5 миллиона писем вместе с прикреплёнными к ним файлами) американской энергетической компании (главным образом из высшего руководства), обанкротившейся в конце 2001 года. Также в пользу выбора данного набора свидетельствовал тот факт, что его использование широко распространено в работах, 58 посвящённых анализу текстовых данных [99, 100], и конференциях по противодействию терроризму и компьютерной безопасности [101]. Отметим, что текстовые данные в наборе Enron являются англоязычными, поэтому на этапе предварительной обработки текста использовалось удаление стоп-слов и приведение слов к нормализованной форме (стемминг) на основе семантической сети WordNet [102]. Для описания проводимых экспериментальных исследований введём понятие «период анализа» — интервал времени, пользовательские поведенческие данные из которого используются для обнаружения аномалий. Напомним, что для формирования модели поведения пользователя используются его поведенческие данные из тренировочного периода. Пользователя, для которого формируется модель поведения, будем также называть анализируемым. Тогда под «экспериментальным периодом» (ЭП) будем понимать совокупность тренировочного периода и периода анализа (см. Рисунок 13). Экспериментальный период. Далее при разработке методов обнаружения аномального поведения пользователя в соответствующих подразделах будут подробно описаны сценарии проводимых экспериментальных исследований. 3.2 Прогнозирование тематической направленности пользователя Прогнозирование тематической направленности пользователя осуществляется по «длительным» интервалам времени на основе сложившихся в прошлом тенденций работы пользователя с текстовым контентом. Для описания предыстории работы пользователя с текстовыми данными должен быть задан тренировочный период, который разбивается на последовательно измеренные через некоторые промежутки времени интервалы (см. Рисунок 14) [103]. Например, в качестве промежутка времени (шага) может быть выбран 59 день, а также время, за которое происходит заданное число событий. Таким образом, выбираемые промежутки времени не обязательно должны быть равны между собой. Далее предложенная тематическая модель поведения пользователя применяется не к отдельным документам пользователя, а к объединённому текстовому контенту заданных временных интервалов тренировочного периода. Другими словами, столбцы в матрицах A и H k будут соответствовать временным интервалам, при этом матрица H k задаёт k-мерный временной ряд изменения тематической направленности пользователя. Формирование временных рядов тематической направленности пользователя. Для построения прогноза k-мерного тематического временного ряда в предлагаемом подходе к обнаружению аномального поведения пользователя применялись как стандартные методы прогнозирования, так и собственный оригинальный метод прогнозирования. После построения прогнозов тематических рядов вычисляются отклонения тематической направленности пользователя за период анализа (время прогноза) от спрогнозированных значений (см. Рисунок 15). Вычисленные отклонения используются для идентификации временных интервалов с несвойственной тематической направленностью пользователя, т.е. соответствующих аномальному поведению. Выделенные аномальные временные интервалы могут означать, что пользователь либо не интересуется своим обычным контентом, либо интересуется, но в несвойственное время. 60 Пример отклонений тематических временных рядов от прогноза. Исследование предлагаемого подхода на основе прогнозирования тематической направленности пользователя за длительные интервалы времени проводилось в два этапа: 1. Предварительное исследование применимости подхода. Первоочередной задачей являлась проверка гипотезы о возможности прогнозирования получаемых тематических рядов пользователя на основе данных за длительные интервалы времени. Для этого достаточно выбрать произвольный тренировочный период тестового пользователя и спрогнозировать, используя стандартные алгоритмы прогнозирования, полученные тематические временные ряды. Далее сравнить значения отклонений тематической направленности тестового пользователя от спрогнозированных данных и аналогичные значения отклонений, рассчитанные для пользователей отличных от тестового. 2. Проведение серии экспериментов. В случае успешного проведения эксперимента на этапе предварительного исследования для подтверждения применимости предлагаемого подхода провести серию экспериментов с различными пользователями и оценкой качества обнаружения аномального поведения пользователя. Ниже настоящий подраздел организован следующим образом. В пункте 3.2.1 рассматриваются популярные методы прогнозирования временных рядов и представлен собственный оригинальный метод прогнозирования на основе ортонормированной неотрицательной матричной факторизации. Пункт 3.2.2 посвящен экспериментальному исследованию предложенного подхода к обнаружению аномального поведения пользователя на примере реальной корпоративной переписки, содержащейся в наборе электронных писем Enron. 61 3.2.1 Методы прогнозирования временных рядов Прогнозирование временных рядов заключается в построении модели для предсказания будущих событий, основываясь на известных событиях прошлого [103]. Для построения прогноза временных рядов использовались следующие модели: На этапе предварительного исследования применимости подхода — модель авторегрессионного интегрированного скользящего среднего (англ. AutoRegressive Integrated Moving Average, ARIMA) и авторегрессионная модель дерева (англ. AutoRegressive Tree Model, ART). Соответствующие алгоритмы прогнозирования ARIMA [104, 105], ARTXP [104, 106] используются в службах Microsoft Analysis Services, входящих в состав Microsoft SQL Server 2012 [104]. На этапе проведения серии экспериментов — модель авторегрессии (англ. AutoRegressive model, AR) [107], авторегрессионная модель дерева (ART) и предложенная оригинальная модель на основе ортонормированной неотрицательной матричной факторизации [29, 32]. Линейная модель авторегрессии (AR), модель авторегрессионного интегрированного скользящего среднего (ARIMA) и авторегрессионная модель дерева (ART) Для построения прогноза временных рядов на этапе предварительного исследования применимости подхода использовались средства Microsoft Analysis Services, входящие в состав Microsoft SQL Server 2012. В Microsoft Analysis Services реализованы два базовых алгоритма прогнозирования временных рядов: ARIMA, ARTXP. Алгоритм ARIMA (англ. AutoRegressive Integrated Moving Average — авторегрессионное интегрированное скользящее среднее) был добавлен к алгоритму ARTXP для повышения точности долгосрочного прогнозирования. Это реализация процесса вычисления авторегрессионных интегрированных скользящих средних, описанного Боксом и Дженкинсом [104, 105]. Методология ARIMA позволяет определять зависимости в результатах наблюдений в форме последовательных временных рядов, при этом модель включает описание случайных скачков. Алгоритм ARIMA также поддерживает мультипликативную сезонность. В основе данного алгоритма лежит модель, которую обычно обозначают, как ARIMA(p,d,q), где p, d и q — целые неотрицательные числа, соответственно характеризующие порядок для частей модели: авторегрессионной (AR), интегрированной (I) и скользящего среднего (MA): Авторегрессионная модель порядка p, AR(p) [107] — модель временных рядов, в которой значение временного ряда в данный момент времени может быть выражено в виде линейной комбинации предыдущих значений этого же ряда и случайной ошибки, обладающей 62 свойством «белого шума». Формально авторегрессионную модель порядка p определяют следующим образом: - t p i i t i t X c X 1 , где i — параметры авторегрессионной модели, c — константа (для простоты константу, как правило, опускают), t — белый шум; - Форма записи с помощью оператора задержки L (𝐿𝑥 𝑡 = 𝑥 𝑡−1 ): t p i i i t X L c 1 1 Модель скользящего среднего порядка q, MA(q) [108] — модель временных рядов, в которой текущее значение случайного процесса представляется в виде линейной комбинации текущего и прошлых значений ошибки, по своим свойствам соответствующей «белому шуму»: - t q i i t i t X 1 , i — параметры модели скользящего среднего; - t q i i i t L X 1 1 Авторегрессионная модель скользящего среднего, ARMA(p,q) [109, 110] — обобщение (сумма) двух более простых моделей временных рядов: модель авторегрессии (AR) порядка p и модель скользящего среднего (MA) порядка q: - q i i t i p i i t i t t X c X 1 1 ; - t q i i i t p i i i L c X L 1 1 1 1 Интегрированная модель авторегрессии – скользящего среднего, ARIMA(p,d,q) [105, 111] — является расширением моделей ARMA для нестационарных временных рядов, которые можно сделать стационарными взятием разностей некоторого порядка от исходного временного ряда: - p i i t d i q i i t i t t d X c X 1 1 , где d — оператор разности временного ряда порядка d (последовательное взятие d раз разностей первого порядка); - t q i i i t d p i i i L c X L L 1 1 1 1 1 Авторегрессионная модель дерева (англ. AutoRegressive Tree Model, ART) — модель дерева принятия решений, в «листьях» которого располагаются авторегрессионные модели (AR). 63 Для реализации данной модели использовался алгоритм ARTXP, разработанный Microsoft, который основан на их реализации алгоритма дерева принятия решений. Алгоритм ARTXP устанавливает соотношение между переменным количеством предыдущих элементов и каждым текущим элементом, для которого выполняется прогноз [106]. Отметим основные отличия базовых алгоритмов Microsoft Analysis Services [104]: Алгоритм ARTXP поддерживает учёт корреляций между несколькими анализируемыми рядами, т.е. поддерживает перекрестное прогнозирование. Алгоритм ARIMA не поддерживает перекрестное прогнозирование; Алгоритм ARTXP используется для прогнозирования ближайших значений временного ряда (примерно 5 временных шагов) и даёт существенно менее точный долгосрочный прогноз по сравнению с ARIMA. По умолчанию алгоритм временных рядов Microsoft Analysis Services использует оба метода (ARTXP, ARIMA) и объединяет результаты для повышения точности прогнозирования. Если необходимо использовать один определенный метод, можно настроить параметры алгоритма на использование только метода ARTXP или ARIMA либо задать степень влияния каждого из базовых методов на итоговый результат. Кроме того, перекрестное прогнозирование также доступно в случае использования сочетания базовых методов. Модель прогнозирования на основе ортонормированной неотрицательной матричной факторизации Сначала рассмотрим случай построения прогноза одномерного временного ряда, т.е. анализируемый временной ряд можно представить в виде вектора. Для того чтобы представить вектор временного ряда в матричной форме введём понятие порядка модели, т.е. количество подряд идущих значений временного ряда по которым определяются основные взаимосвязи, аналогично модели авторегрессии. Тогда вектор временного ряда размерности n при заданном порядке модели p можно представить в виде матрицы размерности p×(np+1), чьи столбцы соответствуют всевозможным подпоследовательностям длины p подряд идущих временных точек анализируемого ряда (см. Рисунок 16). 64 Отображение вектора временного ряда в матрицу. Задача прогнозирования следующего (n+1)-го значения (см. Рисунок 16) сводится к задаче аппроксимации пропущенных значений в матрице временного ряда (матрица [M|m]) на основе уже заполненных значений (матрица M) — так называемая задача подстановки пропущенных значений (англ. Missing Value Imputation) [112, 113]. Для решения задачи подстановки пропущенных значений в матричных данных было предложено исследовать новый подход, основанный на применении методов неотрицательной матричной факторизации для нахождения взаимосвязей между элементами входной матрицы [29]. Рассмотрим ортонормированную неотрицательную матричную факторизацию матрицы M: M ≈ M k = Wm k ∙ Hm k , Wm k T ∙ Wm k = I, где M k является аппроксимацией исходной матрицы M, k — число «латентных» признаков, при этом k << min(p, np+1) (см. пункт 2.2.3). Матрица Wm k задает отображение между пространством «латентных» признаков размерности k и пространством позиций элементов (от 1 до p) в сформированных подпоследовательностях длины p. Таким образом, выделенные «латентные» признаки содержат только наиболее значимую информацию о взаимосвязях между позициями элементов среди всех подпоследовательностей. Каждый столбец матрицы Hm k описывает соответствующую подпоследовательность в виде вектор-столбца с весами соответствующих базисных «латентных» признаков. С другой стороны, применение ортонормированной неотрицательной матричной факторизции к матрице M, можно рассмотреть с точки зрения регрессионного анализа. Пусть M i — i-ый столбец матрицы M, который соответствует наблюдаемым значением, тогда требуется найти вектор минимизирующий: ‖𝑀 𝑖 − 𝑊𝑚 𝑘 ∙ 𝛽‖ 2 65 Решением данной регрессионной задачи методом наименьших квадратов в матричном виде является [112, 114]: 𝛽̂ = (𝑊𝑚 𝑘 𝑇 ∙ 𝑊𝑚 𝑘 ) −1 ∙ 𝑊𝑚 𝑘 𝑇 ∙ 𝑀 𝑖 = 𝑊𝑚 𝑘 𝑇 ∙ 𝑀 𝑖 При этом будут получены следующие оценки наблюдаемых значений: 𝑀 ̂ 𝑖 = 𝑊𝑚 𝑘 ∙ 𝛽̂ = (𝑊𝑚 𝑘 ∙ 𝑊𝑚 𝑘 𝑇 ) ∙ 𝑀 𝑖 (1) На основе формулы (1) был разработан алгоритм аппроксимации пропущенных значений в матрице [M|m]. Общая идея заключается в изначальной инициализации пропущенных значений в m, и дальнейшем итерационном приближении к решению с помощью формулы (1) [112]. Приведём пошаговое описание предложенного алгоритма, на основе ортонормированной неотрицательной матричной факторизации: Шаг 0. Рассчитать ортонормированную неотрицательную матричную факторизацию матрицы M (с изначально заполненными элементами): M ≈ M k = Wm k ∙ Hm k , Wm k T ∙ Wm k = I. Шаг 1. Инициализировать пропущенное значения в столбце m. Традиционно в литературе пропущенные значения инициализируются средним значением по столбцу или всему вектору временного ряда [112]. Если известны данные о сезонности временного ряда, то при расчёте средних значений можно учитывать и шаг сезонности. На выходе получается полностью заполненный столбец m i , где i = 0. Шаг 2. Рассчитать аппроксимацию столбца m с помощью полученной на шаге 0 модели ортонормированной неотрицательной матричной факторизацию (ONMF-модель) по формуле (1): 𝑚 𝑎𝑝𝑝𝑟𝑜𝑥 = (𝑊𝑚 𝑘 ∙ 𝑊𝑚 𝑘 𝑇 ) ∙ 𝑚 𝑖 . После чего сформировать m i+1 путем замены пропущенного значения в исходном столбце m соответствующим полученным значением в m approx Шаг 3. До тех пор пока значение ‖𝑚 𝑖 − 𝑚 𝑖+1 ‖ ‖𝑚 𝑖 ‖ ⁄ не меньше заданного порога (как правило, значение порога берут равным 10 -6 ), установить i = i+1 и перейти на шаг 2. На практике обычно достаточно 5-6 шагов для сходимости алгоритма. При прогнозировании многомерных временных рядов можно их прогнозировать как по отдельности, так и с поддержкой перекрестного прогнозирования. Для этого совокупность из m временных рядов нужно объединить в одну матрицу (см. Рисунок 17). Тогда получаемые «латентные» признаки (матрица Wm k ) будут содержать наиболее значимую информацию о взаимосвязях между позициями элементов всех временных рядов, следовательно, будет учитываться влияние всех анализируемых временных рядов друг на друга. 66 Формирование матрицы прогнозирования для совокупности временных рядов. 3.2.2 Экспериментальные исследования Исследование предлагаемого подхода на основе прогнозирования тематической направленности пользователя за длительные интервалы времени проводилось в два этапа: предварительное экспериментальное исследование применимости подхода — экспериментальная проверка гипотезы о возможности прогнозирования тематических рядов пользователя на основе данных за длительные интервалы времени; проведение серии экспериментов в случае успешного проведения эксперимента на этапе предварительного исследования. Предварительное экспериментальное исследование Для предварительного экспериментального исследования предлагаемого подхода из набора Enron были выбраны два сотрудника с наибольшим количеством писем: «kaminski-v» и «dasovich-j». В качестве экспериментального периода были выбраны три подряд идущих месяца наиболее активных переписок выбранных пользователей: март 2001 г., апрель 2001 г., май 2001 г. При этом март и апрель использовались как тренировочный период, а 15 дней мая как период анализа (время прогноза). Шаг временного интервала выбирался в 1 сутки. Модель поведения и прогнозы соответствующих тематических рядов строились для пользователя «kaminski-v», переписка пользователя «dasovich-j» использовалась для демонстрации разницы в значениях отклонений тематических рядов от прогноза. Полученные тематические временные ряды, отражающие поведение пользователя «kaminski-v» за тренировочные период, представлены на Рисунке 18 и Рисунке 19. На изображённых временных рядах чётко прослеживается недельная периодичность, поэтому при их прогнозировании задавались следующие условия: 67 шаг периодичности равен 7, что соответствует недельной периодичности с учётом дискретизации данных по суткам. значения в спрогнозированных данных не могут быть отрицательными, т.к. они соответствуют весам тематик. отсутствующие значения временного ряда нужно считать равными 0, что соответствует отсутствию обращений пользователя к текстовой информации. Для построения прогнозов тематических временных рядов применялся алгоритм Microsoft Analysis Services, используемый по умолчанию (см подпункт 3.2.1.1). Таким образом, для прогнозирования использовались оба базовых метода (ARTXP, ARIMA), а их результаты были объединены для повышения точности прогноза. На основе тематического портрета пользователя «kaminski-v» были получены представления для следующих 15 временных интервалов (суток) как для пользователя «kaminski-v», так и для пользователя «dasovich-j» (см. Рисунок 18 и Рисунок 19). Результаты отклонений значений рядов от соответствующих прогнозов за 15 суток приведены в Таблице 5. Временные ряды для 1-ой тематики. 68 Временные ряды для 2-ой тематики. Значения отклонений тематических временных рядов. Прогнозируемые временные интервалы Значения отклонений от прогноза для пользователя «kaminski-v» Значения отклонений от прогноза для пользователя «dasovich-j» Тематика 1 Тематика 2 Сумма Тематика 1 Тематика 2 Сумма 01.05.2001 0.010859 0.040380 0.051239 0.185229 0.158786 0.344015 02.05.2001 0093153 0.049967 0.143120 0.199623 0.158365 0.357988 03.05.2001 0.000761 0.003193 0.003954 0.219452 0.225863 0.445316 04.05.2001 0.016120 0.023538 0.039658 0.138337 0.150471 0.288808 05.05.2001 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 06.05.2001 0.086634 0.015882 0.102516 0.018066 0.102539 0.120605 07.05.2001 0.004251 0.006558 0.010808 0.137580 0.172048 0.309628 08.05.2001 0.017441 0.043809 0.061250 0.333764 0.339931 0.673695 09.05.2001 0.059094 0.004907 0.064001 0.451171 0.424336 0.875507 10.05.2001 0.006746 0.040468 0.047214 0.311414 0.309710 0.621124 11.05.2001 0.030262 0.032212 0.062475 0.201191 0.203978 0.405170 12.05.2001 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 13.05.2001 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 14.05.2001 0.002805 0.037000 0.039805 0.287335 0.336787 0.624122 15.05.2001 0.021148 0.053362 0.074510 0.196921 0.167717 0.364638 |