Матрица образов анализируемых объектов
Второй этап установление списка признаков и их значений, подлежащих учету на отдельных объектах. В список включаются признаки, наиболее полно характеризующие изучаемые объекты в смысле заданной цели.
Из рассмотрения исключаются признаки, имеющие слабые разделительные свойства.
Третий этап отбор репрезентативной выборки объектов и производство измерений.
Четвертый этап выбор отношений на множестве описаний объектов; мер, порождающих отношения; решающих правил и критериев эффективности. Здесь же производятся вычисления.
Пятый этап построение и анализ структурной схемы системы, в которой связи между элементами соответствуют выполнению отношений между ними. Способом представления структурных схем являются графы и дендрограммы.
Шестой этап интерпретация полученных результатов, т. е. перенос полученных утверждений с системы-модели на систему-прототип.
Первые три этапа построения систем-классификаций составляют творческую часть процедуры классификации, которая целиком зависит от исследователя и не может быть формализована.
На четвертом и пятом этапах классификации требуется перерабатывать большой объем информации по определенным правилам логики. В связи с этим актуальной становится задача формализации процедур на этих этапах и реализации их в виде компьютерных систем.
Виды измерений
Системы, подлежащие классификации, изучаются прежде всего относительно наличия у них характерных свойств или состояний, которые отражаются различными признаками. Значения признаков могут измеряться с различной точностью.
Для измерения признаков применяются шкалы наименований, порядка, отношений, балльные, интервалов.
При использовании шкалы наименований указывается только, одинаковы или нет объекты относительно измеряемого признака.
Порядковые или ранговые признаки сравниваются только по отношению больше меньше.
Более точные измерения предполагают и большее число значений. В этом случае используются балльные шкалы.
Значения балльной шкалы представляют собой ограниченный дискретный ряд чисел, отстоящих друг от друга на одинаковом расстоянии.
При дальнейшем увеличении точности измерений число значений можно увеличивать, доводя его до максимально осуществимого.
Условно все виды оценок делят на качественные и количественные. В соответствии с рекомендациями, приведенными в работе [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Δ, BΔ соответственно отношения сходства, различия и включения; Δ некоторое произвольное число (0 ≤ Δ ≤ 1,0 для отношения сходства и включения). Записи Sj СΔ Sk и Sj BΔ Sk означают соответственно то, что Sj и Sk находятся в отношении Δ-сходства и Δ-банальности. Отношение банальности или экзотичности порождается мерой включения. При этом запись Sj BΔ Sk означает, что описание Sj банальнее Sk при пороге Δ. Например, если рассчитанные для пары объектов меры включения имеют следующие значения: 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 | 0,73 | 0,33 |
| S4,5 | 0,50 | 0,55 | 0,37 | 1 | 0,43 | 0,61 |
| S6 | 0,55 | 0,50 | 0,73 | 0,43 | 1 | 0,36 |
| S7 | 0,50 | 0,62 | 0,33 | 0,61 | 0,36 | 1 |
На данном шаге запоминаются значения индексов вновь образованного класса (S4,5) и меры сходства, при которой этот класс образовался, С (S4, S5) = 0,75.
Шаг 5. Процедура обработки матрицы сходства вновь начинается с шага 2. Итерационный процесс продолжается до тех пор, пока размерность матрицы сходства не уменьшится до 2 х 2. На этом процесс построения иерархической классификации заканчивается.
В результате работы алгоритма определяются перечень индексов классов в том порядке, в котором они объединялись в новые классы, а также уровни сходства, на которых это объединение происходило. Для рассматриваемого примера имеем следующие результаты:
Полученные результаты используются для построения дендрограмм. Дендрограмма делает наглядной структуру иерархической классификации. В данном примере (рис.
5.4) наибольшим сходством обладают классы S4 и S5, наименьшим классы Н5 = {S1, S2, S4, S5, S7} и Н2= {S3, S6}.
Мера сходства на основе экспертной оценки
Для повышения точности определения сходства исследуемых объектов меру сходства можно формировать на основе экспертной оценки.
Экспертная оценка сходства объектов проводится двумя способами.
Способ 1. Для рассматриваемых объектов первоначально определяется множество признаков {fij }.
На основе множеств признаков и рассматриваемых объектов для последних строится матрица образов, в которой принадлежность признака объекту Si отображается единицей, а отсутствие нулем (табл. 5.10).
Таблица 5.10
Матрица образов анализируемых объектов Все значения каждого признака сравниваются попарно экспертом, который формирует матрицы сходства признаков. Далее составляются матрицы сходства объектов по каждому признаку и на их основе рассчитывается интегральная матрица сходства. Значения мер сходства объектов интегральной матрицы определяются по выражению
где Cl (Si, Sj) значение меры сходства двух объектов по l-му признаку;
ρl(Si, Sj) весовой коэффициент l-го признака, характеризующий его вклад в интегральное значение меры сходства
т число признаков, по которым оценивается сходство объектов.
Значение Сl (Si, Sj) определено в интервале {0...1}, причем Cl(Si, Sj) = 1 при i =j.
Способ 2. Мера сходства между альтернативами устанавливается экспортно по одному или нескольким критериям качества, таким, как качество выполнения основных функций, надежность, технологичность, экологичность, эстетичность и т. д.
Вычисление интегрального значения меры сходства альтернатив по нескольким критериям качества осуществляется по технологии, аналогичной той, которая использовалась в первом способе. Отличие состоит лишь в том, что во втором способе индекс l=1,т в формуле (5.7) обозначает принадлежность к l-му критерию качества, а т-число критериев качества, учитываемых в рассмотрении.
Экспертные методы оценки меры сходства объектов позволяют проводить более точный анализ по сравнению с методом, основанным на обработке качественных бинарных признаков. Однако экспертные методы требуют привлечения высококвалифицированных специалистов, что не всегда бывает возможно, а также существенно повышают время предварительного анализа объектов. Поэтому при анализе большого числа объектов (сотни или тысячи единиц) со значительным числом признаков, характеризующих эти объекты, целесообразно проводить различные классификационные построения в два этапа.
На первом этапе, не используя экспертные методы оценки сходства, проводить грубое усечение исходного множества объектов, а на втором выполнять более тонкие исследования, применяя экспертные методы оценки мер сходства (различия) объектов.
Обработка количественных признаковых образов
При учете данного подхода многие меры сходства, различия, включения и т. д. можно определять для описаний, состоящих из количественных признаков.
Пусть дано два объекта S1 и S2, которые охарактеризованы экспортно по множеству критериев качества: К1 надежность, К2 технологичность, К3 стоимость, К4 компактность. Описания объектов имеют следующие количественные значения критериев:
Требуется найти меры сходства и включения описаний S1 и S2.
Из приведенных примеров видно, что при определении числа пересечений двух множеств подсчитывается сумма минимальных значений, образующих эти множества, а при определении числа элементов множества суммируются все его значения.
Определение оригинальных и типовых систем
На основе матриц сходства и включения можно установить наиболее типовые системы или, напротив, наиболее оригинальные. Выявление указанных закономерностей осуществляется методом определения правого собственного вектора указанных матриц.
При обработке матрицы сходства максимальное значение ее правого собственного вектора будет соответствовать наиболее типовому элементу, т. е. наиболее схожему со всеми остальными рассматриваемыми в этой матрице объектами. Минимальное значение в правом собственном векторе матрицы включения характеризует наиболее оригинальный (экзотичный) объект.
