정보의 변동

확률이론과 정보이론에서 정보의 변동이나 공유정보 거리는 두 군집(요소의 일부분) 사이의 거리를 측정하는 척도다.그것은 상호 정보와 밀접한 관련이 있다; 실제로 상호 정보를 포함하는 단순한 선형 표현이다.그러나 상호 정보와 달리 정보의 변동은 삼각형 불평등에 순응한다는 점에서 진정한 척도다.^[1][2][3]

정의

Suppose we have two partitions ${\displaystyle X}$ and ${\displaystyle Y}$ of a set ${\displaystyle A}$ into disjoint subsets, namely ${\displaystyle X=\{X_{1},X_{2},\ldots ,X_{k}\}}$ and ${\displaystyle Y=\{Y_{1},Y_{2},\ldots ,Y_{l}\$$}}$.

허용:

${\displaystyle n=\sum _{i}X_{i} =\sum _{j}Y_{j} = A }$

${\displaystyle p_{}}$ ${\displaystyle i_{}}$= ${\displaystyle X}$ ${\displaystyle i_{}{}_{}}$/ n ${\displaystyle p_{i}= X_{i} /n}$ 및$$ ${\displaystyle q_{}}$= ${\displaystyle Y_{}}$ ${\displaystyle j{}_{}{}_{}}$/ ${\displaystyle n}$ ${\displaystyle q_{j}= Y_{j} /n}$

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

그러면 두 칸막이 사이의 정보의 변동은 다음과 같다.

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

$이$는 B ${\displaystyle \subseteq }$ ${\displaystyle A}$ ${\displaystyle B\subseteq A}$에 대해 $\mu {\displaystyle (B}$ ${\displaystyle )}$로 정의된$$ A$$${\$$displaystyle$ $A}$에$대한$ 균일한$확률$측정에 $관한$랜덤 $변수$i와 j $사이$의 공유 정보 거리에 해당한다$.$

명시적 정보 내용

우리는 이 측정지표의 정보 내용을 명시적으로 강조하는 용어로 이 정의를 다시 쓸 수 있다.

