Дальше

Назад

Начало

Конец

Список

Пусть в таблице произвольных гидробиологических наблюдений X размерностью m >1 один из признаков, измеренный в порядковой шкале, определяет класс объекта и может принимать значения из некоторого фиксированного набора {у₁, у₂, …, y_k, …, y_p}. Необходимо на основе обучающей выборки сформировать дерево классификации (дерево решений), содержащее совокупность логических условий, позволяющих для произвольного измерения х из Х указать класс качества y_k , к которому оно может принадлежать.

В разделе 6.4 нами описывались простейшие детерминационные правила, как особый математический объект, восходящий к силлогистике Аристотеля, и представляющий суждение вида “Если A, то B” (или сокращенно A → B), где A, B – соответственно, объясняющий и объясняемый признаки. Например, еще Наполеон Бонапарт утверждал "Ля вибрасьен са моле гош этюн гранд синь!" (“Дрожание моей левой икры – есть великий признак”, цит. по проф. Выбегалло). Но, поскольку любая связь такого рода вероятностна, то подобный диагноз не должен основываться на одном суждении. Так дрожание перед Аустерлицем не означает, что с тем же постоянством икра дрожала и перед Йеной (ошибка диагноза 1 рода). И совсем уж непонятно, почему она дрожала перед Ватерлоо (ошибка диагноза 2 рода).

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

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

Рекомендуемая литература: [Breiman et al., 1984; Коршунов, 1995; Loh, Shih, 1997; Деревья классификации.., URL]. Интересные методические материалы и Интернет-конференция по теме находятся также на сайте лаборатории BaseGroup Labs – http://www.basegroup.ru.

Деревья решений – один из методов автоматического анализа данных, основные идеи которого восходят к работам П. Ховленда (Р. Hoveland) и Е. Ханта (Е. Hunt) конца 50-х годов XX в. Их итогом явилась основополагающая монография [Hunt et al., 1966], давшая импульс развитию этого направления.

Построение деревьев классификации – один из наиболее важных приемов, используемых при проведении "добычи данных и разведывательного анализа" (Data Mining), реализуемый как совокупность методов аналитической обработки больших массивов информации с целью выявить в них значимые закономерности и/или систематические связи между предикторными переменными, которые затем можно применить к новым совокупностям измерений.

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

• CART (Classification and Regression Tree), разработанный Л. Брейманом с соавторами [Breiman et al., 1984], представляет собой алгоритм построения бинарного дерева решений – дихотомической классификационной модели; каждый узел дерева при разбиении имеет только двух потомков; как видно из его названия, алгоритм решает задачи как классификации, так и регрессии;
• C4.5 – алгоритм построения дерева решений с неограниченным количеством потомков у узла, разработанный Р. Куинленом [Quinlan, 1993]; не умеет работать с непрерывным целевым полем, поэтому решает только задачи классификации;
• QUEST (Quick, Unbiased, Efficient Statistical Trees) – программа, разработанная В. Ло и И. Ши [Loh, Shih, 1997], в которой используются улучшенные варианты метода рекурсивного квадратичного дискриминантного анализа, позволяющие реализовать многомерное ветвление по линейным комбинациям порядковых предикторов; содержит ряд новых средств для повышения надежности и эффективности индуцируемых деревьев классификации.

Пусть в некотором узле дерева сконцентрировано некоторое множество примеров Х*, Х*Ì Х. Тогда существуют три возможные ситуации.

1. Множество Х* содержит один или более примеров, относящихся к одному классу y_k. Тогда дерево решений для Х* – это "лист", определяющий класс y_k .
2. ·Множество Х* не содержит ни одного примера, т.е. представляет пустое множество. Тогда это снова "лист", и класс, ассоциированный с "листом", выбирается из другого множества, отличного от Х* (скажем, из множества, ассоциированного с родителем).
3. Множество Х* содержит примеры, относящиеся к разным классам. В этом случае следует разбить множество Х* на некоторые подмножества. Для этого выбирается один из признаков j, имеющий два и более отличных друг от друга значений и Х* разбивается на новые подмножества, где каждое подмножество содержит все примеры, имеющие определенный диапазон значений выбранного признака. Это процедура будет рекурсивно продолжаться до тех пор, пока любое подмножество Х* не будет состоять из примеров, относящихся к одному и тому же классу.

