Оцінка загальної складності процедури побудови бінарного логічного дерева класифікації для довільного випадку
DOI:10.31673/2412-4338.2020.021100
Анотація
Пропонується верхня оцінка складності процедури синтезу бінарного логічного дерева класифікації для довільного випадку (для умов слабкого та сильного розділення класів навчальної вибірки). Розв‘язок даного питання має принциповий характер, щодо оцінки структурної складності моделей класифікації (у вигляді деревоподібних конструкцій) дискретних об‘єктів для широкого спектру прикладних задач класифікації та розпізнавання в плані розробки перспективних схем та методів їх фінальної оптимізації (мінімізації) структури. Дане дослідження має актуальність не лише для конструкцій логічних дерев класифікації, але дозволяє розширити саму схему оцінки складності і на загальний випадок структур алгоритмічних дерев класифікації (концепції дерев алгоритмів та дерев узагальнених ознак).
Досліджене актуальне питання складності загальної процедури побудови логічного дерева класифікації на основі концепції поетапної селекції наборів елементарних ознак (можливих їх різнотипних множин та сполучень), яке для заданої початкової навчальної вибірки (масиву дискретної інформації) будує деревоподібну структуру (модель класифікації), з набору елементарних ознак (базових атрибутів) оцінених на кожному кроці схеми побудови моделі за даною вибіркою. Так сучасні інформаційні технології, засновані на математичних моделях розпізнавання образів (логічних та алгоритмічних дерев класифікації), широко використовуються в соціально-економічних, екологічних та інших системах первинного аналізу та обробки великих масивів інформації. Причому це пояснюється тим фактом, що такий підхід дозволяє усунути набір існуючих недоліків добре відомих класичних методів, схем та досягти принципово новий результат. Робота присвячена проблематиці моделей дерев класифікації (дерев рішень), та пропонує оцінку складності структур логічних дерев (моделей дерев класифікації), які складаються з відібраних та ранжованих наборів елементарних ознак побудованих на основі загальної концепції розгалуженого вибору ознак. Даний метод при формуванні поточної вершини логічного дерева (вузла) забезпечує виділення найбільш інформативних (якісних) елементарних ознак з початкового набору. Такий підхід при побудові результуючого дерева класифікації дозволяє значно скоротити розмір та складність дерева (загальну кількість гілок та ярусів структури) підвищити якість його наступного аналізу (інтерпретабельність).
Ключові слова: логічне дерево класифікації, розпізнавання образів, класифікація, дискретна ознака.
Список використаної літератури
1. Srikant R. Mining generalized association rules / R. Srikant, R. Agrawal // Future Generation Computer Systems. 1997, Vol. 13, №2. – P. 161–180.
2. Василенко Ю.А. Концептуальна основа систем розпізнавання образів на основі метода розгалуженого вибору ознак / Ю.А. Василенко, Е.Ю. Василенко, І.Ф. Повхан, Ф.Г. Ващук // Науково технічний журнал “European Journal of Enterprise Technologies”. 2004, №7[1], – С. 13-15.
3. Василенко Ю.А. Проблема оцінки складності логічних дерев розпізнавання та загальний метод їх оптимізації / Ю.А. Василенко, І.Ф. Повхан, Ф.Г. Ващук // Науково технічний журнал “European Journal of Enterprise Technologies”. 2011, 6/4(54), – С . 24-28.
4. Василенко Ю.А Загальна оцінка мінімізації деревоподібних логічних структур / Ю.А. Василенко, Е.Ю. Василенко, І.Ф. Повхан, Ф.Г. Ващук // Науково технічний журнал “European Journal of Enterprise Technologies”. 2012, 1/4(55), – С. 29-33.
5. Povhan I. General scheme for constructing the most complex logical tree of classification in pattern recognition discrete objects / I. Povhan // Збірник наукових праць "Електроніка та інформаційні технології", Львів, 2019, Випуск 11, – С. 112-117.
6. Василенко Ю.А. Мінімізація логічних деревоподібних структур в задачах розпізнавання образів / Ю.А. Василенко, Е.Ю. Василенко, І.Ф. Повхан, М.Й. Ковач, О.Д. Нікарович // Науково технічний журнал “European Journal of Enterprise Technologies”. 2004, 3[9], – С. 12-16.
7. Лавер В.О. Алгоритми побудови логічних дерев класифікації в задачах розпізнавання образів / В.О. Лавер, І.Ф. Повхан // Вчені записки Таврійського національного університету. Серія: технічні науки. 2019, Том 30(69) № 4 2019, – С.100-106.
8. Vtogoff P.E. Incremental Induction of Decision Trees / P.E. Vtogoff // Machine Learning. 2009, № 4, – P. 161−186.
9. Повхан І.Ф. Проблема функціональної оцінки навчальної вибірки в задачах розпізнавання дискретних об‘єктів / І.Ф. Повхан // Вчені записки Таврійського національного університету. Серія: технічні науки. 2018. Том 29(68) № 6 2018, – С. 217-222.
10. Whitley D. An overview of evolutionary algorithms: practical issues and common pitfalls / D. Whitley // Information and Software Technology. 2001, Vol.43, №14, – P. 817–831.
11. Povhan I. Designing of recognition system of discrete objects / I. Povhan // 2016 IEEE First International Conference on Data Stream Mining & Processing (DSMP), Lviv, 2016, Ukraine. – Lviv, 2016. – P. 226–231.
12. Kotsiantis S.B. Supervised Machine Learning: A Review of Classification Techniques / S.B. Kotsiantis // Informatica. 2007, №31, – P. 249–268.
13. Суботин С. А. Построение деревьев решений для случая малоинформативных признаков / С.А. Суботин // Radio Electronics, Computer Science, Control. 2019. № 1, – P. 121–130.
14. Deng H. Bias of importance measures for multi-valued attributes and solutions / H. Deng, G. Runger, E. Tuv // Proceedings of the 21st International Conference on Artificial Neural Networks (ICANN). 2011, – P. 293–300.
15. Повхан І. Ф. Особливості синтезу узагальнених ознак при побудові систем розпізнавання за методом логічного дерева / І.Ф. Повхан // Інформаційні технології та комп’ютерне моделювання ІТКМ-2019 : матеріали міжнародної науково-практичної конференції, Івано-Франківськ, 2019, – С. 169–174.
16. Повхан І. Ф. Особливості випадкових логічних дерев класифікації в задачах розпізнавання образів / І.Ф. Повхан // Вчені записки Таврійського національного університету. Серія : технічні науки. 2019, Т. 30 (69), № 5, – С. 152–161.
17. Povhan I. Generation of elementary signs in the general scheme of the recognition system based on the logical tree / I. Povhan // Збірник наукових праць "Електроніка та інформаційні технології". Lviv, 2019, Vol. 12. – C. 20-29.
18. Povhan I. Question of the optimality criterion of a regular logical tree based on the concept of similarity / I. Povhan // Збірник наукових праць "Електроніка та інформаційні технології". Lviv, 2020, Vol. 13. – C. 19-27.
