Використання довжинної міри подібності в задачах кластеризації

Abstract

UK: Актуальність. Дослідження присвячено розробці гнучкого математичного апарату, який мав би досить широкий спектр засобів для групування об’єктів за різними видами мір подібності. Це дає можливість в межах розробленого підходу ефективно розв’язувати достатньо широкі класи прикладних задач із різних предметних областей та проводити розбиття об’єктів кластерами різних геометричних форм. Метою дослідження є підвищення ефективності розв’язання прикладних задач кластеризації шляхом використання довжинної міри подібності векторних ознак об’єктів. Методи. Описано нечітке бінарне відношення та його функцію належності, що характеризує схожість об’єктів за довжинною мірою подібності їх векторних ознак. Модифіковано метод однорівневої кластеризації, заснований на нечітких бінарних відношеннях для використання довжинної міри подібності. При цьому задаються певні величини – пороги кластеризації, що характеризують ступінь подібності об’єктів в середині кластеру. Змінюючи пороги кластеризації можна проаналізувати динаміку формування кластерів, дослідити їх структуру та взаємозв’язки між об’єктами, визначити граничні об’єкти, зробити ґрунтовніший аналіз отриманих результатів. Запропонований підхід не потребує попереднього визначення кількості кластерів та дозволяє проводити кластеризацію даних концентричними сферами в умовах відсутності додаткової апріорної інформації, тому може використовуватись і на етапі попереднього аналізу даних. Результати. Розроблений підхід реалізовано у вигляді програмної системи, на основі якої розв’язано актуальну прикладну задачу дослідження інтенсивності міграційного руху населення за регіонами України. Висновки. Проведені експериментальні дослідження показали зручність та ефективність використання довжинної міри подібності при розв’язанні прикладних задач, що потребують групування кластерами у вигляді концентричних сфер. Представлений підхід забезпечив можливість проводити нові змістовні дослідження вхідних даних. Перспективи подальших досліджень полягають у розробці системи підтримки прийняття рішень, для розв’язання задач групування об’єктів на кластери концентричними сферами, конусами, еліпсами та їх перетинами; реалізації паралельної багаторівневої кластеризації проведеної одночасно за декількома критеріями подібності об’єктів та її застосуванні; дослідженні розбиттів об’єктів різними геометричними формами кластерів для однієї вибірки вхідних даних та проведенні змістовної інтерпретації отриманих результатів. EN: Context. The study is devoted to the development of a flexible mathematical apparatus, which should have a sufficiently wide range of means for grouping objects into different types of similarity measures. This makes it possible, within the framework of the developed approach, to efficiently solve sufficiently broad classes of applied problems from different subject areas and to partition objects with clusters of different geometric forms. Objective. The aim of the study is improvement of the efficiency of solving cluster problems by applying a similar measure of the vector characteristics of objects. Method. A fuzzy binary relation and its membership function describing the similarity of objects according to the level of similarity of their vector attributes are described. The method of single-level clustering, based on fuzzy binary relations for the use of a similarity measure, is modified. In this case, certain values are set – the thresholds of clusterization that characterize the similarity degree of objects within the cluster. By changing the thresholds of clusterization, one can analyze the dynamics of cluster formation, investigate their structure and interrelationships between objects, determine the ultimate objects, and make a thorough analysis of the obtained results. The proposed approach does not require a preliminary determination of the number of clusters and allows clustering of data in concentric spheres in the absence of additional a priori information, so it can be used at the stage of preliminary data analysis. Results. The developed approach is implemented in the form of a software system on the basis of which the actual applied problem of investigating the intensity of population migration by regions of Ukraine is solved. Conclusions. The conducted experimental researches show the convenience and efficiency of using the similarity measure for solving applied problems requiring clustering in the form of concentric spheres. The presented approach provides an opportunity to conduct new meaningful studies of input data. Prospects for further research are development of a decision support system, to solve the problems of grouping objects into clusters by concentric spheres, cones, ellipses and their intersections; implementation of parallel multi-level clustering carried out simultaneously by several criteria of similarity of objects and their application; study of the partitioning of objects by different geometric forms of clusters for a single sample of input data and carrying out a meaningful interpretation of the obtained results.