Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

5.4. Кластерный анализ морфологических множеств

Основы кластерного анализа систем

Для выявления закономерностей строения сложных систем целесообразно в первую очередь собранные данные разложить "по полочкам", классифицировать. Вопросы кластерного анализа рассмотрены в учебнике А. М. Дуброва, В. С. Мхитаряна, Л. И. Трошиной [З].

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

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

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

Системы-классификации

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

Система может быть представлена пятеркой:


Если хотя бы один член пятерки изменяется во времени или пространстве, то система называется динамичной, в противном случае — статичной.

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

Следовательно, если множество признаков, учитываемое на объектах, является системой описания, а множество значений каждого из учитываемых признаков на конкретных объектах — описанием этих объектов, то аналоги-модели объектов (в частности, системы-классификации) — это системы множеств, каждое из которых есть описание. Система-модель С = С ( I, R, A(S), A(ps) , A(SP) ) является образом системы-оригинала С' = С ( I', R', А(S')), A(RS'), A(SR')). Отображение множества С' на множество С является гомоморфным, если С имеет тот же состав, что и С' (обратное неверно). Из сказанного видно, что система-модель содержит меньшее число элементов и связей, чем система-оригинал, но все элементы и связи, которые имеются в модели, правильно копируют прототип.

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

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

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

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

Третий этап — отбор репрезентативной выборки объектов и производство измерений.

Четвертый этап — выбор отношений на множестве описаний объектов; мер, порождающих отношения; решающих правил и критериев эффективности. Здесь же производятся вычисления.

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

Шестой этап — интерпретация полученных результатов, т. е. перенос полученных утверждений с системы-модели на систему-прототип.

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

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

Виды измерений

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

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

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

Порядковые или ранговые признаки сравниваются только по отношению "больше — меньше".

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

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

Условно все виды оценок делят на качественные и количественные. В соответствии с рекомендациями, приведенными в работе [4], качественными можно считать только те из них, которые измеряются в шкале наименований.

Формализация обработки качественных признаков

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

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

Множество образов вариантов систем может быть представлено как матрица, имеющая q столбцов и р строк (порядка p х q), причем номеру столбца соответствует наименование системы Sj (j = 1, 2, ... , q), а номеру строки — название признака Zi (i =1, 2,..., р). В ряде случаев номеру строки ставится в соответствие значение признака. Информационным содержанием матриц являются указания о присутствии или отсутствии каждого из учитываемых признаков в рассматриваемых системах. При этом если i-й признак присутствует в j-й системе, то на пересечении i-й строки и j-ro столбца помещается "1", в противном случае — "0".

Любой j-й столбец матрицы назовем описанием j-й системы, любую i-ю строку — описанием i-го признака. В терминах теории множеств


Формула (5.1) читается: семейство множеств S, состоящее из всех Sj, таких, у которых элементы j принадлежат множеству J. Аналогично семейство множеств


есть индексированное множество, а I — индексное множество:


Индексация позволяет различать множества, состоящие из одинаковых элементов.

Пример матрицы образов представлен в табл. 5.3.

Таблица 5.3

Матрица образов как семейство множеств

S1

S2

S3

Sq

Z1

0

1

0

1

Z2

1

1

0

1

Z3

1

1

1

0

...

...

Zp

0

0

0

0

0

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

Рассмотрим основные меры, порождающие отношения на множестве исследуемых систем.

Меры сходства и различия. Мерой сходства (близости) обычно называется величина С (Sj, Sk), имеющая предел и возрастающая с возрастанием близости объектов. Под мерой сходства будем понимать неотрицательную вещественную функцию С (Sj, Sk), обладающую следующими свойствами:


Здесь Sj, Sk — множества значений признаков, описывающие сравниваемые объекты. Мера, коэквивалентная мере сходства, называется мерой различия D (Sj, Sk) и обладает свойствами метрики, если:


Свойствами (5.2) обладает, в частности, континуум эквивалентных мер, представляемых формулой



Меры сходства и различия "изобретаются" по специальным правилам [4], а выбор конкретных мер зависит, в первую очередь, от суперзадачи — цели конкретного исследования, а также от шкалы измерений В табл. 5.4 приведены наиболее распространенные меры сходства и различия для различных значений коэффициента и (5.3), предназначенные для обработки качественных и количественных признаков.


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


Здесь S — индексированное множество с элементами Sj (алфавит описаний), Sj —j-e описание объекта; Z — индексированное множество с элементами Zi (алфавит признаков или значений признаков); Zi — i-й признак (значение признака); xiy — одно из двух значений {0, 1} i-гo признака y j-го объекта (xij = 1, если i-й признак есть у j-го объекта, в противном случае xij = 0); J и I— индексные множества.

Бинарная матрица для вычисления меры сходства между двумя объектами имеет следующий вид:


