Локальный поиск для задачи о k-медианах и задачи о размещении объектов

Ключевые слова и синонимы

Метод k-медиан; метод k-средних; метод k-медоидов; задача о размещении объектов; локализация точки; задача о размещении складов; кластеризация

Постановка задачи

Кластеризация представляет собой разновидность обучения без учителя, при котором задача заключается в «обучении» полезным образцам на наборе данных [math]\displaystyle{ \mathcal{D} \; }[/math] размера n. Ее можно также рассматривать как схему сжатия данных, в которой большой набор данных представляется при помощи меньшего набора «представителей». Подобная схема характеризуется путем задания следующих параметров:

1. Метрика расстояния d между элементами набора данных. Эта метрика должна удовлетворять неравенству треугольника: d(i, j) [math]\displaystyle{ \le }[/math] d(j, k) + d(k, i) для любых трех элементов [math]\displaystyle{ i, j, k \in \mathcal{D} \; }[/math]. Кроме того, d(i, j) = d(j, i) для всех [math]\displaystyle{ i, j \in S \; }[/math], d(i, i) = 0. Интуитивно понятно, что если расстояние между двумя элементами меньше, то они больше похожи друг на друга. Элементами обычно являются точки в некотором евклидовом пространстве Rd высокой размерности. В качестве метрик расстояния чаще всего применяются евклидова метрика и расстояние Хэмминга, а также косинусная метрика, измеряющая угол между векторами, представляющими элементы.

2. Результатом (выходными данными) процесса кластеризации является разбиение данных. В данной главе рассматривается кластеризация на основе центров. В ней результатом является множество меньшего размера [math]\displaystyle{ C \subset \mathcal{R}^d }[/math], состоящее из центров, которые наилучшим образом представляют входное множество данных [math]\displaystyle{ S \subset \mathcal{R}^d }[/math]. Как правило, имеет место соотношение [math]\displaystyle{ |C| \ll |\mathcal{D}| }[/math]. Каждый элемент [math]\displaystyle{ j \in \mathcal{D} }[/math] отображается на ближайший центр или аппроксимируется ближайшим центром [math]\displaystyle{ i \in C \; }[/math], из чего следует d(i, j) [math]\displaystyle{ \le }[/math] d(i', j) для всех [math]\displaystyle{ i' \in C \; }[/math]. Обозначим за [math]\displaystyle{ \sigma: \mathbb{D} \to C }[/math] это отображение. Оно является интуитивно понятным, поскольку более близкие (схожие) элементы будут отображаться на один и тот же центр.

3. Мера качества кластеризации, зависящая от желаемого выходного результата. Существует несколько широко используемых мер для оценки качества кластеризации. Для каждой из мер кластеризации, описанных ниже, задача заключается в выборе такого C, что |C| = k и целевая функция f (C) минимизирована.

k-центр: f (C) = maxj2D d( j; _( j)).

k-медианы: f (C) = Pj2D d( j; _( j)).

k-средние: f (C) = Pj2D d( j; _( j))2 .

Все вышеупомянутые цели являются NP-СЛОЖНЫМИ для оптимизации в метрических пространствах общего вида d, что вызвало необходимость изучения эвристических и приближенных алгоритмов. Далее главным образом будет рассматриваться целевая функция на основе k-медиан. Алгоритмы аппроксимации для кластеризации на основе метода k-медиан разработаны для пространства d, являющегося неевклидовым метрическим пространством наиболее общего возможного вида. Совокупность F возможных местоположений центров задана в качестве начального условия, множество центров C ограничено C F. С точки зрения аппроксимации ограничение возможных центров конечным множеством F не является чрезмерно строгим: например, для оптимального решения, ограниченного F = D, его целевое значение не более чем в 2 раза превышает оптимальное значение, допускаемое при произвольном F. Обозначим |D| = n и |F| = m. Время выполнения построенной эвристики будет представлено полиномом от mn с параметром > 0. Метрическое пространство d теперь определяется над D [ F.

Родственной задачей для k-медиан является задача лагранжевой релаксации под названием «задача о размещении объектов». В этой задаче также имеется совокупность F возможных местоположений центров. Каждое местоположение i 2 F имеет стоимость ri. Задача заключается в выборе совокупности C F центров и построении отображения : S ! C элементов на центры, при котором следующая функция достигает минимума: f (C) =X

Задача о размещении объектов позволяет эффективно избавиться от жесткой границы k на количество центров в методе k-медиан, заменяя его компонентом стоимости центров Pi2C ri в целевой функции и тем самым превращая задачу в лагранжеву релаксацию метода k-медиан. Заметим, что стоимость центров в данном случае может быть неоднородной.

Результаты аппроксимации задачи о k-медианах и задачи о размещении объектов можно распространить на взвешенный случай, В котором каждому элементу j 2 D разрешается иметь неотрицательный вес wj. В формулировке целевой функции f (C) компонент Pj2D d( j; _( j)) заменяется на Pj2D wj _ d( j; _( j)). Взвешенный случай особенно релевантен для задачи о размещении объектов, в которой веса элементов обозначают спрос пользователей на ресурс, а центры – местоположение ресурса. Далее термины «элементы» и пользователи» будут в равной степени использоваться для обозначения членов множества D.

Основные результаты

Основным методом решения задач k-медиан и размещения объектов является класс эвристик локального поиска, выполняющихся посредством поэтапных «локальных улучшений». На каждом этапе t эвристика поддерживает множество центров Ct. В задаче о k-медианах эта совокупность удовлетворяет условию |Ct| = k. На этапе локального улучшения вначале генерируется совокупность решений Et+1 из Ct . Это выполняется таким образом, что |Et+1| оказывается полиномиальным относительно размера входных данных. Кроме того, в задаче о k-медианах каждый элемент C 2 Et+1 удовлетворяет условию |C| = k. На этапе улучшения полагаем Ct+1 = argminC2Et+1 f (C). Для предварительно заданного параметра " > 0 итерации улучшений останавливаются на первом этапе T, для которого выполняется f (CT) _ (1 _ ") f (CT_1).

Основными проблемами разработки являются конкретизация начального множества C0 и построение Et+1 из Ct . Основными проблемами анализа являются ограничение количества этапов T до завершения работы алгоритма и качество финального решения f(CT) по отношению к оптимальному решению f (C_). Соотношение ( f (CT ))/( f (C_)) называется «разрывом локальности» эвристики.

Поскольку каждый этап улучшения уменьшает значение решения по меньшей мере на коэффициент (1 _ "), время выполнения в пересчете на этапы улучшения задается следующим выражением (здесь D – отношение между самым большим и самым маленьким расстояниями в метрическом пространстве над D [ F). T _ log1/(1_") _ f (C0)

являющееся полиномиальным относительно размера входных данных. На каждом этапе улучшения требуется вычисление f (C) для C 2 Et. Оно является полиномиальным относительно размера входных данных, поскольку jEt j предполагается полиномиальным.

Задача о k-медианах