平均シフト

Mean_shift

平均シフトは、密度関数の最大値を見つけるためのノンパラメトリックな 特徴空間数学的解析手法であり、いわゆるモード探索アルゴリズムです。アプリケーション ドメインには、コンピューター ビジョンおよび画像処理におけるクラスター分析が含まれます。
コンテンツ
1 歴史2 概要 3 詳細
4 カーネルの種類
5 アプリケーション
5.1 クラスタリング 5.2 追跡 5.3 スムージング
6 強み
7 弱点
8 可用性
9 こちらもご覧ください
10 参考文献

歴史
平均シフト手順は通常、1975年に福永とホステトラーによって功を奏したとされています。

概要
平均シフトは、密度関数からサンプリングされた離散データが与えられた場合に、密度関数の最大値 (モード) を見つける手順です。これは反復法であり、最初の見積もりから始めます。X
{ x}

. カーネルを機能させるK (X I X )
{ K(x_{i}-x)}

与えられる。この関数は、平均値を再推定するために近くのポイントの重みを決定します。通常、現在の推定値までの距離に関するガウス カーネルが使用されます。K (X I X ) = e − c
| |
| |X
I −X | |
| | 2 { K(x_{i}-x)=e^{-c||x_{i}-x||^{2}}}

. によって決定されるウィンドウ内の密度の加重平均 K { K}
は メートル(X ) = ∑X I
εN (X ) K (X I −X )X I∑X I
εN (X ) K (X I −X )
{ m(x)={frac {sum _{x_{i}in N(x)}K(x_{i}-x)x_{i}}{sum _{x_{i} in N(x)}K(x_{i}-x)}}}

どこN (X )
{ N(x)}

の近所ですX
{ x}

、ポイントのセットK (X I X ) ≠ 0
{ K(x_{i}-x)neq 0}
. 違い
メートル(X ) −X
{ m(x)-x}

福永とホステラーでは平均シフトと呼ばれています。平均シフト アルゴリズムが設定されるようになりましたX
メートル(X )
{ xleftarrow m(x)}

、 まで推定を繰り返します。
メートル(X )
{ m(x)}

収束します。
平均シフト アルゴリズムは多くのアプリケーションで広く使用されていますが、高次元空間での一般的なカーネルを使用したアルゴリズムの収束の厳密な証明はまだ知られ Aliyari Ghassabeh は、微分可能な凸型の厳密に減少するプロファイル関数を使用して、1 次元での平均シフト アルゴリズムの収束を示しました。ただし、1 次元のケースは、現実世界での適用が限られています。また、有限数の静止 (または孤立) 点を使用した高次元でのアルゴリズムの収束が証明されています。 しかし、一般的なカーネル関数が有限の静止 (または孤立) 点を持つための十分条件は提供され
Gaussian Mean-Shift は期待値最大化アルゴリズムです。

詳細
データを有限集合とする S { S}

に埋め込まれた n { n}
-次元ユークリッド空間、X
{ X}

. させて K { K}

の特徴的な関数であるフラット カーネル λ { lambda }
-ボールインX
{ X}
K(X ) = { 1
もしも‖X ‖ ≤ λ 0
もしも‖X ‖ > λ
{ K(x)={begin{cases}1&{text{if}} |x|leq lambda \0&{text{if}} |x|>ラムダ \end{cases}}}
lambda \end{cases}}}””>
アルゴリズムの各反復では、 s メートル( s ) { sleftarrow m(s)}

すべてに対して実行されますs ε S
{ sin S}

同時に。したがって、最初の問題は、サンプルのまばらなセットが与えられた場合に密度関数を推定する方法です。最も単純なアプローチの 1 つは、データを単純に平滑化することです。たとえば、幅が固定されたカーネルでデータを畳み込みます。
時間
{ h}
へ(X ) = ∑ I K (X −X I) = ∑ I k( ‖X−X I ‖ 2
時間2 )
{ f(x)=sum _{i}K(x-x_{i})=sum _{i}kleft({frac {|x-x_{i}|^{ 2}}{h^{2}}}右)}

どこX I { x_{i}}

は入力サンプルで、 k ( r ) { k(r)}

はカーネル関数 (またはParzen ウィンドウ) です。
時間
{ h}

はアルゴリズムの唯一のパラメータであり、帯域幅と呼ばれます。このアプローチは、カーネル密度推定またはパルゼン ウィンドウ手法として知られています。計算したらへ (X )
{ f(x)}

上記の式から、勾配上昇またはその他の最適化手法を使用して、その極大値を見つけることができます。この「ブルート フォース」アプローチの問題点は、高次元の場合、評価が計算上非常に困難になることです。へ (X )
{ f(x)}

完全な検索スペースにわたって。代わりに、平均シフトは、最適化の文献で多重再始動勾配降下として知られているものの変形を使用します。極大値の推測から始めて、y k
{ y_{k}}

、これはランダムな入力データ ポイントにすることができますX 1 { x_{1}}

、平均シフトは密度推定の勾配を計算しますへ (X )
{ f(x)}
で y k
{ y_{k}}

そして、その方向に上り坂の一歩を踏み出します。

カーネルの種類
カーネル定義: LetX
{ X}

なる n { n}
-次元ユークリッド空間、
R n { mathbb {R} ^{n}}

. の規範X
{ x}

は負でない数であり、‖X ‖ 2 X ⊤
X≥ 0
{ |x|^{2}=x^{top}xgeq 0}

. 機能K :X R
{ K:Xrightarrow mathbb {R} }

プロファイルが存在する場合、カーネルと呼ばれます。k : R
{ k:rightarrow mathbb {R} }

、 そのような
K(X ) = k( ‖X‖ 2)
{ K(x)=k(|x|^{2})}
と k は非負です。
k は増加しません: k ( a) ≥ k( b ) { k(a)geq k(b)}

もしもa < b
{ a . k は区分連続であり、∫ 0 ∞ k( r) d r < ∞
{ int _{0}^{infty }k(r)，dr
平均シフトに最もよく使用される 2 つのカーネル プロファイルは次のとおりです。
フラットカーネルk (X ) = { 1
もしもX≤ λ 0
もしもX> λ
{ k(x)={begin{cases}1&{text{if}} xleq lambda \0&{text{if}} x>lambda \end{cases} }}
lambda\end{cases} “”>
ガウス カーネルk (X ) = e −X 2 σ
2 { k(x)=e^{-{frac {x}{2sigma ^{2}}}}，}

ここで、標準偏差パラメータ σ { sigma }

帯域幅パラメータとして機能し、
時間
{ h}
. アプリケーション編集

クラスタリング
2 次元空間の点の集合を考えてみましょう。を中心とする円形のウィンドウを仮定します。 ハ { C}

半径を持つ r { r}

カーネルとして。平均シフトは、収束するまで、このカーネルをより高密度の領域に繰り返しシフトするヒル クライミング アルゴリズムです。すべてのシフトは、平均シフト ベクトルによって定義されます。平均シフト ベクトルは常に、密度が最大に増加する方向を指します。反復ごとに、カーネルは重心またはその中の点の平均にシフトされます。この平均を計算する方法は、カーネルの選択によって異なります。この場合、フラット カーネルの代わりにガウス カーネルが選択されると、まずすべてのポイントに重みが割り当てられます。この重みは、カーネルの中心からの距離が増加するにつれて指数関数的に減衰します。収束時には、シフトがカーネル内により多くのポイントを収容できる方向はありません。

追跡
平均シフト アルゴリズムは、ビジュアル トラッキングに使用できます。このような最も単純なアルゴリズムは、前の画像のオブジェクトの色ヒストグラムに基づいて新しい画像に信頼マップを作成し、平均シフトを使用して、オブジェクトの古い位置に近い信頼マップのピークを見つけます。信頼マップは、新しい画像の確率密度関数であり、新しい画像の各ピクセルに確率を割り当てます。これは、前の画像のオブジェクトでピクセルの色が発生する確率です。カーネルベースのオブジェクト追跡、 アンサンブル追跡、 CAMshift などのいくつかのアルゴリズムこの考えを拡張しています。

スムージング
させてX I { x_{i}}
と ぜ
I 私 = 1 . . . n { z_{i}，i=1，…，n，}