Электронная библиотека диссертаций и авторефератов России
dslib.net
Библиотека диссертаций
Навигация
Каталог диссертаций России
Англоязычные диссертации
Диссертации бесплатно
Предстоящие защиты
Рецензии на автореферат
Отчисления авторам
Мой кабинет
Заказы: забрать, оплатить
Мой личный счет
Мой профиль
Мой авторский профиль
Подписки на рассылки



расширенный поиск

Модели и алгоритмы автоматизации проектирования структур хранилищ данных для аналитической обработки числовых показателей Бакулева Марина Алексеевна

Модели и алгоритмы автоматизации проектирования структур хранилищ данных для аналитической обработки числовых показателей
<
Модели и алгоритмы автоматизации проектирования структур хранилищ данных для аналитической обработки числовых показателей Модели и алгоритмы автоматизации проектирования структур хранилищ данных для аналитической обработки числовых показателей Модели и алгоритмы автоматизации проектирования структур хранилищ данных для аналитической обработки числовых показателей Модели и алгоритмы автоматизации проектирования структур хранилищ данных для аналитической обработки числовых показателей Модели и алгоритмы автоматизации проектирования структур хранилищ данных для аналитической обработки числовых показателей Модели и алгоритмы автоматизации проектирования структур хранилищ данных для аналитической обработки числовых показателей Модели и алгоритмы автоматизации проектирования структур хранилищ данных для аналитической обработки числовых показателей Модели и алгоритмы автоматизации проектирования структур хранилищ данных для аналитической обработки числовых показателей Модели и алгоритмы автоматизации проектирования структур хранилищ данных для аналитической обработки числовых показателей Модели и алгоритмы автоматизации проектирования структур хранилищ данных для аналитической обработки числовых показателей Модели и алгоритмы автоматизации проектирования структур хранилищ данных для аналитической обработки числовых показателей Модели и алгоритмы автоматизации проектирования структур хранилищ данных для аналитической обработки числовых показателей
>

Диссертация - 480 руб., доставка 10 минут, круглосуточно, без выходных и праздников

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Бакулева Марина Алексеевна. Модели и алгоритмы автоматизации проектирования структур хранилищ данных для аналитической обработки числовых показателей : диссертация ... кандидата технических наук : 05.13.12 Рязань, 2007 147 с., Библиогр.: с. 124-131 РГБ ОД, 61:07-5/4771

Содержание к диссертации

Введение

1 Анализ проблемы проектирования хранилищ данных 10

1.1 Роль хранилища данных в системах поддержки принятия решений 10

1.2 Модели хранилищ данных 14

1.3 Методология проектирования хранилищ данных 23

1.4 Структура данных хранилища данных 26

1.5 Обоснование выбора инструментария для решения поставленных задач 29

2 Математическая модель структуры хранилища данных 31

2.1 Тензорная модель реляционного хранилища данных 34

2.1.1 Тензорная модель структуры реляционной базы данных ... 35

2.1.2 Тензорная модель запросов к реляционной базе данных... 3 8

2.1.3 Тензорная модель реляционного хранилища данных 42

2.1.4 Тензорная модель ROLAP 45

2.2 Тензорная модель многомерного хранилища данных 46

2.2.1 Модель операций над многомерным хранилищем данных 47

2.3 Алгоритм автоматизации проектирования хранилищ данных на основе разработанных моделей 50

3 Алгоритмы повышения производительности систем оперативного анализа на основе кратномасштабного представления данных 54

3.1 Анализ структуры реляционного хранилища данных 54

3.2 Основная идея кратномасштабного анализа 56

3.3 Обоснование выбора базиса Хаара 60

3.4 Кратномасштабное представление данных хранилища на основе вейвлет разложения в базисе Хаара 66

3.5 Агрегация данных масштабированного хранилища данных... 70

3.6 Расчет аналитических показателей 85

3.6.1 Выделение тренда 85

3.6.2 Периодичность 87

3.6.3 Кратномасштабный анализ 89

3.6.4 Ретроспективный анализ 93

4 Экспериментальная часть 101

4.1 Реализация алгоритма автоматизации 101

