Comparison of classification algorithms C4.5 and C5.0


Cite item

Full Text

Abstract

This work compares features of tree decision algorithms C4.5 and C5.0, which are the most effective data mining classification tool. We considered two software tools: analytics platform Deductor and system See5. Three data sets were tested to improve comparative analysis accuracy. First is conventional Fisher’s iris data set, second contains information about US Congress deputy votes (distribution Deductor), and third includes information about applicants of the one of Russian Federation universities. According to test results, C5.0 builds more compact decision trees, but its operation speed is almost the same to C4.5 under reducing of classification model validity. However, we do not preclude that these results can be explained by using of See5 system demo version that provides only files processing with no more 400 entries.

Full Text

Введение Существуют различные подходы к анализу данных [1]. Одним из самых известных является технология интеллектуального анализа данных (Data Mining, далее DM) - процесс обнаружения в необработанных данных ранее неизвестных нетривиальных знаний, необходимых для принятия решений в различных сферах человеческой деятельности [2]. Технология DM располагает большим числом инструментов (алгоритмов) для проведения различных видов анализа [3]. Одним из наиболее популярных классификационных алгоритмов являются деревья решений. Деревья решений - это способ представления правил в иерархической, последовательной структуре, где каждому объекту соответствует единственный узел, дающий решение [4]. Виды алгоритмов деревьев решений Наиболее эффективным алгоритмом деревьев решений считается C4.5 - усовершенствованная версия алгоритма ID3 [5], разработанная Д. Куинланом, позволяющая строить дерево решений с неограниченным числом ветвей у узла [6]. Однако некоторое время назад появилась новая модификация - C5.0. Как утверждает автор (все тот же Д. Куинлан), она превосходит предыдущую версию: работает быстрее, строит деревья решений меньшей размерности, использование памяти компьютера является более эффективным, имеет более высокую точность результатов, позволяет автоматически удалять незначащие атрибуты [7]. Для проверки данного утверждения нами были выбраны два программных продукта, в которых реализованы алгоритмы C4.5 и С5.0. Программные продукты Алгоритм С4.5. реализован в системе Deductor. Аналитическая платформа Deductor - основа для создания законченных прикладных решений. Реализованные в Deductor технологии позволяют на базе единой архитектуры пройти все этапы построения аналитической системы: от создания хранилища данных до автоматического подбора моделей и визуализации полученных результатов [8-9]. Алгоритм С5.0 реализован в системе See5 [10]. See5 - инструмент анализа данных для прогнозирования диагностического класса какого-либо объекта по значениям его признаков. Содержит единственный обработчик - дерево решений. Причина выбора именно этих программных систем заключается в наличии бесплатных демонстрационных версий, доступных для свободного скачивания с сайтов компании-разработчиков. Данные Для проведения сравнительного анализа было выбрано три набора данных: файл «ирисы Фишера» [11]; файл, содержащий информацию о результатах голосования депутатов Конгресса США (входит в дистрибутив аналитической платформы Deductor); файл, содержащий реальную информацию об абитуриентах одного из вузов РФ. Структура файлов: - ирисы Фишера - 150 записей, 5 атрибутов (целевой атрибут - «класс»); - голосование депутатов - 400 записей, 17 атрибутов (целевой атрибут - «партийная принадлежность»); - абитуриенты - 400 записей, 20 атрибутов (целевой атрибут - «форма обучения»). Риc. 1. Дерево решений и таблица сопряжённости для ирисов Фишера (See5) Риc. 2. Дерево решений и таблица сопряженности для ирисов Фишера (Deductor) Риc. 3. Дерево решений и таблица сопряженности для «Голосование депутатов» (See5) Риc. 4. Дерево решений и таблица сопряженности для «Голосование депутатов» (Deductor) Описание эксперимента Эксперимент состоял из трех частей: построение дерева решений для файла «Ирисы Фишера» средствами Deductor и See5, построение дерева решений для файла «Голосование депутатов» средствами Deductor и See5, построение дерева решений для файла «Абитуриенты» средствами Deductor и See5. Для всех трех случаев были выбраны следующие настройки обработчиков: уровень доверия, используемый при отсечении узлов дерева - 20%, минимальное количество примеров в узле, при котором будет создан новый - 2. Результаты эксперимента приведены на рис. 1-6 и в таблице 1. Выводы Как видно из представленных результатов, во всех трех случаях алгоритм C5.0 построил более компактные деревья, содержащие, как следствие, и меньшее количество правил (см. таблицу 1). Однако точность классификации у алгоритма C4.5 (см. таблицы сопряженности) оказалась несколько выше. Скорость генерации результатов у обоих алгоритмов примерно одинаковая и составляет менее 1 сек. Таким образом, можно сделать вывод, что, как и заявлял Д. Куинлан, алгоритм C5.0 действительно строит более компактные деревья решений, чем его предшественник, а также обладает высокой скоростью построения классификационных моделей. Тем не менее, достоверность результатов работы алгоритма C4.5 выше, чем у C5.0. В то же время нельзя исключать, что вышеуказанные результаты объясняются тем, что в их распоряжении имелась демонстрационная версия системы See5, которая может обрабатывать файлы, содержащие не более 400 записей. Риc. 5. Дерево решений и таблица сопряженности для «Абитуриенты» (See5) Риc. 6. Дерево решений и таблица сопряженности для «Абитуриенты» (Deductor) Таблица 1. Количество правил Алгоритм/Набор данных Ирисы Голосование Абитуриенты C4.5 5 11 5 C5.0 4 5 4
×

About the authors

Sergey Vadimovich Palmov

Povolzhskiy State University of Telecommunications and Informatics

Email: psv@psuti.ru

Alfiya Ashatovna Miftakhova

Povolzhskiy State University of Telecommunications and Informatics

Email: miftaxovaa@mail.ru

References

  1. Большие данные (Big Data) // URL: http:// www.tadviser.ru/index.php (д.о. 10.10.2015).
  2. Data Mining - интеллектуальный анализ данных // URL: http://www.inftech. webservis.ru/it /database/datamining/ar2.html (д.о. 10.10.2015).
  3. Топ-10 data mining-алгоритмов простым языком // URL: http://habrahabr.ru/company /itinvest/blog/262155/ (д.о. 11.10.2015).
  4. Деревья решений - общие принципы работы // URL: http://www.gotai.net/documents/doc-msc-006.aspx (д.о. 12.10.2015).
  5. The ID3 Algorithm // URL: http://www.cise. ufl.edu/~ddd/cap6635/Fall-97/Short-papers/2. htm (д.о. 12.10.2015).
  6. Сидоров А.В. Алгоритмы создания дерева принятия решений // URL: http://econf.rae. ru/pdf/2014/03/3245.pdf (д.о. 13.10.2015).
  7. Is See5/C5.0 Better Than C4.5? // URL: http://rulequest.com/see5-comparison.html. (д.о. 15.10.2015).
  8. Deductor - описание аналитической платформы // URL: http://bitconsulting. ru/product/olap/ (д.о. 17.10.2015).
  9. Studio // URL: http://basegroup.ru/deductor/ components/studio (д.о. 17.10.2015).
  10. Data Mining Tools See5 and C5.0 // URL: http://rulequest.com/see5-info.html (д.о. 17.10.2015).
  11. Iris Data Set // URL: http://archive. ics.uci.edu/ml/datasets/Iris (д.о. 19.10.2015).

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2015 Palmov S.V., Miftakhova A.A.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies