Линейный дискриминантный анализ (с примерами)

Линейный дискриминантный анализ (ЛДА, англ. Linear Discriminant AnalysisLDA), нормальный дискриминантный анализ (англ. Normal Discriminant Analysis, NDA) или анализ дискриминантных функций (англ. Discriminant Function Analysis) является обобщением линейного дискриминанта Фишера, метода, используемого в статистике, распознавании образов и обучении машин для поиска линейной комбинации признаков, которая описывает или разделяет два или более классов или событий.

Построение решающих функций для распознавания двух классов объектов  w1 и w2 по некоторому описанию X = (x1, x2…..xL)

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

Для двухклассовой задачи линейная дискриминантная функция (ЛДФ), являющаяся разделяющей гиперплоскостью, имеет вид

D(X) = WTX-a = 0 или WTX = a,      (1.10)

где W = (w1, w2, …,wL) — весовой вектор единичной длины; а — скалярная пороговая величина.

Алгоритм распознавания, позволяющий отнести неизвестный объект X к одной из групп, в этом случае имеет следующий вид:

если WTX < а, то w1 (1-й класс),

если WTX ≥ а, то w2 (2-й класс).

На рис. 1 изображены данная ЛДФ и соответствующий ей алгоритм распознавания.

Определение проекций объектов двухклассов на прямую, продолжающую вектор W
Определение проекций объектов двухклассов на прямую, продолжающую вектор W

Для того чтобы определить составляющие вектора W и порог а, можно воспользоваться критерием минимизации ошибки классификации. Однако для этого потребуется довольно сложная итеративная  процедура поиска параметров решающего правила. Эту задачу можно решить, применяя другой критерий оптимизации — критерий Фишера. Он позволяет найти такой вектор W, при котором проекции точек классов на выбранное направление разделяются наилучшим образом. Порог а определяется исходя из критерия оптимальности разбиения объектов на два класса. В этом случае алгоритм поиска неизвестных параметров W и а можно представить следующим образом:

  1. найти W, используя критерий Фишера;
  2. спроецировать точки обоих классов на прямую, определяемую положением W;
  3. решить одномерную задачу по поиску наилучшей величины а, например, по критерию минимума ошибок классификации.

Если допустить, что оба класса распределены по нормальному закону с одинаковыми ковариационными матрицами Σ1 = Σ2 = Σ, то из теории известно, что решение 1-го шага вышеприведенного алгоритма определяется выражением

W = Σ-1(M12),               (1.11)

где M1 и М2 — векторы средних значений двух классов. В случае Σ1 ≠ Σ2  в качестве Σ можно использовать усредненную ковариационную матрицу в виде

Σ=½(Σ1 + Σ2).               (1.12)

Так как после вычисления W по формуле (1.11) его надо пронормировать для получения вектора единичной длины, т.е. разделить на |W|, то коэффициент ½ в (1.12) можно отбросить. Тогда Σ=Σ1 + Σ2.

Оценки M1, М2 и Σ1, Σ2 определяются выражениями

M_{1}=\frac{1}{n_{1}} \sum_{i=1}^{n_{1}} \mathbf{X}_{i}^{(1)}

M_{2}=\frac{1}{n_{2}} \sum_{i=1}^{n_{2}} \mathbf{X}_{i}^{(2)}

\boldsymbol{\Sigma}_{j}=\frac{1}{n_{j}-1} \sum_{i=1}^{n_{j}}\left(\mathbf{X}_{i}^{(j)}-\mathbf{M}_{j}\right)\left(\mathbf{X}_{i}^{(j)}-\mathbf{M}_{j}\right)^{T} j =1,2,

где Xi(1) — i-й объект из 1-го класса; Xi(2)i-й объект из 2-го класса; n1 — число объектов 1-го класса; n2  — число объектов 2-го класса.

Если спроецировать точки объектов каждого класса на направление W, то каждый вектор X превратится в соответствующий скаляр у:

y1(1) = WTX1(1),    y2(1) = WTX2(1) и т. д. (рис.).

Тогда средние значения для выборок спроектированных точек равны

