Указания методические к выполнению лабораторных работ по дисциплине «Интеллектуальные информационные системы» Санкт-Петербург ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ РОССИЙСКОЙ ФЕДЕРАЦИИ Санкт-Петербургский Государственный университет аэрокосмического приборостроения ОЦЕНИВАНИЕ СОСТОЯНИЯ СЛОЖНЫХ СИСТЕМ НА ОСНОВЕ ИММУНОКОМПЬЮТИНГА Методические указания к выполнению лабораторных работ по дисциплине «Интеллектуальные информационные системы» Санкт-Петербург 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 = USV T , (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 2 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 значения энергии связи с помощью шага 6: Определить класс 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