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

DOI: 10.25702/KSC.2307-5252.2019.9.116-125 УДК 004.832 А. А. Зуенко, О. Н. Зуенко Институт информатики и математического моделирования ФИЦ КНЦ РАН ПРИМЕНЕНИЕ МЕТОДОВ ДЕКЛАРАТИВНОГО ПРОГРАММИРОВАНИЯ В ЗАДАЧАХ CONSTRAINED CLUSTERING* Аннотация Анализ методов решения задач кластеризации с частичным привлечением учителя (Constrained Clustering или Semi Supervised Clustering) показал, что большинство из них являются приближенными. Точные методы технологии программирования в ограничениях позволяют решать задачи комбинаторного поиска, характеризующиеся большой размерностью. Однако, данные средства всё ещё редко применяются в задачах Constrained Clustering. Сделан вывод о перспективности разработки новых методов удовлетворения ограничений для различных постановок задач Constrained Clustering. Ключевые слова: Кластерный анализ, кластеризация с частичным применением учителя, декларативное программирование, программирование в ограничениях. A. A.Zuenko, О. N.Zuenko APPLICATION OF DECLARATIVE PROGRAMMING METHODS IN THE CONSTRAINED CLUSTERING PROBLEMS Abstract An analysis of the methods of solving Semi Supervised Clustering(Constrained Clustering) problems showed that most of them are approximate. Exact methods of constraint programming technology allow solving combinatorial search problems of large dimension. However, these tools are still rarely used in Constrained Clustering problems. The conclusion is drawn on the prospects of developing new constraint satisfaction methods for various statements of Constrained Clustering problem. Keywords: Cluster analysis, semi supervised clustering, declarative programming, constraint programming. Введение Задача кластеризации относится к задачам комбинаторного поиска. Коснемся несколько более подробно задач комбинаторного поиска. Рассмотрим задачу подбора правильной комбинации для кодового замка. Она решается только прямым последовательным перебором всех возможных комбинаций. Это один из редких примеров задач комбинаторного поиска, для которых сложно предложить какой-либо метод ускорения. Даже уже при 1000 окошках для ввода цифр она порождает Ю1000 комбинаций, что под силу перебрать не каждому компьютеру. Если же предположить, что нам об этих комбинациях что-либо известно, например, комбинация — это год рождения одного из членов семьи, или известны некоторые цифры комбинации или свойства цифр, то задача подбора существенно упрощается. Работа выполнена в рамках темы НИР «Развитие методологии построения интеллектуальных мультипредметных систем информационной поддержки регионального развития на примере территорий Арктической зоны Российской Федерации (АЗРФ)» (№ 0226-2019-0036). 116