Меню Главная Случайная статья Настройки C4.5 Материал из https://ru.wikipedia.org C4.5 — алгоритм для построения деревьев решений, разработанный Джоном Квинланом (англ. John Ross Quinlan). C4.5 является усовершенствованной версией алгоритма ID3 того же автора. В частности, в новую версию были добавлены отсечение ветвей (англ. pruning), возможность работы с числовыми атрибутами, а также возможность построения дерева из неполной обучающей выборки, в которой отсутствуют значения некоторых атрибутов. Содержание 1 Требования к данным 2 Построение дерева 3 Реализации 4 Примечания 5 Литература 6 Ссылки Требования к данным Для того, чтобы с помощью C4.5 построить решающее дерево и применять его, данные должны удовлетворять нескольким условиям. Информация об объектах, которые необходимо классифицировать, должна быть представлена в виде конечного набора признаков (атрибутов), каждый из которых имеет дискретное или числовое значение. Такой набор атрибутов назовём примером. Для всех примеров количество атрибутов и их состав должны быть постоянными. Множество классов, на которые будут разбиваться примеры, должно иметь конечное число элементов, а каждый пример должен однозначно относиться к конкретному классу. Для случаев с нечёткой логикой, когда примеры принадлежат к классу с некоторой вероятностью, C4.5 неприменим. В обучающей выборке количество примеров должно быть значительно больше количества классов, к тому же каждый пример должен быть заранее ассоциирован со своим классом. По этой причине C4.5 является вариантом машинного обучения с учителем. Построение дерева Пусть имеется ${\displaystyle T}$ — обучающая выборка примеров, а ${\displaystyle C}$ — множество классов, состоящее из ${\displaystyle k}$ элементов. Для каждого примера из ${\displaystyle T}$ известна его принадлежность к какому-либо из классов ${\displaystyle C_{1}\ldots C_{k}}$. Построение дерева решений алгоритмом C4.5 принципиально не отличается от его построения в ID3. На первом шаге имеется корень и ассоциированное с ним множество ${\displaystyle T}$, которое необходимо разбить на подмножества. Для этого необходимо выбрать один из атрибутов в качестве проверки. Выбранный атрибут ${\displaystyle A}$ имеет ${\displaystyle n}$ значений, что даёт разбиение на ${\displaystyle n}$ подмножеств. Далее создаются ${\displaystyle n}$ потомков корня, каждому из которых поставлено в соответствие своё подмножество, полученное при разбиении ${\displaystyle T}$. Процедура выбора атрибута и разбиения по нему рекурсивно применяется ко всем ${\displaystyle n}$ потомкам и останавливается в двух случаях: после очередного ветвления в вершине оказываются примеры из одного класса (тогда она становится листом, а класс, которому принадлежат её примеры, будет решением листа), вершина оказалась ассоциированной с пустым множеством (тогда она становится листом, а в качестве решения выбирается наиболее часто встречающийся класс у непосредственного предка этой вершины). Реализации J48 — реализация на языке Java, входит в пакет Weka[1]. C5.0 (для Linux) / See5 (для Windows) — реализация Квинлана на языке C. Примечания Weka.Classifiers.Trees: J48 (англ.). Документация на Sourceforge. Дата обращения: 18 февраля 2012. Архивировано 12 сентября 2012 года. Литература Паклин Н.Б., Орешков В.И. Глава 9. // Бизнес-аналитика: от данных к знаниям(+CD): Учебное пособие. 2-е изд.. — СПб.: Питер, 2013. — С. 444-459. — ISBN 978-5-459-00717-6. Quinlan J. R. Learning With Continuous Classes (англ.) // Proceedings of the 5th Australian Joint Conference on Articial Intelligence. — 1992. — P. 343—348. — ISBN 978-9810-2125-06. Quinlan J. R. Improved Use of Continuous Attributes in C4.5 (англ.) // Journal of Artificial Intelligence Research. — 1996. — Vol. 4. — P. 77—90. — ISSN 1076-9757. — doi:10.1613/jair.279. Архивировано 21 октября 2011 года. Ссылки Data Mining Tools See5 and C5.0 (англ.). RuleQuest Research. Дата обращения: 16 февраля 2012. Архивировано 25 мая 2012 года.