Сравнение классификационных возможностей алгоритмов С4.5 и С5.0

Существуют различные подходы к анализу данных [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 атрибутов (целевой атрибут – «форма обучения»).

Описание эксперимента

Эксперимент состоял из трех частей: построение дерева решений для файла «Ирисы Фишера» средствами Deductor и See5, построение дерева решений для файла «Голосование депутатов» средствами Deductor и See5, построение дерева решений для файла «Абитуриенты» средствами Deductor и See5. Для всех трех случаев были выбраны следующие настройки обработчиков: уровень доверия, используемый при отсечении узлов дерева, – 20%, минимальное количество примеров в узле, при котором будет создан новый, – 2. Результаты эксперимента приведены на рис. 1-6 и в таблице 1.

Выводы

Как видно из представленных результатов, во всех трех случаях алгоритм C5.0 построил более компактные деревья, содержащие, как следствие, и меньшее количество правил (см. таблицу 1). Однако точность классификации у алгоритма C4.5 (см. таблицы сопряженности) оказалась несколько выше. Скорость генерации результатов

Decision tree:

Dlina lepestka <= 1.9: Iria-setosa (50)

Dlina lepestka >1.9:                                    (a)   (b)   (c) <-classified as

:...Shirina lepestka > 1.7: Iris-virginica (46/1)    ---- ---- ----

Shirina lepestka <=1.7:                             50                (a): class Iris-setosa

:.. .Dlina lepestka <= 4.9: Iris-versicolor (48/1)        47     3    (b) : class Iris-versicolor

Dlina lepestka > 4.9: Iris-virginica (6/2)            1    49    (c): class Iris-virginica

Рис. 1. Дерево решений и таблица сопряжённости для «Ирисов Фишера» (See5)

к |^^и| Длина лепестка < 2,45                      Iris-setosa

В |^™| Длина лепестка >= 2,45

Э- |^^е| Ширина лепестка < 1,75			Классифицировано
—[^^Й] Длина лепестка < 4,95	I ris-versicolor	Фактически	Iris-setosa	I ris-versicolor	Iris-virginica	Итого
В- |^^и| Длина лепестка >= 4,95		Iris-setosa	I                         50			50
г ■l^^g] Ширина лепестка < 1.55	Iris-virginica	I ris-versicolor		491	_____________________1_	50
^™ Ширина лепестка >= 1 „55	I ris-versicolor	Iris-virginica		2	48	50
;- |^^е| Ширина лепестка >=1,75	I ris-virginica	Итого	50	51	49	150

Рис. 2. Дерево решений и таблица сопряженности для «Ирисов Фишера» (Deductor)

Decision tree:

Zakon о vrachah in {no,vozderzhalsja}: demokrat (241/5)

Proekt po usynovleniju = yes: demokrat (6/2)                     143    8    (a): class respublikanez

Proekt po usynovleniju = no: respublikanez (17/2)                 5   244    (b): class demokrat

Рис. 3. Дерево решений и таблица сопряженности для «Голосования депутатов» (See5)

D^ Условие

| ^> Следствие

Zakon о vrachah = no

|^^и| Zakon о vrachah = vozderzhalsja

demokrat demokrat

j • |^^■| Proekt po altern istoch topi = no

2 [^^h] Proekt po altern istoch topi = vozderzhalsja В I^^Hl Proekt po altern istoch topi = yes

respublikanez respublikanez

|^^и| Proekt po usynovleniju = no

respublikanez

H | Proekt po usynovleniju = vozderzh... respublikanez B-|^^e| Proekt po usynovleniju =yes k"|^^e| Proekt po vodnym resursam =... respublikanez i "I I Proekt po vodnym resursam = ... demokrat |^^e| Proekt po vodnym resursam = ... demokrat

I | Proekt po raketam = vozderzhalsja respublikanez |^™ Proekt po raketam = yes             demokrat

Ф актически	demokrat	respublikanez	Итого
demokrat	244	_________________5_	249
respublikanez	6	145	151
Итого	250	150	400

Рис. 4. Дерево решений и таблица сопряженности для «Голосования депутатов» (Deductor)

у обоих алгоритмов примерно одинаковая и составляет менее 1 сек.

Таким образом, можно сделать вывод, что, как и заявлял Д. Куинлан, алгоритм C5.0 действительно строит более компактные деревья решений, чем его предшественник, а также обладает высокой скоростью построения классификационных моделей. Тем не менее достоверность результатов работы алгоритма C4.5 выше, чем у C5.0. В то же время нельзя исключать, что вышеуказанные ре-

Decision tree:

Рис. 5. Дерево решений и таблица сопряженности для «Абитуриентов» (See5)

Рис. 6. Дерево решений и таблица сопряженности для «Абитуриентов» (Deductor)

Dokum < = 1: 1 (303/6)

Dokum > 1:

Tip <= 4:

:...ForfinForfin <= 1: 1 (33/6) ForfinForfin > 1: 2 (48/2)

(а)	(Ь)	(с)	^-classified аз
324	2		(а):	class	1
12	46	1	(Ь):	class	2
		15	(с):	class	3

Таблица 1. Количество правил

Алгоритм/Набор данных Ирисы Голосование Абитуриенты С4.5 5 11 5 С5.0 4 5 4 зультаты объясняются тем, что в их распоряжении имелась демонстрационная версия системы See5, которая может обрабатывать файлы, содержащие не более 400 записей.