在特定图形中寻找局部最小值

Question

手头的问题看起来很简单，但我迄今为止还没有找到一个简单的解决方案。

我有一个描述浮点数数组值分布的直方图，大致如下：

如您所见，0附近有一个局部最大值，它不断下降到局部最小值，然后迅速上升到一个高原，最后下降到0。我想检测局部最小值。

在实践中，直方图并不那么平滑：

有许多尖峰，局部最小值可能会被拉伸和不均匀。我不确定如何解决这个问题。

几乎没有领域知识。第一个最大值甚至可能高于第二个最大值。任何方向都可能出现尖峰，值可能低至0。

这是从8个不同运行中取样的真实样本。它被缩放到0-10以便更容易理解。

0: 22%  12% 19% 17% 6%  5%  6%  5%    
1: 3%   2%  1%  1%  4%  1%  4%  1%    
2: 6%   2%  13% 5%  0%  2%  0%  2%   
3: 62%  62% 52% 42% 2%  5%  2%  5%  
4: 4%   19% 12% 28% 10% 13% 10% 13%  
5: 0%   0%      3%  29% 30% 29% 30%
6:                  37% 31% 37% 30%
7:                  1%  7%  1%  7%
8:                  6%  1%  6%  1%
9:
10:

数值向下取整。缺失的数值表示没有出现任何数值。

第一行的解释：

0: 22%   the initial max
1: 3%    local min
2: 6%    still min
3: 62%   plateau max
4: 4%    second min
5: 0%    0
6:   no more values 
7:      
8:      
9:
10:

供参考，这是一份相同数据的列表，但此次将其缩放到0-100（90-100范围内没有任何值）。我在格式上搞砸了，但它应该能给你一个大致的想法。

0:  0%   0%   0%   1%   0%   0%   0%   0%
1:  0%   1%   1%   3%   0%   0%   0%   0%
2:  1%   2%   1%   3%   0%   0%   0%   0%
3:  4%   2%   3%   3%   0%   1%   0%   1%
4:  6%   1%   3%   2%   0%   0%   0%   0%
5:  2%   0%   3%   1%   0%   0%   0%   0%
6:  1%   0%   2%   0%   0%   0%   0%   0%
7:  1%   0%   1%   0%   0%   0%   0%   0%
8:  1%   0%   1%   0%   0%   0%   0%   0%
9:  1%   0%   1%   0%   1%   0%   1%   0%
10: 1%   0%   0%   0%   1%   0%   1%   0%
11: 0%   0%   0%   0%   0%   0%   0%   0%
12: 0%   0%   0%   0%   0%   0%   0%   0%
13: 0%   0%   0%   0%   0%   0%   0%   0%
14: 0%   0%   0%   0%   0%   0%   0%   0%
15: 0%   0%   0%   0%   0%   0%   0%   0%
16: 0%   0%   0%   0%   0%   0%   0%   0%
17: 0%   0%   0%   0%   0%   0%   0%   0%
18: 0%   0%   0%   0%   0%   0%   0%   0%
19: 0%   0%   0%   0%   0%   0%   0%   0%
20: 0%   0%   0%   0%   0%   0%   0%   0%
21: 0%   0%   0%   0%   0%   0%   0%   0%
22: 0%   0%   0%   0%   0%   0%   0%   0%
23: 0%   0%   0%   0%   0%   0%   0%   0%
24: 0%   0%   1%   0%   0%   0%   0%   0%
25: 0%   0%   1%   0%   0%   0%   0%   0%
26: 0%   0%   1%   0%   0%   0%   0%   0%
27: 0%   0%   1%   0%   0%   0%   0%   0%
28: 1%   0%   2%   1%   0%   0%   0%   0%
29: 3%   0%   2%   2%   0%   0%   0%   0%
30: 7%   1%   3%   2%   0%   0%   0%   0%
31: 10%  2%   4%   3%   0%   0%   0%   0%
32: 10%  3%   4%   4%   0%   0%   0%   0%
33: 6%   6%   5%   5%   0%   0%   0%   0%
34: 5%   5%   4%   4%   0%   0%   0%   0%
35: 5%   8%   6%   3%   0%   0%   0%   0%
36: 5%   10%  6%   4%   0%   0%   0%   0%
37: 5%   9%   5%   3%   0%   0%   0%   0%
38: 3%   8%   5%   5%   0%   0%   0%   0%
39: 2%   5%   5%   5%   0%   0%   0%   0%
40: 1%   4%   4%   5%   0%   1%   0%   1%
41: 1%   3%   2%   5%   0%   1%   0%   1%
42: 0%   1%   1%   4%   0%   0%   0%   0%
43: 0%   2%   0%   4%   1%   1%   1%   1%
44: 0%   1%   0%   3%   1%   1%   1%   1%
45: 0%   1%   0%   1%   0%   1%   0%   1%
46: 0%   1%   0%   1%   1%   1%   1%   1%
47: 0%   1%   0%   0%   1%   1%   1%   1%
48: 0%   1%   0%   0%   1%   1%   1%   1%
50: 0%   0%   0%   1%   1%   1%   1%   1%
50:      0%        1%   1%   1%   1%   1%
51:      0%        0%   2%   1%   2%   1%
52:      0%        1%   2%   1%   2%   1%
53:      0%        0%   4%   2%   4%   2%
54:                0%   2%   2%   2%   2%
55:                0%   2%   2%   2%   2%
56:                0%   2%   3%   2%   3%
57:                0%   2%   4%   2%   4%
58:                     4%   6%   4%   6%
59:                     3%   3%   3%   3%
60:                     5%   5%   5%   5%
61:                     5%   7%   5%   7%
62:                     3%   5%   3%   5%
63:                     4%   3%   4%   3%
64:                     5%   2%   5%   2%
65:                     3%   2%   2%   2%
66:                     5%   1%   5%   1%
67:                     1%   0%   1%   0%
68:                     1%   0%   1%   0%
69:                     0%   1%   0%   1%
70:                     0%   0%   0%   0%
71:                     0%   0%   0%   0%
72:                     0%   0%   0%   0%
73:                     0%   1%   0%   1%
74:                     0%   0%   0%   0%
75:                     0%   0%   0%   0%
76:                     0%   1%   0%   1%
77:                     0%   0%   0%   0%
78:                     0%   0%   0%   0%
79:                     0%   0%   0%   0%
80:                     0%   0%   0%   1%
81:                     0%   0%   0%   0%
82:                     0%   0%   0%   0%
83:                     0%   0%   0%   0%
84:                     0%   0%   0%   0%
85:                     1%        1%
86:                     0%        0%
87:                     1%        1%
88:                     1%        1%
89:                     0%        0%

