Normalizovaná kompresní vzdálenost

Normalizovaná kompresní vzdálenost (z angl. "normalized compression distance") je způsob, jakým se dá měřit podobnost dvou objektů, ať už se jedná o dva dokumenty, dva e-maily, dvě hudební díla, dva jazyky, dva programy, dva obrázky, dva genomy, atd. Použitelná definice podobnosti může být jak těžké je převést jeden objekt na druhý. Normalizovaná kompresní vzdálenost může být použita například pro dobývání znalostí, pro shlukovou analýzu.

Výpočet informační vzdálenosti[editovat | editovat zdroj]

Pro výpočet musíme na porovnávané objekty nahlížet jako na sled jedniček a nul - jedná se o binární řetězec. Každý počítačový soubor je takto vnitřně reprezentován.

Označme si první porovnávaný objekt, ve formě binárního řetězce, jako $x$ a druhý jako $y$ . Dále budeme uvažovat počítačový program, který dokáže spočítat $x$ z $y$ a navzájem. Tento program budeme brát v teoretickém zápisu turingova stroje. Délka takovéhoto (nejkratšího) programu pak budiž informační vzdáleností.

|p|=\max\{K(x\mid y),K(y\mid x)\}

kde $K(x\mid y)$ značí kolmogorovskou složitost programu pro výpočet $x$ , když $y$ dostane program na vstupu a obdobně $K(y\mid x)$ značí kolmogorovskou složitost programu pro výpočet $y$ se vstupem $x$ .

Pro výpočet normalizované informační vzdálenosti (NID) pak použijeme vzoreček:

$NID(x,y)={\frac {\max\{K{(x\mid y)},K{(y\mid x)}\}}{\max\{K(x),K(y)\}}},$

Nicméně tento výpočet je bohužel v praxi nespočitatelný ^[1].

Výpočet normalizované kompresní vzdálenosti[editovat | editovat zdroj]

Jelikož normalizovaná informační vzdálenost je nespočitatelná, Vitanyi a Cilibrasi přišli s vylepšenou metrikou nazvanou normalizovaná kompresní vzdálenost. Jedná se o nahrazení $K$ kompresorem - $Z(x)$ značí kompresní binární délku komprimovaného souboru (např. za použití "gzip"). Výsledný vzoreček tedy vypadá takto:

NCD_{Z}(x,y)={\frac {Z(xy)-\min\{Z(x),Z(y)\}}{\max\{Z(x),Z(y)\}}}.

Aplikace[editovat | editovat zdroj]

Normalizovaná kompresní vzdálenost může být použita v celé řadě odvětví. Jedním z příkladů je rozpoznávání podobností v obrázcích na poli počítačové grafiky ^[2], či klasifikovaní počítačových virů a malware ^[3]. Dalším příkladem je Normalizovaná Google vzdálenost - jedná se o přepsání vzorce pro potřeby porovnávání vyhledávaných termů.

Reference[editovat | editovat zdroj]

↑ Nonapproximability of the normalized information distance. Journal of Computer and System Sciences. 2011-07-01, roč. 77, čís. 4, s. 738–742. Dostupné online [cit. 2018-02-09]. ISSN 0022-0000. DOI 10.1016/j.jcss.2010.06.018. (anglicky)
↑ VÁZQUEZ, Pere-Pau; MARCO, Jordi. Using Normalized Compression Distance for image similarity measurement: an experimental study. The Visual Computer. 2012-11-01, roč. 28, čís. 11, s. 1063–1084. Dostupné online [cit. 2018-02-09]. ISSN 0178-2789. DOI 10.1007/s00371-011-0651-2. (anglicky)
↑ BORBELY, Rebecca Schuller. On Normalized Compression Distance and Large Malware. arXiv:1509.00689 [cs]. 2015-09-02. ArXiv: 1509.00689. Dostupné online [cit. 2018-02-09].

[1] Nonapproximability of the normalized information distance. Journal of Computer and System Sciences. 2011-07-01, roč. 77, čís. 4, s. 738–742. Dostupné online [cit. 2018-02-09]. ISSN 0022-0000. DOI 10.1016/j.jcss.2010.06.018. (anglicky)

[2] VÁZQUEZ, Pere-Pau; MARCO, Jordi. Using Normalized Compression Distance for image similarity measurement: an experimental study. The Visual Computer. 2012-11-01, roč. 28, čís. 11, s. 1063–1084. Dostupné online [cit. 2018-02-09]. ISSN 0178-2789. DOI 10.1007/s00371-011-0651-2. (anglicky)

[3] BORBELY, Rebecca Schuller. On Normalized Compression Distance and Large Malware. arXiv:1509.00689 [cs]. 2015-09-02. ArXiv: 1509.00689. Dostupné online [cit. 2018-02-09].

[1]

[2]

[3]