Бакшевникова А.С., Привалов М.В. — Методы анализа метрик исполнения в целеориентированных АСУ

Аннотация

Бакшевникова А.С., Привалов М.В. Методы анализа метрик исполнения в целеориентированных АСУ. Выполнена математическая формализация задачи прогнозирования исполнения в целеориентированной системе, рассмотрены возможные методы анализа метрик. Определены основные преимущества и недостатки использования средств data mining для решения задачи прогнозирования в ЦОАСУ.

Постановка проблемы

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

Цикл управления в ЦОАСУ

Работа ЦОАСУ в целом и каждой из отдельных её составляющих представляет собой непрерывный цикл управления, состоящий из четырёх этапов: наблюдение, ориентирование, решение, действие [1]. Подобный цикл характерен для любого процесса управления в кибернетике. Стадия наблюдения соответствует сбору информации о работе системы; стадия ориентирования — определению проблемы; стадия решения — планированию дальнейших действий, и, наконец, стадия действия соответствует всем операциям системы, выполняемым в соответствии с принятым решением. Сведения о выполнении операций затем передаются подсистеме анализа в качестве наблюдений, что обеспечивает обратную связь.

Работу решающих элементов ЦОАСУ можно представить в виде параметрической программы управления, направленной на поддержание заданных показателей исполнения целей (скорости выполнения, уровня потребления ресурсов и т.д.), которая постоянно корректируется в процессе работы. Система осуществляет управление неизбежно с некоторыми ошибками [2], информация о которых должна поступать в подсистему анализа для поддержания обратной связи. Таким образом, анализ метрик исполнения служит основным инструментом для оперативного планирования и прогнозирования достижения целей.

Планирование и прогнозирование исполнения

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

Задачи прогнозирования в ЦОАСУ сводятся к двум основным типам: прогнозирование времени достижения цели и прогнозирование значений параметров в заданные моменты времени. Математическая модель анализа метрик может быть представлена следующим образом: пусть

P = {p1, p2, ..., pN} — наблюдаемые параметры системы;
N — количество параметров;
YP1..N = {Yp1, Yp2, ..., YpN} — набор временных рядов, описывающих изменение значений параметров P, где
Ypi1..ni = {ypi1, ypi2, ..., ypini} — набор последовательных измерений значений Pi в моменты времени от 1 до ni (в общем случае ni различно для всех Pi);
VP = {VP1, VP2, ..., VPN} — целевые значения параметров, где
VPi = {VPi1, VPi2, ... VPini+h} — целевые значения параметра Pi;
tg = {tP1g, tP2g, ..., tPNg} — целевое время достижения VP;
tr = { tP1r, tP2r, ..., tPNr } — реальное время достижения VP;
tp = { tP1p, tP2p, ..., tPNp } — прогнозируемое время достижения VP.
Ypini+1..hi = {ypini+1, ypini+2, ..., ypini+hi} — прогноз для параметра Pi на hi периодов (в общем случае hi различно для каждого Pi).

Управляющая система стремится уменьшить разницу между прогнозируемыми и целевыми значениями параметров:
в случае прогнозирования значений параметров или
в случае прогнозирования времени достижения цели.

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

Временной ряд (ряд динамики) — это последовательность упорядоченных во времени числовых показателей, характеризующих уровень состояния и изменения изучаемого явления. Временной ряд включает два обязательных элемента: время и уровень ряда — конкретное значение показателя [4], в данном случае значение метрики. Прогнозирование временного ряда заключается в поиске наилучшей в некотором смысле оценки y[N+h] ненаблюдаемой величины y[N+h] (или оценки th времени, необходимого для достижения этой величиной заданного значения) по наблюдениям y[n], n=0,N, то есть как функции этих наблюдений, где

y[N+h] — ненаблюдаемый уровень ряда, соответствующий моменту времени tN+h;
ti — момент времени i;
у — исследуемый временной ряд;
N — количество уровней временного ряда у.

Методы и средства прогнозирования

Задача прогнозирования успешно решается методами математической статистики и средствами интеллектуального анализа данных, среди которых наиболее часто используются нейронные сети (НС) и деревья решений

