Практическая работа №2
«Методы распознавания образов, основанные на построении разделяющей гиперплоскости и гиперсферы»

Тема 4 «Системы распознавания образов»

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

Теоия:
Построение разделяющей гиперплоскости используется для определения принадлежности объекта к тому или иному классу образов. Рассмотрим этапы построения разделяющей гиперплоскости.

Рисунок 1. Построение разделяющей гиперплоскости.
На рисунке 1 схематически изображен процесс построения разделяющей гиперплоскости. Нам известны координаты двух точек(объектов): A,B. Которые представлены на рисунке в виде звездочки (точка А), и в виде кружочка (точка В). Необходимо построить разделяющую гиперплоскость, которая отделяла бы образы «похожие» на А, от образов «похожих» на В.
Для построения, нам необходимо провести между точками А и В, соединяющую их линию. На середине этой линии отложим точку Р, через которую будет проходить разделяющая гиперплоскость. Теперь, зная координаты точки Р, а также имея вектор АВ, построить плоскость, проходящую через точку Р, и перпендикулярную вектору АВ. Теперь чтобы принять решение о принадлежности образа к тому или иному классу, нужно определить расстояние от этого образа до гиперплоскости, кроме того, знак полученного расстояния будет говорить о положении образа с одной или другой стороны от гиперплоскости.
Разделяющая гиперплоскость не может быть построена без базисных  точек. В качестве базисных точек могут быть выбраны:
-   наугад взятые точки , по одной из множества А и множества В;
-   точки, выбранные из А и В с учетом определенных обстоятельств (например, имеющие минимальные расстояния между собой);
-   точки, выбранные на основании каких-либо статистических характеристик.
Пусть нам даны множества А и В, каждое из которых состоит из 5 элементов (рисунок 2):

Рисунок 2.  Разделение классов А и В гиперплоскостью
В качестве базисных точек выберем точки, координаты которых являются средними арифметическими значениями соответствующие координат точек каждого класса.
В качестве разделяющей классы А и В гиперплоскости выберем следующую плоскость:
R(х,у) = 2(Асред- Всред)*Р+| Bсред |2-|Aсред|2 = 0, это векторное уравнение.
Отметим, что все расстояния точек Ai от гиперплоскости отрицательны:
Все расстояния точек Вi от разделяющей гиперплоскости положительны
Следовательно, R(x,y) разделяет множества А и В и если добавить новый элемент в В, то такое расстояние будет положительно.
Метод гиперсфера аналогичен методу построения гиперплоскости, только разделение заключается в следующем: точки которые попадают внутрь гиперсферы относятся к одному классу, а за ее пределы – ко второму.
Гиперсфера описывается следующей формулой:
, где (О1, О2, …,Оn) – координаты центра сферы, R – радиус гиперсферы, (Х1, Х2, …,Хn) – координаты точки.
Для определения, куда попала точка с координатами  (Х1, Х2, …,Хn) в сферу или за ее пределы,  преобразуем формулу к следующему виду:

Если в результате вычисления формулы получается отрицательное значение, то точка попадает в сферу, если равно нулю – на границу сферы, иначе – за ее пределы.

Задание:

Входные данные:

• Задается мерность пространства – N (максимальное значение 5).
• Файл с координатами точек и их номерами (максимальное число точек - 10).

Разработать программное средство, реализующее следующие функции:

• считать номера и координаты точек из файла
• возможность выбора метода распознавания: гиперплоскость или гиперсфера.

Для гиперплоскости:

• выбрать две базовые точки. Предусмотреть следующие варианты выбора: случайным образом, должны задаваться пользователем и выбрать две точки с наименьшим расстоянием между собой из всех возможных вариантов (нужно рассмотреть все возможные пары точек и определить расстояние между ними по формуле );
• разбить точки на два класса;
• вывести на экран или в файл: номера точек и в какой класс они попали;

Для гиперсферы:

• выбрать центр гиперсферы. Предусмотреть следующие варианты: случайном образом из множества точек или задается номер точки пользователем
• радиус сферы должен вычисляться двумя способами: задается пользователем или вычисляется следующим образом:
• находим расстояния Ri между центром гиперсферы и с каждой из оставшихся точек по формуле , где (О1, О2, …,Оn) – координаты центра сферы, а (Х1, Х2, …,Хn) – координаты точки.
• находим среднее расстояние , где n – общее количество точек. Это среднее расстояние и будет радиусом.
• Строим гиперсферу и производим разделение всех точек на два класса.
• Вывести на экран или в файл: номера точек и в какой класс попали.

Примечание
Точки обязательно нумеровать цифрами или буквами.

Отчет
Подготовить отчет, который должен включать в себя:

• отмеченные на координатной плоскости точки примера 1 с нумерацией;
• ручной просчет для примера 1;
• результат, который выдает написанная вами программа для примера 1;

Ручной просчет – это описание решения деления на классы множества точек методом гиперплоскости и гиперсферы.
Пример 1 рассматривает точки в двухмерном пространстве.
Этапы составления отчета:

• Для примера 1 нарисовать на координатной плоскости 6 точек, любые две точки из них выбрать в качестве базовых, выделить их на плоскости.
• Нарисовать на координатной плоскости гиперплоскость. Записать уравнение гиперплоскости. 
• Описать ручной просчет для метода гиперплоскость относительно выделенных базовых точек.
• Отметить на координатной плоскости, в какой класс попали оставшиеся четыре точки.
• Снова нарисовать на координатной плоскости те же 6 точек, выбрать одну из них в качестве центра гиперсферы и рассчитать радиус гиперсферы.
• Нарисовать гиперсферу на плоскости и записать ее уравнение.
• Описать ручной просчет для метода гиперсфера относительно заданного центра и рассчитанного радиуса.
• Отметить на координатной плоскости, в какой класс попали оставшиеся пять точек.
• Привести результат работы программы относительно примера 1 по двум методам  (можно вставить скриншоты).