СРАВНЕНИЕ КЛАССИФИКАЦИОННЫХ ВОЗМОЖНОСТЕЙ АЛГОРИТМОВ С4.5 И С5.0


Цитировать

Полный текст

Аннотация

В статье проводится сравнение возможностей алгоритмов деревьев решений C4.5 и C5.0 - одних из наиболее эффективных инструментов классификации интеллектуального анализа данных. Для этого были выбраны две их программные реализации - отечественная аналитическая платформа Deductor и система See5. Чтобы повысить качество сравнительного анализа, использовались три разных набора данных. Как показали результаты эксперимента, утверждения автора-разработчика обоих алгоритмов Куинлана о том, что новая версия алгоритма во всём превосходит старую, оказались несколько излишне оптимистичными. C5.0, действительно, строит, как и заявлено, более компактные деревья решений, но скорость его работы осталась сопоставимой с C4.5, а достоверность получаемой классификационной модели снизилась. Однако, авторы статьи не исключают, что вышеуказанные результаты объясняются, тем, что в их распоряжении имелась демонстрационная версия системы See5, которая может обрабатывать файлы, содержащие не более 400 записей.

Ключевые слова

Полный текст

Введение Существуют различные подходы к анализу данных [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
×

Об авторах

Сергей Вадимович Пальмов

Поволжский государственный университет телекоммуникаций и информатики

Email: psv@psuti.ru

Альфия Асхатовна Мифтахова

Поволжский государственный университет телекоммуникаций и информатики

Email: miftaxovaa@mail.ru

Список литературы

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

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Пальмов С.В., Мифтахова А.А., 2015

Creative Commons License
Эта статья доступна по лицензии Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.