Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

ПРАВИТЕЛЬСТВО РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»

Факультет компьютерных наук

Департамент программной инженерии

Выпускная квалификационная работа

на тему «Приложение для выявления аномалий при ведении уголовных дел на основе анализа журналов событий»

по направлению подготовки 09.03.04 «Программная инженерия»

Научный руководитель

доктор физико-математических наук

И.А. Ломазова

Выполнила

студентка группы БПИ152

4 курса бакалавриата

А.А. Колосова

Москва 2019



Реферат

Process mining (PM) в настоящее время широко применяется для анализа и улучшения процессов в различных областях, таких как банковское дело или медицина. Методы PM позволяют получать и анализировать модели существующих процессов, основываясь на записанном поведении системы. В результате такого анализа в процессе исполнения могут быть найдены ошибки, отклонения и слабые места. Знания о таких аномалиях необходимы при управлении бизнес-процессами. Для ряда процессов, которые являются нормативными, отклонения от заданных норм не просто нежелательны, а недопустимы. Примером такого процесса является процесс ведения уголовных дел, регулируемый уголовно-процессуальным кодексом.

Целью данной работы является исследование возможности применения методов PM для анализа процесса ведения уголовного дела. В ходе исследования должна быть разработана программа для выявления и визуализации аномалий в процессе. Ожидается, что данное приложение станет удобным инструментом для исследователей проблем в области правоприменения, а также упростит мониторинг сложного процесса уголовного делопроизводства.

Работа содержит 36 страниц, 3 главы, 7 рисунков, 7 таблиц, 3 схемы алгоритма, 32 источника, 4 приложения.

Ключевые слова: аномалии, журналы событий, кластеризация, уголовный процесс, conformance checking, process mining



Abstract

Process mining (PM) is now widely used to analyze and improve processes in various spheres, such as banking or medicine. The PM methods make it possible to obtain and analyze models of existing processes based on a behavior recorded in event logs. As a result of such analysis, possible errors, deviations and bottlenecks in a control-flow can be revealed. Being aware of such anomalies is important in business process management. For normative type of processes deviations from the prescribed behavior are unacceptable.

At this work the focus is on the process of criminal proceedings, which is described in the criminal procedure code. The primary aim of the work is to study the possibility of applying the methods of PM to analyze the criminal proceedings. As a result of the study, a program for detection and visualization of anomalies should be developed. This program will significantly simplify the process of monitoring litigation and can be used in the analysis of the process by researchers of the institute for the rule of law.

The paper contains 36 pages, 3 chapters, 7 images, 32 references, 4 appendices.

Keywords: anomalies detection, criminal proceedings, conformance checking, event logs, process mining.



Содержание

• Определения
• Введение
• Глава 1. Выявление аномалий в процессах и проведение проверки соответствия модели и журналов событий
• 1.1 Выявление аномалий в данных
• 1.2 Проведение conformance checking
• 1.3 Реализация алгоритмов
• Выводы по главе 1
• Глава 2. Метод проверки соответствия с учетом специфики процесса и последующая кластеризация данных
• 2.1 Особенности процесса, влияющие на выбор метода проверки соответствия
• 2.2 Сеть Петри с атрибутами
• 2.3 Взвешенный token-replay
• 2.4 Кластеризация логов с аномалиями
• 2.5 Построение модели процесса для определенного паттерна аномалий
• Выводы по главе 2
• Глава 3. Полученные результаты и их программное представление
• 3.1 Средства и инструменты для разработки приложения для выявления аномалий в журналах событий и для визуализации паттернов выявленных аномалий
• 3.1.1 Приложение для оценки соответствия модели и журналов событий
• 3.1.2 Приложение для визуализации паттернов аномалий
• 3.2 Модель процесса ведения уголовных дел
• 3.3 Предварительная обработка журналов событий
• 3.4 Символьное представление трасс для кластеризации
• 3.5 Модуль выявления возможных отклонений на основе журналов событий
• 3.6 Модуль визуализации паттернов аномалий
• Выводы по главе 3
• Заключение
• Список источников



Определения

приложение аномалия модель журнал событие

Аномалия - паттерн в данных, которые не соответствует четко определенному понятию нормального поведения системы.

Журнал событий (лог событий) - набор трасс исполнения процесса, где каждая трасса содержит последовательность имен событий с атрибутами.

Кластеризация - задача группировки множества объектов на подмножества (кластеры) таким образом, чтобы объекты из одного кластера были более похожи друг на друга, чем на объекты из других кластеров по какому-либо критерию.

Модель процесса - формализм, используемый для описания процесса.

Сеть потоков работ - вид сетей Петри, в которых существует только одна начальная позиция, одна конечная позиция и все узлы сети расположены на пути от начальной позиции к конечной позиции.

Conformance checking - направление в process mining. Содержит методы для оценки соответствия ожидаемого поведения, представленного в виде модели процесса, и реального поведения, записанного в журналах событий.

