Variace informací - Variation of information

v teorie pravděpodobnosti a teorie informace, variace informací nebo sdílená informační vzdálenost je míra vzdálenosti mezi dvěma shluky (oddíly prvků ). Je to úzce spjato s vzájemné informace; ve skutečnosti je to jednoduchý lineární výraz zahrnující vzájemnou informaci. Na rozdíl od vzájemné informace je však variace informací pravdivá metrický, v tom, že se řídí nerovnost trojúhelníku.^[1][2][3]

Informační diagram znázorňující vztah mezi informační entropie, vzájemné informace a variace informací.

Definice

Předpokládejme, že máme dva oddíly ${ displaystyle X}$ a ${ displaystyle Y}$ a soubor ${ displaystyle A}$ disjunktní podmnožiny, jmenovitě ${ displaystyle X = {X_ {1}, X_ {2}, .. ,, X_ {k} }}$ a ${ displaystyle Y = {Y_ {1}, Y_ {2}, .. ,, Y_ {l} }}$. Nechat ${ displaystyle n = součet _ {i} | X_ {i} | = součet _ {j} | Y_ {j} | = | A |}$, ${ displaystyle p_ {i} = | X_ {i} | / n}$ , ${ displaystyle q_ {j} = | Y_ {j} | / n}$, ${ displaystyle r_ {ij} = | X_ {i} čepice Y_ {j} | / n}$. Variace informací mezi těmito dvěma oddíly je pak:

${ displaystyle mathrm {VI} (X; Y) = - součet _ {i, j} r_ {ij} vlevo [ log (r_ {ij} / p_ {i}) + log (r_ {ij } / q_ {j}) vpravo]}$.

To je ekvivalentní s sdílená informační vzdálenost mezi náhodnými proměnnými i a j s ohledem na jednotné opatření pravděpodobnosti dne ${ displaystyle A}$ definován ${ displaystyle mu (B): = | B | / n}$ pro ${ displaystyle B subseteq A}$.

Výslovný informační obsah

Tuto definici můžeme přepsat výrazy, které výslovně zdůrazňují informační obsah této metriky.

Sada všech oddílů sady tvoří kompaktní soubor Mříž kde částečný řád vyvolá dvě operace, setkání ${ displaystyle klín}$ a připojit se ${ displaystyle vee}$, kde je maximum ${ displaystyle { overline { mathrm {1}}}}$ je oddíl pouze s jedním blokem, tj. se všemi prvky seskupenými dohromady, a minimum je ${ displaystyle { overline { mathrm {0}}}}$, oddíl skládající se ze všech prvků jako jednotlivé. Setkání dvou oddílů ${ displaystyle X}$ a ${ displaystyle Y}$ je snadno pochopitelný jako oddíl tvořený všemi párovými průsečíky jednoho bloku, ${ displaystyle X_ {i}}$, z ${ displaystyle X}$ a jeden, ${ displaystyle Y_ {i}}$, z ${ displaystyle Y}$. Z toho pak vyplývá ${ displaystyle X klín Y subseteq X}$ a ${ displaystyle X klín Y subseteq Y}$.

Pojďme definovat entropii oddílu ${ displaystyle X}$ tak jako

kde ${ displaystyle p_ {i} = | X_ {i} | / n}$. Jasně, ${ displaystyle H ({ overline { mathrm {1}}}) = 0}$ a ${ displaystyle H ({ overline { mathrm {0}}}) = log , n}$. Entropie oddílu je monotónní funkce na mřížce oddílů v tom smyslu ${ displaystyle X subseteq Y Rightarrow H (X) geq H (Y)}$.

Pak vzdálenost VI mezi ${ displaystyle X}$ a ${ displaystyle Y}$ je dána

Rozdíl ${ displaystyle d (X, Y) ekviv | H vlevo (X vpravo) -H vlevo (Y vpravo) |}$ je pseudometrická jako ${ displaystyle d (X, Y) = 0}$ to nutně neznamená ${ displaystyle X = Y}$. Z definice ${ displaystyle { overline { mathrm {1}}}}$, to je ${ displaystyle mathrm {VI} (X, mathrm {1}) , = , H vlevo (X vpravo)}$.

Pokud v Hasseův diagram z každého oddílu nakreslíme maximum ${ displaystyle { overline { mathrm {1}}}}$ a přiřaďte jí váhu rovnající se vzdálenosti VI mezi danou přepážkou a ${ displaystyle { overline { mathrm {1}}}}$, můžeme VI vzdálenost interpretovat jako v zásadě průměr rozdílů okrajových hmotností na maximum

Pro ${ displaystyle H (X)}$ jak je definováno výše, platí, že společné informace o dvou oddílech se shodují s entropií setkání

a také to máme ${ displaystyle d (X, X klín Y) , = , H (X klín Y | X)}$ se shoduje s podmíněnou entropií setkání (průsečík) ${ displaystyle X klín Y}$ ve vztahu k ${ displaystyle X}$.

Totožnosti

Variace informací uspokojuje

${ displaystyle mathrm {VI} (X; Y) = H (X) + H (Y) -2I (X, Y)}$,

kde ${ displaystyle H (X)}$ je entropie z ${ displaystyle X}$, a ${ displaystyle I (X, Y)}$ je vzájemné informace mezi ${ displaystyle X}$ a ${ displaystyle Y}$ s ohledem na jednotné opatření pravděpodobnosti dne ${ displaystyle A}$. To lze přepsat jako

${ displaystyle mathrm {VI} (X; Y) = H (X, Y) -I (X, Y)}$,

kde ${ displaystyle H (X, Y)}$ je společná entropie z ${ displaystyle X}$ a ${ displaystyle Y}$nebo

${ displaystyle mathrm {VI} (X; Y) = H (X | Y) + H (Y | X)}$,

kde ${ displaystyle H (X | Y)}$ a ${ displaystyle H (Y | X)}$ jsou příslušné podmíněné entropie.

Variaci informací lze také omezit, ať už jde o počet prvků:

${ displaystyle mathrm {VI} (X; Y) leq log (n)}$,

Nebo s ohledem na maximální počet klastrů, ${ displaystyle K ^ {*}}$:

${ displaystyle mathrm {VI} (X; Y) leq 2 log (K ^ {*})}$

Reference

Další čtení

• Arabie, P .; Boorman, S.A. (1973). Msgstr "Vícerozměrné měřítko míry vzdálenosti mezi oddíly". Journal of Mathematical Psychology. 10 (2): 148–203. doi:10.1016/0022-2496(73)90012-6.
• Meila, Marina (2003). "Porovnání seskupení podle variace informací". Teorie učení a jádrové stroje. Přednášky z informatiky. 2777: 173–187. doi:10.1007/978-3-540-45167-9_14. ISBN  978-3-540-40720-1.
• Meila, M. (2007). "Porovnání shluků - vzdálenost založená na informacích". Journal of Multivariate Analysis. 98 (5): 873–895. doi:10.1016 / j.jmva.2006.11.013.
• Kingsford, Carl (2009). „Poznámky k teorii informací“ (PDF). Citováno 22. září 2009.
• Kraskov, Alexander; Harald Stögbauer; Ralph G. Andrzejak; Peter Grassberger (2003). "Hierarchické shlukování založené na vzájemných informacích". arXiv:q-bio / 0311039.

externí odkazy

• Partanalyzer zahrnuje implementaci VI a dalších metrik a indexů pro analýzu oddílů a klastrů v C ++
• Implementace C ++ se soubory MATLAB mex