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

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

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

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

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

Содержание

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

Пусть дана обучающая выборка X^l=(x_i, y_i)_{i=1}^l, где x_i — объекты, y_i=y^*(x_i) — классы, которым принадлежат эти объекты. Кроме того, задана метрика \rho \: X \times X \rightarrow \mathbb{R}, такая, что выполняется гипотеза компактности. При классификации объектов метрическим классификатором a(u, X^l) = \mathrm{arg}\max_{y\in Y} \Gamma_y (u, X^l) = \mathrm{arg}\max_{y\in Y} \sum_{i=1}^l[y_u^(i)=y]w(i, u), например, методом ближайших соседей необходимо вычислять расстояния от классифицируемого объекта до всех объектов обучающей выборки. Время, затрачиваемое на это для каждого классифицируемого объекта, пропорционально размеру обучающей выборки. Кроме того, оказывается необходимым хранить большой объем данных.

Но не все объекты обучающей выборки равноценны. Среди них есть наиболее типичные представители классов, то есть эталоны; неинформативные объекты, при удалении которых из обучающей выборки качество классификации не изменится; выбросы, или шумовые объекты — объекты, находящиеся в гуще «чужого» класса, только ухудшающие качество классификации.

Поэтому необходимо уменьшить объем обучающей выборки, оставив в ней только эталонные объекты для каждого класса.

Эталоны

  • Эталоны — это такое подмножество выборки X^l, что все объекты X^l (или их большая часть) классифицируются правильно при использовании в качестве обучающей выборки множества эталонов.
  • Эталонами i-го класса при классификации методом ближайшего соседа может служить такое подмножество объектов этого класса, что расстояние от любого принадлежащего ему объекта из выборки X^l до ближайшего «своего» эталона меньше, чем до ближайшего «чужого» эталона.

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

Величина риска

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

  • При использовании метода ближайшего соседа можно считать W(x_i)=\rho_{in}(x_i)/\rho_{out}(x_i), где \rho_{in} — расстояние от объекта x_i до ближайшего к нему объекта (или эталона) из «своего» класса, \rho_{out} — до ближайшего объекта (или эталона) «чужого» класса.
  • При использовании любого метрического метода можно положить W(x_i)=-M(x_i, \Omega), где M(x_i, \Omega)=\Gamma_{y_i}-\max_{y \in Y \setminus y_i} \Gamma_y (x_i) — отступ на объекте x_i при обучающей выборке \Omega, где \Omega — множество эталонов.

Кроме того, в зависимости от используемого метода классификации можно подобрать и другие оценки величины риска. Главное, чтобы они принимали большие значения на объектах-выбросах, меньшие — на объектах, находящихся на границе класса, и еще меньшие — на объектах, находящихся в глубине своего класса.

Алгоритм STOLP

Вход

  • Выборка X^l
  • Допустимая доля ошибок l_0
  • Порог отсечения выбросов δ
  • Алгоритм классификации
  • Формула для вычисления величины риска W.

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

  • Отбросить выбросы (объекты X^l с W>δ)
  • Сформировать начальное приближение \Omega — из объектов выборки X^l выбрать по одному объекту каждого класса, обладающему среди объектов данного класса максимальной величиной риска[1] либо минимальной величиной риска[1]
  • Наращивание множества эталонов (пока число объектов выборки X^l, распознаваемых неправильно, не станет меньше l_0):
    • Классифицировать объекты X^l, используя в качестве обучающей выборки \Omega
    • Пересчитать величины риска для всех объектов X^l \setminus \Omega с учетом изменения обучающей выборки
    • Среди объектов каждого класса, распознанных неправильно, выбрать объекты с максимальной величиной риска и добавить их к \Omega

Результат

Множество эталонов \Omega \in X^l для каждого класса представляет собой некоторый набор объектов, находящихся на границе класса, и, если в качестве начального приближения выбирались объекты с минимальной величиной риска, один объект, находящийся в центре класса.

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

  • Результат работы алгоритма — разбиение всего множества объектов X^l на эталонные, шумовые (выбросы) и неинформативные объекты.
  • Возможен вариант, при котором в обучающей выборке все объекты, принадлежащие одному из классов, имеют W, большую порога отсечения выбросов. Тогда они окажутся отброшены на первом шаге алгоритма. В таком случае имеет смысл сначала сформировать начальное приближение Ω, а потом отбросить объекты с W, большей δ, кроме объектов, входящих в Ω. Но это возможно только при формировании начального приближения множества эталонов из объектов с наименьшей величиной риска, поскольку иначе в начальное приближение попадет большое количество выбросов.
  • Алгоритм STOLP имеет относительно низкую эффективность (порядка O(l^2)), так как на каждой итерации для присоединения очередного эталона необходимо заново классифицировать все объекты, еще не ставшие эталонами и считать на них величину риска. Для ускорения работы можно добавлять по несколько далеко отстоящих друг от друга эталонов, не пересчитывая величины риска.

Литература


См. также

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

Метод ближайших соседей

Отступ

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


Данная статья является непроверенным учебным заданием.
Студент: Участник:LuarSoll
Преподаватель: Участник:Константин Воронцов
Срок: 31 декабря 2009

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

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


Личные инструменты