автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.10, диссертация на тему:Структурно-классификационные методы анализа и прогнозирования в социально-экономических системах управления

Федеральное государственное бюджетное учреждение науки Институт проблем управления им. В. А. Трапезникова Российской академии наук

УДК 338.24.57

На правах рукописи

0050120&I

ДОРОФЕКЖ ЮЛИЯ АЛЕКСАНДРОВНА

СТРУКТУРНО-КЛАССИФИКАЦИОННЫЕ МЕТОДЫ АНАЛИЗА И ПРОГНОЗИРОВАНИЯ В СОЦИАЛЬНО-ЭКОНОМИЧЕСКИХ СИСТЕМАХ УПРАВЛЕНИЯ

Специальность: 05.13.10 - «Управление в социальных и экономических системах»

АВТОРЕФЕРАТ диссертации па соискание учёной степени кандидата технических наук

1 О МАО ?П'|?

Москва 2012

005012057

Работа выполнена в Федеральном бюджетном государственном учреждении науки Институте проблем управления им. В.А. Трапезникова Российской академии наук (ИПУ РАН)

Научный руководитель: - доктор технических наук, профессор

Мандель Александр Соломонович

Официальные оппоненты: - доктор технических наук, профессор

Афанасьев Валерий Николаевич

Защита состоится «29 » марта 2012 г. в 14 часов на заседании Диссертационного Совета Д 002.226.02 при ИПУ РАН по адресу: 117997, Москва, ул. Профсоюзная, 65.

С диссертацией можно ознакомиться в библиотеке ИПУ РАН.

- доктор технических наук, профессор Сидельников Юрий Валентинович

Ведущая организация:

Федеральное бюджетное государственное учреждение науки Институт системного анализа Российской академии наук (ИСА РАН)

Автореферат разослан «_»

2012г.

Ученый секретарь Диссертационного Совета Д 002.226.02, к.т.н.

В.Н.Лебедев

Общая характеристика работы

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

В настоящее время разработано множество методов и алгоритмов, предназначенных для анализа, совершенствования, а также для прогнозирования базовых параметров функционирования сложных систем управления. Для подобных систем анализ и прогнозирование точных значений параметров (или их вероятностных характеристик), определяющих функционирование объектов в составе системы, становится чрезвычайно сложным, а в некоторых случаях практически невозможным. Необходимо отметить, что тематика классификационного анализа данных и прогнозирования широко развита как в России, так и за рубежом. Помимо одной из ведущих в мире школы М.А.Айзермана (Э.М.Браверман, Е.В.Бауман, И.Б.Мучник), большой вклад в эту область внесли следующие учёные: Ю.И.Журавлёв, Я.З.Цыпкин, К.В.Рудаков, Н.Г.Загоруйко, М.И.Шлезингер, В.А.Ковалевский, В.А.Якубович, Ю.И.Неймарк, С.АЛйвазян, В.М.Бухштабер, В.В.Моттль, С.Д.Двоенко, Б.Г.Миркин, Ь.гааеЬ, Е.ЛозепЫай, Е^ску, .Г.С.Вегаек, К.Э.Ри, С.Ва11, Б^Пеу и др.

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

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

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

• создание методологии и разработка алгоритмов структурно-классификационного анализа сложно организованных данных;

• создание структурных методов прогнозирования в задачах исследования сложных социально-экономических систем управления;

• компьютерное моделирование разработанных алгоритмов и процедур при решении как модельных, так и прикладных задач.

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

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

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

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

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

экономического развития субъектов РФ; разработка системы мониторинга и оценки эффективности ЖКХ крупного города; задача корректировки (сглаживания) оценок показателей экономической активности по субъектам РФ в условиях малых выборок; структурно-классификационный анализ пульсового сигнала лучевой артерии в задачах медицинской диагностики.

Связь с плановыми научными исследованиями. Работа выполнена в рамках плана фундаментальных исследований ИПУ РАН: КП №2413/07, Тема 4 «Развитие структурно-системного подхода в теории экспертного и классификационного анализа для анализа и решения крупномасштабных слабо формализуемых задач» (2007, 2008, 2009 гг.), КП№3111, Тема 4.2. «Разработка и исследование э ксие ртно- югассификационных н экспертно-статисгических методов интеллектуального анализа данных, распознавания образов, структурного прогнозирования и принятия решений в условиях неопределённости» (2010, 2011 гг.); при поддержке грантов Российского фонда фундаментальных исследований №№ 08-07-00347, 09-0700503,10-07-00210,10-07-00027, 11-07-00735,11-07-13137-офи-РЖД. Основные положения, выносимые на защиту.

1. Методология структурно-классификационного анализа и прогнозирования для сложных систем управления.

2. Алгоритмическое обеспечение задач структурного анализа и прогнозирования сложно организованных данных.

3. Методология имитационного моделирования и проверки эффективности разработанных алгоритмов и процедур.

4. Программно-алгоритмический комплекс структурно-классификационного анализа сложно организованных данных.

5. Результаты использования разработанных алгоритмов и процедур при решении ряда прикладных задач.

Апробация работы. Основные результаты диссертационной работы докладывались на семинарах ИПУ РАН, МГИЭМ (ТУ), на общемосковском семинаре «Экспертные оценки и анализ данных» (2007 - 2011); на 19 международных и 9 всероссийских конференциях, в том числе: Международная конференция по проблемам управления (МКПУ, 2006, 2009); «Интеллектуализация обработки информации» (ИОИ, 200б, 2008, 2010); «Управление развитием крупномасштабных систем» (MLSD, 2007 - 2011); «Когнитивный анализ и управление развитием ситуаций» (CASC, 2007, 2009, 2011); «Теория активных систем» (TAC, 2007, 2009,2011); «Иннова-тика» - 2006, 2007; «Автоматизация в промышленности» - 2009, Симпозиум IFAC - 2009; «Математические методы распознавания образов» (ММРО-15, 2011); «Проблемы управления и моделирования в сложных системах» (ПУМСС, 2009); «Управление большими системами» (УБС, 2008-2011).

Публикации. По теме диссертации имеется 36 основных публикаций, из них - 14 в изданиях, рекомендованных ВАК.

Объём и структура работы. Диссертационная работа состоит из введения, четырёх глав, заключения, списка литературы и четырёх приложений. Объём текста диссертации составляет 193 страницы, включая 16 иллюстраций и 18 таблиц, список литературы включает 146 наименований.

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

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

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

В разделе 1.2 поставлена задача структурно-классификационного анализа и прогнозирования сложно организованных данных.

Постановка задачи. Пусть исследуемая система состоит из п объектов, каждый из которых характеризуется набором из к параметров. Изучается поведение этого множества объектов в дискретные моменты времени. Вводится в рассмотрение ^-мерное пространство параметров X, в котором у'-ый объект в момент времени ? представляется точкой *.(0 = С*У)(0>*;г)(0>"->*^,(0) ■ Упорядоченная совокупность точек хДг,),...,xj(tm) является известной частью траектории, характеризующей

динамику у-го объекта.

В большинстве приложений для принятия управленческого решения в момент времени 1т используется совокупная информация об известных траекториях каждого объекта и прогноз значений х]{1т + 1),у =1,...,и. При этом, как правило, информация по каждому объекту рассматривается независимо от остальных. Однако для многих прикладных задач требуется знать не точные значения параметров-характеристик в моменты времени ... ,/„, и прогнозировать значения в момент /т+1, а знать (и прогнозировать) лишь класс, к которому принадлежит (будет принадлежать) этот объект в соответствующие моменты времени в рамках некоторой структуры (классификации) множества объектов изучаемой системы. Основу предлагаемого подхода составляет процедура выявления структуры объектов, входящих в исследуемую систему. Предполагается, что вектор значений параметров ху(?) достаточно полно характеризует состояние у-го

объекта в момент времени /. Это означает, что топология взаиморасположения точек х,(1),...,хя(1) в пространстве Xотражает реальную структуру исследуемого множества объектов. Тогда в задаче структурного прогнозирования необходимо спрогнозировать номер класса (тип объекта), к которому будет относиться каждый объект в момент времени /(Л+1.

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

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

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

Алгоритм т-локалыюй оптимизации. Вначале рассматривается алгоритм 1-локальной оптимизации. Пусть задано некоторое начальное разбиение Я0 точек классифицируемой выборки х,,...,хп. Алгоритм итерационный, на каждом шаге рассматривается одна точка из «зацикленной» исходной последовательности. На каждом шаге текущая точка х} относится к тому классу, значение критерия 3 для которого, будет больше (если эти значения равны, то точка относится к классу с меньшим номером). Алгоритм заканчивает работу, если на некотором цикле среди точек хи...,хП не будет сделано ни одной «переброски» точки из класса в класс.

Алгоритм т-локалыюй оптимизации - это поэтапное применение к исходной выборке процедуры ^-локальной оптимизации, 5 = 1т/и. На 5-м этапе на каждом шаге происходит пробная «переброска» из класса в класс 5 точек. Подсчитывается значение критерия 3 до и после «переброски». Принадлежность каждой из 5 точек к классу либо остаётся неизменной (3 до «переброски» больше, чем после), либо меняется на другой класс - в противном случае. Разработано правило для автоматического выбора максимально возможной глубины перебора Доказана теорема о сходимости этого алгоритма за конечное число шагов к локальному максимуму критерия 3. Разработан эвристический алгоритм сокращённого перебора, который на каждом шаге для пробной «переброски» использует точки в определённом смысле ближайшие к границе между классами.

В диссертации рассмотрен специально выделенный одномерный случай алгоритма т-локальной оптимизации {к - 1). Одномерный случай

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

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

= * О)

1 + акр(х,у)

где а и р - настраиваемые параметры алгоритма. Средняя близость точек

2 "

в классе определяется как: К(А.,А^ =-,■*,), где К{хпх)

и, (и,-

определяется формулой (1), и,- - число точек в классе А.. Тогда критерий J] определяется как:

Л (2)

¿=1 п

Во многих задачах объекты по самой постановке задачи могут относиться к разным классам с различной степенью «достоверности». Для таких случаев в диссертации был разработан вариант алгоритма т-локалъной оптимизации в размытой постановке.

Алгоритм выбора информативных параметров. Классификация по всем исходным параметрам не всегда приводит к желаемым результатам. Поэтому классификацию объектов обычно проводят не в исходном пространстве, а в пространстве наиболее существенных (информативных) параметров, имеющем значительно меньшую размерность. Для выбора информативных параметров в диссертации предлагается использовать результаты их структуризации. Чтобы отличать структуризацию объектов и параметров, будем говорить о классификации объектов, но о группировке параметров. Для группировки параметров также предлагается использовать алгоритм т-локалъной оптимизации. Для формулировки критерия качества группировки необходимо ввести меру близости между параметрами (случайными величинами) х и у. В качестве такой меры в диссертации предложено использовать коэффициент ковариации (совпадающий с коэффициентом корреляции для нормированных параметров х и у), который обозначается через соу х у = (х,у), здесь это - скалярное произведение случайных величин хну. Критерий качества группировки определяется следующим функционалом: = £ Х(*(,)>*(/))2, где .у - число

групп разбиения. Этот функционал полностью аналогичен функционалу

(2), который используется как критерий качества классификации объектов. В результате применения алгоритма т-локальной оптимизации к исходным k параметрам получается их разбиение на заданное число групп s, а также значения факторов для полученных групп. Факторы - нормированные аналоги центров классов при структуризации объектов. Набор информативных параметров состоит либо из факторов групп (если имеется их удовлетворительное содержательное описание), либо из такого подна-бора исходных параметров, каждый из которых является ближайшим (в определённом выше смысле) к фактору в соответствующей группе.

Алгоритм выбора числа классов. Для выбора числа классов в диссертации разработана специальная экспертно-компьютерная процедура. Сначала эксперт оценивает диапазон (Vmin,rmaJ), в пределах которого находится искомое число классов. С помощью алгоритма m-локальной оптимизации проводится разбиение анализируемого множества объектов на гми)> гтш + Ь ■ • •, гтах классов. Качество каждой из полученных классификаций оценивается с помощью критерия

J,=J,-qJ2> (3)

где J, - средняя (по классам) мера близости точек, принадлежащих одному и тому же классу, вычисляется по формуле (2); q - свободный (настраиваемый) параметр алгоритма; J2 - средняя мера близости классов,

1 г

определяемая соотношением: J2 =---Здесь и,-

Г - 1 ,=1 j>i п

