Алгоритм 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 , используя концепцию информационной энтропии . Обучающие данные представляют собой набор уже классифицированных образцов. Каждый образец состоит из p-мерного вектора , где представляют значения атрибутов или особенности образца, а также класс, в который он попадает. ${\displaystyle S={s_{1},s_{2},...}}$ ${\displaystyle s_{i}}$ ${\displaystyle (x_{1,i},x_{2,i},...,x_{p,i})}$ ${\displaystyle x_{j}}$ ${\displaystyle s_{i}}$

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

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

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

Псевдокод

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

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

Реализации

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

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

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 автоматически отсеивает атрибуты, удаляя те, которые могут оказаться бесполезными.

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

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

• Алгоритм ID3
• Изменение C4.5 для создания временных и причинных правил

Ссылки

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

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

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