Лаврентьев в. А

Главная страница
Контакты

    Главная страница


Лаврентьев в. А



страница30/63
Дата08.04.2018
Размер8,79 Mb.


1   ...   26   27   28   29   30   31   32   33   ...   63

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




5.1. Анализ математической модели, выбор допустимого алгоритма

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


Критерии допустимости алгоритмов автоматической классификации

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

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


  1. Критерии, связанные с практической реализацией
    алгоритма, в частности, вызванные ограничениями на время вычислений, объемом оперативной памяти ЭВМ и т. д.

  2. Критерии, связанные с особенностями исходных дан­ных.

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

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

Критерии, связанные с особенностями исходных данных.

Все критерии данного класса могут быть разделены на три группы: 1) порождаемые общими свойствами си­стемы данных; 2) связанные с формальным представле­нием данных; 3) связанные с возможными изменениями системы данных.



Критерии первой группы обусловлены общими свой­ствами системы данных, не зависящими от формы их пред­ставления. Здесь можно выделить два их типа: первые отражают требования на общее число элементов, перераба­тываемых алгоритмом, вторые определяются размерностью исходных связей. Критерий первого типа может выгля­деть так: алгоритм должен позволять обрабатывать мас­сивы с числом элементов до N (в частности N = +); второго — алгоритм должен позволять работать с исход­ными связями любой размерности.

В большинство конкретных ситуаций формальное опи­сание системы данных обладает некоторой степенью свободы. Часто связи допускают числовое измерение, по вы­бор единицы измерения не определен жестко постановкой задачи. Иными словами, формальное описание данных частично определено природой объекта классификации, а частично — выбором способа формализации. Алгоритм, применяемый к формальному описанию, должен давать результат, который не зависит от произвольной компонен­ты, а определяется только свойствами объектов классифи­кации. Эта общая формулировка может быть конкретизи­рована через ряд частных критериев. Рассмотрим два из них.

Критерий допустимости относи­тельно перенумерации элементов объекта. Пусть элементы объекта некоторым образом занумерованы, и после применения алгоритма получено разбиение G1. Затем произведена произвольная перенуме­рация элементов, и па этой основе получено разбиение G2. Тогда алгоритм является допустимым относительно дан­ного критерия, если справедливо хотя бы одно из следую­щих утверждении: 1) G2 совпадает с G1 если вернуться к исходной нумерации элементов; 2) G2 и G1 эквивалент­ны с точки зрения целей классификации, например, если решается задача па максимум критерия Ф (G), где G — разбиение множества элементов, то G1 и G2 эквивалент­ны с точки зрения целей классификации, если они удовлет­воряют всем ограничениям и Ф (G1 ) = Ф (G2). Понятно, что первое утверждение представляет собой частный слу­чай второго.

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

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

Рассмотрим в качестве примера два критерия, связанных с возможными изменениями системы данных.

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

Критерий допустимости по отношению к исключению классов. Пусть в результате использования алгоритма получено разбие­ние элементов объекта на п групп (А1, А2, . . ., Ап) и эле­менты некоторой группы Аk исключаются из классифи­цируемого множества А. Тогда этот алгоритм является допустимым относительно данного критерия, если после его применения к множеству А \Аk получается разбиение на п — 1 группу, причем эти группы с точностью до упорядочения совпадают с группами А1, А2,. . , Аk-1, Аk+1,…, Ап.

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

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

1. У исследователя нет никаких представлений о свойствах групп объектов, которые предстоит выделить, кроме самых общих, например, гипотезы компактности связей. Эта ситуация характерна для тех случаев, когда отсутствуют какие-либо четкие представления, для чего и каким образом будут использованы полученные резуль­таты. Она часто встречается при решении задач, связан­ных с первоначальной обработкой информации о незнакомых явлениях, направленной па установление неизвестных закономерностей (ситуация C1).


  1. У исследователя есть опыт решения подобных задач.
    Ему известны характеристики ранее полученных группи­ровок, которые признаны «правильными», однако он незнает строгих формальных свойств таких разбиений.
    Иногда они могут просто отсутствовать, как, например, при выделении хозяйственных отраслей (ситуация G2).

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

