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

РОССИЙСКАЯ АКАДЕМИЯ НАУК ИНСТИТУТ ПРОБЛЕМ УПРАВЛЕНИЯ

Р Г 0 О Л Правах рукописи

УДК 519.1:519.874:658.566

КАРНАУХОВ Владимир Аркадиевич

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

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

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

Москва - 1997

Работа выполнена в Институте проблем упрг тения РАН Научный руководигйль - д.т.н., проф. А.А.ДОРОФЕЮК

Ведущая организация - Институт системного анализа РАН

Защита состоится 02 октября 1997 г. в 14 часов на заседании Специализированного совета N 5 (Д 002.68.03) Института проблем управления РАН по адресу: 117342, Москва, Профсоюзная ул.,65.

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

Автореферат разослан с.(-гл/стсь.' 1997 г.

(фициальные оппоненты - д.т.н. А.С МАНДЕЛЬ

Х.Т.Н..С.Н.С. С.Г.НОВПКОВ

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

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность проблемы. Переход к рыночным отношениям, спад производства, общая экономическая нестабильность о стране резко усложнили условия функционирования промышленных предприятии практически всех отраслей народного хозяйства. Перевод предприятий на реальную самостоятельность, переход в их взаимоотношениях с распределительных на рыночные (договорные) отношения привел к существенному обострение проблемы материально-технического обеспечения производства сырьем, комплектующими и т.д., а также сбыта-готовой продукции. Подавляющая часть снабженческо-сбытовых операций

ч

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

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

Цель работы состоит в разработке методов <И йпторшмов динамического -размытого классификационного анализа многомерных объейто» в задаче управления многономенклатурными поставками и создания ш их базе компьютерной информационно-управляющей системы контроля таких поставок.

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

• Связь с планом. Работа по теме диссертаций ггроводилась в рамках темы Института проблем управления "Разработка методов и алгоритмов анализа данных и их использование для совершенствования систем управления" ^ гос.регистрации 01.96.0040301). '

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

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

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

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

Реализация результатов работы. Методы и алгоритмы, разработанные в диссертации, были использованы при создании информационно-управляющей системы "Поставки". В этой системе предусмотрен специальный блок, позволяющий в адаптивном режиме проводить классификацию потребителей (поставщиков) по уровню надежности. На базе такой классификации действует специальный набор различных управляющих воздействий, позволяющий дифференцирован^ подходить к контролю за поставками и платежами. Все это позволяет существенно повысить оперативность и эффективность работы соответствующего направления коммерческой службы предприятия. Система "Поставки" сдана в опытную эксплуатацию на АОЗТ "АКТЕОН" (г. Новосибирск) и используется на ряде других предприятий.

Апробация работы. Материалы диссертации обсуждались на общемосковехом семинаре "Экспертные оценки и анализ данных", но общемосковском семинаре по статистическим методам, на международной конференции "Интегрированные системы управления предприятием" (Москва, 1996 г.), на международной научно-практической конференции "Управление большими системами" (Москва, 19!>7 г.).

Публикации. Основные результаты диссертационной работы отражены о 4 печатных работах.

Структура и объем рабо^ь;. Диссертация состоит из введения, трех глав, списка литературы, содержит 106 страниц текста.

СОДЕРЖАНИЕ РАБОТЫ

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

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

Во угорой главе диссертации предлагается общая постановка задачи динамического классификационного анализа (ДКА). Исследуется вид оптимальной классификации, разрабатывается алгоритм решения общей задачи и доказывается его сходимость; исследуются различные конкретные функционалы качества Д1СА; способы введения размытых классов '< рассмотрены различные схемы порождения данных в задачах ДКА.

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

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

набором параметров .....л?*К Считается, что для каждого объекта

последовательно снимается т значений каждого из параметров в соответствующие моменты времени. Таким образ 'И, каждый объект характеризуется серией из ш векторов в ¿-мерном пространстве параметров, представляющих собой траекторию изменеш.х данного объекта в пространстве параметров. Такую траекторию будем обозначать ч«.рез л = (•*,,. Итак, в качестве

классифицируемого множества будет рассматриваться конечное множество объектов, задаваемых своими траекториями фиксированной длины, т.е.—надо классифицировать множество Х= {5,.....х,} (Л"с К*"").

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

2). Класс зопус. шых класснфик. лнй. Размытой классификацией множества Х- {*,....,*,} на г классов с фоновым классом называется такая г+1-мерная

вектор-функция Н[х) = (Л,(Х), ^(х).....Ь,(х)) <4(*) - функция принадлежности к

фоновому классу, а - функция принадлежности к ¡-иу классу, что для любого л значение = Д(л),..., 4^*)) принадлежит некоторому ограниченному замкнутому множеству V пространства значений вектор-функции - Н, т.е. Н(х) е Ус И"1. Множество V определяет тип размытости для данной задачи.

