Карты диффузии - это алгоритм уменьшения размерности или выделения признаков , представленный Койфманом и Лафоном [1] [2] [3] [4], который вычисляет семейство вложений набора данных в евклидово пространство (часто низкоразмерное), координаты которого могут быть вычисляется из собственных векторов и собственных значений оператора диффузии для данных. Евклидово расстояние между точками во вложенном пространстве равно «диффузионному расстоянию» между распределениями вероятностей с центрами в этих точках. В отличие от методов уменьшения линейной размерности, таких как анализ главных компонентов (PCA), карты диффузии являются частью семействаметоды нелинейного уменьшения размерности, которые сосредоточены на обнаружении основного многообразия , из которого были взяты данные. Интегрируя локальные сходства в разных масштабах, карты распространения дают глобальное описание набора данных. По сравнению с другими методами алгоритм карты диффузии устойчив к шумовым возмущениям и не требует больших вычислительных затрат.
Определение диффузионных карт
Следуя [3] и [5], карты диффузии могут быть определены в четыре этапа.
Связь
Карты диффузии используют взаимосвязь между диффузией тепла и цепью Маркова случайным блужданием . Основное наблюдение состоит в том, что если мы совершим случайное блуждание по данным, прогулка к ближайшей точке данных будет более вероятной, чем прогулка к другой, которая находится далеко. Позволятьбыть мерным пространством , где это набор данных и представляет собой распределение точек на .
Исходя из этого, возможность подключения между двумя точками данных, а также , можно определить как вероятность ходьбы от к за один шаг случайного блуждания. Обычно эта вероятность определяется в виде ядерной функции двух точек:. Например, популярное гауссовское ядро:
В более общем плане функция ядра имеет следующие свойства
( симметрично)
( сохраняет положительность).
Ядро составляет предварительное определение локальной геометрии набора данных. Поскольку данное ядро захватывает определенную функцию набора данных, при его выборе следует руководствоваться приложением, которое вы имеете в виду. Это главное отличие от таких методов, как анализ главных компонентов , где корреляции между всеми точками данных учитываются сразу.
Дано , тогда мы можем построить обратимую цепь Маркова на (процесс, известный как построение лапласиана нормализованного графа):
и определите:
Хотя новое нормализованное ядро не наследует свойство симметрии, оно наследует свойство сохранения положительности и получает свойство сохранения:
Процесс диффузии
Из мы можем построить матрицу переходов цепи Маркова () на . Другими словами, представляет собой вероятность одношагового перехода от к , а также дает матрицу перехода с t-шагом.
Определим матрицу диффузии (это также версия матрицы Лапласа графа )
Затем мы определяем новое ядро
или эквивалентно,
где D - диагональная матрица, а
Мы применяем лапласовскую нормализацию графа к этому новому ядру:
где диагональная матрица и
Одна из основных идей концепции диффузии заключается в том, что цепочка продвигается вперед во времени (требуя все больших и больших степеней ) раскрывает геометрическую структуру во все больших и больших масштабах (процесс диффузии). В частности, понятие кластера в наборе данных количественно определяется как область, в которой вероятность выхода из этой области мала (в течение определенного времени t). Следовательно, t не только служит параметром времени, но также выполняет двойную роль параметра масштаба.
Собственное разложение матрицы дает
где - последовательность собственных значений а также а также - биортогональные правый и левый собственные векторы соответственно. Из-за спада спектра собственных значений для достижения заданной относительной точности в этой сумме необходимо всего несколько членов.
Параметр и оператор диффузии
Причина введения шага нормализации, включающего заключается в настройке влияния плотности точек данных на бесконечно малый переход диффузии. В некоторых приложениях выборка данных обычно не связана с геометрией многообразия, которое мы хотим описать. В этом случае мы можем установитьа оператор диффузии аппроксимирует оператор Лапласа – Бельтрами. Затем мы восстанавливаем риманову геометрию набора данных независимо от распределения точек. Для описания долговременного поведения точечного распределения системы стохастических дифференциальных уравнений можно использоватьи полученная цепь Маркова аппроксимирует диффузию Фоккера – Планка . С участием, он сводится к классической лапласианской нормировке графа.
Расстояние диффузии
Расстояние диффузии во время между двумя точками можно измерить как схожесть двух точек в пространстве наблюдения со связностью между ними. Это дается
где - стационарное распределение цепи Маркова, заданное первым левым собственным вектором . Ясно:
Интуитивно мала, если есть большое количество коротких путей, соединяющих а также . Есть несколько интересных особенностей, связанных с расстоянием диффузии, на основе нашего предыдущего обсуждения, которое также служит параметром масштаба:
- Очки ближе по заданному масштабу (как указано ), если они сильно связаны в графе, что подчеркивает концепцию кластера.
- Это расстояние устойчиво к шуму, поскольку расстояние между двумя точками зависит от всех возможных путей длины. между точками.
- С точки зрения машинного обучения расстояние учитывает все свидетельства, связывающие к , что позволяет нам сделать вывод, что это расстояние подходит для разработки алгоритмов вывода, основанных на подавляющем большинстве. [3]
Процесс диффузии и низкоразмерное встраивание
Расстояние диффузии можно рассчитать с использованием собственных векторов по формуле
Таким образом, собственные векторы можно использовать как новый набор координат для данных. Карта диффузии определяется как:
Из-за спада спектра достаточно использовать только первые k собственных векторов и собственных значений. Таким образом, мы получаем карту диффузии из исходных данных в k- мерное пространство, которое встроено в исходное пространство.
В [6] доказано, что
таким образом, евклидово расстояние в координатах диффузии приближается к расстоянию диффузии.
Алгоритм
Базовая структура алгоритма карты диффузии выглядит следующим образом:
Шаг 1. Учитывая сходство матрицы L .
Шаг 2. Нормализовать матрицу по параметру : .
Шаг 3. Сформируем нормализованную матрицу .
Шаг 4. Вычислить k наибольших собственных значений и соответствующие собственные векторы.
Шаг 5. Используйте карту диффузии, чтобы получить вложение. .
Заявление
В статье [6] Nadler et. al. показал, как сконструировать ядро, воспроизводящее диффузию, индуцированную уравнением Фоккера – Планка . Кроме того, они объяснили, что, когда данные аппроксимируют многообразие, можно восстановить геометрию этого многообразия, вычислив приближение оператора Лапласа – Бельтрами . Это вычисление совершенно нечувствительно к распределению точек и поэтому обеспечивает разделение статистики и геометрии данных. Поскольку карты диффузии дают общее описание набора данных, они могут измерять расстояния между парой точек выборки в коллекторе, в который встроены данные. Приложения, основанные на диффузионных картах, включают распознавание лиц , [7] спектральную кластеризацию , низкоразмерное представление изображений, сегментацию изображений, [8] сегментацию 3D-моделей, [9] проверку говорящего [10] и идентификацию, [11] выборку на коллекторах, аномалии обнаружение, [12] [13] рисование изображения, [14] выявление организации сетей состояния покоя мозга [15] и так далее.
Смотрите также
Рекомендации
- ^ Койфман, RR; Lafon, S; Ли, AB; Maggioni, M; Надлер, Б; Warner, F; Цукер, SW (2005). «Геометрические диффузии как инструмент гармонического анализа и определения структуры данных: карты диффузии» . PNAS . 102 (21): 7426–7431. Bibcode : 2005PNAS..102.7426C . DOI : 10.1073 / pnas.0500334102 . PMC 1140422 . PMID 15899970 .
- ^ Койфман, Р.Р .; Lafon, S; Ли, AB; Maggioni, M; Надлер, Б; Warner, F; Цукер, SW (2005). «Геометрические диффузии как инструмент гармонического анализа и определения структуры данных: многомасштабные методы» . PNAS . 102 (21): 7432–7437. Bibcode : 2005PNAS..102.7432C . DOI : 10.1073 / pnas.0500896102 . PMC 1140426 . PMID 15899969 .
- ^ а б в Койфман, Р.Р .; С. Лафон. (2006). «Карты диффузии». Прикладной и вычислительный гармонический анализ . 21 : 5–30. DOI : 10.1016 / j.acha.2006.04.006 .
- ^ Лафон, СС (2004). Карты диффузии и геометрические гармоники (PDF) (PhD). Йельский университет.
- ^ De la Porte, J .; Herbst, BM; Хереман, Вт; Ван дер Уолт, SJ (2008). «Введение в карты диффузии». Материалы девятнадцатого ежегодного симпозиума Ассоциации распознавания образов Южной Африки (PRASA) . CiteSeerX 10.1.1.309.674 .
- ^ а б Надлер, Вооз; Стефан Лафон; Рональд Р. Койфман; Иоаннис Г. Кеврекидис (2005). "Карты диффузии, спектральная кластеризация и собственные функции операторов Фоккера – Планка" (PDF) . Достижения в системах обработки нейронной информации . 18 . arXiv : math / 0506090 . Bibcode : 2005math ...... 6090N .
- ^ Баркан, Орен; Вейл, Джонатан; Вольф, Лиор; Ароновиц, Хагай. «Быстрое распознавание лиц с большим векторным умножением» (PDF) . Материалы Международной конференции IEEE по компьютерному зрению 2013 : 1960–1967.
- ^ Зеев, Фарбман; Фаттал Раанан; Лищинский Дани (2010). «Карты диффузии для редактирования изображений с учетом границ». ACM Trans. График . 29 (6): 145: 1–145: 10. DOI : 10.1145 / 1882261.1866171 .
- ^ Оана, Сиди; ван Кайк, Оливер; Клейман, Янир; Чжан, Хао; Коэн-Ор, Даниэль (2011). Неконтролируемая совместная сегментация набора фигур с помощью спектральной кластеризации в пространстве дескрипторов (PDF) . Транзакции ACM на графике .
- ^ Баркан, Орен; Ароновиц, Хагай (2013). «Карты распространения для проверки говорящих на основе PLDA» (PDF) . Труды Международной конференции IEEE по акустике, речи и обработке сигналов (ICASSP) : 7639–7643.
- ^ Михалевский, Ян; Талмон, Ронен; Коэн, Израиль (2011). «Идентификация выступающих с использованием карт диффузии» (PDF) . Неизвестный параметр
|conference=
игнорируется ( справка );Цитировать журнал требует|journal=
( помощь ) - ^ Мишне, Гал; Коэн, Израиль (2013). «Обнаружение многомасштабных аномалий с использованием карт диффузии». Избранные темы IEEE в обработке сигналов . 7 (1): 111–123. Bibcode : 2013ISTSP ... 7..111M . DOI : 10,1109 / jstsp.2012.2232279 . S2CID 1954466 .
- ^ Шабат, Гиль; Сегев, Давид; Авербух, Амир (2018-01-07). «Выявление неизвестных неизвестных в больших данных финансовых услуг с помощью неконтролируемых методологий: нынешние и будущие тенденции» . KDD 2017 Семинар по обнаружению аномалий в финансах . 71 : 8–19.
- ^ Гепштейн, Шай; Келлер, Йози (2013). «Дополнение изображения диффузионными картами и спектральной релаксацией». IEEE Transactions по обработке изображений . 22 (8): 2983–2994. Bibcode : 2013ITIP ... 22.2983G . DOI : 10.1109 / tip.2013.2237916 . PMID 23322762 . S2CID 14375333 .
- ^ https://www.pnas.org/content/113/44/12574.short