Локальный поиск для задачи о 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. Интуитивно понятно, что если расстояние между двумя элементами меньше, то они больше похожи друг на друга. Элементами обычно являются точки в некотором евклидовом пространстве [math]\displaystyle{ \mathcal{R}^d }[/math] высокой размерности. В качестве метрик расстояния чаще всего применяются евклидова метрика и расстояние Хэмминга, а также косинусная метрика, измеряющая угол между векторами, представляющими элементы.
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 \subseteq \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] удовлетворяет условию [math]\displaystyle{ |C| = k \; }[/math]. На этапе улучшения полагаем [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_0 \; }[/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 \Big( \frac{f(C_0)}{f(C_T)} \Big)}{\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-медианах
Первую эвристику локального поиска с доказуемой гарантией эффективности предложили Арья и др. [1]. Это «естественная эвристика с p заменами»: пусть имеется текущее множество центров [math]\displaystyle{ C_t \; }[/math] размера k; множество [math]\displaystyle{ \mathcal{E}_{t+1} }[/math] определяется следующим образом:
[math]\displaystyle{ \mathcal{E}_{t+1} = \{ (C_t \backslash \mathcal{A}) \cup \mathcal{B} }[/math], где [math]\displaystyle{ \mathcal{A} \subseteq C_t, \mathcal{B} \subseteq \mathcal{F} \backslash C_t, |\mathcal{A}| = |\mathcal{B}| \le p \} }[/math].
Вышеописанное обозначает простую замену не более чем p центров из [math]\displaystyle{ C_t \; }[/math] тем же количеством центров из [math]\displaystyle{ \mathcal{F} \backslash C_t }[/math]. Вспомним, что [math]\displaystyle{ |\mathcal{D}| = n }[/math] и [math]\displaystyle{ |\mathcal{F}| = m }[/math]. Очевидно, [math]\displaystyle{ |\mathcal{E}_t+1| \le (k(m - k))^p \le (km)^p }[/math]. Начальное множество [math]\displaystyle{ C_0 \; }[/math] выбирается произвольным образом. Значение p является параметром, от которого зависят время выполнения и коэффициент аппроксимации. Он выбирается константным, так что [math]\displaystyle{ |\mathcal{E}t| }[/math] является полиномом от m.
Теорема 1 ([1]). Эвристика с p заменами обеспечивает разрыв локальности [math]\displaystyle{ (3 + 2/p) + \varepsilon \; }[/math], а время выполнения составляет [math]\displaystyle{ O(nk(log(nD))/\varepsilon(mk)^p) \; }[/math]. Кроме того, для любого значения p существует экземпляр задачи о k-медианах, в которой эвристика с p заменами обеспечивает разрыв локальности, в точности равный (3 + 2/p).
Положив [math]\displaystyle{ p = 1 / \varepsilon \; }[/math], получим, что вышеописанная эвристика имеет коэффициент аппроксимации [math]\displaystyle{ 3 + \varepsilon \; }[/math] и время выполнения [math]\displaystyle{ \tilde{O}(n(mk)^{O(1/\varepsilon)}) }[/math].
Задача о размещении объектов
Поскольку в этой задаче уже нет ограничения на количество центров, этап локального улучшения требует соответствующей модификации. Были разработаны две эвристики локального поиска, обеспечивающие разрыв локальности [math]\displaystyle{ 3 + \varepsilon \; }[/math] за полиномиальное время.
Эвристика «добавление, удаление и замена», предложенная Кюном и Хамбургером [10], добавляет центр в [math]\displaystyle{ C_t \; }[/math], исключает центр из [math]\displaystyle{ C_t \; }[/math] либо заменяет центр из [math]\displaystyle{ C_t \; }[/math] центром из [math]\displaystyle{ \mathcal{F} \backslash C_t }[/math]. Начальное множество [math]\displaystyle{ C_0 \; }[/math] также выбирается произвольно.
[math]\displaystyle{ \mathcal{E}_{t + 1} = \{(C_t \backslash \mathcal{A}) \cup \mathcal{B}, }[/math] где [math]\displaystyle{ \mathcal{A} \subseteq C_t, \mathcal{B} \subseteq \mathcal{F} \backslash C_t, |\mathcal{A}| = 0, |\mathcal{B}| = 1, }[/math] либо [math]\displaystyle{ |\mathcal{A}| = 1, |\mathcal{B}| = 0, }[/math] либо [math]\displaystyle{ |\mathcal{A}| = 0, |\mathcal{B}| = 1 \}. }[/math]
Очевидно, [math]\displaystyle{ |\mathcal{E}_{t + 1}| = O(m^2) }[/math], что делает время выполнения полиномиальным от размера входных данных и значения [math]\displaystyle{ 1/ \varepsilon \; }[/math]. Коруполу, Плакстон и Раджамаран [9] показали, что эта эвристика обеспечивает разрыв локальности не более [math]\displaystyle{ 5 + \varepsilon \; }[/math]. Арья и др. [1] выполнили более строгий анализ, показав, что эвристика достигает разрыва локальности [math]\displaystyle{ 3 + \varepsilon \; }[/math] и что эта граница является точной в том смысле, что существуют экземпляры задачи, для которых разрыв локальности строго равен 3.
Эвристика «добавить один, удалить несколько», предложенная Чарикаром и Гухой [2], несколько сложнее. Она добавляет один объект и отбрасывает все объекты, которые становятся несущественными в новом решении.
[math]\displaystyle{ \mathcal{E}_{t + 1} = \{(C_t \cup \{ i \} ) \backslash I(i), }[/math] где [math]\displaystyle{ i \in \mathcal{F} \backslash C_t, I(i) \subseteq C_t \}. }[/math]
Множество I(i) вычисляется следующим образом. Обозначим за W множество элементов, расположенных ближе к i, чем к назначенным им центрам в [math]\displaystyle{ C_t \; }[/math]. При вычислении I(i) этими элементами можно пренебречь. Для каждого центра [math]\displaystyle{ s \in C_t \; }[/math] обозначим за [math]\displaystyle{ U_s \; }[/math] все элементы, назначенные s. Если [math]\displaystyle{ f_s + \sum_{j \in U_s \backslash W} d_j d(j, s) \gt \sum_{j \in U_s \backslash W} d_j d(j, i) }[/math], то дешевле удалить объект s и переназначить элементы из [math]\displaystyle{ U_s \backslash W \; }[/math] элементу i. В этом случае s размещается в I(i). Обозначим N = m + n. Таким образом, процедура вычисления I(i) требует O(N) времени, что делает общее время выполнения полиномиальным. Чарикар и Гуха [2] сформулировали следующую теорему.
Теорема 2 ([2]). Эвристика локального поиска, которая пытается добавить случайный центр [math]\displaystyle{ i \notin C_t \; }[/math] и удалить множество I(i), вычисляет [math]\displaystyle{ 3 + \varepsilon \; }[/math]-аппроксимацию с высокой вероятностью за [math]\displaystyle{ T = O(N \; log \; N(log \; N + 1/ \varepsilon)) }[/math] этапов улучшения, каждый из которых занимает O(N) времени.
Варианты с ограничением пропускной способности
Эвристики локального поиска также называются вариантами задач о k-медианах и о размещении объектов с ограничением пропускной способности. В этом варианте каждый возможный объект [math]\displaystyle{ i \in \mathcal{F} }[/math] может обслуживать не более [math]\displaystyle{ u_i \; }[/math] пользователей. В мягком варианте задачи о размещении объектов с ограничением пропускной способности в объекте [math]\displaystyle{ i \in \mathcal{F} }[/math] можно открыть [math]\displaystyle{ r_i \ge 0 \; }[/math] копий, так что стоимость объекта составит [math]\displaystyle{ f_i r_i \; }[/math], а количество обслуживаемых пользователей – не более [math]\displaystyle{ r_i u_i \; }[/math]. Задача оптимизации заключается в выборе значения [math]\displaystyle{ r_i \; }[/math] для каждого [math]\displaystyle{ i \in \mathcal{F} }[/math] таким образом, чтобы назначение пользователей центрам удовлетворяло ограничению на пропускную способность каждого центра, а стоимость открытия центров и назначения пользователей была минимальной. Для этого варианта Арья и др. [1] предложили эвристику локального поиска, обеспечивающую разрыв локальности [math]\displaystyle{ 4 + \varepsilon \; }[/math].
В жесткой версии задачи о размещении объектов с ограничением пропускной способности у объекта [math]\displaystyle{ i \in \mathcal{F} }[/math] имеется строгая граница [math]\displaystyle{ u_i \; }[/math] количества объектов, которые могут быть ему назначены. Для случая, когда пропускная способность [math]\displaystyle{ u_i \; }[/math] всех объектов одинакова (однородный случай), Коруполу, Плакстон и Раджамаран [9] представили изящную эвристику локального поиска, основанную на решении задачи о перевозках с промежуточными пунктами и обеспечивающую разрыв локальности [math]\displaystyle{ 8 + \varepsilon \; }[/math]. Чудак и Уильямсон [4] улучшили анализ этой эвристики, показав, что разрыв локальности составляет [math]\displaystyle{ 6 + \varepsilon \; }[/math]. В случае неоднородной пропускной способности требуется кардинально иной подход; Пал, Тардош и Уэкслер [14] представили эвристику локального поиска на базе сетевого потока, обеспечивающую разрыв локальности [math]\displaystyle{ 9 + \varepsilon \; }[/math]. Махдиан и Пал [12] улучшили эту границу до [math]\displaystyle{ 8 + \varepsilon \; }[/math] за счет обобщения нескольких техник локального поиска, описанных выше, с целью получения константного коэффициента аппроксимации для варианта задачи о размещении объектов, в котором стоимости объектов являются произвольными неубывающими функциями от потребностей обслуживаемых ими пользователей.
Родственные алгоритмические техники
Задачи о k-медианах и задачи о размещении объектов могут похвастаться долгой историей аппроксимации с достойными результатами. Начиная с первого исследования задачи о размещении объектов без ограничений на пропускную способность, выполненного Корнюжо, Немхаузером и Уолси [5], которые представили естественную релаксацию линейного программирования (LP) для этой задачи, было разработано несколько аппроксимаций с константными коэффициентами, использующих различные техники – таких как округление LP-решения [11, 15], локальный поиск [2, 9], прямо-двойственная схема [7] и двойное выравнивание [6]. Для задачи о k-медианах первая аппроксимация с константным коэффициентом 6 2/3 [3] была получена в результате округления естественной LP-релаксации при помощи обобщения техники фильтрации, предложенной в работе [11]. Результат был последовательно улучшен до 4-аппроксимации при помощи лагранжевой релаксации и прямо-двойственной схемы [2, 7], а затем до [math]\displaystyle{ \; (3 + \varepsilon) }[/math]-аппроксимации при помощи локального поиска [1].
Применение
Задача о размещении объектов многократно изучалась в работах, посвященных исследованию операций [5, 10]; она является базовым примитивом для нескольких задач о местонахождении ресурсов. Метрики k-медиан и k-средних широко применяются в кластеризации или обучении без учителя. Для алгоритмов кластеризации было предложено несколько улучшений эвристик по отношению к базовой схеме локального поиска: метод k-медоидов [8] выбирает случайную входную точку и заменяет ее одним из существующих центров, если такая замена приводит к улучшению; реализация CLARA [8] метода k-медоидов выбирает центры из случайной выборки входных точек для ускорения вычисления; эвристика CLARANS [13] осуществляет новую случайную выборку подходящих центров перед каждым этапом улучшения, что еще больше повышает эффективность алгоритма.
См. также
Литература
1. Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristics for k-median and facility location problems. SIAM J. Comput. 33(3), 544–562 (2004)
2. Charikar, M., Guha, S.: Improved combinatorial algorithms for facility location problems. SIAM J. Comput. 34(4), 803–824 (2005)
3. Charikar, M., Guha, S., Tardos, É., Shmoys, D.B.: A constant-factor approximation algorithmfor the k-median problem(extended abstract). In: STOC ’99: Proceedings of the thirty-first annual ACMsymposium on Theory of computing, pp. 1–10. Atlanta, May 1-4 1999
4. Chudak, F.A., Williamson, D.P.: Improved approximation algorithms for capacitated facility location problems. Math. Program. 102(2), 207–222 (2005)
5. Cornuejols, G., Nemhauser, G.L., Wolsey, L.A.: The uncapacitated facility location problem. In: Discrete Location Theory, pp. 119–171. Wiley, New York (1990)
6. Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM50(6), 795–824 (2003)
7. Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. J. ACM 48(2), 274–296 (2001)
8. Kaufman, L., Rousseeuw, P.J.: FindingGroups inData: An Introduction to Cluster Analysis.Wiley, New York (1990)
9. Korupolu, M.R., Plaxton, C.G., Rajaraman, R.: Analysis of a local search heuristic for facility location problems. In: SODA ’98: Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, pp. 1–10. San Francisco, USA; 25–26 January 1998
10. Kuehn, A.A., Hamburger, M.J.: A heuristic program for locating warehouses. Management Sci. 9(4), 643–666 (1963)
11. Lin, J.-H., Vitter, J.S.: "-approximations with minimum packing constraint violation (extended abstract). In: STOC ’92: Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, pp. 771–782. Victoria (1992)
12. Mahdian, M., Pál, M.: Universal facility location. In: European Symposium on Algorithms, pp. 409–421. Budapest, Hungary, September 16–19 2003
13. Ng, R.T., Han, J.: Efficient and effective clustering methods for spatial data mining. In: Proc. Symp. on Very Large Data Bases (VLDB), pp. 144–155. Santiago de Chile, 12–15 September 1994
14. Pál, M., Tardos, É., Wexler, T.: Facility location with nonuniform hard capacities. In: Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, pp. 329–338. Las Vegas, 14–17 October 2001
15. Shmoys, D.B., Tardos, É., and Aardal, K.: Approximation algorithms for facility location problems. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 265–274. El Paso, 4–6 May 1997