«Шалымов Дмитрий Сергеевич МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДЛЯ РАЗРАБОТКИ И АНАЛИЗА СИСТЕМ РАСПОЗНАВАНИЯ ОБРАЗОВ, ИСПОЛЬЗУЮЩИХ РАНДОМИЗИРОВАННЫЕ АЛГОРИТМЫ 05.13.11 Математическое и программное обеспечение вычислительных ...»

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ

УНИВЕРСИТЕТ

На правах рукописи

Шалымов Дмитрий Сергеевич

МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ

ДЛЯ РАЗРАБОТКИ И АНАЛИЗА

СИСТЕМ РАСПОЗНАВАНИЯ ОБРАЗОВ,

ИСПОЛЬЗУЮЩИХ

РАНДОМИЗИРОВАННЫЕ АЛГОРИТМЫ

05.13.11 Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель д. ф.-м. н., проф. О.Н.Граничин Санкт-Петербург 2009 Оглавление Введение............................... 1 Задачи распознавания образов, классификации и кластеризации 1.1 Распознавание образов..................... 1.2 Формальная постановка задачи................ 1.3 Примеры задач распознавания образов........... 1.3.1 Распознавание слов речи............... 1.3.2 Распознавание печатных текстов на арабском языке................... 1.4 Программные средства аналитического ПО....................... 2 Рандомизированные алгоритмы кластеризации 2.1 Алгоритмы кластеризации при известном количестве кластеров............. 2.2 Состоятельность оценок алгоритма РАСА в задаче распознавания слов речи.......... 2.3 Устойчивость и качество кластеризации........... 2.4 Рандомизированный метод определения количества кластеров.............. 2.5 Доказательства теорем..................... 3 Программный комплекс для разработки и анализа систем распознавания образов 3.1 Структура программного комплекса............. 3.2 Визуализация и снижение размерности........... 3.3 Апробация алгоритмов устойчивой кластеризации................... Заключение.............................. Литература.............................. Введение Актуальность темы. На протяжении последних десятилетий в связи со стремительным развитием цифровых технологий наблюдается значительный рост объемов хранимых и перерабатываемых данных. Однако увеличение количества информации не означает непосредственного увеличения объемов знаний. В такой ситуации все более востребованными становятся новые математические методы, которые позволяли бы распознавать образы, структурировать информацию и находить объективные закономерности в больших объемах данных. Среди них важную роль при распознавании образов играют методы выявления классов (кластеров), способные работать в режиме реального времени. О популярности этих методов сегодня свидетельствует тот факт, что результат поиска по запросу термина “classication problem” в поисковой системе Google (на сентябрь 2009 года) составил более сорока трех миллионов страниц.

Современные алгоритмы теории распознавания образов, классификации и кластерного анализа базируются на работах С.А.Айвазяна [1], А.Я.Червоненкиса, В.Н.Вапника [5, 131], Ф.Розенблатта [117], Р.А.Фишера [38], В.Н.Фомина [39], И.Форджи [78], К.Фукунаги [81], Дж.Хартигана [87], Дж.Хопфилда [90], Я.З.Цыпкина [42, 43] и др. Многие современные системы распознавания образов основаны на принципах нейронных сетей (см. С.Хайкин [40], Ф.Уоссермен [37], А.В.Тимофеев [36] и др.) Работоспособность различных алгоритмов разбиения множества данных на классы существенно зависит от количества классов (кластеров) и выбора первоначального разбиения. При априори неизвестном количестве кластеров В.Кржановским и И.Лаем [101], Дж.Дуном [75], Л.Хьюбертом и Дж.Шульцом [93], Р.Калинским и Дж.Харабазом [66], Е.Левине и Е.Домани [106], А.Бен-Гуром и И.Гийоном [61], А.Елизивом [60], В.Волковичем и др. [133], Р.Тибширани и Г.Вальтером [128] и др. активно разрабатываются методы устойчивой кластеризации, достаточно точно оценивающие количество кластеров в разнообразных прикладных задачах.

Общим недостатком традиционно используемых алгоритмов кластеризации является значительный рост вычислительной сложности при увеличении мощности исследуемого множества. В условиях многомерных задач и нарастающих объемов данных в современных работах М.Вадьясагара [132], Дж.Галафиори и М.Кампи [67], О.Н.Граничина [8], Ю.М.Ермольева [17], В.Я.Катковника [24, 25], А.И.Кибзуна и Ю.С.Кана [98], Г.Кушнера и Г.Ина [103], Б.Т.Поляка, П.С.Щербакова и А.Б.Цыбакова [30, 31, 32], Дж.Спала [125] и др. эффективно используются новые рандомизированные алгоритмы, развивающие идеи методов случайного поиска и моделирования по методу Монте-Карло, детально исследованные в русскоязычной литературе С.М.Ермаковым, А.А.Жиглявским и В.Б.Меласом [14, 15, 16], А.Жилинскасом [18], Л.А.Растригиным [33, 34] и многими другими. Сложность целого ряда новых рандомизированных алгоритмов, в англоязычной литературе получивших название SPSA (Simultaneous Perturbation Stochastic Approximation), не существенно возрастает при росте размерности данных и, кроме того, они остаются работоспособными в условиях значительных неконтролируемых воздействий, которые трудно исключить в системах реального времени.

Наряду с развитием методов распознавания образов активно разрабатываются соответствующие средства программного обеспечения как для настольных и супер компьютеров, так и для встроенных систем. Наборы библиотек с алгоритмами кластеризации входят в Matlab, SPSS, Statistica, SAS Enterprise Miner и многие другие популярные пакеты прикладных программ. Сформировано несколько больших хранилищ данных (UCI Machine Learning Repository, GEMLeR, StatLib, KDD cups и др.) для тестирования работоспособности алгоритмов и решения практически важных задач. Вместе с тем для разработки и анализа новых пользовательских систем распознавания образов не создано удобного общедоступного средства.

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

Цель достигается в диссертации через решение следующих задач:

• разработать и обосновать для распознавания образов слов в речи прототип дикторонезависимй системы, основанной на использовании рандомизированного алгоритма стохастической аппроксимации типа SPSA;

• разработать и обосновать новый рандомизированный метод устойчивой кластеризации, работоспособный в режиме реального времени;

• создать программный комплекс для разработки и анализа систем распознавания образов, использующих рандомизированные алгоритмы.

Методы исследования. В диссертации применяются методы теории оценивания и оптимизации, функционального анализа, теории вероятностей и математической статистики, имитационного моделирования и системного программирования.

Основные результаты. В работе получены следующие основные научные результаты:

1. На основе рандомизированного алгоритма стохастической аппроксимации (РАСА) и метода кепстральных коэффициентов тоновой частоты разработано программное средство для распознавания образов слов в речи. Исследованы свойства помехоустойчивости РАСА в задаче распознавания и установлены условия состоятельности доставляемых алгоритмом РАСА оценок.

2. Предложен новый рандомизированный метод определения количества кластеров в множесте данных, работоспособный в режиме реального времени.

3. Получены и теоретически обоснованы условия достоверности предложенного нового рандомизированного метода определения количества кластеров в множесте данных.

4. Создан новый программный комплекс для разработки и анализа систем распознавания образов, базирующихся на использовании рандомизированных алгоритмов классификации и кластеризации, обеспечивающий технологичность разработки новых систем распознавания образов. Проведена апробация предложенных в диссертации алгоритмов на данных различной природы.

Научная новизна. Все основные научные результаты диссертации являются новыми.

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

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

Апробация работы. Материалы диссертации докладывались на внутренних семинарах кафедры системного программирования математикомеханического факультета СПбГУ, на российских и международных конференциях по оптимизации, информатике и теории управления: The 3rd Int. IEEE Scientic Conf. on Physics and Control “PhysCon – 2007” (Potsdam, Germany, September 3-7, 2007), 5-я межд. научно-практическая конф.

“Исследование, разработка и применение высоких технологий в промышленности” (Санкт-Петербург, Россия, 28-30 апреля, 2008), The 20th Int.

Conf. “Continuous Optimization and Knowledge-Based Technologies (EUROPTNeringa, Lithuania, May 20-24, 2008), Yalta Conf. on Discrete and Global Optimization (Yalta, Ukraine, August 1-3, 2008), The ERANIS Int.

event in the elds of KBBE, ICT, NMP and Energy (Warsaw, Poland, October 10, 2008), III Межд. научно-практическая конф. “Современные информационные технологии и ИТ-образование” (Москва, Россия, 6- декабря, 2008), The 8th Int. Conf. on System Identication and Control Problems “SICPRO’09” (Moscow, Russia, January 26-30, 2009), XI конф. молодых ученых “Навигация и управление движением” (Санкт-Петербург, Россия, 10-12 марта, 2009), VI Всероссийская межвузовская конф. молодых ученых (Санкт-Петербург, Россия, 14-17 апреля, 2009), Spring Young Researchers’ Colloquium on Software Engineering “SYRCoSE” (Moscow, Russia, May 28-29, 2009), Первая традиционная всероссийская молодежная летняя школа “Управление, информация и оптимизация” (ПереславльЗалесский, Россия, 21-28 июня, 2009), VI школа-семинар молодых ученых “Управление большими системами” (Ижевск, Россия, 31 августа - сентября, 2009).

По материалам диссертации было получено свидетельство об официальной регистрации программы для ЭВМ N 2007611711 “Программная система для обучения, перевода, распознавания арабского текста” от апреля 2007 года. Результаты диссертации были частично использованы в работе по гранту РФФИ 09-04-00789-а. Доклад “Рандомизированные алгоритмы устойчивой кластеризации для динамически изменяющихся данных” на VI Всероссийской межвузовской конференции молодых ученых в СПбГУ ИТМО был отмечен дипломом “За лучший доклад аспиранта на секции”. Проект “ИнтАн: Программный комплекс интеллектуального анализа данных”, использующий во многом материалы диссертации, принял участие в смене “Инновации и Техническое творчество” в рамках молодежного форума Селигер-2009. Результаты диссертационной работы были представлены в проекте “Разработка программного комплекса кластерного анализа данных большого объема”, который победил в конкурсе “У.М.Н.И.К.” в 2009 году.

