Программирование, 2019, № 3, стр. 18-37

3.1. Двухэтапный поиск по образцу

Для решения перечисленных выше проблем предлагается новый подход на основе двухэтапного поиска по образцу [22]. В этом подходе вместо традиционного поискового запроса используется документ-образец, а цель поискового процесса – найти документы и сообщения релевантные этому образцу. В качестве документа-образца удобно использовать примеры сообщений и публикаций, полученных из заведомо террористического или экстремистского источника. При этом сам поиск в сети Интернет осуществляется с помощью стандартных поисковых машин или поисковых машин социальных сетей. Для этого на первом этапе из документа-образца выделяются ключевые слова, с использованием языково-независимого подхода на основе ортонормированной неотрицательной матричной факторизации [11] и представления слов в виде n-грамм. Найденные ключевые слова формируют поисковый запрос, который выполняется сторонней поисковой машиной, а возвращаемая выдача, содержащая много шума и ошибок, уже ранжируется предложенным оригинальным методом на втором этапе. Ранжирование осуществляется таким образом, чтобы более релевантными были те документы в выдаче, в которых веса скрытых тематик документа-образца максимальны. Общая схема работы предложенного подхода представлена на рис. 1.

Документ-образец перед поиском и документы, возвращаемые поисковой машиной, “обогащаются” за счет информации из их ссылочного окружения. Для этого выделяются все ссылки и хэштеги в документах, а специально реализованный краулер осуществляет поиск в сети Интернет информации по заданной ссылочной структуре в зависимости от типа ссылки. Для веб ссылки выполняется http запрос для получения содержимого страницы по ее адресу, по хештегу осуществляется выборка заданного числа последних сообщений, содержащих этот тег в социальной сети, где он используется, для имени пользователя осуществляется выборка заданного числа его последних сообщений из соответствующей социальной сети. Таким образом формируется документ, приблизительно описывающий информацию по каждой заданной ссылке. К этому документу применяется разработанный метод выделения ключевых слов или метод аннотирования (раздел 3.3). Получаемая информационная “выжимка” вместо ссылочной структуры добавляется в исходный анализируемый текст до того, как будет формироваться его матричное представление (раздел 3.2). Общая схема “обогащения” документа за счет информации из его ссылочного окружения представлена на рис. 2.

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

3.2. Матричное представление на основе n-грамм и тематической модели документа

Предлагается использовать представление документа в виде матрицы, для этого его текст разбивается на непересекающиеся фрагменты. В качестве фрагментов выбирают предложения текста или его параграфы (при обработке текста большого размера). Для представления полученной коллекции фрагментов применяется векторная модель [23, 24], в которой в качестве признаков фрагментов текста используются n-граммы. Это позволяет решить проблемы, связанные с многоязыковостью, наличием ошибок и опечаток. Для получения признаков на основе n-грамм для каждого слова в тексте берутся подряд идущие буквосочетания фиксированной длины n [3]. Данный метод является достаточно универсальным, так как он применим для многих современных языков. Таким образом, пространство признаков формируется из множества полученных различных n-грамм L_m. Основным достоинством n-граммного представления текстов является отсутствие необходимости дополнительной лингвистической обработки текста. Разбиение на n-граммы вычислительно проще, чем лингвистический стемминг, а из-за ограниченности алфавита во всех языках максимальное число различных признаков также ограничено и невелико (при небольших n) по сравнению с числом слов. К недостаткам n-грамм можно отнести то, что они могут сильно увеличить количество “ненулевых” признаков каждого отдельного текста, особенно при небольших значениях n.

Набор текстовых фрагментов документа в такой модели представляется в виде числовой матрицы A ∈ ${{\mathbb{R}}^{{m \times n}}}$, строки которой соответствуют признакам, а столбцы – фрагментам. Каждый фрагмент A_j (1 ≤ j ≤ n) представляется в виде числового вектора A_j = [a_1,j, a_2,j, …, a_m,j]^T фиксированной размерности m, равной числу уникальных n-грамм, a_i,j – i-я (1 ≤ i ≤ m) компонента вектора A_j определяет вес i-го признака в j-м фрагменте. Вес a_i,j вычисляется как произведение трех составляющих: a_i,j = L_i,j · G_i · N_j, где L_i,j – локальный вес признака i в фрагменте j, G_i – глобальный вес признака i во всех фрагментах, N_j – нормализация вектора фрагмента A_j. Далее для построения тематической модели документа к его матричному представлению в пространстве n-грамм применяется метод латентно-семантического анализа, который основан на применении ортонормированной неотрицательной матричной факторизации (ОНМФ). Исходное матричное представление текста (матрица A) аппроксимируется произведением двух матриц с неотрицательными элементами: A ≈ ≈ W_k · H_k. Точность аппроксимации обеспечивается нахождением таких матриц W_k ∈ ${{\mathbb{R}}^{{m \times k}}}$ и H_k ∈ ${{\mathbb{R}}^{{k \times n}}}$, которые минимизируют целевую функцию [11]: f(W_k, H_k) = $\frac{1}{2}{\text{||}}A\, - \,{{W}_{k}}{{H}_{k}}{\text{||}}_{F}^{2}$ + $\frac{\alpha }{2}{\text{||}}W_{k}^{T}{{W}_{k}}\, - \,I{\text{||}}_{F}^{2}$, где k ≪ ≪ min(m, n), α ≥ 0 – параметр ортонормированности W_k (при α > 0 накладывается дополнительное условие: $W_{k}^{T} \cdot {{W}_{k}}$ = I). Левая матрица (матрица тематик, W_k) служит для отображения между пространством тематик и пространством текстовых признаков, а правая (матрица фрагментов, H_k) – для представления фрагментов в пространстве тематик, фрагментам соответствуют столбцы матрицы H_k [11, 25, 26]. Требование ортонормированности накладывается на левую матрицу W_k для того, чтобы ее транспонирование позволило отображать пространство признаков в сформированное пространство тематик. Таким образом, получив тематическое представление одного документа, можно любой документ отобразить в пространство его тематик. Отметим, что применение ОНМФ к исходному матричному представлению A возможно за счет свойства неотрицательности получаемых весов признаков. Далее под тематической моделью будем понимать совокупность (L_m, W_k, H_k). Сформированная тематическая модель имеет следующие свойства. Во-первых, столбцы матрицы фрагментов W_k соответствуют выделенным тематикам. Элементы матрицы W_k неотрицательны, поэтому их можно рассматривать как вклад (вес) признаков (n-грамм) в соответствующую тематику, т.е. элементы матрицы W_k задают весовые коэффициенты n-грамм, объединяемых в каждой тематике. Чем больше значение j-го элемента в i-м столбце по сравнению с другими элементами столбца (i-й тематике), тем более характерна  j-я n-грамма для данной тематики. Следовательно, выделенные тематики можно описывать n-граммами, имеющими наибольший вес. Аналогично, элементы матрицы фрагментов (H_k) неотрицательны, поэтому их можно рассматривать как вклад (вес) тематик в соответствующий фрагмент. Чем больше значение j-го элемента в i-м столбце по сравнению с другими элементами столбца (представление i-го фрагмента в пространстве тематик), тем сильнее фрагмент относится к  j-й тематике.

Следует отметить, что описанная матричная модель представления документа является достаточно общим подходом, конкретный вид представления определяется схемой нормализации и кодирования глобальных и локальных весов. В рамках настоящего исследования были проверены разные схемы и для задачи аннотирования и поиска ключевых слов. В результате наилучшие результаты показала схема с бинарным локальным весом (есть или нет такая n-грамма в тексте) и глобальным весом на основе энтропии [22]:

где ${{t}_{{i,j}}}$ – число вхождений i-й n-граммы в  j-й фрагмент. Нормализация для поиска ключевых слов и аннотирования не используется N_j = 1 [22–24]. В задаче расчета меры сходства при ранжировании выдачи используется схема с логарифмическим локальным весом: и глобальным весом на основе IDF: где N число фрагментов в тексте, а n_i – число фрагментов, содержащих i-ю n-грамму. При этом используется косинусная нормализация:

3.3. Выделение ключевых слов

