Применение smart-таблиц и оценок целевой функции для снижения размерности и ускорения решения задач Constrained Clustering

Аннотация

В статье представлен комплексный подход к точному решению задач Constrained Clustering, то есть задач кластеризации, предполагающих анализ, помимо матрицы расстояний, фоновых знаний о необходимости/недопустимости вхождения некоторых объектов в те или иные кластеры. Подход реализован в рамках парадигмы программирования в ограничениях (Constraint Programming), ориентированной на построение процедур систематического поиска (процедур обхода дерева поиска) для решения сложных комбинаторных задач. При этом, вся исходная информация о задаче выражается с помощью ограничений, то есть качественных и количественных зависимостей. Существенная сложность заключается в том, что в современных средах и библиотеках программирования в ограничениях обработка качественных ограничений, которыми, в частности, являются правила отнесения объектов к одному или различным кластерам, производится недостаточно эффективно. Таким образом, представляется актуальной разработка способов ускорения обработки подобных ограничений. В статье предлагается представлять и обрабатывать качественные ограничения в форме табличных ограничений нового типа, а именно smart-таблиц D-типа. Для smart-таблиц D-типа разработаны высокоэффективные процедуры вывода на ограничениях, осуществляющие раннее отсечение неперспективных ветвей дерева поиска. Другое направление работ, которое активно развивается в настоящих исследованиях, связано с уменьшением количества ограничений, используемых для представления задачи, и с упрощением их вида. Предлагается генерировать ограничения лишь для некоторых пар объектов, основываясь на интервальной оценке для оптимального значения критерия кластеризации. Для получения данной оценки используется ранее предложенный авторами метод иерархической кластеризации, который позволяет анализировать ограничения на комбинации пар объектов внутри кластера. Предложенный подход позволяет находить все варианты разбиений, обеспечивающие глобальный оптимум целевой функции для рассматриваемых задач Constrained Clustering высокой размерности. Разработанный подход проиллюстрирован на примере задачи выявления зон участка горного массива с различной степенью сейсмической активности.