Прогнозирование в математической статистике представляет собой подбор аналитического выражения y = F(x), наиболее точно описывающего тренд — зависимость уровней ряда от времени, и последующую экстраполяцию ряда для получения предсказанных значений. Ключевым этапом является выбор модели регрессии — вида уравнения, описывающего зависимость. Простейший вид модели — линейная регрессия. На практике также часто используются аппроксимирующие многочлены. Подбор параметров регрессии выполняется, как правило, методом наименьших квадратов. Главным недостатком использования статистических подходов является проблема выбора модели регрессии: недостаточно сложные модели не смогут обеспечить необходимую точность, а модели, обладающие избыточной сложностью, могут оказаться переобученными.

Нейронные сети в настоящее время являются одним из наиболее популярных и стремительно развивающихся направлений исследований в области искусственного интеллекта. Задачи управления и регулирования с предсказанием хорошо изучены и успешно решаются с помощью НС [5].

Задача прогнозирования для НС сводится к задаче аппроксимации — поиска такой зависимости, которая наилучшим образом отражала бы изменение временного ряда во времени. Для прогнозирования применяются однослойные линейные сети с временной задержкой (TDNN), многослойные полносвязные сети прямого распространения (многослойные персептроны), сети на основе радиально-базисных функций (RBF-сети), обобщённо-регрессионные (GRNN-сети), некоторые специфические виды сетей с частичными связями специальной структуры, а также нейросети нечёткого вывода [6].

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

Многослойный персептрон — хорошо изученная модель НС с широкими возможностями, применимая для задачи аппроксимации. Для обучения, как правило, используется метод обратного распространения ошибки. Важным вопросом при использовании многослойных персептронов является определение количества скрытых слоёв и числа элементов в них. Оптимальный выбор архитектуры такой сети зависит от конкретной задачи.

Обобщённо-регрессионная сеть, предложенная Шпехтом [7], предназначена для построения обобщённых (линейных и нелинейных) регрессий. Использование такой сети не требует априорных знаний о виде регрессионной зависимости. Обучение GRNN-сети осуществляется особым образом и не требует итерационной подстройки весов. Более быстрый и простой процесс обучения делает возможным применение GRNN-сети для работы в реальном времени.

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

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

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

В задачах прогнозирования применяются регрессионные деревья решений, оперирующие численными значениями атрибутов. Для их построения используются алгоритмы CART, SLIQ, SPRINT.

Основной сложностью в процессе конструирования дерева является выбор критерия остановки разбиения или отсечения ветвей. Критериями остановки, как правило, служат глубина дерева — максимальное количество уровней или минимальное число примеров, которые содержит конечный узел. Алгоритмов сокращения деревьев достаточно много (cost-complexity, reduced error, MDL-based pruning [8]).

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

Выводы

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

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

Список использованной литературы

1. McElman, C. From Buttons to Bits — Achieving Level 3 Integration. Paper 4383, APCOM 2009 conference, Vancouver BC, Oct. 2009. / C. McElman, S. Seroukhov // [Электронный ресурс]. — Режим доступа: www/URL: http://www.mmsi.com/files/download/TechPapers/McElman_Seroukhov_APCOM_2009.pdf.
2. Бесекерский В.А. Теория систем автоматического управления. / В.А.Бесекерский, Е.П.Попов — СПб. : Профессия, 2003 p. — 751 с.
3. Саати Т. Аналитическое планирование. Организация систем; пер. с англ. / Т. Саати, К. Керис — М. —: Радио и связь, 1991 p. — 224 c.
4. Чураков Е.П. Прогнозирование эконометрических временных рядов: Учеб. пособие / Чураков Е.П. — М. : Финансы и статистика, 2008 г. — 208 c.
5. Хайкин С. Нейронные сети: полный курс, 2-е издание.; пер. с англ. — М. : Издательский дом "Вильямс", 2006. — 1104 с.
6. Рутковская Д. Нейронные сети, генетические алгоритмы и нечёткие системы; пер. с польск. И.Д.Рудинского. / Рутковская Д., Пилиньский М., Рутковский Л. — М. : Горячая линия-Телеком, 2006. — 452 с.
7. Specht D.F. A General Regression Neural Network / D.F.Specht // IEEE Trans. on Neural Networks. — 1991. — 2. — №6.
8. Mehta M., Rissanen J., Agrawal R. MDL-based Decision Tree Pruning / M.Mehta, J.Rissanen, R.Agrawal // Proceedings of the 1st International Conference on Knowledge Discovery and Data Mining. Montreal, Canada. — 1995. — P. 216–221.