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

Перейти к навигации Перейти к поиску
Строка 7: Строка 7:
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. Интуитивно понятно, что если расстояние между двумя элементами меньше, то они больше похожи друг на друга. Элементами обычно являются точки в некотором евклидовом пространстве Rd высокой размерности. В качестве метрик расстояния чаще всего применяются евклидова метрика и расстояние Хэмминга, а также косинусная метрика, измеряющая угол между векторами, представляющими элементы.
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. Интуитивно понятно, что если расстояние между двумя элементами меньше, то они больше похожи друг на друга. Элементами обычно являются точки в некотором евклидовом пространстве Rd высокой размерности. В качестве метрик расстояния чаще всего применяются евклидова метрика и расстояние Хэмминга, а также косинусная метрика, измеряющая угол между векторами, представляющими элементы.


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: \mathbb{D} \to C</math> это отображение. Оно является интуитивно понятным, поскольку более близкие (схожие) элементы будут отображаться на один и тот же центр.
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) = maxj2D d( j; _( j)).
'''k-центр''': <math>f(C) = max_{j \in \mathcal{D} } \; d(j, \sigma (j))</math>.


k-медианы: f (C) = Pj2D d( j; _( j)).
'''k-медианы''': <math>f(C) = \sum_{j \in \mathcal{D}} \; d(j, \sigma (j))</math>.
 
'''k-средние''': <math>f(C) = \sum_{j \in \mathcal{D}} \; d(j, \sigma (j))^2</math>.


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.
Все вышеупомянутые цели являются NP-СЛОЖНЫМИ для оптимизации в метрических пространствах общего вида d, что вызвало необходимость изучения эвристических и приближенных алгоритмов. Далее главным образом будет рассматриваться целевая функция на основе k-медиан. Алгоритмы аппроксимации для кластеризации на основе метода k-медиан разработаны для пространства d, являющегося неевклидовым метрическим пространством наиболее общего возможного вида. Совокупность F возможных местоположений центров задана в качестве начального условия, множество центров C ограничено C  F. С точки зрения аппроксимации ограничение возможных центров конечным множеством F не является чрезмерно строгим: например, для оптимального решения, ограниченного F = D, его целевое значение не более чем в 2 раза превышает оптимальное значение, допускаемое при произвольном F. Обозначим |D| = n и |F| = m. Время выполнения построенной эвристики будет представлено полиномом от mn с параметром > 0. Метрическое пространство d теперь определяется над D [ F.
Источник — http://pco.iis.nsk.su/wega/index.php/Локальный_поиск_для_задачи_о_k-медианах_и_задачи_о_размещении_объектов