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

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

Версия 16:28, 26 декабря 2009 (править) LuarSoll (Обсуждение | вклад) ← К предыдущему изменению		Версия 14:09, 28 декабря 2009 (править) (отменить) LuarSoll (Обсуждение | вклад) К следующему изменению →
Строка 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==
-	===Для отбора эталонных объектов===	+	*Первый шаг: отбросить выбросы (то есть элементы выборки с [[Отступ|отступом]], меньшим некоторой константы δ)
-	*Из [[Обучающая выборка|обучающей выборки]] необходимо изъять ''шумовые объекты'', так как их наличие только ухудшает [[Классификация|классификацию]]	+	*Второй шаг: сформировать начальное приближение
-	*Без снижения качества [[Классификация|классификации]] из [[Обучающая выборка|обучающей выборки]] можно изъять ''неинформативные объекты'', что уменьшит объем хранимой информации и время на ее обработку	+	*Третий шаг: "жадное" наращивание множества эталонов, пока число ошибок станет не меньше некоторой константы l<sub>0</sub>
-	===Для оценки качества выборки===	+
-	*Если большая часть объектов [[Обучающая выборка|обучающей выборки]] имеет положительные отступы, выборку можно считать разделимой	+
-	*Если в выборке много объектов с отрицательными отступами, гипотеза компактности классов не выполняется и применение метрических алгоритмов с данной метрикой для данной задачи классификации является нецелесообразным	+
-	*Если в выборке много объектов с отступами, близкими к нулю, классификация неустойчива	+
-		+
-	==Литература==	+
-	{{книга	+
-	|автор = Воронцов К.В.	+
-	|заглавие = Лекции по метрическим алгоритмам классификации	+
-	|ссылка = http://www.machinelearning.ru/wiki/images/9/9d/Voron-ML-Metric.pdf	+
-	}}	+
-		+
-	==См. также==	+
-	[[Метрический классификатор]]	+

---

Версия 14:09, 28 декабря 2009

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

Задача

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

Эталоны

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

Простой перебор для отбора эталонов не подходит, так как число способов выбора по t эталонов для каждого класса (число классов k) составляет . Но перебор вариантов можно сократить при помощи алгоритма STOLP

Суть алгоритма STOLP

• Первый шаг: отбросить выбросы (то есть элементы выборки с отступом, меньшим некоторой константы δ)
• Второй шаг: сформировать начальное приближение
• Третий шаг: "жадное" наращивание множества эталонов, пока число ошибок станет не меньше некоторой константы l₀