5.2. ЛИНЕЙНЫЕ РАЗДЕЛЯЮЩИЕ ФУНКЦИИ И ПОВЕРХНОСТИ РЕШЕНИЙ

5.2.1. СЛУЧАЙ ДВУХ КЛАССОВ

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

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

Уравнение определяет поверхность решений, отделяющую точки, соответствующие решению от точек, соответствующих решению . Когда функция линейна, данная поверхность представляется гиперплоскостью. Если и принадлежат поверхности решений, то справедливо следующее выражение:

или

так что w есть нормаль по отношению к любому вектору, лежащему в гиперплоскости. В общем случае гиперплоскость Н делит пространство признаков на два полупространства: область решений для и область решений для Поскольку если х находится в области то из этого следует, что нормальный вектор w направлен в сторону . В этом случае иногда говорят, что любой вектор х, находящийся в области лежит на положительной стороне гиперплоскости , а любой вектор х, находящийся в области лежит на отрицательной стороне Н.

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

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

если х находится с отрицательной стороны гиперплоскости. Тогда, поскольку

или

В частности, расстояние от начала координат до гиперплоскости выражается отношением Если начало координат находится с положительной стороны ; если — с отрицательной стороны . Если то функция становится однородной и гиперплоскость проходит через начало координат.

Рис. 5.1. Линейная граница областей решений

Геометрическая интерпретация данных результатов приведена на рис. 5.1.

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

5.2.2. СЛУЧАЙ МНОГИХ КЛАССОВ

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

Рис. 5.2. Линейные границы областей решений для задачи трех классов. а — дихотомия б — дихотомия

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

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

или

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

Рис. 5.3. Границ областей решений, полученные с помощью линейной машины. а — задача для трех классов, б — задача для, пяти классов.

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