число точек в классе Ап а величина K(AnAj) - мера близости классов Ап А. - вычисляется по формуле: К(АпАЛ = ——£ Y к(хпх), где

и, rij xreaj

K(xltxp) определяется формулой (1). В итоге получается последовательность J3{rmj!i),... ,Ji(r.Формально в качестве оптимального можно выбрать такое число классов г , которое соответствует экстремальному значению критерия (3). Если полученное гор1 не удовлетворяет

эксперта, то используется процедура экспертной коррекции, описанная в разделе 2.1.4.

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

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

9

адаптивный алгоритм классификационного анализа с оптимизацией числа выбираемых классов. Основная идея разработанного алгоритма состоит в том, что оптимизация по числу классов проводится не единожды (и в дальнейшем не меняется), а производится на каждом шаге алгоритма для всех моментов времени в пределах диапазона Т стационарности, выбираемого экспертным путём. В первый же момент времени вне этого диапазона система «перезагружается» - все предыдущие результаты отправляются в архив, структуризация проводится заново как для момента времени ь. Разработан вариант адаптивного алгоритма, когда такой перерасчёт производится в пределах скользящего окна ширины Т.

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

Метод структурной группировки объектов. Идея предлагаемого метода состоит в том, что для повышения надёжности оценки исследуемого показателя производится усреднение не по времени, а по ансамблю объектов мониторинга. Другими словами, в одну выборку объединяются выборки, полученные в одном и том же месяце, но для нескольких объектов, близких (в определённом смысле) по динамике исследуемого показателя. Этот метод для краткости называется методом группировки объектов. В диссертации метод группировки объектов описан как метод оценки исследуемого показателя у для ¿-го объекта в £-ом месяце текущего года. Этот объект называется /-эталонным, а /с-ый месяц - расчётным. Метод включает 3 этапа:

Этап 1. Производится сглаживание помесячных данных мониторинга /-эталонного объекта, для чего используется процедура трёхточечного скользящего среднего.

Этап 2. С помощью разработанного в диссертации алгоритма /эталонной классификации формируется класс объектов, близких (в определённом смысле) к /-эталонному объекту по динамике исследуемого показателя. Выборки вошедших в этот класс объектов для каждого момента времени из рассматриваемого диапазона мониторинга объединяются, то есть эти объекты рассматриваются как один виртуальный объект, ассоциируемый с /-эталонным объектом.

Этап 3. На базе объединённых выборок для виртуального объекта с помощью процедуры масштабирования находится искомая оценка исследуемого показателя для /-эталонного региона по состоянию на расчётный месяц.

В разделе 2.3 описаны разработанные в диссертации алгоритмы построения «хорошо интерпретируемых» классификаций. Для того чтобы результаты классификации можно было использовать в практических задачах, важно то, насколько эта классификация удобна для интерпретации в содержательных терминах. В этом разделе описаны три алгоритма построения хорошо интерпретируемых классификаций - покоординатной, спрямляющей, а также содержательно-экспертной классификаций. Дня алгоритмов покоординатной и спрямляющей классификаций множество значений каждого параметра разбивается на небольшое число диапазонов. При этом классификация фактически задаётся набором границ этих диапазонов. Как только границы диапазонов определены, каждый объект получает описание в виде позиционного кода, где число позиций равно числу параметров. Классом в такой классификации является совокупность объектов с идентичными кодами. Причём, если покоординатная классификация осуществляет для каждого параметра независимое от других разбиение на заданное число диапазонов (такая классификация является сочетанием одномерных классификаций), то спрямляющая классификация строится как аппроксимация некоторой многомерной автоматической классификации. Иногда возникает ситуация, когда каждый из имеющегося множества объектов, подлежащих классификации, задан своим названием и содержательным описанием. Кроме того, экспертным путём задана, так называемая «содержательная» классификация, которая определяется названиями и содержательным описанием классов. Требуется по этой информации о заданном множестве объектов провести их классификацию. В работе предложен алгоритм содержательно-экспертной классификации дая решения подобных задач.

В разделе 2.4 описана разработанная в диссертации методика формирования тестовых массивов. Там же приведены результаты компьютерного моделирования разработанного в диссертации комплексного алгоритма структурного анализа данных на тестовых данных. Основное внимание при моделировании обращалось на влияние выбора свободных параметров потенциальной функции (1), основных показателей структуры тестового массива (размер класса, расстояние между классами и др.), а также уровня шума на качество итоговых результатов работы алгоритмов. Оказалось, что выбор основных параметров потенциальной функции (Яср, а и р), сделанный в соответствии с рекомендациями, данными в диссертации, приводит за 2-3 итерации к таким значениям этих параметров, которые обеспечивают «хорошие» результаты классификации. А именно, -соответствие оптимального числа классов «истинному», а также низкий процент ошибок при классификации. Оказалось, что качество классификации практически не меняется при существенном отклонении значений параметров потенциальной функции от «наилучших» (т.е. полученных в результате вышеописанных рекомендаций). Это свидетельствует о высо-

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

Отметим, что в первой серии моделирования расчёты проводились в отсутствии шума. Вначале анализировалось влияние значения параметра q из выражения (3) на ropt, и его соответствие «истинному». Оказалось, что

наилучшие результаты достигаются при q = 2. Поэтому, в последующем значения параметра q фиксировались на этом уровне. Для 45 различных тестовых материалов (число объектов изменялось от 200 до 700, число параметров - от 10 до 50, число классов - от 5 до 10, отношение максимального и минимального диаметра классов - от 1,2 до 2,5) в широком диапазоне изменения параметров потенциальной функции ( Rcp от 300 до 850, р от 2 до 6), число ошибок для всех вариантов было равно 0, и число классов ropt совпадало с «истинным». Эти результаты свидетельствуют о

высокой эффективности как предложенных алгоритмов, так процедур и рекомендаций настройки свободных параметров. Вторая серия моделирования связана с влиянием шума е на результаты работы предложенных алгоритмов. Оказалось, что при малом уровне шума, не превосходящего значения б =0,1, число ошибок классификации не превышает 3-5%. При среднем уровне шума порядка е= 0,15 число ошибок классификации составляет величину 7-10%. При существенном уровне шума (е= 0,25) число ошибок увеличивается до 14-18%. В этой же серии модельных экспериментов исследовалось влияние уровня шума на работу алгоритма выбора «оптимального» числа классов - гор1. Вплоть до значения е= 0,15 значение ropt совпадало с «истинным» числом классов, и только при £ = 0,25 число ropt отличалось от «истинного» на 1-2 единицы. Это является хорошим результатом для такого высокого значения уровня шума.

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

Раздел 3.1 посвящен разработанному в диссертации алгоритму структурного прогнозирования.

Формальная постановка задачи структурного прогнозирования. В момент времени t\ с помощью комплексного алгоритма структурного анализа данных производится структуризация п точек в пространстве X на г классов, каждый из которых и характеризует определённый тип объекта. Вводится понятие модели (эталона) класса а,(/), i = \...,г (чаще всего это центр класса). Для каждого объекта кроме принадлежности к классу вычисляются расстояния до эталонов всех классов Rv(t)', i = l,...,r;

j - 1,...,и. В момент времени t2 каждая точка xy.(i2) с помощью одного из

алгоритмов распознавания образов с учителем относится к тому или иному классу в рамках классификации, полученной на первом шаге. В работе

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

максимальна, то есть: К(х,{1г),А,) = шахЛ^(хAt2),At), i = 1 ,...,r,j = 1 ,...,п.

1 i

В качестве меры близости используется величина

К(хпА,) = — X! , где п, число точек в классе А,, К(х,у) - по-

П, xfiA,

тенциальная функщм (1). После того, как определена принадлежность всех точек к тому или иному классу, производится пересчёт эталонов a;(i2), i = l,...,r. Для каждой точки с предыдущего шага пересчитываются, а для каждой новой точки вычисляются расстояния до новых эталонов R(Xj(t2),ai(t2y), i = 1, 7=1,...,и. Такая процедура выполняется для

всех т моментов времени. В итоге для каждого объекта получается последовательность (траектория) из т позиций. В каждой позиции находится (г + 1) число, первое из которых - это номер класса, к которому относился этот объект в соответствующий момент времени, а последующие числа -это значения расстояний до центров классов в тот же момент времени. Требуется прогнозировать номер класса, к которому будет относиться каждый объект в момент времени tmA.

Алгоритм структурного прогнозирования. В качестве прогнозной модели доя каждого объекта используется марковская цепь с г состояниями. На каждом шаге рассчитываются элементы матрицы переходных вероятностей Р - I; = i = 1,..., г . Разработан алгоритм пересчёта на каждом шаге соответствующих переходных вероятностей psi с использованием информации о значениях расстояний до центров классов и

г

условия нормировки Y.P¡, -1 ДОя всех 7=1,...,п. Алгоритм работает i=i

следующим образом. На s-м шаге элементы матрицы переходных вероятностей модифицируется при помощи следующей процедуры. Введены следующие обозначения; Д« = Д(хД ),а,(гл)); AR™ = - R(f;

^j(j-I) _ ^j(s)

AR'j.' = ■ Если j-я точка совпадает с эталоном некоторого клас-

са, то вероятность для этой точки остаться в этом классе равна единице, а вероятность перехода в другой класс равна 0. Для случая, когда j-я точка не совпадает с эталоном одного из классов и соответственно i?'.?5 * 0,

происходит модификация всех переходных вероятностей по следующей схеме:

jl / Pji r.

-p^sign{ARf) AR(;> , (4)

где: sign(z) =

1, если z > 0, -1, если z < 0

ay- нормирующий множитель, опреде-

ляемый условием нормировки переходных вероятностей =1:

У =

/

1 + sign(ARf) 2

\

1 +

-p^sign(AR^) ARf

v

/

Введение в выражении (4) величины sign(ЛR{j1¡') вызвано необходимостью производить различными способами модификацию переходных вероятностей для случаев увеличения и уменьшения расстояния от точки хД^) до эталонов классов на 5-м шаге.

зуется для прогнозирования принадлежности объекта к тому или иному классу. На практике обычно используется не рандомизированная, а байесовская схема, когда объект относится к тому классу ¿0, для которого рА = max р;1. В случае равенства переходных вероятностей pyi для прогнозируемого объекта для двух или нескольких классов, он относится к классу с наименьшим номером. Разработана модификация процедуры прогнозирования, когда классификация объектов задаётся заранее (например, экспертным путём) и в последующем остаётся неизменной. Разработан также вариант алгоритма «с памятью», где используются данные только об s прошлых состояниях множества объектов (.? - глубина памяти).

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

Р = ||ру,| ,j = 1, -.., п, i = 1,..., г. Разработан алгоритм пересчёта на каждом

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

Так построенная матрица переходных вероятностей Р = |j/?,..j| исполь-

число классов для классификации на каждом шаге, г, e(rmin,rniM). Построенная при помощи этого алгоритма матрица переходных вероятностей I] используется для прогнозирования принадлежности объекта тому или иному классу. На практике, как и ранее, используется байесовская схема.

В разделе 3.3 разработаны оптимальные алгоритмы кусочно-линейной аппроксимации для задач структурной идентификации и структурного прогнозирования. Для многих объектов управления проблема прогнозирования может быть сформулирована как проблема восстановления модели функционирования объекта (входо-выходной зависимости). В диссертации были разработаны методы кусочной аппроксимации сложных зависимостей, существенно использующие алгоритмы автоматической классификации. Постановка задачи описывается на примере статической модели у = F{x) объекта как модели зависимости выходного показателя у от вектора входных показателей x = (xm,...,xlk))eX cRk. Такая модель строится по выборке (>', ,х, )= {у, ,x?},...,x(k))e X - Ri+1 из п векторов размерности (/сН), получаемых в режиме нормальной эксплуатации исследуемого объекта. Предлагаемый далее подход без особых изменений может использоваться также для идентификации динамической модели объекта y(t) = F[x(t),x(t-\),x(t-2),...,x(l-m)], где т - «глубина памяти» динамической модели.

Многие сложные объекты могут функционировать в нескольких «режимах», существенно различающихся своими моделями у =Fj(x), где j - индекс «режима». При этом j-му режиму соответствует определённая область Hj в пространстве входных параметров X. Далее функциональный преобразователь F(x) (идентифицируемую модель) будем рассмат-

r fl, еа/шхеЯ,

ривать в виде: F(x)= Z£j(x)F,(x) , еДх) = 1 , где е (х) -

J-1 1 1 ' еслихеНj

характеристические функции областей Hj.eX, \JHj -X, г — число областей. В качестве оценок локальных моделей F. (х) чаще всего используются достаточно простые функции. По этой причине далее рассматриваются только кусочно-линейные представления идентифицируемой модели.

Общая схема идентификации кусочно-линейной модели сложного объекта состоит в следующем. Пространство Xc.Rk разбивается на г

классов (Я,,...,ЯГ). Затем для каждого класса Н1 находятся такие оценки ^ £

локальной модели Ft{x) = + ¿6;<J)x(/), для которых минимизируется

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

г

./ = -/ = -Е ЕСУ, + ■ Этот функционал является частным

/=1 х,чН<

случаем функционала классификационного анализа общего вида: АН, Л) = 11 К(х,а,)(р <7г,(х)).

хсХ /=1

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

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

На первом этапе, используя выборку хи ..., хм, пространство X разделяется на области Я],у = 1, ..., I, где число / значительно больше, чем «реальное» число областей г . Каждая из этих областей содержит только «близкие» наблюдения х]- (в соответствии с выбранным критерием). Соответствующую классификацию будем обозначать через # = (#,,...,#,). Используется стандартный критерий качества классификации - среднеквадратичное отклонение точек в областях II} от соответствующих эталонов

