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

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

Перейти к: навигация, поиск
Предлагаю посвятить статью этому термину, а дополнительный материал организовать как его иллюстрации. --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»
Личные инструменты