4.2 Реализация алгоритмов агрегации и ROLAP 109

4.3 Результаты проводимых экспериментов 115

Заключение 122

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

Введение к работе

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

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

Основу информационно-поисковых систем производственных предприятий, образовательных учреждений, муниципальных структур и коммерческих образований составляют многочисленные базы данных (БД), построенные на основе реляционной модели [17, 18, 23, 25, 26, 51]. Основной идеей реляционной модели является нормализация с целью экономии ресурсов памяти [17, 18, 21, 39]. Сложные по структуре и многообразию связей реляционные БД не отвечают требованиям производительности аналитических приложений и соответственно не могут выполнять функции информационной поддержки процедуры принятия решений.

Поэтому в современных информационных системах наиболее востребованы денормализованные БД - хранилища данных (ХД). ХД являются основным источником данных оперативно-аналитических подсистем (OLAP-систем) современных систем поддержки принятия решений (СППР).

Однако отсутствие единого математического описания исходной БД и ХД, проектируемого на ее основе, приводит к торможению процесса разработки и внедрения ХД.

В работах Р. Кимбала [68], Б. Инмона [65], М.С. Куприянова [12], Б. Маркова [30] рассматриваются методы построения ХД на основе реляционной модели. В работах А. Кэмбла [60], Д. Сел ко [39] метод построения модели основан на теории множеств. Многомерная модель данных приводится в работе Э. Франкони [60] и У. Сатлера [61]. Некоторые из перечисленных методов применяются для автоматизации формирования многомерных представлений данных.

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

Потребность оперативной обработки данных ХД (содержащих порядка 107 записей) приводит к необходимости создания специализированных аналитических решений. Для достижения приемлемого быстродействия (время ответа не более 5 секунд) необходимо разработать способ представления данных, адаптированный к условиям оперативного анализа.

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

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

7 Поэтому целями диссертационной работы являются:

  1. ускорение процесса проектирования ХД;

  2. повышение скорости аналитической обработки данных ХД. Для достижения поставленных целей необходимо решить ряд задач:

1) разработать единую математическую модель реляционной БД и ХД;

2) разработать математическую модель многомерного ХД;

  1. разработать математическую модель операций над многомерным ХД;

  2. разработать математическую модель структуры данных в ХД, отвечающую требованиям OLAP - систем по быстродействию;

  3. разработать алгоритмы, автоматизирующие процесс построения ХД на основе предложенных моделей;

  4. разработать алгоритмы OLAP на основе предложенной структуры;

  5. разработать программную систему, осуществляющую автоматизацию проектирования ХД и оперативный анализ данных реляционного ХД на основе предложенных алгоритмов.

Методы исследований. Для решения поставленных задач привлечены методы тензорной алгебры [1, 13, 15, 24, 27], кратномасштабного анализа [14, 19, 36, 37, 72], вейвлет-преобразований [34, 50, 53, 70, 71, 74, 81] и сигнатурного поиска [19,41, 48, 53].

В качестве инструментальных средств использовались: Borland Delphi 7, MySQL, PostgreSQL.

Научная новизна. В работе новыми являются следующие результаты:

  1. Предложены новые модели реляционного и многомерного ХД на основе тензорного аппарата.

  2. Разработан метод аналитической обработки данных ХД, основанный на вейвлет - преобразовании.

3. Разработан алгоритм автоматизации процесса проектирования ХД на
t основе разработанных моделей. Основным преимуществом данных алгорит
мов является снижение временных затрат на разработку ХД и автоматизация

8 рутинных операций по описанию разнообразных связей исходной БД и проецированию соответствующих отношений в ХД.

  1. Разработаны алгоритмы агрегации и анализа данных ХД. Отличие от известных заключается в использовании кратномасштабного анализа.

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

