Метрическое сгущение

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: Быстрый алгоритм нахождения метрических сгущений с использованием матрицы парных расстояний в ранг...)
 
(1 промежуточная версия не показана)
Строка 1: Строка 1:
 +
{{tip|Предлагаю посвятить статью этому термину, а дополнительный материал организовать как его иллюстрации. --[[Участник:Strijov|Strijov]] 02:23, 15 мая 2014 (MSD)}}
 +
Быстрый алгоритм нахождения метрических сгущений с использованием матрицы парных расстояний в ранговых шкалах - алгоритм [[Кластеризация |кластеризации]], основанный на идее нахождения метрических сгущений.
Быстрый алгоритм нахождения метрических сгущений с использованием матрицы парных расстояний в ранговых шкалах - алгоритм [[Кластеризация |кластеризации]], основанный на идее нахождения метрических сгущений.

Текущая версия

Предлагаю посвятить статью этому термину, а дополнительный материал организовать как его иллюстрации. --Strijov 02:23, 15 мая 2014 (MSD)


Быстрый алгоритм нахождения метрических сгущений с использованием матрицы парных расстояний в ранговых шкалах - алгоритм кластеризации, основанный на идее нахождения метрических сгущений.

Для выявления сгущений используется редуцированная матрица парных расстояний. При кластеризации рассматриваются только ранги расстояний. Отличительной особенностью предложенного алгоритма является то, что не требуется строитьполную матрицу парных расстояний. Это снижает его вычислительную сложность.

Метрическое сгущение

Задана выборка X=\{\mathbf{x}_1,\ldots,\mathbf{x}_N\} — множество элементов метрического пространства с заданной на нем метрикой ρ. Будем обозначать X(\mathbf{c}|r) множество, состоящее из элементов множества X, содержащихся в шаре с центром \mathbf{c}\in X и радиусом r, X(\mathbf{c}|r)=\{\mathbf{x}_i\in X|\; \rho(\mathbf{x}_i,\mathbf{c}) \leq r\}.

Центром метрического сгущения радиуса r будем называть точку \hat{\mathbf{c}}(r)\in X, такую, что \begin{equation} \hat{\mathbf{c}}(r)=\arg\max\limits_{\mathbf{c}\in X}|X(\mathbf{c}|r)|. \end{equation}

Метрическим сгущением радиуса r будем называть множество C(r)=X({\hat{\mathbf{c}}}|r).

Предлагаемый метод поиска метрических сгущений состоит из следующих этапов:

  • задание метрики на элементах выборки,
  • задание разреженного множества точек — ρ-сети,
  • вычисление расстояния между всеми элементами выборки и элементами ρ-сети,
  • нахождение метрических сгущений.

Ссылки

А. М. Катруца, М. П. Кузнецов, В. В. Стрижов, К. В. Рудаков. Быстрый алгоритм нахождения метрических сгущений с использованием матрицы парных расстояний в ранговых шкалах: PDF

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D1%81%D0%B3%D1%83%D1%89%D0%B5%D0%BD%D0%B8%D0%B5»
Личные инструменты