ランド指数のソースを表示

[[ファイル:Example_for_Adjusted_Rand_index.svg|サムネイル| [[K平均法]]（左）および平均値シフト法（右）によるデータセットのクラスタリングの例。この2つのクラスタリングについて計算された調整ランド指数は <math>ARI \approx 0.94</math>]]
'''ランド指数'''<ref name="rand71">{{Cite journal|last=W. M. Rand|year=1971|title=Objective criteria for the evaluation of clustering methods|journal=[[Journal of the American Statistical Association]]|volume=66|issue=336|pages=846–850|publisher=American Statistical Association|DOI=10.2307/2284239|JSTOR=2284239}}</ref>（ランドしすう、{{lang-en-short|Rand index}}）または'''ランド測度'''（ランドそくど、{{lang-en-short|Rand measure}}）は、[[統計学|統計]]、特に[[データ・クラスタリング]]において、2つのクラスタリングの類似性を図る尺度である。William M. Randにちなんで名付けられた。要素の偶然のグループ化を調整した形で定義したものが'''調整ランド指数'''である。数学的には、ランド指数は accuracy に関連しているが、クラスラベルを使用しない場合にも適用できる。

== ランド指数 ==

=== 定義 ===
<math>n</math> 個の要素からなる所与の集合<math>S = \{o_1, \ldots, o_n\}</math>および <math>S</math> の分割<math>X = \{X_1, \ldots, X_r\}</math>および<math>Y = \{Y_1, \ldots, Y_s\}</math> を考え、以下のように定義する。

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

ランド指数 <math>RI</math> は <ref name="rand71" /><ref name="hb85">{{Cite journal|last=Lawrence Hubert and Phipps Arabie|year=1985|title=Comparing partitions|journal=Journal of Classification|volume=2|issue=1|pages=193–218|DOI=10.1007/BF01908075}}</ref>

: <math> RI = \frac{a+b}{a+b+c+d} = \frac{a+b}{{n \choose 2 }}</math>

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

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

<math> {n \choose 2 }</math>は、<math> n(n-1)/2</math>  として計算される。


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

:: <math>
RI = \frac {TP + TN} {TP + FP + FN + TN}
</math>
: ここで、<math>TP</math> は真陽性の数、<math>TN</math> は真陰性の数、 <math>FP</math> は偽陽性の数、<math>FN</math> は偽陰性の数を表す。

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

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

* <math>a = |S^{*}|</math>, <math>S^{*} = \{ (o_{i}, o_{j}) \mid o_{i}, o_{j} \in X_{k}, o_{i}, o_{j} \in Y_{l}\}</math>
* <math>b = |S^{*}|</math>, <math>S^{*} = \{ (o_{i}, o_{j}) \mid o_{i} \in X_{k_{1}}, o_{j} \in X_{k_{2}}, o_{i} \in Y_{l_{1}}, o_{j} \in Y_{l_{2}}\}</math>
* <math>c = |S^{*}|</math>, <math>S^{*} = \{ (o_{i}, o_{j}) \mid o_{i}, o_{j} \in X_{k}, o_{i} \in Y_{l_{1}}, o_{j} \in Y_{l_{2}}\}</math>
* <math>d = |S^{*}|</math>, <math>S^{*} = \{ (o_{i}, o_{j}) \mid o_{i} \in X_{k_{1}}, o_{j} \in X_{k_{2}}, o_{i}, o_{j} \in Y_{l}\}</math>

（任意の<math>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}</math>に対して）

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

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

== 調整ランド指数 ==
調整ランド指数は、ランド指数を偶然性に基づいて補正したものである<ref name="rand71" /><ref name="hb85" /><ref>{{Cite conference|last=Nguyen Xuan Vinh, Julien Epps and James Bailey|title=Information Theoretic Measures for Clustering Comparison: Is a Correction for Chance Necessary?|book-title=ICML '09: Proceedings of the 26th Annual International Conference on Machine Learning|year=2009|pages=1073–1080|url=http://www.jmlr.org/papers/volume11/vinh10a/vinh10a.pdf|publisher=ACM}}[http://www.ima.umn.edu/~iwen/REU/10.pdf PDF].
</ref>。このような偶然性の補正は、ランダムに指定されたクラスタリング間のすべてのペアワイズ比較の類似度の期待値を使用して、ベースラインを確立します。従来、ランド指数は、クラスタリングのための順列モデル（クラスタリング内のクラスターの数とサイズは固定されており、すべてのランダムクラスタリングは、固定されたクラスター間で要素をシャッフルすることによって生成される）を用いて補正されていた。

しかし、順列モデルの前提は頻繁に破られる。多くのクラスタリングのシナリオでは、クラスターの数またはクラスターのサイズ分布が大幅に異なる。例えば、[[K平均法]]では、クラスターの数は実務者によって固定されているが、それらのクラスターのサイズはデータから推測されるものとする。調整ランド指数のバリエーションは、ランダムなクラスタリングのさまざまなモデルを説明する<ref name="ga17">{{Cite journal|last=Alexander J Gates and Yong-Yeol Ahn|year=2017|title=The Impact of Random Models on Clustering Similarity|url=http://www.jmlr.org/papers/volume18/17-039/17-039.pdf|journal=Journal of Machine Learning Research|volume=18|pages=1-28}}[http://www.jmlr.org/papers/volume18/17-039/17-039.pdf PDF].
</ref>。

ランド指数は0から1の間の値しか得られないが、調整ランド指数は、当てはまりが期待値よりも悪い場合、負の値を取り得る<ref>{{Cite web |url=https://i11www.iti.kit.edu/extra/publications/ww-cco-06.pdf |title=Comparing Clusterings - An Overview |author=Silke Wagner |format=pdf |date=2007-01-12 |accessdate=2021-10-05}}</ref>。

=== 分割表 ===
<math>n</math> 個の要素からなる集合 <math>S</math> に対し、2つのグループ化または分割（クラスタリングなど）<math>X = \{ X_1, X_2, \ldots, X_r \}</math> と <math>Y = \{ Y_1, Y_2, \ldots, Y_s \}</math> を考える。

<math>X</math> と <math>Y</math> の重なりは、次のような分割表 <math>\left[n_{ij}\right]</math> にまとめることができる。ここで、<math>n_{ij}</math> のそれぞれは、<math>X_i</math>と<math>Y_j</math> が共有するオブジェクトの数を表す 。すなわち、<math>n_{ij}=|X_i \cap Y_j|</math> 。

: <math>\begin{array}{c|cccc|c}
{{} \atop X}\!\diagdown\!^Y &
Y_1&
Y_2&
\cdots&
Y_s&
\text{sums}
\\
\hline
X_1&
n_{11}&
n_{12}&
\cdots&
n_{1s}&
a_1
\\
X_2&
n_{21}&
n_{22}&
\cdots&
n_{2s}&
a_2
\\
\vdots&
\vdots&
\vdots&
\ddots&
\vdots&
\vdots
\\
X_r&
n_{r1}&
n_{r2}&
\cdots&
n_{rs}&
a_r
\\
\hline
\text{sums}&
b_1&
b_2&
\cdots&
b_s&
\end{array}</math>

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

: <math>ARI = \frac{ \left. \sum_{ij} \binom{n_{ij}}{2} - \left[\sum_i \binom{a_i}{2} \sum_j \binom{b_j}{2}\right] \right/ \binom{n}{2} }{ \left. \frac{1}{2} \left[\sum_i \binom{a_i}{2} + \sum_j \binom{b_j}{2}\right] - \left[\sum_i \binom{a_i}{2} \sum_j \binom{b_j}{2}\right] \right/ \binom{n}{2} }</math>

ここで、<math>n_{ij}, a_i, b_j</math> は分割表の値を表す。

== 関連項目 ==
* 単純一致係数

== 脚注 ==
{{Reflist}}

== 外部リンク ==
* [https://github.com/bjoern-andres/partition-comparison MATLAB mexファイルを使用した C++ の実装]

{{DEFAULTSORT:らんとしすう}}
[[Category:クラスター分析]]
[[Category:統計学]]