3.1.5. Декомпозиция задач принятия решения
Решать задачи по очереди. Естественным является желание разбить сложную задачу принятия решения на несколько, чтобы воспользоваться возможностью решать их по очереди.
Пример 1. Простейшим вариантом является дихотомическая схема для наглядного представления возможных решений [8]. Например, необходимо решить приятную практическую задачу: «Как встречать новый год?» На первом шаге надо выбрать одно из двух возможных решений: 1) остаться дома; 2) уехать.
В каждом из двух случаев возникает необходимость принять решения второго уровня. Так, в первом случае: 1.1) пригласить гостей: 1.2) не звать гостей.
Во втором случае: 2.1) уехать к родственникам или знакомым; 2.2) уехать в общедоступные места (отправиться в путешествие, пойти в клуб или ресторан и т.п.).
После двух шагов получили четыре возможных решения. Каждое из них, вообще говоря, предполагает дальнейшее деление. Так, например, вариант «пригласить гостей» приводит к дальнейшему обсуждению их списка. При этом могут сопоставляться различные варианты. Например, что предпочесть – гастрономические утехи за телевизором в хорошо знакомой компании или бурное обсуждение злободневных проблем или нравов далеких стран с интересными людьми, с которыми давно не встречались?
Вариант «остаться дома и не звать гостей» также имеет свои варианты. Можно проводить новогоднюю ночь в семейном кругу, и одна из решаемых подзадач – какую программу телевидения смотреть. А можно лечь спать вскоре после полуночи, например, в случае болезни или после долгой тяжелой работы.
Вариант «уехать к родственникам или знакомым» также требует дальнейших решений. Поездка связана прежде всего с поддержанием родственных отношений или с желанием получить удовольствие? Какую пищу Вы предпочитаете – физическую или духовную (гастрономические утехи или интересную беседу)?
Оставшийся четвертый вариант «уехать в общедоступные места» предполагает еще больше возможностей выбора. Можно остаться в своем городе, отправиться в другой город (например, из Москвы в Смоленск), выехать на природу (на горнолыжную базу, на курорт), пересечь границу. А тут возможностей масса – все страны, все континенты, можно покататься на слоне в Таиланде, искупаться в Атлантическом океане или побродить по Парижу.
Итак, рядовая задача принятия решения «Как встречать новый год?» при проработке превращается в выбор из невообразимого количества вариантов. При этом нет необходимости доходить до перечня конкретных вариантов (выехать 28 декабря таким-то поездом туда-то), поскольку решение, очевидно, принимается последовательно, и решение «остаться дома» делает ненужным рассмотрение всех туристических маршрутов.
Что дает нам декомпозиция решений? Пример 1 демонстрирует, как несколько принятых друг за другом решений позволяют справиться с многообразием вариантов. При принятии решений может использоваться весь арсенал теории принятия решений, такие понятия, как цели, критерии, ресурсы, риски и др., однако довольно часто решения принимаются на интуитивном уровне, без введения в обсуждение перечисленных понятий.
Дерево решений. Довольно часто удобно представить варианты графически. Обычно возможные решения представляют в виде одного из видов графов – дерева (рис.1). Строго говоря, это перевернутое дерево. Корнем является исходная задача – «Как встречать Новый год?» От него идут две ветви – к вариантам «Остаться дома» и «Уехать». От этих вариантов, в свою очередь являющихся задачами принятия решений («Что делать, оставшись дома?» и «Куда уехать?»), ветки ведут к вариантам задач принятия решений следующего порядка.
Рис.1. Дерево решений – дихотомическая схема для наглядного представления возможных решений.
Пример 2. Приведем начало (корень) «Дерева решений проекта», использованного в практической работе.
Задача предприятия – производить качественные изделия из стекловолокна, т.к. растет потребность в утеплителях и расширяется рынок. Необходимо сделать выбор из двух вариантов:
1) работать на существующем оборудовании;
2) провести реконструкцию цеха.
При выборе первого варианта следует иметь в виду, что мощности оборудования не столь большие, чтобы обеспечить возросшую потребность (велик физический износ линии), а качество производимой продукции не соответствует международным требованиям (значителен моральный износ линии). Поэтому следует ожидать, что даже в условиях ожидаемого повышенного спроса выпущенные на существующем оборудовании материалы не будут востребованы (реализация будет падать), соответственно мощность производства не будет расти.
При выборе второго варианта решения после реконструкции производительность увеличивается в 2 раза по сравнению с существующей технологической линией, качество выпускаемой предприятием продукции будет соответствовать международным требованиям, она сможет конкурировать с главными производителями стекловаты. Повысятся основные технико-экономические показатели. Однако существует определенный риск проекта, поскольку необходимы большие капитальные вложения (большая часть которых – из заемных источников).
Дальнейшее построение дерева решений здесь достаточно очевидно. От варианта «Работать на существующем оборудовании» пойдут линии к решениям, связанным с упрощением ассортимента выпускаемой продукции, поиском ниши рынка, готовой принимать продукцию более низкого качества, и т.д. Это – линия на выживание в условиях отставания от научно-технического прогресса, вплоть до ликвидации предприятия. В некоторых условиях ликвидация предприятия – это оптимальный выход.
От варианта «Провести реконструкцию цеха» пойдут линии двух типов – сначала «технологические», а затем «финансовые». Сначала надо выбрать конкретный вариант реконструкции и подготовить бизнес-план соответствующего инвестиционного проекта. Затем необходимо обеспечить финансовые поступления для выполнения этого инвестиционного проекта, обеспечив минимальный риск для предприятия. Здесь проблема – выбор кредиторов и заемщиков, заключение с ними договоров на приемлемых условиях.
Кроме последовательного принятия решений, декомпозиция задач принятия решений используется для «разделения проблем на части». При этом результатом декомпозиции является не выбор одного из большого числа вариантов, как при последовательном принятии решений, а представление решаемой задачи в виде совокупности более мелких задач, в пределе – таких задач, методы решения которых известны.
Пример 3. Рассмотрим проблему борьбы с транспортным шумом [8]. Целесообразно выделить следующие типы мероприятий:
1) мероприятия, связанные с источником шума;
2) мероприятия на месте проявления шума;
3) мероприятия на пути распространения шума;
4) мероприятия, относящиеся ко всей системе транспортных средств;
5) мероприятия, связанные с реконструкцией транспортной системы и разработкой способов ее технико-экономической оценки.
В отличие от примера 1, здесь не идет речь о том, чтобы выбрать один из вариантов решения. Наоборот, для эффективной борьбы с транспортным шумом необходимо использовать все ветви, все пять типов мероприятий.
Источник шума – это автомашина. Поэтому сразу выделяются три направления воздействия на ситуацию:
1.1) конструкция автомашины (включая регулировку ее узлов);
1.2) топливо;
1.3) дорога.
Непосредственная защита от шума может быть индивидуальная - шлемы, наушники, вставки в уши - беруши (сокращение от «берегите уши»). А может быть и коллективная (звуконепроницаемые оконные рамы, стены со звукоизоляцией). Поэтому мероприятия на месте проявления шума естественным образом делятся на два класса:
2.1) индивидуальная защита от шума;
2.2) подавление шума в зданиях.
Можно ослабить шум «по дороге» от источника шума до ушей людей. Хорошо известны различные способы для этого:
3.1) сооружение звукозащитных стен и экранов, отражающих звуковые волны в безопасных направлениях;
3.2) создание звукозащитных полос из деревьев и кустарников;
3.3.) противошумное расположение зданий на местности (как по расстоянию от источника шума, так и по ориентации зданий относительно него и друг друга.
Снижение шума возможно также с помощью различных мероприятий, относящихся ко всей системе транспортных средств. Речь идет о рациональной организации движения в рамках действующей транспортной системы. Эта рациональная организация осуществляется региональными властями административными и частично организационно-экономическими методами. Примерами подобных мероприятий являются:
4.1) направление транзитного транспорта в объезд крупных городов;
4.2) ограничение движения транспорта в определенные часы или по определенным улицам;
4.3) планирование движения транспорта – по времени, по скорости, по маршрутам.
Наконец, необходимо обсудить мероприятия, нацеленные на будущее. Они связаны с реконструкцией транспортных систем и разработкой способов ее технико-экономической оценки. Каков должен быть транспорт будущего? Ясно, что в нем должны быть предусмотрены меры, направленные на снижение шумовой нагрузки. Технико-экономическая оценка транспортных систем будущего должна определяться с учетом шумовой нагрузки. Выразим это как
5.1) шумоподавление в проектируемых и реконструируемых транспортных системах.
Таким образом, одна исходная задача породила 12 новых. Надо не выбирать одну из них, а решать все 12. Однако каждая из 12 является более конкретной, чем исходная. Ее легче решить (после дальнейшей декомпозиции), чем исходную.
Алгоритм дерева принятия решений (Майкрософт) представляет собой алгоритм регрессии и алгоритм классификации, предоставляемый службами Microsoft SQL Server Службы Analysis Services для использования в прогнозирующем моделировании как дискретных, так и непрерывных атрибутов.
Для дискретных атрибутов алгоритм осуществляет прогнозирования на основе связи между входными столбцами в наборе данных. Он использует значения этих столбцов (известные как состояния) для прогнозирования состояний столбца, который обозначается как прогнозируемый. Алгоритм идентифицирует входные столбцы, которые коррелированы с прогнозируемым столбцом. Например, в сценарии для прогнозирования того, какие заказчики, скорее всего, приобретут велосипед, если девять из десяти молодых заказчиков покупают велосипед, но только двое из более старших заказчиков делают это, то алгоритм заключает, что возраст является хорошим прогнозом приобретения велосипеда. Дерево решений осуществляет прогнозирование на основе этой тенденции в направлении конкретного результата.
Для непрерывных атрибутов алгоритм использует линейную регрессию для определения места разбиения дерева решений.
Если несколько столбцов установлены как прогнозируемые или если входные данные содержат вложенную таблицу, которая задана как прогнозируемая, то алгоритм строит отдельное дерево решений для каждого прогнозируемого столбца
Пример
Отделу маркетинга компании Adventure Works Cycles нужно идентифицировать характеристики предыдущих заказчиков, которые могут указывать на высокую вероятность приобретения этими заказчиками продукта в будущем. В базе данных AdventureWorks2012 хранятся демографические данные, описывающие предыдущих заказчиков. Используя алгоритм дерева принятия решений (Майкрософт) для анализа этих данных, маркетинговый отдел может построить модель, которая прогнозирует, будет ли конкретный заказчик покупать продукты, на основании состояний известных столбцов, содержащих данные об этом заказчике, например демографические данные и сведения о покупках в прошлом.
Принцип работы алгоритма
Алгоритм дерева принятия решений (Майкрософт) строит модель интеллектуального анализа данных путем создания ряда разбиений в дереве. Эти разбиения представлены как узлы. Алгоритм добавляет узел к модели каждый раз, когда выясняется, что входной столбец имеет значительную корреляцию с прогнозируемым столбцом. Способ, которым алгоритм определяет разбиение, отличается в зависимости от того, прогнозирует ли он непрерывный столбец или дискретный столбец.
Алгоритм дерева принятия решений Майкрософт использует выбор компонентов для руководства набором наиболее полезных атрибутов. Выбор компонентов используется всеми алгоритмами интеллектуального анализа данных служб Службы Analysis Services для увеличения производительности и качества анализа. Выбор компонентов играет важную роль в предотвращении использования процессорного времени малозначительными атрибутами. Если при разработке модели интеллектуального анализа данных в нее было добавлено слишком много входных или прогнозируемых атрибутов, то ее обработка может занять очень много времени или даже привести к нехватке памяти. В методы, определяющие необходимость в разбиении дерева, входят стандартные для отраслей метрики для энтропии и Байесовых сетей. Дополнительные сведения о методах, используемых для выбора полезных атрибутов, а затем для создания рейтингов и для ранжирования атрибутов, см. в разделе Выбор компонентов (интеллектуальный анализ данных).
Одной из часто встречающихся проблем в моделях интеллектуального анализа данных является чрезмерная чувствительность к небольшим различиям в обучающих данных; в таких случаях модель называется чрезмерно оснащенной или чрезмерно обученной. Чрезмерно оснащенную модель нельзя свести к другим наборам данных. Во избежание чрезмерного оснащения определенного набора данных, в алгоритме дерева принятия решений (Майкрософт) используются методики контроля роста дерева. Более подробное описание работы алгоритма дерева принятия решений Майкрософт см. в разделе Технический справочник по алгоритму дерева принятия решений (Майкрософт).