メドカップル

Statistics term

上は歪んだガンマ分布から抽出された5000個のランダム値のヒストグラム、下はmedcoupleカーネル値の対応するヒストグラムです。実際のmedcoupleは、下側の分布の中央値であり、黄色の線で0.188994と示されています。

統計学において、medcoupleは単変量分布の歪度を測定するロバストな統計量である。^[1] これは、分布の左半分と右半分の間の尺度化された中央値の差として定義される。そのロバスト性により、調整済み箱ひげ図における外れ値識別に適している。^{[2] [3]}通常の箱ひげ図は、非対称な長い裾を外れ値として分類するため、歪んだ分布には適していない。medcoupleを用いることで、箱ひげ図のヒゲを歪んだ分布に合わせて調整することができ、非対称な分布における外れ値をより正確に識別することができる。

メドカップルは順序統計量の一種で、不完全一般化L統計量のクラスに属します。^[1]通常の中央値や平均値と同様に、メドカップルはノンパラメトリック統計量であるため、任意の分布に対して計算できます。

意味

以下の説明では、多くのプログラミング言語のインデックスと調和させるために、 ゼロベースのインデックスを使用します。

を大きさ の順序付き標本とし、をの中央値とする。集合を定義する。 ${\displaystyle X:=\{x_{0}\geq x_{1}\geq \ldots \geq x_{n-1}\}}$ ${\displaystyle n}$ ${\displaystyle x_{m}}$ ${\displaystyle X}$

${\displaystyle X^{+}:=\{x_{i}~|~x_{i}\geq x_{m}\}}$、

${\displaystyle X^{-}:=\{x_{j}~|~x_{j}\leq x_{m}\}}$、

それぞれサイズとである。とに対して、カーネル関数を定義する。 ${\displaystyle p:=|X^{+}|}$ ${\displaystyle q:=|X^{-}|}$ ${\displaystyle x_{i}^{+}\in X^{+}}$ ${\displaystyle x_{j}^{-}\in X^{-}}$

${\displaystyle h(x_{i}^{+},x_{j}^{-}):={\begin{cases}\displaystyle {\frac {(x_{i}^{+}-x_{m})-(x_{m}-x_{j}^{-})}{x_{i}^{+}-x_{j}^{-}}}&{\text{ if }}x_{i}^{+}>x_{j}^{-},\\\operatorname {signum} (p-1-i-j)&{\text{ if }}x_{i}^{+}=x_{m}=x_{j}^{-},\end{cases}}}$

ここで、は符号関数です。 ${\displaystyle \operatorname {signum} }$

medcoupleはセットの中央値である^{[1] ：998}

${\displaystyle \{h(x_{i}^{+},x_{j}^{-})~|~x_{i}^{+}\in X^{+}{\text{ and }}x_{j}^{-}\in X^{-}\}}$。

言い換えれば、分布を中央値以上のすべての値と、中央値以下のすべての値に分割します。カーネル関数を定義し、その第1変数は中央値より大きい値に、第2変数は中央値より小さい値にそれぞれ対応させます。中央値と同値である特殊なケースについては、カーネルを符号関数で定義します。この場合、medcouple はのすべての値における中央値となります。 ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle pq}$ ${\displaystyle h(x_{i}^{+},x_{j}^{-})}$

medcoupleはすべてのカップルに適用される中央値ではなく、 のカップルにのみ適用される中央値であるため、不完全一般化L統計量のクラスに属します。^{[1] : 998} ${\displaystyle (x_{i},x_{j})}$ ${\displaystyle x_{i}^{+}\geq x_{m}\geq x_{j}^{-}}$

medcoupleの特性

medcouple には多くの望ましい特性があります。そのうちのいくつかはカーネル関数から直接継承されています。

medcoupleカーネル

カーネル関数については次のことが言えます。 ${\displaystyle h(x_{i}^{+},x_{j}^{-})}$

1. カーネル関数は位置不変である。^{[1] ：999}サンプルの各要素に任意の値を加算または減算しても、カーネル関数の対応する値は変化しない。 ${\displaystyle X}$
2. カーネル関数はスケール不変である。^{[1] : 999}サンプルのすべての要素を均等にスケーリングしても、カーネル関数の値は変化しない。 ${\displaystyle X}$

これらの特性は、medcoupleにも継承されます。したがって、medcoupleは分布の平均と標準偏差に依存しません。これは歪度を測定する上で望ましい特性です。計算を容易にするために、これらの特性を用いて2つの集合を定義することができます。

${\displaystyle Z^{+}:=\left.\left\{{\frac {x_{i}^{+}-x_{m}}{r}}~\right|~x_{i}^{+}\in X^{+}\right\}}$

${\displaystyle Z^{-}:=\left.\left\{{\frac {x_{j}^{-}-x_{m}}{r}}~\right|~x_{j}^{-}\in X^{-}\right\}}$

ここで、 です。これにより、セットの範囲は最大で 1、中央値は 0 になり、 medcouple は と同じになります。 ${\displaystyle r=2\max _{0\leq i\leq n-1}|x_{i}|}$ ${\displaystyle Z:=Z^{+}\cup Z^{-}}$ ${\displaystyle X}$

の場合、medcoupleカーネルは次のように簡約される。 ${\displaystyle Z}$

${\displaystyle h(z_{i}^{+},z_{j}^{-}):={\begin{cases}\displaystyle {\frac {z_{i}^{+}+z_{j}^{-}}{z_{i}^{+}-z_{j}^{-}}}&{\text{ if }}z_{i}^{+}>z_{j}^{-}\\\operatorname {signum} (p-1-i-j)&{\text{ if }}z_{i}^{+}=0=z_{j}^{-}\end{cases}}}$

再中心化され、再スケールされたセットを使用すると、次のことがわかります。 ${\displaystyle Z}$

3. 核関数は-1から1までの範囲にあり、^{[1] : 998、}つまり である。これは、と の逆三角不等式とという事実から導かれる。 ${\displaystyle |h(z_{i}^{+},z_{j}^{-})|\leq 1}$ ${\displaystyle |a|-|b|\leq |a-b|}$ ${\displaystyle a=z_{i}^{+}}$ ${\displaystyle b=z_{j}^{-}}$ ${\displaystyle z_{i}^{+}\geq 0\geq z_{j}^{-}}$
4. medcoupleカーネルは各変数について非減少です。 ${\displaystyle h(z_{i}^{+},z_{j}^{-})}$^{[1] : 1005}これは偏導関数とによって検証できます。どちらも非負です。なぜなら だからです。 ${\displaystyle {\frac {\partial h}{\partial z_{i}^{+}}}}$ ${\displaystyle {\frac {\partial h}{\partial z_{j}^{-}}}}$ ${\displaystyle z_{i}^{+}\geq 0\geq z_{j}^{-}}$

特性1、2、4を用いて、次の行列を定義することができる。

${\displaystyle H:=(h_{ij})=(h(z_{i}^{+},z_{j}^{-}))={\begin{pmatrix}h(z_{0}^{+},z_{0}^{-})&\cdots &h(z_{0}^{+},z_{q-1}^{-})\\\vdots &\ddots &\vdots \\h(z_{p-1}^{+},z_{0}^{-})&\cdots &h(z_{p-1}^{+},z_{q-1}^{-})\end{pmatrix}}.}$

セットを降順でソートすると、行列はソートされた行とソートされた列を持つ。^{[1] : 1006} ${\displaystyle Z^{+}}$ ${\displaystyle Z^{-}}$ ${\displaystyle H}$

${\displaystyle H={\begin{pmatrix}h(z_{0}^{+},z_{0}^{-})&\geq &\cdots &\geq &h(z_{0}^{+},z_{q-1}^{-})\\\geq &&&&\geq \\\vdots &&\ddots &&\vdots \\\geq &&&&\geq \\h(z_{p-1}^{+},z_{0}^{-})&\geq &\cdots &\geq &h(z_{p-1}^{+},z_{q-1}^{-})\end{pmatrix}}.}$

medcouple は、行と列がソートされたこの行列の中央値です。行と列がソートされているため、medcouple を計算する高速アルゴリズムを実装できます。