Публикации. Основные результаты диссертации опубликованы в восемнадцати работах. Из них три публикации [11,52,55] в журналах из перечня ВАК. Работы [9–11,84–85,120] написаны в соавторстве. В работах [9–11,84–85] О.Н.Граничину принадлежат общие постановки задач, а Д.С.Шалымову – реализации и обоснования описываемых методов, создание демонстрационных примеров и программных средств. В работе [120] Д.С.Шалымов является автором I–VIII секций, К.Скрыгану принадлежит участие в реализации вычислительного ядра и соавторство в IV секции, посвященной организации его внутренней структуры, Д.Любимову принадлежит участие в создании демонстрационных примеров, проиллюстрированных на рис. 3–5.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, списка литературы, включающего 136 источников. Текст занимает 126 страниц, содержит 34 рисунка и две таблицы.

Во введении обосновывается актуальность тематики диссертационной работы и кратко излагаются ее основные результаты.

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

В п. 1.1 анализируются типичные задачи распознавания образов, которые достаточно часто трактуются как классификация входных сигналов (стимулов, объектов). В процессе классификации обнаруживаются признаки, которые характеризуют группы объектов исследуемого набора данных – классы (кластеры). По этим признакам каждый сигнал можно отнести к тому или иному классу. Результатом кластеризации является разбиение сигналов на группы в условиях, когда классы заранее не определены. Получающееся разбиение естественным образом характеризует структуру множества данных и может быть использовано в дальнейшем для ее определения.

В п. 1.2 описывается формальная постановка задачи. С содержательной точки зрения процесс распознавания образов трактуется как классификация входных сигналов x из некоторого множества X, заключающаяся в построении правила сопоставления каждой точке x X некоторого образа (класса) Xk. (В диссертации для упрощения рассматриваются только задачи однозначной классификации, хотя это ограничение и не носит принципиального характера и может быть расширено.) Выбор правила классификации порождает разбиение множества X на классы. Будем считать, что правило классификации однозначно определяется конечномерным набором и задана функция l() возвращающая количество классов при классификации по правилу. Всякий способ классификации связан с потерями, которые обычно характеризуются с помощью штрафных функций стоимости q k (x, ) при отнесении точки x к классу с номером k. В типичных случаях, когда X вещественное векторное пространство, значения штрафных функций q k (x, ) возрастают при удалении x от центра соответствующего образа (класса).

В диссертации рассматривается следующее правило классификации:

при заданных и функциях q k (x, ), k = 1,..., l(), входной сигнал x из множества X относится к тому классу Xk с наименьшим номером k = k(x), для которого значение соответствующей штрафной функции q k (x, ) минимально Например, если на X задана норма · и в множестве данных l классов, а l набор векторов центров классов: l = (1, 2,..., l), то можно считать = {l, l } и в качестве q k (x, ) можно задать расстояние до центра k-го класса k : q k (x, ) = x k. При этом множество X разбивается на l классов X1 (), X2(),..., Xl () таким образом, что к классу (подмножеству) Xk () относятся все точки x, находящиеся к центру k ближе, чем к любому другому. Интеграл Xk () x k 2 определяет рассеяние точек x в подмножестве Xk ().

Предположим, что на множестве X задано распределение P(·). Определим функционал качества кластеризации по правилу :

Тогда задача кластеризации множества данных из l классов состоит в определении набора центров l, минимизирующего суммарную стоимость разбиения. Задача устойчивой кластеризации является обобщением для случая нахождения заранее неизвестного оптимального значения количества классов l и соответствующего набора центров l.

В системах, работающих в режиме реального времени в условиях изменяющейся со временем обстановки, распределение P(·) очень часто бывает неизвестно. Будем предполагать, что в режиме реального времени на вход поступает последовательность x1, x2,... сигналов, порожденная неизвестным распределением P(·). Требуется предложить алгоритм построения последовательности оценок {n} набора, минимизирующего определенный выше функционал среднего риска. Решение задачи дополнительно осложняется тем, что на практике функции q k (·, ·), k = 1, 2,..., l() не всегда заданы аналитически, но доступны измерению их значения (может быть с помехами):

В следующем пункте 1.3 описаны два примера задач распознавания образов: распознавание слов речи и распознавание печатных текстов на арабском языке.

В п. 1.4 рассматриваются основные программные средства аналитического ПО, поддерживающего методы классификации и кластеризации.

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

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

В п. 2.1 для случая известного количества классов описывается метод k -средних, предложенный Дж.Хартиганом и М.Вонгом [88], широко применяемый при стандартных предположениях о свойствах погрешностей в измерениях, и рандомизированный алгоритм стохастической аппроксимации (РАСА), предложенный О.Н.Граничиным и О.А.Измаковой [7], работоспособный при ограниченных неконтролируемых (unknown but bounded) погрешностях.

В п. 2.2 формулируется Теорема 1 о свойствах оценок РАСА алгоритма в применении к задаче о дикторонезависимом распознавании образов слов речи. В предлагаемом новом способе звуковые сигналы последовательно преобразуются методом кепстральных коэффициентов (MKK) тоновой частоты в конечномерные вектора характеристических свойств размерности n 4000, подаваемые впоследствии на вход алгоритма РАСА с двумя измерениями целевой функции на каждой итерации. Исходные элементы множества речевых сигналов принадлежат пространству с очень большой размерностью n 32000, зависящей от частоты дискретизации аналого-цифрового преобразователя (АЦП).

Далее в п. 2.3 описываются несколько способов определения априори неизвестного количества кластеров в множестве данных X, основные идеи которых сводятся к заданию максимально возможной верхней границы lmax и вычислению некоторых индексных функций Ind(l), характеризующих оптимальные разбиения множества X на l классов. Многие из таких функций строятся через степени рассеяния внутри класса, определяющие т. н. “искажения”. В работе К.Сьюгер и Г.Джеймса [127] обоснована целесообразность использования индексных функций вида Ind(l) = I(Dl ), где для анализа кривой “искажений” Dl : [1, lmax] R, которая монотонно убывает с ростом l. В частности предлагается рассчитывать I(D) = (Dl )n/2. При этом трудоемкость алгоритмов прямопропорциональна размерности фазового пространства, выбору максимального количества кластеров lmax и среднему времени на кластеризацию при заданном l.

Существенное сокращение трудоемкости достигается при использовании описанного в п. 2.4 нового рандомизированного алгоритма достоверного определения количества кластеров с задаваемой вероятностью, который является развитием идей К.Сьюгер и Г.Джеймса [127].

В Теореме 2 сформулированы условия для нахождения оптимального значения количества кластеров с определенной вероятностью.

Доказательства теорем приведены в п. 2.5.

В третьей главе описана разработанная автором система для анализа и тестирования алгоритмов классификации и кластеризации. В п. 3. описана структура программного комплекса, п. 3.2 посвящен вопросам визуализации данных и методам снижения размерности, в п. 3.3 описана апробация алгоритмов устойчивой кластеризации.

Система была реализована на языке Java с использованием технологий JSP, JDBC, JavaServlets, Xml-RPC, JavaScript, сервлет-контейнера Tomcat и сервера базы данных MySQL, а также с использованием вычислительного ядра, реализованного на С Sharp. Система позволяет структурировать уже известную информацию об алгоритмах классификации и кластеризации, а также исследовать новые эффективные методы.

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

Глава Задачи распознавания образов, классификации и кластеризации 1.1 Распознавание образов Для того, чтобы распознать какой-либо объект, необходимо сначала определить его признаки. Например, измерив его. Помимо признаков, соответствующих измерениям объекта, существует так же выделенный признак, либо группа признаков, которые называются классифицирующими признаками. В выяснении их значений состоит задача, которую выполняют естественные и искусственные распознающие системы.

Чтобы установить значения признаков объекта, необходимо иметь информацию о том, как связаны известные признаки с классифицирующими. Информация об этой связи задается в форме прецедентов, то есть множества описаний объектов с известными значениями классифицирующих признаков. По этой прецедентной информации требуется построить решающее правило, которое будет ставить в соответствие произвольному описанию объекта значения его классифицирующих признаков.

Такое понимание задачи распознавания образов утвердилось в науке, начиная с 50-х годов прошлого века. И тогда же было замечено, что такая постановка вовсе не является новой. С подобной формулировкой сталкивались ранее, и уже существовали не плохо зарекомендовавшие себя методы статистического анализа данных, которые активно использовались для многих практических задач, таких как, например, техническая диагностика. Поэтому первые шаги распознавания образов прошли под знаком статистического подхода, который и диктовал основную проблематику. Так, например, работы Р.Фишера [38], выполненные в 20-х годах, привели к формированию дискриминантного анализа как одного из разделов теории и практики распознавания. Задачей о разделении смеси двух распределений в 30-х годах занимались А.Н.Колмогоров [27] и А.Я.Хинчин [41].

Статистический подход основывается на идее, что исходное пространство объектов представляет собой вероятностное пространство, а признаки (характеристики) объектов – случайные величины, заданные на нем.

Наиболее часто применяемыми статистическими алгоритмами являются алгоритмы типа линейного дискриминанта Фишера [38, 77], парзеновского окна [114], EM-алгоритма [71], метода ближайших соседей [1], байесовских сетей доверия [79] и др. Большинство из них имеют сильно выраженный эвристический характер и могут иметь интерпретации отличные от статистических.

Задача исследователя данных состоит в том, чтобы из некоторых соображений выдвинуть статистическую гипотезу о распределении признаков, а точнее, о зависимости классифицирующих признаков от остальных. Статистическая гипотеза, как правило, представляет собой параметрически заданное множество функций распределения признаков. Типичной и классической статистической гипотезой является гипотеза о нормальности этого распределения. После формулировки гипотезы остается проверить эту гипотезу на прецедентных данных. Эта проверка состоит в выборе некоторого распределения из первоначально заданного множества распределений (параметра гипотезы о распределении) и оценки надежности (доверительного интервала) этого выбора. Собственно эта функция распределения и является ответом к задаче, только объект классифицируется уже не однозначно, а с некоторыми вероятностями принадлежности к классам [77].

