Variation av information

I sannolikhetsteori och informationsteori är variationen av information eller delad informationsavstånd ett mått på avståndet mellan två klustringar ( partitioner av element) . Det är nära besläktat med ömsesidig information ; Det är faktiskt ett enkelt linjärt uttryck som involverar den ömsesidiga informationen. Till skillnad från den ömsesidiga informationen är dock informationens variation ett sant mått , eftersom det lyder triangelojämlikheten .

Informationsdiagram som illustrerar sambandet mellan informationsentropier , ömsesidig information och variation av information.

Definition

Antag att vi har två partitioner $X$ och $Y$ av en uppsättning $A$ i disjunkta delmängder , nämligen $X =\{X_{1},X_{2},\ldots ,X_{k}\}$ och $Y=\{Y_{1}, Y_{2},\ldots ,Y_{l}\}$ .

Låta:

$n=\summa _{i}|X_{i}|=\summa _{j}|Y_{j}|=|A|$

$p_{i}=|X_{i}|/n$ och $q_{j}=|Y_{j}|/n$

$r_{ij}=|X_{i}\cap Y_{j}|/n$

Då är variationen av information mellan de två partitionerna:

${\displaystyle \mathrm {VI} (X$ .

Detta är ekvivalent med det delade informationsavståndet mellan de slumpmässiga variablerna i och j med avseende på det enhetliga sannolikhetsmåttet på $A$ definierad av $\mu (B):=|B|/n$ för $B\subseteq A$ .

Explicit informationsinnehåll

Vi kan skriva om denna definition i termer som uttryckligen belyser informationsinnehållet i detta mått.

Mängden av alla partitioner i en uppsättning bildar ett kompakt gitter där den partiella ordningen inducerar två operationer, meet $\wedge$ och join $\vee$ , där maximalt ${\ overline {\mathrm {1} }}$ är partitionen med endast ett block, dvs alla element grupperade tillsammans, och minimum är ${\overline {\mathrm {0} }}$ , partitionen består av alla element som singlar. Mötet mellan två partitioner $X$ och $Y$ är lätt att förstå eftersom den partition som bildas av alla parskärningar av ett block av, ${\displaystyle X_{i}} ,$ av ${\ displaystyle X}$ och en, $Y_{i}$ , av $Y$ . Det följer sedan att $X\wedge Y\subseteq X$ och $X\wedge Y\subseteq Y$ .

Låt oss definiera entropin för en partition $X$ som

$H\left(X\right)\,=\,-\summa _{i}\,p_{i}\log p_{i}$ ,

där $p_{i}=|X_{i}|/n$ . Tydligen är $H({\overline {\mathrm {1} }})=0$ och $H({\overline {\mathrm {0} }})=\log \,n$ . Entropin för en partition är en monoton funktion på partitionernas gitter i den meningen att $X\subseteq Y\Rightarrow H(X)\geq H(Y)$ .

ges VI-avståndet mellan $X$ och ${\displaystyle Y} av$

$\displaystyle \mathrm {VI} (X,Y)\,=\,2H(X\wedge Y) \,-\,H(X)\,-\,H(Y)}$ .

Skillnaden ${\displaystyle d(X,Y)\equiv |H\left(X\right)-H\left(Y\right)|} är$ en pseudo-metrisk som $d(X ,Y)=0$ betyder inte nödvändigtvis att $X=Y$ . Från definitionen av ${\overline {\mathrm {1} }}$ är det $\mathrm {VI} (X,\mathrm { 1} )\,=\,H\vänster(X\höger)$ .

Om vi ​​i Hasse-diagrammet ritar en kant från varje partition till maximalt ${\overline {\mathrm {1} }}$ och tilldelar den en vikt lika med VI-avståndet mellan den givna partitionen och ${ \displaystyle {\overline {\mathrm {1} }}}$ , kan vi tolka VI-avståndet som i princip ett genomsnitt av skillnader mellan kantvikter till det maximala

$\mathrm {VI} (X,Y)\,=\,|\mathrm {VI} (X,{\överlinje {\ mathrm {1} }})\,-\,\mathrm {VI} (X\kil Y,{\överlinje {\mathrm {1} }})|\,+\,|\mathrm {VI} (Y, {\överlinje {\mathrm {1} }})\,-\,\mathrm {VI} (X\kil Y,{\överlinje {\mathrm {1} }})|\,=\,d(X, X\kil Y)\,+\,d(Y,X\kil Y)$ .

För $H(X)$ enligt definitionen ovan gäller att den gemensamma informationen för två partitioner sammanfaller med entropin för mötet

$H(X,Y)\,=\,H(X\wedge Y)$

och vi har också att $d(X,X\wedge Y)\,=\,H(X\wedge Y|X)$ sammanfaller med den villkorliga entropin för mötet (skärningspunkten) $X\wedge Y$ relativt $X$ .

Identiteter

Variationen av information tillfredsställer

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

där $H(X)$ är entropin för $X$ , och $I(X,Y)$ är ömsesidig information mellan $X$ och $Y$ med avseende på det enhetliga sannolikhetsmåttet på $A$ . Detta kan skrivas om som

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

där $H(X,Y)$ är den gemensamma entropin för $X$ och $Y$ , eller

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

där $H(X|Y)$ och $H(Y|X)$ är de respektive villkorliga entropierna .

Variationen av information kan också begränsas, antingen i termer av antalet element:

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

Eller med avseende på ett maximalt antal kluster, $K^{*}$ :

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

Vidare läsning

• Arabie, P.; Boorman, SA (1973). "Multidimensionell skalning av mått på avstånd mellan partitioner". Journal of Mathematical Psychology . 10 (2): 148–203. doi : 10.1016/0022-2496(73)90012-6 .
•   Meila, Marina (2003). "Jämföra kluster genom variationen av information". Inlärningsteori och kärnmaskiner . Föreläsningsanteckningar i datavetenskap. 2777 : 173–187. doi : 10.1007/978-3-540-45167-9_14 . ISBN 978-3-540-40720-1 .
• Meila, M. (2007). "Jämföra klustringar - ett informationsbaserat avstånd" . Journal of Multivariate Analysis . 98 (5): 873–895. doi : 10.1016/j.jmva.2006.11.013 .
• Kingsford, Carl (2009). "Anteckningar om informationsteori" (PDF) . Hämtad 22 september 2009 .
• Kraskov, Alexander; Harald Stögbauer; Ralph G. Andrzejak; Peter Grassberger (2003). "Hierarkisk klustring baserad på ömsesidig information". arXiv : q-bio/0311039 .

externa länkar

• Partanalyzer inkluderar en C++-implementering av VI och andra mätvärden och index för att analysera partitioner och klustringar
• C++ implementering med MATLAB mex-filer