Moluch 114 c indd

Метод определения весов параметров из набора входящих данных с применением возможностей алгоритма C4.5

Удовиченко Олег Игоревич, магистрант;
Сабинин Олег Юрьевич, кандидат технических наук, доцент, научный руководитель
Санкт-Петербургский политехнический университет Петра Великого
Ключевые слова: классификация, деревья принятия решений, отсутствующие значения, веса параме- тров, C4.5.

Д
еревья принятия решений применяются во многих сферах деятельности. Одним из главных направ- лений их использования является решение задач клас- сификации [1]. C4.5 — алгоритм построения деревьев решений, разработанный Джоном Квинланом [2]. C4.5 является усовершенствованной версией алгоритма ID3, который также был разработан Квинланом [3]. В версию C4.5 были добавлены возможность отсечения ветвей де- ревьев, возможность работы с числовыми атрибутами, а также возможность построения дерева на основе вы- борки с отсутствующими значениями атрибутов [4]. Ос- новная причина, по которой C4.5 применен в данном
отсутствующих значений и в обучающих, и в тестовых вы- борках данных.
В данной работе рассматривается случай, когда все значения выходных параметров, в обучающей и в тестовой выборках данных для прогнозирования, являются дис- кретными величинами, а не непрерывными. Значения ат- рибутов на входе при этом могут быть как дискретными, так и непрерывными.
В классическом случае применения дерева принятия ре- шений для прогнозирования, в тестовой выборке отсутствую- щими значениями являются значения классов — выходных параметров [7]. Назовем такой параметр c_i , где

исследовании — его умение успешно работать при от-
i соответствует порядковому номеру набора атрибутов
^aij ^,

сутствующих значениях атрибутов в выборке. Часто при прогнозировании или классификации возникает необхо- димость предварительно выбирать, какие из параметров следует включать в выборки данных и в какой форме это делать. В этой статье рассматривается решение задачи
а j — количеству атрибутов в каждом из наборов A_i ={ a_i1 ; a_i2 ; a_i3 ;…; a_ij } на входе в выборке данных. Значения всех ат- рибутов c_i и a_ij в выборке могут повторяться. Задача прогно- зирования, в данном случае, сводится к классификации таких

подбора параметров для выборки с целью формирования
наборов
A_i при неизвестных значениях c_i . Для распределе-

наиболее подходящих, с точки зрения эффективности классификации, выборок данных. Далее рассматривается метод определения, распределения весов входящих пара- метров с применением возможностей алгоритма C4.5.
Существует несколько подходов к решению проблемы прогнозирования при отсутствующих значениях в на- борах входящих данных [5]. Самый простой подход со- стоит в игнорировании случаев с любыми пропущенными значениями. Такой подход уменьшает выборку и, следо- вательно, не является приемлемым в случае наличия вы- сокой доли недостающих значений.
Другой распространенный подход заключается в за- мене отсутствующих значений глобальным или соответ- ствующим одному классу средним или наиболее часто встречающимся значением, но при этом не задейство- ваны возможные зависимости недостающего атрибута от других атрибутов. Создатель алгоритма С4.5 Р. Квинлан установил [6], что выделив случаи с пропущенными зна- чениями среди подмножеств при разбиении обучающей выборки в дереве решений, и объединив все возможные результаты на тестовом примере с отсутствующими значе- ниями во время классификации, можно добиться большей точности классификации, чем при использовании других вариантов процесса обучения дерева решений. В C4.5 применяется такой вероятностный подход для обработки
ния наборов атрибутов необходимо сперва указать возмож- ные значения классов, а также выработать соответственные правила классификации, что и выполняется с помощью пред- варительного обучения алгоритма построения дерева приня- тия решений на основе данных из обучающей выборки [8].
Однако влияние значений отдельных атрибутов a_ij на вы-
бор того или иного значения класса c_i неочевидно. Расчет же значений энтропии [9] не всегда позволяет определить влия- ние на результат классификации отдельных подмножеств па- раметров из множества A_i всех доступных параметров.
Представим структуру данных в обучающей выборке в следующем виде: