Определение локальных минимумов в гистограмме

Мне интересно найти локальные минимумы в гистограмме, которая примерно напоминает

Я бы хотел найти локальный минимум на уровне 109.258, и самый простой способ сделать это - определить, будет ли количество отсчетов в 109.258 ниже среднего числа отсчетов вокруг в некотором интервале (включая 109.258). Это определяет этот интервал, который является самой трудной для меня частью.

Что касается источника этих данных, то это гистограмма со 100 бункерами неравномерной ширины. Каждый бит имеет значение (показано на оси x) и количество образцов, попадающих в этот бункер (показано на оси y). То, что я пытаюсь сделать, - найти "лучшее" место для разделения гистограммы. Каждая сторона раскола распространяется по двоичному дереву как часть алгоритма классификации.

Я думаю, что мой лучший способ действий - попытаться подогнать кривую к этой гистограмме, используя что-то вроде алгоритм Левенберга-Марквардта, а затем сравнить локальные минимумы, чтобы найти "лучший". Правильная мера "наилучшего" будет включать некоторые признаки значимости этого раскола, который измеряется как разница между средними значениями в интервале слева и средним числом отсчетов в интервале справа, а затем, возможно, вес каждой разницы с количеством включенных отсчетов, чтобы получить составное измерение "лучше", если это имеет смысл.

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

Кстати, я делаю все на С++ и использую библиотеки boost и STL, поэтому в этом отношении ничего не выходит.

Любые мысли или идеи, касающиеся наилучшей практики, будут очень признательны!

Ответ 1

Если я правильно понимаю, kmore хочет разбить два "пика" на основе наибольшего разделения (произведение количества гистограмм и расстояния до бина). Если это верно:

Найти все макс.
для каждого прямоугольника max build, как на рисунке.
Найти прямоугольник с максимальной белой областью, которая дает вам диапазон x, чтобы найти желаемый бит 109.258

Ответ 2

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

Вам нужно что-то, что находит самый значительный локальный минимум. Например, какой-то алгоритм кластеризации. Вот очень простой:

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

Шаг 2: Найдите пару с наименьшей дельтой. Это будет либо локальная максимальная, либо локальная минимальная, либо пара (локальный минимальный, локальный максимум).

Шаг 3: Найдите пару элементов для удаления, один из

Пара, найденная на шаге 2
Пара, содержащая первый элемент пары из шага 2 и ее предшественника
Пара, содержащая последний элемент пары из шага 2 и ее преемник

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

Шаг 4: Удалите пару элементов с шага 3, отслеживая удаляемую пару.

Шаг 5: Повторите шаги с 2 по 4, пока в наборе экстремумов не останется всего три элемента (крайности диапазона плюс локальный максимум, надеюсь, глобальный максимум).

Последние удаленные минимумы - это то, что вы хотите.

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

Ответ 3

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

В качестве альтернативы, если пример типичен, можно начать с поиска пиков в нетрансформированных данных и искать области, где пики (относительно) широко разделены как кандидаты на сохранение хороших локальных минимумов.

Я навсегда рекомендую метод, используемый ROOT TSpectrum классы для нахождения пика.

Алгоритм underling подробно обсуждается в

M.Morhac et al.: методы устранения фона для спектров гамма-спектров многомерных совпадений. Ядерные приборы и методы в физических исследованиях 401 (1997) 113-132.
M.Morhac et al.: эффективная одно- и двумерная деконволюция золота и ее применение к разложению спектров гамма-лучей. Ядерные приборы и методы в физических исследованиях A 401 (1997) 385-408.
M.Morhac et al.: Идентификация пиков в многомерных совпадениях гамма-спектров. Ядерные приборы и методы в физике исследований A 443 (2000), 108-125.

Копии этих документов хранятся на веб-сайте ROOT и связаны в документации TSpectrum для тех, у кого нет подписки на NIM A.

Ответ 4

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

Вы слышали о методе Otsu? Это может быть больше в соответствии с тем, что вы хотите.

Здесь другая ссылка Otsu.