The fractal analysis of sample and decision tree model

Abstract

EN: Context. The problem of decision tree model synthesis using the fractal analysis is considered in the paper. The object of study is a decision trees. The subject of study is a methods of decision tree model synthesis and analysis. Objective. The objective of the paper is a creation of methods and fractal indicators allowing jointly solving the problem of decision tree model synthesis and the task of reducing the dimension of training data from a unified approach based on the principles of fractal analysis. Method. The fractal dimension for a decision tree based model is defined as for whole training sample as for specific classes. The method of the fractal dimension of a model based on a decision tree estimation taking into account model error is proposed. It allows to built model with an acceptable error value, but with optimized level of fractal dimensionality. This makes possibility to reduce decision tree model complexity and to make it mo interpretable. The set of indicators characterizing complexity of decision tree model is proposed. The set of indicators characterizing complexity of decision tree model is proposed. It contains complexity of node checking, complexity of node achieving, an average model complexity and worst tree model complexity of computations. On the basis of proposed set of indicators a complex criterion for model building is proposed. The indicators of the fractal dimension of the decision tree model error can be used to find and remove the non-informative features in the model. Results. The developed indicators and methods are implemented in software and studied at practical problem solving. As results of experimental study of proposed indicators the graphs of their dependences were obtained. They include graphs of dependencies of number of hyperblocks covering the sample in the features space from size of block side: for whole sample, for each class, for different set error values and obtained error values, for varied values of resulted number of features and instances, also as graphs of dependencies between average and worst tree complexities, decision tree fractal dimensionality and tree average complexity, joint criterion and indicator of feature set reduction, and between joint criterion and tree fractal dimensionality/ Conclusions. The conducted experiments confirmed the operability of the proposed mathematical support and allow recommending it for use in practice for solving the problems of model building by the precedents. UK: Актуальність. У статті розглядається проблема синтезу моделі на основі дерева рішень з використанням фрактального аналізу. Об’єктом дослідження є дерева рішень. Предметом дослідження є методи синтезу та аналізу моделей на основі дерев рішень. Мета роботи – створення методів і фрактальних індикаторів, що дозволяють спільно вирішити задачу синтезу моделі на основі дерева рішень і завдання скорочення розмірності навчальних даних за допомогою єдиного підходу, заснованого на принципах фрактального аналізу. Метод. Фрактальна розмірність для моделі на основі дерева рішень визначена як для всієї навчальної вибірки, так і для кожного класу. Запропоновано метод визначення фрактальної розмірності моделі, заснований на оцінюванні дерева рішень з урахуванням похибки моделі. Це дозволяє побудувати модель з прийнятним значенням помилки, але з оптимізованим рівнем фрактальної розмірності, що дозволяє зменшити складність моделі дерева рішень і зробити її більш зрозумілою. Запропоновано набір показників, що характеризують складність моделі на основі дерева рішень. Він містить складність перевірки вузлів, складність досягнення вузла, середню і найгіршу складність обчислень моделі дерева. На основі запропонованого набору показників запропоновано комплексний критерій побудови моделі. Індикатори фрактальної розмірності помилки моделі дерева рішень можуть бути використані для пошуку і видалення неінформативних ознак в моделі. Результати. Розроблені показники і методи реалізовані в програмному забезпеченні і вивчені при вирішенні практичних завдань. В результаті експериментального дослідження запропонованих показників отримані графіки залежностей між ними, включаючи графіки залежностей числа гіперблоков, що охоплюють вибірку в просторі ознак, від розміру боку блоку: для всієї вибірки, для кожного класу, для різних встановлених значень помилок і отриманих значень помилок, для різних значень результуючих чисел ознак і екземплярів, також графіків залежностей між середньою і найгіршою складнощами дерева, фрактальної розмірністю дерева рішень і ср днів складністю дерева, об’єднаним критерієм і індикатором скорочення набору ознак, а також між спільним критерієм і фрактальної розмірністю дерева. Висновки. Проведені експерименти підтвердили працездатність запропонованого математичного забезпечення та дозволяють рекомендувати його для практичного використання для вирішення завдань побудови моделей по прецедентах.