Conformance testing - процесс оценивания соответствия логов и модели, проведение conformance checking.

Fitness - одна из метрик для оценки модели процесса, показывает долю трасс в журнале событий, возможных в данной модели.



Введение

Поддержание корректности бизнес-процесса - одна из важнейших задач при ведении уголовного дела. В последние несколько лет задачи, связанные с управлением процессами, стали особенно популярны. Это произошло, в том числе, на фоне развития такой дисциплины как process mining (PM). PM включает в себя набор техник, позволяющих строить, анализировать и улучшать модели процессов с помощью данных о выполнении процессов, записанных в журналах событий или логах [1]. Логи состоят из трасс, представляющих экземпляры отдельных исполнений процесса. Каждая трасса включает в себя записи о произошедших событиях, а также дополнительную информацию по каждому событию - дату и время, ресурс исполнения, параметры системы или процесса. Все это позволяет проводить анализ процесса с различных точек зрения на него [14].

Техники PM нашли свое применение в мониторинге сложных процессов в различных сферах деятельности. Так, в сфере медицины это клинические процессы в областях онкологии, хирургии, кардиологии, урологии [17],[18]. G. Mapikou и R. Etoundi в своей работе адаптировали -алгоритм для упрощения структуры административных процессов в развивающихся странах Африки [15]. R. Driessen в своей работе проанализировал возможные способы улучшения логистических процессов Министерства обороны Нидерландов [12]. Каждая работа требует индивидуального подхода, основанного на специфике процесса и целях исследования. Целями работы могут быть улучшение процесса, нахождение слабых мест в системе или получение модели процесса на основе имеющегося поведения системы.

Данная работа посвящена анализу логов процесса ведения уголовного дела. Компьютерные технологии уже используются для анализа и улучшения процессов в области криминалистики. На основании данных, собранных из открытых медиа, S. Sathyadevan и S. Gangadharan разработали систему прогнозирования регионов Индии с повышенной опасностью возникновения преступлений. В своей работе они использовали методы машинного обучения [19]. A. Babakura, M. Sulaiman и M. Yusuf использовали классификацию данных для предсказывания категорий преступлений США[3]. Другим направлением работы стала разработка интегрированных систем данных для мониторинга различных органов системы правосудия [8, 11].

Цель проводимого в работе анализа - мониторинг процесса работы с уголовными делами. Выявление аномалий в процессе ведения уголовного дела основывается на анализе рабочего процесса правоохранительных органов. Модель данного процесса регламентирована и допускает гибкость только в рамках, установленных уголовно-процессуальным кодексом. Тем не менее, на практике в процессе возникают отклонения, появляются слабые места [20]. Одно из направлений PM, conformance checking (проверка соответствия модели и логов), содержит подходы, позволяющие проверить, соответствует ли реальное поведение процесса, записанное в журналах событий, модели этого процесса. С помощью проверки соответствия можно выявить аномалии, возникшие в процессе ведения уголовного дела. Причины возникновения данных аномалий соответствуют определенным паттернам, для выявления которых используется кластеризация данных.

Цель данной работы - разработать программу для выявления аномалий в процессе ведения уголовных дел. Для ее достижения необходимо выполнить следующие задачи:

1. Изучить методы проверки соответствия модели бизнес-процесса и журналов событий;

2. Разработать модель процесса ведения уголовного дела в нотации сети Петри;

3. Провести предварительную обработку данные журналов событий для последующего анализа;

4. Адаптировать стандартный метод проверки соответствия для выявления аномалий в процессе ведения уголовных дел;

5. Провести кластеризацию данных журналов событий для выявления паттернов аномалий;

6. Визуализировать результаты, полученные из анализа метаданных.

Особенностью работы является ее релевантность для процесса ведения уголовных дел в Российской Федерации. Указанная особенность возникла исходя из специфики процесса и доступа к данным об уголовных дел.

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



Глава 1. Выявление аномалий в процессах и проведение проверки соответствия модели и журналов событий

Целью данной работы является выявление аномалий в процессе с помощью проверки соответствия модели и реального поведения процесса, записанного в журналах событий. Рассмотрим существующие подходы к а) выявлению аномалий в данных; б) проведению проверки соответствия.

1.1. Выявление аномалий в данных

Аномальное поведение в данных - это паттерны, не соответствующие ожидаемому поведению. Потребность в обнаружении аномалий в данных возросла с увеличением объема данных, усложнением информационных систем и переходом к облачным вычислениям [22]. Однако понятие аномального поведения отличается для различных сфер и задач. Степень отклонения от нормы, которая в приборостроении или медицине будет критической и сигнализировать об аномалии, в сфере финансов может быть лишь небольшим колебанием. Поэтому нет одного универсального алгоритма или решения для всех задач. Исследователями были адаптированы методы из статистики, машинного обучения, data mining, обработки естественных языков, спектрального анализа, теории информации [7, 22]. Наиболее распространенными являются:

