Первичная обработка сигналов вейвлетами на примере подготовки данных к классификации и кластеризации | Статья в журнале «Молодой ученый»

Автор:

Рубрика: Информатика

Опубликовано в Молодой учёный №5 (5) май 2009 г.

Статья просмотрена: 144 раза

Библиографическое описание:

Прыткова Н. М. Первичная обработка сигналов вейвлетами на примере подготовки данных к классификации и кластеризации // Молодой ученый. — 2009. — №5. — С. 8-9. — URL https://moluch.ru/archive/5/402/ (дата обращения: 16.07.2018).

Вся информация, получаемая нами из внешнего мира, проходит определённые стадии обработки, главной из которой является анализ. Для подготовки сигнала к анализу необходимо применить первичную обработку для того, чтобы сделать возможным использование стандартных алгоритмов анализа. Часто первичная обработка может занимать большее количество времени, чем анализ. Например, для решения финансовых задач более 90% вычислительного времени уходит на первичную обработку [8].

Первичную обработку определяют как преобразование входного сигнала в форму, пригодную для подачи на вход стандартному алгоритму. Целью предварительной обработки могут быть уменьшение размерности или сложности задачи [8]. Рассмотрим предварительную обработку сигнала при помощи вейвлетов. Вейвлеты в таком применении помогают решить ряд задач, к примеру, сжатие данных [2], выявление особенностей [7], моделирование [9], удаление зашумлённости. Среди приложений, использующих первичную обработку вейвлетами есть сигнализаторы пожара [8], выявление особенностей сейсмических волн [1], компрессия данных [4], обработка данных ЭКГ [5], распознавание клеток крови [3] и др. Как правило, первичная обработка вейвлетами позволяет произвести выбор некоторого числа значащих вейвлетных коэффициентов, к которым в дальнейшем применяются стандартные методы обработки.

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

Существует большое количество стандартных алгоритмов классификации и кластеризации. Но точность и скорость вычисления зависит не только от самого алгоритма, но и от данных. Как уже говорилось, вейвлет-анализ помогает уменьшить размерность задачи. Но кроме уменьшения размера входных данных, вейвлет-анализ помогает выявить ещё и особенности сигнала. Для этих задач используется алгоритм выбора наилучшего базиса [6].

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

Начиная с предпоследнего уровня:

1. Подсчитаем значение стоимостной функции узла (F)

2. Сравниваем F данного узла с суммой стоимостных функций дочерних узлов (F и F)

3. Если F < F + F, то F включается в число выбранных узлов (при этом всё поддерево под этим узлом исключается из списка выбранных)

4. Иначе F = F + F

Как видно из алгоритма, на выходе мы получим непересекающиеся множетсва узлов, которые полностью покрывают полученное пространство разложения.

Возникает два вопроса: какую именно функцию выбрать в качестве стоимостной и каким образом этот алгоритм адаптировать к задаче классификации и кластеризации.

В примере, рассмотренном ниже, была использована функция  , где   - это вейвлет-коэффициент, а. Стоимостная функция всего узла, таким образом, будет равна . Проведём вейвлет-преобразование входного сигнала X = {2, -10, 5, 0, 4, 16, 7, -2}. Дерево декомпозиции выглядит следующим образом:

img1

Используя предложенную характеристическую функцию, были отобраны узлы {(1,0), (2,2), (2,3)}.

Теперь обратимся к вопросу адаптации этого алгоритма к задачам классификации и кластеризации. В [7] было предложено в качестве стоимостной функции применить расстояние Кульбака-Лейблера. На самом деле, получая очередной образец, мы стремимся увеличить расстояние между классами, что позволит точнее соотнести входной сигнал с классом.

Итак, сначала зададим сигнал, принадлежащий классу А. Тогда энергию этого класса можно получить по формуле  . А расстояние Кульбака-Лейблера мы вычислим по формуле  .

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

 

Литература:

1.      Астафьева Н.М. Вейвлет-анализ: основы теории и примеры применения // Успехи физических наук. 1996, том 166, №11. с. 1145-1170.

2.      Воробьев В.И., Грибунин В.Г. Теория и практика вейвлет-преобразования. ВУС, 1999.

3.      Дремин И.М., Иванов О.В., Нечитайло В.А. Вейвлеты и их использование // Успехи физических наук. 2001, том 171, №5. с. 465-501.

4.      Стояновский С.Ю. Сжатие речевых сигналов с использованием ортогональных и биортогональных вейвлет-функций // Світ інформації та телекомунікацій - 2005. Матеріали ІІ міжнародної науково-технічної конференції студенства та молоді. Київ 2005, 174 с.

5.      Шитов А.Б. Разработка численных методов и программ, связанных с применением вейвлет-анализа для моделирования и обработки экспериментальных данных // диссертация на соискание учёной степени кандидата физико-математических наук. Ивановский Государственный университет. Иваново, 2001.

6.      Percival, Donald B. Wavelet methods for time series analysis / Donald B. Percival and Andrew T. Walden Cambridge University Press 2000.

