幾何平均線

幾何学において、ユークリッド空間内の離散点集合の幾何中央値は、標本点までの距離の合計を最小化する点である。これは、1次元データの距離の合計または絶対差を最小化する特性を持つ中央値を一般化したものである。これは、空間中央値^[1]、ユークリッド最小和点^[1]、トリチェリ点^[2]、または1中央値とも呼ばれる。これは、高次元での中心傾向の尺度を提供し、施設配置、すなわち輸送コストを最小化する施設の配置における標準的な問題である。^[3]

幾何中央値は統計学において重要な位置推定量です。 ^[4]これは、サンプルのL ₂距離の合計を最小化するためです。 ^{[5]これは、} L _2距離の二乗の合計を最小化する平均と比較されます。また、 L ₁距離の合計を最小化する座標ごとの中央値と比較されます。より一般的なk中央値問題は、各サンプルポイントから最も近い中心までのL ₂距離の合計を最小化するk個のクラスター中心の位置を求めます。

平面上の 3 点 (つまり、以下の定義でm = 3 およびn = 2) の問題の特殊なケースは、フェルマーの問題とも呼ばれることがあります。これは極小シュタイナー木の構築で発生し、もともとピエール・ド・フェルマーによって問題として提起され、エヴァンジェリスタ・トリチェリによって解決されました。^[6]その解は現在、3 つのサンプル ポイントによって形成される三角形のフェルマー点^{として知られています。 [7]幾何学的中央値は、}重み付き距離の合計を最小化する問題に一般化できます。これは、アルフレッド・ウェーバーが 1909 年に施設配置に関する本でこの問題について議論したことにちなんで、ウェーバー問題^{と呼ばれています。 [1]一部の情報源では、ウェーバーの問題を}フェルマー-ウェーバー問題と呼んでいますが、^[8]この名前を重みなしの幾何学的中央値問題に使用することもあります。^[9]

Wesolowsky (1993) は、幾何中央値問題の概要を示しています。この問題を非離散点集合に一般化したものについては、Fekete、Mitchell、Beurer (2005) を参照してください。

正式には、各 のm点の集合に対して、幾何中央値はL ₂距離最小値 の合計として定義されます。${\displaystyle \mathbb {X} ^{m}=x_{1},x_{2},\dots ,x_{m}\,}$${\displaystyle x_{i}\in \mathbb {R} ^{n}}$

${\displaystyle {\underset {y\in \mathbb {R} ^{n}}{\operatorname {arg\,min} }}\sum _{i=1}^{m}\left\|x_{i}-y\right\|_{2}}$

ここで、arg min は、合計を最小にする引数の値を意味します。この場合、引数は、までのすべてのユークリッド距離の合計が最小となるn次元ユークリッド空間内の点です。 ${\displaystyle y}$${\displaystyle y}$${\displaystyle x_{i}}$

• 1次元の場合、幾何中央値は中央値と一致します。これは、一変量中央値も点からの距離の合計を最小化するためです。（より正確には、点がp ₁、...、p _{n の}順序である場合、幾何中央値はnが奇数であれば中点ですが、 nが偶数の場合は一意に決定されず、2つの中点とを結ぶ線分上の任意の点になります。）^{[10] [11]}${\displaystyle p_{(n+1)/2}}$${\displaystyle p_{n/2}}$${\displaystyle p_{(n/2)+1}}$
• 幾何中線は点が同一直線上にない場合には一意である。^[12]
• 幾何中央値は、平行移動や回転を含むユークリッド相似変換に対して同変である。^{[13] [10]}これは、幾何中央値を変換しても、同じ変換をサンプルデータに適用して変換されたデータの幾何中央値を見つけても同じ結果が得られることを意味する。この特性は、幾何中央値がペアワイズ距離からのみ定義され、サンプルデータが表現される直交デカルト座標系に依存しないという事実から生じる。対照的に、多変量データセットの成分ごとの中央値は一般に回転不変ではなく、座標の選択からも独立していない。^[13]
• 幾何中央値のブレークダウンポイントは0.5です。^[13]つまり、サンプルデータの最大半分が任意に破損している可能性があり、サンプルの中央値は破損していないデータの位置の堅牢な推定値を提供します。

• 3 つの点（同一直線上にない）について、それらの点によって形成される三角形のいずれかの角度が 120° 以上である場合、幾何中線はその角度の頂点にある点です。すべての角度が 120° 未満の場合、幾何中線は三角形の頂点の 3 組それぞれに対して 120° の角度を成す三角形内の点です。^{[10]これは、3 つの頂点によって形成される三角形の}フェルマー点としても知られています。（3 つの点が同一直線上にある場合、幾何中線は 1 次元中線の場合と同様に、他の 2 点間の点です。）
• 4つの共平面点の場合、 4つの点のうち1つが他の3つの点によって形成される三角形の内側にある場合、その点が幾何学的中線となります。それ以外の場合、4つの点は凸四辺形を形成し、幾何学的中線は四辺形の対角線の交点となります。4つの共平面点の幾何学的中線は、4つの点の唯一のラドン点と同じです。^[14]

