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

111111111111

003481493

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

МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДЛЯ РАЗРАБОТКИ И АНАЛИЗА СИСТЕМ РАСПОЗНАВАНИЯ ОБРАЗОВ, ИСПОЛЬЗУЮЩИХ РАНДОМИЗИРОВАННЫЕ АЛГОРИТМЫ

05.13.11 Математическое и программное обеспеченно вычислительных машин, комплексов и компьютерных сетей

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

ШАЛЫМОВ Дмитрий Сергеевич

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Санкт-Петербург

2009

Работа выполнена на Кафедре системного программирования Математико-механического факультета Санкт-Петербургского государственного университета.

Научный руководитель:

Официальные оппоненты:

Ведущая организация:

доктор физико-математических наук, профессор ГРАНИЧИН Олег Николаевич

доктор технических наук, профессор ТИМОФЕЕВ Адиль Васильевич (Санкт-Петербургский институт информатики и автоматизации РАН)

кандидат физико-математических наук, доцент КОСОВСКАЯ Татьяна Матвеевна (Санкт-Петербургский государственный университет)

Институт проблем управления им. В.А.Трапезникова РАН (Москва)

Защита состоится года в часов на заседании сове-

та Д 212.232.51 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу 108504, Санкт-Петербург, Петродворец, Университетский пр.,28, Математи ко-механическиП факультет.

С диссертацией можно ознакомиться в Научной библиотеке им.М.Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб. 7/9.

Автореферат разослан "_"_2009 г.

Ученый секретарь

диссертационного совета Даугавет И. К.

Общая характеристика работы

Актуальность темы. На протяжении последних десятилетий в связи со стремительным развитием цифровых технологий наблюдается значительный рост объемов хранимых и перерабатываемых данных. Однако увеличение количества информации не означает непосредственного увеличения объемов знаний. В такой ситуации все более востребованными становятся новые математические методы, которые позволяли бы распознавать образы, структурировать информацию и находить объективные закономерности в больших объемах данных. Среди них важную роль при распознавании образов играют методы выявления классов (кластеров), способные работать в режиме реального времени. О популярности этих методов сегодня свидетельствует тот факт, что результат поиска по запросу термина "Classification problcm" в поисковой системе Google (на сентябрь 2009 года) составил более сорока трех миллионов страниц.

Современные алгоритмы теории распознавания образов, классификации и кластерного анализа базируются на работах С.А.Айвазяна, А.Я.Червоненкиса, В.Н.Вап-ника, Ф.Розепблата, Р.А.Фишера, В.Н.Фомина, Н.Форджи, К.Фукунагп, Дж.Хар-тигана. Дж.Хопфилда, Я.З.Цыпкина и др. Многие современные системы распознавания образов основаны на принципах нейронных сетей (С.Хайкпп, Ф.Уоссерман, А.В.Тимофеев и др.)

Работоспособность различных алгоритмов разбиения множества данных па классы существенно зависит от количества классов (кластеров) и выбора первоначального разбиения. При априори неизвестном количестве кластеров В.Кржаповскнм и II.Лаем, Дж.Дуном, Л.Хьюбертом и Дж.Шульцом, Р.Калинским и Дж.Хараба-зом, Е.Левине и Е.Домани, А.Бен-Гуром и И.Гшюном, А.Елизнвом, В.Волковичем и др., Р.Тнбшпраии и Г.Вальгером и др. активно разрабатываются методы устойчивой кластеризации, достаточно точно оценивающие количество кластеров в разнообразных прикладных задачах.

Общим недостатком традиционно используемых алгоритмов кластеризации является значительный рост вычислительной сложности при увеличении мощности исследуемого множества. В условиях многомерных задач и нарастающих объемов данных в современных работах М.Вадьясагара, Дж.Галафиорп и М.Кампн, О.Н.Граничина, Ю.М.Ермольева, В.Я.Катковника, А.И.Кибзуна и Ю.С.Кана, Г.Куш-пера и Г.Пиа, Б.Т.Поляка, П.С.Щербакова и А.Б.Цыбакова, Дж.Спала и др. эф-

фективно используются новые рандомизированные алгоритмы, развивающие идеи методой случайного поиска и моделирования но методу Монте-Карло, детально исследованные и русскоязычной литературе С.М.Ермаковым, А.А.Жиглявским и В.Б.Меласом, А.Жнлннскасом, Л.А.Растрпгнным и многими другими. Сложность целого ряда новых рандомизированных алгоритмов, в англоязычной литературе получивших название SPSA (Simultaneous Perturbation Stochastic Approximation), не существенно возрастает при росте размерности данных и, кроме того, они остаются работоспособными в условиях значительных неконтролируемых воздействий, которые трудно исключить в системах реального времени.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Материалы диссертации докладывались на внутренних семинарах кафедры системного программирования математико-механического факультета СПбГУ, на российских и международных конференциях по оптимизации, информатике и теории управления: The 3rd Int. IEEE Scientific 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 (EUROPT-08)" (Neringa, Lithuania, May 20-24, 2008), Yalta Conf. on Discrete and Global Optimization (Yalta, Ukraine, August 1-3, 2008), The ERANIS Int. event in the fields of KBBE, ICT, NMP and Energy (Warsaw, Poland, October 10, 2008), III Межд. научно-практическая копф. "Современные информационные технологии и ИТ-образование" (Москва, Россия, 6-9 декабря, 2008), The 8th Int. Conf. on System Identification and Control Problems "SICPROW (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 августа - 5 сентября, 2009).

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

стие в смене "Инновации и Техническое творчество" в рамках молодежного форума Сслигср-2009. Результаты диссертационной работы были представлены в проекте "Разработка программного комплекса кластерного анализа данных большого объема", который победил в конкурсе "У.М.Н.И.К." в 2009 году. Публикации. Основные результаты диссертации опубликованы в работах [1-18]. Из них три публикации [12,17,18] в журналах из перечня ВАК. Работы [2,3,8,9,12,14| написаны в соавторстве. В работах [2,3,8,9,12) О.Н.Граничину принадлежат общие постановки задач, а Д.С.Шалымову - реализация описываемых методов, создание демонстрационных примеров и программных средств. В [14| Д.С.Шалымов является автором 1-УШ секций, К.Скрыгану принадлежит участие в реализации вычислительного ядра и соавторство в IV секции, посвященной организации его внутренней структуры, Д.Любимову принадлежит участие в создании демонстрационных примеров, проиллюстрированных на рис. 3-5.

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

Содержание работы

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

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

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

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

В п. 1.2 описывается формальная постановка задачи. С содержательной точки зрения процесс распознавания образов трактуется как классификация входных сигналов х из некоторого множества X, заключающаяся в построении правила сопоставления каждой точке х е X некоторого образа (класса) Хк. (В диссертации для упрощения рассматриваются только задачи однозначной классификации, хотя это ограничение и не носит принципиального характера и может быть расширено.) Выбор правила классификации порождает разбиение множества X на классы. Будем считать, что правило классификации однозначно определяется конечномерным набором Tf и задана функция l{rj) возвращающая количество классов при классификации по правилу г/. Всякий способ классификации т] связан с потерями, которые обычно характеризуются с помощью штрафных функций стоимости qk(x,rj) при отнесении точки х к классу с номером к. В типичных случаях, когда X — вещественное векторное пространство, значения штрафных функций qk(x, rj) возрастают при удалении х от центра соответствующего образа (класса).

В диссертации рассматривается следующее правило классификации: при заданных rj и функциях qk{x, rj), к = 1,..., l(rj), входной сигнал х из множества X относится к тому классу Xс наименьшим номером к = к(х), для которого значение соответствующей штрафной функции qk(x,ij) минимально

к(х) = min{arg min д!(ж,г;)}.

ИЕ1:/(ч)

Например, если на X задана норма [| ■ || и в множестве данных I классов, a if — набор векторов центров классов: т/ = (в1, в2,..., в1), то можно считать т) = {/, //} и в качестве qk(x, rj) можно задать расстояние до центра к-го класса вк\ qk(x, rj) = ||ж - б^'Ц2. При этом множество X разбивается на I классов Х\(т]),Х2('!}), • ■ ■ ,Xi(rj) таким образом, что к классу (подмножеству) Xk(rç) относятся все точки х, находящиеся к центру вк ближе, чем к любому другому. Интеграл JXk^ \\х ~ вк\\2 определяет рассеяние точек х в подмножестве X^{rj)-

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

Ич) ,

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

Если в каком-то смысле можно было бы говорить о дифференцируемое™ функционала F, то искомый набор центров должен был бы удовлетворять уравнению VF(77J,) = 0, которое можно было бы попытаться решить традиционными средствами. Сложность рассматриваемой задачи заключается в недифференцируемости функционала F. При известном распределении Р(-) сформулированные задачи все-таки могут быть точно или приближенно решены. Нетрудно убедиться, что в описанном выше примере множества X»..(?;) имеют вид многогранников, а минимизирующий функционал среднего риска набор центров Г]1; = в1,..., 6^) совпадает с центрами тяжести этих множеств, т. с.

[х , , хР (<1х) в = Г Р /, !> к = 1,2,...,Г.

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

В системах, работающих в режиме реального времени в условиях изменяющейся со временем обстановки, распределение Р(-) очень часто бывает неизвестно. Будем предполагать, что в режиме реального времени на вход поступает последовательность х2, ■ ■ ■ сигналов, порожденная неизвестным распределением Р(-). Требуется предложить алгоритм построения последовательности оценок {г}п} набора 77*, минимизирующего определенный выше функционал среднего риска. Решение задачи дополнительно осложняется тем, что на практике функции •), к= 1,2,..., 1(т]) не всегда заданы аналитически, но доступны измерению их значения (может быть

с помехами):

ук{х, г]) = qk(x, J]) + vk, к — 1,2,..., 1(т)).

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

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

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

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

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

МКК позволяет значительно сократить размерность фазового пространства, задавая отображение Ф : X —> R". Будем считать, что количество классов (различных слов) априори известно и равно I. Обозначим г] = {l,(9l,в2,...,в,)} и выберем для разных классов однотипные штрафные функции qk[x,r]) = ||Ф(а;) - 0fc||2.

Зафиксируем некоторый начальный набор rj0 6 Rnxi и выберем последовательности положительных чисел {о,} и {Д}, стремящиеся к нулю. По алгоритму РАСА последовательность оценок {/),} оптималыюго набора центров I классов r]t из пространства К" строится следующим образом при помощи наблюдаемой последо-

ватсльиости случайных независимых друг от друга векторов Ai 6 К", i = 1,2,..., (называемых пробным одновременным возмущением и составленных из взаимно независимых берпуллиевских, равных ±1, компонент):

(nt = '/),;_! ± ДА JT{Xi, f/i-i),

r'h = Ге (fh-г ~ a, Jr(x„ А^М-О) ,

в котором JT{xi,f\i) — /-мерный вектор, составленный из нулей и одной единицы, соответствующей координате с номером к в том случае, когда Ф(Х{) располагается ближе всего к множеству •Xfc(i),;); Y(xi,r^) = Q(xi,rjf) + V* — i-мерные векторы, составленные из измеренных с помехами в соответствующих точках значений штрафных функций; V* — соответствующие вектора из ошибок наблюдений; Ve -оператор проектирования на некоторое выпуклое замкнутое ограниченное подмножество 0 С К"х', которое содержит JJ*. Условия состоятельности последовательности оценок {fin} сформулированы в Теореме 1. Теорема 1 Пусть выполнены условия: < С„, Cv > 0;

Vi > 1 случайные вектора V^, V^ ■ ■ ■, V^ и xi,x2,..., £¡-1 не зависят от Xi, Ai, случайный вектор Xi не зависит от Д;,-

tti = оо и а; —> 0, f)i —> 0, Qi/3~2 —> 0 при i —У оо; расстояния в Rm между образами разных классов более rmax + 2Cv, т. е.

йЩФ(ХкМ), $№(7?,))) > rmax + 2Cv Vi Ф к,

где

'"max = max max ||Ф(ж) - ||2. k€l:t xeXtM

Если для последовательности оценок {/¡¡}, доставляемых РАСА при произвольном выборе г}о, выполнено

1 max

i—*oc

