Adjusted Rand Index (ARI) について勉強してみた

クラスタリングの性能評価でよくAdjusted Rand Index (ARI) が使われます． 僕もよく使っていますが，お恥ずかしながらよく知らずに使っていました． というのも，Rand Index (RI) は理解できるのですが，ARIのAdjustedの意味がよくわかりませんでした． というわけで，勉強してみました．

まず，クラスタリングは，サンプル$S = \{o_i\}_{i=1}^n$を$k (1 \leq k \leq n)$個の互いに素なグループに分けることを目的とします． この記事では，真のクラスタリング結果と，クラスタリングアルゴリズムの結果が似ているかどうかを測ることを目的とします． なお，ここでは，クラスタリングの結果をクラスタラベルで表現することにします．

さて，$S$に対する， 真のクラスタラベルを$\boldsymbol{\ell}=[\ell_1 \cdots \ell_n], \ell_i \in \{1, \ldots, k\} \forall i=1, \ldots, n$， クラスタリングアルゴリズムによるクラスタラベルを$\hat{ \boldsymbol{\ell}}=[\hat{\ell}_1 \cdots \hat{\ell}_n], \hat{\ell}_i \in \{1, \ldots, \hat{k}\} \forall i=1, \ldots, n$とします． クラスタリングの結果は，分類のようにラベルで考えるのではなく，ラベルのペアで考えます． つまり，「このサンプルとこのサンプルは同じクラスタに属するか否か」で性能を評価します． というわけで，$\boldsymbol{\ell}$と $\hat{\boldsymbol{\ell}}$を以下のように表現し直します．

$$\begin{align*} \mathcal{X} &= \{I(\ell_i = \ell_j) | (i,j) \in C(n, 2)\} = \{x_i\}_{i=1}^m\\ \mathcal{Y} &= \{I(\hat{\ell}_i = \hat{\ell}_j) | (i,j) \in C(n, 2)\} = \{y_i\}_{i=1}^m \end{align*}$$

ただし，$m={}_n C _2$． さて，ここで，Rand Indexの定義を見てみます． 正規化されていないRand Indexは次式で定義されます（自己流です）．

$$\begin{align*} RI(x, y) = \sum_{i=1}^m I(x_i=y_i) \end{align*}$$

ただし，$I$は指示関数で，$I(true) = 1, I(false) = 0$です． この式は，$x_i=y_i$ の数を表しており，二つのクラスタリングがどのくらい似ているかを表しています．

よくRIの欠点として，「二つのクラスタリングに相関がなくても，高い値をとってしまう」という説明がなされます． これの意味は，「適当（ランダム）にクラスタリングしても高い値をとってしまう」ということだと思います． $x_i = 0$となる$\mathcal{X}$内の要素数が，$x_i = 1$となる要素数に比べて圧倒的に多いので， 例えば「全てを異なるクラスタに分ける」というクラスタリングを行うと，$y_i = 0$となり，RIの値が高くなってしまいます． これは，分類問題において，クラスバランスが偏った状態で精度を使うのが適切ではない理由に似ています．

このような問題を解決しようと提案されたのがARIです． ARIでは，適当に行われたであろうクラスタリングにペナルティを与えます． どのようなペナルティが適切でしょうか？ ARIでは，ペナルティ＝「適当にクラスタリングした時のRIの値」と考えます． 以下このペナルティを求めていきます．

まず，二つのデータ$\mathcal{X}, \mathcal{Y}$がぞれぞれ独立に同一の分布$p(x), p(y)$から生成されたと仮定します：

$$\begin{align*} \mathcal{X} \stackrel{i.i.d.}{\sim} p(x)\\ \mathcal{Y} \stackrel{i.i.d.}{\sim} p(y) \end{align*}$$

$p(x)$と$p(y)$はそれぞれ確率変数$x$と$y$の従う分布に対応する確率密度関数を表します． まず，上で定義したペナルティ中の「適当にクラスタリングした時」というのを，「$x$と$y$が独立な時」と定義します． そうすると，求めるペナルティは「$x$と$y$が独立な時のRIの値」となり，具体的になりました． そのようなペナルティは，以下で求められます．

$$\begin{align*} \mathbb{E}_{(x,y) \sim p(x,y)}\left[RI\right] &= \mathbb{E}_{(x,y) \sim p(x,y)}\left[ \sum_{i=1}^m I(x_i=y_i) \right] \\ &= \sum_{x=0}^1 \sum_{y=0}^1 \sum_{i=1}^m I(x_i=y_i) p(x, y) \\ &= \sum_{i=1}^m \left( p(x=1, y=1) + p(x=0, y=0) \right) \\ &= m \left( p(x=1, y=1) + p(x=0, y=0) \right) \\ &= m \left( p(x=1)p(y=1) + p(x=0)p(y=0) \right) \end{align*}$$

最後の変形は$x$と$y$の独立性を使いました． $p(x=0), p(x=1), p(y=0), p(y=1)$は未知なので，データから推定してやらねばなりません． ここでは，以下のように，最尤推定で求めることにしましょう．

$$\begin{align*} p(x=1) &= \frac{1}{m} \sum_{i=1}^m x_i, \ p(x=0) = 1 - p(x=1) \\ p(y=1) &= \frac{1}{m} \sum_{i=1}^m y_i, \ p(y=0) = 1 - p(y=1) \end{align*}$$

無事上で定義したペナルティをもとめることができました． RIから求めたペナルティを引けば，ARIの完成になります：

$$\begin{align*} ARI(x, y) = \sum_{i=1}^m I(x_i=y_i) - \mathbb{E}_{(x,y) \sim p(x,y)}\left[RI\right] \end{align*}$$

通常，RIは以下のように，0から1の値をとるように正規化して使われます．

$$\begin{align*} normalized RI(x, y) = \frac{1}{m} \sum_{i=1}^m I(x_i=y_i) \end{align*}$$

なので，正規化したARIは以下のようになります．

$$\begin{align*} normalized ARI(x, y) = \frac{\sum_{i=1}^m I(x_i=y_i) - \mathbb{E}_{(x,y) \sim p(x,y)}\left[RI\right]}{m-\mathbb{E}_{(x,y) \sim p(x,y)}\left[RI\right]} \end{align*}$$

Wikipediaの定義式なんかと一致するのを示したほうが良かったですね…． 時間があれば追記しておきます． なお，具体例は以下のページが参考になります．

• http://y-uti.hatenablog.jp/entry/2014/01/19/133936