平均シフト

平均シフトは、密度関数の最大値を見つけるためのノンパラメトリック 特徴空間数学解析手法であり、いわゆるモード探索アルゴリズムです。^[1]応用分野には、コンピュータービジョンや画像処理におけるクラスター分析が含まれます。^[2]

平均シフト法は、通常、1975年の福永とホステラーの研究によるものとされている。^[3]しかし、これは1964年のシュネルによる以前の研究を彷彿とさせる。^[4]

平均シフトは、その関数からサンプリングされた離散データが与えられたときに、密度関数の最大値（モード）を見つける手順です。 ^[1]これは反復法であり、初期推定値 から開始します。カーネル関数が与えられているとします。この関数は、平均の再推定のために近くの点の重みを決定します。通常、現在の推定値までの距離に関するガウスカーネルが使用されます。によって決定されるウィンドウ内の密度の加重平均は、 ${\displaystyle x}$ ${\displaystyle K(x_{i}-x)}$${\displaystyle K(x_{i}-x)=e^{-c||x_{i}-x||^{2}}}$${\displaystyle K}$

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

ここで、は の近傍、つまり となる点の集合です。 ${\displaystyle N(x)}$${\displaystyle x}$${\displaystyle K(x_{i}-x)\neq 0}$

この差は、福永とホステラー^[3]では平均シフトと呼ばれています。 平均シフトアルゴリズムでは、 を設定し、収束するまで推定を繰り返します。 ${\displaystyle m(x)-x}$${\displaystyle x\leftarrow m(x)}$${\displaystyle m(x)}$

平均シフトアルゴリズムは多くのアプリケーションで広く使用されていますが、高次元空間で一般的なカーネルを使用したアルゴリズムの収束に対する厳密な証明はまだ知られていません。^[5] Aliyari Ghassabehは、微分可能で凸で厳密に減少するプロファイル関数を使用して、1次元で平均シフトアルゴリズムの収束を示しました。 ^[6]しかし、1次元の場合は現実世界でのアプリケーションが限られています。また、有限数の定常（または孤立）ポイントを持つ高次元でのアルゴリズムの収束も証明されています。^{[5] [7]}しかし、一般的なカーネル関数が有限の定常（または孤立）ポイントを持つための十分な条件は提供されていません。

ガウス平均シフトは期待値最大化アルゴリズムである。^[8]

データを-次元ユークリッド空間に埋め込まれた有限集合とする。を-球体の特性関数である平坦核とする。 ${\displaystyle S}$${\displaystyle n}$${\displaystyle X}$${\displaystyle K}$${\displaystyle \lambda }$${\displaystyle X}$

アルゴリズムの各反復では、すべてに対して同時に実行されます。最初の問題は、サンプルのスパースセットが与えられた場合に密度関数をどのように推定するかです。最も単純なアプローチの1つは、データを平滑化することです。たとえば、幅 の固定カーネルで畳み込むことによって、 ${\displaystyle s\leftarrow m(s)}$${\displaystyle s\in S}$${\displaystyle h}$

ここで、は入力サンプルで、はカーネル関数 (またはParzen ウィンドウ) です。はアルゴリズムの唯一のパラメータで、帯域幅と呼ばれます。 このアプローチは、カーネル密度推定または Parzen ウィンドウ手法として知られています。 上記の式から計算したら、勾配上昇法またはその他の最適化手法を使用して、その極大値を見つけることができます。 この「力ずく」アプローチの問題点は、高次元の場合、完全な検索空間を評価するには計算上不可能になることです。 代わりに、平均シフトは、最適化の文献で多重再開勾配降下法として知られているもののバリエーションを使用します。ランダムな入力データ ポイントである可能性のある極大値の推測から始めて、平均シフトはでの密度推定の勾配を計算し、その方向に上り坂を進みます。^[9]${\displaystyle x_{i}}$${\displaystyle k(r)}$${\displaystyle h}$${\displaystyle f(x)}$${\displaystyle f(x)}$${\displaystyle y_{k}}$${\displaystyle x_{1}}$${\displaystyle f(x)}$${\displaystyle y_{k}}$

