Сибирский федеральный университет

Перевод названия: ДИФФЕРЕНЦИАЛЬНАЯ ЭВОЛЮЦИЯ В АЛГОРИТМЕ ОБУЧЕНИЯ ДЕРЕВЬЕВ ПРИНЯТИЯ РЕШЕНИЙ

Тип публикации: статья из журнала

Год издания: 2019

Ключевые слова: Separation measure, Population-Level Dynamic Probabilities, Success History Adaptation, decision tree, classification, optimization, differential evolution, деревья принятия решений, классификация, оптимизация, дифференциальная эволюция

Аннотация: Decision trees (DT) belong to the most effective classification methods. The main advantage of decision trees is a simple and user-friendly interpretation of the results obtained. But despite its well-known advantages the method has some disadvantages as well. One of them is that DT training on high-dimensional data is very time-consuming. The paper considers the way to reduce the DT learning process duration without losses of classification accuracy. There are different algorithms of DT training; the main of them being ID3 and CART algorithms. The paper proposes a modification of DT learning algorithms by means of the information criterion optimization for some selected attribute. The use of this modification allows avoiding optimization by means of enumeration search over the entire data set. The Separation Measure method is used to select the attribute. The method selects the attribute whose class-based averages are most distant from each other. Optimization of the selected attribute is carried out using the method of differential evolution, which is one of the evolutionary modeling methods designed to solve problems of multidimensional optimization. Self-configuring at the population level based on the probabilities of using mutation operator's variants was applied for differential evolution. The classification problems were solved to compare standard DT learning algorithms with the modified ones. Algorithm efficiency refers to the percentage of correctly classified test sample objects. Statistical analysis based on Student's t-test was carried out to compare the efficiency of the algorithms. The analysis showed that the use of the proposed modification of the DT learning algorithm makes it possible to significantly speed up the training process without losses in the classification effectiveness. Деревья принятия решений (ДПР) являются одним из наиболее эффективных методов классификации. Основным преимуществом деревьев принятия решений является простая и понятная пользователю интерпретация полученных результатов. Но, несмотря на известные преимущества подхода, он имеет и недостатки. Одним из главных недостатков является то, что обучение ДПР на данных большой размерности требует значительных затрат времени. В данной статье рассматривается способ уменьшения времени обучения ДПР без потери точности классификации. Существуют различные алгоритмы обучения ДПР, основными из которых являются алгоритмы ID3 и CART. В статье предложена модификация алгоритмов обучения ДПР с помощью оптимизации критерия информативности по некоторому выбранному атрибуту. Применение данной модификации позволяет избежать оптимизации полным перебором по всему набору данных. Для выбора атрибута используется метод Separation Measure. В данном методе выбирается тот атрибут, у которого выборочные средние по классам наиболее отдалены друг от друга. Оптимизация по выбранному атрибуту осуществляется с помощью метода дифференциальной эволюции, одного из методов эволюционного моделирования, предназначенного для решения задачи многомерной оптимизации. Для дифференциальной эволюции применена самонастройка на уровне популяции на основе вероятностей применения видов мутации. Для сравнения стандартных алгоритмов обучения ДПР с модифицированными алгоритмами были решены задачи классификации. Под эффективностью алгоритмов понимается процент правильно классифицированных объектов тестовой выборки. Для сравнения эффективности алгоритмов проведен статистический анализ с применением t-критерия Стьюдента. Анализ показал, что при использовании предложенной модификации алгоритма обучения деревьев принятия решений можно значительно ускорить процесс обучения, не потеряв при этом в эффективности классификации.

Журнал: Сибирский журнал науки и технологий

Выпуск журнала: Т. 20, № 3

Номера страниц: 312-319

ISSN журнала: 25876066

Место издания: Красноярск

Издатель: Федеральное государственное бюджетное образовательное учреждение высшего образования Сибирский государственный университет науки и технологий имени академика М.Ф. Решетнева

• Mitrofanov S.A. (Reshetnev Siberian State University of Science and Technology)
• Semenkin E.S. (Reshetnev Siberian State University of Science and Technology)
• Медведев А.В., рец.

• РИНЦ (eLIBRARY.RU)
• Список ВАК