Метод дробящихся эталонов

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

Версия от 06:49, 9 июля 2026; Dan-Кhaiaa Lakpazhap (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Статья написана с использованием LLM DeepSeek-V4 и проверена участником Участник:Dan-Кhaiaa Lakpazhap 18:29, 30 июня 2026 (MSD).

Промпт приводится полностью в Обсуждение:Метод дробящихся элементов.

Метод дробящихся эталонов (англ. method of splitting standards) — детерминированный метод распознавания образов, относящийся к группе метрических классификаторов. В основе метода лежит иерархическое построение систем гиперсфер, каждая из которых охватывает объекты одного класса в признаковом пространстве. В случае пересечения гиперсфер разных классов процедура рекурсивно повторяется для областей пересечения, что позволяет строить решающее правило без явного вычисления разделяющих поверхностей^[1].

Содержание

1 История
2 Математическое описание
- 2.1 Иерархическое дробление
3 Алгоритм
- 3.1 Обучение
- 3.2 Распознавание
4 Свойства
5 Связь с другими методами машинного обучения
6 Критика и ограничения
7 Современные разработки
8 См. также
9 Примечания
10 Литература

История

Метод дробящихся эталонов относится к классическим детерминистским подходам в распознавании образов, получившим развитие в 1960–1970-х годах. В этот период активно разрабатывались методы, не требующие задания априорных вероятностей и функций потерь, что выгодно отличало их от статистических подходов^[1]. Метод дробящихся эталонов представляет собой развитие метода построения эталонов: если последний ограничивается одной гиперсферой на класс, то дробящийся вариант позволяет строить многоуровневую систему гиперсфер, адаптирующуюся к сложной геометрии данных^[1].

В русскоязычной литературе метод описывается в учебных курсах по распознаванию образов как один из базовых детерминистских алгоритмов наряду с методом ближайших соседей и методом потенциальных функций^[1].

Математическое описание

Пусть задано обучающее множество $X = \{(x_i, y_i)\}_{i=1}^N$ , где $x_i \in \mathbb{R}^d$ — признаки объекта, $y_i \in \{1, \dots, K\}$ — метка класса. Для каждого класса $k$ строится эталон $e_k$ — некоторая точка в признаковом пространстве, представляющая данный класс. В простейшем случае в качестве эталона берётся центроид (среднее арифметическое) всех объектов класса:

$e_k = \frac{1}{N_k} \sum_{i: y_i = k} x_i$ , где $N_k$ — число объектов класса $k$ ^[1].

Затем для каждого класса вычисляется радиус охвата $R_k$ — максимальное расстояние от эталона до объектов данного класса:

$R_k = \max_{i: y_i = k} \rho(x_i, e_k)$ , где $\rho(\cdot, \cdot)$ — выбранная метрика (как правило, евклидово расстояние).

Гиперсфера $S_k = \{x \in \mathbb{R}^d : \rho(x, e_k) \le R_k\}$ охватывает все объекты класса $k$ ^[1].

Иерархическое дробление

Если гиперсферы различных классов пересекаются, то для области пересечения $P = S_a \cap S_b$ процедура повторяется: строятся новые эталоны и гиперсферы меньшего радиуса, охватывающие объекты разных классов, попавшие в $P$ . Этот процесс продолжается до тех пор, пока на некотором уровне не будет достигнуто одно из условий:

все гиперсферы одного уровня попарно не пересекаются;
в каждой области пересечения присутствуют объекты только одного класса.

В результате строится дерево (точнее, лес) гиперсфер, где каждый уровень соответствует определённому масштабу рассмотрения признакового пространства^[1].

Алгоритм

Обучение

Для каждого класса $k$ вычислить эталон $e_k$ и радиус $R_k$ .
Построить гиперсферы первого уровня $S_k^{(1)}$ .
Для каждой пары пересекающихся гиперсфер разных классов выделить область пересечения и перейти к шагу 1 для объектов, попавших в эту область (построение гиперсфер следующего уровня).
Процесс повторяется до выполнения критерия остановки.

Распознавание

Для нового объекта $x$ :

Проверить принадлежность гиперсферам первого уровня.
- Если объект попал только в одну гиперсферу, отнести его к соответствующему классу.
- Если объект не попал ни в одну гиперсферу — принять специальное решение (отказ от классификации или использование резервного правила, например правила ближайшего соседа).
- Если объект попал в область пересечения гиперсфер разных классов — перейти к гиперсферам следующего уровня, соответствующим этой области.
Процесс продолжается до однозначного отнесения объекта к классу либо до исчерпания уровней^[1].

Свойства

Детерминированность: метод не использует вероятностные предположения о распределении данных, что делает его применимым в условиях малой априорной информации^[1].
Иерархичность: многоуровневая структура позволяет адаптироваться к данным со сложной геометрией классов, включая нелинейно разделимые множества.
Вычислительная сложность: на этапе обучения требуется $O(K \cdot N \cdot d)$ операций для вычисления эталонов и радиусов; на этапе распознавания — $O(L \cdot d)$ , где $L$ — число уровней, задействованных при классификации конкретного объекта.
Память: требуется хранить эталоны и радиусы для всех уровней, что, как правило, существенно меньше объёма хранения всей обучающей выборки (в отличие от метода ближайших соседей)^[1].
Эвристический характер: метод не гарантирует оптимальности построенного решающего правила, и его эффективность сильно зависит от выбора метрики, способа вычисления эталонов и критерия остановки^[1].

Связь с другими методами машинного обучения

Метод дробящихся эталонов занимает промежуточное положение между:

Метод построения эталонов — одноуровневый предшественник, использующий одну гиперсферу на класс;
Метод ближайших соседей — метод, хранящий всю обучающую выборку; комбинация двух методов позволяет сократить объём хранимых данных, запоминая только объекты, попавшие в зоны пересечения гиперсфер^[1];
Деревья решений — также используют иерархическое разбиение пространства, но, в отличие от дробящихся эталонов, строят оси-ортогональные (или более общие) разделяющие поверхности, а не гиперсферы;
Метод опорных векторов (англ. Support Vector Machine, SVM) — строит оптимальные разделяющие гиперплоскости, в то время как дробящиеся эталоны используют гиперсферы и не требуют решения задачи оптимизации;
Метод потенциальных функций — также является детерминистским и неметрическим подходом, но строит потенциальные функции в каждой точке обучающей выборки.

В современном машинном обучении идеи иерархического разбиения пространства и использования эталонов находят применение в:

кластеризации — методы, подобные k-средних, используют центры кластеров как эталоны;
обработке естественного языка — при построении векторных представлений слов (word2vec, GloVe) центры кластеров могут интерпретироваться как семантические эталоны;
сжатии данных и поиске ближайших соседей — иерархические структуры, такие как VP-дерево и шаровое дерево, используют идею рекурсивного разбиения пространства гиперсферами для ускорения запросов^[1].

Критика и ограничения

Основные недостатки метода дробящихся эталонов:

Эвристичность: отсутствие теоретических гарантий качества классификации; метод не минимизирует явно заданный функционал качества.
Чувствительность к выбросам: эталон, вычисленный как среднее арифметическое, может быть смещён при наличии выбросов.
Зависимость от метрики: выбор метрики существенно влияет на форму гиперсфер и, следовательно, на результат.
Проблема остановки: не существует универсального критерия, гарантирующего конечность процесса дробления для произвольных данных.
Масштабируемость: при большом числе классов и высокой размерности признакового пространства число уровней и гиперсфер может стать неприемлемо большим.

В литературе отмечается, что метод дробящихся эталонов носит «в основном эмпирический характер» и его практическая ценность заключается скорее в педагогической иллюстрации идей иерархической классификации, нежели в промышленном применении^[1].

Современные разработки

Несмотря на свою простоту, идеи метода дробящихся эталонов находят отражение в современных подходах:

Глубокие метрические нейронные сети (англ. deep metric learning) используют эталонные представления (прототипы) классов и обучают вложения, в которых объекты одного класса собираются вокруг своих прототипов^[1].
Прототипные сети (англ. Prototypical Networks) для обучения с немногими примерами (англ. few-shot learning) вычисляют центроиды классов в пространстве вложений и классифицируют новые объекты по расстоянию до ближайшего центроида^[1] — что представляет собой прямое обобщение метода построения эталонов на случай нейросетевых представлений.
Иерархическая кластеризация и построение дендрограмм используют рекурсивное разбиение множества объектов, аналогичное дроблению областей пересечения.
Метод опорных гиперсфер (англ. Support Vector Data Description, SVDD) строит гиперсферу минимального радиуса, охватывающую объекты одного класса, что является оптимизационной версией идеи эталонной гиперсферы^[1].

См. также

Примечания

Литература

Вапник В. Н., Червоненкис А. Я. Теория распознавания образов. — М.: Наука, 1974. — 415 с.
Волошин Г. Я. Методы распознавания образов. — М.: МГУП, 2010. — 120 с.
Дуда Р., Харт П. Распознавание образов и анализ сцен. — М.: Мир, 1973. — 512 с.
Фу К. Структурные методы в распознавании образов. — М.: Мир, 1977. — 320 с.
Snell J., Swersky K., Zemel R. Prototypical Networks for Few-shot Learning // Advances in Neural Information Processing Systems. — 2017. — Т. 30. — С. 4077–4087.
Tax D. M. J., Duin R. P. W. Support Vector Data Description // Machine Learning. — 2004. — Т. 54. — № 1. — С. 45–66.
Omohundro S. M. Five Balltree Construction Algorithms // International Computer Science Institute Technical Report. — 1989. — Т. TR-89-063.

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B4%D1%80%D0%BE%D0%B1%D1%8F%D1%89%D0%B8%D1%85%D1%81%D1%8F_%D1%8D%D1%82%D0%B0%D0%BB%D0%BE%D0%BD%D0%BE%D0%B2»