Алгоритм СТОЛП

Материал из MachineLearning.

(Различия между версиями)

Версия 16:52, 29 декабря 2009

Алгоритм СТОЛП (STOLP) - алгоритм отбора эталонных объектов для метрического классификатора.

Содержание

1 Назначение алгоритма
2 Эталоны
3 Алгоритм STOLP
4 Особенности алгоритма
5 Литература
6 См. также

Назначение алгоритма

Пусть дана обучающая выборка $X^l=(x_i, y_i)_{i=1}^l$ , где $x_i$ - объекты, $y_i=y^*(x_i)$ - классы, которым принадлежат эти объекты. Кроме того, задана метрика $\rho \: X \times X \rightarrow \mathbb{R}$ , такая, что выполняется гипотеза компактности. При классификации объектов метрическим классификатором, например, методом ближайших соседей на основании данной выборки необходимо вычислять расстояния от классифицируемого объекта для всех объектов обучающей выборки, а время, затрачиваемое на это для каждого классифицируемого объекта, пропорционально размеру обучающей выборки. Кроме того, оказывается необходимым хранить большой объем данных, среди которых есть и наиболее типичные представители классов, то есть эталоны, и неинформативные объекты, при удалении которых из обучающей выборки качество классификации не изменится, и выбросы, или шумовые объекты - объекты, находящиеся в гуще "чужого" класса, только ухудшающие качество классификации. Поэтому необходимо уменьшить объем обучающей выборки, оставив в ней только эталонные объекты.

Эталоны

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

Простой перебор для отбора эталонов не подходит, так как число способов выбора по t эталонов для каждого класса (число классов k) составляет $\prod_{j=1}^k C_{m_j}^t$ . Но перебор вариантов можно сократить при помощи алгоритма STOLP

Алгоритм STOLP

Вход

Выборка $X^l$
Допустимая доля ошибок $l_0$
Порог отсечения выбросов δ

Кроме того, известны алгоритм классификации и формула вычисления величины риска (W) для объекта быть распознанным как объект чужого класса.

Выход

Построить множество эталонов Ω∈X^l

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

отбросить выбросы (объекты $X^l$ с W, большей некоторой константы δ)
сформировать начальное приближение Ω - выбрать из каждого класса по объекту, обладающему
- либо максимальной величиной риска^[1]
- минимальной величиной риска^[1]
наращивание множества эталонов (пока число объектов, распознанных неправильно, не станет меньше ):
- классифицировать объекты $X^l$ , используя в качестве обучающей выборки Ω
- пересчитать величины риска
- среди объектов каждого класса, распознанных неправильно, выбрать объекты с максимальным W, добавляемые к Ω

Примечания

возможен вариант, при котором в обучающей выборке все объекты, принадлежащие одному из классов, имеют W, большую порога отсечения выбросов. Тогда они окажутся отброшены на первом шаге алгоритма. В таком случае имеет смысл сначала сформировать начальное приближение Ω, а потом отбросить объекты с W, большей δ, кроме объектов, входящих в Ω
если для классификации объектов $X^l$ при построении множества эталонов используется метод ближайшего соседа, то W можно вычислять как отношение расстояния от данного объекта до ближайшего объекта "своего" класса к расстоянию до ближайшего объекта "чужого" класса
независимо от алгоритма, используемого для классификации $X^l$ , в качестве W можно взять $-M(x_i, \Omega)$ , где $M(x_i, \Omega)$ - отступ на объекте $x_i$ при текущем наборе эталонов Ω

Особенности алгоритма

Результат работы алгоритма - разбиение всего множества объектов $X^l$ на эталонные, шумовые (выбросы) и неинформативные.
Алгоритм STOLP имеет относительно низкую эффективность, так как на каждой итерации для присоединения очередного эталона необходимо заново классифицировать все объекты, еще не ставшие эталонами и считать на них величину риска. Для ускорения работы можно добавлять по несколько далеко отстоящих друг от друга эталонов, не пересчитывая величины риска.

Литература

См. также

Метрический классификатор

Отступ

алгоритм FRiS-СТОЛП

Данная статья является непроверенным учебным заданием.

Студент: Участник:LuarSoll

Преподаватель: Участник:Константин Воронцов

Срок: 31 декабря 2009