В предложенном подходе каждую найденную тематику можно описать набором ключевых n-грамм, поэтому ключевым признакам будут соответствовать не слова текста на исходном языке, а n-граммы. Очевидно, что набор ключевых n-грамм текста является неприменимым и с точки зрения понимания человеком, и с точки зрения формирования из них поискового запроса. Поэтому необходимо от n-грамм перейти к ключевым словам. Для выделения ключевых слов текста по его сформированной тематической модели (т.е. по совокупности матриц W_k и H_k) было предложено каждое слово z анализируемого документа сначала представить в виде вектора в пространстве n-грамм данного документа: z = [z_1,i, z_2,i, …, z_m,i]^T.  Таким образом, множество слов текста представляется также в виде матрицы Z, строки которой соответствуют n‑граммам, а столбцы – словам. Затем матрица Z отображается в сформированное пространство тематик путем ее умножения слева на транспонированную матрицу W_k. Результатом данного перемножения будет матрица $C = W_{k}^{T} \cdot Z$, которая соответствует представлению множества слов документа в пространстве тематик данного документа, задаваемом матрицей W_k. Тогда для формирования набора ключевых слов последовательно для каждой строки (тематики) матрицы С выбираются p слов с индексами, соответствующими максимальным значениям нормы этих элементов в рассматриваемой строке (в работе в качестве нормы вектора использовался поэлементный максимум). При этом возникает ряд проблем. (1) Длинные слова получают больший вес, так как имеют больше непустых n-грамм. (2) Разные словоформы одного и того же слова отбираются как кандидаты на ключевое слово, поскольку подход языково-независимый, и все они имеют близкий вес. (3) Зачастую, несмотря на ортогональность тематик (за счет ОНМФ), одни и те же слова оказываются кандидатами для разных тематик. Это происходит вследствие того, что, хотя ключевые n-граммы не пересекаются по темам, но могут входить в одни и те же слова. Для решения первой проблемы в работе были исследованы разные схемы нормировки с учетом длины слова и весов тематик. И был выбран простой вариант нормировки на длину слова в символах, таким образом среди различных словоформ одного и того же слова приоритет получали наиболее короткие. Для решения второй проблемы применяется языково-независимый метод кластеризации слов на основе алгоритма DSCAN [29] с использованием строчного расстояния Левенштейна [30] между словами, который позволяет находить одну, наиболее общую словоформу (наиболее близкую всему кластеру схожих слов). Для решения третьей проблемы применен подход, основанный на расчете для каждого кандидата на роль ключевого слова относительного веса, т.е. веса слова K в тематике j (максимальный среди всех тематик), деленного на вес слова K в тематике i (второй после максимального, наибольший вес по тематикам). В результате отбираются слова-кандидаты с наибольшим таким отношением, т.е. наиболее характерные только для одной тематики.

3.4. Фильтрация шума и автоматическое аннотирование

Другая важная задача связана с удалением информационного шума из документа. Она заключается в оценке значимости (релевантности) отдельных фрагментов текста и последующего удаления из результирующего документа наименее значимых фрагментов. При этом оставляемые фрагменты должны описывать все главные темы исходного текста. Рассматриваемая задача тесно связана с задачей автоматического аннотирования, для решения которой необходимо сформировать аннотацию, состоящую из наиболее значимых фрагментов текста. На сегодняшний день наиболее популярные методы автоматического аннотирования, которые вычисляют релевантность фрагментов текста, основаны на тематическом моделировании текстов с использованием латентно-семантического анализа, примененного к коллекции отдельных фрагментов (например, предложений) анализируемого документа [27, 28]. В текущей работе используется ранее предложенный авторами метод вычисления релевантности фрагментов текста, основанный на оценке весов тематик в нормализированном пространстве тематик, получаемом с помощью неотрицательной матричной факторизации [27]. Первый этап предложенного метода состоит в нормировке пространства тематик, т.е. в приведении длин вектор-столбцов матрицы W_k к единице. Этот шаг обусловлен тем, что неотрицательная матричная факторизация дает не единственное решение [11]. Второй этап заключается в оценке глобальных весов полученных тематик во всем документе. Каждая из строк матрицы H_k соответствует вектору, показывающему, насколько сильно представлена соответствующая тематика в каждом из фрагментов. Следовательно, чем больше длина вектор-строки матрицы H_k, тем соответствующая тематика больше представлена во всем документе. Поэтому предложено оценивать глобальный вес выделенных тематик как норму соответствующих вектор-строк матрицы H_k. На основе полученных оценок глобальных весов тематик документа релевантность j-го фрагмента текста ${{R}_{j}}\quad$ вычисляется как норма вектора, являющегося результатом поэлементного умножения вектора глобальных весов тематик и вектора весов тематик в рассматриваемом фрагменте (т.е. соответствующего вектор-столбца матрицы H_k), где k – число тематик:

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

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

3.5. Вычисление релевантности документов выдачи тематикам документа-образца

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

1. Представление найденного документа в виде матрицы B размерности число фрагментов на число n-грамм.

2. Проецирование матрицы найденного документа B в пространство тематик документа-образца. Для этого матрицу B умножают слева на транспонированную матрицу W_k. Результатом данного перемножения будет матрица $C = W_{k}^{T} \cdot B$, которая соответствует представлению найденного документа в пространстве тематик документа-образца, задаваемом матрицей W_k. Следует отметить, что ортонормированность разложения как раз необходима, чтобы получить возможность выполнить эту операцию – проекцию произвольного документа в пространство тематик документа-образца.

