Zmienność informacji

W teorii prawdopodobieństwa i teorii informacji zmienność informacji lub odległość wspólnych informacji jest miarą odległości między dwoma skupieniami ( podziałami elementów ). Jest to ściśle związane z wzajemną informacją ; w rzeczywistości jest to proste wyrażenie liniowe obejmujące wzajemne informacje. Jednak w przeciwieństwie do informacji wzajemnych, zmienność informacji jest prawdziwą metryką , ponieważ jest zgodna z nierównością trójkąta .

Diagram informacyjny ilustrujący zależność między entropiami informacyjnymi , informacją wzajemną i zmiennością informacji.

Definicja

$=\{X_{1},X_{2},\ldots,X_{k}\}}$$,$ że mamy dwie zbioru na rozłączne $podzbiory$ , a mianowicie X $k$$X$ } i ${\ Displaystyle Y = \ {Y_ {1}, Y_ {2}, \ ldots, Y_ {l} \}}$ .

Pozwalać:

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

${\ displaystyle p_ {i} = | X_ {i} |/ n}$ i ${\ Displaystyle q_ {j} = | Y_ {j} |/n}$

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

Wtedy zmienność informacji między dwiema partycjami wynosi:

${\ Displaystyle \ operatorname {VI} (X; Y)=-\suma _{i,j}r_{ij}\left[\log(r_{ij}/p_{i})+\log(r_{ij}/q_{j})\right]}$ .

Jest to równoważne ze wspólną odległością informacyjną między zmiennymi losowymi i i j w odniesieniu do jednolitej miary prawdopodobieństwa na $zdefiniowanej$ przez ${\ Displaystyle \ mu (B): = | B |/ n}$ dla ${\ Displaystyle B \ subseteq A}$ .

Wyraźna treść informacyjna

Możemy przepisać tę definicję w terminach, które wyraźnie podkreślają zawartość informacyjną tej metryki.

Zbiór wszystkich partycji zbioru tworzy zwartą kratę , $displaystyle \ vee}$ której porządek częściowy indukuje dwie operacje, spotkanie i łączenie $\$ , gdzie maksimum ${\ displaystyle {\ displaystyle} overline {\ operatorname {1}}}}$ to partycja z tylko jednym blokiem, tj. wszystkimi elementami zgrupowanymi razem, a minimum to partycja składająca się z ${\ displaystyle {\ overline {\ operatorname {0}}}}$ wszystkie elementy jako singletony. Spotkanie dwóch partycji ${\ displaystyle X}$ i ${\ displaystyle Y}$ jest łatwe do zrozumienia, ponieważ podział utworzony przez wszystkie przecięcia par jednego bloku , ${\ displaystyle X_ {i}}$ , ${\ displaystyle X}$ i jeden, ${\ displaystyle Y_ {i}}$ , z ${\ Displaystyle Y}$ . Wynika z tego, że ${\ Displaystyle X \ klin Y \ subseteq X}$ i ${\ Displaystyle X \ klin Y \ subseteq Y}$ .

Zdefiniujmy entropię partycji jako ${\ displaystyle X}$

${\ Displaystyle H \ lewo (X \ prawo) \ = \, - \ suma _ {i} \, p_ {i} \ log p_ {i}}$ ,

gdzie ${\ displaystyle p_ {i} = | X_ {i} |/n}$ . Oczywiście ${\ Displaystyle H ({\ overline {\ operatorname {1}}}) = 0}$ i ${\ Displaystyle H ({\ overline {\ operatorname {0} }})=\log \,n}$ . Entropia partycji jest monotonną funkcją na siatce partycji w tym sensie, że ${\ Displaystyle X \ subseteq Y \ Strzałka w prawo H (X) \ geq H (Y)}$ .

Następnie odległość VI między i Y $\ displaystyle Y}$ jest określona przez ${\ displaystyle X}$

${\ Displaystyle \ operatorname {VI} (X, Y) \ = \, 2H (X \ klin Y) \,-\,H(X)\,-\,H(Y)}$ .

Różnica ${\ Displaystyle d (X, Y) \ równoważnik | H \ lewo (X \ prawej) -H \ lewo (Y \ prawej) |} jest$ pseudo-metryką jako ${\ Displaystyle d (X , Y) = 0}$ niekoniecznie oznacza, że ${\ displaystyle X = Y}$ . definicji ${\ Displaystyle {\ overline {\ operatorname {1}}}}$ , to jest ${\ Displaystyle \ operatorname {VI} (X, \ operatorname {1}) \ = \,H\lewo(X\prawo)}$ .

Jeśli na diagramie Hassego narysujemy krawędź z każdej partycji do maksimum $i$ przypiszemy jej wagę równą odległości VI między daną ${ \ displaystyle {\ overline {\ mathrm {1}}}}$ , możemy zinterpretować odległość VI jako zasadniczo średnią różnic wag krawędzi do maksimum

${\ Displaystyle \ operatorname {VI} (X, Y) \ = \, | \ operatorname {VI} (X, {\ overline {\ operatorname {\ operatorname { 1} }})\,-\,\mathrm {VI} (X\klin Y,{\overline {\mathrm {1} }})|\,+\,|\mathrm {VI} (Y,{\ overline {\mathrm {1} }})\,-\,\mathrm {VI} (X\klin Y,{\overline {\mathrm {1} }})|\,=\,d(X,X\ klin Y)\,+\,d(Y,X\klin Y)}$ .

Dla zdefiniowanego powyżej, oznacza to, $\ Displaystyle H (X)$ łączna informacja o dwóch partycjach pokrywa się z entropią spotkania H. ( X

${\ Displaystyle H (X, Y) \, = \, H (X \ klin Y)}$

i mamy również, że pokrywa się ${\ Displaystyle d (X, X \ klin Y) \, = \, H (X \ klin Y | X)}$ z warunkową entropią spotkania (przecięcia) względem ${\$$Displaystyle X \ klin Y$ .

Tożsamości

Różnorodność informacji jest zadowalająca

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

gdzie $}$$}$$}$$)$ ( jest entropią i jest informacją \ $X$ i w $odniesieniu$ do jednolitej $.$ prawdopodobieństwa Można to przepisać jako

${\ Displaystyle \ operatorname {VI} (X; Y) = H (X, Y) -I (X, Y)}$ ,

gdzie ${\ Displaystyle H (X, Y)}$ jest wspólną entropią X ${\ Displaystyle X}$ i $\ Displaystyle Y}$ lub

${\ Displaystyle \ operatorname {VI} (X; Y) = H (X | Y) + H (Y | X)}$ ,

gdzie ${\ Displaystyle$$H (Y$ odpowiednimi entropiami warunkowymi .

Zmienność informacji może być również ograniczona, albo pod względem liczby elementów:

${\ Displaystyle \ operatorname {VI} (X; Y) \ równoważnik \ log (n)}$ ,

Lub w odniesieniu do maksymalnej liczby klastrów: ${\ Displaystyle K ^ {*}}$ :

${\ Displaystyle \ operatorname {VI} (X; Y) \ równoważnik 2 \ log (K ^ {*})}$

Dalsza lektura

• Arabie, P.; Boorman SA (1973). „Wielowymiarowe skalowanie miar odległości między przegrodami”. Journal of Psychologii Matematycznej . 10 (2): 148–203. doi : 10.1016/0022-2496(73)90012-6 .
•   Meila, Marina (2003). „Porównywanie skupień według zmienności informacji”. Teoria uczenia się i maszyny jądrowe . Notatki z wykładów z informatyki. 2777 : 173–187. doi : 10.1007/978-3-540-45167-9_14 . ISBN 978-3-540-40720-1 .
• Meila, M. (2007). „Porównywanie skupień - odległość oparta na informacjach” . Dziennik analizy wielowymiarowej . 98 (5): 873–895. doi : 10.1016/j.jmva.2006.11.013 .
• Kingsford, Carl (2009). „Notatki z teorii informacji” (PDF) . Źródło 22 września 2009 .
• Kraskow, Aleksander; Haralda Stögbauera; Ralph G. Andrzejak; Petera Grassbergera (2003). „Hierarchiczne klastrowanie na podstawie wzajemnych informacji”. arXiv : q-bio/0311039 .

Linki zewnętrzne

• Partanalyzer zawiera implementację VI w C++ oraz inne metryki i indeksy do analizy partycji i grupowania
• Implementacja C++ z plikami MATLAB mex