Оцінка складності побудови логічного дерева класифікації для довільного випадку в умовах сильного розділення класів початкової навчальної вибірки
DOI: 10.31673/2412-4338.2020.035566
Анотація
В роботі пропонується оцінка складності побудованої структури логічного дерева класифікації для довільного випадку в умовах сильного розділення класів початкової навчальної вибірки. Принциповий розв‘язок даного питання має визначальний характер, щодо оцінки структурної складності моделей класифікації (у вигляді деревоподібних конструкцій ЛДК/АДК) дискретних об‘єктів для широкого спектру прикладних задач класифікації та розпізнавання в плані розробки перспективних схем та методів їх фінальної оптимізації (мінімізації) обрізки (post pruning) структури. Представлене дослідження має актуальність не лише для конструкцій (структур) логічних дерев класифікації, але дозволяє розширити саму схему оцінки складності і на загальний випадок структур алгоритмічних (моделей АДК) дерев класифікації (концепції дерев алгоритмів та дерев узагальнених ознак – ДУО). Досліджене актуальне питання концепції дерев рішень (дерев розпізнавання) – оцінка максимальної складності загальної схеми побудови логічного дерева класифікації на основі процедури поетапної селекції наборів елементарних ознак (можливих їх різнотипних множин та сполучень), яке для заданої початкової навчальної вибірки (масиву дискретної інформації) будує деревоподібну структуру (модель класифікації), з набору елементарних ознак (базових атрибутів) оцінених на кожному кроці схеми побудови моделі за даною вибіркою для випадку сильного розділення класів. Сучасні інформаційні системи та технології, засновані на математичних підходах (моделях) розпізнавання образів (структурах логічних та алгоритмічних дерев класифікації), широко використовуються в соціально-економічних, екологічних та інших системах первинного аналізу та обробки великих масивів інформації, причому це пояснюється тим фактом, що такий підхід дозволяє усунути набір існуючих недоліків добре відомих класичних методів, схем та досягти принципово новий результат. Дослідження присвячена проблематиці моделей дерев класифікації (дерев рішень), та пропонує оцінку складності структур логічних дерев (моделей дерев класифікації), які складаються з відібраних та ранжованих наборів елементарних ознак (окремих ознак та їх сполучень) побудованих на основі загальної концепції розгалуженого вибору ознак. Даний метод при формуванні поточної вершини логічного дерева (вузла) забезпечує виділення найбільш інформативних (якісних) елементарних ознак з початкового набору. Такий підхід при побудові результуючого дерева класифікації дозволяє значно скоротити розмір та складність дерева (загальну кількість гілок та ярусів структури) підвищити якість його наступного інструментального аналізу (фінальної декомпозиції моделі).
Ключові слова: логічне дерево класифікації, навчальна вибірка, розпізнавання образів, класифікація, дискретна ознака, схема класифікації.
Список використаної літератури
1. 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.
2. 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.
3. Повхан І.Ф. Проблема функціональної оцінки навчальної вибірки в задачах розпізнавання дискретних об‘єктів. Вчені записки Таврійського національного університету. Серія: технічні науки, 2018, Том 29(68) № 6 2018. С. 217-222.
4. Василенко Ю.А., Василенко Е.Ю., Повхан І.Ф., Ковач М.Й., Нікарович О.Д. Мінімізація логічних деревоподібних структур в задачах розпізнавання образів. Науково технічний журнал “European Journal of Enterprise Technologies”, 2004, 3[9]. С. 12-16.
5. Alpaydin E. Introduction to Machine Learning. London: The MIT Prs, 2010. 400p.
6. 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-153.
7. Srikant R. Mining generalized association rules. Future Generation Computer Systems, 1997, Vol. 13, №2. P. 161-180.
8. Василенко Ю.А., Василенко Е.Ю., Повхан І.Ф., Ващук Ф.Г. Концептуальна основа систем розпізнавання образів на основі метода розгалуженого вибору ознак. Науково технічний журнал “European Journal of Enterprise Technologies”, 2004, №7[1]. С. 13-15.
9. Василенко Ю.А., Василенко Е.Ю., Повхан І.Ф., Ващук Ф.Г. Проблема оцінки складності логічних дерев розпізнавання та загальний метод їх оптимізації. Науково технічний журнал “European Journal of Enterprise Technologies”, 2011, 6/4(54). С. 24-28.
10. Василенко Ю.А., Василенко Е.Ю., Повхан І.Ф., Ващук Ф.Г. Загальна оцінка мінімізації деревоподібних логічних структур. Науково технічний журнал “European Journal of Enterprise Technologies”, 2012, 1/4(55). С. 29-33.
11. Povhan I. General scheme for constructing the most complex logical tree of classification in pattern recognition discrete objects. Збірник наукових праць "Електроніка та інформаційні технології", Львів, 2019, Випуск 11. С. 112-117.
12. Лавер В.О., Повхан І.Ф. Алгоритми побудови логічних дерев класифікації в задачах розпізнавання образів. Вчені записки Таврійського національного університету. Серія: технічні науки, 2019, Том 30(69) № 4 2019. С. 100-106.
13. Повхан І.Ф. Оцінка загальної складності процедури побудови бінарного логічного дерева класифікації для довільного випадку. Науковий журнал: Телекомунікаційні та інформаційні технології, 2020, №2 (67) 2020. С. 100-111.
14. Vtogoff P.E. Incremental Induction of Decision Trees. Machine Learning, 2009, №4. P. 161-186.
15. Whitley D. An overview of evolutionary algorithms: practical issues and common pitfalls. Information and Software Technology, 2001, Vol. 43, №14. P. 817–831.
16. 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. 17. Kotsiantis S.B. Supervised Machine Learning: A Review of Classification Techniques. Informatica, 2007, №31. P. 249-268.
18. Суботин С. А. Построение деревьев решений для случая малоинформативных признаков. Radio Electronics, Computer Science, Control, 2019, № 1. P. 121-130. 19. 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.
20. 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.
21. Subbotin S.A. Methods of sampling based on exhaustive and evolutionary search. Automatic Control and Computer Sciences, 2013, Vol. 47, №3. P. 113-121.
22. De Mántaras R.L. A distance-based attribute selection measure for decision tree induction. Machine learning, 1991, Vol. 6. №1. P. 81-92.
23. 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.
24. Povkhan I.F. Features of synthesis of generalized features in the construction of recognition systems using the logical tree method. Information technologies and computer modeling ІТКМ-2019: materials of the international scientific and practical conference, Ivano- Frankivsk, May 20–25, 2019, Ivano-Frankivsk, 2019. P. 169-174.