m_{1}=\frac{1}{n_{1}} \sum_{i=1}^{n_{1}} y_{i}^{(1)}=\frac{1}{n_{1}} \sum_{i=1}^{n_{1}} \mathbf{W}^{T} \mathbf{X}_{i}^{(1)}=\mathbf{W}^{T} \frac{1}{n_{1}} \sum_{i=1}^{n_{1}} \mathbf{X}_{i}^{(1)}=\mathbf{W}^{\mathrm{T}} \mathbf{M}_{1}

m_{2}=\frac{1}{n_{2}} \sum_{i=1}^{n_{2}} y_{i}^{(2)}=\frac{1}{n_{2}} \sum_{i=1}^{n_{2}} \mathbf{W}^{T} \mathbf{X}_{i}^{(2)}=\mathbf{W}^{T} \frac{1}{n_{2}} \sum_{i=1}^{n_{2}} \mathbf{X}_{i}^{(2)}=\mathbf{W}^{\mathrm{T}} \mathbf{M}_{2}

Очевидно, что расстояние между m1 и m2 будет отражать удаленность классов друг от друга после их проецирования на W. Это расстояние, оценивающее межклассовый разброс, задается выражением

(m1m2)2 = (WTM1 – WTM2)2 = WT(M1 – М2)(M1 – M2)TW = WTSBW, (1.13)

где SB = (M1 – М2)(M1 – M2)T — матрица разброса между классами. Также можно определить выборочный разброс для двух классов s12 и s22 в виде

s_{1}^{2}=\sum_{i=1}^{n_{1}}\left(y_{i}^{(1)}-m_{1}\right)^{2}=\sum_{i=1}^{n_{1}}\left(\mathbf{W}^{\mathrm{T}} \mathbf{X}_{i}^{(1)}-\mathbf{W}^{\mathrm{T}} \mathbf{M}_{1}\right)^{2}

s_{2}^{2}=\sum_{i=1}^{n_{2}}\left(y_{i}^{(2)}-m_{2}\right)^{2}=\sum_{i=1}^{n_{2}}\left(\mathbf{W}^{\mathrm{T}} \mathbf{X}_{i}^{(2)}-\mathbf{W}^{\mathrm{T}} \mathbf{M}_{2}\right)^{2}

Этот показатель, как и дисперсия, является оценкой внутриклассового рассеяния — чем он больше, тем и рассеяние данных больше. По s12 и s22 можно определить «средний» внутриклассовый разброс в виде s12 + s22

Для определения s12 и s22 через статистические параметры выборок классов определим матрицу разброса Sj для j-ro класса (аналог корреляционной матрицы) в виде

S_{j}=\sum_{i=1}^{n_{j}}\left(\mathbf{X}_{i}^{(j)}-\mathbf{M}_{j}\right)\left(\mathbf{X}_{i}^{(j)}-\mathbf{M}_{j}\right)^{T}

и «усредненную» матрицу разброса для двух классов в виде Sw = S1 + S2.

Тогда

\begin{aligned} s_{j}^{2}=& \sum_{i=1}^{n_{j}}\left(\mathbf{W}^{\mathrm{T}} \mathbf{X}_{i}^{(j)}-\mathbf{W}^{T} \mathbf{M}_{j}\right)^{2}=\sum_{i=1}^{n_{j}} \mathbf{W}^{\mathrm{T}}\left(\mathbf{X}_{i}^{(j)}-\mathbf{M}_{j}\right)\left(\mathbf{X}_{i}^{(j)}-\mathbf{M}_{j}\right)^{\mathrm{T}} \mathbf{W}=\\ &=\mathbf{W}^{T}\left[\sum_{i=1}^{n_{j}}\left(\mathbf{X}_{i}^{(j)}-\mathbf{M}_{j}\right)\left(\mathbf{X}_{i}^{(j)}-\mathbf{M}_{j}\right)^{\mathrm{T}}\right] \mathbf{W}=\mathbf{W}^{T} \mathbf{S}_{j} \mathbf{W}, \quad j=1,2 \end{aligned}

s12 + s22 = WTS1W + WTS2W = WT(S1 + S2)W = WTSWW. (1.14)

Теперь можно определить линейный дискриминант Фишера — линейную функцию с максимальным отношением разброса между классами к «среднему» разбросу внутри классов. Тогда ЛДФ Фишера определяется как такой вектор W, для которого критерий

J(\mathbf{W})=\frac{\left(m_{1}-m_{2}\right)^{2}}{s_{1}^{2}+s_{2}^{2}}

максимален. Для W, найденного по данному критерию, классы, спроецированные на направление W, максимально удалены друг от друга.

С учетом выражений (1.13) и (1.14) вышеприведенный критерий записывается как

J(\mathbf{W})=\frac{\mathbf{W}^{T} \mathbf{S}_{B} \mathbf{W}}{\mathbf{W}^{T} \mathbf{S}_{W} \mathbf{W}}

Анализ этой формулы3 показывает, что максимум J(W) достигается при

W = SW-1(M1 – М2), (1.15)

что почти совпадает с выражением (1.11) для нормальных классов с равными ковариационными матрицами.

Преобразование признакового пространства на основе линейного дискриминанта Фишера

Можно улучшить качество классификации в методе линейного дискриминанта Фишера, если для распознавания применять нс один, а большее число признаков, найденных, как ортогональные весовые векторы в пространствах меньшей размерности с помощью критерия Фишера. В работе4 выведена формула для рекуррентного вычисления дополнительных ортогональных весовых векторов. Для исходного n-мсрного признакового пространства формулу (1.15) можно переписать в виде

Wn = Sn-1(m1n-m2n)              (1.16)

Спроектируем все данные на плоскость перпендикулярную W,,. Тогда на этой плоскости, которая является (п – 1)-мерным признаковым пространством, можно найти наилучший весовой вектор, используя критерий Фишера. Очевидно, что на этой плоскости мы имеем:

Wn-1 = Sn-1-1(m1n-1-m2n-1)  (1.17)

где

m1n-11= m1n – m1nWn = mln – WnTm1nWn,

m2n-11 = m2n – m2nWn = m2n – WnTm2nWn,

m1n-11 – m2n-11 = m1n – m2n – WnT(m1n – m2n)Wn.   (1.18)

При вычислении      обращаемая матрица может оказаться вы

рожденной. В этом случае вместо вычисления явной обратной матрицы можно вычислять пссвдообратную матрицу.

Sn-1 =S1n-1 +S2n-1,                         (1.19)

\mathbf{S} \mathbf{1}_{n-\mathbf{I}}=\sum_{x \in \omega_{1}}\left(\mathbf{X}_{n-1}-\mathbf{m} \mathbf{1}_{n-1}\right)\left(\mathbf{X}_{n-1}-\mathbf{m} \mathbf{1}_{n-1}\right)^{\mathrm{T}},

где

Xn-1 – m1n-1 = (Xn – WnTXnWn) – (m1n – WnTm1nWn) = (Xn-m1n) -WnT(Xn-m1n)Wn,

\mathbf{S} \mathbf{1}_{n-1}=\sum_{x \in \mathbb{w}_{1}}\left[\left(\mathbf{X}_{n}-\mathbf{m} \mathbf{1}_{n}\right)-\mathbf{W}_{n}^{\mathrm{T}}\left(\mathbf{X}_{n}-\mathbf{m} \mathbf{l}_{n}\right) \mathbf{W}_{n}\right]\left[\left(\mathbf{X}_{n}-\mathbf{m} \mathbf{l}_{n}\right)-\right.
\left.-\mathbf{W}_{n}^{T}\left(\mathbf{X}_{n}-\mathbf{m} \mathbf{l}_{n}\right) \mathbf{W}_{n}\right]^{\mathrm{T}}=\sum_{x \in \omega_{1} }\left[\left(\mathbf{X}_{n}-\mathbf{m} \mathbf{l}_{n}\right)\left(\mathbf{X}_{n}-\mathbf{m} \mathbf{l}_{n}\right)^{\mathrm{T}}-\right.
-\mathbf{W}_{n}^{\mathrm{T}}\left(\mathbf{X}_{n}-\mathbf{m} \mathbf{l}_{n}\right) \mathbf{W}_{n}\left(\mathbf{X}_{n}-\mathbf{m} \mathbf{l}_{n}\right)^{\mathrm{T}}-
\left.-\left(\mathbf{X}_{n}-\mathbf{m} \mathbf{l}_{n}\right) \mathbf{W}_{n}^{\mathrm{T}}\left(\mathbf{X}_{n}-\mathbf{m} \mathbf{l}_{n}\right) \mathbf{W}_{n}^{\mathrm{T}}+B\right]

В = WnT(Xn-m1n)Wn * |WnT(Xn-m1n)Wn|T.

