Найти локальный минимум в специальном графе

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%

Answer 1

Ваша "истинная" гистограмма имеет низкую частоту.Ваш шум высокочастотный.Низкочастотная фильтрация данных с использованием соответствующего фильтра пропускной способности избавит от большей части шума.

Answer 2

Вот алгоритм:

1. Сглаживание набора данных путем расчета скользящего среднего для небольшого окна.
2. Проверка сглаженных данных на локальные минимумы (т. Е. На любые единичные данные, которые онименьше, чем его соседи.
3. Если существует более двух локальных минимумов, увеличьте размер окна и перейдите к шагу 1.

Обновление:

Изучив образцы данных, которые вы разместили, я понял, что вам нужно обнаруживать минимальные плато, а не только отдельные точки, поэтому второй шаг в алгоритме должен быть настроен для определения точки как части минимума, если естьнет соседей с меньшими значениями между ближайшими соседями с более высокими значениями с обеих сторон. Тогда при подсчете минимумов на шаге 3 минимальное плато должно учитываться как один минимум.

Я протестировал этот алгоритм на ваших примерах наборов данныхи он работает хорошо, выбирая минимумы в: 18, 12, 15, 13, 23, 20, 23 и 20 для ваших наборов данных соответственно.

Answer 3

Для меня это звучит скорее как сегментация изображения на основе гистограммы (хотя это не изображение, так что на самом деле это просто сегментация гистограммы). Звучит странно, но терпите меня.

Что важного в минимуме - тот факт, что это минимум или что он отделяет маленький максимум от большого максимума? Если это тот факт, что он разделяет максимумы, то сегментация определенно то, что вы хотите.

Взгляните на K-средних кластеров . У тебя будет два кластера. Это не очень сложная процедура, но Википедия (и другие источники) гораздо лучше объясняет ее, чем могла бы, поэтому я оставлю ее им.

Answer 4

возможная эвристика: использование аппроксимации сплайн для сглаживания гистограммы, ее полиномиального типа и последующего поиска локального минимума.
обратите внимание, что это только эвристическое решение, которое может дать сбой ... но я думаю, что оно подойдет для большинства случаев.