|
правило отказа, например, на основе требования достаточного превышения количества «своих» изображений над «чужими». Наибольшее влияние на классификатор по ближайшему соседу оказывает правильный выбор набора прототипов. Для распознавания образов, как правило, используются признаковые пространства высокой размерности. С ростом размерности, с одной стороны, экспоненциально возрастает число прототипов, необходимое для покрытия пространства с заданной плотностью. С другой стороны, число возможных прототипов обычно лимитируется размером оперативной памяти компьютера и требованиями к скорости классификации. В результате подобного конфликта возникает задача компромиссного поиска на множестве имеющихся эталонных векторов такого их подмножества, которое в «рабочем» режиме дает наилучшие показатели в условиях заведомой недостаточности данных. Для решения этой задачи предлагались различные приемы, подавляющее большинство которых базируется на идее кластерного анализа, который рассмотрен в следующем разделе. Кластерный анализ Задача кластерного анализа состоит в том, чтобы для заданного (большого) обучающего множества объектов найти небольшое число эталонных объектов (центров кластеров), которые, с точки зрения заданного критерия оптимизации, представляют обучающее множество наилучшим образом. В ходе решения задачи кластеризации все объекты обучающего множества обычно относятся к какому-то одному эталонному объекту', в результате чего обучающее множество разбивается на подмножества, называемые кластерами. Для решения задачи распознавания изображений необходимы такие приемы кластерного анализа, которые способны свести большое число обучающих изображений (Ь = 105-107) к небольшому числу кластеров К 10-104 (1-100 эталонов на класс, умноженные на 10-100 классов), то есть Ь » К> I. При таких масштабах задачи все приемы кластеризации, использующие метод полного перебора вариантов разбиения множества на кластеры, и приемы, требующие построения полной матрицы расстояний между изображениями, становятся неприемлемыми. 45 |
точность, которую можно ожидать в данном случае. Практическое же использование этого классификатора обычно ограничивается не его точностью, а вычислительными ресурсами компьютера, необходимыми для его работы [49]. Существует много обобщений и улучшений базовой схемы работы классификатора. Их можно условно разделить на три группы: выбор функции расстояния, выбор решающего правила и выбор прототипов. Выбор функции расстояния важен в силу того обстоятельства, что выбор окрестности по евклидову расстоянию предполагает равноправные измерения. Поэтому, как минимум, необходимо нормализовать масштаб осей. В случае сильно коррелированных признаков вместо евклидова часто используется расстояние Махаланобиса. Выбор решающего правила возможен тогда, когда в рассматриваемую окрестность включается более одного изображения. Обычно применяется простое голосование по мажоритарной схеме, возможно, с взвешиванием изображений по удаленности отточки. В зависимости от типа задачи, можно также сформулировать правило отказа, например, на основе требования достаточного превышения количества «своих» изображений над «чужими». Наибольшее влияние на классификатор по ближайшему соседу оказывает правильный выбор набора прототипов. Для распознавания образов, как правило, используются признаковые пространства высокой размерности. С ростом размерности, с одной стороны, экспоненциально возрастает число прототипов, необходимое для покрытия пространства с заданной плотностью. С другой стороны, число возможных прототипов обычно лимитируется размером оперативной памяти компьютера и требованиями к скорости классификации. В результате подобного конфликта возникает задача компромиссного поиска на множестве имеющихся эталонных векторов такого их подмножества, которое в «рабочем» режиме дает наилучшие показатели в условиях заведомой недостаточности данных. Для решения этой задачи предлагались различные приемы, однако подавляющее большинство из них базируется на идее кластерного анализа, который рассмотрен в следующем разделе. 26 Кластерный анализ Задача кластерного анализа состоит в том, чтобы для заданного (большого) обучающего множества объектов найти небольшое число эталонных объектов (центров кластеров), которые с точки зрения заданного критерия оптимизации представляют обучающее множество наилучшим образом. В ходе решения задачи кластеризации все объекты обучающего множества обычно относятся к какому-то одному эталонному объекту, в результате чего обучающее множество разбивается на подмножества, называемые кластерами. Для нужд задачи распознавания изображений необходимы такие приемы кластерного анализа, которые способны свести большое число обучающих изображений (Ь = ЮМО7) к небольшому числу кластеров К = 10-104 (1-100 эталонов на класс, умноженные на 10-100 классов), то есть Ь » К > 1. При таких масштабах задачи становятся неприменимыми все приемы кластеризации, использующие метод полного перебора вариантов разбиения множества на кластеры и приемы, требующие построения полной матрицы расстояний между изображениями. Критерий оптимизации для случая евклидова расстояния может быть сформирован следующим образом: где Гк обозначает вектор признаков обучающего изображения, а С центр кластера. Задача кластеризации обычно разбивается на подзадачи выбора оптимального разбиения обучающего множества на заданное число кластеров и выбора оптимального числа кластеров. Наиболее известным алгоритмом для первой задачи является алгоритм «Ксредних». Входные данные этого алгоритма представляют собой множество распознаваемых изображений и число кластеров К. На этапе инициализации выбирается случайным образом К изображений, которые принимаются за центры кластеров. Основной цикл работы алгоритма состоит в последовательном уточнении центров кластеров. Для этого каждое изображение условно относится к одному ближайшему кластеру. Далее для каждого кластера вычисляется центр масс всех отнесенных к нему изображений, который принимается за новый центр кластера. Процесс повторяется до тех (2.17) 27 |