=Paper=
{{Paper
|id=Vol-2022/paper56
|storemode=property
|title=
Метод прогнозирования развития ситуаций на основе обнаружения событий в потоке текстовых документов
(Method for Forecasting of Situations Development Based on Event Detection in Text Stream)
|pdfUrl=https://ceur-ws.org/Vol-2022/paper56.pdf
|volume=Vol-2022
|authors=Ark Andreev,Dmitry Berezkin,Ilya Kozlov
|dblpUrl=https://dblp.org/rec/conf/rcdl/AndreevBK17a
}}
==
Метод прогнозирования развития ситуаций на основе обнаружения событий в потоке текстовых документов
(Method for Forecasting of Situations Development Based on Event Detection in Text Stream)
==
https://ceur-ws.org/Vol-2022/paper56.pdf
Метод прогнозирования развития ситуаций на
основе обнаружения событий в потоке текстовых
документов
© А.М. Андреев © Д.В. Березкин © И.А. Козлов
Московский государственный технический университет им. Н. Э. Баумана,
Москва
arkandreev@gmail.com berezkind@bmstu.ru kozlovilya89@gmail.com
Аннотация. Рассмотрен метод автоматизированного прогнозирования развития ситуаций на
основе обнаружения событий в потоке текстовых документов. Описаны существующие подходы к
анализу ситуаций, выявлены их преимущества и недостатки с точки зрения специфики решаемой
задачи. Предложен метод формирования сценариев развития ситуаций на основе принципа
исторической аналогии, учитывающий динамику развития ситуаций. Этот метод позволяет оценивать
вероятность реализации сформированных сценариев с помощью логистической регрессии.
Представлен метод выделения оптимистического и пессимистического сценариев на основе метода
анализа иерархий. Описан способ снабжения сценариев предложениями для лиц, принимающих
решения. Представлены результаты экспериментальной оценки качества разработанного метода.
Ключевые слова: ситуационный анализ, прогнозирование, сценарный анализ, система
поддержки принятия решений, аналогия, анализ текстового потока.
Method for Forecasting of Situations Development
Based on Event Detection in Text Stream
© Ark Andreev © Dmitry Berezkin © Ilya Kozlov
Bauman Moscow State Technical University,
Moscow
arkandreev@gmail.com berezkind@bmstu.ru kozlovilya89@gmail.com
Abstract. The article deals with the problem of automated forecasting of situations development based
on event detection in a stream of text documents. Existing methods of situational analysis are analyzed and
their advantages and disadvantages in view of the specifics of the task are determined. A method for
generation of possible scenarios of situations development is described. The method generates scenarios on
the principle of historical analogy, taking into account the dynamics of situation development. The probability
of the generated scenarios' implementation is estimated via logistic regression. A method for the optimistic
and the pessimistic scenario identification based on analytic hierarchy process is proposed. A way to
supplement scenarios with recommendations for decision-makers is described. The results of experimental
evaluation of the developed method's quality are presented.
Keywords: situational analysis, forecasting, scenario analysis, decision support system, analogy, text
stream analysis.
1 Введение частности, в форме текста. Так, форму текстовых
потоков имеют сообщения пользователей в
В настоящий момент большое количество социальных сетях, новости СМИ, официальные
данных, обрабатываемых современными заявления органов власти.
информационными системами (ИС), имеет форму Динамический характер текстовых потоков
информационных потоков: новые информационные делает их важным средством информационной
сообщения постоянно поступают из источников и поддержки для людей, которым требуется принимать
должны обрабатываться ИС с минимальной управленческие решения в режиме реального
задержкой. Как правило, информация в потоке времени в условиях меняющейся обстановки. Задачи
представлена в неструктурированном виде, в своевременного обнаружения проблемной ситуации,
отслеживания её развития и оперативного принятия
Труды XIX Международной конференции решений по управлению развитием ситуации
«Аналитика и управление данными в областях с возникают в различных сферах – политической,
интенсивным использованием данных» социальной, военной, экономической.
(DAMDID/ RCDL’2017), Москва, Россия, 10–13
октября 2017 года
367
Анализ текстового потока позволяет течением времени необходимо формировать
осуществлять мониторинг интересующих ситуации – цепочки взаимосвязанных событий,
пользователей тем, т. е. обнаруживать отражающие развитие тех или иных процессов. Для
возникновение важных событий, относящихся к тем этого из множества обнаруженных событий
или иным явлениям или объектам [5]. выделяют пары взаимосвязанных событий 𝑝𝑖𝑗 =
Обнаруживаемые события отражают развитие (𝜀𝑖 , 𝜀𝑗 ), потенциально принадлежащих одной
различных ситуаций с течением времени. Однако для ситуации. На основе формирования таких пар
принятия наилучших решений необходимо также выполняется построение ситуационного графа 𝐺 =
определять возможные варианты дальнейшего (𝐸, 𝑃). В этом графе узлы 𝐸 = {𝜀𝑖 } соответствуют
развития этих ситуаций – это позволяет на основе событиям, а ребра 𝑃 = {𝑝𝑖𝑗 } – выделенным парам
полученного прогноза предпринимать определенные (каждое ребро является ориентированным и
шаги, направленные на изменение ситуации в направлено к более позднему событию пары). Любой
нужную сторону. путь в этом графе является потенциальной ситуацией
В статье предложено решение задачи 𝑠 = (𝜀𝑠1 , 𝜀𝑠2 , … , 𝜀𝑠𝑛 ).
автоматизированного прогнозирования развития
На Рис. 1 представлен пример ситуации,
ситуаций на основе анализа потока текстовых
представляющей собой последовательность из
сообщений. четырех взаимосвязанных событий.
2 Постановка задачи 2.2 Особенности решаемой задачи
2.1 Функционирование системы мониторинга Прогнозирование заключается в построении
развития ситуаций возможных сценариев развития ситуации. Каждый
В [5] предложено решение задачи мониторинга сценарий представляет собой потенциальное
продолжение текущей ситуации, т. е. цепочку
тем на основе обнаружения событий, релевантных
событий, которые могут наступить в будущем. Для
заданным темам, в потоке текстовых документов.
эффективного использования результатов
Под событием понимается некоторое изменение, прогнозирования из множества сформированных
произошедшее в реальном мире и отраженное в сценариев необходимо выделить три варианта,
текстовом потоке. Обнаружение событий представляющих наибольший интерес для лиц,
рассматривается как задача кластеризации, принимающих решения (ЛПР), – пессимистический,
заключающаяся в разбиении текстового потока на оптимистический и наиболее вероятный. На основе
группы документов, описывающих различные результатов прогнозирования должны приниматься
события. Для этого каждый документ представляется решения по управлению ситуацией. Поэтому помимо
многокомпонентной моделью, компоненты которой сформированных сценариев пользователю должны
описывают содержание, структуру и метаданные предлагаться предложения по действиям, которые
𝑝 𝑔
документа: 𝑑𝑖 = (𝑑𝑖𝑤 , 𝑑𝑖𝑡𝑤 , 𝑑𝑖𝑐 , 𝑑𝑖 , 𝑑𝑖𝑛 , 𝑑𝑖𝑑𝑡 , 𝑑𝑖𝑒 , 𝑑𝑖 , 𝑑𝑖𝑡 ). необходимо предпринять для способствования
В частности, текстовое содержание документа развитию ситуации по наиболее благоприятному
представлено вектором 𝑑𝑖𝑤 = (𝑤𝑖1 , 𝑤𝑖2 , … , 𝑤𝑖𝑁 ),
𝑤 сценарию.
каждый элемент которого 𝑤𝑖𝑘 отражает значимость k- 3 Обзор существующих подходов к
го терма в контексте документа и рассчитывается с анализу ситуаций
помощью метода TF-IDF. Каждое событие также
описано многокритериальной моделью, компоненты В некоторых работах, посвященных
которой формируются на основе документов, ситуационному анализу, ситуации описываются
относящихся к событию: 𝜀𝑗 = совокупностями определенных числовых
𝑝 𝑔
(𝜀𝑗𝑤 , 𝜀𝑗𝑡𝑤 , 𝜀𝑗𝑐 , 𝜀𝑗 , 𝜀𝑗𝑛 , 𝜀𝑗𝑑𝑡 , 𝜀𝑗𝑒 , 𝜀𝑗 , 𝜀𝑗𝑡 ). Объединение показателей [13]. Для прогнозирования в этом случае
могут использоваться методы анализа временных
документов в группы выполняется с помощью рядов и методы регрессионного анализа. Такие
алгоритма инкрементальной кластеризации, в основе подходы не могут быть использованы для анализа
которого лежит покомпонентное сопоставление развития ситуаций на основе текстового потока,
каждого документа с ранее обнаруженными поскольку требуемый результат прогнозирования
событиями. Более подробно модели документа и имеет качественный, а не количественный характер.
события, а также метод обнаружения событий В ряде работ предложены подходы к
описаны в [5]. формированию сценариев на основе когнитивных
Метод позволяет работать с документами на карт и знаковых орграфов [14, 16]. В них ситуация
произвольном языке при наличии подготовленных представляется как граф, узлы которого
экспертами тематических запросов, а также словарей соответствуют факторам ситуации, а ребра отражают
имен персон, названий организаций и влияние факторов друг на друга. Прогнозирование
географических наименований на соответствующем заключается в оценке будущих значений факторов
языке. Для повышения качества обнаружения путем моделирования изменения ситуации с учетом
событий могут быть использованы наработки различных управляющих воздействий. Построение
авторов в области морфологического [6], описания ситуации в виде когнитивной карты
синтаксического [4] и семантического [7] анализа выполняется экспертом, поэтому такие подходы
текстов. Для отслеживания изменения обстановки с неприменимы для автоматического формирования
сценариев развития ситуаций.
368
Рисунок 1 Пример выявления событий и формирования ситуации
Многие работы используют принцип аналогии – эталону – в ней могут содержаться дополнительные
прогнозирование дальнейшего развития ситуации и события или, напротив, отсутствовать какие-либо
формирование предложений по управляющим события из графа.
действиям основано на поиске аналогичных Подход на основе нестрогой аналогии предложен
ситуаций, имевших место в прошлом. В работах, в [8]. Ситуации представляются цепочками событий,
базирующихся на принципе аналогии, используются близость между ними определяется с помощью
различные подходы к представлению ситуаций. модифицированного расстояния Левенштейна. Но
В [10] ситуация представляется фрагментом этот подход требует выделения для каждого события
семантической сети, содержащим объекты и их объекта и субъекта, что не может быть сделано
отношения в рамках ситуации. Получить такое автоматически для произвольных текстовых
представление автоматически возможно лишь для сообщений. Кроме того, результат определения
определенных предметных областей, поэтому такой аналогов текущей ситуации в названной работе
подход нельзя использовать для прогнозирования используется лишь для отнесения этой ситуации к
развития произвольных ситуаций. одному из заданных классов.
В ряде работ предложено описание ситуаций в
виде набора или вектора параметров с 4 Предлагаемый метод прогнозирования
определенными значениями [1, 12]. Для сравнения развития ситуаций
ситуаций с целью определения аналогии
Обнаружение для текущей последовательности 𝑠𝑐
используются евклидово расстояние, манхэттенская
цепочки-аналога 𝑠𝑒 позволяет не только определить
метрика, расстояние Чебышева, мера Хэмминга,
вероятный итог развития ситуации (как предлагается
косинусная мера и другие меры близости.
в [8]), но и объяснить, какие события могут привести
Недостаток данных подходов заключается в
к этому итогу. Такой прогноз можно получить, если
статическом описании ситуаций – при определении
обнаружено сходство всей текущей
близости между ситуациями не учитывается
последовательности с начальной частью 𝑠𝑡(𝑠𝑒 , 𝑠𝑐 )
сходство динамики их развития.
цепочки-аналога. В этом случае можно
Для учета динамики можно использовать
предположить, что в будущем наступят события,
описание эталонной ситуации в виде графа или
аналогичные тем, которые составляют
автомата [3, 9, 11, 15, 18], пути в котором отражают
заключительную часть цепочки-аналога 𝑓𝑖𝑛(𝑠𝑒 , 𝑠𝑐 ).
различные варианты развития ситуации. Все эти
Таким образом, эту заключительную часть можно
подходы позволяют применять лишь принцип
рассматривать как возможный сценарий
строгой аналогии: анализируемая текущая ситуация
дальнейшего развития текущей ситуации.
должна точно соответствовать некоторому пути в
Для выполнения сопоставления необходимо
графе, построенном экспертом. Однако цепочка
событий, автоматически построенная при анализе наличие базы ситуаций-эталонов 𝑆𝑒 = {𝑠𝑒𝑖 }. Такие
текстового потока, не всегда точно соответствует эталоны отбираются экспертами в зависимости от
369
задачи, для которой используется система учитываются их названия, текстовые описания и
мониторинга. Так, для анализа ситуации, связанной с тематический состав. Текстовое описание события 𝜀𝑖
𝑤
тестированием беспилотных такси (рис. 1), задается вектором 𝜀𝑖𝑤 = (𝑤𝑖1 , 𝑤𝑖2 , … , 𝑤𝑖𝑁 ), где 𝑁 𝑤 –
использовалась база эталонных ситуаций, количество различных слов, встречающихся в
отражающих развитие различных технологий в описаниях событий, 𝑤𝑖𝑙 – вес -го слова в описании 𝑖-
прошлом. го события, который находится методом TF-IDF.
Поскольку текущие ситуации представляют Для того чтобы наиболее важную роль при
собой пути в ситуационном графе, процесс определении аналогичности играли термы,
прогнозирования состоит из следующих этапов: характерные для конкретного события, а не ситуации
1. При появлении в ситуационном графе в целом, было решено умножать вес каждого терма
нового события 𝜀𝑐 (либо при изменении 𝑤𝑖𝑙 в 𝜀𝑖𝑤 на коэффициент 𝑘𝑖𝑙 , отражающий
существующего события) осуществляется соотношение значимости терма для события и для
поиск аналогичных ему событий, ситуации 𝑠, к которой относится это событие: 𝑘𝑖𝑙 =
принадлежащих эталонным ситуациям.
𝑤𝑖𝑙 𝑙𝑒𝑛(𝑠)⁄∑𝜀𝑗𝜖𝑠 𝑤𝑗𝑙 , где 𝑙𝑒𝑛(𝑠)– количество событий в
2. При нахождении эталонного события 𝜀𝑒 ∈
𝑠𝑒 , аналогичного событию 𝜀𝑐 , выполняется ситуации 𝑠:
попытка выделить в графе цепочку событий 𝑤 𝑤
𝜀𝑖𝑤 ′ = (𝑤𝑖1 𝑘𝑖1 , 𝑤𝑖2 𝑘𝑖2 , … , 𝑤𝑖𝑁 𝑘𝑖𝑁 ).
𝑠𝑐 (текущую ситуацию), которая содержит
событие 𝜀𝑐 и имеет максимальное сходство с Расстояние между событиями с точки зрения
начальной частью 𝑠𝑡(𝑠𝑒 , 𝑠𝑐 ) текста рассчитывается на основе косинусной меры:
последовательности 𝑠𝑒 . Если 𝑠𝑐 является 𝑤
𝛾𝑖,𝑗 = 1 − 𝑠𝑖𝑚cos (𝜀𝑖𝑤 ′ , 𝜀𝑗𝑤 ′). Представление слов
аналогом 𝑠𝑒 , то заключительная часть названия события 𝜀𝑖𝑡𝑤 ′ и расчёт расстояния между
эталонной ситуации 𝑓𝑖𝑛(𝑠𝑒 , 𝑠𝑐 ) признается событиями с точки зрения названий 𝛾𝑖,𝑗 𝑡𝑤
выполняется
возможным сценарием развития текущей аналогично.
ситуации. Тематический состав события характеризует
3. Сценарии, сформированные для текущей 𝑡
вектор 𝜀𝑖𝑡 = (𝑡𝑖1 , 𝑡𝑖2 , … , 𝑡𝑖𝑁 ), где 𝑁 𝑡 – количество
ситуации, ранжируются по приоритетности.
Наиболее приоритетный сценарий считается анализируемых тем, а 𝑡𝑖𝑙 – значение, отражающее
оптимистическим, наименее приоритетный релевантность -го события 𝑙-ой теме. Темы задаются
– пессимистическим. экспертами в виде формализованных поисковых
4. Формируются предложения по действиям, запросов, а значения 𝑡𝑖𝑙 рассчитываются на основе
которые необходимо предпринять для модифицированного метода Okapi BM25 с помощью
способствования развитию текущей поисковой машины Sphinx [2]. Расстояние между
𝑡
ситуации по благоприятным сценариям. событиями с точки зрения тематического состава 𝛾𝑖,𝑗
также определяется на основе косинусной меры
4.1 Обнаружение аналогичных событий близости векторов: 𝛾𝑖,𝑗 𝑡
= 1 − 𝑠𝑖𝑚cos (𝜀𝑖𝑡 , 𝜀𝑖𝑡 ).
Событие представляет собой некоторое Расстояние между событиями с точки зрения
изменение ситуации в реальном мире. Однако аналогичности может быть представлено как
текстовое описание события характеризует не только взвешенная сумма расстояний по различным
само изменение, но и его контекст, т. е. содержит критериям:
информацию о ситуации в целом. Например, в 𝑤 𝑡𝑤 𝑡
сообщении о завершении тушения пожара 𝛾𝑎𝑛 (𝜀𝑖 , 𝜀𝑗 ) = 𝜆𝑤 𝛾𝑖,𝑗 + 𝜆𝑡𝑤 𝛾𝑖,𝑗 + 𝜆𝑡 𝛾𝑖,𝑗 .
содержится некоторая общая информация о Нахождение значений коэффициентов 𝜆𝑤 , 𝜆𝑡𝑤 , 𝜆𝑡
чрезвычайной ситуации – место и время и порогового значения 𝑇ℎ𝑎𝑛 может быть выполнено
возникновения пожара, причина и условия путем решения задачи линейной бинарной
протекания. Аналогичными будем считать события, классификации, состоящей в отнесении векторов
соответствующие схожим изменениям ситуаций без 𝑤
𝛾𝑖,𝑗 = (𝛾𝑖,𝑗 𝑡𝑤 𝑡
, 𝛾𝑖,𝑗 , 𝛾𝑖,𝑗 ) к одному из двух классов: один
учета контекста. означает аналогичность сравниваемых событий, а
Для определения аналогичности события 𝜀𝑖 , второй – её отсутствие. Решение задачи заключается
принадлежащего ситуационному графу, и события
𝑗 в построении разделяющей плоскости:
𝜀𝑠𝑒 , принадлежащего эталонной ситуации 𝑠𝑒 ,
𝑤 𝑡𝑤 𝑡
𝑗 𝜆𝑤 𝛾𝑖,𝑗 + 𝜆𝑡𝑤 𝛾𝑖,𝑗 + 𝜆𝑡 𝛾𝑖,𝑗 − 𝑇ℎ𝑎𝑛 = 0.
определим расстояние 𝛾𝑎𝑛 (𝜀𝑖 , 𝜀𝑠𝑒 ) между ними.
Функция 𝛾𝑎𝑛 (𝜀𝑖 , 𝜀𝑗 ) принимает неотрицательные Анализируемый вектор 𝛾𝑖,𝑗 относится к одному из
значения, причем 𝛾𝑎𝑛 (𝜀𝑖 , 𝜀𝑗 ) = 0, если события 𝜀𝑖 и 𝜀𝑗 классов, исходя из его расположения относительно
описывают полностью идентичные изменения, плоскости.
произошедшие в рамках соответствующих ситуаций. Для решения задачи может быть использована
𝑗
Если расстояние 𝛾𝑎𝑛 (𝜀𝑖 , 𝜀𝑠𝑒 ) меньше порогового машина опорных векторов (SVM). Чтобы обеспечить
возможность нахождения расстояния 𝛾𝑎𝑛 (𝜀𝑖 , 𝜀𝑗 ) как
значения 𝑇ℎ𝑎𝑛 , делается вывод о том, что текущее 𝑤 𝑡𝑤 𝑡
𝑗 взвешенной суммы значений 𝛾𝑖,𝑗 , 𝛾𝑖,𝑗 и 𝛾𝑖,𝑗 ,
событие 𝜀𝑖 аналогично эталону 𝜀𝑠𝑒 .
необходимо использовать SVM с линейным ядром.
При определении аналогичности событий Для обучения машины используется набор векторов
370
обоих классов, подготовленный экспертами. текущей ситуации с эталонной. В данном случае
Описанный способ обнаружения аналогов пары событий (𝜀11 ,𝜀21 ), (𝜀12 ,𝜀22 ) и (𝜀13 ,𝜀23 ) являются
позволяет находить для текущих событий схожие аналогами, событие 𝜀14 является «лишним» событием
события, происходившие в прошлом. Так, для текущей ситуации, а событие 𝜀24 является
события «Власти вынудили Uber свернуть онлайн- заключительной частью эталонной ситуации.
вызов такси с автопилотом в Сан-Франциско» (Рис.
1) такими аналогами являются другие случаи запрета Таблица 1 Сопоставление текущей и эталонной
использования тех или иных технологий органами ситуаций
власти по соображениям безопасности, в частности, Текущая ситуация Эталонная ситуация
событие «США официально запретили продажу 𝜀11 : Компания Uber 𝜀21 : Выпущен Samsung
Samsung Galaxy Note 7». После обнаружения запустила беспилотное Galaxy Note 7
события-аналога выполняется попытка выделения в такси в США
ситуационном графе цепочки, аналогичной 𝜀12 : Власти Калифорнии 𝜀22 : Власти США
соответствующей эталонной ситуации (в данном требуют от Uber призвали отказаться от
случае – ситуации, касающейся проблем Samsung, прекратить использования Samsung
связанных со смартфоном Galaxy Note 7). использование Galaxy Note 7
4.2 Определение близости между ситуациями беспилотных такси
𝜀13 : Власти вынудили 𝜀23 : США официально
На формируемую текущую ситуацию Uber свернуть онлайн- запретили продажу
накладывается следующее ограничение: события, вызов такси с Samsung Galaxy Note 7
аналогичные событиям из эталонной цепочки,
автопилотом в Сан-
должны следовать друг за другом в том же порядке,
Франциско
что и соответствующие события в эталонной
𝜀14 : Uber перенесла
ситуации. Это связано с тем, что последовательность
беспилотные такси в
событий в эталонной цепочке отражает их причинно-
Аризону
следственную связь и логику развития ситуации.
Если в текущей и эталонной последовательностях 𝜀24 : Samsung объявил о
события располагаются в разном порядке, значит, прекращении
логика их развития различна, и они не могут быть производства Galaxy
признаны аналогами. Note 7
Таким образом, при определении близости между Для измерения близости ситуаций используется
ситуациями необходимо учитывать, что цепочки метод, представляющий собой модификацию
содержат ряд попарно аналогичных событий, расстояния Левенштейна: расстояние между
располагающихся в цепочках в одинаковом порядке цепочками определяется суммарным весом
(на Рис. 2 они выделены серым цветом, пунктирной операций, необходимых для превращения одной
линией соединены события-аналоги). Кроме того, цепочки в другую. Рассмотрим операции, которые
каждая из ситуаций может содержать события, требуются для превращения начальной части
аналоги которых отсутствуют в другой цепочке. На эталонной ситуации 𝑠𝑡(𝑠𝑒 , 𝑠𝑐 ) в текущую ситуацию
Рис. 2 эталонные события, аналоги которых 𝑠𝑐 , а также способы измерения веса этих операций.
отсутствуют в текущей ситуации, выделены • Удаление событий 𝜀𝑠𝑖𝑒 , аналоги которых
вертикальной штриховкой, «лишние» события отсутствуют в текущей ситуации. В качестве веса
текущей ситуации – горизонтальной. Также
операции 𝑤𝑑𝑒𝑙 (𝜀𝑠𝑖𝑒 ) может использоваться
необходимо помнить о том, что при сравнении
учитывается лишь начальная часть эталонной значимость удаляемого события – показатель,
ситуации 𝑠𝑡(𝑠𝑒 , 𝑠𝑐 ) – от её первого события (𝜀𝑠1𝑒 на учитывающий количество документов,
описывающих событие, и авторитетность
рис. 2) до последнего события, имеющего аналог в
источников, опубликовавших эти документы.
текущей ситуации (𝜀𝑠6𝑒 на рис. 2). События,
Множество удаляемых событий обозначим 𝐸𝑑𝑒𝑙 .
составляющие заключительную часть эталонной Суммарный вес таких операций: 𝑊𝑑𝑒𝑙 =
ситуации 𝑓𝑖𝑛(𝑠𝑒 , 𝑠𝑐 ), не влияют на значение ∑𝜀𝑠 𝜖𝐸𝑑𝑒𝑙 𝑤𝑑𝑒𝑙 (𝜀𝑠𝑒 ).
близости. 𝑒
• Добавление событий 𝜀𝑠𝑖𝑐 , аналоги которых
st ( se , sc ) fin( se , sc ) отсутствуют в эталонной ситуации. Вес операции
𝑤𝑎𝑑𝑑 (𝜀𝑠𝑖𝑐 ) вычисляется аналогично. Множество
s1 s2 s3 s4 s5 s6 s7 s8
se
e e e e e e e e добавляемых событий обозначим 𝐸𝑎𝑑𝑑 .
Суммарный вес операций добавления: 𝑊𝑎𝑑𝑑 =
pre( se , sc ) ∑𝜀𝑠 𝜖𝐸𝑎𝑑𝑑 𝑤𝑎𝑑𝑑 (𝜀𝑠𝑐 ).
𝑐
sc
s1c s2 s3 s4 s5 s6 s7 • Замена события из эталонной цепочки 𝜀𝑠𝑖𝑒 на его
c c c c c c 𝑗 𝑗
аналог 𝜀𝑠𝑐 . Вес этой операции 𝑤𝑟𝑒𝑝 (𝜀𝑠𝑖𝑒 , 𝜀𝑠𝑐 )
Рисунок 2 Сопоставление цепочек событий 𝑗
определяется расстоянием 𝛾𝑎𝑛 (𝜀𝑠𝑖𝑒 , 𝜀𝑠𝑐 ) между
В Таблице 1 представлен пример сравнения 𝑗
событиями 𝜀𝑠𝑖𝑒 и 𝜀𝑠𝑐 с точки зрения аналогичности.
371
𝑗
Множество пар (𝜀𝑠𝑖𝑒 , 𝜀𝑠𝑐 ) обозначим 𝑃𝑟𝑒𝑝 . выборки, состоящей из множества пар аналогичных
Суммарный вес операций этого вида: 𝑊𝑟𝑒𝑝 = и неаналогичных ситуаций.
𝑗 Логистическая регрессия позволяет также
∑ 𝑖 𝑗
(𝜀 ,𝜀 )𝜖𝑃
𝑤𝑟𝑒𝑝 (𝜀𝑠𝑖𝑒 , 𝜀𝑠𝑐 ). выполнить бинарную классификацию пар ситуаций:
𝑠𝑒 𝑠𝑐 𝑟𝑒𝑝
• Изменение (сокращение или удлинение) цепочки 𝑠𝑒 и 𝑠𝑐 считаются потенциальными
𝑖,𝑗 аналогами при P(𝑦 = 0|𝑠𝑒 , 𝑠𝑐 ) > 0.5.
временного интервала 𝑡𝑠𝑒 между событиями.
𝑖,𝑗
Интервалу 𝑡𝑠𝑒 в эталонной последовательности 4.4 Формирование сценария
соответствует интервал 𝑡𝑠𝑘,𝑙 в текущей ситуации, Построение текущей ситуации начинается с
𝑐
𝑘 𝑖 𝑙 𝑗 нового или измененного события ситуационного
где 𝜀𝑠𝑐 – аналог 𝜀𝑠𝑒 , а 𝜀𝑠𝑐 – аналог 𝜀𝑠𝑒 . Вес этой графа 𝜀𝑐 , которое обязательно должно ей
𝑖,𝑗
операции 𝑤𝑡𝑟𝑒𝑝 (𝑡𝑠𝑒 , 𝑡𝑠𝑘,𝑙
𝑐
) определяется принадлежать. Далее на каждом шаге выполняется
относительной разностью между величинами попытка дополнить ситуацию путем присоединения
𝑖,𝑗
интервалов: 𝑤𝑡𝑟𝑒𝑝 (𝑡𝑠𝑒 , 𝑡𝑠𝑘,𝑙 ) = |𝑡𝑠𝑖,𝑗𝑒 − 𝑡𝑠𝑘,𝑙 𝑖,𝑗
|⁄𝑡𝑠𝑒 . к цепочке одного из соседей события, которое на
𝑐
𝑖,𝑗
𝑐 данный момент является первым или последним в
Множество пар (𝑡𝑠𝑒 , 𝑡𝑠𝑘,𝑙 𝑐
) обозначим 𝑇𝑡𝑟𝑒𝑝 . цепочке. При этом необходимо рассмотреть
Суммарный вес таких операций: 𝑊𝑡𝑟𝑒𝑝 = различные варианты интерпретации добавляемого в
∑(𝑡 𝑖,𝑗,𝑡 𝑘,𝑙 )𝜖𝑇 𝑤𝑡𝑟𝑒𝑝 (𝑡𝑠𝑖,𝑗𝑒 , 𝑡𝑠𝑘,𝑙 ). цепочку события. Оно может интерпретироваться и
𝑠𝑒 𝑠𝑐 𝑡𝑟𝑒𝑝 𝑐
как аналог некоторого события из 𝑠𝑒 , и как «лишнее»
Ввиду различия способов расчёта веса операций событие, не имеющее аналогов в эталонной цепочке.
разных типов, при вычислении расстояния между Путем выбора на каждом шаге одного из возможных
цепочками они должны учитываться с различными событий, добавляемых в цепочку, а также одного из
коэффициентами. Кроме того, расстояние возможных вариантов его интерпретации
необходимо нормировать, поскольку, чем короче формируется дерево возможных вариантов
учитываемая при сравнении часть эталонной построения текущей ситуации. Из всех вариантов
текущей ситуации, рассмотренных в процессе
цепочки, тем меньше модифицирующих операций с
построения, выбирается цепочка 𝑠𝑐𝑚𝑎𝑥 , имеющая
ней можно произвести с сохранением аналогичности
максимальную близость к эталону. Эта
полученной последовательности оригиналу. Таким последовательность считается завершенной текущей
образом, расстояние между эталонной и текущей ситуацией.
цепочкой Если P(𝑦 = 0|𝑠𝑒 , 𝑠𝑐𝑚𝑎𝑥 ) > 0.5, полученная
𝜃𝑇 𝑊 текущая ситуация признается аналогом 𝑠𝑒 . В этом
𝜌(𝑠𝑒 , 𝑠𝑐 ) = =
𝑙𝑒𝑛(𝑠𝑡(𝑠𝑒 , 𝑠𝑐 )) случае 𝑓𝑖𝑛(𝑠𝑒 , 𝑠𝑐𝑚𝑎𝑥 ) считается возможным
=
(𝜃𝑑𝑒𝑙 𝑊𝑑𝑒𝑙 +𝜃𝑎𝑑𝑑 𝑊𝑎𝑑𝑑 +𝜃𝑟𝑒𝑝 𝑊𝑟𝑒𝑝 +𝜃𝑡𝑟𝑒𝑝 𝑊𝑡𝑟𝑒𝑝 )
, сценарием дальнейшего развития текущей ситуации,
𝑙𝑒𝑛(𝑠𝑡(𝑠𝑒 ,𝑠𝑐)) а значение P(𝑦 = 0|𝑠𝑒 , 𝑠𝑐𝑚𝑎𝑥 ) – вероятностью того,
где 𝑙𝑒𝑛(𝑠𝑡(𝑠𝑒 , 𝑠𝑐 )) – количество событий в начальной что текущая ситуация будет развиваться в
части 𝑠𝑡(𝑠𝑒 , 𝑠𝑐 ) эталонной ситуации 𝑠𝑒 , а 𝜃𝑑𝑒𝑙, 𝜃𝑎𝑑𝑑 , соответствии с этим сценарием. На основе всех
𝜃𝑟𝑒𝑝 и 𝜃𝑡𝑟𝑒𝑝 – коэффициенты, определяющие вклад эталонных ситуаций, аналогичных текущей,
операций различных типов в значение расстояния. формируется множество возможных сценариев её
дальнейшего развития. Заключительная часть
4.3 Определение вероятности аналогичности
цепочки, для которой вероятность аналогичности
ситуаций 𝑝𝑟𝑜𝑏
текущей ситуации максимальна (𝑠𝑒 =
На основе расстояния 𝜌(𝑠𝑒 , 𝑠𝑐 ) необходимо 𝑚𝑎𝑥
argmax[P(𝑦 = 0|𝑠𝑒 , 𝑠𝑐 )]), является наиболее
определить, является ли текущая ситуация аналогом 𝑠𝑒
эталонной и какова вероятность того, что текущая вероятным сценарием.
ситуация будет развиваться по сценарию, 4.5 Выделение оптимистического и
определяемому эталонной ситуацией. С этой целью пессимистического сценариев
было принято решение рассмотреть сравнение
цепочек как задачу логистической регрессии. Для Для выделения оптимистического и
этого введем переменную 𝑦, принимающую одно из пессимистического сценариев необходимо
двух возможных значений: определить оптимальность каждого из них. Для этого
1, еслицепочкинеявляютсяаналогами, используется метод анализа иерархий (МАИ),
𝑦={ позволяющий определить приоритет различных
0, еслицепочкиявляютсяаналогами.
Предположим, что вероятность наступления альтернатив с точки зрения цели с учетом различных
события 𝑦 = 0 (т. е. вероятность того, что текущая критериев [17]. Целью в данном случае является
ситуация является аналогом эталонной) задана выбор оптимального сценария, альтернативами –
сформированные сценарии, а в качестве критериев
функцией:
1 могут использоваться такие характеристики
P(𝑦 = 0|𝑠𝑒 , 𝑠𝑐 ) = 1 − . сценариев, как длительность, экономическая
𝜃𝑇 𝑊 эффективность и другие. Выбор критериев
1 + exp (− ) определяется предметной областью, в рамках
𝑙𝑒𝑛(𝑠𝑡(𝑠𝑒 , 𝑠𝑐 ))
которой используется прогнозирование развития
Значения параметров 𝜃 подбираем методом
ситуаций.
максимального правдоподобия на основе обучающей
372
Значения критериев для эталонных ситуаций Также на рисунке представлен наиболее вероятный
определяются экспертами на этапе подготовки базы сценарий, определенный с помощью логистической
эталонов 𝑆𝑒 . Также эксперты путем попарных регрессии.
сравнений определяют приоритетность критериев
4.6 Формирование предложений для лиц,
относительно цели. Приоритетность сценариев
принимающих решения
относительно каждого из критериев может быть
определена автоматически при анализе С целью последующего формирования
ситуационного графа на основе сравнения предложений эксперты должны снабжать каждое
характеристик соответствующих эталонных событие 𝜀𝑒 каждой эталонной ситуации 𝑠𝑒
ситуаций. Это позволяет автоматически определить рекомендациями по действиям, которые должны
приоритет относительно цели для каждого из предприниматься при наступлении аналогичного
сценариев, сформированных для текущей ситуации. события в будущем. Рекомендация 𝑟𝑒𝑐𝜀𝑒 =
Сценарий с максимальным приоритетом считается 〈𝑎𝑐𝑡𝑖𝑜𝑛𝜀𝑒 , 𝑎𝑐𝑡𝑜𝑟𝜀𝑒 , 𝑝𝑒𝑟𝑖𝑜𝑑𝜀𝑒 〉 содержит информацию о
оптимистическим, сценарий с минимальным действиях 𝑎𝑐𝑡𝑖𝑜𝑛𝜀𝑒 , которые должны быть
приоритетом – пессимистическим. предприняты лицом 𝑎𝑐𝑡𝑜𝑟𝜀𝑒 в срок 𝑝𝑒𝑟𝑖𝑜𝑑𝜀𝑒 для
На Рис. 3 показаны оптимистический и
пессимистический сценарии, сформированные для содействия или противодействия развитию текущей
ситуации, связанной с тестированием беспилотных ситуации по сценарию, сформированному на основе
такси. Для определения приоритетности сценариев 𝑠𝑒 .
использовались такие критерии, как «безопасность», На Рис. 3 показаны рекомендации для ЛПР с
«длительность» и «экономическая эффективность». учетом сценариев, сформированных для ситуации с
тестированием беспилотных такси.
Рисунок 3 Пример формирования оптимистического, наиболее вероятного и пессимистического сценариев
развития ситуации
Рисунок 3 Пример формирования оптимистического, наиболее вероятного и пессимистического сценариев
развития ситуации
5 Экспериментальная проверка метода
На основе предложенного метода разработана
система автоматизированного мониторинга и
прогнозирования развития ситуаций. Обучение
системы выполняется экспертами на основе
эталонных событий и ситуаций. Обученная система
автоматически обрабатывает текстовый поток,
обнаруживает события и формирует ситуации, а
также определяет вероятные сценарии их Рисунок 4 Зависимость точности (тонкая сплошная
дальнейшего развития и вырабатывает линия), полноты (пунктирная линия) и F-меры
рекомендации. (жирная линия) от мощности обучающей выборки
Результаты качества работы подсистемы
обнаружения событий приведены в [5].
Эксперименты показали, что при использовании для 6 Направления дальнейших
обучения 1300 пар документов и событий исследований
достигается значение точности 85,2%, полноты – Предложенный метод прогнозирования развития
76% и F-меры – 79,8%. ситуаций предоставляет пользователю сценарии
Для анализа качества работы подсистемы дальнейшего развития ситуации и рекомендации по
формирования сценариев был проведен эксперимент действиям, необходимым для их реализации, но не
с целью определения зависимости точности, полноты позволяет осуществлять управление развитием
и F-меры выявления аналогичных ситуаций от ситуации по оптимальному сценарию. Пользователю
мощности обучающей выборки. Полученные требуется определять, соответствует ли развитие
зависимости приведены на Рис. 4. В результате ситуации сформированному ранее сценарию, и
проведения эксперимента оказалось, что для получать рекомендации в случае необходимости
обучения системы достаточно 90 пар ситуаций. При корректировки намеченного плана мероприятий. В
таком количестве обучающих примеров достигается связи с этим дальнейшим направлением развития
значение F-меры около 0.8, с дальнейшим метода является разработка более сложных сетевых
увеличением обучающей выборки качество работы моделей эталонных ситуаций, способных отражать
метода не улучшается. различные варианты возможного развития текущей
ситуации в зависимости от действий ЛПР на каждом
этапе управления ситуацией.
373
Выше описан эксперимент по оценке качества электронные коллекции: Труды Седьмой
обнаружения аналогичных ситуаций, однако Всерос. науч. конф. (RCDL–2005), сс. 173-181
необходимо также оценивать качество (2005)
прогнозирования. В связи с этим в рамках [7] Андреев, А.М., Березкин, Д.В., Симаков, К.В.:
дальнейших исследований планируется выработать Особенности проектирования модели и
критерий качества ситуационного прогноза и онтологии предметной области для поиска
выполнить оценку результатов прогноза по этому противоречий в правовых электронных
критерию. библиотеках. Электронные библиотеки:
перспективные методы и технологии,
7 Заключение электронные коллекции: Труды Шестой Всерос.
Предложен метод прогнозирования развития науч. конф. RCDL, сс. 93-102 (2004)
ситуаций на основе обнаружения событий в потоке [8] Ахременко, А.С.: Политический анализ и
текстовых документов. Прогнозирование состоит в прогнозирование: Учеб. пособие. М.: Гардарики
формировании сценариев дальнейшего развития (2006)
ситуаций по принципу исторической аналогии: [9] Борисов, В.В., Зернов, М.М.: Реализация
выполняется построение текущей ситуации, для ситуационного подхода на основе нечеткой
которой существует аналог в базе эталонных иерархической ситуационно-событийной сети.
ситуаций. Этот аналог считается возможным Искусственный интеллект и принятие решений,
сценарием развития текущей ситуации. 1, сс. 18-30 (2009)
Предложенный метод формирования сценариев
[10] Варшавский, П.Р.: Методы и программные
учитывает динамику развития ситуаций и нестрогий
средства поиска решения на основе аналогий в
характер аналогии между ситуациями. Из множества
интеллектуальных системах поддержки
сформированных сценариев выделены
принятия решения. Дисс. … канд. техн. наук,
оптимистический и пессимистический, для этого
Московский энергетический институт (2005)
использован метод анализа иерархий. Также
предложен способ подготовки предложений по [11] Волгин, Н.С.: Исследование операций, ч. 1. С-
действиям, которые необходимо предпринять для Пб.: ВМА им. Н. Г. Кузнецова (1999)
способствования или препятствования развитию [12] Еремеев, А.П., Варшавский, П.Р.:
ситуации по построенным сценариям. Моделирование рассуждений на основе
прецедентов в интеллектуальных системах
Литература поддержки принятия решений. Искусственный
интеллект и принятие решений, 2, сс. 45-57
[1] Aggarwal, C.C., Subbian, K.: Event Detection in
(2009)
Social Streams. Proc. of the 2012 SIAM Int. Conf.
on Data Mining, pp. 624-635. Society for Industrial [13] Зацаринный, А.А., Сучков, А.П.: Некоторые
and Applied Mathematics, Philadelphia (2012). doi: подходы к ситуационному анализу потоков
10.1137/1.9781611972825.54 событий. Открытое образование, 1, сс. 39-46
(2012)
[2] How Sphinx Relevance Ranking Works.
http://sphinxsearch.com/blog/2010/08/17/how- [14] Кононов, Д.А., Косяченко, С.А., Кульба, В.В.:
sphinx-relevance-ranking-works/ Формирование и анализ сценариев развития
социально-экономических систем с
[3] van der Aalst, W.M.P.: Process Mining: Data
использованием аппарата операторных графов.
Science in Action. Springer, Heidelberg (2016).
Автоматика и телемеханика, 68 (1), сс. 121-136
doi: 10.1007/978-3-662-49851-4
(2007)
[4] Андреев, А.М., Березкин, Д.В., Брик, А.В.,
[15] Косяченко, С.А., и др.: Модели, методы и
Смирнов, Ю.М.: Вероятностный
автоматизация управления в условиях
синтаксический анализатор для
чрезвычайных ситуаций. Автоматика и
информационно-поисковых систем. Вестник
телемеханика, 59 (6), сс. 3-66 (1998)
МГТУ. Сер. Приборостроение, 2, сс. 34-53
(2000) [16] Кулинич, А.А.: Компьютерные системы
[5] Андреев, А.М., Березкин, Д.В., Козлов, И.А.:
моделирования когнитивных карт: подходы и
методы. Проблемы управления, 3, сс. 2-16
Подход к автоматизированному мониторингу
(2010)
тем на основе обнаружения событий в потоке
текстовых документов. Информационно- [17] Саати, Т.: Методы анализа иерархий. М.: Радио
измерительные и управляющие системы, 15 (3), и связь (1993)
сс. 49-60 (2017) [18] Ситчихин, А.Н.: Иерархические ситуационные
[6] Андреев, А.М., Березкин, Д.В., Симаков, К.В.: модели с предысторией для
Обучение морфологического анализатора на автоматизированной поддержки решений в
большой электронной коллекции текстовых сложных системах. Дисс. … канд. техн. наук,
документов. Электронные библиотеки: Уфимский гос. авиационный технический
перспективные методы и технологии, университет (2002)
374