Итак, рассматривается следующий класс размытых классификаций.

= {Я V* е ХН(х) € V)

3). Критерий качесгва классификации. В рамках общего вариационного подхода все исследования проводятся для произвольного выпуклого функционала Ф от вектор-функции Н. Для ДКА предлагается строить критерий качества классификации в соответствии с методом обобщенного среднего:

Считается, что объекты одного и того же класса искомой классификации должны хорош-» описываться некоторой - моделью траектории этого класса, а объекты, чьи траектории плохо описываются всеми моделями классов должны попасть в фоновый класс. Поэтому критерий качества должен отражать , во-первых, близость траекторий объектов внутри нефоновых классов и, во-вторых, отнесение к фоновому классу объектов, чьи траектории достаточно удалены от моделей нефоновых классов. Далее, вводится в рассмотрение множество А возможных моделей траекторий классов. Между элементами множества объектов X и элементами множества моделей Л вводится мера близости К{~х,а) (л е А',« еЛ).

В таком случае величина

^

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

Обобщенным средним или эталоном множества, заданного функцией принадлежности Hjx), называется модель

s, = argmax*(A(3).e> <2.0 -

5 € Л

В соответствии с этим вводится следующий критерий качества классификации

/(я)=£к(4(*),аА) + в£/^,) (2.2)

1-1 ' )ш\

здесь a - эталон i-го класса (в дальнейшем вместо будем писать 5,), а В •

некоторая константа, регулирующая отнесение объектов к фоновому хлаесу.

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

В параграфе 2.2 исследуется вид оптимальной классификации для" ДКА. Исследование вида оптимальной классификации основано на выпуклости рассматриваемого функционала. Выпуклость функционала (2.2) устанавливает следующая лемма, доказанная в диссертации.

Лемма 2.1. Функционал (2.2) является выпуклым функционалом от вектор-функции Н.

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

Лемма 2.2. Для данной классификации Я* вектор-функция ф) = (ф), ф)..... ф)), у которой ф)*Д ф)=х(х,а% где а] -

обобщенное среднее i-то класса классификации IT, является субградиентом функционала (2.2) в точке Н .

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

Рассмотрим какой-иибудь вектор моделей Л=(й,,...,5,)€Л. Назовем классификацию ЛГд(л) = (дДл), 4(лг). .,. , Л,(х)) - эталонной вектором А, если она является опорной к вектор-функции Ф) = {Ф). Ф)..... Ф))-У которой/0(Х)-а, ф)=ф.5 ).т.с.

нА{х)= Шётах (2.3)

(А.. А...../фу*'-' -1 -

Из лемм 2.! и 2.2 непосредственно следует доказаиная в диссертации теорема о виде оптимальной классификации ДКА:

Теорема 2.1. Если классификация Н" доставляет максимум функционалу (2.2), то тот же максимум достигался на некоторой эталонной классификации //^(л) = (Д)(Х), Л(лг), ..., с вектором эталонов Д= (а,,...,й,) € Л, компоненты которого Б, в свою очередь являются обобщенными средними классов классификации НА(х).

В > параграфе 2.3. Приводится алгоритм нахождения оптимальной классификации ДКА. Общий алгоритм классифика: ионного анализа для данного случая реализуется следующим образом.

Выбирается некоторая начальная классификация НЛ. Затем применяется следующая итерационная процедура: для классификации Н. в каждом нефоновом классе находится его обобщенное среднее 5* (соотношение (2.1)), по вектору А' =(2*,. строится (п+1)-е приближение оптимальной классификации

Нгде Ндп - эталонная классификация для вектора моделей

А' =(а',...,сс?) (соотношение (2.3)), и т.д. Сходимость этого алгоритма следует из

сходимости общего алгоритма.

В параграфе 2.4 рассмотрены различные варианты реализации ДКА-Конкретизация общей задачи производится по двум направлениям: рассмотрение различных видов функционала (2.2) и различных типов размытости.

