WWW.DOC.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Различные документы
 


«Метрические алгоритмы классификации Отбор эталонов и оптимизация метрики Профиль компактности и скользящий контроль Метрические методы классификации К. В. ...»

Метрические алгоритмы классификации

Отбор эталонов и оптимизация метрики

Профиль компактности и скользящий контроль

Метрические методы классификации

К. В. Воронцов

vokov@forecsys.ru

Этот курс доступен на странице вики-ресурса

http://www.MachineLearning.ru/wiki

Машинное обучение (курс лекций, К.В.Воронцов)

март 2011

К. В. Воронцов (www.ccas.ru/voron) Метрические методы классификации

Метрические алгоритмы классификации

Отбор эталонов и оптимизация метрики

Профиль компактности и скользящий контроль Содержание Метрические алгоритмы классификации Гипотеза компактности Метод ближайших соседей и его обобщения Снова метод парзеновского окна Метод потенциальных функций Отбор эталонов и оптимизация метрики Понятие отступа Алгоритм отбора эталонных объектов STOLP Понятие конкурентного сходства Простой жадный алгоритм оптимизации метрики Профиль компактности и скользящий контроль Полный скользящий контроль CCV Понятие профиля компактности Отбор эталонов по функционалу CCV К. В. Воронцов (www.ccas.ru/voron) Метрические методы классификации Гипотеза компактности Метрические алгоритмы классификации Метод ближайших соседей и его обобщения Отбор эталонов и оптимизация метрики Снова метод парзеновского окна Профиль компактности и скользящий контроль Метод потенциальных функций Гипотеза компактности

Задача классификации:

объекты, Y ответы (идентификаторы классов);

X X = (xi, yi ) обучающая выборка;

i=1

Гипотеза компактности:

Схожие объекты, как правило, лежат в одном классе.

Формализация понятия сходства :

Задана функция расстояния : X X [0, ).

Например, евклидово расстояние:

n 1/2 xij j (u, xi ) = u, j=1 где u = (u 1,..., u n ), xi = (xi1,..., xin ) признаковые описания объектов.

К. В. Воронцов (www.ccas.ru/voron) Метрические методы классификации Гипотеза компактности Метрические алгоритмы классификации Метод ближайших соседей и его обобщения Отбор эталонов и опт

–  –  –

Метод ближайшего соседа w (i, u) = [i=1].

Преимущества:

простота реализации;

интерпретируемость решений, вывод на основе прецедентов (case-based reasoning, CBR)

Недостатки:

неустойчивость к погрешностям (шуму, выбросам);

отсутствие настраиваемых параметров;

низкое качество классификации;

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

–  –  –

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

4.0 3.5 3.0 2.5 2.0 1.5 1.0 0.5

-0.5

-1.0

-1.5

-2.0

-1.5 -1.0 -0.5 0 0.5 1.0 1.5 2.0 2.5 3.0 3.5

–  –  –

Анализ преимуществ и недостатков

Преимущества:

простота реализации;

не надо хранить выборку (потоковый алгоритм обучения);

разреженность: не все обучающие объекты учитываются.

Недостатки:

медленная сходимость;

результат обучения зависит от порядка просмотра объектов;

слишком грубо настраиваются веса i ;

вообще не настраиваются параметры hi ;

вообще не настраиваются центры потенциалов;

может, некоторые i можно было бы обнулить?

–  –  –

Алгоритм STOLP: преимущества и недостатки

Преимущества отбора эталонов:

сокращается число хранимых объектов;

сокращается время классификации;

объекты распределяются по величине отступов;

Недостатки алгоритма STOLP:

необходимость задавать параметр ;

относительно низкая эффективность O(||2 ).

Другие методы отбора:

стратегия последовательного удаления не-эталонов;

минимизация полного скользящего контроля (CCV);

FRiS-STOLP на основе оценок конкурентного сходства.

–  –  –

Найдём t [0, 1] и признак j, при которых благонадёжность D(jt ) максимальна (два вложенных цикла перебора).

3. Будем добавлять признаки до тех пор, пока благонадёжность D(jt ) увеличивается.

К. В. Воронцов (www.ccas.ru/voron) Метрические методы классификации Метрические алгоритмы классификации Полный скользящий контроль CCV Отбор эталонов и оптимизация метрики Понятие профиля компактности Профиль компактности и скользящий контроль Отбор эталонов по функционалу CCV Полный скользящий контроль CCV

–  –  –

Замечание 1. При q = 1 имеем: CCV(X L ) = LOO(X L ).

