Дискриминантные информанты и классификация

     Пусть в k -мерном вещественном пространстве R^k действуют независимо друг от друга два случайных механизма. Первый выдает случайные векторы X, подчиняющиеся закону распределения с плотностью f ₁(x), второй - f ₂(x). Класс векторов Х, выданных первым механизмом, обозначим W₁, вторым - W₂. Пусть также известны априорные вероятности срабатывания каждого из этих механизмов p ₁ и p ₂, p ₁+ p ₂=1. Для данного вектора X требуется принять решение, к какому классу он принадлежит, W₁ или W₂. Решающее правило состоит в разбиении пространства R^k на две области W ₁ и W ₂ так, что если X Î W_i, то принимается решение   X ÎW _i.  

    Рассмотрим сначала одномерный случай, k =1 (рис.7.1). Решающее правило имеет вид:  Границей между ними является значение x = T *.

   Если то вероятность ошибки r ₁ = 1- F ₁(T *); если  то вероятность ошибки r ₂ = F ₂(T *). Учитывая априорные вероятности p ₁ и p ₂, получаем, что границу T * нужно определять из условия минимума байесовского риска

 

Вычислим производную по T * от обеих частей последнего выражения и приравняем ее нулю:

- p ₁ f ₁(T *) + p ₂ f ₂(T *) = 0.

                        

Рис.7.1. Одномерный случай

Это значит, что правило, минимизирующее вероятность ошибочного распознавания, должно быть основано на выражении d_i = p_i f_i (x):

В случае произвольной размерности k выражение

d _i (X) = p_i f_i (X)                                                        (7.1)

называют дискриминантным информантом вектора Х для класса W _i. При этом байесово классификационное правило  имеет вид: Х принадлежит тому из классов W _i, для которого его дискриминантный информант максимален.

    Величина r_i  представляет ожидаемую долю ошибочных распознаваний для объектов класса W _i  , а r - для объектов всех классов. Данное правило минимизирует математическое ожидание числа ошибочных распознаваний. Можно строить решающие правила на основе других принципов, например, минимизируя максимальную компоненту вектора средних потерь { r _i }. Каждое из таких правил совпадает с некоторым байесовым правилом при соответствующем выборе p_i. Приведенную конструкцию можно усложнять, рассматривая величины l_ij, i, j = 1, 2 - потери от отнесения вектора X ÎW _i    к классу W _j.

   Выражение (7.1) для дискриминантного информанта можно упрощать, подвергая монотонным преобразованиям и отбрасывая члены, не зависящие от i. Если классы задаются k -мерными нормальными распределениями N_k (a_i ,å _i),то, логарифмируя равенство (10.1) и отбрасывая члены, не зависящие от i, получим

                            (7.2)

Граница областей W ₁  и W ₂ оказывается при этом поверхностью второго порядка в R^k.  

  Пример 7.1. Построение разделяющей кривой в двумерном пространстве. Пусть 

p ₁ = p ₂ = 0.5;   X = (x, y) ^T,

Прежде всего, необходимо вычислить значения дискриминантных информантов (общее слагаемое ln(0.5) отбрасываем):

Уравнение разделяющей кривой d ₁(X) = d ₂(X) приводится к виду 

ln(2) + (x+ 3)² + 0.5 y ² = ln(0.75) + 4 / 3(x- 3)² – 4/3(x- 3) y + 4/3 y ²

или, в эквивалентной форме,

        2 x ²  - 8 xy + 5 y ² – 84 x + 24 y = -12.12.                               (7.3)

Уравнение (13.3) описывает кривую второго порядка на плоскости. Выделяя в нем полные квадраты, приводим его к виду

                        (7.4)

Для приведения этого уравнения к каноническому виду рассмотрим квадратичную форму

Ее собственные числа l₁, l₂ определяются из уравнения

Нормированные собственные векторы этой квадратичной формы

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

                                    x = -0.82 x ₁–0.57 y ₁;   y = -0.57 x ₁+0.82 y ₁.

Отсюда получаем уравнение разделяющей кривой в новых переменных x ₁, y ₁ в каноническом виде:

В данном случае разделяющая кривая представляет собой гиперболу, график которой приведен на рис. 13.2 а),б).При попадании точки Х в выделенную заливкой область W ₂ принимается гипотеза Х ÎW₂. Левая половина области W ₂ на рис.13.2 а), очевидно, относится к чрезвычайно мало вероятным значениям X и физического смысла не имеет, но при некритическом подходе может оказаться источником грубых ошибок. 

    Если å₁ = å₂ = å, то разделяющая поверхность представляет собой гиперплоскость, в двумерном случае - прямую. Если при этом р ₁ = р ₂, то решающее правило удобно интерпретировать с помощью расстояния Махаланобиса D (X, a_i ). Правило распознавания в этом случае называют методом ближайшего соседа: Х относится к тому из классов W _i, центр которого а_i   оказывается ближе.

     Приведенные рассуждения легко обобщить на случай произвольного числа классов.

Рис. 7.2. Разделяющая кривая в примере 7.1

   Пример 7.2. Построение разделяющих прямых в двумерном пространстве для трех классов. Пусть p ₁ = p ₂ = p ₃ = 1/3; X = (x, y) ^T , å₁ = å₂ = å₃ =å;

В этом случае квадраты расстояний Махаланобиса выражаются формулами:

                    D_M ²(X, a ₁) = 4/7[(x+ 3)² + (x+ 3) y + 2 y ²];                  

                    D_M ² (X, a₂) = 4/7[(x- 3)² + (x- 3) y + 2 y ²];

                    D_M ² (X, a ₃) = 4/7 [ x² + x (y- 4)+ 2(y- 4)²].

Приравнивая эти выражения попарно, получаем три разделяющие прямые:

                    D_M ² (X, a ₁) = D_M ²(X, a ₂): 2 x + y = 0;

                    D_M ² (X, a ₁) = D_M ²(X, a ₃): 10 x + 19 y – 23 = 0;

                   D_M ² (X, a ₂) = D_M ² (X, a ₃): 2 x - 13 y + 23 = 0.

Соответствующие зоны   W ₁, W ₂, W ₃  показаны на рис. 7.3.

   В общем k - мерном случае если ковариационные матрицы классов совпадают, то при отбрасывании в (13.2) членов, не зависящих от i, выражение для дискриминантного информанта получается в виде линейной функции от Х:

           d_i (X) = ln p_i + a _i^T å ^-1 X – 0.5 a _i^T å^-1 a_i.                         (7. 4)

Рис. 7.3. Разделяющие прямые в примере 7.2

   Вообще, для любых плотностей вида

f (x) = C j [(x - b) ^T S (x - b)], x Î R^k,

где С - нормирующая константа; b - постоянный вектор; S - симметричная матрица, границы зон состоят из  кусков плоскостей и поверхностей второго порядка в R.

   Если плотности f ₁(x) и f ₂(x) не заданы, их приходится оценивать по обучающим выборкам, описывающим классы Ω₁ и Ω₂. В гауссовом случае достаточно получить выборочные оценки средних и ковариационных матриц этих обучающих выборок. В других случаях используют непараметрические сглаженные оценки плотностей f ₁(x) и f ₂(x), которые строятся по этим обучающим выборкам, причем результаты могут значительно отличаться в зависимости от использованной процедуры сглаживания.