- mafu

---

问题在于，你不是在寻找“本地最小值”，而是在寻找“特定的”本地最小值...第二个最低点。你的第二个例子有很多局部最小值。局部最小值只是图形中周围所有值都比它高的凹陷处。因此，你需要更好地定义你实际上想要完成的任务……是什么使这个特定的凹陷成为一个局部最小值，而不是其他任何凹陷？你对局部最小值的接受标准是什么？ - Mark Peters

@mafutrct：直方图中有多少个点，它们是如何存储的？ - NPE

你可能想使用样条逼近来平滑图形（请参见链接），然后寻找局部最小值。请注意，这有时可能会失败，但我认为这是一个很好的启发式方法。http://en.wikipedia.org/wiki/Spline_%28mathematics%29 - amit

没有更多的领域知识很难提供建议。你尝试过平滑处理（例如移动平均）或曲线拟合吗？两个最大面积之间的x距离是否一致（达到数量级）？ - Ergwun

我会尝试创建一些真实的样例并在这里发布。 - mafu

Answer 1

你的“真实”直方图是低频的。你的噪音是高频的。使用适当带宽的低通滤波器过滤数据将消除大部分噪音。

- Jim Clay

Answer 2

这是一个算法：

1. 通过计算小窗口的移动平均值来平滑数据集。
2. 测试平滑后的数据是否存在局部极小值（即任何单个数据点都比其邻居小）。
3. 如果局部极小值超过两个，则增加窗口大小并返回步骤1。

更新：

经过查看您发布的示例数据，我意识到您需要检测最小高原而不仅仅是单个点，因此算法中的第二步应进行调整，以便在最近的更高值邻居之间没有较小值的情况下将点识别为最小值。然后，在步骤3中计数最小值时，最小高原应视为单个最小值。

我已在您的示例数据集上测试了此算法，并且表现良好，分别选择以下最小值：18、12、15、13、23、20、23和20。

- Ergwun

---

一个移动平均值可以比较快地消除低的局部极小值，在高峰（因此不太有趣）之前。想象一下，有一个深的局部极小值被高峰锐利地包围，和一个非常微妙的极小值被非常缓慢、温和的上升斜坡所包围。微妙的一个将会“胜出”。 - Mark Peters

@马克：那不正是重点吗？这个所谓的感兴趣的最低值被高峰包围，根本不是一个真正的最低值，它只是噪音。如果它是一个真正的低谷，就不会有那些尖峰了。这有点像寻找山谷底部：如果你在斜坡中途停在深井处，那么你就是错的。 - Tom Anderson

@Tom：这有可能是真的，也有可能不是。虽然这个算法有着极其重要的意义，但它会被一个很浅但是非常广泛的“其他”局部最小值所击败。 - Mark Peters

移动平均线是一种低通滤波器，但它们并不是非常好的低通滤波器。 - Jim Clay

@Mark Peters：我是在考虑期望信号的算法，其中感兴趣的极小值将是数据集中唯一的“宽谷”。 - Ergwun

@Jim Clay：对于所描述的数据集来说，可能已经足够好了，并且非常容易解释。 - Ergwun

Answer 3

一种可能的启发式方法：使用样条逼近来平滑直方图，并使其类似于多项式，然后寻找局部最小值。 请注意，这只是一种启发式解决方案，可能会失败...但我认为对大多数情况都提供了一个很好的解决方案。

- amit

Answer 4

这实际上听起来更像是基于直方图的图像分割（尽管这不是一张图片，所以它实际上只是直方图分割）。听起来很奇怪，但请耐心看下去。

最小值的重要性在于它是一个最小值，还是它将小最大值与大最大值分开？如果它是将极值分开的事实，那么分割肯定是您想要的。

查看K-means聚类。您将有两个簇。这不是一个特别复杂的过程，但维基百科（和其他来源）更好地解释了它，所以我会留给他们。

- Tom Anderson

---

数据实际上来自于一张图片（尽管中间有很多东西）。思考一下，主要目标可能是分离这两个极大值点。我将会查看 WP。 - mafu

还有其他也许更好的分割算法，但我只记得k-means（以及模糊c-means，这不是你想要的）。还有一个非常好的算法是由一个日本人发明的，但他的名字我完全想不起来了。很抱歉我没能提供更多帮助。 - Tom Anderson