Замечание 2. CCV характеризует лишь среднюю частоту ошибок, но не учитывает её разброс.

К. В. Воронцов (www.ccas.ru/voron) Метрические методы классификации Метрические алгоритмы классификации Полный скользящий контроль CCV Отбор эталонов и оптимизация метрики Понятие профиля компактности Профиль компактности и скользящий контроль Отбор эталонов по функционалу CCV Понятие профиля компактности

–  –  –

0.8 0.6 0.4 0.2 0 0.2 0.4 0.6 0.8 1.0 0 0.2 0.4 0.6 0.8 1.0 0 0.2 0.4 0.6 0.8 1.0 0 0.2 0.4 0.6 0.8 1.0 1.0 0.8 0.6 0.4 0.2 0.6 0.5 0.4 0.3 0.2 0.1

–  –  –

К. В. Воронцов (www.ccas.ru/voron) Метрические методы классификации Метрические алгоритмы классификации Полный скользящий контроль CCV Отбор эталонов и оптимизация метрики Понятие профиля компактности Профиль компактности и скользящий контроль Отбор эталонов по функционалу CCV Модельные данные Модельная задача классификации: 1000 объектов.

Алгоритм 1NN К. В. Воронцов (www.ccas.ru/voron) Метрические методы классификации Метрические алгоритмы классификации Полный скользящий контроль CCV Отбор эталонов и оптимизация метрики Понятие профиля компактности Профиль компактности и скользящий контроль Отбор эталонов по функционалу CCV Последовательный отсев не-эталонных объектов

–  –  –

К. В. Воронцов (www.ccas.ru/voron) Метрические методы классификации Метрические алгоритмы классификации Полный скользящий контроль CCV Отбор эталонов и оптимизация метрики Понятие профиля компактности Профиль компактности и скользящий контроль Отбор эталонов по функционалу CCV Последовательный отсев не-эталонных объектов

–  –  –

Зависимость CCV от числа удаленных неэталонных объектов.

Похожие работы:

«Известия высших учебных заведений. Поволжский регион УДК 101.1:316 В. П. Демидов ЗРЕЛОСТЬ ЧЕЛОВЕКА И ПАРАМЕТРЫ СОЦИАЛЬНОГО ВРЕМЕНИ Аннотация. В статье сделана попытка охарактеризовать ос...»

«384 ЛЮДИ И ВЕЩИ С.А. БЕЛОБОРОДОВ ЮВЕЛИРНОЕ ИСКУССТВО В ЕКАТЕРИНБУРГЕ В ПЕРИОД ЕГО РАСЦВЕТА (конец XVIII первая треть XIX вв.) Употребив в названии статьи термин "ювелирное искусство", необходимо определить, что именно мы понимаем под этим словосочетанием. Признавая, что в наши дн...»

«1 МГУ имени М.В. ЛОМОНОСОВА ОЛИМПИАДА "ПОКОРИ ВОРОБЬЕВЫ ГОРЫ-2013" ОБЩЕСТВОЗНАНИЕ Инструкция для участника олимпиады: олимпиадная работа состоит из двух частей – выполнения заданий на бланке и написания эссе. На олимпиаду отводится 180 минут (3 часа). Вы сами определя...»

«ПРОЕКТ Правила по благоустройству территории муниципального образования "Кривополянский сельсовет" Правила по благоустройству территории муниципального образования "Кривополянский сельсовет" разработаны в соответствии с приказом Министерства...»

«1 И.А.Зеленев младший научный сотрудник Центра социологических исследований МГУ им. М.В.Ломоносова Синдром депрессии и политические ориентации в странах СНГ. Представления людей о соответствующих их потребностям целях политической деятельности и приемлемых для них средствах достижения этих целей формируют политические ориентации. В...»

«Практикум по курсу "Основы земельного законодательства" Самостоятельная работа №1 Тема: "Изъятие и предоставление земельных участков" Решаемая задача: Закрепление знаний о порядке изъятия и предоставления земельных участков, а также о порядке выкупа находящихся в частной собственности земельных участков для государствен...»

«Работы сотрудников лаборатории "Нелинейная оптика  конденсированных сред" в реферируемых журналах  (фамилии сотрудников ЦИОТ выделены полужирным шрифтом) А.В. Иванов, Е.Ю. Перлин. Предпробойное возбуждение кристаллов при двойном мн...»







 
2017 www.doc.knigi-x.ru - «Бесплатная электронная библиотека - различные документы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.