3. Расчет релевантности нового документа как нормы (в данной работе использовалась норма Фробениуса) матрицы C: чем больше ${\text{||}}C{\text{|}}{{{\text{|}}}_{F}}$, тем сильнее документ выдачи соответствует тематикам документа-образца.

Для проверки предложенного подхода было проведено экспериментальное исследование на подготовленном тестовом наборе данных, состоящем из сообщений из набора данных джихадистского форума Ansar1 в качестве “плохих” примеров и данных из тематик набора 20 Newsgroups [41] на политические и религиозные темы (talk.politics. misc, talk.politics.guns, talk.politics.mideast, talk.religion.misc, alt.atheism, soc.religion.christian) в качестве нейтральных примеров. С применением описанных выше методов поиска по образцу были получены высокие оценки точности распознавания, а именно, средняя точность (average precision) на уровне 0.95 и выше [22].

4.1. Представление тематик потока текстовых сообщений в виде многомерного временного ряда

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

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

Формально поток текстовых сообщений представляется множеством пар x = {(d₁, t₁), …, (d_n, t_n)}, где каждый элемент (d_j, t_j) – анализируемый объект (1 ≤ j ≤ n), где d_j – документ, содержащий текстовые данные, t_j – временная метка. Для формирования тематической модели по потоку его текстовые данные описываются набором признаков, изменения значений которых определяет изменение набора обсуждаемых тем с течением времени. Коллекция документов (d₁, …, d_n) представляется в виде числовой матрицы D ∈ ${{\mathbb{R}}^{{m \times n}}}$, строки которой соответствуют признакам (n-граммам), а столбцы – документам. Тогда матрица D задает модель поведения потока сообщений в виде m-мерного временного ряда, показывающего изменение весов соответствующих признаков в потоке сообщений. Пространство признаков при использовании модели n-грамм имеет высокую размерность, которая равна числу различных n-грамм во всей коллекции. Кроме того, в таких признаках игнорируются семантические взаимосвязи между n-граммами, а матрица D содержит большое число строк и является разреженной. Последнее приводит к бессмысленности применения методов прогнозирования временных рядов для строк матрицы D. Использование тематических моделей представления документов позволяет уменьшить пространство признаков за счет объединения разных, но семантически связанных n-грамм в один признак – тематику. Полученная таким образом тематическая модель, сформированная по потоку текстовых документов {(d₁, t₁), …, (d_n, t_n)}, представляет собой совокупность (L_m, W_k, H_k, T_n), где (L_m, W_k, H_k) – тематическая модель коллекции документов (d₁, …, d_n), T_n = (t₁, …, t_n) – временные метки документов. Столбец H_j (1 ≤ j ≤ n) матрицы H_k соответствует тематической направленности в момент времени t_j. Требование ортонормированности W_k является необходимым, так как тематическая модель потока сообщений может применяться для анализа дальнейшей активности в потоке y = {(d_new, t_new)}, где d_new – новое сообщение, а t_new > t_n. Поэтому необходимо иметь возможность представлять новые документы d_new в уже сформированном тематическом пространстве (L_m, W_k): ${{H}_{{new}}} = W_{k}^{T} \cdot {{A}_{{new}}}$, где A_new – вектор представления d_new со словарем n-грамм L_m.

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

4.2. Применение методов анализа временных рядов для прогнозирования поведения тематик потока сообщений и поиска исключений

Как показали экспериментальные исследования на эталонных наборах данных DarkWeb и на реальных собранных данных, использование для поиска корреляций, автокорреляций и прогнозирования тематических временных рядов, получаемых напрямую с помощью методов латентно-семантического анализа, затруднительно, поскольку такие ряды оказываются зашумленными, нестационарными, с “пропущенными” периодами (когда обсуждение темы в сообществе временно полностью прекращается, а потом возобновляется). Поэтому было принято решение анализировать сглаженные тематические ряды. Были рассмотрены методы экспоненциального сглаживания, регуляризированные сплайны и непараметрическая взвешенная локальная регрессия (loess). Последняя показала наилучшие результаты при выборе параметра регуляризации для loess по скорректированному информационному критерию Акаика (AICC) [31]. Для поиска коррелирующих тематик были реализованы алгоритмы расчета близости сглаженных тематических временных рядов на основе евклидового расстояния и расстояния на основе динамического выравнивания временной шкалы DTW (dynamic time wrapping) [32]. Последнее позволяет находить похожие по поведению во времени тематики с учетом “сжатия и растяжения” соответствующих временных рядов, оно показало наиболее интересные результаты на практике.

