Из какого числа вариантов выбираются бинарные решения
Перейти к содержимому

Из какого числа вариантов выбираются бинарные решения

  • автор:

2. Стандартные, бинарные, многоальтернативные, инновационные решения.

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

Рассмотрение данного типа решений определяется двумя обстоятельствами:

• эти решения представляют собой наиболее распространенный тип решений;

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

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

• постановка цели решения;

• установление критериев решения;

• разделение критериев (желательные характеристики);

• оценка риска (опасность/серьезность);

Бинарное решение. В бинарном решении представлены две диаметрально противоположные альтернативы. Обычно это конкурирующие альтернативы, которые вынуждают к выбору типа «да -нет», «или-или» (например, открыть еще один филиал фирмы или нет). Эти решения отличаются высокой степенью связанной с ними неопределенности. Бинарные решения отражают неестественное положение вещей.

Причины возникновения бинарных решений следующие:

• переадресование принятия решений вышестоящим инстанциям;

• поверхностный анализ проблемы;

• нехватка времени на выработку оптимальных решений;

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

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

Многоальтернативное решение. Многовариантная разновидность решений встречается не так часто.

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

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

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

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

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

оптимальному, поэтому может рассматриваться как временный или основа для продолжения работы в данном направлении.

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

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

1.10. Деревья решений ¶

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

Например, в приведенном ниже примере деревья решений обучаются на основе данных, чтобы аппроксимировать синусоидальную кривую с набором правил принятия решений «если-то-еще». Чем глубже дерево, тем сложнее правила принятия решений и тем лучше модель.

Некоторые преимущества деревьев решений:

  • Просто понять и интерпретировать. Деревья можно визуализировать.
  • Требуется небольшая подготовка данных. Другие методы часто требуют нормализации данных, создания фиктивных переменных и удаления пустых значений. Однако обратите внимание, что этот модуль не поддерживает отсутствующие значения.
  • Стоимость использования дерева (т. Е. Прогнозирования данных) является логарифмической по количеству точек данных, используемых для обучения дерева.
  • Может обрабатывать как числовые, так и категориальные данные. Однако реализация scikit-learn пока не поддерживает категориальные переменные. Другие методы обычно специализируются на анализе наборов данных, содержащих только один тип переменных. См. Алгоритмы для получения дополнительной информации.
  • Способен обрабатывать проблемы с несколькими выходами.
  • Использует модель белого ящика. Если данная ситуация наблюдаема в модели, объяснение условия легко объяснить с помощью булевой логики. Напротив, в модели черного ящика (например, в искусственной нейронной сети) результаты могут быть труднее интерпретировать.
  • Возможна проверка модели с помощью статистических тестов. Это позволяет учитывать надежность модели.
  • Работает хорошо, даже если его предположения несколько нарушаются истинной моделью, на основе которой были сгенерированы данные.

К недостаткам деревьев решений можно отнести:

  • Обучающиеся дереву решений могут создавать слишком сложные деревья, которые плохо обобщают данные. Это называется переобучением. Чтобы избежать этой проблемы, необходимы такие механизмы, как обрезка, установка минимального количества выборок, необходимых для конечного узла, или установка максимальной глубины дерева.
  • Деревья решений могут быть нестабильными, поскольку небольшие изменения в данных могут привести к созданию совершенно другого дерева. Эта проблема смягчается за счет использования деревьев решений в ансамбле.
  • Как видно из рисунка выше, предсказания деревьев решений не являются ни гладкими, ни непрерывными, а являются кусочно-постоянными приближениями. Следовательно, они не годятся для экстраполяции.
  • Известно, что проблема обучения оптимальному дереву решений является NP-полной с точки зрения нескольких аспектов оптимальности и даже для простых концепций. Следовательно, практические алгоритмы обучения дереву решений основаны на эвристических алгоритмах, таких как жадный алгоритм, в котором локально оптимальные решения принимаются в каждом узле. Такие алгоритмы не могут гарантировать возврат глобального оптимального дерева решений. Это можно смягчить путем обучения нескольких деревьев в учащемся ансамбля, где функции и образцы выбираются случайным образом с заменой.
  • Существуют концепции, которые трудно изучить, поскольку деревья решений не выражают их легко, например проблемы XOR, четности или мультиплексора.
  • Ученики дерева решений создают предвзятые деревья, если некоторые классы доминируют. Поэтому рекомендуется сбалансировать набор данных перед подгонкой к дереву решений.

1.10.1. Классификация

DecisionTreeClassifier — это класс, способный выполнять мультиклассовую классификацию набора данных.

Как и в случае с другими классификаторами, DecisionTreeClassifier принимает в качестве входных данных два массива: массив X, разреженный или плотный, формы (n_samples, n_features), содержащий обучающие образцы, и массив Y целочисленных значений, формы (n_samples,), содержащий метки классов для обучающих образцов:

>>> from sklearn import tree >>> X = [[0, 0], [1, 1]] >>> Y = [0, 1] >>> clf = tree.DecisionTreeClassifier() >>> clf = clf.fit(X, Y)

После подбора модель можно использовать для прогнозирования класса образцов:

>>> clf.predict([[2., 2.]]) array([1])

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

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

>>> clf.predict_proba([[2., 2.]]) array([[0., 1.]])

DecisionTreeClassifier поддерживает как двоичную (где метки — [-1, 1]), так и мультиклассовую (где метки — [0,…, K-1]) классификацию.

Используя набор данных Iris, мы можем построить дерево следующим образом:

>>> from sklearn.datasets import load_iris >>> from sklearn import tree >>> iris = load_iris() >>> X, y = iris.data, iris.target >>> clf = tree.DecisionTreeClassifier() >>> clf = clf.fit(X, y)

После обучения вы можете построить дерево с помощью plot_tree функции:

>>> tree.plot_tree(clf)

Мы также можем экспортировать дерево в формат Graphviz с помощью export_graphviz экспортера. Если вы используете Conda менеджер пакетов, то Graphviz бинарные файлы и пакет питон может быть установлен conda install python-graphviz .

В качестве альтернативы двоичные файлы для graphviz можно загрузить с домашней страницы проекта graphviz, а оболочку Python установить из pypi с помощью pip install graphviz .

Ниже приведен пример экспорта graphviz вышеуказанного дерева, обученного на всем наборе данных радужной оболочки глаза; результаты сохраняются в выходном файле iris.pdf :

