识别直方图中的局部最小值

Question

我有兴趣在直方图中找到大致相似的局部最小值

我想找到109.258的局部最小值,最简单的方法是确定109.258处的计数数是否低于某些区间内的平均计数(包括109.258).它确定了这个间隔对我来说是最困难的部分.

至于这个数据的来源,它是一个100个不均匀宽度的直方图.每个bin都有一个值(显示在x轴上),以及落入该bin的样本计数(显示在y轴上).我想要做的是找到分割直方图的"最佳"位置.分割的每一侧沿二叉树向下传播,作为分类算法的一部分.

我认为我最好的做法是尝试使用Levenberg-Marquardt算法之类的方法拟合这个直方图的曲线,然后比较局部最小值以找到"最佳"."最佳"的适当度量将包括对该分裂的重要性的一些指示,其被测量为左侧区间中的平均计数与右侧区间中的计数的平均值之间的差异,然后可能如果有意义的话,将每个差异与所包括的计数数量相加以得到"最佳"的复合测量值.

无论哪种方式,算法的计算复杂性都不是一个大问题,100个箱子大约是我期望遇到的最大数量.然而,这种计算将对于每个样品进行一次,因此保持它相对于线性的二进制位的数目将当然是理想的.

顺便说一下,我正在用C++做所有事情,并且使用了boost库和STL,因此在这方面没有任何限制.

任何有关最佳实践的想法或见解将不胜感激!

Answer 1

Levenberg-Marquardt在坚固耐用的优化地形中不是一个很好的选择 - 你的非常坚固.那里有很多当地的迷你.Levenberg-Marquardt可能会在100左右找到局部最小值.或者它可能会在图的极值处找到一个两个全局最小值,其中函数的尾部为零.

你想要找到最重要的局部最小值的东西.例如,某种聚类算法.这是一个非常简单的:

第1步:找到数据集中的本地极值.这些是极端范围的极值加上内部局部最小值和最大值.使用直方图,你应该有一个奇数的这种极值,在最小值和最大值之间交替.

第2步:找到具有最小增量的对.这将是(本地最大,本地最小)或(本地最小,本地最大)对.

第3步:找到要删除的一对元素,其中一个

1. 这对在步骤2找到
2. 该对包括来自步骤2的该对中的第一元素及其前身
3. 该对包括步骤2中该对的最后一个元素及其后继元素

当找到的对包括边界点时,您应该根据需要使用选项2或3.对于内部对,您可能希望在三个选项之间进行选择时使用一些启发式方法.或者你可以做一些简单的事情并使用找到的对.

步骤4:从步骤3中删除元素对,跟踪已删除的对.

步骤5:重复步骤2到4,直到极值数据集中只剩下三个元素(范围的极值加上局部最大值,希望是全局最大值).

最后删除的最小值是你想要的.

还有很多其他的聚类算法.我提出的那个相当粗糙,显然不是特别快.可以很好地扩展到更多数据和更高维度数据的是期望最大化算法.模拟退火(Metropolis-Hastings)也可以适应这个问题.

Answer 2

如果我正确理解，那么kmore希望根据最大间隔（直方图计数和bin距离的乘积）划分两个“峰”。如果是这样：

1. 找到所有的最大值。
2. 对于每个最大构建矩形，如图2所示。
3. 查找具有最大白色区域的矩形，它为您提供x范围以找到所需的bin 109.258