Влияние устойчивости алгоритмов классификации на точность их работы тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Московский государственный университет им. М.В. Ломоносова

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

Ветров Дмитрий Петрович

Влияние устойчивости алгоритмов классификации на точность их работы

Специальность 01.01.09 — дискретная математика и математическая

кибернетика

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

Работа выполнена на кафедре математических методов прогнозирования факультета вычислительной математики и кибернетики Московского государственного университета им. М.В. Ломоносова.

Научный руководитель: доктор физико-математических наук,

доцент Рязанов Владимир Васильевич

Официальные оппоненты: доктор технических наук, профессор,

ведущий научный сотрудник ВЦ РАН Моттль Вадим Вячеславович,

кандидат физико-математических наук, сотрудник фирмы Рогесвув Песков Николай Владимирович

Ведущая организация: Московский физико-технический институт

Защита диссертации состоится 8 декабря 2006 г. в 11-00 на заседании диссертационного совета Д 501.001.44 Московского государственного университета им. М.В. Ломоносова (119992, ГСП-2, г.Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2 уч. корпус, ауд. 685).

С диссертацией можно ознакомиться в библиотеке факультета ВМиК

МГУ.

Автореферат разослан « » ноября 2006 г.

Ученый секретарь диссертационного совета профессор

Трифонов Н.П.

ХооВРь

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

Актуальность темы. На протяжении последних 50 лет теория машинного обучения является одним из важных направлений прикладной математики. Она включает в себя разработку методов решения задач распознавания образов, восстановления регрессии, классификации, выделения кластеров, идентификации объектов, анализа изображений, нахождения скрытых закономерностей в данных и др. Необходимость в обучении ЭВМ возникает при отсутствии адекватных математических моделей исследуемой задачи. В основе теории лежит так называемый прецедентный подход к обучению. Предполагается, что имеется некоторый набор данных (прецедентов), характеризующий решаемую задачу. Требуется извлечь из этих данных объективные закономерности, которые будут использованы для принятия решений при обработке новых данных. Задачи такого рода часто возникают в плохоформализованных областях науки таких как биология, социология, медицина, геология, химия.

Первые работы в области теории распознавания и классификации по прецедентам появились в 30-х годах прошлого столетия и были связаны с теорией принятия решений (работы Дж. Неймана, Е. Пирсона), применением разделяющих функций к задаче классификации, решением вопросов проверки гипотез. В 50-х годах появились первые нейросетевые модели распознавания (перцептрон Розенблата), связанные с успехами в моделировании головного мозга. К концу 60-х годов уже были разработаны и детально исследованы различные подходы для решения задач распознавания в рамках статистических, перцептронных моделей и моделей с разделяющими функциями. Большой вклад в развитие теории машинного обучения и распознавания образов внесли отечественные ученые. Так М.А. Айзерман, Э.М. Браверман и Л.И. Розоноэр, разработав теорию потенциальных функций, стали ■ родоначальниками принципиально нового подхода по использованию ядровых методов машинного обучения. Среди других достижений отечественных специалистов можно отметить работы В.Н. Вапника, В.Д. Мазурова, А.Г. Ивахненко, Г.С. Лбова и др.

Крупной вехой в развитии теории распознавания образов явились работы Ю.И. Журавлева и его учеников по алгебраической теории

3 ,___

РОС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА С.-Петербург ОЭ 2Ц0&иа

распознавания. Унифицированный язык описания различных алгоритмов позволил предложить оригинальную схему построения корректных (безошибочных на контрольной выборке) алгоритмов классификации в алгебраическом замыкании множества исходных алгоритмов. Среди современных зарубежных исследований можно отметить работы К. Бишопа, Д. МакКая, А. Елиссееффа, П. Золлиха и др. В последнее время методы машинного обучения находят применение также и в таких, областях как экономика (особенно банковское дело, кредитование, анализ рынков ценных бумаг), физика. Методы data-mining, составляющие основу теории машинного обучения, являются одними из наиболее часто используемых средств извлечения знаний в генной инженерии, лингвистике, анализе баз данных.

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

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

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

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

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

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

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

Научная новизна. Понятие устойчивости алгоритмов машинного обучения не является новым. Попытки его использования для повышения обобщающей способности были предприняты, по крайней мере, дважды в статье Й. ЛеКуна по двойному обратному распространению ошибки (double back-propagation) в 1992г. и в работах А. Елиссееффа, О. Буске по устойчивости моделей классификаторов в 2001-2005гг. Первая концепция носит эвристический характер и имеет ограниченную область применения. Вторая парадигма, напротив, являясь теоретически обоснованной, накладывает слишком серьезные требования на семейства алгоритмов, поэтому получить оценки на обобщающую способность и устойчивость практически невозможно для большинства используемых алгоритмов машинного обучения.

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

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

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

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

Теоретическая и практическая ценность. Результаты, полученные в работе имеют большую практическую ценность, т.к. применение предложенных методов позволяет получать алгоритмы с более высокой обобщающей способностью, с меньшими вычислительными затратами, и более низкими требованиями к пользователю. Последнее позволяет расширить область применения методов машинного обучения и упростить процесс обучения и настройки структурных параметров алгоритмов распознавания. Практическая ценность предложенных в работе методов подтверждена многочисленными экспериментами. Часть описанных методов включена в состав универсальной программной системы анализа данных и прогнозирования .«РАСПОЗНАВАНИЕ», разработанной в ВЦ РАН.

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

Апробация работы. Результаты, изложенные в диссертации докладывались на международных конференциях по распознаванию образов ICPR (Кембридж, Великобритания, 2004, Гонконг, КНР, 2006), CIARP (Гавана, Куба, 2005), ICONIP (Гонконг, КНР, 2006), PRIA (В.-Новгород,

2002, и С.-Петербург, 2004), Всероссийской конференции ММРО (Пущино,

2003, и Звенигород, 2005). Основные результаты диссертации были изложены на научно-исследовательских семинарах МГУ ВМиК (рук. С.И. Гуров), ВЦ РАН (рук. В.В. Рязанов), Валлийского университета (рук. JI. Кунчева), университета Восточной Англии (рук. Г. Коули).

Публикации. По теме диссертации опубликовано 16 работ, в том числе 1 книга, 1 ■ статья в IEEE Transactions on Pattern Analysis and Machine Intelligence, 2 статьи в ЖВМ и МФ, 1 статья в WSEAS Transac-

tions on Information Science and Applications и 2 статьи в Pattern Recognition and Image.Analysis. Список работ приведен в конце автореферата. Описание части методов, разработанных автором включено в состав монографии «РАСПОЗНАВАНИЕ. Математические методы. Программная система. Практические приложения.»

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка иллюстраций (12 пунктов) и списка литературы (112 наименований). Общий объем работы составляет 138 страниц.

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

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