Пусть в пространстве Rn задано конечное число объектов двух классов X1 и X2. Объекты классов X1 и X2 появляются с некоторыми неизвестными вероятностями PX1 и PX2, а их распределения подчиняются нормальному закону. Требуется построить решающее правило, которое разделяло бы пространство Rn на два подмножества – объекты класса X1 и X2, и причем с малой вероятностью ошибалось бы на внешних данных. Р.Фишер [77] предложил следующее решение: вначале оценить по обучающей выборке вероятности PX1 и PX2, а затем оценить математические ожидания и ковариационные матрицы нормальных законов элементов из X1 и X1. Нормальные законы обозначим как N (x, E, ), где E – матожидание, а – ковариационная матрица. Решающее правило имело следующий вид: объект классифицировался как X1, если PX1 N (x, EX1, X1 ) > PX2 N (x, EX2, X2 ), и как X2 – в противном случае.

Обосновывается этот алгоритм следующим образом. При достаточно большой величине обучающей выборки вероятности PX1 и PX2 оцениваются с большой точностью по закону больших чисел [56]. Параметры (EX1, X1 ) и (EX2, X2 ) оцениваются, соответственно, по частям выборки классов X1 и X2 c помощью стандартных статистик, доверительные интервалы которых стремятся к нулю при увеличении числа точек, по которым они оцениваются.

В случае, когда нормальные распределения достаточно хорошо отстоят относительно друг друга, можно с большой вероятностью (которая может быть оценена) ожидать правильной классификации.

В повседневной жизни люди постоянно решают проблемы распознавания различных ситуаций, слуховых и зрительных образов. Отсюда некоторыми исследователями был сделан вывод, что решение этих проблем на ЭВМ должно в общих чертах моделировать процессы человеческого мышления. Наиболее известной попыткой подойти к проблеме с этой стороны было знаменитое исследование Ф.Розенблатта [117], который разработал модель обучения распознаванию зрительных образов, названную им персептроном. Схема работы персептрона Розенблатта изображена на рис. 1.1.

На входе персептрон получает вектор объекта X = (x1, x2,..., xn)T, который в работах Розенблатта предсталял собой бинарный вектор, показывавший, какой из пикселов экрана зачернен изображением, а какой нет. Далее каждый из признаков подается на вход нейрона, действие которого на значение xi представляет собой умножение на некоторый вес нейрона wi. Результаты подаются на последний нейрон, который их складывает и общую сумму сравнивает с некоторым порогом w0. В зависимости от результатов сравнения входной объект X признается нужным образом либо нет. Задача обучения распознаванию образов состояла в таком подборе весов нейронов wi и значения порога w0, чтобы персептрон давал на прецедентных зрительных образах правильные ответы. Этот подход оказался успешным в ряде задач распознавания и породил собой целое направление исследований алгоритмов обучения, основанных на нейронных сетях, частным случаем которых и является персептрон.

Далее были придуманы различные обобщения персептрона, функция нейронов была усложнена: нейроны теперь могли не только умножать входные числа или складывать их и сравнивать результат с порогами, но применять по отношению к ним более сложные нелинейные функции [90, 100].

Усложнения приводили к увеличению числа настраиваемых параметров при обучении, но при этом давали возможность настраиваться на очень сложные закономерности. Исследования в этой области сейчас идут по двум тесно связанным направлениям: изучаются и различные топологии сетей и различные методы настроек [37, 40].

Еще одним популярным направлением в распознавании образов являются логические правила и деревья решений [115]. В сравнении с вышеупомянутыми методами распознавания эти методы наиболее активно используют идею выражения наших знаний о предметной области в виде логических правил. Для поиска логических правил в данных необходимы две вещи: определить меру “информативности” правила и пространство правил. И задача поиска правил после этого превращается в задачу полного либо частичного перебора в пространстве правил с целью нахождения наиболее информативных из них.

В конце 60-х – начале 70-х годов В.Н.Вапником и А.Я.Червоненкисом [5] была создана статистическая теория распознавания, которая стала основным инструментом в обосновании методов распознавания. Под обоснованием метода распознавания будем считать некоторый набор количественных критериев, удовлетворение которых обеспечивает с разумной вероятностью хорошую обобщающую способность алгоритма.

В этой теории предполагается следующая модель обучения. Пусть существует фиксированное множество функций Здесь Objects – множество классифицируемых объектов, f – функция принадлежности объекта к некоторому фиксированному классу, C = {0, 1}. Обучающая выборка состоит из элементов, которые последовательно и независимо выбираются из множества Objects C согласно некоторому неизвестному распределению. При предъявлении обучающей выборки X s = {(xi, yi)}s метод выбирает некоторую функцию f F, которая является результирующим классификатором. Теория Вапника– Червоненкиса (VC) занимается оценкой вероятности того факта, что ошибка на контроле значительно превысит ошибку на обучении:

где X m – контрольная выборка, которая выбирается независимо. Это оценка для любого распределения на Objects C (т. е. оценка в худшем случае).

VC-размерность – это максимальное число d такое, что найдется набор из d классифицируемых объектов, который может быть классифицирован функциями из F всеми 2d способами. Конечная VC-размерность обеспечивает асимптотически малую разницу между ошибками на обучении и контроле. Для параметрических моделей обучения, как правило, VC-размерность соизмерима с числом параметров, необходимых для настройки модели [65].

Однако теория Вапника и Червоненкиса, несмотря на то, что асимптотически хорошо объясняла многие методы распознавания, давала очень большие оценки необходимых длин обучающих выборок, в то время как на практике эффективные результаты наблюдались при сотнях объектов. Например, в случае алгоритма поиска линейной разделяющей гиперплоскости [65, 131].

Существуют также подходы на основе композиции методов распознавания. Например, алгебраический подход Ю.И.Журавлева [19]. Математический формализм, возникающий при анализе подобных методов, весьма сложен. Одним из основных вопросов, интересующих теорию композиций алгоритмов, является нахождение условий, при которых соответствующие модели смогут обеспечить полное удовлетворение ограничений обучающей выборки (условия разрешимости). На этой идее основывается весьма глубокая теория локальных и универсальных ограничений, выдвинутая К.В.Рудаковым [35].

В связи с новыми прикладными задачами распознавания образов, возникающими в физике, биологии, медицине, технике и экономике, в последние годы активно развиваются динамические методы Монте–Карло (в англоязычной литературе также распространен термин Markov Chain Monte Carlo – MCMC), байесовские подходы и методы стохастической оптимизации [6].

Кластеризация и классификация В процессе классификации обнаруживаются признаки, которые характеризуют группы объектов исследуемого набора данных – классы. По этим признакам каждый сигнал можно отнести к тому или иному классу. Результатом кластеризации является разбиение сигналов на группы в условиях, когда классы заранее не определены. Получающееся разбиение естественным образом характеризует структуру множества данных и может быть использовано в дальнейшем для ее определения.

Кластерный анализ находит применение в самых разнообразных научных направлениях: биология, медицина, археология, история, география, экономика, филология и т. д. Большая часть литературы по кластерному анализу появилась в течение последних трех десятилетий, хотя первые работы, в которых упоминались кластерные методы, появились достаточно давно. Термин “кластерный анализ” впервые был предложен Трионом [130]. Заметный толчок в развитии работ по кластерному анализу дали работы Р.Розенблатта [117]. В книге 1936 года биологов Р.Сокэла и П.Снита [124] рассмотрены методы эффективных биологических классификаций. Авторы предполагали, что выявление структуры распределения объектов в группы помогает установить процесс образования этих структур. А различие и сходство организмов разных кластеров (групп) могут служить базой для осмысления происходившего эволюционного процесса и выяснения его механизма.

В 60-е годы XX века были развиты многочисленные алгоритмы по принципу k -средних, которые до сих пор являются одними из наиболее популярных. Название k -средних предложено Дж. Мак-Кином в году [108]. Этот алгоритм имеет много модификаций, авторами которых являются Г. Болл, Д. Холл [59], Дж. Хартиган [87] и др., а также существует несколько версий для нечеткого случая, например, fuzzy c-means algorithm (FCM) [62, 91], который был разработан Дж.Дуном [75] и развит Дж.Бездеком [62, 63], Ф.Хопнером и Ф.Клавоном [91].

В 70-х годах XX века Н.Джардайном [96], Э.Уильямом [134], Г.Лансом и В.Уильямсом [104] и др. были предложены алгоритмы иерархической кластеризации.

Заметный вклад в развитие методов кластерного анализа был внесен в 60-70 гг. XX в. отечественными учеными Э.М.Браверманом, И.Б.Мучником [4], Ю.И.Журавлевым [19], И.И.Елисеевой [13], Н.Г.Загоруйко, В.Н.Елкиной и Г.С.Лбовым [20, 21] и др.

Различные подходы к задаче кластеризации данных представлены на диаграмме рис. 1.2, которая согласуется с общепринятым подходом разделения множества алгоритмов на иерархические и неиерархические.

Кроме этого алгоритмы делятся на:

• Агломеративные и дивизивные. В агломеративных алгоритмах считается, что изначально каждый элемент содержится в отдельном кластере, которые на каждом шаге объединяются между собой, пока не будет выполнено условия остановки. В дивизимных алгоритмах наоборот – изначально предполагается, что все элементы содержатся в едином кластере, который на каждом шаге разделяется.

• Монотетические и политетические. В зависимости от того, используются свойства объекта при кластеризации последовательно или одновременно, соответственно. Большинство алгоритмов политетические. В некоторых задачах монотетические подходы оказываются эффективными [57], однако с ними возникают большие трудности при работе в пространствах с большими размерностями [118].

• Непересекающиеся и нечеткие. Непересекающиеся алгоритмы относят каждый элемент строго к одному определенному кластеру, в то время как нечеткие алгоритмы каждому элементу возвращают вектор степеней принадлежности к тому или иному кластеру.

Любой нечеткий алгоритм может быть преобразован в непересекающийся за счет выбора для каждого объекта наибольшей степени принадлежности.

• Детерминированные и стохастические. Эти методы относятся к неиерархическим алгоритмам кластеризации, оптималное решение для которых ищется за счет минимизации определенного функционала. В зависимости от того, каким способом ищутся оптимальные значения – традиционными методами или методами случайного поиска – происходит такое деление.