Вычисление меры сходства, например, по формуле Чекановского — Серенсена (см. табл. 5.4) с учетом бинарной матрицы (5.4) осуществляется по следующему выражению:


где xi1, xi2 — одно из двух значений {0, 1).

Рассмотрим правила вычисления количества элементов некоторых множеств, получаемых в результате операций над ними. Количество элементов множества S равно


где р — общее число элементов множества S;

xi — значение i-ro элемента множества S, при этом

Î S®xi = 1.

Количество элементов пересечения двух множеств S1 Ç S2 равно


где xi1, xi2 — соответственно значения i-го элемента для множеств S1 и S2 .

Количество элементов объединения двух множеств S1 È S2 равно


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

Меры включения множества S2 в множество S1 и S1 в S2 определяются следующим образом:


Меры включения несимметричны, а включение j-го описания в самом себе стопроцентно, так как


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

Отношения мер сходства, включения и иерархии

Отношения мер сходства (различия), включения и иерархии позволяют при обработке множеств исследуемых объектов выявлять наиболее интересные закономерности строения анализируемых множеств. В общем случае под отношением понимается пара <А, М>, где М— множество, на котором отношение определено, а А — подмножество пар М x М, для которых это отношение выполнено. Множество М называется областью задания отношения А.

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

Отношения сходства, различия и включения, порождаемые соответствующими мерами, определяются следующим образом:


Здесь j, k Î J; СD, DD, BD —соответственно отношения сходства, различия и включения; D— некоторое произвольное число (0 £ D £ 1,0 для отношения сходства и включения). Записи Sj СD Sk и Sj BD Sk означают соответственно то, что Sj и Sk находятся в отношении "D-сходства" и "D-банальности". Отношение "банальности" или "экзотичности" порождается мерой включения. При этом запись Sj BD Sk означает, что описание Sj "банальнее" Sk при пороге D. Например, если рассчитанные для пары объектов меры включения имеют следующие значения: W(S1; S2) = 0,57, W(S2; S1)= 0,67, то эти результаты можно интерпретировать следующим образом. Мера включения первого описания во второе (0,67) показывает, что второй объект "оригинальнее", или "экзотичнее", первого. Т. e. описание второго объекта содержит больше специфических признаков, чем описание первого объекта, поскольку первое описание включено во второе на 67 %, а второе включено в первое на 57 %.

Отношение иерархии определяется следующим образом. Если множество H(i) образовано соединением некоторых классов из множества Н(i), то f: Н(i) ® Н(j) сюръективно: каждому элементу Н(i) соответствует хотя бы один элемент из Н(j) То обстоятельство, что класс появляется классом более широким, чем Н(j) отображается через отношение иерархии И следующим образом: Н(i) И Н(j) (класс H(i) подчиняет класс H(j)).

Множество H(i) называется сгущением H(j), если хотя бы один из классов H(i) есть соединение классов из H(j).

Если И = {Н(1),..., H(S)} есть множество разбиений, таких, что Н(k) сгущение Н(k-1), где k Î К, К = {k ½ k — целое число, 1 £ k £ S}, то в предельном случае Н(1) состоит из всех классов, содержащих ровно по одному элементу, a H(S) — из одного класса, совпадающего с исходным множеством исследуемых объектов J. При этом если задано разбиение, то элементы, входящие в один и тот же класс, являются неразличимыми (эквивалентными). Здесь под разбиением Н множества J понимается представление J в виде совокупности непустых подмножеств Hk, k = 1, 2,..., п , таких, что


Множество И есть иерархическая система, состоящая из S уровней. Номеру каждого уровня можно поставить в соответствие его ранг, так как К— упорядоченное множество, а названия всех классов одного ранга считать категорией.

При практической реализации иерархических классификаций строятся дендрограммы, являющиеся графическим способом изображения системы, что делает наглядной структуру иерархической системы. Последовательный процесс построения сгущений начинается с рассмотрения q объектов {q Î H(1)). Таким образом, на первом шаге каждый объект из заданного множества считается классом. Далее два наиболее схожих объекта объединяются в один класс, и общее число последних становится равным q -1. Эти классы принадлежат разбиению H(2), являющемуся сгущением Н(1). Если число схожих объектов п, то объединяются любые два из них. Среди оставшихся снова отыскиваются наиболее схожие, которые также объединяются. Аналогичные процедуры осуществляются до тех пор, пока все объекты не попадут в один класс H(S).

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

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


где G(Hj,Hk) — мера сходства или различия классов Hj и Hk = {Ни ,Hl}.


Здесь nu, nk — число объектов соответственно u-го и k-го классов; пk = nu + nl.

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

Обобщенные алгоритмы классификационных построений

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

Шаг 1. Формируются два множества: множество исследуемых объектов J = { S1, S2,..., Sq} и множество признаков Z = { Z1, Z2,..., Zp}. Каждый объект Si описывается подмножеством признаков {Zi} Î Z, являющимся качественным признаковым образом. Все образы объектов систематизируются в матрицу образов, где представляются индексированными множествами (табл. 5.5).

