ОСОБЛИВОСТІ ПРОГРАМНИХ РІШЕНЬ МОДЕЛЕЙ ЛОГІЧНИХ ДЕРЕВ КЛАСИФІКАЦІЇ НА ОСНОВІ СЕЛЕКЦІЇ НАБОРІВ ЕЛЕМЕНТАРНИХ ОЗНАК

Автор(и)

Ключові слова:

задачі розпізнавання, дерева класифікації, логічне дерево, схема розпізнавання, алгоритм, дискретний об’єкт, елементарна ознака, розгалужений вибір ознак

Анотація

Актуальність теми дослідження. Нині існує декілька незалежних, загальних підходів (концепцій) для вирішення різнотипних завдань класифікації у класичній постановці, розроблено набір різних концепцій, підходів, методів, моделей та схем, інструментарію, які охоплюють загальну проблему теорії штучного інтелекту та інформаційних систем. Причому всі ці підходи в теорії розпізнавання мають свої фіксовані переваги і недоліки та утворюють єдиний інструментарій розв’язку прикладних задач теорії штучного інтелекту. Важливою проблемою залишається питання ефективності програмних схем та алгоритмів синтезу конструкцій дерев класифікації в розрізі ефективності критерію розгалуження їхньої структури. Отже, центральну увагу в цьому дослідженні буде приділено актуальній концепції дерев рішень (дерев класифікації), розглядається загальна задача програмної (алгоритмічної) побудови логічних дерев розпізнавання (класифікації). Об’єктом цього дослідження є логічні дерева класифікації (структури ЛДК) їхні сучасні програмні реалізації. Предметом дослідження є актуальні методи та алгоритмічні схеми побудови логічних дерев класифікації.

Постановка проблеми. Основні наявні методи та алгоритми роботи з масивами дискретної інформації при побудові функції розпізнавання (класифікаторів) не дозволяють досягнути наперед заданого рівня точності (ефективності) системи класифікації та регулювати їх складність у процесі побудови. Однак цей недолік відсутній у методах та схемах побудови систем розпізнавання, які базуються на концепції логічних дерев класифікації (дерев рішень). Структура логічного дерева являє собою зв’язану множину гілок та вузлів, причому на гілках дерева розташовуються деякі мітки (атрибути, значення ознак), від яких залежить цільова функція (у випадку ЛДК – функція розпізнавання), а у вузлах (вершинах) знаходяться значення функції розпізнавання або розширені атрибути переходів. Тобто схема покриття навчальної вибірки набором елементарних ознак у випадку ЛДК породжує фіксовану деревоподібну структуру даних (модель ЛДК), яка забезпечує стиск та перетворення початкових даних НВ, а отже, дозволяє суттєву оптимізацію та економію апаратних ресурсів системи, до того ж в основі лежить єдина методологія – оптимальної апроксимації навчаючої вибірки набором елементарних ознак (атрибутів), які входять у деяку схему (оператор), побудовану в процесі навчання. 

Аналіз останніх досліджень і публікацій. У представленому дослідженні були розглянуті останні публікації у відкритому доступі, які присвячені загальній тематиці підходів, методів, алгоритмів та схем розпізнавання (моделей дерев класифікації – структур ЛДК/АДК) дискретних об’єктів, відповідним програмним реалізаціям дерев рішень у задачах розпізнавання образів теорії штучного інтелекту.

Виділення недосліджених частин загальної проблеми. Можливість ефективної та економної програмної (алгоритмічної) схеми побудови логічного дерева класифікації (моделі структури ЛДК) на основі початкових масивів навчальних вибірок (масивів дискретної інформації) великого об’єму.

Постановка завдання. Розробка простого та якісного програмного методу (алгоритму та програмної системи) побудови моделей (структур) ЛДК для великих масивів початкових вибірок шляхом синтезу мінімальних форм дерев класифікації та розпізнавання, які забезпечують ефективну апроксимацію навчальної інформації набором ранжованих елементарних ознак (атрибутів) на основі схеми розгалуженого вибору ознак у широкому спектрі прикладних задач. 

Виклад основного матеріалу. Пропонується загальна програмна схема побудови структур логічних дерев класифікації, яка для заданої початкової навчальної вибірки будує деревоподібну структуру (модель класифікації), яка складається з набору елементарних ознак оцінених на кожному кроці побудови моделі за даною вибіркою. Запропоновано метод та готова програмна система побудови логічних дерев, основна ідея якого полягає в апроксимації начальної вибірки довільного об‘єму набором елементарних ознак. Цей метод при формуванні поточної вершини логічного дерева (вузла) забезпечує виділення найбільш інформативних (якісних) елементарних ознак із початкового набору. Такий підхід при побудові результуючого дерева класифікації дозволяє значно скоротити розмір та складність дерева (загальну кількість гілок та ярусів структури) підвищити якість його наступного аналізу.

Висновки відповідно до статті. Розроблене та запропоноване в роботі програмне забезпечення побудови структур ЛДК (моделей дерев класифікації) дозволяє використовувати його для розв‘язку широкого спектра практичних задач розпізнавання та класифікації, а перспективи подальших досліджень можуть полягати у створенні обмеженого методу логічного дерева класифікації (структур ЛДК), який полягає у введенні критерію зупинки процедури побудови логічного дерева за глибиною структури, оптимізації його програмних реалізацій, а також експериментальних дослідженнях цього методу на більш широке коло практичних задач. 

Біографія автора

Ігор Федорович Повхан, ДВНЗ «Ужгородський національний університет»

кандидат технічних наук, доцент

Посилання

Повхан І. Ф. Особливості випадкових логічних дерев класифікації в задачах розпізнавання образів. Вчені записки Таврійського національного університету. Серія : технічні науки. 2019. Т. 30(69), № 5, С. 152–161.

