Проверяемый текст
Терещенко Вадим Владиславович. Разработка и реализация новых принципов автоматического распознавания рукописных документов в компьютерных системах обработки данных (Диссертация 2000)
[стр. 46]

Критерий оптимизации, для случая евклидова расстояния, может быть сформирован следующим образом: где г* обозначает вектор признаков обучающего изображения, а С^ центр кластера.
Задача кластеризации обычно разбивается на подзадачи выбора оптимального разбиения обучающего множества на заданное число кластеров и выбора оптимального числа кластеров.
Наиболее известным алгоритмом для первой задачи является алгоритм «Ксредних».
Входные данные этого алгоритма представляют собой множество распознаваемых изображений и число кластеров К.
На этапе инициализации выбирается случайным образом К изображений, которые принимаются за центры кластеров.
Основной цикл работы алгоритма состоит в последовательном уточнении центров кластеров.
Для этого каждое изображение условно относится к одному ближайшему кластеру.
Далее для каждого кластера вычисляется центр масс всех отнесенных к нему изображений, который принимается за новый центр кластера.
Процесс повторяется до тех
пор, пока он не сойдется или пока не будет достигнут предел по числу итераций.
На основе этого базового варианта алгоритма было разработано большое количество разнообразных модификаций.
Существуют и более совершенные методики.
Например, в работе
[51] предлагается вариационный подход к общей задаче классификационного анализа данных.
За счет использования размытой постановки задачи обобщаются многие частные постановки этой задачи.
Для оценки качества размытой функции используется широкий класс выпуклых функционалов, который включает значительную часть известных критериев качества.
Описанный алгоритм классификации включает в себя,
(2.17) 46
[стр. 27]

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

[стр.,28]

пор, пока он не сойдется или пока не будет достигнут предел по числу итераций.
На основе этого базового варианта алгоритма было разработано большое количество разнообразных модификаций.
Существуют и более совершенные методики.
Например, в работе
[50] предлагается вариационный подход к общей задаче классификационного анализа данных.
За счет использования размытой постановки задачи обобщаются многие частные постановки этой задачи.
Для оценки качества размытой функции используется широкий класс выпуклых функционалов, который включает значительную часть известных критериев качества.
Описанный алгоритм классификации включает в себя
как частный случай такие известные алгоритмы как 18СЮАТА и РИ22У 18СЮАТА [51].
Для работы с очень большими множествами обучающих изображений разработаны последовательные методы кластеризации [43, 44], которые не требуют присутствия всего множества изображений в памяти компьютера.
Суть этих методов сводится к тому, что изображения предъявляются по одному.
Для каждого предъявленного изображения определяется ближайший кластер Гк, который слегка сдвигается в направлении изображения у;.
на величину, определяемую скоростью обучения а: гк(Н1) = гк(0 + а-(Уд.Гк(0) (2.18) Для решения подзадачи выбора правильного числа кластеров, к сожазению не существует простого универсального критерия оптимизации.
Критерий (2.17) здесь неприменим, так как его можно свести к нулю простым увеличением числа кластеров.
Выбор правильного числа кластеров обычно требует учета целевых критериев всей системы, например числа ошибок при классификации.
Задача решается, как правило, путем прямого перебора по числу кластеров.
11роцедура кластеризации повторяется для каждого числа кластеров, и затем вычисляется значение целевой функции.
Существуют комбинированные приемы выбора числа и положения кластеров.
Например, в методе последовательного уточнения кластеризации все обучающее множество изображений изначально рассматривается как один большой кластер.
Шаг алгоритма состоит в выборе одного кластера и разбиения его на две части.
Алгоритм останавливается тогда, когда в результате очередного шага получилось разбиение на кластеры, уступающее предшествующему разбиению по значению целевой функции.
Для 28

[Back]