Математическая формализация задачи

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

.

Следовательно, задача обучения сводится к разбиению пространства индикаторов на классы (т.е. к проведению классификации), а задача распознавания сводится к определению класса (т.е. к проведению кластеризации) z_j={X}_j, j=1,…,k с помощью выбранной векторной нормы:

.

Как известно, с помощью векторной нормы можно определить понятие расстояния между вектором и классом, а также понятие расстояния между классами.

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

Определим образ как n-мерный вектор-столбец X=[x₁, x₂,…,x_n], где x₁, x₂,…,x_n являются вещественными числами, и индекс T является символом транспонирования матрицы.

Представим задачу распознавания образовкак отображение f(X)→{1,…,c} любого образа X в одно из целых чисел 1,…,c, которые представляют классы.

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

Дано:

- Число классов c;

- набор из m обучающих образов: X1,….,Xm;;

- класс любого обучающего образа:f(X1)=c1…,f(Xm)=cm;

- произвольный n-мерный вектор P.

Найти:

Класс вектора P: f(P)=?.

Для реальных задач исходные данные в самом общем случае являются многомерными и допускают представление в виде массивов (векторов) вещественных и/или целых чисел. Как было отмечено выше, одной из основных особенностей ИК-алгоритма распознавания образов является проекция произвольных данных в пространство ФИС. Такое преобразование обладает следующими преимуществами:

- имеет строгое математическое обоснование в терминах сингулярного разложения матриц;

- существенно снижает размерность данных (до одно- двух- или трехмерного пространства ФИС);

- позволяет наглядно представить и визуализировать любую ситуацию как точку одно- двух- или трехмерного пространства.

Рассмотрим математическое описание основных процедур алгоритма иммунокомпьютинга.

Обучение

1. Сформировать обучающую матрицу A=[X₁,…,X_m]^T размерности m×n.

2. Вычислить максимальное сингулярное число s, а также левый и правый сингулярные векторы U и V обучающей матрицы по следующей итеративной (эволюционной) схеме:

до выполнения условия

3. Хранить сингулярное число s.

4. Хранить правый сингулярный вектор V как антитело-пробу.

5. Для всякого i=1,…,m хранить компоненту u_i левого сингулярного вектора U (как клетку формальной иммунной сети) и класс c_i, соответствующий обучающему образу X_i.

Распознавание

6. Для всякого n-мерного образа Z вычисляется энергия связи с V:

(напомним, что s–хранимое сингулярное число, а V– это хранимый правый сингулярный вектор обучающей матрицы A).

7. Выбирается u_i, которая имеет минимальное расстояние (близость) с энергией связи w:

8. Считать класс c_i искомым классом образа Z.

Замечания

Данное ядро алгоритма распознавания образов использует только максимальное (первое) сингулярное число s и соответствующие ему сингулярные векторы U и V, которые вычисляются на шаге 2 данного алгоритма.

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

1.Вычислить максимальное сингулярное число s₁ и соответствующие ему сингулярные вектора U₁ и V₁ обучающей матрицы на шаге 2.

2.Сформировать матрицу A₂=A‑s₁U₁V₁ и вычислить ее максимальное сингулярное число s₂ и соответствующие ему сингулярные векторы U₂ и V₂ посредством шага 2.

3.Сформировать матрицу A₃=A – s₂U₂V₂ и вычислить ее максимальное сингулярное число s₃ и соответствующие ему сингулярные векторы U₃ и V₃ посредством шага 2.

Затем вычислить 3 значения энергии связи с помощью шага 6:

Определить класс c_i на шаге 8 посредством определения минимального расстояния в трехмерном Евклидовом пространстве на шаге 7:

,

где являются i-ми компонентами левых сингулярных векторов U₁, U₂, U₃.

Отметим, что шаги 2 и 3 над матрицами A₂ и A₃ обеспечивают более точную аппроксимацию обучающей матрицы, согласно следующему свойству сингулярного разложения:

где – ранг матрицы A.

Следует также отметить, что данный алгоритм иммунокомпьютинга может быть рассмотрен как «иммунный» алгоритм, так как любой образ может быть представлен как частный случай формального протеина и его распознавание основывается на энергии связи с антителом формального протеина.

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

Цель работы:создание программного модуля для реализации вычислительной процедуры обучения с экспертом на основе инструментария универсальной системы MATLAB.

Порядок выполнения работы

1. Открыть универсальную систему MATLAB.

2. Задать исходную матрицу А соответствующейразмерности и матрицу анализируемого объекта М. Программно реализовать шаги 1-8 алгоритма вычислительной процедуры обучения с экспертом.

3. Сохранить все результаты выполнения работы в файле на диске.

4.5.2. Порядок оформления отчета

Отчетом о лабораторной работе № 4 является файл с именем, совпадающим с фамилией студента с результатами работы в папке Мои документы/номер группы.

Пример выполнения лабораторной работы №4

Рассмотрим решение задачи классификации (задачи обучения с экспертом) на примере классификации легковых автомобилей.

Пусть имеется обучающая выборка в виде матрицы R размерности (3×33). Эта матрица в качестве элементов имеет индикаторы, характеризующие три класса легковых автомобилей (второй, пятый и шестой):

Рисунок 19 Обучающая выборка в виде матрицы R размерности (3×33).

Сингулярное разложение обучающей матрицы R осуществляется c помощью оператора: [U S V]=svd(R).

Ниже представлены матрицы компонент сингулярного разложения:

Рисунок 20 Матрицы компонент сингулярного разложения

Анализируемый объект представляется в виде вектора М:

M=[2000 3 1375 1925 222 10.1 445 4547 1766 1428 2650 1528 106 3 2 1781 9.5 2 20 150 210 2 1 3 2 2 2 2 11.3 6.4 9.2 1 71].

Для этого вектора М вычисляем значения энергии связи и расстояние до соответствующих точек для 2, 5, 6, классов в пространстве ФИС.

Рисунок 21 Результаты вычислений значений энергии

Из полученного множества значений расстояний от точки в пространстве ФИС, характеризуемой анализируемый объект до точек, характеризующих соответственно, классы 2, 5, 6:

d={d2,d5,d6}={1.0090, 0.4082, 1.2202}

выбираем наименьшее значение, которое равно 0.4082. Это значение определяет принадлежность анализируемого объекта к 5 классу.

Вывод: анализируемый объект принадлежит к 5 классу.

4.5.4. Контрольные вопросы

1. Какая норма была использована при проведении классификации?

2. Сущность вычислительной процедуры автоматической классификации.

3. Можно ли назвать рассмотренную процедуру обучения с экспертом интеллектуальной процедурой?

4.

5.

6.

7.

8.

9.

10.

ФОРМИРОВАНИЕ ИНДЕКСОВ РИСКА