Рис. 1.2: Алгоритмы кластеризации данных Также можно производить деление алгоритмов на те, что работают в режиме реального времени, зависят или не зависят от начального разбиения и порядка рассмотрения объектов и т. д.

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

Это неизбежно приводит к увеличению количества переменных, учитываемых при анализе тех или иных объектов и явлений. Вследствие этого субъективная классификация, которая ранее опиралась на достаточно малое количество учитываемых признаков, часто оказывается уже ненадежной. А объективная классификация, со все возрастающим набором характеристик объекта, требует использования сложных алгоритмов кластеризации.

1.2 Формальная постановка задачи С содержательной точки зрения процесс распознавания образов обычно трактуется как классификация входных сигналов x из некоторого множества X, заключающаяся в построении правила сопоставления каждой точке x X некоторого образа (класса) Xk. Для упрощения будем рассматривать только задачи однозначной классификации, хотя это ограничение и не носит принципиального характера и может быть расширено. Выбор правила классификации порождает разбиение множества X на классы. Будем считать, что правило классификации однозначно определяется конечномерным набором и задана функция l(), возвращающая количество классов при классификации по правилу.

Всякий способ классификации связан с потерями, которые обычно характеризуются с помощью штрафных функций стоимости q k (x, ) при отнесении точки x к классу с номером k. В типичных случаях, когда X вещественное векторное пространство, значения штрафных функций q k (x, ) возрастают при удалении x от центра соответствующего образа (класса). Рассмотрим следующее правило классификации: при заданных и функциях q k (x, ), k = 1,..., l(), входной сигнал x из множества X относится к тому классу Xk с наименьшим номером k = k(x), для которого значение соответствующей штрафной функции q k (x, ) минимально Например, если на X задана норма · и в множестве данных l классов, а l набор векторов центров классов: l = (1, 2,..., l), то можно считать = {l, l } и в качестве q k (x, ) можно задать расстояние до центра k-го класса k : q k (x, ) = x k. При этом множество X разбивается на l классов X1 (), X2(),..., Xl () таким образом, что к подмножеству (классу) Xk () относятся все точки x, находящиеся к центру k ближе, чем к любому другому. Интеграл Xk () x k 2 определяет рассеяние точек x в подмножестве Xk ().

Расстояние между объектами Выбор метрики (или меры близости) является узловым моментом исследования, от которого решающим образом зависит окончательный вариант разбиения объектов на классы при заданном алгоритме разбиения. В каждой конкретной задаче этот выбор должен производиться по-своему.

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

где – ковариационная матрица генеральной совокупности, из которой извлекаются наблюдения x, а – некоторая симметричная неотрицательноопределенная матрица “весовых” коэффициентов, которая чаще всего выбирается диагональной [64, 111].

В кластерном анализе нередко используются метрики, являющиеся частными случаями метрики Махаланобиса. Прежде всего, это евклидово расстояние, применение которого оправдано в случае, когда наблюдения извлекаются из генеральных совокупностей, описываемых многомерным нормальным законом с общей ковариационной матрицей.

В случае использования дихотомических (имеющих всего два значения) качественных признаков широко используется расстояние Хемминга, равное числу несовпадений значений соответствующих признаков для рассматриваемых i-того и j-того объектов:

где n – размерность пространства.

Часто также используется метрика Минковского, в общем виде записываемая так:

Выбор конкретного значения степенного показателя производится как правило исследователем.

Частным случаем расстояния Минковского является так называемое манхэттенское расстояние, или “расстояние городских кварталов” (cityblock), соответствующее = 1, Устремив к бесконечности, можно получить метрику “доминирования”, или Sup-метрику:

Адаптивная метрика – это метрика, уточняемая в процессе классификации. Рассмотрим адаптивную метрику Махаланобиса. Квадрат расстояния в этом случае задается как где V (t) – некоторая положительно определенная симметричная матрица, пересчитываемая на каждом шаге работы алгоритма следующим образом. Пусть на шаге t фиксирована метрика V (t), при которой мы проводим разделение выборки с помощью какого-либо алгоритма кластеризации с известным фиксированным количеством классов l, которое не меняется в процессе работы. Далее по полученной классификации вычисляем матрицу внутриклассового разброса на шаге t:

и вводим новую метрику с матрицей как V (t+1) = W (t). Состоятельность алгоритмов с адаптивной метрикой Махаланобиса доказывается в [1].

Функционалы качества разбиения на классы Понятие функционала качества разбиения вводится с целью определить тот количественный критерий, следуя которому можно было бы предпочесть одно разбиение другому. Выбор того или иного функционала качества, как правило, осуществляется весьма произвольно и опирается скорее на эмпирические соображения, чем на какую-либо строгую формализованную систему.

Предположим, что на множестве X задано распределение P(·). Функционал качества правила классификации выберем как взвешенную сумму внутриклассовых расстояний [108]:

При заданном количестве кластеров функционал можно определить и как сумму попарных внутриклассовых расстояний между элементами [80]:

При заранее неизвестном количестве классов при описании функционала качества разбиения часто опираются на понятие меры концентрации где (xi) – число элементов в классе, содержащем точку xi, – параметр, выбирающийся исходя из конкретных целей разбиения, m – количество элементов множества наблюдения.

Кроме этого, используется понятие средней меры внутриклассового рассеяния:

Постановка задачи Задача кластеризации множества данных из l классов состоит в определении набора центров l, минимизирующего суммарную стоимость разбиения. Задача устойчивой кластеризации является обобщением для случая нахождения заранее неизвестного оптимального значения количества классов l и соответствующего набора центров l.

В системах, работающих в режиме реального времени в условиях изменяющейся со временем обстановки, распределение P(·) очень часто бывает неизвестно. Будем предполагать, что в режиме реального времени на вход поступает последовательность x1, x2,... сигналов, порожденная неизвестным распределением P(·). Требуется предложить алгоритм построения последовательности оценок {n} набора, минимизирующего определенный выше функционал среднего риска. Решение задачи дополнительно осложняется тем, что на практике функции q k (·, ·), k = 1, 2,..., l() не всегда заданы аналитически, но их значения доступны измерению (может быть с помехами):

Если в каком-то смысле можно было бы говорить о дифференцируемости функционала F, то искомый набор центров должен был бы удовлетворять уравнению F ( ) = 0, которое можно было бы попытаться решить традиционными средствами. Сложность рассматриваемой задачи заключается в недифференцируемости функционала F.

1.3 Примеры задач распознавания образов В работах [11, 52, 45, 48, 85, 119] можно найти описания различных аспектов постановки и решения задачи о распознавании слов речи, в [46, 47, 50] дано решение задачи распознавания арабского текста, в [9, 84] приведены возможные варианты постановки конкретных задач кластеризации, возникающих при проектировании современных вычислительных устройств и систем.

1.3.1 Распознавание слов речи В качестве примера задачи распознавания образов рассмотрим задачу распознавания слов речи. Несмотря на то, что задачей распознавания речи занимаются уже более сорока лет, она остается актуальной и на сегодняшний день.

Цифровая система обработки звукового сигнала предполагает представление аналогового речевого сигнала в цифровом виде. В результате аналого-цифрового преобразования (АЦП) непрерывный сигнал переводится в ряд дискретных временных отсчетов, каждый из которых представляет собой число. Это число храктеризует сигнал в точке с определенной точностью. Точность представления зависит от ширины диапазона получаемых чисел, а, следовательно, от разрядности АЦП. Процесс извлечения из сигнала численных значений называется квантованием.

Процесс разбиения сигнала на отсчеты - дискретизацией. Число отсчетов в секунду называется частотой дискретизации.

Рис. 1.3: Этапы обработки звуковой волны Процесс обработки звуковой волны схематически показан на рис. 1.2.

Аналоговый акустический сигнал, поступающий с микрофона, подвергается с помощью АЦП дискретизации и квантованию. Происходит так называемая реализация слова, т. е. цифровая запись произнесения слова (звука) в виде последовательности отсчетов звукового сигнала sk. Реализация слова (звука) в процессе цифровой обработки разбивается на последовательность кадров Xi. Кадром X (длины N ) назовем последовательность отсчетов звукового сигнала s1, s2,..., sN. Длина кадра фиксирована во времени. Например, при N = 100 и частоте дискретизации 8000 Гц она соответствует длительности в 12.5 мс. Кадры часто смещают друг относительно друга для того, чтобы не происходило потери информации на границе кадров. Шаг смещения кадра – количество звуковых отсчетов между началами следующих друг за другом кадров. Шаг смещения меньший, чем N (длина кадра) означает, что кадры идут “внахлест”.

Далее в целом ряде задач, таких как распознавание речи или идентификация личности, каждому кадру сопоставляются некоторые данные, характеризующие звук наилучшим образом. Такие данные формируют вектор свойств (или вектор признаков). С математической точки зрения это может быть как вектор из пространства Rn, так и набор функций или одна функция, где n 4000.

В случае, когда необходимо распознать слитную речь, ее нужно разбить на отдельные слова. Как правило, это осуществляется за счет эмпирического порогового значения интенсивности сигнала, за счет которого определяется начало и конец слова. Задачей системы является отождествление каждого слова с заранее определенным классом.

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

Распознающая система является независимой от диктора, если она распознает слово независимо от того, кто его произносит. На практике реализовать такую систему сложно по той причине, что звуковые сигналы сильно зависят от громкости, тембра голоса, состояния и настроения диктора. Для извлечения информации из таких сигналов нередко используют фильтры тоновых частот (мел-скейл фильтры), которые усредняют спектральные составляющие в определенных диапазонах частот, тем самым делая сигнал менее зависимым от диктора.

Предварительная фильтрация Для спектрального выравнивания речевого сигнала его следует пропустить через низкочастотный фильтр. Цель этого преобразования – снизить влияние локальных искажений на характеристические признаки, которые в дальнейшем будут использоваться для распознавания. Часто низкочастотная фильтрация осуществляется на аппаратном уровне, хотя существуют различные математические методы, которые успешно применяются в задачах работы со звуком. Известно, что наиболее информативные частоты человеческого голоса сосредоточены в интервале 100 3400 КГц, поэтому при решении задач распознавания речи уже на начальном этапе в спектрограмме оставляют только гармоники, частоты которых попадают в этот интервал.