Множество моделей траекторий классов ~ множество возможных траекторий объекта. Также, как и при классификации обычных объектов, наиболее простым вариантом введения множества моделей классов является множество всех возможных . траекторий объектов, т.е. Л, =Кт*к . -Другими словами модели (эталоны) классов , представляют собой в пространстве параметров траектории такой же длины, как и объекты, т.е. можно считать, чтоУо ёЛ, а = .,ал,), где в ■ свою :очередь

от, ^«¡".....а^')- вектор в пространстве параметров, отражающий состояние.

модели в /-й момент времени.

Для множества эталонов Л, в диссертации рассмотрены следующие меры близости:

Мера близости типа /г. Эта мера близости совпадает с евклидовым расстоянием в пространстве К""*:

»•I / I

(знак минус здесь стоит из-за предположения о том, что чем больше мера близости, тем точки должны быть ближе, а у расстояния - наоборот).

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

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

Мера близости типа /,. Эта мера близости совпадает с расстоянием суммы модулей в пространстве :

Использование данной меры приводит к тому, что обобщенные средние классов будут совпадать с медианами классов в пространстве IIй"'.

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

-А1 ¿(4л - в«/)* - д| - - «й)]г

Здесь О0 и Д - некоторые весовые коэффициенты.

Модельные траектории классов - представители классов. Другой возможностью ввода множества эталонов является использование самого исходного множества объектов, т.е. Лг = X, а в качестве меры близости - одной нз мер ЛГ|(л,а), или ЛЦЗг.5). В данном случае эталонная траектория каждого из

классов будет совпадать с траекторией одного из объектов.

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

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

Пусть по параметру д/'' весь диапазон значений разделен на р интервалов, а - среднее значение /-го интервала по у-му параметру. Обозначим множество средних значений интервалов параметра ^ через (/^ = . Будем

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

множество

т

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

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

приращения каждого параметра лИ, т.е. разбивается диапазон значенич параметрг , который в /-й момент времени принимает значение // = л^' - л1/'. Обозначь множество средних значений интервалов параметра через £лу) = Пусть = Сг*1' х Рассмотрим следующее множество моделе!

Л5 = Л<4) х Л*,'Х...ХЛ',' х Л У х Л» . Его элемент а будет иметь в качеств!

а ю- ■

компонент т значений вектора параметров а1 (они соответствует вектора» параметров х1, Н/5и) и т- 1 значение вектора [3¡ (они соответствует вектора» приращений у^ 2 & /2 пз). Для этого случая мера близости Ку(х,а)

ы 1-1М ' ' 1

В параграфе 2.4 исследуются также различные типы классификаций, получаемых при экстремизации функционала (2.2).

Пусть в результате экстремизации функционала получена некоторая эталонная классификация //д(л) = ..., с вектором моделей

Л = (5,,...,а,) б Л. Построим вектор-функцию = ^(х)..........У

которой ^(х) = К{х, а,).

Показано, что за счет выбора ограничивающего множества V можно получить различные типы размытости с учетом фонового класса.

!). Четкая классификация.

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

Ц:05 1; ф) 11,/= 1,...,г, + £ЛДл) = 1.

1=1

Из (2.3) следует, что в этом случае в эталонной класс фикации отнесение объекта к классу (фоновому или обычному) однозначно.

2). Размытая классификация.

к:0 < 4(л) 5 1; 0<; Л,(лг)* 1./ = 1,.... г,( Д,(5))Я + £ (А (*))' = 1-

1\

Было показано, что в данном случае каждый объект в оптимальной классификации принадлежит с ненулевым весом всем классам, в том числе и фоновому. Причем принадлежность к фоновому классу тем больше, чем

дальше объект от обобщенных средних (центров) нефоновых классов.

3). Классификация с размытой границей.

Ц :0<; 1; 0 < ф) 5 1,/= 1.....Г (а -А>(*)Г + £(* ~ +(« " 1У ■

1=1

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

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

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

Для фильтрации грубых ошибок наблюдений вводятся два специальных вида размытости. Для того, чтобы размытыми были лишь обычные классы, а <} ¿новый класс был четким, необходимо выбрать тип размытости для обычных классов, а затем множество V сконструировать из двух частей V*0' и V0' (V- так

чтобы соответствовало однозначному отнесению объекта к фоновому классу (4>(5)=1). а V'1' задавалось бы с помощью ограничения 4,(3?) = О и выбранных ограничений на функции принадлежности обычных классов А,(Х),. ,,Л,(д). Из (2.3) следует, что оптимальна» классификация ЯеН( дает желаемый результат.

4). Размытая классификация с четким фоновым классом.

1^:4(5)=«;ЛДл)=0,/=1.....г.

.....г.Е(М*)У =1

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

5). Классификация с размытыми границами между нефоновыми

классам»» четким фоновым классом.

.....

>1 ' В диссертации показано, что использование ограничения Ц приводит к тому, что фоновый класс - четкий, а между остальными классами границы размыты.

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

ввести функцию принадлежности всем обычным классам Л(х) = .^Г /гДл) и

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

