Карта диффузии

Учитывая неравномерно выбранные точки данных на тороидальной спирали (вверху), наносятся первые две координаты карты диффузии с нормализацией Лапласа – Бельтрами (внизу). Карта диффузии распутывает тороидальную спираль, восстанавливая внутреннюю круговую геометрию данных.

Карты диффузии — это алгоритм уменьшения размерности или выделения признаков, предложенный Койфманом и Лафоном. который вычисляет семейство вложений набора данных в евклидово пространство (часто низкоразмерное), координаты которого можно вычислить на основе собственных векторов и собственных значений оператора диффузии данных. Евклидово расстояние между точками во встроенном пространстве равно «диффузионному расстоянию» между распределениями вероятностей с центрами в этих точках. В отличие от методов линейного уменьшения размерности, таких как анализ главных компонентов (PCA), диффузионные карты являются частью семейства нелинейных методов уменьшения размерности , которые направлены на обнаружение основного многообразия , из которого были выбраны данные. Объединяя локальные сходства в разных масштабах, карты диффузии дают глобальное описание набора данных. По сравнению с другими методами алгоритм карты диффузии устойчив к шумовым возмущениям и не требует больших вычислительных затрат.

Определение карт диффузии

Следующий и, Карты диффузии могут быть определены в четыре этапа.

Возможности подключения

Карты диффузии используют взаимосвязь между диффузией тепла и случайного блуждания цепью Маркова . Основное наблюдение заключается в том, что если мы совершаем случайное блуждание по данным, переход к ближайшей точке данных более вероятен, чем переход к другой, которая находится далеко. Позволять $(X,{\mathcal {A}},\mu )$ — пространство с мерой , где $X$ это набор данных и $\mu$ представляет собой распределение очков на $X$.

На основании этого связь $k$ между двумя точками данных, $x$ и $y$, можно определить как вероятность перехода от $x$ к $y$ за один шаг случайного блуждания. Обычно эта вероятность определяется через ядерную функцию двух точек: $k:X\times X\rightarrow \mathbb {R}$. Например, популярное ядро ​​Гаусса:

$k(x,y)=\exp \left(-{\frac {||x-y||^{2}}{\epsilon }}\right)$

В более общем смысле функция ядра имеет следующие свойства:

$k(x,y)=k(y,x)$

( $k$ симметричен)

$k(x,y)\geq 0\,\,\forall x,y$

( $k$ сохраняет позитив).

Ядро представляет собой предварительное определение локальной геометрии набора данных. Поскольку данное ядро ​​будет фиксировать определенную особенность набора данных, его выбор должен определяться предполагаемым приложением. В этом заключается главное отличие от таких методов, как анализ главных компонент , где корреляции между всеми точками данных учитываются одновременно.

Данный $(X,k)$, мы можем затем построить обратимую цепь Маркова с дискретным временем на $X$ (процесс, известный как конструкция Лапласа нормализованного графа):

$d(x)=\int _{X}k(x,y)d\mu (y)$

и определим:

$p(x,y)={\frac {k(x,y)}{d(x)}}$

Хотя новое нормализованное ядро ​​не наследует свойства симметричности, оно наследует свойство сохранения положительности и приобретает свойство сохранения:

$\int _{X}p(x,y)d\mu (y)=1$

Процесс диффузии

От $p(x,y)$ мы можем построить матрицу перехода цепи Маркова ( $M$) на $X$. Другими словами, $p(x,y)$ представляет собой вероятность одношагового перехода от $x$ к $y$, и $M^{t}$ дает матрицу перехода t-шага.

Определим матрицу диффузии $L$ (это также версия графической матрицы Лапласа )

$L_{i,j}=k(x_{i},x_{j})\,$

Затем мы определяем новое ядро

$L_{i,j}^{(\alpha )}=k^{(\alpha )}(x_{i},x_{j})={\frac {L_{i,j}}{(d(x_{i})d(x_{j}))^{\alpha }}}\,$

или эквивалентно,

$L^{(\alpha )}=D^{-\alpha }LD^{-\alpha }\,$

где D — диагональная матрица и $D_{i,i}=\sum _{j}L_{i,j}.$

Мы применяем нормализацию Лапласа графа к этому новому ядру:

$M=({D}^{(\alpha )})^{-1}L^{(\alpha )},\,$

где $D^{(\alpha )}$ является диагональной матрицей и ${D}_{i,i}^{(\alpha )}=\sum _{j}L_{i,j}^{(\alpha )}.$

$p(x_{j},t|x_{i})=M_{i,j}^{t}\,$

Одна из основных идей диффузионной модели заключается в том, что продвижение цепочки вперед во времени (принимая все большие и большие степени $M$) раскрывает геометрическую структуру $X$ во все больших и больших масштабах (процесс диффузии). В частности, понятие кластера в наборе данных количественно определяется как область, в которой вероятность выхода из этой области мала (в течение определенного времени t). Следовательно, t не только служит параметром времени, но также играет двойную роль параметра масштаба.

Собственное разложение матрицы $M^{t}$ урожайность

$M_{i,j}^{t}=\sum _{l}\lambda _{l}^{t}\psi _{l}(x_{i})\phi _{l}(x_{j})\,$

где $\{\lambda _{l}\}$ есть последовательность собственных значений $M$ и $\{\psi _{l}\}$ и $\{\phi _{l}\}$ — биортогональные правый и левый собственные векторы соответственно. Из-за затухания спектра собственных значений для достижения заданной относительной точности в этой сумме необходимо всего несколько членов.

Параметр α и оператор диффузии

Причина введения шага нормализации, включающего $\alpha$ заключается в настройке влияния плотности точек данных на бесконечно малый переход диффузии. В некоторых приложениях выборка данных обычно не связана с геометрией многообразия, которое мы хотим описать. В этом случае мы можем установить $\alpha =1$ а оператор диффузии аппроксимирует оператор Лапласа–Бельтрами. Затем мы восстанавливаем риманову геометрию набора данных независимо от распределения точек. Для описания долговременного поведения распределения точек системы стохастических дифференциальных уравнений мы можем использовать $\alpha =0.5$ и полученная цепь Маркова аппроксимирует диффузию Фоккера – Планка . С $\alpha =0$, оно сводится к классической нормализации графа по Лапласу.

Диффузионное расстояние

Диффузионное расстояние во времени $t$ Между двумя точками можно измерить как сходство двух точек в пространстве наблюдения со связностью между ними. Это дано

$D_{t}(x_{i},x_{j})^{2}=\sum _{y}{\frac {(p(y,t|x_{i})-p(y,t|x_{j}))^{2}}{\phi _{0}(y)}}$

где $\phi _{0}(y)$ — стационарное распределение цепи Маркова, заданное первым левым собственным вектором $M$. Явно:

$\phi _{0}(y)={\frac {d(y)}{\sum _{z\in X}d(z)}}$

Интуитивно, $D_{t}(x_{i},x_{j})$ мал, если имеется большое количество коротких путей, соединяющих $x_{i}$ и $x_{j}$. Судя по нашему предыдущему обсуждению, с диффузионным расстоянием связано несколько интересных особенностей. $t$ также служит параметром масштаба:

1. Точки ближе в данном масштабе (как указано в $D_{t}(x_{i},x_{j})$), если они сильно связаны в графе, что подчеркивает концепцию кластера.
2. Это расстояние устойчиво к шуму, поскольку расстояние между двумя точками зависит от всех возможных путей длины. $t$ между точками.
3. С точки зрения машинного обучения, расстояние учитывает все доказательства, связывающие $x_{i}$ к $x_{j}$, что позволяет нам заключить, что это расстояние подходит для разработки алгоритмов вывода, основанных на преобладании большинства.

Процесс диффузии и низкоразмерное встраивание

Диффузионное расстояние можно рассчитать с использованием собственных векторов по формуле

$D_{t}(x_{i},x_{j})^{2}=\sum _{l}\lambda _{l}^{2t}(\psi _{l}(x_{i})-\psi _{l}(x_{j}))^{2}\,$

Таким образом, собственные векторы можно использовать в качестве нового набора координат для данных. Карта диффузии определяется как:

$\Psi _{t}(x)=(\lambda _{1}^{t}\psi _{1}(x),\lambda _{2}^{t}\psi _{2}(x),\ldots ,\lambda _{k}^{t}\psi _{k}(x))$

Из-за затухания спектра достаточно использовать только первые k собственных векторов и собственных значений. Таким образом, мы получаем карту диффузии исходных данных в k -мерное пространство, вложенное в исходное пространство.

В доказано, что

$D_{t}(x_{i},x_{j})^{2}\approx ||\Psi _{t}(x_{i})-\Psi _{t}(x_{j})||^{2}\,$

поэтому евклидово расстояние в диффузионных координатах аппроксимирует диффузионное расстояние.

Алгоритм

Базовая структура алгоритма карты диффузии выглядит следующим образом:

Шаг 1. Учитывая матрицу подобия L .

Шаг 2. Нормализовать матрицу по параметру $\alpha$: $L^{(\alpha )}=D^{-\alpha }LD^{-\alpha }$.

Шаг 3. Формируем нормализованную матрицу $M=({D}^{(\alpha )})^{-1}L^{(\alpha )}$.

Шаг 4. Вычислить k наибольших собственных значений $M^{t}$ и соответствующие собственные векторы.

Шаг 5. Используйте карту диффузии, чтобы получить вложение $\Psi _{t}$.

Приложение

В газете Надлер и др. показал, как спроектировать ядро, воспроизводящее диффузию, вызванную уравнением Фоккера-Планка . Они также объяснили, что, когда данные аппроксимируют многообразие, можно восстановить геометрию этого многообразия, вычислив аппроксимацию оператора Лапласа-Бельтрами . Это вычисление совершенно нечувствительно распределению точек и, следовательно, обеспечивает разделение статистики и геометрии данные. Поскольку карты диффузии дают глобальное описание набора данных, они могут измерять расстояния между парами точек выборки в многообразии, в которое встроены данные. Приложения, основанные на картах диффузии, включают распознавание лиц , спектральная кластеризация , низкоразмерное представление изображений, сегментация изображений, 3D model segmentation, проверка динамика и идентификация, отбор проб на коллекторах, обнаружение аномалий, роспись изображений, разоблачение организации государственных сетей, обеспечивающих отдых мозга и так далее.

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

См. также

• Нелинейное уменьшение размерности
• Спектральная кластеризация