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

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

(Различия между версиями)
Перейти к: навигация, поиск

Oleg Bakhteev (Обсуждение | вклад)
(Новая: Быстрый алгоритм нахождения метрических сгущений с использованием матрицы парных расстояний в ранг...)
К следующему изменению →

Версия 17:16, 7 мая 2014

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

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

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

Задана выборка 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://www.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»
Личные инструменты