6). Классификация с четкими классами и размытым фоном.

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

7). Аналогичным ©"разом рассматривается случай когда между обычными классами четкие границы, а между обычным ю. 1ССом и фоновым -размытые. Это обеспечивает ограничение вида

Ц :0 5 Л.(*) * I; о 5 А(л)£ 1;(а - /Цл))2 +(а - Л(лг))! = аг + (я -1)1.

В параграфе 2.5 рассмотрены различные схемы порождения данных в задачах ДКА. В постановке зада и ДКА фигурирует классифицируемое множество объектов X¡= {5,.....л,} - множество траекторий (фиксированной длины) изменения

набора параметров. К таким данным можно прийти различными способами.

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

1......

где Ы- число объектов; К - число параметров; Т - число моментов времени.

Классификация множества объектов куба данных. В качестве примера рассмотрена задача классификации предприятий некоторой отрасли или региона по р-зультатам их работы за год, причем данные о параметрах их функционирования снимаются ежемесячно (ежеквартально). Тякая постановка точно укладывается в рассматриваемую схему ДКА. Здесь л= Л^ к- К, ш= Г= 12 £т= Т= 4) и

х, у, 1,..., ],... тЦ - таблица значений "параметры - моменты времени"

для ¡-го объекта. Таким образом, множество объектов куба данных в таком случае и является классифицируемым множеством.

Увеличения числа объектов за счет разбиения периода времени куба данных. .Используется более сложный вариант порождения данных , если данные о,работе

предприятий снимаются не за один год, а за несколько, Причем часто происходит изменение (обновление) самого предприятия. В таком случае при классификации лучше считать отдельным объектом пару "предприятие - год" и объектом будет траектория изменения вектора-параметров предприятия за год, т.е. п= Ы* к= К, т=\2 (ж=4), где " число лет, и

х. , ,ч = 1у, . > ., /=1,...,Л!/=1,...,л| - таблица значений

/х(от-1) + г [(ях^-Ч+г),» ^ I

^"параметры - моменты времени" для / * го предприятия за т -й год. В общем случае,

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

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

Классификация объектов куба данных без фиксированных моментов времени. Обычно в кубе данных объекты синхронизированы по времени. В задачах ДКА это не обязательно так. Например, если исследуется влияние некоторого управленческого воздействия на определенную группу предприятий, то за период наблюдений несколько раз снимают характеристики их состояния. Задача состоит в выявлении II .»более типичных реакций на данное воздействие. В этом случае

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

Увеличения числа объектов за счет использования скользящего "окошка" в кубе данных без фиксирования моментов времени, Такой тип данных используется в задаче анализа постоянных покупателей продукции некоторого предприятия. Здесь пара "покупатель-товар" характеризуется серией поставок предприятием товара для данного покупателя, причем длина серии для каждой пары своя. Каждая поставка описывается некоторым набором параметров, которые описаны в главе 3. Таким

Т. -.длина серии поставок для У-й пары "покупатель-товар". Цель анализа таких

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

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

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

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

образом, í-ой паре соответствует таблица данных

чрезвычайно важная и сложная. Сами платежи по договору за поставляемые товары харакгв|!из^к>тс&,чрезвычайным разнообразием, как по способу и форме оплаты, тик и гю срокам «;речисления финансовых средств. Кроме того, при поставке большого количества товара в виде отдельных партий предусматривается различная форма оплаты за каждую партию или за серию партий. Оплата производится часто не непосредственно деньгами, а различными финансовыми документами, типа векселей разной степени ликвидности, ГКО и др., что так же оговаривается в договоре на поставку .^асто имеет место и бартер, то есть оплата за поставку некоторого товара встречными поставками другого товара, или договоры на обработку давальческого сырья, например, поставка зерна на мелькомбинаты и встречное получение муки. Используются и совершс жо особые формы оплаты типа взаимозачетов по долгам железной дороге, поставщикам электроэнергии и др.

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

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

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

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

. Исходная информация содержала данные о поставках фирмой "Актеон" 43 видов товаров за 1995-1996 гт. Поставка этих товаров осуществлялась 52 фирмам И предприятиям - покупателям. По каждому виду товара и каждому покупателю ' эти данные включали фактические объемы поставок, плановые графики поставок, суммы, способы, формы и сроки (графики) оплаты поставок.

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

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

1) - запаздывание в оплате А'-го вида товара 1-м покупателем за поставку /;

