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

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

Метод деревьев решений (decision trees) является одним из наиболее популярных методов решения задач классификации и прогнозирования. Иногда этот метод Data Mining также называют деревьями решающих правил, деревьями классификации и регрессии. Как видно из последнего названия, при помощи данного метода решаются задачи классификации и прогнозирования. Если зависимая, т.е. целевая переменная принимает дискретные значения, при помощи метода дерева решений решается задача классификации. Если же зависимая переменная принимает непрерывные значения, то дерево решений устанавливает зависимость этой переменной от независимых переменных, т.е. решает задачу численного прогнозирования.

Впервые деревья решений были предложены Ховилендом и Хантом (Hoveland, Hunt) в конце 50-х годов прошлого века. Самая ранняя и известная работа Ханта и др., в которой излагается суть деревьев решений – «Эксперименты в индукции» («Experiments in Induction») – была опубликована в 1966 году.

В наиболее простом виде дерево решений – это способ представления правил в иерархической, последовательной структуре. Основа такой структуры – ответы «Да» или «Нет» на ряд вопросов.

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

Рис. 9.1. Дерево решений «Играть ли в гольф?»

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

В результате прохождения от корня дерева (иногда называемого корневой вершиной) до его вершины решается задача классификации, т.е. выбирается один из классов – «Играть» и «Не играть» в гольф.

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

Итак, для нашей задачи основными элементами дерева решений являются:

- Корень дерева: «Солнечно?»

- Внутренний узел дерева или узел проверки: «Температура воздуха высокая?», «Идет ли дождь?»

- Лист, конечный узел дерева, узел решения или вершина: «Играть», «Не играть»

- Ветвь дерева (случаи ответа): «Да», «Нет».

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

В узлах бинарных деревьев ветвление может вестись только в двух направлениях, т.е. существует возможность только двух ответов на поставленный вопрос («Да» и «Нет»).

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

Рассмотрим более сложный пример.

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

Эксперты в области банковского кредитования выделяют несколько факторов, которые влияют на кредитоспособность человека (табл. 9.1).

Таблица 9.1. Факторы, влияющие на кредитоспособность

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

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

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

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

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

Правилом является логическая конструкция, представленная в виде «если: то:».

На рис.9.2. приведен пример дерева классификации, с помощью которого решается задача «Выдавать ли кредит клиенту?». Она является типичной задачей классификации, и при помощи деревьев решений получают достаточно хорошие варианты ее решения.

Рис. 9.2. Дерево решений «Выдавать ли кредит?»

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

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

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

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

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

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

Пример 9.3. Для демонстрации подобной технологии будет использоваться программа Tree Analyzer из пакета Deductor. В качестве исходных данных была взята выборка, состоящая из 1000 записей. Где каждая запись – это описание характеристик заемщика плюс параметр, описывающий его поведение во время погашения ссуды. При обучении дерева использовались следующие факторы, определяющие заемщика: «N Паспорта»; «ФИО»; «Адрес»; «Размер ссуды»; «Срок ссуды»; «Цель ссуды»; «Среднемесячный доход»; «Среднемесячный расход»; «Основное направление расходов»; «Наличие недвижимости»; «Наличие автотранспорта»; «Наличие банковского счета»; «Наличие страховки»; «Название организации»; «Отраслевая принадлежность предприятия»; «Срок работы на данном предприятии»; «Направление деятельности заемщика»; «Срок работы на данном направлении»; «Пол»; «Семейное положение»; «Количество лет»; «Количество иждивенцев»; «Срок проживания в данной местности»; «Обеспеченность займа»; «Давать кредит». При этом поля: «N Паспорта», «ФИО», «Адрес», «Название организации» алгоритм уже до начала построения дерева решений определил как непригодные (рис. 9.3) по причине практической уникальности каждого из значений.

Целевым полем является поле «Давать кредит», принимающий значения «Да»(True) и «Нет»(False). Эти значения можно интерпретировать следующим образом: «Нет» – плательщик либо сильно просрочил с платежами, либо не вернул часть денег, «Да» – противоположность «Нет».

Рис. 9.3. Настройка определяющих и целевых факторов

После процесса построения дерева решений при помощи программы Tree Analyzer получаем следующую модель оценки кредитоспособности физических лиц, описывающую ситуацию, относящуюся к определенному банку. Эта модель представлена в виде иерархической структуры правил – дерева решений (рис. 9.4).

Рис. 9.4. Фрагмент модели определения кредитоспособности физических лиц

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

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

2. Можно заметить, что такие показатели как «Размер ссуды», «Срок ссуды», «Среднемесячный доход» и «Среднемесячный расход» вообще отсутствуют в полученном дереве. Данный факт можно объяснить тем, что в исходных данных присутствует такой показатель как «Обеспеченность займа», и т.к. этот фактор является точным обобщением 4 вышеописанных показателей, алгоритм построения дерева решений выбрал именно его.

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

1. ЕСЛИ Обеспеченность займа = Да И Срок проживания в данной местности, лет > 5.5 И Количество лет > 19.5 И Наличие недвижимости = Да И Наличие банковского счета = Да ТО Давать кредит = Да (Достоверно на 98%)

2. ЕСЛИ Обеспеченность займа = Да И Срок проживания в данной местности, лет > 5.5 И Наличие недвижимости = Да И Количество лет > 21.5 И Срок работы на данном направлении, лет <= 5.5 И Пол = Муж И Наличие банковского счета = Нет И Основное направление расходов = Одежда, продукты питания и т.п. ТО Давать кредит = Нет(Достоверно на 88%)

3. …

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

На основе построенной модели можно определять принадлежность потенциального заемщика к одному из классов. Для этого необходимо воспользоваться диалоговым окном «Эксперимент» программы Tree Analyzer (рис. 9.5), в котором, последовательно отвечая на вопросы, можно получить ответ на вопрос: «Давать ли кредит».

Рис. 9.5. Окно «Эксперимент»