カーネルの定義: を-次元ユークリッド空間とします。 のノルムは非負の数です。関数がカーネルであるとは、プロファイル、が存在し、 ${\displaystyle X}$${\displaystyle n}$${\displaystyle \mathbb {R} ^{n}}$${\displaystyle x}$${\displaystyle \|x\|^{2}=x^{\top }x\geq 0}$${\displaystyle K:X\rightarrow \mathbb {R} }$${\displaystyle k:[0,\infty ]\rightarrow \mathbb {R} }$

${\displaystyle K(x)=k(\|x\|^{2})}$ そして

• k は負ではありません。
• k は非増加です:の場合。${\displaystyle k(a)\geq k(b)}$${\displaystyle a<b}$
• kは区分的に連続しており、${\displaystyle \int _{0}^{\infty }k(r)\,dr<\infty \ }$

平均シフトに最も頻繁に使用される 2 つのカーネル プロファイルは次のとおりです。

フラットカーネル

ガウスカーネル

ここで、標準偏差パラメータは帯域幅パラメータとして機能します。 ${\displaystyle \sigma }$${\displaystyle h}$

2 次元空間の点の集合について考えてみましょう。 を中心とし、半径をカーネルとする円形のウィンドウを想定します。平均シフトは、収束するまでこのカーネルを高密度領域に繰り返しシフトするヒル クライミング アルゴリズムです。すべてのシフトは平均シフト ベクトルによって定義されます。平均シフト ベクトルは常に、密度が最大に増加する方向を指します。すべての反復で、カーネルは重心またはカーネル内の点の平均にシフトされます。この平均を計算する方法は、カーネルの選択によって異なります。この場合、フラット カーネルの代わりにガウス カーネルを選択すると、各点に最初に重みが割り当てられ、カーネルの中心からの距離が増加するにつれて、この重みは指数関数的に減少します。収束すると、シフトによってカーネル内の点をさらに収容できる方向はなくなります。 ${\displaystyle C}$${\displaystyle r}$

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

を、結合空間範囲領域における次元の入力ピクセルとフィルタリングされた画像ピクセル とする。各ピクセルについて、${\displaystyle x_{i}}$${\displaystyle z_{i},i=1,...,n,}$${\displaystyle d}$

• 初期化して${\displaystyle j=1}$${\displaystyle y_{i,1}=x_{i}}$
• 収束するまで、に従って計算します。${\displaystyle y_{i,j+1}}$${\displaystyle m(\cdot )}$${\displaystyle y=y_{i,c}}$
• を割り当てます。上付き文字 s と r は、それぞれベクトルの空間成分と範囲成分を表します。この割り当ては、空間位置軸でフィルタリングされたデータが収束点の範囲成分を持つことを指定します。${\displaystyle z_{i}=(x_{i}^{s},y_{i,c}^{r})}$${\displaystyle y_{i,c}^{r}}$

1. 平均シフトは、実際のデータ分析に適した、アプリケーションに依存しないツールです。
2. データ クラスター上で事前定義された形状を想定しません。
3. 任意の特徴空間を扱うことができます。
4. この手順では、帯域幅という単一のパラメータの選択に依存します。
5. 帯域幅/ウィンドウ サイズ 'h' は、 k平均法とは異なり、物理的な意味を持ちます。

1. ウィンドウ サイズの選択は簡単ではありません。
2. ウィンドウ サイズが不適切だと、モードがマージされたり、追加の「浅い」モードが生成されたりする可能性があります。
3. 多くの場合、適応ウィンドウ サイズを使用する必要があります。

アルゴリズムのバリエーションは、機械学習および画像処理パッケージで見つけることができます。

• ELKI。多数のクラスタリング アルゴリズムを備えた Java データ マイニング ツール。
• ImageJ。平均シフト フィルターを使用した画像フィルタリング。
• mlpack。効率的なデュアルツリー アルゴリズム ベースの実装。
• OpenCVにはcvMeanShiftメソッドによる平均シフト実装が含まれています。
• Orfeo ツールボックス。C++ 実装。
• scikit-learn Numpy/Python 実装では、効率的な隣接ポイントの検索にボールツリーを使用します。

• DBスキャン
• OPTICSアルゴリズム
• カーネル密度推定(KDE)
• カーネル（統計）