4430
правок
Локальный поиск для задачи о k-медианах и задачи о размещении объектов: различия между версиями
Материал из WEGA
Локальный поиск для задачи о k-медианах и задачи о размещении объектов (посмотреть исходный код)
Версия от 11:43, 17 апреля 2018
, 17 апреля 2018→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Метод k-медиан; метод k-средних; метод k-медоидов; задача о ра…») |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Кластеризация представляет собой разновидность обучения без учителя, при котором задача заключается в «обучении» полезным образцам на наборе данных D размера n. Ее можно также рассматривать как схему сжатия данных, в которой большой набор данных представляется при помощи меньшего набора «представителей». Подобная схема характеризуется путем задания следующих параметров: | Кластеризация представляет собой разновидность ''обучения без учителя'', при котором задача заключается в «обучении» полезным образцам на наборе данных <math>\mathcal{D} \;</math> размера n. Ее можно также рассматривать как схему сжатия данных, в которой большой набор данных представляется при помощи меньшего набора «представителей». Подобная схема характеризуется путем задания следующих параметров: | ||
1. Метрика расстояния d между элементами набора данных. Эта метрика должна удовлетворять неравенству треугольника: d(i, j) | 1. Метрика ''расстояния'' '''d''' между элементами набора данных. Эта метрика должна удовлетворять неравенству треугольника: <math>d(i, j) \le d(j, k) + d(k, i) \;</math> для любых трех элементов <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. Результатом (выходными данными) процесса кластеризации является разбиение данных. В данной главе рассматривается кластеризация на основе центров. В ней результатом является множество меньшего размера C Rd, состоящее из центров, которые наилучшим образом представляют входное множество данных S Rd . Как правило, имеет место соотношение |C| |D|. Каждый элемент j 2 D отображается на ближайший центр или аппроксимируется ближайшим центром i 2 C, из чего следует d(i; j) _ d(i0; j) for all i0 2 C. Обозначим за _ : D ! C это отображение. Оно является интуитивно понятным, поскольку более близкие (схожие) элементы будут отбражаться на один и тот же центр. | 2. Результатом (выходными данными) процесса кластеризации является разбиение данных. В данной главе рассматривается кластеризация на основе центров. В ней результатом является множество меньшего размера C Rd, состоящее из центров, которые наилучшим образом представляют входное множество данных S Rd . Как правило, имеет место соотношение |C| |D|. Каждый элемент j 2 D отображается на ближайший центр или аппроксимируется ближайшим центром i 2 C, из чего следует d(i; j) _ d(i0; j) for all i0 2 C. Обозначим за _ : D ! C это отображение. Оно является интуитивно понятным, поскольку более близкие (схожие) элементы будут отбражаться на один и тот же центр. | ||
