d9e5a92d

Кластеризация морфологических множеств

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

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

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

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

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

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

Вычисление мер сходства осуществляется по различным правилам.
При первом способе описания альтернатив в виде наименований Аij меры сходства между двумя вариантами S' и S вычисляются по известной формуле

с учетом следующих правил:
- число элементов множества, образующего вариант системы S′ или S′′', равно числу альтернатив Аij, входящих в данное множество;
- число пересечений элементов двух множеств S' и S равно числу одинаковых пар альтернатив А′lm и А′′lm, принадлежащих соответственно вариантам S' и S, т. е.

При втором способе описания альтернатив на основе экспертной оценки их степени сходства друг с другом расчет меры сходства между двумя вариантами S′ и S системы определяется по формулам:


где Сl (A′lm, А′′lm) экспертное интегрированное значение меры сходства пары альтернатив, принадлежащих l-и обобщенной функциональной подсистеме;
L число обобщенных функциональных подсистем, образующих вариант системы;
Сi (Z′ilm, Z′′ilm) экспертное значение меры сходства пары альтернатив по i-му классификационному признаку или критерию качества;
ρi весовой коэффициент, определяющий вклад в меру сходства i-ro признака или критерия;
К число признаков или критериев, по которым описаны свойства альтернатив А′lm и A′′lm.
При третьем способе описания вариантов синтезируемых систем определение меры сходства между вариантами осуществляется по выражению (5.9). Вариант системы здесь описан множеством значений признаков Zilm = {0,1}. Значение признака Zilm равно единице в описании альтернативы Аlm, если признак присутствует в ней, в противном случае Zilm = 0.
Рассмотрим строение морфологических множеств относительно иерархических классификаций. Первоначально исследуем морфологическое множество, включающее варианты, альтернативы которых описаны в соответствии с первым способом, т. е. простым указанием их наименований. При проведении исследований данного типа целесообразно определить наиболее приемлемый метод классификации. Критерием для отбора метода кластеризации может являться хорошая интерпретируемость полученных результатов, т. е. достижение высокой адекватности между моделью-классификацией и реальной системой-прототипом.

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

5.11). Исходное морфологическое множество (табл.

5.12) сформировано алгоритмом лексикографического упорядочения альтернатив.

Объекты морфологического множества состоят из трех функциональных подсистем. С учетом выражения (5.8) и относящихся к нему правил формируется матрица мер сходства вариантов:

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

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

При этом более верные результаты дают методы медианы и средней группы. Действительно, пары объектов S5S7, S1S3, S2S4, S6S8 сходны между собой двумя альтернативами, а при наличии в объекте трех функциональных подсистем, реализуемых альтернативами, его сходство с любым другим объектом по двум альтернативам оценивается значением 0,67.

Классы, образованные объектами S5S7 и S1S3, а также S2S4 и S6S8, сходны между собой в среднем одной альтернативой, т. е. G(S5-7, S1-3) = G(S2-4, S6-8) = 0,5.
На вид дендрограммы влияет не только метод определения сходства между классами, но и порядок извлечения классов из матрицы сходства для тех случаев, когда указанные матрицы содержат несколько одинаковых максимальных значений. В этих случаях возможны два способа извлечения классов из матрицы. Первый способ основан на случайном выборе двух классов, на пересечении которых в матрице сходства стоит одно из максимальных значений.

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

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

5.6. Она построена для случая, когда из матрицы сходства первой извлекалась пара S1 и S2.

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

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

5.7), который построен для максимального порогового значения отношения сходства СΔ = 0,67.
Построение матрицы включения вариантов систем, входящих в рассматриваемое морфологическое множество, показало, что она идентична матрице сходства, т. е. симметрична относительно главной диагонали. Это подтверждает наличие особой специфики у морфологических множеств, полученных методом комбинирования альтернатив.


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

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

5.5. Синтез новых и рациональных систем на морфологических множествах

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



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

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

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

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

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

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

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

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

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

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

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

Аддитивная и мультипликативная целевые функции в этой задаче определяются следующим образом.
Аддитивная целевая функция. Найти подмножество S∈ Ω, для элементов которого

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