堅牢性

ブレークダウンポイントとは、統計量が意味を失わずに耐えられる値の数、つまり、統計量に影響が出る前にデータセットが持ちうる任意の大きな外れ値の数です。medcoupleの場合、ブレークダウンポイントは25%です。これは、各カップルの中央値をとった値であるためです。[ ^{1] : 1002} ${\displaystyle X}$ ${\displaystyle (x_{i},x_{j})}$ ${\displaystyle x_{i}\geq x_{m}\geq x_{j}}$

価値観

他の歪度指標と同様に、medcoupleは右に歪んだ分布では正、左に歪んだ分布では負、対称分布ではゼロとなります。さらに、medcoupleの値は絶対値が1で制限されます。^{[1] : 998}

medcoupleを計算するためのアルゴリズム

medcoupleアルゴリズムを紹介する前に、中央値を求めるアルゴリズムが存在することを思い出してください。medcoupleは中央値であるため、中央値を求めるための一般的なアルゴリズムが重要になります。 ${\displaystyle O(n)}$

ナイーブアルゴリズム

medcoupleを計算するナイーブなアルゴリズムは遅い。 ^{[1] : 1005}このアルゴリズムは2つのステップで実行される。まず、medcoupleカーネルの可能な値すべてを含むmedcouple行列を構築する。次のステップでは、この行列の中央値を求める。データセットのすべての要素が一意である場合、行列には​​要素が存在するため、ナイーブなアルゴリズムのアルゴリズムの複雑さはである。 ${\displaystyle H}$ ${\displaystyle pq\approx {\frac {n^{2}}{4}}}$ ${\displaystyle X}$ ${\displaystyle O(n^{2})}$

より具体的には、ナイーブなアルゴリズムは以下のように進行します。ゼロベースのインデックスを使用していることを思い出してください。

function naïve_medcouple( vector X): // X はサイズ n のベクトルです。 // 降順ソートはO(n log n)時間でインプレースで実行できます sort_decreasing (X)  xm := 中央値(X) xスケール:= 2 * max(abs(X)) // 上と下の中央揃えおよび再スケールされたベクトルを定義します // これらは X 自身の降順ソートを継承します Zplus := [(x - xm)/xscale | x in X such that x >= xm] Zminus := [(x - xm)/xscale | x <= xmとなるX内のx]  p := サイズ(Zプラス) q := サイズ(Zマイナス) // Zplus と Zminus 関数h(i, j)を閉じるカーネル関数を定義します。 a := Zplus[i] b := Zマイナス[j] a == bの場合: signum (p - 1 - i - j) を返す。 そうでない場合: (a + b) / (a - b) を返す。endif endfunction  // このベクトルを形成するのに必要な O(n^2) 回の演算 H := [h(i, j) | i は[0, 1, ..., p - 1]の範囲内、 j は[0, 1, ..., q - 1]の範囲内 中央値(H)を返す関数

medianサイズのベクトルに対する の最後の呼び出しは、操作内でそれ自体で実行できるため、単純な medcouple アルゴリズム全体の複雑さは同じです。 ${\displaystyle O(n^{2})}$ ${\displaystyle O(n^{2})}$

高速アルゴリズム

高速アルゴリズムは、medcouple行列のソートされた性質を利用することで、ナイーブアルゴリズムよりも優れた性能を発揮します。行列のすべての要素を計算する代わりに、高速アルゴリズムはJohnson & MizoguchiのK^番目のペアアルゴリズムを使用します。^[4] ${\displaystyle H}$

高速アルゴリズムの第一段階は、ナイーブアルゴリズムと同様に進行します。まず、カーネル行列 に必要な要素を計算します。この要素は、行と列が降順でソートされています。 のすべての値を計算する代わりに、以下の観察に基づいて、行と列の単調性を利用します。 ${\displaystyle H=(h_{ij})}$ ${\displaystyle h_{ij}}$

値をカーネル行列と比較する

まず、任意の を のすべての値と時間内に比較できることに注目してください。^{[4] : 150}たとえば、となるすべてのと を決定するには、次の関数があります。 ${\displaystyle u}$ ${\displaystyle h_{ij}}$ ${\displaystyle H}$ ${\displaystyle O(n)}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle h_{ij}>u}$

 function greater_h ( kernel h , int p , int q , real u ) : // h はカーネル関数、h(i,j) は H の i 番目と j 番目のエントリを返します// p と q はカーネル行列 H の行数と列数です// サイズ p のベクトルP : = vector ( p ) // インデックスは 0 から始まりますj : = 0 // 下から始めて、各行の [[supremum|least upper bound]] を計算しますfor i := p - 1 , p - 2 , ..., 1 , 0 : // u より小さい値が見つかるまでこの行を検索しますwhile j < qかつh ( i , j ) > u : j : = j + 1 endwhile // 今見つけたエントリの前のエントリが u より大きいですP [ i ] := j - 1 endfor return P endfunction                                                              

このgreater_h関数はカーネル行列を左下から右上へ走査し、各行について より大きい値と より小さいか等しい値の境界を示すインデックスのベクトルを返します。この方法は の行-列ソート特性のために機能します。 は の最大値を計算するため、その計算量は です。^{[4] : 150} ${\displaystyle P}$ ${\displaystyle u}$ ${\displaystyle u}$ ${\displaystyle H=(h_{ij})}$greater_h ${\displaystyle p+q}$ ${\displaystyle h_{ij}}$ ${\displaystyle O(n)}$

概念的には、結果のベクトルは、次の図に示すように、行列上に境界を確立するものと視覚化できます。ここで、赤い要素はすべて よりも大きくなります。 ${\displaystyle P}$ ${\displaystyle u}$

より小さい値を計算する対称アルゴリズムは非常に似ています。代わりに、右上から左下へと逆方向に処理が進みます。 ${\displaystyle h_{ij}}$ ${\displaystyle u}$ ${\displaystyle H}$

 function less_h ( kernel h , int p , int q , real u ) : // サイズ p のベクトルQ : = vector ( p ) // 最後の可能な行のインデックスj : = q - 1 // 上から始めて、各行の [[infimum|最大の下限]] を計算しますfor i := 0 , 1 , ..., p - 2 , p - 1 : // u より大きい値が見つかるまでこの行を検索しますwhile j >= 0かつh ( i , j ) < u : j : = j - 1 endwhile // 今見つけたエントリの次のエントリは u より小さいですQ [ i ] := j + 1 endfor return Q endfunction                                                              

この下限は次のように視覚化できます。ここで、青いエントリは より小さいです。 ${\displaystyle u}$

各 について が成り立ち、 に等しい値を持つ行に対してのみ厳密な不等式が発生します。 ${\displaystyle i}$ ${\displaystyle P_{i}\geq Q_{i}}$ ${\displaystyle u}$

また、合計額は

${\displaystyle \sum _{i=0}^{p-1}(P_{i}+1)~\qquad ~\sum _{i=0}^{p-1}Q_{i}}$

はそれぞれ、 の要素のうち より大きい要素の数、 以上の要素の数を与えます。したがって、この方法はの要素内におけるの順位も計算します。^{[4] : 149} ${\displaystyle H}$ ${\displaystyle u}$ ${\displaystyle u}$ ${\displaystyle u}$ ${\displaystyle h_{ij}}$ ${\displaystyle H}$

行中央値の加重中央値

2つ目の観察点は、ソートされた行列構造を用いることで、任意の要素を行列内の少なくとも半数の要素と瞬時に比較できることです。例えば、行列全体の行中央値の中央値は、赤色で示された左上象限よりも小さく、青色で示された右下象限よりも大きくなります。

より一般的には、前のセクションで与えられたベクトルと境界を使用して、いくつかの反復の後、medcoupleの位置が赤い左境界と青い右境界の間に位置することを正確に特定したと仮定できます。^{[4] ：149} ${\displaystyle P}$ ${\displaystyle Q}$

黄色のエントリは各行の中央値を示しています。中央値が揃うように行を並べ替え、境界外のエントリを無視すると、

