ランド指数

2つのデータクラスタリング間の類似性の尺度

kMeans（左）とMean Shift （右）アルゴリズムを用いたデータセットのクラスタリング例。これら2つのクラスタリングの調整Rand指数は以下のように算出される。 ${\displaystyle ARI\approx 0.94}$

統計学、特にデータクラスタリングにおけるランド指数^[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値分類精度の観点からも見ることができます。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]}このような偶然性補正は、ランダムモデルによって指定されたクラスタリング間のすべてのペアワイズ比較の期待類似度を用いてベースラインを確立する。伝統的に、ランド指数はクラスタリングの順列モデルを用いて補正されてきた（クラスタリング内のクラスターの数とサイズは固定されており、すべてのランダムクラスタリングは固定されたクラスター間で要素をシャッフルすることによって生成される）。^{[注 1]}しかし、順列モデルの前提はしばしば破られる。多くのクラスタリングシナリオでは、クラスターの数またはクラスターのサイズ分布のいずれかが大幅に変化するからである。例えば、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}}$

参照

• 単純マッチング係数

注記

^{[注1]同様に順列を用いて}反事実的 再サンプルを作成する別のアプローチについては、 順列検定を参照してください。

参考文献

1. WM Rand (1971). 「クラスタリング手法の評価のための客観的基準」.アメリカ統計学会誌. 66 (336). アメリカ統計学会誌: 846–850 . doi :10.2307/2284239. JSTOR  2284239.
2. Lawrence HubertとPhipps Arabie (1985). 「パーティションの比較」. Journal of Classification . 2 (1): 193– 218. doi :10.1007/BF01908075.
3. Nguyen Xuan Vinh、Julien Epps、James Bailey (2009). 「クラスタリング比較のための情報理論的尺度：偶然性の補正は必要か？」(PDF) . ICML '09: 第26回国際機械学習会議議事録. ACM. pp.  1073– 1080.
4. Alexander J GatesとYong-Yeol Ahn (2017). 「ランダムモデルがクラスタリング類似度に与える影響」(PDF) . Journal of Machine Learning Research . 18 : 1–28 . arXiv : 1701.06508 .
5. Wagner, Silke; Wagner, Dorothea (2007年1月12日). 「クラスタリングの比較 - 概要」(PDF) . 2020年12月1日時点のオリジナル(PDF)からアーカイブ。

外部リンク

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

「https://en.wikipedia.org/w/index.php?title=Rand_index&oldid=1318214634」より取得