Методы распознавания образов

Методы распознавания образов применяются для задач анализа данных, которые характеризуются малым числом объектов в классах и для которых важно определить степень сходства или различия классов. Часто необходимо создать алгоритм автоматического определения (распознавания) принадлежности объектов к определенным классам. Распознавание образов относится к автоматизации интеллектуальных задач принятия решений и опирается на теорию вероятностей, теорию матриц, математическую логику и математическую лингвистику. Методам распознавания образов посвящена обширная литература¹²³⁴⁵ .

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

диагностика заболеваний⁶⁷;
распознавание и прогнозирование угрожающих жизни состояний больного, психофизиологических состояний человека по комплексу электрофизиологических показателей⁸;
автоматический анализ и интерпретация биомедицинских сигналов и изображений⁹¹⁰;
другие задачи: машинное зрение; распознавание речи; идентификация человека по голосу, отпечаткам пальцев, изображению глаза; чтение печатного и рукописного текста, топографических карт и т. п.

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

Допустим, мы имеем m классов объектов w₁,w₂,.., w_m. Каждый поступающий объект должен быть отнесен к одному из этих m классов и каждый объект описывается набором из n измерений (действительных чисел) x₁, x₂,…,х_n, которые называются признаками. Такой набор может быть представлен точкой в n-мерном евклидовом пространстве или, иначе говоря, вектором признаков X = (x₁, x₂,…,х_n) в n-мерном признаковом пространстве, где x₁, x₂,…,х_n — декартовы координаты конца вектора X. Например, при диагностике состояний больного мы имеем 2 класса: w₁ — A-состояние, w₂ — В-состояние.

Каждый поступающий больной описывается 3 признаками (показателями), полученными по результатам его объективного обследования:

x₁ — частота пульса,
х₂ – частота дыхания,
x₃ — среднее артериальное давление.

В этом случае состояние одного больного, описываемое точкой (вектором) X = (x₁, x₂,x₃) в 3-мерном пространстве, должно быть отнесено к одному из двух классов: w₁ или w₂ (рис. 1).

Рис. 1. Описание классов в признаковом пространстве

Разделяющие поверхности в признаковом пространстве. Дискриминантные функции

Таким образом, классификатор объектов является устройством, которое отображает точки из Еⁿ в множество классов {w₁,w₂,…,w_m} (рис. 2). Обозначим через R_i, множество точек из Е_n, которое отображается в класс w_i.

Тогда множеству классов {w₁,w₂,…,w_m} будет соответствовать множество областей из Еⁿ {R₁,R₂,…,R_m}. Например, на рис. 3, где n = 2, m = 3, любая точка на плоскости в зависимости от ее принадлежности к областям R₁,R₂,R₃ отображается, соответственно, в один из классов w₁,w₂,w₃, Все три области отделены друг от друга поверхностями (кривыми в Е²), которые мы будем называть разделяющими.

Рис. 3. Отображение объектов в множество классов

Разделяющие поверхности любого классификатора объектов можно полностью определить m скалярными функциями: D₁(X), …,D_m(Х), называемыми дискриминантными функциями (ДФ). Они выбираются так, чтобы для всех Х ∈ R_i, выполнялось D_i(Х) > D_j(X) при i, j = 1, …, m; i ≠ j. Мы также предполагаем, что ДФ непрерывны на разделяющих поверхностях. Тогда поверхность, разделяющая смежные области R_i и R_j, определяется уравнением

D_i(X)-D_j(X) = 0. (1.1)

На рис. 4 показаны три ДФ и области решений, порождаемые ими на плоскости x₁, x₂.

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

Рис. 5. Распознавание с помощью дискриминантных функций

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

Линейные дискриминантные функции

К простейшим дискриминантным функциям относятся линейные (ЛДФ), определяемые выражением

$D_{i}(\mathbf{X})=\sum_{k=1}^{m} w_{i k} x_{k}+w_{i(n+1)}, \quad i=1, \ldots, m$

Для i = 1 ЛДФ имеет вид

D₁(X) = w₁₁x₁+ w₁₂x₂ + w₁₃x₃ + … + w_1(n+1).

В этом случае поверхность, разделяющая смежные области R_i и R_j, в Еⁿ определяется из (1.1)

$D_{i}(\mathbf{X})-D_{j}(\mathbf{X})=\sum_{k=1}^{n} w_{k} x_{k}+w_{n+1}=0$ (1.2)

где w_k = w_ik – w_jk, w_n+i = w_i(n+1) – w_j(n+1).

Полученное уравнение это уравнение гиперплоскости в пространстве Еⁿ.

Если m = 2, то уравнение (1.2) превращается в следующее:

D(X) = D₁(X) – D₂(Х) = w₁x₂ + w₂x₂ +… + w_nx_n + w_n+1 = 0,

и по знаку новой дискриминантной функции D(X) мы можем отнести входной объект к одному из двух классов — w₁ или w_2.

Если D(X) >0, то R₁ и входной объект относится к классу w₁.

Если D(X) < 0, то R₂ и входной объект относится к классу w₂.

Введя пороговый логический блок (ПЛБ), классификатор для этого случая можно изобразить, как показано на рис. 6.

Вышеприведенное выражение для £)(Х) можно также записать в виде

D(X)=W^TX—а=0,

где W — весовой вектор; 0 — пороговая величина. Удобно сделать вектор W единичным, разделив все компоненты на норму этого вектора. В этом случае, так как W^TX = |X|cos a (рис. 7), то процедура распознавания заключается в вычислении проекции вектора X на направление весового вектора W и сравнении полученной величины с порогом а. Также ясно, что разделяющая гиперплоскость проходит перпендикулярно к W на расстоянии а от начала координат.

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

Классификатор ЭЭГ

Примером линейного классификатора является классификатор электроэнцефалограмм (ЭЭГ) (рис. 8). На вход устройства подается сигнал ЭЭГ, обозначенный как z(t). В устройстве вычисляется 6 признаков (параметров):

x₁ — число пересечений нулевой линии,
x₂ — средняя амплитуда исходной ЭЭГ,
x₃ — число максимумов и минимумов,
x₄ — средняя амплитуда 1-й производной,
x₅— число точек перегиба,
x₆ — средняя амплитуда 2-й производной.

Как видно из рисунка, сигнал U на выходе ОУ равен

$U=\sum_{i=1}^{6} w_{i} x_{i}+w_{7}$
гдe $w_{i}=\frac{r_{8}}{r_{i}}, i=1, \ldots, 7$

В случае, когда некоторые w_iотрицательны, в схеме перед соответствующими r_i необходимо поставить инверторы. Сигнал на выходе ПЛБ равен +1, если U > 0, и —1, если U < 0.

Реальная схема классификатора немного сложнее. Она разбивает не на 2, а на 4 класса за счет использования не одного, а 3 порогов. В этом случае на рисунке соединение с r₇ удаляется, а правая часть рисунка приобретает вид рис. 9. Сравнение с порогами производится по следующему правилу:

если $\sum_{i=1}^{6} w_{i} x_{i}<w_{7},$ тo ЭЭГ относится к классу 1, иначе
если $w_{7} \leqslant \sum_{i=1}^{6} w_{i} x_{i}<w_{8},$ то ЭЭГ относится к классу 2, иначе
если $w_{8} \leqslant \sum_{i=1}^{6} w_{i} x_{i}<w_{9}$ , то ЭЭГ относится к классу 3, иначе
если $\sum_{i=1}^{6} w_{i} x_{i}>w_{9}$ , то ЭЭГ относится к классу 4 .

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

Классификатор по минимуму расстояния

Пусть в n-мерном признаковом пространстве мы имеем m эталонных векторов P₁, Р₂, …. Р_m, каждый из которых является эталоном (шаблоном) своего класса (эталонных векторов), как изображено на рис. 10. Вектор Р_i = (р_i1, р_i2…..p_in) соответствует классу w_i. Классификатор по минимуму расстояния относит входной вектор X к том классу w_i, для которого расстояние |Х – P_i| между X и эталонным вектором P_i минимально. Вместо расстояния |Х – P_i| можно взять его квадрат |Х – P_i|². Так как |Х – P_i| = √(Х – P_i)^Т(Х – P_i), то |Х – P_i|² = (X – Р_i)^Т(Х – Р_i) и на основании свойства дистрибутивности скалярных произведений векторов имеем

|Х – Р_i|² = Х^ТХ – X^TP_i – Р_i^TХ + Р_i^TР_i. (1.3)

Произведение X^TX = |Х| на расстояние не влияет, а на основании свойства коммутативности скалярных произведений векторов справедливо равенство X^TР_i = Р_i^TX. так как

$\sum_{j=1}^{n} x_{j} p_{i j}=\sum_{j=1}^{n} p_{i j} x_{j}$

Тогда, исключив X^TX из выражения (1.3), поменяв знаки и поделив все члены на 2, получим дискриминантную функцию D_i(X) для класса Она имеет вид

