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

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

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

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

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

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

Пример 1) Количество снимавшихся в фильме звёзд как первый из признаков, по которому производится разбиение данных

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

Пример

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

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

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

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

Энтропия как мера чистоты групп Энтропия как мера чистоты групп Если у системы всего 2 возможных состояния, то её энтропия – функция одной переменной p , график которой имеет вид:

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

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

задача классификации. Дискриминантный анализ

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

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

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

Дискриминация Коэффициенты  βi первой канонической дискриминантной функции d выбираются таким образом, чтобы центроиды различных групп как можно больше отличались друг от друга. Коэффициенты второй группы выбираются также, но при этом налагается дополнительное условие, чтобы значения второй функции были некоррелированы со значениями первой. Аналогично определяются и другие функции. Отсюда следует, что любая каноническая дискриминантная функция  имеет нулевую внутригрупповую корреляцию с d1, d2, …, dg-1