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

пройденных состояний. Их существенным недостатком является то, что они сильно зависят от выбора начального состояния. К неиерархическим эвристическим алгоритмам можно отнести методы k-means [3], к-median, k-medoid, метод спектральной кластеризации, метод FTP {Furthest Point First ) [4]. Далее перечислим наиболее популярные точные методы решения задач неиерархической кластеризации. Это, прежде всего, теоретико-графовые методы и метод ветвей и границ. Теоретико-графовые методы сводят задачу кластеризации к задаче раскраски графа. Наиболее известный алгоритм, относящийся к данному классу, разработан для критерия минимального диаметра [5] Bench&bound - метод ветвей и границ. Это целый класс методов, которые отличаются критерием кластеризации. В зависимости от этого критерия, выстраивается процедура обхода дерева поиска, а именно, строится своя функция оценки (стоимостная функция), позволяющая отсекать заранее неперспективные ветви дерева поиска [6, 7]. Задача Constrained Clustering Задача классического кластерного анализа — это задача разбиения множества объектов на классы, когда какая-либо априорная информация о принадлежности объектов этим классам отсутствует. Классификация — это задача отнесения предъявляемых объектов к заранее указанным классам, сопровождаемая этапом предварительного обучения. На этапе обучения для некоторых объектов (объектов обучающей выборки) указывается, каким классам они принадлежат. Выводится правило классификации. Задача Constrained Clustering использует некоторые фоновые знания из предметной области. Количество классов и сами классы неизвестны, но для некоторых пар объектов известно, например, что они попадают или не попадают в один кластер. Поэтому задача Constrained Clustering также называется задачей кластеризации с частичным привлечением учителя ( semi-supervised clustering). Основная идея состоит в том, что при кластеризации хорошо бы использовать фоновые или базовые знания из предметной области. Эти базовые знания предложено представлять в виде пользовательских ограничений. В таких задачах выделяют два вида пользовательских ограничений: 1. Ограничения на кластеры ( cluster-level constraints), указывающие требования к кластерам. 2. Ограничения на объекты кластеров ( instance-level constraints), уточняющие требования к парам конкретных объектов. Примерами ограничений на кластеры является минимальная/максимальная населенность кластера, средняя населенность кластера (отношение минимума к максимуму) - это ограничение говорит о том, что кластеры должны быть примерно одного размера. Наиболее интересны ограничения на объекты кластеров. Выделяют два вида таких ограничений [8]: must-link и cannot-link. Данные ограничения также называются попарными. Ограничение must-link означает, что два объекта должны быть в одном кластере. A cannot-link означает, что два объекта должны быть в разных кластерах. 120