>>> import graphviz >>> dot_data = tree.export_graphviz(clf, out_file=None) >>> graph = graphviz.Source(dot_data) >>> graph.render("iris")

Экспортер export_graphviz также поддерживает множество эстетических вариантов, в том числе окраски узлов их класс (или значение регрессии) и используя явные имена переменных и классов , если это необходимо. Блокноты Jupyter также автоматически отображают эти графики встроенными:

>>> dot_data = tree.export_graphviz(clf, out_file=None, . feature_names=iris.feature_names, . class_names=iris.target_names, . filled=True, rounded=True, . special_characters=True) >>> graph = graphviz.Source(dot_data) >>> graph

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

>>> from sklearn.datasets import load_iris >>> from sklearn.tree import DecisionTreeClassifier >>> from sklearn.tree import export_text >>> iris = load_iris() >>> decision_tree = DecisionTreeClassifier(random_state=0, max_depth=2) >>> decision_tree = decision_tree.fit(iris.data, iris.target) >>> r = export_text(decision_tree, feature_names=iris['feature_names']) >>> print(r) |--- petal width (cm) 0.80 | |--- petal width (cm) 1.75 | | |--- class: 2
  • Постройте поверхность принятия решений дерева решений на наборе данных радужной оболочки глаза
  • Понимание структуры дерева решений

1.10.2. Регрессия

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

Как и в настройке классификации, метод fit будет принимать в качестве аргументов массивы X и y, только в этом случае ожидается, что y будет иметь значения с плавающей запятой вместо целочисленных значений:

>>> from sklearn import tree >>> X = [[0, 0], [2, 2]] >>> y = [0.5, 2.5] >>> clf = tree.DecisionTreeRegressor() >>> clf = clf.fit(X, y) >>> clf.predict([[1, 1]]) array([0.5])

1.10.3. Проблемы с несколькими выходами

Задача с несколькими выходами — это проблема контролируемого обучения с несколькими выходами для прогнозирования, то есть когда Y — это 2-й массив формы (n_samples, n_outputs) .

Когда нет корреляции между выходами, очень простой способ решить эту проблему — построить n независимых моделей, то есть по одной для каждого выхода, а затем использовать эти модели для независимого прогнозирования каждого из n выходов. Однако, поскольку вполне вероятно, что выходные значения, относящиеся к одному и тому же входу, сами коррелированы, часто лучшим способом является построение единой модели, способной прогнозировать одновременно все n выходов. Во-первых, это требует меньшего времени на обучение, поскольку строится только один оценщик. Во-вторых, часто можно повысить точность обобщения итоговой оценки.

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

  • Сохранять n выходных значений в листьях вместо 1;
  • Используйте критерии разделения, которые вычисляют среднее сокращение для всех n выходов.

Этот модуль предлагает поддержку для задач с несколькими выходами, реализуя эту стратегию как в, так DecisionTreeClassifier и в DecisionTreeRegressor . Если дерево решений соответствует выходному массиву Y формы (n_samples, n_outputs), то итоговая оценка будет:

  • Вывести значения n_output при predict ;
  • Выведите список массивов n_output вероятностей классов на predict_proba .

Использование деревьев с несколькими выходами для регрессии продемонстрировано в разделе «Регрессия дерева решений с несколькими выходами» . В этом примере вход X — это одно действительное значение, а выходы Y — синус и косинус X.

Использование деревьев с несколькими выходами для классификации демонстрируется в разделе «Завершение лица с оценками с несколькими выходами» . В этом примере входы X — это пиксели верхней половины граней, а выходы Y — пиксели нижней половины этих граней.

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

1.10.4. Сложность

В общем, время выполнения для построения сбалансированного двоичного дерева составляет $O(n_n_\log(n_))$ и время запроса $O(\log(n_))$. Хотя алгоритм построения дерева пытается генерировать сбалансированные деревья, они не всегда будут сбалансированными. Предполагая, что поддеревья остаются примерно сбалансированными, стоимость на каждом узле состоит из перебора $O(n_)$ найти функцию, обеспечивающую наибольшее снижение энтропии. Это стоит $O(n_n_\log(n_))$ на каждом узле, что приводит к общей стоимости по всем деревьям (суммируя стоимость на каждом узле) $O(n_n_^\log(n_))$

1.10.5. Советы по практическому использованию

  • Деревья решений имеют тенденцию чрезмерно соответствовать данным с большим количеством функций. Получение правильного соотношения образцов к количеству функций важно, поскольку дерево с небольшим количеством образцов в многомерном пространстве, скорее всего, переоборудуется.
  • Предварительно рассмотрите возможность уменьшения размерности (PCA, ICA, или Feature selection), чтобы дать вашему дереву больше шансов найти отличительные признаки.
  • Понимание структуры дерева решений поможет лучше понять, как дерево решений делает прогнозы, что важно для понимания важных функций данных.
  • Визуализируйте свое дерево во время тренировки с помощью export функции. Используйте max_depth=3 в качестве начальной глубины дерева, чтобы понять, насколько дерево соответствует вашим данным, а затем увеличьте глубину.
  • Помните, что количество образцов, необходимых для заполнения дерева, удваивается для каждого дополнительного уровня, до которого дерево растет. Используйте max_depth для управления размером дерева во избежание переобучения.
  • Используйте min_samples_split или, min_samples_leaf чтобы гарантировать, что несколько выборок информируют каждое решение в дереве, контролируя, какие разделения будут учитываться. Очень маленькое число обычно означает, что дерево переоборудуется, тогда как большое число не позволяет дереву изучать данные. Попробуйте min_samples_leaf=5 в качестве начального значения. Если размер выборки сильно различается, в этих двух параметрах можно использовать число с плавающей запятой в процентах. В то время как min_samples_split может создавать произвольно маленькие листья, min_samples_leaf гарантирует, что каждый лист имеет минимальный размер, избегая малодисперсных, чрезмерно подходящих листовых узлов в задачах регрессии. Для классификации с несколькими классами min_samples_leaf=1 это часто лучший выбор.

1.10.6. Алгоритмы дерева: ID3, C4.5, C5.0 и CART

Что представляют собой различные алгоритмы дерева решений и чем они отличаются друг от друга? Какой из них реализован в scikit-learn?

ID3 (Iterative Dichotomiser 3) был разработан Россом Куинланом в 1986 году. Алгоритм создает многостороннее дерево, находя для каждого узла (т. Е. Жадным образом) категориальный признак, который даст наибольший информационный выигрыш для категориальных целей. Деревья вырастают до максимального размера, а затем обычно применяется этап обрезки, чтобы улучшить способность дерева обобщать невидимые данные.

C4.5 является преемником ID3 и снял ограничение, что функции должны быть категориальными, путем динамического определения дискретного атрибута (на основе числовых переменных), который разбивает непрерывное значение атрибута на дискретный набор интервалов. C4.5 преобразует обученные деревья (т. Е. Результат алгоритма ID3) в наборы правил «если-то». Затем оценивается точность каждого правила, чтобы определить порядок, в котором они должны применяться. Удаление выполняется путем удаления предусловия правила, если без него точность правила улучшается.

C5.0 — это последняя версия Quinlan под частной лицензией. Он использует меньше памяти и создает меньшие наборы правил, чем C4.5, но при этом является более точным.

CART (Classification and Regression Trees — деревья классификации и регрессии) очень похож на C4.5, но отличается тем, что поддерживает числовые целевые переменные (регрессию) и не вычисляет наборы правил. CART строит двоичные деревья, используя функцию и порог, которые дают наибольший прирост информации в каждом узле.

scikit-learn использует оптимизированную версию алгоритма CART; однако реализация scikit-learn пока не поддерживает категориальные переменные.

1.10.7. Математическая постановка

Данные обучающие векторы $x_i \in R^n$, i = 1,…, l и вектор-метка $y \in R^l$ дерево решений рекурсивно разбивает пространство признаков таким образом, что образцы с одинаковыми метками или аналогичными целевыми значениями группируются вместе.

Пусть данные в узле m быть представлен $Q_m$ с участием $N_m$ образцы. Для каждого раскола кандидатов $\theta = (j, t_m)$ состоящий из функции $j$ и порог $t_m$, разделите данные на $Q_m^(\theta)$ а также $Q_m^(\theta)$ подмножества
$$Q_m^(\theta) = <(x, y) | x_j <= t_m>$$
$$Q_m^(\theta) = Q_m \setminus Q_m^(\theta)$$

Качество кандидата разделения узла $m$ затем вычисляется с использованием функции примеси или функции потерь $H()$, выбор которых зависит от решаемой задачи (классификация или регрессия)
$$G(Q_m, \theta) = \frac> H(Q_m^(\theta)) + \frac> H(Q_m^(\theta))$$

Выберите параметры, которые минимизируют примеси
$$\theta^* = \operatorname_\theta G(Q_m, \theta)$$

Рекурсия для подмножеств $Q_m^(\theta^*)$ а также $Q_m^(\theta^*)$ пока не будет достигнута максимально допустимая глубина, $N_m < \min_$ или же $N_m = 1$.

1.10.7.1. Критерии классификации

Если целью является результат классификации, принимающий значения 0,1,…, K-1, для узла m, позволять
$$p_ = 1/ N_m \sum_ I(y = k)$$

быть пропорцией наблюдений класса k в узле m. Еслиmявляется конечным узлом, predict_proba для этого региона установлено значение $p_$. Общие меры примеси следующие.

Энтропия:
$$H(Q_m) = — \sum_k p_ \log(p_)$$

Неверная классификация:
$$H(Q_m) = 1 — \max(p_)$$

1.10.7.2. Критерии регрессии

Если целью является непрерывное значение, то для узла m, общими критериями, которые необходимо минимизировать для определения местоположений будущих разделений, являются среднеквадратичная ошибка (ошибка MSE или L2), отклонение Пуассона, а также средняя абсолютная ошибка (ошибка MAE или L1). MSE и отклонение Пуассона устанавливают прогнозируемое значение терминальных узлов равным изученному среднему значению $\bar_m$ узла, тогда как MAE устанавливает прогнозируемое значение терминальных узлов равным медиане $median(y)_m$.

Половинное отклонение Пуассона:
$$H(Q_m) = \frac \sum_ (y \log\frac<\bar_m> — y + \bar_m)$$

Настройка criterion=»poisson» может быть хорошим выбором, если ваша цель — счетчик или частота (количество на какую-то единицу). В любом случае, y>=0 является необходимым условием для использования этого критерия. Обратите внимание, что он подходит намного медленнее, чем критерий MSE.

Обратите внимание, что он подходит намного медленнее, чем критерий MSE.

1.10.8. Обрезка с минимальными затратами и сложностью

Сокращение с минимальными затратами и сложностью — это алгоритм, используемый для сокращения дерева во избежание чрезмерной подгонки, описанный в главе 3 [BRE] . Этот алгоритм параметризован $\alpha\ge0$ известный как параметр сложности. Параметр сложности используется для определения меры затрат и сложности, $R_\alpha(T)$ данного дерева $T$:
$$R_\alpha(T) = R(T) + \alpha|\widetilde|$$

где $|\widetilde|$ количество конечных узлов в $T$ а также $R(T)$ традиционно определяется как общий коэффициент ошибочной классификации конечных узлов. В качестве альтернативы scikit-learn использует взвешенную общую примесь конечных узлов для $R(T)$. Как показано выше, примесь узла зависит от критерия. Обрезка с минимальными затратами и сложностью находит поддеревоT что сводит к минимуму $R_\alpha(T)$.

Оценка сложности стоимости одного узла составляет $R_\alpha(t)=R(t)+\alpha$. Ответвление $T_t$, определяется как дерево, в котором узел $t$ это его корень. В общем, примесь узла больше, чем сумма примесей его конечных узлов, $R(T_t)(t)=\frac<|T|-1>$. Нетерминальный узел с наименьшим значением $\alpha_$ является самым слабым звеном и будет удалено. Этот процесс останавливается, когда обрезанное дерево минимально $\alpha_$ больше ccp_alpha параметра.

  • BRE Л. Брейман, Дж. Фридман, Р. Олшен и К. Стоун. Деревья классификации и регрессии. Уодсворт, Белмонт, Калифорния, 1984.
  • https://en.wikipedia.org/wiki/Decision_tree_learning
  • https://en.wikipedia.org/wiki/Predictive_analytics
  • JR Quinlan. C4. 5: программы для машинного обучения. Морган Кауфманн, 1993.
  • Т. Хасти, Р. Тибширани и Дж. Фридман. Элементы статистического обучения, Springer, 2009.

