ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
РОССИЙСКОЙ ФЕДЕРАЦИИ
Санкт-Петербургский
Государственный университет аэрокосмического приборостроения
ОЦЕНИВАНИЕ СОСТОЯНИЯ СЛОЖНЫХ СИСТЕМ НА ОСНОВЕ ИММУНОКОМПЬЮТИНГА
Методические указания
к выполнению лабораторных работ по дисциплине «Интеллектуальные информационные системы»
Санкт-Петербург
2010
Составители: С.П. Соколова, И.В. Усикова, Н.В. Зуева
Рецензент: кафедра менеджмента и маркетинга ГУАП
Методические указания содержат ряд лабораторных работ, целью выполнения которых является разработка пакета прикладных программ для комплексного оценивания состояния сложных систем на основе иммунокомпьютинга с использованием инструментария универсальных системы MATLAB. Эта система имеет дружественный интерфейс, реализует множество стандартных и специальных математических операций, снабжена мощными графическими средствами и обладает собственным языком программирования.
Математической основой комплексного оценивания состояния сложных систем служит подход иммунокомпьютинга с использованием сингулярного разложения произвольных матриц.
Методические указания предназначены для студентов очной, заочной и дистантной форм подготовки для выполнения лабораторных работ по дисциплине «Интеллектуальные информационные системы».
ОГЛАВЛЕНИЕ
ПРЕДИСЛОВИЕ.. 5
1. МАТРИЧНЫЕ ВЫЧИСЛЕНИЯ НА ОСНОВЕ УНИВЕРСАЛЬНОЙ СИСТЕМЫ MATLAB.. 7
1.1. Задание матриц. 7
1.2. Матричные вычисления. 8
1.2.1.
Функции описания матриц
.. 8
1.2.2.
Знаки операций
.. 8
1.2.3.
Матричные характеристики
.. 8
1.2.4.
Команды линейной алгебры
.. 8
1.2.5.
Команды факторизации
.. 9
1.2.6.
Команды вычисления спектра
. 9
1.3. Интегрирование MATLAB и Excel 10
1.3.1.
Конфигурирование Excel
10
1.3.2.
Обмен данными между MATLAB и Excel
11
1.4. Программирование. 12
1.4.1.
М-файлы
.. 12
1.4.2.
Файл-программа
. 13
1.4.3.
Файл-функция
. 15
1.4.4.
Создание графика
. 16
1.4.5.
Печать графиков
. 18
1.5. Лабораторная работа № 1. 19
1.5.1.
Порядок выполнения работы
.. 19
1.5.2.
Оформление отчета
. 19
1.5.3.
Контрольные вопросы
.. 19
2. ВЫЧИСЛИТЕЛЬНАЯ ПРОЦЕДУРА СИНГУЛЯРНОГО РАЗЛОЖЕНИЯ МАТРИЦ.. 20
2.1. Математический аппарат. 20
2.2. Лабораторная работа № 2. 22
2.2.1.
Порядок выполнения работы
.. 22
2.2.2.
Пример выполнения лабораторной работы №2
. 22
2.2.3.
Порядок оформления отчета
. 26
2.2.4.
Контрольные вопросы
.. 26
3. ВЫЧИСЛИТЕЛЬНАЯ ПРОЦЕДУРА ОБУЧЕНИЯ С ЭКСПЕРТОМ... 26
3.1. Математический аппарат. 26
3.2. Лабораторная работа № 3. 29
3.2.1.
Порядок выполнения работы
.. 29
3.2.2.
Порядок оформления отчета
. 29
3.2.3.
Пример выполнения лабораторной работы №3
. 29
3.2.4.
Контрольные вопросы
.. 31
4. ВЫЧИСЛИТЕЛЬНАЯ ПРОЦЕДУРА ОБУЧЕНИЯ С ЭКСПЕРТОМ... 32
4.1. Математическая формализация задачи. 32
4.2. Обучение. 34
4.3. Распознавание. 34
4.4. Замечания. 35
4.5. Лабораторная работа № 4. 36
4.5.1.
Порядок выполнения работы
.. 36
4.5.2.
Порядок оформления отчета
. 37
4.5.3.
Пример выполнения лабораторной работы №4
. 37
4.5.4.
Контрольные вопросы
.. 39
5. ФОРМИРОВАНИЕ ИНДЕКСОВ РИСКА.. 40
5.1. Описание задачи формирования индексов. 40
5.2. Базовый алгоритм вычисления индекса. 40
Ниже представлены частные случаи процедуры формирования индекса с использованием компонент сингулярного разложения матрицы М
. 45
5.3. Одномерный линейный случай. 45
5.4. Лабораторная работа № 5. 45
5.4.1.
Порядок выполнения работы
.. 48
5.4.2.
Порядок оформления отчета
. 48
5.4.3.
Контрольные вопросы
.. 48
6. ТЕСТИРОВАНИЕ ПОЛУПРОВОДНИКОВЫХ ЛАЗЕРНЫХ ДИОДОВ НА ОСНОВЕ ИНСТРУМЕНТАРИЯ УНИВЕРСАЛЬНЫХ СИСТЕМ MATLAB.. 49
6.1. Описание задачи. 49
6.2. Тестовые данные. 50
6.3. Лабораторная работа № 6. 51
6.3.1.
Порядок выполнения работы
.. 52
6.3.2.
Порядок оформления отчета
. 52
6.3.3.
Контрольные вопросы
.. 52
7. ПРОВЕДЕНИЕ ЭКСПЕРТИЗЫ НАУЧНО-ТЕХНИЧЕСКИХ ПРОЕКТОВ.. 52
7.1. Описание задачи. 52
7.2. Лабораторная работа № 7. 55
7.2.1.
Порядок выполнения работы
.. 55
7.2.2.
Порядок оформления отчета
. 55
7.2.3.
Контрольные вопросы
.. 56
8. КОМПЛЕКСНАЯ ЭКСПЕРТИЗА ВНУТРИВУЗОВСКИХ СИСТЕМ УПРАВЛЕНИЯ КАЧЕСТВОМ ОБРАЗОВАНИЯ 56
8.1. Описание задачи. 56
8.2. Лабораторная работа № 8. 58
8.2.1.
Порядок выполнения работы
.. 58
8.2.2.
Порядок оформления отчета
. 60
8.2.3.
Контрольные вопросы
.. 60
9. АЛГОРИТМ ФОРМИРОВАНИЯ ЭЛЕКТРОННОЙ ЦИФРОВОЙ ПОДПИСИ.. 60
9.1. Описание задачи. 60
9.2. Лабораторная работа № 10. 64
9.2.1.
Порядок выполнения работы
.. 64
9.2.2.
Порядок оформления отчета
. 65
9.2.3.
Контрольные вопросы
.. 65
ПРЕДИСЛОВИЕ
Новая вычислительная процедура, называемая искусственные иммунные системы (ИИС), основанная на принципах иммунной системы, обладает способностью обучаться новой информации, запоминать ранее полученную информацию и осуществлять распознавание образов и анализ данных на основе принципов биомолекулярного узнавания в высоко распределенной манере. Эти системы предлагают мощные и робастные возможности обработки больших массивов информации для решения сложных задач. Строгий математический базис ИИС основан на биологическом прототипе иммунной сети и понятиях формального протеина и формальной иммунной сети (ФИС).
Эти математические модели были названы формальной иммунной системой или иммунокомпьютингом на основе свойств сингулярного разложения произвольных матриц.
Иммунокомпьютинг (ИК) позволяет с большой эффективностью решать следующие задачи: обучения с экспертом, самообучения (обучения без эксперта), группировки и классификации, представления результатов вычислений в пространстве образов.
Структурная схема ИК для решения вышеперечисленных задач представлена на рис. 1.
Как видно из структурной схемы, на основе исходной информации формируется база данных. База данных содержит фактографические данные об исследуемой системе.
База знаний содержит сведения, которые отражают закономерности, существующие в рассматриваемой предметной области, позволяют выводить новые знания и прогнозировать потенциально возможные состояния исследуемой области; сведения о структуре и содержании базы данных; сведения по языку общения; метазнания, определяющие способы представления и переработки знаний. В базу знаний помещаются как общедоступные данные, так и знания эксперта в данной предметной области, вычислительные алгоритмы реализации процедур иммунокомпьютинга, результаты группировки и автоматической классификации, а также интерпретация результатов вычислений.
Основные вычислительные процедуры: обучение с экспертом и самообучение (обучение без эксперта), автоматической классификации, основаны на свойствах сингулярного разложения произвольных матриц и математическом аппарате иммунокомпьютинга.
Ниже представлены описания взаимосвязанного комплекса из 11 лабораторных работ, первые 5 лабораторных работ выполняются всеми студентами, из последующих 5 лабораторных работ студенты по желанию выбирают одну, которая является прикладной и завершающей.
|
||
Рисунок 1. Структурная схема иммунокомпьютинга
1. МАТРИЧНЫЕ ВЫЧИСЛЕНИЯ НА ОСНОВЕ УНИВЕРСАЛЬНОЙ СИСТЕМЫ MATLAB
1.1. Задание матриц
По умолчанию все числовые переменные в MATLAB считаются матрицами с комплексными числами. Скалярная величина есть матрица первого порядка, а векторы являются матрицами, состоящими из одного столбца. Матрицу можно ввести, задавая элементы матрицы или считывая данные из файла, а также в результате обращения к стандартной или написанной пользователем функции. Элементы матрицы в пределах строки отделяются пробелами или запятыми.
[ ] – квадратные скобки используются при задании матриц и векторов;
пробел служит для разделения элементов матриц;
, запятая применяется для разделения элементов матриц и операторов в строке ввода;
; точка с запятой отделяет строки матриц, а точка с запятой в конце оператора (команды) отменяет вывод результата на экран;
: двоеточие используется для указания диапазона (интервала изменения величины) и в качестве знака групповой операции над элементами матриц;
() круглые скобки применяются для задания порядка выполнения математических операций, а также для указания аргументов функций и индексов матриц;
. точка отделяет дробную часть числа от целой его части, а также применяется в составе комбинированных знаков;
… три точки и более в конце строки отмечают продолжение выражения на следующей строке;
% знак процента обозначает начало комментария.
Большую матрицу можно определить поэлементно при помощи оператора цикла или набрать ее в обычном редакторе в виде ASCII-файла (например, data.ext), а затем считать при помощи команды
>>load data.ext
В результате матрица будет присвоена переменной data.
1.2. Матричные вычисления
1.2.1.
Функции описания матриц
eye единичная матрица;
zeros нулевая матрица;
ones матрица из единиц;
rand случайная матрица со значениями из интервала [0,1];
hilb гильбертова матрица;
diag создание диагональной матрицы или выделение диагонали;
triu выделение верхней треугольной части матрицы;
tril выделение нижней треугольной части матрицы.
1.2.2.
Знаки операций
+,- символы плюс и минус обозначают знак числа или операцию сложения или вычитания матриц, причем матрицы должны быть одной размерности;
* знак умножения обозначает матричное умножение;
‘ апостроф обозначает операцию транспонирования (вместе с комплексным сопряжением);
/ левое деление;
правое деление;
^ оператор возведения в степень.
1.2.3.
Матричные характеристики
det вычисление определителя;
trace вычисление следа матрицы;
rank определение ранга матрицы;
norm вычисление нормы матрицы;
normest оценка нормы матрицы.
1.2.4.
Команды линейной алгебры
inv вычисление обратной матрицы;
pinv вычисление псевдообратной матрицы;
null определение ядра (нуль-пространства) матрицы;
orth вычисление ортонормированного базиса.
1.2.5.
Команды факторизации
chol разложение Холецкого для симметричных, положительно-определенных матриц;
cholnc неполное разложение Холецкого (представление симметричной матрицы в виде произведения верхней треугольной и транспонированной матриц);
lu LU-разложение (для квадратных матриц);
hess приведение к форме Хессенберга;
rref приведение к треугольной форме;
qr QR-разложение (представление матрицы в виде произведения ортогональной и верхней треугольной матриц).
1.2.6.
Команды вычисления спектра
poly вычисление характеристического полинома для квадратной матрицы. В результате выполнения команды будут получены коэффициенты нормированного характеристического полинома a
1
,
a
2
, ….,
an
:
det(pE – A)=pn
+a1
pn-1
+a2
pn-2
+ ….+ an
;
polyeig вычисление собственных значений матричного полинома;
eig вычисление собственных чисел и векторов;
schur декомпозиция (разложение) Шура;
svd сингулярное разложение матрицы (SVD-разложение).
Для определения собственных значений и собственных векторов матрицы А
служит команда
[U, D] = eig(A)
Здесь диагональная матрица D состоит из собственных чисел, а матрица U составлена из собственных векторов-столбцов матрицы А
. Если в левой части указан единственный выходной параметр, то результатом будет выступать вектор-столбец собственных чисел eig(A).
Функция svd определяет сингулярное разложение матрицы. Сингулярное число s и соответствующие ему векторы u и v матрицы А удовлетворяют равенствам
Av
=
su
,
A
Т
u
=
sv
.
Здесь A
Т
–
транспонированная матрица, s
– вещественное число. Образуем матрицу S
, в которой расположены на диагонали сингулярные числа. Тогда AV
=
US
,
A
Т
U
=
VS
,
и A
=
USV
Т
.
Диагональ матрицы S
состоит из положительных значений квадратных корней матрицы АТ
А.
Если матрица А
симметричная и положительно определенная, то сингулярные числа совпадают с собственными значениями матрицы А.
Вектор сингулярных чисел получается при обращении с одним выходным параметром S
=
svd
(А)
Для выполнения сингулярного разложения заданной матрицы А
служит команда
>>[
U
,
S
,
V
] =
svd
(
A
),
где U
,
V
–
соответственно, матрицы левых и правых сингулярных векторов, S
–
матрица сингулярных чисел.
1.3. Интегрирование MATLAB и Excel
Интегрирование MATLAB и Excel позволяет пользователю Excel обращаться к многочисленным функциям MATLAB для обработки данных, различных вычислений и визуализации результата. Надстройка excllink.xla реализует данное расширение возможностей Excel. Для связи MATLAB и Excel определены специальные функции.
1.3.1.
Конфигурирование Excel
Перед тем как настраивать Excel на совместную работу с MATLAB, следует убедиться, что Excel Link входит в установленную версию MATLAB. В подкаталоге exclink основного каталога MATLAB или подкаталога toolbox должен находиться файл с надстройкой excllink.xla. Запустите Excel и в меню Tools выберите пункт Add-ins. Откроется диалоговое окно, содержащее информацию о доступных в данный момент надстройках. Используя кнопку Browse, укажите путь к файлу excllink.xla. В списке надстроек диалогового окна появится строка Excel Link 2.0 for use with MatLab с установленным флагом. Нажмите OK, требуемая надстройка добавлена в Excel.
Обратите внимание, что в Excel теперь присутствует панель инструментов Excel Link, содержащая три кнопки: putmatrix, getmatrix, evalstring. Эти кнопки реализуют основные действия, требуемые для осуществления взаимосвязи между Excel и MATLAB— обмен матричными данными, и выполнение команд MATLAB из среды Excel. При повторных запусках Excel надстройка excllink.xla подключается автоматически.
Согласованная работа Excel и MATLAB требует еще нескольких установок, которые приняты в Excel по умолчанию (но могут быть изменены). В меню Tools перейдите к пункту Options, открывается диалоговое окно Options. Выберите вкладку General и убедитесь, что флаг R1C1 reference style выключен, т.е. ячейки нумеруются A1, A2 и т.д. На вкладке Edit должен быть установлен флаг Move selection after Enter.
1.3.2.
Обмен данными между MATLAB и Excel
Запустите Excel, проверьте, что проделаны все необходимые настройки так, как описано в предыдущем разделе (MATLAB должен быть закрыт). Введите в ячейки с A1 по C3 матрицу, для отделения десятичных знаков используйте точку в соответствии с требованиями Excel.
Рисунок 2 Пример ввода дробных чисел в Excel
Выделите на листе данные ячейки и нажмите кнопку putmatrix, появляется окно Excel с предупреждением о том, что MATLAB не запущен. Нажмите OK, дождитесь открытия MATLAB. Появляется диалоговое окно Excel со строкой ввода, предназначенной для определения имени переменной рабочей среды MATLAB, в которую следует экспортировать данные из выделенных ячеек Excel. Введите, к примеру, М и закройте окно при помощи кнопки OK. Перейдите к командному окну MATLAB и убедитесь, что в рабочей среде создалась переменная М, содержащая массив три на три:
Рисунок 3 Отображение массива М в командном окне.
Проделайте некоторые операции в MATLAB с матрицей М, например, обратите ее.
Вызов inv для обращения матрицы, как и любой другой команды MATLAB можно осуществить прямо из Excel. Нажатие на кнопку evalstring, расположенную на панели Excel Link, приводит к появлению диалогового окна, в строке ввода которого следует набрать команду MATLAB:
IM=inv(M)
Результат аналогичен полученному при выполнении команды в среде MATLAB.
Вернитесь в Excel, сделайте текущей ячейку A5 и нажмите кнопку getmatrix. Появляется диалоговое окно со строкой ввода, в которой требуется ввести имя переменной, импортируемой в Excel. В данном случае такой переменной является IM. Нажмите OK, в ячейки с A5 по A7 введены элементы обратной матрицы.
Итак, для экспорта матрицы в MATLAB следует выделить подходящие ячейки листа Excel, а для импорта достаточно указать одну ячейку, которая будет являться верхним левым элементом импортируемого массива. Остальные элементы запишутся в ячейки листа согласно размерам массива, переписывая содержащиеся в них данные, поэтому следует соблюдать осторожность при импорте массивов.
Вышеописанный подход является самым простым способом обмена информацией между приложениями — исходные данные содержатся в Excel, затем экспортируются в MATLAB, обрабатываются там некоторым образом и результат импортируется в Excel. Пользователь переносит данные при помощи кнопок панели инструментов Excel Link. Информация может быть представлена в виде матрицы, т.е. прямоугольной области рабочего листа. Ячейки, расположенные в строку или столбец, экспортируются, соответственно, в вектор-строки и вектор-столбцы MATLAB. Аналогично происходит и импорт вектор-строк и вектор-столбцов в Excel.
1.4. Программирование
1.4.1.
М-файлы
Работа из командной строки MATLAB затрудняется, если требуется вводить много команд и часто их изменять. Ведение дневника при помощи команды diary и сохранение рабочей среды незначительно облегчают работу. Самым удобным способом выполнения групп команд MATLAB является использование М-файлов, в которых можно набирать команды, выполнять их все сразу или частями, сохранять в файле и использовать в дальнейшем. Для работы с М-файлами предназначен редактор М-файлов. С его помощью можно создавать собственные функции и вызывать их, в том числе и из командного окна.
Откройте меню File основного окна MATLAB и в пункте New выберите подпункт M-file. Новый файл открывается в окне редактора M-файлов, которое изображено на рисунке 4.
Рисунок 4. Окнo редактора M-файлов
М-файлы в MATLAB бывают двух типов: файл-программы (Script M-Files
), содержащие последовательность команд, и файл-функции, (Function M-Files
), в которых описываются функции, определяемые пользователем.
1.4.2.
Файл-программа
Наберите в редакторе команды, приводящие к построению двух графиков на одном графическом окне
Рисунок 5 Команды файла в окне редактора.
Сохраните теперь файл с именем mydemo.m в подкаталоге work основного каталога MATLAB, выбрав пункт Save as меню File редактора. Для запуска на выполнение всех команд, содержащихся в файле, следует выбрать пункт Run в меню Debug. На экране появится графическое окно Figure 1
, содержащее графики функций.
Команды файл-программы осуществляют вывод в командное окно. Для подавления вывода следует завершать команды точкой с запятой. Если при наборе сделана ошибка и MATLAB не может распознать команду, то происходит выполнение команд до неправильно введенной команды, после чего выводится сообщение об ошибке в командное окно.
Очень удобной возможностью, предоставляемой редактором М-файлов, является выполнение части команд. Закройте графическое окно Figure 1. Выделите при помощи мыши, удерживая левую кнопку, или клавишами со стрелками при нажатой клавише Shift, первые четыре команды и выполните их из пункта Text. Обратите внимание, что в графическое окно вывелся только один график, соответствующий выполненным: командам. Запомните, что для выполнения части команд их следует выделить и нажать клавишу F9.
Отдельные блоки М-файла можно снабжать комментариями, которые пропускаются при выполнении, но удобны при работе с М-файлом. Комментарии начинаются со знака процента и автоматически выделяются зеленым цветом, например:
Рисунок 6 Команды файла с комментариями.
Открытие существующего М-файла производится при помощи пункта Open меню File рабочей среды, либо редактора М-файлов.
1.4.3.
Файл-функция
Рассмотренная выше файл-программа является только последовательностью команд MATLAB, она не имеет входных и выходных аргументов. Для использования численных методов и при программировании собственных приложений в MATLAB необходимо уметь составлять файл-функции, которые производят необходимые действия с входными аргументами и возвращают результат действия в выходных аргументах. Разберем несколько простых примеров, позволяющих понять работу с файл-функциями.
Для проведения предобработки данных многомерного анализа часто используют операцию центрирования
. Имеет смысл один раз написать файл-функцию, а потом вызывать его всюду, где необходимо производить центрирование. Откройте в редакторе М-файлов новый файл и наберите
Рисунок 7 Пример файла – функции.
Слово function в первой строке определяет, что данный файл содержит файл-функцию. Первая строка является заголовком функции, в которой размещается имя функции и списка входных и выходных аргументов. В примере имя функции centering, один входной аргумент X и один выходной — Xc. После заголовка следуют комментарии, а затем — тело функции (оно в данном примере состоит из двух строк), где и вычисляется ее значение. Важно, что вычисленное значение записывается в Xc. Не забудьте поставить точку с запятой для предотвращения вывода лишней информации на экран. Теперь сохраните файл в рабочем каталоге. Обратите внимание, что выбор пункта Save или Save as меню File приводит к появлению диалогового окна сохранения файла, в поле File name которого уже содержится название centering. Не изменяйте его, сохраните файл функцию в файле с предложенным именем!
Теперь созданную функцию можно использовать так же, как и встроенные sin, cos и другие. Вызов собственных функций может осуществляться из файл-программы либо из другой файл-функции. Попробуйте сами написать файл-функцию, которая будет шкалировать матрицы, т.е. делить каждый столбец на величину среднеквадратичного отклонения по этому столбцу.
Можно написать файл-функции с несколькими входными аргументами, которые размещаются в списке через запятую. Можно также создавать и функции, возвращающие несколько значений. Для этого выходные аргументы добавляются через запятую в список выходных аргументов, а сам список заключается в квадратные скобки. Хорошим примером является функция, переводящая время, заданное в секундах, в часы, минуты и секунды.
Рисунок 8 Команды функции перевода времени.
При вызове файл-функций с несколькими выходными аргументами результат следует записывать в вектор соответствующей длины.
1.4.4.
Создание графика
MATLAB имеет широкие возможности для графического изображения векторов и матриц, а также для создания комментариев и печати графиков. Приведем описание несколько важных графических функций.
Функция plot имеет различные формы, связанные с входными параметрами, например plot(y) создает кусочно-линейный график зависимости элементов y от их индексов. Если в качестве аргументов заданы два вектора, то plot(x,y) создаст график зависимости y от x.
Рисунок 9 Пример команд для построения графика функции sin в интервале от 0 до 2p
Программа построила график зависимости, который отображается в окне Figure 1
Рисунок 10 График функции sin в интервале от 0 до 2p
MATLAB автоматически присваивает каждому графику свой цвет (исключая случаи, когда это делает пользователь), что позволяет различать наборы данных.
Команда hold on позволяет добавлять кривые на существующий график. Функция subplot позволяет выводить множество графиков в одном окне
Рисунок 11. Пример использования функции subplot.
Рисунок 12. Результат использования функции subplot.
1.4.5.
Печать графиков
Пункт Print в меню File и команда print печатают графику MATLAB. Меню Print вызывает диалоговое окно, которое позволяет выбирать общие стандартные варианты печати. Команда print обеспечивает большую гибкость при выводе выходных данных и позволяет контролировать печать из М-файлов. Результат может быть послан прямо на принтер, выбранный по умолчанию, или сохранен в заданном файле.
1.5. Лабораторная работа № 1
Цель работы:
освоить операции матричного вычисления средствами универсальной системы MATLAB.
1.5.1.
Порядок выполнения работы
Средствами универсальной системы MATLAB получить для исходной матрицы А
размерности (3х3) следующие величины:
- транспонированную, псевдообратную, евклидову норму;
- собственные значения и собственные векторы;
- сингулярные числа, правые и левые сингулярные векторы.
1.5.2.
Оформление отчета
Отчетом о лабораторной работе является файл с именем, совпадающим с фамилией студента с результатами работы в папке Мои документы/номер группы.
1.5.3.
Контрольные вопросы
1. Что такое иммунокомпьютинг?
2. Перечислите основные вычислительные процедуры иммунокомпьютинга.
3. Свойства сингулярного разложения матриц.
4.
5.
6.
7.
8.
9.
10.
2. ВЫЧИСЛИТЕЛЬНАЯ ПРОЦЕДУРА СИНГУЛЯРНОГО РАЗЛОЖЕНИЯ МАТРИЦ
2.1. Математический аппарат
Как известно, для произвольной матрицы А
размерности (m
´
n)
существует так называемое сингулярное разложение, т.е. представление матрицы в виде
| A
|
(1)
|
где U
‑ (
m
´
m
)
и V
– (
n
x
n
)
– ортогональные квадратные матрицы, удовлетворяющие критерию ортогональности:
VVT
= VT
V = Em
´
m
, UUT
= UT
U = En
´
n
,
где E
‑
единичные матрицы соответствующих размерностей.
Матрица S
состоит из квадратного диагонального блока размерности r
´
r (r = min (m, n)
) с неотрицательными элементами на главной диагонали и, если , из дополнительных нулевых строк или столбцов
S = [S’
;0],
если m < n
,
S = [S’
;0]T
, если m > n
,
S = S’
, если m = n
,
S’
=
diag {s1
,s2
,…,sr
, s1
s2
…sr
}.
Числа si
,
i
= 1, 2,….,
r
называются сингулярными числами матрицы A
, которые определяются матрицей A
однозначно.
Сингулярное разложение вещественной прямоугольной матрицы A
в покомпонентной форме имеет следующее представление:
A
=
s
1
U
1
V
1
T
+
s
2
U
2
V
2
T
+ …. +
sr
Ur
Vr
T
, (2)
где s
i
–сингулярные числа матрицы A
, Ui
, Vi
– соответственно, правые и левые сингулярные векторы, r
–ранг матрицы. Эти сингулярные числа и сингулярные векторы удовлетворяют следующим соотношениям:
s
1
³
s
2
³
…,
sr
³
0
,
si
=
Ui
T
AVi
,
Ui
T
Ui
= 1,
Vi
T
Vi
= 1,
i
= 1,….,
r
. (3)
Известно, что процессы сингулярного разложения для любой вещественной матрицы А
обладают весьма полезными свойствами для теории и приложений, а именно, каждая матрица над полем вещественных чисел имеет вещественные сингулярные числа и векторы. Кроме того, сингулярное разложение матриц устойчиво к малым возмущениям матриц, т.е. сингулярное разложение каждой матрицы является хорошо обусловленной процедурой.
Относительно практических аспектов, сингулярное разложение матрицы в общем случае может быть получено по достаточно простой и надежной схеме:
VT
(k+1)
= UT
(k)
A,
V(k+1)
= V(k+1)
/ /V(k+1)
/
U(k+1) =
AV(k+1)
, U(k+1)
= U(k+1)
/ /U(k+1)
/
(4)
sk
=
UT
k
AVk
,
/
sk
+1
–
sk
/ ≤
ε
где k=0,1,2,... –
номер итерации, |
U
(
k
+1)
|
-
любая векторная норма, e
- заданная точность вычисления. Можно показать, что для произвольных начальных векторов U
(0)
,
V
(0)
итерации по схеме (4)
сходятся в общем случае к сингулярным векторам U
,
V
, соответствующим максимальному сингулярному числу s
max
=
U
T
A
V
.
Следуют отметить, что такие свойства не свойственны спектральному разложению, которое в действительности формирует основу для многомерного статистического анализа. В отличие от сингулярного разложения матриц, собственные числа и собственные векторы спектрального разложения являются вещественными только для вещественных симметрических матриц, в общем случае не симметрические вещественные матрицы обладают комплексным спектром и определить его не просто.
С использованием вышеприведенного итеративного алгоритма (4)
сингулярное разложение матрицы А
, представленное в форме (2,3)
может быть получено с использованием метода исчерпывания.
Сущность этого метода заключается в следующем:
· максимальное сингулярное число и соответствующие ему правый и левый сингулярный векторы матрицы А
вычисляются с помощью итеративного алгоритма (4).
Формируется матричная компонента А1
=
s
1
U
1
VT
1
;
· формируется матрица невязки
А2
= А ‑ А1
= А ‑
s
1
U
1
VT
1
, (5)
для которой максимальное сингулярное число и соответствующие ему правый и левый сингулярный векторы матрицы А2
вычисляются с помощью итеративного алгоритма (4)
и т.д.
2.2. Лабораторная работа № 2
Цель работы:
создание программного модуля для сингулярного разложения произвольной матрицы.
2.2.1.
Порядок выполнения работы
1. Открыть универсальную систему MATLAB.
2. Задать исходную матрицу А
размерности (3 х 4)
.
3. Используя команду для сингулярного разложения MATLAB, получить представление для матрицы А
через сингулярные числа, правые и левые сингулярные векторы в покомпонентной (в виде 2, 3
) и в векторно-матричной формах (в виде 1
).
4. Проверить условия ортогональности для вышеперечисленных форм представления.
5. Реализовать итеративную процедуру (4)
вычисления максимального сингулярного числа и соответствующих ему правого и левого сингулярных векторов при произвольно заданных начальных значениях левого сингулярного вектора U
0
и правого сингулярного вектора V
0
. Вычислить матричную компоненту, соответствующую найденным максимальному сингулярному числу и соответствующим ему правому и левому сингулярным векторам.
6. Используя процедуру метода исчерпывания, получить матричную невязку вида (5),
для которой выполнить все перечисленные операции пункта 4.
7. Сохранить все результаты выполнения работы в файле на диске.
2.2.2.
Пример выполнения лабораторной работы №2
В соответствии с п.2 формируем произвольную матрицу А
размерности (3×4
) с помощью генератора случайных чисел: A=
rand(3,4),
проверяем условия ортогональности: U*
UT
,
V*
VT
:
Получаем представление в покомпонентной форме:
- для первого слагаемого в (2) формируем следующие компоненты сингулярного разложения: первый левый сингулярный вектор ‑ U1=U(:,1), первое сингулярное число ‑ S1=S(1,1), первый правый сингулярный вектор ‑ V1=V(:,1), с использованием полученных компонент формируем первое слагаемое в (2): S1*U1*V1T;
- аналогично формируем компоненты сингулярного разложения для второго слагаемого: U2=U(:,2), S2=S(2,2), V2=V(:,2). Вычисляем второе слагаемое S2*U2*V2T и т.д.
В соответствии с п.4 для реализации итеративной процедуры вычисления максимального сингулярного числа и соответствующих правого и левого сингулярных векторов задаем исходные данные: матрицу А
размерности (3×4
), произвольные: левый сингулярный вектор U
0
размерности (3×1
), правый сингулярный вектор V
0
размерности (4×1
), число, характеризующее точность вычисления epsilon = 0.01. По заданным исходным данным вычисляем значение сингулярного числа S
0=
U
0
T
*
A
*
V
0.
Итеративный алгоритм включает следующие шаги:
Шаг 1.
V
1
T
=
U
0
T
*
A
,
V
1=
V
1/
norm
(
V
1) –
вычисление правого сингулярного вектора и его нормировка;
U
1=
A
*
V
1,
U
1=
U
1/
norm
(
U
1)‑
вычисление левого сингулярного вектора и его нормировка;
S
1=
U
1
T
*
A
*
V
1 –
вычисление сингулярного числа;
/
S
1-
S0/≤epsilon=0.01 – проверка точности определения сингулярного числа, если условие выполняется, то вычисленные компоненты запоминаются, как первые компоненты сингулярного разложения, в противном случае переходим к шагу 2.
Шаг 2.
V
2
T
=
U
1
T
*
A
,
V
2/
norm
(
V
2) –
вычисление правого сингулярного вектора и его нормировка;
U
2=
A
*
V
2,
U
2=
U
2/
norm
(
U
1)‑
вычисление левого сингулярного вектора и его нормировка;
S
2=
U
2
T
*
A
*
V
2 –
вычисление сингулярного числа;
/
S
2-
S1/≤epsilon=0.01 – проверка точности вычисления сингулярного числа и т.д.
Рисунок 13
После первой итерации модуль разности двух последующих сингулярных чисел не удовлетворяет заданной точности вычисления, поэтому необходимо следующие шаги до тех пор, пока неравенство не будет удовлетворено.
2.2.3.
Порядок оформления отчета
Отчетом о лабораторной работе №2 является файл с именем, совпадающим с фамилией студента с результатами работы в папке Мои документы/номер группы.
2.2.4.
Контрольные вопросы
1. Свойство сходимости вычислительной процедуры (4)
.
2. Преимущество сингулярного разложения матриц перед спектральным разложением матриц.
3. Условие останова итеративного алгоритма вычисления максимального сингулярного числа, правого и левого сингулярного вектора.
4. В чем заключается сущность метода исчерпывания?
5.
6.
7.
8.
9.
10.
3. ВЫЧИСЛИТЕЛЬНАЯ ПРОЦЕДУРА ОБУЧЕНИЯ С ЭКСПЕРТОМ
3.1. Математический аппарат
Пусть имеется сложная система (научная, техническая, экономическая и т.д.), которая может характеризоваться определенным набором признаков Xk
,
k = 1,2,3,….
Такой произвольный вектор значений признаков можно трактовать как образ, принадлежащий пространству признаков {X}
.
Множество образов представляется в виде множества векторов, состоящего из k
подмножеств или классов:
z1
={X}1
,..., zk
={X}k
.
Для процедуры обучения с экспертом исходной информацией служат векторы значений признаков ситуаций по каждому из рассматриваемых эталонных классов и сформированная на основе мнения эксперта обучающая выборка. Исследуя и анализируя указанным образом, ряд таких систем с привлечением эксперта-человека, можно на основании его знаний и личного опыта выстроить классификацию и оценить, к какому из классов принадлежит исследуемый объект. Набор признаков системы, перечисленный выше, эксперт может оценивать либо по 10-бальной системе, либо в пределах от 0 до 1, как в рассматриваемом ниже примере.
На основе полученной информации и с учетом мнения эксперта формируется обучающая выборка, которая представлена в таблице 1.
Таблица 1. Обучающая выборка
| Номер объекта |
Значения признаков |
Классификация эксперта |
||||
| z1
|
z
|
z3
|
|
zn
|
||
| 1 |
1 |
0,3 |
1 |
1 |
1 |
|
| 2 |
0,1 |
0,6 |
1 |
1 |
2 |
|
| 3 |
0,2 |
0,8 |
0,9 |
0,7 |
3 |
|
| 4 |
0,5 |
1 |
0,7 |
0,1 |
2 |
|
|
|
|
|||||
| : |
||||||
| L |
1 |
1 |
0,5 |
0,1 |
||
Задача обучения сводится к разбиению пространства признаков на классы (т.е. к проведению классификации), а задача распознавания сводится к определению класса zj
={
X
}j
, j=1,...,k,
с помощью векторной нормы:
zk
(X): mink
//X - {X}k
//.
В качестве векторной нормы могут быть использованы следующие известные нормы:
· евклидова норма //Xi
–
Xki
//Е
= (
Σi
(
Xi
–
Xki
)2
)1/2
;
· норма расстояния //Xi
–
Xki
//М
= (
Σi
/
Xi
–
Xki
/);
· норма Чебышева //Xi
–
Xki
//С
=
maxi
/
Xi
–
Xki
/.
В вычислительных процедурах иммунокомпьютинга в качестве аналога расстояния используется понятие энергии связи, основанное на сингулярном разложении матрицы. Энергия связи между объектами A
и M
представляется следующим образом:
ω
i
= - U Т
i
MVi
, Ui
T
Ui
= 1, Vi
T
Vi
= 1, i =1, ,r,
где Ui
, Vi
– соответственно, правые и левые сингулярные векторы
матрицы А
, r
–ранг матрицы.
Алгоритм вычислительной процедуры обучения с экспертом состоит их следующих шагов:
Шаг 1.
Сворачивание вектора в матрицу. Заданный вектор Х
размерности (
n
x
1)
сворачиваем в матрицу M
размерности nU
x
nV
=
n
.
Шаг 2.
Формируем матрицы A
1
,
A
2
,….,
Ak
для эталонных классов с = 1,…,к
и вычисляем их сингулярные векторы:
{
U
1
,
V
1
} –
для A
1
, {
U
2
,
V
2
}
- для A
2
, {
U
к
,
V
к
}
- для Ak
.
Шаг 3.
Распознавание. Для каждого входного образа М
вычисляем к
значений энергии связи между каждой парой сингулярных векторов:
ω1
= -
U
Т
1
MV
1
, ….., ω
k
= -
U
Т
к
MV
к
.
Шаг 4
. Определяем класс, к которому принадлежит входной образ М.
Минимальное значение энергии связи ω*
определяет этот класс,:
c
= ω*
=
minc
{ ω
c
}.
3.2. Лабораторная работа № 3
Цель работы:
создание программного модуля для реализации вычислительной процедуры обучения с экспертом на основе инструментария универсальной системы MATLAB.
3.2.1.
Порядок выполнения работы
1. Открыть универсальную систему MATLAB.
2.
Задать обучающие матрицы А
i
и матрицу М
размерности (4 х 3)
.
3.
Программно реализовать шаги 1-4 алгоритма вычислительной процедуры обучения с экспертом.
4. Сохранить все результаты выполнения работы в файле на диске.
3.2.2.
Порядок оформления отчета
Отчетом о лабораторной работе № 3 является файл с именем, совпадающим с фамилией студента с результатами работы в папке Мои документы/номер группы.
3.2.3.
Пример выполнения лабораторной работы №3
В соответствии с п. 2 формируем обучающие матрицы трех эталонных классов А
i
,
i
=1,2,3
размерности (4 х 3) и анализируемую матрицу М
размерности (4 х 3).
Рисунок 14 Обучающие матрицы трёх эталонных классов.
Для сформированных обучающих эталонных матриц А
i
,
i
=1,2,3
вычисляем первые левые и правые сингулярные векторы Ui
,
Vi
,
i
=1,2,3.
Рисунок 15
Используя эти компоненты, вычисляем значения энергии связи анализируемой матрицы М
с эталонными обучающими матрицами А
i
Рисунок 16
Из вычисленных значений энергии связи формируем множество W=[W11
, W21,
W31
], минимальное значение которого определяет принадлежность анализируемого объекта к соответствующему классу.
Вывод
: анализируемый объект относится к первому классу.
3.2.4.
Контрольные вопросы
1. Что такое энергия связи?
2. Роль эксперта при реализации вычислительной процедуры обучения с экспертом.
3. Что является мерой близости выбранного образа М
к конкретному классу?
4.
5.
6.
7.
8.
9.
10.
4. ВЫЧИСЛИТЕЛЬНАЯ ПРОЦЕДУРА ОБУЧЕНИЯ С ЭКСПЕРТОМ
4.1. Математическая формализация задачи
Отнесение различных векторов индикаторов к одному классу может рассматриваться как агрегация исходных данных, при этом геометрическая близость (расстояние) между объектами формализуется с помощью соответствующей векторной нормы. Наиболее распространенной является евклидова норма:
.
Следовательно, задача обучения сводится к разбиению пространства индикаторов на классы (т.е. к проведению классификации), а задача распознавания сводится к определению класса (т.е. к проведению кластеризации) zj
={
X}
j
,
j=1,…,
k
с помощью выбранной векторной нормы:
.
Как известно, с помощью векторной нормы можно определить понятие расстояния между вектором и классом, а также понятие расстояния между классами.
С точки зрения распознавания образов полагается, что чем меньше значение выбранной нормы, тем сходство между объектами больше.
Определим образ как n
-мерный вектор-столбец X=[
x1
,
x2
,…,
xn
]
, где x1
,
x2
,…,
xn
являются вещественными числами, и индекс T
является символом транспонирования матрицы.
Представим задачу распознавания образов как отображение f(
X)→{1,…,
c}
любого образа X
в одно из целых чисел 1,…,
c
, которые представляют классы.
Задача распознавания образов может быть сформулирована следующим образом:
Дано:
- Число классов c;
- набор из m обучающих образов: X1,….,Xm;;
- класс любого обучающего образа:f(X1)=c1…,f(Xm)=cm;
- произвольный n-мерный вектор P.
Найти:
Класс вектора P:
f(
P)=?
.
Для реальных задач исходные данные в самом общем случае являются многомерными и допускают представление в виде массивов (векторов) вещественных и/или целых чисел. Как было отмечено выше, одной из основных особенностей ИК-алгоритма распознавания образов является проекция произвольных данных в пространство ФИС. Такое преобразование обладает следующими преимуществами:
- имеет строгое математическое обоснование в терминах сингулярного разложения матриц;
- существенно снижает размерность данных (до одно- двух- или трехмерного пространства ФИС);
- позволяет наглядно представить и визуализировать любую ситуацию как точку одно- двух- или трехмерного пространства.
Рассмотрим математическое описание основных процедур алгоритма иммунокомпьютинга.
4.2. Обучение
1. Сформировать обучающую матрицу A=[
X1
,…,
Xm
]
T
размерности m×
n
.
2. Вычислить максимальное сингулярное число s
, а также левый и правый сингулярные векторы U
и V
обучающей матрицы по следующей итеративной (эволюционной) схеме:
до выполнения условия
3. Хранить сингулярное число s
.
4. Хранить правый сингулярный вектор V
как антитело-пробу.
5. Для всякого i=1,…,
m
хранить компоненту ui
левого сингулярного вектора U
(как клетку формальной иммунной сети) и класс ci
, соответствующий обучающему образу Xi
.
4.3. Распознавание
6. Для всякого n
-мерного образа Z
вычисляется энергия связи
с V
:
(напомним, что s
–хранимое сингулярное число, а V
– это хранимый правый сингулярный вектор обучающей матрицы A
).
7. Выбирается ui
, которая имеет минимальное расстояние (близость
) с энергией связи w
:
8. Считать класс ci
искомым классом образа Z
.
4.4. Замечания
Данное ядро алгоритма распознавания образов использует только максимальное (первое) сингулярное число s
и соответствующие ему сингулярные векторы U
и V
, которые вычисляются на шаге 2 данного алгоритма.
В общем случае, рекомендуется использовать первые три сингулярных числа и соответствующие им сингулярные векторы обучающей матрицы. Они могут быть вычислены по той же итеративной схеме (шаг 2) с использованием вычислительной процедуры метода исчерпывания:
1.Вычислить максимальное сингулярное число s1
и соответствующие ему сингулярные вектора U1
и V1
обучающей матрицы на шаге 2.
2.Сформировать матрицу A2
=
A‑
s1
U1
V1
и вычислить ее максимальное сингулярное число s2
и соответствующие ему сингулярные векторы U
2
и V2
посредством шага 2.
3.Сформировать матрицу A3
=
A –
s2
U2
V2
и вычислить ее максимальное сингулярное число s3
и соответствующие ему сингулярные векторы U3
и V3
посредством шага 2.
Затем вычислить 3 значения энергии связи с п
Определить класс ci
на шаге 8 посредством определения минимального расстояния в трехмерном Евклидовом пространстве на шаге 7:
,
где являются i
-ми компонентами левых сингулярных векторов U1
, U2
,
U3
.
Отметим, что шаги 2 и 3 над матрицами A2
и A3
обеспечивают более точную аппроксимацию обучающей матрицы, согласно следующему свойству сингулярного разложения:
где – ранг матрицы A
.
Следует также отметить, что данный алгоритм иммунокомпьютинга может быть рассмотрен как «иммунный» алгоритм, так как любой образ может быть представлен как частный случай формального протеина и его распознавание основывается на энергии связи с антителом формального протеина.
4.5. Лабораторная работа № 4
Цель работы:
создание программного модуля для реализации вычислительной процедуры обучения с экспертом на основе инструментария универсальной системы MATLAB.
4.5.1.
Порядок выполнения работы
1. Открыть универсальную систему MATLAB.
2.
Задать исходную матрицу А
соответствующей размерности и матрицу анализируемого объекта М
. Программно реализовать шаги 1-8
алгоритма вычислительной процедуры обучения с экспертом.
3. Сохранить все результаты выполнения работы в файле на диске.
4.5.2.
Порядок оформления отчета
Отчетом о лабораторной работе № 4 является файл с именем, совпадающим с фамилией студента с результатами работы в папке Мои документы/номер группы.
4.5.3.
Пример выполнения лабораторной работы №4
Рассмотрим решение задачи классификации (задачи обучения с экспертом) на примере классификации легковых автомобилей.
Пусть имеется обучающая выборка в виде матрицы R
размерности (3×33). Эта матрица в качестве элементов имеет индикаторы, характеризующие три класса легковых автомобилей (второй, пятый и шестой):
Рисунок 17 Обучающая выборка в виде матрицы R
размерности (3×33).
Сингулярное разложение обучающей матрицы R осуществляется c помощью оператора: [U S V]=svd(R).
Ниже представлены матрицы компонент сингулярного разложения:
Рисунок 18 Матрицы компонент сингулярного разложения
Анализируемый объект представляется в виде вектора М:
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, классов в пространстве ФИС.
Рисунок 19 Результаты вычислений значений энергии
Из полученного множества значений расстояний от точки в пространстве ФИС, характеризуемой анализируемый объект до точек, характеризующих соответственно, классы 2, 5, 6:
d
={
d
2,
d
5,
d
6}={1.0090, 0.4082, 1.2202}
выбираем наименьшее значение, которое равно 0.4082. Это значение определяет принадлежность анализируемого объекта к 5 классу.
Вывод
: анализируемый объект принадлежит к 5 классу.
4.5.4.
Контрольные вопросы
1. Какая норма была использована при проведении классификации?
2. Сущность вычислительной процедуры автоматической классификации.
3. Можно ли назвать рассмотренную процедуру обучения с экспертом интеллектуальной процедурой?
4.
5.
6.
7.
8.
9.
10.
5. ФОРМИРОВАНИЕ ИНДЕКСОВ РИСКА
5.1. Описание задачи формирования индексов
Индексом сложной многомерной системы является общая величина, которая объединяет большое количество особых множителей (факторов) или переменных величин, называемых индикаторами. В некоторых случаях такой индекс является единственным путем представления текущего состояния системы и ее динамики, по которым возможно оценить активность системы и предсказать риски и тенденции. Например, риски деловой активности, такие как Dow-Jones или NASDAQ, широко используются в экономике и финансах. Как правило, такие индексы были введены на основе эмпирических соображений, некоторые из них рассчитываются достаточно легко, как среднее арифметическое последовательностей определенных переменных. К примеру, The Standard and Poor Index применяет стоимость к среднему представлению 500 акций на Нью-Йоркской фондовой бирже в течение дня. The Retail Price Index, как другой пример, измеряет среднее увеличение цены обычной сети продуктов питания в Великобритании.
Аналогичные индексы являются такими же важными, как в экономике, так и в других областях, например, в медицине.
5.2. Базовый алгоритм вычисления индекса
Пусть состояние многомерной системы характеризуется вектором индикаторов X
=[
x1
,…,
xn
]
. Пусть имеется набор из m
векторов Xk
,
k=1,2,…,
m,
с известными значениями индикаторов. Предлагается следующий базовый алгоритм вычисления индекса данной системы.
1. По исходным данным формируется матрица A=[
X1
,…,
Xm
]
T
размерности m×
n
, где m
– количество объектов, которые соответствуют строкам матрицы, а n
– количество параметров (индикаторов), которые соответствуют столбцам матрицы.
2. Методом сингулярного разложения матрицы A
вычисляется k
-й правый сингулярный вектор Vk
=[
ν1
,…,
νn
]
k
, который соответствует k
-му сингулярному числу матрицы sk
.
3. Для любого входного (распознаваемого) вектора Z
размерности n×1
вычисляется его энергия связи с вектором Vk
=[
ν1
,…,
νn
]
k
:
(1)
4. Искомое значение индекса вычисляется по следующей формуле:
Ik
(
Z
)=
c
0
+
c
1
ωk
.
(2)
Рассмотрим важное математическое свойство базового алгоритма.
Предложение 1.
Если входной вектор совпадает со строкой матрицы A
:
то значение
энергии
связи
в точности совпадает с соответствующей компонентой левого сингулярного вектора Uk
=[
u1
,….,
um
]
k
: ω
k
(
Ai
)=
uki
.
Значения коэффициентов c0
и c1
индекса Ik
(
Z)
, а также номер k
правого сингулярного вектора в уравнении (2) могут определяться двумя способами:
1) экспериментально (на основе экспертных оценок) в соответствии с особенностью приложения;
2) как решение задачи параметрической оптимизации для определения значений коэффициентов индекса.
Рассмотрим решение второй задачи на основе среднеквадратического критерия качества.
Пусть имеется матрица
M=[
ωkj
]
размерности (
p×
m)
, где k=1,…,
p
и p
– количество сингулярных векторов, используемых для расчета индекса, а j=1,…,
m
и m
– количество обучающих векторов. При этом значение элементов данной матрицы вычисляются по формуле (1) базового алгоритма для обучающих векторов.
Представим задачу в векторно-матричном виде:
MC=
B,
(3)
где C
‑ вектор коэффициентов индекса размерности (
m×1)
:
C=[
cm
-1
,…,
c1
,
c0
]
T
,
вектор B
‑ вектор размерности (
p×1)
, компонентами которого являются заданные значения индекса для обучающей выборки:
B=[
b1
,…,
bp
]
T
.
Рассмотрим сингулярное разложение матрицы M
:
(4)
Определим матрицу M+
следующим образом:
(5)
Предложение 3.
Матрица M+
определяет решение уравнения (3) в следующем виде:
C=
M+
B
. (6)
Доказательство:
Умножим обе части уравнения (6) слева на матрицу M+
:
M+
MC=
M+
B
. (7)
Умножим обе части полученного уравнения (7) слева на матрицу M
:
MM+
MC=
MM+
B.
(8)
Учитывая в левой части (8) условие М+
М=Е
, получаем
,
где ‑ нулевой вектор размерности (
p×1)
.
Так как исходная матрица М
тождественно не равна нулю, получаем решение (6), что доказывает справедливость Предложения.
Предложение 4.
Формула (6) дает решение уравнения (3) в смысле минимума среднеквадратической ошибки:
Q= (
MC ‑
B)
T
(
MC ‑
B).
(9)
Доказательство:
Для доказательства определим в явном виде вектор коэффициентов C
таким образом, чтобы минимизировать квадратичный критерий качества (9):
По правилам векторно-матричного дифференцирования, возьмем производную от Q
по C
и приравняем ее нулю:
(10)
Из полученной системы алгебраических уравнений (10) определим вектор коэффициентов C
:
(11)
Получим выражение для правой части (11) через компоненты сингулярного разложения.
Транспонированная матрица MT
имеет следующий вид:
(12)
Сформируем произведение MT
M
:
С учетом условий ортогональности для правых и левых сингулярных векторов получим:
(13)
Так как матрица (13) симметричная, то обратная матрица представляется в виде
(14)
Сравнивая (14) с (5) получаем:
M+
= (
MT
M)-1
MT
,
что и требовалось доказать.
Матрица M+
называется псевдообратной матрицей (Мура-Пенроуза) для матрицы M
. В зависимости от соотношения размерностей выражение для нахождения псевдообратной матрицы будет различным:
· при p≥
m
;
· при p<m
;
· M+
=
M-1
при p=
n
(псевдообратная матрица равна обратной матрице).
На основе сингулярного разложения, нетрудно проверить, что матрица M+
удовлетворяет следующим четырем условиям Мура-Пенроуза [9]:
.
Важным свойством представления M+
через компоненты сингулярного разложения является то, что задача определения оптимальных коэффициентов C
индекса решается на основе сингулярного разложения матрицы M
, которое выполняется теми же процедурами базового алгоритма вычисления индекса.
Выражение для оптимального вектора коэффициентов C
через компоненты сингулярного разложения имеет вид:
(14)
Ниже представлены частные случаи процедуры формирования индекса с использованием компонент сингулярного разложения матрицы
М
.
5.3. Одномерный линейный случай
Для этого случая обучающая система уравнений (2) имеет следующий вид:
. (15)
При векторно-матричном представлении этой системы матрица M=
M1
, где матрица M1
размерности (
m×2)
и вектор коэффициентов C1
размерности (2×1)
имеют следующий вид:
(16)
5.4. Лабораторная работа № 5
Цель работы:
создание программного модуля для формирования индексов риска на основе инструментария универсальной системы MATLAB.
Рисунок 20
Рисунок 21
5.4.1.
Порядок выполнения работы
5.4.2.
Порядок оформления отчета
5.4.3.
Контрольные вопросы
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
6. ТЕСТИРОВАНИЕ ПОЛУПРОВОДНИКОВЫХ ЛАЗЕРНЫХ ДИОДОВ НА ОСНОВЕ ИНСТРУМЕНТАРИЯ УНИВЕРСАЛЬНЫХ СИСТЕМ MATLAB
6.1. Описание задачи
Полупроводниковые лазерные диоды способны генерировать большую мощность оптических импульсов в пикосекундах, требуемых в различных приложениях, таких как высокое разрешение лазерных измерителей время пролета дистанции, лазерной томографии и т.д. Ниже рассматривается лазерный диод GaAs/AlGaAs с модуляцией усиления, с двойной гетероструктурой и одной возможной преградой (помехой), объединенной с активной областью. Показано, что оптическая энергия в этой преграде может быть значительно увеличена. Также было принято предположение, что присутствие нескольких потенциальных барьеров могло бы увеличить дополнительную излучаемую оптическую энергию. Вычислительная имитация для структуры с тремя барьерами показывает, что оптические ответы структуры строго зависят от параметров всех барьеров, и эта зависимость является гораздо меньше, чем для структуры с одним или двумя барьерами.
Для создания лазерного диода, сначала необходимо удостовериться, что выбранная структура является оптимальной. Очевидно, что создание и тестирование различных структур является дорогостоящим процессом, который также отнимает много времени. С одной стороны, традиционные методы симуляции лазерной динамики (например, вычислительная физика) являются такими же дорогостоящими и время поглощающими, в результате чего также невозможно протестировать достаточное количество исходных данных. Для того, чтобы синтезировать структуру лазерного диода, который обеспечил бы максимальную мощность оптической энергии, необходимы новые нестандартные вычислительные подходы.
6.2. Тестовые данные
Тестовые данные для структуры лазерного диода с тремя барьерами приведены в таблице 5. Эти данные были получены с использованием методов вычислительной физики. Следует отметить, что для такой структуры лазерного диода до сих пор не существует экспериментальных результатов. Однако вычислительные результаты для более простой структуры, которая имеет только один внутренний барьер, хорошо согласуются с экспериментальными структурами.
Как утверждалось выше, оптическая энергия зависит от свойств внутренних барьеров лазерного диода. Входными данными являются значения этих барьеров и процентное отношение алюминия в тернарном решении AlGaAs, которые определяют возмещение энергии этих барьеров. Поэтому, индикаторы определены следующим образом:
- x1 и x5 являются процентным отношением алюминия в генераторах электронов и отверстий соответственно;
- x2, x3 и x4 являются процентным отношением алюминия в 1-ом, 2-ом и 3-ем внутренних барьерах соответственно.
Число класса (индекса) соответствует выходной оптической мощности в отклике к наносекундному текущему импульсу с амплитудой в 3.2 А, а именно:
- класс 1: 0-2 Вт;
- класс 2: 2-3 Вт;
- класс 3: 3-4 Вт;
- класс 4: 4-5 Вт;
- класс 5: 5-6 Вт;
- класс 6: 6-7 Вт;
- класс 7; более, чем 7 Вт.
В таблице 5 представлены первые 15 структур, которые были использованы как обучающие образы (выделены жирным).
Таблица 2Оптическая мощность различных структур лазерного диода
|
|
|
|
|
|
|
Класс
(оптическая мощность)
|
| 1 |
40 |
40 |
30 |
30 |
40 |
1
|
| 2 |
40 |
20 |
40 |
30 |
40 |
1
|
| 3 |
40 |
30 |
55 |
40 |
40 |
1
|
| 4 |
30 |
40 |
40 |
30 |
55 |
1
|
| 5 |
40 |
30 |
40 |
30 |
40 |
2
|
| 6 |
40 |
40 |
40 |
30 |
55 |
3
|
| 7 |
40 |
40 |
30 |
40 |
40 |
3
|
| 8 |
40 |
20 |
30 |
40 |
40 |
4
|
| 9 |
40 |
30 |
40 |
55 |
40 |
4
|
| 10 |
40 |
30 |
40 |
40 |
40 |
4
|
| 11 |
55 |
40 |
40 |
30 |
30 |
4
|
| 12 |
30 |
40 |
40 |
30 |
30 |
5
|
| 13 |
40 |
40 |
40 |
30 |
40 |
6
|
| 14 |
55 |
40 |
40 |
30 |
55 |
6
|
| 15 |
40 |
40 |
40 |
30 |
30 |
7
|
| 16 |
30 |
40 |
40 |
30 |
40 |
? |
| 17 |
40 |
40 |
40 |
20 |
40 |
? |
| 18 |
40 |
40 |
40 |
40 |
40 |
? |
| 19 |
40 |
20 |
40 |
40 |
40 |
? |
6.3. Лабораторная работа № 6
Цель работы:
создание программного модуля для реализации вычислительной процедуры проведения тестирования полупроводниковых лазерных диодов на основе инструментария универсальных систем MATLAB.
6.3.1.
Порядок выполнения работы
1. Открыть универсальную систему MATLAB.
2.
Из таблицы 5 сформировать обучающую матрицу размерности 7×5 для решения задачи тестирования.
3.
Реализовать вычислительную процедуру обучения с экспертом (использовать программный модуль лабораторной работы №3).
4.
Реализовать вычислительные процедуры самообучения и формирования индекса риска с оптимальными коэффициентами (использовать программный модуль лабораторной работы №4).
5.
Вычислить оптимальный вектор индекса, построить график изменения индекса.
6. Сохранить все результаты выполнения работы в файле на диске.
6.3.2.
Порядок оформления отчета
Отчетом о лабораторной работе № 6 является файл с именем, совпадающим с фамилией студента с результатами работы в папке Мои документы/номер группы.
6.3.3.
Контрольные вопросы
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
7. ПРОВЕДЕНИЕ ЭКСПЕРТИЗЫ НАУЧНО-ТЕХНИЧЕСКИХ ПРОЕКТОВ
7.1. Описание задачи
Проведение экспертизы научно-технических проектов, получение экспертных оценок и прогнозов является весьма важной задачей при проведении различного рода тендеров. Процедуры оценки и прогнозирования функционируют в условиях, как неполноты, так и субъективности информации, связанной с присутствием в системе человеческого фактора. Разнообразие, большой объем и противоречивость данных, используемых при экспертизе, предопределяют применение новых информационных технологий искусственного интеллекта при разработке процедур обучения, узнавания и принятия решений в условиях неопределенности.
Интеллектуальные системы оказывают все большее влияние на сферы человеческой деятельности, в которых возможность решать сложные трудно формализуемые задачи, связана с наличием разнообразных знаний о рассматриваемой предметной области. Здесь просматриваются три положительных момента:
1 – знания получают технологическую основу, благодаря интеллектуальной системе, которая сначала получает знания от эксперта, а затем применяет их и формирует новые знания;
2 – активизируется деятельность по сбору, организации, хранению, передаче и использованию человеческих знаний, что ведет к расширению и уточнению знаний самих по себе;
3 – просматривается принципиальная возможность выявления знаний из накопленного опыта, что открывает совершенно новые перспективы по организации и переработке знаний.
Остановимся на функциях эксперта, которым может являться высококвалифицированный специалист, обладающий огромным багажом знаний, в том числе и индивидуальных личных знаний. Такие знания в значительной степени состоят из эмпирических правил, называемых эвристиками. Именно эвристики позволяют эксперту при необходимости выдвигать разумные предложения, находить перспективные подходы к решаемым задачам и эффективно работать при неточных и неполных данных. Поэтому при создании интеллектуальной системы одной из главных проблем является извлечение знаний у эксперта и придание им формы, позволяющей использовать знания в компьютерной обработке.
Чтобы понять, как работает эксперт, полезно рассмотреть различие между знанием и умением. Умелое выполнение некоторой задачи часто обладает многими чертами, которые не свойственны работе хорошо информированного, но неумелого человека. В их число входят большая скорость или другой показатель эффективности, меньшее число ошибок, меньшая умственная напряженность (требования к вниманию), большая приспособляемость и робастность (устойчивость к сбоям). В этих чертах проявляются как сами знания, так и техника их использования.
Рассмотрим в качестве предметной области экспертизу проектов, которыми могут быть научные, технические, экономические, экологические и другие проекты. Каждый проект характеризуется определенным набором признаков или характеристик. В качестве примера можно указать следующий набор признаков:
1) срок реализации проекта;
2) стоимость проекта;
3) потребность проекта в трудовых ресурсах;
4) источники финансирования проекта:
- собственные источники финансирования,
- потребность в заемных средствах,
- обслуживание кредитов: сумма кредита, процентная ставка, срок кредита, порядок выплат;
5) производственный план:
- стоимость основных вложений в производство,
- мощности производства, используемые в проекте,
- стоимость производства,
- оценка себестоимости производства единицы продукции,
- прибыльность выпускаемой продукции,
- поставщики сырья и нового оборудования;
6) финансовая рентабельность проекта:
- потоки денежных средств,
- уровень рентабельности продукции,
- срок окупаемости,
- рентабельность собственного капитала,
- рентабельность активов,
- рентабельность инвестиций,
- коэффициент платежеспособности;
7) выгоды от реализации проекта:
- создание новых рабочих мест,
- освоение передовых технологий.
Интеллектуальная система, позволяющая провести комплексную экспертизу проекта и сформировать оценку качества этого проекта, должна на первых порах использовать опыт и знания эксперта, рассматривая эталонные проекты. А затем, обладая способностью к самообучению, узнаванию и принятию решений в условиях неопределенности и неполноты информации, должна формировать комплексную оценку рассматриваемого проекта, по качеству не уступающую оценке эксперта. Такие возможности предоставляют так называемые искусственные иммунные системы, основанные на принципах обработки информации биологической иммунной системой.
Рассмотрим, как можно использовать алгоритмы иммунокомпьютинга для комплексной экспертизы проектов. Как уже сказано ранее, пусть имеется некоторый проект (научный, технический, экономический), который характеризуется определенным набором признаков Xk
,
k = 1,2,3,…,
N.
Такой произвольный вектор значений признаков можно трактовать как образ, принадлежащий пространству признаков {X}
. Множество образов представляется в виде множества векторов, состоящего из k
подмножеств или классов:
z1
={X}1
,..., zk
={X}k
.
Исследуя и анализируя указанным образом ряд проектов с привлечением эксперта-человека, можно на основании его знаний и личного опыта выстроить классификацию и оценивать качество представленных проектов как низкое (оценка=3), среднее (оценка=2) и высокое (оценка=1). Набор признаков проекта, перечисленный выше, эксперт может оценивать либо по 10-бальной системе, либо в пределах от 0 до 1, как в нашем примере. На основе полученной информации и с учетом мнения эксперта формируется обучающая выборка.
7.2. Лабораторная работа № 7
Цель работы:
создание программного модуля для реализации вычислительной процедуры проведения экспертизы научно-технических проектов на основе инструментария универсальных систем MATLAB.
7.2.1.
Порядок выполнения работы
1. Открыть универсальную систему MATLAB.
2.
Получить у преподавателя таблицу с обучающей выборкой для решения задачи проведения экспертизы научно-технических проектов.
3.
Реализовать вычислительную процедуру обучения с экспертом (использовать программный модуль лабораторной работы №3).
4.
Реализовать вычислительную процедуру самообучения (использовать программный модуль лабораторной работы №4).
5.
Представить результаты решения задачи проведения экспертизы научно-технических проектов.
6.
Оформить тематическую заглавную страницу лабораторной работы № 7.
7. Сохранить все результаты выполнения работы в файле на диске.
7.2.2.
Порядок оформления отчета
Отчетом о лабораторной работе № 7 является файл с именем, совпадающим с фамилией студента с результатами работы в папке Мои документы/номер группы.
7.2.3.
Контрольные вопросы
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
8. КОМПЛЕКСНАЯ ЭКСПЕРТИЗА ВНУТРИВУЗОВСКИХ СИСТЕМ УПРАВЛЕНИЯ КАЧЕСТВОМ ОБРАЗОВАНИЯ
8.1. Описание задачи
Качество подготовки специалистов в современных условиях является одной из важнейших задач, определяющих как востребованность выпускников социальной практикой, так и конкурентоспособность учебного заведения на рынке образовательных услуг.
В последнее время “традиционные” подходы по осуществлению контроля качества образования стали трансформироваться в создание систем качества
(управления качеством, обеспечения качества), суть которых сводится к установлению степени соответствия заданным целям при помощи самооценки деятельности образовательного учреждения, дополненное суждением внешних экспертов. Процедуры самооценки качества подготовки выпускников функционируют в условиях, как неполноты, так и субъективности информации, связанной с присутствием в системе человеческого фактора.
В свою очередь разнообразие, большой объем и противоречивость данных, используемых при этом, предопределяют применение новых информационных технологий искусственного интеллекта, важное место, среди которых занимают методы распознавания и классификации образов.
Интеллектуальные системы, к числу которых относятся искусственные иммунные системы, оказывают все большее влияние на такие сферы человеческой деятельности как образовательная деятельность, в которых возможность решать сложные трудно формализуемые задачи, связана с наличием разнообразных аспектов, затрудняющих формализацию задачи, в рассматриваемой предметной области.
Здесь можно отметить три положительных момента:
- благодаря интеллектуальной системе информация, полученная от эксперта, приобретает технологическую основу, которая позволяет применять и формировать новые знания;
- деятельность по сбору информации, ее организации, хранению, передаче и использованию активизируется, что ведет к расширению и уточнению самих знаний;
- просматривается принципиальная возможность использования накопленного банка данных и знаний, что открывает совершенно новые перспективы по организации и переработке полученной информации о качестве образования.
Остановимся на функциях эксперта, оценивающего качество образовательной деятельности вуза и которым может являться высококвалифицированный специалист, обладающий огромным багажом знаний, в том числе и индивидуальных личных. Такие знания в значительной степени состоят из эмпирических правил, называемых эвристиками. Именно эвристики позволяют эксперту при необходимости выдвигать разумные предложения, находить перспективные подходы к решаемым задачам и эффективно работать при неточных и неполных данных. Поэтому при создании интеллектуальной системы одной из главных проблем является извлечение знаний у эксперта и придание им формы, позволяющей использовать его знания при реализации вычислительных процедур обучения с экспертом и самообучения иммунокомпьютинга.
Рассмотрим в качестве предметной области экспертизу внутри вузовских систем качества. Каждая система представляется определенным набором критериев, характеризующих:
ВОЗМОЖНОСТИ:
- роль руководства в организации работ по обеспечению качества подготовки специалистов;
- использование потенциала преподавателей, сотрудников, обучаемых;
- планирование в области качества подготовки специалистов;
- рациональное использование ресурсов.
РЕЗУЛЬТАТЫ:
- удовлетворенность преподавателей и сотрудников работой в вузе;
- удовлетворенность потребителей качеством подготовки специалистов вуза;
- влияние вуза на общество;
- результаты итоговой аттестации выпускников вуза.
Интеллектуальная система, позволяющая провести комплексную экспертизу системы качества и сформировать оценку этой системы, может работать в двух режимах: обучения с экспертом и обучения без эксперта (самообучения). В режиме обучения с экспертом она использует опыт и знания эксперта. В режиме самообучения на основе исходной информации о значениях критериев (индикаторов), характеризующих качество подготовки специалистов, обладая способностью к узнаванию и принятию решений в условиях неопределенности и неполноты информации, формирует комплексную оценку рассматриваемой системы, по качеству не уступающую оценке эксперта.
8.2. Лабораторная работа № 8
Цель работы:
создание программного модуля для реализации вычислительной процедуры проведения комплексной экспертизы внутри вузовских систем управления качеством образования на основе инструментария универсальных систем MATLAB.
8.2.1.
Порядок выполнения работы
1. Открыть универсальную систему MATLAB.
2. Получить у преподавателя таблицу с обучающей выборкой для решения задачи проведения экспертизы внутри вузовских систем управления качеством образования.
3. Реализовать вычислительную процедуру обучения с экспертом (использовать программный модуль лабораторной работы №3).
4.
Реализовать вычислительную процедуру самообучения (использовать программный модуль лабораторной работы №4).
5.
Представить результаты решения задачи проведения экспертизы внутри вузовских систем управления качеством образования.
6.
Оформить тематическую заглавную страницу лабораторной работы № 8.
7. Сохранить все результаты выполнения работы в файле на диске.
8.2.2.
Порядок оформления отчета
Отчетом о лабораторной работе № 8 является файл с именем, совпадающим с фамилией студента с результатами работы в папке Мои документы/номер группы.
8.2.3.
Контрольные вопросы
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
9. АЛГОРИТМ ФОРМИРОВАНИЯ ЭЛЕКТРОННОЙ ЦИФРОВОЙ ПОДПИСИ
9.1. Описание задачи
В наше время Internet становится все более обыденным и хорошо известным. Многие пользователи, компании подключаются к глобальной сети Internet для того, чтобы воспользоваться ее ресурсами и преимуществами для получения или обмена любого рода информации. Во многих случаях понятием «информация» обозначают специальный товар, который можно приобрести, продать, обменять на что-то другое и т.п. При помощи средств, предоставляемых Internet любой пользователь, подключенный к ее сети, становится малой ячейкой во всемирной “паутине”, объединившей мир. В связи с этим возникает острая необходимость в разработке эффективных аппаратных или программных средств для обеспечения защиты компьютерных систем обработки и хранения информации от несанкционированного доступа извне. Одним из таких средств безопасности передаваемых данных является аутентификация автора электронного документа и самого электронного документа, т.е. установление подлинности автора и отсутствия изменений в полученном документе. В настоящее время, в компьютерных сетях для аутентификации текстов, передаваемых по телекоммуникационным каналам, используется электронная цифровая подпись, которая в принципе аналогична обычной рукописной подписи и следовательно обладает ее основными достоинствами:
- удостоверяет, что подписанный текст исходит от лица, поставившего подпись;
- не дает самому этому лицу возможности отказаться от обязательств, связанных с подписанным текстом;
- гарантирует целостность подписанного текста.
Цифровая электронная подпись представляется в виде относительно небольшого количества дополнительной цифровой информации, передаваемой вместе с подписываемым текстом.
Система электронной цифровой подписи включает в себя две процедуры:
1) процедуру постановки подписи
, в которой отправитель прежде всего вычисляет хэш-функцию h
(
M
)
подписываемого текста M
. Вычисленное значение хэш-функции h
(
M
)
представляет собой один короткий блок информации m
, характеризующий весь текст M
в целом. Затем число m
шифруется секретным ключом отправителя. Получаемая при этом пара чисел представляет собой электронную цифровую подпись для данного текста M
.
2) процедуру проверки подписи
, при которой получатель сообщения снова вычисляет хэш-функцию m = h(M)
принятого по каналу текста M
, после чего при помощи открытого ключа отправителя проверяет, соответствут ли полученная подпись вычисленному значению m
хэш-функции.
Как видно, в обеих процедурах системы электронной цифровой подписи участвует алгоритм хеширования исходного текста M
, т.е. по существу сжатия подписываемого документа M
произвольной длины до фиксированной длины в несколько десятков или сотен бит. Следует отметить, что хэш-функция должна удовлетворять целому ряду условий:
- хэш-функция должна быть чувствительна к всевозможным изменениям в тексте M, таким как вставки, выбросы, перестановки и т.п.;
- хэш-функция должна обладать свойством необратимости, то есть задача подбора документа M’, который обладал бы требуемым значением хэш-функции, должна быть вычислительно неразрешима;
- вероятность того, что значения хэш-функций двух различных документов (вне зависимости от их длин) совпадут, должна быть ничтожно мала.
- Вычислительный алгоритм безопасного хэширования на основе использования процедур обучения иммунокомпьютинга состоит из следующих шагов:
Шаг 1.
Представим текстовую информацию исходного текста M
в виде множества отдельных букв I
, т.е. в виде:
I = {
i1
,
i2
,…,
ik
}
(1)
и сопоставим в строгое соответствие каждой букве ik
определенную цифру ak
, т.е. вместо буквенного множества (1)
в результате получим цифровой ряд вида:
A = {
a1
,.. ,
ak
}
(2)
Шаг 2
. Сформируем определенным образом из ряда (2)
матрицу A
размерности (s
x
q)
.
Шаг 3.
Сгенерируем случайным образом набор цифр bk
. В качестве примера возьмем формулу генератора случайных чисел вида: bk
= (
p+
k)2
/100
, т.е. получим цифровой ряд вида:
B = {
b1
, ….,
bk
}.
(3)
Шаг 4.
Сформируем из ряда (3)
матрицу B
одинаковой с матрицей A
размерности (s
x
q)
.
Шаг 5.
Осуществим сингулярное разложение матрицы А,
т.е. определим множества сингулярных чисел, правых и левых сингулярных векторов:
{s1
, s2,
sd
}, {U1
, U2
,…Ud
}, {V1
, V2
,….,Vd
}.
Шаг 6.
Вычислим значение энергии связи w.
Результатом хэширования будет величина l
равная w.
После применения вышеуказанного алгоритма, следуя процедуре постановки подписи, автор электронного документа передает получателю тройку (
M,
l,
p)
, где l
представляет собой электронную цифровую подпись, а p
- открытый ключ.
Пусть, к примеру, текстовый документ M
представлен в виде сообщения: «Петров Л.П. вылетел 17 января в Москву. Прошу встретить. Иванов.». Сопоставляя в строгое соответствие каждой букве указанного сообщения цифру, получим ряд вида (2)
, элементы которого отражены в таб. 3.
Таблица 3 Цифровое соответствие букв сообщения M
| П
|
е
|
т
|
р
|
о
|
в
|
Л
|
.
|
П
|
.
|
в
|
ы
|
л
|
е
|
||
| 149
|
18
|
54
|
48
|
42
|
124
|
53
|
158
|
82
|
149
|
82
|
53
|
124
|
81
|
33
|
18
|
| т
|
е
|
л
|
1
|
7
|
я
|
н
|
в
|
а
|
р
|
я
|
в
|
||||
| 54
|
18
|
33
|
53
|
1
|
7
|
53
|
93
|
39
|
124
|
114
|
48
|
93
|
53
|
124
|
53
|
| М
|
о
|
с
|
к
|
в
|
у
|
.
|
П
|
р
|
о
|
ш
|
у
|
в
|
с
|
||
| 155
|
42
|
51
|
30
|
124
|
57
|
82
|
53
|
149
|
48
|
42
|
72
|
57
|
53
|
124
|
51
|
| т
|
р
|
е
|
т
|
и
|
т
|
ь
|
.
|
И
|
в
|
а
|
н
|
о
|
в
|
.
|
|
| 54
|
48
|
18
|
54
|
27
|
54
|
84
|
82
|
53
|
152
|
124
|
114
|
39
|
42
|
124
|
82
|
На основе исходных данных, сформируем матрицу A
размерности (8 x 8)
вида:
. (4)
Подразумевая, что p
= 5 сгенерируем ряд (3).
Матрица B
размерности (8 x 8)
будет иметь вид:
. (5)
Применяя (1), получим: l
= 1656,77.
Согласно процедуре проверки подписи получатель электронного документа, в свою очередь, по заранее согласованной с автором и переданной по защищенному каналу, формуле генератора случайных чисел (3)
, а также алгоритму хэш-функции вида восстанавливает матрицы A’
и B’
, которые, в случае достоверной передачи, должны совпадать с (4)
и (5)
. Затем вычисляет численное значение хэш-функции l’
. В том случае если выполнится равенство вида:
l = l''
, (6)
то можно с уверенностью сказать, что электронный документ дошел по телекоммуникационному каналу до адресата в неискаженном злоумышленником виде и электронная цифровая подпись автора подлинная.
Особо следует отметить, что для обеспечения наилучшей защищенности передаваемой информации исходный текст M
и значение хэш-функции l
можно зашифровать при помощи известных, действующих криптографических методов.
В виду того, что созданная по предложенному алгоритму хэш-функция полностью удовлетворят вышеотмеченным свойствам, а сам алгоритм претендует на нестандартность и хорошо программно реализуем, созданная на основе указанного алгоритма система электронной цифровой подписи будет обеспечивать целостность автоматизированной системы обработки и хранения информации и надежную аутентификацию подлинности электронного документа и его автора.
9.2. Лабораторная работа №
9
Целью работы
является реализация программной системы безопасного хэширования сообщения произвольной длины на основе средств универсальных систем MATLAB.
9.2.1.
Порядок выполнения работы
1. Открыть универсальную систему MATLAB.
2. Получить у преподавателя таблицу с обучающей выборкой для реализации алгоритма формирования электронной цифровой подписи.
3. Реализовать вычислительную процедуру обучения с экспертом (использовать программный модуль лабораторной работы № 3).
4.
Реализовать вычислительную процедуру самообучения (использовать программный модуль лабораторной работы № 4).
5. Представить результаты реализации алгоритма формирования электронной цифровой подписи.
6.
Оформить тематическую заглавную страницу лабораторной работы № 9.
7. Сохранить все результаты выполнения работы в файле на диске.
9.2.2.
Порядок оформления отчета
Отчетом о лабораторной работе № 9 является файл с именем, совпадающим с фамилией студента с результатами работы в папке Мои документы/номер группы.
9.2.3.
Контрольные вопросы
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.