Были протестированы алгоритмы прогнозирования изменения тематик в сообществе на основе прогнозирования сглаженного многомерного временного ряда соответствующих тематик с помощью линейной ARIMA [33]. Экспериментальное исследование на наборе данных DarkWeb показало достаточно высокую точность прогнозирования на маленький горизонт (несколько дней), но плохую точность на длительные периоды. Это, возможно, связано с тем, что в эксперименте не было данных для длительного периода, а также с тем, что, судя по всему, тематики в потоке текстовых сообщений существуют не очень долго и достаточно быстро полностью меняются.

Были разработаны два новых алгоритма обнаружения аномального содержания в потоке сообщений, использующие предложенное тематическое представление потока текстовых документов. В первом алгоритме рассматривается пользовательский поток документов x = {(d, t)}, где документ d представляет собой объединенные текстовые данные пользователя, к которым он обращался за время [t, t + t₀), при этом t₀ выбирается достаточно “длительным”. По потоку x строится тематическая модель поведения пользователя (L_m, W_k, H_k, T_n). Тогда поток x можно представить в виде множества упорядоченных пар F = ((H₁, t₁), …, (H_n, t_n)), где t₁ < t₂ < … < t_n. Выборка F рассматривается как k-мерный временной ряд, по которому строится прогноз (в работе использовалась линейная ARIMA) на следующие p шагов: (($H_{{n + 1}}^{f}$, t_{n + 1}), …, ($H_{{n + p}}^{f}$, t_{n + p})). После чего определяется решающая функция:

где h – представление документа d в (L_m, W_k), a_j – уровень аномальности контента d за время [t_{n + j}, t_{n + j + t0}). Здесь уровень аномальности соответствует отклонению тематической направленности от ожидаемых значений, поэтому чем меньше значение a_j, тем менее аномально содержание сообщений пользователя. Во втором подходе к обнаружению аномального содержания сообщений пользователя используется оценка принадлежности отдельных документов к характерным тематикам анализируемого потока. Рассматривается поток x = {(d, t)}, где документ d соответствует тексту, который сгенерировал или прочитал пользователь в момент времени t. По потоку x строится тематическая модель (L_m, W_k, H_k, T_n). Вычислять оценку степени принадлежности произвольного документа d' к тематикам пользователя предложено как норму вектора h', являющегося представлением документа d' в (L_m, W_k), т.е. с помощью решающей функции при этом чем сильнее документ d' соответствует характерным тематикам анализируемого потока, тем меньше значение нормы и, значит, менее аномально сообщение d' данного пользователя.

4.3. Экспериментальное исследование предложенного подхода

Для демонстрации предложенного подхода рассмотрим следующий сценарий. В качестве документа-образца была взята статья от 22 февраля 2017 года с запрещенного экстремистского сайта kavkazcenter.com под название “Дорогой друг Эрдогана помог Асадитам войти в Африн”, где критикуются действия РФ в Сирии и выражается поддержка террористам, противостоящим этим действиям. По этой статье с помощью методов из раздела 3 были выявлены следующие ключевые слова: асадитам, курдские, асаду, турецких, эрдогана, русские, вошли, африн, войск, коммунистов, курдам, спину, заявил. Очевидно, что они не являются специфической экстремистской лексикой и по ним можно найти много легитимной информации. На основе этих слов был сформирован поисковый запрос в сеть “Вконтакте” (vk.com), а полученная выдача была обогащена и ранжирована с помощью методов раздела 3. В результате в числе наиболее релевантных оказались сообщения ряда подозрительных пользователей с именами: natisc_na_ivanov, islamword1071, club68716929. Визуальный анализ их страниц в vk подтвердил предположения, что они распространяют экстремистскую информацию, в том числе разжигают рознь по национальному и религиозному признаку. В рамках мониторинга из этих аккаунтов vk были выкачены сообщения за период с 1 ноября 2017 по 22 февраля 2018, к ним были применены методы тематического анализа и построения соответствующих временных рядов с тремя тематиками и прогнозом, описанными в предыдущем разделе. Результат приведен на рис. 5.