Если вы хотите помочь проекту с переводом, то можно обращаться по следующему адресу support@scikit-learn.ru
© 2007 — 2020, scikit-learn developers (BSD License).

Деревья решений: общие принципы

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

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

Они представляют собой иерархические древовидные структуры, состоящие из решающих правил вида «Если . то . ». Правила автоматически генерируются в процессе обучения на обучающем множестве и, поскольку они формулируются практически на естественном языке (например, «Если объём продаж более 1000 шт., то товар перспективный»), деревья решений как аналитические модели более вербализуемы и интерпретируемы, чем, скажем, нейронные сети.

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

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

Основополагающие идеи, послужившие толчком к появлению и развитию деревьев решений, были заложены в 1950-х годах в области исследований моделирования человеческого поведения с помощью компьютерных систем. Среди них следует выделить работы К. Ховеленда «Компьютерное моделирование мышления»[1] и Е. Ханта и др. «Эксперименты по индукции»[2].

Дальнейшее развитие деревьев решений как самообучающихся моделей для анализа данных связано с именами Джона Р. Куинлена[3], который разработал алгоритм ID3 и его усовершенствованные модификации С4.5 и С5.0, а так же Лео Бреймана[4], который предложил алгоритм CART и метод случайного леса.

Терминология

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

Название Описание
Объект Пример, шаблон, наблюдение
Атрибут Признак, независимая переменная, свойство
Целевая переменная Зависимая переменная, метка класса
Узел Внутренний узел дерева, узел проверки
Корневой узел Начальный узел дерева решений
Лист Конечный узел дерева, узел решения, терминальный узел
Решающее правило Условие в узле, проверка

Структура дерева решений

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

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

Затем к каждому подмножеству вновь применяется правило и процедура рекурсивно повторяется пока не будет достигнуто некоторое условие остановки алгоритма. В результате в последнем узле проверка и разбиение не производится и он объявляется листом. Лист определяет решение для каждого попавшего в него примера. Для дерева классификации — это класс, ассоциируемый с узлом, а для дерева регрессии — соответствующий листу модальный интервал целевой переменной.

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

Очевидно, чтобы попасть в лист, пример должен удовлетворять всем правилам, лежащим на пути к этому листу. Поскольку путь в дереве к каждому листу единственный, то и каждый пример может попасть только в один лист, что обеспечивает единственность решения.

Задачи

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

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

Процесс построения

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

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

В основе большинства популярных алгоритмов обучения деревьев решений лежит принцип «разделяй и властвуй». Алгоритмически этот принцип реализуется следующим образом. Пусть задано обучающее множество S , содержащее n примеров, для каждого из которых задана метка класса C_i(i=1..k) , и m атрибутов A_j(j=1..m) , которые, как предполагается, определяют принадлежность объекта к тому или иному классу. Тогда возможны три случая:

  1. Все примеры множества S имеют одинаковую метку класса C_i (т.е. все обучающие примеры относятся только к одному классу). Очевидно, что обучение в этом случае не имеет смысла, поскольку все примеры, предъявляемые модели, будут одного класса, который и «научится» распознавать модель. Само дерево решений в этом случае будет представлять собой лист, ассоциированный с классом C_i . Практическое использование такого дерева бессмысленно, поскольку любой новый объект оно будет относить только к этому классу.
  2. Множество S вообще не содержит примеров, т.е. является пустым множеством. В этом случае для него тоже будет создан лист (применять правило, чтобы создать узел, к пустому множеству бессмысленно), класс которого будет выбран из другого множества (например, класс, который наиболее часто встречается в родительском множестве).
  3. Множество S содержит обучающие примеры всех классов C_k . В этом случае требуется разбить множество S на подмножества, ассоциированные с классами. Для этого выбирается один из атрибутов A_j множества S который содержит два и более уникальных значения (a_1,a_2. a_p) , где p — число уникальных значений признака. Затем множество S разбивается на p подмножеств (S_1,S_2. S_p) , каждое из которых включает примеры, содержащие соответствующее значение атрибута. Затем выбирается следующий атрибут и разбиение повторяется. Это процедура будет рекурсивно повторяться до тех пор, пока все примеры в результирующих подмножествах не окажутся одного класса.

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

В настоящее время разработано значительное число алгоритмов обучения деревья решений: ID3, CART, C4.5, C5.0, NewId, ITrule, CHAID, CN2 и т.д. Но наибольшее распространение и популярность получили следующие:

  • ID3 (Iterative Dichotomizer 3) — алгоритм позволяет работать только с дискретной целевой переменной, поэтому деревья решений, построенные с помощью данного алгоритма, являются классифицирующими. Число потомков в узле дерева не ограничено. Не может работать с пропущенными данными.
  • C4.5 — усовершенствованная версия алгоритма ID3, в которую добавлена возможность работы с пропущенными значениями атрибутов (по версии издания Springer Science в 2008 году алгоритм занял 1-е место в топ-10 наиболее популярных алгоритмов Data Mining).
  • CART (Classification and Regression Tree) — алгоритм обучения деревьев решений, позволяющий использовать как дискретную, так и непрерывную целевую переменную, то есть решать как задачи классификации, так и регрессии. Алгоритм строит деревья, которые в каждом узле имеют только два потомка.

Основные этапы построения

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

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

Рассмотрим эти этапы ниже.

Выбор атрибута разбиения

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

Теоретико-информационный критерий

Как следует из названия, критерий основан на понятиях теории информации, а именно — информационной энтропии.

где n — число классов в исходном подмножестве, N_i — число примеров i-го класса, N — общее число примеров в подмножестве.

Таким образом, энтропия может рассматриваться как мера неоднородности подмножества по представленным в нём классам. Когда классы представлены в равных долях и неопределённость классификации наибольшая, энтропия также максимальна. Если все примеры в узле относятся к одному классу, т.е. N=N_i , логарифм от единицы обращает энтропию в ноль.

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

где \text(S) — информация, связанная с подмножеством S до разбиения, \text(S_A) — информация, связанная с подмножеством, полученными при разбиении по атрибуту A .

Таким образом, задача выбора атрибута разбиения в узле заключается в максимизации величины \text(A) , называемой приростом информации (от англ. gain — прирост, увеличение). Поэтому сам теоретико-информационный подход известен как критерий прироста информации. Он впервые был применён в алгоритме ID3, а затем в C4.5 и других алгоритмах.

