平均移动

均值平移是一种用于定位密度函数最大值的非参数 特征空间分析技术，即所谓的模式寻找算法。^[1]应用领域包括聚类分析在计算机视觉和图像处理。^[2]

历史

平均移位程序最初由Fukunaga和Hostetler于1975年提出。^[3]

总览

均值偏移是用于定位所述最大值-所述一个程序模式 -of密度函数从该函数取样给定的离散数据。^[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}）\ neq 0}$。

区别 ${\ displaystyle m（x）-x}$在福永和Hostetler中被称为均值漂移。^[3] 所述的均值偏移算法现在套${\ displaystyle x \ leftarrow m（x）}$，然后重复估算，直到 ${\ displaystyle m（x）}$ 收敛。

尽管均值偏移算法已在许多应用中得到广泛使用，但是在高维空间中使用通用核对算法收敛的严格证明仍然未知。^[4] Aliyari Ghassabeh展示了一维平均偏移算法的收敛性，具有可微，凸和严格减小的轮廓函数。^[5]但是，一维案例在现实世界中的应用受到限制。此外，还证明了算法在较高维度上具有有限数量的（或孤立的）固定点的收敛性。^{[4] [6]}但是，尚未提供一般内核函数具有有限（或孤立）固定点的充分条件。

细节

设数据为有限集 ${\ displaystyle S}$ 嵌入 ${\ displaystyle n}$维欧氏空间， ${\ displaystyle X}$。让${\ displaystyle K}$ 是扁平核，这是 ${\ displaystyle \ lambda}$球进 ${\ displaystyle X}$，

在算法的每次迭代中， ${\ displaystyle s \ leftarrow m（s）}$ 为所有人执行 ${\ displaystyle s \ in S}$同时。那么，第一个问题是在给定稀疏样本集的情况下如何估计密度函数。最简单的方法之一是仅使数据平滑，例如通过将其与固定宽度的内核卷积${\ displaystyle h}$，

哪里 ${\ displaystyle x_ {i}}$ 是输入样本， ${\ displaystyle k（r）}$是内核函数（或Parzen窗口）。${\ displaystyle h}$是算法中的唯一参数，称为带宽。这种方法称为内核密度估计或Parzen窗口技术。一旦我们计算了${\ displaystyle f（x）}$从上面的方程式中，我们可以使用梯度上升或其他优化技术找到其局部最大值。这种“蛮力”方法的问题是，对于较大的尺寸，评估变得计算上难以实现${\ displaystyle f（x）}$在整个搜索空间中。取而代之的是，均值平移使用的是优化文献中称为多次重启梯度下降的变体。从一些局部最大值开始猜测，${\ displaystyle y_ {k}}$，可以是随机输入数据点 ${\ displaystyle x_ {1}}$，均值偏移计算密度估计值的梯度 ${\ displaystyle f（x）}$ 在 ${\ displaystyle y_ {k}}$并朝着这个方向迈出了艰难的一步。^[7]

内核类型

内核定义： ${\ 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 \}$

均值平移的两个最常用的内核配置文件是：

扁核

高斯核

标准偏差参数 ${\ displaystyle \ sigma}$ 用作带宽参数， ${\ displaystyle h}$。

应用领域

聚类

考虑二维空间中的一组点。假设一个以C为中心且半径为r的圆形窗口作为核。均值平移是一种爬山算法，它涉及将该内核迭代移至较高密度的区域，直到收敛为止。每个移位都由平均移位向量定义。平均偏移矢量始终指向密度最大增加的方向。在每次迭代中，内核都会移动到质心或其中的点的平均值。计算该平均值的方法取决于内核的选择。在这种情况下，如果选择高斯核而不是平面核，那么将首先为每个点分配一个权重，该权重会随着距核中心的距离增加而呈指数衰减。趋同

追踪

均值漂移算法可用于视觉跟踪。最简单的算法是根据先前图像中对象的颜色直方图在新图像中创建一个置信度图，并使用均值平移来找到对象旧位置附近的置信度图的峰值。置信度图是新图像上的概率密度函数，为新图像的每个像素分配一个概率，该概率是像素颜色在先前图像中的对象中出现的概率。一些算法（例如基于内核的对象跟踪，^[8] 集成跟踪，^[9] CAMshift ^{[10] [11]）} 扩展了这一思想。

平滑处理

让 ${\ 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}}$。
• 分配 ${\ displaystyle z_ {i} =（x_ {i} ^ {s}，y_ {i，c} ^ {r}）}$。上标s和r分别表示向量的空间和范围分量。该分配指定在空间位置轴处的已过滤数据将具有会聚点的范围分量${\ displaystyle y_ {i，c} ^ {r}}$。

长处

1. 均值平移是适合实际数据分析的独立于应用程序的工具。
2. 在数据群集上不采取任何预定义的形状。
3. 它能够处理任意特征空间。
4. 该过程取决于单个参数的选择：带宽。
5. 带宽/窗口大小'h'具有物理含义，与k -means不同。

弱点

1. 窗口大小的选择并非无关紧要。
2. 不合适的窗口大小可能导致模式合并，或生成其他“浅”模式。
3. 通常需要使用自适应窗口大小。

可用性

可以在机器学习和图像处理软件包中找到该算法的变体：

• ELKI。具有许多聚类算法的Java数据挖掘工具。
• ImageJ的。使用均值漂移滤波器进行图像滤波。
• OpenCV通过cvMeanShift方法包含均值偏移实现
• Orfeo工具箱。一个C ++实现。
• Scikit学习 Numpy / Python实现使用球树进行有效的相邻点查找

也可以看看

• 数据库扫描
• OPTICS算法
• 内核密度估计（KDE）
• 内核（统计）

参考文献