Локальный поиск для задачи о 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: \mathcal{D} \to C }[/math] это отображение. Оно является интуитивно понятным, поскольку более близкие (схожие) элементы будут отображаться на один и тот же центр.

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

k-центр: [math]\displaystyle{ f(C) = max_{j \in \mathcal{D} } \; d(j, \sigma (j)) }[/math].

k-медианы: [math]\displaystyle{ f(C) = \sum_{j \in \mathcal{D}} \; d(j, \sigma (j)) }[/math].

k-средние: [math]\displaystyle{ f(C) = \sum_{j \in \mathcal{D}} \; d(j, \sigma (j))^2 }[/math].

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

Родственной для задачи о k-медианах является задача лагранжевой релаксации под названием «задача о размещении объектов». В этой задаче также имеется совокупность [math]\displaystyle{ \mathcal{F} }[/math] возможных местоположений центров. Каждое местоположение [math]\displaystyle{ i \in \mathcal{F} }[/math] имеет стоимость [math]\displaystyle{ r_i \; }[/math]. Задача заключается в выборе совокупности [math]\displaystyle{ C \subseteq \mathcal{F} }[/math] центров и построении отображения [math]\displaystyle{ \sigma: S \to C }[/math] элементов на центры, при котором следующая функция достигает минимума:

[math]\displaystyle{ f(C) = \sum_{j \in \mathcal{D}} d(j, \sigma(j)) + \sum_{i \in C} r_i }[/math].

Задача о размещении объектов позволяет эффективно избавиться от жесткой границы k на количество центров в методе k-медиан, заменяя его компонентом стоимости центров [math]\displaystyle{ \sum_{i \in C} r_i }[/math] в целевой функции и тем самым превращая задачу в лагранжеву релаксацию метода k-медиан. Заметим, что стоимость центров в данном случае может быть неоднородной.

Результаты аппроксимации задачи о k-медианах и задачи о размещении объектов можно распространить на взвешенный случай, В котором каждому элементу [math]\displaystyle{ j \in \mathcal{D} }[/math] разрешается иметь неотрицательный вес [math]\displaystyle{ w_j \; }[/math]. В формулировке целевой функции [math]\displaystyle{ f(C) \; }[/math] компонент [math]\displaystyle{ \sum_{j \in \mathcal{D}} d(j, \sigma(j)) }[/math] заменяется на [math]\displaystyle{ \sum_{j \in \mathcal{D}} w_j \cdot d(j, \sigma(j)) }[/math]. Взвешенный случай особенно релевантен для задачи о размещении объектов, в которой веса элементов обозначают спрос пользователей на ресурс, а центры – местоположение ресурса. Далее термины «элементы» и пользователи» будут в равной степени использоваться для обозначения членов множества [math]\displaystyle{ \mathcal{D} }[/math].

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

Основным методом решения задач k-медиан и размещения объектов является класс эвристик локального поиска, выполняющихся посредством поэтапных «локальных улучшений». На каждом этапе t эвристика поддерживает множество центров [math]\displaystyle{ C_t \; }[/math]. В задаче о k-медианах эта совокупность удовлетворяет условию [math]\displaystyle{ |C_t| = k \; }[/math]. На этапе локального улучшения вначале генерируется совокупность решений [math]\displaystyle{ \mathcal{E}_{t+1} }[/math] из [math]\displaystyle{ C_t \; }[/math]. Это выполняется таким образом, что [math]\displaystyle{ |\mathcal{E}_{t+1}| }[/math] оказывается полиномиальным относительно размера входных данных. Кроме того, в задаче о k-медианах каждый элемент [math]\displaystyle{ C \in \mathcal{E}_{t+1} }[/math] удовлетворяет условию |C| = k. На этапе улучшения полагаем [math]\displaystyle{ C_{t+1} = argmin_{C \in \mathcal{E}_{t+1}} f(C) }[/math]. Для предварительно заданного параметра [math]\displaystyle{ \varepsilon \gt 0 \; }[/math] итерации улучшений останавливаются на первом этапе T, для которого выполняется [math]\displaystyle{ f(C_T) \ge (1 - \varepsilon) f(C_{T - 1}) \; }[/math].

Основными проблемами разработки являются конкретизация начального множества [math]\displaystyle{ C' \; }[/math] и построение [math]\displaystyle{ \mathcal{E}_{t+1} }[/math] из [math]\displaystyle{ C_t \; }[/math]. Основными проблемами анализа являются ограничение количества этапов T до завершения работы алгоритма и качество финального решения [math]\displaystyle{ f(C_T) \; }[/math] по отношению к оптимальному решению [math]\displaystyle{ f(C^*) \; }[/math]. Соотношение [math]\displaystyle{ (f(C_T))/( f(C^*)) \; }[/math] называется «разрывом локальности» эвристики.

Поскольку каждый этап улучшения уменьшает значение решения по меньшей мере на коэффициент [math]\displaystyle{ (1 - \varepsilon) \; }[/math], время выполнения в пересчете на этапы улучшения задается следующим выражением (здесь D – отношение между самым большим и самым маленьким расстояниями в метрическом пространстве над [math]\displaystyle{ \mathcal{D} \cup \mathcal{F} }[/math]):

[math]\displaystyle{ T \le log_{1 / (1 - \varepsilon)} \bigg( \frac{f(C_0)}{f(C_T)} \bigg) \le \frac{log \bigg( \frac{f(C_0)}{f(C_T)} \bigg)}{\varepsilon} \le \frac{log(nD)}{\varepsilon} }[/math],

являющееся полиномиальным относительно размера входных данных. На каждом этапе улучшения требуется вычисление [math]\displaystyle{ f(C) \; }[/math] для [math]\displaystyle{ C \in \mathcal{E}_t }[/math]. Оно является полиномиальным относительно размера входных данных, поскольку [math]\displaystyle{ |\mathcal{E}_t| }[/math] предполагается полиномиальным.

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