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

задает верхнюю границу у на диаметр кластеров, таким образом, расстояние между любой парой точек, принадлежащих одному и тому же кластеру, должно быть не более значения у . Это ограничение может рассматриваться как конъюнкция ограничений cannot-link между всеми парами объектов с расстоянием, превышающим у . Методы решения задач Constrained Clustering За последнее десятилетие было выполнено много работ, направленных на расширение классических алгоритмов для обработки ограничений must-link и cannot-link, например, расширение для COBWEB [11], k-means [12, 13], иерархической кластеризации [14] и т.д. Методы решения задач Constrained Clustering получаются при помощи модификации базовых методов кластеризации. Можно выделить три вида таких модификаций. 1. Модификация формул расстояния. 2. Модификация целевой функции, которая должна учитывать штрафы за нарушение ограничений must-link и cannot-link. 3. Модификация стратегии поиска. Однако, общего решения, чтобы расширить традиционные алгоритмы для различных типов ограничений, не существует. Далее рассматривается еще один подход, который может быть применен для решения задач Constrained Clustering. Данный подход может являться основой для разработки высокоэффективных методов систематического поиска. Методы декларативного программирования в задачах Constrained Clustering Существующие к данному моменту методы Constrained Clustering являются развитием методов классической кластеризации и наследуют их недостатки. Большинство данных методов это методы локального поиска, т.е. они позволяют часто найти лишь локальный экстремум. Дело в том, что пространство поиска в задачах кластеризации достаточно большое, и до недавнего времени не существовало технологий систематического обхода пространства поиска такой размерности. В 90-х годах появились мощные SAT solvers, а затем и технология программирования в ограничениях. Эта технология позволяем систематически исследовать куда большие пространства поиска, чем ранее. В связи с этим, в последнее время возрос интерес к разработке декларативного подхода для Data Mining [15], в том числе задачи Constrained Clustering. Декларативный подход, возможно, менее эффективен, нежели классические алгоритмы, для специфических задач, зато он более гибок и носит более общий характер, а также существенно упрощает интеграцию новых знаний в задачу. Декларативный подход включает методы программирования в ограничениях, методы сведения задачи к задаче пропозициональной выполнимости (Boolean satisfiability), методы целочисленного линейного программирования, методы логического программирования. Кроме того, именно в рамках данного подхода стало возможно задачу Constrained Clustering решать при помощи конструктивного (систематического) перебора пространства поиска. В [16] предлагается подход в рамках программирования в ограничениях для извлечения набора ^-паттернов. В [17] представлен язык, основанный на 122