Задача классификации. Метод деревьев решений

состоит в том, чтобы осуществлять процесс деления исходных данные на группы, пока не будут получены однородные (или почти однородные) их множества. Совокупность правил, которые дают такое разбиение (partition), позволят затем делать прогноз (определять наиболее вероятный номер класса) для новых данных.
Примеры практических задач классификации:
• скоринговые модели кредитования;
• маркетинговые исследования, направленные на выявление предпочтений клиента или степени его удовлетворённости;
• диагностика (медицинская или техническая).

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

принятия решений.
Графически её можно представить в виде древовидной структуры, где моменты принятия решений соответствуют так называемым узлам (decision nodes).
В узлах происходит ветвление процесса (branching), т.е. деление его на так называемые ветви (branches) в зависимости от сделанного выбора.
Конечные (или, терминальные) узлы называют листьями (leafs, leaf nodes), каждый лист – это конечный результат последовательного принятия решений.
Данные, подлежащие классификации, находятся в так называемом «корне» дерева (root).
В зависимости от решения, принимаемого в узлах, процесс в конце концов останавливается в одном из листьев, где переменной отклика (искомому номеру класса) присваивается то или иное значение.

Основные понятия

partitioning).
Эта стратегия также называется «Разделяй и властвуй» («Divide and conquer»).
В узлах, начиная с корневого, выбирается признак, значение которого используется для разбиения всех данных на 2 класса.
Процесс продолжается до тех пор, пока не выполнится критерий остановки:
Все (или почти все) данные данного узла принадлежат одному и тому же классу;
Не осталось признаков, по которым можно построить новое разбиение;
Дерево превысило заранее заданный «лимит роста» (если таковой был заранее установлен).

Идея метода

трём ящикам:
Популярные («mainstream hits»);
Не популярные у зрителей, но получившие высокую оценку критиков;
Не имеющие успеха.
Не прочитывая каждый сценарий нужно разработать алгоритм классификации сценариев по трем классам.

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

которому производится разбиение данных

Пример

2) Рассмотрим группу сценариев с большим числом задействованных звёзд.
Разобьём её на 2 подгруппы по признаку «размер бюджета»

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

«мелкое» разделение (может оказаться, что каждая группа будет содержать лишь по одному элементу), однако понятно, что смысла в такой классификации нет.
Ограничим ветвление дерева – например, остановим процесс, когда каждая группа хотя бы на 80% будет состоять из элементов одного и того же класса.
Заметим, что в данном случае мы говорим лишь о разбиениях данных (точек в Евклидовом пространстве) прямыми (в общем случае – гиперплоскостями), параллельными осям координат.

Пример

Метод деревьев решений не позволяет строить такие разбиения, поскольку для разделения данных используются условия вида:
{x < a}, {x > a},
где x – значение фактора, a – некоторое фиксированное число.
«axis-parallel splits», т.е. «разбиения, параллельные осям».

(количество занятых звёзд и бюджет) - дерево получилось небольшим.

построения деревьев решений: CART, C4.5, CHAID, CN2, NewId, ITrule и другие.
Алгоритм CART (Classification and Regression Tree) очевидно решает задачи классификации и регрессии.
Разработан в 1974-1984 годах четырьмя профессорами статистики - Leo Breiman (Berkeley), Jerry Friedman (Stanford), Charles Stone (Berkeley) и Richard Olshen (Stanford).
Атрибуты набора данных могут иметь как дискретное, так и числовое значение.
Алгоритм CART предназначен для построения бинарного дерева решений.
Другие особенности алгоритма CART:
функция оценки качества разбиения;
механизм отсечения дерева;
алгоритм обработки пропущенных значений;
построение деревьев регрессии.

Gini . Данная оценочная функция основана на идее уменьшения неопределенности в узле:
Допустим, есть узел, и он разбит на два класса. Максимальная неопределенность в узле будет достигнута при разбиении его на два подмножества по 50 примеров, а максимальная определенность - при разбиении на 100 и 0 примеров.
Правила разбиения. В каждом узле разбиение может идти только по одному атрибуту. Если атрибут является числовым, то во внутреннем узле формируется правило вида xi <= c.
Значение c в большинстве случаев - среднее арифметическое двух соседних упорядоченных значений переменной xi обучающего набора данных.
Если же атрибут относится к категориальному типу, то во внутреннем узле формируется правило xi V(xi), где V(xi) - некоторое непустое подмножество множества значений переменной xi в обучающем наборе данных.

Алгоритм CART

где T - текущий узел, pj - вероятность класса j в узле T, n - количество классов.

деревьев решений.
В рассматриваемом алгоритме отсечение - это компромисс между получением дерева "подходящего размера" и получением наиболее точной оценки классификации.
Метод заключается в получении последовательности уменьшающихся деревьев, но деревья рассматриваются не все, а только "лучшие представители".
Перекрестная проверка (V-fold cross-validation) является наиболее сложной и одновременно оригинальной частью алгоритма CART - путь выбора окончательного дерева, при условии, что набор данных имеет небольшой объем или же записи набора данных настолько специфические, что разделить набор на обучающую и тестовую выборку не представляется возможным.

