комплекс лабораторных работ. Методические указания по выполнению лабораторных работ по дисциплине Модели и алгоритмы распознавания и обработки данных
 Скачать 4.91 Mb.
|
|
2. Сколько слоев имеет сеть Хемминга? 3. Какую роль играют обратные связи? 4. Каким образом определяется распонаваемый образ? 5. Какой вид имеет авктивационная функция для сети Хеммнга? 6. Совпадает ли количество входов и выходов в сети Хемминга? Приложение: 1. Варианты интерфейса с результатами работы программы 34 Рис. 2. Зашумлённая цифра 7. Рис. 3. Зашумлённая цифра 5. 1. Листинг процедур Процедура распознавания зашумлённого образа void CHammingDlg::OnRecognition() 35 { // TODO: Add your control notification handler code here Invalidate(); UpdateWindow(); int k, i, j, iter=0; for(k=0; k T = m_m*m_n/2.0; srand((unsigned)time(NULL)); double e = rand()%((m_m*m_n))/(m_m*m_n*100.0); //Вычисление состояния нейронов первого слоя for(k=0; k //Инициализация значений аксонов второго слоя полученными значениями for(k=0; k //Вычислить значения аксонов второго слоя for(k=0; k } iter++; } while(Change()); //Определение схожих образов double etalon=-100; int index[10], l=0; for(k=0; k {etalon = y2new[k]; index[0] = k;} for(k=0; k } 36 } sprintf(str,"Число итераций: %d", iter); pdc2->TextOut(50, 60+20*s, str); s++; m_results.ReleaseDC(pdc2); } Процедура проверки изменения выходов нейронов второго слоя int CHammingDlg::Change() { for(int k=0; k } Считывание эталонных образов из файла FILE *f; if((f=fopen("cifir.txt","r"))==NULL){printf("Невозможно открыть файл!\n"); return FALSE;} for(int k=0; k Кохонена) Цельработы. Научиться использовать метод кластерной обработки данных в виде самоорганизующихся карт Кохонена». Теоретическая часть. Существуют задачи анализа данных, которые затруднительно представить в числовой форме. При этом нужно извлечь данные, принципы отбора которых заданы нечетко: выделить надежных партнеров, определить перспективный товар и т.п. Также необходимо на основании имеющихся априорныхданных получить прогноз на дальнейший период. Существует метод, позволяющий автоматизировать все действия по поиску закономерностей – метод анализа с использованием самоорганизующихся карт Кохонена. Самоорганизующаяся карта Кохонена (англ. Self-organizing map — SOM) — нейронная сеть с обучением без учителя, выполняющая задачу визуализации и кластеризации. Является методом проецирования многомерного пространства в пространство с более низкой размерностью (чаще всего 37 двумерное), применяется также для решения задач моделирования, прогнозирования и др. Каждый объект характеризуется набором различных параметров, описывающих его состояние. Например, параметрами будут данные из финансовых отчетов. Эти параметры часто имеют числовую форму или могут быть приведены к ней. Таким образом, нам надо на основании анализа параметров объектов выделить схожие объекты и представить результат в форме, удобной для восприятия. Эти задачи решаются самоорганизующимися картами Кохонена. Пусть объект расположен в трехмерном пространстве. Тогда каждый объект с признаками можно представить в виде точки в данном пространстве, и пронормировать эти признаки в интервал [0,1]), в результате чего все точки попадут в куб единичного размера. Отобразим эти точки. Расположение объектов в пространстве На рисунке видно, как расположены объекты в пространстве, причем легко заметить участки, где объекты группируются, т.е. у них схожи параметры, значит, и сами эти объекты, скорее всего, принадлежат одной группе. Но так можно поступить только в случае, когда признаков немного. Значит, надо найти способ, преобразующий данную систему в простую для восприятия, желательно двумерную систему (потому что уже трехмерную картинку 38 невозможно корректно отобразить на плоскости) так, чтобы соседние в искомом пространстве объекты оказались рядом и на полученной картинке. Для этого используем самоорганизующуюся карту Кохонена. В первом приближении ее можно представить в виде «гибкой» сети. Предварительно «скомкав», бросаем сеть в пространство признаков, где уже имеются объекты, и далее поступаем следующим образом: берем один объект (точку в этом пространстве) и находим ближайший к нему узел сети. После этого узел подтягивается к объекту (т.к. сетка «гибкая», то вместе с этим узлом так же, но с меньшей силой подтягиваются и соседние узлы). Затем выбирается другой объект (точка), и процедура повторяется. В результате получется карта, расположение узлов которой совпадает с расположением основных скоплений объектов в исходном пространстве. Полученная карта обладает следующим замечательным свойством – узлы ее расположились таким образом, что объектам, похожим между собой, соответствуют соседние узлы карты. Теперь находим, какие объекты попали в какие узлы карты. Это также определяется ближайшим узлом – объект попадает в тот узел, который находится ближе к нему. Вид пространства после наложения карты В результате данных операций объекты со схожими параметрами попадут в один узел или в соседние узлы. Хотя задача поиска похожих объектов и их группировки решена, но на этом возможности карт Кохонена не заканчиваются. Они позволяют также представить полученную информацию 39 в простой и наглядной форме путем нанесения раскраски полученной карты (точнее ее узлы) цветами, соответствующими интересующим нас признакам объектов. Также можно получить информацию о зависимостях между параметрами. Нанеся на карту раскраску, соответствующую различным статьям отчетов, можно получить так называемый атлас, хранящий в себе информацию о состоянии рынка. Можно анализировать, сравнивать расположение цветов на раскрасках, порожденных различными параметрами, тем самым получая все новую информацию. При всем этом описанная технология является универсальным методом анализа. С ее помощью можно анализировать различные стратегии деятельности, производить анализ результатов маркетинговых исследований, проверять кредитоспособность клиентов и т.д. Ход работы Импортируйте в АП «Deductor» исходные данные из файла C:\Program\Files\BaseGroup\Deductor\Samples\CreditSample.txt. Процесс построения карты Кохонена состоит из 10 этапов. Запустите мастер обработки, в котором в разделе «Data Mining» выберете способ обработки данных «Карта Кохонена», нажмите «Далее». В окне настройки назначения столбцов необходимо обозначить столбцы «Код» и «№ паспорта» как «Неиспользуемые» (так как значения этих столбцов уникальны, а это не позволит их классифицировать по общим признакам). Определите поле «Давать кредит» как «Выходное». 40 Пример настройки назначений столбцов Настройку обучающей выборки и параметров карты Кохонена можно оставить без изменений. Настройка параметров карты Кохонена Настройте параметры остановки обучения, указав уровень допустимой погрешности, если он будет превышен, анализ данного множества будет прекращен. Можно оставить значения «по умолчанию». 41 Настройка параметров остановки обучения. Настройку параметров обучения также оставьте без изменений. Далее запустите процесс построения карты Кохонена, нажав кнопку «Пуск». Итог построения карты Кохонена На вкладке «Выбор способа отображения данных» поставьте галочку напротив пункта «Самоорганизующаяся карта Кохонена». Теперь необходимо провести настройку отображения карты: 42 отметьте разделы «Давать кредит» и «Кластеры» и другие разделы – по желанию. Настройка отображений карты Кохонена Далее задайте имя, метку и описание карты (по желанию). В результате получатся карты Кохонена, подобные изображенным на рисунке. Примеры карт Кохонена Щелкнув левой клавишей мыши по любому шестиугольнику на любой карте, выделятся соответствующие ему ячейки на остальных картах, в том 43 числе на картах «Давать кредит» и «Кластеры». При этом на шкалах в нижней части карт отобразятся значения соответствующих параметров. Задание 1. Выполните описанные выше действия по построению карт Кохонена. Проанализируйте результаты, что можно сказать о вероятности возврата кредита для групп 2, 3 и 4? 2. Используя различные отображения карты Кохонена, постройте 3-4 правила выдачи кредитов. Содержание отчета 1. Цель работы. 2. Краткое описание хода работы 3. Вид карт Кохонена 4. Ответы на вопросы. 5. Листинг программы 6. Заключение. Вопросы: 1. Для чего используются карты Кохонена? 2. По какому принципу происходит перенос многомерного пространства на пространство меньшей размерности? 3. Что обзначает фраза “Победитель берет все” 4. Какие метрики испоьзуются пи разбиении на кластеры 5. Целессобразность применения карт Кохонена при клстеризации данных Лабораторная работа №6. Классификация данных Цель работы. Целью данной лабораторной работы является исследование способности нейронной сети решать задачи классификации. Сеть необходимо обучить классификации по пяти классам по 10-20 числовым признакам. Используемая модель: одномерная сеть Кохонена. Теория. Задача классификации заключается в идентификации объекта и отнесении его к одному из нескольких множеств. При этом задача классификации предполагает, что множества попарно не пересекаются. Применительно к нейронным сетям задачу классификации можно поставить 44 следующим образом: пусть имеется N множеств D1,D2…Dn признаков объектов. Сеть обучается на парах векторов X и Y, где: X = (x1,x2…xm) – входной вектор признаков; Y = (y1,y2…yn) = C(X) – выходной вектор, классифицирующий вектор X. При этом возможно несколько случаев: 1. Y = k, классификатор имеет скалярный характер. k – порядковый номер множества, к которому относится X. 2. Y = (y1,y2 …yk … yn). При этом только yk=1, остальные компоненты вектора равны 0. Таким образом работает звено Кохонена 3. Y = (y1,y2 … yn). При этом каждая компонента yk характеризует степень принадлежности к множеству Dk. В режиме нормального функционирования сеть по входному вектору X выдает вектор Z по правилам, аналогичным описанным для векторов Y. Точность решения определяется статистикой: сколько раз вектор Z правильно классифицировал объект с признаками X, соотнося его с той или иной группой Dk. Для пункта 3 возможно вычисление погрешности, при наличии функции-скаляризатора степени принадлежности вектора X к множествам Dk. Задача может быть дополнена введением «шума», однако смысл от этого не изменится. Шум лишь изменит границы областей D1…Dn. Для решения задачи классификации с линейной и нелинейной разделимостью классов используются классические модели нейронных сетей: многослойный персептрон и рекуррентные сети на его основе, радиально-базисные сети, сети Кохонена, гибридные сети, рекуррентные самоорганизующиеся сети. При наложении множества объектов друг на друга, то задача классификации становится более общей и предполагает, что объект характеризуется степенью принадлежности к тому или иному множеству, то есть имеет место задача классификации с вероятностной разделимостью классов. Ход работы: 1. Необходимо выбрать предметную область, отобрать не менее 10 числовых характеристик объектов и задать их диапазоны. 45 2. Сгенерировать обучающую выборку размерностью от 10 до 20 примеров для каждого класса. Предусмотреть нормализацию входных векторов. 3. Написать программу, имитирующую работу нейронной сети Кохонена 4. Провести обучение сети Кохонена по алгоритму Кохонена с прямоугольным соседством. 5. Исследовать эффективность алгоритмов обучения от значения коэффициента обучения. 6. Исследовать зависимость погрешности классификации от алгоритма обучения. 7. Исследовать зависимость погрешности классификации от объёма обучающей выборки. 8. Исследовать зависимость погрешности классификации от числа итераций обучения. Cодержание отчета 1. Цель лабораторной работы. 2. Краткое описание хода работы. 3. Файл обучающей выборки. 4. Результатов работы нейросетевого клссификатора Выводы по результатам работы. 5. Ответы на вопросы. 6. Ответы на вопросы. Вопросы 1. В чем суть классификации данных? 2. Отличие классификации от кластеризации. 3. Какие существуют методы классификации кроме нейросетевого? 4. Целесособразность применения нейросетевого метода для лссификации данных. 5. Как определяется погрешность классификации? Лабораторная работа №8 . Алгоритмы распознавания прецендентов 46 Цель работы: изучить существующие алгоритмы распознавания образов в виде прецендентов. Теоретическая часть. Обзор алгоритмов распознавания образов 1. Алгоритм ближайшего соседа Процедуравзятая в качестве решающего правила: оставить в памяти машины все реализации обучающей выборки и классифицируемую точку (образ) отнести к тому классифицирующему образу, чья реализация оказалась ближайшей. Это – правило ближайшего соседа. Учитывая, что результаты реальных измерений свойств могут быть «зашумлены», можно использовать правило k ближайших соседей: если больше половины из k ближайших соседей принадлежат образу i, то и объект (точка) q относится к образу i. 2. Метод потенциальных функций Иногда в «голосовании» принимают участие все реализации обучающей выборки, но с разными весами, зависящими от расстояния. Смысл алгоритма заключается в излучении точками каждого класса потенциала, величина убывающего с расстоянием. Характер убывания может быть самым различным. В точке q определяется «притяжение» к каждому из классов. Если окажется, что какая-то точка распознается с ошибкой, то можно изменить картину потенциального поля. Доказана сходимость алгоритма к оптимальному при увеличении обучающей выборки и конечность числа шагов при не слишком сложной («вычурной») картине потенциального поля. 3. Алгоритм STOPL Сложность заключается в комбинаторном характере задачи - вечный поиск компромиса между требуемой скоростью и затратами памяти. Для сокращения перебора выбирают точки пограничные точки наибольшего риска. Пусть rin - расстояние до своей ближайшей точки, rout - до чужой. Тогда отношение W =rin / rout характеризует величину риска быть опознаной в качестве чужого образа. Среди точек каждого образа выбираются в качестве 47 прецедентов по одной точке с максимальным значением W. После этого распознаются все точки обучающей выборки с опорой на прецеденты по методу ближайшего соседа. Среди опознанных неправильно вновь выбирается точка с максимальным значением W и ею пополняется список прецедентов. Процесс повторяется до тех пор, пока все точки обучающей выборки не будут распознаваться правильно. 4. Метод дробящихся эталонов - алгоритм ДРЭТ Стремимся опять же к безошибочному распознаванию обучающей выборки, но для выбора прецедентов используется метод покрытий обучающей выборки каждого образа простыми фигурами (которые можно усложнять при необходимости). В качестве покрывающих фигур выбираются гиперсферы. Для каждого образа строится гиперсфера минимального радиуса, покрывающая все его точки (реализации). Значения радиусов гиперсфер и расстояния между центрами позволяет определить непересекающиеся гиперсферы. Это - эталоны первого поколения. Если сферы пересекаются, но пересечения пусты, то такие гиперсферы (центры и радиусы) также относятся к эталонам первого поколения. Приэтом область пересечения считается принадлежащей 21 гиперсфере меньшего радиуса. Эталоны второго поколения строятся только для пересечений, содержащих точки двух или более образов. Если эталоны второго поколения также пересекаются, то процесс продолжается до полной надежности распознавания обучающих выборок. Контрольные образцы классифицируются по попаданию в эталонные гиперсферы. Если контрольная точка не попадает в гиперсферу, то определяется ближайшие и далее используется метод ближайшего соседа. 5. Логические решающие правила. В задачах распознавания образов зачастую требуется, чтобы компактные точки в n-мерном пространстве признаков были компактными и несовпадающими в проекциях на координатные оси (гипотеза локальной компактности). Конечно, это не 48 всегда так. Например, все трехмерные геометрические фигуры (сферы, пирамиды, параллелепипеды) могут быть синими. Но здесь мы сталкиваемся с проблемой ситуативной информативности признаков. Очевидно, фигуры с геометрической точки зрения не будут классифицировать по цвету. Обычно, проекции на координатные оси пересекаются, но могут выглядеть по разному и это дает надежду, что комбинация несовпадающих проекций на несколько осей позволит построить эффективное решающее правило за счет сокращения размерности признакового пространства. Решающие правила, учитывающие разницу в проекциях разных образов имеют вид «Если- условие-то- следствие» и получили наименование логических решающих правил (ЛРП). 6. Алгоритм CORAL Выделяется подмножество значений Xjv ∈ Xj признака Xj. Для сильных признаков – это интервал значений, для шкал порядка - ряд соседних порядковых позиций, для шкал наименований - одно или несколько имен. Обозначается факт, что некоторое значение признака Xj объекта ai принадлежит подмножеству Xjv как J(ai, Xjv), факт попадания объекта a в область v, образованную границами подмножеств Xjv, т.е. в гиперпараллелепипед , запишется в виде логического высказывания: n’ ≤ n, где n - размерность признакового пространства. Число n’ называется длиной высказывания. Логической закономерностью называется высказывание, удовлетворяющее двум условиям: где w - индекс объектов своего образа, w − - индекс всех чужих объектов, mw - число всех своих объектов, mw− - число чужих объектов, mws - число своих, удовлетворяющих высказыванию S, mws− - число чужих, 49 удовлетворяющих тому же высказыванию S, 23 α, β - некоторые величины в диапазоне от 0 до 1. Желательно, чтобы высказывание S отбирало больше своих объектов и поменьше чужих, т.е. чтобы α было как можно большим, а β - как можно меньшим. Набор закономерностей называется покрывающим для образа w, если для любой его реализации выполняется хотя бы одна закономерность из этого набора. Желательно, чтобы число закономерностей в наборе было минимальным. Поиск закономерностей начинается с больших значений α (например, α = 1) и малых значений β ≈ 0.02. Просматриваются все подмножества значений первого случайно выбранного признака и находится высказывание S, удовлетворяюшее условиям 1 и 2. Если таковое не находится, то процесс поиска продолжается при более низком пороге α вплоть до α = 0.5. Если и в этом случае нет результата, то увеличивается β в предельно допустимой доле «чужих среди своих». Если условия 1 и 2 не выполняются и при α = β = 0.5., то делается переход к рассмотрению второго признака, случайным образом выбранным из оставшихся. Если условия 1 и 2 на каком-то шаге выполняются, то объекты своего образа, удовлетворяющие высказыванию S, из дальнейшего рассмотрения исключаются. Для оставшихся объектов образа w длина высказывания увеличивается на единицу. Процесс продолжается до получения покрывающего набора закономерностей для всех объектов образа w. Аналогично строятся покрывающие наборы и для всех других распознаваемых образов. Можно потребовать, чтобы алгоритм делал для каждого образа не по одному, а по несколько покрывающих наборов, что соответствует высказыванию Р. Фейнмана о том, что можно говорить о понимании явления, если в состоянии объяснить его несколькими способами. С этой целью после получения первого покрытия исключают из рассмотрения первый признак, включенный в это покрытие, и процесс поиска закономерностей начинается с другого случайно выбираемого 50 признака. Распознавание контрольного объекта q с помощью покрывающих наборов закономерностей сводится к проверке того, каким высказываниям удовлетворяют его характеристики. Если таких высказываний одно или несколько и все они находятся в списке образа w, то объект q распознается в качестве реализации образа w. Если же объект q удовлетворяет закономерностям нескольких образов, то решение принимается в пользу того образа, которому принадлежит закономерность с наибольшим значением величины Pws. Анализ общего списка закономерностей может показать, что некоторые признаки из исходной системы X в них отсутствуют. Это означает, что они оказались неинформативными и в процессе принятия решения на них можно не обращать внимания. Для каждого i-го образа подмножество информативных признаков может оказаться разным. А это значит, что при проверке гипотезы о принадлежности объекта к тому или иному образу, нужно анализировать не все пространство признаков, а его информативное подпространство, что хорошо согласуется с интуитивными методами неформального распознавания. 7. Метод случайного поиска с адаптацией (алгоритм СПА) Единичный отрезок разбивается на g участков одинаковой длины (1/g). Каждому участку сопоставляется свой признак: первому - первый, второму - второй и т.д. Запускается датчик случайных чисел с равномерным распределениют в диапазоне 0..1. После n шагов работы выбирается n признаков. По числу ошибок оценивается качество распознавания. Такая 25 процедура проделывается r раз. В итоге будет получен список оценок L = (α1, ..., αr). Теперь можно упорядочить список L по возрастанию α, т.е. по убыванию качества распознавания, и ввести систему поощрений и наказаний. Участки, соответствующие признакам, дающим лучший результат, увеличиваются, «худшие» - уменьшаются, но так, чтобы суммарная длина по-прежнему была равна Испытывают r новых признаковых подсистем, но теперь вероятность 51 попадания на «лучшие» участки выше, чем на плохие. Продолжают процесс адаптации таким образом, что длина участков признаков, регулярно попадающих в самые информативные подсистемы, увеливается на величину h < 1/g, а для самых неинформативных длины их участков уменьшаются. После некоторого количества циклов поиска и адаптации, процесс стабилизируется. Алгоритм СПА был протестирован для систем, в которых возможен полный перебор сочетаний признаков. Задание. Составить программу, реализующую один из предложенных алгоритмов. Вариант 1. Написать программу, выполняющую поиск слова в строке при помощи алгоритма ближайших соседей. Вариант 2. Написать программу, реализующую поиск слова в текстовом файле с помощью алгоритма ближайших соседей. Вариант 3. Написать программу, реализующую поиск слова в текстовом файле с помощью алгоритма STOPL. Вариант 4. Написать программу, реализующую поиск слова в текстовом файле с помощью алгоритма CORAL. Вариант 5. Написать программу, реализующую поиск слова в текстовом файле с помощью метода случайного поиска с адаптацией. Вариант 6. Написать программу, реализующую поиск слова в текстовом файле с помощью алгоритма ДРЭТ. Вариант 7. Написать программу, реализующую поиск слова в текстовом файле с помощью алгоритма потенциальных функций. Содержание отчета 1. Цель лабораторной работы 2. Краткое описание хода работы 3. Схема алгоритма метода распознавания прецендентов 4. Результатов работы программы распознавания прецендентов 5. Выводы по результатам работы 52 6. Ответы на вопросы Вопросы 1. Перечислите существующие алгоритмы распознавания образов. 2. Описание алгоритма ближайших соседей. 3. Описание алгоритма потенциальных функций. 4. Описание алгоритма STOPL. 5. Описание алгоритма CORAL. 6. Описание метода случайного поиска с адаптацией. 7. Описание алгоритма ДРЭТ. Лабораторная работа № 8. Фильтрация данных Цель работы. Ознакомиться с методом фильтрации данных фильтром Калмана. Оценить возможность применения фильтра Калмана на практике. Теоретическая часть. Фильтр Калмана применяют в разных областях – от радиотехники до экономики. В экономике, например, измеряемой величиной могут быть курсы валют, колебания цен. Каждыё день курс валют разный, т.е. каждый день “его измерения” дают нам разную величину. Измерения всегда идут с некоторой ошибкой. В простейшем случае описанное можно свести к следующему выражению: z=x+y, где x – истинное значение, которое нужно измерить, y – ошибка измерения, вносимая измерительным прибором, а z – измеряемая величина. Задача фильтра Калмана состоит в том, чтобы по измеренной z определить истинное значение x, т.е. необходимо отфильтровать (отсеять) из z истинное значение x – убрать из z искажающий шум y. Для прогнозирования цены отдельного вида продукции предлагается рассмотреть следующую стохастическую нестационарную модель, описывающую процесс изменения цены: 53 или в виде уравнения в дифференциальной форме: где p(t) – значение цены в момент времени t; f(t,p(t),z(t)) – скорость изменения цен во времени – непрерывная функция по переменной t, определяющая тренд цены и восстанавливаемая по статистической информации; F(t,p(t)) – среднеквадратичное отклонение; ω – винеровский процесс; v – случайная пуассоновская мера с параметром λ(t); v t – случайная величина, вызывающая приращение цены согласно закону P(c(v)), P(c(v)) = δ(v-a), a>0. Первый элемент в правой части представленных выше уравнений, это тренд цены, зависящий от величины предложения и от потребности покупателей в данном товаре. Кроме того, цены постоянно колеблются около своего тренда вследствие аддитивного воздействия на них случайных факторов, и будем считать, что приращения цены - независимые величины. Можно утверждать, что в краткосрочном периоде закон распределения приращений процесса изменения цен близок к нормальному. Также будем считать, что трендовая составляющая не оказывает влияния на случайную, и наоборот, случайные изменения не влияют на характер тренда. Второй элемент в правой части уравнений отражает именно случайную составляющую – незначительные колебания цен около своего тренда. На практике часто приходится наблюдать резкие изменения цен - скачки. Их появление свидетельствует о нестабильности рынка или экономики в целом или об ее зависимости от внешних факторов: политических, спекулятивных и других. Причем появление таких скачков не связано с чисто сезонными колебания ми цены. Третий элемент в правой части уравнений отражает эту случайную составляющую, причем 54 предполагается, что величины скачков будут всюду положительными. Время появления скачков можно моделировать с помощью пуассоновского случайного процесса. Амплитуды скачков случайны и закон распределения их вероятности может быть восстановлен по тем же статистическим данным. Отсюда как следствие имеем, что промежутки между скачками характеризуются показательным распределением. Любая реализация цены есть решение представленного выше дифференциального уравнения и имеет общий вид: Прогнозное значение, полученное с помощью модифицированного фильтра Калмана-Бьюси, будет оптимально с точки зрения принципа максимума апостериорной вероятности. Ниже изложена структура алгоритма для решения поставленной задачи. 2. Структура алгоритма прогнозирования на основе реализации модифицированного фильтра Калмана-Бьюси Модифицированное уравнение для оптимальной оценки записывается в виде где p * (t) – значение оценки; K(t) – коэффициент усиления фильтра, определяемый из следующего соотношения в этом соотношении R(t) = M[p * (t)-p(t)] [p * (t)-p(t)] – дисперсия ошибок оценки, для которой справедливо рекуррентное соотношение функции R η (t) = M[η(t) η(τ)] = Q(t)δ(t-τ) и R φ (t+1) – известны. Модификация связана с представлением уравнения состояния как 55 и уравнения наблюдения в виде где η(t) – гауссов белый шум; y(t) – наблюдаемое значение. Структура алгоритма прогнозирования: 1. Задать начальные приближения из условия р(τ) = р * (τ); р * (τ) = p 0 ; R(τ) = 0; 2. Вычислить коэффициент усиления K(t); 3. Вычислить по формуле значение R(t+l); 4. Получить прогноз цены р * (t+1) как численное решение дифференциального уравнения. Производя операции 2-4, при t = τ, τ +1, ... получим траекторию предсказанных на шаг вперед значений цены. Модель и алгоритм прогнозирования цены Для практической реализации непрерывное время заменено дискретным; уравнения модифицированной модели: уравнение состояния: x(k+l) = Ф(k+1,k)х(k) + Г(k+1,k)ω(k), уравнение измерения: z(k+l) = H(k+l)x(k+l)+v(k+1), где Ф – переходная матрица состояния размера n x n; Г – переходная матрица возмущения размера n x p; ω – p-вектор возмущения; H – матрица измерения размера m x n; v – m-вектор ошибки измерения. Процесс {ω(k), k = 0,1, 2, ...} является p-мерной гауссовской белой последовательностью с неотрицательно определенной корреляционной матрицей Q(k) размером p x p. Процесс {v(k) , k = 0,1, 2, ...} является m- 56 мерной гауссовской белой последовательностью с неотрицательно определенной корреляционной матрицей R(k+1) размером m x m. Оба эти процесса взаимно независимы Начальное состояние x(0) есть гауссовский случайный n-вектор с неотрицательно определенной корреляционной матрицей P(0) размера n x n. Тогда алгоритм фильтра Калмана будет в виде: 1) x(k+1|k) = Ф(k+1,k)x(k|k); 2) P(k+1|k) = Ф(k+1,k)P(k|k)Ф’(k+1,k) + Г(k+1,k)Q(k) Г’(k+1,k); 3) K(k+1) = P(k+1|k)H’(k+1)[H(k+1)P(k+1|k)H’(k+1) + R(k+1)] -1 ; 4) P(k+1|k+1) = [I – K(k+1)H(k+1)]P(k+1|k); 5) x(k+1|k+1) = x(k+1|k) + K(k+1)[z(k+1) – H(k+1)x(k+1|k)]. Можно еще более упростить модель, взяв вместо векторов x, ω и v одиночные переменные, тогда матрицы Ф, Г и H превратятся в скаляр. Ход работы Из статистической информации выбираем временной ряд, отражающий динамику цен. Таблица 1 Динамика цен Дата Цена 01.06.2016 3,7 02.06.2016 3,65 03.06.2016 3,7 04.06.2016 3,59 05.06.2016 3,7 06.06.2016 3,7 07.06.2016 3,58 08.06.2016 3,52 09.06.2016 3,52 10.06.2016 3,34 57 11.06.2016 3,52 12.06.2016 3,52 13.06.2016 3,45 14.06.2016 3,47 15.06.2016 3,52 16.06.2016 3,08 17.06.2016 3,09 18.06.2016 3,15 19.06.2016 2,95 20.06.2016 3,05 21.06.2016 3,11 22.06.2016 2,99 23.06.2016 3,1 24.06.2016 3,15 25.06.2016 3,09 26.06.2016 3,15 27.06.2016 3,15 28.06.2016 3,08 29.06.2016 3,37 30.06.2016 3,28 При анализе этого временного ряда формируем тренд изменения цены: 58 0 0,5 1 1,5 2 2,5 3 3,5 4 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 Рис. 1. Изменение цен (исходные данные и тренд) Уравнение тренда получили в виде: x(k+1) = 0,9929x(k). Затем формируем следующую модель: уравнение состояния: x(k+l) = 0,9929х(k) + ω(k), уравнение измерения: z(k+l) = x(k+l)+v(k+1), где дисперсия ω(k) = Q; дисперсия v(k+1) = R. Тогда уравнения фильтра примут вид: 1) x(k+1|k) = 0,9929x(k); 2) P(k+1|k) = P(k|k) + Q; 3) K(k+1) = P(k+1|k)[P(k+1|k) + R] -1 ; 4) P(k+1|k+1) = R*K(k+1); 5) x(k+1|k+1) = x(k+1|k) + K(k+1)[z(k+1) – x(k+1|k)]. при начальном условии P(0|0) = 0; x(0|0) = z(0|0). Исходный код программа, реализующей фильтр Калмана, на языке Си приведен в Приложении 1. Таблица 2 Результаты работы алгоритма фильтра Калмана (Q=0,1;R=0,15) Дата Цена Тренд P(k+1|k+1) x(k+1|k) x(k+1|k+1) 59 01.06.2016 3,7 3,700000 0,060000 3,673730 3,664238 02.06.2016 3,65 3,673730 0,077419 3,638222 3,670108 03.06.2016 3,7 3,647647 0,081281 3,644050 3,614762 04.06.2016 3,59 3,621748 0,082082 3,589097 3,649785 05.06.2016 3,7 3,596034 0,082246 3,623871 3,665613 06.06.2016 3,7 3,570502 0,082279 3,639587 3,606902 07.06.2016 3,58 3,545151 0,082286 3,581293 3,547669 08.06.2016 3,52 3,519981 0,082287 3,522481 3,521120 09.06.2016 3,52 3,494989 0,082287 3,496120 3,410475 10.06.2016 3,34 3,470175 0,082288 3,386261 3,459628 11.06.2016 3,52 3,445536 0,082288 3,435065 3,481659 12.06.2016 3,52 3,421073 0,082288 3,456939 3,453132 13.06.2016 3,45 3,396783 0,082288 3,428615 3,451318 14.06.2016 3,47 3,372666 0,082288 3,426814 3,477934 15.06.2016 3,52 3,348720 0,082288 3,453241 3,248487 16.06.2016 3,08 3,324944 0,082288 3,225423 3,151132 17.06.2016 3,09 3,301337 0,082288 3,128759 3,140412 18.06.2016 3,15 3,277898 0,082288 3,118115 3,025890 19.06.2016 2,95 3,254625 0,082288 3,004406 3,029418 20.06.2016 3,05 3,231517 0,082288 3,007909 3,063915 21.06.2016 3,11 3,208573 0,082288 3,042161 3,013546 22.06.2016 2,99 3,185792 0,082288 2,992150 3,051315 23.06.2016 3,1 3,163173 0,082288 3,029650 3,095672 24.06.2016 3,15 3,140715 0,082288 3,073693 3,082639 25.06.2016 3,09 3,118416 0,082288 3,060752 3,109712 26.06.2016 3,15 3,096275 0,082288 3,087633 3,121847 27.06.2016 3,15 3,074291 0,082288 3,099682 3,088885 28.06.2016 3,08 3,052464 0,082288 3,066954 3,233200 29.06.2016 3,37 3,030791 0,082288 3,210244 3,248511 60 0 0,5 1 1,5 2 2,5 3 3,5 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Цена x(k+1|k+1) x(k+1|k) Рис. 2. Результат работы фильтра (Q=0,1; R=0,15) 0 0,5 1 1,5 2 2,5 3 3,5 4 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 Цена x(k+1|k+1) x(k+1|k) Рис. 3. Результат работы фильтра (Q=0,01; R=0,5) 61 0 0,5 1 1,5 2 2,5 3 3,5 4 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 Цена x(k+1|k+1) x(k+1|k) Рис. 4. Результат работы фильтра (Q=0,5; R=0,01) Как видно из результатов работы алгоритма фильтра Калмана, если дисперсия ω(k) больше дисперсии v(k+1), то фильтр приближает значение оценки к измерениям. Если же дисперсия ω(k) меньше дисперсии v(k+1), то наоборот, скорректированная оценка будет ближе к модели. Также видно, что при начальном значении P(0|0) = 0, фильтр уже после обработки седьмого измерения, находится в установившемся состоянии. Кроме того, алгоритм был протестирован и при других значениях P(0|0), все равно после седьмого измерения фильтр приходил в устойчивое состояние. С помощью фильтра Калмана, зная дисперсии случайных процессов ω(k) и v(k+1), можно получать достаточно точные оценки значений цены отдельного продукта. Приложение1 1. #include 2. #include 62 3. #include 4. int main(int argc, char *argv[]){ 5. FILE *input,*out; 6. char buf[257]; 7. int k; 8. float res,z,K,P,P1,Q,R,F,x;//косметика 9. if(argc!=2){ 10. printf("Синтаксис: %s 11. printf(" где 12. printf("В результате работы программы создается файл \"result.txt\"\n"); 13. return(1); 14. } //есть ли параметр Задание Для различных объктов (продуктов или издений по желанию студента) составить статистический ряд и используя фильтр Калмана выполнить прогноз цены. Выполнить исследования полученных результатов при различных значениях Q и R. Сделать выводы. Содержание отчета 1. Цель лабораторной работы 2. Краткое описание хода работы 3. Файл статистического ряда исследуемого объекта 4. Результатов работы фильтра после прогноза в виде 5. Выводы по результатам работы 6. Ответы на вопросы Вопросы: 1. В чем заключается суть работы фильтра Калмана? 2. Пояснить, что происходит с фильтром, если дисперсия ω(k) больше дисперсии v(k+1) и почему? 63 3. В чем смысл уравнение состояния? 4. Что представляет уравнение измерения? 5. Поясните возможность применения фильтра Калмана для нестанционарных процессов. Лабораторная работа № 9. Парциальная обработка данных Цель работы. Изучить возможности АП процедур обработки данных.ых выполнить обработку данных выбранной предметной области. Теоретическая часть. В процессе парциальной обработки восстанавливаются пропущенные данные, редактируются аномальные значения, проводится спектральная обработка. В Deductor Studio при этом используются алгоритмы, в которых каждое поле анализируемого набора обрабатывается независимо от остальных полей, то есть данные обрабатываются по частям. По этой причине такая предобработка получила название парциальной. В числе процедур предобработки данных, реализованных в Deductor Studio, входят сглаживание, удаление шумов, редактирование аномальных значений, заполнение пропусков в рядах данных. 1) таблица с аномальными данными: 2) открываем мастер обработки и выбираем парциальную обработку: 64 3) выбор операции восстановления пропущенных данных: 4) выбор степени подавления: 65 5) сглаживание данных возможно выполнить с помощью вейвлет- преобразования и вычитания шума: 6) полученная таблица: 66 Полученная таблица отличается от первоначальной. Задание: Извлечь данные выбранной предметной области из хранилища данных и выполнить парциальную обработку. Содержание отчета 1. Цель лабораторной работы 2. Краткое описание хода работы 3.Файл первоначальных данных 4. Файл данных после парциальной обработки 5. Выводы по результатам работы 6. Ответы на вопросы Вопросы: 1. Что такое парциальная обработка данных? 2. Зачем нужен спектральный анализ при обработке данных? 3. Приведите основные методики восстановления данных 4. Основное назначение вейвлет-преобразования при обработке данных 5. Укажите каким образом выбирается степень подавления шума 10. Список рекомендуемой литературы 1. Методы и модели анализа данных: OLAP и Data Mining. / А.А. Барсегян, М.С. Куприянов, В.В.Степаненко, И.И. Холод – СПб.: БХВ-Петербург, 2004.- 336 с.: ил. 2. Аналитика: методология, технология и организация информационно - аналитической работы /П.Ю. Конотопов, Ю.В. Курносов - М.: РУСАКИ, 2004. - 512 с. 3. Официальный сайт компании «BaseGroup Labs» [Электрон. ресурс]. Рязань, 1995-2010.- Режим доступа: http://www.basegroup.ru/ 4. Data Mining и аналитическая платформа Deductor [Электрон. ресурс] : [статья]. М., 2008.- Режим доступа: http://sttc. ru/index.php?option=com_content&task=view&id=56&Itemid=90 67 5. Г.И. Пpocвeтoв (МГУ им. М.В. Ломоносова). Дерево решений [Электрон. ресурс] : [статья] / Г.И. Просветов.- СПб, 2008.- Режим доступа: http://www.elitarium.ru/2008/04/09/derevo_reshenijj.html 6. Деревянко В.А. Поиск ассоциативных правил при интеллектуальном анализе данных [Электрон. ресурс] : [статья] / В.А. Деревянко.- 2009.- Режим доступа: http://www.rammus.ru/products/arda/article_lam_translation |