7.      Saito Naoki Local Feature Extraction and Its Application Using a Library of Bases // a Dissertation Present to the Faculty of the Graduate School of Yale University in Candidacy for the Degree of Doctor of Philosophy. 1994.

8.      Thuillard, Mark Wavelets in Soft Computing. World Scientific Series in Robotics and Intelligent Systems – Vol. 25. World Scientific Publishing Co. Ptl. Ltd. 2001.

9.                  Urban, Karsten Wavelets in numerical simulation: problem adapted construction and application. Springer-Verlag Berlin Heidelberg 2002. (Lecture notes in computational science and engineering; Vol. 22).

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


Похожие статьи

Кластерный анализ разработки современных алгоритмов...

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

Метод k средних при решении задачи распознавания диктора по...

Рис. 1.Результат кластеризации алгоритмом k-means (k=3). Метод k-means хорошо работает, когда кластеры

Аграновский А. В., Леднов Д. А. Теоретические аспекты алгоритмов обработки и классификации речевых сигналов Москва: Изд-во «Радио и связь», 2004.

Применение методов кластеризации для обработки новостного...

Целью алгоритмов кластеризации является создание классов, которые максимально связаны внутри себя, но различны друг от друга.

В этом состоит главное отличие кластеризации данных от другой задачиклассификации

Задана функция расстояния между объектами .

Кластер как одна из форм познавательной деятельности...

В своих работах известный экономист ХIХ века Альфред Маршал писал, что значительную роль в кластеризации играют ассоциации

 В составе малой группы с последующим конкурсом на лучший кластер, составленный по заданному преподавателем главному термину.

Метод естественной кластеризации данных | Статья в журнале...

Методы решения задачи кластеризации и прогнозирования в электронном архиве. Первичная обработка сигналов вейвлетами на примере подготовки данных к классификации и кластеризации.

Оценка рисков информационной безопасности с помощью метода...

Основной процесс K-means кластеризации — это отображение заданного набора векторов в улучшенных через разделение точек данных.

За функцию определения расстояния принимается евклидова функция.

Анализ эффективности применения аппаратных устройств...

По сути, МК — однокристальный компьютер, способный выполнять только простые задачи.

– Firm ядра — то же самое, что и Soft ядра, но с полностью или частично выполненной разводкой линий

Но функции Hard ядра строго определены, что снижает универсальность схемы.

Использование матриц комбинаторного типа для построения...

В результате сбора и первичной обработки данных формируются описания объектов или явлений.

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

Будем формулировать задачу кластеризации таким образом, чтобы...

Поэтапный процесс кластерного анализа данных на основе...

Рассмотрим задачу кластеризации данных. Имеется выборка и функция, отображающая расстояние между объектами Алгоритм

Рассмотрим один из самых популярных и широко используемых методов кластерного анализа — алгоритм k–means (k–средних).

Обсуждение

Социальные комментарии Cackle

Похожие статьи

Кластерный анализ разработки современных алгоритмов...

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

Метод k средних при решении задачи распознавания диктора по...

Рис. 1.Результат кластеризации алгоритмом k-means (k=3). Метод k-means хорошо работает, когда кластеры

Аграновский А. В., Леднов Д. А. Теоретические аспекты алгоритмов обработки и классификации речевых сигналов Москва: Изд-во «Радио и связь», 2004.

Применение методов кластеризации для обработки новостного...

Целью алгоритмов кластеризации является создание классов, которые максимально связаны внутри себя, но различны друг от друга.

В этом состоит главное отличие кластеризации данных от другой задачиклассификации

Задана функция расстояния между объектами .

Кластер как одна из форм познавательной деятельности...

В своих работах известный экономист ХIХ века Альфред Маршал писал, что значительную роль в кластеризации играют ассоциации

 В составе малой группы с последующим конкурсом на лучший кластер, составленный по заданному преподавателем главному термину.

Метод естественной кластеризации данных | Статья в журнале...

Методы решения задачи кластеризации и прогнозирования в электронном архиве. Первичная обработка сигналов вейвлетами на примере подготовки данных к классификации и кластеризации.

Оценка рисков информационной безопасности с помощью метода...

Основной процесс K-means кластеризации — это отображение заданного набора векторов в улучшенных через разделение точек данных.

За функцию определения расстояния принимается евклидова функция.

Анализ эффективности применения аппаратных устройств...

По сути, МК — однокристальный компьютер, способный выполнять только простые задачи.

– Firm ядра — то же самое, что и Soft ядра, но с полностью или частично выполненной разводкой линий

Но функции Hard ядра строго определены, что снижает универсальность схемы.

Использование матриц комбинаторного типа для построения...

В результате сбора и первичной обработки данных формируются описания объектов или явлений.

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

Будем формулировать задачу кластеризации таким образом, чтобы...

Поэтапный процесс кластерного анализа данных на основе...

Рассмотрим задачу кластеризации данных. Имеется выборка и функция, отображающая расстояние между объектами Алгоритм

Рассмотрим один из самых популярных и широко используемых методов кластерного анализа — алгоритм k–means (k–средних).

Задать вопрос