Курсовая работа: Стохастическое моделирование и прогноз загрязнения атмосферы с использованием нелинейной регрессии
Для решения задачи регрессионного анализа методом наименьших квадратов вводится понятие функции невязки:
, (16)
Условие минимума функции невязки – равенство нулю всех частых производных, то есть:
, (17)
Полученная система является системой I+1 линейных уравнений с I+1 неизвестными b0 ...bI . Так как матрица системы уравнений является симметричной, то система решается методом LU-разложения.
5. Сортировка. Сортировка массивов осуществляется методом разделения (Quicksort). Шаги алгоритма таковы:
1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить.
2. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него. Обычный алгоритм операции:
- два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно;
- вычисляется опорный элемент m;
- индекс l последовательно увеличивается до m или до тех пор, пока l -й элемент не превысит опорный;
- индекс r последовательно уменьшается до m или до тех пор, пока r-й элемент не окажется меньше опорного;
- если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент;
- если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r или l соответственно.
3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.
4. Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.
Алгоритм называется быстрой сортировкой, поскольку для него оценкой числа сравнений и обменов является O(n*lg n).
2.4 Программа
Для автоматизации расчёта по описанной модели была составлена прикладная программа. Она была написана на языке C++ в среде разработки Microsoft Visual Studio 2005, и её объём составляет несколько тысяч операторов. Программа состоит из трёх основных модулей: управляющая часть, блок с функциями, реализующими логику всех необходимых методов, и модулем, который отвечает за взаимодействие программы с пользователем. Таким образом, программа составлена в соответствии с шаблоном проектирования модель-вид-контроллер (model-view-controller).
Управляющая часть – контроллер – позволяет разграничить модель и представление модели. Она включает в себя последовательность команд, которые вызывают требуемые функции.
Основные функции реализованы во втором модуле программы. В нём реализованы все этапы, необходимые для построения прогностической схемы, начиная от разбиения всех данных на зависимую и независимую выборки, и заканчивая прогнозированием концентрации загрязняющего вещества для введённых параметров.
Основные функции, реализованные во втором модуле программы:
- Считывание данных из файла. Для удобства пользователя исходные данные читаются из файла в формате xls.
- Деление выборки на зависимую и независимую части. В «обучающую» выборку попадают первые две недели из каждых трёх, а в независимую – каждая третья неделя. Отсчёт начинается от первого понедельника года.
- Определение граничного значения и отбрасывание из выборки неподходящих данных. В качестве аргумента данной функции передаётся процентиль, по которому определяется граничное значение. Если значение концентрации меньше граничного, то соответствующая строка отбрасывается из выборки.
- Линеаризация. Функция преобразует предикторы так, чтобы исключить нелинейность связей. Для этого все значения предиктора делятся на несколько интервалов и для каждого интервала находится среднее значение концентрации. Таким образом, строится кусочно-линейная функция, которая проходит через точки с координатами: седина интервала, соответствующее среднее значение. Координаты этих точек запоминаются в специальной структуре для дальнейшего использования.
- Нормализация. Данная функция для каждой преобразуемой величины вычисляет значение выборочной функции распределения вероятности. Затем она сопоставляет этому значению значение функции, обратной к функции распределения нормальной случайной величины. Таким образом, происходит преобразование всех случайных величин к нормальным.
- Определение предикторов, которые будут включены в модель. Необходимо выявить наиболее значимые предикторы. Для этого используется метод пошагового регрессионного анализа. При пошаговом алгоритме для критерия Фишера назначаются значения включения и исключения переменных. За счёт этого можно регулировать количество включаемых в модель предикторов.
- Функция составления системы для метода наименьших квадратов и её решения - определение коэффициентов регрессии.
- Проверка полученной схемы на «обучающей» и «независимой» выборках. Функция с помощью сохранённых параметров для преобразования линеаризует, нормализует необходимые величины и вычисляет прогностическое значение концентрации загрязняющего вещества.