Алгоритм CART

алгоритм может работать только с дискретным зависимым атрибутом и поэтому может решать только задачи классификации.
C4.5 считается одним из самых известных и широко используемых алгоритмов построения деревьев классификации.
Для работы алгоритма C4.5 необходимо соблюдение следующих требований:
Каждая запись набора данных должна быть ассоциирована с одним из предопределенных классов, т.е. один из атрибутов набора данных должен являться меткой класса.
Классы должны быть дискретными. Каждый пример должен однозначно относиться к одному из классов.
Количество классов должно быть значительно меньше количества записей в исследуемом наборе данных.
Версия алгоритма - алгоритм C4.8 - реализована в инструменте Weka как J4.8 (Java). Коммерческая реализация метода: C5.0, разработчик RuleQuest, Австралия.
Алгоритм C4.5 медленно работает на сверхбольших и зашумленных наборах данных.

разработан Джоном Квинланом (John Ross Quinlan).
C4.5 является усовершенствованной версией алгоритма ID3 того же автора.

стандарт процедуры построения деревьев решений.
Эта программа реализуется на коммерческой основе (http://www.rulequest.com/ ), но версия, встроенная в пакет R (и некоторые другие пакеты) доступны бесплатно.
Выбор признака, по которому будет осуществляться разбиение: ищем такой признак (для построения разбиения по нему), который позволил бы получить как можно более чистые группы.
Для измерения степени чистоты группы существует несколько способов. Алгоритм C5.0 использует в качестве меры чистоты группы понятие энтропии:

- для системы, допускающей с возможных состояний.

Группы, полностью состоящие из элементов одного класса называют «чистыми» («pure»).

Здесь ?? – вероятность нахождения системы в состоянии i.

то её энтропия – функция одной переменной p , график которой имеет вид:

Энтропия максимальна, когда p=0,5. Нетрудно доказать аналитически, что для любого числа состояний максимум энтропии достигается в том случае, когда все они равновероятны.
Нулевая энтропия означает отсутствие неопределённости (применительно к деревьям решений это означает, что группа является полностью однородной, т.е. чистой).
Единичная энтропия означает полную неопределённость (в нашем случае – неопределённость относительно состава группы).

группу (т.е. группу, имеющую наименьшую энтропию). Эти вычисления называются «information gain» (буквально «усиление информации»).
Этот признак определяется методом перебора. Для каждого признака F («feature» – признак, свойство, характеристика) значение information gain вычисляется как разность энтропий группы до разбиения и после него:

Алгоритм (С5.0) автоматизированного построения дерева решений

Чем больше значение information gain для выбранного признака F, тем лучше этот признак F подходит для того, чтобы провести по нему разбиение.
Если для выбранного признака F значение information gain = 0, это означает, что разбиение по этому признаку бесперспективно, т.к. оно не приведёт к снижению энтропии.
С другой стороны, максимально возможное значение величины information gain = величине энтропии до разбиения (энтропия после разбиения будет = 0, т.е. полученные в результате разбиения группы будут полностью однородными - чистыми).

Здесь Entropy(S2) – суммарная энтропия групп, полученных в результате разбиения.

будет слишком много – в этом случае говорят, что модель «is overfitted», т.е. переопределена.
Пользоваться такими деревьями решений на практике бывает неудобно. Чтобы избежать этого, осуществляют так называемую «обрезку» (pruning) дерева решений. Результат «обрезки» - уменьшение размера дерева решений.

«Обрезка» дерева решений

«Pre-pruning» - «предварительная обрезка»: состоит в том, чтобы заранее условиться о том, что процесс ветвления будет остановлен по достижении заданного числа решений. Как любой метод без обратной связи, он чреват тем, что будут пропущены важные, но трудно обнаруживаемые данные.

«Post-pruning» - «последующая обрезка»: сначала строится всё дерево решений, а потом по определённым правилам производится его «обрезка», т.е. отсечение лишних ветвей. Этот подход считается более надёжным - он гарантирует, что никакая важная информация не будет потеряна.

Иногда вместо того, чтобы «отсекать» ветви, их переносят выше по дереву или же заменяют более простыми - «subtree raising» («подъём поддерева») и «subtree replacement» («замена поддерева»).

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

статистическим процедурам.
Эти процедуры можно разделить на методы интерпретации межгрупповых различий – дискриминации и методы классификации наблюдений по группам.
Задачи дискриминантного анализа
Задачи первого типа – задачи дискриминации (пример – в медицинской практике).

Дискриминантный анализ

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

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

эти переменные будем называть дискриминантными переменными), которая бы оптимально разделила рассматриваемые группы. Линейная функция
называется канонической дискриминантной функцией с неизвестными коэффициентами βi  

значение дискриминантной функции для m-го объекта в группе k

значение дискриминантной переменной

для m-го объекта в группе k.

С геометрической точки зрения дискриминантные функции определяют гиперповерхности в p-мерном пространстве.