2) х" - У^'/О - удельные потери предприяп.д от задержки п оплате 1-й покупателем А--го товара за поставку Г, где

= • гяе ' коэффициент потерь, 5 - сумма поставки (в

руб.), Т - период оплаты поставки (по договору);

3) X* - ' относительное отклонение цены на А-й товар для 1-го покупателя за поставку /, где

= Т " сРад"яя Цена А'-го товара для

" £ п м

поставки I (в нормативный период времени, включающий ьую поставку);

4) х''= 'у"{1) - запаздывание (в днях) /-й поставки к-то товаоа 1-му покупателю.

Для формирования множества объектов классификации применялась схема порождения данных, в которой увеличение числа объектов осуществляется за счет использования скользящего "окошка" в кубе данных без фиксирования моментов времени, рассмотренная во второй главе. Для этого траектория каждого предприятия (значения введенных выше параметров, связанных с платежами за последовательность поставок в анализируемый период времени) при помощи • скользящего "окошка" фиксированной длины разбивалась на несколько подтраекторий с длиной, совпадающей с размером "окошка". Таким образом, {-й объект порождает набор из Г.-го+1 новых объектов, где Т.- длина траектории ¡-га

объекта, т.е. Число анализируемых поставок для 1-й гары "покупатель-товар" (для

— '• '.'-■' ' ' о .

анализируемых данных длина траектории изменялась от 5 до 24), т - размер

"окошка". При расчетах т, как и число классов, используется как свободный

параметр алгоритма. Для конкретного материала, анализируемого в третьей главе, .

наилучшие результаты были получены при т = 4. В итоге, -из 79 пар "покупатель-

товар" было образовано 385 объектов классификации. Поскольку длина траектории

каждого вновь образованного объекта теперь фиксирована и равна 4, то при

использовании всех 4-х введенных выше параметров, объекты классифицируются в 16-мерном пространстве признаков.

Ниже приводятся основные результаты классификации.

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

2. Наилучшие результаты (как с точки зрения содержательной интерпретации, так и с точки зрения удобства восприятия) дает алгоритм с размытой границей

между основными и четким фоновым классом.

3. Наиболее информативной (с точки зрения анализа надежности) оказывается классификация 8 пространстве признаков, порожденных скользящим "окошком" длины 4 для всех 4-х введенных выше параметров (в различных вариантах классификации использовались также н другие параметры, в частности приращения

этих 4-х параметров).

4. Результаты классификации позволяют выявить основные классы объектов

(коротких траекторий).

Первый класс (130 - около трети всех объектов) - это пары "покупатель-товар" с незначительными отклонениями в сроках и объемах платежей для всех поставок в пределах временного "Окошка". Полная оплата поставок в пределах "окошка" в сроки, оговоренные договором о поставке (за исключением семи объектов,

оплативших поставки в сроки, превышающие договорные на 5-12%).

Второй класс (86 объектов) - это пары покупатель-товар" с существенными отклонениями в сроках и объемах платежей для всех поставок в пределах временного "окошка", которые приносят максимальные (среди анализируемых объектов) удельное потери предприятию от задержек оплаты или неплатежей. Около 10% объектов этого класса (8 объектов) вообще не оплатили часть поставок товара. Для 90% объектов второго класса среднее запаздывание в оплате превышало в 2.3 раза

сроки, оговоренные договором о поставке.

) Третий класс (92 объекта) - промежуточный, в него попали пары "покупатель-товар", с задержками сроков платежей на 30 - 40% не более, чем для 2-х поставок из

4-х в пределах "окошка".

Фоновый класс (77 объектов) - это пары "покупатель-товар" с "нетипичными" траекториями, т.е. с резкими колебаниями фактических сроков оплаты поставок в пределах "окошка" (как в сторону превышения, так и наоборот). Шесть пар из этого класса по совокупности значений 4-х показателей экспертно могут быть отнесены ко второму классу.

5. Исследовалась также статистическая достоверность результатов классификации в зависимости от числа классов. Оказалось, что при увеличении

