Justerad ömsesidig information

Inom sannolikhetsteori och informationsteori , justerad ömsesidig information , kan en variation av ömsesidig information användas för att jämföra klustringar . Det korrigerar effekten av överensstämmelse enbart på grund av slumpen mellan klustringar, på samma sätt som det justerade randindexet korrigerar Randindexet . Det är nära relaterat till variation av information : när en liknande justering görs av VI-indexet blir det ekvivalent med AMI. Det justerade måttet är dock inte längre metriskt.

Ömsesidig information om två partitioner

Givet en uppsättning S av N element ${\displaystyle S=\{s_{1},s_{2},\ldots s_{N}\}},$ överväg två partitioner av S , nämligen $U=\{U_{1},U_{2},\ldots ,U_{R}\}$ med R -kluster och $V=\{V_{1},V_{2},\ldots,V_{C}\}$ med C- kluster. Det antas här att partitionerna är så kallade hårda kluster; partitionerna är parvis osammanhängande:

$U_{i}\cap U_{j}=\varnothing =V_{i}\cap V_{j}$

för alla $i\neq j$ , och fyll i:

$\cup _{i=1}^{R}U_{i}=\cup _{j=1}^{C}V_ {j}=S$

Den ömsesidiga informationen om klusteröverlappning mellan U och V kan sammanfattas i form av en R x C -kontingenstabell $M=[n_{ij} ]_{j=1\ldots C}^{i=1\ldots R}$ , där $n_{ij}$ anger antalet objekt som är gemensamma för kluster $U_{ i}$ och $V_{j}$ . Det är,

$n_{ij}=\left|U_{i}\cap V_{j}\right|$

Antag att ett objekt plockas slumpmässigt från S ; sannolikheten att objektet hamnar i kluster $U_{i}$ är:

$P_{U}(i)={\frac {|U_{i}|}{N}}$

Entropin som är associerad med partitioneringen U är:

$H(U)=-\summa _{i=1}^{R}P_{U}(i )\log P_{U}(i)$

H(U) är icke-negativ och tar endast värdet 0 när det inte finns någon osäkerhet som bestämmer ett objekts klustermedlemskap, dvs när det bara finns ett kluster. På liknande sätt kan entropin för klustringen V beräknas som:

$H(V)=-\summa _{j=1}^{C}P_{V}(j )\log P_{V}(j)$

där $P_{V}(j)={|V_{j}|}/{N}$ . Den ömsesidiga informationen (MI) mellan två partitioner:

$MI (U,V)=\summa _{i=1}^{R}\summa _{j=1}^{C}P_{UV}(i,j)\log {\frac {P_{UV}( i,j)}{P_{U}(i)P_{V}(j)}}$

där $P_{UV}(i,j)$ anger sannolikheten att en punkt tillhör både klustret $U_{i}$ i U och kluster ${ \displaystyle V_{j}}$ i V :

$P_{UV}(i,j)={\frac {|U_{i}\cap V_{j}|}{N}}$

MI är en icke-negativ storhet som är övre gränsad av entropierna H ( U ) och H ( V ). Den kvantifierar informationen som delas av de två klustringarna och kan därför användas som ett klustringslikhetsmått .

Justering för slumpen

Liksom Rand-indexet antar inte baslinjevärdet för ömsesidig information mellan två slumpmässiga kluster ett konstant värde och tenderar att vara större när de två partitionerna har ett större antal kluster (med ett fast antal uppsättningselement N ) . Genom att anta en hypergeometrisk modell för slumpmässighet kan det visas att den förväntade ömsesidiga informationen mellan två slumpmässiga klustringar är:

${\begin{aligned}E\{MI(U,V)\}=&\summa _{i=1}^{R}\summa _{j=1}^{C}\summa _{ n_{ij}=(a_{i}+b_{j}-N)^{+}}^{\min(a_{i},b_{j})}{\frac {n_{ij}}{N }}\log \left({\frac {N\cdot n_{ij}}{a_{i}b_{j}}}\right)\gånger \\&{\frac {a_{i}!b_{j }!(N-a_{i})!(N-b_{j})!}{N!n_{ij}!(a_{i}-n_{ij})!(b_{j}-n_{ij })!(N-a_{i}-b_{j}+n_{ij})!}}\\\end{aligned}}$

där $(a_{i}+b_{j}-N)^{+}$ anger $\max( 0,a_{i}+b_{j}-N)$ . Variablerna $a_{i}$ och $b_{j}$ är partiella summor av beredskapstabellen ; det är,

$a_{i}=\summa _{j=1}^{C}n_{ij}$

och

$b_{j}=\summa _{i=1}^{R}n_{ij}$

Det justerade måttet för den ömsesidiga informationen kan sedan definieras som:

$AMI(U,V)={\frac {MI(U,V)-E\{MI(U,V)\}}{\max {\{H(U),H(V)\} }-E\{MI(U,V)\}}}$ .

AMI tar värdet 1 när de två partitionerna är identiska och 0 när MI mellan två partitioner är lika med det förväntade värdet på grund av enbart slumpen.

externa länkar

• Matlab-kod för att beräkna den justerade ömsesidiga informationen
• R-kod för snabb och parallell beräkning av justerad ömsesidig information
• Python-kod för att beräkna den justerade ömsesidiga informationen