Расстояние редактирования графика

В математике и информатике ( расстояние редактирования графа GED ) является мерой сходства (или несходства) между двумя графами .Концепция расстояния редактирования графа была впервые математически формализована Альберто Санфелиу и Кинг-Сунь Фу в 1983 году. ^[1]Основное применение расстояния редактирования графа заключается в неточном сопоставлении графов , напримеркак устойчивое к ошибкам распознавание образов в машинном обучении . ^[2]

Расстояние редактирования графика между двумя графиками связано с расстояние редактирования строки между строками .С интерпретацией строк как связные ациклические ориентированные графы максимальная степень один, классические определениярасстояния редактирования, такого как расстояние Левенштейна , ^[3]^[4]Расстояние Хэмминга ^[5]а расстояние Джаро – Винклера можно интерпретировать как расстояния редактирования графика.между соответствующим образом ограниченными графами. Аналогично, расстояние редактирования графикатакже обобщение расстояния редактирования дерева между деревья с корнями . ^[6]^[7]^[8]^[9]

Формальные определения и свойства [ править ]

Математическое определение расстояния редактирования графика зависит от определенийграфы, на которых он определен, т. е. являются ли вершины и ребра графа и если да, то каким образом.граф помечен ли его ребра и направлены .Обычно, учитывая набор операций редактирования графа (также известных как элементарные операции графа ), расстояние редактирования графа между двумя графами $g_{1}$ и $g_{2}$ , записанный как $GED(g_{1},g_{2})$ может быть определен как

GED(g_{1},g_{2})=\min _{(e_{1},...,e_{k})\in {\mathcal {P}}(g_{1},g_{2})}\sum _{i=1}^{k}c(e_{i})

где ${\mathcal {P}}(g_{1},g_{2})$ обозначает набор путей редактирования, преобразующих $g_{1}$ в (граф, изоморфный ) $g_{2}$ и $c(e)\geq 0$ — стоимость каждой операции редактирования графика $e$ .

Набор элементарных операторов редактирования графа обычно включает в себя:

вставка вершин для введения в граф одной новой помеченной вершины.

удаление вершин для удаления одной (часто несвязной) вершины из графа.

подстановка вершин для изменения метки (или цвета) данной вершины.

вставка ребра , чтобы ввести новое цветное ребро между парой вершин.

удаление ребер для удаления одного ребра между парой вершин.

подстановка ребра для изменения метки (или цвета) данного ребра.

Дополнительные, но менее распространенные операторы включают такие операции, как разделение ребер , которое вводит новую вершину в ребро (также создавая новое ребро), и сжатие ребра , которое удаляет вершины второй степени между ребрами (одного и того же цвета). Хотя такие сложные операторы редактирования можно определить с помощью более элементарных преобразований, их использование позволяет более точно параметризовать функцию стоимости. $c$ когда оператор дешевле суммы его составляющих.

Глубокий анализ операторов редактирования элементарных графов представлен в ^[10]^[11]^[12]

И были представлены некоторые методы для автоматического вывода этих элементарных операторов редактирования графа. ^[13]^[14]^[15]^[16]^[17] Некоторые алгоритмы изучают эти затраты онлайн: ^[18]

Приложения [ править ]

Расстояние редактирования графика находит применение в распознавании рукописного ввода , ^[19] распознавание отпечатков пальцев ^[20] и хеминформатика . ^[21]

Алгоритмы и сложность [ править ]

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

Помимо точных алгоритмов известен также ряд эффективных алгоритмов аппроксимации. Большинство из них имеют кубическое время вычислений. ^[22]^[23]^[24]^[25]^[26]

Более того, существует алгоритм, который выводит аппроксимацию ОЭД за линейное время. ^[27]

Несмотря на то, что приведенные выше алгоритмы иногда хорошо работают на практике, в целом проблема вычисления расстояния редактирования графа является NP-трудной (доказательство, доступное в Интернете, см. в разделе 2 работы Zeng et al. ) и даже трудно аппроксимировать (формально, это APX- сложно ^[28]).

Ссылки [ править ]

^ Санфелиу, Альберто; Фу, Король-Солнце (1983). «Мера расстояния между атрибутированными реляционными графами для распознавания образов». Транзакции IEEE по системам, человеку и кибернетике . 13 (3): 353–363. дои : 10.1109/TSMC.1983.6313167 . S2CID 1087693 .
^ Гао, Синьбо; Сяо, Бин; Тао, Даченг; Ли, Сюэлун (2010). «Обзор расстояния редактирования графика». Анализ шаблонов и приложения . 13 : 113–129. дои : 10.1007/s10044-008-0141-y .
^ Влади́мир И. Левенштейн (1965). Двоичные коды с исправлением выпадений, вставок и замещений символов [Binary codes capable of correcting deletions, insertions, and reversals]. Доклады Академий Наук СССР (in Russian). 163 (4): 845–848.
^ Левенштейн, Владимир Иванович (февраль 1966 г.). «Двоичные коды, способные исправлять удаления, вставки и обращения». Доклады советской физики . 10 (8): 707–710.
^ Хэмминг, Ричард В. (1950). «Коды обнаружения и исправления ошибок» (PDF) . Технический журнал Bell System . 29 (2): 147–160. дои : 10.1002/j.1538-7305.1950.tb00463.x . hdl : 10945/46756 . МР 0035935 . S2CID 61141773 . Архивировано из оригинала 25 мая 2006 г. {{cite journal}}: CS1 maint: bot: исходный статус URL неизвестен ( ссылка )
^ Шаша, Д; Чжан, К. (1989). «Простые быстрые алгоритмы редактирования расстояния между деревьями и связанные с этим проблемы». СИАМ Дж. Компьютер. 18 (6): 1245–1262. CiteSeerX 10.1.1.460.5601 . дои : 10.1137/0218082 . S2CID 10970317 .
^ Чжан, К. (1996). «Ограниченное расстояние редактирования между неупорядоченными помеченными деревьями». Алгоритмика . 15 (3): 205–222. дои : 10.1007/BF01975866 . S2CID 20043881 .
^ Билле, П. (2005). «Опрос о расстоянии редактирования дерева и связанных с этим проблемах» . Теор. Вычислить. наук. 337 (1–3): 22–34. CiteSeerX 10.1.1.100.2577 . дои : 10.1016/j.tcs.2004.12.030 .
^ Демейн, Эрик Д .; Мозес, Шей; Россман, Бенджамин; Вейманн, Орен (2010). «Оптимальный алгоритм декомпозиции для расстояния редактирования дерева». Транзакции ACM на алгоритмах . 6 (1): А2. arXiv : cs/0604037 . CiteSeerX 10.1.1.163.6937 . дои : 10.1145/1644015.1644017 . МР 2654906 . S2CID 7878119 .
^ Серратоза, Франческ (2021). Переопределение расстояния редактирования графика . SN Computer Science, стр: 2-438.
^ Серратоза, Франческ (2019). Расстояние редактирования графика: ограничения могут быть метрикой . Распознавание образов, 90, стр: 250–256.
^ Серратоза, Франческ; Кортес, Ксавье (2015). Расстояние редактирования графа: переход от глобальной к локальной структуре для решения проблемы сопоставления графов . Письма о распознавании образов, 65, стр: 204–210.
^ Сантакрус, Пеп; Серратоза, Франческ (2020). Изучение затрат на редактирование графа на основе модели обучения, применяемой для неоптимального сопоставления графов . Письма о нейронной обработке, 51, стр: 881–904.
^ Алгабли, Шайма; Серратоза, Франческ (2018). Внедрение сопоставлений между узлами для изучения параметров расстояния редактирования графика . Письма о распознавании образов, 112, стр: 353–360.
^ Ксавье, Кортес; Серратоза, Франческ (2016). Обучение сопоставлению весов замены графа на основе соответствия основного истинного узла . Международный журнал распознавания образов и искусственного интеллекта, 30 (2), стр: 1650005 [22 страницы].
^ Ксавье, Кортес; Серратоза, Франческ (2015). Стоимость редактирования сопоставления графов на основе оптимальности соответствий узлов Oracle . Письма о распознавании образов, 56, стр: 22–29.
^ Конте, Донателло; Серратоза, Франческ (2020). Интерактивное онлайн-обучение сопоставлению графиков с использованием активных стратегий . Системы, основанные на знаниях, 105, стр: 106275.
^ Рика, Елена; Альварес, Сусана; Серратоза, Франческ (2021). Он-лайн обучение графику редактирования затрат на расстояние . Письма о распознавании образов, 146, стр: 52–62.
^ Фишер, Андреас; Суен, Чинг Ю.; Фринкен, Фолькмар; Ризен, Каспар; Бунке, Хорст (2013), «Алгоритм быстрого сопоставления для распознавания рукописного текста на основе графов», Представления на основе графов в распознавании образов , Конспекты лекций по информатике , том. 7877, стр. 194–203, номер doi : 10.1007/978-3-642-38221-5_21 , ISBN. 978-3-642-38220-8
^ Нойхаус, Мишель; Бунке, Хорст (2005), «Подход к классификации отпечатков пальцев на основе сопоставления графов с использованием направленной дисперсии», Биометрическая аутентификация человека на основе аудио и видео , Конспекты лекций по информатике , том. 3546, стр. 191–200, номер документа : 10.1007/11527923_20 , ISBN. 978-3-540-27887-0
^ Бирчалл, Кристиан; Жилле, Валери Дж.; Харпер, Гэвин; Пикетт, Стивен Д. (январь 2006 г.). «Меры сходства обучения для конкретных действий: применение к сокращенным графам». Журнал химической информации и моделирования . 46 (2): 557–586. дои : 10.1021/ci050465e . ПМИД 16562986 .
^ Нойхаус, Мишель; Бунке, Хорст (ноябрь 2007 г.). Преодоление разрыва между расстоянием редактирования графа и машинами с ядром . Машинное восприятие и искусственный интеллект. Том. 68. Всемирный научный. ISBN 978-9812708175 .
^ Ризен, Каспар (февраль 2016 г.). Распознавание структурных образов с расстоянием редактирования графика: алгоритмы аппроксимации и приложения . Достижения в области компьютерного зрения и распознавания образов. Спрингер. ISBN 978-3319272511 .
^ Серратоза, Франческ (2014). Быстрое вычисление сопоставления двудольных графов . Письма о распознавании образов, 45, стр: 244–250.
^ Серратоза, Франческ (2015). Ускорение быстрого сопоставления двудольных графов за счет новой матрицы затрат . Международный журнал распознавания образов и искусственного интеллекта, 29 (2), 1550010, [17 страниц].
^ Серратоза, Франческ (2015). Вычисление расстояния редактирования графа: рассуждения об оптимальности и ускорении . Image and Vision Computing, 40, стр: 38-48.
^ Сантакрус, Пеп; Серратоза, Франческ (2018). Устойчивое к ошибкам сопоставление графов с линейными вычислительными затратами с использованием начального небольшого частичного сопоставления . Буквы распознавания образов.
^ Линь, Чи-Лонг (25 августа 1994 г.). «Трудность аппроксимирующей задачи преобразования графов». В Ду, Дин-Чжу; Чжан, Сян-Сунь (ред.). Алгоритмы и вычисления . Конспекты лекций по информатике. Том. 834. Шпрингер Берлин Гейдельберг. стр. 74–82. дои : 10.1007/3-540-58325-4_168 . ISBN 9783540583257 .

[1] Санфелиу, Альберто; Фу, Король-Солнце (1983). «Мера расстояния между атрибутированными реляционными графами для распознавания образов». Транзакции IEEE по системам, человеку и кибернетике . 13 (3): 353–363. дои : 10.1109/TSMC.1983.6313167 . S2CID 1087693 .

[2] Гао, Синьбо; Сяо, Бин; Тао, Даченг; Ли, Сюэлун (2010). «Обзор расстояния редактирования графика». Анализ шаблонов и приложения . 13 : 113–129. дои : 10.1007/s10044-008-0141-y .

[3] Влади́мир И. Левенштейн (1965). Двоичные коды с исправлением выпадений, вставок и замещений символов [Binary codes capable of correcting deletions, insertions, and reversals]. Доклады Академий Наук СССР (in Russian). 163 (4): 845–848.

[4] Левенштейн, Владимир Иванович (февраль 1966 г.). «Двоичные коды, способные исправлять удаления, вставки и обращения». Доклады советской физики . 10 (8): 707–710.

[5] Хэмминг, Ричард В. (1950). «Коды обнаружения и исправления ошибок» (PDF) . Технический журнал Bell System . 29 (2): 147–160. дои : 10.1002/j.1538-7305.1950.tb00463.x . hdl : 10945/46756 . МР 0035935 . S2CID 61141773 . Архивировано из оригинала 25 мая 2006 г. {{cite journal}}: CS1 maint: bot: исходный статус URL неизвестен ( ссылка )

[6] Шаша, Д; Чжан, К. (1989). «Простые быстрые алгоритмы редактирования расстояния между деревьями и связанные с этим проблемы». СИАМ Дж. Компьютер. 18 (6): 1245–1262. CiteSeerX 10.1.1.460.5601 . дои : 10.1137/0218082 . S2CID 10970317 .

[7] Чжан, К. (1996). «Ограниченное расстояние редактирования между неупорядоченными помеченными деревьями». Алгоритмика . 15 (3): 205–222. дои : 10.1007/BF01975866 . S2CID 20043881 .

[8] Билле, П. (2005). «Опрос о расстоянии редактирования дерева и связанных с этим проблемах» . Теор. Вычислить. наук. 337 (1–3): 22–34. CiteSeerX 10.1.1.100.2577 . дои : 10.1016/j.tcs.2004.12.030 .

[9] Демейн, Эрик Д .; Мозес, Шей; Россман, Бенджамин; Вейманн, Орен (2010). «Оптимальный алгоритм декомпозиции для расстояния редактирования дерева». Транзакции ACM на алгоритмах . 6 (1): А2. arXiv : cs/0604037 . CiteSeerX 10.1.1.163.6937 . дои : 10.1145/1644015.1644017 . МР 2654906 . S2CID 7878119 .

[10] Серратоза, Франческ (2021). Переопределение расстояния редактирования графика . SN Computer Science, стр: 2-438.

[11] Серратоза, Франческ (2019). Расстояние редактирования графика: ограничения могут быть метрикой . Распознавание образов, 90, стр: 250–256.

[12] Серратоза, Франческ; Кортес, Ксавье (2015). Расстояние редактирования графа: переход от глобальной к локальной структуре для решения проблемы сопоставления графов . Письма о распознавании образов, 65, стр: 204–210.

[13] Сантакрус, Пеп; Серратоза, Франческ (2020). Изучение затрат на редактирование графа на основе модели обучения, применяемой для неоптимального сопоставления графов . Письма о нейронной обработке, 51, стр: 881–904.

[14] Алгабли, Шайма; Серратоза, Франческ (2018). Внедрение сопоставлений между узлами для изучения параметров расстояния редактирования графика . Письма о распознавании образов, 112, стр: 353–360.

[15] Ксавье, Кортес; Серратоза, Франческ (2016). Обучение сопоставлению весов замены графа на основе соответствия основного истинного узла . Международный журнал распознавания образов и искусственного интеллекта, 30 (2), стр: 1650005 [22 страницы].

[16] Ксавье, Кортес; Серратоза, Франческ (2015). Стоимость редактирования сопоставления графов на основе оптимальности соответствий узлов Oracle . Письма о распознавании образов, 56, стр: 22–29.

[17] Конте, Донателло; Серратоза, Франческ (2020). Интерактивное онлайн-обучение сопоставлению графиков с использованием активных стратегий . Системы, основанные на знаниях, 105, стр: 106275.

[18] Рика, Елена; Альварес, Сусана; Серратоза, Франческ (2021). Он-лайн обучение графику редактирования затрат на расстояние . Письма о распознавании образов, 146, стр: 52–62.

[19] Фишер, Андреас; Суен, Чинг Ю.; Фринкен, Фолькмар; Ризен, Каспар; Бунке, Хорст (2013), «Алгоритм быстрого сопоставления для распознавания рукописного текста на основе графов», Представления на основе графов в распознавании образов , Конспекты лекций по информатике , том. 7877, стр. 194–203, номер doi : 10.1007/978-3-642-38221-5_21 , ISBN. 978-3-642-38220-8

[20] Нойхаус, Мишель; Бунке, Хорст (2005), «Подход к классификации отпечатков пальцев на основе сопоставления графов с использованием направленной дисперсии», Биометрическая аутентификация человека на основе аудио и видео , Конспекты лекций по информатике , том. 3546, стр. 191–200, номер документа : 10.1007/11527923_20 , ISBN. 978-3-540-27887-0

[21] Бирчалл, Кристиан; Жилле, Валери Дж.; Харпер, Гэвин; Пикетт, Стивен Д. (январь 2006 г.). «Меры сходства обучения для конкретных действий: применение к сокращенным графам». Журнал химической информации и моделирования . 46 (2): 557–586. дои : 10.1021/ci050465e . ПМИД 16562986 .

[22] Нойхаус, Мишель; Бунке, Хорст (ноябрь 2007 г.). Преодоление разрыва между расстоянием редактирования графа и машинами с ядром . Машинное восприятие и искусственный интеллект. Том. 68. Всемирный научный. ISBN 978-9812708175 .

[23] Ризен, Каспар (февраль 2016 г.). Распознавание структурных образов с расстоянием редактирования графика: алгоритмы аппроксимации и приложения . Достижения в области компьютерного зрения и распознавания образов. Спрингер. ISBN 978-3319272511 .

[24] Серратоза, Франческ (2014). Быстрое вычисление сопоставления двудольных графов . Письма о распознавании образов, 45, стр: 244–250.

[25] Серратоза, Франческ (2015). Ускорение быстрого сопоставления двудольных графов за счет новой матрицы затрат . Международный журнал распознавания образов и искусственного интеллекта, 29 (2), 1550010, [17 страниц].

[26] Серратоза, Франческ (2015). Вычисление расстояния редактирования графа: рассуждения об оптимальности и ускорении . Image and Vision Computing, 40, стр: 38-48.

[27] Сантакрус, Пеп; Серратоза, Франческ (2018). Устойчивое к ошибкам сопоставление графов с линейными вычислительными затратами с использованием начального небольшого частичного сопоставления . Буквы распознавания образов.

[28] Линь, Чи-Лонг (25 августа 1994 г.). «Трудность аппроксимирующей задачи преобразования графов». В Ду, Дин-Чжу; Чжан, Сян-Сунь (ред.). Алгоритмы и вычисления . Конспекты лекций по информатике. Том. 834. Шпрингер Берлин Гейдельберг. стр. 74–82. дои : 10.1007/3-540-58325-4_168 . ISBN 9783540583257 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]