Линейные решающие функции

Лабораторная работа № 3

Решающие функции

Линейные решающие функции

Геометрически распознаваемые (классифицируемые) объекты выражается в виде точки в n -мерном пространстве. Если имеется только два класса, то при известном распределении их точек, задаваемых в виде n -мерных векторов признаков X = (x ₁, x ₂, …, x_n), то можно попытаться установить границу

g (x ₁, x ₂, …, x_n) = g (X) = 0,

которая делит пространство на две области. Тогда классификация сводится к анализу знака функции g (X): если g (X) > 0, то объект будет к одному классу, иначе – к другому.

В общем случае (классов может быть более двух) при выполнении классификации объектов, представленных в виде n -мерных векторов признаков, обычно предполагают, что объекты каждого класса группируются в некоторой области пространства признаков и существуют гиперповерхности, «окаймляющие» эти области. Тогда для классификации объектов можно применять процедуру, состоящую из двух этапов: оптимизации положения гиперповерхностей и оценки положения анализируемого объекта по отношению к гиперповерхностям. На первом этапе следует выработать некоторые разделяющие функции, а на втором – сопоставить конкретное значение функции с вектором признаков, представляющих объект.

Разделяющими функциями называют функции g ₁(X), g ₂(X), …, g_N (X), которые обуславливают принятие решения, обеспечивающего выполнение следующего условия:

w(X) = w _i «g_i (X) ³ g_j (X) " j = 1, 2, …, N,

где w(X) – класс объекта X, w _i – i -ый класс, i = 1, …, N.

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

Линейные разделяющие функции имеют вид

g (X) = g (x ₁, x ₂, …, x_n) = w ₀ + w ₁ x ₁ + w ₂ x ₂ + … + w_nx_n,

где W = (w ₀, w ₁, …, w_n) ^T – вектор весовых коэффициентов, X = (x ₁, x ₂, …, x_n) ^T – вектор признаков. Иногда в вектор X вводят дополнительный признак x ₀ = 1 и линейную разделяющую функцию определяют в виде суммы

.

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

Рассмотрим для примера случай двух классов w₁ и w₂. Имеем две линейные разделяющие функции и . Решающее правило для выполнения классификации можно представить в виде

Это равносильно правилу

Таким образом, разделяющая поверхность описывается уравнением g (X) = g ₁(X) – g ₂(X) = 0. Запишем решающее правило с использованием функции g (X) в следующей форме:

Очевидно, что уравнение разделяющей поверхности будет также иметь линейный вид. Действительно:

где .

Определим функцию знака sign(z):

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

.

Действительно: