Нейронные сети

ГОУ ВПО «Рязанский государственный медицинский университет им. акад. И.П. Павлова Минздрава РФ»

Кафедра математики и информатики

Практикум

Рязань 2009

Введение

Цели и задачи практикума

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

В практикуме рассматриваются важнейшие темы для специалиста по  обработке тестовых данных в условиях неопределенности:

  •  Искусственные нейронные сети. Основы описания многомерных тестовых данных (глава 1);
  •  Обучение сети (глава 2);
  •  Многомерная кластеризация (глава 3);
  •  Построение области допустимых изменений параметров (области работоспособности) однородных групп (глава 4);
  •  Модели регрессии при наличии сильной корреляции независимых факторов и наличии аномальных результатов измерения (глава 5);
  •  Определение главных компонент дискретного конечного множества элементов. Выбор центров кластеризации на основе метода оптимума номинала (глава 6);
  •  Адаптивный итеративный метод восстановления входного сигнала измерительной системы (глава 7);
  •  Hейронная сеть Хопфильда (глава 8);
  •  Нечеткие нейронные сети (глава 9).

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

Глава 1. Искусственные нейронные сети. Основы описания многомерных тестовых данных

1.1. Понятие искусственного нейрона

Искусственный нейрон можно представить в виде рис. 1.

Рис.  Искусственный нейрон

Где F – функция активации, y = F(d)

Виды F:

1. Линейная функция активации F(d)=K·d;

2. Сигмоидальная (S-образная) функция

a) Логистическая функция. Эта функция математически выражается как

б) Гиперболический тангенс

3. Релейная характеристика функции активации

1.2. Искусственные нейронные сети

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

Однослойные искусственные нейронные сети

Многослойные искусственные нейронные сети

Любая многослойная нейронная линейная сеть может быть заменена эквивалентной однослойной сетью. Однако однослойные сети ограничены

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

1.3. Основы представления многомерных данных

1.3.1. Упорядоченные множества элементов. Структура и способы представления многомерных матриц

Наряду с понятием множества как совокупности неупорядоченных элементов важным понятием является понятие упорядоченного множества элементов. Многомерной матрицей (ММ) называется упорядоченная совокупность многоиндексных элементов i1i2…i, где i = 1,2,…n; . Целые положительные числа , NA = n1n2…n, n называются соответственно размерностью матрицы А, размером матрицы А, размером индекса i. Размерность  показывает число индексов в обозначении элементов i1i2…i матрицы. Размер NA матрицы А указывает общее число элементов матрицы. Размер индекса n показывает, сколько значений (от 1 до n) пробегает соответствующий индекс.

Структура многомерных матриц определяется структурой их индексов. Структура индекса может быть столбцовой или строчной. Индексы, имеющие, например, строчную структуру (строчные индексы), показывают положение элементов внутри какого-либо столбца. При индексном представлении элементов матрицы целесообразно ставить знак «+» или «–» соответственно над столбцовым или строчным индексом. Например, di+j- - элементы обычной двухмерной (плоской) матрицы. Общее представление многомерной матрицы А имеет вид А = А(p,q), где р – число столбцовых индексов, q – число строчных индексов. Для получения индексного представления многомерной матрицы вводится помечивание индексов. Пометка начинается с последнего индекса, который при q0 принимается за строчный. Далее столбцовые и строчные индексы чередуются до тех пор, пока один из видов индексов не исчерпывается. При pq все оставшиеся индексы принимаются за столбцовые, при pq – за строчные. Числа p и q в сумме дают размерность  матрицы А: p+q = . Если матрица А является функциональной, например зависит от времени t, от пространственных координат x, y и т.д., то структурные числа p и q следует отделять от аргументов точкой с запятой, например A = A(p,q;t,x,y). Для наглядного представления многомерной матрицы используют табличное представление. Табличное представление многомерной матрицы – это блочно-иерархическая таблица, отображающая на плоскости структуру матрицы и численные значения элементов. Иерархия согласована с иерархией индексов таким образом, что крайним левым индексам соответствуют наиболее крупные блоки. При этом столбцовые индексы изменяются в столбцах, а строчные – в строках. Примеры представления многомерных матриц приведены в таблице 1.1.

Таблица 1.1

Общее представлениеИндексное представлениеТабличное представлениеА(0,1){ai-}i = i=1i=2a1a2А(1,2){αi-j+k-}=i, j, k = i=1i=1i=2i=2k=1k=2k=1k=2j=1a111a112a211a212j=2a121a122a221a222

j = 1j = 2B(1,1) = {bi+j-} = i = 132i = 274

1.3.2.Структурное преобразование массивов данных

1.3.2.1. Преобразование старшинства индексов

(p - столбцовый индекс, q – строчный индекс)

A(p,q)==

j=1j=2l=1l=2l=1l=2i=1k=11234k=25678i=2k=19101112k=213141516

A1(p,q)==

l=1l=2j=1j=2j=1j=2k=1i=11324i=29111012k=2i=15768i=213151416

1.3.2.2. Аналитическое преобразование старшинства индексов

C(p,p)*A(p,q)*C1(q,q)

C(p,p)= {}

Столбцовые индексы матрицы С располагаются в новой последовательности. Строчные индексы остаются в той последовательности, в которой они были в исходной матрице А.

 C(p,p)= {}=

i=1i=2k=1k=2k=1k=2k=1i=11000i=20010k=2i=10100i=20001

C1(q,q)=

(Столбцовые индексы идут в той последовательности, как они были в исходной матрице А; а строчные – так как необходимо).

C1(q,q)= =

l=1l=2j=1j=2j=1j=2j=1l=11000l=20010j=2l=10100l=20001

В итоге получаем:

Глава 2. Обучение сети

2.1. Постановка задачи обучения сети с учителем

Когда в сети только один слой, алгоритм ее обучения с учителем довольно очевиден, так как правильные выходные состояния нейронов единственного слоя заведомо известны и подстройка синаптических связей идет в направлении, минимизирующим ошибку на выходе сети. Согласно методу наименьших квадратов, минимизируемой целевой функцией ошибки НС является величина:

,

где  – реальное выходное состояние нейрона j выходного слоя N нейронной сети при подаче на ее входы p-го образа; dj,p – идеальное (желаемое) выходное состояние этого нейрона.

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

.

Здесь ωij – весовой коэффициент синаптической связи, соединяющей i-ый нейрон слоя n-1 с j-ым нейроном слоя n, η– коэффициент скорости обучения, 0< η <1.

2.2. Минимизация многомерной функции на основе метода Давидона-Флетчера-Пауэлла

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

Ф = Ф(X1,X2,…,Xn). (6)

Определение оптимального управления сводится к поиску такого набора численных значений переменных, при котором функция Ф достигает экстремального значения. Для определенности будут рассматриваться только минимумы функции (1.2.1).

Функцию можно задавать в виде точного описания последовательности операций над численными значениями переменных X1,X2,…,Xn. Функция должна обладать свойством однозначности, т.е. при любом наборе численных значений X1,X2,…,Xn принимать только одно значение.

Будем считать набор численных значений X1,X2,…,Xn координатами некоторой точки n-мерного пространства, которую можно представить вектором . Для такой точки можно подсчитать значения функции . выделим из совокупности точек n-мерного пространства те точки, которым соответствуют равные значения функции , где Ф0 – некоторое численное значение. Геометрическое место точек с равными значениями функции называют поверхностью равного уровня. Изменив уровень Ф0 функции, получим другую поверхность равного уровня, причем различные поверхности равных уровней вложены одна в другую, но нигде не соприкасаются. Отсутствие общих точек у этих поверхностей непосредственно следует из свойства однозначности функции.

Градиентом функции будем называть вектор , (.7)

где частные производные функции  вычислены в точке . В n-мерном пространстве градиент направлен перпендикулярно (нормально) к поверхности равного уровня в точке  и указывает направление наискорейшего возрастания функции. Противоположный по направлению вектор , называемый антиградиентом, дает направление наискорейшего убывания функции. В различных методах поиска минимума функции можно выделить два основных этапа: определение направления и минимизацию функции в этом направлении. Методы минимизации многомерных функций различаются способами реализации этих этапов. В одних методах векторы направлений наперед заданы (координатный спуск в методе Гаусса-Зейделя), а в других выбор направления зависит от поведения функции, как, например, в рассматриваемом градиентном методе Давидона-Флетчера-Пауэлла (ДФП). Второй этап – минимизация функции в выбранном направлении – представляет собой одномерный поиск и наиболее трудоемкую часть процесса. Рассмотрим теперь подробнее градиентный метод ДФП.

Исходные данные: начальная точка поиска , градиент функции , градиент функции в начальной точке нормируется по уравнению , где ; .

Начальная матрица n×n, равная единичной матрице, H(1,1) = E[1,1]; ε – коэффициент, задающий точность одномерного поиска; Δ – точность поиска минимума функции.

  1.  Вычисляем вектор направления   (.8)
  2.  Формируем вектор , (.9)

и, изменяя параметр α, проводим в направлении  одномерный поиск минимума функции. По его результатам определяем положение оптимальной конечной точки на этом направлении: ; .

Начальное значение шага одномерного поиска α0 принимается равным 1, если выполняется условие , иначе величина уменьшается. Регулировка масштаба одномерного поиска заложена в формуле (6.8), так как величина модуля  зависит от модуля градиента и по мере приближения к минимуму функции неограниченно убывает. Уменьшение шага поиска по мере приближения к минимуму многомерной функции является необходимым, иначе трудно будет достаточно точно определить координаты этого минимума.

3. Вычисляем градиент  и приращение градиента

(.10)

4. Находим новую матрицу  по рекуррентной формуле  (.11)

5. Переходим на этап 1 с новыми начальными условиями.

Отметим некоторые вычислительные особенности метода ДФП. Метод подвержен накоплению ошибок, вследствие чего рекомендуется время от времени «забывать» накопленную информацию и начинать вычислительный процесс заново. Для этого необходимо предусмотреть «обновление» расчетов. Оно заключается в замене с некоторой периодичностью (обычно через n или 2n итераций) текущей матрицы  единичной матрицей . При обновлении на каждой итерации метод ДФП превращается в метод наискорейшего спуска.

