Оптимальное дерево вейвлета пакетный анализ
T = besttree(
T
)
[T,E] = besttree(T
)
[T,E,N] = besttree(T
)
besttree
является одно- или двумерной функцией вейвлета анализа пакетов, которая вычисляет оптимальное поддерево начального дерева относительно критерия типа энтропии. Получившееся дерево может быть намного меньше начального.
После организации библиотеки вейвлет-пакетов естественно считать декомпозиции, выданные из данного ортогонального вейвлета.
Сигнал длины N = 2L может быть расширен α различными способами, где α - количество двоичных подтревов полного двоичного дерева глубин L.
В результате можно сделать вывод, что α ≥ 2N/2 (для получения дополнительной информации см. книгу Mallat's, приведенную в ссылки на странице 323).
Это число может быть очень большим, и поскольку явное перечисление в целом неразрешимо, интересно найти оптимальное разложение относительно удобного критерия, вычисляемого эффективным алгоритмом. Мы ищем минимум критерия.
T = besttree(
вычисляет лучшее дерево T
)T
соответствует лучшему значению энтропии.
[T,E] = besttree(
вычисляет лучшее дерево T
)T
и, в сложение, лучшее значение энтропии E
.
Оптимальная энтропия узла, чей индекс j-1
, есть E(j)
.
[T,E,N] = besttree(
вычисляет лучшее дерево T
)T
, лучшее значение энтропии E
и, в сложение, вектор N
содержит индексы объединенных узлов.
Рассмотрим одномерный случай. Начиная с корневого узла, лучшее дерево вычисляется с помощью следующей схемы. Узел N разделяется на два узла N1 и N2 тогда и только тогда, когда сумма энтропии N1 и N2 ниже энтропии N. Это локальный критерий, основанный только на информации, доступной в узле N.
Можно использовать несколько критериев типа энтропии (см. wenergy
для получения дополнительной информации. Если функция энтропии является аддитивной функцией вдоль коэффициентов вейвлет, этот алгоритм приводит к лучшему дереву.
Начиная с начального дерева T и используя сторону слияния этого алгоритма, мы получаем лучшее дерево среди всех двоичных поддеревьев T.
Койфман, Р.Р.; М. В. Викерхаузер (1992), «Основанные на энтропии алгоритмы для наилучшего выбора базиса», IEEE Trans. on Inf. Теория, т. 38, 2, с. 713-718.
Mallat, S. (1998), Wavelet tour of signal processing, Academic Press.