Формирование инвестиционно-инновационной стратегии холдинга тема диссертации по экономике, полный текст автореферата

Автореферат диссертации по теме "Формирование инвестиционно-инновационной стратегии холдинга"

На правах рукописи

Гудков Андрей Сергеевич

ИСПОЛЬЗОВАНИЕ ПРЕФИКСНЫХ ДЕРЕВЬЕВ ПРИ ПОСТРОЕНИИ СИСТЕМ АНАЛИЗА ДАННЫХ

Специальность 05.13.18 - Математическое моделирование, численные методы н комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2006

Работа выполнена на кафедре управляющих и информационных систем Московского физико-технического института (государственного университета).

Научный руководитель:

кандидат физико-математических наук, доцент

БОНДАРЕНКО Александр Викторович

Официальные оппоненты:

доктор физико-математических наук, профессор

СТОЛЯРОВ Лев Николаевич кандидат технических наук СЕМИН Николай Николаевич

Ведущая организация: Институт прикладной математики

имени М.В.Келдыша Российской академии наук (ИПМ РАН)

Защита диссертации состоится « » Дек<¿¿>¿>3 2006 года в /¿ч. Зо мин. на заседании диссертационного совета 12.156.02 в Московском физико-техническом институте (государственном университете) по адресу: 141700, Московская область, г. Долгопрудный, Институтский пер., д. 9, ауд. 903 КПМ.

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

Автореферат разослан «3! » 2006 года

Ученый секретарь диссертационного совета К212.156.02 к. ф.-м. н.

О. С. Федько

Общая характеристика работы

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

В литературе активно исследуются три основных технологии систем анализа данных: хранилища данных, оперативная аналитическая обработка данных (Online Analytical Processing, или сокращённо OLAP), интеллектуальный анализ данных (Data Mining).

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

Если объёмы данных очень велики, то предагрегация может значительно ускорить выполнение запросов. Также агрегирование может применяться для ответа на запросы пользователя с одновременным требованием просмотра многих агрегатных данных (например, при отображении сводной таблицы). Первые алгоритмы агрегирования куба основываются на существенном использовании диска и являются достаточно медленными. Алгоритмы МешогуСиЬе и В11С компактно используют оперативную память для проведения вычислений, но их планы выполнения являются неоптимальными. Предложенный в диссертации алгоритм перестроек префиксного дерева предлагает более быстрое выполнение по сравнению с заявленными алгоритмами при тех же объёмах обрабатываемых данных.

Одним из наиболее популярных направлений интеллектуального анализа данных является поиск правил в данных. В большинстве алгоритмов поиска правил первым и наиболее трудоёмким шагом является поиск частых наборов. Предложенный в диссертации алгоритм перестроек префиксного дерева обладает минимальными требованиями к памяти среди остальных алгоритмов и может обрабатывать большие объёмы данных без выхода на диск, что позволяет ускорить вычисления.

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

Цели работы. Основными целями диссертационной работы являются:

1. Разработка эффективных алгоритмов реализации интерактивного анализа данных, автоматического поиска частых наборов и правил в данных, основанных на использовании префиксного дерева.

2. Разработка алгоритмов удобного просмотра извлечённых правил.

3. Анализ разработанных алгоритмов.

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

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

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

Разработанный алгоритм интерактивного анализа данных внедрён в автоматизированной информационной системе "Консул ЗУ" в МИД РФ.

Апробация работы. Основные результаты работы докладывались, обсуждались и получили одобрение специалистов на следующих конференциях:

• XLVIII и XLIX научных конференциях Московского физико-технического института (государственного университета), (Долгопрудный, 2005, 2006)

• XIII международной научной конференции студентов, аспирантов и молодых учёных "Ломоносов", (Москва, МГУ, 2006),

а также на научных семинарах кафедры управляющих и информационных систем МФТИ и 3500 отделения ГосНИИ авиационных систем в 2002-2006 гг.

Публикации. Основные положения работы отражены в 6 публикациях. Структура н объём диссертации. Диссертация состоит из введения, пяти глав, заключения и списка использованных источников. Объём работы составляет 154 страницы. Список использованных источников содержит 101 наименование.

Краткое содержание работы

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

1.1. Классификация аналитических систем. По целям компьютерные системы можно разделить на вычислительные, ориентированные па

вычисления, и информационные, ориентированные на сбор и хранение данных. Последние делятся на оперативные и аналитические системы, целями которых являются соответственно оперативная обработка и анализ данных. Системы анализа данных классифицируются по способам хранения данных, способам анализа данных и степени участия человека в анализе. В каждом из этих направлений с развитием аналитических систем были предложены новые технологии: независимое хранение аналитических данных в технологиях хранилищ и витрин данных, динамический анализ данных на основе многомерной модели в технологии OLAP (Online Analytical Processing, или оперативная аналитическая обработка данных), автоматическое извлечение закономерностей из данных в технологии Data Mining (добыча данных, или интеллектуальный анализ данных). Одним из важных направлений Data Mining является извлечение правил из данных.

В диссертации предложены подходы к решению следующих основных задач в рамках рассмотренных технологий:

1. Реализация ответов на запросы интерактивного анализа данных (OLAP).

2. Агрегирование куба.

3. Поиск частых наборов и ассоциативных правил.

4. Эффективный просмотр ассоциативных правил.

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

Два наиболее популярных метода реализации OLAP - это реляционный OLAP (ROLAP), где данные хранятся в виде таблиц в реляционной базе данных специальной структуры, и многомерный OLAP (MOLAP), где данные хранятся в специальных структурах данных, реализующих многомерный массив. Кроме того, существует множество индексных структур, которые могут применяться как для ускорения программ ROLAP, так и самостоятельно. В качестве индексов могут использоваться многомерные массивы, инвертированные списки, битовые индексы, иерархические индексы, специальные многомерные индексы. Для ответов на запросы нужно не только выбрать удовлетворяющие ограничениям данные, но и произвести агрегацию. Для ускорения ответов на запросы часто используется частичная материализация агрегатных данных. Хранение данных во время работы программы может осуществляться на диске или в оперативной памяти.

1.3. Алгоритмы агрегирования куба. Задача агрегирования куба состоит в вычислении всех агрегатных данных по заданным исходным данным, что соответствует одновременному выполнению агрегатных запросов для всех подмножеств множества измерений, или подкубов.

Алгоритмы выполнения отдельного агрегатного запроса делятся на две группы: основанные на сортировке и основанные на хешировании. Алгоритмы агрегирования куба являются обобщениями этих алгоритмов с применением ряда оптимизаций: разделение сортировок и разбиений между подкубами, одновременное вычисление нескольких подкубов, вычисление по родительскому подкубу вместо исходного отношения. В работе рассматриваются алгоритмы PipeSort, PipeHash, Overlap, ArrayCube, PartitionedCube, MemoryCube, BUC. Для сравнения с разработанным алгоритмом используется алгоритм MemoryCube. Он выполняет вычисления над таблицей в оперативной памяти с помощью сортировок. План сортировок разработан таким образом, что число сортировок минимально.

1.4. Алгоритмы поиска частых наборов и ассоциативных правил. Ассоциативное правило - это выражение вида а—>Ь, где а и b - множества

значений атрибутов базы данных. Обычно поиск правил осуществляется с ограничениями по поддержке и доверию. Поддержкой правила называется число записей базы, где встречаются левая и правая часть правила одновременно. Доверием правила называется отношение поддержки левой и правой частей к поддержке левой части. Доверие характеризует точность правила. Задача поиска правил разбивается на два шага: поиск частых наборов, или наборов, удовлетворяющих порогу поддержки, и извлечение правил, удовлетворяющих порогу доверия, из частых наборов. Наиболее трудоёмкой является первая задача.

В работе рассматриваются алгоритмы поиска частых наборов для баз транзакций и баз данных. Сравнительный анализ проводится с алгоритмами Арпоп и РР-ОгодуШ. Наивный алгоритм генерирует все возможные комбинации и считает для них частоту за один проход по базе, после чего выделяет частые наборы. При этом число комбинаций очень велико. Алгоритм Арпоп уменьшает число комбинаций с помощью свойства антимонотонности: если набор является частым, то все его поднаборы также являются частыми. Отсюда следует, что если набор является редким, то все его расширения также являются редкими, и их можно не рассматривать. Для наибольшей эффективности отсечения с помощью этого свойства на каждом шаге должны рассматриваться комбинации-кандидаты одинаковой длины. Алгоритм РР-Ого\уЙ1 использует другую стратегию. Вместо генерации наборов-кандидатов строится компактное представление базы данных в виде структуры данных РР-дерева. Далее частые наборы извлекаются из этой структуры.

1.5. Эффективный просмотр ассоциативных правил. Обычно число потенциальных правил в данных очень велико, и только их маленькая доля является полезной. Чтобы убрать бесполезные правила, должны быть установлены некоторые критерии выбора правил. В качестве решений в литературе предлагаются использование мер интереса правил, синтаксические ограничения и специальные методы просмотра.

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

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

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

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

значениями измерений в базе данных. Оно показывает, что из наличия в строке элементов левой части правила следует наличие элемента правой части.

В диссертации решаются следующие задачи:

1. Ответы на запросы интерактивного анализа данных. По базе данных и запросу получить отчёт с промежуточными итогами или сводную таблицу.

2. Агрегирование куба. По базе данных получить все значения агрегированного куба.

3. Поиск частых наборов. По базе данных и порогу частоты s получить все значения агрегированного куба, большие или равные s.

2.2. Структура данных — префиксное дерево. Префиксное дерево строится для заданного порядка измерений, так что на каждом уровне хранятся элементы одного измерения, а каждый путь соответствует записи таблицы. В каждом узле помимо элемента измерения хранится суммарная частота встречаемости префикса в таблице.

Префиксное дерево строится из исходной таблицы за один проход. В процессе прохода каждая строка таблицы по очереди вставляется в дерево.

В алгоритмах используется перестройка уровней дерева. Любая перестройка дерева может быть сведена к перестановке двух соседних уровней. Эта операция называется подъёмом уровня и является основной операцией в выполнении запросов префиксным деревом. Пусть осуществляется подъём уровня k, к=2,...,т. Подъём осуществляется независимо для поддерева каждого узла уровня к-2. Для разных элементов уровня к этого поддерева создаются узлы с суммарной частотой и заносятся на уровень к-1 вместо старых узлов. Для каждого узла уровня к меняется элемент на элемент родительского узла, и меняется родительский узел на узел с тем же старым элементом.

2.3. Алгоритм выполнения запросов OLAP. Выполнение запроса с помощью префиксного дерева выполняется в два шага. Вначале производится перестановка уровней для приведения дерева к виду, когда

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

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

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

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

2.4. Алгоритм агрегирования куба с помощью перестроек префиксного дерева. В работе предложен следующий алгоритм агрегирования куба на основе перестроек префиксного дерева, названный РгеПхТгееСиЬ^. Алгоритм выполняется в два шага: построение плана вычислений и выполнение плана вычислений. План вычислений содержит два типа операций: подъём заданного уровня и подсчёт частот комбинаций

для заданного уровня. План вычислений строится с помощью следующей рекурсивной процедуры, входом которой является последовательность номеров (1,...^). Вначале в план добавляется подсчёт частот комбинаций уровня 1, затем строится план для номеров (¡+1,..^), в план добавляется последовательность подъёмов уровней ¡+1,для переноса уровня 1 после уровня строится план для номеров (¡,...0-1). В начальный момент для построения плана добавляется подсчёт общей частоты и вызывается рекурсивная функция для последовательности (1,...,ш), где щ - число измерений. На шаге выполнения плана последовательно производятся подсчёты частот комбинаций и подъёмы заданных уровней.

2.5. Алгоритм поиска частых наборов с помощью перестроек префиксного дерева. Для поиска частых наборов предложено 4 алгоритма, основанных на перестройках префиксного дерева: РТ11, РТ12, РТ13, РТ14.

Алгоритм РТ11 работает в основном также, как алгоритм РгейхТгееСиЬ^, но вводит одну оптимизацию, связанную с использованием свойства антимонотонности. При выполнении подсчёта комбинаций в случае встречи узла с частотой меньше порога подсчёт не проводится для всего соответствующего поддерева, так как там нет частых комбинаций.

Алгоритм РТ12 использует свойство антимонотонности в большей степени. Для поддерева, соответствующего узлу с частотой меньше порога, не производится не только подсчётов, но н перестроек уровней. При этом перестройки выполняются не для всего уровня целиком, а для каждого поддерева отдельно. Для того, чтобы на каждом уровне сохранялись элементы одного измерения, вводятся обратные перестройки после окончания обработки каждого поддерева.

Алгоритмы РТ13 и РТТ4 предварительно приводят префиксное дерево к такому виду, когда в нём хранятся только частые элементы, а затем работают как алгоритмы РТ11 и РТ12. Это позволяет уменьшить объём дерева и соответственно ускорить работу.

В главе 3 рассматриваются подходы к обеспечению эффективного

просмотра ассоциативных правил. Основная проблема заключается в

большом количестве получаемых правил. Два основных подхода к решению

этой проблемы: отсечение правил по мерам интереса и с помощью

синтаксических ограничений. Рассмотрена классификация мер правил.

Введены меры интереса, учитывающие состав левой части правила. Для них

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

интереса. Рассмотрены основные способы отображения правил. Предложен

способ интерактивного просмотра правил в виде сводной таблицы и

соответствующий алгоритм выполнения запросов и отображения,

основанный на перестройках префиксного дерева.

Рассмотрим правило вида а—>Ь. Меры делятся на 4 группы: точность,

статистическая обоснованность, неожиданность (интерес) и полезность. В

качестве меры точности в основном используется условная вероятность

Р(Ь | а). Основная мера интереса заключается в сравнении точности правила с

Р(Ь | а) Р(аЬ) г, _

вероятностью правой части ^ ^ Р( )Р(Ь)' Данная меРа не учитывает

структуры левой части правила. Одна из возможностей учёта — мера

ЗирегЫегеи(а ->Ь) =-^а>- Она эффективно отсекает правила, но

Р(Ь | с)

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

П Р{В\Ал...А,к)

равна ЕхрР(В\Аг..А„)=".....*'с1'гт^Г7 . ^

(]1.....¡У. [I.....II|,н-Ь-чвтиое

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

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

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

В главе 4 проводится теоретический анализ разработанных алгоритмов. Решена вспомогательная задача о среднем числе разных значений и среднем числе разных частых значений при заданном пороге частоты в выборке из конечного множества. На основе этой задачи получены оценки сложности решаемых задач, включая объём исходных данных, запрашиваемых данных, частых наборов. Подсчитаны объём префиксного дерева, время построения по базе данных, время подъёма уровня в лучшем, худшем и среднем случаях. Вычислено время работы для алгоритмов агрегирования куба и поиска частых наборов.

Теорема 4.1 (о среднем числе разных элементов). Пусть имеется т-элементное множество, из которого делается выбор с возвращением п элементов. Тогда

1. Среднее число разных элементов для заданных значении m,n

Кср(т,п) = т-[\-(\--)п]. ^ m

2. Среднее число элементов, встречающихся больше или равно s раз, для заданных значений m,n Kcp(m,n,s) = -—т-=-_ ■-.

' т" 1 т" 1

Теорема 4.2 (о сложности задач). Пусть

1.т - число измерений, п - число записей, Рь---,Рт - число разных значений измерений 1,...,т. Тогда

1. Минимальное число разных записей равно 1, максимальное равно тт(п,р1■••••Рт), среднее равно КсР(рг...-рт,п).

2. Минимальное число ненулевых ячеек полного агрегированного куба равно 2т, максимальное равно ^ ют(Д^,л), среднее равно

1.....т|

X ^срСП^У''1)- При р1=...=рт=р максимальное и среднее значения

.........и} /«./

принимают вид ¿С^ •тт(р',п) и ¿С^, •Кср(р\п) соответственно. /=0 (=0

3. Минимальное число частых комбинаций при заданном пороге

частоты э равно £ £(л,0 -1)]~| />,), максимальное равно

-'<=(1.....»о ¡^

2 тт([]р^п\з), среднее равно У Кср($\ррп,$). При р!=...=рт=р