Статистический подход

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

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

Индекс Джини может быть рассчитан по формуле:

где Q — результирующее множество, n — число классов в нём, p_i — вероятность i-го класса (выраженная как относительная частота примеров соответствующего класса). Очевидно, что данный показатель меняется от 0 до 1. При этом он равен 0, если все примеры Q относятся к одному классу, и равен 1, когда классы представлены в равных пропорциях и равновероятны. Тогда лучшим будет то разбиение, для которого значение индекса Джини будут минимальным.

Критерий остановки алгоритма

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

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

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

  1. Ранняя остановка — алгоритм будет остановлен, как только будет достигнуто заданное значение некоторого критерия, например процентной доли правильно распознанных примеров. Единственным преимуществом подхода является снижение времени обучения. Главным недостатком является то, что ранняя остановка всегда делается в ущерб точности дерева, поэтому многие авторы рекомендуют отдавать предпочтение отсечению ветвей.
  2. Ограничение глубины дерева — задание максимального числа разбиений в ветвях, по достижении которого обучение останавливается. Данный метод также ведёт к снижению точности дерева.
  3. Задание минимально допустимого числа примеров в узле — запретить алгоритму создавать узлы с числом примеров меньше заданного (например, 5). Это позволит избежать создания тривиальных разбиений и, соответственно, малозначимых правил.

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

Отсечение ветвей

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

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

К сожалению, это задача относится к классу NP-полных задач, что было показано Л. Хайфилем (L. Hyafill) и Р. Ривестом (R. Rivest), и, как известно, этот класс задач не имеет эффективных методов решения.

Альтернативным подходом является так называемое отсечение ветвей (pruning). Он содержит следующие шаги:

  1. Построить полное дерево (чтобы все листья содержали примеры одного класса).
  2. Определить два показателя: относительную точность модели — отношение числа правильно распознанных примеров к общему числу примеров, и абсолютную ошибку — число неправильно классифицированных примеров.
  3. Удалить из дерева листья и узлы, отсечение которых не приведёт к значимому уменьшению точности модели или увеличению ошибки.

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

Извлечение правил

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

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

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

Преимущества алгоритма

Рассмотрев основные проблемы, возникающие при построении деревьев, было бы несправедливо не упомянуть об их достоинствах:

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

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

Области применения

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

Деревья решений успешно применяются на практике в следующих областях:

  • Банковское дело. Оценка кредитоспособности клиентов банка при выдаче кредитов.
  • Промышленность. Контроль за качеством продукции (выявление дефектов), испытания без разрушений (например, проверка качества сварки) и т.д.
  • Медицина. Диагностика заболеваний.
  • Молекулярная биология. Анализ строения аминокислот.
  • Торговля. Классификация клиентов и товаров.

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

  1. Hovland, C. I. (1960). Computer simulation of thinking. American Psychologist, 15(11), 687-693.
  2. Hunt, Earl B.; Janet Marin; Philip J. Stone (1966). Experiments in Induction. New York: Academic Press. ISBN 978-0-12-362350-8.
  3. Quinlan, J. R. (1986). Induction of decision trees. Machine Learning, 1(1):81-106.
  4. Quinlan, J. Ross. C4.5: Programs for Machine learning. Morgan Kaufmann Publishers 1993.
  5. Breiman, Leo, J. Friedman, R. Olshen, and C. Stone. Classification and Regression Trees. Wadsworth, Belmont, CA, 1984.
  6. Murthy, S. Automatic construction of decision trees from data: A Multi-disciplinary survey.1997.
  7. Buntine, W. A theory of classification rules. 1992.
  8. Machine Learning, Neural and Statistical Classification. Editors D. Mitchie et.al. 1994.
  9. Шеннон, К. Работы по теории информации и кибернетике. М. Иностранная литература, 1963.
  10. Айвазян С. А., Мхитарян В. С Прикладная статистика и основы эконометрики, М. Юнити, 1998.

Другие материалы по теме:

Из какого числа вариантов выбираются бинарные решения

ВАК 05.12.2013 Системы, сети и устройства телекоммуникаций
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 004.056.5
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления

Язык материала:
Ключевые слова:

квадратичное программирование, бинарные переменные, оптимальное решение, формула Кардано, эвристический алгоритм

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

Ключевые слова:
квадратичное программирование, бинарные переменные, оптимальное решение, формула Кардано, эвристический алгоритм