Шаг 2. Генерируются все парные сочетания объектов, и для каждой пары описаний объектов Si и Sj строится индексная матрица В = ║ xij ║; i =

; j =
; где р — число строк матрицы образов, соответствующее числу рассматриваемых признаков m(Z). На основе индексной матрицы рассчитываются меры сходства C(Si, Sj) или включения W(Si, Sj). Для определения меры сходства может быть использована одна из формул, приведенных в табл. 5.4. Расчет мер включения осуществляется по формулам (5.5).

Таблица 5.5

Пример матрицы образов


Например, для пары объектов S1 и S2 (см. табл. 5.5) меры сходства и включения имеют следующие значения:


Шаг 3. На основе рассчитанных на шаге 2 значений мер сходства и включения (см. табл. 5.5) строятся соответствующие матрицы размерностью q x q (табл. 5.6, 5.7).



Матрица мер сходства симметрична относительно главной диагонали, а матрица мер включения таким свойством в общем случае не обладает. В приведенной матрице включения число 0,57 (первый столбец и вторая строка) соответствует W(S1; S2), а число 0,67 (второй столбец и первая строка) соответствует W(S2, S1). Таким образом, индекс при названии первого множества в скобках указывает номер столбца, а второго — номер строки матрицы включения. При построении матрицы сходства индекс при первом множестве в мере сходства указывает номер строки матрицы, а при втором — номер столбца.

Шаг 4. Задается отношение сходства или включения в следующем виде:


где Δ — произвольное число (0 £ Δ £ 1,0); i, j Î J.

Для заданного значения Δ строится матрица сходства [СΔ] или включения [BΔ], в которой все значения, большие или равные Δ, заменяются единицами, а оставшиеся — нулями.

Примеры матриц [С0,60] и [B0,67] Для значений Δ ³ 0,60 и Δ ³ 0,67 приведены в табл. 5.8, 5.9.



Матрицы [С0,60] и [B0,67] отображены соответственно графами и орграфами отношений сходства и включений (рис 5.3). Дуги и стрелки соединяют те объекты, которые имеют единицу на пересечении соответствующих строк и столбцов матриц.


Направление стрелки в графе отношений включения устанавливается таким образом, что она начинается в вершине графа, соответствующей Si-му объекту, принадлежащему i-й строке матрицы, и заканчивается в Sj-м объекте, принадлежащем j-му столбцу матрицы. При этом Si-й и Sj-й объекты должны быть связаны отношением включения, т. е. иметь на пересечении Si-го и Sj-го объектов в матрице отношений включения единицу. Чем больше стрелок входит в тот или иной объект, тем более он оригинален по сравнению с другим объектом. Например, наиболее оригинальным является объект S2, так как в него входят три стрелки (рис. 5.3б).

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

Алгоритм построения иерархической классификация (дендрограммы)

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

Шаг 1. Определяются два множества: множество исследуемых объектов J= {S1, S2, ..., Sq} и множество признаков Z = {Z1, Z2, ..., Zp}. Экспертно формируются индексированные множества по каждому объекту. Строится матрица сходства


где Sij — значение меры сходства объекта Si с объектом Sj;

q — число анализируемых объектов.

Последующую иллюстрацию алгоритма осуществим на примере матрицы сходства {см. табл. 5.6).

Шаг 2. Просматриваются все элементы матрицы сходства [С], расположенные выше главной диагонали. Определяется и метится элемент, имеющий максимальное значение меры сходства С (Si, Sj)max (данный элемент не принадлежит к элементам главной диагонали). Для рассматриваемой матрицы сходства таким элементом является С (S4, S5) = 0,75. Если в матрице сходства более одного элемента с одинаковым максимальным значением, то отбирается и метится любой их них.

Шаг 3. Определяются номера i-й строки j-го столбца, на пересечении которых расположен отмеченный на шаге 2 элемент. Из матрицы сходства извлекаются все значения, соответствующие i-й строке и j-му столбцу, из которых формируются два массива значений мер сходства:

Hi=Si

S1

S2

S3

S4

S5

S6

S7

С(S4, Si)

0,44

0,60

0

1

0,75

0,25

0,67

C(S5, Si)

0,55

0,5

0,73

0,75

1

0,60

0,55

Ш а г 4. Определяется мера сходства классов G (Н, Н^) одним из методов, описываемых обобщенной формулой (5.6). Используем метод медианы. Тогда


С учетом метода медианы имеем

Hi=Si

S1

S2

S3

S4, S5

S6

S7

С(S4,5, Si)

0,50

0,55

0,37

1

0,43

0,61

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

S1

S2

S3

S4,5

S6

S7

S1

1

0,62

0,50

0,55

0,55

0,5

S2

0,62

1

0,46

0,55

0,50

0,62

S3

0,50

0,46

1

0,37