집합의 모든 파티션 집합은 콤팩트한 래티스(Lattice)를 형성하며, 여기서 부분 순서는${\displaystyle }${ ${\displaystyle \wedge}$과 조인$${\$displaystyle \ve}$의 두 가지 작업을 유도하며${\displaystyle \stackrel{}{}}$ $최대{\displaystyle \stackrel{}{\mathrm{}}}$ 1 블록${\displaystyle }$${\$은 하나의 블록만 그룹화된 파티션이다$$.nd 최소값은 ${\$이며$,$ 모든 원소로 구성된 파티션은 단골격이다.두 칸막이 $X{\displaystyle }$ ${\displaystyle$ X$}$과 $Y{\displaystyle }$ ${\displaystyle Y}$의 한 ${\displaystyle {블록}_{}}$인 $X{\displaystyle }$ i$${\$displaystyle X_$$\{$$i$$}$와 ${\displaystyle Y_{}}$${\displaystyle$ Y$}$의 한 블록의 모든 쌍 교차점에 의해 형성된 칸막이가 그 뒤를 따르기 때문에 이해하기 쉽다$$$.$${\displaystyle X}$ ${\displaystyle \wedge }$ ${\displaystyle Y}$ ${\displaystyle \subseteq }$ X ${\displaystyle$ ${\displaystyle X}$ {\displaystyle $X\wedge$ Y$\subseteq X}$ 및$$ $X{\displaystyle }$ ${\displaystyle \wedge }$ ${\displaystyle Y}$ ∧ Y ${\displaystyle \subseteq }$ ${\displaystyle Y}$ ${\displaystyle X\wedge$ Y$\subseteq Y$

파티션 $X{\displaystyle }$ ${\displaystyle X}$의 엔트로피를 다음과$$ 같이 정의하십시오.

${\displaystyle H}$( ${\displaystyle X}$)${\displaystyle }$= -${\displaystyle \underset{}{}}$ i ${\displaystyle i\underset{}{}{}_{}}$ ${\displaystyle \mathrm{로그}}$ log${\displaystyle }$p ${\displaystyle i_{}}$ ${\$ ,

where ${\displaystyle p_{i}= X_{i} /n}$. Clearly, ${\displaystyle H({\overline {\mathrm {1} }})=0}$ and ${\displaystyle H({\overline {\mathrm {0} }})=\log \,n}$. The entropy of a partition is a monotonous function on the lattice of partitions in the sense$X{\displaystyle }$ ${\displaystyle \subseteq }$ ${\displaystyle Y}$ ${\displaystyle \Rightarrow }$ ${\displaystyle H}$( X${\displaystyle }$) ${\displaystyle \ge }$ H${\displaystyle }$( ${\displaystyle Y}$ )${\displaystyle }${ H ( ${\displaystyle Y}$ )$$\\$displaystyle$ X$\subseteq Y\Rightarrow H(X)\geq H(Y$ .

$그런{\displaystyle }$ 다음 X ${\displaystyle X}$과 $Y{\displaystyle }$ ${\displaystyle Y}$ 사이의 VI 거리는 다음과 같이 지정된다$$.

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

The difference ${\displaystyle d(X,Y)\equiv H\left(X\right)-H\left(Y\right) }$ is a pseudo-metric as ${\displaystyle d(X,Y)=0}$ doesn't necessarily imply that ${\displaystyle X=Y}$. From the definition of ${\displaystyle {\overline {\mathrm {1} }}}$, V ${\displaystyle \mathrm{I}}$( ${\displaystyle X\mathrm{}}$, ${\displaystyle 1}$)${\displaystyle }$= ${\displaystyle H}$( ${\displaystyle X}$) ${\$ {$1} )\,=\,H\left(X\right)}$ 입니다$.$

Hasse 다이어그램에서 모든 파티션에서 최대 $("\$까지 에지를 그리고 $지정$된 파티션과 1$({\$ 사이의 VI 거리와 동일한 가중치를 할당하면 기본적으로 VI 거리를 차이의 평균으로 해석할 수 있다$.$최대 에지 웨이트의

${\displaystyle \mathrm {VI} (X,Y)\,=\, \mathrm {VI} (X,{\overline {\mathrm {1} }})\,-\,\mathrm {VI} (X\wedge Y,{\overline {\mathrm {1} }}) \,+\, \mathrm$${VI}(Y,$ {\$overline {\mathrm {$1$} })\,-\,\,\\mathrm {VI}(X\wedge$ Y$,{\overline {\mathrm {$1$}$ })$\,=\,=\,+\,d(Y,X\wedge Y$

위에서 정의한$$ $H{\displaystyle }$( ${\displaystyle X}$) ${\displaystyle H(X)}$의 경우, 두 파티션의 공동 정보가 모임의 엔트로피와 일치함을 유지한다.

$[\displaystyle H(X,Y)\,=\,H(X\웨지 Y)}$

and we also have that ${\displaystyle d(X,X\wedge Y)\,=\,H(X\wedge Y X)}$ coincides with the conditional entropy of the meet (intersection) ${\displaystyle X\wedge Y}$ relative to ${\displaystyle X}$.

정체성

정보의 변동이 만족한다.

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

where ${\displaystyle H(X)}$ is the entropy of ${\displaystyle X}$, and ${\displaystyle I(X,Y)}$ is mutual information between ${\displaystyle X}$ and ${\displaystyle Y}$ with respect to the uniform probability measure on ${\displaystyle A}$. This can be rewritten as

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

여기서 $H{\displaystyle }$( ${\displaystyle X}$, Y${\displaystyle }$) ${\displaystyle H(X,Y)}$은(는) $X{\displaystyle }$ ${\displaystyle X}$$$및$$ $Y{\displaystyle }$ ${\displaystyle Y}$의 공동 엔트로피 또는$$

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

여기서 $H{\displaystyle (}$ ${\displaystyle X}$ Y${\displaystyle }$) ${\displaystyle H(X$ Y$)}$ 및$$ $H{\displaystyle (Y}$ ${\displaystyle X)}$ ${\displaystyle H(Y$ X$)}$은 각각의$$ 조건부 엔트로피이다.

정보의 변동은 또한 요소의 수에 따라 제한될 수 있다.

${\displaystyle \mathrm{V}}$ ${\displaystyle \mathrm{I}}$( ${\displaystyle X}$; ${\displaystyle Y}$) ${\displaystyle \le }$ ${\displaystyle \mathrm{로그}}$ ${\displaystyle }$(${\displaystyle n}$) ${\displaystyle \mathrmatrm$ {$VI}(X;$Y)\$leq \log$(n$)\},$

또는 최대 클러스터 수와 관련하여$$$K{\displaystyle {}^{}}$ $∗{\$ K$^{*}$ :

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

참조

추가 읽기

• Arabie, P.; Boorman, S. A. (1973). "Multidimensional scaling of measures of distance between partitions". Journal of Mathematical Psychology. 10 (2): 148–203. doi:10.1016/0022-2496(73)90012-6.
• Meila, Marina (2003). "Comparing Clusterings by the Variation of Information". Learning Theory and Kernel Machines. Lecture Notes in Computer Science. 2777: 173–187. doi:10.1007/978-3-540-45167-9_14. ISBN 978-3-540-40720-1.
• Meila, M. (2007). "Comparing clusterings—an information based distance". Journal of Multivariate Analysis. 98 (5): 873–895. doi:10.1016/j.jmva.2006.11.013.
• Kingsford, Carl (2009). "Information Theory Notes" (PDF). Retrieved 22 September 2009.
• Kraskov, Alexander; Harald Stögbauer; Ralph G. Andrzejak; Peter Grassberger (2003). "Hierarchical Clustering Based on Mutual Information". arXiv:q-bio/0311039.

외부 링크

• Partanalyzer에는 파티션 및 클러스터 분석을 위한 VI 및 기타 메트릭과 지수의 C++ 구현이 포함됨
• MATLAB mex 파일을 사용한 C++ 구현