Анализ, синтез, планирование решений в экономике (стр. 43 из 65)

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

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

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

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

где G(H_j,H_k) — мера сходства или различия классов H_j и H_k = {Н_и ,H_l}.

Здесь n_u, n_k — число объектов соответственно u-го и k-го классов; п_k = n_u + n_l.

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

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

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

Шаг 1. Формируются два множества: множество исследуемых объектов J = { S₁, S₂,..., S_q} и множество признаков Z = { Z₁, Z₂,..., Z_p}. Каждый объект S_i описывается подмножеством признаков {Z_i} Î Z, являющимся качественным признаковым образом. Все образы объектов систематизируются в матрицу образов, где представляются индексированными множествами (табл. 5.5).

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

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

Таблица 5.5

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

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

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

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

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

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

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

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

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

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

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

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

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

Шаг 1. Определяются два множества: множество исследуемых объектов J= {S₁, S₂, ..., S_q} и множество признаков Z = {Z₁, Z₂, ..., Z_p}. Экспертно формируются индексированные множества по каждому объекту. Строится матрица сходства

где S_ij — значение меры сходства объекта S_i с объектом S_j;

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

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

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

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