На рис. 5 цветом показано поведение и прогноз трех выявленных тематик, обсуждаемых этими пользователями. Прерывистые линии – веса тематик во времени, сплошные линии – сглаженные (по loess) значения тематик. Список ключевых слов первой (синей в цветном варианте рисунка) тематики содержит слово “Сирия”, второй (коричневой в цветном варианте рисунка) содержит слово “Украина” и третьей (зеленой в цветном варианте рисунка) слово “США”. При этом, согласно прогнозу, интенсивность обсуждения Сирии далее будет также возрастать, для обсуждения Украины ожидается плавный рост, обсуждение США останется на том же уровне.

Если применить алгоритм поиска исключений, описанный в разделе 4.2, то самым нетипичным окажется документ из зеленой тематики (про США), где просто перепечатана статья с выступлением президента США Трампа про обращение к Северной Корее. И действительно, с точки зрения остального потока сообщений, где преобладает антироссийская пропаганда, указанная обычная новостная статья действительно выглядит исключением.

5.1. Подготовка тестового набора данных

Стоит отдельно отметить, что качественных эталонных наборов данных (чатов/форумов/социальных сетей с размеченными с точки зрения опасности пользователями) для проверки предлагаемых для решения этой задачи алгоритмов найдено не было. Из используемых наборов данных в открытом доступе есть данные с соревнований Kaggle [42, 43], в которых отсутствует информация о связях пользователей, а разметка пользователей осуществляется очень неточно, по “экстремистским” хэштегам и ключевым словам. В силу указанных особенностей такие наборы не применимы для экспериментальной оценки моделей прогнозирования опасности пользователя в текущей постановке задачи. Поэтому в настоящей работе для выявления радикальных пользователей и построения связей между пользователями использовался набор данных, самостоятельно сформированный на основе набора KavkazChat. Подготовка набора данных делится на следующие этапы: разметка пользователей и создание графа. В первой части применяется простой интерактивный способ обнаружения пользователей, чьи сообщения содержат опасный контент, что позволяет поставить метку “опасный”/”неопасный” пользователям социальной сети, основываясь на генерируемом ими контенте. Но при этом далее в экспериментах по классификации пользователей с неизвестной меткой контент не используется. Таким образом, для части пользователей будет ставиться метка “неизвестно”, и алгоритм классификации должен будет ее спрогнозировать уже без использования контента. Для оценки точности будем сравнивать метку, спрогнозированную по графовым признакам, с исходной меткой, полученной на основе анализа контента. Разметка пользователей на “опасный”/“неопасный” производилась с использованием языково-независимой модели представления текстовых сообщений на основе n-грамм, так как анализ именно символьных последовательностей хорошо зарекомендовал себя в вышеописанных задачах тематического моделирования. Для получения менее разряженных векторов признаков меньшей размерности при разметке использовался подход из области латентно-семантического анализа, но на основе нейронных сетей, а не ОНМФ. Был создан нейросетевой автоэнкодер (autoencoder) [40], у которого все веса – неотрицательные, нулевые смещения и ReLU-активации на каждом слое. Число нейронов на каждом слое было следующим N, 500, 100, 10, где N – размерность входного вектора представления текстов через n-граммы. Для настройки весов использовался алгоритм Adam [40] и среднеквадратичная ошибка (MSE) в качестве функции потерь.

Далее был сформирован набор текстов из всех сообщений форума KavkazChat с помощью простого поиска по ключевым словам – сообщения, содержащие слова “джихад”, “призываю”, “война”, “кафир”, “моджахед” и ряд других. Таких было найдено 248. Среди них вручную было отобрано первые 10 сообщений, гарантировано экстремистского содержания. После чего использовался Алгоритм 1. На каждой из его итераций анализировались 100 наиболее релевантных текстов, и в результате его работы менее чем за 6 итераций стало возможным определение 171 сообщения с радикальным содержанием, а также 135 пользователей (1.8% всех пользователей форума), генерирующих соответствующий контент. На каждой итерации случайно выбирались неразмеченные сообщения из всего корпуса таким образом, чтобы пропорция выделенных опасных к неразмеченным составляла 5 к 95. Затем полученный набор данных делился на 5 стратифицированных частей (5-fold cross-validation), и оптимизировались параметры метода опорных векторов с RBF ядром. Константа регуляризации, ширина ядра и другие параметры отбирались с помощью кросс-валидации выборки, максимизируя среднее значение меры F1-меры (гармоническое среднее между точностью и полнотой). После этого обучался классификатор на всем наборе данных (с пропорцией отклика 5%), с использованием набора найденных кросс-валидацией лучших гиперпараметров, а применялся обученный классификатор для разметки всего множества сообщений набора KavkazChat. В качестве признаков использовались выходы среднего слоя автоэнкодера (аналог весов скрытых тематик) для каждого текста. Далее сообщения ранжировались по убыванию соответствия классу с “радикальными” текстами, и вручную выбирались среди ста наиболее потенциально радикальных только те, которые содержали опасный контент, за исключением сообщений пользователей, которые уже были помечены как “опасные” (сгенерировали хотя бы одно сообщение, которое уже было помечено как радикальное). Из отсортированного списка сообщений выбирались первые 100, которые размечались вручную, после чего добавлялись во множество опасных сообщений для дообучения, и описанная выше процедура переходила на следующую итерацию. В итоге было получено множество опасных пользователей – тех, кто сгенерировал хотя бы одно сообщение с радикальным содержанием.

