ВОПРОСЫ АВТОМАТИЗИРОВАННОЙ МЕДИКО-ТЕХНИЧЕСКОЙ ДИАГНОСТИКИ (1050259), страница 2
Текст из файла (страница 2)
Общая теория распознавания образов является теоретическим фундаментом для решения основной задачи медико-технической диагностики. Эта теория занимается распознаванием образов любой природы (геометрических, звуковых, текстовых и т. п.) и представляет раздел теории управления (кибернетики). Медико-техническая диагностика разрабатывает алгоритмы распознавания применительно к задачам диагностики, которые обычно рассматривают как задачи классификации.
Алгоритмы распознавания в медико-технической диагностике основаны на диагностических моделях. Эти модели устанавливают связь между состояниями биологического объекта и их отображениями – кластерами в пространстве МБС. Важной частью проблемы распознавания являются правила принятия решений (решающие правила).
Классификация образов с помощью функций расстояния — одна из первых идей автоматического распознавания образов. Этот простой метод классификации оказывается весьма эффективным инструментом при решении таких задач, в которых классы характеризуются степенью изменчивости, ограниченной в разумных пределах. Ниже подробно рассматриваются свойства и способы реализации классификаторов, работающих на основе критерия минимума расстояния.
Например, встречаются классы, которые можно характеризовать, выбрав по одному эталонному образу из класса.
В этих случаях образы любого из рассматриваемых классов проявляют тенденцию к тесной группировке вокруг некоторого образа, являющегося типичным или репрезентативным для соответствующего класса. Подобные ситуации возникают, если изменчивость образов невелика, а помехи легко поддаются учету.
Типичным примером служит задача считывания банковских чеков с помощью ЭВМ. Символы, помещаемые на чеках, сильно стилизованы и обычно наносятся магнитной печатной краской с тем, чтобы упростить процесс снятия показаний. В ситуациях, подобных этой, векторы измерений (образы) в каждом классе будут почти идентичны, поскольку одинаковые символы на всех практически используемых чеках идентичны. В таких условиях классификаторы, действующие по принципу минимального расстояния, могут оказаться чрезвычайно эффективным средством решения задачи классификации.
Иногда классы характеризуют, выбрав несколько эталонов из класса.
Допустим, что каждый класс можно охарактеризовать не единственным, а несколькими эталонными образами. Т. е. любой образ, принадлежащий классу А, проявляет тенденцию к группировке вокруг одного из эталонов Z1, Z2...ZNI, где ni — количество эталонных образов, определяющих i-й класс. В этом случае нужно воспользоваться иным классификатором.
Выбор функций расстояния в качестве инструмента классификации является естественным следствием того обстоятельства, что наиболее очевидный способ введения меры сходства для векторов образов, интерпретируемых нами также как точки в евклидовом пространстве — определение их близости.
В частности, изучая рис. 5, можно прийти к интуитивному выводу о принадлежности вектора X классу С1 исключительно из тех соображений, что этот вектор находится ближе к векторам образа класса С1, чем класса С2.
Рис. 10.1. Образы, поддающиеся классификации с помощью понятия близости.
Можно рассчитывать на получение удовлетворительных практических результатов при классификации образов с помощью функций расстояния только в тех случаях, когда классы образов обнаруживают тенденцию к проявлению кластеризационных свойств.
Интуитивным идеям необходимо придать общую форму и развить их на уровне соответствующей математической строгости.
Поскольку близость данного образа к образам некоторого класса используется в качестве критерия для его классификации, такой подход называют классификацией образов по критерию минимума расстояния. Так как кластеризационные свойства весьма существенно влияют на работу автоматических классификаторов, основанных на концепции расстояния, предложено несколько алгоритмов отыскания кластеров.
Необходимо отметить, что выявление кластеров во многих отношениях является «искусством» весьма эмпирическим. Качество работы определенного алгоритма зависит не только от характера анализируемых данных, но в значительной степени определяется выбранной мерой подобия образов и методом, используемым для идентификации кластеров в системе данных. Соответствующие понятия, рассматриваемые ниже, обеспечивают основу для построения систем распознавания без учителя.
На формальном уровне для определения кластера на множестве данных, необходимо в первую очередь ввести меру сходства (подобия), которая может быть положена в основу правила отнесения образов к области, характеризуемой некоторым центром кластера.
Ранее, на примере температуры тела, рассматривалось евклидово расстояние между образами х и z:
D = || x – z ||; (2.1)
Эту характеристику используют в качестве меры сходства соответствующих образов: чем меньше расстояние между ними, тем больше сходство. На этом понятии основаны алгоритмы, рассматриваемые далее.
М
еры сходства не исчерпываются расстояниями. В качестве примера можно привести неметрическую функцию сходства
(2.3)
представляющую собой косинус угла, образованного векторами х и z, и достигающую максимума, когда их направления совпадают. Этой мерой сходства удобно пользоваться в тех случаях, когда кластеры обнаруживают тенденцию располагаться вдоль главных осей. Следует, однако, отметить, что использование данной меры сходства связано определенными ограничениями, например такими, как достаточная удаленность кластеров друг от друга и от начала координат.
Проблема определения процедуры разбиения анализируемых данных на кластеры остается открытой и после выбора меры сходства образов. Критерий кластеризации может либо воспроизводить некие эвристические соображения, либо основываться на минимизации (или максимизации) какого-нибудь показателя качества.
При эвристическом подходе решающую роль играют интуиция и опыт. Он предусматривает задание набора правил, которые обеспечивают использование выбранной меры сходства для отнесения образов к одному из кластеров. Евклидово расстояние хорошо приспособлено для подобного подхода, что связано с естественностью его интерпретации как меры близости. Поскольку, однако, близость двух образов является относительной мерой их подобия, обычно приходится вводить порог, чтобы установить приемлемые степени сходства для процесса отыскания кластеров.
Подход к кластеризации, предусматривающий использование показателя качества, связан с разработкой процедур, которые обеспечивают минимизацию или максимизацию выбранного показателя качества.
Одним из наиболее популярных показателей является сумма квадратов ошибки
(2.4)
где Nc — число кластеров, Sj — множество образов, относящихся к j-му кластеру,
(2.5)
вектор выборочных средних значений для множества Sj; Nj - число образов, входящих во множество Sj.
Показатель качества (2.4) определяет общую сумму квадратов отклонений характеристик всех образов, входящих в некоторый кластер, от соответствующих средних значений по кластеру. Алгоритм, основанный на этом показателе качества, рассматривается ниже.
Естественно, существуют другие показатели качества. Вот некоторые широко распространенные показатели: среднее квадратов расстояний между образами в кластере; среднее квадратов расстояний между образами, входящими в разные кластеры; показатели, основанные на понятии матрицы рассеяния; минимум и максимум дисперсии, а также еще дюжина показателей качества, использовавшихся прежде.
Нередко применяются алгоритмы отыскания кластеров, основанные на совместном использовании эвристического подхода и показателя качества. Подобной комбинацией является алгоритм ИСОМАД, рассматриваемый.
В свете предыдущих замечаний о состоянии дел в области кластеризации это обстоятельство нельзя назвать неожиданным, так как качество отдельных алгоритмов отыскания кластеров в значительной степени определяется способностями его авторов по части извлечения полезной информации из анализируемых данных.
Алгоритмы, рассматриваемые ниже, служат для этого хорошей иллюстрацией.
Простой алгоритм выявления кластеров. Пусть задано множество N образов {х1, х2 ... хN}. Пусть также центр первого кластера zi совпадает с любым из заданных образов и определена произвольная неотрицательная пороговая величина Т; для удобства можно считать, что zi = xi.
Вычисляется расстояние D2i между образом х2 и центром кластера zi по формуле (2.1). Если это расстояние больше значения пороговой величины Т D2i > Т, то учреждается новый центр кластера z2 = х2. В противном случае образ Х2 включается в кластер, центром которого является zi.
Пусть условие D2i > Т выполнено, т. е. z2 — центр нового кластера. На следующем шаге вычисляются расстояния D31 и D32 от образа х3 до центров кластеров z1 и z2. Если оба расстояния оказываются больше порога Т, то учреждается новый центр кластера z3 = x3. В противном случае образ х3 зачисляется в тот кластер, чей центр к нему ближе.
Подобным же образом расстояния от каждого нового образа до каждого известного центра кластера вычисляются и сравниваются с пороговой величиной — если все эти расстояния превосходят значение порога Т, учреждается новый центр кластера. В противном случае образ зачисляется в кластер с самым близким к нему центром.
Результаты описанной процедуры определяются выбором первого центра кластера, порядком рассмотрения образов, значением пороговой величины Т и, конечно, геометрическими характеристиками данных. Эти влияния иллюстрируются рис. 8, на котором представлены три различных варианта выбора центров кластеров для одних и тех же данных, возникшие в результате изменения только значения порога Т и исходной точки кластеризации.
Простой алгоритм выявления кластеров обладает рядом очевидных недостатков. Однако он позволяет просто и быстро получить приблизительные оценки. основных характеристик заданного набора данных. Кроме того, этот алгоритм привлекателен с вычислительной точки зрения, так как для выявления центров кластеров, соответствующих определенному значению порога Т, требуется только однократный просмотр выборки.
Рис. 10.2. Иллюстрация влияния выбора величины порога и исходных точек
Практически, чтобы хорошо понять геометрию распределения образов с помощью такой процедуры, приходится проводить многочисленные эксперименты с различными значениями порога и различными исходными точками кластеризации. Поскольку изучаемые образы обычно имеют высокую размерность, визуальная интерпретация результатов исключается. Поэтому необходимая информация добывается в основном при помощи сопоставления после каждого цикла просмотра данных расстояний, разделяющих центры кластеров, и количества образов, вошедших в различные кластеры.
Полезными характеристиками являются также ближайшая и наиболее удаленная от центра точки кластера и различие размеров отдельных кластеров. Информацию, полученную таким образом после каждого цикла обработки данных, можно использовать для коррекции выбора нового значения порога Т и новой исходной точки кластеризации в следующем цикле. Можно рассчитывать на получение с помощью подобной процедуры полезных результатов в тех случаях, когда в данных имеются характерные «гнезда», которые достаточно хорошо разделяются при соответствующем выборе значения порога.
Алгоритм К внутригрупповых средних. Алгоритм, рассмотренный выше, является в сущности эвристической процедурой. Алгоритм К внутригрупповых средних, представленный ниже, минимизирует показатель качества, определенный как сумма квадратов расстояний всех точек, входящих в кластерную область, до центра кластера. Эта процедура, которую часто называют алгоритмом, основанным на вычислении К внутригрупповых средних, состоит из следующих шагов.
Шаг 1. Выбираются K исходных центров кластеров z1(l), z2(l) , ..., zK(l). Этот выбор производится произвольно, и обычно в качестве исходных центров используются первые К результатов выборки из заданного множества образов.
Шаг 2. На k-м шаге итерации заданное множество образов {х} распределяется по К кластерам по следующему правилу:
(2.6)
для всех i - 1, 2 ..... К, i j, где Sj (k) — множество образов, входящих в кластер с центром zj(k). В случае равенства в (2.6) решение принимается произвольным образом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
