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

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

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

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

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

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

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 от числа удаленных неэталонных объектов.