1

а : 3 — Е Е ~а¡У ■ Для разбиения пространства Хна области Н , в

диссертации использовался комплексный алгоритм автоматической классификации. На втором этапе по выборке (у,, х,) = {у,,х((|),...,) строятся локальные регрессионные модели х). Затем производится пошаговое объединение областей следующим образом. На каждом шаге находится ближайшая пара областей Я, и Щ- кандидатов на объединение, для чего 16

используется мера близости К(Н„ Щ областей Я, и Нг Затем проверяется гипотеза: «локальные модели аппроксимации Р](х) и /^(х) в областях Я; и //у статистически неразличимы». Для верификации этой гипотезы в диссертации используется статистика Фишера-Чоу

к, н,

I ^ + 2

Р(к,М, + - 2*) =-=!-/"гм V5, = ск*,) - Зад.

{ы,+М;-2кУк £5гр+£8?

_/1=1 ' м

х,еВ„ 5, =[><*,)-£(*,)], 8, ,*, еВ, , где

А - размерность пространства X; и число наблюдений, попавшие в

области Я( и Я,- соответственно, ^¡(х) - локальная модель аппроксимации

в объединенной области Я,иЯ„ г5 - отклонение фактических данных по выходному показателю от локальной модели.

Если ^ < ^о, тогда гипотеза верна - уровень значимости), в противном случае гипотеза отвергается. Найденные таким образом области объединяются в новую область Я, = Я, и Я;, если Р < /"о, т.е. гипотеза «локальные модели аппроксимации ^(х) и /^(х) в областях Я; и Я,- статистически эквивалентны» верна. Новая локальная модель аппроксимации в объединённой области Я,, обозначается как = Процедура

повторяется для всех областей Я; и Я,- (или Я, и Я,.). В результате, возможно, получатся новые области Н. и, соответственно, новые локальные модели аппроксимации Г, (х), которые в совокупности, после окончания процесса объединения областей, составляют итоговую кусочно-линейную модель.

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

В разделе 4.1 подробно описан созданный на базе разработанных алгоритмов и процедур программно-алгоритмический комплекс (ПАК) структурно-классификационного анализа сложноорганизованных данных. Приведена общая блок-схема ПАК, а также подробно описаны входящие в её состав блоки.

В разделе 4.2 разработанные методы использовалась для сравнительного анализа социального развития субъектов Российской Федерации (47 показателей для 79 регионов за 3 года). С помощью разработанного алгоритма выбора информативных параметров было отобрано 6 информативных показателей, ближайших к факторам групп: среднедушевой доход, доля оплаты труда в среднедушевом доходе, превышение доходов над