幾何中線は理解しやすい概念であるにもかかわらず、それを計算するのは難しい。重心または質量の中心は、幾何中線と同様に、各点までの距離の二乗の合計を最小化するものとして定義され、その座標が各点の座標の平均である簡単な式で求めることができるが、幾何中線に対しては、明示的な式や、算術演算とk乗根のみを含む正確なアルゴリズムは一般には存在しないことが示されている。したがって、この問題の解は、この計算モデルでは数値的または記号的な近似値しか得られない。^[15]

しかし、各ステップでより正確な近似値が得られる反復手順を使用して、幾何中央値の近似値を計算するのは簡単です。このタイプの手順は、各サンプル ポイントまでの距離が凸であり、凸関数の合計が凸のままであるため、サンプル ポイントまでの距離の合計が凸関数であるという事実から導き出すことができます。したがって、各ステップで距離の合計を減らす手順は、局所最適値に陥ることはありません。

このタイプの一般的なアプローチの1つは、エンドレ・ワイスフェルトの研究にちなんでワイスフェルトのアルゴリズムと呼ばれ、^[16]は、反復的に再重み付けされた最小二乗法の一種です。このアルゴリズムは、現在の推定値からサンプルポイントまでの距離に反比例する重みのセットを定義し、これらの重みに従ってサンプルの加重平均である新しい推定値を作成します。つまり、

${\displaystyle \left.y_{k+1}=\left(\sum _{i=1}^{m}{\frac {x_{i}}{\|x_{i}-y_{k}\|}}\right)\right/\left(\sum _{i=1}^{m}{\frac {1}{\|x_{i}-y_{k}\|}}\right).}$

この方法はほぼすべての初期位置で収束しますが、推定値の1つが与えられた点の1つに該当する場合は収束に失敗する可能性があります。これらのケースを処理するように修正することで、すべての初期点で収束するようにすることができます。^[12]

Bose、Maheshwari、Morin (2003)は、この問題の近似最適解を見つけるためのより洗練された幾何最適化手順を説明しています。Cohenら (2016)は、ほぼ線形時間で任意の精度で幾何中央値を計算する方法を示しています。また、この問題は2次円錐計画として定式化できることにも注意してください。

${\displaystyle {\underset {y\in \mathbb {R} ^{n},\ s\in \mathbb {R} ^{m}}{\min }}\ \sum _{i=1}^{m}s_{i}{\text{ ただし }}s_{i}\geq \left\|x_{i}-y\right\|_{2}{\text{ }}i=1,\ldots ,m, の場合}$

これは一般的な最適化ソルバーを使用して多項式時間で解決できます。

y がすべての指定された点x _iと異なる場合、y が幾何中央値となるのは、次の条件を満たす場合のみです。

${\displaystyle 0=\sum _{i=1}^{m}{\frac {x_{i}-y}{\left\|x_{i}-y\right\|}}.}$

これは次と同等です:

${\displaystyle \left.y=\left(\sum _{i=1}^{m}{\frac {x_{i}}{\|x_{i}-y\|}}\right)\right/\left(\sum _{i=1}^{m}{\frac {1}{\|x_{i}-y\|}}\right),}$

これはワイズフェルドのアルゴリズムと密接に関連しています。

一般に、 y が幾何中央値となるのは、次の条件を満たす ベクトルu _{iが存在する場合のみです。}

${\displaystyle 0=\sum _{i=1}^{m}u_{i}}$

ただし、 x _i ≠ yの場合、

${\displaystyle u_{i}={\frac {x_{i}-y}{\left\|x_{i}-y\right\|}}}$

そしてx _i = y の場合、

${\displaystyle \|u_{i}\|\leq 1.}$

この条件の同等の定式化は次のようになる。

${\displaystyle \sum _{1\leq i\leq m,x_{i}\neq y}{\frac {x_{i}-y}{\left\|x_{i}-y\right\|}}\leq \left|\{\,i\mid 1\leq i\leq m,x_{i}=y\,\}\right|.}$

これは、特にy を通る任意の超平面によって誘導される点の任意の分割が、各側でyからの正の方向の合計が同じで反対であるという意味において、中位特性の一般化として見ることができます。1 次元の場合、超平面は点y自体であり、方向の合計は (有向) 計数測度に簡略化されます。

幾何中央値は、リーマン多様体上のフレシェ平均を定義するのと同じ考え方を使って、ユークリッド空間から一般リーマン多様体（さらには計量空間）に一般化できる。 ^{[17] [18]}を対応する距離関数 を持つリーマン多様体とし、 を合計1になる重みとし、をからの観測 値とする。次に、データ点の 加重幾何中央値（または加重フレシェ中央値）を次のように定義する。${\displaystyle M}$${\displaystyle d(\cdot ,\cdot )}$${\displaystyle w_{1},\ldots ,w_{n}}$${\displaystyle n}$${\displaystyle x_{1},\ldots ,x_{n}}$${\displaystyle n}$${\displaystyle M}$${\displaystyle m}$

${\displaystyle m={\underset {x\in M}{\operatorname {arg\,min} }}\sum _{i=1}^{n}w_{i}d(x,x_{i})}$。

すべての重みが等しい場合は、単に幾何中央値であると言います。 ${\displaystyle m}$

• メドイド
• 幾何平均絶対偏差