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

Анализ знаний из предметной области способен ускорить процесс получения решения задач комбинаторного поиска. Этот вывод кажется банальным, но если рассмотреть классическую задачу кластерного анализа, то там учет фоновых знаний не предусмотрен. Исходными данными в задаче классического кластерного анализа является матрица расстояний между кластеризуемыми объектами, которая получается из объекто-признаковой таблицы. Далее свойства объектов не анализируются. На основании введенного расстояния объекты раскладываются (разбиваются) на кластеры, в один кластер попадают наиболее близкие друг другу объекты. Однако, часто отнесение двух объектов в один кластер только лишь на основе метрики является семантически некорректной операцией. Таким образом, основным недостатком большинства существующих методов кластеризации является невозможность учитывать пользовательские ограничения на то, какие объекты обязательно должны/не должны попадать в один кластер. В статье рассматривается подход к кластеризации, когда при отнесении объектов к одному или различным кластерам анализируются не только расстояния между объектами, но и значения их признаков. Кроме того, чтобы лучше смоделировать задачу и снизить ее сложность, могут быть добавлены пользовательские ограничения. В этом случае задача кластеризации становится задачей Constrained Clustering, целью которой является получение кластеров, удовлетворяющих не только критерию кластеризации, но и пользовательским ограничениям. В статье представлен обзор методов Constrained Clustering, а также необходимые сведения из классического кластерного анализа. Задача кластеризации Рассмотрим набор данных из п объектов О = {о,;.. } . Каждый объект описывается значениями р атрибутов, также называемых переменными. Обозначим оу значение j -го атрибута объекта о; . Большинство алгоритмов кластеризации опираются не на анализ свойств объектов, а используют только таблицы расстояний между объектами. Пусть С1;С2;...;Ск - подмножества множества О . Тогда {С1;С2;...;Ск} является разбиением О на к кластеров, если для всех с е |1 ;2 ;.. ,;к} выполняется: 1. Се * 0 ; 2. ( J Сс=0; С 3. с ф с',Сс С\Сс, = 0 . Предположим, что имеется мера различия между любыми двумя объектами о і: о , е О , которую обозначим d tj. Мера различия d tj обычно рассчитывается с использованием метрики расстояния, определенной в пространстве атрибутов. 117