расходами, число пенсионеров на 1000 чел. населения, уровень безработицы, общий объём финансовой помощи на душу населения. В результате классификационного анализа в шестимерном пространстве этих показателей было получено 7 классов регионов. На базе этой классификации с использованием разработанных в диссертации алгоритмов хорошо интерпретируемой классификации был построен рейтинг социального развития регионов для каждого из 3 лет, проанализирована динамика рейтингов регионов по основным показателям. При построении рейтингов по двум показателям (уровень безработицы и среднедушевой доход) возникает проблема многокритериальности, которая в диссертации разрешалась с помощью привлечения специальной экспертной процедуры. Кроме того, каждый рейтинговый класс получил интегральную характеристику по всем основным показателям. На этом же материале использовался разработанный в диссертации алгоритм структурного прогнозирования. Результаты использования полученной прогнозной модели был оценён экспертами-предметниками как очень хорошие.

В разделе 4.3 рассмотрена задача разработки системы мониторинга и оценки эффективности функционирования ЖКХ крупного города (на примере города Москвы). На базе разработанных в диссертации алгоритмов была разработана методика, предназначенная для: структуризации исходной информации, формирования критериев эффективности, оценивания административных подразделений города по этим критериям, представления полученных таким образом оценок в сжатой и наглядной форме руководству городского хозяйства для принятия управленческих решений. Для разработки конкретных разделов методики в Москве была проведена экспертиза существующей системы управления ЖКХ, которая показала, что существующая система управления ЖКХ может быть описана стандартной моделью управления динамическим объектом с обратной связью в условиях сильного влияния человеческого фактора. Оказалось, что наиболее приемлемым с точки зрения баланса информативности (для оценки эффективности системы управления) и трудоёмкости сбора информации является уровень района города. Был определён перечень показателей (около 60 первичных показателей) и источников их сбора. В результате применения разработанных алгоритмов был сформирован список агрегированных информативных показателей - факторов, а также были оценены их значения в выбранных балльных шкалах. Была разработана система поддержки принятия решений (СППР) для формирования критериев оценки эффективности функционирования системы ЖКХ города. В настоящее время с использованием результатов структурно-классификационной экспертизы проводится проработка критериев, модели и научно-обоснованной методики оценки эффективности ЖКХ г. Москвы на уровне района, административного округа и города в целом.

В разделе 4.4 рассмотрена задача корректировки (сглаживания) оценок показателей экономической активности населения по субъектам РФ в

условиях малых выборок. В настоящее время по вопросам экономической активности, занятости и безработицы объём месячной выборки обеспечивает представительные данные только в целом по РФ и некоторым крупным (по численности населения) субъектам РФ. Однако для эффективного мониторинга требуются оценки для каждого конкретного месяца по каждому субъекту РФ, при этом в оценках должны быть учтены колебания, вызванные фактором сезонности, эффектом размещения выборки. Разработанный в диссертации метод структурной группировки (МСГ) объектов использовался для сглаживания показателей экономической активности населения, безработицы и занятости по субъектам РФ, формируемых по итогам месячных обследований населения по проблемам занятости. В результате применения этого метода для каждого из 83 регионов РФ в период начиная с сентября 2010 года по октябрь 2011 года были проведены расчёты ежемесячных оценок значений следующих показателей: численности экономически активного населения, уровня экономической активности, численности безработного населения, уровня безработного населения, численности занятого населения, уровня занятости населения. Для проверки эффективности МСГ объектов было проведено сравнение этих оценок с оценками, полученными методом скользящего среднего (МСС). Результаты этих расчётов позволяют сделать следующие выводы. Оценки соответствующих показателей, полученные МСС и МСГ, очень близки (около 2% от величины оцениваемого параметра для самых «проблемных» регионов). Ошибки МСС - это ошибки интерполяции. Ошибки МСГ объектов связаны с неоднородностью выборки. При разных источниках ошибок результаты получаются достаточно близкими, это говорит об эффективности использования МСГ для достоверной оценки уровня соответствующего параметра. Однако МСГ объектов имеет решающее преимущество: позволяет получать оценки уровня анализируемого параметра сразу после получения данных выборочного обследования.

В разделе 4.5 рассмотрена задача структурно-классификационного анализа пульсового сигнала лучевой артерии в задачах медицинской диагностики. В работе описаны результаты использования разработанного комплекса алгоритмов структурного анализа для диагностики сердечнососудистых заболеваний (на примере дифференциальной диагностики ранней гипертензии детей и подростков). Специфика задачи анализа пульсового сигнала состоит в том, что многие его характеристики являются одномерными сигналами. Именно поэтому для подобного класса задач анализа квазипериодических сигналов (ЭКГ, ЭЭГ и др.) в диссертации была разработана модификация алгоритма т-локалъной оптимизации для одномерного случая. На базе разработанного комплекса алгоритмов были созданы процедуры выделения из реальных записей пульсового сигнала лучевой артерии как амплитудных, так и временных параметров основного квазипериода пульсового сигнала. Строились также

динамические ряды выделенных параметров. Проведенные исследования показали, что наиболее информативными с точки зрения диагностики являются базовые характеристики спектров таких динамических рядов. Было показано, что в задаче диагностики ранней гипертензии ярко выраженную типологию имеет как сама форма пульсового сигнала, так и форма спектров динамических рядов. Была построена как экспертная, так и формализованная типология этих форм. Выяснилось, что диагностические решающие правила существенно отличаются для разных классов формы сигнала (спектра). Для формирования диагностических правил в диссертации использовалась так пазываемая «ступенчатая схема распознавания», основная идея которой и схема её использования в задачах медицинской диагностики подробно описана в диссертации. В экспериментальном исследовании принимали участие более 350 пациентов в возрасте от 9 до 16 лет, по основному диагнозу разделенные на два класса: первичная артериальная гипертензия и различные виды психосоматической функциональной патологии при нормальном артериальном давлении. Разработанное в диссертации программно-алгоритмическое обеспечение позволило получить существенно более эффективные диагностические правила определения ранней гипертензии у детей, чем используемые в настоящее время в медицинской практике.

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

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

Основные результаты и выводы

В диссертации получены следующие основные результаты.

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

2. Создана методология структурно-классификационного прогнозирования, в том числе: алгоритм структурного прогнозирования; алгоритм адаптивного структурного прогнозирования в задачах исследования систем с существенно изменяющейся со временем структурой объектов; алгоритм кусочно-линейной аппроксимации идентификационной модели сложного объекта управления.

3. Проведено моделирование и анализ эффективности разработанных алгоритмов структурно-классификационного анализа.

4. Разработан программно-алгоритмический комплекс (ПАК) структурно-классификационного анализа сложноорганизованных данных.

5. Проведено компьютерное моделирование разработанных алгоритмов и процедур при решении как модельных, так и ряда прикладных задач, в том числе: исследование социально-экономического развития субъектов РФ; разработка системы мониторинга и оценки эффективности функционирования ЖКХ крупного города; разработка алгоритма корректировки оценок показателей занятости по субъектам РФ в условиях малых выборок; структурный анализ пульсового сигнала лучевой артерии в задачах медицинской диагностики.

Основные публикации автора по теме диссертации

Публикации в изданиях, рекомендованных ВАК РФ

1. Десова A.A., Дорофеюк A.A., Гучук В.В., Дорофеюк Ю.А., Покровская И.В. Процедуры классификационного анализа в задаче формирования информативных признаков при исследовании ритмической структуры биосигнала. / Автоматика и телемеханика. 2008. № 6. - С. 143-152.