Введение При решении задач принятия решений часто возникают ситуации, когда результирующее решение выбирается из большого набора вариантов (альтернатив). Формализованное описание подобных задач часто осуществляется путем введения бинарных переменных по каждой альтернативе, которые могут принимать только два значения, например 0 и 1. Если целевые функции и ограничения в подобной задаче могут быть представлены аналитическими выражениями, то полученные формализованные модели называются задачами математического бинарного (или булевого) программирования. Наиболее важными задачами бинарного программирования являются задачи линейного и квадратичного бинарного программирования, когда целевые функции и ограничения описывают линейными и квадратичными функциями соответственно, поскольку во многих приложениях задач математического программирования использование более сложных функций не позволяет повысить качество результатов ввиду наличия больших погрешностей в исходных данных, сравнимых с погрешностями самой модели. Вышеупомянутые задачи являются частным случаем задач целочисленного математического программирования, и поэтому, казалось бы, могут быть решены методами, используемыми при решении задач целочисленного программирования. Однако одна важная особенность делает все известные методы решения задач целочисленного программирования практически неприемлемыми и бесполезными при решении указанных задач: число альтернатив часто бывает настолько большим, что существующие вычислительные средства оказываются неспособными за разумное время найти решение указанных задач. Так, например, в работах [1, 2] приведены формализованные постановки задачи составления учебного расписания, когда в качестве бинарных переменных берутся следующие: , если занятие по d-й дисциплине у g-й подгруппы проводится в a-й аудитории на p-й паре, и в противном случае. Это означает, что в данной задаче индекс суммирования i представлен набором pgad. Тогда, как показано в [1], в этом случае число всех возможных переменных для типового вуза с общим числом студентов порядка 7 500 достигает 150 миллионов переменных , что делает практически невозможным автоматизированное решение указанной задачи на основе алгоритмов целочисленного программирования. Бинарное программирование как самостоятельное научное направление исследований было выделено еще в 60-е гг. ХХ в.; наиболее важные методы решения задач бинарного программирования, применявшиеся в то время, можно найти в [3]. В дальнейшем сколь-нибудь значимых результатов по решению задач бинарного программирования с большим числом переменных, по-видимому, получить не удалось. Состояние исследований в данном направлении в настоящее время отражено в [4, 5]. Отметим также отсутствие значимых результатов по использованию современных эвристических методов оптимизации (генетических алгоритмов, нейронных сетей, методов муравьиных или пчелиных колоний и др.), которые доказали свою эффективность при решении многих других типов задач оптимизации. Ниже нами предлагаются набор условий для нахождения оптимального решения и построенный на их основе эвристический алгоритм решения. 1. Формализация задачи с использованием метода штрафных функций В анализируемой ниже задаче квадратичного программирования ограничения заданы в виде равенств, в то время как в классической постановке эти ограничения имеют форму неравенств. Однако способы сведения ограничений в виде неравенств к ограничениям в виде равенств и обратно известны, поэтому предлагаемая постановка охватывает все классические постановки задач квадратичного программирования. Приведем формализованную постановку задачи. Пусть задан набор переменных xi (), каждая из которых принимает только значения 0 или 1, т. е. является бинарной переменной; . Тогда задачей квадратичного бинарного программирования является следующая оптимизационная задача: (1) при условии , . (2) Для нас представляет интерес также несколько другая запись целевой функции (1): (3) т. е. квадратичное выражение в целевой функции (1) представляется как сумма из S отдельных квадратичных выражений. Именно в таком виде представлена целевая функция в задаче формирования расписания занятий в [1], где S = 19, каждое квадратичное выражение в сумме по S имеет относительно простой вид и соответствует разным ограничениям задачи, число которых составляет порядка 30. Отметим, что поскольку общее число возможных вариантов решений задачи (1), (2) ограничено (не превосходит 2N), то задача (1), (2) всегда имеет решение. Без ограничения общности можно считать C = 0. Как было указано выше, для решения задачи (1), (2) предлагается использовать метод штрафных функций — т. е. решение задачи (1), (2) заменяется решением следующей задачи безусловной оптимизации (т. е. задачи без ограничений): (4) где () — вспомогательные переменные; Lk > 0 трактуется как величина штрафа за нарушение k-го ограничения: если хотя бы одно из слагаемых в последней сумме не равно нулю (т. е. положительно), то значение целевой функции при больших значениях Lk резко уменьшается. Поэтому оптимальное решение вынуждено стремиться обеспечить выполнение ограничений (2), при которых все слагаемые последней суммы равны нулю. Известно, что при достаточно больших значениях Lk для всех k решения задач (4) и (1), (2) совпадают, поэтому вместо решения задачи (1), (2) можно решать задачу (4). В записи задачи (4) учтены все ограничения задачи (1), (2), кроме самого важного — переменные xi являются бинарными. Для учета данного ограничения предлагается добавить в целевую функцию задачи еще по одному слагаемому на каждую переменную: (5) где L >> max(Li). Действительно, если для некоторого индекса i выражение ) отличается значимо от нуля, в целевой функции появляется большое по модулю отрицательное слагаемое (последняя сумма в правой части), которое сильно уменьшает значение целевой функции по сравнению со случаем ) = 0. В результате исходная задача квадратичного программирования переходит в задачу полиномиального программирования четвертой степени. Однако, как будет следовать из приводимых ниже рассуждений, задача (5) по ряду важных свойств аналогична задаче квадратичного программирования. 2. Базовый случай одной переменной Покажем вначале, что при достаточно больших L решение задачи (5) получается из решения задачи (4) путем целочисленного округления и при этом обеспечивается выполнение требования бинарности переменных xi. Рассмотрим вначале случай функции одной переменной (т. е. N = 1). Тогда левую часть соотношения (5) после деления обеих частей на L можно записать в виде или, после обозначений , , , получаем Проведем замену переменных , т. е. . Тогда, полагая , , из последнего соотношения выводим следующее представление задачи (5): (6) В силу необходимого условия экстремума из (6) следует уравнение Таким образом, точки максимума функции f(z) являются корнями кубического уравнения (7) Уравнение (7) имеет в комплексной плоскости три корня zi(L) (i = 1, 2, 3), которые упорядочим лексикографически, т. е. в порядке возрастания их действительной части; если же действительные части равны, то в порядке возрастания их мнимых частей. Покажем, что корни z1(L) и z3(L) симметричны относительно корня z2(L). Для этого воспользуемся формулами Кардано [6, с. 235]: если дано кубическое уравнение , то (напомним, кубический корень в поле комплексных чисел имеет три возможных значения): (8) причем первый и второй кубические корни в правой части выбираются таким образом, чтобы их произведение равнялось -p/3. В нашем случае , . Кроме того, оба квадратных корня в правой части должны быть одинаковыми. Использование формулы (8) для анализа симметричности корней, ввиду указанных ограничений, неудобно. В частности, необходимо перебрать до девяти пар чисел — все комбинации пар трех значений кубического корня первого слагаемого в правой части (8) и трех — второго слагаемого, поэтому преобразуем выражение (8) в более удобную для анализа форму. Умножим второе слагаемое в правой части (8) на сопряженное выражение — по сути, сопряженным является первое слагаемой в (8). Получим (9) Пусть вначале 0, и = π, если w 0. Случаи a(L) 0, точка z3 не может быть точкой максимума. Сравним между собой значения f(z1) и f(z3). Обозначим: и исследуем поведение ψ при . Поскольку при имеем и , , , то ввиду соотношения при выводим: при Отсюда получаем: при . На основе (10) выводим: при , (12) и, аналогично, . На основе (12) имеем: при , и, аналогично, . Отсюда выводим: при . Следовательно, для точки максимума zmax функции f(z) имеем: если > 0, то ; если же 0 при достаточно больших L) для функции f(z) справедливо представление , откуда вытекает: , и , т. е. и в качестве точки максимума можно выбирать любую из точек — z1 или z3. Последние соотношения можно получить и на основе соотношений (10) — в данном случае . На основе всего вышесказанного, определения функций a(L) и b(L), полагая , , приходим к следующему правилу выбора решения задачи (6): если A0 + B0 > 0, то ; если A0 + B0 0, и xi = 0, если Bi 0, то желательно, чтобы вектор был бы по направлению как можно ближе к вектору . Если же в (16) xi = 0, т. е. ≤ 0, то вектор должен быть направлен в противоположную сторону, т. е. как можно ближе к вектору -. Выполнение данных условий дает определенные гарантии того, что условие (16) для индекса i сохранится в новом решении . В случае же выполнения (17) для индекса i, т. е. при , требования к вектору в каждом из двух случаев (xi = 0 и xi = 1) заменяются на противоположные по соображениям, аналогичным предыдущему случаю: если в (17) xi = 0, т. е. > 0, то желательно, чтобы вектор был бы направлен в сторону, противоположную направлению роста функции для того, чтобы добиться выполнения противоположного неравенства ≤ 0 — по направлению как можно ближе к вектору -; если же в (17) xi = 1, т. е. ≤ 0, то вектор должен быть направлен в противоположную сторону, т. е. как можно ближе к вектору . Аналогичные рассуждения и обоснования можно использовать и для выбора значений последних K компонентов вектора , относящихся к переменным tk, поскольку необходимо обеспечить выполнение условия tk ≥ 0. Вектор сформируем как линейную комбинацию векторов по всем i. Встает вопрос о величине коэффициента перед каждым слагаемым в этой линейной комбинации. Отметим: можно принять, что вклад слагаемых, для которых выполняется условие (14) (выполнение этих условий надо сохранить), равен вкладу слагаемых, для которых это условие не выполняется, поскольку для решения задачи одинаково важны как сохранение части уже выполняемых условий, так и обеспечение изменения невыполняемых условий. Важно также, чтобы векторы и были равноценны при формировании вектора , поскольку влияние обоих слагаемых одинаково важно при вычислении . Последнее требование мы представим в виде соотношение , где есть длина вектора . Для вычисления коэффициентов указанной линейной комбинации воспользуемся следующим рассуждениями. Если значение достаточно велико по модулю, то значения функции могут быть подвергнуты более резким изменениям с относительно большими шансами, что при этом условие (15) для индекса i сохранится при , условие (17) заменится на противоположное при , и, аналогично, для условий (18). Сказанное означает, что вектор в линейной комбинации должен учитываться в меньшей степени (т. к., как было сказано выше, предполагается вектор максимально «запараллелить» с векторами ), т. е. его коэффициент в линейной комбинации может быть малым, чтобы меньше мешать изменению условий в (17). Если же значение мало, то при формировании вектора в случае (16) (т. е. при ) значение вектора — в составе должно учитываться в большей степени, чтобы обеспечить, по возможности, сохранение условия (16), т. е. коэффициент должен быть большим. В случае же условия (17), т. е. при , при малом абсолютном значении значение коэффициента перед вектором может быть большим, чтобы способствовать изменению условий (17) на противоположные. Отметим: чем больше значение , тем в большей степени должно учитываться значение вектора . Построим векторы и на основе вектора путем замены на нулевые значения последних K координат (относящихся к переменным tk) соответственно первых N координат (относящихся к переменным xi). При этом (N + k)-я координата последнего вектора умножается на tk/2 для всех k от 1 до K. Вышесказанное позволяет предложить следующее выражение для вектора : , (19) где задает знак i-го слагаемого в соответствии с представленными выше обоснованиями для случаев xi = 0 и xi = 1, sgn(tk) =1, если tk ≥ 0, sgn(tk) = -1, если tk 0, > 0, > 0 и > 0, > 0, > 0 выбираются так, чтобы и . Можно взять β = 0,1 (на порядок меньше промежутка [0; 1] поиска решений) и δ = 0,01 (большая часть переменных tk равна нулю в оптимальном решении). Тогда линейно выражается через , что после подстановки в выражение для в (19) приводит к сокращению числителя и знаменателя на . Это означает, что вектор от конкретных значений не зависит, и поэтому можно положить = 1. Тогда Аналогичное выражение выводится и для : Необходимо также описать процесс построения начального значения вектора решений . Отметим, что в качестве начального варианта может быть взят любой набор из нулей и единиц длины N, например набор, состоящий из одних нулей. Однако в этом случае в процессе поиска оптимального решения может потребоваться большое число дополнительных итераций, поэтому выбор наиболее приемлемого начального варианта также является важным элементом процедуры решения системы (14). В ряде случаев можно выбрать решение на основе следующей процедуры. Предположим, что целевую функцию исходной задачи (1) удалось представить в виде суммы S отдельных относительно простых слагаемых; например, в задаче формирования учебного расписания [1] целевая функция представляет собой сумму 19 относительно простых слагаемых. Тогда исходная задача (1) запишется в виде (3). По описанной процедуре с нулевыми начальными данными решаем независимо S задач (2), (3), в k-й из которых целевая функция равна k-му квадратичному слагаемому целевой функции. Пусть в результате решения k-й задачи получено оптимальное решение . Тогда в качестве начального решения исходной задачи (1), (2) можно взять следующий вектор: полагаем ; тогда вектор , где , если , и , если . Полученное описанным образом решение во многих случаях будет существенно ближе к искомому оптимальному решению, чем при случайном начальном варианте решения, что значимо уменьшит число требуемых итераций для нахождения оптимального решения . Описанная процедура нахождения решения системы (14) может быть записана в виде следующего общего алгоритма. 1. Задается начальное решение . Можно положить либо взять любой другой набор из N чисел 0 и 1, либо найти начальное значение на основе описанной выше процедуры. 2. Пусть построено решение для некоторого k ≥ 0. Тогда на основе соотношений (17) и (18) находим вектор . 3. Находим вектор : . Затем находим новый вектор решений , где = 1, если , и = 0, если (. 4. Если для i выполнены условия (14), то процесс поиска прекращаем и полагаем . В противном случае переходим к шагу 2. Укажем на следующий важный элемент решения задачи (1), (2). В процессе преобразования указанной задачи в соответствии с методом штрафных функций были введены параметры (см. (5)). Выбор указанных параметров метода штрафных функций предполагается выполнить на основе существующих методов, приведенных во многих источниках; например в [7]. Однако специфический тип целевой функции (мы рассматриваем квадратичные функции), по-видимому, позволяет уточнить правила выбора параметров штрафных функций, что предполагается выполнить в дальнейшем. Заключение В ходе исследования рассматривалось обобщение классической задачи квадратичного программирования, когда наряду с линейными ограничениями допускается наличие квадратичных ограничений, в частности случай, когда переменные могут принимать только бинарные значения — 0 или 1. Подобные задачи важны при выборе оптимальных структур систем, состоящих из большого числа вариантов, и выбор или отказ от выбора отдельных вариантов равносилен значениям 1 или 0 соответствующих бинарных переменных. Описана процедура сведения указанной задачи на основе метода штрафных функций к задаче полиномиального программирования четвертой степени, когда все слагаемые, кроме одного, имеющего четвертую степень, имеют степень не более второй. Решение полученной оптимизационной задачи сведено к решению системы уравнений, содержащих только бинарные переменные. Предложен эвристический рекуррентный алгоритм решения полученной системы уравнений, описаны варианты построения начального варианта решения, а также параметров, используемых в предложенном методе. В процессе сведения использованы классические формулы Кардано для корней кубического уравнения, для практического нахождения которых получены соотношения и описана процедура вычисления. Полученный алгоритм может быть использован также при решении многих задач дискретной математики. Возможным продолжением исследований в рамках рассмотренной задачи может стать обоснование приведенного в работе алгоритма решения системы (14), а также поиск и разработка новых, более эффективных методов решения указанной системы, в том числе на основе различных современных эвристических алгоритмов. в частности генетических алгоритмов, алгоритмов муравьиных колоний, пчелиного роя и т. п. Важным направлением является также использование разработанного алгоритма при решении конкретных прикладных задач в различных профессиональных сферах.

1. Попов Г. А. Формализация задачи составления учебного расписания в высшем учебном заведении // Вестн. Астрахан. гос. техн. ун-та. 2006. № 1. С. 120-140.

2. Астахова И. Ф., Фирас А. М. Составление расписания учебных занятий на основе генетического алгоритма // Вестн. Воронеж. гос. ун-та. 2013. № 2. C. 93-99.

3. Кофман А., Анри-Лабордер А. Методы и модели исследования операций. Т. 3. Целочисленное программирование. М.: Мир, 1977. 433 с.

4. Соколов Г. А. Линейные и целочисленные задачи оптимизации: учеб. пособие. М.: Инфра-М, 2017. 132 с.

5. Ковалев М. М. Дискретная оптимизация: Целочисленное программирование. М.: Эдиториал УРСС, 2003. 191 с.

6. Курош А. Г. Курс высшей алгебры. М.: Наука, 1968. 451 с.

7. Васильев Ф. П. Численные методы решения экстремальных задач. М.: Наука, 1980. 518 с.

Цитировать

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

  • Электронная ссылка
  • Печатная ссылка

Попов Г. АЛГОРИТМ РЕШЕНИЯ ЗАДАЧ БИНАРНОГО КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ МЕТОДОМ ШТРАФНЫХ ФУНКЦИЙ // Вестник Астраханского государственного технического университета. Серия: Управление, вычислительная техника и информатика. 2017. №. 2. С. 48-61. DOI: https://doi.org/ 10.24143/2072-9502-2017-2-48-61 (дата обращения: 30.10.2023).

Попов Г. АЛГОРИТМ РЕШЕНИЯ ЗАДАЧ БИНАРНОГО КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ МЕТОДОМ ШТРАФНЫХ ФУНКЦИЙ // Вестник Астраханского государственного технического университета. Серия: Управление, вычислительная техника и информатика. 2017. №. 2. С. 48-61. DOI: https://doi.org/ 10.24143/2072-9502-2017-2-48-61

  • Электронная ссылка
  • Печатная ссылка

Попов Г. «АЛГОРИТМ РЕШЕНИЯ ЗАДАЧ БИНАРНОГО КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ МЕТОДОМ ШТРАФНЫХ ФУНКЦИЙ» Вестник Астраханского государственного технического университета. Серия: Управление, вычислительная техника и информатика 2 (2017): 48-61. DOI: https://doi.org/ 10.24143/2072-9502-2017-2-48-61 (дата обращения: 30.10.2023).

Попов Г. «АЛГОРИТМ РЕШЕНИЯ ЗАДАЧ БИНАРНОГО КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ МЕТОДОМ ШТРАФНЫХ ФУНКЦИЙ» Вестник Астраханского государственного технического университета. Серия: Управление, вычислительная техника и информатика 2 (2017): 48-61. DOI: https://doi.org/ 10.24143/2072-9502-2017-2-48-61 Print.

  • Электронная ссылка
  • Печатная ссылка

Попов Г. (2017). АЛГОРИТМ РЕШЕНИЯ ЗАДАЧ БИНАРНОГО КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ МЕТОДОМ ШТРАФНЫХ ФУНКЦИЙ. Вестник Астраханского государственного технического университета. Серия: Управление, вычислительная техника и информатика. (2), 48-61. DOI: https://doi.org/ 10.24143/2072-9502-2017-2-48-61 Получено из (дата обращения: 30.10.2023)

Попов Г. (2017). АЛГОРИТМ РЕШЕНИЯ ЗАДАЧ БИНАРНОГО КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ МЕТОДОМ ШТРАФНЫХ ФУНКЦИЙ. Вестник Астраханского государственного технического университета. Серия: Управление, вычислительная техника и информатика. (2), 48-61. DOI: https://doi.org/ 10.24143/2072-9502-2017-2-48-61

  • Электронная ссылка
  • Печатная ссылка

Попов Г. «АЛГОРИТМ РЕШЕНИЯ ЗАДАЧ БИНАРНОГО КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ МЕТОДОМ ШТРАФНЫХ ФУНКЦИЙ». Вестник Астраханского государственного технического университета. Серия: Управление, вычислительная техника и информатика, 2017 (2): 48-61. DOI: https://doi.org/ 10.24143/2072-9502-2017-2-48-61 (дата обращения: 30.10.2023).

Попов Г. «АЛГОРИТМ РЕШЕНИЯ ЗАДАЧ БИНАРНОГО КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ МЕТОДОМ ШТРАФНЫХ ФУНКЦИЙ». Вестник Астраханского государственного технического университета. Серия: Управление, вычислительная техника и информатика, 2017 (2): 48-61. DOI: https://doi.org/ 10.24143/2072-9502-2017-2-48-61

  • Электронная ссылка
  • Печатная ссылка

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *