Задания для спецпрактикума "Анализ временных рядов" | Лабораторная работа No.5 | Главная К52 |
Теоретические сведения к лабораторной работе No. 5
практикума "Анализ временных рядов": Меры сложности. Расчет энтропии источника.
Энтропия источника
К настоящему времени в научной литературе предложен целый ряд различных энтропий. Среди них энтропия источника является одной из наиболее известных и общепринятых характеристик сложности символьных последовательностей. Прежде чем давать ее определение, рассмотрим некоторые предварительные сведения. Исторически понятие энтропии было введено Больцманом в термодинамике. В 40-х годах 20-го века концепция Больцмана была обобщена Шенноном на случай символьных последовательностей для того, чтобы иметь возможность охарактеризовать последовательность символов с точки зрения ее упорядоченности.
Предположим, что мы рассматриваем символьную последовательность,
составленную из алфавита, содержащего
Следовательно, формула для ![]()
Если символы не являются равновероятными, то необходимо провести усреднение
по всем возможным ![]() Обычно логарифмы берутся по основанию ![]() Что может сообщить энтропия о последовательности символов? Здесь нужно обратить внимание на одно обстоятельство. Меры сложности (и, в частности, энтропия) широко применяются при анализе структуры не только текстов и ''естественных'' символьных последовательностей (таких как цепочка нуклеотидов ДНК), но и временных рядов самого различного происхождения. Часто расчет энтропии проводится в целях получения количественной характеристики сложности изучаемого процесса; при этом используется символьное представление сигналов (в простейшем случае сигнал преобразуется в бинарный код). Например, если наблюдаемая переменная в данный момент времени принимает значение больше среднего, то в качестве очередного символа бинарного кода выбирается ``1'', если меньше среднего - ``0'' и т.п. Анализ последовательностей символов вместо временного ряда осуществляется в рамках так называемой символьной динамики. В данной работе для простоты мы ограничимся только рассмотрением случая бинарных кодов.
Итак, пусть анализируется последовательность из ``0'' и ``1''; вероятности
данных символов соответственно равны
Однако, рассматриваемое определение энтропии дает не так уж много полезной
информации. Например, принципиально различные процессы могут иметь одно и то
же значение энтропии. Рассмотрим две последовательности:
![]() и ![]() Если в обоих случаях ![]() ![]() ![]() ![]()
Данный недостаток можно устранить, если вычислять блочные энтропии
(или энтропии высокого порядка). Рассмотрим вначале вероятности встретить
различные блоки из 2-х символов: ``00'', ``01'', ``10'', ``11''. Если мы будем
анализировать вероятности данных блоков для последовательностей ![]() которая определяет среднее количество информации, содержащееся в блоке из ![]() ![]() ![]() ![]()
Если энтропии отдельных символов не позволяют получать много информации об
особенностях анализируемых последовательностей, то блочные
энтропии
Символьные последовательности, несущие какую-либо полезную информацию, должны
находиться между случаем полной неупорядоченности и периодическими
последовательностями. Для них приращения ![]() Их можно интерпретировать как среднюю неопределенность о символе, если известны ![]() ![]() ![]() называется энтропией источника. ![]() ![]() ![]() ![]()
При практических вычислениях блочных энтропий и энтропии источника нужно
обращать внимание на возможность достоверной оценки вероятностей различных
блоков. На практике их определяют как относительную частоту появления того
или иного блока:
![]() где ![]() ![]() ![]() ![]() ![]() ![]()
Энтропию источника иногда определяют другим способом (без расчета
блочных энтропий). В качестве примера рассмотрим определение сложности
Лемпеля-Зива. Идея предложенного ими алгоритма состоит в следующем.
Последовательность символов разбивается на фрагменты, и метками отмечаются
фрагменты, которые ранее еще не были идентифицированы. Например, пусть есть
последовательность ![]() Для не совсем случайных последовательностей ![]() где ![]() ![]() ![]() ![]() Возможность разбить последовательность символов на участки по определенным правилам имеет важное значение в задачах сжатия данных. Одним из потенциальных приложений задач об исследовании мер сложности является создание алгоритмов оптимального архивирования данных. В частности, подход Лемпеля-Зива реализован в известной программе ``gzip''.
|