Алгоритм 1. Выделение радикальных пользователей

Вход:

• M_D: множество опасных сообщений;

• M_ALL: все сообщения;

• USERS: множество пользователей;

• M_I: множество сообщений пользователя I;

• N: количество итераций;

• K: количество сообщений для ручной разметки на каждой итерации;

Выход:

• M_D: обновленное множество опасных сообщений.

1: Для всех i от 1 до N

2: M_R = | M_R | произвольных сообщений из M_ALL, где |M_R|/|M_D|=95/5

3: Найти классификатор с оптимальным набором параметров с помощью, стратифицированной кросс-валидации на M_R + M_D

4: Обучить классификатор на наборе данных M_R + M_D

5: M_E = {} – множество сообщений для исключения из процесса ручной разметки

Для всех USER из USERS:

Если пересечение (M_USER, M_D) != {}

    То добавить M_USER к M_E

6: M_A = M_{ALL –} M_E – множество сообщений для анализа

7: P = предсказать M_A с помощью классификатора и извлечь топ K релевантных текстов (ближайших к классу “радикальный”)

8: Вручную разметить P, после чего добавить релевантные сообщения в множество M_D

9: Вернуть M_D

Для того чтобы сформировать сетевую структуру социальной сети и представить ее в виде графа был использован Алгоритм 2. В этом алгоритме сначала инициализируется полносвязный ориентированный граф со всеми пользователями в качестве вершин и нулевыми весами ребер. Если пользователь A имел некоторую активность “в направлении” пользователя B (поставил лайк, сделал репост записи, написал сообщение и т.д.), то вес ребра, исходящего из вершины A в вершину B, увеличивается на единицу. Все ребра с нулевыми весами удаляются, а ненулевой вес ребра инвертируется. Это означает, что если пользователь A имел x “активностей” в сторону B, то вес соответствующего ребра из A в B считается равным 1/x. Таким образом вычисленный вес ребра может быть использован в качестве меры “расстояния” между пользователями – чем “больше” активность, тем “ближе” пользователи. Такой подход оказался более эффективным при вычислении кратчайших путей между вершинами графа, подсчет пути без учета весов дуг. В экспериментальном исследовании также использовались графы с бинарными весами, в которых ненулевые веса заменялись на единицы. Для определения активности может быть использован большой набор взаимодействий: добавление в “друзья”, “репосты”, “лайки”, просмотры страницы, число общих групп, количество входящих/исходящих сообщений, ответы в ветке форума и т.д. Кроме того, необходимо учитывать, что связи могут быть двунаправленными, а также для одной социальной сети можно построить несколько графов (свой для каждого типа активности).

Алгоритм 2. Создание графа социальной сети

Вход:

• USERS – множество пользователей социальной сети;

• W_ij – матрица, элементы которой – число “активностей” от пользователя i к j;

Выход:

• G: граф пользовательских связей;

1: G = полносвязный ориентированный граф с нулевыми весами

2: Для всех вершин i из USERS

3:  Для всех j из USERS/{i}

4:     если W_ij != 0

5:      то установить вес 1/W_ij ребру из i в j в графе G

6: Удалить ребра с нулевыми весами в G

7: Вернуть G

В ходе экспериментов было обнаружено, что многие признаки, которые рассчитываются с учетом направления ребер в графе, лучше отражают связь между пользователями, если это направление поменять на обратное. По построению графа связь из A в B имеет семантику “A что-то сделал с контентом В”. Обратная связь имеет семантику “В заинтересовал А”, и как раз на таких обратных связях экспериментальный результат оказался лучше.

Для набора данных KavkazChat были построены следующие графы пользовательских связей, по которым вычислялись признаки:

• ориентированный граф со связями только по репостам сообщений без весов у связей;

