В настоящий момент большое количество данных, обрабатываемых современными информационными системами (ИС), имеет форму информационных потоков: новые информационные сообщения постоянно поступают из источников и должны обрабатываться ИС с минимальной задержкой. Как правило, информация в потоке представлена в неструктурированном виде, в Труды XIX Международной конференции «Аналитика и управление данными в областях с интенсивным использованием данных» (DAMDID/ RCDL’2017), Москва, Россия, 10–13 октября 2017 года частности, в форме текста. Так, форму текстовых потоков имеют сообщения пользователей в социальных сетях, новости СМИ, официальные заявления органов власти.
Динамический характер текстовых потоков делает их важным средством информационной поддержки для людей, которым требуется принимать управленческие решения в режиме реального времени в условиях меняющейся обстановки. Задачи своевременного обнаружения проблемной ситуации, отслеживания её развития и оперативного принятия решений по управлению развитием ситуации возникают в различных сферах – политической, социальной, военной, экономической. т. е.
или Анализ , , , , , ,
, ). содержание
документа
= ( 1, 2, … , ), каждый элемент которого отражает значимость kго терма в контексте документа и рассчитывается с помощью
метода TF-IDF. Каждое событие также описано многокритериальной моделью, компоненты формируются на основе документов, течением времени ситуации.
потенциально принадлежащих
одной На основе формирования таких
пар выполняется построение ситуационного графа = ( , ). В этом графе узлы событиям, а ребра = { } – выделенным парам = { } соответствуют
(каждое ребро , , , ).
событию: = Объединение группы
выполняется с помощью события, а описаны в [5]. алгоритма инкрементальной кластеризации, в основе которого каждого лежит документа покомпонентное
сопоставление с ранее
обнаруженными событиями. Более подробно модели документа и
также метод обнаружения событий Метод
позволяет работать с документами на произвольном языке при наличии подготовленных экспертами тематических запросов, а также словарей имен персон, названий организаций
и географических наименований на соответствующем языке.
Многие работы используют принцип аналогии – прогнозирование дальнейшего развития ситуации и формирование предложений по управляющим действиям основано на поиске аналогичных ситуаций, имевших место в прошлом. В работах, базирующихся на принципе аналогии, используются различные подходы к представлению ситуаций.
В [10] ситуация представляется фрагментом семантической сети, содержащим объекты и их отношения в рамках ситуации. Получить такое представление автоматически возможно лишь для определенных предметных областей, поэтому такой подход нельзя использовать для прогнозирования развития произвольных ситуаций.
В ряде работ предложено описание ситуаций в
виде набора или вектора параметров с
определенными значениями [
Для учета динамики можно использовать
описание эталонной ситуации в виде графа или
автомата [
Подход на основе нестрогой аналогии предложен в [8]. Ситуации представляются цепочками событий, близость между ними определяется с помощью модифицированного расстояния Левенштейна. Но этот подход требует выделения для каждого события объекта и субъекта, что не может быть сделано автоматически для произвольных текстовых сообщений. Кроме того, результат определения аналогов текущей ситуации в названной работе используется лишь для отнесения этой ситуации к одному из заданных классов. 4 Предлагаемый метод прогнозирования развития ситуаций
Обнаружение для текущей последовательности цепочки-аналога позволяет не только определить вероятный итог развития ситуации (как предлагается в [8]), но и объяснить, какие события могут привести к этому итогу. Такой прогноз можно получить, если обнаружено сходство всей текущей последовательности с начальной частью ( , ) цепочки-аналога. В этом случае можно предположить, что в будущем наступят события, аналогичные тем, которые составляют заключительную часть цепочки-аналога ( , ). Таким образом, эту заключительную часть можно рассматривать как возможный сценарий дальнейшего развития текущей ситуации.
Для выполнения сопоставления необходимо наличие базы ситуаций-эталонов = { }. Такие эталоны отбираются экспертами в зависимости от задачи, для 1.
неотрицательные значения, причем
( , )= 0, если события и описывают полностью идентичные
изменения, произошедшие в рамках соответствующих ситуаций. Если расстояние ( , ) меньше порогового
событие аналогично эталону . значения ℎ , делается вывод о том, что текущее При определении аналогичности учитываются их названия, текстовые описания и тематический состав. Текстовое описание события задается вектором количество различных = ( 1, 2, … , ), где – слов,
встречающихся в описаниях событий, – вес -го слова в описании го события, который находится методом TF-IDF.
Для того чтобы наиболее важную
роль при определении аналогичности играли
термы, характерные для конкретного события, а не ситуации в целом, было решено умножать вес каждого терма в на коэффициент ,
отражающий соотношение значимости терма для события и для ситуации , к которой относится это событие: = ( )⁄ ∑ , где
( )– количество событий в ′ = ( 1 1, 2 2, … , ).
Расстояние между событиями с точки зрения текста рассчитывается на основе косинусной меры:
, = 1 − названия события cos( ′ , ′).
Представление
слов ′ и расчёт расстояния между событиями с точки зрения названий , выполняется аналогично.
Тематический
состав события характеризует вектор = ( 1, 2, … , анализируемых тем, а
), где – количество – значение, отражающее релевантность -го события -ой теме. Темы задаются экспертами в виде
формализованных поисковых
запросов, а значения рассчитываются на основе
модифицированного метода Okapi BM25 с помощью
поисковой машины Sphinx [
).
Расстояние между событиями с точки зрения аналогичности
может взвешенная сумма быть представлено
как расстояний по
различным критериям: ( , )= , +
, + , .
Нахождение значений коэффициентов , , путем
решения и порогового значения ℎ
может быть выполнено обоих классов, подготовленный экспертами.
Описанный способ обнаружения аналогов позволяет находить для текущих событий схожие события, происходившие в прошлом. Так, для события «Власти вынудили Uber свернуть онлайнвызов такси с автопилотом в Сан-Франциско» (Рис. 1) такими аналогами являются другие случаи запрета использования тех или иных технологий органами власти по соображениям безопасности, в частности, событие «США официально запретили продажу Samsung Galaxy Note 7». После обнаружения события-аналога выполняется попытка выделения в ситуационном графе цепочки, аналогичной соответствующей эталонной ситуации (в данном случае – ситуации, касающейся проблем Samsung, связанных со смартфоном Galaxy Note 7). 4.2 Определение близости между ситуациями
На формируемую текущую ситуацию накладывается следующее ограничение: события, аналогичные событиям из эталонной цепочки, должны следовать друг за другом в том же порядке, что и соответствующие события в эталонной ситуации. Это связано с тем, что последовательность событий в эталонной цепочке отражает их причинноследственную связь и логику развития ситуации. Если в текущей и эталонной последовательностях события располагаются в разном порядке, значит, логика их развития различна, и они не могут быть признаны аналогами.
Таким образом, при определении близости между ситуациями необходимо учитывать, что цепочки содержат ряд попарно аналогичных событий, располагающихся в цепочках в одинаковом порядке (на Рис. 2 они выделены серым цветом, пунктирной линией соединены события-аналоги). Кроме того, каждая из ситуаций может содержать события, аналоги которых отсутствуют в другой цепочке. На Рис. 2 эталонные события, аналоги которых отсутствуют в текущей ситуации, выделены вертикальной штриховкой, «лишние» события текущей ситуации – горизонтальной. Также необходимо помнить о том, что при сравнении учитывается лишь начальная часть эталонной ситуации ( , ) – от её первого события ( 1 на рис. 2) до последнего события, имеющего аналог в текущей ситуации ( 6 на рис. 2). События, составляющие заключительную часть эталонной ситуации ( , ), не влияют на значение близости.
st(se, sc ) s2e s3e s4e s5e s6e
s8e s1e se pre(se, sc ) sc
s1c s2c s3c s4c s5c s6c Рисунок 2 Сопоставление цепочек событий В Таблице 1 представлен пример сравнения fin(se, sc ) s7e s7c текущей ситуации с эталонной. В данном случае пары событий ( 11, 21), ( 12, 22) и ( 13, 23) являются аналогами, событие 14 является «лишним» событием текущей ситуации, а событие 24 является заключительной частью эталонной ситуации. Таблица 1 Сопоставление текущей и эталонной ситуаций Текущая ситуация Эталонная ситуация 11: Компания Uber 21: Выпущен Samsung запустила беспилотное Galaxy Note 7 такси в США 12: Власти Калифорнии 22: Власти США требуют от Uber призвали отказаться от прекратить использования Samsung использование Galaxy Note 7 беспилотных такси 13: Власти вынудили 23: США официально Uber свернуть онлайн- запретили продажу вызов такси с Samsung Galaxy Note 7 автопилотом в СанФранциско 14: Uber перенесла беспилотные такси в Аризону 24: Samsung объявил о прекращении производства Galaxy
Note 7 Для измерения близости ситуаций используется метод, представляющий собой модификацию расстояния Левенштейна: расстояние между цепочками определяется суммарным весом операций, необходимых для превращения одной цепочки в другую. Рассмотрим операции, которые требуются для превращения начальной части эталонной ситуации ( , ) в текущую ситуацию , а также способы измерения веса этих операций. • Удаление событий , аналоги которых отсутствуют в текущей ситуации. В качестве веса операции ( ) может использоваться значимость удаляемого события – показатель, учитывающий количество документов, описывающих событие, и авторитетность источников, опубликовавших эти документы. Множество удаляемых событий обозначим . Суммарный вес таких операций: = ∑ ( ). • Добавление событий , аналоги которых отсутствуют в эталонной ситуации. Вес операции ( ) вычисляется аналогично. Множество добавляемых событий обозначим . Суммарный вес операций добавления: = ∑ ( ). • Замена события из эталонной цепочки на его аналог . Вес этой операции определяется расстоянием ( , ) между
с точки зрения аналогичности. событиями и ( , ) сравнений определяют приоритетность критериев относительно цели.
Приоритетность 〉 содержит информацию о предприняты лицом
в срок содействия или противодействия развитию текущей ситуации по сценарию, сформированному на основе
На Рис. 3 показаны рекомендации для ЛПР с учетом сценариев, сформированных для ситуации с тестированием беспилотных такси. Значения критериев для эталонных ситуаций определяются экспертами на этапе подготовки базы Также на рисунке представлен наиболее вероятный сценарий, определенный с помощью логистической эталонов . Рисунок 3 Пример формирования оптимистического, наиболее вероятного и пессимистического сценариев развития ситуации 5 Экспериментальная проверка метода
На основе предложенного метода разработана Рисунок 4 Зависимость точности (тонкая сплошная линия), полноты (пунктирная линия) и F-меры (жирная линия) от мощности обучающей выборки 6 Направления дальнейших исследований
Предложенный метод прогнозирования развития
Выше описан эксперимент по оценке качества обнаружения аналогичных ситуаций, однако необходимо также оценивать качество прогнозирования. В связи с этим в рамках дальнейших исследований планируется выработать критерий качества ситуационного прогноза и выполнить оценку результатов прогноза по этому критерию. 7 Заключение
Предложен метод прогнозирования развития ситуаций на основе обнаружения событий в потоке текстовых документов. Прогнозирование состоит в формировании сценариев дальнейшего развития ситуаций по принципу исторической аналогии: выполняется построение текущей ситуации, для которой существует аналог в базе эталонных ситуаций. Этот аналог считается возможным сценарием развития текущей ситуации. Предложенный метод формирования сценариев учитывает динамику развития ситуаций и нестрогий характер аналогии между ситуациями. Из множества сформированных сценариев выделены оптимистический и пессимистический, для этого использован метод анализа иерархий. Также предложен способ подготовки предложений по действиям, которые необходимо предпринять для способствования или препятствования развитию ситуации по построенным сценариям. Литература