При расчете на ЭВМ первая производная функции по некоторому параметру Xi заменяется первой разделенной разностью , (.12)

где X1, Xi, Xn - координаты точки , в которой вычисляется производная.

Для метода ДФП рассматриваются 2 варианта реализации, которые различаются только методами одномерного поиска. В первом варианте применяется метод золотого сечения, во втором – квадратичная аппроксимация. Рассмотрим кратко эти методы.

Сокращение интервала неопределенности методом золотого сечения

Название метода указывает на его связь с золотым делением отрезка, т.е. таким делением отрезка на две неравные части на X и Y (X>Y), при котором , где .

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

; α-1 = 0; α0 = 1, (.13)

если при этом происходит убывание функции.

На рис. 6.1 изображена последовательность точек α0, α1, α2, полученная согласно алгоритму (.13).

 

Рис. 6.1. Последовательность точек α

Из рисунка видно, что интервал неопределенности лежит между точками α0 и α2. Выберем новую точку α3 так, чтобы получить золотое сечение интервала неопределенности  (рис. 6.2).

Рис. 1.2.2. Сокращение интервала неопределенности

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

, (6.14)

где  – два последних значения значений функции,  - коэффициент, задающий точность одномерного поиска.

Сокращение интервала неопределенности методом квадратичной аппроксимации

В основе метода лежит аппроксимация функции Ф() квадратичным полиномом. Для ускорения поиска на этапе выделения интервала неопределенности необходимо ввести, как и ранее, переменный шаг i в (6.9):

; (6.15)

0 = 1, если при этом происходит убывание функции, -1 = 0,  - коэффициент, численное значение которого в начале одномерного поиска равно нулю, а затем возрастает на 1 через каждые R шагов. Пусть произведены измерения функции в точках 0, 1, 2 согласно алгоритму. Интервал неопределенности лежит между точками 0 и 2 (рис. 6.1). Для сокращения интервала заменяем реальную функцию Ф() аппроксимирующей функцией Фапр(), которая проходит через те же точки 0, 1, 2, Фапр()=a2+b+c и имеет координату минимума опт=-b/(2a). Связывая неизвестные коэффициенты a, b, c со значениями 0, 1, 2 и Ф(0), Ф(1), Ф(2) получаем расчетную формулу:

. (6.16)

Причем точка 3=опт (рис. 6.2) попадает внутрь интервала неопределенности 2 - 0.

Новый интервал неопределенности уменьшился и стал равным 2 -1. Вычислительный процесс сокращения интервала необходимо продолжить, пока не будет выполнено условие одномерного поиска (6.14).

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

,

где H – симметричная и положительно определенная матрица вторых частных и смешанных производных (матрица Гессе, или гессиан), с – постоянный вектор, b – константа.

Оптимальное решение приведенной задачи соответствует нулевым значениям первых производных, то есть

 

откуда .

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

Среди подобных алгоритмов одним из наиболее популярных и используемым в пакете Optimization Toolbox является так называемый BFGS-алгоритм, получивший свое название по фамилиям предложивших его авторов (Broyden, Fletcher, Goldfarb, Shanoo), в котором аппроксимация Н производится итерационно, по формуле

,

где , .

Заметим, что наиболее удобно иметь аппроксимацию не матрицы Н, а обратной к ней матрицы Н-1, приведенное рекуррентное соотношение подобную замену допускает, при этом сам алгоритм становится практически идентичным хорошо известному отечественным исследователям алгоритму Давидона-Флетчера-Пауэлла, за тем исключением, что в последнем векторы q заменены на векторы s и наоборот.

Именно такие алгоритмы являются основой численных методов, заложенных в распространенные математические пакеты прикладных программ (MS Excel, Mathcad, Mathlab и т.д).

Блок-схема алгоритма минимизации функции многих переменных метода Давидона-Флетчера-Пауэлла приведена на рис. 6.3.

Рис,6,3, Блок-схема алгоритма метода Давидона-Флетчера-Пауэлла

2.3. Минимизация многомерной функции при наличии линейных ограничений на основе метода Давидона-Флетчера-Пауэлла

Имеются ограничения:

Ранее (без ограничений) матрица была единичной, теперь она рассчитывается:

2.4. Учебный пример №1

2.4.1. Минимизация многомерных гладких функций

1. Перед выполнением учебных примеров необходимо изучить теоретический материал.

2. Открыть программу lor2a.exe – ”Минимизация функции многих переменных (демонстрационная программа)”. Диалоговое меню программы имеет следующие пункты:

  1.  Просмотр функции в целом (для всех вариантов она имеет вид F=(x12+x2-11)2+(x1+x22-7)2).
  2.  Просмотр функции по квадрантам.
  3.  Метод золотого сечения.
  4.  Метод квадратичной аппроксимации
  5.  Задание/снятие ограничений.

Просмотреть график функции (с линиями уровня) целиком и по квадрантам. Записать координаты начальной точки в тетрадь (в частности, для 1 варианта это x1=-3,4 и х2=-3,7), которую можно просмотреть ближе, записав указанный квадрант. Уточнить координаты точки двумя методами: золотого сечения и квадратичной аппроксимации. Координаты минимума, полученные обоими методами (без задания ограничений), равны: х1 = -3,779, х2 = -3,283. Можно просмотреть направление движения точки по графику, выбрав соответствующий пункт меню. В тетрадь записать координаты точки минимума, количество итераций, за которое достигнуто решение и оптимальное значение Alpha.

Далее накладывается ограничение на направление поиска минимума (для всех вариантов оно различно, в частности, для первого варианта имеет вид: -2х1 - 3х2+5=0). Начальные значения координат точки минимума х1=-4, х2=4,3. Зарисовать в тетради направление движения точки по графику. Вдоль данного направления координаты точки минимума имеют значения: х1 = -2,557, х2 = 3,371, (метод золотого сечения дает этот результат после 2-ой итерации, при α = 0,002, метод квадратичной аппроксимации после 3-ей итерации при α = 0,82).

3. Открыть программу lor4.exe. –”Минимизация многомерной функции. Реализация градиентного метода”.

Диалоговое меню:

  1.  вычисление F(x1, x2);
  2.  Grad;
  3.  нормирование градиента;
  4.  формирование вектора положения;
  5.  выход.

Все данные заносить в таблицу, вид который предложен в самой программе. Значения F1 и F2 получаются из значений нормированного градиента, взятых с противоположным знаком. Для взятой произвольно начальной точки х1=4, х2=3, градиентный метод дает следующие результаты:

X1X2AlphaF(x1,x2)Grad FF1F2430105,501461,043; 27,426-0,137-0,0613,8632,939195,704758,150; 26,086-0,133-0,0603,5972,819278,011652,523; 23,476-0,125-0,0553,2222,654356,225744,620; 19,820-0,114-0,0512,7662,450434,488134,985; 15,354-0,101-0,0442,2612,230516,666224,360; 10,443-0,088-0,0371,7332,00864,969513,307; 5,353-0,074-0,0301,2151,79870,26622,52; 0,404-0,064-0,0100,7031,71881,6029

Видно, что минимум функции равен 0,22662 в точке (1,215; 1,798) при alpha равном 7. Результат достигнут на седьмой итерации, но если процесс поиска минимума затянулся, то через 5 шагов alpha можно увеличивать вдвое. Построить график зависимости F=F(α).

4. Открыть программу lor.exe –”Программа минимизации функции многих переменных”.

Система меню ориентирована на реализацию всех этапов минимизации многомерной функции методом ДФП, который может использоваться для численной реализации других методов: координатного спуска в методе Гаусса-Зейделя, наискорейшего спуска и других градиентных методов.

  1.  Вычисление функции F(X1, X2) (в лабораторной работе только для простоты выполнения и наглядности визуализации исходных данных и результатов оптимизации число переменных n в целевой функции берут равным двум).
  2.  Вычисление GRAD(X1, X2) (реализация выражения (6.7)).
  3.  Нормирование градиента (осуществляется лишь в начальной точке поиска минимума, при дальнейших операциях эта итерация может опускаться).
  4.  Вычисление вектора направления (реализация выражения (6.8)).
  5.  Формирование вектора положения (реализация выражения (6.9)).
  6.  Сокращение интервала неопределенности методом золотого сечения (реализация выражения (6.13)). При выполнении данной операции, если не соблюдается условие , принять  и так до тех пор, пока не произойдет убывание функции.
  7.  Золотое деление отрезка (деление отрезка на две неравные части X и Y (X>Y)), при котором , где .
  8.  Вычисление вектора направления на второй и последующих итерациях (реализация последовательно выражений (6.11), (6.8)).
  9.  Поиск интервала неопределенности методом квадратичной аппроксимации (реализация выражения (6.15)). Рекомендации по выбору α те же, что и в меню под номером 6.
  10.  Определение координаты минимума в методе квадратичной аппроксимации (реализация выражения (6.16)).
  11.  Построение графика функции (Х2 – ордината, Х1 - абсцисса).
  12.  Завершение работы.

Записать координаты начальной точки в тетрадь и начертить таблицу, как в программе lor4.exe.Проделать 2 итерации по поиску минимума функции (первые пять пунктов, т.е., alfa при этом равны 0 и 1 соответственно). Для дальнейшего определения значения alfa перейти к <6> пункту. Найти alfa по предлагаемой формуле и высчитывать далее по первым пяти пунктам вектор положения с учетом нового значения alfa. После нахождения точки минимума методом золотого сечения перейти ко второму методу. Для этого начертить еще одну такую же таблицу, переписать туда результаты первых двух итераций и перейти к пункту <9> для определения значения alfa, далее продолжить работу по пяти пунктам и по <9> пункту.

5.Открыть программу lor5.exe – ”Программа минимизации функции многих переменных (со сбойными результатами)”.

Диалоговое меню программы имеет вид, как и у lor4.exe. Начертить в тетради исходную таблицу. Для начальной точки взять такие же координаты, как и в программе lor4.exe. Найти координаты точки минимума. При вычислении функции F убедиться, что налицо сбойный результат (при x1=4, x2=3 значение F = 34684,888). При выполнении работы сбой постепенно ликвидируется, но результат будет достигнут за большее количество шагов (для уменьшения количества итераций целесообразно использовать рекомендации по изменению α из предыдущего пункта). Построить график зависимости F=F(α).

6. Открыть программу lor6.exe – ”Программа минимизации функции многих переменных без сбойных результатов. Адаптация”.

Диалоговое меню программы имеет вид, как и у lor4.exe. Начертить в тетради исходную таблицу и найти координаты точки минимума (начальные данные такие же, как и в предыдущей программе). Сравнить результаты 5-ой и 6-ой программ. Построить график зависимости F=F(α).

Отметим, что использованные в программе алгоритмы минимизации многомерных функций являются стандартными и применяются во всех известных математических пакетах, разработанных в Windows (Excel, MathCad, MathLab, Mathematica и другие).

Одним из самых распространенных и наиболее популярных в вузовской среде является пакет Microsoft Excel, обладающий удобным и понятным интерфейсом, подробной справочной системой, мощным инструментарием и множеством математических функций.

2.4.2. Минимизация многомерных негладких функций

Метод Симплекс-планирования

Симплекс-планирование проведем в многомерном пространстве.

Симплекс – это множество (k+1) точек, образующих выпуклую фигуру в k-мерном пространстве.

,

,

Пример, k=2

=0.866

=0.5

х1х20,8660,5-0,8660,501

Оптимизация:

  1.  Реализация плана.
  2.  Отбрасываем вершины симплекса с максимальным значением.
  3.  построение на оставшейся грани нового симплекса, у которого отброшенная вершина заменена ее зеркальным отображением.

Координаты новой точки  находятся по формуле:

Опять находим максимальное значение, отбрасываем его.

Достоинства метода:

  •  Число необходимых опытов при определении направления движения мало по сравнению с другими методами.
  •  Малый объем вычислений.
  •  Ограничения на область изменения факторов легко учитываются при движении симплекса.
  •  Если новые вершины выходят за пределы допустимой области, то выбирают вершину, следующую за наихудшей вершиной симплекса.
  •  При достижении области оптимума размеры симплекса уменьшают на ¼ начальной величины.

Критерии остановки:

Пример реализации метода

X1X2F[x1,x2]0.0866-0.086600.050.05-0.15.20916.23096.6200.0866-0.08660.20.050.054.885.20916.23090.173200.08660.20.20.053.97014.885.20910.08660.173200.350.350.22.90313.70103.97010.17320.25980.08660.50.350.352.69402.90313.70100.34640.17320.25980.50.50.352.00802.69402.90310.25980.34640.17320.650.50.51.85892.00802.69400.4330.25980.34640.650.650.51.28491.85892.00800.34640.4330.25980.80.650.651.19581.28491.85890.51960.34640.4330.80.80.650.73371.19581.28490.4330.51960.34640.950.80.80.70470.73371.19580.60620.4330.51960.950.950.80.35450.70470.73370.51960.60620.4331.10.950.950.38550.35450.70470.69280.60620.51961.10.951.10.14730.35450.38550.77940.69280.60620.951.10.950.12440.14730.3545

Содержание отчета по учебному примеру№1:

1. Краткое описание алгоритма минимизации функции многих переменных.

2. Результаты поиска минимума функции многих переменных.

3. Выводы.

2.5.Учебный пример №2

Моделирование на НС нелинейной функции.

а) создать и обучить нейронную сеть выполнению операции: y=x1^2+x2

Исходные данные:

X1X2Y1-2-10,500,2500,50,5112

Возьмем нейронную сеть вида:

Подстройка параметров нейронной сети произведем с помощью MS Excel.

Введем параметры W11, W12, b1, W21, b2 случайным образом.

Для нахождения f1 в ячейку I2 введем функцию =A2*$D$2+B2*$E$2+$F$2

В ячейку J2 введем логистоническую функцию  в виде функции =1/(1+EXP(-I2)).

Для получения реального выхода нейрона необходимо полученное значение домножить на W21 и прибавить b2, для этого в ячейку K2 введем функцию =J2*$H$2+$G$2. Ошибка – разность желаемого и реального выходов. Сумма квадратов ошибок будет являться критерием поиска подстраиваемых параметров нейронной сети. В меню Сервис\Поиск решения проводим минимизацию критерия, путем подбора весовых коэффициентов.

б) реализовать булевы функции с помощью нейронных сетей.

Нейронная сеть:

Реализуем булеву алгебру с помощью этой нейронной сети.

  1.  реализация операции И:

Поиск решения:

  1.  реализация операции ИЛИ:

Поиск решения:

Поиск решения:

в) Рекуррентная процедура оценки параметров на скользящем постоянном интервале.

Пример реализации на основе нейронной сети:

№x1x2x3x4x5Y10,10,0998330,1986690,295520,3894180,4794260,56464220,20,1986690,295520,3894180,4794260,5646420,64421830,30,295520,3894180,4794260,5646420,6442180,71735640,40,3894180,4794260,5646420,6442180,7173560,78332750,50,4794260,5646420,6442180,7173560,7833270,84147160,60,5646420,6442180,7173560,7833270,8414710,89120770,70,6442180,7173560,7833270,8414710,8912070,93203980,80,7173560,7833270,8414710,8912070,9320390,96355890,90,7833270,8414710,8912070,9320390,9635580,985451010,8414710,8912070,9320390,9635580,985450,997495111,10,8912070,9320390,9635580,985450,9974950,999574121,20,9320390,9635580,985450,9974950,9995740,991665131,30,9635580,985450,9974950,9995740,9916650,973848141,40,985450,9974950,9995740,9916650,973848151,50,9974950,9995740,9916650,9738480161,60,9995740,9916650,97384800171,70,9916650,973848000181,80,9738480000w1-0,39993w2-0,10553w30,191922w40,490453w50,78808Y аппроксимирующВВ=Y-YаппрокВВ^20,5646422,79E-077,77E-140,6442173,05E-079,28E-140,7173563,28E-071,07E-130,7833273,47E-071,21E-130,8414713,63E-071,32E-130,8912073,76E-071,41E-130,9320393,85E-071,48E-130,9635583,9E-071,52E-130,9854493,91E-071,53E-130,9974953,88E-071,51E-130,999573Сумма1,28E-120,9916640,973847

г) НС с радиальными базисными функциями

Аппроксимировать функцию: f(x)=0.5*x+2*x2-x3.

Функция активации: . Возьмем 9 функций активации.

МС={-0.8; -0.6; -0.4; -0.2; 0; 0.2; 0.4; 0.6; 0.8}. σ =0.5.

Реализуем сеть

YA=w1*exp[-(-0.8-x)2/0.5]+w2*exp[-(-0.6-x)2/0.5]+…+w9*exp[-(0.8 - x)2/0.5].

Сервис, Поиск решения, находим минимум критерия.

Получаем:

XYЕσYA(Y-YA)2-12,5-0,80,52,4659090,001162-0,91,899-0,62,0325230,017828-0,81,392-0,41,3725770,000377-0,70,973-0,20,8517730,014696-0,60,63600,5058610,016936-0,50,3750,20,2952090,006367-0,40,1840,40,1761256,2E-05-0,30,0570,60,116330,00352-0,2-0,0120,80,0950930,011469-0,1-0,0290,1002970,016718000,1257330,0158090,10,0690,1692360,0100470,20,1720,2315320,0035440,30,3030,3155210,0001570,40,4560,4256410,0009220,50,6250,5668570,0033810,60,8040,7425190,003780,70,9870,9499630,0013720,81,1681,1728192,32E-050,91,3411,3721130,00096811,51,4949412,56E-05Суммаw10,0713050,129163w2-0,68783w31,441818w40,396578w5-0,65029w6-0,45863w70,368084w8-0,07066w9-0,48776

График Y и (Y–YA)2.

д) Обобщенная структура радиальной сети:

Функция 2-х переменных f(x1,x2).

X1X2Y011101000110

Исходные элементы линейно не отделены:

E2=(Y-f(x1,x2))2;

YA=W1*φ1+W2*φ2.

Y=ЕСЛИ(YA<0,4;1;0).

X1X2Fi1Fi2YAE2Y010,3678790,3678790,2957620,4959511100,3678790,3678790,2957620,4959511000,13533510,4563840,20828701110,1353350,4563840,2082870Сумма1,408476X11X12X21X22W1W210100,4019820,401982

Содержание отчета по учебному примеру№2:

1. Краткое описание алгоритма обучения нейронных сетей с гладкими функциями активации.

2. Результаты обучения.

3. Выводы.

Лаб.раб.- получение тестовых данных -”Тест”.

Глава 3.Многомерная кластеризация

Предположим, что рассматриваемая совокупность случайной величины Х неоднородна (рис.5.1) и в нее входят, например, три группы совокупностей случайной величины с существенно различными параметрами распределений (математическим ожиданием и средним квадратическим отклонением).

Рис. 5.1. Кластеризация однородных групп

Истинные зависимости y=y(x) для этих групп совокупности показаны на рис. 5.1. Там же пунктиром показана линия регрессии y на x, построенная для совокупности всех групп. Таким образом, обработка неоднородной совокупности теми же методами, какие применимы для однородных, могут привести к серьезным ошибкам. Рассмотрим два подхода к кластеризации: на основе разбиения графа и на основе гистограммного метода.

3.1.Разбиение дискретного конечного множества элементов на основе кратчайшего остовного дерева

3.1.1. Задача дискретной математики о разбиении множества.

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

В работе такая группировка делается с помощью построения кратчайшего остовного дерева. Алгоритмы разбиения отличаются друг от друга процедурой группировки и критерием качества разбиения множества. Введем некоторые обозначения. Пусть данные таблицы Т, подлежащие разбиению, содержат М объектов (а1,а2,.,аM), имеющих N свойств (x1,x2,…,xN), и требуется выявить К классов(S1,S2,…,SK), 1<K<N-1. Различные варианты разбиения объектов на К классов будем сравнивать по некоторому критерию качества разбиения F. Если свойства объекта представить себе в виде координат метрического пространства, то каждый объект со своими значениями свойств будет отображаться в некоторую точку этого пространства. Два объекта с почти одинаковыми значениями свойств отобразятся в две близкие точки, а объекты с сильно отличающимися свойствами будут представлены далекими друг от друга точками. Если имеются сгустки точек, отделенные промежутками от других сгустков, то их целесообразно выделить в отдельные структурные части множества-классы. В дальнейшем можно аппроксимировать сгустки каким-либо известным законом распределения. Можно также указать границы класса, описав их геометрические параметры(например, задав систему уравнений разделяющих гиперплоскостей). По этим описаниям можно узнать, какому классу принадлежит любой объект как изучаемой конечной выборки, так и любого нового объекта из генеральной совокупности.

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

3.1.2. Графовое представление связей между объектами

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

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

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

Матрицей смежности ориентированного помеченного графа с n вершинами называется матрица A=[aij], i,j=1,2…n, в которой

aij= m, если существует m ребер (xi, xj ),

0, если вершины xi, xj не связаны ребром (xi, xj).

Матрица смежности однозначно определяет структуру графа.

Граф называется взвешенным, если каждому его ребру сопоставлено число. Простой взвешенный граф может быть представлен своей матрицей весов W=[wij], где wij – вес ребра, соединяющего вершины i, j =1,2.n. Веса несуществующих ребер полагают равными . Матрица весов является простым обобщением матрицы смежности.

При описании графа списком его ребер каждое ребро представляется парой его вершин. Это представление можно реализовать двумя массивами r=(r1, r2,…, rn) и t=(t1, t2,…, tn), где n- количество вершин в графе. Ребро Li,j графа выходит из вершины ri и входит в вершину tj. Здесь L-характеристика ребра, например, вес ребра.

Деревом называется неориентированный граф, не имеющий циклов и изолированных вершин.Минимальным (кратчайшим) остовным деревом называется остовное дерево с минимальным общим весом его ребер.

3.1.3. Построение кратчайшего остовного дерева. Алгоритм Прима в табличной форме

По заданному графу заполняется матрица весов W(N, N). Веса несуществующих ребер предполагаются сколь угодно большими. Образуется массив P(N) меток вершин графа (столбцов матрицы весов). Алгоритм решения задачи заключается в последовательном заполнении массива меток столбцов и состоит из следующих этапов.

Предварительный этап. Обнуляется массив P(N) меток столбцов таблицы. Произвольно выбранному столбцу присваивается значение метки, равная его номеру.

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

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

Адаптивная кластеризация множества элементов производится путем удаления части ребер графа по критерию минимальной суммарной дисперсии классов. Для разбиения множества элементов на ”К”классов удаляются ”К-1” ребер. Пример расчета на MS Excel показан на рис.5.2

рис.5.2. Пример разбиения многомерного множества элементов на однородные группы

3.1.4. Алгоритм Краскала определения минимального остовного дерева

Для использования алгоритма Краскала применяется список ребер графа. Метод состоит в последовательном подключении к остовному дереву ребер с минимальным весом и заключается в следующем.

Предварительный этап. Список ребер сортируется в порядке возрастания весов. Ребро, имеющее минимальный вес (первое в упорядоченном списке) включается в искомый остов.

Этап, повторяющийся (N-1) раз (общий этап). Очередное ребро в списке включается в остов, если оно не образует цикл. Если ребро образует цикл с уже включенными в остов ребрами, то оно вычеркивается из списка и просматривается следующее по списку ребро.

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

Пример.

Известна стоимость обеспечения связи между источником и потребителями информации (рис.2).

Рис.2.

Нужно синтезировать топологию сети, обеспечивающей минимальную стоимость. Требуется определить методами Краскала и Прима минимальное остовное дерево графа G(5, 10), представленного на рис.2.

Метод Прима. Матрица весов, получаемая после предварительного этапа алгоритма, представлена в таблице 1, где в качестве начальной выбрана вершина 3.

Таблица 1.

312345151089253713103264872459164

Задачей общего этапа является помечивание всех столбцов таблицы. В 3-ей строке находится минимальный элемент w34=2. 4-ый столбец, содержащий минимальный элемент, помечается номером строки, где этот элемент находится. Элементу w43 присваивается сколь угодно большое значение. В непомеченных столбцах 3-ей и 4-ой строк находится минимальный элемент w32=3. 2-ой столбец, его содержащий, помечается номером 3-ей строки. Элементу w23 присваивается сколь угодно большое значение. После этого шага матрица имеет вид, представленный в табл. 2.

Таблица 2.

333123451510892571310326487459164

В непомеченных столбцах 2, 3 и 4-ой строк находится минимальный элемент w25 =1. 5-й столбец помечается номером 2-й строки, где находится минимальный элемент. Элементу w52 присваивается сколь угодно большое значение. На очередном шаге общего этапа в непомеченных столбцах 2, 3, 4 и 5-ой строк находится минимальный элемент w21=5. 1-ый столбец помечается номером 2, элементу w12 присваивается сколь угодно большое значение. Таблица после этого шага имеет вид, представленный в табл. 3.

Таблица 3.

233321234511089257131032648745964

Все столбцы таблицы помечены, общий этап закончен.

На заключительном этапе выписывается последовательность вершин, ребра между которыми включаются в минимальное остовное дерево. Это ребра, соединяющие вершины 1-2, 2-3, 3-4, 2-5.

Вес остовного дерева равен 5+3+2+1=11. Полученное остовное дерево показано на рис.3.

Рис.3.

Метод Краскала. По заданному графу (рис.2) составляется список ребер (см. табл.4), который на предварительном этапе упорядочивается в порядке возрастания весов (табл.5). Ребро №7, имеющее минимальный вес, включается в искомое остовное дерево (рис.4). Выполняется общий этап. Второе по весу ребро №6 также включается в остов. Следующее по весу ребро №1 включается в остовное дерево, так как оно не образует цикла с ребрами №6 и 7 (рис.4). Ребро №5 с минимальным весом среди оставшихся не включается в остов, так как оно образует цикл с ребрами №1, 6 и 7. Следующее по весу ребро №10 включается в остов. Вес остова равен 11, а его структура совпадает со структурой остова, полученного методом Прима (см. рис.3).

Таблица 4.

№ВесНачалоКонец132321013381449155445623471258635972410512

Таблица 5.

№ВесНачалоКонец712562341323544510512863597243814491521013

Рис.4.

Реализация алгоритма Краскала требует предварительной сортировки весов всех ребер. Алгоритм Прима не имеет этого недостатка.

3.1.5. Алгоритм построения кратчайшего остовного дерева  для ориентированного графа на основе решения задачи  линейного программирования.

Пусть граф имеет следующий вид:

Веса ребер данного графа представлены в таблице 6:

Таблица 6.

РебраВесаХ11Х22Х30Х46Х57Х61Х75

Для данного графа составляется система уравнений, в которой учитывается, что все выходящие потоки берутся со знаком «+», а входящие – со знаком «-». В данном графе начальной является вершина №1, а конечной - №5. Число уравнений, входящих в систему, равно n, где n-число вершин графа. В данном примере n=5. Для начальной вершины сумма потоков должна равняться (n-1) (в данном примере 4), а для всех остальных вершин сумма равняется ”–1”. Система уравнений имеет вид:

где хi0, i=1…7.

Данная система уравнений будет являться ограничениями при поиске решения. При решении данной задачи необходимо найти минимум целевой функции:

х1+2*х2+0*х3+6*х4+7*х5+х6+5*х7.

Теперь рассмотрим реализацию данной задачи на Excel.

Вначале вводим значения ребер графа, т.е. значения х1 – х7 в ячейках B7:H7 (B7=x1, C7=x2, D7=x3, E7=x4, F7=x5, G7=x6, H7=x7). Они берутся произвольно и не влияют на решение. Затем вводим веса этих ребер соответственно в ячейках B9:H9 (B9=1, C9=2, D9=0, E9=6, F9=7, G9=1, H9=5). Далее в ячейках B11:B15 вводим систему уравнений:

 B11=B7+C7+D7;

 B12=H7-B7;

B13=F7-C7-H7-E7;

B14=E7+G7-D7;

B15=-F7-G7.

В ячейку I11 вводим целевую функцию: B7*B9+C7*C9+D7*D9+E7*E9+F7*F9+G7*G9+H7*H9.

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

  •  целевая ячейка: $I$11
  •  за счет изменения: $B$7:$H$7
  •  минимальное значение
  •  ограничения:

$B$11=4

$B$12=-1

$B$13=-1

$B$14=-1

$B$15=-1

$B$7: $H$7>=0.

Нажимаем «Выполнить». Найдено следующее решение: в ячейках, содержащих значения ребер, появляются новые значения. Ребра, не включаемые в искомый остов, принимают значение 0, а включаемые – любое другое значение. В данном примере в остов включаются ребра: х1, х2, х3, х6. Структура таблицы MS Excel с найденным решением, представлена на рис.6.

ЗАДАЧА О НАХОЖДЕНИИ МИНИМАЛЬНОГО ОСТОВНОГО ДЕРЕВА ГРАФАРешение:Ребраx1x2x3x4x5x6x71120010Веса1206715Система уравнений:Целевая функция:4x1+x2+x3=4x1+2*x2+0*x3+6*x4+7*x5+x6+5*x7-1x7-x1=-14-1x5-x2-x7-x4=-1-1x4+x6-x3=-1-1(-x5)+(-x6)=-1В итоговое остовное дерево включаются ребра:x1,x2,x3,x6

3.1.6. Оперативный кластерный анализ данных на основе гистограммного метода

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

Исходные данные {Zi} – множество значений признака представлено таблицей следующего вида:

9987986775998776439887764398877643887795428688537765

Предварительная обработка включает 2 шага:

  1.  «Данные» квантуются с помощью L уровней. Число L определяется точностью преобразователя диалог – цифра.
  2.  Вычисляется «гистограмма»

, , .

Без потери общности алгоритма считается, что элементы множеств  и  упорядочены по правилу N1>N2>…>NL. Адаптивное планирование задачи кластеризации осуществляется выбором числа кластеров.

Обозначения. K – число групп (классов);

ni – число элементов i-ой группы;

- значение оценки математического ожидания k-ой группы на l-ом шаге;

- расстояние  от математического ожидания k-ой группы;

.

η – «допустимое» расстояние внутри группы (класса).

, , .

- характеризует «расстояние» между группами.

, , ,  – две «ближайшие» группы, pi,  - нормированный коэффициент, характеризующий «вес» класса.

Плотность вероятности случайной величины .

Разбиение выборки на кластеры осуществляется по правилу: для  находится кластер “i”.

В практических алгоритмах кластерного анализа часто принимается допущение о том, что  описывает семейство нормальных распределений:

Блок-схема алгоритма приведена на рис. 5.3.

0

 

1

2

3

4

5

6

7

8 13

 

9

10 14

11

12 15

16

17

18

 

19

Рис.5.3. блок-схема алгоритма кластеризации исходных данных.

  1.  . Коррекция

16. Коррекция

18. ;

Решение.

№12345678Zi78965432Ni1312864441

L=8

1) K=2; μ1 = 0; μ2 = 0

n1 = 0; n2 = 0

η1 = 0; η2 = 0

2) l = 0

  1.  L = l +1 = 1
  2.  N1 = 13 ≠ 0; нет.
  3.  r1(1) = 7; r2(1) = 7
  4.  I = 1; r1(1) = 7
  5.  η1>r1, нет
  6.  n1 = 0
  7.  j = 1
  8.  формирование группы

μ1 = 7; n1 = 13; σ1 = 0; η1 = 0

17) l = L, нет

3) l = 2

4) N2 = 12

5)

 

6) i = 1;

7) , 0 > 1, нет.

8) Поиск свободной группы

 n2 = 0; j = 2.

9) j = 2

14) формирование группы 2

; n2 = 12;

  1.  l = L, нет

3) l = 3

4) N3 = 8

5)

 

6) i = 2; r2 = 1

7) , нет (0 > 1)

8) Поиск свободной группы

9) Нет свободной группы

10) Вычисление rpq

m = 1; n = 2

rmn = 1;

m = 2; n = 1

p = 1; q = 2; rpq = 1

11) ; 1 > 1, нет

12) объединение групп 1, 2

Группа 1:

n1 = 25;

В группе 1

n1 = 33

;

В группе 2

 

;

f1 (Z)

рис. 5.4 Модель первой группы ()

f2 (Z)

 Z

рис. 5.5 Модель второй группы

Содержание отчета по разделу №3

1. Краткое описание алгоритмов кластеризации.

2. Результаты кластеризации.

3. Выводы.

Глава 4. Метод построения области допустимых изменений параметров (области работоспособности) объекта управления

4.1. Выбор метода построения области работоспособности

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

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

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

Уменьшения погрешности аппроксимации можно достигнуть более точным заданием границ областей, например, аппроксимировать системой гиперпараллелепипедов, системой многомерных эллипсоидов [4-5].В этом случае наиболее распространенным является задание области работоспособности системой линейных неравенств:

. (1.1)

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

Для построения области работоспособности предлагается использовать метод гиперплоскостей, позволяющий получить область в виде многогранника, вершинами которого будут граничные точки. Грани многогранника представляют собой гиперплоскости, которые соответствуют уравнениям неравенств (1) при замене знака “” на знак “=”.

4.2. Метод гиперплоскостей для построения выпуклой области

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

Вычислительная процедура построения области работоспособности по граничным точкам методом гиперплоскостей заключается в выполнении следующих операций. 1. Выбираются произвольным образом первые (N + I) граничные точки (на рис.1 для N = 2 точки 1, 2, 3) и строятся по ним (N + 1) гиперплоскости (для N = 2 прямые 1-2, 2-3, 3-1). Для каждой построенной гиперплоскости запоминаются координаты граничных точек, по которым она построена, и координаты ее вершины.

Вершиной данной гиперплоскости условимся называть ту точку из выбранных (N + 1) точек, через которую не проводится гиперплоскость (на рис.1.1 точки 1 и 2 являются соответственно вершинами гиперплоскостей 2-3 и 1-3).

Рис.1.1 Пример построения выпуклой оболочки

2. Определяется для следующей, выбранной произвольно, граничной точки (точка 4) соответствующая ей генеральная прямая гиперплоскость (прямая 1-3). Генеральной гиперплоскостью данной граничной точки будем называть гиперплоскость, вершина которой и данная граничная точка расположены по разные от нее стороны.

Генеральных гиперплоскостей для данной граничной точки может быть несколько (для точки 5 прямые 1-4, 3-4), особенно при построении многомерных областей работоспособности. Поэтому поиск генеральной гиперплоскости осуществляется среди всех ранее построенных гиперплоскостей.

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

3. Выполняется п.1 для данной граничной точки и точек, через которые была ранее проведена ее генеральная плоскость, найденная в п.2. Затем в памяти ЭВМ стираются значения коэффициентов генеральной гиперплоскости, координаты ее вершины и точек, через которые она проведена. В противном случае область может быть построена неверно, так как генеральная гиперплоскость пересекает ее, а также может быть принята за генеральную гиперплоскость для последующих граничных точек.

Аналогичные действия выполняются для каждой генеральной гиперплоскости, если их для данной граничной точки несколько. При этом среди вновь проведенных гиперплоскостей будут одинаковые (на рис. 2 через точки 4 и 5 дважды проводится прямая 4-5), информация о которых должна стираться в памяти ЦВМ по тем же причинам, что и для генеральных гиперплоскостей.

4. Выбирается следующая по порядку граничная точка, и все повторяется с п.2.

После перебора всех граничных точек процесс построения области работоспособности заканчивается и производится определение знаков “” “” для системы линейных неравенств 1).

Блок-схема алгоритма построения области работоспособности по граничным точкам приведена на рис.1.2.

Блок 1

Производится выбор первых (N + 1) граничных точек из массива всех граничных точек.

Блок 2

Процедура построения гиперплоскости через заданные N граничных точек занимает центральное место в данном алгоритме. Коэффициенты гиперплоскости (неравенства) определяются в результате решения системы линейных алгебраических уравнений (N + 1)-го порядка. Систему получают в результате составления уравнений гиперплоскостей, записав вместо переменных координаты N точек, через которые необходимо провести гиперплоскость:

.  (1.2)   

Так как количество неизвестных коэффициентов (N + I), то необходимо одному из них задать произвольное значение, например a = 1, Однако в этом случае невозможно построить гиперплоскости, параллельную оси координат X.

Аналогично, если присвоить значение другому коэффициенту b = 1 уравнений (3), то предлагаемый подход будет неприменим для построения гиперплоскостей, параллельных соответствующим осям координат, а при задании k  0 - для построения гиперплоскостей, проходящих через начало координат.

С целью устранения второго недостатка вводятся (N + 1)-я переменная z и дополнительная точка (точка 4 на рис.4). Тогда построение гиперплоскости осуществляется в (N + 1)-м пространстве, а произвольное значение присваивается коэффициенту при переменной z. Координаты дополнительной точки (точка 4) необходимо выбирать такими, чтобы ни одна из гиперплоскостей не была параллельна оси координат (N + 1)-й переменной z. Это требование выполняется, если значение хотя бы одной из координат дополнительной точки (не считая координаты по оси z) меньше минимального или больше максимального значения соответствующей координаты множества граничных точек. Значения остальных координат задаются произвольно.

 

В результате решения системы (N + 1)-го порядка (1.2) определяются значения коэффициентов (N + 1)-й гиперплоскости. Исключение из уравнений гиперплоскостей дополнительной переменной позволяет получить область в N-мерном пространстве (заштрихованная область на рис.1.3).

Блоки 3, 4

Производится проверка - первые ли (N + 1) гиперплоскостей построены. Если первые, то осуществляется поиск генеральной гиперплоскости. В противном случае выполняется проверка - все ли генеральные гиперплоскости найдены и использованы при построении гиперплоскостей для данной граничной точки.

Блоки 5, 6

После построения всех гиперплоскостей для данной граничной точки внутри области работоспособности оказываются генеральная гиперплоскость и одна или несколько пар одинаковых гиперплоскостей, если генеральных гиперплоскостей больше одной (рис1.2).

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

Блоки 7, 8

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

Блок 9

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

Блок 10

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

Блок 11

Для найденной генеральной гиперплоскости производится поиск координат N точек, по которым она была построена.

Блок 12

Знаки неравенств “” и " " определяются в результате подстановки координат вершин гиперплоскости в уравнение гиперплоскости. При этом используется свойство вершин принадлежать области работоспособности. Символ "” соответствует отрицательному знаку результата подстановки, символ “” - положительному. Для удобства использования результатов построения области работоспособности все неравенства приводятся к виду “0”.

1.2.1. Пример построения области работоспособности и расчета попадания точки в заданную область

Задана таблица работоспособности объекта

Таблица 1

№ п/пx1x2работоспособность объекта1610да218да323да475да582да6116да7108да

Вопрос: будет ли работоспособен объект с данными параметрами

Решение. Геометрическое представление исходных данных.

Рис.1.4. Координаты исходных данных

Проведем построение области согласно алгоритму, изложенному выше.

1 шаг. Берется (N + 1) точки в N – мерном пространстве в нашем случае N=2, т.е. берем точки 1, 2, 3.

Через каждые N точек проводится гиперплоскость и заполняется таблица

Таблица 2

Прямая1 – 22 – 31 – 3Вершина312координаты вершин2; 36; 101; 8координаты 1-ой точки6; 101; 86; 10координаты 2-ой точки1; 82; 32; 3уравнение прямойx1–2,5x2+19=0x1+0,2x2–2,6=07x1–4x2–2=0

2 шаг. Для точки 4 ищем генеральную гиперплоскость среди всех ранее построенных плоскостей. Является ли (1–2) генеральной гиперплоскостью для точки 4.

S (т.4) = 7 – 2,5  5 + 19 > 0

S (т.3) = 2 – 2,5  3 + 19 > 0, т.е. (1-2), не является для точки 4 генеральной гиперплоскостью.

Для т. 4 генеральная гиперплоскость (1-3);

S (т.4) = 7  7 – 4,5 - 2 > 0

S (т.2) = 7  1 – 4,8 - 2 < 0, т.е. (1-3), является для точки 4 генеральной гиперплоскостью.

Мы снова имеем (N+1) точку – это 1, 3, 4.

Через каждые N точек проведем гиперплоскости (в данном случае прямые).

Для упрощения построения часть таблицы не заполняется.

Прямая1 – 33 – 41 – 4Вершина413

После обработки каждой точки генеральная гиперплоскость и плоскости повторяющиеся (одни и те же плоскости в разных таблицах) вычеркиваются.

3 шаг. Для точки 5 генеральная гиперплоскость (1–4)

Прямая1 – 44 – 51 – 5Вершина514

а также (3 – 4)

Прямая3 – 43 – 55 – 4Вершина543

4 шаг. Для точки 6 генеральная гиперплоскость (1 – 5)

Прямая1 – 55 – 61 – 6Вершина615

5 шаг. Для точки 7 генеральная гиперплоскость (1 – 6)

Прямая1 – 66 – 77 – 1Вершина716

Получили границу области работоспособности:

(1 – 2) – (2 – 3) – (3 – 5) – (5 – 6) – (6 – 7) – (7 – 1).

Окончательный шаг. Для перехода от уравнений к неравенствам необходимо в линейную форму (левая часть равенства) поставить координаты вершины.

Если величина линейной формы положительна, то знак “=” заменяется на “”, если же отрицательна то знак “=” заменяется на “”.

Пример: (1 – 2): x1 – 2,5x2 + 19 = 0.

S(т.3) = 2 – 2,5  3 + 19 > 0.

Соответствующее неравенство имеет вид: x1 – 2,5x2 + 19  0.

Полученная область имеет вид, представленный на рис.1.5.

Рис.1.5. Область решений системы неравенств.

(1 – 2)  x1 – 2,5x2 + 19  0

(2 – 3)  x1 + 0,2x2 – 2,6  0

(3 – 5)  x1 + 6x2 - 20  0

(5 – 6)  -x1 + 0,75x2 + 6,5  0

(6 – 7)  -x1 – 0,5x2 +14  0

(7 – 1)  -x1 - 2x2 + 26  0

Проверка работоспособности объекта состоит в выполнении данных неравенств. Если хотя бы одно из неравенств не удовлетворяет условию, то точка не попадает в область.

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

1.2.2. Пример удаления сбойных результатов

Для работы открыть файл or_teach.exe. В открывшемся поле системы координат ввести любые 4 точки, определяющие выпуклый четырехугольник (координаты точек записать в тетрадь). Внутрь полученного четырехугольника случайным образом ввести 4 точки, координаты которых также записать в тетрадь. Допустим, координаты полученных восьми точек следующие: {1 (73;127), 2 (190;126), 3 (84;204), 4 (217;224), 5 (115;139), 6 (94;162), 7 (153;169), 8 (179;214)}. Подсчитать средние значения координат x и y. В нашем случае xср = 138 и yср = 303 (округленные до целых значений).

Далее ввести точку, которая будет расположена за границами четырехугольника (например, точку 9 (152;43)). С учетом этой точки вычислим средние значения xcp1 = 140 и ycp1 = 282. Отбросим граничные точки: 1,2,3,4,9. Вычислим средние значения координат оставшихся точек 5,6,7,8: xcp2 = 135 и ycp2 = 274. Сравнить результат с первоначальным.

На рис.7 изображено множество точек из некоторой области. Видно, что точка 54 дает сбойный результат. Данный метод с удалением выпуклых оболочек (выпуклых слоев) предложил Тьюки. Процедура получила название «шелушение». Она позволяет при большом количестве точек измерения эффективно удалять сбойные результаты для объектов высокой размерности и, таким образом вести адаптивную обработку данных в задаче принятия решения о работоспособности объекта. При этом при вводе данных в программу or_teach.exe необходимо преобразовать исходные значения переменных Xисход. данных в координаты машинные Xмаш. По формуле линейного масштабного преобразования:

.

Например, Хисх.дан =Хисх.дан max, тогда Хмаш=Хмаш max;

Хисх.дан =Хисх.дан min, тогда Хмаш =Хмаш min.

Для учебных целей (рис.1.6) примем Хмаш max =300, Хмаш min=50.

Рис1. 6. Исключение сбойных результатов методом Тьюки.

Рассмотрим теперь пример определения попадания точки с заданными координатами (х1;х2) в полученную область. Для этого открыть Windows-приложение MS Excel.

Все необходимые данные занести в таблицу, как показано на рис.1.7.

Рис. 1.7. Рабочее окно пакета MS Excel.

В ячейках B4 и C4 записаны координаты заданной точки.

Для неравенства 1 в ячейке В8 и С8 записаны коэффициенты при переменных х1 и х2 соответственно. В ячейку F8 занесен свободный коэффициент, причем необходимо учесть, что все неравенства записаны в виде Ах1+Вх2С. В ячейке D8 записана формула подстановки точки (6;6) в линейную форму первого неравенства: 6*1+6*(-2,5)=-9. В обозначениях редактора электронных таблиц Excel данная формула будет выглядеть следующим образом: =суммпроизв($B$4:$C$4;B8:C8).

В ячейке Е8 проставлен знак неравенства 1, а в ячейку G8 занесена формула, =D8>=F8, вычисляющая логическую функцию со значениями ИСТИНА или ЛОЖЬ. Формулу в ячейке Е8 необходимо скопировать в ячейки Е9:Е13.

Окончательный результат записывается в ячейке I16 в виде формулы =И(G8:G13). То есть если во всех ячейках столбца G записано значение ИСТИНА, то, значит, точка попадает в данную область. Если же хотя бы оно из значений в столбце G принимает значение ЛОЖЬ, то результатом значения в ячейке I16 будет ЛОЖЬ. Это означает непопадание точки в данную область.

Изложенный алгоритм может служить основой для построения информационных систем контроля объектов. Пакет MS Excel позволяет реализовать алгоритм контроля для достаточно сложных объектов.

Содержание отчета по разделу №4

1. Краткое описание алгоритма описания области системой линейных неравенств.

2. Результаты описания области с различными масштабами.

3. Выводы.

Глава 5. Адаптивное построение модели регрессии при наличии сильной корреляции независимых факторов

Наличие корреляции независимых факторов в модели (4.1) и определение оценок вектора  на основе соотношения (4.2) приводят к неустойчивости решения.

В этом случае при выполнении операции обращения матрицы в выражении (4.2) следует применять псевдообращение [4]:

(4.9)

5.1. Определение псевдообратной матрицы А+(1,1) для произвольной матрицы А(1,1) на основе метода ортогонализации Грамма-Шмидта (ГШО)

  1.  Столбцы матрицы А(1,1), которые обозначим , преобразуются методом ГШО в ортогональные векторы (не обязательно, чтобы они получились ортонормированными). Из множества этих векторов образуется матрица .

Ортогонализация столбцов матрицы методом ГШО производится по уравнениям ;

,  (4.15)

где .

Здесь  - норма вектора, определяемая выражением .

Сравнивая нормы векторов , принимают решение об обнулении вектора с малой нормой.

  1.  Столбцы  матрицы  переставляются с помощью матрицы перестановок  таким образом, что

,(4.16)

где

Матрица перестановок  может быть подобрана следующим образом. Если требуется поменять местами i – столбец и j – столбец, то в единичной  - матрице  нужно сделать следующие замены: ; . В общем случае матрица  в (9.2) может включать произведение нескольких перестановочных матриц.

  1.  Столбцы  исходной матрицы А(1,1) переставляются с помощью матрицы перестановок Р(1,1), применяемой в п.2. При этом получают новую матрицу со столбцами, которые обозначим, например, так:

;

.

  1.  Вычисляются \вспомогательные коэффициенты

  1.  Вычисляется матрица В(1,1) размером  с элементами

  1.  Вычисляется матрица U(1,1) размером  с элементами

  1.  Вспомогательная матрица  находится методом ГШО из столбцов матрицы , т.е. к столбцам матрицы, сформированной из двух матриц U(1,1), E(1,1), применяют процедуру, аналогичную процедуре (4.15), но с тем отличием, что после получения каждого ортогонального вектора, начиная с первого вектора, его нормируют путем деления всех компонентов вектора на его норму. Условно эту процедуру можно представить в виде следующей цепочки преобразований:

Здесь размер матриц ;

; ;

  1.  Вычисляется матрица .
  2.  Используя матрицу, полученную в (4.15), вычисляем матрицу

.

  1.  С помощью вспомогательных матриц B(1,1), U(1,1), W(1,1), Q(1,1), P(1,1), вычисленных в пп. 2, 5, 6, 8, 9, определяется псевдообратная матрица

Оценка коэффициентов линейной регрессии определяется выражением .

Пример 1. Получение устойчивого решения системы линейных уравнений на основе использования псевдообратных матриц.

Система уравнений имеет вид

Её точное решение:

Рассмотрим систему с измененной правой частью:

Её точное решение: , т.е. решение неустойчиво.

Исследуем матрицу системы на обусловленность. Матрица А(1,1) в данном случае симметрична. Тогда на основании того, что  имеем

Обусловленность матрицы , т.е. матрица системы плохо обусловлена и необходимо применять методы повышения устойчивости решения. Рассмотрим два метода.

Построение псевдообратной матрицы для симметричной матрицы. Используя уравнения , определяем собственные векторы матрицы

;  .

После нормировки

;  .

На основании соотношения

 

определяем псевдообратную матрицу (в примере примем q=1).

.

Решение при «точных» данных

.

Решение при измененной правой части

.

Из полученных результатов видно, что решение задачи с помощью псевдообращения становится менее чувствительным к ошибкам (изменениям) исходных данных.

Построение псевдообратной матрицы на основе метода ортогонализации Грамма-Шмидта.

  1.  Используя (4.15), определяем ортогональные векторы

;  ;

;  .

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

  1.  Таким образом, число независимых столбцов k=1.

Матрица перестановок .

  1.  ;  .
  2.  .
  3.  B=0,7246.
  4.  U=0,9837.
  5.  .
  6.  W=0,5082.
  7.  .
  8.  .

Решение при «точных» данных

.

Решение при измененной правой части

,

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

5.2. Решение линейных многомерно-матричных уравнений на основе псевдообращения многомерной матрицы

