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

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

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

Дерево решений (decision tree) представляет собой способ представления правил в виде иерархической структуры (графадерева). В вершинах графа записываются вопросы, а ребра соответствуют вариантам ответов. Выбирая ответы на поставленные вопросы, осуществляется постепенный спуск по дереву к концевым (терминальным) вершинам, соответствующим решениям. Каждый следующий вопрос, который задает система, зависит от предыдущих ответов. Таким образом, организуется содержательный диалог, позволяющий выбрать «правильное» решение из нескольких альтернатив, с учетом множества факторов.

С математической точки зрения, ДР – это размеченный, ориентированный нерегулярный граф.

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

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

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

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

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

Качество классификационной модели, построенной при помощи дерева решений, характеризуется двумя основными признаками:

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

Существует множество алгоритмов, реализующих деревья решений: CART, C4.5, Quest, CHAID, CN2, NewId, ITrule и другие. В работе будет использован алгоритм CART (Classification and Regression Tree), который предназначен для построения бинарного ДР, т.е. дерева, каждый узел которого имеет только две дочерние ветви. В результате на каждом шаге построения дерева правило, формируемое в узле, делит заданное множество на две части так, что в правой части правило выполняется, в левой – нет.

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

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

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

  • результате система должна содержать следующие функциональные подсистемы:
  • Аналитическая подсистема. Данная подсистема предназначена для сбора информации от пользователя и передачи ее непосредственно в подсистему инсталляции.
  • Программная подсистема инсталляции. Представляет собой существующий WPI продукт для «тихой установки» программ на основе имеющихся данных, полученных от пользователя.

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

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

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

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

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

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

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

Статья на тему разработка инструментального средства принятия решений в сфере потребительского выбора