Сравнение массивов
дискретных данных на основе сжатия информации
Тверетин Алексей Александрович,
соискатель Самарского
государственного технического университета,
заместитель директора по
внедрению ООО «Системы управления бизнесом».
Введение и постановка задачи
В последнее время
широкое распространение получили системы так называемого интеллектуального
анализа (business intelligence). Как правило,
объектом анализа таких систем являются базы данных систем, накапливающих информацию
о неких общественных или экономических процессах. Примером таких дискретных
данных являются показатели бюджета, которые представляют собой
последовательность дельта-функций, показывающих
значение того или иного разреза бюджета во времени. Различные варианты таких
последовательностей можно наблюдать также в ERP (enterprise resource planning, корпоративное
планирование ресурсов) [3],
CRM (customer relationship management system,
система управления взаимодействием с клиентами) [2] и многих подобных им
системах.
Большинство методов анализа дискретных данных
сформировались в ходе решения задач, связанных с системами передачи данных и
представляют такие данные в виде дискретных сигналов. Технически, методы
преобразования и фильтрации таких данных реализованы в виде
программно-аппаратных систем, которые обычно совмещают в себе устройства
регистрации и обработки данных с помощью узкого набора алгоритмов. Данные
систем более сложной организации принципиально не могут иметь такую структуру,
так как непосредственно регистрация данных в таких системах возложена на
человека, кроме того, структура данных принципиально отличается из-за
неэргодичности сигнала.
В частности, актуальна задача сравнения
дискретных массивов данных, например при план-фактном анализе исполнения
бюджета [4], с целью определения наиболее близкого планового варианта по фактическим
показателям. Сложность такого сравнения состоит в том, что массивы могут быть
сдвинуты друг относительно друга на небольшое количество отсчетов, что делает
трудным использование корреляционного анализа. Очевидно, что в этом случае
перспективным видится применение спектрального анализа. Переход в частотную
область дает множество преимуществ для анализа. Но
данный подход имеет ряд недостатков, а именно отсутствие в явном виде
структурной информации о сигнале, а так же, выбор гармоник, что нежелательно,
так как может теряться важная информация при резких всплесках значений данных
[1].
Очевидно, что актуальным видится разработка
алгоритма сжатия информации, который позволит сравнивать лишь ограниченное число
признаков массивов данных, и при этом, иметь высокую эффективность с учетом
вышеприведенных особенностей данных.
Marvel, DC на русском языке. В наличии и под заказ erokomiksi.com
Разработка алгоритма
Данные о процессах, протекающих в системах,
можно представить как сигнал 
. Причем, такой сигнал является случайным, то есть каждый
отсчет принимает некоторые
значения с определенной вероятностью. Сигнал является данными о случайном
процессе, и получаемая последовательность отсчетов будет зависеть от конкретной
реализации случайного процесса. Реализация такого сигнала может быть записана
как 
, где 
- амплитуда, 
- частота, 
- случайная начальная фаза, кратная дискретности отсчетов.
Нужно отметить, что использования времени 
весьма условно, и
вместо него могут использоваться другие характеристики сигнала, например
пространственные характеристики. Кроме того, такие сигналы являются финитными.
Важным свойством сигналов является то, что сигнал изначально имеет цифровой
характер, то есть он квантован по частоте и по уровню. Основной сложностью при
анализе таких данных является характер этой зависимости.
Для
решения поставленных задач предложено использовать базисную комплексную систему
импульсных функций, которая определяется на множестве 
, и имеет вид 
, где 
- номер гармоники
анализируемого сигнала. Функции 
и 
определяются как: 
для нулевой гармоники 
. В случае, если 
и изменяется от 0 до 
с
шагом 
, функции можно записать как: 
, 
, где 
.
При
практической реализации алгоритма, предложено вместо вычисления тригонометрических
функций синуса и косинуса использовать матрицу заранее вычисленных значений.
Для выражения 
такая матрица записывается
как:
,
Для
выражения 
матрица записывается
как:
.
Таким
образом, импульсные функции запишутся как: 
, 
.
Реализация данного подхода позволяет
отказаться от вычисления значений тригонометрических функций, что значительно
ускоряет процедуру вычисления. Для каждой гармоники множество 
делится на 
интервалов,
в каждом из которых происходит сдвиг импульсных функций на 
подинтервалов.
Сдвигаемые импульсные функции формируются на основе вспомогательных функций и , их можно записать как: 
и 
. Количество сдвигов можно определить как 
, где 
- позиция первого
подинтервала, с которого начинается сдвиг.
Формирование
амплитудно-частотного спектра анализируемого сигнала 
осуществляется
в соответствии с выражением 
, где 
. Выражение 
представляет собой
суперпозицию значений: 
, где: 
, 
, 
- значение анализируемого сигнала в точке 
, где 
. То есть, на каждой гармонике спектр представляет собой суперпозицию
значений сигнала умноженного на значения опорных импульсных функций, которые
подвергаются сдвигу на значение подинтервалов внутри
каждого интервала. С учетом произведенных изменений спектр запишем как:
.
Выводы
Разработанный алгоритм сжатия имеет трудоемкость,
близкую к 
, что соответствует быстрому преобразованию Фурье. Кроме
этого, спектр позволяет осуществлять
сжатие массива дискретных данных в 
раз, так же он
инвариантен к сдвигам сигнала и зависит от малейшего изменения сигнала, что
позволяет хорошо фиксировать его структуру. Данные преимущества создают
предпосылки для создания методики сравнения массивов дискретных данных с
высоким быстродействием.
Литература
1.
Гольденберг Л.М., Матюшкин Б.Д., Поляк
М.Н. Цифровая обработка сигналов: Учеб. Пособие для вузов. - М.: Радио и связь,
1990. – С.123-143.
2.
Елашкин М.
SAP Business One. Строим эффективный бизнес. – М.: КУДИЦ-ПРЕСС,
2007. – С.105-109.
3.
Рыбников А.И. Система управления
предприятием типа ERP.
– М.: Азроконсалт, 1999. – 214 с.
4.
Теплова Т.В.
Планирование в финансовом менеджменте. - М.: ГУ ВШЭ, 1998. – С.85 - 91.
Поступила в редакцию 09.07.2010 г.