До указанного срока статья не должна редактироваться другими участниками проекта MachineLearning.ru. По его окончании любой участник вправе исправить данную статью по своему усмотрению и удалить данное предупреждение, выводимое с помощью шаблона {{Задание}}.

См. также методические указания по использованию Ресурса MachineLearning.ru в учебном процессе.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A1%D0%A2%D0%9E%D0%9B%D0%9F»

Категории: Метрические алгоритмы классификации | Непроверенные учебные задания

@@ Строка 1: / Строка 1: @@
-'''Алгоритм СТОЛП''' (STOLP) - [[Алгоритм|алгоритм]] отбора эталонных объектов для [[Метрический классификатор|метрического классификатора]]; алгоритм минимизации набора эталонов.
+'''Алгоритм СТОЛП''' (STOLP) - алгоритм отбора эталонных объектов для [[Метрический классификатор|метрического классификатора]].
-==Задача==
+==Назначение алгоритма==
-Дана выборка <tex>X^l</tex>. Необходимо оставить в качестве [[Обучающая выборка|обучающей выборки]] только ее часть, не ухудшая качества [[Классификация|классификации]], то есть построить множество эталонов, не менее чем по одному эталону на класс.
+Пусть дана [[Обучающая выборка|обучающая выборка]] <tex>X^l=(x_i, y_i)_{i=1}^l</tex>, где <tex>x_i</tex> - объекты, <tex>y_i=y^*(x_i)</tex> - классы, которым принадлежат эти объекты. Кроме того, задана [[Метрика|метрика]] <tex>\rho \: X \times X \rightarrow \mathbb{R}</tex>, такая, что выполняется [[Гипотеза компактности|гипотеза компактности]]. При классификации объектов [[Метрический классификатор|метрическим классификатором]], например, [[Метод ближайших соседей|методом ближайших соседей]] на основании данной выборки необходимо вычислять расстояния от классифицируемого объекта для всех объектов обучающей выборки, а время, затрачиваемое на это для каждого классифицируемого объекта, пропорционально размеру обучающей выборки. Кроме того, оказывается необходимым хранить большой объем данных, среди которых есть и наиболее типичные представители классов, то есть ''эталоны'', и ''неинформативные'' объекты, при удалении которых из обучающей выборки качество классификации не изменится, и ''выбросы'', или ''шумовые объекты'' - объекты, находящиеся в гуще "чужого" класса, только ухудшающие качество классификации.
+Поэтому необходимо уменьшить объем обучающей выборки, оставив в ней только эталонные объекты.
 ==Эталоны==
@@ Строка 14: / Строка 15: @@
 *Допустимая доля ошибок <tex>l_0</tex>
 *Порог отсечения выбросов δ
-Кроме того, известны [[Алгоритм|алгоритм]] [[Классификация|классификации]] и формула вычисления величины риска (W) для объекта быть распознанным как объект чужого класса.
+Кроме того, известны алгоритм классификации и формула вычисления величины риска (W) для объекта быть распознанным как объект чужого класса.
 ===Выход===
@@ Строка 22: / Строка 23: @@
 * отбросить выбросы (объекты <tex>X^l</tex> с W, большей некоторой константы δ)
 * сформировать начальное приближение Ω - выбрать из каждого класса по объекту, обладающему
-**минимальной величиной риска<ref>{{книга |автор = Воронцов К.В. |заглавие = Лекции по метрическим алгоритмам классификации | ссылка = http://www.machinelearning.ru/wiki/images/9/9d/Voron-ML-Metric.pdf}}</ref>
 **либо максимальной величиной риска<ref>{{книга |автор= Загоруйко Н. Г. |заглавие = Прикладные методы анализа данных и знаний. |место = Новосибирск |издательство = ИМ СО РАН |год = 1999}}</ref>
+**минимальной величиной риска<ref>{{книга |автор = Воронцов К.В. |заглавие = Лекции по метрическим алгоритмам классификации | ссылка = http://www.machinelearning.ru/wiki/images/9/9d/Voron-ML-Metric.pdf}}</ref>
 * наращивание множества эталонов (пока число объектов, распознанных неправильно, не станет меньше <tex>l_0</tex>):
 ** [[Классификация|классифицировать]] объекты <tex>X^l</tex>, используя в качестве обучающей выборки Ω