これらの中央値の加重中央値を選択できます。各エントリは、この行に残っているエントリの数で重み付けされます。これにより、赤色で示された大きい値を破棄するか、青色で示された小さい値を破棄するかに関係なく、残りの値の少なくとも4分の1を破棄できます。

各行の中央値は行がソートされているので時間内に計算でき、加重中央値はバイナリ検索を使用して時間内に計算できる。^{[4] : 148} ${\displaystyle O(1)}$ ${\displaystyle O(n)}$

K^番目ペアアルゴリズム

高速medcoupleアルゴリズムの視覚化。これは、行と列がソートされた行列から始まり、暗い色の四角形は明るい色の四角形よりも小さくなります。各反復処理において、行の中央値の加重中央値が黄色で選択されます。次に、この値を行列の残りの部分と比較し、赤色の上限境界と青色の下限境界の候補を生成します。次に、アルゴリズムは、この境界によって除外されるエントリの数（黄色のエントリの順位を考慮することと同等）を考慮して、行列全体の中央値を除外することが分かっている境界を選択します。アルゴリズムは、黄色の行の中央値の加重中央値がmedcoupleと完全に一致するか、候補エントリの数が残りのエントリ間で選択ソートを実行できるほど小さくなるまで処理を続行します。

これら2つの観察をまとめると、高速medcoupleアルゴリズムは概ね次のように進行します。^{[4] : 148}

1. ソートされた行とソートされた列を使用して、 medcouple カーネル関数に必要な要素を計算します。 ${\displaystyle h(i,j)}$ ${\displaystyle p}$ ${\displaystyle q}$
2. 各反復において、medcoupleを行中央値の加重中央値で近似する。 ^{[4] : 148}
3. この暫定的な推測を行列全体と比較すると、それぞれ右境界ベクトルと左境界ベクトルが得られます。これらのベクトルの和から、この暫定的なmedcoupleの順位も得られます。 ${\displaystyle P}$ ${\displaystyle Q}$
   1. 仮のmedcoupleのランクがちょうど であれば、そこで終了です。medcoupleが見つかりました。 ${\displaystyle pq/2}$
   2. それ以外の場合は、ランクの要素がどちら側にあるかに応じて、 または を新しい右境界または左境界として選択して、暫定的な推測より大きいか小さいエントリを破棄します。この手順では、常に残りのすべてのエントリの少なくとも 1/4 が破棄されます。 ${\displaystyle P}$ ${\displaystyle Q}$ ${\displaystyle pq/2}$
4. 右境界と左境界の間の候補となるメドカップルの数が 以下になったら、残りのエントリ間で順位選択を実行し、この小さな候補セット内の順位がマトリックス全体内のメドカップルの順位に対応するようにします。 ${\displaystyle p}$ ${\displaystyle pq/2}$

関数を形成するための初期のソートには時間がかかります。各反復では、加重中央値の計算と、新たな暫定境界、左境界、右境界の計算に時間がかかります。各反復で残りのエントリの少なくとも4分の1が破棄されるため、反復回数は最大で^[4]回になります。したがって、高速アルゴリズム全体には時間がかかります。^{[4] :  150} ${\displaystyle h(i,j)}$ ${\displaystyle O(n\log n)}$ ${\displaystyle O(n)}$ ${\displaystyle P}$ ${\displaystyle Q}$ ${\displaystyle O(\log n)}$ ${\displaystyle O(n\log n)}$

高速アルゴリズムをもう少し詳しく説明しましょう。