Нарезка сигнала перекрывающимися сегментами Для того чтобы получить векторы признаков одинаковой длины, нужно ”нарезать” речевой сигнал на равные части, а затем выполнить преобразования внутри каждого сегмента. Обычно сегменты выбирают таким образом, чтобы они перекрывались либо наполовину, либо на 2/3. Перекрытие используется для предотвращения потери информации о сигнале на границе. Чем меньше перекрытие, тем меньшей размерностью в итоге будет обладать вектор свойств, характерный для рассматриваемого участка, поскольку он составляется из кепстральных коэффициентов каждого сегмента в отдельности. Кепстральными коэффициентами называют набор чисел, полученных после спектрального анализа участка звукового сигнала. Обычно выбирается длина участка (сегмента), соответствующая временному интервалу в 2030 мс. На рис. 1.4 изображена нарезка сигнала сегментами с перекрытием на половину длины.

Рис. 1.4: Нарезка сигнала перекрывающимися сегментами Обработка сигнала в окне Цель этого этапа обработки – снижение граничных эффектов, возникающих в результате сегментации. Для подавления нежелательных граничных эффектов принято умножать сигнал s(n) на оконную функцию w(n):

В качестве функции w(n) часто используется окно Хэмминга, график которой изображен на рис. 1.5. Функция задается следующей формулой:

Извлечение векторов свойств и распознавание Каждый входной звуковой сигнал представляется в виде специального вектора свойств (или вектора признаков), определенным образом характеризующего сигнал. Есть довольно много методов для формирования вектора свойств. Наиболее популярным является подход кепстральных коэффициентов. Существует две основные технологии извлечения из сигнала вектора свойств, состоящего из кепстральных коэффициентов: на основе кепстральных коэффициентов тональной частоты (Mel-Frequency Cepstral Coecients – MFCC) [82] и на основе кепстральных коэффициентов линейного предсказания (Linear Predictive Cepstral Coecients – LPCC) [116]. Более широкое распространение в задачах распознавания речи получили коэффициенты линейного предсказания LPCC. Однако они настроены для более качественной обработки речи и потому требуют больших вычислительных затрат. Коэффициенты MFCC являются эффективными в системах распознавания речи [136] при меньших вычислительных затратах, что является важным фактором при реализации в виде электронного устройства.

Распознавание после выделения из звукового сигнала характеристических признаков происходит за счет отнесения сигнала к одному из предопределенных классов с помощью одного из методов распознавания образов. Это может быть, например, метод на основе скрытых моделей Маркова (СММ) [129], когда моделируемый процесс распознавания описывается с помощью конечного набора состояний, меняющихся на каждом шаге в произвольном, но статистически прогнозируемом направлении. Такие подходы базируются на предположении, что речь может быть разбита на сегменты (состояния), внутри которых речевой сигнал может рассматриваться как стационарный, причем переход между этими состояниями осуществляется мгновенно. Также предполагается, что вероятность символа наблюдения, порождаемого моделью, зависит только от текущего состояния модели и не зависит от предыдущих порожденных символов. По сути, ни одно из этих двух предположений не является справедливым для речевого сигнала. Тем не менее, стандартные СММ являются основой для многих современных систем распознавания речи.

Также может быть использован метод на основе опорных векторов (Support Vector Machine – SVM) [65]. Метод SVM осуществляет поиск такой гиперплоскости в пространстве всех возможных входов, что она разделяет различные классы данных и максимально удалена от каждого из них. Использование метода опорных векторов позволяет получить функцию классификации с минимальной верхней оценкой ожидаемого риска (уровня ошибки классификации), а также использовать линейный классификатор для работы с нелинейно разделяемыми данными, сочетая простоту с эффективностью.

В задаче распознавания при наличии неконтролируемых помех в сигнале оказывается эффективным использование методов, основанных на стохастической аппроксимации градиента функционала качества [11, 85, 119], которые детально описаны во второй главе.

1.3.2 Распознавание печатных текстов Задачей автоматического распознавания текстов является перевод напечатанных на бумаге символов в цифровые данные, которые потом могут быть легко обработаны текстовым редактором. Эта задача является довольно-таки трудной, поскольку каждый печатный символ может быть представлен несколькими способами за счет того, что существует множество различных шрифтом и стилей (bold, italic и др.) Распознавание печатных символов является актуальной проблемой, поскольку имеет множество практических применений: архивация документов, автоматическое чтение чеков, автоматический перевод на другие языки и т. д.

Исследовательской деятельностью в области распознавания печатных и рукописных текстов занимаются во всем мире уже несколько десятилетий подряд. За это время удалось создать довольно эффективные системы распознавания для языков латинской группы, а также для китайского и индийского языков. Прогресс в области арабского языка описан в работах [122, 94].

На сегодняшний день существует несколько устройств, позволяющих осуществлять автоматическое распознавание текстов. Но точность переводов таких устройств оставляет желать лучшего. Это происходит потому, что при попытке создания подобных устройств разработчики сталкиваются с проблемами, которых нет при распознавании языков латинской группы [46, 47]. Например:

• арабские тексты пишутся справа налево;

• некоторые символы могут перекрываться в горизонтальном направлении;