Многоиндексные задачи линейного оценивания можно формализовать в виде многомерно-матричных уравнений

 Y(p,0) = H(p,q)X(q,0) + V(p,0) (4.10)

где X(q,0) – столбец оцениваемых характеристик или массивов; Y(p,0) – столбец наблюдений или измерений; H(p,q) – известная матрица преобразования; V(p,0) – столбец ошибок измерений.

Матрица H+(q,p) может быть выражена через сингулярное разложение матрицы H(p,q).

Прямое и обратное сингулярные преобразования многомерной матрицы имеют вид

, (4.11)

, (4.12)

где U(p,p), V(q,q) – многомерные ортогональные матрицы собственных элементов для матриц H(p,q)HT(p,q) и HT(p,q) H(p,q) соответственно; l1/2(p,q) – диагональная многомерная матрица сингулярных чисел H(p,q). Выражение для псевдообращения H(p,q) через сингулярное разложение запишется в виде

 (4.13)

Псевдообращение диагональных элементов l1/2(p,q) означает вычисление их обратных значений, а для «нулевых» элементов (величина «нулевых» элементов меньше некоторого малого числа t) результат псевдообращения будет равен нулю. Основная трудность вычисления псевдообратной матрицы через сингулярное разложение заключается в нахождении матриц U(p,p), V(q,q). После определения многомерной псевдообратной матрицы псевдорешение многомерного уравнения (4.10) находится в виде

 (4.16)

Это решение минимизирует норму

 ½½Y(p,0) – H(p,q)X(q,0)½½.

Адаптивное оценивание параметров модели регрессии при наличии аномальных результатов измерений.

В реальных системах обработки информации оценки  вектора регрессионных коэффициентов b для модели

 (4.1)

(X[m] – вектор наблюдаемых линейно независимых факторов;

 b – вектор неизвестных и подлежащих оценке параметров;

 [m] – помеха типа белого шума) приходится проводить в условиях аномальных измерений (АИ) Y(l), l  ().

Наибольшее распространение при решении поставленной задачи получили методы максимального правдоподобия при известном законе распределения ошибки и метод наименьших модулей, обеспечивающий устойчивое решение в условиях отклонения реального закона распределения ошибки от постулируемого априори закона распределения [7,10]. Однако все эти методы требуют в случае обнаружения АИ значительных вычислительных затрат для исключения влияния самих измерений на искомую регрессионную зависимость.

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

4.1. Метод выделения результата АИ

В основу алгоритма положен итеративный метод решения на основе МНМ. При этом оценка , полученная на основе N результатов измерения, имеет вид

(4.2)

где

      (4.3)

(4.4)

где   - оценка m-го измерения выходного сигнала.

Начальные значения R[m]=1;  соответствуют определению параметров  по методу наименьших квадратов (МНК). Далее вычисления оценок по формулам (4.2) – (4.4) проводятся итерационно до тех пор, пока изменения оценок за одну итерацию не достигнут заданной малой величины. При этом наименьший весовой коэффициент R[l] указывает на наиболее грубое l-измерение.

4.2. Рекуррентная процедура исключения АИ

Матрицу  и вектор Zn-1[n] при R[m]=1;  можно определить из , ZN[n] полученных на первой итерации, путем исключения аномальных составляющих

      (4.5)

 (4.6)

На основании леммы об обращении матриц можно записать

 (4.7)

Используя выражения (4.6) и (4.7), получим

(4.8)

4.3. Рекуррентная процедура учета текущего неаномального измерения

Эта процедура соответствует обычному рекуррентному МНК с нарастающей памятью.

Рекуррентные расчетные соотношения имеют вид:

При большом числе измерений итерационную процедуру проверки на аномальность очередного измерения следует начинать с весовой функции

В ряде случаев достаточно проверки

Величина  определяется статистическими характеристиками помехи.

Глава 6. Определение главных компонент дискретного конечного множества элементов

6.1. Определение первого главного компонента

J=N

У1 =∑ W1J*XJ

J=0

X0=1

W1J(K+1)= W1J(K)+

 * У1 [XJ(K)- W1J(K)*Y1(K)]

Коэффициент  обозначает коэффициент обучения. Он оказывает существенное влияние на сходимость алгоритма.

В процессе обучения сети одни и те же обучающие выборки предъявляются вплоть до стабилизации весов сети.

6.2. Последовательное определение множества главных компонентов в векторной форме

W2(K+1)= W2(K)+ * У2(K) [X**(K)- W2(K)*Y2(K)]

Для второго нейрона (второго главного компонента)

X**(K)=[X(K)- W1(K)*Y1(K)].

В этой формуле присутствуют только уже известные веса первого нейрона.

Аналогично для третьего нейрона

W3(K+1)= W3(K)+  * У3(K) [X**(K)- W3(K)*Y3(K)]

X**(K)=[X(K)- W1(K)*Y1(K)- W2(K)*Y2(K)].

6.3. Модификация алгоритма

1. Входной и выходной слои имеют одинаковую размерность:

X1 Xапр1

X2 Xапр2

X3 Xапр3

XN XапрN

2. Скрытый слой определяется числом главных компонент M<N.

Недостаток структуры: все нейроны подстраиваются одновременно.

Пример 1.

x111347НС-ГЛ_Компx2226814WY=w*x0,4472130,8944272,2360682,2360686,7082038,94427115,65247wT=0,4472130,894427WT*Y=112,9999993,9999986,999997226814X-XA=4,5E-074,5E-071,35E-061,8E-063,15E-061,04E-071,04E-073,13E-074,17E-077,3E-07(X-XA)^2=2,03E-132,03E-131,83E-123,24E-129,94E-121,09E-141,09E-149,79E-141,74E-135,33E-13критерий=1,62E-11(сумE^2)

Пример 2.

x113795x226141810x33917114x41236684416W-0,21737-0,434750,2119610,8478260,3908280,7816580,1178850,471557Y9,72292229,1687753,6473929,854038,9786737,96647723,8994347,748939,6325217,78717WT-0,217370,390828-0,434750,7816580,2119610,1178850,8478260,471557WT*Y=1,0000063,0000197,0000298,9999954,9999892,0000036,00000914,00001189,9999933,0000099,00002817,0000410,999973,9999661235,9999967,9999844,0000116,00001(X-Xa)^2=4,03E-113,62E-108,4E-102,18E-111,15E-109,61E-128,65E-111,84E-102,12E-114,68E-118,93E-118,04E-101,33E-091,13E-091,18E-092,4E-112,16E-104,34E-109,36E-111,55E-10Крит=7,18E-09(сумма)

6.4. Построение опорных векторов

Опорные векторы являются теми точками данных, которые ближе всего лежат к поверхности решений.

Выбор центров кластеризации осуществляется на основе метода оптимума номинала и проверки статистических гипотез.

Метод оптимизации номинала.

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

Исходная система ограничений:

(*)

Левые части обозначим:

Берём у1 как целевую функцию и на множестве (*) находим максимальное и минимальное значения у1. Затем берем у2 и опять находим максимальное и минимальное значения у2 и т.д. (yi min, yi max).

- среднее значение.

Тогда система ограничений примет вид:

Это система линейных алгебраических уравнений.

.

Пример.

Имеется система ограничений:

Обозначим левые части:

Средние значения: , так как max=10, min=0.

Вместо уi подставляем :

Решение: , .

Глава 7. Адаптивный итеративный метод восстановления входного сигнала измерительной системы

Для уравнения (2.8) итерационная процедура может быть представлена в виде [6]:

(3.1)

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

(7)

где Т (шаг интегрирования) и  определяются точностью интегрирования, К – матрица преобразования интегрирующего оператора, для примера S = 0…7, M = =0…7, I = 1…2000 (число итераций). За счет выбора малого значения = 0,1 обеспечиваем сходимость итерационной процедуры. Итерационная процедура записана для реализации в пакете MATHCAD.

Пример 1. Восстановление входного сигнала интегрирующего звена  с помощью итерационных процедур.

Начальные значения входного сигнала принимаются равными выходному сигналу.

Входной сигнал: XT = [1 2 3 4 3 2 1 1].

Выходной сигнал: YT = [0,1 0,3 0,6 1 1,3 1,5 1,6 1,7]. T=0,1, =0,1.

.

восстановленный сигнал = [1 2 3 4 3 2 1 1].

Пример 2. Восстановление входного сигнала апериодического звена

Для восстановления входного сигнала используем итерационную процедуру (3.2). Начальные значения входного сигнала принимаются равными выходному сигналу. Импульсная переходная функция рассчитывается по формуле K(t) = e–t. Матрица преобразования имеет вид

.

Входной сигнал ХТ = [1 2 3 4 3 2 1 1].

Выходной сигнал: YT = [0,1 0,29 0,563 0,909 1,123 1,216 1,2 1,186]. T=0,1,  = 0,1.

Восстановленный входной сигнал после 2000-й итерации

= [1 2 3 4 3 2 1 1].

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

7.1. Оптимальная коррекция динамических погрешностей измерений

В данном пособии принята на интервале наблюдения модель входного сигнала полиномиального типа

. (3.3)

В качестве моделей линейной динамической измерительной системы приняты передаточные функции вида:

  (3.4)

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

Рис. 3.1. Схема оптимальной фильтрации при наличии помехи типа «белый шум»

Необходимо синтезировать линейные фильтры Wfi, i=1,2, выделяющие с наименьшей дисперсией ошибки из выходного сигнала измерительной системы Yn(t) составляющие, пропорциональные контролируемым параметрам b1,b2,…,bn. Сигналы Z1(t), Z2(t) (рис. 3.1) являются случайными из-за случайности параметров b1,b2. Желаемым выходным сигналом mj(t) синтезируемого линейного фильтра Wfj является сигнал

. (3.5)

Сформируем ошибку при определении параметра bj с помощью фильтра Wfj в виде

(3.6)

и определим оператор Wfj из условия минимума дисперсии этой ошибки

. (3.7)

Рассмотрим вначале решение данной задачи для случая помехи n(t) типа «белого шума» с корреляционной функцией Rn(t) = n*d(|t|). Затем на основе данного решения произведем обобщение на случай произвольной помехи.

