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

• Ветров, Дмитрий Петрович
• кандидат физико-математических наук
• 2006

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

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) анализа данных. Данный подход представляется достаточно общим. По мнению автора он может быть использован как альтернатива скользящему контролю и известным методам выбора моделей.

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Ветров, Дмитрий Петрович, 2006 год

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