4430
правок
Локальный поиск для задачи о k-медианах и задачи о размещении объектов: различия между версиями
Материал из WEGA
Локальный поиск для задачи о k-медианах и задачи о размещении объектов (посмотреть исходный код)
Версия от 13:53, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| (не показано 30 промежуточных версий этого же участника) | |||
| Строка 5: | Строка 5: | ||
Кластеризация представляет собой разновидность ''обучения без учителя'', при котором задача заключается в «обучении» полезным образцам на наборе данных <math>\mathcal{D} \;</math> размера n. Ее можно также рассматривать как схему сжатия данных, в которой большой набор данных представляется при помощи меньшего набора «представителей». Подобная схема характеризуется путем задания следующих параметров: | Кластеризация представляет собой разновидность ''обучения без учителя'', при котором задача заключается в «обучении» полезным образцам на наборе данных <math>\mathcal{D} \;</math> размера n. Ее можно также рассматривать как схему сжатия данных, в которой большой набор данных представляется при помощи меньшего набора «представителей». Подобная схема характеризуется путем задания следующих параметров: | ||
1. Метрика ''расстояния'' '''d''' между элементами набора данных. Эта метрика должна удовлетворять неравенству треугольника: | 1. Метрика ''расстояния'' '''d''' между элементами набора данных. Эта метрика должна удовлетворять неравенству треугольника: '''d'''(i, j) <math>\le</math> '''d'''(j, k) + '''d'''(k, i) для любых трех элементов <math>i, j, k \in \mathcal{D} \;</math>. Кроме того, '''d'''(i, j) = '''d'''(j, i) для всех <math>i, j \in S \;</math>, '''d'''(i, i) = 0. Интуитивно понятно, что если расстояние между двумя элементами меньше, то они больше похожи друг на друга. Элементами обычно являются точки в некотором евклидовом пространстве <math>\mathcal{R}^d</math> высокой размерности. В качестве метрик расстояния чаще всего применяются евклидова метрика и расстояние Хэмминга, а также косинусная метрика, измеряющая угол между векторами, представляющими элементы. | ||
2. Результатом (выходными данными) процесса кластеризации является разбиение данных. В данной главе рассматривается кластеризация на основе центров. В ней результатом является множество меньшего размера C | 2. Результатом (выходными данными) процесса кластеризации является разбиение данных. В данной главе рассматривается кластеризация ''на основе центров''. В ней результатом является множество меньшего размера <math>C \subset \mathcal{R}^d</math>, состоящее из ''центров'', которые наилучшим образом представляют входное множество данных <math>S \subset \mathcal{R}^d</math>. Как правило, имеет место соотношение <math>|C| \ll |\mathcal{D}|</math>. Каждый элемент <math>j \in \mathcal{D}</math> ''отображается'' на ближайший центр или ''аппроксимируется'' ближайшим центром <math>i \in C \;</math>, из чего следует '''d'''(i, j) <math>\le</math> '''d'''(i', j) для всех <math>i' \in C \;</math>. Обозначим за <math>\sigma: \mathcal{D} \to C</math> это отображение. Оно является интуитивно понятным, поскольку более близкие (схожие) элементы будут отображаться на один и тот же центр. | ||
3. Мера качества кластеризации, зависящая от желаемого выходного результата. Существует несколько широко используемых мер для оценки качества кластеризации. Для каждой из мер кластеризации, описанных ниже, задача заключается в выборе такого C, что |C| = k и целевая функция f (C) минимизирована. | 3. Мера ''качества'' кластеризации, зависящая от желаемого выходного результата. Существует несколько широко используемых мер для оценки качества кластеризации. Для каждой из мер кластеризации, описанных ниже, задача заключается в выборе такого C, что |C| = k и целевая функция f(C) минимизирована. | ||
k-центр: f (C) = | '''k-центр''': <math>f(C) = max_{j \in \mathcal{D} } \; d(j, \sigma (j))</math>. | ||
k-медианы: f (C) = | '''k-медианы''': <math>f(C) = \sum_{j \in \mathcal{D}} \; d(j, \sigma (j))</math>. | ||
k-средние: f (C) = | '''k-средние''': <math>f(C) = \sum_{j \in \mathcal{D}} \; d(j, \sigma (j))^2</math>. | ||
Все вышеупомянутые цели являются NP-сложными для оптимизации в метрических пространствах общего вида '''d''', что привело к необходимости изучения эвристических и приближенных алгоритмов. Далее главным образом будет рассматриваться целевая функция на основе k-медиан. Аппроксимационные алгоритмы для кластеризации на основе метода k-медиан разработаны для метрического пространства '''d''' общего вида, возможно, являющегося неевклидовым. Совокупность <math>\mathcal{F}</math> возможных местоположений центров задана в качестве начального условия, множество центров C ограничено <math>C \subseteq \mathcal{F}</math>. С точки зрения аппроксимации ограничение возможных центров конечным множеством <math>\mathcal{F}</math> не является чрезмерно строгим: например, для оптимального решения, ограниченного <math>\mathcal{F} = \mathcal{D}</math>, целевое значение не более чем в 2 раза превышает оптимальное значение при произвольном <math>\mathcal{F}</math>. Обозначим <math>|\mathcal{D}| = n</math> и <math>|\mathcal{F}| = m</math>. Время выполнения построенной эвристики будет представлено полиномом от mn с параметром <math>\varepsilon > 0 \;</math>. Метрическое пространство '''d''' теперь определяется над <math>\mathcal{D} \cup \mathcal{F}</math>. | |||
Родственной для задачи о k-медианах является задача лагранжевой релаксации под названием «[[задача о размещении объектов]]». В этой задаче также имеется совокупность <math>\mathcal{F}</math> возможных местоположений центров. Каждое местоположение <math>i \in \mathcal{F}</math> имеет стоимость <math>r_i \;</math>. Задача заключается в выборе совокупности <math>C \subseteq \mathcal{F}</math> центров и построении отображения <math>\sigma: S \to C</math> элементов на центры, при котором следующая функция достигает минимума: | |||
<math>f(C) = \sum_{j \in \mathcal{D}} d(j, \sigma(j)) + \sum_{i \in C} r_i</math>. | |||
Результаты аппроксимации задачи о k-медианах и задачи о размещении объектов можно распространить на взвешенный случай, | Задача о размещении объектов позволяет эффективно избавиться от жесткой границы k на количество центров в методе k-медиан, заменяя его компонентом стоимости центров <math>\sum_{i \in C} r_i</math> в целевой функции и тем самым превращая задачу в лагранжеву релаксацию метода k-медиан. Заметим, что стоимость центров в данном случае может быть неоднородной. | ||
Результаты аппроксимации задачи о k-медианах и задачи о размещении объектов можно распространить на взвешенный случай, в котором каждому элементу <math>j \in \mathcal{D}</math> разрешается иметь неотрицательный вес <math>w_j \;</math>. В формулировке целевой функции <math>f(C) \;</math> компонент <math>\sum_{j \in \mathcal{D}} d(j, \sigma(j))</math> заменяется на <math>\sum_{j \in \mathcal{D}} w_j \cdot d(j, \sigma(j))</math>. Взвешенный случай особенно релевантен для задачи о размещении объектов, в которой веса элементов обозначают спрос пользователей на ресурс, а центры – местоположение ресурса. Далее термины «элементы» и «пользователи» будут в равной степени использоваться для обозначения членов множества <math>\mathcal{D}</math>. | |||
== Основные результаты == | == Основные результаты == | ||
Основным методом решения задач k-медиан и размещения объектов является класс эвристик локального поиска, выполняющихся посредством поэтапных «локальных улучшений». На каждом этапе t эвристика поддерживает множество центров | Основным методом решения задач k-медиан и размещения объектов является класс эвристик локального поиска, выполняющихся посредством поэтапных «локальных улучшений». На каждом этапе t эвристика поддерживает множество центров <math>C_t \;</math>. В задаче о k-медианах эта совокупность удовлетворяет условию <math>|C_t| = k \;</math>. На этапе локального улучшения вначале генерируется совокупность решений <math>\mathcal{E}_{t+1}</math> из <math>C_t \;</math>. Это выполняется таким образом, что <math>|\mathcal{E}_{t+1}|</math> оказывается полиномиальным относительно размера входных данных. Кроме того, в задаче о k-медианах каждый элемент <math>C \in \mathcal{E}_{t+1}</math> удовлетворяет условию <math>|C| = k \;</math>. На этапе улучшения полагаем <math>C_{t+1} = argmin_{C \in \mathcal{E}_{t+1}} f(C)</math>. Для предварительно заданного параметра <math>\varepsilon > 0 \;</math> итерации улучшений останавливаются на первом этапе T, для которого выполняется соотношение <math>f(C_T) \ge (1 - \varepsilon) f(C_{T - 1}) \;</math>. | ||
Основными проблемами разработки являются конкретизация начального множества <math>C_0 \;</math> и построение <math>\mathcal{E}_{t+1}</math> из <math>C_t \;</math>. Основными проблемами анализа являются ограничение количества этапов T до завершения работы алгоритма и качество финального решения <math>f(C_T) \;</math> по отношению к оптимальному решению <math>f(C^*) \;</math>. Соотношение <math>(f(C_T))/( f(C^*)) \;</math> называется «разрывом локальности» эвристики. | |||
Поскольку каждый этап улучшения уменьшает значение решения по меньшей мере на коэффициент <math>(1 - \varepsilon) \;</math>, время выполнения в пересчете на этапы улучшения задается следующим выражением (здесь D – отношение между самым большим и самым маленьким расстояниями в метрическом пространстве над <math>\mathcal{D} \cup \mathcal{F}</math>): | |||
<math>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>, | |||
являющееся полиномиальным относительно размера входных данных. На каждом этапе улучшения требуется вычисление f (C) для C | являющееся полиномиальным относительно размера входных данных. На каждом этапе улучшения требуется вычисление <math>f(C) \;</math> для <math>C \in \mathcal{E}_t</math>. Оно является полиномиальным относительно размера входных данных, поскольку <math>|\mathcal{E}_t|</math> предполагается полиномиальным. | ||
'''Задача о k-медианах''' | '''Задача о k-медианах''' | ||
Первую эвристику локального поиска с доказуемой гарантией эффективности предложили Арья и др. [1]. Это «''естественная эвристика с p заменами''»: пусть имеется текущее множество центров <math>C_t \;</math> размера k; множество <math>\mathcal{E}_{t+1}</math> определяется следующим образом: | |||
<math>\mathcal{E}_{t+1} = \{ (C_t \backslash \mathcal{A}) \cup \mathcal{B}</math>, где <math>\mathcal{A} \subseteq C_t, \mathcal{B} \subseteq \mathcal{F} \backslash C_t, |\mathcal{A}| = |\mathcal{B}| \le p \}</math>. | |||
Вышеописанное обозначает простую замену не более чем p центров из <math>C_t \;</math> тем же количеством центров из <math>\mathcal{F} \backslash C_t</math>. Вспомним, что <math>|\mathcal{D}| = n</math> и <math>|\mathcal{F}| = m</math>. Очевидно, <math>|\mathcal{E}_t+1| \le (k(m - k))^p \le (km)^p</math>. Начальное множество <math>C_0 \;</math> выбирается произвольным образом. Значение p является параметром, от которого зависят время выполнения и коэффициент аппроксимации. Он выбирается константным, так что <math>|\mathcal{E}t|</math> является полиномом от m. | |||
'''Теорема 1 ([1]). Эвристика с p заменами обеспечивает разрыв локальности <math>(3 + 2/p) + \varepsilon \;</math>, а время выполнения составляет <math>O(nk(log(nD))/\varepsilon(mk)^p) \;</math>. Кроме того, для любого значения p существует экземпляр задачи о k-медианах, в которой эвристика с p заменами обеспечивает разрыв локальности, в точности равный (3 + 2/p).''' | |||
Положив <math>p = 1 / \varepsilon \;</math>, получим, что вышеописанная эвристика имеет коэффициент аппроксимации <math>3 + \varepsilon \;</math> и время выполнения <math>\tilde{O}(n(mk)^{O(1/\varepsilon)})</math>. | |||
'''Задача о размещении объектов''' | |||
Поскольку в этой задаче уже нет ограничения на количество центров, этап локального улучшения требует соответствующей модификации. Были разработаны две эвристики локального поиска, обеспечивающие разрыв локальности <math>3 + \varepsilon \;</math> за полиномиальное время. | |||
Эвристика «''добавление, удаление и замена''», предложенная Кюном и Хамбургером [10], добавляет центр в <math>C_t \;</math>, исключает центр из <math>C_t \;</math> либо заменяет центр из <math>C_t \;</math> центром из <math>\mathcal{F} \backslash C_t</math>. Начальное множество <math>C_0 \;</math> также выбирается произвольно. | |||
<math>\mathcal{E}_{t + 1} = \{(C_t \backslash \mathcal{A}) \cup \mathcal{B},</math> где <math>\mathcal{A} \subseteq C_t, \mathcal{B} \subseteq \mathcal{F} \backslash C_t, |\mathcal{A}| = 0, |\mathcal{B}| = 1,</math> либо <math>|\mathcal{A}| = 1, |\mathcal{B}| = 0,</math> либо <math>|\mathcal{A}| = 0, |\mathcal{B}| = 1 \}.</math> | |||
Очевидно, <math>|\mathcal{E}_{t + 1}| = O(m^2)</math>, что делает время выполнения полиномиальным от размера входных данных и значения <math>1/ \varepsilon \;</math>. Коруполу, Плакстон и Раджамаран [9] показали, что эта эвристика обеспечивает разрыв локальности не более <math>5 + \varepsilon \;</math>. Арья и др. [1] выполнили более строгий анализ, показав, что эвристика достигает разрыва локальности <math>3 + \varepsilon \;</math> и что эта граница является точной в том смысле, что существуют экземпляры задачи, для которых разрыв локальности строго равен 3. | |||
Эвристика «''добавить один, удалить несколько''», предложенная Чарикаром и Гухой [2], несколько сложнее. Она добавляет один объект и отбрасывает все объекты, которые становятся несущественными в новом решении. | |||
<math>\mathcal{E}_{t + 1} = \{(C_t \cup \{ i \} ) \backslash I(i),</math> где <math>i \in \mathcal{F} \backslash C_t, I(i) \subseteq C_t \}.</math> | |||
Множество I(i) вычисляется следующим образом. Обозначим за W множество элементов, расположенных ближе к i, чем к назначенным им центрам в <math>C_t \;</math>. При вычислении I(i) этими элементами можно пренебречь. Для каждого центра <math>s \in C_t \;</math> обозначим за <math>U_s \;</math> все элементы, назначенные s. Если <math>f_s + \sum_{j \in U_s \backslash W} d_j d(j, s) > \sum_{j \in U_s \backslash W} d_j d(j, i)</math>, то дешевле удалить объект s и переназначить элементы из <math>U_s \backslash W \;</math> элементу i. В этом случае s размещается в I(i). Обозначим N = m + n. Таким образом, процедура вычисления I(i) требует O(N) времени, что делает общее время выполнения полиномиальным. Чарикар и Гуха [2] сформулировали следующую теорему. | |||
'''Теорема 2 ([2]). Эвристика локального поиска, которая пытается добавить случайный центр <math>i \notin C_t \;</math> и удалить множество I(i), вычисляет <math>3 + \varepsilon \;</math>-аппроксимацию с высокой вероятностью за <math>T = O(N \; log \; N(log \; N + 1/ \varepsilon))</math> этапов улучшения, каждый из которых занимает O(N) времени.''' | |||
'''Варианты с ограничением пропускной способности''' | |||
Эвристики локального поиска также называются вариантами задач о k-медианах и о размещении объектов с ограничением пропускной способности. В этом варианте каждый возможный объект <math>i \in \mathcal{F}</math> может обслуживать не более <math>u_i \;</math> пользователей. В мягком варианте задачи о размещении объектов с ограничением пропускной способности в объекте <math>i \in \mathcal{F}</math> можно открыть <math>r_i \ge 0 \;</math> копий, так что стоимость объекта составит <math>f_i r_i \;</math>, а количество обслуживаемых пользователей – не более <math>r_i u_i \;</math>. Задача оптимизации заключается в выборе значения <math>r_i \;</math> для каждого <math>i \in \mathcal{F}</math> таким образом, чтобы назначение пользователей центрам удовлетворяло ограничению на пропускную способность каждого центра, а стоимость открытия центров и назначения пользователей была минимальной. Для этого варианта Арья и др. [1] предложили эвристику локального поиска, обеспечивающую разрыв локальности <math>4 + \varepsilon \;</math>. | |||
В жесткой версии задачи о размещении объектов с ограничением пропускной способности у объекта <math>i \in \mathcal{F}</math> имеется строгая граница <math>u_i \;</math> количества объектов, которые могут быть ему назначены. Для случая, когда пропускная способность <math>u_i \;</math> всех объектов одинакова (однородный случай), Коруполу, Плакстон и Раджамаран [9] представили изящную эвристику локального поиска, основанную на решении задачи о перевозках с промежуточными пунктами и обеспечивающую разрыв локальности <math>8 + \varepsilon \;</math>. Чудак и Уильямсон [4] улучшили анализ этой эвристики, показав, что разрыв локальности составляет <math>6 + \varepsilon \;</math>. В случае неоднородной пропускной способности требуется кардинально иной подход; Пал, Тардош и Уэкслер [14] представили эвристику локального поиска на базе сетевого потока, обеспечивающую разрыв локальности <math>9 + \varepsilon \;</math>. Махдиан и Пал [12] улучшили эту границу до <math>8 + \varepsilon \;</math> за счет обобщения нескольких техник локального поиска, описанных выше, с целью получения константного коэффициента аппроксимации для варианта задачи о размещении объектов, в котором стоимости объектов являются произвольными неубывающими функциями от потребностей обслуживаемых ими пользователей. | |||
'''Родственные алгоритмические техники''' | |||
Задачи о k-медианах и задачи о размещении объектов могут похвастаться долгой историей аппроксимации с достойными результатами. Начиная с первого исследования задачи о размещении объектов без ограничений на пропускную способность, выполненного Корнюжо, Немхаузером и Уолси [5], которые представили естественную релаксацию линейного программирования (LP) для этой задачи, было разработано несколько аппроксимаций с константными коэффициентами, использующих различные техники – таких как округление LP-решения [11, 15], локальный поиск [2, 9], прямо-двойственная схема [7] и двойное выравнивание [6]. Для задачи о k-медианах первая аппроксимация с константным коэффициентом 6 2/3 [3] была получена в результате округления естественной LP-релаксации при помощи обобщения техники фильтрации, предложенной в работе [11]. Результат был последовательно улучшен до 4-аппроксимации при помощи лагранжевой релаксации и прямо-двойственной схемы [2, 7], а затем до <math> \; (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 | |||