2. Ю.А.Дорофеюк Структурно-классификационые методы анализа и прогнозирования в крупномасштабных системах управления. / Проблемы управления. 2008. № 4. - С. 78-83.

3. Julia Dorofeyuk, Alexander Dorofeyuk Classification and Piecewise Approximation Methods in the Problem of Industrial Plant Control and Identification. / Preprints of the 13th IFAC Symposium on Information Control Problems in Manufacturing. Moscow, ICS RAS Publisher. 2009. pp. 719-723.

4. Ю.А.Дорофеюк, А.С.Мандель Структурно-классификационная методология оценки эффективности функционирования жилищно-коммунального хозяйства крупного города (на примере Москвы). / Проблемы управления. 2010. №4.-С. 25-31.

5. А.А.Дорофеюк, В.В.Гучук, А.А.Десова, Ю.АДорофеюк Методология экс-пертно-классификационного анализа квазипериодических сигналов в задачах диагностики. / Проблемы управления. 2010. № 5. - С. 39-47.

6. Дорофеюк Ю. А. Структурная идентификация сложных объектов управления на базе методов кусочной аппроксимации / Управление большими системами. Вып. 30. -М.: ИПУ РАН, 2010. - С.79-88.

7. Дорофеюк Ю.А. Формирование массивов для моделирования алгоритмов интеллектуальной обработки информации, моделирование комплексного алгоритма автоматической классификации. / Управление большими системами. Вып. 31. -М.: ИПУ РАН, 2010. - С.353-362.

8. Ю.А.Дорофеюк Методы адаптивного структурного прогнозирования./ Информационные технологии и вычислительные системы./2010, №3. -с.34-39.

9. Десова A.A., Дорофеюк Ю.А., Гучук В.В. Алгоритм последовательного анализа диагностически значимых показателей пульсовых сигналов лучевой артерии. / Биомедицинская радиоэлектроника. / 2010, № 12. - С. 1-8.

10.Ю.А.Дорофеюк, А.А.Дорофеюк, А.Л.Чернявский Анализ и оценка эффективности социально-экономических систем управления экспертно-классификационными методами. / Информационные технологии и вычислительные системы. / 2011, №1. - с. 14-23.

11. Лайкам К.Э., Дорофеюк A.A., Дорофгюк Ю.А., Чернявский А.Л. Классификационные методы коррекции результатов мониторинга социально-экономических показателей в условиях нерепрезентативных выборок. / Вопросы статистики. 2011, №5. -с. 13-18.

12.А.Г.Спиро, ЮА.Дорофеюк Структурно-графовые методы анализа фондовых рынков. / Проблемы управления. 2011. № 6. - С. 61-65.

13.СпироАТ., Дорофеюк Ю.А., Alperovich Ed. Индексные паевые инвестиционные фонды (анализ доходности) / Управление большими системами. Вып. 34. -М.: ИПУ РАН, 2011. - С.200-212.

14.Десова A.A., Гучук В.Б., Дорофеюк A.A., Дорофеюк Ю.А. Типологический анализ спектральных характеристик пульсового сигнала лучевой артерии.// Биомедицинская радиоэлектроника. 2012, № 2. - С. 23-29.

Публикации в других изданиях

15.Дорофеюк Ю.А. Методология структурного анализа и прогнозирования в слабоформализованных системах управления. / Когнитивный анализ и управление развитием ситуаций. Труды VII Международной конференции. / - М.: Институт проблем управления РАН. 2007. - С. 108-111.

16.Бауман Е.В., Дорофеюк A.A., Дорофеюк Ю.А., Киселёва Н.Е. Программно-алгоритмический комплекс структурно-классификационного анализа сложноорганизованных данных. / Таврический вестник информатики и математики. 2008. № 1. -с. 66-72.

11 .Дорофеюк A.A., Дорофеюк Ю.А., Покровская КВ. Методология экспертно-классификационного анализа в задачах анализа развития региональных систем. / Таврический вестник информатики и математики. 2008. № 1.-е. 159-165.

18. Дорофеюк Ю.А. Комплексный алгоритм автоматической классификации и его использование в задачах анализа и принятия решений. / Таврический вестник информатики и математики. 2008. № 1. -с. 171-177.

19.Дорофеюк Ю.А. Структурно-классификационные методы анализа и прогнозирования в системах управления. / Таврический вестник информатики и математики. 2008. № 1. -с. 166-170.