тогда последовательность оценок {fji} сходится в среднеквадратичном смысле: lim^ooЕ{||?7, — г/*||2} = 0. при г —У оо, к одному из наборов г]*, состоящему из векторов в1,91,... ,6'+.

Если, более того, aj/5f + а?/3~2 < оо, то щ -л при i -» оо с вероятностью

единица.

Далее в п. 2.3 описываются несколько способов определения априори неизвестного количества кластеров в множестве данных X, основные идеи которых сводятся к заданию максимально возможной верхней границы /гаах и вычислению некоторых индексных функций Ind(l), характеризующих оптимальные разбиения множества X на I классов. Многие из таких функций строятся через степени рассеяния внутри класса, определяющие так называемые "искажения". В работе К.Сыогер и Г.Джсймса обоснована целесообразность использования индексных функций вида Ind(l) = I(Dt), где

Di = mini (I, r][))P(dx),

161:1 JXiV, Til)

для анализа кривой "искажений" Dj : [l,/m<u:] —> К, которая монотонно убывает с ростом I. В частности предлагается рассчитывать I{D) = При этом трудо-

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

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

Будем считать априори известными два положительных числа В к С:

В > \[(Ц - I(L - 1)|, С > maXj=2,...,i.-i,/,+i.....,„JI(lj) - I(lj - 1)|,

где U - оптимальное количество кластеров.

Зафиксируем три натуральных числа К, L,N и выберем из набора 1 : lmax независимо с равномерным распределением К групп по L точек ij, j = 1,..., К. Для каждого набора i 6 1 : lmax обозначим spj(-) равномерную аппроксимацию функции /(•) многочленами Чебышева степени небольшой N, построенную по соответствующим г точкам при условии выбора коэффициентов аппроксимации, непревосходящими С/К2. Обозначим 7 = тах_,е1:я inaxig{. |sp; (г) - /(г)| - максимальную невязку. Определим на всем интервале [1,/тах] характеристическую функцию

y(z) = max spi (z) — min s№.(2). v ' iei-.K ^ ' jsi-.к '

Теорема 2 Если при выбора достаточно малых параметров уровня и достоверности c.ff < 1 выполняется условие L > - 1 и множество

Z = {i: v(c)>2(7 + 2(C+ß)i)}

не пустое, тогда с вероятностью р = (1 - ß)2 множество Z содержит точку /„.

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

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

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

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

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

Выоор (генерацияI входных данных

.X

Входные данные

Алгоритм

кластеризации

ЯДРО

'I" тмине

итторнтмл по мегл описанию

Оракул

ш

А

II

А

Л

—» II

1

А

Т

О

р

Рис. 1: Схема работы программного комплекса для разработки и анализа алгоритмов классификации и кластеризации.

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

Работы автора по теме диссертации

Статьи в журналах, рекомендованных ВАК:

[1| Граничим О. Н., Шалимов Д. С. Решение задачи автоматического распознавания отдельных слов речи при помощи рандомизированного алгоритма стохастической аппроксимации /'/ Нейрокомпьютеры: разработка, применение. -М., Радиотехника, 2009. - N 3. - С. 58-64.

(2| Шалимов Д. С. Распознавание слитной речи с использованием рандомизированного алгоритма стохастической аппроксимации // Вестник СПбГУ. Сер. 10: Прикладная математика, информатика, процессы управления. - С.: Изд-во СПбГУ, 2009. - N 3. - С. 171-181.

[3| Шалимов Д. С. Рандомизированный метод определения количества кластеров на множестве данных // Научно-технический вестник СПбГУ ИТМО. -Санкт-Петербург, 2009. - N 5. - С. 111-116.

Друте публикации:

|4) Шалимов Д. С. Рандомизированный алгоритм стохастической аппроксимации в задаче распознавания отдельных слов речи //. В сб. ''Стохастическая оптимизация в информатике" под ред. О. Н. Грапичина, Вып. 2. - Изд-но С.-Петерб. ун-та, 2006. - С. 207-218.

[5| Granichin О. N., Shalymov D. S. New breed stochastic hybrid computers // In: Proc. of the 3-rd Int. IEEE Scientific Conf. ori Physics and Control (PhysCon 2007). - Potsdam, Germany, 2007. - C. 178.

|6] Граничин О. H., Шалимов Д. С. Новые компьютеры. Вычислительные устройства будущего // Компьютерные инструменты в образовании. - М., '2007. -N 6. - С. 23-31.

|7] Шалимов Д. С. Автоматическое распознавание печатных текстов арабского языка // В сб. "Стохастическая оптимизация и информатике" иод ред. О. Н. Грапичина. Выи. 3. - Изд-во С.-Петерб. ун-та, 2007. - С. 124-137.

[8| Шалимов Д. С. Методы стохастической оптимизации в задаче распознавании печатных текстов арабского языка // В сб. трудов пятой межд. научно-практической конф. "Исследование, разработка и применение высоких технологий в промышленности". - Санкт-Петербург, 2008. - С. 140-142.

|9] Шалимов Д. С. Дикторонезависимое распознавание речи при помощи рандомизированного алгоритма стохастической аппроксимации // В сб. трудов пятой межд. научно-прак тической конф. "Исследование, разработка и применение высоких технологий в промышленности". - Санкт-Пе тербург, 2008. - С. 131-138.

(10) Shalymov D. S. Noise Robust Isolated Words Recognition Problem Solving Based On Simultaneous Perturbation Stochastic Approximation Algorithm //' The 20th Int. Conf. "Continuous Optimization and Knowledge-Based Technologies". - Neringa, Lithuania, 2008. - C. 112-118.

[11] Granichin O. N., Shalymov D. S. Speaker-Independent Isolated Words Recognition Problem Solving Based On Simultaneous Perturbation Stochastic Approximation Algorithm // Yalta Conf. on Discrete and Global Optimization. - Yalta, Ukraine, 2008. - C. 13.

|12| Граничил О. H., Шалимов Д. С. Исследование и рандомизация алгоритмов устойчивой кластеризации на основе индексов // Сб. трудов III Межд. научно-

практической коиф. "Современные информационные технологии и НТ-образо-нание". - М., '2008. - Режим доступа: http://2008.it-«lu.ru/pages/Conference-works, свобо.чный.

113] Шалимов Д. С. Алгоритмы устойчивой кластеризации на основе индексных функций и функций устойчивости // В сб. "Стохастическая оптимизация н информатике" иод ред. О. Н. Граничнна. Вып. 4. - Изд-во С-Г1егерб. ун-та,

2008, - С. 236-248.

|14] Шалимов Д. С. Рандомизированный алгоритм стохаст ической аппроксимации в задаче распознавания печатных текстов арабского языка / /' VIII Межд. конф. "Идентификации систем и задачи управления'" (System Identification and Control Problems (SICPRO '09}). - M., CD Proceedings, ISBN 978-5-91450-024-2, 2009

|15) Шалимов Д. С. Определение количества кластеров на множестве данных с использованием рандомизированных алгоритмов /7 В сб. трудов XI конф. молодых ученых "Навигация и управление движением". - Санкт-Петербург,

2009. - Режим доступа: http://xvA\'\v.clpkl ropribor.spb.ru/ciif/kmii 11 /rrels.ht.inl, свободный.

(16[ Shalymov D., S'кгцуап К., Lyubimov О Clustering Algorithms Mela Applier

(САМА) Toolbox /7 SYRCoSE (Spring Young Researchers Colloquium on Software Engineering). - Moscow, 2009. - С. C1-C4.

(17] Шалимов Д. С. Рандомизированные алгоритмы в задаче кластеризации дан-пых // В сб. трудов Первой традиционной всероссийской молодежной летней школе "Управление, информация и оптимизация". - I [ереславль-Залесский, 2009. - С. 25-31.

|18j Шалимов Д. С. On-line кластеризация данных с пешш.зоканием рандомизированных алгоритмов // Сб. трудов VI школы-семинара молодых ученых "Управление большими системами". - Ижевск, 2009. - С. 389-399.

Подписано в печать 14.10.2009. Формат бумаги 60 х 84 1/16. Бумага офсетная. Печать цифровая. Усл. печ. л. 1,0. Тираж 100 экз. Заказ 4521. Отпечатано в отделе оперативной полиграфии химического факультета СПбГУ. 198504, Санкт-Петербург, Петродворец. Университетский пр. 26.

Введение

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 Апробация алгоритмов устойчивой кластеризации.

Актуальность темы. На протяжении последних десятилетий в связи со стремительным развитием цифровых технологий наблюдается значительный рост объемов хранимых и перерабатываемых данных. Однако увеличение количества информации не означает непосредственного увеличения объемов знаний. В такой ситуации все более востребованными становятся новые математические методы, которые позволяли бы распознавать образы, структурировать информацию и находить объективные закономерности в больших объемах данных. Среди них важную роль при распознавании образов играют методы выявления классов (кластеров), способные работать в режиме реального времени. О популярности этих методов сегодня свидетельствует тот факт, что результат поиска по запросу термина "classification problem" в поисковой системе Google (на сентябрь 2009 года) составил более сорока трех миллионов страниц.

Современные алгоритмы теории распознавания образов, классификации и кластерного анализа базируются на работах С.А.Айвазяна [1],

A.Я.Червопснкиса. В.Н.Вапника [5, 131], Ф.Розенблатта [117], Р.А.Фишера [38], В.Н.Фомина [39], И.Форджи [78], К.Фукунаги [81], Дж.Хартигапа [87], Дж.Хопфилда [90], Я.З.Цыпкипа [43], В.А.Якубовича [40] и др. Многие современные системы распознавания образов основаны на принципах нейронных сетей (см. С.Хайкин [41], Ф.Уоссермен [37], А.В.Тимофеев [36] и др.)

Работоспособность различных алгоритмов разбиения множества данных на классы существенно зависит от количества классов (кластеров) и выбора первоначального разбиения. При априори неизвестном количестве кластеров В.Кржаповским и И.Лаем [101], Дж.Дуном [75], Л.Хыо-бертом и Дж.Шульцом [93], Р.Калинским и Дж.Харабазом [66], Е.Левине и Е.Домани [106], А.Бен-Гуром и И.Гийоном [61], А.Елизивом [60],

B.Волковичсм и др. [133], Р.Тибширани и Г.Вальтером [128] и др. активно разрабатываются методы устойчивой кластеризации, достаточно точно оценивающие количество кластеров в разнообразных прикладных задачах.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Материалы диссертации докладывались па внутренних семинарах кафедры системного программирования математико-мехапического факультета СПбГУ, на российских и международных конференциях по оптимизации, информатике и теории управления: The 3rd

Int. IEEE Scientific 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 (EUROPT-08)" (Neringa, Lithuania, May 20-24, 2008), Yalta Conf. on Discrete and Global Optimization (Yalta, Ukraine, August 1-3, 2008), The ERANIS Int. event in the fields of KBBE, ICT, NMP and Energy (Warsaw, Poland, October 10, 2008), III Межд. научно-практическая копф. "Современные информационные технологии и ИТ-образование" (Москва, Россия, 6-9 декабря, 2008), The 8th Int. Conf. on System Identification 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 августа - 5 сентября, 2009).

По материалам диссертации было получено свидетельство об официальной регистрации программы для ЭВМ N 2007611711 "Программная система для обучения, перевода, распознавания арабского текста" от 23 апреля 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. На основе рандомизированного алгоритма стохастической аппроксимации (РАСА) и метода кепстральных коэффициентов топовой частоты разработано программное средство для распознавания образов слов в речи. Проведена апробация РАСА па данных больших размерностей, исследованы свойства помехоустойчивости РАСА в задаче распознавания и установлены условия состоятельности доставляемых РАСА оценок.

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

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

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

1. Айвазян C.A.j Бухгитабер D.M., Енюков И.С., Мешалкии Л.Д. Прикладная статистика: Классификация и снижение размерности. - М.: Финансы и статистика. 1989, 607 с.

2. Барсегяп А. А., Куприянов М. С., Степапепко В. В., Холод И. И. Методы и модели анализа данных: OLAP и Data Mining. Санкт-Петербург: БХВ-Петербург, 2004, 336 с.

3. Боумен У. Графическое представление информации. М.: Мир, 1971. 227 с.

4. Браверлшн Э.М., Мучник И.Б. Структурные методы в обработке эмпирических данных. М.: Наука, 1983, 464 с.

5. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов: статистические проблемы обучения. М.: Наука, 1974. 416 с.

6. Винклер Г. Анализ изображений, случайные поля и методы Мопте-Карло па цепях Маркова. Новосибирск : Гео, 2008, 440 с.

7. Граничил, О. Н., Измакова О. А. Рандомизированный алгоритм стохастической аппроксимации в задаче самообучения // Автоматика и телемеханика, 2005, N 8, С. 52-63.

8. Граничить О. Н., Поляк Б. Т. Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах. М.: Наука, 2003. 291 с.

9. Граничин О. И., Шалымов Д. С. Новые компьютеры. Вычислительные устройства будущего // Компьютерные инструменты в образовании, 2007, N 6, С. 23-31.

10. Граничин О. Н., Шалимов Д. С. Решение задачи автоматического распознавания отдельных слов речи при помощи рандомизированного алгоритма стохастической аппроксимации // Нейрокомпьютеры: разработка, применение. М.: Радиотехника, 2009, N 3, С. 58-64.

11. Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976, 511 с.

12. Елисеева И.И., Рукавишников В. О. Группировка, корреляция, распознавание образов: Статистические методы классификации и измерения связей. М.: Статистика, 1977, 143 с.

13. Ермаков С.М. Метод Монте-Карло и смежные вопросы. -М.:Наука, 1975, 471 с.

14. Ермаков С.М., Жиглмвский A.A. Математическая теория оптимального эксперимента. М.:Наука, 1987, 320 с.

15. Ермаков С.М., Мелас В.В. Математический эксперимент с моделями сложных стохастических систем. Санкт-Петербург: изд. СПб-ГУ, 1993.

16. Ермольев Ю.М. О методе обобщенных стохастических градиентов и стохастических квазифейеровских последовательностях // Кибернетика, 1969, N 2, с. 73-83.

17. Жилиискас А. Глобальная оптимизация. Вильнюс: Мокслас, 1986, 165 с.

18. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики. М.: Наука, 1978, N 33, С. 5-68.

19. Загоруйко Н.Г. Прикладные методы анализа данных и знаний. -Новосибирск: ИМ СО РАН, 1999, 270 с.

20. Загоруйко Н.Г., Елкииа В.Н., Лбов P.C. Алгоритмы обнаружения эмпирических закономерностей. Новосибирск: Наука, 1985, 110 с.

21. Загоруйко Н.Г., Елкина В.Н., Емельянов С.В., Лбов Г.С. Пакет прикладных программ ОТЭКС (для анализа данных). М.: Финансы и статистика. 1986, 160 с.

22. Закс Л. Статистическое оценивание. М.: Статистика, 1976, 598 с.

23. Кат,ковиик В.Я. Линейные оценки и стохастические задачи оптимизации. М.: Наука, 1976, 487 с.

24. Катковник В.Я. Непараметрическая идентификация и сглаживание данных. М.: Наука, 1985, 336 с.

25. Ковальченко И. Д. Количественные методы в исторических исследованиях. М.: Высшая школа. 1984. 384 с.

26. Колмогоров А.Н. Об аналитических методах в теории вероятностей // Успехи математических наук, 1932, N 5, с. 5-41.

27. Маидель И.Д. Кластерный анализ. М.: Финансы и статистика, 1988, 176 с.

28. Миркии Б. Г. Группировки в социально-экономических исследованиях. М.: Финансы и статистика, 1985. 224 с.

29. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983, 384 с.

30. Поляк Б. Т., Щербаков П.С. Робастпая устойчивость и управление. М.: Наука, 2002, 303 с.

31. Поляк Б. Т., Цыбаков А.Б. Оптимальные порядки точности поисковых алгоритмов стохастической аппроксимации // Проблемы передачи информации. 1990, N 2, с. 45-53.

32. Растригии Л.А. Статистические методы поиска. М.: Наука, 1968, 376 с.

33. Растригии Л.А. Адаптация сложных систем. Рига: Зипатпе, 1981, 386 с.

34. Рудаков К.В. Об алгебраической теории универсальных и локальных ограничений для задач классификации. Распознавание, классификация, прогноз // Математические методы и их применение. М.: Наука, 1989, N 1, С. 176-200.

35. Тимофеев A.B. Адаптивное робототехнические комплексы. JL: Машиностроение, 1988, 332 с.

36. Уоссермеп Ф. Нейрокомпьютерная техника: Теория и практика. -М.: Мир, 1992, 240 с.

37. Фишер P.A. Статистические методы для исследователей. М.: Гос-статиздат, 1954, 267 с.

38. Фомин В.Н. Математическая теория обучаемых опознающих систем. JL: ЛГУ, 1976, 236 с.

39. Фомин В.Н., Фрадков А.Л., Якубович В.А. Адаптивное управление динамическими объектами. М.: Наука, 1981, 448 с.

40. Хайкип С. Нейронные сети: полный курс. М.: Вильяме, 2006, 1104 с.

41. Хипчин А.Я. Теория корреляции стационарных стохастических процессов // Успехи математических наук. 1938, N 5, с. 42-51.

42. Цыпкин Я.З. Основы теории обучающихся систем. М.: Наука, 1970, 252 с.

43. Чубукова И.А. Основы информационных технологий: Data Mining. М.:Бииом, 2008, 384 с.

44. Шалимов Д. С. Рандомизированный алгоритм стохастической аппроксимации в задаче распознавания отдельных слов речи // В сб. "Стохастическая оптимизация в информатике" под ред. О. Н. Гра-ничина, Вып. 2. Изд-во С.-Пстерб. ун-та, 2006, С. 207-218.

45. Шалимов Д. С. Автоматическое распознавание печатных текстов арабского языка //В сб. "Стохастическая оптимизация в информатике" под ред. О. Н. Граничипа. Вып. 3. Изд-во С.-Петерб. ун-та, 2007, С. 124-137.

46. Шалимов Д. С. Методы стохастической оптимизации в задаче распознавания печатных текстов арабского языка //В сб. трудов пятой межд. научно-практической копф. "Исследование, разработка и применение высоких технологий в промышленности", 2008, С. 140142.

47. Шалимов Д. С. Алгоритмы устойчивой кластеризации на основе индексных функций и функций устойчивости // В сб. "Стохастическая оптимизация в информатике" под ред. О. Н. Граничипа. Вып. 4. Изд-во С.-Петерб. ун-та, 2008, С. 236-248.

48. Шалимов Д. С. Распознавание слитной речи с использованием рандомизированного алгоритма стохастической аппроксимации // Вестник СПбГУ. Сер. 10: Прикладная математика, информатика, процессы управления. С.: Изд-во СПбГУ, 2009, N 3, С. 171-181.

49. Шалимов Д. С. Рандомизированные алгоритмы в задаче кластеризации данных // В сб. трудов Первой традиционной всероссийской молодежной летней школе "Управление, информация и оптимизация", 2009, С. 25-31.

50. Шалъшов Д. С. On-line кластеризация данных с использованием рандомизированных алгоритмов // Сб. трудов VI школы-семинара молодых ученых "Управление большими системами", 2009, С. 389399.

51. Шалимов Д. С. Рандомизированный метод определения количества кластеров на множестве данных // Научно-технический вестник СПбГУ ИТМО, 2009, N 5, С. 111-116.

52. Ширяев А.Н. Вероятность. М.: Наука, 1980, 574 с.

53. Anderberg M. B,. Cluster Analysis for Applications. New York: Academic Press, 1973, 359 p.

54. Bagirov A.M., Yearwood J. A new nonsmooth optimization algorithm for minimum sum-of-squares clustering problems // European J. of Operational Research, 2006, N 170, pp. 578-596.

55. Ball G.H., Hall D.J. ISODATA, a novel technique for data analysis and pattern classification. Menlo Park, CA: Standford Res. Inst. Press, 1965.

56. Ben-Hur A., Elisseeff A., Guy on I. A stability based method for discovering structure in clustered data //In Pacific Symposium on Biocomputing, 2002, pp. 6-17.

57. Ben-Hur A., Guyon I. Detecting stable clusters using principal component analysis //In Methods in Molecular Biology. Humana press, 2003, pp. 159-182.

58. Bezdek J.C. Pattern Recognition with Fuzzy Objective Function Algorithms. New York: Plenum Press, 1981, 256 p.

59. Bezdek J.C., Pal S.K. Fuzzy Models for Pattern Recognition. Methods that Search for Patterns in Data. New York: IEEE Press, 1992, 539 p.

60. Bolshev L. N. Cluster analysis // Bull. Int. Stat. Inst, 1969, N 43, pp. 425-441.

61. Burges C. A Tutorial on Support Vector Machines for Pattern Recognition // J. Data Mining and Knowledge Discovery, 1998, N 2, pp. 121-167.

62. Calinski R., Harabasz J. A dendrite method for cluster analysis // Commun. Statistics, 1974, N 3, pp. 1-27.

63. Calafiore G., Campi M.C. Uncertain convex problems: randomized solutions and confidence levels // Mathematical Programming, 2005, N 102. pp. 25-46.

64. Can F. Incremental clustering for dynamic information processing // ACM Trans. Inf. Syst, 1993, N 11, pp. 143-164.

65. Carpenter G., Grossberg S. Hierarchical search using chemical transmitters in self-organizing pattern recognition architectures // Neural Networks, 1990, N 3, pp. 129-152.

66. Choudhury S., Murty M. N. A divisive scheme for constructing minimal spanning trees in coordinate space // Pattern Recogn. Lett, 1990, N 11, pp. 385-389.

67. Dempster A., Laird N., Rubin D. Maximum likelihood from incomplete data via the EM algorithm // J. of the Royal Statistical Society, 1977, Series B, N 39(1), pp. 1-38.

68. Day W. Complexity theory: An Introduction for Practitioners of Classification. New Jersey: World Scientific Publishing, 1992.

69. Dubes R. C. How many clusters are best? // Pattern Recogn, 1987 N 20, pp. 645-663.

70. Dudoit S., Fridlyand J. A prediction-based resampling method for estimating the number of clusters in a dataset // Genome Biol., 2002, N 3, pp. 112-129.

71. Dunn J.C. Well Separated Clusters and Optimal Fuzzy Partitions // J. Cybern., 1974, N 4, pp. 95-104.

72. Fayyad U.M., Piatetsky-Shapiro G., Smyth P., Uthurusamy R. Advances In Knowledge Discovery And Data Mining. Mcnlo Park, CA.: The MIT Press, 1996, 560 p.

73. Fisher R.A. The Use of Multiple Measurements in Taxonomic Problems // Annals of Eugenics, 1936, N 7, pp. 179-188.

74. Forgy E. W. Cluster analysis of multivariate data efficiency vs interpretability of classifications // Biometrics, 1965, N 21, pp. 768769.

75. Friedman N., Geiger D., Goldszmidt M. Bayesian network classifiers // Machine Learning, 1997, N 29, pp. 131-165.

76. Fridman H. P., Rubin J. On some invariant criterion for grouping data // J. Amer. Stat. Ass, 1967, N 67, pp. 1159-1178.

77. Fukunaga K. Introduction to Statistical Pattern Recognition. New York: Academic Press, 1972, 618 p.

78. Gold B., Morgan N. Speech and Audio Signal Processing: Processing and Perception of Speech and Music. New York: Wiley, 1999, 560 p.

79. S3. Gordon A. D. Identifying genuine clusters in a classification // Computational Statistics and Data Analysis, 1994. N 18, pp. 561-581.

80. Granichin 0. N., Shalymov D. S. New breed stochastic hybrid computers // In: Proc. of the 3-rd Int. IEEE Scientific Conf. on Physics and Control (PhysCon 2007), 2007, p. 178.

81. Granichin 0. N., Shalymov D. S. Speaker-independent isolated words recognition problem solving based on simultaneous perturbation stochastic approximation algorithm // Yalta Conf. on Discrete and Global Optimization, 2008, p. 13.

82. Hansen P., Ngai E., Cheung B.K., Mladenovic N. Analysis of global k-means, an incremental heuristic for minimum sum-of-squares clustering // Pattern Recognition, 2001, N 4, pp. 405-413.

83. Hartigan J.A. Clustering Algorithms. New York: Wiley, 1975. 351 p.

84. Hartigan J. A., Wong M. A. A k-means clustering algorithm // Applied Statistics, 1979, N 28, pp. 100-108.

85. Hogg R., McKean J., Craig A. Introduction to Mathematical Statistics. New Jersey: Prentice Hall, 2005, 576 p.

86. Hopfield J. Neurons with graded response have collective computational properties like those of two-state neurons // Proc. Natl. Acad. Sci. USA, 1984, N 81, pp.3088-3092.

87. Hoppner F., Klawonn F. A Contribution to Convergence Theory of Fuzzy c- Means and Derivatives // IEEE Transactions on Fuzzy Systems, 2003, N 11(5), pp. 682-694.

88. Hornick M. JSRs: Java Specification Requests Detail JSR 73 Data Mining API. http://webl.jcp.org/en/jsr/detail?id=73

89. Hubert L., Schultz J. Quadratic assignment as a general data-analysis strategy // J. Math. Statist. Psychol., 1974, N 76, pp. 190-241.

90. Hussain F., Cornell J. Character Recognition of Arabic and Latin Scripts // Proc. IEEE International Conference on Information Visualisation, 2000, pp. 51-56.

91. Jain A.K., Moreau J.V. Bootstrap technique in cluster analysis // Pattern Recognition, 1987, N 20, pp. 547-568.

92. Jardine N., Sibson R. Mathematical Taxonomy. London: John Wiley and Sons, 1971, 286 p.

93. Kaufman L., Rousseeuw P. Finding Groups in Data: An Introduction to Cluster Analysis. New York: Wiley, 1990. 368 p.

94. Kibzun A. L, Kan Yu. S. Stochastic Programming Problems (with probability and quantile functions). London: Wiley and Sons, 1996, 301 p.

95. Kiefer J., Wolfowitz J. Statistical Estimation on the Maximum of a Regression Function // Ann. Math. Statist., 1952, N 23, pp. 462-466.

96. Kohonen T. Self-Organizing Maps. New York: Springer-Verlag, third edition, 2001, 501 p.

97. Krzanowski W., Lai Y A criterion for determining the number of groups in a dataset using sum of squares clustering // Biometrics, 1985, N 44, pp. 23-34.

98. Kurita T. An efficient agglomerative clustering algorithm using a heap // Pattern Recogn, 1991, N 24, pp. 205-209.

99. Melton J., Eisenberg A SQL Multimedia and Application Packages // ACM SIGMOD Record, 2001, N 30, pp. 97-102.

100. Milligan G., Cooper M. An examination of procedures for determining the number of clusters in a data set // Psychometrika, 1985, N 50, pp. 159-179.

101. Morrison D. G. Multivariate Statistical Methods. New York: Me Grou Hill Book Company, 1967, 338 p.

102. Mufti G. D., Dertrand P., Moubarki L. Determining the number of groups from measures of cluster validity // In Proceedigns of ASMDA2005, 2005, pp. 404-414.

103. OMG Common Warehouse Metamodel (CWM) Specification. OMG, Version 1.0, 2001.

104. Parzen E. On Estimation of a Probability Density Function and Mode // Annals of Math. Statistics, 1962, N 33, pp. 1065-1076.

105. Quinlan J.R. Induction of decision trees // Mach. Learn., 1986, N 1, pp. 81-106.

106. R.abiner L. R., Juang B. H Fundamentals of Speech Recognition. -New Jersey: Prentice Hall, 1993. 496 p.

107. Rosenblatt F. Principles of Neurodynamics. New York: Spartan Press, 1962, 616 p.

108. Salton G. Developments in automatic text retrieval // Science, 1991, N 253, pp. 974-980.

109. Shalymov D. S. Noise robust isolated words recognition problem solving based on simultaneous perturbation stochastic approximation algorithm // The 20th Int. Conf. "Continuous Optimization and Knowledge-Based Technologies", 2008, C. 112-118.

110. Shalymov D., Skrygan K., Lyubimov D. Clustering algorithms meta applier (CAMA) toolbox // SYRCoSE (Spring Young Researchers Colloquium on Software Engineering), 2009, C. 61-64.

111. Shearer C. The CRISP-DM model: The new blueprint for data mining. // J. of Data Warehousing, 2000, N 5, pp 146-158.

112. Sheikh T. S., Guindi R. M. Computer recognition of arabic cursive script // Pattern Recognition, 1988, N 21(4), pp. 293-302.

113. Slagle J. R., Chang C. L., Heller S. R. A clustering and data-reorganizing algorithm // IEEE Trans. Syst. Man Cybern., 1975, N 5, pp. 125-128.

114. Sokal R,., P. Sneat Principles of Numerical Taxonomy. San Francisco: Freeman, 1963, 573 p.

115. Spall J.C. Multivariate Stochastic approximation using a simultaneous perturbation gradient approximation /'/ IEEE Transactions on Automatic Control. 1992, N 37, pp. 332-341.

116. Spall J. C. Introduction to Stochastic Search and Optimization. New York: Wiley, 2003, 620 p.

117. Sugar C., James G. Finding the number of clusters in a data set : An information theoretic approach // J. of the American Statistical Association, 2003. N 98, pp. 750-763.

118. Tibshirani R., Walther G., Hastie T. Estimating the number of clusters in a data set via the gap statistic // J. of the Royal Statistical Society, 2001, N 63. pp. 411-423.

119. Tran D., Wagner M., Zheng T. A Fuzzy approach to Statistical Models in Speech and Speaker Recognition // IEEE International Fuzzy Systems Conference Proceedings, Korea, 1999, pp. 1275-1280.

120. Tryon R.C. Cluster Analysis. New York: McGraw-Hill, 1939, 347 p.

121. Vapnik V. The Nature of Statistical Learning Theory. New York, Springer-Verlag, 1999, 314 p.

122. Vidyasagar M. Statistical learning tTheory and randomized algorithms for control // IEEE Control Systems, 1998, N 12, pp. 69-85.

123. Volkovich Z., Barzily Z., Morozensky L. A statistical model of cluster stability // Pattern Recognition, 2008, N 41, pp. 2174-2188.

124. William E. Approximate evaluation techniques for the single link and complete link hierarchical clastering procedures // J. of the American Statistical Association, 1974, N 69, pp. 698-704.

125. Wishart D. Mode analysis: A generalisation of nearest neighbour which reduces chaining effects // Numerical Taxonomy, 1969, pp. 282-311.

126. Yoon J. S., Lee G. H. A MFCC-Based CELP speech coder for server-based speech recognition in network environments // IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2007, N E90-A, pp. 626-632.