Обозначим α = WnT(Xn-m1n). Это скаляр. Отметим, что также α = (Xn-m1n)TWn. Тогда В = αWnαWnT и

\mathbf{S} \mathbf{1}_{n-1}=\sum_{x \in \omega_{1}}\left[\left(\mathbf{X}_{n}-\mathbf{m} \mathbf{l}_{n}\right)\left(\mathbf{X}_{n}-\mathbf{m} \mathbf{l}_{n}\right)^{\mathbf{T}}-\right.
\left.-\alpha \mathbf{W}_{n}\left(\mathbf{X}_{n}-\mathbf{m} \mathbf{l}_{n}\right)^{\mathbf{T}}-\alpha\left(\mathbf{X}_{n}-\mathbf{m} \mathbf{l}_{n}\right) \mathbf{W}_{n}^{\mathbf{T}}+B\right]. (1.20)

Так как

\sum_{x \in \omega_{1}}\left|-\alpha \mathbf{W}_{n}\left(\mathbf{X}_{n}-\mathbf{m} \mathbf{l}_{n}\right)^{\mathbf{T}}-\alpha\left(\mathbf{X}_{n}-\mathbf{m} \mathbf{l}_{n}\right) \mathbf{W}_{n}^{\mathrm{T}}\right|=
\quad=\sum_{x \in \mathbb{\omega}_{1}}\left[\left(\alpha \mathbf{W}_{n} \mathbf{m} \mathbf{l}_{n}^{\mathrm{T}}-\alpha \mathbf{W}_{n} \mathbf{X}_{n}^{\mathrm{T}}\right)+\left(\alpha \mathbf{m} \mathbf{l}_{n} \mathbf{W}_{n}^{\mathrm{T}}-\alpha \mathbf{X}_{n} \mathbf{W}_{n}^{\mathrm{T}}\right)\right]=
=\left(\alpha N_{1} \mathbf{W}_{n} \mathbf{m} \mathbf{l}_{n}^{\mathrm{T}}-\alpha N_{1} \mathbf{W}_{n} \mathbf{m} \mathbf{l}_{n}^{\mathrm{T}}\right)+\left(\alpha N_{1} \mathbf{m} \mathbf{l}_{n} \mathbf{W}_{n}^{\mathrm{T}}-\alpha N_{1} \mathbf{m} \mathbf{l}_{n} \mathbf{W}_{n}^{\mathrm{T}}\right)=0

где N1 — число элементов в множестве w1, то из (1.19) следует  \mathbf{S} \mathbf{1}_{n-1}=\sum_{x \in \omega_{1}}\left(\mathbf{X}_{n}-\mathbf{m} \mathbf{l}_{n}\right)\left(\mathbf{X}_{n}-\mathbf{m} \mathbf{l}_{n}\right)^{\mathbf{T}}+\sum_{x \in \omega_{1}} B=\mathbf{S} \mathbf{I}_{n}+\sum_{x \in \omega_{1}} B  (1.21)

Так как

\begin{aligned} \sum_{x \in \mathbb{C}_{1}} B=\sum_{x \in \mathbb{C}_{1}} \alpha \mathbf{W}_{n} \alpha \mathbf{W}_{n}^{\mathrm{T}}=& \\=\sum_{x \in \mathbb{W}_{1}} \mathbf{W}_{n}^{\mathrm{T}}\left(\mathbf{X}_{n}-\mathbf{m} \mathbf{l}_{n}\right)\left(\mathbf{X}_{n}-\mathbf{m} \mathbf{l}_{n}\right)^{\mathrm{T}} \mathbf{W}_{n}\left(\mathbf{W}_{n} \mathbf{W}_{n}^{\mathrm{T}}\right)=& \\=\mathbf{W}_{n}^{\mathrm{T}}\left[\sum_{x \in \omega_{1}}\left(\mathbf{X}_{n}-\mathbf{m} \mathbf{l}_{n}\right)\left(\mathbf{X}_{n}-\mathbf{m} \mathbf{l}_{n}\right)^{\mathrm{T}}\right] & \mathbf{W}_{n}\left(\mathbf{W}_{n} \mathbf{W}_{n}^{T}\right)=\\=& \mathbf{W}_{n}^{\mathrm{T}} \mathbf{S} \mathbf{l}_{n} \mathbf{W}_{n}\left(\mathbf{W}_{n} \mathbf{W}_{n}^{T}\right) \end{aligned}