L число функций системы (число строк морфологической таблицы);
wlm, w*lm, соответственно рассматриваемое и наилучшее интегральные по нескольким критериям качества значения векторов приоритетов, соответствующих альтернативам Alm, и А*lm, входящих в i-й вариант синтезируемой системы и наилучшей по рассматриваемым критериям альтернативы;
N размерность морфологического множества;
Kl число способов (альтернатив А lm для реализации i-й функции системы.
Аддитивные модели базируются на предположении о том, что качество системы (экономической, управленческой и т. д.), т. е. ее ценность, полезность, эффективность, определяется суммой эффектов от каждого ее свойства. Частной и широко применяемой на практике формой выражения аддитивного показателя качества является взвешенная арифметическая (5.10), (5.11).

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

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

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

где С(Si1, S2) мера сходства между описанием рассматриваемого варианта системы Si1 и описанием поискового задания S2;
x1lm, x2l числовые значения критериев качества, характеризующие соответственно рассматриваемый вариант системы и поисковое задание;
L может иметь два значения и определять либо число обобщенных функциональных подсистем, либо число критериев качества, которыми на количественном уровне охарактеризованы описания Si1 и S2;
т порядковый номер альтернативы в строке морфологической матрицы.
Первое значение индекс L имеет в том случае, если x1lm и x2l представляют интегральную оценку по множеству критериев качества, характеризующих альтернативу Аlm, являющуюся компонентом описания рассматриваемой системы Si1 и описания системы S2, выступающей в роли поискового задания (это могут быть прототип, идеальная система, желаемая система).
Второе значение индекс L имеет в случае, когда x1lm и x2l представляют неинтегральные по множеству критериев качества значения, характеризующие в целом альтернативу рассматриваемых вариантов систем и поискового задания. Верхние индексы указывают на принадлежность к рассматриваемому варианту системы (индекс равен единице) и поисковому заданию (индекс равен двум).
Если в выражении (5.12) х1lт и x2i отражают интегральные значения всего множества критериев, характеризующих альтернативы, то при необходимости учета различной степени влияния на меру сходства функциональных подсистем в числитель и знаменатель после знака суммы необходимо добавить весовой коэффициент ωl и присвоить соответствующие значения каждой функциональной подсистеме. Если x1lm и х2l, отражают значения индивидуальных критериев качества, то для учета влияния на меру сходства (5.12) одновременно функциональных подсистем и критериев качества необходимо ввести два весовых коэффициента. В этом случае целевая функция будет иметь следующий вид: найти подмножество S∈ Ω, для элементов которого

где ρl весовой коэффициент, определяющий вклад в меру сходства критериев качества обобщенной функциональной подсистемы ОФПСl;
ωlp весовой коэффициент, определяющий вклад в меру сходства критерия качества Кp по которому оценивается ОФПСl;
L число обобщенных функциональных подсистем;
P число критериев качества, характеризующих альтернативы Аlm и Аl, причем Р = 1,2,..., r при l = 1; Р = 1,2,..., s при l = 2; Р = 1,2,..., t при l = h;
x1lpm - оценка по критерию качества Кр альтернативы Аlm, участвующей в синтезе и принадлежащей обобщенной функциональной подсистеме ОФПСl;
x2lp оценка по критерию качества Кр обобщенной функциональной подсистемы ОФПСl, принадлежащей системе, представляющей поисковое задание.
Рассмотрим примеры синтеза вариантов систем на основе аддитивной целевой функции и на принципе определения меры сходства между вариантом и поисковым заданием. Используем для этой цели ранее построенную морфологическую таблицу (см. рис.

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

Упорядочив варианты в направлении уменьшения значений целевой функции (табл. 5.13), можно определить подмножество наиболее эффективных решений, которые подлежат дополнительному анализу. К таким решениям относятся, например, варианты 16, 10 и 4. Сформулируем поисковое задание из альтернатив, содержащихся в морфологической таблице. Примем в качестве поискового задания интегральные значения критериев качества, относящиеся к альтернативам, из которых состоит наилучший вариант, синтезированный на основе аддитивной целевой функции. Лучший вариант состоит из альтернатив (А13, A22, А31). Расчет мер сходства по формуле (5.13) между лучшим вариантом и всеми остальными синтезированными вариантами (см. табл.

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

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

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

3. Составляются иерархические структуры критериев качества для определения векторов приоритетов обобщенных функциональных подсистем и альтернатив, конкретизирующих указанные подсистемы. Для оценки обобщенных функциональных подсистем и альтернатив могут использоваться как одинаковые по структуре и содержанию иерархии критериев качества, так и различающиеся.
Следует отметить, что оценка по иерархиям критериев второго типа имеет наибольшее распространение.
4. Для сформированных иерархий рассчитывают векторы приоритетов альтернатив принадлежащих каждой обобщенной функциональной подсистеме, и вектор приоритетов WОФПС собственно обобщенных функциональных подсистем. Последний определяет их вклад в эффективность и новизну системы в целом.
Значения векторов приоритетов приписываются соответствующим элементам иерархии (см. рис. 5.10), отражающей множество функциональных реализаций. При этом рассчитанные векторы нормированы следующим образом:



Содержание раздела