Практическая ценность. Практическая ценность полученных результатов состоит в следующем:

  1. Создан комплекс программных средств на основе разработанного алгоритма автоматизации проектирования структур ХД, позволяющий сократить сроки проектирования ХД. На основе данного комплекса в научно -производственном предприятии «Эльф 4М» (г. Рязань) произведена реконструкция системы информационного обеспечения производственной деятельности предприятия.

  2. Созданный комплекс программных средств по обработке данных ХД является инструментом, обеспечивающим высокую скорость аналитической обработки большого числа хранимых данных. Внедрение разработанного комплекса значительно повысило эффективность работы научно - производственного предприятия «Эльф 4М», масштабы производства которого охватывают 12 стран (БД содержит «500000 записей). Созданный программный комплекс предоставляет руководителю актуальную информацию о темпах производства, географии сбыта, а также векторе развития предприятия.

  3. Созданный программный комплекс используется в ООО «Торгтек» (г. Рязань) для оперативной обработки отчетной и аналитической информации.

Апробация результатов диссертации. Результаты, полученные в рамках работы над диссертацией, докладывались на 10-й Всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и образовании»,

9 Рязань, 2005 г. [6]; 2-й Международной научно-практической конференции «Информационная деятельность: проблемы науки и практики», Киев, 2005 г. [10]; 14-й Международной научно-технической конференции «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций», Рязань, 2005 г. [5]; 11-й Всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и образовании», Рязань, 2006 г. [3]; 12-й Всероссийской научно-технической конференции студентов, молодых ученых и специалистов «Новые информационные технологии в научных исследованиях и образовании», Рязань, 2007 г. [9].

Публикации. Основные результаты диссертации опубликованы в 11 работах, из них 2 работы опубликованы в изданиях, рекомендованных ВАК.

Внедрение результатов работы. Результаты, полученные в диссертационной работе, внедрены и использованы в научно - производственном предприятии «Эльф 4М» (г. Рязань), ООО «Торгтек» (г. Рязань) (приложение 3), а также представляют часть НИР (НИР № 10-06Г (РНТП 3.2.3.7637) «Разработка нормативной базы, информационного обеспечения и регламентов открытой информационно-образовательной среды для дистанционной подготовки, переподготовки и повышения квалификации специалистов в области ИЛИ (CALS) и CASE-технологий», НИР 11-06Г (РНТП 3.2.3.7652) «Интегрированная автоматизированная информационная система управления качеством образования ВУЗа»), проводимых РГРТУ.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, библиографического списка (82 источника), изложенных на 131 странице (содержит 10 таблиц, 53 рисунка), и 3 приложения. Общий объем диссертации 147 страниц.

Методология проектирования хранилищ данных

Для анализа данных важно иметь возможность отслеживать хронологию их изменений, поэтому, единожды попав в хранилище, данные уже практически не изменяются. Ввод новых данных носит эпизодический характер и производится в период низкой активности системы (например, в выходные дни). Поскольку данные меняются редко, к ХД не предъявляются жесткие требования, которые обычно предъявляются к БД: отсутствие избыточности хранения информации и приведение к третьей нормальной форме [21,39,40]. По этой причине может сложиться неверное представление, что проектировать хранилище проще, чем базы данных, предназначенные для оперативной обработки информации. На самом деле проектирование хранилища данных является весьма сложной задачей в силу следующих причин.

1. Менеджеру, принимающему решения, необходимы самые разнообразные отчеты, причем каждый раз новые. Не всегда есть возможность выделить специального сотрудника, который бы непрерывно готовил все новые и новые отчеты. Лучший выход — самому менеджеру научиться создавать отчеты. Однако, даже хорошо подготовленный пользователь, успешно справляясь с операциями поиска и сортировки, не может правильно объединять таблицы. Существуют разнообразные инструменты (например, упомянутые выше Crystal Reports, Reporting Services, Component One, Fast Report Studio), интерфейс которых достаточно прост, чтобы непрофессионалы в области информационных технологий могли готовить отчеты. Однако в этом случае конечный пользователь непосредственно обращается к структуре данных, поэтому структура данных хранилища должна быть понятна пользователям;

2. Формирование нового заранее не определенного запроса - сложная квалифицированная работа с большими временными затратами. Данные хранилищ, как правило, представляют собой результаты таких запросов. Для описания нерегламентированных запросов заполнения ХД необходимо четко представлять архитектуру исходной БД, в то время как разработчик ХД и администратор БД в общем случае не одно и тоже лицо;