В каждой из рассмотренных ситуаций возникают свои специфические критерии допустимости алгоритмов. Для первой они порождаются необходимостью интерпретации полученного разбиения. Важнейшую роль здесь играют особенности восприятия результатов решения задач клас­сификации человеком. На такие особенности в советской экономической литературе впервые было указано в работе [14], где была предпринята попытка исследования спо­собностей человека воспринимать группы сложной кон­фигурации. Гипотеза, сформулированная автором, со­стоит в том, что в процессе многомерной классификации человек использует линейные решающие функции. Был проведен ряд экспериментов, в основном подтвердивших ее справедливость. Этот факт следует иметь в виду при ис­пользовании алгоритмов, так как можно превысить спо­собности человека не только проводить многомерную клас­сификацию, но и воспринимать полученные результаты. Допустимость алгоритмов во второй ситуации определяет­ся путем сравнения с результатами классификации, про­веденной неформальными методами. Алгоритм называется допустимым, если он дает тождественные или близкие ре­шения.

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

Кроме выделенных выше классов критериев допусти­мости алгоритмов автоматической классификации целесооб­разно их деление па общие критерии и частные. Частные критерии определяются спецификой конкретных задач, общие — характерны для подавляющего большинства задач автоматической классификации. К ним могут быть отнесены многие критерии, связанные с особенностя­ми представления и изменения исходных данных, в част­ности критерии допустимости относительно перенумерации элементов и монотонного преобразования исходных свя­зей. Хотя такое деление довольно условно, оно оказы­вается полезным при выборе алгоритмов в рамках общей схемы этого процесса.
Классификации алгоритмов. Процедура поиска алгоритмов, удовлетворяющих критериям допустимости

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

В одном из первых в отечественной литературе обшир­ном обзоре алгоритмов автоматической классификации, приведенном в [13], все множество алгоритмов делится на три класса : 1) эвристические алгоритмы ; 2) вариацион­ные алгоритмы; 3) методы, связанные с задачей разделе­ния смеси.

К эвристическим относятся алгоритмы, основанные на интуитивных соображениях выделения изолированных групп объектов в пространстве их признаков и не имею­щие эквивалентной формальной постановки задачи. Среди представленных в [13] эвристических алгоритмов можно выделить ряд типов: 1) алгоритмы, основанные на идее распознавания образов с учителем; 2) пороговые алго­ритмы, связанные с выбором точек-эталонов; 3) алгоритмы, использующие матрицу близости объектов; 4) алго­ритмы, опирающиеся на поиск мод (локальных макси­мумов) функции плотности распределения в простран­стве признаков; 5) алгоритмы, использующие свойства ковариационной матрицы параметров; 6) алгоритмы, основанные на методе потенциальных функций; 7) алгоритмы численной таксономии.

Вариационные алгоритмы связаны с введением неко­торого функционала (например, средней по группам меры близости объектов в пределах группы пли средней меры удаленности групп), зависящего от разбиения объектов па группы, экстремум которого достигается на «хороших» в интуитивном смысле разбиениях. Все алгоритмы этого класса разделены в на две группы: в первую входят алгоритмы, соответствующие постановке задачи автомати­ческой классификации для случая, когда число элементов классифицируемого множества конечно (в этой ситуации, вообще говоря, всегда существуют алгоритмы экстремизации любого функционала); во вторую — алгоритмы, со­ответствующие постановке задачи, когда число элемен­тов может расти до бесконечности. В этом случае допусти­мы лишь рекуррентные алгоритмы, т. е. такие, которые при появлении очередного элемента а, строят i-e прибли­жение искомого разбиения, используя фиксированное число элементов (например, только at), и приближение, построенное на предыдущем шаге.

Алгоритмы третьего класса основаны па сведении за­дачи автоматической классификации к классической в ма­тематической статистике задачи разделения смеси. В приводится обзор известных работ, в которых развивается этот подход и используются различные методы для оценки неизвестных параметров (метод моментов, метод макси­мального правдоподобия и др.) при различных предпо­ложениях о типе распределения элементов совокупности.[18,43,44]

В [15] предлагается двухуровневая классификация ал­горитмов автоматической классификации. Прежде всего, все алгоритмы в соответствии с числом градаций призна­ков, описывающих классифицируемые множества, делят­ся на две группы: алгоритмы для таксономии по' «качест­венным» и по «количественным» признакам. Первые пред­назначены для классификации множеств, описываемых двоичными признаками, вторые — признаками, имею­щими более двух градаций. В каждой из этих групп в свою очередь выделены алгоритмы, дающие линейно раздели­мые классы и классы, для разделения которых требуются более сложные функции. Кроме того, в третью подгруппу выделены алгоритмы, занимающие промежуточное поло­жение, они дают классы, которые разделяются кусочно-линейными функциями с небольшим числом гиперплоскостей.

В [32] рассматривается множество объектов А, на ко­тором задана функция р (аi, аj), характеризующая пар­ные связи между объектами. Задачи автоматической клас­сификации (а соответственно и алгоритмы) предлагается разделять по двум признакам. По первому выделяются задачи, в которых классификация происходит па основе явного определения понятия класса, и задачи, в которых классификация происходит непосредственно в терминах структуры системы классов. Вторая группа задач в свою очередь делится па две в соответствии с тем, как учитывают­ся связи между объектами: а) все связи учитываются оди­наково, безотносительно к их интенсивности; б) произво­дится сравнение связей по интенсивности.

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

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

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

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

В основе классификации, предложенной в [3], также лежат два признака. В зависимости от объема классифи­цируемой совокупности задачи автоматической класси­фикации делятся на два типа: Б1 и Б2, К типу Б1 отно­сятся задачи классификации сравнительно небольших по объему совокупностей, состоящих не более чем из не­скольких десятков объектов. К типу Б2, — задачи класси­фикации достаточно больших массивов, порядка несколь­ких сотен и тысяч элементов. Указывается, что хотя подоб­ное разбиение задач довольно условно, оно оказывается целесообразным в первую очередь с точки зрения принци­пиального различия идей и методов, лежащих в основе соответствующих алгоритмов.

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



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

Иерархические процедуры предназначены в основном для решения задач типа (в). Что касается объема класси­фицируемой совокупности, то формально иерархические процедуры применимы как для задач Б1, так и для задач Б2, однако, по мнению авторов [3], конструктивно реали­зуемыми их можно признать лишь для задач типа Б1. Принцип работы иерархических процедур состоит в по­следовательном объединении (разделении) групп элемен­тов сначала самых близких (далеких), а затем все более отдаленных друг от друга (приближенных друг к другу). При этом отдельные процедуры различаются способом вычисления расстояния между классами. Кроме того, рас­сматриваются иерархические процедуры, использующие понятие порога. Здесь дополнительно задается последо­вательность, как правило, монотонная, порогов Q1, Q2,. . . . ., Qd, которая используется, например, следующим образом. На первом шаге алгоритма попарно объединяют­ся элементы, расстояние между которыми не превосходит величины Q1, либо мера их близости не менее Q1 (если на множестве элементов задана мера близости, а не расстоя­ние). На втором шаге объединяются элементы или группы элементов, расстояние между которыми не более Q2, либо мера их близости не менее Q2, и т. д. Попятно, что при Qd = или, при сравнении мер близости, при Qd = 0, па последнем d-м. шаге все элементы исходного мно­жества окажутся объединенными в один класс.

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

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

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

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

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

Вид, наиболее близкий к функциональному, имеет классификация, представленная в [32].

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

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

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

Пару элементов (а, в), будем называть границей мно­жеств А и В, если

шах р (с, d) t=p (а, b),



сА, dB

где р (а, b) — введенная мера близости. Число р (а, b) будем называть значением границы.

1   ...   26   27   28   29   30   31   32   33   ...   63