• ориентированный граф со связями только по репостам сообщений с весами у связей, обратно пропорциональными интенсивности (числу действий);

• ориентированный граф со связями только по ответам в ветке без весов у связей;

• ориентированный граф со связями только по ответам в ветке с весами у связей, обратно пропорциональными интенсивности (числу действий);

• ориентированный граф с обратными связями только по репостам сообщений без весов у связей;

• ориентированный граф с обратными связями только по репостам сообщений с весами у связей, обратно пропорциональными интенсивности (числу действий);

• ориентированный граф с обратными связями только по ответам в ветке без весов у связей;

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

5.2. Построение пространства признаков

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

• “важность” узла по PageRank [35];

• “уровень авторитета” и “уровень посредника” (hub) по HITS (Hyperlink Induced Topic Search) [36];

• betweenness centrality [37] – доля кратчайших путей между любыми двумя вершинами, которые включают в себя данную вершину;

• proximity prestige [37] – нормализованное среднее расстояние от текущей вершины до всех достигаемых вершин;

• sociability [37] – число входящих в вершину ребер, деленное на число всех ребер, связанных с данной вершиной;

• три бинарных признака – наличие в ближайшем окружении хотя бы одного “опасного”/“неопасного”/“неизвестного” узла;

• три числовых признака – число “опасных”, число “неопасных” и число “неизвестных” ближайших соседей;

• шесть числовых признаков – минимальное расстояние с учетом весов ребер и без до ближайшего “опасного”/“неопасного”/“неизвестного” узла;

• три числовых признака – доля “опасных”/“неопасных”/“неизвестных” узлов среди всех ближайших соседей.

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

5.3. Экспериментальное исследование

Для эталонного набора данных с разметкой пользователей, описанной в разделе 5.1, и с признаковым пространством, описанным в разделе 5.2, была проведена следующая серия экспериментов. В каждом эксперименте из исходного набора формировался тренировочный и тестовой в пропорции 70 к 30. На каждом таком наборе обучались следующие классификаторы: логистическая регрессия с L2 регуляризацией, дерево решений типа CART [44], случайный лес [45], ансамбли деревьев решений на основе градиентного бустинга XGBoost [38] и LightGBM [39]. При обучении подбирались оптимальные параметры каждого из алгоритмов с помощью стратифицированной кросс-валидации на тренировочном наборе. Для логистической регрессии и градиентных бустингов подбирался оптимальный параметр L2-регуляризации признаков на сетке возможных параметров. Для алгоритмов на основе деревьев решений выбирались максимальная глубина деревьев, минимальное число листьев в вершине каждого дерева, для ансамблей – оптимальный размер ансамбля. Для того чтобы избежать перебора всевозможных комбинаций параметров и эффективно выбирать очередную точку в пространстве гиперпараметров использовался подход последовательной оптимизации SMBO (Sequential Model-Based Optimization) [46].

Для сравнения моделей использовалась площадь под ROC кривой – AUC. По результатам серии экспериментов оценивалось среднее значение и разброс AUC.

Как видно из приведенных в таблице 1 результатов ни одна из моделей не получилась переобученной, и наилучшее качество показали современные бустинг ансамбли с регуляризацией. Отдельно была проведена проверка предположения о том, возможно ли классифицировать пользователей потенциально террористического или экстремистского сообщества, если вообще нет информации об “опасных” соседях, исходя только из признаков, рассчитанных без учета метки класса узлов-соседей. Это значит, что при расчете признаков по методу, изложенному в разделе 5.2, считалось, что у всех узлов класс – “неизвестный пользователь”. Результаты (представлены в таблице 2) получились неожиданно удачными и в общем близкими к результатам на всем признаковом пространстве.

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

Для того чтобы выявить влияние отдельных признаков на результат (оценить важности каждого из предикторов), была построена описательная модель на основе регуляризированной логистической регрессии. Для этого выделены наиболее важные переменные с точки зрения их абсолютных весов в регрессионной модели, изменения которых значимо влияют на шанс принадлежности к классу “опасных” пользователей (Таблица 3).

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

Если же использовать только информацию о центральностях пользователей и считать всех пользователей в анализируемом сообществе “неизвестными”, то окажется, что наиболее важными будут уровень посредника (Hub) в графе прямых связей по ответам в общих ветках, а также Proximity Prestige значения во всех графах прямых связей. Это можно упрощенно проинтерпретировать как то, что чем больше связей у члена в целом подозрительного сообщества, тем более вероятно, что он играет в нем ключевую роль и является “опасным”.