· Классификация - обучение классификатора для различения нормального и аномального поведения. Однако этот метод сильно зависит от качества разметки данных

Рисунок 1. Аномалии при классификации данных [7]

· Метод ближайшего соседа - основывается на предположении, которое подразумевает близкое пространственное расположение случаев нормального поведения, тогда как аномалии должны быть выбросами. Недостатки метода ближайшего соседа: а) зависимость точности определения аномальных выбросов от выбранной метрики расстояния; б) неверно интерпретируемое взаимное расположение объектов.

· Кластеризация - используется для группирования похожих объектов в одинаковые кластеры. Кластеризация относится к методам обучения без учителя, что исключает необходимость иметь размеченные данные. В зависимости от выбранного подхода, аномалии при кластеризации могут а) не относится ни к одному из кластеров, б) находиться на периферии кластеров, в) объединяться в меньшие по сравнению с нормальным поведением кластеры [7].

· Статистические методы основаны на законах распределения вероятностей для стохастических моделей (моделей с параметрами, представляющими собой случайные величины [23]). Статистические методы выявления аномалий исходят из предположения, что объекты нормального поведения расположены в области высокой вероятности стохастической модели, в то время как аномалии расположены в областях с низкой вероятностью. Недостатком данного подхода является то, что данные могут не соответствовать какому-либо распределению, соответственно, делать выводы на основе частоты отдельных встречающихся кейсов нельзя.

Кроме указанных подходов, есть методы для определения аномалий с использованием техник process mining. Так, F. Bezerra и J. Wainer в своей работе привели адаптированный метод нахождения показателя alignment для выявления аномальных трасс лога [5]. Метод использует метрику «стоимости включения» (inclusion cost) - количество изменений, которые необходимо внести в модель, чтобы она соответствовала трассам лога. Трассы, соответствующие нормальному поведению системы, формируют модель процесса. Для аномальных трасс стоимость включения в формирование такой модели велика - необходимо сделать большое количество модификаций в модели.

1.2. Проведение conformance checking

Вообще говоря, метод, использованный в работе [5], можно охарактеризовать как «проверка соответствия логов и модели» или conformance checking. Conformance checking - одно из направлений PM, которое можно определить как «выявление и оценивание расхождений между наблюдаемым и моделируемым поведением» [4]. Данный процесс сравнения логов и модели процесса позволяет проводить как глобальную оценку (какой процент трасс, соответствующих реальному поведению системы, удовлетворяет имеющейся модели), так и локальную диагностику (проверка условий и структуры выполнения отдельных участков процесса). В зависимости от специфики модели значения, полученные в результате проведения проверки соответствия, могут иметь различную трактовку. Так, если модель является описательной, то низкое значение «соответствия» указывает на необходимость корректировки модели. Для нормативных моделей такой результат указывает на отклонения в протекании процесса [1].

Существует несколько основных подходов к проведению проверки соответствия:

· “Token replay” - основан на измерении метрики fitness путем воспроизведения логов на модели (replay). В процессе воспроизведения трассы ( производится подсчет количества токенов, использованных (c) и произведенных (p) переходами, а также количества токенов, которые необходимо добавить для выполнения процесса (m), и количества неактивированных токенов (r). Затем по формуле 1 вычисляется значение fitness, показывающее степень воспроизводимости логов моделью (N) [1].

(1)

Значение fitness изменяется от 0 до 1, где fitness = 1 соответствует идеальному соответствию лога и модели.

· Анализ матрицы следов (footprint matrix). Матрица следов - это матрица, показывающая взаимные причинно-следственные связи между событиями процесса. Получить ее из модели можно путем построения всех возможных на данной модели трасс (play-out). Затем для полученных трасс, и трасс из логов строятся матрицы, отображающие все возможные попарные зависимости между событиями в трассах. Матрицы модели и логов сравниваются на предмет соответствия [1].

· Alignment - основан на сравнении трасс из журнала событий и трасс, сгенерированных моделью с помощью play-out. Одна из используемых метрик для этого метода - стоимость включения. Она показывает «расстояние между трассами», то есть минимальное число изменений, которое необходимо внести в одну трассу, чтобы получить другую [21]. Однако данный подход требует больших вычислительных затрат, т.к. модель допускает большое количество альтернативных поведений.

На основе этих подходов исследователями производятся различные модификации, которые учитывают особенности модели или оценивают значение соответствия с разных перспектив, не ограничиваясь перспективой последовательности выполнения действий процесса. Так, F. Mannhardt предлагает усовершенствованный alignment- алгоритм для учета атрибутов записей в логе, таких, как потоки данных, время и ресурсы [14]. Помимо атрибутов, у процесса могут быть ограничения. Для работы с ними была разработана специальная нотация - декларативные модели. При проверке соответствия поведения декларативных моделей следует учитывать в первую очередь налагаемые на нее ограничения - порядок исполнения, количество выполнений и условия срабатывания переходов [6].

1.3. Реализация алгоритмов

Существует ряд программных средств для анализа бизнес-процессов с применением техник PM. Разработан целый фреймворк ProM [24], представляющий собой набор инструментов для анализа процессов в виде плагинов.

Рисунок 2. Фреймворк ProM для анализа бизнес-процессов

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

Помимо готовых программных продуктов есть набор библиотек, предоставляющих возможность для работы с моделями процессов и журналами событий. Наиболее популярная библиотека, pm4py для языка Python, содержит функционал для построения моделей и их визуализации в виде изображений в формате *.svg, анализа различных типов процессов (социальные сети, стохастические сети Петри), проведение conformance checking [25]. Несмотря на большое количество предоставляемых средств для работы с процессами, данная библиотека имеет существенный недостаток - невозможно загрузить уже готовую модель процесса. Однако специфика процесса ведения уголовных дел не позволяет полагаться на автоматическую генерацию модели процесса. Кроме того, необходимо добавить ограничения на срабатывания переходов.

Библиотека PNet, представленная в работе Z. Chau, B. Goh и M. Ling [9], позволяет задавать модель процесса, используя текстовый (естественный) язык вместо программных конструкций. Составные правила переходов определяются с помощью функций. Данная библиотека предоставляет возможности моделирования процесса, однако средства анализа логов в ней отсутствуют.

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

1. Разработать модель процесса ведения уголовного дела в нотации сети Петри;

2. Провести предварительную обработку данные журналов событий для последующего анализа;

3. Адаптировать стандартный метод проверки соответствия для выявления аномалий в процессе ведения уголовных дел;

4. Провести кластеризацию данных журналов событий для выявления паттернов аномалий;

5. Визуализировать результаты, полученные из анализа метаданных.

Выводы по главе 1

В данной главе мы рассмотрели подходы к выявлению аномалий в процессах, а также основные методы проведения проверки соответствия модели процесса и журналов событий. Несмотря на наличие существующих имплементаций алгоритмов анализа бизнес-процессов, специфика данной задачи требует разработки специального подхода к процессу выявления аномалий процесса. Далее во 2 главе будет описан метод для проведения проверки соответствия, основанный на token replay и учитывающий ограничения, налагаемые на процесс ведения уголовного дела. Также будет описан процесс выявления паттернов аномалий на основе кластеризации данных логов.



Глава 2. Метод проверки соответствия с учетом специфики процесса и последующая кластеризация данных

2.1. Особенности процесса, влияющие на выбор метода проверки соответствия

Процесс ведения уголовных дел является строго регламентированным. Правила выполнения операций с уголовными делами записаны в уголовно-процессуальном кодексе РФ. Особенности и ограничения процесса должны быть учтены при проведении проверки соответствия реального поведения процесса, записанного в журналах событий, и модели данного процесса. Кроме того, построение модели процесса в формальной нотации, само по себе являющееся одной из задач данного исследования, также должно быть проведено с учетом специфики процесса.

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

· Уголовное дело, представляющее собой папку с документами, уникально в рамках одного уголовного процесса. Таким образом, в сети Петри не может быть параллельных переходов. Также в идеальной ситуации без аномалий в текущей разметке не может быть более одного токена.

· Всего есть 116 типов событий, которые могут встречаться в журналах событий. Использование их для построения модели невозможно, так как полученная модель не будет удовлетворять критериям простоты (simplicity) и обобщения (generalization) [1]. Другими словами, она будет слишком усложненной. Это будет затруднять дальнейшие исследования. Кроме того, такая детализация излишня при поиске аномалий на отдельных этапах ведения уголовных дел.

· Между некоторыми событиями есть установленные временные ограничения. Совершение действия, выходящего за временные рамки, будет считаться нарушением. Данные ограничения добавляют необходимость анализа с точки зрения временных ограничений на переходы в сети Петри.

· «Нежелательные» действия. Проведение ряда действий является показателем отклонений в процессе, недостаточно тщательного расследования или нежелания работать над делом. Это может быть отражено добавлением весов к переходам для дальнейшего выявления аномалий.

· В процессе работы над уголовным делом могут наблюдаться зацикливания, например, при многократном прекращении и возобновлении дела. Таким образом, при подсчете соответствия необходимо накладывать ограничения на число уникальных срабатываний переходов.

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

2.2. Сеть Петри с атрибутами

В данной работе процесс рассматривается, прежде всего, с точки зрения потока работ. Мы предполагаем, что у нас есть набор действий , которые могут быть выполнены при работе с уголовным делом. Модель процесса описывает, в каком порядке будут производиться эти действия.

Для разработки модели процесса была выбрана нотация сети Петри. Сеть Петри - это двудольный граф, состоящий из позиций и переходов. Позиции содержат токены, распределение которых определяет состояние сети в текущий момент времени [1].

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

Существуют различные расширения сетей Петри, позволяющие моделировать процесс с учетом времени, ресурсов (исполнителей), потоков данных, затрат на выполнение действий. Одним из наиболее используемых являются Petri Net with time and cost (сети Петри с атрибутом времени и стоимостью переходов) [2]. Среди паттернов учета значений даты и времени, встречающихся при моделировании процессов, наибольший интерес в контексте процесса ведения уголовных дел представляют ограничение времени выполнения и поддержка цикличности [13]. Для проверки соблюдения временных ограничений необходимо хранить в модели временные метки, соответствующие как текущему состоянию модели, так и текущему действию (переходу).

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

Таким образом, мы получаем сеть Петри с атрибутами. Приведем ее формальное описание.

:

· конечный набор позиций

· конечный набор переходов

· - набор направленных дуг, соединяющих позиции и переходы

· - присваивает каждой позиции исходный момент попадания в данное состояние

· - присваивает каждому переходу временной интервал для срабатывания

· - присваивает каждому переходу число допустимых срабатываний

· - присваивает каждому переходу вес (стоимость активации перехода)

B (P) - состояния сети Петри, определяемые расположением токенов в позициях.

M ? B(P) - разметка сети Петри (текущее состояние)

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

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

2.3. Взвешенный token-replay

Для определения того, является ли отдельная трасса в журнале событий аномальной, использован метод проверки соответствия, основанный на процессе token-replay (воспроизведение лога на модели). Ниже описан алгоритм воспроизведения одной трассы лога, представляющей собой последовательность событий.

1. function replay_log:

2. current_pos := start

3. count := 0 // счетчик записей в одной трассе

4. while current_pos != finish and count != длина трассы:

5. current_event := отобразить в переход модели (trace[count])

6. if current_event == исходящий переход для current_pos:

7. проверить ограничение времени выполнения для current_event ()

8. активировать переход (current_event)

9. обновить вес трассы ()

10. count++

11. elif есть скрытый переход (hidden) для current_pos:

12. активировать переход (hidden)

13. else

14. добавить отсутствующий (missing) токен

15. активировать переход (current_event)

16. count++

17. обновить current_pos ()

Алгоритм 1 Воспроизведение лога на модели

При воспроизведении алгоритма мы последовательно проходим по всем событиям в логе и пытаемся активировать соответствующие переходы на модели. Если какой-либо из переходов не активен, мы добавляем недостающие токены, что указано в строке 14 алгоритма 1. Однако записи событий в логах находятся на низком уровне абстракций, поэтому мы не можем использовать их все в качестве переходов. В строке 5 мы проводим отображение записей лога в переходы, используемые в модели, для дальнейшей работы с ними. Подробнее процесс отображения логов будет рассмотрен в главе 3. Кроме того, в модели есть несколько искусственных переходов, которые отсутствуют напрямую в журналах событий. Они были добавлены в информационных целях и служат для лучшей читабельности модели. Такие переходы должны игнорироваться при воспроизведении логов. Поэтому при наличии такого скрытого перехода мы его активируем, но не учитываем при общем подсчете активированных переходов (строки 11-12).

При определении значения соответствия рассчитывается значение метрики fitness, которое учитывает количество потребленных и произведенных токенов при активации переходов, а также количество недостающих и неиспользованных токенов. Обновление счетчиков потребленных и произведенных токенов происходит при активации перехода.

1. function активировать_переход (переход):

2. для всех входящих позиций в переходе:

3. забрать токен ()

4. обновить количество потребленных токенов ()

5. обновить текущую разметку()

6. для всех исходящих позиций в переходе:

7. добавить токен ()

8. обновить количество произведенных токенов()

9. обновить дату перехода в позицию ()

10. обновить текущую разметку ()

11. обновить счетчик активированных переходов ()

12. зафиксировать срабатывание в текущем переходе ()

Алгоритм 2 Активация перехода

Кроме обновления счетчиков и атрибутов внутри элементов модели, в процессе выполнения алгоритма 2 происходит обновление текущей разметки. На основании состояния текущей разметки в строке 17 алгоритма 1 обновляется текущая позиция во время воспроизведения трассы.

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

(2)

где - трасса журнала событий,

- модель процесса в нотации сети Петри с атрибутами,

- функция веса активированных переходов,

m - количество недостающих токенов,

c - количество потребленных переходами токенов,

r - количество оставшихся после воспроизведения токенов,

p - количество произведенных переходами токенов.

При отсутствии аномалий в трассе значения соответствия будет равно 1. Значение взвешенного соответствия, меньшего 1, является сигналом к наличию отклонений от установленного хода процесса.

2.4. Кластеризация логов с аномалиями

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

В качестве метрики расстояния между трассами использовано расстояние Левенштейна - минимальное количество операций редактирования, необходимых для превращения одной строки в другую. Данная метрика используется для анализа строк, в том числе, при анализе последовательностей потоков данных информационных систем [10]. Алгоритм кластеризации, использовавшийся в работе, - метод распространения близости (Affinity propagation), который в качестве входных данных использует матрицу схожести между трассами [26].

2.5. Построение модели процесса для определенного паттерна аномалий

В процессе кластеризации аномальные логи были разбиты на кластеры, содержащие наборы трасс, которые относятся к одному паттерну. Для наглядного представления мест возникших аномалий трассы в пределах одного паттерна объединяются в одну модель процесса, которую можно изобразить графически, выделяя слабые места. Такая модель не должна соответствовать строгим ограничениям, так как служит в качестве дополнительного наглядного материала в изучении процесса ведения уголовного дела. Построение модели может быть выполнено с помощью -алгоритма, который предназначен для построения сети потоков работ по журналам событий [1].

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

1. function createModel (аномальные_трассы):

2. transitionList := Получить все уникальные переходы (аномальные_трассы);

3. tStart := Выделить все начальные переходы (аномальные_трассы)

4. tFinish := Выделить все конечные переходы (аномальные_трассы)

5. footpritnMatrix := Получить матрицу попарных отношений переходов, находящихся в отношении прямого следования, отношении «причина-следствие», параллельном отношении и не связанных друг с другом указанными отношениями

6. distSet := Получить все пары наборов переходов, в которых элементы пары соединены позицией

7. places := Получить список всех позиций

8. edges := Связать все переходы с позициями

9. Добавить начальную и конечную позиции ()

Алгоритм 3. -алгоритм для построения модели по журналам событий

Во время выполнения алгоритма 3 мы устанавливаем отношения между переходами в трассах, основываясь на взаимном расположении переходов (строка 5). Отношение прямого следования для переходов a и b: означает, что для трассы существует такое , что и . Отношение «причина - следствие» для переходов a и b: a означает, что из a следует b , но из b не следует a . Отношение параллельности для переходов a и b: || означает, что из a следует b ( и из b следует a ().

Важным шагом измененного алгоритма является процесс получения уникальных переходов в строке 2 алгоритма 3. Уникальными будут считаться как чистый переход {a}, так и переход, содержащий при себе специальный символ {!a}. Это позволит не только построить модель, с учетом специальных символов, но и разграничить аномальное и ожидаемое поведение процесса.

Выводы по главе 2

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



Глава 3. Полученные результаты и их программное представление

3.1. Средства и инструменты для разработки приложения для выявления аномалий в журналах событий и для визуализации паттернов выявленных аномалий

3.1.1. Приложение для оценки соответствия модели и журналов событий

Для разработки модуля для выявления возможных отклонений между журналами событий и моделью процесса ведения уголовных дел был использован язык программирования Python 3.7. Для хранения и предварительной обработки журналов событий использовалась библиотека pandas [27]. Для кластеризации трасс использовалась библиотека scikit-learn [28].

Выбор в пользу языка python был сделан, т.к. это один из наиболее широко используемых в научном сообществе и поддерживаемых языков для работы с данными [16]. Большое количество библиотек, находящихся в свободном доступе, позволяет удобно и быстро проводить операции с большим набором данных.

3.1.2. Приложение для визуализации паттернов аномалий

Разработка интерфейса для визуализации файлов, полученных при выявлении аномалий, была проведена с использованием фреймворка Electron, позволяющего разрабатывать настольные кросс-платформенные приложения с помощью веб-технологий [29], и фреймворка Vue.js [30]. Для отрисовки графов использована библиотека Jointjs [31].



3.2. Модель процесса ведения уголовных дел

Чтобы модель процесса являлась отображением регламентированного процесса ведения уголовных дел, ее построение проведено вручную, а не с использованием автоматических алгоритмов построения моделей. Изначально набор действий, которые могут быть записаны в журнал событий в ходе ведения уголовного дела, состоит из 116 различных событий. Модель, содержащая такое количество переходов, будет слишком детализированной и усложнит проведение дальнейшего анализа. Однако эти события можно сгруппировать по различным этапам процесса ведения уголовного дела. Мы поставили в соответствие каждому событию переход, относящийся к более высокому уровню абстракции. События соответствуют только переходам на модели, поэтому все позиции являются искусственными и носят лишь информативный характер. Кроме того, в модель было добавлено несколько скрытых переходов. Таким переходам не поставлены в соответствия события

из журнала событий, они необходимы для поддержания согласованности модели. Таким образом, модель насчитывает 14 позиций, включая одну начальную и одну конечную позиции, и 34 перехода, 6 из которых являются скрытыми. На рис. 3 представлено графическое изображение полученной модели.

Рисунок 3. Графическое изображение модели процесса ведения уголовных дел в нотации сети Петри с атрибутами

Приведем в табл. 1 описание условных обозначений, использованных при построении модели.

Таблица 1

Условные обозначения, используемые при построении модели процесса

Символ	Описание
	Начальная позиция в модели.
	Позиции в модели. Служат для обозначения текущего состояния, носят информативный характер.
	Финальная позиция в модели.
	Позиции в модели, которые также могут быть финальными. Введены для упрощения модели.
	Переходы в модели
	Скрытые переходы в модели.
	Переходы в модели, которым назначено значение атрибута стоимости.
	Атрибут ограничения времени срабатывания у перехода.
	Атрибут ограничения числа срабатываний у перехода.

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

Таблица 2

Переходы, используемые в модели процесса ведения уголовных дел

Позиция в модели	Наименование позиции	Примеры действий из журнала событий
t1.1	Сообщение о происшествии	· сообщение поступило по телефону; · сообщение поступило нарочным под расписку
t1.2	Обращение в другое ведомство	· материалы, которые поступили из налоговых органов в соответствии с законодательством о налогах и сборах для решения вопроса о возбуждении уголовного дела
t2.1	Закрыть рассмотрение сообщения о преступлении	· приобщено в специальное номенклатурное дело
t2.2	Регистрация сообщения о преступлении	Скрытый переход, нет соответствия в журнале событий
t3.1	Доследственная проверка завершена	Скрытый переход, нет соответствия в журнале событий
t3.2	Передача в другой орган для доследственной проверки	· передано ца в подчиненный орган; · дело передано по ч.6 ст.152 УПК РФ
t4.0	Доследственная проверка продлена	· доследственная проверка продлена
t4.1	Передать сообщение	· передано по подследственности; · передано по подведомственности
t4.2	Отказать в возбуждении УД	· отказано в возбуждении уголовного дела по нереабилитирующим основаниям
t4.3	Возбуждено УД	· возбуждено уголовное дело
t5.1	Отмена отказа в возбуждении УД	· отменено постановление об отказе в возбуждении уголовного дела
t5.1.1	Перевести в сообщения о преступлении	Скрытый переход, нет соответствия в журнале событий
t5.1.2	Возбудить УД после отмены отказа	Скрытый переход, нет соответствия в журнале событий
t5.2	Отмена возбуждения УД	· в связи с отменой постановления о возбуждении уголовного дела в порядке ч. 4 ст. 146 УПК РФ
t5.3	Передать в производство	Скрытый переход, нет соответствия в журнале событий
t5.0	Поступление УД	· в связи с соединением уголовных дел по преступлениям, предусмотренным ст. 186, 187 УК РФ, в одно производство
t5.4	Дело в производстве	· дело изъято прокурором для производства предварительного следствия (без обвинительного акта) по п. 11 ч. 2 ст. 37
t6.0	Дополнительные материалы по делу	· заявление о явке с повинной · появление лица, подозреваемого в совершении преступления
t6.1	Приостановить дело	· дело приостановлено по п. 1 ч. 1 ст. 208 УПК РФ
t6.1.1	Возобновить производство по приостановленному делу	· возобновлено производство по делу, ранее приостановленному
t6.2	Прекратить делопроизводство	· дело (уголовное преследование) прекращено по реабилитирующим основаниям: п. 2 ч. 1 ст. 24 УПК РФ
t6.2.1	Возобновить производство по прекращенному делу	· возобновлено производство по делу, ранее прекращенному
t6.4	Передать дело	· дело передано по подследственности без снятия с учета по ст. 151 УПК РФ
t6.3	Передать дело прокурору	· дело направлено прокурору в порядке ч. 5 ст. 439 УПК РФ · дело направлено прокурору в порядке ст. 220 УПК РФ
t6.3.1	Направить дело вышестоящему прокурору	· дело направлено вышестоящему прокурору в порядке п.3 ч.1 ст. 221 УПК РФ
t7.1	Дело направлено прокурором в суд	· дело направлено прокурором в суд в порядке ч. 1 ст. 427 УПК РФ
t7.2	Прокурор вернул дело	· дело возвращено на дополнительное расследование прокурором в порядке п.2 ч.5 ст. 439 УПК РФ
t7.0	Поступило дело частного обвинения	· заявление потерпевшего или его законного представителя по уголовному делу частного обвинения
t8.1	Дело рассмотрено судом	· рассмотрено судом
t9.1	Вынесения решения суда	· судом принято решение по ч. 1 ст. 443 УПК РФ
t9.2	Суд вернул дело прокурору	· дело возвращено судом прокурору в соответствии со ст. 237 УПК РФ

3.3. Предварительная обработка журналов событий

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

Таблица 3

Фрагмент журнала событий, содержащий записи о процессах ведения уголовных дел

UNIQ_ID	event_date	event_type
1	09.02.2015	устное сообщение о преступлении
1	09.02.2015	приобщено к материалам сообщения
2	08.02.2015	сообщение о происшествии
2	08.02.2015	возбуждено уголовное дело
2	08.02.2015	появление потерпевшего
2	26.03.2015	дело направлено прокурору в порядке ст. 220 УПК РФ
2	15.05.2015	дело направлено прокурором в суд в порядке ч. 1 ст. 221 УПК РФ

В разработанном приложении функция для отображения событий в позиции представлена в классе Matcher. Во время работы программы существует единственный экземпляр данного класса, который хранит в себе все возможные отображения событий, переходов и символов. При инициализации данного экземпляра в память загружается файл с информацией об отображении всех возможных событий в переходы модели и на его основе создается словарь записей.

class Matcher(object):

def __init__(self):

df = pd.read_csv("events_to_transitions.csv", sep=';')

df = df.loc[:, ~df.columns.str.contains('^Unnamed')]

event_list = df['event'].tolist()

transition_id_list = df['transition_id'].tolist()

self.events_to_transitions = dict(zip(event_list, transition_id_list))

Во время воспроизведения трассы происходит обращение к объекту Matcher и он возвращает переход, соответствующий переданному значению события.

def event_to_transition(self, evname):

return self.events_to_transitions[evname]

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



3.4. Символьное представление трасс для кластеризации

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

Таблица 4

Последовательность событий с добавленными символьными пометками слабых мест

	Исходная последовательность переходов	Последовательность переходов с символьными пометками
Несоблюдение ограничений времени	...t4.2t5.3t6.3 ...	...t4.2t5.3фt6.3 ...
Зацикливание	...t5.3t6.2t7.1t6.2t7.1t6.2t7.1t6.2t7.1t8.1...	...t5.3@t6.2t7.14t8.1 ...

3.5. Модуль выявления возможных отклонений на основе журналов событий

Разработанная на языке python 3.7 программа позволяет по входным файлам журнала событий и отображений переходов получить данные о значении соответствия каждой трассы и модели процесса ведения уголовных дел, а также метку кластера, показывающего принадлежность к одному из возможных паттернов аномалий. Входные файлы должны быть в формате *.csv. Пример входного файла журнала событий был представлен в табл. 3. Пример входного файла, содержащего отображения событий в переходы представлен в табл. 5.

Таблица 5

Фрагмент файла с отображениями событий в переходы

event	transition_id	transition_name
сообщение о происшествии	t1.1	Сообщение о происшествии
приобщено в специальное номенклатурное дело	t2.1	Закрыть рассмотрение сообщения о происшествии
отказано в возбуждении уголовного дела за отсутствием события или состава преступления	t4.2	Отказать в возбуждении УД
доследственная проверка продлена	t4.0	Доследственная проверка продлена
сообщение поступило по телефону	t1.1	Сообщение о происшествии
передано по подследственности	t4.1	Передать сообщение

В качестве выходных данных генерируются два файла отчета в формате *.csv, а также два словаря для декодирования символов и переходов в формате *.json. Файл отчета “result.csv”, содержащий информацию о возникновении аномалий при ведении уголовных дел, представляет собой набор трасс журнала событий с соответствующими им значениями соответствия. Фрагмент файла “result.csv” представлен в табл. 6.



Таблица 6

Фрагмент файла отчета, содержащий информацию о наличии аномалий в трассах

UNIQ_ID	event_date	event_type	conformance
1	09.02.2015	устное сообщение о преступлении	1.000
1	09.02.2015	приобщено к материалам сообщения	1.000
2	08.02.2015	сообщение о происшествии	0.875
2	08.02.2015	возбуждено уголовное дело	0.875
2	08.02.2015	появление потерпевшего	0.875

Файл отчета “clusters.csv” содержит информацию о аномальных трассах, включающую последовательность переходов трассы с добавленными символьными пометками слабых мест и метку кластера, указывающего на определенный паттерн аномалий. Пример фрагмента файла отчета “clusters.csv” представлен в табл. 7.

Таблица 7

Фрагмент файла, содержащего информацию о принадлежности аномальных класс к одному из паттернов аномалий

UNIQ_ID	trace	cluster_label
2	qugdѕD	1
3	qug@dx3dDr	0
8	qug!ji	1
11	qjѕugi	1
16	qu	2

Файлы-декодеры “decoder.json” и “events.json” (рис.4), полученные в результате работы данного модуля программы, используются во время визуализации паттернов аномалий для построения моделей, содержащих переходы, идентичные переходам модели процесса ведения уголовных дел, представленной на рис. 3.

Рисунок 4. Структура файлов-декодеров

Диаграмма классов модуля выявления возможных отклонений в процессе ведения уголовных дел на основе журналов событий представлена на рис. 5. Весь описанный функционал реализован в данных классах.

Рисунок 5. Диаграмма классов модуля выявления паттернов аномалий

3.6. Модуль визуализации паттернов аномалий

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

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

Рисунок 6. Модель сети потоков работ для паттерна «Незаконченная трасса»

...