D_i(Х) = Х^ТР_i -½Р_i^ТP_i_; i = 1, …, m. (1.4)

Как и ранее, входной вектор X относится к классу w_i. если

D_i(Х) > D_j(Х), i, j=1…..m, i ≠ j.

Выражение (1.4) также можно написать в виде

D_i(X) = x₁w_i1 + x₂w_i₂ +… + x_nw_in + w_i_(n+1), i = 1, …, m,

где w_ij=p_iji=1, …, m, j=1,…,n;

w_i_(n+1) = -½(p²_i1 +p²_i2 + … +p²_in) , i=1, …, m

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

При m = 2 (два класса)

D₁(Х) = Х^ТР₁ – ½ Р₁^TР₁ , D₂(Х) = Х^ТР₂ – ½ Р₂^TP₂.

D⁰(X) = D₁(X) – D₂(X) = X^TР₁ – X^TP₂ – ½ (Р₁^TР₁ – Р₂^TP₂).

Добавим к выражению в скобках член Р₁^TР₂ и вычтем равный ему Р₂^TР₁. Тогда

D⁰(Х) = Х^Т(Р₁ – Р₂) – ½ (Р₁^TР₁ – Р₁^TР₂ +Р₂^TР₁– P₂^TP₂).

D⁰(X) = Х^Т(Р₁ – P₂) – ½(Р₁ + P₂)^T(Р₁ – P₂).

Разделим все члены последнего выражения на |Р₁ — Р₂|. Тогда

$D(\mathbf{X})=\mathbf{X}^{\top} \frac{\mathbf{P}_{1}-\mathbf{P}_{2}}{\left|\mathbf{P}_{1}-\mathbf{P}_{2}\right|}-\frac{1}{2} \frac{\left(\mathbf{P}_{1}+\mathbf{P}_{2}\right)^{\mathrm{T}}\left(\mathbf{P}_{1}-\mathbf{P}_{2}\right)}{\left|\mathbf{P}_{1}-\mathbf{P}_{2}\right|}$
$D(\mathbf{X})=\mathbf{W}^{T} \mathbf{X}-a, \quad \mathbf{W}=\frac{\mathbf{P}_{1}-\mathbf{P}_{2}}{\left|\mathbf{P}_{1}-\mathbf{P}_{2}\right|}, \quad a=-\frac{1}{2}\left(\mathbf{P}_{1}+\mathbf{P}_{2}\right)^{\mathrm{T}} \mathbf{W}$

Нa рис. 1.11 показана разделяющая (линейная) граница D(Х) =0 между двумя классами, проведённая для классификации по минимуму расстояния до эталонов классов.

Рис. 10. Классификация по минимуму расстояния до эталонов двух классов

Зависимость относительной доли суммарной дисперсии исследуемых признаков q(p') от числа р' первых главных компонент (случай р = 10) — Рис. 11. Зависимость относительной доли суммарной дисперсии исследуемых признаков q(p’) от числа р’ первых главных компонент (случай р = 10)

Footnotes

Ту Дж., Гонсалес Р. Принципы распознавания образов / Пер. с англ.; Пол ред. Ю. И. Журавлева. М.: Мир, 1978. — 411 с.
Дуда 3., Харт П. Распознавание образов и анализ сцен / Пер. с англ. — М.: Мир, 1976. – 511 с.
Вапник В. //., Червоненкис Л. Я. Теория распознавания образов. Стохастические проблемы обучения. — М.: Наука, 1974.
Нильсон Н. Обучающиеся машины / Пер. с англ. — М.: Мир, 1967. -180 с.
Фу К. Структурные методы в распознавании образов / Пер. с англ. -М.. Мир, 1977. – 320 с.
Рангайян Р. М. Анализ биомедицинских сигналов. Практический подход / Пер. с англ. А. II. Калиниченко; Под ред. Л. П. Немирно. -М.: Физматлит, 2007. — 440 с.
Гублер Е. В. Вычислительные методы анализа и распознавания патологических процессов. Л.: Медицина, 1978. 290 с.
Генкин А. А., Медведев В. И. Прогнозирование психофизиологических состояний. Вопросы методологии и алгоритмизации. — Л.: Наука. 1973. — 144 с.
Рангайян Р. М. Анализ биомедицинских сигналов. Практический подход / Пер. с англ. А. II. Калиниченко; Под ред. Л. П. Немирно. -М.: Физматлит, 2007. — 440 с.
Немирно А. П. Цифровая обработка биологических сигналов. М.: Наука, 1984. — 144 с.