3. В связи с тем, что отчет будет создавать конечный пользователь, следует упростить требования к запросам с целью исключения таких запросов, которые могли бы требовать множественных SQL-предложений как в традиционных реляционных СУБД;

4. Обработка запросов к хранилищу должна быть проведена с высокой производительностью, желательно в реальном масштабе времени. Поэтому должна быть обеспечена приемлемая скорость выполнения сложных аналитических запросов, для которых необходима последовательная обработка тысяч или миллионов записей [29].

На сегодняшний день для проектирования хранилищ данных используется размерная (Dimensional) модель [29]. Dimensional — это методология проектирования, специально предназначенная для разработки хранилищ данных. Размерное моделирование сходно с моделированием связей и сущностей для реляционной модели, но отличается от него целями [59]. Если реляционная модель ориентирована на целостность данных и эффективность их ввода, то размерная модель (Dimensional) ориентирована, прежде всего, на выполнение сложных запросов к БД [82].

В размерном моделировании принят стандарт модели — схема «звезда» (star schema) [65], которая обеспечивает высокую скорость выполнения запроса посредством денормализации и разделения данных. Схема «звезда» строится таким образом, чтобы обеспечить наивысшую производительность при выполнении либо одного, самого важного запроса, либо группы похожих запросов. Прежде чем создать базу данных со схемой типа «звезда», необходимо проанализировать бизнес-правила предметной области для выяснения центрального вопроса, ответ на который наиболее важен. Все прочие вопросы должны быть объединены вокруг основного вопроса, и моделирование должно начинаться с него. Данные, необходимые для ответа на этот вопрос, должны быть помещены в центральную таблицу модели — таблицу фактов. Таблица фактов может состоять из миллионов строк и содержать суммируемые или фактические данные. Она объединяет в себе данные, которые иначе хранились бы во многих таблицах традиционных реляционных баз данных.

Одним из недостатков методологии проектирования Dimensional является ограниченность схемой «звезда». Схема «звезда» представляет собой средство многомерного представления реляционных данных [65] и не отвечает требованиям многомерных ХД. Очевидно, что для проектирования последних размерная модель не подходит.

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

Тензорная модель структуры реляционной базы данных

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

Пусть в некоторой БД существует отношение R(Ax,A2,...,An; Вх,В2,...,Вк; С„С2,...,СШ), где Ах,Аг,...,Ап- п ключевых атрибутов отношения, атрибуты5,,В2,...,Вк определяют А: внешних ключей, C,,C2,...,Cm- т остальных атрибутов сущности, которые однозначно определяются первичными ключами. Пусть атрибут Ах принимает / значений ап,ап,...,аи, атрибут А2 -/значений а2Х,а22,...,а21, Ап -/значений ani,an2,...,anl. Аналогично для атрибутов Bl,B2,...,Bk: Вх-+Ьп,Ьх2,..Ъи\ B2- b2l,b22,...b2l;...Bk- bk],bk2,...bkl и атрибутов Сх,С2,...,Ст: Cx cu,cn,...cu; C2 c2Vc22,...c2l ,...Cm- cmX,cm2,...cml. Тогда кортежи отношения R можно представить в виде таблицы 2.1. Для отношения R(AX,A2,-M„i Вх,В2,...,Вк; Сх,С2,...,Ст) формирование тензорного представления будет описываться следующим формальным правилом. Правило 1:

1) отношению R(Ax,A2,...,An; Вх,В2,...,Вк; Сх,С2,...,Ст) присваивается произвольная заглавная литера, например R;

2) п ключевым атрибутам Ах,А2,...,Ап присваивается п разноименных произвольных индексов, например ах,а2,...,ап;

3) атрибутам Вх,В2,...,Вк и Сх,С2,...,Ст присваивается (к + т) разноименных произвольных индексов, отличных от индексов п.2, например

4) ах,а2,...,ап будут соответствовать ковариантным (нижним) индексам тензора, определяющим входной поток данных, Ьх,Ь2,...,Ьк,сх,сг,...,ст будут соответствовать контравариантным (верхним) индексам тензора, определяющим выходной поток данных (см. рисунок 2.1);

5) тензор будет иметь вид &Ьарг"л/г Ст «Представление тензора» Замечание: Вход и выход тензора рассматривается с точки зрения потока запросов к сущности, таким образом, тензор описывает соответствие между ключевыми и не ключевыми атрибутами, однозначно определяя какие данные будут результатом запроса при обращении к сущности через ключевые атрибуты.

Поскольку достаточно трудно описывать построение ХД на абстрактных отношениях, то дальнейшие математические модели будут рассмотрены на конкретном примере (рисунок 2.2). Приведенный пример представляет собой усеченную версию БД предприятия, где осуществлялось внедрение.

Пользуясь правилом 1, составим тензорную модель для БД, представленную на рисунке 2.2, где литеры отношений и индексы атрибутов приведены рядом с соответствующей ТБД [11].

Рисунок 2.2 «Структура БД» Сущности «Сотрудники» будет соответствовать тензор р [27], сущ-ности «Требования» - тензор is і , «Выпуск» - г а, «Изделие» - J1"1 , «Сор тировка» - JYc , «Заказчики» - Sdb , «Поставщики» - ьР , «Детали» - М g, «Производство» — Ejg, Связь между сущностями БД, которая в реляционной модели осуществляется через первичные ключи, в данном случае будет определяться наличием у тензоров одноименных индексов. Таким образом, тензорная модель БД приведенной структуры имеет вид: Fr,Nfrb !nTjc\w Q Lm Kp Eijg Математическое описание БД, предложенное в этом разделе, опубликовано в статье [10].

Основная идея кратномасштабного анализа

Для решения проблемы приемлемого соотношения между вычисляемыми и хранящимися агрегированными данными предлагается привлечение методов кратномасштабного анализа [58, 67].

Идея кратномасштабного (многомасштабного) анализа (относящиеся сюда английские слова — multiscale и multiresolution) сводится к последовательному огрублению той информации, которая дана изначально.

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

Классическим примером конструкций, обеспечивающих кратномасштабное представление информации, служат пирамиды лапласианов и гаус-сианов, предложенные в [48]. Идеи, использованные при построении этих пирамид, легли в основу теории вейвлет-анализа (или анализа всплесков) [19, 36, 41, 47, 48, 70, 72, 74, 81] — инструмента, который активно используется в настоящее время для работы с кратномасштабными представлениями данных самой различной структуры.

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

Считается, что начало вейвлет-анализу было положено в работах А. Хаара еще в начале XX века. В дальнейшем предпринимались попытки создания иерархических базисов для решения различных задач, но они не были объединены единой теорией и, следовательно, не имели единого подхода.

В конце 80-х годов С. Малла вводит понятие кратномасштабного анализа [72], и определяет общий подход для поиска различных вейвлет-базисов. Им же разрабатывается основной алгоритм вычисления вейвлет-преобразований для дискретных сигналов, что открывает широкие возможности для практической реализации метода. С этого момента теория и практика вейвлет-анализа начинают активно развиваться. В 1992 году появляется классическая работа И. Добеши «Десять лекций по вейвлетам» [55] (в 2001 году издана на русском языке [19]).

Исходя из определения данного в [19] вейвлет-преобразование — это разложение сигнала по системе функций, которые являются сдвинутыми и масштабированными (сжатыми или растянутыми) копиями одной функции — порождающего вейвлета.

Правила выбора копий, участвующих в разложении, могут быть разными. Допустимо, например, разложение по всем возможным сдвигам и масштабам одной функции. Такое вейвлет-преобразование называется непрерывным [19, 74].

При наложении дополнительных условий на порождающий вейвлет, количество функций может быть сокращено до счетного множества. Наиболее распространенный случай — так называемое диадное преобразование, с помощью которого сигнал f(x) є L2(R) (сигнал рассматривается в двумерном пространстве) может быть представлен в виде суммы следующего ряда: /W = I V2 (2 -y) (3.1)

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

Для того чтобы представление (3.1) существовало для любого f{x)eL2(R), необходимо, чтобы система функций, порожденная вейвлетом р(х), являлась базисом в L2(R) (более подробно о базисах кратномасштабно-го представления рассказано в Приложении 1).

