Алгоритм C4.5 - Википедия - C4.5 algorithm

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

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

Алгоритм

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

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

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

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

Псевдокод

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

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

Реализации

J48 является Открытый исходный код Ява реализация алгоритма C4.5 в Weka сбор данных инструмент.

Улучшения алгоритма ID.3

C4.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 доступен под лицензией GPL.

Смотрите также

Рекомендации

  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 г.

внешняя ссылка