Труды КНЦ вып.12 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ вып. 5/2021(12))

Abstract An approach to solving the constrained clustering problem has been developed, based on the aggregation of data obtained as a result of evaluating the characteristics of clustered objects by several independent experts, and the analysis of alternative variants of clustering by constraint programming methods using original heuristics. Objects clusterized are represented as multisets, which makes it possible to use appropriate methods of aggregation of expert opinions. It is proposed to solve the constrained clustering problem as a constraint satisfaction problem. The main attention is paid to the issue of reducing the number and simplifying the constraints of the constraint satisfaction problem at the stage of its formalization. Within the framework of the approach, we have created: a) a method for estimating the optimal value of the objective function by hierarchical clustering of multisets, taking into account a priori constraints of the subject domain, and b) a method for generating additional constraints on the desired solution in the form of “smart tables”, based on the obtained estimate. The approach allows us to find the best partition in the problems of the class under consideration, which are characterized by a high dimension. Keywords: semi-supervised clustering, the theory of multisets, constraint programming Funding The study was carried out with the financial support of the Russian Foundation for Basic Research within the framework of the scientific project No. 20-07-00708a. For citation: Zuenko A. A., Fridman O. V., Zuenko O. N. An approach to finding a global optimum in Constrained Clustering tasks involving the assessments of several experts // ^ansactions of the Kola Science Centre. Information technologies. Series 12. 2021. Vol. 12, no. 5. P. 75-90. http://dx/doi.org/10.37614/2307-5252.2021.5.12.007. Введение В рамках настоящих исследований для систематического решения задачи Constrained Clustering предложено использовать парадигму Constraint Programming. Предлагается решать задачу Constrained Clustering как задачу удовлетворения ограничений (Constraint Satisfaction Problem - CSP). Особенностью предложенного подхода является его ориентация на групповое принятие решений, то есть характеристики всех кластеризуемых объектов оцениваются несколькими экспертами. Основное внимание уделено вопросу уменьшения количества и упрощению ограничений задачи CSP в процессе её постановки. В качестве базовой модели для решения задачи Constrained Clustering была использована модель, описанная в [1]. В отличие от исследований, представленных в [1], в настоящей работе предполагается, что и кластер и кластеризуемый объект представляются как мультимножества, а расстояние ( dij ) между ними ищется с помощью метрик в пространстве мультимножеств Петровского [2]. Это позволяет расширить область применения методов решения задач кластеризации в пространствах большой размерности на базе Constrained Clustering на задачи группового принятия решений, и в случае необходимости, использовать соответствующие методы агрегации данных [2] В базовой модели существенная проблема состоит в организации эффективной обработки нечисловых ограничений, формализующих для пар объектов правила их отнесения к одному или различным классам, а именно ограничений вида: (d > D) ^ (G. фG ). Проблема заключается в том, что большое число подобных ограничений в совокупности не могут быть эффективно обработаны с помощью существующих сред программирования в ограничениях. 76