Оптимальные несмещенные оценки  в случае помехи типа «белого шума» определяются соотношением:

. (3.8)

Элементы матрицы А и вектора  равны

(3.9)

. (3.10)

Точность оценок характеризуется дисперсионной матрицей ошибок

, (3.11)

где n – интенсивность белого шума.

В случае дискретных измерений выходного сигнала измерительной системы в моменты t=nT уравнения (3.9), (3.10) перепишутся в виде

, (3.12)

. (3.14)

Синтезируем на основе рассмотренной схемы рис. 3.1 оптимальный фильтр в случае помехи, отличной от «белого шума».

Преобразуем расчетную схему, представленную на рис. 3.2. Помеха n(t) характеризуется нулевым математическим ожиданием и корреляционной функцией Rn(t). Будем искать оптимальный фильтр в виде последовательного соединения двух звеньев F1 и F2j, j=1,2. Звено F1 такое, что преобразует стационарную произвольную помеху n(t) в стационарный «белый шум». Эквивалентная расчетная схема представлена на рис. 3.2.

Здесь F1-1 представляет собой формирующий фильтр для помехи n(t) c корреляционной функцией Rn(t). Окончательно схему (рис. 3.2) можно представить в виде рис. 3.3.

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

Глава 8. Нейронная сеть Хопфильда

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

Весовые значения сети Хопфильда : W=

Первый столбец представляет весовые значения, связанные c первым элементом нейронной сети. Столбец 2-весовые значения, связанные со вторым элементом.

Когда элемент обновляется, его состояние изменяется в соответствии с правило Sj=sgn()

Работа сети.

Входной вектор задает начальные состояния всех элементов.

Элемент для обновления выбирается случайным образом.

Выбранный элемент получает взвешенные сигналы от всех остальных элементов Sj=sgn() и изменяет свое состояние.

Выбирается другой элемент и процесс повторяется до установившегося состояния.

Весовая матрица, соответствующая ”сохранению” векторов Xi, задается формулой:W=, в которой все диагональные элементы должны быть установлены равными нулю (поскольку диагональные элементы задают автосвязи, а элементы сами с собой, естественно, не связаны).

Сеть Хопфильда

№1.

№2.

Диагональные элементы обнулены

Работа сети.

Случайная последовательность обработки нейронов:

на выходе

Сначала рассмотрим элемент S1

S1=1

То есть первый нейрон сохранил свое значение

Теперь рассмотрим элемент S2

S2= –1

То есть второй нейрон сохранил свое значение

Теперь рассмотрим элемент S3

S3=1

То есть третий нейрон сохранил свое значение.

Таким образом, сеть Хопфильда считает, что на вход нейронной сети подан второй вектор (из двух сданных на хранение).

Глава 9. Нечеткие нейронные сети

9.1. Общая схема модели управления в условиях неопределенности

Рис. 1. Общая схема модели управления в условиях неопределенности

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

Второй слой формирует принадлежности преобразованных нечетких переменных с помощью преобразователя F (рис.1).

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

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

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

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

Обусловленная НС функция (или оператор) могут быть произвольными при легко осуществимых требованиях к структурной сложности сети и наличия нелинейности в Передаточных (активационных) функциях нейронов. При моделировании реальных сложных систем значения функции системы S или оператора F[*] определяются на основе экспериментов или наблюдений, которые проводятся лишь для конечного числа параметров х. При этом значения как x, так и y измеряются приблизительно, и подвергнуты ошибкам разной природы (т. н. «мягкие вычисления»).

Цель моделирования - получение значений системных откликов при произвольном изменении х. В этой ситуации в условиях определенности (например, статистической) может быть успешно применена информационная (статистическая) модель G исследуемой системы S. Укажем, что ИМ для задач управления в условиях определенности могут строиться на основе традиционных методов непараметрической статистики. Эта наука позволяет строить обоснованные модели систем в случае большого набора экспериментальных данных (достаточного для доказательства статистических гипотез о характере распределения) и при относительно равномерном их распределении в пространстве параметров. Однако при высокой стоимости экспериментальных данных, или невозможности получения достаточного их количества (как, например, при построении моделей сложных производственных аварий, пожаров и т. п.), или их высокой зашумленности, неполноте и противоречивости такие модели являются неработоспособными. В особенности опасно использование этих моделей при малых статистических выборках, так как полученные на них законы распределения могут быть неустойчивыми, т.е. при увеличении (уменьшении) количества элементов выборки закон распределения может принципиально изменяться. На это впервые обратил внимание академик Ю. В. Линник.

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

Информационные модели по своей природе всегда являются неполными. Пространства входных - выходных переменных в общем случае, не могут содержать все важные для описания параметры системы. Это связано как с техническими ограничениями, так неограниченностью наших представлений о моделируемой системе. Кроме того, при увеличении числа переменных увеличиваются требования к объему экспериментальных данных, необходимых для построения модели. Эффект неучтенных (скрытых) параметров может повлиять на однозначность моделирования системы S.

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

Экспериментальные данные, как правило, имеют произвольное распределение в пространстве переменных задач. Как следствие, получаемые модели будут иметь неодинаковую достоверность и точность в разных областях изменения параметров.

Экспериментальные данные могут содержать изъятые значения (например, вследствие потери информации, отказа датчиков, невозможности проведения полного набора экспериментов и т.п.). Произвол в интерпретации этих значений, опять-таки, ухудшает свойства модели. Такие особенности в данных и в постановке задач требуют особого отношения к ошибкам ИМ.

9.2 Концепция измерений, основанная на подходе Заде. Понятие о нечетких множествах

3.1.Понятия о нечетких множествах.

переменная = , можно xi ставить в числителе.

Пример

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

1. Мало

;

2. Очень мало ;

ОЧЕНЬ МАЛО = (µмало)2

3. Немало

m немало =1-m мало

4.

5. y=f(x), f – четкий функциональный преобразователь, x – нечеткая переменная.

6. y1=f (x, y), f - четкий функциональный преобразователь, x, y – нечеткие переменные.

µy1 = µx^µy

Ù - означает минимум

Например,

f(x, y) – это, например, x+y; x/y; x*y; и т.д.

3.2. Примеры формирования нечетких множеств

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Мало =

Велико =

Не очень мало и не очень велико = (не очень мало) Ç (не очень велико).

Очень мало

Не очень мало

 

Очень велико

Не очень велико

Не очень мало и не очень велико = (не очень мало) Ç (не очень велико)

(не очень мало) или (не очень велико)

3.3. Построение функций принадлежности.

Коэффициент принадлежности mx отождествляют с вероятностью появления «x».

Количественная оценка m выводится путем сравнения свойств нечеткого множества.

Пример:

Петр похож на Ивана.

Пусть из «m» признаков (свойств) у Петра «k» признаков (свойств) является общими с Иваном.

 mПетр похож на Ивана = . Если признаки неэквивалентны, то при расчете следует учитывать их весовые коэффициенты (pi).

.

- суммируется вероятные коэффициенты с общими «П» и «И» свойствами. Конечно, можно заменить Петра на кардиограмму сердца Петра,

 m =

Величина m определяется с помощью экспертных оценок, то есть путем опроса (голосования) специалистов.

При этом может предлагаться методика, основанная на применении стандартного набора графиков функций принадлежности. Специалист выбирает наиболее подходящий ему график из стандартного набора, а затем в диалоге с ЭВМ задает принадлежность.

9.3. Перспективы использования теории нечетких множеств при обработке измерений

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

Библиографический список

  1.  Владимирский Б.М., Горстко А.Б., Ерусалимский Я.М. Математика. Общий курс. СПб: Лань, 2002.-960с
  2.  Гласс Дж., Стенли Дж. Статистические методы в педагогике и психологии. - М.: Прогресс, 1976. - 496 c.
  3.  Математические методы обработки и интерпретации результатов тестовых экспериментов. Практикум/РГМУ: сост. Булаев М.П., Дорошина Н.В., Кабанов А.Н. Рязань, РГМУ, 2005. – 31 с.
  4.  Менделевич В.Д. Клиническая и медицинская психология -М.:2002.-592 c.
  5.  Осовский С. Нейронные сети для обработки информации. -М.: Финансы и статистика, 2002.-344 c.
  6.  Рассел Стюарт, Норвиг Питер. Искусственный интеллект: современный подход. - М. : Издательский дом «Вильямс», 2007. - 1408 с.

Содержание

Начало

Начальные условия

i=0, ,, 

i=i+1

i=1

Формир. Ф()

Поиск * с точностью 

||<=

Конец

Да

Да

3

4

5

1

x3

x1

5

x2

x4

4

5

3

1

2

4

3

2

1

7

6

x2

1   2    3   4    5    6    7   8    9  10  11   x1

10

9

8

7

6

5

4

3

2

1

x7

x6

x5

3

2

1

5

4

5

3

1

2

3

2

1

5

Рис. 3.3. Схема оптимальной фильтрации при помехе отличной от «белого шума»

Рис. 3.2. Схема оптимальной фильтрации при помехе, отличной от «белого шума»

Построение

(N+1)-й гипер-

плоскости

Выбор первых

(N+1) граничных

точек

начало

1 шаг?

2

3

Все генер. плоскости найдены?

Генеральных плоскостей 2? найдены?

4

5

6

1

+

+

х1

х2

xn

.

.

.

+

Y

φ1

φ2

w1

w2

y

b2

W21

W11

f1

b1

х1

+

х2

F

W21

+

Поиск и удаление

одинаковых гиперплоскостей

Все граничные точки?

Выбор следующей

по порядку граничной точки

Поиск

генеральной

гиперплоскости

Есть генер. гиперплоскость

Определение

координат гранич.

точек генеральн.

гиперплоскостей

Определение

знаков неравенств

“”, “”

конец

1

22

3

4

5

62

11

10000000

9

8

7

12

Да

Да

Да

Да

Нет

Нет

Нет

Нет

Нет

Да

X

Y

Z

4

3

2

1

Риc1.3Пример построения гиперплоскости

1   2    3   4    5    6    7   8    9  10  11   x1

5

3

2

1

7

6

x2

10

9

8

7

6

5

4

3

2

1