ВИКОРИСТАННЯ ЗАДАЧІ ПРО МІНІМАЛЬНЕ ОСТОВНЕ ДЕРЕВО ДЛЯ ІНТЕЛЕКТУАЛЬНОГО АНАЛІЗУ ДАНИХ
DOI:
https://doi.org/10.32782/tnv-tech.2024.1.5Ключові слова:
граф, мінімальне остовне дерево, «жадібний» алгоритм, найкоротший шлях, кластеризація, інтелектуальний аналіз данихАнотація
Стаття присвячена спробі визначення кластерів за допомогою оптимізаційної задачі про мінімальне остовне дерево. Проблема задачі кластеризації полягає в групуванні подібних об’єктів у множину кластерів таким чином, щоб об’єкти всередині одного кластера були схожі між собою, а об’єкти між різними кластерами були відмінними. Одним із підходів до розв’язання цієї проблеми є використання задачі про мінімальне остовне дерево. Ідея використання задачі про мінімальне остовне дерево для кластеризації полягає в тому, щоб побудувати дерево, яке з’єднує всі об’єкти, де ваги ребер відповідають відстаням між об’єктами. Потім, за допомогою деякого методу обрізання, можна видалити певну кількість ребер, щоб розділити дерево на кластери. Для цього необхідно видалити найбільш довгі ребра, щоб розділити дерево на окремі компоненти, які відповідають кластерам. Цей підхід може бути особливо ефективним у випадках, коли необхідно мінімізувати збіги: мінімальне остовне дерево об’єднує вершини з найменшими відстанями, тобто вершини, які найбільше схожі одна на одну, будуть розташовані поруч. Це допомагає зменшити кількість збігів у кластерах та поліпшити якість кластеризації. Мінімальне остовне дерево може бути легко інтерпретоване, оскільки воно показує найближчі зв’язки між вершинами, це дозволяє зрозуміти, які групи даних схильні до групування разом. Він також може бути корисним у випадках, коли маємо справу з великими обсягами даних, оскільки алгоритми побудови мінімального остовного дерева мають низьку обчислювальну складність. Мінімальне остовне дерево дозволяє ігнорувати шум у даних, оскільки він будує з’єднання між найближчими точками, і шумові дані зазвичай будуть далеко від інших точок, а також дозволяє природним чином визначити кількість кластерів. Кількість кластерів відповідає кількості ребер у мінімальному остовному дереві після видалення найбільш довгих ребер. Однак, варто враховувати, що цей підхід може не завжди бути найкращим для всіх типів даних і вимагає уважного аналізу та налаштування параметрів для кожного конкретного випадку.
Посилання
Поповський, В., Сабурова, С., Олійник, В., Лосєв, Ю., Агеєв, Д. Математичні основи теорій телекомунікаційних систем. Харків : ТОВ «Компанія СМІТ», 2006. 564 с.
Капітонова Ю.В. Основи дискретної математики. Київ : Наукова думка, 2002. 580 с.
Димова Г.О., Ларченко О.В. Моделі і методи інтелектуального аналізу даних: навчальний посібник. Херсон : Книжкове видавництво ФОП Вишемирський В. С., 2021. 142 с.
Phillips D.T., Garcia-Diaz A. Fundamentals of Network Analysis. Prentice-Hall, Inc., Englewood Cliffs, N.J., 1981. 496 p.
Dymova H. Development Of A Software Application Algorithm For Solving Computer Network Optimization Problems. Débats scientifiques et orientations prospectives du développement scientifique : c avec des matériaux de la VI conférence scientifique et pratique internationale, Paris, 1er Mars 2024. Paris-Vinnytsia : La Fedeltà & UKRLOGOS Group LLC, 2024. Pp. 226–229. DOI 10.36074/logos-01.03.2024.051.
Димова Г., Ларченко О. Розробка комп’ютерної програми розв’язання задач мережевої оптимізації. Науковий журнал «Комп’ютерно-інтегровані технології: освіта, наука, виробництво», (41), 2020. С. 142–150. DOI 10.36910/6775-2524-0560-2020-41-23.
Bhargava A. Grokking Algorithms. An Illustrated Guide For Programmers And Other Curious People. By Manning Publications Co. All Rights Reserved, 2016. 288 p.
Dymova H. Application of Characterization Analysis Methods to Investigation of Logical Networks Structures. Theoretical and Empirical Scientific Research: Concept and Trends with Proceedings of the V International Scientific and Practical Conference. Oxford, United Kingdom : European Scientific Platform, 2023. Pp. 124–128. DOI: 10.36074/logos-23.06.2023.34.
