ПОНЯТИЕ ОКРУЖЕННОГО ЭЛЕМЕНТА И ПРИМЕНЕНИЕ ЭТОГО ПОНЯТИЯ К РЕШЕНИЮ НЕКОТОРЫХ

ЗАДАЧ КЛАССИФИКАЦИИ
ТАТЬЯНА АНДРЕЕВА
Наука вовсе не является коллекцией законов, собранием несвязных

фактов. Она является созданием человеческого разума с его свободно изобретенными идеями и понятиями.
Альберт Эйнштейн

РУКОВОДИТЕЛЬ: А. Е. ЛЕПСКИЙ

разделить их наилучшим образом с точки зрения минимума вероятности неверной

классификации.

«неокруженный» классом А.
Определение. Если максимальный угол между векторами с началом

в точке b и концами в точках класса А, между которыми нет других элементов, меньше либо равен π, то элемент b называется «окруженным» классом А; в противном случае – «неокруженным».

С2 линейно отделимы друг от друга, то каждая точка класса

С1 является «неокруженной» классом С2 точкой.

1. Строим вектора от исследуемой на «окруженность» точки А до всех точек класса В и вектор

2. Находим вектор, для которого угол между ним и вектором минимален

3. Проверяем линейную отделимость точки А от класса В: если вектора имеют правую ориентацию, то точка A линейно отделима от класса В. Тогда по теореме 1 из линейной отделимости следует то, что А – точка, «неокруженная» классом В.

4. Трудоемкость метода

, где - число элементов класса В,

- число элементов, принадлежащих прямой

- количество элементов класса , - количество

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

элементы
Выпуклые оболочки, состоящих из «неокруженных» элементов исходных классов
Разделение выпуклых оболочек
Разделение

непересекающихся классов

положения разделяющей прямой
Наилучшее разделение исходных классов

в области D разделяет исходные классы наилучшим образом с точки

зрения минимума вероятности неверной классификации.

точек классов А и В
2. Вычисляем вероятности неверной

3. Из полученных вероятностей выбираем минимальную.

4. Фиксируем начала тех векторов, для которых вероятность минимальна.

классификации для этих векторов:

Если для всех этих векторов неверно классифицированные элементы одинаковые, то получаем одну область

Строим область , образованную этими элементами

точки, на которых достигается минимум вероятности неверной классификации
3. Выбираем

ту область, для которой ширина коридора максимальна:

4. Искомой будет любая прямая, принадлежащая области

2. Строим области

классификации p= 0,233
Метод параллельного переноса
Метод выделения областей

классификации p= 0,21
Метод параллельного переноса
Метод выделения областей

n-МЕРНОМ ПРОСТРАНСТВЕ
- плотность нормального распределения исходных классов
Даны

два класса и , нормально распределенные, с известными векторами средних и и известными ковариационными матрицами и . Требуется определить положение разделяющей гиперплоскости, ортогональной , так, чтобы ошибка неправильной классификации была наименьшей.

минимум:
где

–

точка в n-мерном пространстве, через которую, перпендикулярно , проходит искомая решающая гиперплоскость .


В частности, когда исходные классы имеют одинаковое распределение, получим следующую решающую гиперплоскость:

алгоритмы наилучшего разделения классов в двумерном и трехмерном пространствах.
Представлены примеры

численной реализации данных алгоритмов, вычислены трудоемкости методов, проведено их сравнение.
Для нормального n-мерного распределения двух классов с известными характеристиками аналитически найдено решение задачи наилучшего разделения гиперплоскостью, перпендикулярной отрезку, соединяющему центры классов.