Минимальное остовное дерево

Минимальное остовное дерево (англ. Minimum Spanning Tree, MST) — это ациклическое подмножество рёбер взвешенного, связного, неориентированного графа, которое соединяет все его вершины и обладает минимальным суммарным весом среди всех таких подмножеств. В контексте машинного обучения и анализа данных MST является фундаментальным инструментом для выявления глобальной структуры данных, кластеризации и снижения размерности, позволяя улавливать нелинейные взаимосвязи без априорных предположений о форме распределений.

Формальное определение

Пусть задан связный неориентированный граф $G = (V, E)$ , где $V$ — множество вершин, $E$ — множество рёбер, и весовая функция $w : E \to \mathbb{R}$ , ставящая в соответствие каждому ребру его вес. Остовным деревом $T$ графа $G$ называется подграф, содержащий все вершины $V$ и представляющий собой дерево. Минимальным остовным деревом называется такое остовное дерево $T^*$ , для которого сумма весов его рёбер минимальна: $T^* = \arg\min_{T} \sum_{e \in T} w(e)$ . Для полного графа с $n$ вершинами число различных остовных деревьев равно $n^{n-2}$ (формула Кэли), что делает задачу перебора NP-трудной в общем случае, поэтому на практике применяются эффективные жадные алгоритмы.

Основные алгоритмы построения

Все алгоритмы поиска MST опираются на лемму о безопасном ребре, гласящую, что для любого разреза графа, не пересекающего уже построенный фрагмент остова, ребро минимального веса, пересекающее разрез, является безопасным и может быть добавлено в MST.

Алгоритм Краскала

Алгоритм Краскала сортирует все рёбра графа по возрастанию веса и последовательно добавляет их в строящийся остов, пропуская те, которые образуют цикл. Принадлежность вершин различным компонентам связности эффективно отслеживается с помощью системы непересекающихся множеств (Union-Find). Вычислительная сложность составляет $O(E \log E)$ , что в основном определяется временем сортировки рёбер. Алгоритм предпочтителен для разреженных графов.

Алгоритм Прима

Алгоритм Прима начинает с произвольной вершины и на каждом шаге присоединяет к уже построенному дереву ребро минимального веса, соединяющее вершину дерева с вершиной, ещё не входящей в него. При использовании двоичной кучи для хранения рёбер сложность составляет $O(E \log V)$ . Применение фибоначчиевой кучи теоретически улучшает сложность до $O(E + V \log V)$ . Алгоритм Прима эффективен на плотных графах.

Алгоритм Борувки

Алгоритм Борувки исторически является первым алгоритмом для решения задачи MST. На каждой итерации для каждой компоненты связности текущего леса выбирается инцидентное ей ребро минимального веса, после чего выбранные рёбра добавляются в остов, объединяя компоненты. Процесс повторяется, пока не останется одна компонента. Алгоритм хорошо поддается распараллеливанию и имеет сложность $O(E \log V)$ .

Применение в машинном обучении и анализе данных

MST служит мостом между теорией графов и статистическим анализом, позволяя строить непараметрические оценки и выявлять структуру данных "без учителя".

Кластеризация

Одним из прямых приложений является алгоритм кластеризации MST, порождающий иерархическую структуру кластеров. Разрезы графа — удаление $k-1$ самых длинных рёбер MST — разбивают множество объектов на $k$ кластеров. Этот подход, в отличие от k-means, способен выделять кластеры произвольной невыпуклой формы и автоматически определять их количество через анализ распределения длин рёбер MST. В биоинформатике MST-кластеризация применяется для анализа профилей генной экспрессии.

Снижение размерности и вложение многообразий

Концепция MST лежит в основе ряда методов нелинейного снижения размерности, восстанавливающих структуру низкоразмерного многообразия, вложенного в высокоразмерное пространство:

Isomap: Строит граф k ближайших соседей, а затем заменяет расстояния между удаленными точками длиной кратчайшего пути в этом графе (своего рода MST с избыточными связями). Идейно близкая концепция используется и при построении скелетона распределения данных.
Минимальное остовное дерево как скелет многообразия: MST, построенное на всем наборе данных, образует древовидный скелет, аппроксимирующий геодезические расстояния на многообразии и устойчивый к шумам при правильном выборе метрики.

Обнаружение аномалий

В задаче обнаружения аномалий объекты, соединенные с MST ребрами аномально большого веса, или вершины, удаление которых вызывает резкое увеличение суммарного веса дерева, могут классифицироваться как выбросы. Этот непараметрический тест не требует допущений о типе распределения и основан на графовых свойствах выборки.

Тестирование многомерной однородности

Мультивариативный критерий на основе MST (Multivariate Two-Sample Test) используется для проверки гипотезы о том, что две выборки извлечены из одного и того же многомерного распределения. Процедура заключается в построении MST на объединенной выборке и подсчете числа рёбер, соединяющих точки из разных выборок. Принадлежность ребра к разным выборкам оценивается по гипергеометрическому распределению или при помощи пермутационных тестов. Критерий состоятелен против произвольных альтернатив и не требует предположений о виде распределений.

Визуализация данных

В задачах визуализации многомерных данных MST часто используется совместно с проекциями: например, метод главных компонент (PCA) используется для отображения вершин, а рёбра MST рисуются поверх проекции, чтобы продемонстрировать, как сильно проекционные соседи отличаются от "истинных" соседей, определенных через MST в исходном пространстве.

Выбор метрики расстояния

Ключевой аспект практического применения MST в машинном обучении — выбор подходящей метрики расстояния $d(x_i, x_j)$ между объектами. Помимо стандартных расстояний (евклидова, манхэттенского), в зависимости от природы данных применяются:

Косинусное расстояние — для анализа текстов и разреженных векторов признаков.
Расстояние Махаланобиса — когда признаки коррелированы.
Ядерные расстояния, индуцированные нелинейным отображением в пространство признаков.

Оценка устойчивости и продолжения

Для оценки стабильности выделяемых структур в анализе данных применяют концепцию k-рёберно связного MST, добавляя в дерево ребра из оставшихся до тех пор, пока компонента не станет k-рёберно связной. Это приводит к идее минимального остовного дерева с ограничениями (Degree-Constrained MST) и Евклидова MST, широко исследуемых в вычислительной геометрии.

См. также

Литература

Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms. — 3-е изд.. — Вильямс, 2013. — 1328 с. — ISBN 978-5-8459-1794-2
Friedman, J.H., Rafsky, L.C. Multivariate Generalizations of the Wald-Wolfowitz and Smirnov Two-Sample Tests // The Annals of Statistics. — 1979. — Т. 7. — № 4. — С. 697–717.
Xu, R., Wunsch, D. Survey of Clustering Algorithms // IEEE Transactions on Neural Networks. — 2005. — Т. 16. — № 3. — С. 645-678.
Duda, R.O., Hart, P.E., Stork, D.G. Pattern Classification. — 2nd edition. — Wiley-Interscience, 2000. — ISBN 978-0471056690
Tenenbaum, J. B., de Silva, V., Langford, J. C. A Global Geometric Framework for Nonlinear Dimensionality Reduction // Science. — 2000. — Т. 290. — № 5500. — С. 2319-2323.

Источник — «http://recognition.su/wiki/index.php?title=%D0%9C%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B5_%D0%BE%D1%81%D1%82%D0%BE%D0%B2%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE»

@@ Строка 1: / Строка 1: @@
-== Минимальное остовное дерево (Minimum Spanning Tree, MST) ==
+== Минимальное остовное дерево ==
-'''Минимальное остовное дерево''' (''Minimum Spanning Tree'', '''MST''') — это [[Остовное дерево|остовное дерево]] [[Граф|взвешенного]] [[Неориентированный граф|неориентированного]] [[Связный граф|связного графа]], которое имеет минимальный возможный суммарный вес всех своих рёбер. Иными словами, это [[Ациклический граф|ациклический]] [[Связный граф|связный]] подграф, содержащий все вершины исходного графа, для которого сумма весов рёбер минимальна.
+'''Минимальное остовное дерево''' (англ. ''Minimum Spanning Tree'', ''MST'') — это [[ациклический граф|ациклическое]] [[подмножество]] [[рёбер]] [[взвешенный граф|взвешенного]], [[связный граф|связного]], [[неориентированный граф|неориентированного графа]], которое соединяет все его [[вершина (теория графов)|вершины]] и обладает минимальным суммарным [[вес ребра|весом]] среди всех таких подмножеств. В контексте [[машинное обучение|машинного обучения]] и [[анализ данных|анализа данных]] MST является фундаментальным инструментом для выявления глобальной структуры данных, [[кластеризация|кластеризации]] и снижения размерности, позволяя улавливать нелинейные взаимосвязи без априорных предположений о форме [[распределение вероятностей|распределений]].
-Задача о поиске минимального остовного дерева является одной из классических [[Оптимизация|оптимизационных]] задач на графах. Она имеет множество эффективных решений и широко применяется в различных областях, включая [[Кластеризация|кластеризацию]], проектирование сетей и [[Анализ данных|анализ данных]].
+== Формальное определение ==
+Пусть задан связный неориентированный граф <tex>G = (V, E)</tex>, где <tex>V</tex> — множество вершин, <tex>E</tex> — множество рёбер, и [[весовая функция]] <tex>w : E \to \mathbb{R}</tex>, ставящая в соответствие каждому ребру его вес. Остовным деревом <tex>T</tex> графа <tex>G</tex> называется подграф, содержащий все вершины <tex>V</tex> и представляющий собой [[дерево (теория графов)|дерево]]. Минимальным остовным деревом называется такое остовное дерево <tex>T^*</tex>, для которого сумма весов его рёбер минимальна:
+<tex>T^* = \arg\min_{T} \sum_{e \in T} w(e)</tex>.
+Для полного графа с <tex>n</tex> вершинами число различных остовных деревьев равно <tex>n^{n-2}</tex> ([[формула Кэли]]), что делает задачу перебора NP-трудной в общем случае, поэтому на практике применяются эффективные жадные алгоритмы.
-=== Определения ===
+== Основные алгоритмы построения ==
+Все алгоритмы поиска MST опираются на [[лемма о безопасном ребре|лемму о безопасном ребре]], гласящую, что для любого разреза графа, не пересекающего уже построенный фрагмент остова, ребро минимального веса, пересекающее разрез, является безопасным и может быть добавлено в MST.
-Пусть задан связный неориентированный граф <tex>G = (V, E)</tex>, где <tex>V</tex> — множество вершин, а <tex>E</tex> — множество рёбер. Для каждого ребра <tex>e \in E</tex> определена его весовая функция <tex>w(e) \in \mathbb{R}</tex>, которая сопоставляет ребру некоторое числовое значение (стоимость, длину, пропускную способность и т.д.).
+=== Алгоритм Краскала ===
+[[Алгоритм Краскала]] сортирует все рёбра графа по возрастанию веса и последовательно добавляет их в строящийся остов, пропуская те, которые образуют [[цикл (теория графов)|цикл]]. Принадлежность вершин различным компонентам связности эффективно отслеживается с помощью [[структура данных|системы непересекающихся множеств]] (Union-Find). Вычислительная сложность составляет <tex>O(E \log E)</tex>, что в основном определяется временем сортировки рёбер. Алгоритм предпочтителен для разреженных графов.
-Остовное дерево графа <tex>G</tex> — это ациклический связный подграф <tex>T = (V, E')</tex>, где <tex>E' \subseteq E</tex> и <tex>|E'| = |V| - 1</tex>. Вес остовного дерева определяется как сумма весов входящих в него рёбер: <tex>w(T) = \sum_{e \in E'} w(e)</tex>.
+=== Алгоритм Прима ===
+[[Алгоритм Прима]] начинает с произвольной вершины и на каждом шаге присоединяет к уже построенному дереву ребро минимального веса, соединяющее вершину дерева с вершиной, ещё не входящей в него. При использовании [[двоичная куча|двоичной кучи]] для хранения рёбер сложность составляет <tex>O(E \log V)</tex>. Применение [[фибоначчиева куча|фибоначчиевой кучи]] теоретически улучшает сложность до <tex>O(E + V \log V)</tex>. Алгоритм Прима эффективен на плотных графах.
-'''Минимальное остовное дерево''' (MST) — это остовное дерево <tex>T^*</tex>, такое что <tex>w(T^*) \le w(T)</tex> для любого другого остовного дерева <tex>T</tex> графа <tex>G</tex>.
+=== Алгоритм Борувки ===
+[[Алгоритм Борувки]] исторически является первым алгоритмом для решения задачи MST. На каждой итерации для каждой компоненты связности текущего леса выбирается инцидентное ей ребро минимального веса, после чего выбранные рёбра добавляются в остов, объединяя компоненты. Процесс повторяется, пока не останется одна компонента. Алгоритм хорошо поддается [[параллельные вычисления|распараллеливанию]] и имеет сложность <tex>O(E \log V)</tex>.
-=== Свойства MST ===
+== Применение в машинном обучении и анализе данных ==
+MST служит мостом между [[теория графов|теорией графов]] и статистическим анализом, позволяя строить непараметрические оценки и выявлять структуру данных "без учителя".
-Задача поиска MST обладает рядом важных свойств, которые лежат в основе всех классических алгоритмов её решения:
+=== Кластеризация ===
+Одним из прямых приложений является [[алгоритм кластеризации MST]], порождающий иерархическую структуру кластеров. Разрезы графа — удаление <tex>k-1</tex> самых длинных рёбер MST — разбивают множество объектов на <tex>k</tex> кластеров. Этот подход, в отличие от [[метод k-средних|k-means]], способен выделять кластеры произвольной невыпуклой формы и автоматически определять их количество через анализ распределения длин рёбер MST. В [[биоинформатика|биоинформатике]] MST-кластеризация применяется для анализа [[экспрессия генов|профилей генной экспрессии]].
-* '''Свойство разреза (Cut Property):''' Рассмотрим произвольное подмножество вершин <tex>S \subset V</tex>, где <tex>S \neq \emptyset</tex> и <tex>S \neq V</tex>. Пусть ребро <tex>e</tex> — ребро минимального веса среди всех рёбер, пересекающих разрез <tex>(S, V \setminus S)</tex> (т.е. соединяющих вершину из <tex>S</tex> с вершиной из <tex>V \setminus S</tex>). Тогда существует минимальное остовное дерево, содержащее ребро <tex>e</tex>.
+=== Снижение размерности и вложение многообразий ===
+Концепция MST лежит в основе ряда методов [[нелинейное снижение размерности|нелинейного снижения размерности]], восстанавливающих структуру низкоразмерного [[многообразие|многообразия]], вложенного в высокоразмерное пространство:
+* '''[[Алгоритм Изомап|Isomap]]:''' Строит граф k ближайших соседей, а затем заменяет расстояния между удаленными точками длиной кратчайшего пути в этом графе (своего рода MST с избыточными связями). Идейно близкая концепция используется и при построении скелетона распределения данных.
+* '''Минимальное остовное дерево как скелет многообразия:''' MST, построенное на всем наборе данных, образует древовидный скелет, аппроксимирующий геодезические расстояния на многообразии и устойчивый к шумам при правильном выборе метрики.
-* '''Свойство цикла (Cycle Property):''' Рассмотрим любое ребро <tex>e</tex>, принадлежащее некоторому циклу в графе <tex>G</tex>. Если вес ребра <tex>e</tex> строго больше веса любого другого ребра в этом цикле, то <tex>e</tex> не может принадлежать никакому минимальному остовному дереву.
+=== Обнаружение аномалий ===
+В задаче [[обнаружение аномалий|обнаружения аномалий]] объекты, соединенные с MST ребрами аномально большого веса, или вершины, удаление которых вызывает резкое увеличение суммарного веса дерева, могут классифицироваться как [[выброс]]ы. Этот непараметрический тест не требует допущений о типе распределения и основан на [[теория графов|графовых]] свойствах выборки.
-* '''Свойство безопасного ребра (Safe Edge Property):''' Добавление ребра, удовлетворяющего свойству разреза, к частичному остовному лесу сохраняет возможность построения MST. Такое ребро называется ''безопасным''.
+=== Тестирование многомерной однородности ===
+Мультивариативный критерий на основе MST (''Multivariate Two-Sample Test'') используется для проверки гипотезы о том, что две выборки извлечены из одного и того же многомерного распределения. Процедура заключается в построении MST на объединенной выборке и подсчете числа рёбер, соединяющих точки из разных выборок. Принадлежность ребра к разным выборкам оценивается по [[гипергеометрическое распределение|гипергеометрическому распределению]] или при помощи [[пермутационное тестирование|пермутационных тестов]]. Критерий состоятелен против произвольных альтернатив и не требует предположений о виде распределений.
-=== Алгоритмы построения ===
+=== Визуализация данных ===
+В задачах визуализации многомерных данных MST часто используется совместно с проекциями: например, [[метод главных компонент]] (PCA) используется для отображения вершин, а рёбра MST рисуются поверх проекции, чтобы продемонстрировать, как сильно проекционные соседи отличаются от "истинных" соседей, определенных через MST в исходном пространстве.
-Для решения задачи о минимальном остовном дереве разработано несколько классических алгоритмов. Все они, как правило, являются [[Жадный алгоритм|жадными]] и основаны на свойствах разреза и цикла.
+== Выбор метрики расстояния ==
+Ключевой аспект практического применения MST в машинном обучении — выбор подходящей [[функция расстояния|метрики расстояния]] <tex>d(x_i, x_j)</tex> между объектами. Помимо стандартных расстояний ([[евклидово расстояние|евклидова]], [[манхэттенское расстояние|манхэттенского]]), в зависимости от природы данных применяются:
+* '''[[Косинусное расстояние]]''' — для анализа текстов и [[разреженные данные|разреженных]] векторов признаков.
+* '''Расстояние [[Махаланобис]]а''' — когда признаки коррелированы.
+* '''[[Ядерные методы|Ядерные]] расстояния''', индуцированные нелинейным отображением в [[спрямляющее пространство|пространство признаков]].
-==== Алгоритм Крускала (Kruskal's algorithm) ====
+== Оценка устойчивости и продолжения ==
+Для оценки стабильности выделяемых структур в анализе данных применяют концепцию ''k-рёберно связного'' MST, добавляя в дерево ребра из оставшихся до тех пор, пока компонента не станет k-рёберно связной. Это приводит к идее [[минимальное остовное дерево с ограничениями|минимального остовного дерева с ограничениями]] (Degree-Constrained MST) и [[Евклидово минимальное остовное дерево|Евклидова MST]], широко исследуемых в [[вычислительная геометрия|вычислительной геометрии]].
-[[Алгоритм Краскала|Алгоритм Крускала]] был предложен Джозефом Крускалом в 1956 году . Его основная идея заключается в построении MST путём последовательного добавления рёбер в порядке возрастания их весов, при условии, что добавляемое ребро не создаёт цикла .
+== См. также ==
+* [[Теория графов]]
+* [[Задача коммивояжёра]]
+* [[Алгоритм Дейкстры]]
+* [[Спектральная кластеризация]]
+* [[Самоорганизующаяся карта Кохонена]]
-'''Этапы алгоритма:'''
+== Литература ==
-# Инициализировать лес, состоящий из изолированных вершин графа <tex>G</tex>.
+* {{книга
-# Отсортировать все рёбра графа <tex>G</tex> по неубыванию весов.
+ | автор = Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К.
-# Для каждого ребра <tex>e = (u, v)</tex> в отсортированном порядке:
+ | заглавие = Алгоритмы: построение и анализ
-#* Если вершины <tex>u</tex> и <tex>v</tex> принадлежат разным [[Компонента связности|компонентам связности]] текущего леса, добавить ребро <tex>e</tex> в остовное дерево и объединить эти две компоненты.
+ | оригинал = Introduction to Algorithms
-#* В противном случае (если <tex>u</tex> и <tex>v</tex> уже в одной компоненте), пропустить ребро, так как его добавление создаст цикл.
+ | издание = 3-е изд.
-# Алгоритм завершается, когда в остовном дереве будет <tex>|V| - 1</tex> ребро (т.е. все вершины будут соединены в одну компоненту).
+ | издательство = Вильямс
+ | год = 2013
-Для эффективной проверки принадлежности вершин к разным компонентам и их объединения используется структура данных [[Система непересекающихся множеств|системы непересекающихся множеств]] (''Union-Find, DSU'') .
+ | страниц = 1328
+ | isbn = 978-5-8459-1794-2
-'''Сложность алгоритма:''' <tex>O(E \log E) = O(E \log V)</tex>, где <tex>E</tex> — число рёбер, <tex>V</tex> — число вершин. Сложность определяется, в первую очередь, сортировкой рёбер . При использовании эффективной реализации DSU операции ''find'' и ''union'' выполняются почти за константное время.
+}}
+* {{статья
-==== Алгоритм Прима (Prim's algorithm) ====
+ | автор = Friedman, J.H., Rafsky, L.C.
+ | заглавие = Multivariate Generalizations of the Wald-Wolfowitz and Smirnov Two-Sample Tests
-[[Алгоритм Прима]] был разработан Робертом Примом в 1957 году. В отличие от алгоритма Крускала, он строит дерево, последовательно наращивая его от одной начальной вершины .
+ | издание = The Annals of Statistics
+ | год = 1979
-'''Этапы алгоритма:'''
+ | том = 7
-# Выбрать произвольную стартовую вершину <tex>r \in V</tex> и добавить её в множество построенного дерева <tex>U</tex>.
+ | номер = 4
-# Для каждой вершины <tex>v \notin U</tex> вычислить расстояние до текущего дерева <tex>U</tex> как минимальный вес ребра, соединяющего <tex>v</tex> с какой-либо вершиной из <tex>U</tex>.
+ | страницы = 697–717
-# На каждом шаге выбирается вершина <tex>v \notin U</tex>, имеющая минимальное расстояние до дерева. Вершина <tex>v</tex> и соответствующее ребро минимального веса добавляются в дерево <tex>U</tex> .
+}}
-# Шаги 2-3 повторяются, пока <tex>U \neq V</tex> (пока не будут включены все вершины).
+* {{статья
+ | автор = Xu, R., Wunsch, D.
-'''Сложность алгоритма:''' зависит от реализации приоритетной очереди для выбора вершины с минимальным расстоянием.
+ | заглавие = Survey of Clustering Algorithms
-* Простая реализация (без кучи): <tex>O(V^2)</tex>, эффективна для [[Плотный граф|плотных графов]].
+ | издание = IEEE Transactions on Neural Networks
-* С использованием [[Двоичная куча|двоичной кучи]]: <tex>O(E \log V)</tex> .
+ | год = 2005
-* С использованием [[Куча Фибоначчи|кучи Фибоначчи]]: <tex>O(E + V \log V)</tex> .
+ | том = 16
+ | номер = 3
-==== Алгоритм Борувки (Borůvka's algorithm) ====
+ | страницы = 645-678
+}}
-Один из первых алгоритмов для решения задачи MST, предложенный Отакаром Борувкой в 1926 году . Его идея заключается в параллельном добавлении минимальных рёбер для каждой компоненты связности. На каждом шаге для каждой компоненты выбирается исходящее ребро минимального веса, и все такие рёбра добавляются в дерево, объединяя компоненты. Алгоритм завершается, когда остаётся одна компонента. Его сложность составляет <tex>O(E \log V)</tex>.
+* {{книга
+ | автор = Duda, R.O., Hart, P.E., Stork, D.G.
-=== Применение в анализе данных и машинном обучении ===
+ | заглавие = Pattern Classification
+ | издание = 2nd edition
-Хотя задача о MST традиционно относится к области [[Теория графов|теории графов]], она находит важные применения в [[Анализ данных|анализе данных]] и [[Машинное обучение|машинном обучении]]:
+ | издательство = Wiley-Interscience
+ | год = 2000
-* '''Кластеризация с одиночной связью (Single-linkage clustering):''' Это один из базовых иерархических алгоритмов кластеризации. Процесс построения [[Дендрограмма|дендрограммы]] методом одиночной связи эквивалентен построению MST графа, вершинами которого являются объекты, а весами рёбер — расстояния между ними . Отсечение рёбер MST с весами, превышающими некоторый порог, позволяет получить кластеры.
+ | isbn = 978-0471056690
+}}
-* '''Визуализация многомерных данных:''' MST может быть использовано для построения скелетной структуры данных, отражающей их топологию. Например, для отображения структуры [[Многообразие|многообразия]] или для выявления цепочек и паттернов в данных.
+* {{статья
+ | автор = Tenenbaum, J. B., de Silva, V., Langford, J. C.
-* '''Выделение признаков и снижение размерности:''' Алгоритмы, подобные ''Isomap'', используют MST (или его вариант, ''Minimum Spanning Tree в метрическом пространстве'') для оценки [[Геодезическое расстояние|геодезических расстояний]] между точками на нелинейном многообразии, что помогает выполнить [[Снижение размерности|снижение размерности]].
+ | заглавие = A Global Geometric Framework for Nonlinear Dimensionality Reduction
+ | издание = Science
-* '''Сжатие данных:''' MST может быть использовано для построения аппроксимирующих графов, которые компактно описывают структуру данных и могут служить для эффективного поиска ближайших соседей.
+ | год = 2000
+ | том = 290
-=== Вариации и обобщения ===
+ | номер = 5500
+ | страницы = 2319-2323
-* '''Минимальное остовное дерево с ограничениями (Constrained MST):''' Задача поиска MST с дополнительными ограничениями, например, на степень вершины или на включение обязательных рёбер.
+}}
-* '''Задача о минимальном остовном дереве Штейнера (Steiner Tree Problem):''' Обобщение, в котором не требуется включать все вершины графа, а только заданное подмножество (терминалы). Разрешается добавлять вспомогательные вершины (''точки Штейнера'') для уменьшения суммарного веса дерева .
-* '''MST в динамических графах:''' Задача поддержания MST при добавлении или удалении рёбер в графе.
-=== Список литературы ===
-* {{книга | автор = Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. | заглавие = Алгоритмы: построение и анализ | издательство = Вильямс | год = 2013 | издание = 3-е}}
-* {{книга | автор = Седжвик Р. | заглавие = Фундаментальные алгоритмы на C++. Алгоритмы на графах | издательство = ДиаСофт | год = 2002}}
-* {{статья | автор = Vorontsov, K.V., Inyakin, A.S., Strizhov, V.V., Chekhovich, Y.V. | заглавие = MachineLearning.ru – информационно-аналитический ресурс по проблемам машинного обучения и интеллектуального анализа данных | издание = Труды конференции | год = 2008 | ссылка = http://www.ccas.ru/frc/papers/voron08machinelearning.pdf }}
-* {{книга | автор = Клейнберг Д., Тардос Е. | заглавие = Алгоритмы: разработка и применение | издательство = Питер | год = 2016}}

Минимальное остовное дерево

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

Версия 15:38, 14 июля 2026

Содержание