Povhan I. Generation of elementary signs in the general scheme of the recognition system based on the logical tree. Збірник наукових праць «Електроніка та інформаційні технології». Lviv, 2019, Vol. 12. C. 20-29.

Povhan I. Question of the optimality criterion of a regular logical tree based on the concept of similarity. Збірник наукових праць «Електроніка та інформаційні технології». Lviv, 2020, Vol. 13. C. 19-27.

Повхан І. Ф. Особливості синтезу узагальнених ознак при побудові систем розпізнавання за методом логічного дерева. Інформаційні технології та комп’ютерне моделювання ІТКМ-2019 : матеріали міжнародної науково-практичної конференції. Івано-Франківськ, 2019. С. 169–174.

Kotsiantis S. B. Supervised Machine Learning: A Review of Classification Techniques. Informatica. 2007, № 31. Pр. 249–268.

Суботин С. А. Построение деревьев решений для случая малоинформативных признаков. Radio Electronics, Computer Science, Control. 2019. № 1. Pр. 121–130.

Deng H., Runger G., Tuv E. Bias of importance measures for multi-valued attributes and solutions. Proceedings of the 21st International Conference on Artificial Neural Networks (ICANN). 2011. Pр. 293–300.

Srikant R., Agrawal R. Mining generalized association rules. Future Generation Computer Systems. 1997, Vol. 13, № 2. P. 161–180.

Quinlan J.R. Induction of Decision Trees. Machine Learning. 1986. № 1. Pр. 81–106.

Miyakawa M. Criteria for selecting a variable in the construction of efficient decision trees. IEEE Transactions on Computers. 1989. Vol. 38, № 1. Pр. 130–141.

Whitley D. An overview of evolutionary algorithms: practical issues and common pitfalls. Information and Software Technology. 2001, Vol. 43, № 14. Pр. 817–831.

Vtogoff P. E. Incremental Induction of Decision Trees. Machine Learning. 2009. № 4. Pр. 161−186.

Лавер В. О., Повхан І. Ф. Алгоритми побудови логічних дерев класифікації в задачах розпізнавання образів. Вчені записки Таврійського національного університету. Серія: технічні науки. 2019. Том 30(69), № 4. С. 100–106.

Povhan I. Designing of recognition system of discrete objects. 2016 IEEE First International Conference on Data Stream Mining & Processing (DSMP), Lviv, 2016, Ukraine. Lviv, 2016. Pр. 226–231.

Повхан І. Ф. Проблема функціональної оцінки навчальної вибірки в задачах розпізнавання дискретних об’єктів. Вчені записки Таврійського національного університету. Серія: технічні науки. 2018. Том 29(68), № 6. С. 217–222.

Mingers J. An empirical comparison of pruning methods for decision tree induction. Machine learning. 1989. Vol. 4, № 2. Pр. 227–243.

Subbotin S. A. Methods and characteristics of locality-preserving transformations in the problems of computational intelligence. Radio Electronics, Computer Science, Control. 2014. № 1. Pр. 120–128.

Subbotin S. A. Methods of sampling based on exhaustive and evolutionary search. Automatic Control and Computer Sciences. 2013. Vol. 47, № 3. Pр. 113–121.

De Mántaras R. L. A distance-based attribute selection measure for decision tree induction. Machine learning. 1991. Vol. 6, № 1. Pр. 81–92.

Alpaydin E. Introduction to Machine Learning. London: The MIT Press, 2010. 400 p.

Painsky A., Rosset S. Cross-validated variable selection in tree-based methods improves predictive performance. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2017. Vol. 39, № 11. Pр. 2142–2153.

Василенко Ю. А., Повхан І. Ф., Ващук Ф. Г. Загальна оцінка мінімізації деревоподібних логічних структур. Eastern-European Journal of Enterprise Technologies. 2012. Том 2, № 4(56). С. 29-33.

Povhan I. General scheme for constructing the most complex logical tree of classification in pattern recognition discrete objects. Збірник наукових праць «Електроніка та інформаційні технології». 2019. Вип. 11. С. 112–117.

What is the C4.5 algorithm and how does it work (2019). URL: https://towardsdatascience.com/what-is-the-c4-5-algorithm-and-how-does-it-work-2b971a9e7db0.

C5.0 Classification Models (2020). URL: https://cran.r-project.org/web/packages/C50/vignettes/ C5.0.html.

C5.0 Decision Trees and Rule-Based Models (2020). URL: https://topepo.github.io/C5.0/ reference/C5.0.html.

C5.0 An Informal Tutorial (2020). URL: https://www.rulequest.com/see5-unix.html.

Subbotin S., Oliinyk A. The dimensionality reduction methods based on computational intelligence in problems of object classification and diagnosis. Recent Advances in Systems, Control and Information Technology / R. Szewczyk, M. Kaliczyńska (Eds.) Cham: Springer (Advances in Intelligent Systems and Computing), 2017. Vol. 543. Pр. 11–19.

Subbotin S. A. Random forest model building using a priori information for diagnosis. CEUR Workshop Proceedings. 2019. № 23. Pр. 962–973.

Dietterich T. G. An experimental comparison of three methods for constructing ensembles of decision trees: bagging, boosting, and randomization. Machine learning. 2019. Vol. 40(2). Pр. 139–157.

Kamiński B., Jakubczyk M., Szufel P. A framework for sensitivity analysis of decision trees. Central European Journal of Operations Research. 2017. Vol. 26(1). Pр. 135–159.

##submission.downloads##

Номер

Розділ

ІНФОРМАЦІЙНО-КОМП’ЮТЕРНІ ТЕХНОЛОГІЇ