function medcouple(ベクトルX): // Xはサイズnのベクトルです // 単純なmedcouple  sort_decreasing (X)と同様に初期成分を計算する  xm := 中央値(X) xスケール:= 2 * max(abs(X))  Zplus := [(x - xm)/xscale | x >= xmとなるX内のx] Zminus := [(x - xm)/xscale | x <= xmとなるX内のx]  p := サイズ(Zプラス) q := サイズ(Zマイナス) 関数h(i, j): a := Zplus[i] b := Zマイナス[j] a == bの場合: signum (p - 1 - i - j) を返す。 そうでない場合: (a + b) / (a - b) を返す。endif endfunction  // K番目のペアアルゴリズムの開始 (Johnson & Mizoguchi) // 左と右の初期境界、サイズ p の 2 つのベクトル L := [0, 0, ..., 0] R := [q - 1, q - 1, ..., q - 1] // 左境界の左側のエントリ数 合計 := 0 // 右境界の左側のエントリ数 R合計 := p*q // インデックスは 0 から始まるため、medcouple インデックスは その順位より 1 小さくなります。medcouple_index := floor (Rtotal / 2) // 境界間のエントリ数が 行列の行数より大きい間、反復します。 while Rtotal - Ltotal > p: // 行の中央値とそれに関連する重みを計算しますが、 すでに空になっている行はスキップします。middle_idx := [i | i in [0, 1, ..., p - 1] such  that L[i] <= R[i]] row_medians := [h(i, floor ((L[i] + R[i])/2) | middle_idxのi ] 重み := [R[i] - L[i] + 1 | middle_idxのi ]  WM :=加重中央値(row_medians, weights) // 新しい暫定的な右と左の境界 P := greater_h(h, p, q, WM) Q := less_h(h, p, q, WM)  P合計:=合計(P)+サイズ(P) Q合計:=合計(Q) // どのエントリを破棄するかを決定する、または medcouple が見つかったかどうか if medcouple_index <= Ptotal - 1: R := P R合計 := P合計 そうでない場合: medcouple_index > Qtotal - 1の場合: L := Q Ltotal := Qtotal それ以外： // medcouple が見つかりました。加重中央値の順位は medcouple インデックスに等しくなります。 WM を返すendif  endif 終わりまで  // medcouple は見つかりませんでしたが、暫定的なエントリはほとんど残っていません 残り := [h(i, j) | i in [0, 1, ..., p - 1],[L[i], L[i] + 1, ..., R[i]] 内の jであって、L[i] <= R[i]となるもの  // 残りのエントリの中から順位によってmedcoupleを選択します medcouple:= select_nth (remaining,medcouple_index - Ltotal) medcouple の終了関数を返す

実世界での使用においては、アルゴリズムは有限精度浮動小数点演算から生じる誤差も考慮する必要があります。例えば、medcoupleカーネル関数の比較はマシンイプシロン内で実行する必要があります。また、greater_h関数とless_h関数の順序比較も同様です。

ソフトウェア/ソースコード

• 高速 medcouple アルゴリズムは、Rの robustbase パッケージに実装されています。
• 高速 medcouple アルゴリズムは、Robustats Python パッケージの Python の C 拡張機能に実装されています。
• R 実装から派生した高速アルゴリズムのGPL ライセンスのC++実装。
• 高速アルゴリズムのStata実装。
• Matlab (およびGNU Octave )でのナイーブ アルゴリズムの実装。
• ナイーブ アルゴリズムは、Pythonパッケージ statsmodels にも実装されています。

参照

• 数学ポータル

• 堅牢な統計
• 歪度
• 調整済み箱ひげ図

参考文献

1. Brys, G.; Hubert, M.; Struyf, A. (2004年11月). 「歪度の堅牢な測定法」. Journal of Computational and Graphical Statistics . 13 (4): 996– 1017. doi :10.1198/106186004X12632. MR  2425170.
2. Hubert, M.; Vandervieren, E. (2008). 「歪んだ分布のための調整済み箱ひげ図」.計算統計とデータ分析. 52 (12): 5186– 5201. doi :10.1016/j.csda.2007.11.008. MR  2526585.
3. Pearson, Ron (2011年2月6日). 「Boxplots and Beyond – Part II: Asymmetry」. ExploringDataBlog . 2015年4月6日閲覧。
4. Johnson, Donald B. ; Mizoguchi, Tetsuo (1978年5月). 「X + YとX ₁ + X ₂ +...+ X _mにおけるK^番目の要素の選択」. SIAM Journal on Computing . 7 (2): 147– 153. doi :10.1137/0207013. MR  0502214.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Medcouple&oldid=1313033895"