Участник:LuarSoll/Песочница

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

< Участник:LuarSoll(Различия между версиями)

Текущая версия

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

Содержание

1 Задача
2 Эталоны
3 Алгоритм STOLP
4 Литература
5 См. также

Задача

Дана выборка $X^l$ . Необходимо оставить в качестве обучающей выборки только ее часть, то есть построить множество эталонов, не менее чем по одному эталону на класс.

Эталоны

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

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

Алгоритм STOLP

Вход

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

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

Выход

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

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

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

Примечания

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

Литература

↑ Воронцов К.В. Лекции по метрическим алгоритмам классификации.
↑ Загоруйко Н. Г. Прикладные методы анализа данных и знаний.. — Новосибирск: ИМ СО РАН, 1999.

См. также

Метрический классификатор Отступ алгоритм FRiS-СТОЛП

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:LuarSoll/%D0%9F%D0%B5%D1%81%D0%BE%D1%87%D0%BD%D0%B8%D1%86%D0%B0»

@@ Строка 1: / Строка 1: @@
-'''Отступ''' (margin) объекта из [[Обучающая выборка|обучающей выборки]] - величина, показывающая степень типичности этого объекта
+'''Алгоритм СТОЛП''' (STOLP) - алгоритм отбора эталонных объектов для [[Метрический классификатор|метрического классификатора]]; алгоритм минимизации набора эталонов.
-==Основная формула==
+==Задача==
-Отступ объекта <tex>x_i \in X^l</tex> относительно [[Алгоритм|алгоритма]] [[Классификация|классификации]], имеющего вид <tex>a(u)=\mathrm{arg}\max_{y\in Y}\Gamma_{y}(u)</tex> - определяется формулой <tex>M(x_i)=\Gamma_y_i(x_i)-\max_{y \in Y \setminus y_i}\Gamma_y(x_i)</tex>
+Дана выборка <tex>X^l</tex>. Необходимо оставить в качестве обучающей выборки только ее часть, то есть построить множество эталонов, не менее чем по одному эталону на класс.
-==Степени типичности объектов==
+==Эталоны==
-*''Эталонные объекты'' - объекты, имеющие большой положительный отступ, плотно окруженные объектами своего класса и являющиеся наиболее типичными его представителями.
+*Эталонами для i-го класса могут служить такие объекты этого класса, что расстояние от любого принадлежащего ему объекта из обучающей выборки расстояние до ближайшего "своего" эталона больше, чем расстояние до ближайшего "чужого" эталона, то есть все объекты обучающей выборки классифицируются правильно по набору эталонов.
-*''Неинформативные объекты'' - объекты, имеющие положительный отступ. Изъятие их из выборки не влияет на качество [[Классификация|классификации]].
+*Кроме того, эталон можно определить как объект с большим положительным [[Отступ|отступом]].
-*''Пограничные объекты'' - объекты с отступом, близким к нулю. [[Классификация]] пограничных ответов неустойчива, малые изменения [[Метрика|метрики]], параметров [[Алгоритм|алгоритма]] [[Классификация|классификации]] или обучающей выборки могут изменить их классификацию.
+Простой перебор для отбора эталонов не подходит, так как число способов выбора по t эталонов для каждого класса (число классов k) составляет <tex>\prod_{j=1}^k C_{m_j}^t</tex>. Но перебор вариантов можно сократить при помощи алгоритма STOLP
-*''Ошибочные объекты'' - объекты с отрицательным отступом. На них данный [[Алгоритм|алгоритм]] [[Классификация|классификации]] дает ошибку
-*''Шумовые объекты'' (''выбросы'') - объекты с большим по модулю отрицательным отступом. Они плотно окружены объектами другого класса и возникают из-за ошибок или недостатка информации в исходных данных.
-==Применение отступов==
+==Алгоритм STOLP==
-===Для отбора эталонных объектов===
+===Вход===
-*Из [[Обучающая выборка|обучающей выборки]] необходимо изъять ''шумовые объекты'', так как их наличие только ухудшает [[Классификация|классификацию]]
+*Выборка <tex>X^l</tex>
-*Без снижения качества [[Классификация|классификации]] из [[Обучающая выборка|обучающей выборки]] можно изъять ''неинформативные объекты'', что уменьшит объем хранимой информации и время на ее обработку
+*Допустимая доля ошибок <tex>l_0</tex>
-===Для оценки качества выборки===
+*Порог отсечения выбросов δ
-*Если большая часть объектов [[Обучающая выборка|обучающей выборки]] имеет положительные отступы, выборку можно считать разделимой
+Кроме того, известны алгоритм классификации и формула вычисления величины риска (W) для объекта быть распознанным как объект чужого класса.
-*Если в выборке много объектов с отрицательными отступами, гипотеза компактности классов не выполняется и применение метрических алгоритмов с данной метрикой для данной задачи классификации является нецелесообразным
-*Если в выборке много объектов с отступами, близкими к нулю, классификация неустойчива
+===Выход===
+Построить множество эталонов Ω∈X<sup>l</sup>
+===Описание алгоритма===
+* отбросить выбросы (объекты <tex>X^l</tex> с W, большей некоторой константы δ)
+* сформировать начальное приближение Ω - выбрать из каждого класса по объекту, обладающему
+**минимальной величиной риска<ref>{{книга |автор = Воронцов К.В. |заглавие = Лекции по метрическим алгоритмам классификации | ссылка = http://www.machinelearning.ru/wiki/images/9/9d/Voron-ML-Metric.pdf}}</ref>
+**либо максимальной величиной риска<ref>{{книга |автор= Загоруйко Н. Г. |заглавие = Прикладные методы анализа данных и знаний. |место = Новосибирск |издательство = ИМ СО РАН |год = 1999}}</ref>
+* наращивание множества эталонов (пока число объектов, распознанных неправильно, не станет меньше <tex>l_0</tex>):
+** классифицировать объекты <tex>X^l</tex>, используя в качестве обучающей выборки Ω
+** пересчитать величины риска
+** среди объектов каждого класса, распознанных неправильно, выбрать объекты с максимальным W, добавляемые к Ω
+===Примечания===
+* возможен вариант, при котором в обучающей выборки все объекты выборки имеют W, большую порога отсечения выбросов. Тогда они окажутся отброшены на первом шаге алгоритма. В таком случае имеет смысл сначала сформировать начальное приближение Ω, а потом отбросить объекты с W, большей δ, кроме объектов, входящих в Ω
+* если для классификации объектов <tex>X^l</tex> при построении множества эталонов используется метод ближайшего соседа, то W можно вычислять как отношение расстояния от данного объекта до ближайшего объекта "своего" класса к расстоянию до ближайшего объекта "чужого" класса
+* независимо от алгоритма, используемого для классификации <tex>X^l</tex>, в качестве W можно взять <tex>-M(x_i, \Omega)</tex>, где <tex>M(x_i, \Omega)</tex> - [[Отступ|отступ]] на объекте <tex>x_i</tex> при текущем наборе эталонов Ω
+==Литература==
+<references/>
+==См. также==
+[[Метрический классификатор]]
+[[Отступ]]
+[[алгоритм FRiS-СТОЛП]]