Частичную сумму ряда (3.1) /0-1 +» .— /( "Ч ) = І л/ (2 -Д/0 /=-00/=-00 называют приближением сигнала/(3с,) с разрешением /0. Сигнал f(x) можно представить в виде суммы начального приближения (то есть приближения с некоторым начальным разрешением /0) и оставшихся членов ряда: f(x) = fM(x)+YJ2cj) (P(2ix-jVo Z (3.2) " о /=-0

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

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

Реализация алгоритмов агрегации и ROLAP

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

Наиболее часто для формализации тренда временного ряда x(t) используется метод наименьших квадратов [28]. Функция тренда принимается линейной, вида r=a t+b, причем b = x, где х = — У х,, а = - — 1 /(/ + 1))2 В кратномасштабном представлении тренд определяется как значимое движение на рассматриваемом масштабе [43].

Разработанный алгоритм превосходит классический метод наименьших квадратов по быстродействию, что особенно актуально для оперативных аналитических систем. Алгоритм 3.6.1 (выделение тренда) Пусть в исходном ряде W(t) необходимо выявить тренд на интервале [х, УІ ШагЗ. п =

Шаг 1. Вычисляется длина интервала исходного диапазона h=y-x+\. Шаг 2. Определяется базовый уровень вейвлет-разложения /, масштаб которого будет соответствовать размеру исходного диапазона: / = _log2 h\. x-l 2 +1 индекс элемента Wln вейвлет-разложения на уров не/. Шаг 4. пу = у-\ + 1 индекс элемента Wln вейвлет-разложения на уров не/. Шаг 5. Уравнение тренда r=a t+b, где а = у-х = ! . { У-х х. Шаг 6. Конец.

Пример. Пусть для ряда W(t)=[\2, 4, 5, 7, 2, 8, 15, 9, 17, 5, 3, 19, 4, 8, 6, 2] (глава 3.4) необходимо выделить тренд на диапазоне с третьего по двенадцатое число. Таким образом, имеем интервал [3, 12]. Шаг 1. Вычисляется длина интервала исходного диапазона //=12-3+1=10. Шаг 2. Определяется базовый уровень вейвлет-разложения /, масштаб которого будет соответствовать размеру исходного диапазона: / = [log2 /zj=3. х-1 3-1 .23 . 12-2 12-3 I + 1 = + 1 = 1. . 2 -1 2 + 1 = 2. ШагЗ. п = + 1 = Шаг 4. п = r=a t+b, Шаг5. Уравнение тренда wi wi» w32-w3l , b = W, x = W3] у-х is, где а = — і±. = _і2 hi у-х 12-3 8 — 7-75 рисунком 3.6 a = !— = 0,028; В соответствии с 1 8-7,75 12-3 Шаг 6. Конец. 6 = 7,75 3 = 7,667, тогда уравнение тренда г=0,028/+7,667.

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

В кратномасштабном представлении выявляется необходимое условие существования периодичности в заданном диапазоне, индикатором которого явля ется равенство соответствующих коэффициентов разложения. В практических задачах абсолютное равенство этих коэффициентов встречается крайне редко, поэтому при сравнении допускается приближенное равенство с некоторой погрешностью є. Алгоритм использует исходный ряд значений данных W0J, /є[0,и] и его однократное вейвлет-разложение Wu, j е [\,р], р = _log2 п\.

Вход:/— длина диапазонов исходного ряда, в которых ведется поиск периодичности; є - погрешность вычислений периодичности. Выход: сообщение о наличии или отсутствии периодичности, начальное значение интервалов, где наблюдаются равные гармоники, значение периода. Шаг 1. Определение базового уровня вейвлет-разложения / = _log2 /J, масштаб которого будет соответствовать размеру исходного диапазона Шаг 2. Сравнение коэффициентов вейвлет-разложения масштаба / Whj U-Ц) Если Wu-Wlx s (x = j+\,j), тогда goto шагЗ, j:=x; иначе вывод сообщения «на заданном уровне приближения периодичности не наблюдается».

Похожие диссертации на Модели и алгоритмы автоматизации проектирования структур хранилищ данных для аналитической обработки числовых показателей