Здравоохранение, медицина

Деревья решений

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

Примем для простоты, что целевая переменная – булева переменная, принимающая только два значения – 0 и 1 и определенная для всех записей базы данных. Все множество записей в базе данных E мы можем разбить на 2 подмножества: Е+ (для которых целевая переменная Y имеет значение 1) и Е- (для которых ее значение равно 0). И теперь мы ищем классифицирующее правило, позволяющее разбить базу данных на эти два подмножества. В процессе поиска классифицирующего правила мы перебираем все независимые переменные и смотрим, какая из них может дать нам наиболее точное правило. Эти правила имеют обычно простой вид. Например, в случае действительной переменной это предикат вида x>A (или x

Одним из наиболее важных свойств деревьев решений является представление данных в виде иерархической структуры. Такая структура естественным образом может быть использована для классификации. Допустим, мы построили дерево, и у нас имеется запись, не включенная в число обучающих примеров, использованных для построения классифицирующих правил. Тогда, идя по этому дереву от корня (начального узла) к листьям (конечным узлам), проверяя каждый раз критерии, соответствующие узлам этого дерева, мы выбираем правую или левую ветвь дерева (правого или левого потомка) соответственно выполнению или невыполнению этого критерия. В конце концов, мы приходим к листу этого дерева (конечному узлу) и, соответственно, относим запись к одному из классов. За значение атрибута Y классифицируемой записи мы принимаем 0 или 1 в соответствии с меткой этого листа. Процесс классификации немного напоминает определение видов в ботанике или зоологии – отвечая на ряд вопросов, мы относим рассматриваемый объект к тому или иному классу.

Существует большое количество вариантов алгоритмов, строящих деревья решений. Многие из них состоят в рекурсивном применении некоторой процедуры расщепления первоначально ко всему множеству обучающих примеров, а затем к их подмножествам, получаемым в результате расщепления исходного множества записей. Для каждого множества записей эта процедура определяет непрерывный или дискретный атрибут, значение которого может быть наиболее точно использовано для прогноза значения атрибута Y и определяет критерий дробления. Если поля всех записей известны точно и полностью определяют значение поля Y, дробление должно идти до тех пор, пока оно дает хотя бы какой-то выигрыш в точности классификации. Эта процедура должна также уметь закончить процесс дробления – определить, что для некоторого множества записей уже не может быть построено статистически значимое классификационное правило, и таким образом это подмножество соответствует листу строимого дерева решений. Выбор атрибута и критерия, по которым производится расщепление множества, решение ситуации, когда не ясно к какому классу отнести некоторую запись, являются принципиальными моментами, различающими используемые алгоритмы построения деревьев решений.

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

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

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

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

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

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

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

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