ランド指数

ランド指数^[1]（ランドしすう、テンプレート:Lang-en-short）またはランド測度（ランドそくど、テンプレート:Lang-en-short）は、統計、特にデータ・クラスタリングにおいて、2つのクラスタリングの類似性を図る尺度である。William M. Randにちなんで名付けられた。要素の偶然のグループ化を調整した形で定義したものが調整ランド指数である。数学的には、ランド指数は accuracy に関連しているが、クラスラベルを使用しない場合にも適用できる。

ランド指数

定義

$n$ 個の要素からなる所与の集合 $S = {o_{1}, \dots, o_{n}}$ および $S$ の分割 $X = {X_{1}, \dots, X_{r}}$ および $Y = {Y_{1}, \dots, Y_{s}}$ を考え、以下のように定義する。

$a$ は、 $S$ の要素の組み合わせのうち、 $X$ で同じサブセット、 $Y$ で同じサブセットにあるものの数。
$b$ は、 $S$ の要素の組み合わせのうち、 $X$ で異なるサブセット、 $Y$ で異なるサブセットにあるものの数。
$c$ は、 $S$ の要素の組み合わせのうち、 $X$ で同じサブセット、 $Y$ で異なるサブセットにあるものの数。
$d$ は、 $S$ の要素の組み合わせのうち、 $X$ で異なるサブセット、 $Y$ で同じサブセットにあるものの数。

ランド指数 $R I$ は ^[1]^[2]

R I = \frac{a + b}{a + b + c + d} = \frac{a + b}{(\binom{n}{2})}

直感的には、 $a + b$ は $X$ と $Y$ の間の合意の数、 $c + d$ は $X$ と $Y$ の間の意見の相違の数と考えることができる。

分母はペアの総数なので、ランド指数はペアの総数に対する合意の発生頻度、つまり無作為に選ばれたペアにおいて $X$ と $Y$ が合意する確率を表している。

$(\binom{n}{2})$ は、 $n (n - 1) / 2$ として計算される。

同様に、次式のように、ランド指数 RI をアルゴリズムによる正しい判断の割合を示す指標として捉えることもできる。

R I = \frac{T P + T N}{T P + F P + F N + T N}

ここで、

T P

は真陽性の数、

T N

は真陰性の数、

F P

は偽陽性の数、

F N

は偽陰性の数を表す。

性質

ランド指数は0〜1の値を持ち、0は2つのデータ・クラスタリングがどのペアでも一致しないことを、1はデータクラスタリングが全く同じであることを示す。

数学的には、a、b、c、dは次のように定義される。

$a = | S^{*} |$ , $S^{*} = {(o_{i}, o_{j}) ∣ o_{i}, o_{j} \in X_{k}, o_{i}, o_{j} \in Y_{l}}$
$b = | S^{*} |$ , $S^{*} = {(o_{i}, o_{j}) ∣ o_{i} \in X_{k_{1}}, o_{j} \in X_{k_{2}}, o_{i} \in Y_{l_{1}}, o_{j} \in Y_{l_{2}}}$
$c = | S^{*} |$ , $S^{*} = {(o_{i}, o_{j}) ∣ o_{i}, o_{j} \in X_{k}, o_{i} \in Y_{l_{1}}, o_{j} \in Y_{l_{2}}}$
$d = | S^{*} |$ , $S^{*} = {(o_{i}, o_{j}) ∣ o_{i} \in X_{k_{1}}, o_{j} \in X_{k_{2}}, o_{i}, o_{j} \in Y_{l}}$

（任意の $1 \leq i, j \leq n, i \neq j, 1 \leq k, k_{1}, k_{2} \leq r, k_{1} \neq k_{2}, 1 \leq l, l_{1}, l_{2} \leq s, l_{1} \neq l_{2}$ に対して）

分類精度との関係

ランドインデックスは、 $S$ の要素のペアを対象とした二項分類精度を通して見ることもできる。 2つのクラスラベルは「 $o_{i}$ と $o_{j}$ が $X$ と $Y$ の同じサブセットにある」と「 $o_{i}$ と $o_{j}$ が $X$ と $Y$ の異なるサブセットにある」である。

その設定では、 $a$ は同じサブセットに属すると正しくラベル付けされたペアの数（真陽性）、 $b$ は異なるサブセットに属すると正しくラベル付けされたペアの数（真陰性）である。

調整ランド指数

調整ランド指数は、ランド指数を偶然性に基づいて補正したものである^[1]^[2]^[3]。このような偶然性の補正は、ランダムに指定されたクラスタリング間のすべてのペアワイズ比較の類似度の期待値を使用して、ベースラインを確立します。従来、ランド指数は、クラスタリングのための順列モデル（クラスタリング内のクラスターの数とサイズは固定されており、すべてのランダムクラスタリングは、固定されたクラスター間で要素をシャッフルすることによって生成される）を用いて補正されていた。

しかし、順列モデルの前提は頻繁に破られる。多くのクラスタリングのシナリオでは、クラスターの数またはクラスターのサイズ分布が大幅に異なる。例えば、K平均法では、クラスターの数は実務者によって固定されているが、それらのクラスターのサイズはデータから推測されるものとする。調整ランド指数のバリエーションは、ランダムなクラスタリングのさまざまなモデルを説明する^[4]。

ランド指数は0から1の間の値しか得られないが、調整ランド指数は、当てはまりが期待値よりも悪い場合、負の値を取り得る^[5]。

分割表

$n$ 個の要素からなる集合 $S$ に対し、2つのグループ化または分割（クラスタリングなど） $X = {X_{1}, X_{2}, \dots, X_{r}}$ と $Y = {Y_{1}, Y_{2}, \dots, Y_{s}}$ を考える。

$X$ と $Y$ の重なりは、次のような分割表 $[n_{i j}]$ にまとめることができる。ここで、 $n_{i j}$ のそれぞれは、 $X_{i}$ と $Y_{j}$ が共有するオブジェクトの数を表す。すなわち、 $n_{i j} = | X_{i} \cap Y_{j} |$ 。

\begin{matrix} \binom{}{X} ╲^{Y} & Y_{1} & Y_{2} & \dots & Y_{s} & sums \\ X_{1} & n_{11} & n_{12} & \dots & n_{1 s} & a_{1} \\ X_{2} & n_{21} & n_{22} & \dots & n_{2 s} & a_{2} \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ & ⋮ \\ X_{r} & n_{r 1} & n_{r 2} & \dots & n_{r s} & a_{r} \\ sums & b_{1} & b_{2} & \dots & b_{s} \end{matrix}

定義

順列モデルを使用したオリジナルの調整ランド指数は

A R I = \frac{\sum_{i j} (\binom{n_{i j}}{2}) - [\sum_{i} (\binom{a_{i}}{2}) \sum_{j} (\binom{b_{j}}{2})] / (\binom{n}{2})}{\frac{1}{2} [\sum_{i} (\binom{a_{i}}{2}) + \sum_{j} (\binom{b_{j}}{2})] - [\sum_{i} (\binom{a_{i}}{2}) \sum_{j} (\binom{b_{j}}{2})] / (\binom{n}{2})}

ここで、 $n_{i j}, a_{i}, b_{j}$ は分割表の値を表す。

脚注

テンプレート:Reflist

外部リンク

MATLAB mexファイルを使用した C++ の実装

[rand71-1] 1.0 ^1.1 ^1.2 テンプレート:Cite journal

[hb85-2] 2.0 ^2.1 テンプレート:Cite journal

[3] テンプレート:Cite conference PDF.

[ga17-4] テンプレート:Cite journal PDF.

[5] テンプレート:Cite web

[1]

[2]

[3]

[4]

[5]

ランド指数

目次