Дистанция земляных движителей - Earth movers distance

В статистике расстояние землекопа (EMD) это мера расстояния между двумя распределения вероятностей по регионуD. В математике это известно как Метрика Вассерштейна. Неформально, если раздачи интерпретируются как два разных способа накопления определенного количества грязи по региону DEMD - минимальная стоимость превращения одной сваи в другую; где предполагается, что стоимость равна количеству перемещенной грязи, умноженному на расстояние которым он перемещается.^[1]

Приведенное выше определение действительно только в том случае, если два распределения имеют одинаковый интеграл (неформально, если две стопки имеют одинаковое количество грязи), как в нормализованном гистограммы или же функции плотности вероятности. В этом случае EMD эквивалентен 1-му Расстояние Мальлоу или 1-е расстояние Вассерштейна между двумя дистрибутивами.^[2][3]

Теория

Предположим, что у нас есть набор точек в ${\textstyle \mathbb {R} ^{d}}$ (измерение ${\textstyle d}$). Вместо того, чтобы назначать одно распределение набору точек, мы можем кластеризовать их и представить набор точек в терминах кластеров. Таким образом, каждый кластер представляет собой единую точку в ${\textstyle \mathbb {R} ^{d}}$ и вес кластера определяется долей распределения, присутствующей в этом кластере. Такое представление распределения набором кластеров называется подпись. Две сигнатуры могут иметь разные размеры, например, бимодальное распределение имеет более короткую сигнатуру (2 кластера), чем комплексные. Одно представление кластера (среднее значение или режим в ${\textstyle \mathbb {R} ^{d}}$) можно рассматривать как отдельный элемент подписи. Расстояние между каждой из функций называется расстояние до земли.

Расстояние земного движителя можно сформулировать и решить как транспортная проблема. Предположим, что несколько поставщиков, каждый с заданным количеством товаров, должны снабжать нескольких потребителей, каждый с заданной ограниченной производительностью. Для каждой пары поставщик-потребитель указана стоимость перевозки отдельной единицы товара. Тогда проблема транспортировки состоит в том, чтобы найти наименее затратный поток товаров от поставщиков к потребителям, который удовлетворяет спрос потребителей. Точно так же здесь проблема заключается в преобразовании одной подписи (${\textstyle P}$) другому(${\textstyle Q}$) с минимумом проделанной работы.

Предположим, что подпись ${\textstyle P}$ имеет ${\textstyle m}$ кластеры с ${\textstyle P=\{(p_{1},w_{p1}),(p_{2},w_{p2}),...,(p_{m},w_{pm})\}}$, куда ${\textstyle p_{i}}$ является представителем кластера и ${\textstyle w_{pi}>0}$ - вес кластера. Аналогично другая подпись ${\textstyle Q=\{(q_{1},w_{q1}),(q_{2},w_{q2}),...,(q_{n},w_{qn})\}}$ имеет ${\textstyle n}$ кластеры. Позволять ${\textstyle D=[d_{i,j}]}$ быть земным расстоянием между кластерами ${\textstyle p_{i}}$ и ${\textstyle q_{j}}$.

Мы хотим найти поток ${\textstyle F=[f_{i,j}]}$, с ${\textstyle f_{i,j}}$ поток между ${\textstyle p_{i}}$ и ${\textstyle q_{j}}$, что сводит к минимуму общую стоимость.

${\displaystyle \min {\sum _{i=1}^{m}\sum _{j=1}^{n}f_{i,j}d_{i,j}}}$

с учетом ограничений:

${\displaystyle f_{i,j}\geq 0,1\leq i\leq m,1\leq j\leq n}$

${\displaystyle \sum _{j=1}^{n}{f_{i,j}}\leq w_{pi},1\leq i\leq m}$

${\displaystyle \sum _{i=1}^{m}{f_{i,j}}\leq w_{qj},1\leq j\leq n}$

${\displaystyle \sum _{i=1}^{m}\sum _{j=1}^{n}f_{i,j}=\min \left\{\ \sum _{i=1}^{m}w_{pi},\quad \sum _{j=1}^{n}w_{qj}\ \right\}}$

Оптимальный поток ${\textstyle F}$ находится путем решения этой задачи линейной оптимизации. Дальность землеройного двигателя определяется как работа, нормированная на общий расход:

${\displaystyle {\text{EMD}}(P,Q)={\frac {\sum _{i=1}^{m}\sum _{j=1}^{n}f_{i,j}d_{i,j}}{\sum _{i=1}^{m}\sum _{j=1}^{n}f_{i,j}}}}$

Расширения

В некоторых приложениях может потребоваться сравнение распределений с разной полной массой. Один из подходов - позволить частичное совпадение, где грязь из самого массового распределения перестраивается, чтобы сделать наименее массивным, а вся оставшаяся "грязь" отбрасывается бесплатно. При таком подходе EMD больше не является истинным расстоянием между распределениями.

Другой подход состоит в том, чтобы разрешить создание или уничтожение массы на глобальном и / или локальном уровне в качестве альтернативы транспортировке, но со штрафом. В этом случае необходимо указать реальный параметр σ, соотношение между стоимостью создания или уничтожения одной единицы «грязи» и стоимостью ее транспортировки на единицу расстояния. Это эквивалентно минимизации суммы затрат на перемещение земли плюс σ, умноженное на L¹ расстояние между переставленной стопкой и второй раздачей.

Условно, если ${\displaystyle \pi :P\to Q}$ это частичная функция который является биекция на подмножествах ${\displaystyle P'\subset P}$ и ${\displaystyle Q'\subset Q}$, то интересует функция расстояния

${\displaystyle |P-Q|_{\pi }=|P\setminus P'|+|Q\setminus Q'|}$

куда ${\displaystyle P\setminus P'}$ обозначает установить минус. Здесь, ${\displaystyle P'}$ будет перемещенной частью земли; таким образом ${\displaystyle P\setminus P'}$ будет часть не перемещена, и ${\displaystyle |P\setminus P'|}$ размер стопки не перемещается. Симметрично созерцая ${\displaystyle Q'\subset Q}$ как куча в пункте назначения, которая "попала туда" из п, по сравнению с общим Q что мы хочу иметь там. Формально это расстояние показывает, насколько инъективный переписка отличается от изоморфизм.

EMD можно естественным образом расширить на случай, когда сравнивается более двух распределений. В этом случае «расстояние» между множеством распределений определяется как оптимальное значение линейной программы. Этот обобщенный EMD может быть точно вычислен с использованием жадного алгоритма, и было показано, что результирующий функционал равен Добавка Минковского и выпуклый монотонный. ^[4]

Вычисление EMD

EMD можно вычислить, решив экземпляр транспортная проблема, используя любой алгоритм для проблема минимальных затрат, например то сетевой симплексный алгоритм.

Венгерский алгоритм можно использовать для получения решения, если домен D - это множество {0, 1}. Если область целочисленная, ее можно преобразовать для того же алгоритма, представив целые интервалы как несколько двоичных интервалов.

В частном случае, если D представляет собой одномерный массив «ящиков», который можно эффективно вычислить EMD, сканируя массив и отслеживая, сколько грязи необходимо транспортировать между последовательными ящиками:

${\displaystyle {\begin{array}{rl}{\text{EMD}}_{0}&=0\\{\text{EMD}}_{i+1}&=P_{i}+{\text{EMD}}_{i}-Q_{i}\\{\text{Total Distance}}&=\sum |{\text{EMD}}_{i}|\end{array}}}$

Анализ подобия на основе EMD

Анализ подобия на основе EMD (EMDSA) - важный и эффективный инструмент во многих поиск мультимедийной информации^[5] и распознавание образов^[6] Приложения. Однако вычислительные затраты на EMD суперкубичны по отношению к количеству «бинов», заданных произвольным «D». Эффективные и масштабируемые методы вычисления EMD для крупномасштабных данных были исследованы с использованием Уменьшение карты,^[7][8] а также объемная синхронная параллель и устойчивый распределенный набор данных.^[9]

Приложения

Одним из первых применений EMD в информатике было сравнение двух оттенки серого изображения, которые могут отличаться из-за дизеринг, размытость или локальные деформации.^[10] В этом случае область - это область изображения, а общее количество света (или чернил) - это «грязь», которую нужно перестроить.

EMD широко используется в поиск изображений на основе содержимого для вычисления расстояний между цветные гистограммы из двух цифровые изображения.^{[нужна цитата ]} В этом случае регион - это Цветовой куб RGB, а каждый пиксель изображения - это кусок «грязи». Тот же метод можно использовать для любого другого количественного пиксель атрибут, например яркость, градиент, кажущееся движение в кадр видео, так далее..

В более общем плане EMD используется в распознавание образов для сравнения общих сводок или суррогатов записей данных, называемых подписи. Типичная подпись состоит из списка пар ((Икс₁,м₁), ... (Икс_п,м_п)), где каждый Икс_я это определенная «особенность» (например, цвет изображения, буква в тексте и т. д.), и м_я "масса" (сколько раз эта функция встречается в записи). В качестве альтернативы, Икс_я может быть центроид из кластер данных, и м_я количество объектов в этом кластере. Чтобы сравнить две такие сигнатуры с EMD, необходимо определить расстояние между элементами, которое интерпретируется как стоимость преобразования единицы массы одного объекта в единицу массы другого. EMD между двумя подписями - это минимальная стоимость превращения одной из них в другую.

EMD-анализ использовался для количественной оценки многомерных изменений в биомаркеры измеряется проточной цитометрии, с потенциальными приложениями к другим технологиям, которые сообщают о распределении измерений.^[11]

История

Концепция была впервые представлена Гаспар Монж в 1781 г.,^[12] в контексте теория транспорта. Использование EMD в качестве меры расстояния для монохроматических изображений было описано в 1989 году S. Peleg, M. Werman и H. Rom.^[10] Название «дистанция землекопов» было предложено J. Stolfi в 1994 г.^[13] и был использован в печати в 1998 г. Ю. Рубнером, К. Томази и Л. Г. Гибас.^[14]

Рекомендации

1. Формальное определение
2. Елизавета Левина; Питер Бикель (2001). «Расстояние EarthMover - это расстояние Mallows: некоторые выводы из статистики». Материалы ICCV 2001. Ванкувер, Канада: 251–256.
3. К. Л. Мэллоуз (1972). «Замечание об асимптотической совместной нормальности». Анналы математической статистики. 43 (2): 508–515. Дои:10.1214 / aoms / 1177692631.
4. Клайн, Джеффри (2019). «Свойства d-мерной задачи землекопа». Дискретная прикладная математика. 265: 128–141. Дои:10.1016 / j.dam.2019.02.042.
5. Марк А. Рузон; Карло Томази (2001). «Обнаружение краев, стыков и углов с использованием цветового распределения». IEEE Transactions по анализу шаблонов и машинному анализу.
6. Кристен Грауман; Тревор Даррел (2004). «Быстрое сопоставление контуров с использованием приблизительного расстояния землекопа». Материалы CVPR 2004 г..
7. Цзинь Хуан; Руи Чжан; Раджкумар Буйя; Цзянь Чен (2014). «MELODY-Join: сходство расстояний для эффективных землеройных машин с использованием MapReduce». Труды Международной конференции IEEE по инженерии данных.
8. Цзя Сюй; Бин Лэй; Ю Гу; Winslett, M ​​.; Ге Ю; Чжэньцзе Чжан (2015). «Эффективное соединение сходства на основе расстояния от землекопа с использованием MapReduce». IEEE Transactions по разработке знаний и данных.
9. Цзинь Хуан; Руи Чжан; Раджкумар Буйя; Jian Chen, M .; Юнвэй Ву (2015). «Heads-Join: эффективное соединение на расстоянии от Earth Mover на Hadoop». Транзакции IEEE в параллельных и распределенных системах.
10. С. Пелег; М. Верман; Х. Ром (1989). «Единый подход к изменению разрешения: пространство и уровень серого». IEEE Transactions по анализу шаблонов и машинному анализу. 11 (7): 739–742. Дои:10.1109/34.192468.
11. Орлова Д.Ю .; Циммерман, Н; Михан, C; Михан, S; Waters, Дж; Гон, EEB (23 марта 2016 г.). «Расстояние земного движителя (EMD): истинный показатель для сравнения уровней экспрессии биомаркеров в клеточных популяциях». PLOS One. 11 (3): e0151859. Дои:10.1371 / journal.pone.0151859. Получено 14 января 2020.
12. "Mémoire sur la theorie des déblais et des remblais". Histoire de l'Académie Royale des Science, Année 1781, avec les Mémoires de Mathématique et de Physique. 1781.
13. J. Stolfi, личное сообщение L. J. Guibas, 1994, цитируется Рубнер, Йосси; Томази, Карло; Гибас, Леонидас Дж. (2000). «Расстояние землечерпалки как показатель для поиска изображений» (PDF). Международный журнал компьютерного зрения. 40 (2): 99–121. Дои:10.1023 / А: 1026543900054.
14. Йоси Рубнер; Карло Томази; Леонидас Дж. Гибас (1998). «Метрика для распределений с приложениями к базам данных изображений». Слушания ICCV 1998: 59–66. Дои:10.1109 / ICCV.1998.710701. ISBN  81-7319-221-9.

внешняя ссылка

• C-код для расстояния земного движителя
• Реализация Python со ссылками
• Обертка Python2 для реализации C для Earth Mover's Distance
• Код оболочки C ++, Matlab и Java для расстояния Earth Mover's Distance, особенно эффективен для пороговых расстояний от земли
• Реализация на Java универсального генератора для оценки крупномасштабного анализа подобия на основе расстояния Earth Mover