Описанная процедура построения дерева решений сверху вниз, называемая схемой "разделения и захвата" (divide and conquer), лежит в основе многих современных методов построения деревьев решений. Процесс обучения также называют индуктивным обучением или индукцией деревьев (tree induction).

Для построения дерева c одномерным ветвлением, находясь на каждом внутреннем узле, необходимо найти такое условие проверки, связанное с одной из переменных j, которое бы разбивало множество, ассоциированное с этим узлом на подмножества. Общее правило для выбора опорного признака можно сформулировать следующим образом: “выбранный признак должен разбить множество Х* так, чтобы получаемые в итоге подмножества Х*_k , k = 1, 2, …, p, состояли из объектов, принадлежащих к одному классу, или были максимально приближены к этому, т.е. количество чужеродных объектов из других классов в каждом из этих множеств было как можно меньше”.

где H(Х*) и H(Х*_k ) – энтропия подмножеств, разбитых на классы, рассчитанная по формуле Шеннона.

где c – текущий узел, а p_j – вероятность класса j в узле c.

• использование статистических методов для оценки целесообразности дальнейшего разбиения или так называемой "ранней остановки" (prepruning); в конечном счете, "ранняя остановка" процесса построения привлекательна в плане экономии времени обучения, но здесь уместно сделать одно важное предостережение: этот подход строит менее точные классификационные модели и поэтому ранняя остановка крайне нежелательна – признанные авторитеты в этой области Л. Брейман и Р. Куинлен советуют буквально следующее: “Вместо остановки используйте отсечение”.
• ограничение глубины дерева; можно остановить дальнейшее построение, если разбиение ведет к дереву с глубиной превышающей заданное значение;
• контроль нетривиальности разбиения, т.е. получившиеся в результате узлы должны содержать количество примеров, не менее заданного порога.

Очень часто алгоритмы построения деревьев решений дают сложные деревья, которые имеют много узлов и ветвей. Такие "ветвистые" деревья очень трудно понять, а ценность правила, справедливого скажем для 1-3 объектов, крайне низка и в целях анализа данных практически непригодно. Гораздо предпочтительнее иметь дерево, состоящее из малого количества узлов, не вполне идеально классифицирующее обучающую выборку, но обладающее способностью столь же хорошо прогнозировать результат для тестовой выборки.

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

Сформируем обучающую выборку, состоящую из 117 наблюдений, признаками которой являются значения индексов Вудивисса, Шеннона, Пареле, Балушкиной, а также число видов в пробе, средние значения численности и биомассы, концентрация минерального фосфора и тип водоема (значения от 1 до 5 в зависимости от ширины русла и скорости течения). В качестве целевой переменной будем использовать класс качества вод от 2 до 6.

В частности, двигаясь от корня, мы, вместе с 7 измерениями попадаем в узел B, если индекс Вудивисса больше 6.75, либо, в противном случае, с остальными измерениями поступаем в узел А. Из узла B, используя дополнительное условие по типу водоема, осуществляется переход на два листа C и D. Двигаясь же по основной ветви от узла А мы, в конце концов, приходим к узлу G, где сосредотачиваются все плохо распознаваемые примеры в количестве 63 измерений. Всем этим объектам присваивается класс 4, причем в 44 случаях это было выполнено ошибочно. Таким образом, исполнив свою объясняющую роль интерпретации существенных факторов, "компактное" дерево показало посредственные результаты в прогнозировании (38.4% ошибок).

Дальше

Назад

Начало

Конец

Список