Обновлено 23.06.2009 Автор: Administrator
Бесплатная библиотека для статистически мотивированной сегментации гистограмм (поиск пиков)
Статистически мотивированная сегментация частотных гистограмм (разделение пиков) - ключ к успеху при решении самых разных задач статистики, биоинформатики, обработки изображений, data mining. Алгоритмы, выявляющие пики, относятся к области bump hunting ("охота за пиками"). При этом необходимо отличить случайные провалы и пики, вызванные флуктуациями частот от тех, где плотность вероятности действительно имеет минимум или максимум. Следует предостеречь от использования многих эвристических алгоритмов выявления пиков, которые игнорируют статистическую природу задачи. Такие алгоритмы могут успешно использоваться только для той узкой задачи, для которой они разрабатывались. Так изменение объема выборки может изменить результат. Поэтому статистическое обоснование существенно, так как обеспечивает должную устойчивость и универсальность.
Для свободного скачивания предлагается демонстрационная программа и библиотека HistSegm, решающая задачу сегментации (поиска пиков) одномерных гистограмм. Используемый алгоритм основан на выявлении значимых различий частот в соседних интервалах. Наличие пиков эквивалентно отсутствию монотонности в изменении частот, при этом число пиков определяется автоматически. Интервалы предполагаются имеющими одинаковую длину.
Библиотека и программа скомпилированы для платформы Win32. Работа с демонстрационной программой состоит из 3 этапов:
1) загрузка исходных данных, кнопка "Load". Данные должны быть представлены как текстовый файл, каждая строка является значением.
2) построение гистограммы, число интервалов указывается пользователем
3) сегментация гистограммы, кнопка "Segment histogram"
Если вы заинтересованы задачей сегментации одномерных гистограмм, то по запросу на Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript вам будет бесплатно выслано описание интерфейса библиотеки. После этого разрешается свободное использование библиотеки HistSegm для собственных программ (с указанием автора HistSegm в вашем about box).
Библиотека HistSegm представлена демонстрационной (однако полностью функциональной) версией. Тем не менее алгоритм, который автор использует в реальных приложениях является более мощным. Если вы заинтересованы в решении подобного рода задач, пишите на Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript .
Сегментирование гистограмм в различной форме часто встречается при решении практических задач. Приведем два общеупотребительных примера.
Разбиение гистограммы сигнала в программе HistSegmDemo:
Сегментация одномерного сигнала на основе гистограммы:
Исходное изображение сегментоядерного нейтрофила.
Сегментация гистограммы зеленого канала в программе HistSegmDemo
Итоговая сегментация изображения:
1.Очень важно, чтобы границы интервалов были "правильно" (естественно) выбраны.
В следующей версии предполагается дать возможность работы с самими исходными данными. Это важно, так как субъективность при выборе границ интервалов, может породить ложные кластеры и скрыть истинные!
2.Количество точек внутри интервалов может выражаться любым неотрицательным вещественным числом.
3.Количество интервалов с ненулевыми частотами не должно быть слишком большим, чтобы вероятность обнаружения ложных пиков была пренебрежимо малой.
4. Вероятность ошибки первого рода - появления ложных разделений (выявление ложной не монотонности в изменении частот, а, следовательно, пиков) зависит от числа интервалов. Из всех монотонных плотностей наиболее неблагоприятной является постоянная плотность (равномерное распределение). При N<=20 вероятность появления ложных пиков пренебрежимо мала: <0.01.
5. Ввести величину ошибки второго рода без количественной характеристики альтернативной гипотезы невозможно. При N<=20 предлагаемый алгоритм "консервативен" - он скорее не обнаружит существующие пики, чем выявит ложные.
1.Если числовые значения признака, отвечающие разным кластерам, существенно перекрываются, то пики могут не разделиться (вместо этого на них появляются "плечи"). Выявление этих более тонких особенностей производится в следующей версии, в которой учитывается выпуклость гистограммы частот (оценка второй производной).
2.Так как гистограммы могут быть весьма разнообразны по своей форме, то для устойчивой их сегментации необходим целый набор разных критериев (алгоритмов для выявления пиков).
| < Предыдущая | Следующая > |
|---|