• в арабском языке всего 28 букв, каждая из которых может быть соединена тремя различными способами с другими, а также может быть отделена ото всех (т. о., каждый символ может иметь от двух до четырех различных форм в зависимости от места расположения • некоторые символы имеют дополнительные символы акцентирования, которые обладают очень малыми размерами по сравнению с основным текстом, что значительно затрудняет процесс их распознавания;

• арабские символы имеют различные высоты, что затрудняет определение помех;

• слова могут состоять из одного или нескольких подслов в силу того, что некоторые буквы нельзя соединить с левой стороны.

Система распознавания арабского печатного текста состоит из нескольких этапов. Сначала текст анализируется и из него выделяются отдельные блоки, которые сканируются и сохраняются, например, как Bit-map изображения. В арабском языке написание слова возможно в форме, содержащей гласные, и в форме, в которой гласных нет. Рассмотрим один из методов распознавания текста, содержащего гласные.

Первоначальный этап заключается в удалении помех в бинарном изображении, которые получаются в ходе сканирования. Существует множество фильтров, которые можно использовать для фильтрации избражений: фильтр основного значения, фильтр Гаусса, фильтр медиан и т. д.

Как правило, используется фильтр медиан, поскольку он обладает наибольшей эффективностью. На рис. 1.6-1.7 изображен фрагмент текста до и после применения фильтра медиан. Фильтр рассматривает каждую точку битового изображения и возвращает среднее значение ее восьми соседей (см. рис. 1.8).

Рис. 1.7: Сканированный текст после применения фильтра медиан Использованный метод основан на наблюдении гистограмм строк и колонок. При этом учитываются особенности арабского письма. Сегментация осуществляется в три этапа:

1. выделение строк;

2. выделение отдельных слов;

3. разбиение каждого слова на отдельные буквы.

Горизонтальная сегментация Этот шаг заключается в получении строк текста (см. рис. 1.9). Для этого используются горизонтальные гистограммы. Для выделения отдельных строк необходимо определить пробелы между строками, которые состоят из областей с нулевой или минимальной гистограммой. При этом строкой считается область текста, ширина которой больше определенного порога. Если расстояние между двумя строками меньше некоторого порога, то эти две строки воспринимаются как одна. Горизонтальная сегментация осуществляется следующим образом:

• определяется начало строки (оно соответствует первой строке в бинарной матрице, которая содержит хотя бы один черный пиксел);

• конец строки соответствует строке бинарной матрицы, в которой нет черных пикселов (процесс осуществляется справа налево).

Вертикальная сегментация Операция вертикальной сегментации осуществляется за счет проекции строки на горизонтальную ось (рис. 1.10). Полученные гистограммы будут иметь нулевые колонки, которые используются для разбиения строки на отдельные слова. Вертикальное разбиние производится сверху вниз следующим образом:

• началом слова считается первая колонка бинарной матрицы, содержащая по крайней мере один черный пиксел;

• конец слова определяется первой колонкой, не содержащей черных пикселов.

Разбиение слов на символы Для выделения символов из слов необходимо определить:

1. связывающую строку (она определяется как строка с наибольшей концентрацией черных пикселов);

2. верхнюю строку для каждой колонки слова (это первая строка сверху, содержащая черный пиксел);

3. нижнюю строку для каждой колонки слова (это первая строка снизу, содержащая черный пиксел);

4. вертикальную гистограмму для каждой колонки слова.

Считается, что символ выделен из слова, если определены его начало и конец. Колонка, которая соответствует началу символа, должна удовлетворять тому условию, что ее вертикальная гистограмма больше заданного порогового значения. Завершающей колонкой является та, которая следует непосредственно перед стартовой колонкой следующего символа. Она должна удовлетворять следующим условиям:

1. верхняя строка данной колонки должна быть не меньше связывающей строки;

2. нижняя строка данной колонки должна быть не больше связывающей строки;

3. разница между верхней и нижней строками должна быть не больше порогового значения;

4. вертикальная гистограмма должна быть не больше порогового значения;

5. верхняя строка данной колонки должна быть выше верхней строки первой колонки в слове.

Классификация символов Вогнутость и выгнутость линий, замкнутые области и их количество представляют собой характеристики (морфологические), которые используются для классификации символов. Каждый символ можно отнести к определенному классу, используя, например, формулу:

где H количество замкнутых областей (holes), L количество выпуклостей слева, R количество выпуклостей справа, U количество выпуклостей вверх, B количество выпуклостей вниз.

Рис. 1.11: Пример классификации нескольких символов Рис. 1.12: Существенные точки. 1, 4 - замкнутая область, 2, 3, 5 - выпуклость слева Пример классификации символов с использованием описанной формулы изображен на рис. 1.11.

Для определения замкнутых областей и выгнутостей линий анализируется вся область, которую занимает символ. Используются так называемые существенные точки (essential points). Строка (или столбец) бинарной матрицы, пересекающий символ в двух местах, образует отрезок, центр которого считается существенной точкой.

Далее из каждой такой точки выпускают лучи в восьми направлениях (N, N E, E, SE, S, SW, W и N W ). Пересекая символ в каком-либо одном направлении, можно сделать вывод, что в данном направлении выпуклоРис. 1.13: Соединяя точки 1 и 4 определяем, что они лежат в одной замкнутой области; соединяя точки 2, 3, 5 определяем, что они лежат в одной выпуклости. Поскольку точки 1 и 4 не связаны с 2, 3 и 5, они действительно лежат в замкнутой области сти нет. Например, если лучи пересекают символ во всех направлениях, то рассматриваемая точка принадлежит замкнутой области. Если же лучи пересекают символ в направлении SE, S и SW, то точка принадлежит участку, соответствующему выпуклости вверх.

Таким способом можно подсчитать точное количество замкнутых областей и выпуклостей. Все существенные точки соединяются между собой попарно. Если отрезок, соединяющий две точки, не пересекает символ, то данные точки лежат в одной области. Если одна из точек лежит в замкнутой области, а другая в выпуклости, то это означает, что замкнутая область была определна неправильно. Пример определения замкнутых областей и выпуклостей можно увидеть на рис. 1.12–1.13.

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

1. Форма символа. Она может быть квадратной, вытянутой или сжатой в зависимости от отношения высоты и ширины символа (рис. 1.14–1.16). Если символ вытянут, то FORM=1, если похож на квадрат, то FORM=2, если сжат, то FORM=3.

2. Степень заполненности. Рассматривается прямоугольник, содержащий символ. В нем анализируются все углы (рис. 1.17). Введем переменную CorVar:

где Si равна 1 в случае заполенности i-го угла и 0 в противном случае. Эта характеристика позволяет узнать, как расположен символ внутри прямоугольника.

3. Присутствие пунктуации. Определим переменную ExPoint в случае символа с пунктуацией как 1 и как 0 в противном случае.

4. Место расположения пунктуации. Определим переменную PosPoint, которая принимает следующие значения (см. рис. 1.18):

• PosPoint = 1, когда знак пунктуации расположен над символом;

• PosPoint = 2, когда знак пунктуации расположен в середине • PosPoint = 3, когда знак пунктуации расположен под символом.

5. Количество точек в знаках пунктуации NumbPoint:

• NumbPoint = 1, если символ имеет одну точку;

• NumbPoint = 2, если символ имеет две точки;

• NumbPoint = 3, если символ имеет три точки;

• NumbPoint = 4, если символ имеет специальный знак “Хамза”.

Описанные характеристики в совокупности составляют вектор свойств V, который можно использовать для распознавания конкретного символа внутри одного класса [46, 47, 50]:

1.4 Программные средства аналитического ПО Инструменты аналитического ПО чаще всего рассматриваются как составная часть рынка Business Intelligence, на котором сегодня существует огромное разнообразие продуктов. К аналитическим технологиям проявляется огромный интерес. На этом рынке работает множество фирм, ориентированных на создание инструментов для разработки систем распознавания образов, интеллектуального анализа данных, Data Mining, OLAP и хранилищ данных. При этом постоянно появляются новые фирмы-разработчики и новые инструменты.

Еще в 60–70 гг. XX века на основе алгоритмов FOREL, BIGFOR, KRAB, NTTP, DRET, TRF и др. был создан специализированный пакет программ ОТЭКС [22]. Позднее московскими математиками С.А.Айвазяном, И.С.Енюковым и Б.Г.Миркиным были созданы программные продукты ППСА и Класс-Мастер [29]. В работе [1] описана методо-ориентированная статистическая экспертная система по классификации объектов и признаков МОСЭС-КЛАСС, в которой были поддержаны многочисленные методы распознавания образов, автоматической классификации, кластерного анализа, дискриминантного анализа и др. Эта система активно использовалась в экономических и социально-экономических приложениях, в задачах технической и медицинской диагностики в 80-х гг XX в. в СССР.

Разработкой аналитического программного обеспечения заняты как всемирно известные лидеры, так и новые развивающиеся компании. Разнообразные инструменты могут быть представлены либо как самостоятельное приложение, либо как дополнения к основному продукту. Последний вариант реализуется многими лидерами рынка программного обеспечения. Так, например, уже стало традицией, что разработчики универсальных статистических пакетов, в дополнение к традиционным методам статистического анализа, включают в пакет определенный набор методов Data Mining. Это такие пакеты как SPSS (SPSS, Clementine), Statistica (StatSoft), SAS Institute (SAS Enterprise Miner). Некоторые разработчики OLAP-решений также предлагают набор методов Data Mining.

Например, семейство продуктов Cognos. Есть поставщики, включающие системы интеллектуального анализа данных в функциональность СУБД:

Microsoft (Microsoft SQL Server), Oracle, IBM (IBM Intelligent Miner for Data).

Инструменты аналитического ПО можно оценивать по различным критериям. Оценка программных средств с точки зрения конечного пользователя определяется путем оценки набора его характеристик. Их можно поделить на две группы: бизнес-характеристики и технические характеристики. Это деление является достаточно условным, и некоторые характеристики могут попадать одновременно в обе категории.

• Интуитивный интерфейс. Интерфейс – среда передачи информации между программной средой и пользователем, диалоговая система, которая позволяет передать человеку все необходимые данные, полученные на этапе формализации и вычисления. Интерфейс подразумевает расположение различных элементов, в т.ч. блоков меню, информационных полей, графических блоков, блоков форм, на экранных формах. Для удобства работы пользователя необходимо, чтобы интерфейс был интуитивным. Интуитивный интерфейс позволяет пользователю легко и быстро воспринимать элементы интерфейса, благодаря чему диалог “программная средапользователь” становится проще и доступней. Понятие интуитивного интерфейса включает также понятие знакомой окружающей среды и наличие внятной нетехнической терминологии (например, для сообщения пользователю о совершенной ошибке).

• Удобство экспорта/импорта данных. При работе с инструментом пользователь часто применяет разнообразные наборы данных, работает с различными источниками данных. Это могут быть текстовые файлы, файлы электронных таблиц, файлы баз данных.

Инструмент Data Mining должен иметь удобный способ загрузки (импорта) данных. По окончании работы пользователь также должен иметь удобный способ выгрузки (экспорта) данных в удобную для него среду. Программа должна поддерживать наиболее распространенные форматы данных: txt, dbf, xls, csv и другие. Дополнительное удобство для пользователя создается при возможности загрузки и выгрузки определенной части (по выбору пользователя) импортируемых или экспортируемых полей.

• Наглядность и разнообразие получаемой отчетности. Эта характеристика подразумевает получение отчетности в терминах предметной области, а также в качественно спроектированных выходных формах в том количестве, которое может предоставить пользователю всю необходимую результативную информацию.

• Легкость обучения работы с инструментарием.

• Прозрачные и понятные шаги аналитического процесса.

• Руководство пользователя. Существенно упрощает работу пользователя наличие руководства пользователя с пошаговым описанием шагов генерации моделей Data Mining.

• Удобство и простота использования. Существенно облегчает работу начинающего пользователя возможность использовать Мастер или Визард (Wizard).

• Для пользователей, не владеющих английским языком, важной характеристикой является наличие русифицированной версии инструмента, а также документации на русском языке.

• Наличие демонстрационной версии с решением конкретного примера.

• Возможности визуализации. Наличие графического представления информации существенно облегчает интерпретируемость полученных результатов.

• Наличие значений параметров, заданных по умолчанию. Для начинающих пользователей – это достаточно существенная характеристика, так как при выполнении многих алгоритмов от пользователя требуется задание или выбор большого числа параметров.

Особенно много их в инструментах, реализующих метод нейронных сетей. В нейросимуляторах, чаще всего, заранее заданы значения основных параметров; иной раз неопытным пользователям даже не рекомендуется изменять эти значения. Если же такие значения отсутствуют, пользователю приходится перепробовать множество вариантов, прежде чем удастся получить приемлемый результат.

• Количество реализуемых методов и алгоритмов. Во многих инструментах Data Mining реализовано сразу несколько методов, позволяющих решать одну или несколько задач. Если для решения одной задачи (классификации) предусмотрена возможность использования нескольких методов (деревьев решений и нейронных сетей), пользователь получает возможность сравнивать характеристики моделей, построенных при помощи этих методов.

• Скорость вычислений и скорость представления результатов.

• Наличие квалифицированного ассистента (консультации по выбору методов и алгоритмов), консультационная поддержка.

• Возможности поиска, сортировки, фильтрации. Такая возможность полезна как для входных данных, так и для выходной информации. Применяется сортировка по различным критериям (полям), с возможностью накладывания условий. При условии фильтрации входных данных появляется возможность построения модели Data Mining на одной из выборок набора данных. Фильтрация выходной информации полезна с точки зрения интерпретации результатов.

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

•

Защита, пароль. Очень часто при помощи Data Mining анализируется конфиденциальная информация, поэтому наличие пароля доступа в систему является желательной характеристикой для инструмента.

• Платформы, на которых поддерживается работа инструмента, в частности: PC Standalone (95/98/2000/NT), Unix Server, Unix Standalone, PC Client, NT Server.

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

Стандарты интеллектуальной обработки данных Центральное место в аналитических системах и технологиях хранилищ данных занимают вопросы управления метаданными, среди которых одной из наиболее сложных является проблема обмена данными между различными базами данных, репозиториями и продуктами.

Прежде всего, это связано с тем, что в любой системе интеллектуальной обработки данных одновременно участвуют различные компоненты: базы данных, играющие роль информационных источников, средства сбора данных, их согласования, преобразования и загрузки в целевые базы данных, а также аналитические средства, поддерживающие различные методы анализа, включая методы распознавания образов, кластерный анализ, извлечение знаний (Data Mining). Каждый из этих компонентов имеет свои метаданные, хранящиеся в соответствующем репозитории или словаре данных в специальных форматах. Проблема состоит в том, что все эти разнородные по структуре и синтаксису метаданные семантически взаимосвязаны, т. е. для согласованной и корректной работы системы в целом их необходимо передавать от одних средств другим, совместно использовать, устранять несоответствия, противоречия и т. д.

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

В качестве одного из таких стандартов был создан стандарт CWM (Common Warehouse Metamodel) [113]. Он был разработан консорциумом OMG (Object Management Group) для обмена метаданными между различными программными продуктами и репозиториями при создании систем интеллектуальной обработки данных. Стандарт основан на открытых объектно-ориентированных технологиях, в качестве языка моделирования использует UML (Unied Modeling Language), а XML и XMI (XML Metadata Interchange) – для обмена метаданными.

Разработку методологии создания интеллектуальных систем обработки данных регламентирует стандарт CRISP-DM (CRoss-Industry Standard Process for Data Mining) [121]. Это документированная и свободно доступная модель, описывающая основные фазы, выполнение которых позволяет получать максимальную выгоду от использования методов анализа данных.

Стандарт CRISP-DM описывается в терминах иерархической модели, состоящей из четырех уровней абстракции (от более общего к более конкретному): фазы, общие задачи, специализированные задачи и примеры процессов.

Для обмена построенными моделями и полученными знаниями между различными системами анализа данных существует стандарт PMML (Predicted Model Markup Language), описывающий модели в виде XMLдокументов. Этот стандарт активно используется разработчиками, т. к.

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

Стандарт SQL/MM (Multi Media) [109] обеспечивает интерфейс для алгоритмов интеллектуальной обработки данных. Он может представлять собой как верхний уровень любой объектно-реляционной системы базы данных, так и промежуточный уровень.

Стандарт OLE DB был разработан компанией Microsoft и, подобно SQL/MM, применяется к реляционным базам данных. Этот стандарт расширяет OLE DB корпорации Microsoft и включен в SQL Server Analysis Services.

Стандарт JDMAPI (Java Data Mining API) [92] представляет собой спецификацию API-функций для построения моделей Data Mining, извлечения знаний, их использование, а также создание, хранение, доступ и сохранение данных и метаданных, поддерживающих результаты интеллектуальной обработки данных.

Современные инструменты Наиболее популярные инструменты аналитического ПО сегодня включают в себя механизмы классификации данных, средства кластеризации и сегментации, методы статистического анализа, пакеты для анализа текстов (Text Mining) и извлечения отклонений (Information Retrieval (IR)), а также инструменты визуализации.

Перечислим универсальные современные инструменты интеллектуальной обработки данных:

• SPSS (http://www.spss.com). Один из наиболее популярных инструментов, поддерживается множество методов Data Mining.

• IBM Intelligent Miner for Data (http://www.ibm.com/software/data/ iminer/fordata). Инструмент предлагает последние Data Mining-методы, поддерживает полный Data Mining процесс: от подготовки данных до презентации результатов. Поддержка языков XML и PMML.

• KXEN (Knowledge eXtraction ENgines). Инструмент, работающий на основе теории Вапника с использованием метода опорных векторов [131]. Решает задачи подготовки данных, сегментации, временных рядов и SVM-классификации.

• SAS Enterprise Miner (http://www.sas.com). Интегрированный набор, который обеспечивает дружественный GUI. Поддерживается методология SEMMA.

• Statistica Data Miner (http://www.StatSoft.com). Инструмент обеспечивает всесторонний, интегрированный статистический анализ данных, имеет мощные графические возможности, управление базами данных, а также приложение разработки систем.

• Polyanalyst (http://www.megaputer.com). Набор, обеспечивающий всесторонний Data Mining. Сейчас, помимо методов прежних версий, также включает анализ текстов, лес решений, анализ связей.

Поддерживает OLE DB for Data Mining и DCOM-технологию.

• Oracle Data Mining (ODM) (http://otn.oracle.com/products/bi/ 9idmining.html). Инструмент обеспечивает GUI, PL/SQL-интерфейсы, Java-интерфейс. Используемые методы: байесовская классификация, алгоритмы поиска ассоциативных правил, кластерные методы, SVM и другие.

• DBMiner 2.0 Enterprise (http://www.dbminer.com), мощный инструмент для исследования больших баз данных; использует Microsoft Сервер SQL 7.0 Plato.

• Clementine (http://www.spss.com/clementine). Data Mining с использованием Clementine является бизнес-процессом, разработанным для минимизации времени решения задач. Clementine поддерживает процесс Data Mining: доступ к данным, преобразования, моделирование, оценивание и внедрение.

• Библиотека Xelopes, поддерживающая все вышеописанные стандарты. Базовое ядро сформировано в UML, что делает возможным получение реализации практически на любом объектно-ориентированном языке.

• Свободно распространяемый пакет программ Weka (http://www.cs.

waikato.ac.nz/ml/weka/index.html). Представляет собой набор алгоритмов машинного обучения для решения реальных задач интеллектуального анализа данных. Weka реализован на Java и запускается практически со всех платформ.

Существует множество программных продуктов для решения задач классификации и кластеризации. Многие из них совмещают в себе реализацию нескольких методов. Например, часто вместе с кластерными методами также реализованы и методы визуализации. Перечислим некоторые из них. Коммерческие инструменты:

• StarProbe, (http://www.roselladb.com/starprobe.htm) основан на Web кросс-платформенной системе, включает методы кластеризации, нейронные сети, деревья решений, визуализацию и т. д.;

• PolyAnalyst (http://www.megaputer.com) предлагает кластеризацию, основанную на алгоритме локализации аномалий;

• ClustanGraphics3 (http://www.clustan.com) реализует иерархический кластерный анализ “сверху вниз”, поддерживаются мощные графические возможности;

• Neusciences aXi.Kohonen (http://www.neusciences.com) – ActiveX Control для кластеризации алгоритмом Кохонена, включает Delphi-интерфейс;

• IBM Intelligent Miner for Data (http://www-4.ibm.com/software/data /iminer) поддерживает два кластерных алгоритма.

• CViz Cluster Visualization (http://www.alphaworks.ibm.com/tech/cviz) – продукт для анализа наборов данных с большой размерностью, обеспечивает визуализацию наполнения кластеров объектами;

• Visipoint (http://www.visipoint./). Поддержана кластеризация методом самоорганизующихся карт Кохонена, также реализована визуализация многомерных данных.

Свободно распространяемые инструменты:

• Autoclass C (http://ic.arc.nasa.gov) – “обучение без учителя” при помощи Байесовских сетей, работает в операционных системах Unix и Windows;

• CLUTO (http://www.cs.umn.edu/ karypis/cluto). Реализован набор алгоритмов кластеризации, основанных на разделении данных;

• Databionic ESOM Tools (http://databionic-esom.sourceforge.net). Инструмент представлен набором программ для кластеризации, визуализации и классификации, реализован алгоритм ESOM, работающий по принципу самоорганизующихся карт;

• MCLUST-EMCLUST (http://www.stat.washington.edu/ fraley/mclusthome.html). В инструменте реализовано создание кластеров при помощи модельного подхода (modelbased) и дискриминантного анализа, поддержана иерархическая кластеризация;

• PermutMatrix (http://www.lirmm.fr). Программное обеспечение для кластерного анализа, с хорошими графическими возможностями, здесь реализовано несколько методов иерархического кластерного анализа;

• PROXIMUS (http://www.cs.purdue.edu/homes/koyuturk/proximus).

Инструмент для сжатия размерности, кластеризации и обнаружения образцов в дискретных наборах данных;

• ReCkless (http://cde.iiit.net/RNNs) является набором кластерных алгоритмов, основанных на концепции k -ближайших соседей. Инструмент перед проведением кластеризации выполняет поиск и идентификацию шумов и выбросов для уменьшения их влияния на результаты кластеризации;

• Snob (http://www.csse.monash.edu.au) – организована кластеризация на основе MML (Minimum Message Length);

• SOM in Excel (http://www.geocities.com/adotsaha/NN/SOMinExcel.html) – реализация метода самоорганизующихся карт Кохонена в Microsoft Все большее число поставщиков стремится объединить в своих инструментах как можно большее число современных методов и технологий. В то же время некоторые специалисты отмечают отставание существующего программного обеспечения от теоретических результатов в связи со сложностью программной реализации некоторых новых теоретических разработок [44].

Несмотря на многообразие представленных программных средств, обычно исследователи сталкиваются с целым рядом трудностей при разработке и анализе своих собственных методов распознавания образов, значительную часть из которых мог бы решить программный комплекс, позволяющий анализировать не только свои данные, но и свои алгоритмы в универсальном формате. Для анализа важно уметь представлять результаты работы различных алгоритмов в унифицированным виде и сравнивать эффективность нового алгоритма с общеизвестными подходами. Наличие подобного программного комплекса позволит структурировать уже известную информацию о существующих алгоритмах, а также исследовать новые эффективные методы для решения задачи распознавания образов.

Глава Рандомизированные алгоритмы кластеризации Эта глава посвящена применению рандомизированных алгоритмов в задаче распознавания образов.

В первой части описываются алгоритмы кластеризации при известном количестве кластеров. Подробно рассмотрен алгоритм k -средних, предложенный Дж.Хартиганом и М.Вонгом [88], широко применяемый при стандартных предположениях о свойствах погрешностей в измерениях, и рандомизированный алгоритм стохастической аппроксимации (РАСА), предложенный О.Н.Граничиным и О.А.Измаковой [7], работоспособный при ограниченных неконтролируемых (unknown but bounded) погрешностях. Установлено условие состоятельности оценок, предоставляемых РАСА, в задаче распознавания образов слов в речи.

Во второй части рассматриваются задачи устойчивой кластеризации, описывается и обосновывается новый метод устойчивой кластеризации, использующий рандомизированный подход.

2.1 Алгоритмы кластеризации при известном количестве кластеров В иерархических алгоритмах фактически отказываются от определения числа кластеров, строя полное дерево вложенных кластеров (дендрограмму). Число кластеров определяется из предположений, в принципе, не относящихся к работе алгоритмов, например, по динамике изменения порога расщепления (слияния) кластеров.

Иерархией H на множестве X = {x1,.., xm} будем называть систему подмножеств (классов) {S : S X}, удовлетворяющую условиям:

Иерархической классификацией данного множества объектов X = {x1,.., xm} называется построение иерархии H на X, отражающей наличие однородных по некоторому определенному критерию классов и взаимосвязи между ними.

Алгоритмы иерархической классификации бывают: дивизимные, в которых множество X постепенно разделяется на все более мелкие подмножества, и агломеративные, в которых точки множества X постепенно объединяются во все более крупные подмножества.

В зависимости от того, по какому принципу происходит объединнение (или разбиение в случае дивизимных алгоритмов) элементов, различают Singlelink (на каждом шаге объединяются два кластера с наименьшим расстоянием между двумя любыми представителями) и Complete link (на каждом шаге объединяются два кластера с наименьшим расстоянием между двумя наиболее удаленными представителями) алгоритмы.

Трудности иерархических алгоритмов кластеризации хорошо изучены: выбор мер близости кластеров, проблема инверсий индексации в дендрограммах, негибкость иерархических классификаций, которая иногда весьма нежелательна. Тем не менее, представление кластеризации в виде дендрограммы позволяет получить наиболее полное представление о структуре кластеров [2].

Наиболее популярным неиерархическим алгоритмом является алгоритм k -средних [108], суть которого сводится к минимизации квадратичного отклонения объектов от центров кластеров. Этот метод популярен за счет того, что прост в реализации и его временная сложность линейна относительно мощности исследуемого множества O(m). Основная проблема этого алгоритма заключается в том, что он оказывается чувствителен к выбору начального разбиения и может сойтись к локальному минимуму.

В работе алгоритма k -средних можно выделить четыре основных этапа:

1. выбираются или назначаются k наблюдений, которые будут первичными центрами кластеров;

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

3. после назначения всех наблюдений отдельным кластерам производится замена первичных кластерных центров на кластерные средние;

4. предыдущая итерация повторяется до тех пор, пока изменения координат кластерных центров не станут минимальными.

В некоторых модификациях [57] пользователь может задать числовое значение критерия, трактуемого как минимальное расстояние для отбора новых центров кластеров. Наблюдение не будет рассматриваться как претендент на новый центр кластера, если его расстояние до заменяемого центра кластера превышает заданное число. Такой параметр в ряде алгоримов называется “радиусом”. На основе такого параметра может происходит слияние или объединение кластеров, например, как это организовано в алгоритме ISODATA [59].

Инкрементальные алгоритмы также относятся к неиерархическим алгоритмам кластеризации. Они основаны на предположении, что можно последовательно рассматривать каждый элемент множества и либо относить его к какому-либо уже существующему кластеру, в случае когда расстояние от него до ближайшего кластера меньше некоторого заданного порогового значения, либо создавать новый кластер для этого элемента. Алгоритм ведущего кластера (Sequential Leader Clustering – (SLC)) [87] обладает небольшой как емкостной, так и временной сложностью. Метод стал довольно популярным за счет реализации на искусственных нейронных сетях (ИНС) [69]. Инкрементальные алгоритмы успешно применяются в задачах динамической обработки данных [68].

Также известен инкрементальный алгоритм кратчайшего пути [123].

Основным преимуществом алгоритмов этого типа является тот факт, что не нужно держать в памяти матрицу всех элементов. Поэтому емкостная сложность этих алгоритмов невелика. Как правило, они неитеративны. Поэтому временная сложность также невелика относительно других подходов.

Алгоритм k -средних и его модификации Большинство статистических алгоритмов основано на предположении, что кластеры достаточно точно можно описать некоторым семейством вероятностных распределений. В этом случае задача кластеризации сводится к разделению смеси распределений по конечной выборке.

Как правило используются гипотезы байесовского подхода к разделению смесей вероятностных распределений о вероятностной природе данных и о форме кластеров. Т. е. предполагается, что объекты выборки x1, x2,..., xm появляются случайно и независимо согласно вероятностному распределению, представляющему собой смесь распределений где pk (x) – функция распределения кластера k, wk – неизвестная вероятность появления объектов из кластера k. Также предполагается, что кластеры обладают эллиптической формой и каждый кластер может быть описан n-мерной гауссовской плотностью (где n – размерность пространства) с центром k и диагональной ковариационной матрицей k.

При этих предположениях задача кластеризации совпадает с задачей разделения смеси вероятностных распределений, и для ее решения можно применить EM-алгоритм [71].

Работа этого алгоритма заключается в итерационном повторении двух шагов. На E-шаге по формуле Байеса вычисляются скрытые переменные gik, значение которых равно вероятности того, что объект xi принадлежит кластеру с номером k. На M-шаге с использованием скрытых переменных уточняются параметры каждого кластера (k, k ).

Алгоритм k -средних по своей сути является упрощением EM-алгоритма.

Главное отличие заключается в том, что:

• В EM-алгоритме каждый объект xi распределяется по всем кластерам с вероятностями А в алгоритме k -средних каждый объект жестко приписывается только к одному кластеру.

• В k -средних форма кластеров не настраивается. Это отличие не столь принципиально. Можно предложить упрощенный вариант EM-алгоритма, в котором форма кластеров также не будет настраиваться. Для этого достаточно зафиксировать ковариационные матрицы k. С другой стороны, возможен и обобщенный вариант k средних, в котором будут определяться дисперсии кластеров вдоль координатных осей.

Суть алгоритма заключается в следующем:

• сформировать начальное приближение центров всех кластеров k ;

• отнести каждую точку к тому кластеру, чей центр ближе всего:

Это аналог E-шага;

• пересчитать координаты центров кластеров согласно новому разбиению и вернуться на второй шаг. При этом повторять итерации, пока кластеры не перестанут меняться. Это аналог M-шага.

Алгоритм k -средних имеет несколько вариантов – вышеописанный вариант Болла-Холла [59] и вариант МакКина [108], который отличается тем, что второй и третий шаги выполняются внутри одного цикла по объектам выборки. Когда находится объект, переходящий из одного кластера в другой, центры обоих кластеров пересчитываются. МакКин показал, что этот вариант алгоритма приводит к локальному минимуму функционала качества [108].

Алгоритм k -средних крайне чувствителен к выбору начальных приближений центров. Случайная инициализация центров на первом шаге может приводить к сколь угодно плохим кластеризациям. Кластеризация может оказаться неадекватной и в том случае, если изначально будет неверно угадано число кластеров.

Для нахождения глобального минимума был создан модифицированный алгоритм k -средних – Global k-means [107]. Для того, чтобы вычислить k -разбиение на k-ой итерации используется (k-1)-разбиение, полученное на предыдущей итерации.

Основные операции сводятся к следующим шагам:

• Вычисляется центр первого кластера из предположения, что всего на множестве один кластер, т. е. l = 1:

m – количество элементов в множестве.

• Изменяется количество кластеров l = l + 1 и рассматриваются центры кластеров 1, 2,..., l1 с предыдущей итерации.

• Каждя точка xi исходного множества X рассматривается как кандидат для назначения в качестве центра k-го кластера. Таким образом получается всего 1, 2,..., l1, xi начальных значений, для которых запускается алгоритм k -средних. На основании m k -разбиений выбирается наилучшее, и далее рассматриваются центры 1, 2,..., l.

• происходит повторение второго шага до того момента, пока количество кластеров l не будет равно некоторому наперед заданному значению.

Существуют другие модификации алгоритма, настроенные для задач с большим размерностями фазового пространства [86]. В [58] рассматривается другая инкрементальная версия алгоритма k -средних, основанная на подходах невыпуклой оптимизации.

Далее рассмотрим рекуррентную форму алгоритма k -средних, использующую для оптимизации функционала качества принципы стохастической аппроксимации и искусственного пробного возмущения.

Алгоритмы стохастической аппроксимации В обобщенной форме алгоритмы стохастической аппроксимации могут быть записаны следующим образом:

где gk (k ) – оценка градиента g() = F/ на итерации k, полученной на основе предыдущих измерений функции. При необходимых условиях алгоритмы такого типа сходятся “почти наверное” к оптимальному значению [103].

Существенной частью алгоритмов является аппроксимация градиента gk (k ). Для классического алгоритма СА (конечно-разностный алгоритм или процедура Кифера–Вольфовица) [99] любая компонента вектора k возмущается по отдельности на каждом шаге, и производятся соответствующие измерения функции y(·) для оценки компоненты вектора градиента функции.

Таким образом, i-я компонента gk (k ) для конечно-разностной аппроксимации задается так:

где ei обозначает вектор, у которого на i-м месте стоит единица, а на всех остальных нули, ck – небольшое положительное число, которое, как правило, убывает с ростом k.

В алгоритме РАСА все компоненты вектора k возмущаются одновременно, i-я компонента оценки градиента здесь – определенный пользователем случайный наблюдаемый вектор, удовлетворяющий условиям, описанным в [8, 125].

Заметим, что необходимое количество измерений целевой функции в алгоритме конечно-разностной СА увеличивается с ростом размерности пространства, в то время как в РАСА требуется только два измерения независимо от размерности. Это обеспечивает большой выигрыш в вычислительной сложности относительно классических подходов. При этом Дж.Спалом доказано [126], что при выполнении определенных условий РАСА и конечно-разностный алгоритм СА обеспечивают одинаковую точность за одно и то же количество итераций, хотя РАСА требуется в n (где n – размерность пространства) раз меньше измерений функции.

Более того Б.Т.Поляком и А.Б.Цыбаковым [32] установлена минимаксная асимптотическая оптимальность скорости сходимости в том смысле, что для достаточно широкого класса функций порядок асимптотической скорости сходимости не может быть улучшен никаким другим итеративным алгоритмом, если наблюдения происходят с невырожденными помехами.

Пробное возмущение и алгоритм оценивания Пусть распределение вероятностей неизвестно, но известна обучающая последовательность x1, x2,..., xm, им порожденная. С помощью РАСА можно построить последовательности оценок i набора, минимизирующего функционал среднего риска.

Зафиксируем некоторый начальный набор 0 Rnl и выберем последовательности положительных чисел {i } и {i}, стремящиеся к нулю.

По алгоритму РАСА последовательность оценок {i} оптимального набора центров l классов из пространства Rn строится следующим образом при помощи наблюдаемой последовательности случайных независимых друг от друга векторов i Rn, i = 1, 2,..., (называемых пробным одновременным возмущением и составленных из взаимно независимых бернуллиевских, равных ±1, компонент):