Алгоритм C4.5

C4.5 — это алгоритм, используемый для создания дерева решений , разработанный Россом Куинланом . ^[1] C4.5 — это расширение более раннего алгоритма ID3 Куинлана . Деревья решений, сгенерированные C4.5, можно использовать для классификации, и по этой причине C4.5 часто называют статистическим классификатором . В 2011 году авторы программного обеспечения для машинного обучения Weka описали алгоритм C4.5 как «знаковую программу дерева решений, которая, вероятно, является рабочей лошадкой машинного обучения, наиболее широко используемой на практике на сегодняшний день». ^[2]

Он стал довольно популярным после того, как занял первое место в «10 лучших алгоритмов интеллектуального анализа данных» выдающейся статье , опубликованной Springer LNCS в 2008 году. ^[3]

Алгоритм

C4.5 строит деревья решений из набора обучающих данных так же, как ID3 , используя концепцию информационной энтропии . Данные обучения представляют собой набор $S={s_{1},s_{2},...}$ уже засекреченных образцов. Каждый образец $s_{i}$ состоит из p-мерного вектора $(x_{1,i},x_{2,i},...,x_{p,i})$ , где $x_{j}$ представляют значения атрибутов или особенности выборки, а также класс, в котором $s_{i}$ падает.

В каждом узле дерева C4.5 выбирает атрибут данных, который наиболее эффективно разбивает набор выборок на подмножества, обогащенные тем или иным классом. Критерием расщепления является нормированный прирост информации (разница энтропии). Для принятия решения выбирается атрибут с наибольшим нормализованным приростом информации. Затем алгоритм C4.5 рекурсивно обрабатывает секционированные подсписки.

Этот алгоритм имеет несколько базовых случаев .

Все образцы в списке принадлежат одному классу. Когда это происходит, он просто создает листовой узел для дерева решений, говорящий о выборе этого класса.
Ни одна из функций не дает никакой информации. В этом случае C4.5 создает узел принятия решения выше по дереву, используя ожидаемое значение класса.
Обнаружен экземпляр ранее невиданного класса. Опять же, C4.5 создает узел принятия решения выше по дереву, используя ожидаемое значение.

Псевдокод

В псевдокоде общий алгоритм построения деревьев решений такой: ^[4]

Проверьте приведенные выше базовые случаи.
Для каждого атрибута a найдите нормализованный коэффициент получения информации от разделения на a .
Пусть a_best будет атрибутом с наибольшим нормализованным приростом информации.
Создайте узел принятия решения , который разделяется на a_best .
Повторно обработайте подсписки, полученные путем разделения на a_best , и добавьте эти узлы как дочерние элементы node .

Реализации

J48 — это с открытым исходным кодом Java- реализация алгоритма C4.5 Weka в инструменте интеллектуального анализа данных .

Улучшения алгоритма ID3

В версии 4.5 в ID3 внесен ряд улучшений. Некоторые из них:

Обработка как непрерывных, так и дискретных атрибутов. Для обработки непрерывных атрибутов C4.5 создает порог, а затем разбивает список на те, чье значение атрибута превышает пороговое значение, и те, которые меньше или равны ему. ^[5]
Обработка обучающих данных с отсутствующими значениями атрибутов. C4.5 позволяет помечать значения атрибутов как ? за пропажу. Отсутствующие значения атрибутов просто не используются в расчетах выигрыша и энтропии.
Обработка атрибутов с разными затратами.
Обрезка деревьев после создания. C4.5 снова проходит по дереву после его создания и пытается удалить ветки, которые не помогают, заменяя их листовыми узлами.

Улучшения в алгоритме C5.0/See5

Куинлан продолжил создание C5.0 и See5 (C5.0 для Unix/Linux, See5 для Windows), которые он продает на коммерческой основе. C5.0 предлагает ряд улучшений по сравнению с C4.5. Некоторые из них: ^[6]^[7]

Скорость — C5.0 значительно быстрее, чем C4.5 (на несколько порядков)
Использование памяти. C5.0 более эффективен, чем C4.5.
Меньшие деревья решений. C5.0 дает результаты, аналогичные C4.5, но со значительно меньшими деревьями решений.
Поддержка повышения . Повышение улучшает деревья и придает им большую точность.
Взвешивание — C5.0 позволяет взвешивать различные случаи и типы ошибочной классификации.
Отсеивание — опция C5.0 автоматически отсеивает атрибуты, удаляя те, которые могут оказаться бесполезными.

Исходный код однопоточной версии C5.0 для Linux доступен по лицензии GNU General Public License (GPL).

См. также

Ссылки

^ Куинлан, младший C4.5: Программы для машинного обучения . Издательство Морган Кауфманн, 1993.
^ Ян Х. Виттен; Эйбе Франк; Марк А. Холл (2011). «Интеллектуальный анализ данных: практические инструменты и методы машинного обучения, 3-е издание» . Морган Кауфманн, Сан-Франциско. п. 191.
^ Umd.edu - 10 лучших алгоритмов интеллектуального анализа данных
^ С.Б. Коциантис, «Машинное обучение с учителем: обзор методов классификации», Informatica 31 (2007) 249-268, 2007 г.
^ Дж. Р. Куинлан. Улучшено использование непрерывных атрибутов в c4.5. Журнал исследований искусственного интеллекта, 4:77-90, 1996.
^ See5/C5.0 лучше, чем C4.5?
^ М. Кун и К. Джонсон, Прикладное прогнозное моделирование, Springer, 2013 г.

Внешние ссылки

Оригинальная реализация на домашней странице Росса Куинлана: http://www.rulequest.com/Personal/
См. 5 и C5.0.

[1] Куинлан, младший C4.5: Программы для машинного обучения . Издательство Морган Кауфманн, 1993.

[2] Ян Х. Виттен; Эйбе Франк; Марк А. Холл (2011). «Интеллектуальный анализ данных: практические инструменты и методы машинного обучения, 3-е издание» . Морган Кауфманн, Сан-Франциско. п. 191.

[3] Umd.edu - 10 лучших алгоритмов интеллектуального анализа данных

[4] С.Б. Коциантис, «Машинное обучение с учителем: обзор методов классификации», Informatica 31 (2007) 249-268, 2007 г.

[5] Дж. Р. Куинлан. Улучшено использование непрерывных атрибутов в c4.5. Журнал исследований искусственного интеллекта, 4:77-90, 1996.

[6] See5/C5.0 лучше, чем C4.5?

[7] М. Кун и К. Джонсон, Прикладное прогнозное моделирование, Springer, 2013 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]