Просмотр кода страницы C4.5

'''C4.5''' — [[алгоритм]] для построения [[Дерево принятия решений|деревьев решений]], разработанный Джоном Квинланом ({{lang-en|[[:en:Ross Quinlan|John Ross Quinlan]]}}). C4.5 является усовершенствованной версией [[ID3 (алгоритм)|алгоритма ID3]] того же автора. В частности, в новую версию были добавлены отсечение ветвей ({{lang-en|[[:en:Pruning (decision trees)|pruning]]}}), возможность работы с числовыми атрибутами, а также возможность построения дерева из неполной обучающей выборки, в которой отсутствуют значения некоторых атрибутов.

== Требования к данным ==
Для того, чтобы с помощью C4.5 построить решающее дерево и применять его, данные должны удовлетворять нескольким условиям.

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

Множество классов, на которые будут разбиваться примеры, должно иметь конечное число элементов, а каждый пример должен однозначно относиться к конкретному классу. Для случаев с [[Нечёткая логика|нечёткой логикой]], когда примеры принадлежат к классу с некоторой вероятностью, C4.5 неприменим.

В обучающей выборке количество примеров должно быть значительно больше количества классов, к тому же каждый пример должен быть заранее ассоциирован со своим классом. По этой причине C4.5 является вариантом [[Обучение с учителем|машинного обучения с учителем]].

== Построение дерева ==
Пусть имеется <math>T</math> — обучающая [[выборка]] примеров, а <math>C</math> — множество классов, состоящее из <math>k</math> элементов. Для каждого примера из <math>T</math> известна его принадлежность к какому-либо из классов <math>C_1 \ldots C_k</math>.

Построение дерева решений алгоритмом C4.5 принципиально не отличается от его построения в [[ID3 (алгоритм)|ID3]]. На первом шаге имеется корень и ассоциированное с ним множество <math>T</math>, которое необходимо разбить на подмножества. Для этого необходимо выбрать один из атрибутов в качестве проверки. Выбранный атрибут <math>A</math> имеет <math>n</math> значений, что даёт разбиение на <math>n</math> подмножеств. Далее создаются <math>n</math> потомков корня, каждому из которых поставлено в соответствие своё [[подмножество]], полученное при разбиении <math>T</math>. Процедура выбора атрибута и разбиения по нему [[Рекурсия|рекурсивно]] применяется ко всем <math>n</math> потомкам и останавливается в двух случаях:
* после очередного ветвления в вершине оказываются примеры из одного класса (тогда она становится ''листом'', а класс, которому принадлежат её примеры, будет решением листа),
* вершина оказалась ассоциированной с [[Пустое множество|пустым множеством]] (тогда она становится листом, а в качестве решения выбирается наиболее часто встречающийся класс у непосредственного предка этой вершины).

== Реализации ==
* ''J48'' — реализация на языке [[Java]], входит в пакет [[Weka]]<ref>{{cite web
 | url         = http://weka.sourceforge.net/doc/weka/classifiers/trees/J48.html
 | title       = Weka.Classifiers.Trees: J48
 | accessdate  = 2012-02-18
 | lang        = en
 | work        = Документация на [[Sourceforge]]
 | archiveurl  = https://www.webcitation.org/6Ad2xSvBT?url=http://weka.sourceforge.net/doc/weka/classifiers/trees/J48.html
 | archivedate = 2012-09-12
}}</ref>.
* ''C5.0'' (для [[Linux]]) / ''See5'' (для [[Windows]]) — реализация Квинлана на языке [[Си (язык программирования)|C]].

== Примечания ==
{{примечания}}

== Литература ==
* {{книга
|часть          = Глава 9.
|заглавие       = Бизнес-аналитика: от данных к знаниям(+CD): Учебное пособие. 2-е изд.
|автор          = Паклин Н.Б., Орешков В.И.
|ссылка = 
|isbn           = 978-5-459-00717-6
|страницы       = 444-459
|год            = 2013
|место          =  СПб
|издательство   = Питер
}}
* {{статья
 |автор         = Quinlan J. R.
 |заглавие      = Learning With Continuous Classes
 |язык          = en
 |издание       = Proceedings of the 5th Australian Joint Conference on Artiﬁcial Intelligence
 |год           = 1992
 |pages         = 343—348
 |isbn          = 978-9810-2125-06
}}
* {{книга
 |автор         = Quinlan J. R.
 |заглавие      = C4.5: Programs for Machine Learning
 |ссылка       = https://archive.org/details/c45programsforma0000quin
 |место         = [[Сан-Матео|San Mateo]]
 |издательство  = Morgan Kaufmann Publishers Inc.
 |год           = 1993
 |allpages      = 302
 |isbn          = 1-5586-0238-0
}} {{ref-en}}
* {{статья
 |автор       = Quinlan J. R.
 |заглавие = Improved Use of Continuous Attributes in C4.5
 |ссылка     = http://www.jair.org/papers/paper279.html
 |язык         = en
 |издание   = Journal of Artificial Intelligence Research
 |год           = 1996
 |volume           = 4
 |pages            = 77—90
 |issn             = 1076-9757
 |doi              = 10.1613/jair.279
 |archiveurl       = https://web.archive.org/web/20111021033458/http://jair.org/papers/paper279.html
 |archivedate      = 2011-10-21
}}

== Ссылки ==
* {{cite web
 | url         = http://rulequest.com/see5-info.html
 | title       = Data Mining Tools See5 and C5.0
 | publisher   = RuleQuest Research
 | accessdate  = 2012-02-16
 | lang        = en
 | archiveurl  = https://www.webcitation.org/67vUuUZgk?url=http://rulequest.com/see5-info.html
 | archivedate = 2012-05-25
}}

[[Категория:Деревья принятия решений]]