числа классов наблюдается достаточно устойчивый состав 2-го и фонового класса (изменяются в среднем не более чем на 5%), из 1-го класса выделяются в отдельный класс 9 объектов, в том числе, 7 отмеченных выше, а 3-й класс дробится на подклассы пар "покупатель-товар", допускающих задержки сроков платежей либо для первых двух, либо для вторых двух поставок в пределах "окошка" , соответственно.

6. Полученные результаты классификации К1 ротких траекторий для пар "покупатель-товар" позволяют выделить типы поведения покупателей в отношении соблюдения ими объемов и сроков оплаты поставок товара.

Первый тип - покупатели с ¿[Ьстоянной формой траектории, не изменяющейся от поставки к поставке. Они естественным образом разделяются на два подтипа: первый включает покупателей с высокой надежностью, практически всегда оплачивающих поставки в полном объеме и в с^оки, оговоренные договором; и второй, включающий ненадежных покупателей, регулярно Допускающих срывы сроков и объемов оплаты. Поведение покупателей этого типа (обоих подтипов) достаточно просто прогнозируется.

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

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

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

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

М - „.

АРМ "Поставки" представляет собой постоянно развиваемый и расширяемый Программный продукт, реализованный на лерсональ"ЫХ ЭВМ типа IBM PC в среде программирования, разработки а поддержки баз данных Fox Base+.

АРМ "Поставки" выночает следующие базы данных:

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

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

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

база данных "договоры*, включающая все их реквизиты, в том числе, сроки действия, объемы и условия поставок и платежей;

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

база данных, фактически отправленных поставок по сбыту, (аналогичная информация); ; .

база данных фактического наличия сырья на складах и в цехах; база данных фактического наличия продукции на складах готовой продукции и в цехах;- ' ■■''•'..'■.',■■■■■.;•'■■■'-'"'..

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

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

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

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

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

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

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

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

классификации покупателей (адаптивный режим/ по мере накопления данных о поставках.

Система "Поставки" сдан." в опытную эксплуатацию на АОЗТ "АКТЕОЫ" (г. Новосибирск) и используется на ряде других предприятии, в результате внедрения получен существенны" экономический эффект.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

-1 .—Приведен обзор рибот по моделям.» методам классификационного

анализ- данных.

2. Поставлена задача динамического классификационно! о анализа (ДКА).

3. Исследован вид оптимальной классификации и задачах ДКА, доказана соответствующая теорема.

4. Разработан итерационный алгоритм размытой классификации динамических ооъектов.

5. Проведен теоретический анализ разработанного алгоритма, доказана его сходимость в достаточно общих предположениях.

6. Рассмотрены модификации алгоритмов ДКА #для различных видов критерия качества и типов размытости.

7. Проведено машинное моделирование разработанного алгоритма, показавшее его высокую эффективность.

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

9. Система реализована и внедрена в опытную эксплуатацию на Новосибирском АОЗТ "Актеон".

ОПУБЛИКОВАННЫЕ РАБОТЫ ПО ТЕМЕ ДИССЕРТАЦИИ.

1.Бауман Е.В., Громыко И.Д., Карнаухов В.А. Методы автоматической классификации в задаче анализа надежности поставок сырья для крупного предприятия. - Материалы международной конференции "Интегрированные системы управления предприятиями". Москва, ИПУ, 1996.

2. Громыко И.Д., Карнаухов В .А., Кузнецов E.H. Автоматизированная систем контроля многономенклалурных поставок. - Материалы международной конференции "Интегрированные системы управления предприятиями". Москва, ИПУ.1996.

3. Карнаухов В.А., Кузин М.Г., Кузнецов E.H. Управление многономенклатурными поставками сырья для крупного предприятия,- Материалы

международно» научно-практнческой конференции "Управление большими системами". Москва. ИПУ, 19ч7.

4. Бауман Е.В., Карнаухов В.А. Методы кластер-анализа в задачах управления динамическим объектом. - Материалы международной научно-практической конференции "Управление большими системами". Москва, ИПУ,

В работах [1.4] диссертанту принадлежит постановка задачи и разработка алгоритмов классификационного анализа данных о многономенклатурных

поставках, а в работах [2,3] - разработка методологии и алгоритмического

■о

обеспечения автоматизированном системы управления многономенклатурными поставками. * ~ ----- ------- •- —•----

1997

Подписано а печать 21.08»97, Офсетная печать Уч.-изд.л.1,5 л.л. Тира* 100 экз . Заказ № 312.

Формат 60x84,1/16 Бесплатно,

Участок оперативной полиграфии НГУ,6300090, Новосибирск,90,ул.Пирогова ,2.