興味深い現象

興味深い現象、言語化、備忘。

Adjusted Mutual Information

イントロダクション

クラスタリングの性能を評価する指標に、AMI (Adjusted Mutual Information)というものがある。Wikipediaに英語の記事はあったが、日本語で解説している記事を見つけられなかったのでここに日本語でまとめる。

結局のところ

結局のところ、AMIはARI(Adjusted Rand Index)と同じような補正をしている。すなわち、真のクラスタとクラスタリングにより推定されたクラスタ間の相互情報量から、ランダム予測をした時の相互情報量の期待値を差し引くような補正をしている。

相互情報量

{N}個の要素からなる集合 {S=\{s_1,...,s_N\}} に対して、この {R} 個への分割 {U=\{U_1,...,U_R\}}と C個への分割 V=\{V_1,...V_C\}を考える。ここで考えているのはいわゆる堅いクラスタ、すなわち、

 { U_i \cap U_j = \emptyset = V_i \cap V_j}\, \, \, (i\not=j) \\
{\cup_{i=1}^R U_i = \cup_{j=1}^C V_j = S}

を満たすようなクラスタである。 このU,Vの情報はR×Cの行列Mを用いて

{

\begin{equation}
    n_{ij} = |U_i \cap V_j|
\end{equation}
}

として表せる。要素をランダムに選択した時、クラスタU_iの要素が選ばれる確率は

{\begin{equation}
    P_U(i) = \frac{|U_i|}{N}
\end{equation}
}

であり、分割U,Vのエントロピーは

{
\begin{equation}
    H(U) = -\sum_{i=1}^R P_U(i)\log P_U(i)
\end{equation}
}

{
\begin{equation}
    H(V) = -\sum_{i=1}^C P_V(i)\log P_V(i)
\end{equation}
}

である。二つの分割U,Vの相互情報量は

{
\begin{equation}
    MI(U,V) = \sum_{i=1}^R\sum_{j=1}^C P_{UV}(i,j)\log \frac{P_{UV}(i,j)}{P_U(i)P_V(j)}
\end{equation}
}

ここで、

{
\begin{equation}
    P_{UV}(i,j) = \frac{|U_i \cap V_j|}{N}
\end{equation}
}

ある分割の組U,Vが与えられている時の、相互情報量の期待値は

{
\begin{equation}
    \begin{split}
        E\{MI(U,V)\} &=\sum_{i=1}^R\sum_{j=1}^C \sum_{n_{ij}=(a_i+b_j-N)^+}^{\min(a_i,b_j)}\frac{n_{ij}}{N}\log\frac{N\cdot n_{ij}}{a_i b_j} \times \frac{\frac{a_i!}{n_{ij}!(a_i-n_{ij})!}\frac{(N-a_i)!}{(b_j-n_{ij})!(N-a_i-b_j-n_{ij})!}}{\frac{N!}{b_j!(N-b_j)!}}\\
        &= \sum_{i=1}^R\sum_{j=1}^C \sum_{n_{ij}=(a_i+b_j-N)^+}^{\min(a_i,b_j)}\frac{n_{ij}}{N}\log\frac{N\cdot n_{ij}}{a_i b_j}\times \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{split}
\end{equation}
}

ただし、

{
\begin{equation}
    (a_i+b_j-N)^+ = \max(1,a_i+b_j-N)
\end{equation}
}

これを用いて補正された相互情報量AMI(U,V)は

{
\begin{equation}
    AMI(U,V) = \frac{MI(U,V)-E\{MI(U,V)\}}{\max{H(U),H(V)}-E\{MI(U,V)\}}
\end{equation}
}

と表せる.