20.Дорофеюк Ю.А., Мандель A.C. Экспертно-классификационная и эксперт-но-статистическая методология создания систем поддержки принятия управленческих решений./ Управление развитием крупномасштабных систем (MLSD'2008). Материалы Второй международной конференции. Том II. / -М.: ИПУ РАН, 2008. -С. 192-195.

21 .Дорофеюк Ю.А., Дорофеюк A.A., Чернявский А.Л. Построение хорошо ин-

терпретируемых классификаций - методология и алгоритмы. / Управление развитием крупномасштабных систем (MLSD'2008). Труды Второй международной конференции. / -М.: ИПУ РАН, 2008. -С. 164-170.

22.Дорофеюк A.A., Десова A.A., Гучук В.В., Дорофеюк /О.Л.Измерение, преобразование и обработка пульсового сигнала лучевой артерии в задачах медицинской диагностики. / Мир измерений. №1, 2009. -С. 4-10.

23 .Дорофеюк Ю.А. Комплекс алгоритмов экспертно-классификационного анализа для решения прикладных задач. 1 Четвертая международная кон-

ференция по проблемам управления (МКПУ-IV): Сборник трудов. - М.: ИПУ РАН, 2009. - С. 373-379.

24.Дорофеюк Ю.А. Классификационные методы прогнозирования многомерных динамических систем управления в условиях неопределённости. / 4-ая международная конференция по проблемам управления (МКПУ-IV): Сборник трудов. - М.: ИПУ РАН, 2009. - С. 380-384.

25.Лифшщ Д.В., Дорофеюк Ю.А. Методология разработки системы оценки эффективности функционирования жилищно-коммунального хозяйства крупного города. У 4-ая международная конференция по проблемам управления (МКПУ-IV): Сборник трудов. - М.: ИПУ РАН, 2009. - С. 440-449.

26. Бауман Е.В., Дорофеюк A.A., Дорофеюк Ю.А., Киселёва Н.Е. Глобально-оптимальные алгоритмы классификационного анализа сложноорганизо-ванных данных. / 4-ая международная конференция по проблемам управления (МКПУ-IV): Сборник трудов. - М.: ИПУ РАН, 2009. - С. 344-349.

21.Дорофеюк A.A., Дорофеюк Ю.А., Чернявский А.Л. Алгоритмы построения когнитивно-экспертной классификации. / Когнитивный анализ и управление развитием ситуаций (CASC'2009): Труды Международной конференции. / - М: ИПУ РАН, 2009. - с. 109-112.

28.Дорофеюк Ю.А. Совершенствование методов принятия решений с помощью алгоритма адаптивного структурного прогнозирования. / Теория активных систем: Труды международной научно-практической конференции. Том I. / -М.: ИПУ РАН, 2009. - с. 241-245.

29.Дорофеюк Ю.А. Адаптивный по числу классов алгоритм автоматической классификации в условиях существенной структурной динамики. / Теория активных систем: Труды международной научно-практической конференции. Том I. / -М.: ИПУ РАН, 2009. - с. 237-241.

30. Julia A. Dorofeyuk, Eugene V. Ваитап, Alexander A. Dorofeyuk Optimal Fuzzy Piecewise Approximation. / Developments in Fuzzy Clustering. Ed. D.Viatchenin. / - Minsk: VEVER, 2009. - pp. 46-55. ISBN 978-985-6215-77-6.

Ъ\.Мандель А. С., Дорофеюк Ю. А. Экспертно-классификационная и эксперт-но-статистическая обработка информации и принятие решений. / Интеллектуализация обработки информации (ИОИ-2010): 8-ая международная конференция. Пафос, Республика Кипр: Сборник докладов. / - М.: МАКС Пресс, 2010. - с. 165-168.

32. Манделъ А. С, Дорофеюк Ю.А. Модель принятия решений об упорядочении объектов в условиях неопределённости. / Управление развитием крупномасштабных систем (MLSD'2010): Материалы 4-ой международной конференции. Том I. / -М.: ИПУ РАН, 2010. - с. 341-345.

33. Дорофеюк Ю.А. Компьютерное моделирование комплексного алгоритма автоматической классификации./ Управление развитием крупномасштабных систем (MLSD'2010): Материалы 4-ой международной конференции. Том П. / -М.: ИПУ РАН, 2010. - с. 246-249.

ЗА. Дорофеюк Ю.А. Алгоритм «-локальной оптимизации в задачах структуризации. / Управление развитием крупномасштабных систем (MLSD'2010): Труды 4-ой международной конференции. Том I. / -М.: ИПУ РАН, 2010. -с. 248-256.

35. Чернявский А.Л., Дорофеюк А.А., Дарофеюк Ю.А., Лайкам К.Э. Струкгур-но-классификационный алгоритм коррекции квазистационарных временных рядов в задачах статистического и социально-экономического мониторинга. / ММРО - 15-ая международная конференция: Сборник докладов. - М.: МАКС ПРЕСС, 2011. - с. 188-192. Ъб.Дорофеюк Ю.А. Метод структурного прогнозирования на базе адаптивного алгоритма кластер-анализа. / ММРО - 15-ая международная конференция: Сборник докладов. - М.: МАКС ПРЕСС, 2011.-е. 184-188.

Личный вклад автора в совместные публикации

В работах [1,5,9,14,22]: постановка задачи структурной обработки временных рядов пульсовых сигналов, разработка соответствующих алгоритмов, их моделирование и использование для расчётов в конкретных задачах медицинской диагностики. В работах [3,30]: постановка задачи и разработка алгоритмов двухэтапной схемы построения кусочно-линейной аппроксимации моделей сложного объекта. В работах [11,35,36]: постановка задачи ¡'-эталонной классификации, разработка алгоритма её решения, проведение расчётов для прикладной задачи коррекции оценок экономической активности населения по субъектам РФ. В работах [4,10,25]: разработка алгоритмов структуризации первичной информации и результатов экспертизы (предварительного обследования) состояния ЖКХ. В работах [10,17]: разработка алгоритмов структурно-классификационного анализа параметров, характеризующих функционирование субъектов РФ, ранжировки субъектов РФ по выбранным критериям, а также алгоритмов прогнозирования динамики выявленной структуры исследуемых объектов. В работах [21,27]: разработка рабочих вариантов алгоритмов покоординатной, спрямляющей и экспертно-содержательной классификаций, компьютерное моделирование и подбор свободных параметров алгоритмов при решении прикладных задач. В работах [12,13] - разработка алгоритмов структурно-классификационного анализа временных рядов, характеризующих работу финансовых рынков. В работе [16] - разработка комплексного алгоритма автоматической классификации, структурно-классификационного алгоритма Прогнозирования как в детерминированной, так и в размытой постановке, а также алгоритма кусочно-линейной аппроксимации сложных зависимостей. В работе [26] - разработка и реализация глобально-оптимального алгоритма /и-локальной оптимизации для одномерного случая. В работе [31] - разработка экспертно-классификационной методологии обработки информации. В работе [32] -разработка и применение экспертно-классификационных методов обработки информации к решению задачи принятия решений в условиях неопределенности.

Подписано в печать:

22.02.2012

Заказ № 6726 Тираж - 100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

61 12-5/2166

Учреждения Российской академии наук Институт проблем управления им. В.А.Трапезникова РАН

На правах рукописи

ДОРОФЕЮК Юлия Александровна

СТРУКТУРНО-КЛАССИФИКАЦИОННЫЕ МЕТОДЫ АНАЛИЗА И ПРОГНОЗИРОВАНИЯ В СОЦИАЛЬНО-ЭКОНОМИЧЕСКИХ СИСТЕМАХ УПРАВЛЕНИЯ

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Специальность 05.13.10 -управление в социальных и экономических системах

Научный руководитель: д.т.н., проф. А.С.Мандель

Москва 2012

ОГЛАВЛЕНИЕ

Введение 5

Глава 1. Современное состояние методов классификационного ана- 11 лиза в социально-экономических системах управления. Постановка задачи исследования.

1.1. Методы автоматической классификации объектов * *

1.1.1. Содержательная постановка задачи. Эвристические алгорит- 11

мы автоматической классификации

1.1.2. Формальная постановка задачи - вариационный подход к зада- 20

че автоматической классификации

1.1.3. Формальная постановка задачи - вероятностно-статистический 34

подход

1.1.4. Методы диагонализации матрицы связи 44

1.2. Структурный подход к проблеме исследования социально- 49 экономических систем управления - постановка задачи

Глава 2. Разработка методов и алгоритмов структурно-классифика- 52 ционного анализа сложно-организованных данных

2.1. Разработка комплекса алгоритмов автоматической классификации 52

2.1.1. Алгоритм га-локальной оптимизации 53

2.1.1.1. Случай одномерной классификации 5 6

2.1.1.2. Размытый вариант алгоритма 60

2.1.2. Алгоритм выбора информативных параметров 62

2.1.2.1. Алгоритм ш-локальной оптимизации в задаче группиров- 63 ки параметров

2.1.2.2. Процедура выбора информативных параметров

2.1.3. Алгоритм построения начального разбиения

2.1.4. Алгоритм выбора числа классов 69

2.1.5. Особенности реализации комплексного алгоритма 7 *

2.1.5.1. Выбор свободных параметров алгоритма

2.1.5.2. Процедура заполнения пропущенных наблюдений

2.1.6. Адаптивный вариант комплексного алгоритма 77

2.2. Разработка классификационного алгоритма повышения достоверно- 79 сти статистических показателей в условиях малых выборок

86

88 91

2.2.1. Содержательная постановка задачи

82

2.2.2. Метод структурной группировки объектов

2.2.2.1.Формирование виртуального объекта для /-эталонного 83 объекта

2.2.2.2. Процедура масштабирования

2.3. Разработка алгоритмов построения хорошо интерпретируемых клас- 87 сификаций

2.3.1. Покоординатная и спрямляющая классификации

2.3.2. Содержательно-экспертная классификация.

2.4. Моделирование и анализ эффективности разработанных алгоритмов 94 структурно-классификационного анализа

2.4.1. Формирование массивов данных для моделирования

2.4.2. Результаты моделирования

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

3.1. Разработка алгоритма структурного прогнозирования в социально- 104 экономических системах управления

3.1.1. Методы классификационного анализа в задаче структурно- 105 классификационного прогнозирования объектов в динамике

3.1.2. Алгоритм структурно-классификационного прогнозирования 107

3.2. Разработка адаптивного алгоритма структурного прогнозирования в 109 условиях существенной динамики структуры объектов

3.3. Разработка оптимальных алгоритмов кусочно-линейной аппрокси- 112 мации для задач структурной идентификации и структурного прогнозирования

3.3.1. Постановка задачи

94 100

104

112 116 117

3.3.2. Методы решения задачи кусочной аппроксимации

3.3.2.1. Алгоритм, базирующийся на вариационном подходе.

3.3.2.2. Двухэтапный алгоритм кусочно-линейной идентифика- 123 ции

Глава 4. Использование структурно-классификационных методов 127 анализа и прогнозирования для решения прикладных задач

4.1. Разработка программно-алгоритмического комплекса структурно- 127 классификационного анализа сложноорганизованных данных (ПАК)

157 159

4.1.1. Состав программно-алгоритмического комплекса

4.2. Задача исследования социально-экономического развития субъектов 135 РФ

^ 137

4.2.1. Отбор и предобработка исходных данных

4.2.2. Структуризация исходных параметров и отбор основных по- 138 казателей, характеризующих регионы

4.2.3. Классификация регионов и прогнозирование показателей их 144 социального развития

4.3. Задача разработки системы мониторинга и оценки эффективности 151 функционирования жилищно-коммунального хозяйства крупного города

4.3.1. Результаты предварительного обследования существующей 154 системы

4.3.2. Структура и состав первичной информации (первичных показателей).

4.3.3. Экспертно-классификационные методы структуризации первичных показателей и объектов оценки

4.3.4. Методы экспертно-статистической корректировки результатов

4.4. Задача корректировки (сглаживания) оценок показателей экономической активности по субъектам РФ в условиях малых выборок

4.4.1. Результаты работы метода на примере конкретного региона

4.4.2. Результаты экспериментальных расчетов

4.5 Структурно-классификационный анализ пульсового сигнала лучевой артерии в задачах медицинской диагностики.

4.5.1. Основные характеристики пульсового сигнала

4.5.2. Структурно-классификационные алгоритмы выделения характерных элементов пульсового сигнала

4.5.3. Классификации характеристик пульсограмм

4.5.4. Методы классификационного анализа параметров пульсового сигнала в задачах медицинской диагностики

Заключение и основные выводы Список использованной литературы Приложения

162 165

167

172

173

174 176

179 182

185 187 194

Введение

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

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

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

В диссертации для такого класса сложных социально-экономических систем разработаны структурно-классификационные методы анализа и прогнозирования, базирующиеся на методологии классификационного анализа сложно организованных данных. Необходимо отметить, что тематика классификационного анализа данных широко развита как в России, так и за рубежом. Помимо одной из ведущих в мире школы М.А.Айзермана (Э.М.Браверман, Е.В.Бауман, И.Б.Мучник), большой вклад в эту область внесли следующие учёные: Ю.И.Журавлёв, Я.З.Цыпкин, К.В.Рудаков, Н.Г.Загоруйко, М.И.Шлезингер, В.А.Ковалевский, В.А.Якубович, Ю.И.Неймарк, С.А.Айвазян, В.М.Бухштабер, В.В.Моттль, С.Д.Двоенко, Б.Г.Миркин, Ь.гаёеЬ, Г.ЯозепЫай, Е.Б1<1ау, 1.С.Вегс1ек, К.8.Би, О.Ва11, Б-БПеу и др.

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

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

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

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

• создание методологии и разработка алгоритмов структурно-классификационного анализа сложно организованных данных;

• создание структурных методов прогнозирования в задачах исследования сложных социально-экономических систем управления;

• компьютерное моделирование разработанных алгоритмов и процедур при решении как модельных, так и прикладных задач.

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

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

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

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

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

1. Исследование социально-экономического развития субъектов РФ.

Эта задача имеет чрезвычайно важное прикладное значение для оптимизации и повышения эффективности финансирования субъектов РФ по социальным программам из федерального бюджета.

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

После указа Президента РФ от 26 июня 2007 г. № 825 «Об оценке эффективности деятельности органов исполнительной власти субъектов Российской Федерации» задача оценки эффективности работы системы ЖКХ стала одной из важнейших задач государственного управления.

3. Задача корректировки (сглаживания) оценок показателей экономической активности по субъектам РФ в условиях малых выборок.

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

4. Структурно-классификационный анализ пульсового сигнала лучевой артерии в задачах медицинской диагностики.

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

Основные положения, выносимые на защиту.

1. Методология структурно-классификационного анализа и прогнозирования

для сложных систем управления.

2. Алгоритмическое обеспечение задач автоматической классификации сложно организованных данных и структурного прогнозирования.

3. Методология имитационного моделирования и проверки эффективности разработанных алгоритмов автоматической классификации.

4. Программно-алгоритмический комплекс структурно-классификационного анализа сложно организованных данных.

5. Результаты апробации методологии и разработанных алгоритмов и процедур структурно-классификационного анализа и прогнозирования в задачах исследования социально-экономического развития субъектов РФ; разработки системы мониторинга и оценки эффективности функционирования ЖКХ крупного города; структурно-классификационного анализа пульсового сигнала лучевой артерии в задачах медицинской диагностики; корректировки (сглаживания) оценок показателей экономической активности по субъектам РФ в условиях малых выборок

Практическая значимость работы состоит в том, что использование разработанных в ней методов и алгоритмов позволяет повысить эффективность решения широкого круга прикладных задач. В работе были решены следующие прикладные задачи: исследование социально-экономического развития субъектов РФ; разработка системы мониторинга и оценки эффективности ЖКХ крупного города; задача корректировки (сглаживания) оценок показателей экономической активности по субъектам РФ в условиях малых

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

Апробация работы. Основные результаты диссертационной работы докладывались на семинарах ИПУ РАН, МГИЭМ (ТУ), на общемосковском семинаре «Экспертные оценки и анализ данных» (2007, 2008, 2009, 2010 гг.); на 19 международных и 9 всероссийских конференциях, в том числе: Международная конференция по проблемам управления (МКПУ) - 2006, 2009; «Интеллектуализация обработки информации» (ИОИ) - 2006, 2008, 2010; «Управление развитием крупномасштабных систем» (MLSD) - 2007, 2008, 2009, 2010, 2011; «Когнитивный анализ и управление развитием ситуаций» (CASC) - 2007, 2009, 2011; «Теория активных систем» (TAC) - 2007, 2009, 2011; «Инноватика» (Сочи) - 2006, 2007; «Автоматизация в промышленности» - 2009, Симпозиум IFAC (Москва) - 2009; «Математические методы распознавания образов» (ММРО-15, Петрозаводск) - 2011; «Проблемы управления и информационные технологии» (ПУИТ, Самара) - 2008; «Молодёжная конференция по проблемам управления» (МолКПУ, Москва) - 2008; «Проблемы управления и моделирования в сложных системах» (ПУМСС, Самара) - 2009; «Управление большими системами» (УБС) - 2008 (Липецк), 2009 (Ижевск), 2010 (Пермь), 2011 (Магнитогорск).

Публикации. Автором �