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

Виды управленческих решений

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

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

Постановка цели решения – первый шаг алгоритма стандартного вида принятия управленческого решения. Правильность постановки цели решения предопределяет ответы на три вопроса: «Какой выбор я пытаюсь сделать? Почему это решение необходимо? Каким было последнее принятое решение?» (последний вопрос связан с концепцией конкретного предприятия). Правильность постановки цели решения определяется его связью с предшествующими решениями.

Стандартный вид принятия управленческого решения

Рис. 6.8. Стандартный вид принятия управленческого решения

Установление критериев решения – второй шаг. Первый вопрос, который задает себе руководитель: «Достигнет ли решение желаемых результатов?», т.е. рассмотренные факторы должны быть учтены в конкретных требованиях. Чтобы принять эффективное решение, необходимо разделить имеющиеся критерии на жесткие ограничения и характеристики, без которых невозможно обойтись, – эго третий шаг в данном алгоритме. Желательные критерии необходимо расположить в порядке приоритетов. Существует несколько методов оценки приоритетов. Простейший из них – балльная система, где максимальное количество баллов равно 10. Каждый балл указывает на относительную ценность и влияние желательного критерия при принятии решения.

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

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

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

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

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

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

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

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

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

Управление рисками в процессе принятия управленческого решения

Рис. 6.9. Управление рисками в процессе принятия управленческого решения

Процесс принятия бинарного решения

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

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

Принятие бинарного решения возможно в том случае, когда предполагается решение «да» или «нет». Выбор бинарного решения отображен на рис. 6.10.

Алгоритм бинарного принятия решений

Рис. 6.10. Алгоритм бинарного принятия решений

Основные шаги: постановка цели, выявление потенциальных результатов, установление критериев решения, разделение критериев и сравнение альтернатив «да, нет», выявление и оценка риска.

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

Процесс принятия многовариантного решения

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

Алгоритм принятия многовариантного решения

Рис. 6.11. Алгоритм принятия многовариантного решения

Процесс принятия инновационного решения

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

Выбор инновационного решения делается с помощью шагов, которые отражены рис. 6.12.

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

Сравним рациональный и инновационный процессы принятия решений (табл. 6.1).

Алгоритм принятия инновационного решения

Рис. 6.12. Алгоритм принятия инновационного решения

Таблица 6.1

Сравнение рационального и инновационною процессов

Постановка проблемы

Носит конкретный характер

Носит более общий характер

Используется логический подход

Синтез, мозговая атака, другие методы

Результаты

Вырабатывается одна альтернатива

Вырабатывается несколько альтернатив

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм решения задач бинарного квадратичного программирования методом штрафных функций Текст научной статьи по специальности «Математика»

КВАДРАТИЧНОЕ ПРОГРАММИРОВАНИЕ / БИНАРНЫЕ ПЕРЕМЕННЫЕ / ОПТИМАЛЬНОЕ РЕШЕНИЕ / ФОРМУЛА КАРДАНО / ЭВРИСТИЧЕСКИЙ АЛГОРИТМ / QUADRATIC PROGRAMMING / BINARY VARIABLES / OPTIMAL SOLUTION / CARDANO FORMULA / HEURISTIC ALGORITHM

Аннотация научной статьи по математике, автор научной работы — Попов Георгий Александрович

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

i Надоели баннеры? Вы всегда можете отключить рекламу.

ALGORITHM OF SOLVING THE PROBLEMS OF THE BINARY SQUARE PROGRAMMING BY THE METHOD OF PENALTY FUNCTIONS

In this paper the author analyses generalization of the classical quadratic programming problem, when along with linear constraints quadratic constraints are allowed. The author consider the case when variables can take only binary values 0 or 1. Such problems are important when choice of the optimal structures of systems covers a large number of variants, and the choice or refusal to select individual variants is equivalent to values 1 or 0 of the corresponding binary variables . There is described the procedure of reducing the indicated problem to the fourth-degree polynomial programming problem on the basis of the penalty method, when all terms are no greater than in the second power, except one having a fourth power. The solution of the obtained optimization problem is reduced to solving a system of equations containing only binary variables . The author proposes a heuristic recursive algorithm for solving the resulting system of equations, and variants of constructing the initial version of the solution. The parameters used in the proposed method are described. In the process of reduction, there are used the classical Cardano formulas for the roots of a cubic equation, for the practical finding of which the relations are obtained and the calculation procedure is described. The algorithm given in this paper can also be used to solve many problems of discrete mathematics.

Текст научной работы на тему «Алгоритм решения задач бинарного квадратичного программирования методом штрафных функций»

DOI: 10.24143/2072-9502-2017-2-48-61 УДК 004.056.5

АЛГОРИТМ РЕШЕНИЯ ЗАДАЧ БИНАРНОГО КВАДРАТИЧНОГО ПРОГРАММИРОВАНИЯ МЕТОДОМ ШТРАФНЫХ ФУНКЦИЙ

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

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

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

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

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

Вышеупомянутые задачи являются частным случаем задач целочисленного математического программирования, и поэтому, казалось бы, могут быть решены методами, используемыми при решении задач целочисленного программирования. Однако одна важная особенность делает все известные методы решения задач целочисленного программирования практически неприемлемыми и бесполезными при решении указанных задач: число альтернатив часто бывает настолько большим, что существующие вычислительные средства оказываются неспособными за разумное время найти решение указанных задач. Так, например, в работах [1, 2] приведены формализованные постановки задачи составления учебного расписания, когда в качестве бинарных переменных берутся следующие: xpgad = 1, если занятие по d-й дисциплине у g-й подгруппы проводится в a-й аудитории наp-й паре, и xpgad = 0 в противном случае. Это

означает, что в данной задаче индекс суммирования i представлен набором pgad. Тогда, как показано в [1], в этом случае число всех возможных переменных для типового вуза с общим числом студентов порядка 7 500 достигает 150 миллионов переменных xpgad, что делает практически невозможным автоматизированное решение указанной задачи на основе алгоритмов целочисленного программирования.

Бинарное программирование как самостоятельное научное направление исследований было выделено еще в 60-е гг. ХХ в.; наиболее важные методы решения задач бинарного программирования, применявшиеся в то время, можно найти в [3]. В дальнейшем сколь-нибудь значимых результатов по решению задач бинарного программирования с большим числом переменных, по-видимому, получить не удалось. Состояние исследований в данном направлении в настоящее время отражено в [4, 5]. Отметим также отсутствие значимых результатов по использованию современных эвристических методов оптимизации (генетических алгоритмов, нейронных сетей, методов муравьиных или пчелиных колоний и др.), которые доказали свою эффективность при решении многих других типов задач оптимизации.

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

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

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

Пусть задан набор переменных x, (i = 1; N ), каждая из которых принимает только значения 0 или 1, т. е. является бинарной переменной; x = (x1, x2, . xN). Тогда задачей квадратичного бинарного программирования является следующая оптимизационная задача:

Z(x) = ZZA,xx + ZBx + C ^ max, (1)

Для нас представляет интерес также несколько другая запись целевой функции (1):

Z(x) = Z ZZAjxx +ZBSx, + C ^max, (3)

s=1 у i=1 j>1 i=1 у

т. е. квадратичное выражение в целевой функции (1) представляется как сумма из S отдельных квадратичных выражений. Именно в таком виде представлена целевая функция в задаче формирования расписания занятий в [1], где S = 19, каждое квадратичное выражение в сумме по S имеет относительно простой вид и соответствует разным ограничениям задачи, число которых составляет порядка 30.

Отметим, что поскольку общее число возможных вариантов решений задачи (1), (2) ограничено (не превосходит 2N), то задача (1), (2) всегда имеет решение. Без ограничения общности можно считать C = 0.

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

_ _ NN N K f N Л2

Z(x;Lkk = 1;K) = ZZAjxx +ZBx I ZGf^r + E(k) + С 1 ^ max, (4)

i=1 j>1 i=1 k=1 v i=1 у

где tk = —I ZG(k)x, + E^k) l>0 (k = 1;K) — вспомогательные переменные; Lk > 0 трактуется как

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

ях Lk резко уменьшается. Поэтому оптимальное решение вынуждено стремиться обеспечить выполнение ограничений (2), при которых все слагаемые последней суммы равны нулю. Известно, что при достаточно больших значениях Lk для всех k решения (x*,i = 1;N> задач (4) и (1), (2) совпадают, поэтому вместо решения задачи (1), (2) можно решать задачу (4).

В записи задачи (4) учтены все ограничения задачи (1), (2), кроме самого важного — переменные xi являются бинарными. Для учета данного ограничения предлагается добавить в целевую функцию задачи еще по одному слагаемому на каждую переменную:

_ __NN N K f N Л2 N

Z(x;Lkkk = 1;K;L) = ZZ A.xx — ZL[ZGf^ + E(k) + tk I -(1 -x))2 ^ max, (5)

i=1 J>1 i=1 k=1 V i=1 ) i=1

где L >> max(Lj). Действительно, если для некоторого индекса i выражение xi (1 — xi) отличается

значимо от нуля, в целевой функции Z(x; Lk. k = 1; K; L) появляется большое по модулю отрицательное слагаемое (последняя сумма в правой части), которое сильно уменьшает значение целевой функции по сравнению со случаем xi (1 — xi) = 0.

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

2. Базовый случай одной переменной

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

Рассмотрим вначале случай функции одной переменной (т. е. N = 1). Тогда левую часть соотношения (5) после деления обеих частей на L можно записать в виде

или, после обозначений a = a(L) = -1 A + ZLk(G(k))2I, b = b(L) = -1 В — 2^LkG(k)(E(k) + tk)|,

e(L) = «L [ Zl (e (k) + tk ij, получаем f (x, L) = a(L) x2 + b(L) x — e(L) — ( x(1 — x) )2.

Проведем замену переменных 2 = 2 X — 1, т. е. х = ^ . Тогда, полагая

f (—) = f (L) = А (——, L) , с(Ь) = — е(L) +—(4-) +—(Ц-, из последнего соотношения выводим следующее представление задачи (5):

В силу необходимого условия экстремума из (6) следует уравнение

(—, Ь) = — а( Ь) — +—(а(Ь) + Ъ(Ь)) — (—2 — 1) — = 0. а— 2 2

Таким образом, точки максимума функции А—) являются корнями кубического уравнения

г> + | -1 -2а(Ц) 12 -|(а(Ц) + Ь(Ц)) = 0.

Уравнение (7) имеет в комплексной плоскости три корня Zi(L) (/ = 1, 2, 3), которые упорядочим лексикографически, т. е. в порядке возрастания их действительной части; если же действительные части равны, то в порядке возрастания их мнимых частей. Покажем, что корни Zl(L) и z3(Ц) симметричны относительно корня z2(Ц). Для этого воспользуемся формулами Кардано

[6, с. 235]: если дано кубическое уравнение г3 + р 2 + q = 0, то (напомним, кубический корень

в поле комплексных чисел имеет три возможных значения):

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

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

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

У 2 V 4 27 V 2 V

д-+р3 I—1— = 3 -1 + £+2 +. 2 4 27

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

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

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

Они представляют собой иерархические древовидные структуры, состоящие из решающих правил вида «Если . то . ». Правила автоматически генерируются в процессе обучения на обучающем множестве и, поскольку они формулируются практически на естественном языке (например, «Если объём продаж более 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) , которые, как предполагается, определяют принадлежность объекта к тому или иному классу. Тогда возможны три случая:

Все примеры множества S имеют одинаковую метку класса C_i (т.е. все обучающие примеры относятся только к одному классу). Очевидно, что обучение в этом случае не имеет смысла, поскольку все примеры, предъявляемые модели, будут одного класса, который и «научится» распознавать модель. Само дерево решений в этом случае будет представлять собой лист, ассоциированный с классом C_i . Практическое использование такого дерева бессмысленно, поскольку любой новый объект оно будет относить только к этому классу.
Множество S вообще не содержит примеров, т.е. является пустым множеством. В этом случае для него тоже будет создан лист (применять правило, чтобы создать узел, к пустому множеству бессмысленно), класс которого будет выбран из другого множества (например, класс, который наиболее часто встречается в родительском множестве).
Множество 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) — алгоритм обучения деревьев решений, позволяющий использовать как дискретную, так и непрерывную целевую переменную, то есть решать как задачи классификации, так и регрессии. Алгоритм строит деревья, которые в каждом узле имеют только два потомка.

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

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

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

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

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

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

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

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

где 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, когда классы представлены в равных пропорциях и равновероятны. Тогда лучшим будет то разбиение, для которого значение индекса Джини будут минимальным.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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