Grafikon szerkesztési távolság

A grafikon szerkesztési távolsága a hasonlósági (vagy eltérési) együttható két grafikon között . A gráfszerkesztési távolság fogalmát először Alberto Sanfeliu és King-San Fu fogalmazta meg matematikailag 1983-ban [1] . A grafikonszerkesztési távolság fő alkalmazása a pontatlan gráfillesztésben , például a robusztus mintafelismerésben a gépi tanulásban [2] .

A grafikon két grafikon közötti szerkesztési távolsága a sorok közötti szerkesztési távolsághoz kapcsolódik . Amikor a nyelőket összekapcsolt irányított aciklikus gráfokként értelmezzük , legfeljebb kettős fokú , a szerkesztési távolság klasszikus definíciói, mint például a Levenshtein-távolság [3] , a Hamming-távolság [4] és a Jaro-Winkler-távolság , értelmezhetők gráf-szerkesztési távolságként megfelelő grafikonok. Hasonlóképpen, a grafikon szerkesztési távolsága a fák szerkesztési távolságának általánosítása a gyökeres fák között [5] [6] [7] [8] .

Formális definíciók és tulajdonságok

A grafikonszerkesztési távolság matematikai definíciója azon grafikonok definíciójától függ, amelyekhez a távolság definiálva van. Ez például attól függ, hogy a gráf csúcsai és élei vannak-e címkézve , és hogyan, valamint attól is, hogy a gráf irányított -e . Általánosságban elmondható, hogy adott gráfszerkesztési műveletek halmaza (más néven elemi gráfműveletek ), a grafikon szerkesztési távolsága két grafikon és -ként írva - között a következőképpen definiálható: ${\displaystyle g_{1))$ ${\displaystyle 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})

ahol a transzformációs útvonalak halmazát jelenti ( a gráfhoz képest izomorf ) , és egyenlő az egyes szerkesztési műveletek költségével . ${\mathcal {P}}(g_{1},g_{2})$ ${\displaystyle g_{1))$ ${\displaystyle g_{2))$ $c(e)\geqslant 0$ $e$

Az elemi gráfműveletek halmaza általában a következőket tartalmazza:

csúcs beillesztése — egy új címkézett csúcs kerül beillesztésre a gráfba. csúcs eltávolítása – egy (gyakran nem kapcsolódó) csúcs eltávolításra kerül a gráfból. csúcs behelyettesítése - egy adott csúcs címkéjének (vagy színének) megváltoztatása. élbeillesztés – egy új színes él kerül beillesztésre a gráfba egy csúcspár közé. él eltávolítása — egy él eltávolítása egy csúcspár között. élhelyettesítés - az adott él címkéjének (vagy színének) megváltoztatása.

Ezen túlmenően, de ritkábban, olyan műveletek, mint egy él felosztása , amely új csúcsot szúr be egy élbe (ami két élt eredményez), és egy él összezsugorítása , amely eltávolítja a második fokú csúcsot az élek között (azonos színű), míg a két él összevonása egyben szerepel. Bár az ilyen összetett műveletek egyszerűbb transzformációkkal is definiálhatók, használatuk lehetővé teszi a költségfüggvény jobb paraméterezését, ha az operátor olcsóbb, mint a részek összege. $c$

Alkalmazások

A grafikonszerkesztési távolságnak vannak alkalmazásai a kézírás-felismerésben [9] , az ujjlenyomat-felismerésben [10] és a kemoinformatikában [11] .

Algoritmusok és összetettség

A gráfpárok közötti grafikonszerkesztési távolság kiszámítására szolgáló pontos algoritmusok általában a problémát a két gráf közötti minimális transzformációs út megtalálásának problémájává alakítják. Az optimális szerkesztési útvonal kiszámítása az útkeresésre vagy a legrövidebb út problémájára redukálódik , amelyet gyakran A* keresési algoritmusként valósítanak meg .

Az egzakt algoritmusok mellett számos hatékony közelítő algoritmus ismert [12] [13] .

Bár a fenti algoritmusok néha jól működnek a gyakorlatban, általában a gráf szerkesztési távolságának kiszámítása NP-teljes [14] (erre bizonyítékot talál Zeng et al. honlapján a 2. részben ), sőt nehéz közelíteni (formálisan APX kemény [15] ).

Jegyzetek

↑ Sanfeliu, Fu, 1983 , p. 353–363.
↑ Gao, Xiao, Tao, Li, 2010 , p. 113-129.
↑ Levenshtein, 1965 , p. 845–848.
↑ Hamming, 1950 , p. 147–160.
↑ Shasha és Zhang 1989 , p. 1245–1262.
↑ Zhang, 1996 , p. 205–222.
↑ Bille, 2005 , p. 22–34.
↑ Demaine, Mozes, Rossman, Weimann, 2010 , p. A2.
↑ Fischer, Suen, Frinken, Riesen, Bunke, 2013 , p. 194–203.
↑ Neuhaus, Bunke, 2005 , p. 191–200.
↑ Birchall, Gillet, Harper, Pickett, 2006 , p. 557–586.
↑ Neuhaus, Bunke, 2007 .
↑ Riesen, 2016 .
↑ Garey, Johnson, 1979 .
↑ Lin, 1994 , p. 74–82.

Irodalom

Alberto Sanfeliu, King-Sun Fu. Távolságmérés a mintafelismeréshez hozzárendelt relációs gráfok között // IEEE Transactions on Systems, Man and Cybernetics . - 1983. - T. 13 , sz. 3 . – S. 353–363 . - doi : 10.1109/TSMC.1983.6313167 .
Xinbo Gao, Bing Xiao, Dacheng Tao, Xuelong Li. A grafikonszerkesztési távolság felmérése // Mintaelemzés és alkalmazások. - 2010. - T. 13 . – 113–129 . - doi : 10.1007/s10044-008-0141-y .
Vlagyimir I. Levenstein. Bináris kódok a törlések, beillesztések és szimbólumok helyettesítésének korrekciójával // A CCCP Tudományos Akadémiáinak jelentései. - 1965. - T. 163 , sz. 4 . – S. 845–848 .
Richard W. Hamming. Hibafelismerés és hibajavító kódok // Bell System Technical Journal . - 1950. - T. 29 , sz. 2 . – S. 147–160 . - doi : 10.1002/j.1538-7305.1950.tb00463.x . Az eredetiből archiválva : 2006. május 25.
Shasha D., Zhang K. Egyszerű gyors algoritmusok a fák közötti szerkesztési távolsághoz és a kapcsolódó problémákhoz // SIAM J. Comput. . - 1989. - T. 18 , 6. sz . - S. 1245-1262 . - doi : 10.1137/0218082 .
Zhang K. Korlátozott szerkesztési távolság rendezetlen címkézett fák között // Algorithmica . - 1996. - T. 15 , 3. sz . – S. 205–222 . - doi : 10.1007/BF01975866 .
Bille P. Felmérés a fa szerkesztési távolságáról és a kapcsolódó problémákról // Theor. Comput. sci. . - 2005. - T. 337 , sz. 1–3 . – S. 22–34 . - doi : 10.1016/j.tcs.2004.12.030 .
Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann. Optimális dekompozíciós algoritmus a fa szerkesztési távolságához // ACM Transactions on Algorithms . - 2010. - T. 6 , sz. 1 . - S. A2 . - doi : 10.1145/1644015.1644017 .
Andreas Fischer, Ching Y. Suen, Volkmar Frinken, Kaspar Riesen, Horst Bunke. Gyors illesztési algoritmus grafikon alapú kézírás-felismeréshez // Grafikonalapú ábrázolások a mintafelismerésben. - 2013. - T. 7877. - S. 194-203. — ( Számítástechnikai előadásjegyzetek ). — ISBN 978-3-642-38220-8 . - doi : 10.1007/978-3-642-38221-5_21 .
Michel Neuhaus, Horst Bunke. Grafikonegyeztetésen alapuló megközelítés az ujjlenyomat-osztályozáshoz irányvarianciával // Audio- és videoalapú biometrikus személyhitelesítés. - 2005. - T. 3546. - S. 191-200. — ( Számítástechnikai előadásjegyzetek ). — ISBN 978-3-540-27887-0 . - doi : 10.1007/11527923_20 .
Kristian Birchall, Valerie J. Gillet, Gavin Harper, Stephen D. Pickett. Képzési hasonlósági intézkedések specifikus tevékenységekhez: Alkalmazás csökkentett grafikonokra // Journal of Chemical Information and Modeling . - 2006. - január ( 46. évf. , 2. szám ). – S. 557–586 . - doi : 10.1021/ci050465e . — PMID 16562986 .
Michel Neuhaus, Horst Bunke. A grafikonszerkesztési távolság és a kernelgépek közötti szakadék áthidalása. - World Scientific, 2007. - V. 68. - (Gépi észlelés és mesterséges intelligencia). — ISBN 978-9812708175 .
Kaspar Riesen. Strukturális mintázat felismerés grafikonszerkesztési távolsággal: Közelítő algoritmusok és alkalmazások. - Springer, 2016. - (A számítógépes látás és a mintafelismerés fejlődése). — ISBN 978-3319272511 .
Garey MR, Johnson DS Számítógépek és kezelhetetlenség: Útmutató az NP-teljesség elméletéhez . - W.H. Freeman and Company, 1979. - ISBN 978-0-7167-1045-5 .
Chih Long Lin. A gráftranszformációs feladat közelítésének keménysége // Algoritmusok és számítások / Ding-Zhu Du, Xiang-Sun Zhang. - Springer Berlin Heidelberg, 1994. - T. 834. - (Számítástechnikai előadásjegyzetek). — ISBN 9783540583257 . - doi : 10.1007/3-540-58325-4_168 .