В главе 1 подробно исследуются вопросы выбора модели. Решение задачи машинного обучения обычно ведется путем оптимизации некоторого функционала качества по обучающей выборке. Практическая необходимость вынуждает ограничивать семейство отображений, подмножествами {A(w)}wSfi = А(0), допускающими параметризацию конечным числом параметров w. В дальнейшем рассматривается классическая задача классификации. Пусть (x,t) = {(^i^OlSi ~ обучающая выборка, причем х - признаковое описание объекта, a i - его метка класса. Тогда процесс обучения алгоритма можно выразить в виде следующей оптимизационной задачи

4>(t, х, w) -4 max weil

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

Определение 1.1. Моделью классификаторов назовем пространство Q всевозможных значений параметров алгоритма, которые допускаются

в ходе обучения, совокупность их априорных вероятностей Р(ги) и вид параметрического семейства отображений А.

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

В разделе 1.2 приводятся общие подходы к проблеме выбора модели. Кратко изложена структурная минимизация риска ВапникагЧервоненкиса, принцип минимальной длины описания Дж. Риссанена и Байесовская регуляризация Д. МакКая. Эти три подхода позволяют установить единые термины для исходного функционала качества, связанного с качеством работы алгоритма на обучающей выборке и регуляризатором. При этом в качестве нежелательных свойств выступают, соответственно, излишняя «гибкость», высокая алгоритмическая сложность классификаторов, низкое правдоподобие модели. Подробно проанализированы достоинства и недостатки каждого из рассмотренных подходов. Схема Байесовского обучения рассмотрена более детально.

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

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

w, а) = ехр ^ 1а(щ х, t)P(x, t)dxdtj = exp(La(w)) (1)

где P(x, t) - плотность распределения объектов генеральной совокупности, la(w,x,t) = logP(t|a;; w, а) - логарифм правдоподобия классификации объекта х.

При отклонении от оптимальных (в смысле выбранного функционала качества) на генеральной совокупности параметров алгоритма ад» на величину £ нижняя оценка на правдоподобие генеральной совокупности может быть получена как

P{T\X,w,a)>

> ехр (¿аю - Icv^MLj+^vv^HL^i) =

-В{ С, а, ад.)

Под обозначением VV/(.)|.„,=t0() подразумевается, что Гессиан используется в случае, когда функция вогнута по го в точке г«о- В противном случае, это слагаемое полагается равным нулю.

Определение 1.9. Нижней интегральной границей правдоподобия классификации генеральной совокупности называется величина

/•00

J(cx,w*)= / B((,a,wt)dC (2)

J о

Определение 1.12. Величина

Г* (lA-

J (a, w0) = ехр — У, l*(wo, xit U)~

J о

где /(го, х, = 1(,ш,х,{) + ^\ogP(w\a.) - логарифм регуляризованного правдоподобия правильной классификации г-го объекта обучающей выборки

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

Теорема 1.4. Пусть параметры алгоритма удовлетворяют условию регулярности, т.е.

при || го || —>■ оо, а функция их априорной плотности строго положительна и вместе со своими первыми двумя производными ограничена. Тогда величина локальной обоснованности является асимптотически несмещенной оценкой /(а, г»*) при обучении по максимуму выбранного критерия качества и объеме выборки т-ь оо.

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

Определение' 1.13. Модель ао выбрана с помощью принципа устойчивости, если на ней достигается максимум локальной обоснованности

Связь принципа устойчивости (или принципа максимума локальной обоснованности) с Байесовской регуляризацией иллюстрирует следующая теорема

Теорема 1.5. При обучении по принципу максимума правдоподобия обобщенных линейных моделей вида

с использованием логарифмически строго вогнутых функций правдоподобия и априорной -вероятности распределения параметров алгоритма, максимизация правдоподобия модели с использованием аппроксимации Лапласа эквивалентна оптимизации локальной обоснованности </(а,и>о).

РЩх, IV, а) О

ао = альтах .7(а,гоо)

В разделе 1.4 изложен метод релевантных векторов (Relevance Vector Machine) , представляющий собой пример применения Байесовского обучения для выбора подходящих коэффициентов регуляризации и автоматического определения релевантности (Automatic Relevance Determination). В разделе 1.5 описано обобщение этого метода с учетом разработанного принципа устойчивости. Путем введения в рассмотрение неустойчивости относительно координат центров ядровых функций z, эквивалентную неустойчивости относительно изменений положения объектов обучающей выборки, получен ядровой индекс пригодности, позволяющий эффективно проводить выбор параметров ядровой функции а минуя трудоемкую процедуру скользящего контроля

• KV(a\ _ P{t\x> wmp, a, z)P(wMp\a)

[а> zVditr

где первая компонента характеризует правдоподобие обучающей выборки (т.е. связана с точностью на обучении), вторая и третьи компоненты отвечают, соответственно, за устойчивость относительно изменений центров, и весов ядровых функций. Выражение £ представляет собой гессиан, относительно весов, логарифма регуляризованного правдоподобия в точке максимума по весам w = wmp-, взятый с противоположным знаком Е = —VVlogP(i|a;,io, a)F(w;|a), а компонента Z вычисляется по формулам

m / п ¿=1 \j=1

где тi - эффективный вес параметра Wi, характеризующий, насколько он определяется данными, a Aij - компонента устойчивости относительно изменения j-ой координаты г-ой ядровой функции

А^ —

|а| если Ъ < О

= 1|у/¥ехКЮ (l-«£(&)), «««в

В последнем выражении

9l0g(P(t|£C,WMi>,z))

а = -;-

dz>{

ь=

д2\оё(Р{±\х^мр,г))

(д4)2

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

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

В разделе 2.3 введено понятие неустойчивости классификатора на объекте и описана процедура выпуклой стабилизации коллектива алгоритмов. При построении коллективного решения используется т.н. контрольная выборка АгаШ = (у> и) =.{у1,и,-)?=1, которая, вообще говоря, отлична от обучающей выборки.

Определение 2.7. Неустойчивостью алгоритма распознавания А на ]-оы объекте контрольной выборки называется величина

где е; - единичный вектор соответствующей координаты, е = (еь..., е<*).

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

2а(Уз, е) = ^ -2 2>(% + е*е0 ~ Р(кЫ

>. • ч

|2

к= I « »=1

рА{г\х) =

Т,иМ*)РАт№

О)

где ¿^ : {1,2,... , д} —>■ {1,2,... ,р} - некоторая функция, определяющая индекс «наилучшего» алгоритма распознавания для каждого объекта контрольной выборки, а Ук : Е - весовые функции, обладающие

следующими свойствами:

ьк(х)>0, Чк = 1,2,...,5,

ук(х) -»• 0, при р(х, ук) оо, (4)

1> пРи К^Ы доопределение 2.11. Пара < {«¿(.Ж=1! <?(.) > называется выпуклым кластерным стабилизатором.

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

т=т

{1, р(х,Ук)<е,

О, ф ук : р(х, ук) < е,

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

Теорема 2.5. Алгоритм распознавания А, полученный применением рассмотренного выпуклого стабилизатора к семейству алгоритмов

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

В разделе 2.4 описана модификация этого подхода, получившая название выпуклого кластерного стабилизатора. Контрольная выборка разбивается на г кластеров С\, ...,СГ и для каждого кластера вводится понятие наилучшего алгоритма.

Определение 2.13. Алгоритм Ato является наилучшим для к-го кластера, если он доставляет максимум следующей целевой функции:

. «о = arg max [Acck(Ai) + aSi^t)]

где Асск(А{) - доля правильно классифицированных объектов контрольной выборки, принадлежащих к-иу кластеру, алгоритмом At, а Stk(Ai) -компонента устойчивости, определяемая следующим образом:

В последней формуле - количество объектов контрольной выборки, попавших в к-й кластер, Л и а - действительные числа такие, что А > О, а а > 0.

Определение 2.14. Алгоритм А получен из алгоритмов ...,АР путем выпуклой кластерной стабилизации, если его можно представить в виде следующей выпуклой комбинации исходных алгоритмов:

Рл№- п=Мх) (5)

где в : {1,2,...,г} {1,2.....р} - функция, возвращающая индекс

наилучшего алгоритма распознавания для соответствующего кластера, а

ьк : Ш? К - весовые функции, обладающие следующими свойствами: ук(х) > О = 1,2,...,г,

ук(х) 0 при р(х, Ок) -»• оо, (6)

В последних формулах Ик = ^ ^у,ес1: У> ~ Центры кластеров.

Определение 2.15. Пара < {г^(-)К=и > называется выпуклым кластерным стабилизатором.

В работе показано, что при использовании «четких» весовых функций, т.е.

1 при р(х, Дь) < р(х, Д) V» ф к, О иначе.

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

Теорема 2.6. Коллективное решение, полученное в результате применения выпуклого кластерного стабилизатора (5), (6) при г = д и О < а < 1, совпадает с результатом применения к коллективу выпуклого стабилизатора (3), (4) с той же системой весовых функций и ^Р(^) = Р{]).

Раздел 2.5 и 2.6 содержат результаты экспериментов и выводы. В частности, показано, что выпуклая кластерная стабилизация при естественном выборе параметров и весовых функциях

/ V 1 ( Р\х,-Р*Л

позволяет получать коллективные решения, в среднем, не уступающие по качеству основным методам коллективных решений, использующимся в мире. К интересным эффектам можно отнести значительное падение точности на тестовой выборке при установке «четких» весовых функций и/или при выборе о; = 0, т.е. игнорированию значений устойчивости алгоритмов.

В главе 3 исследован вопрос об устойчивости коллективных методов кластерного анализа (ансамблей кластеризаторов). Специфика задач

Щ

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

В разделе 3.5 подробно описано содержание эксперимента по использованию различных методик подсчета устойчивости с последующим выбором наиболее устойчивого решения для повышения качества кластеризации. Основным объектом исследования являются ансамбли алгоритмов /г-средних со случайным значением к и начальным приближением. Для проверки применимости методик используются различные реальные выборки для задач классификации с учителем, а также ряд модельных задач, содержащих кластеры различной формы. В ходе эксперимента установлено, что ансамбли кластеризаторов приводят, в среднем, к более устойчивым решениям. Наблюдается значительная корреляция между качеством кластеризации и устойчивостью решения в тех случаях, когда ансамбль правильно выявляет элементы кластеров. Наконец, наиболее устойчивыми (и более точными) могут оказываться решения, не соответствующие «истинному» количеству кластеров. Для нахождения наиболее точных вариантов кластеризации предложено использовать комбинированную меру устойчивости, характеризующую устойчивость алгоритмов-членов ансамбля и самого ансамбля.

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

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

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

На защиту выносятся следующие основные результаты, полученные в диссертационной работе:

- Нижняя интегральная оценка правдоподобия классификации произвольного объекта генеральной совокупности фиксированным алгоритмом распознавания и ее связь со значением обоснованности модели;

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

- Теоремы о возможности одновременной коррекции и стабилизации коллективов алгоритмов классификации;

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

- Комбинированный индекс устойчивости ансамблей кластеризаторов и методика его подсчета.

Публикации по теме диссертации

[1] Ветров Д.П., Кропотов Д.А. Алгоритмы выбора моделей и построения коллективных решений в задачах классификации, основанные на принципе устойчивости. М.:УРСС, 2006.

[2] Vetrov D. On Stability of Pattern Recognition Algorithms. Pattern Recognition and Image Analysis, 13(3), 2003, pp.470-475.

[3] Ветров Д.П. О синтезе корректных алгоритмов распознавания образов с минимальной величиной неустойчивости Ж. вычисл. матем. и матем. физ. 43(11), 2003, С.1754-1760.

[4] Zhuravlev Yu., Ryazanov V., Senko О., Biryukov A., Vetrov D., Dokukin A., Kropotov D. The Program System for Intellectual Data Analysis, Recognition and Forecasting. WSEAS Transactions on Information Science and Applications, 2(1), 2005. pp.55-59.

[5] Kropotov D., Tolstov I., Vetrov D. Decision Trees Regularization Based on Stability Principle. Pattern Recognition and Image Analysis, 15(1), 2005. pp.107109.

[6] Ветров Д.П., Кропотов Д.А. Выпуклая кластерная стабилизация алгоритмов распознавания как способ получения коллективных решений с высокой обобщающей способностью. Ж. вычисл. матем. и матем. физ. 45(7), 2005, С.1318-1325.

[7] Kuncheva L., Vetrov D. Evaluation of Stability of k-means Cluster Ensembles with Respect to Random Initialization, IEEE Trans. Mach. Intell. and Pattern Anal., 2006. To appear.

[8] Ветров Д.П. Об устойчивости алгоритмов распознавания образов. Труды 6-ой Международной конференции "Распознавание образов и анализ изображений: новые информационные технологии (РОАИ-6-2002)", 2002, С.96-100

[9] Ветров Д.П. Об одном методе регуляризации некорректно-поставленных задач распознавания образов. Докл. XI Всерос. конф. Матем. методы распознавания образов (ММРО-11). 2003, С.41-44.

[10] Vetrov D., Kropotov D. Data-dependent Classifier Fusion for Construction of Stable Effective Algorithms. Proc. 17th Internat. Conf. on Pattern Recognition (ICPR), 1, 2004, pp.144-147.

[11] Kropotov D., Ptashko N., Vetrov D. The Use of Bayesian Framework for Kernel Selection in Vector Machines Classifiers. Progress in Pattern Recognition, Image Analysis and Applications, LNCS 3773, Springer, 2005. pp.252-261.

[12] Ветров Д.П.,. Кропотов Д.А., Пташко И.О. О связи Байесовской регуляризации с устойчивостью алгоритмов распознавания. Докл. XII Всерос. конф. Матем. методы распознавания образов (ММРО-12). 2005, С.54-57.

[13] Ветров Д.П., 'Кропотов Д.А., Пташко Н.О. Использование принципа наибольшего основания для автоматического выбора ядровой функции. Докл. XII Всерос. конф. Матем. методы распознавания образов (ММРО-12). 2005, С.51т54.

[14] Ветров Д.П., Кропотов Д.А., Толстов И.В. Применение принципа минимальной длины описания для обрезания бинарных решающих

деревьев. Докл. XII Всерос. конф. Матем. методы распознавания образов (ММРО-12). 2005, С.57-60.

[15] Kropotov D., Ptashko N., Vasiliev О., Vetrov D. On Kernel Selection in Relevance Vector Machines Using Stability Principle, Proc. 18th Internat. Conf. on Pattern Recognition (ICPR), 4, 2006.

[16] Kropotov D., Vetrov D., Ptashko N., Vasiliev 0. The Use of Stability Principle for Kernel Determination in Relevance Vector Machines, ICONIP 2006, 1, LNCS 4232, Springer, 2006, pp.727-736.

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. Подписано к печати 30.10.2006 г. Формат 60x90 1/16. Усл.печл. 1,25. Тираж 80 экз. Заказ 748. Тел. 939-3890. Тел./факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

Ао&бА JfrÏÏV

»2 17 14

0 Введение

1 Выбор модели с помощью принципа устойчивости

1.1 Проблема выбора модели.

1.2 Общие методы выбора модели

1.2.1 Структурная минимизация риска.

1.2.2 Принцип минимальной длины описания.

1.2.3 Байесовское обучение.

1.3 Принцип устойчивости.

1.4 Метод релевантных векторов.

1.5 Ядровой индекс пригодности.

1.6 Результаты экспериментов

1.6.1 Модельная задача

1.6.2 Реальные данные.

1.7 Обсуждение и выводы.

2 Выпуклая стабилизация коллективов алгоритмов

2.1 Особенности построения коллективных решений.

2.2 Методы получения коллективных решений.

2.2.1 Общие положения.

2.2.2 Комитетные методы.

2.2.3 Методы выбора классификатора.

2.3 Выпуклый стабилизатор.

2.3.1 Неустойчивость классификаторов.

2.3.2 Стабилизация корректных алгоритмов.

2.3.3 Стабилизация некорректных алгоритмов.

2.4 Выпуклая кластерная стабилизация.

2.5 Результаты экспериментов

2.6 Выводы.

3 Устойчивость ансамблей кластеризаторов

3.1 Специфика задачи кластерного анализа.

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

3.2.1 Методы построения ансамблей кластеризаторов.

3.2.2 Устойчивость методов кластеризации.

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

3.3 Описание эксперимента.

3.3.1 Устойчивость ансамблей относительно исходных алгоритмов кластеризации.

3.3.2 Связь между устойчивостью ансамбля и его точностью.

3.3.3 Использование устойчивости ансамблей для определения числа кластеров.

3.4 Выводы.

На протяжении последних 50 лет теория машинного обучения является одним из важнейших направлений прикладной математики и информатики. Она включает в себя разработку методов решения задач распознавания образов, восстановления регрессии, классификации, выделения кластеров, идентификации объектов, анализа изображений, нахождения скрытых закономерностей в данных и др. Необходимость в обучении ЭВМ возникает при отсутствии адекватных математических моделей исследуемой задачи. В основе теории лежит так называемый прецедентый подход к обучению. Предполагается, что имеется некоторая обучающая выборка признаковых описаний. Требуется извлечь из этих данных объективные закономерности и построить алгоритм, который будет использован (машиной или человеком) для принятия решений при обработке новых данных. Заметим, что задачи такого рода часто возникают в плохоформализованных областях таких как биология, социология, медицина, геология, химия. В последнее время методы машинного обучения находят применение также в таких областях знаний как экономика (особенно банковское дело, кредитование, анализ рынков ценных бумаг), физика. Методы data-mining, составляющие основу теории машинного обучения являются одними из наиболее активно используемых средств извлечения знаний в генной инженерии, лингвистике, анализе баз данных. Первые работы в области теории распознавания и классификации по прецедентам появились в 30-х годах прошлого столетия и были связаны с теорией принятия решений (работы Дж. Неймана, Е. Пирсона [88]), применением разделяющих функций к задаче классификации [51], решением вопросов проверки гипотез [110]. В 50-х годах появились первые нейросетевые модели распознавания (перцептрон Розенблата), связанные с успехами в моделировании головного мозга [26]. К концу 60-х годов уже были разработаны и детально исследованы различные подходы для решения задач распознавания в рамках статистических, перцептронных моделей, и моделей с разделяющими функциями. Большой вклад в развитие теории машинного обучения и распознавания образов внесли отечественные ученые. Так М.А. Айзерман, Э.М. Браверман и Л.И. Розоноэр, разработав теорию потенциальных функций, стали родоначальниками принципиально нового подхода по использованию ядровых методов машинного обучения [1]. Широко известны такие достижения советских (российских) ученых как метод комитетов, изложенный в работах В.Д. Мазурова [23], метод группового учета аргументов А.Г. Ивахненко [20], решающие деревья Г.С. Лбова [22], метод обобщенного портрета В.Н. Вапника и пр. Крупной вехой в развитии теории распознавания образов явились работы академика РАН Ю.И. Журавлева и его учеников (алгебраическая теория распознавания, теория алгоритмов вычисления оценок) [15], [27], [14], [24], [29]. Унифицированный язык описания поведения различных алгоритмов позволил предложить оригинальную схему построения коллективных решений в алгебраическом замыкании множества исходных алгоритмов. Среди современных зарубежных исследований можно отметить работы К. Бишопа [38], Д. МакКая [84], А. Елиссееффа [40], П. Золлиха [99] и др.

В дальнейшем будут рассматриваться преимущественно задачи классификации с учителем и без учителя. Необходимо отметить, что к ним сводятся многие задачи анализа данных (нахождение закономерностей, прогнозирование дискретных состояний, идентификация, прогноз исходов). Рассмотрим классическую постановку задачи классификации с учителем1. Пусть имеется некоторый набор данных, состоящий из независимых однотипных элементов, которые в дальнейшем будут называться объектами или прецедентами. Каждый объект характеризуется d—мерным вектором признаков х G Pi х . х Pd к классом t, к которому он принадлежит. Вообще говоря, структура множеств Pi может быть различной. Тем не менее, в дальнейшем будем считать, что все Р{ = R, т.е. х Е Rd. Кроме того, будем полагать, что переменная t принимает конечное число значений из неупорядоченного множества t 6 Т. Будем считать объекты элементами вероятностностного пространства < Rd х Т,Вхт,Рхт >, где В является сг-алгеброй Борелевских подмножеств в Rd х Т. 2 Требуется построить такой алгоритм А (алгоритм распознавания или классификации), который по значениям признаков объекта х возвращал бы оценки вероятностей принадлежности х к тому или иному классу. Иными словами

Л : {Pa(s\X)}U

Вероятности Pa(s\x) будем называть апостериорными вероятностями принадлежности объекта х к классу s. Заметим, что во многих работах под алгоритмом распознавания понимается отображение

1)

В данной работе такой подход не рассматривается ввиду относительной

1 Постановка задачи классификации без учителя (кластеризация данных) будет рассмотрена в главе 3

2В дальнейшем, для удобства обозначений, индексы вероятностной меры (сг-алгебры) будем опускать, если из контекста понятно о какой мере (ст-алгебре идет речь. бедности методов, позволяющих проводить оценку качества получившегося алгоритма в последнем случае. При необходимости, к алгоритмам вида (1) можно перейти преобразованием вида А(х) = argmaxi<s<z Pa(s\x). Результат такого преобразования будем брать в качестве итоговой классификации объекта алгоритмом А. Легко видеть, что это преобразование естественным образом обобщается на случай, когда различные виды ошибок классификации имеют разную цену. В настоящей работе, не ограничивая общности, будем исходить из того, что все виды ошибок классификации равноценны.

Пусть имеется некоторая контрольная выборка данных с известным правильным ответом, не участвовавшая в обучении, (у,и) = {Vj^Uj)^. Два подхода к интерпретации алгоритма распознавания дают две различные возможности для оценивания качества алгоритма относительно рассматриваемых данных. Пусть 1{а = Ь) - индикаторная функция, возвращающая единицу, если а = Ь, и ноль в противном случае.

Определение 1. Частотной оценкой алгоритма по контрольной выборке называется величина

1 9 q з=i

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

Определение 2. Правдоподобием правильной классификации контрольной выборки объектов называется величина q ыу) = рл{и\у) = ~[[раыуз)

3=1

Легко показать, что Ра{п\у) как функция А действительно является функцией правдоподобия. 3 Будем считать, что каждый алгоритм однозначно определяется значением своих параметров w. В дальнейшем, при рассмотрении зависимости работы алгоритма от изменения его параметров для удобства иногда будем обозначать функцию Ра{1\%) как P(t\x,w), а правдоподобие выборки РаЩх) как P(t\x,w).

Процесс обучения алгоритма распознавания заключается в нахождении значений параметров ги* наилучших, в некотором смысле, относительно обучающей выборки Dtrain = = (xi,ti)™=l w* = arg тахФ(£, x, w) wGQ где Q, - множество допустимых значений параметров алгоритма.

Функционал Ф(t,x,w) обычно так или иначе связан с качеством работы алгоритма на обучающей выборке. В частном случае, при Ф(£, x,w) = P(t\x, w) получается известный принцип максимального правдоподобия. В общем случае, оптимизация качества на обучающей выборке не приводит к получению наилучшего алгоритма с точки зрения генеральной совокупности. Более того, часто наблюдается даже значительное снижение качества на независимой (тестовой) выборке, т.е. выборке, не предъявлявшейся алгоритму на этапе обучения, но для которой известны правильные ответы. Такое явление получило название переобучения или перенастройки

Достаточно убедиться, что при фиксированном алгоритме А и входных данных у функция Рл(и\у) задает распределение вероятностей всевозможных классификаций объектов выборки алгоритма (overtraining, overfitting). Оно связано с тем, что, вообще говоря, не все закономерности, определяющие классификацию обучающей выборки справедливы для генеральной совокупности. Как правило, задачи с реальными данными содержат зашумленную информацию, что, в частности, приводит к наличию ложных закономерностей в конечных подмножествах генеральной совокупности. Наиболее интригующей задачей машинного обучения является построение общих методов, позволяющих добиться максимальной обобщающей способности алгоритма, т.е. способности выявить как можно больше объективных закономерностей, присущих генеральной совокупности при как можно меньшем количестве ложных закономерностей. Следует отметить, что до сих пор не существует единого общего метода контроля обобщающей способности алгоритмов распознавания. Проблема связана с тем, что понятие обобщающей способности для своей формализации и оценивания требует работы со всей генеральной совокупностью объектов, которая, естественно, недоступна. Различные методы косвенного оценивания обобщающей способности путем анализа используемого алгоритма и обучающей выборки пока не привели к общепринятому решению. Целью настоящей работы является исследование влияния устойчивости (понимаемой в различных смыслах) алгоритмов классификации на их обобщающую способность и разработка методов классификации с высокими обобщающими свойствами.

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

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

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

Автор хотел бы выразить искреннюю признательность своему наставнику д.ф.-м.н. В.В. Рязанову и академику РАН Ю.И. Журавлеву за постоянную поддержку и внимание, оказывавшуюся на всех этапах работы. Данная работа была бы невозможной без помощи Дмитрия Кропотова, друга и коллеги автора. Также автор благодарен всем студентам, принимавшим активное участие в научной работе по данной теме. Исследования, лежащие в основе диссертации, проводились на протяжении нескольких лет при частичной поддержке различных грантов Российского Фонда Фундаментальных Исследований (проекты 02-01-08007, 02-07-90134, 02-0790137, 03-01-00580, 04-01-08045, 05-01-00332, 05-07-90085, 05-07-90333, 0601-00492), целевой программы ОМН РАН е2, гранта Президента РФ НШ1721.2003.1, а также фонда INTAS (проект YS04-83-2942).

3.4 Выводы

Устойчивость алгоритмов кластеризации относительно различных случайных факторов играет важную роль. Высокая устойчивость решения представляется крайне желательной. В данной главе исследовалась устойчивость ансамблей клатеризаторов, состоящих из алгоритмов к-средних, запущенных со случайным начальным приближением и случайным числом кластеров к. Устойчивость ансамбля сравнивалась с устойчивостью отдельных алгоритмов ^-средних для значений к, варьировавшихся от 2 до 20. Основные результаты, полученные в ходе эксперимента, кратко перечислены ниже.

1. В целом, ансамбли кластеризаторов являются более устойчивыми, чем отдельные кластеризаторы. Это особенно ярко проявляется с увеличением к (Рис. 9), когда Se(k) > Sl(k) для всех 20 выборок данных. Этот факт делает интуитивно понятным введение комбинированного показателя устойчивости S*, направленного на поиск такого числа кластеров к, при котором истинная структура данных отражалась бы в наибольшей степени. При использовании только устойчивости собственно ансамбля весьма вероятен пропуск [возможного] пика точности, соответствующего верному числу кластеров, при котором наблюдается пик устойчивости отдельных кластеризаторов. Примером такого эффекта может служить выборка «лодка» в таблице 6. Максимум устойчивости собственно ансамбля приходится на к = 20 кластеров (точность 0.28). Максимум комбинированного показателя устойчивости совпадает с максимумом индивидуальной устойчивости на 2 кластерах (точность 0.34). Обратным примером может служить выборка ionosphere, где пик индивидуальной устойчивости на верном числе кластеров к = 2 недостаточен для соответствующего пика комбинированного показателя. Однако, несмотря на то, что верное количество кластеров не определено, точность ансамбля на 20 кластерах (максимум комбинированной устойчивости) выше, чем на истинном их числе.

2. В ходе экспериментов были обнаружены следующие соотношения устойчивости и точности. В то время как для одних выборок Se(k) и А6(к) имели корреляцию, близкую к единице (0.97, для выборки glass), для других выборок имела место сильная отрицательная корреляция (—0.93, для выборки crabs). В целом, между S*(k) с одной сотороны, и Ае(к) и А*(к) с другой, имеется корреляция, хотя ее значение довольно сильно меняется от выборки к выборке (таблицы 4 и 5). Поскольку на практике истинное распределение объектов по кластерам неизвестно, в общем случае, нельзя гарантировать хорошую корреляцию между устойчивостью и точностью. Наименьшее количество отрицательных коэффициентов корреляции с точностью на различных выборках данных имеет показатель S*(k).

3. Гипотеза о связи устойчивости кластеризатора при верном числе кластеров широко распространена в современной научной литературе. Согласно ей, устойчивость решения означает, что в анализируемых данных найдена некоторая (верная) структура кластеров. В этом случае, число кластеров, использовавшееся в алгоритме может отвечать верному числу кластеров, а найденная структура данных верной конфигурации кластеров. Соответственно, для поиска верного (или наиболее подходящего) числа кластеров рекомендуется брать точку, отвечающую максимуму используемого показателя устойчивости. В настоящем исследовании такой подход использовался применительно к ансамблям кластеризаторов. В одном случае устойчивость оценивалась для ансамбля из 2500 отдельных алгоритмов, в другом - по 100 ансамблям из 25 алгоритмов каждый. Предложенный показатель комбинированной устойчивости ансамбля показал лучшие результаты по сравнению с индивидуальными и групповыми попарными и общими методами подсчета устойчивости (таблица 6). Также улучшение в точности отмечено по сравнению с известным количеством кластеров. В особенности это проявилось на реальных данных, в которых «истинное» количество кластеров можно определить по-разному.

4. По результатам исследования можно предложить следующую процедуру кластеризации:

1) Выбрать максимально возможное число кластеров Ктах, размер ансамбля L и их количество Т;

2) Сгенерировать L х Т алгоритмов fc-средних со случайным к от 2 до К ■

3) Случайным образом сгруппировать кластеризаторы в Т ансамблей из L отдельных алгоритмов и вычислить S* (к) используя (33), для к = 2, . . . , i^maxj

4) Найти к* = argmaxfc {£*(&)};

5) Соединить все L х Т отдельных кластеризаторов вместе, вычислить матрицу согласованнности М, и, трактуя ее как матрицу схожести объектов, воспользоваться алгоритмом иерархической группировки на к*. Полученное разбиение Р* вернуть в качестве искомого.

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

4 Заключение

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

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

В третьей главе рассматривался вопрос о принципиальной возможности использования понятия устойчивости кластеризации для определения объективной структуры данных. Основной задачей проводимых экспериментов была оценка влияния устойчивости решения задачи кластерного анализа коллективом кластеризаторов относительно начального приближения (и различного выбора числа кластеров в алгоритмах-членах ансамбля) на точность нахождения структуры кластеров (понимавшуюся как близость состава найденных кластеров к априори известному «истинному» разбиению). Эксперименты позволили установить, что устойчивость коррелирует с точностью в тех случаях, когда принципиально возможно достижение высокой точности. Если максимально возможная точность кластеризации низка, то значимая корреляция между ней и устойчивостью отсутствует. Наилучшие результаты были достигнуты при использовании т.н. комбинированного показателя устойчивости, характеризующего совместную устойчивость алгоритмов-членов ансамбля и самого ансамбля кластеризации.

1. Айзерман М.А., Браверманн Э.М., Розоноэр Л.И. Метод потенциальных функций в теории обучения машин. М.: Наука, 1970.

2. Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. М.:Наука, 1974.

3. Ветров Д.П. Об устойчивости алгоритмов распознавания образов. Труды 6-ой Международной конференции "Распознавание образов и анализ изображений: новые информационные технологии (РОАИ-6-2002)11, 2002, С.96-100

4. Ветров Д.П. О синтезе корректных алгоритмов распознавания образов с минимальной величиной неустойчивости Ж. вычисл. матем. и матем. физ. 43(11), 2003, С. 1754-1760.

5. Ветров Д.П. Об одном методе регуляризации некорректно-поставленных задач распознавания образов. Докл. XI Всерос. конф. Матем. методы распознавания образов (ММРО-11). 2003, С.41-44.

6. Ветров Д.П., Кропотов Д.А. Выпуклая кластерная стабилизация алгоритмов распознавания как способ получения коллективных решений с высокой обобщающей способностью. Ж. вычисл. матем. и матем. физ. 45(7), 2005, С.1318-1325.

7. Ветров Д.П., Кропотов Д.А., Пташко И.О. О связи Байесовской регуляризации с устойчивостью алгоритмов распознавания. Докл. XII Всерос. конф. Матем. методы распознавания образов (ММРО-12). 2005, С.54-57.

8. Ветров Д.П., Кропотов Д.А., Пташко И.О. Использование принципа наибольшего основания для автоматического выбора ядровой функции. Докл. XII Всерос. конф. Матем. методы распознавания образов (ММРО-12). 2005, С.51-54.

9. Ветров Д.П., Кропотов Д.А., Толстов И.В. Применение принципа минимальной длины описания для обрезания бинарных решающих деревьев. Докл. XII Всерос. конф. Матем. методы распознавания образов (ММРО-12). 2005, С.57-60.

10. Вешторт A.M., Зуев Ю.А., Краснопрошин В.В. Двухуровневая схема распознавания с логическим корректором. Распознавание, классификация, прогноз. Математические методы и их применение. Вып.2, 1989, С.73-98.

11. И. Воронцов К.В. Комбинаторные обоснования обучаемых алгоритмов. Ж. вычисл. матем. и матем. физ. 44(11), 2004, С.2099-2112.

12. Воронцов К.В. Обзор современных исследований по проблеме качества обучения алгоритмов. Таврический вестник информатики и математики. 2004.

13. Ворончихин В.А., Рязанов В.В. О видео-логическом подходе к решению задач таксономии. Труды Всероссийской конференции «Математические методы распознавания образов» (ММРО-8), 1997, С.30-31

14. Дюкова Е.В. Асимптотически оптимальные тестовые алгоритмы в задачах распознавания. Проблемы кибернетики. Вып.39,1982, С.165-199.

15. Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации. Проблемы кибернетики. Вып.ЗЗ, 1978, С.5-68.

16. Журавлев Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. I. Кибернетика, 4, 1977, С.5-17., II. Кибернетика, 6, 1977., III. Кибернетика, 2, 1978, С.35-43.

17. Журавлев Ю.И. Избранные научные труды. М.:Магистр, 1998.

18. Журавлев Ю.И., Рязанов В.В., Сенько О.В. РАСПОЗНАВАНИЕ. Математические методы. Программная система. Практические применения. М.:Фазис, 2006.

19. Зуев Ю.А. Метод повышения надежности классификации при наличии нескольких классификаторов, основанный на принципе монотонности. Ж. вычисл. матем. и матем. физ. 21(1), 1981, С.157-167.

20. Ивахненко А.Г. Системы эвристической самоорганизации в технической кибернетике. Киев: Технжа, 1971.

21. Колмогоров А.Н. Три подхода к определению понятия «количество информации». Проблемы передачи информации. 1(1), 1965, С.3-11

22. Лбов Г.С. Методы обработки разнотипных экспериментальных данных. Новосибирск: Наука, 1981.

23. Мазуров Вл.Д. Комитеты систем неравенств и задача распознавания // Кибернетика. 3, 1971, С. 140-146.

24. Матросов В.Л. Синтез оптимальных алгоритмов в алгебраических замыканиях моделей алгоритмов распознавания. Распознавание, классификация, прогноз: Матем. методы и их применение. Вып.1, 1988, С.149-175.

25. Расстригин Л.А., Эренштейн Р.Х. Метод коллективного распознавания. М.:Энергоиздат, 1981.

26. Розенблатт Ф. Принципы нейродинамики (перцептрон и теория механизмов мозга). М.:Мир, 1965.

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

28. Рязанов В.В. О построении оптимальных алгоритмов распознавания и таксономии (классификации) при решении прикладных задач. Распознавание, классификация, прогноз: Матем. методы и их применение. Вып.1, 1988, С.229-279.

29. Рязанов В.В. Комитетный синтез алгоритмов распознавания и классификации. Ж. вычисл. матем. и матем физ. 21(6), 1981, С.1533-1543.

30. Рязанов В.В. О синтезе классифицирующих алгоритмов на конечных множествах алгоритмов классификации (таксономии). Ж. вычисл. матем. и матем физ. 22(2), 1982, С.429-440.

31. Рязанов В.В. О решении задачи кластерного анализа на базе склеивания решений по признаковым подпространствам. Труды 5-й Всероссийской конференции «Распознавание образов и анализ изображений", 2000, С.118-122

32. Шумский С.А. Байесовская регуляризация обучения. IV Всерос. научно-техн. конф. «Нейроинформатика 2002", Т.2, 2002, С.30-93.

33. Шурыгин A.M. Прикладная статистика: Робастность, оценивание, прогноз. М.:Финансы и статистика, 2000.

34. Ayat, N.E., Cheriet, M., Suen, C.Y.: Optimization of SVM Kernels using an Empirical Error Minimization Scheme. Proc. of the First International Workshop on Pattern Recognition with Support Vector Machines, 2002

35. Bel Mufti G., Bertrand P., El Moubarki L. Determining the number of groups from measures of cluster validity. Proc. of ASMDA2005, 2005, pp.404-414.

36. Ben-Hur A., Elisseeff A., Guyon I. A stability based method for discovering structure in clustered data. Proc. of Pacific Symposium on Biocomputing, 2002, pp.6-17.

37. Bishop C. Pattern Recognition and Machine Learning. Springer, 2006.

38. Blake C. and Merz C. UCI repository of machine learning databases, 1998. http://www. ics. uci. edu/ mlearn/MLRepository.html.

39. Bousquet О., Elisseeff A. Algorithmic stability and generalization performance. Advances in Neural Information Processing Systems. 13, 2001, pp.196-202.

40. Bousquet 0., Elisseeff A. Stability and generalization. Journal of Machine Learning Research. 2, 2002, рр.499-Ц526.

41. Breiman L. Bagging predictors. Machine Learning, 24(2), 1996, рр.123-Щ40.

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

43. Chapelle O., Vapnik V. Model Selection for Support Vector Machines. Advances in Neural Information Processing Systems 12, ed. S.A. Solla, Т.К. Leen and K.-R. Muller, MIT Press, 2000.

44. Corduneanu A., Bishop C. Variational Bayesian model selection for mixture distributions. In T. Richardson and T. Jaakkola (Eds.), Proc. of 8th International Conference on Artificial Intelligence and Statistics, 2001, рр.27-Ц34

45. Drucker H., LeCun Y. Improving Generalization Performance Using Double Backpropagation. IEEE Transaction on Neural Networks, 3(6), 1992, pp.991997.

46. Duda R., Hart P. Pattern Classification and Scene Analysis. John Wiley & Sons, NY, 1973.

47. Dudoit S., Fridlyand J. Bagging to improve the accuracy of a clustering procedure. Bioinformatics, 19(9), 2003, pp.1090-1099.

48. Esposito F., Malerba D., Semeraro G. A compararive analysis of methods for pruning decision trees IEEE Trans. Pattern Analys. Mach. Intelligence, 19(5), 1997, pp.476-492.

49. Fern X., Brodley C. Random projection for high dimensional data clustering: A cluster ensemble approach. Proc. 20th International Conference on Machine Learning, (ICML), 2003, pp. 186-193.

50. Fisher R.A. The use of multiple measurements in taxonomic problems. Ann. Eugenics, 7(2), 1936, pp.179-188.

51. Fischer В., Buhmann J. Bagging for path-based clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(11), 2003, pp.14111415.

52. Fred A. Finding consistent clusters in data partitions. In F. Roli and J. Kit-tier, editors, Proc. 2nd International Workshop on Multiple Classifier Systems, MCS'01, volume 2096 of Lecture Notes in Computer Science, Springer, 2001, pp. 309-318.

53. Fred A., Jain A. Data clustering using evidence accumulation. Proc. 16th International Conference on Pattern Recognition, (ICPR), 2002, pp. 276-280.

54. Fred A., Jain A. Robust data clustering. Proc. IEEE Computer Society Conference on Computer Vision and Pattern Recognition, (CVPR), 2003.

55. Fred A., Jain A. Combining multiple clusterungs using evidence accumulation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(6), 2005, pp.835-850.

56. Freund Y. Boosting a weak learning algorithm by majority. COLT: Proceedings of the Workshop on Computational Learning Theory. Morgan Kaufmann Publishers, 1990.

57. Friedman J., Hastie Т., Tibshirani R. The Elements of Statistical Learning. Springer, 2001.

58. Friedrichs F., Igel C. Evolutionary Tuning of Multiple SVM Parameters. Neu-rocomputing, 64, 2005, pp.107-117.

59. Ghosh J. Multiclassifier systems: Back to the future. In F.Roli and J.Kittler, editors, Proc. 3rd International Workshop on Multiple Classifier Systems, (MCS'02), volume 2364 of Lecture Notes in Computer Science, Springer, 2002, pp. 1-15.

60. Gold C., Sollich P. Model Selection for Support Vector Machine Classification. Neurocomputing, 55(1-2), 2003, pp.221-249.

61. Gordon A. Classification. Chapman к Hall /CRC, Boca Raton, FL, 1999.

62. Greene D., Tsymbal A., Bolshakova N., Cunningham P. Ensemble clustering in medical diagnostics. Technical Report TCD-CS-2004-12, Department of Computer Science, Trinity College, Dublin, Ireland, 2004.

63. Hadjitodorov S., Kuncheva L., Todorova L. Moderate diversity for better cluster ensembles. Information Fusion, 2005. To appear.

64. Ни X., Yoo I. Cluster ensemble and its applications in gene expression analysis. Proc. 2nd Asia-Pacific Bioinformatics Conference (APB2004), 2004.

65. Hubert L., Arabie P. Comparing partitions. Journal of Classification, 2,1985, pp.193-218.

66. Jain A., Dubes R. Algorithms for Clustering Data. Prentice Hall, Englewood Cliffs, NJ, 1988.

67. Kittler J., Hatef M., Duin R., Matas J. On combining classifiers IEEE Trans. Pattern Analys. and Mach. Intelligence, 20(3), 1998, pp.226-239.

68. Kropotov D., Ptashko N., Vetrov D. The Use of Bayesian Framework for Kernel Selection in Vector Machines Classifiers. Progress in Pattern Recognition, Image Analysis and Applications, LNCS 3773, Springer, 2005. pp.252-261.

69. Kropotov D., Tolstov I., Vetrov D. Decision Trees Regularization Based on Stability Principle. Pattern Recognition and Image Analysis, 15(1), 2005. pp.107-109.

70. Kropotov D., Vetrov D., Ptashko N., Vasiliev 0. On Kernel Selection in Relevance Vector Machines Using Stability Principle, Proc. 18th Intrenat. Conf. on Pattern Recognition (ICPR), 2006. To appear.

71. Kuncheva L. Combining Pattern Classifiers. Methods and Algorithms. Wiley, 2004.

72. Kuncheva L., Bezdek J., Duin R. Decision templates for multiple classifier fusion: an experimental comparison Pattern Recognition, 34(2), 2001, pp.299-314.

73. Kuncheva L., Hadjitodorov S. Using diversity in cluster ensembles. Proceedings of IEEE Int Conf on Systems, Man and Cybernetics, 2004.

74. Kuncheva L., Vetrov D. Evaluation of Stability of k-means Cluster Ensembles with Respect to Random Initialization, IEEE Trans. Mach. Intell. and Pattern Anal., 2006. To appear.

75. Kutin S., Niyogi P. Almost-everywhere algorithmic stability and generalization error. Tech. Rep. TR-2002-03: University of Chicago, 2002.

76. Kwok J. The Evidence Framework Applied to Support Vector Machines. IEEE Trans, on Neural Networks, 11(5), 2000.

77. Lange Т., Roth V., Borun M., Buhmann J. Stability-based validation of clustering solutions. Neural Computation, 16, 2004, pp. 1299-1323.

78. Law M., Jain A. Cluster validity by boostrapping partitions. Technical Report MSU-CSE-03-5, Michigan State University, 2003.

79. Levine E., Domany E. Resampling method for unsupervised estimation of cluster validity. Neural Computation, 13, 2001, pp.2573-2593.

80. Lipnikas A. Classifier fusion with data-dependent aggregation schemes. Proc. 7th Internat. Conf. Inform. Networks, Systems and Technol., 1, 2001, pp.147153.

81. Antos A., Kegl В., Linder Т., Lugosi G. Data-dependent margin-based generalization bounds for classification, Journal of Machine Learning Research, 3, 2002, pp.73-98.

82. MacKay D. Bayesian interpolation Neural Computation, 4(3), 1992, pp.415447.

83. MacKay D. Information Theory, Inference, and Learning Algorithms. Cambridge University Press, 2003.

84. Maulik U.,Bandyopadhyay S. Performance evaluation of some clustering algorithms and validity indices. IEEE Transaction on Pattern Analysis and Machine Intelligence, 24(12), 2002, pp.1650-1654.

85. Minaei В., Topchy A., Punch W. Ensembles of partitions via data resampling. Proceedings of the International Conference on Information Technology: Coding and Computing, (ITCC04), 2004.

86. Monti S., Tamayo P., Mesirov J., Golub T. Consensus clustering: A resampling based method for class discovery and visualization of gene expression microarray data. Machine Learning, 52, 2003, pp.91-118.

87. Neyman J., Pearson E. On the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of Royal Society, Series A, 231, 1933, pp.289-337.

88. Poggio Т., Girosi F. Regularization algorithms for learning that are equivalent to multilayer networks. Science, 247, 1990, pp.978-982.

89. Qi Y, Minka Т., Picard R.,Ghahramani Z. Predictive Automatic Relevance Determination by Expectation Propagation. Proceedings of 21st International Conference on Machine Learning (ICML), 2004.

90. Rand W. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical Association, 66, 1971, pp.846-850.

91. Rasmussen C., Williams C., Gaussian Processes for Machine Learning, MIT Press, 2005.

92. Ripley В. Pattern Recognition and Neural Networks. Cambridge University Press, 1996.

93. J.Rissanen. Modeling by shortest data description. Automatica, 14, 1978, pp.465-471.

94. Roth V., Lange Т., Braun M, Buhmann J. A resampling approach to cluster validation. Proc. in Computational Statistics (COMSTAT2002), Physica-Verlag, 2002, pp.123-128.

95. Scholkopf В., Smola A. Learning with Kernels. MIT Press, 2002

96. Seeger M. Gaussian processes for machine learning. International Journal of Neural Systems, 14(2), 2004, pp.69-106

97. Shapire R., Freund Y., Bartlett P., Lee W. Boosting the margin: a new explanation for the effectiveness of voting methods. Proc. 14th Internat. Conf. Mach. Learning (ICML), 1998, pp.322-330.

98. Sollich P., Williams C. Using the equivalent kernel to understand Gaussian process regression. In L. K. Saul, Y. Weiss, and L. Bottou, editors, Advances in Neural Information Processing Systems, 17, 2005.

99. Strehl A., Ghosh J. Cluster ensembles A knowledge reuse framework for combining multiple partitions. Journal of Machine Learning Research, 3, 2002, pp.583-618.

100. Tibshirani R., Walther G., Hastie T. Estimating the number of clusters in a dataset via Gap statistic. J. Royal Statistical Society, В 63, 2001, pp.411-423.

101. Tipping M. Sparse Bayesian Learning and the Relevance Vector Machines. Journal of Machine Learning Research, 1, 2001, pp.211-244.

102. Topchy A., Jain A., Punch W. Combining multiple weak clusterings. Proceedings of IEEE Int Conf on Data Mining, 2003, pp.331-338.

103. Topchy A., Jain A., Punch W. A mixture model for clustering ensembles. Proc. of SIAM Conference on Data Mining, 2004, pp.379-390.

104. Vilarino F., Kuncheva L., Radeva P. ROC curves in video analysis optimization in intestinal capsule endoscopy. Pattern Recognition Letters, 2005. To appear.

105. Vapnik V. The Nature of Statistical Learning Theory. Springer-Verlag, 1995

106. Vapnik V. Statistical Learning Theory. Wiley, 1998.

107. Vetrov D. On Stability of Pattern Recognition Algorithms. Pattern Recognition and Image Analysis, 13(3), 2003, pp.470-475.

108. Vetrov D., Kropotov D. Data-dependent Classifier Fusion for Construction of Stable Effective Algorithms. Proc. 17th Internat. Conf. on Pattern Recognition (ICPR), 1, 2004, pp.144-147.

109. Wald A. Contributions to the theory of statistical estimation and testing of hypotheses. Ann. Math. Stat., 10, 1939, pp.299-326.

110. Weingessel A., Dimitriadou E., Hornik K. An ensemble method for clustering, 2003. Working paper, http://www.ci.tuwien.ac.at/Conferences/DSC-2003/.

111. Weston J., Mukherjee S., Chapelle O., Pontil M., Poggio Т., Vapnik V. Feature Selection for Support Vector Machines. Proc. of 15th International Conference on Pattern Recognition, 2, 2000.

112. Woods K., Keelmeyer W., Bowyer K. Combination of multiple classifiers using local accuracy estimates. IEEE Transactions on Pattern Recognition and Machine Intelligence, 19, 1997, pp.405-410.

113. Xu L., Krzyzak A., Suen C. Methods of combining multiple classifiers and their application to handwritten recognition. IEEE Trans. Systems, Man, Cybernetics, 22, 1992, pp.418-435.

114. Zhu H., Williams C., Rohwer R., Morciniec M. Gaussian regression and optimal finite dimensional linear models. In С. M. Bishop, editor, Neural Networks and Machine Learning. Springer-Verlag, Berlin, 1998.

115. Обучающая выборка искусственной задачи. Черная линияоптимальная по Байесу граница классов.

116. Доля выборок, для которых устойчивость ансамблейпревосходит усредненную устойчивость отдельныхкластеризаторов для попарной (Sp) и энтропийной (<Snp)мер устойчивости.1021. S*

117. Устойчивость Sp, Sp, -f, а также точность ансамбля А как функции от к для задач thyroid и «лепестки".105

118. Зависимость коэффициента корреляции между А* и S* от maxfcv4*(£;) для 20 выборок.106

119. Максимально возможная точность (серый) и точность, полученная при использовании к (S'*) кластеров (черный). . . . 110