уеУ ./<=(1.....т|

минимальное, максимальное и среднее значения принимают вид

т т т

С'щ ■ Е(п,(я -1)р'), ^С^, ■ тт(р',п \ ,ч) и Кср(р1,п,з) соответственно. Здесь

1-0 1=0 *=0

п\з обозначает целочисленное деление п на б, Е(к1,к2)=1, если к!>к2, и 0 в противном случае.

Теорема 4.3 (о числе узлов префиксного дерева). Пусть

1.т — число измерений, п — число записей, р!,...,рт — число разных значений измерений 1,...,т.

2. Префиксное дерево построено в порядке измерений (1,...,ш). Тогда

1. Минимальное число узлов префиксного дерева на уровне 1 равно 1, максимальное равно тш(п,р1-...-р0> среднее равно К<;р(р1-...-рьп).

2. Минимальное число узлов префиксного дерева равно т+1,

максимальное равно р1 + п(т - Г), среднее равно ^ Кср{р\ -...- р^п).

Ру-Р,™ '=0

Теорема 4.4 (о времени построения префиксного дерева). Пусть

1.m — число измерений, п - число записей, pi,...,pm - число разных значений измерений 1,...,ш.

2. Если префиксное дерево строится в порядке измерений (1,...,ш) с помощью последовательной вставкн записей, то

2.1. Количество добавлений узлов равно Nnodes-

2.2. Количество операций сложения равно (m+l)n-NnodL.s.

2.3. Количество операций сравнения равно О(шп) при использовании хеш-таблиц для хранения узлов, 0((pi+...+pm)n) при использовании списков.

3. Если префиксное дерево строится в порядке измерений (1,...,ш) из отсортированной в том же порядке измерений таблицы, то

3.1. Количество добавлений узлов равно Nn0deS.

3.2. Количество операций сложения равно п-1.

3.3. Количество операций сравнения равно mn.

Здесь Nnodes — число узлов префиксного дерева.

Теорема 4.5 (о времени подъёма уровня префиксного дерева). Пусть

1. щ - число измерений, п - число записей, pi,...,pm - число разных значений измерений 1,...,ш.

2. Префиксное дерево построено в порядке измерений (1,...,ш).

3. Осуществляется подъём уровня i, is {2,...,m}.

Тогда число созданий узлов равно nb, число удалений узлов равно па, число сложений равно nab-nb, число сравнений равно O(nab). Здесь па -число узлов префиксного дерева на уровне i-1 до подъёма уровня i, nb -число узлов префиксного дерева на уровне i-1 после подъёма уровня i, nab -число узлов префиксного дерева на уровне i.

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

Время перестройки дерева определяется общим числом подъёмов уровней для выполнения запроса и числом подъёмов каждого отдельного

17

уровня. Эти величины проанализированы для двух типов запросов: вставка измерения на новую позицию и произвольная перестановка всех измерений. Для каждого случая рассмотрены оценки в лучшем случае, худшем случае и в среднем.

Теорема 4.6 (о числе перестроек уровней в алгоритме интерактивного анализа данных).

1. Пусть префиксное дерево имеет порядок уровней (1,...,т).

2. Если задан запрос на перестановку измерения i после измерения j, ije{l,...,m},TO

2.1. Минимальное число подъёмов уровней равно 0, максимальное

(т - 1)(2лг — 1)

равно т-1, среднее равно -----.

6т

2.2. Минимальное число подъёмов уровня k,2<k<m, равно О, максимальное равно 1, среднее равно -—■—^-

3. Если задан запрос на приведение префиксного дерева к порядку уровней (i и..., im), то

3.1.Минимальное число подъёмов уровней равно 0, максимальное

т(т— 1) т(т-1)

равно ———-, среднее равно —^—-.

3.2. Минимальное число подъёмов уровня k,2<k<m, равно О,

максимальное равно т—к+1, среднее равно {к .

i.t'

Теорема 4.7 (о времени работы алгоритма поиска всех наборов). Для алгоритма PrefixTreeCubing справедливы следующие формулы для числа подсчётов и подъёмов уровней.

1. Число подсчётов уровней Nc(rn)=2m.

2. Число подсчётов на уровне i Nc(m,i)= С'т ,i=0,... ,m.

3. Число подъёмов уровней Nr(m)=2m-m-l.

4. Число подсчётов на уровне i Nr(m,i)=c;;'-1, i=l,...,m.

Они являются оптимальными среди всех алгоритмов поиска всех наборов с помощью перестроек префиксного дерева

Теорема 4.8 (о времени работы алгоритмов поиска частых наборов).

1. Для алгоритма PTI1 справедливы следующие оценки.

1.1. Число подсчётов и подъёмов уровней совпадает с соответствующим числом для алгоритма PrefixTreeCubing.

1.2. Число просматриваемых узлов при подсчёте комбинаций на уровне i меньше соответствующего числа для алгоритма PrefixTreeCubing и определяется формулой Kcp_np(pi-...-p¡-i,p¡,n,s), где

KCp_np(mhm2,n,s)= £ ■ J^Kcp(m2,ij) ■

1.3. Число обрабатываемых узлов уровня i при подъёме уровня i равно числу узлов на уровне i.

2. Для алгоритма PTI2 справедливы следующие оценки.

2.1. Число подсчётов уровней совпадает с соответствующим числом для алгоритма PrefixTreeCubing.

2.2. Число подъёмов уровней в два раза больше соответствующего числа для алгоритма PrefixTreeCubing.

2.3. Число просматриваемых узлов при подсчёте комбинаций на уровне i меньше соответствующего числа для алгоритма PrefixTreeCubing и определяется формулой Kcp_np(pi-...p¡_i,pj,n,s).

2.4. Число обрабатываемых узлов уровня i при подъёме уровня i меньше соответствующего числа для алгоритма PrefixTreeCubing и определяется формулой KCp_rip(pr...-p,-2,pi.1pi,n,s).

3.Для алгоритмов PTI3 и PTI4 справедлива следующая оценка. Среднее число узлов на уровне i получаемого после первого шага префиксного дерева с частыми элементами определяется формулой Kcp_,n(pi.....p¡,n,s), где

кср _ чэ(/>1.....Pm,n,s) =

= Pl--PmZ-Z(—)W-(—Ml-— )"-*1...0—±- +

»1-! tm-s Pi Pm P\ Pm ••>

В главе 5 проводится экспериментальный анализ разработанных алгоритмов для выполнения запросов интерактивного анализа данных, агрегирования куба и поиска частых наборов.

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

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

5.2. Алгоритмы агрегирования куба. Для проведения экспериментов по эффективности алгоритмы PrefixTreeCubing и MemoryCube были реализованы в виде программы на языке Delphi7. Эксперименты проводились на случайно сгенерированных данных для двух распределений значений измерений: равномерного и распределения Зипфа с показателем 1, а также на реальных данных. Для алгоритма MemoryCube эксперименты проведены для двух случаев: непосредственное выполнение на заданной таблице и выполнение после предварительного объединения одинаковых записей. Алгоритм на основе префиксного дерева показал в несколько раз

большую скорость выполнения запросов при сравнимом объёме занимаемой памяти.

5.3. Алгоритмы поиска частых наборов. Для проведения экспериментов по эффективности были реализованы в виде программы на языке Delphi7 четыре варианта алгоритма PrefixTreelceberg и алгоритмы Apriori и FP-Growth. Эксперименты проводились на случайно сгенерированных данных для двух распределений значений измерений: равномерного и распределения Зипфа с показателем 1, а также на реальных данных. В среднем наилучшие результаты показал алгоритм PTI3.

5.4. Меры интереса правил. Для сравнения эффективности мер сравнивалось количество правильно предсказанных правил для различных наборов реальных данных. Мера Superlnterest и меры предсказания показали высокую эффективность по сравнению с простой мерой интереса.

В заключении приведены основные результаты работы.

Основные результаты работы

1. Предложена математическая модель в виде префиксного дерева для хранения данных при интерактивном анализе данных и процедура перестройки уровней префиксного дерева для задания различных порядков на множестве данных.

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

3. Введено несколько мер ценности ассоциативных правил, учитывающих их специфику, и разработан алгоритм поиска интересных ассоциативных правил с учётом этих мер.

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

5. Разработан комплекс программ для предложенных и ряда известных алгоритмов. Проведено экспериментальное сравнение их эффективности.

Список публикаций по теме диссертации

1. Бондаренко A.B., Галактионов В.А., Горемычкин В,И., Гудков A.C., Стриковский И.И. Реализация интерактивного анализа данных с помощью префиксного дерева: Препринт / ИПМ. — М., 2005. —№61. — 34 с.

2. Гудков A.C. Агрегирование куба с помощью префиксного дерева. // Современные проблемы фундаментальных и прикладных наук. Часть VII. Управление и прикладная математика: Труды XLVIII научной конференции. / МФТИ. - М. - Долгопрудный, 2Ó05. - С.92-93.

3. Гудков A.C. Поиск частых комбинаций в базах данных. // Материалы XIII Международной конференции студентов, аспирантов и молодых учёных "Ломоносов", секция "Вычислительная математика и кибернетика". - М., 2006. — С.19-20.

4. Бондаренко A.B., Гудков A.C. Поиск частых и разных комбинаций с помощью перестроек префиксного дерева. // Процессы и методы обработки информации: Сб.ст. / МФТИ. - М., 2006. - С.69-78.

5. Бондаренко A.B., Гудков A.C. Интерактивный анализ ассоциативных правил в базе данных. // Вестник компьютерных и информационных технологий. - 2006. - №10. - С.42-45.

6. Гудков A.C. Меры интереса ассоциативных правил, основанные на предсказании точности. // Современные проблемы фундаментальных и

прикладных наук. Часть VII. Управление и прикладная математика: Труды Х1ЛХ научной конференции. / МФТИ. - М. - Долгопрудный, 2006. - С.84-85.

Гудков Андрей Сергеевич

ИСПОЛЬЗОВАНИЕ ПРЕФИКСНЫХ ДЕРЕВЬЕВ ПРИ ПОСТРОЕНИИ СИСТЕМ АНАЛИЗА ДАННЫХ

Автореферат

Подписано в печать 30.10.2006. Формат 60x84 1/16. Усл. печ. л. 1,0. Тираж 80 экз. Заказ № 316.

ФГУП Государственный научно-исследовательский институт авиационных систем 125319, Москва, ул. Викторенко, 7

Диссертация: содержание автор диссертационного исследования: кандидата экономических наук, Носенко, Алексей Сергеевич

Введение

1. Теоретические предпосылки перехода к интеграции инвестиционной и инновационной стратегий в условиях холдинга

1.1. Корпоративное управление как условие ускоренного инвестиционно-инновационного развития предприятий холдинга

1.2. Анализ сущности инвестиций и инноваций холдинга

1.3. Инвестиционно-инновационный процесс и его структура

2. Исследование инвестиционно-инновационных возможностей развития кондитерской промышленности в конкурентной среде

2.1. Анализ условий формирования инвестиционно-инновационного потенциала российских предприятий

2.2. Диагностика современного состояния и тенденций развития отрасли

2.3. Оценка инвестиционной и инновационной деятельности холдингов, предприятий кондитерской промышленности

3. Концепция реализации инвестиционно-инновационной стратегии холдинга кондитерской промышленности

3.1. Методические аспекты формирования инвестиционно-инновационной стратегии холдинга

3.2. Алгоритм формирования инвестиционно-инновационной стратегии холдинга

3.3. Методика выбора и оценки альтернативных инвестиционно-инновационных стратегий 147 Выводы и предложения 163 Список использованной литературы

Диссертация: введение по экономике, на тему "Формирование инвестиционно-инновационной стратегии холдинга"

Актуальность темы исследования. На современном этапе развития России наблюдается некоторый экономический рост, но конкурентоспособность многих отечественных товаров на мировом рынке еще недостаточна.

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

Мировой опыт свидетельствует, что на научно-исследовательские и опытно-конструкторские работы расходуется достаточно большая доля валового внутреннего продукта, которая в перспективе увеличится.

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

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

Степень разработанности проблемы. Проблемы инновационного развития, привлечения инвестиций получили широкое трактование в трудах российских ученых: Дасковского В.Б., Булатова А.Е., Киселёва В.Б., Крейниной

М.М., Масленниковой O.A., Мильнера Б.З., Ульянова Е.В., Магомедова М.Д., а также зарубежных учёных Гитмана Л.Дж., Питерса Т., Фостера Р. и др.

Вопросы теории и практики корпоративного управления отражены в работах Абалкина Л.И., Балабанова И.Т., Винслава Ю.Б., Гапоненко В.Н., Гатов-ского Л.М., Гусева В.В., Гончарова В.Д., Егорова Ю.И., Игольникова Г.Л., Кейнса Д.М., Минаевой Е.В., Русинова В.М., Рябовой Т.Ф., Туровца О.Г., Фат-хутдинова Р., Филатова O.K., Шумпетера И. и др.

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

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

Для достижения цели исследования были поставлены и решены следующие задачи:

• выполнен анализ условий формирования инвестиционно-инновационного потенциала российских предприятий;

• исследовано современное состояние управления корпоративной деятельностью на основе инновационной и инвестиционной стратегий;

• систематизированы научно-теоретические подходы к инвестиционной и инновационной стратегиям, уточнён терминологический аппарат теории формирования интегрированной инновационной и инвестиционной стратегии холдинга на основе изучения генезиса понятия «инвестиции», «инновации», «инвестиционная и инновационная деятельность», «инвестиционно-инновационный процесс» и теоретического осмысления их применительно к холдингу кондитерской промышленности;

• изучены основные особенности инвестиционного и инновационного процессов в холдинге кондитерской промышленности;

• проанализировано современное состояние инновационных разработок в кондитерской отрасли;

• выполнен ретроспективный анализ производства кондитерской продукции в Российской Федерации;

• разработаны научно-методические и практические подходы к формированию инвестиционно-инновационной стратегии кондитерского холдинга;

• обоснованы меры по совершенствованию организационной структуры холдинга путём создания «Центра инновационного развития холдинга и его предприятий».

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

Объектом исследования являются холдинги и предприятия кондитерской промышленности.

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

Информационную базу исследования составили материалы Государственного комитета по статистике Российской Федерации; законодательные и нормативно-правовые акты Президента и Правительства РФ, относящиеся к теме диссертации; материалы научно-практических конференций; ресурсы Интернет (электронные версии аналитических отраслевых отчётов и справочно-информационных материалов); отчёты Ассоциации предприятий кондитерской промышленности (АСКОНД); сведения о деятельности кондитерских предприятий, холдингов, собранные непосредственно автором.

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

Научная новизна исследования заключается в следующем:

• научно обосновано понятие «инвестиционно-инновационная стратегия», которое вносит уточнение в классификацию функциональных стратегий с учётом их проявления в условиях корпоративного управления;

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

• вскрыты дополнительные возможности инновационного развития предприятий, входящих в состав холдинга, путем создания «Центра инновационного развития холдинга и его предприятий», в рамках которого осуществляется координация НИОКР;

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

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

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

Прикладную направленность имеют следующие разработки:

• алгоритм формирования инвестиционно-инновационной стратегии холдинга;

• методика выбора альтернативных инвестиционно-инновационных стратегий на основе предложенной системы показателей их оценки;

• рекомендации по созданию «Центра инновационного развития холдинга и его предприятий».

Апробация работы. Основные результаты диссертационной работы были представлены и обсуждены:

- на научно-практической конференции «Актуальные проблемы экономики, менеджмента и маркетинга в отраслях АПК», Москва, МГУПП, 2005;

- на третьей юбилейной Международной выставке-конференции «Высокоэффективные пищевые технологии, методы и средства для их реализации», Москва, МГУПП, 2005;

- на четвертой международной конференции-выставке «Высокоэффективные пищевые технологии, методы и средства для их реализации», Москва, МГУПП, 2006.

Положения, изложенные в диссертационной работе, были апробированы при разработке стратегии развития на 2010 г. в кондитерском холдинге при участии автора; приняты для использования в учебном процессе Московского государственного университета пищевых производств при проведении занятий со студентами специальностей 080502 «Экономика и управление на предприятиях пищевой промышленности» и 080111 «Маркетинг».

На защиту выносятся следующие наиболее существенные положения:

1. Предложенное понятие интегрированной инвестиционно-инновационной стратегии расширяет классификацию функциональных стратегий и требует разработки алгоритма ее формирования в условиях корпоративного управления;

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

3. Формирование модели инвестиционно-инновационной стратегии во многом зависит от механизма привлечения инвестиций и типа инновации, что обуславливает необходимость разработки программ реализации выбранной стратегии;

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

5. Руководство инновационным развитием в холдинге должно быть возложено на новое структурное подразделение — «Центр инновационного развития холдинга и его предприятий».

Публикации. По теме диссертации опубликовано 6 статей и 1 брошюра общим объёмом 4,4 п.л. (авторский вклад — 4,3 п.л.).

Диссертация: заключение по теме "Экономика и управление народным хозяйством: теория управления экономическими системами; макроэкономика; экономика, организация и управление предприятиями, отраслями, комплексами; управление инновациями; региональная экономика; логистика; экономика труда", Носенко, Алексей Сергеевич

Выводы и предложения

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

2. Исследование теоретических основ корпоративного управления позволило автору уточнить сущность «инвестиционно-инновационного процесса», «инвестиционно-инновационной деятельности», «инвестиционно-инновационного потенциала» с учетом особенностей их проявления в условиях холдинга.

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

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

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

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

7. Руководство инновационным развитием холдинга должно быть возложено на специальное структурное подразделение «Инновационный центр научных исследований» в составе департамента «Стратегическое управление». Его назначение — обосновать приоритеты НИР и инвестиции, внедрять трансферт технологий по договорам с НИИ и ВУЗами, а также собственные инновации; отслеживать первоочередность разработки инноваций в соответствии с принятой классификацией.

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