Реализация метода интервальной регрессии в пакете knime выпускная работа бакалавра

Скачать 263.67 Kb.

Название	Реализация метода интервальной регрессии в пакете knime выпускная работа бакалавра
страница	6/6
Дата публикации	29.03.2015
Размер	263.67 Kb.
Тип	Выпускная работа

100-bal.ru > Информатика > Выпускная работа

1 2 3 4 5 6

2.3. Задача линейного программирования

Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств. Линейное программирование является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования.[7]

Термин «программирование» нужно понимать в смысле «планирования». Он был предложен в середине 1940-х годов Джорджем Данцигом, одним из основателей линейного программирования, ещё до того, как компьютеры были использованы для решения линейных задач оптимизации.

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

Математическая постановка задачи линейного программирования:

(2.1)

(2.2)

(2.1) называется целевой функцией, (2.2) набором ограничений. Задача состоит в поиске экстремумов целевой функции при заданных ограничениях.

(2.3)

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

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

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

Симплекс метод подробно рассмотрен в литературе [] и является классическим методом для решения задач линейного программирования. Также он не сложен в программной реализации. Существует довольно много уже готовых библиотек в функционал которых входит и необходимый метод решения ЗЛП (LpSolve, SimplexWin, ApacheCommonsMath), нет смысла в самостоятельной реализации.

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

Библиотека для математических вычислений ApacheCommonsMath [8] удовлетворяет обоим требованиям, хотя её функционал выходит далеко за необходимые пределы. Это бесплатная библиотека с открытым исходным кодом в настоящий момент активно развивающаяся. Многие классы и методы до сих пор находятся в разработке. К счастью модуль линейного программирования был недавно дополнен (с версии 2.0) симплнес-методом.

Компания Google выпустила под лицензией Apache SimplexSolver - систему для решения задач линейного программирования симплекс-методом. Код системы уже принят в состав открытой математической библиотеки Apache Commons Math 2.0 [9].

С помощью добавленного класса довольно просто решать ЗЛП. Частным случаем которых являются задачи (1.4), (1.7), (1.12) описанные в главе 1.

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

(2.4)

Ниже приведён код решающий эту задачу с использованием класса SimplexSolver из библиотеке Apache Commons Math.

Листинг 2:

// describe the optimization problem
LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { -2, 1 }, -5);
Collection constraints = new ArrayList();
constraints.add(new LinearConstraint(new double[] { 1, 2 }, Relationship.LEQ, 6));
constraints.add(new LinearConstraint(new double[] { 3, 2 }, Relationship.LEQ, 12));
constraints.add(new LinearConstraint(new double[] { 0, 1 }, Relationship.GEQ, 0));

// create and run the solver
RealPointValuePair solution = new SimplexSolver().optimize(f, constraints, GoalType.MINIMIZE, false);

// get the solution
double x = solution.getPoint()[0];
double y = solution.getPoint()[1];
double min = solution.getValue();

Этот пример приводится в [9], в качестве демонстрации простоты работы с методом.

Библиотека commons math версии 2.0 не всегда корректно работает для задач линейного программирования. В самом деле, когда симплекс таблица является недопустимой – необходимо действовать обратным симплекс-методом, неправильно происходит выделение памяти. В этом случае метод не срабатывает – происходит ошибка “null pointer exception”.

Эту ошибку планируется исправить в версии 2.1. Решение это проблемы описано в [10]. После соответствующих изменений ошибка не возникает, метод можно применять для решения ЗЛП.

2.4. Структура программы

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

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

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

3. Программная реализация метода интервальной регрессии

Большая часть классов необходима в соответствии с документацией по написанию пакетов KNIME, но иногда удобнее использовать свои вспомогательные классы. В описании каждого узла присутствует класс IRSolver, который упрощает работу с библиотекой Apache commons math.

3.1. Модуль для решения задачи линейного программирования

Задача линейного программирования есть встречается в каждом из предполагаемых узлов метода. Действительно для узла IRLearner это (1.2), для узла IROutlier это (1.12). Поэтому в каждом из узлов применяется модуль решения задачи линейного программирования.

Класс IRSolver сделан для простого доступа к модулю решения задач линейного программирования. Такая модульность позволит не задумываться над интерфейсом решателя, а применят описанные в IRSolver методы.

Класс IRSolver реализует следующий набор базовых методов необходимых для решения задачи линейного программирования:

public void setConstraints(double[][], double[], double[])

устанавливает набор ограничений для задачи, учитывая специфику метода каждая строка двумерного массивы задаёт два ограничения как (1.10).

public void setObjective(double[])

устанавливает коэффициенты целевой функции (2.1).

public void solve()

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

public double getMin([int])

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

public double getMax([int])

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

public int getExitCode()

Возвращает код выхода: 0 – удачный выход, -1 – не было инициализации, 4 – оптимизация невозможна.

public void solveForAll()

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

public double[] getMins() , public double[] getMaxs()

Возвращают массивы вершин множества (1.3).

public double[] getResiduals()

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

(3.1)

Где

– остаток,

– отклик,

– минимальное значение модели,

– ошибка измерения.

public double[] getLeverage()

Возвращает массив размахов. Размах – половина разности между максимальным и минимальным значением отклика модели деленная на ошибку измерения. Или в символьных обозначениях:

(3.2)

Где

– размах,

– минимальное значение модели,

– ошибка измерения.

public int[] getBoundary()

Возвращает массив нолей и единиц, если образец является граничным то на его месте в массиве стоит 1 иначе 0.

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

Важно также понимать, что вычисление размаха и размера не является неотъемлемой частью метода. Это есть характеристика построенной модели в данной реализации, но в других источниках можно найти иное задание модели[9].

Дальше в этой главе будут описаны принципы устройства каждого узла. Идея и математическое описание приведено в главе 1, здесь же будет описана реализация непосредственно на языке java.

Структура пакетов KNIME (структура пакетов описана в главе 2) предполагает, что основную функциональность несёт метод execute класса NodeModel. Дальше для каждой вершины будет описан метод execute.

3.2. Вершина IRLearner

…

Вершина IRPredictor

Список литературы

1. Канторович Л.В. О некоторых новых подходах к вычислительным методам и обработке наблюдений. Сиб. мат. журн., 3 , 701 (1962)

2. Вощинин А.П., Бочков А.Ф., Сотиров Г.Р. Методы анализа данных при интервальной нестатистической ошибке. Завод. лаб., 56, 76 (1990)

Жилин С.И. “Нестатистические модели и методы построения и анализа зависимостей”, 119 (2004)
www.knime.org
Акулич И.Л. Глава 1. Задачи линейного программирования// Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986
http://commons.apache.org/math/
http://google-opensource.blogspot.com/2009/06/introducing-apache-commons-math.html
https://issues.apache.org/jira/browse/MATH-290
Родионова О.Е. “Интервальный подход к анализу больших массивов физико-химических данных”, 273 (2007)
Максимов А.В., Оскорбин Н.М. Многопользовательские информационные системы: основы теории и методы исследования: монография. — Барнаул: Изд-во Алтайского университета, 2005. — 250с.
Clancey V.J. Statistical methods in chemical analyses. Nature, 159, 339 (1947)
Rajkó R. Treatment of model error in calibration by robust and fuzzy procedures. Anal. Letters, 27, 215 (1994)
Акулич И.Л. Задачи линейного программирования// Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — 319 с.