то

S1n-1=S1n  + WnTS1nWn(WnWnT)

и

Sn-1=S1n-1  + S2n-1 = S1n+ S2n +WnT(S1n+S2n)Wn(WnWnT) =Sn+WnTSnWn(WnWnT)   (1.22)

Окончательно из (1.17) с учетом (1.18) получаем

Wn-1 = Sn-1-1|(m1n– m2n) – WnT(m1n– m2n)Wn|             (1.23)

или подставляя в (1.23) выражение (1.22) получаем

Wn-1 = |SnWnTSnWn(WnWnT)|-1 х |(m1n-1– m2n-1) – WnT(m1n-m2n)Wn|. (1.24)

В (n – 2)-мерном признаковом пространстве получаем, соответственно Wn-2 = |Sn-1 +Sn-1TSn-1Wn-1(Wn-1Wn-1T| -1 x |(m1n-1– m2n-1) -Wn-1T(m1n-1-m2n-1)Wn-1|.

и так далее.

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

Для примера выберем два множества 3-мерных данных f1 и f2, которые приведены ниже. Столбцы этих матриц — признаки, а строки — отдельные объекты. Известно, что данные множества линейно разделимы в 3-мерном пространстве. Применим к ним метод главных компонент, линейный дискриминант Фишера и линейный дискриминант Фишера с одним добавочным признаком, полученным по формуле 1.24. Результат вычисления первых двух главных компонент показан на рис. 2. Из него видно, что метод главных компонент не обеспечивает линейную разделимость классов.

Реализация метода линейного дискриминанта Фишера с одним добавочным признаком на данных множествах показана на рис.3.

Анализ множеств f1 и f2 по методу главных компонент
Рис. 1. Анализ множеств f1 и f2 по методу главных компонент
Анализ множеств f1 и f2 методом линейного дискриминанта Фишера с одним добавочным признаком.
Рис. 2. Анализ множеств f1 и f2 методом линейного дискриминанта Фишера с одним добавочным признаком.

Из рис. 3 видно, что использование только одного весового вектора W1, найденного по критерию Фишера, линейной разделимости достичь не удается. Добавочный же признак (весовой вектор W2) обеспечивает полную линейную разделимость классов f1 и f2. Такой же результат получен при нахождении весового вектора с помощью простого однослойного персептрона.

На рис. 4 изображена область пересечений двух классов ирисов Фишера: виргинского и разноцветного (справа)5 в сокращенном пространстве, образованном двумя весовыми векторами W1 и W2.

Анализ ирисов Фишера
Рис 3. Анализ ирисов Фишера
Двумерное пространство (x1, x2) с двумя классами объектов w1 и w2
Рис. 4. Двумерное пространство (x1, x2) с двумя классами объектов w1 и w2

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

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

Дискриминантный анализ многоклассовой задачи с использованием критерия Фишера

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

При наличии с классов необходимо построить (с – 1) решающую функцию. Решение данной задачи возможно путем сведения ее к набору двухклассовых задач или на основе множественного дискриминантного анализа. Последний подход основан на применении того же критерия оптимизации J и обобщении определений для матриц разброса между классами и внутри классов. Критерий J, оценивающий степень разделения заданных классов сигналов, в общем виде задается следом матрицы

J = tr (SW-1 SB),             (1.25)

где SB — матрица рассеяния между классами; SW — обобщенная матрица рассеяния внутри классов6. Его также нужно максимизировать.

Для случая двух классов нахождение линейного преобразования Y = WTX, максимизирующего значение J, сводится к определению всего одного собственного значения матрицы (SW-1 SB). Отсюда следует возможность определения W с максимальным отношением разброса между классами к разбросу внутри классов в виде

W = SW-1(M1 – М2),

где SW = 0,5(Σ1 + Σ2).

В случае с классов проекции объектов при переходе из L-мерного пространства признаков в (с – 1)-мерное пространство находятся с помощью тою же матричного преобразования Y = WTX, но W — это уже матрица размера L х (с – I). Нахождение ее связано с представлением в формуле (1.25) матрицы в следующем виде7:

\mathbf{S}_{B}=\sum_{i=1}^{c-1} \sum_{j=i+1}^{c} n_{i} n_{j}\left(\mathbf{M}_{i}-\mathbf{M}_{j}\right)\left(\mathbf{M}_{i}-\mathbf{M}_{j}\right)^{\mathrm{T}}=\sum_{i=1}^{c-1} \sum_{j=i+1}^{c} n_{i} n_{j} \mathbf{S}_{B}^{(i, j)}

где ni и nj — частоты появления объектов, образующих классы wи w2.

Матрица SW определяется в том же виде:

\mathbf{S}_{W}=\sum_{j=1}^{c} n_{j} S_{j}

где Sj матрица разброса для j-ro класса.

Ранг матрицы SB равен (с – 1), и это значение определяет число собственных значений и собственных векторов, задаваемых матрицей W.

Недостаток применения выражения (1.25) связан с тем, что при увеличении числа классов критерий J ориентирован в основном на большие межгрупповые расстояния и слабо отражает взаимное расположение близко расположенных классов. А это в свою очередь ограничивает возможности применения метода для классификации трудно разделимых групп объектов.

Оптимизировать процедуру построения решающих правил можно путем сведения ее к набору задач попарной классификации с введением весовых коэффициентов ai,j, усиливающих влияние на критерий J близко расположенных классов8. В этом случае обобщенное выражение для критерия J принимает вид:

J=\sum_{i=1}^{c-1} \sum_{j=i+1}^{c} n_{i} n_{j} a_{i, j} \operatorname{tr}\left[\left(\mathbf{W}^{T} \mathbf{S}_{W} \mathbf{W}\right)^{-1} \cdot\left(\mathbf{W}^{T} \mathbf{S}_{B}^{(i, j)} \mathbf{W}\right)\right]   (1.26)

Весовую функцию ai,j можно связать с ценой ошибки распознавания классов wi и wj. В указанной работе предлагается использовать веса в виде функции ошибок erf [(η – t ) / σ ], где t — граница решающего правила, a η и σ — параметры распределений. Эта функция вычисляется для заданных групп объектов (i и j) исходя из предположений о нормальном законе распределений и равенстве ковариационных матриц. В этом случае критерий J может быть приближен к оценке достоверности распознавания объектов, представленных c-классами, путем суммирования вероятностей правильного решения при их попарной классификации.

Нахождение элементов матрицы W сводится к задаче определения собственных значений матрицы

\mathbf{S}_{W}^{-1} \sum_{i=1}^{c-1} \sum_{j=i+1}^{c} n_{i} n_{j} a_{i, j} \mathbf{S}_{B}^{(i, j)}

Они могут быть найдены как корни характеристического уравнения |SB – λSW| = 0, а затем получены d = с – 1 собственных векторов W, как решение системы уравнений (SB – λiSW) • Wi = 0. В новом пространстве размерности d значение критерия J определяется в виде

J=\sum_{i=1}^{d} \lambda_{i}

Представление объектов классов w1, w2, w3 в пространстве векторов W1, W2, полученных с применением весовых функций
Рис. 5. Представление объектов классов w1, w2, w3 в пространстве векторов W1, W2, полученных с применением весовых функций

Задачу выбора вида ai,j в (1.26) можно решить следующим образом. Рассмотрим в двумерном пространстве (x1,x2) два класса объектов w1 и w2 с нормальным законом распределения и единичными матрицами ковариации (рис. 5). Если расстояние между центрами этих классов обозначить как Δi,j =|mi — mj|, где mi и mj  — векторы средних значений, то, проецируя эти классы на новое направление V, получим изменение расстояния между ними в зависимости от угла α между направлением, соединяющим центры классов, и вектором V. Эту зависимость можно представить как Δi,j (V)= Δi,j cos α = Δi,j  sin β, где β — дополнительный угол. При равных априорных вероятностях появления объектов обоих классов вероятность правильного распознавания определится в виде

\gamma_{i, j}=\frac{1}{2}+\gamma_{i, j}^{\prime}=\frac{1}{2}+\frac{1}{2} \operatorname{erf}\left[\frac{\Delta_{i, j}^{(\mathbf{V})}}{2 \sqrt{2}}\right]

где erf(•) — функция ошибок.

Тогда для случая с классов с одинаковыми распределениями критерий J(γ), оценивающий среднюю точность распознавания, можно записать в виде

J^\lambda=\sum_{i=1}^{c-1} \sum_{j=i+1}^{c} n_{i} n_{j} \gamma_{i, j} (1.27)

а критерий J, оценивающий степень расхождения классов (1.26), примет вид

J=\sum_{i=1}^{c-1} \sum_{j=i+1}^{c} n_{i} n_{j} a_{i, j} \operatorname{tr}\left|\left(\mathbf{V}^{T} \mathbf{S}_{B}^{(i, j)}\mathbf{V} \right)| (1.28)

Сравнивая (1.27) и (1.23) веса ai,j можно задать в виде

ai,ji,j/tr(VTSB(i,j)V)

для случая наилучшего взаимного расположения двух классов (w1, w2). что соответствует совпадению направлений векторов V и mi,j = (mi -mj). При этом α = 0; β =π/2,  tr(VTS1(i,j)V)  = (Δi,j)2, и параметр

ai,j определится следующим образом:

a_{i, j}=\gamma_{i, j}^{\prime} /\left(\Delta_{i, j}\right)^{2}=\frac{1}{2\left(\Delta_{i, j}\right)^{2}} \operatorname{erf}\left(\frac{\Delta_{i, j}}{2 \sqrt{2}}\right)

Такой вид задания весовых функций предлагается в работе9. В области малых значений Δi,j например, при распознавании объектов по параметрам нормированного спектра или иным нормированным параметрам, веса ai,j можно задать, используя приближение функции ошибок полиномиальной функцией

a_{i, j} \approx \frac{1}{8 \sqrt{\pi} \cdot x_{i, j}}\left(1-\frac{x_{i, j}^{2}}{3}+\frac{x_{i, j}^{4}}{2 ! 5}\right) (1.29)

где

x_{i, j}= \left(\frac{\Delta_{i, j}}{2 \sqrt{2}}\right), Δi,j ≤ √2, xi,j ≤0.5

Этот способ нахождения весовых функций ai,j = a(Δi,j) можно

применить и для многоклассовой задачи1011, предполагая, что каждый из с классов имеет матрицу внутригруппового рассеяния, равную Sw. Тогда для каждой пары классов (w1, w2; i, j = 1, … , c; i ≠ j) в исходном L-мерном пространстве признаков необходимо найти евклидово расстояние Δi,j между их центрами и определить веса ai,j используя выражение (1.29). Максимизация критерия J (1.26) позволяет перейти к процедуре нахождения собственных векторов Wi , i= 1, …., с — 1 и анализу групп объектов в пространстве признаков пониженной размерности.

Применение метода для распознавания опасных аритмий

Эффективность применения рассмотренных процедур оценивалась по результатам экспериментов, выполненных на реальных данных, включающих записи ЭКС длительностью более 20 минут12. Все реализации ЭКГ получены из стандартной компьютерной базы ЭКГ-сигналов MIT-BIH.

В качестве примера на рис. 6 приведены результаты отображения объектов на плоскость, заданную координатами (y1, y2) в пространстве собственных векторов W1, W2, которые получены при распознавании следующих трех классов сигналов: w1— опасные аритмии (желудочковая фибрилляция и трепетание желудочков); w2— пароксизмальная тахикардия и фоновый ритм, представленный разными формами экстрасистолии; w3 — пируэтная тахикардия, являющаяся переходной формой опасного нарушения ритма. Оптимизация пространства проведена по критерию J (1.26) с применением весовых функций.

Классификатор на 2 класса (персептрон)
Рис. 6. Классификатор на 2 класса (персептрон)

В качестве исходного описания объектов, представленных фрагментами электрокардиосигнала длительностью 2 с, дискретизированными с частотой 250 Гц, использован упорядоченный набор 28 спектральных признаков. Они получены для частотной области, ограниченной частотой 15 Гц, с применением перекрывающихся сегментов. Некоррелированные оценки спектральной плотности мощности вычислены при ширине спектрального окна Δ f = 0,976 Гц, но при этом шаг по частотной оси выбран вдвое меньше этой величины и составлял 0,488 Гц. В этом случае удается сохранить особенности формы спектра анализируемых сигналов при относительной устойчивости получаемых оценок СПМ.

На рисунке выделены области нахождения представленных групп объектов, причем видно, что классы частично пересекаются. Соотношение расстояний между центрами классов в исходном пространстве составило Δ1,2 = 0.42; Δ1,3 = 0,36; Δ2,3 = 0,22, откуда следует, что исходно классы w2 и w3 расположены значительно ближе друг к другу, чем к w1. Вычисление весов по формуле (1.29), а именно a1,2 = 0,623; a1,3 = 0,707; a2,3 = 1.165, обеспечило преимущественное влияние расстояния Δ2,3 на критерий J. В результате в пространстве координат (y1, y2) анализируемые группы объектов (w1, w2, w3) расположились относительно друг друга на расстоянии Δ1,2 = 0,36; Δ1,3 = 0,34; Δ2,3 = 0,30, что обеспечило более равномерную картину распределения центров классов.

В ходе экспериментов были построены разделяющие функции, определены границы областей решений и найдены ошибки классификации. Распределение объектов в двумерном пространстве d = 2 было получено для традиционного подхода на основе критерия (1.25) и с использованием весовых функций (1.26). Как показал результат линейного дискриминантного анализа, при использовании весовых функций средняя ошибка классификации может быть уменьшена с 8,2% до 4,6%, что является показателем эффективности применения этой процедуры оптимизации.

В результате анализа объектов, попавших в зону пересечения полученных областей решений, установлено, что они являются спорными в плане классификации, поскольку могут быть отнесены к одному из альтернативных классов. Это касается в основном пересечения областей w1 и w2  с промежуточным классом w3. Важным является результат безошибочного распознавания классов w1 и w2, что гарантирует надежное обнаружение желудочковой фибрилляции в стадии устойчивого ее проявления.

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

 

 

Footnotes

  1. Ту Дж., Гонсалес Р. Принципы распознавания образов / Пер. с англ.; Пол ред. Ю. И. Журавлева. М.: Мир, 1978. — 411 с.
  2. Дуда 3., Харт П. Распознавание образов и анализ сцен / Пер. с англ. — М.: Мир, 1976. – 511 с.
  3. Дуда 3., Харт П. Распознавание образов и анализ сцен / Пер. с англ. — М.: Мир, 1976. – 511 с.
  4. . Немирно А. П. Микропроцессорные медицинские диагностические системы: учеб, пособие / ЛЭТИ. — Л.» 1984. — 64 с.
  5. Iris Data Set. UCI Machine Learning epository, https://archive.ics.uci.edu/ml/datasets/lris, 2016.
  6. Дуда 3., Харт П. Распознавание образов и анализ сцен / Пер. с англ. — М.: Мир, 1976. – 511 с.
  7. I.oog AL, Duin R. P. tt”., Haeb-Umbach R. Multiclass Linear Dimension Reduction by Weighted Pairwise Fisher Criteria // IEEE Transactions on Pattern Analysis and Machine Intelligence. 2001. Vol. 23, № 7. P. 762-766.
  8. I.oog AL, Duin R. P. tt”., Haeb-Umbach R. Multiclass Linear Dimension Reduction by Weighted Pairwise Fisher Criteria // IEEE Transactions on Pattern Analysis and Machine Intelligence. 2001. Vol. 23, № 7. P. 762-766.
  9. I.oog AL, Duin R. P. tt”., Haeb-Umbach R. Multiclass Linear Dimension Reduction by Weighted Pairwise Fisher Criteria // IEEE Transactions on Pattern Analysis and Machine Intelligence. 2001. Vol. 23, № 7. P. 762-766.
  10. Манило JI. А. Преобразование пространства спектральных признаков с использованием весовых функций в задачах распознавания сигналов // Изв. вузов России. Сер. Радиоэлектроника». 2007. Вып. 2. С. 37-42.
  11. Манило Л.A., Немирно Л. П. Сокращение размерности пространства спектральных признаков в многоклассовой задаче распознавания сигналов. Математические методы распознавания образов ММРО-13: 13-я Всерос. конф. Ленингр. обл., г. Зеленогорск, 30 сснт. — 6 окт. 2007 г. // Сб. докл. М.: МАКС Пресс, 2007. С. 356-359.
  12. Манило Л.A., Немирно Л. П. Сокращение размерности пространства спектральных признаков в многоклассовой задаче распознавания сигналов. Математические методы распознавания образов ММРО-13: 13-я Всерос. конф. Ленингр. обл., г. Зеленогорск, 30 сснт. — 6 окт. 2007 г. // Сб. докл. М.: МАКС Пресс, 2007. С. 356-359.