ランド指数

統計学、特にデータクラスタリングにおけるランド指数[ ^1]またはランド尺度（ウィリアム・M・ランドにちなんで名付けられた）は、2つのデータクラスタリング間の類似性を測る尺度である。要素の偶然のグループ化に合わせて調整されたランド指数の形式を定義することができ、これが調整ランド指数である。ランド指数は、リンクがクラスター内に属するかどうかを判断する 精度である。

要素の集合と、比較する の 2 つの分割、( Sをr個のサブセットに分割)、および( Sをs 個のサブセットに分割)が与えられた場合、次を定義します。 ${\displaystyle n}$ ${\displaystyle S=\{o_{1},\ldots ,o_{n}\}}$${\displaystyle S}$${\displaystyle X=\{X_{1},\ldots ,X_{r}\}}$${\displaystyle Y=\{Y_{1},\ldots ,Y_{s}\}}$

• ${\displaystyle a}$、 の同じ部分集合にあり、の同じ部分集合にあるの要素のペアの数${\displaystyle S}$${\displaystyle X}$${\displaystyle Y}$
• ${\displaystyle b}$、 の異なる部分集合に含まれる の要素のペアの数との異なる部分集合に含まれる の要素のペアの数${\displaystyle S}$${\displaystyle X}$${\displaystyle Y}$
• ${\displaystyle c}$、 の同じ部分集合にあり、の異なる部分集合にあるの要素のペアの数${\displaystyle S}$${\displaystyle X}$${\displaystyle Y}$
• ${\displaystyle d}$、 の異なる部分集合にあり、の同じ部分集合にあるの要素のペアの数${\displaystyle S}$${\displaystyle X}$${\displaystyle Y}$

ランド指数は、次のとおりです。^{[1] [2]}${\displaystyle R}$

${\displaystyle R={\frac {a+b}{a+b+c+d}}={\frac {a+b}{n \choose 2}}}$

直感的には、 は との間の一致の数、は と の間の不一致の数と考えることができます。 ${\displaystyle a+b}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle c+d}$${\displaystyle X}$${\displaystyle Y}$

分母はペアの総数なので、ランド指数は、 ペアの総数に対する合意の発生頻度、またはランダムに選択されたペアに対して とが 合意する確率を表します。 ${\displaystyle X}$${\displaystyle Y}$

${\displaystyle {n \choose 2}}$は次のように計算されます。 ${\displaystyle n(n-1)/2}$

同様に、ランド指数はアルゴリズムによって下された正しい決定の割合の尺度として見ることもできます。これは次の式を使用して計算できます。

${\displaystyle RI={\frac {TP+TN}{TP+FP+FN+TN}}}$

ここで 、 は真陽性の数、は真陰性の数、は偽陽性の数、 は偽陰性の数です。${\displaystyle TP}$${\displaystyle TN}$${\displaystyle FP}$${\displaystyle FN}$

Rand 指数は 0 から 1 の間の値を持ち、0 は 2 つのデータ クラスタリングがどのポイントのペアでも一致しないことを示し、1 はデータ クラスタリングがまったく同じであることを示します。

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

• ${\displaystyle a=|S^{*}|}$、 どこ${\displaystyle S^{*}=\{(o_{i},o_{j})\mid o_{i},o_{j}\in X_{k},o_{i},o_{j}\in Y_{l}\}}$
• ${\displaystyle b=|S^{*}|}$、 どこ${\displaystyle 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}}\}}$
• ${\displaystyle c=|S^{*}|}$、 どこ${\displaystyle 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}}\}}$
• ${\displaystyle d=|S^{*}|}$、 どこ${\displaystyle 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}\}}$

一部の人にとって${\displaystyle 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}}$

Rand 指数は、 内の要素のペアに対するバイナリ分類精度のプリズムを通して見ることもできます。 2 つのクラス ラベルは「 と は、 と では同じサブセットにあります」であり、「とは、と では異なるサブセットにあります」です。 ${\displaystyle S}$${\displaystyle o_{i}}$${\displaystyle o_{j}}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle o_{i}}$${\displaystyle o_{j}}$${\displaystyle X}$${\displaystyle Y}$

この設定では、は同じサブセットに属すると正しくラベル付けされたペアの数 (真陽性) であり、 は 異なるサブセットに属すると正しくラベル付けされたペアの数 (真陰性) です。 ${\displaystyle a}$${\displaystyle b}$

調整済みランド指数は、ランド指数の偶然性補正版である。^{[1] [2] [3]}このような偶然性補正は、ランダムモデルによって指定されたクラスタリング間のすべてのペアワイズ比較の予想される類似性を使用してベースラインを確立する。従来、ランド指数はクラスタリングの順列モデルを使用して補正されていた（クラスタリング内のクラスターの数とサイズは固定されており、すべてのランダムクラスタリングは固定されたクラスター間で要素をシャッフルすることによって生成される）。しかし、順列モデルの前提は頻繁に破られる。多くのクラスタリングシナリオでは、クラスターの数またはそれらのクラスターのサイズ分布のいずれかが大幅に変化する。たとえば、K平均法では、クラスターの数は実行者によって固定されているが、それらのクラスターのサイズはデータから推測されることを考えてみてほしい。調整済みランド指数の変動は、ランダムクラスタリングのさまざまなモデルを説明するものである。^[4]

ランド指数は0から+1の間の値しか出ないが、調整されたランド指数は、指数が期待指数より小さい場合、負の値を出す可能性がある。^[5]

n個の要素の集合Sと、これらの要素の 2 つのグループ化または分割 (クラスタリングなど)、つまりと が与えられた場合、 XとYの重なりは分割表にまとめることができます。 分割表の各エントリは、とに共通するオブジェクトの数を表します 。${\displaystyle X=\{X_{1},X_{2},\ldots ,X_{r}\}}$${\displaystyle Y=\{Y_{1},Y_{2},\ldots ,Y_{s}\}}$${\displaystyle \left[n_{ij}\right]}$${\displaystyle n_{ij}}$${\displaystyle X_{i}}$${\displaystyle Y_{j}}$${\displaystyle n_{ij}=|X_{i}\cap Y_{j}|}$

${\displaystyle {\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}}}$

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

${\displaystyle 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}}}}}$

ここで、値は分割表から取得されます。 ${\displaystyle n_{ij},a_{i},b_{j}}$

• 単純マッチング係数

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