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

ограничениях, для выражения запросов, чтобы обнаруживать паттерны в Data Mining. Подход на основе сведения задачи Constrained Clustering к задаче выполнимости булевой функции ( SAT) предложен в [18] для кластерного анализа с 2 кластерами. Данный подход объединяет различные виды пользовательских ограничений: must-link, cannot-link, а также ограничения диаметра и разбиения. В статье [19] рассматривается подход к Constrained Clustering, основанный на целочисленном линейном программировании. В работе [20] разрабатывается точный подход для задачи Constrained Clustering с критерием минимизации внутрикластерной суммы квадратов, основанный на целочисленном линейном программировании. Среди средств оптимизации общего назначения, программирование в ограничениях является мощной парадигмой для решения задач комбинаторного поиска, которая основывается на широком спектре методов из искусственного интеллекта, информационных технологий и исследования операций. Основная идея программирования в ограничениях состоит в том, чтобы решать задачи путем наложения ограничений, которые должны быть удовлетворены при помощи решения. Главные принципы программирования в ограничениях это: 1) пользователи формулируют задачу декларативно, как задачу удовлетворения ограничений; 2) solver ищет решение путем удовлетворения ограничений и поиска. Программирование в ограничениях также реализует идею декларативного программирования. С точки зрения теории методы программирования в ограничениях можно разделить на три основные группы: 1. Методы распространения ограничений - суть этих методов состоит в уменьшении пространства поиска за полиномиальное время. Когда алгоритмы распространения ограничений останавливаются, достигнув некоторой неподвижной точки, то в дело вступают алгоритмы второй группы: 2. Алгоритмы поиска - прежде всего, это алгоритмы поиска «в глубину с возвратами», которые используют эвристики при разборе случаев. 3. Алгоритмы структурной декомпозиции задач удовлетворения ограничений. Методы этой группы предназначены для разбиения задачи либо на независимые, либо на слабо связанные задачи. Цель разбиения состоит в том, чтобы решать каждую из подзадач в отдельности, а затем комбинировать полученные решения. Чаще всего граф задачи преобразуют к дереву. Для деревьев есть доказанный быстродействующий алгоритм распространения ограничений. Программирование в ограничениях могло бы стать полезным инструментом для задач кластерного анализа с ограничениями, поскольку данный подход обладает такими преимуществами как: декларативность, которая дает возможность добавлять новые ограничения, и возможность находить оптимальное решение, удовлетворяющее всем ограничениям (если оно существует). Однако, по мнению авторов, данный подход не получил пока должного развития в области разработки высокоэффективных конструктивных методов решения задач Constrained Clustering. 123

RkJQdWJsaXNoZXIy MTUzNzYz