Компьютерные системы поддержки принятия решений

Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования «Омский государственный технический университет» В.Н. Цыганенко А.Г. Белик КОМПЬЮТЕРНЫЕ СИСТЕМЫ ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ Конспект лекций Омск - 2007 PDF created with pdfFactory Pro trial version www.pdffactory.com УДК 004.891.2(075) ББК 32.973.26-018.2я73 Ц 94 Рецензенты: Чуканов С.Н., д-р.техн.наук, профессор, с.н.с. ОФ ИМ им. С.Л.Соболева СО РАН; Семенова И.И., канд.техн.наук, доцент кафедры прикладной информатики факультета информатики Сибирской автомобильно-дорожной академии. Цыганенко В. Н. Ц 94 Компьютерные системы поддержки принятия решений: консп. лекций / В. Н. Цыганенко, А. Г. Белик – Омск: ОмГТУ, 2007. – 96 с. Приводятся основные направления в области анализа данных. Приведено описание методов и алгоритмов решения основных задач анализа, дополненных конкретными примерами для применения. Конспект лекций предназначен для студентов специальности 230102 – Автоматизированные системы обработки информации и управления. УДК 004.891.2(075) ББК 32.973.26-018.2я73 Печатается по решению редакционно-издательского государственного технического университета. совета Омского © В.Н. Цыганенко, А.Г. Белик, 2007 © Омский государственный технический университет, 2007 PDF created with pdfFactory Pro trial version www.pdffactory.com СО ДЕРЖ А Н ИЕ Введение ...........................................................................................................................5 1. СППР. Задачи. Назначение. Архитектуры..................................................................5 1.1. Перегрузка информацией................................................................................6 1.2. Data Mining.......................................................................................................6 1.3. Анализ данных .................................................................................................6 1.4. Основные задачи СППР ..................................................................................7 1.5. Три класса задач анализа.................................................................................7 1.6. Обобщенная архитектура СППР.....................................................................8 1.7. Два класса задач: OLTP и DSS системы.........................................................9 1.8. Неэффективность использования OLTP для анализа данных.....................10 1.9. Статические и динамические DSS ................................................................12 2. Подготовка данных к анализу....................................................................................13 2.1. Структура подсистем подготовки данных ...................................................13 2.2. Этапы и методы подготовки данных ............................................................15 2.3. Децимация, фильтрация ................................................................................17 3. Хранилища данных. Data Warehouse.........................................................................22 3.1. Концепция хранилища данных .....................................................................22 3.2. ХД – многомерные кубы ...............................................................................23 3.3. Неудачи проектов по созданию ХД..............................................................26 3.4. Витрины данных. Data Marts.........................................................................26 3.5. Эффективность архитектур ХД ....................................................................27 3.6. Основные свойства ХД..................................................................................28 3.7. Основные проблемы создания ХД................................................................31 3.8. Организация ХД.............................................................................................31 3.9. Информационные потоки..............................................................................33 3.10. Перенос данных ...........................................................................................33 3.11. Инструментарий хранилищ данных ...........................................................35 4. Оперативный анализ данных OLAP ..........................................................................37 4.1. Определение, назначение, общий принцип работы.....................................37 4.2. 12 правил Кодда – принципы OLAP.............................................................41 4.3. Архитектура OLAP-систем ...........................................................................43 4.4. Аналитические OLAP-операции...................................................................44 5. Интеллектуальный анализ данных. Data Mining ......................................................48 5.1. Добыча данных. Data Mining ........................................................................48 5.2. Модели Data Mining.......................................................................................51 5.3. Методы Data Mining ......................................................................................51 5.4. Процесс поддержки принятия решений .......................................................53 5.5. Процесс обнаружения знаний .......................................................................55 6. Классификация и регрессия .......................................................................................57 6.1. Постановка задачи. Представление результатов .........................................58 6.2. Построение правил классификации..............................................................59 6.3. Построение деревьев решений......................................................................61 7. Поиск ассоциативных правил....................................................................................63 7.1. Формальная постановка задачи ....................................................................63 3 PDF created with pdfFactory Pro trial version www.pdffactory.com 7.2. Ассоциативные правила ............................................................................... 64 7.3. Алгоритм Apriori........................................................................................... 65 8. Кластеризация............................................................................................................ 66 8.1. Постановка задачи. Формальная постановка задачи .................................. 66 8.2. Меры близости, используемые при кластеризации .................................... 67 8.3. Классификации и виды алгоритмов кластеризации.................................... 69 9. Практическое применение некоторых методов и алгоритмов................................ 70 9.1. Алгоритмы фильтрации, сглаживание данных ........................................... 70 9.2. Алгоритм CART............................................................................................ 74 9.3. Алгоритм HITS.............................................................................................. 77 9.4. Алгоритм Гюстафсона – Кесселя................................................................. 78 9.5. Агломеративные алгоритмы......................................................................... 79 9.6. Алгоритм K-MEANS..................................................................................... 81 9.7. Генетические алгоритмы .............................................................................. 83 9.8. Алгоритм метода скользящего окна ............................................................ 87 10. Стандарты Data Mining............................................................................................ 90 10.1. Стандартизация Data Mining. Основные аспекты ..................................... 90 10.2. Стандарт CWM............................................................................................ 90 10.3. Стандарт CRISP........................................................................................... 93 10.4. Стандарт PMML.......................................................................................... 95 10.5. Библиотеки Data Mining ............................................................................. 96 Список литературы........................................................................................................ 98 4 PDF created with pdfFactory Pro trial version www.pdffactory.com Введение Учебная дисциплина «Компьютерные системы поддержки принятия решений» читается студентам специальности «Автоматизированные системы обработки информации и управления» с целью обучения и применения современных методов анализа данных для разработки информационных систем и систем поддержки принятия решений. Знание методик поддержки принятия решений, позволит будущему специалисту, принимающего решение, сочетать собственные субъективные предпочтения с компьютерным анализом ситуации в процессе выборки решений. Теоретическое содержание дисциплины, предусмотренное действующим государственным образовательным стандартом, охватывает обширный круг вопросов дисциплин, ранее изученных студентом на втором, третьем и четвертом году обучения. Применительно к дисциплине «Компьютерные системы поддержки принятия решений» рассматриваются вопросы, содержащие общую информацию о современных направлениях анализа данных, хранения информации, оперативного и интеллектуального анализа, методы и алгоритмы интеллектуального анализа, особенности и эффективность генетических алгоритмов, нейронечетких систем. По окончании изучения дисциплины, рассматриваемые методы поддержки принятия решений дают возможность студентам, как потенциальным экспертам в данной области, генерировать большое число возможных вариантов решений, прогнозировать последствия принимаемых решений, выбирать наилучший вариант, приводящий к решению проблемы. Подробное рассмотрение методов и алгоритмов интеллектуального анализа позволяет не только ознакомиться с данной областью применения информации систем, но и разрабатывать конкретные системы. 1. СППР. Задачи. Назначение. Архитектуры Частью повседневной деятельности человека является принятие решений. Простые, привычные решения человек принимает часто автоматически, не задумываясь об этом. Но в более сложных и ответственных ситуациях, он прибегает к помощи опытных, знающих людей, либо для подтверждения своего решения, либо для несогласия с ним, либо за советом. Принятие решения в большинстве случаев заключается в генерации возможных альтернатив решений, их оценке и выборе лучшей альтернативы. Большое количество задач, являются многокритериальными задачами, в которых необходимо учитывать большое число факторов. Системы поддержки принятия решений (СППР) помогают произвести оценку ситуации, осуществить выбор критериев, оценить их относительную важность, генерировать возможные сценарии действия, моделировать принимаемые решения, осуществлять оценку результатов. 5 PDF created with pdfFactory Pro trial version www.pdffactory.com 1.1. Перегрузка информацией Объем информации в мире увеличивается на 5 миллиардов миллиардов (5,000,000,000,000,000,000) байт. Информация удваивается каждые 2-3 года. Этот потоп, цунами данных приходит из науки, бизнеса, Интернета и других источников. Среди самых больших баз данных в France Telecom имела СППР размером более 30,000 миллиардов байт, а Alexa Internet Archive содержал 500, 000 миллиардов байт. Из-за огромного количества информации, очень малая ее часть будет когда-либо увидена человеческим глазом. Наша единственная надежда понять и найти что-то полезное в этом океане информации – широкое применение методов интеллектуального анализа Data Mining. 1.2. Data Mining Data Mining (также называемая Knowledge Discovery In Data – обнаружение знаний в данных) изучает процесс нахождения новых, действительных и потенциально полезных знаний в базах данных. Data Mining лежит на пересечении нескольких наук, главные из которых – это системы баз данных, статистика и искусственный интеллект. Data Mining широко используется во многих областях с большим объемом данных. В науке – астрономии, биологии, биоинформатике, медицине, физике и других областях. В бизнесе – торговле, телекоммуникациях, банковском деле, промышленном производстве и т.д. Благодаря сети Интернет Data Mining используется каждый день тысячи раз в секунду – каждый раз, когда кто-то использует поисковые системы на просторах Интернета. Виды информации, с которыми работают исследователи, включают не только цифровые данные, но и в большей степени это текст, изображение, видео, звук и т.д. Одна новая и быстро растущая часть Data Mining – это анализ связей между данными, которая имеет приложения в таких разных областях, как биоинформатика, цифровые библиотеки и защита против терроризма. Математический и статистический подходы являются основой для Data Mining. 1.3. Анализ данных С появлением первых ЭВМ наступил этап информатизации разных сторон человеческой деятельности, этап осознания процессов, связанных с информацией. Вычислительная техника создавалась, прежде всего, для обработки данных. В настоящее время современные вычислительные системы и компьютерные сети позволяют накапливать большие массивы данных для решения задач обработки и анализа. Машинная форма представления данных содержит информацию, необходимую человеку, в скрытом виде, и для ее извлечения нужно использовать специальные методы анализа данных. Большой объем информации позволяет с одной стороны, получить более точные расчеты и анализ, с другой – превращает поиск решений в сложную задачу. Появился целый класс программных систем, призванных облегчить работу людей, выполняющих анализ (аналитиков). Такие системы принято называть Системами поддержки принятия решений – СППР (DSS, Decision Support System). 6 PDF created with pdfFactory Pro trial version www.pdffactory.com 1.4. Основные задачи СППР Для выполнения анализа СППР должна накапливать информацию, обладая средствами ее ввода и хранения. Таким образом, можно выделить три основные задачи, решаемые в СППР: − ввод данных; − хранение данных; − анализ данных. СППР – это системы, обладающие средствами ввода, хранения и анализа данных, относящихся к определенной предметной области, с целью поиска решений. Ввод данных Ввод данных в СППР осуществляется либо автоматически от датчиков, характеризующих состояние среды или процесса, либо человеком-оператором. В первом случае данные накапливаются путем циклического опроса, либо по сигналу готовности, возникающему при появлении информации. Во втором случае СППР должны предоставлять пользователям удобные средства ввода данных, контролирующие корректность вводимых данных и выполняющие сопутствующие вычисления. Если ввод осуществляется одновременно несколькими операторами, то система должна решать проблемы параллельного доступа и модификации одних и тех же данных. Хранение данных Постоянное накопление данных приводит к непрерывному росту их объема. В связи с этим на СППР ложится задача обеспечить надежное хранение больших объемов данных. На СППР также могут быть возложены задачи предотвращения несанкционированного доступа, резервного хранения данных, архивирования и т.д. Анализ данных в СППР Основная задача СППР – предоставить аналитикам инструмент для выполнения анализа данных. Для эффективного использования СППР ее пользователь – аналитик должен обладать соответствующей квалификацией. Система не генерирует правильные решения, а только предоставляет аналитику данные в соответствующем виде (отчеты, таблицы, графики) для изучения и анализа, именно поэтому такие системы обеспечивают выполнение функций поддержки принятия решений. Качество принятых решений зависит от квалификации аналитика. Рост объемов анализируемых данных, высокая скорость обработки и анализа, сложность использования машинной формы представления данных – стимулируют исследования и разработку интеллектуальных СППР. Для таких СППР характерно наличие функций, реализующих отдельные умственные возможности человека. 1.5. Три класса задач анализа По степени «интеллектуальности» обработки данных при анализе выделяют три класса задач анализа: − информационно – поисковый – СППР осуществляет поиск необходимых данных. Характерной чертой такого анализа является выполнение заранее определенных запросов; 7 PDF created with pdfFactory Pro trial version www.pdffactory.com − оперативно – аналитический – СППР производит группирование и обобщение данных в любом виде, необходимом аналитику. В отличие от предыдущего анализа в данном случае невозможно заранее предсказать необходимые аналитику запросы; − интеллектуальный – СППР осуществляет поиск функциональных и логических закономерностей в накопленных данных, построение моделей и правил, которые объясняют найденные закономерности и/или (с определенной вероятностью) прогнозируют развитие некоторых процессов. 1.6. Обобщенная архитектура СППР Обобщенная архитектура СППР, представленная на рисунке 1 имеет три подсистемы, которые необходимо рассмотреть подробнее. Подсистема ввода данных. В таких подсистемах, называемых OLTP (On-line transaction processing), реализуется операционная (транзакционная) обработка данных. Для их реализации используют обычные системы управления базами данных (СУБД). Подсистема хранения. Для реализации данной подсистемы используют современные СУБД и концепцию хранилищ данных. Подсистема анализа. Данная подсистема может быть построена на основе: − подсистемы информационно – поискового анализа на базе реляционных СУБД и статических запросов с использованием языка SQL; − подсистемы оперативного анализа. Для реализации таких подсистем применяется технология оперативной аналитической обработки данных OLAP (On-line analytical processing), использующая концепцию многомерного представления данных; − подсистемы интеллектуального анализа. Данная подсистема реализует методы и алгоритмы Data Mining. Рис. 1. Обобщенная архитектура системы поддержки принятия решений 8 PDF created with pdfFactory Pro trial version www.pdffactory.com 1.7. Два класса задач: OLTP и DSS системы 1) OLTP-системы – системы оперативной обработки транзакций. Исторически такие системы возникли в первую очередь, из-за того, что аналитики реализовывали потребности в учете, скорости обслуживания, сборе данных и пр. Однако вскоре пришло понимание, что сбор данных — не самоцель, и накопленные данные могут быть полезны: из данных можно извлечь информацию. OLTP-системы характеризуются большим количеством изменений, одновременным обращением множества пользователей к одним и тем же данным для выполнения разнообразных операций – чтения, записи, удаления или модификации данных. Для нормальной работы множества пользователей применяются блокировки и транзакции. Эффективная обработка транзакций и поддержка блокировок входят в число важнейших требований к системам оперативной обработки транзакций. Основная функция подобных систем заключается в одновременном выполнении большого количества коротких транзакций от большого числа пользователей. Практически все запросы к базе данных в OLTP-системах состоят из команд вставки, обновления, удаления. Запросы на выборку в основном предназначены для предоставления пользователям возможности выбора из различных справочников. Большая часть запросов, таким образом, известна заранее еще на этапе проектирования системы. Таким образом, критическим для OLTP-приложений является скорость и надежность выполнения коротких операций обновления данных. Системы OLTP характеризуются поддержкой большого числа пользователей, малым временем отклика на запрос, относительно короткими запросами, участие в запросах небольшого числа таблиц. 2) DSS-системы – системы поддержки принятия решений. Это системы, ориентированные на анализ данных, на выполнение более сложных запросов, моделирование процессов предметной области, прогнозирование, нахождение зависимостей между данными (например, можно попытаться определить, как связан объем продаж товаров с характеристиками покупателей), для проведения анализа "что если" – аналитические системы. Под DSS понимают человеко-машинный вычислительный комплекс, ориентированный на анализ данных и обеспечивающий получение информации, необходимой для принятия решений в сфере управления. Характеристики DSS: использование больших объемов данных; добавление в систему новых данных происходит относительно редко крупными блоками (например, раз в квартал загружаются данные по итогам квартальных продаж из OLTP-приложения); данные, добавленные в систему, обычно никогда не удаляются; перед загрузкой, данные проходят различные процедуры "очистки", связанные с тем, что в одну систему могут поступать данные из многих источников, имеющих различные форматы представления для одних и тех же понятий, данные могут быть некорректны, ошибочны; небольшое число пользователей (аналитиков); очень часто новый запрос формулируется аналитиком для уточнения результата, полученного в результате предыдущего запроса (интерактивность); скорость выполнения запросов важна, но не критична. 9 PDF created with pdfFactory Pro trial version www.pdffactory.com Перечисленные характеристики требуют особой организации данных, отличных от тех, что используются в OLTP-системах. 1.8. Неэффективность использования OLTP для анализа данных Практика использования OLTP-систем показала неэффективность их применения для полноценного анализа информации. Такие системы достаточно успешно решают задачи сбора, хранения и поиска информации, но они не удовлетворяют требованиям, предъявляемым к современным СППР. Подходы, связанные с наращиванием функциональности OLTP-систем, не дали удовлетворительных результатов. Основной причиной неудачи является противоречивость требований, предъявляемым к системам OLTP и СППР. Степень детализации хранимых данных – типичный запрос в OLTP-системе, как правило, выборочно затрагивает отдельные записи в таблицах, которые эффективно извлекаются с помощью индексов. В системах анализа, наоборот, требуется выполнять запросы сразу над большим количеством данных с широким применением группировок и обобщений (суммирования, агрегирования). Качество данных – OLTP-системы, как правило, хранят информацию, вводимую непосредственно пользователями систем (операторами ЭВМ). Присутствие «человеческого фактора» при вводе повышает вероятность ошибочных данных и может создавать локальные проблемы в системе. При анализе ошибочные данные могут привести к неправильным выводам и принятию неверных стратегических решений. Формат хранения данных – OLTP-системы, обслуживающие различные участки работы, не связаны между собой. Они часто реализуются на разных программно – аппаратных платформах. Одни и те же данные в разных базах могут быть представлены в различном виде и могут не совпадать. В процессе анализа такое различие форматов чрезвычайно затрудняет совместный анализ этих данных. Поэтому к системам анализа предъявляется требование единого формата. Как правило, необходимо, чтобы этот формат был оптимизирован для анализа данных (нередко за счет их избыточности). Допущение избыточности данных – структура базы данных, обслуживающей OLTP-систему, обычно довольно сложна. Она может содержать многие десятки и даже сотни таблиц, ссылающихся друг на друга. Данные в такой БД сильно нормализованы для оптимизации занимаемых ресурсов. Аналитические запросы к БД очень трудно формулируются и крайне неэффективно выполняются, поскольку содержат в себе представления, объединяющие большое количество таблиц. При проектировании систем анализа стараются максимально упростить схему БД и уменьшить количество таблиц, участвующих в запросе. С этой целью часто допускают денормализацию (избыточность данных) в БД. Управление данными – основное требование к OLTP-системам – обеспечить выполнение операций модификации над БД. При этом предполагается, что они должны выполняться в реальном режиме, и часто очень интенсивно. В отличие от OLTP-систем данные в системах анализа меняются редко. Единожды попав в систему, данные уже практически не изменяются. Ввод новых данных, как правило, 10 PDF created with pdfFactory Pro trial version www.pdffactory.com носит эпизодический характер и выполняется в периоды низкой активности системы. Количество хранимых данных – как правило, системы анализа предназначены для анализа временных зависимостей, в то время как OLTP-системы обычно имеют дело с текущими значениями каких – либо параметров. В OLTP-системах допускается хранение данных за небольшой период времени. Для анализа данных, наоборот, необходимы сведения за максимально большой интервал времени. Характер запросов к данным – в OLTP-системах из-за нормализации БД составление запросов является достаточно сложной работой и требует необходимой квалификации. Поэтому для таких систем заранее составляется некоторый ограничительный набор статистических запросов к БД, необходимый для работы с системой. Для СППР невозможно заранее определить необходимые запросы, поэтому к ним предъявляется требование обеспечить формирование произвольных запросов к БД аналитиками. Время обработки обращений к данным – OLTP-системы, как правило, работают в режиме реального времени, поэтому к ним предъявляются жесткие требования по обработке данных. В системах анализа, по сравнению с OLTP, обычно выдвигают значительно менее жесткие требования ко времени выполнения запроса. При анализе данных аналитик может потратить больше времени для проверки своих гипотез. Его запросы могут выполняться в диапазоне от нескольких минут до нескольких часов. Характер вычислительной нагрузки на систему – работа с OLTP-системами, как правило, выполняется в режиме реального времени. В связи с этим такие системы нагружены равномерно в течение всего интервала времени работы с ними. Аналитик при работе с системой анализа обращается к ней для проверки некоторых своих гипотез и получения отчетов, графиков, диаграмм. При выполнении запросов степень загрузки системы высокая, т.к. обрабатывается большое количество данных, выполняются операции суммирования, группирования и т.д. Таким образом, характер загрузки систем анализа является пиковым. Приоритетность характеристик системы – для OLTP-систем приоритетным является высокая производительность и доступность данных, т.к. работа с ними ведется в режиме реального времени. Для систем анализа наиболее приоритетными являются задачи обеспечения гибкости системы и независимости работы пользователей. Противоречивость требований к OLTP-системам, ориентированным на глубокий анализ информации, усложняет задачу интеграции их как подсистем единой СППР. В настоящее время наиболее популярным решением этой проблемы является подход, ориентированный на использование концепции хранилищ данных. Общая идея хранилищ данных заключается в разделении БД для OLTP-систем и БД для выполнения анализа и последующим их проектировании с учетом соответствующих требований. 11 PDF created with pdfFactory Pro trial version www.pdffactory.com 1.9. Статические и динамические DSS Аналитические системы, ориентированные на аналитика, можно разделить на статические DSS, известные в литературе как информационные системы руководителя (Executive Information Systems – EIS) и динамические DSS. EIS-системы содержат в себе предопределенные множества запросов и, будучи достаточными для повседневного обзора, неспособны ответить на все вопросы к имеющимся данным, которые могут возникнуть при принятии решений. Результатом работы такой системы, как правило, являются многостраничные отчеты, которые нельзя "покрутить", "развернуть" или "свернуть", чтобы получить желаемое представление данных и после тщательного изучения которых, у аналитика появляется новая серия вопросов. Вторая группа (динамические DSS), напротив, ориентированы на обработку нерегламентированных (ad hoc) запросов аналитиков к данным. Наиболее глубоко требования к таким системам рассмотрел в 1993 г. E. F. Codd, положивший начало концепции OLAP. В последние годы в этом направлении оформился ряд новых концепций хранения и анализа корпоративных данных: − концепция хранилища данных (Data Warehouse); − оперативная аналитическая обработка OLAP (On-Line Analytical Processing); − интеллектуальный анализ данных (Data Mining). Концепция хранилища данных определяет процесс сбора, отсеивания, предварительной обработки и накопления данных с целью: − долговременного хранения данных; − предоставления результирующей информации пользователям в удобной форме для статистического анализа и создания аналитических отчетов. Концепция OLAP – концепция комплексного многомерного анализа данных, накопленных в хранилище. Теоретически средства OLAP можно применять и непосредственно к оперативным данным или их точным копиям (чтобы не мешать оперативным пользователям). П р и м е ч а н и е : термин OLAP очень популярен в настоящее время и OLAPсистемой зачастую называют любую DSS-систему, основанную на концепции хранилищ данных и обеспечивающих малое время выполнения (On-Line) аналитических запросов, независимо от того, используется ли многомерный анализ данных, что не совсем верно. Термин OLAP был предложен в 1993 г. Эдвардом Коддом (E.Codd – автор реляционной модели данных). По Кодду OLAP-технология это технология комплексного динамического синтеза, анализа и консолидации больших объемов многомерных данных. Концепция интеллектуального анализа данных определяет задачи поиска функциональных и логических закономерностей в накопленной информации, построение моделей и правил, которые объясняют найденные аномалии и прогнозируют развитие некоторых процессов. Структура информационно-аналитической системы, построенной на основе хранилища данных, представлена на рисунке 2. 12 PDF created with pdfFactory Pro trial version www.pdffactory.com Рис. 2. Структура информационно-аналитической системы 2. Подготовка данных к анализу Очень часто в аналитических приложениях сосредотачивают усилия на механизмах анализа данных, не уделяя должного внимания задачам предобработки и очистки данных. Хотя именно плохое «качество» исходных данных является одной из самых серьезных и распространенных проблем. Очевидно, что некорректные исходные данные приводят к некорректным выводам. А в связи с тем, что в большинстве случаев источником информации для аналитических систем является хранилище данных, в котором аккумулируются сведения из множества разнородных источников, острота проблемы существенно возрастает. 2.1. Структура подсистем подготовки данных Необходимость предварительной обработки при анализе данных возникает независимо от того, какие технологии и алгоритмы используются. Более того, эта задача может представлять самостоятельную ценность в областях, не имеющих непосредственного отношения к анализу данных. При использовании же механизмов анализа, в основе которых лежат самообучающиеся алгоритмы, такие как нейронные сети, деревья решений и прочее, хорошее качество данных является ключевым требованием. Очевидно, что исходные «сырые» данные чаще всего нуждаются в очистке. В процессе этого восстанавливаются пропущенные данные, редактируются аномальные значения, вычитается шум, проводится сглаживание и другие операции. При этом используются большой набор математических методов, таких как 13 PDF created with pdfFactory Pro trial version www.pdffactory.com алгоритмы робастной фильтрации, спектрального и Вейвлет анализа, последовательной рекуррентной фильтрации, статистического анализа. Но термин «предобработка» можно трактовать шире, а именно как процесс предварительного экспресс-анализа данных. Например, оценить фактор как значимый или нет, все ли факторы учтены для объяснения поведения результирующей величины и т.д. Для этих целей используются такие алгоритмы, как корреляционный анализ, факторный анализ, метод главных компонент, регрессионный анализ. Кроме того, очень часто в процессе предобработки необходимо проводить различного рода вспомогательные операции, например, фильтрацию данных по условиям, расчет относительных показателей, замену значений и т.п. Данные действия не используют сколь либо серьезный математический аппарат, но являются совершенно необходимыми этапами в процессе подготовки данных для последующего анализа. Таким образом, для полноценного анализа данных необходимо к сырым данным первоначально последовательно применить различные методы предобработки данных и только после этого приступать, собственно, к анализу. Аналитическая платформа должна содержать набор методов, позволяющий пройти все этапы предобработки очистки данных в едином приложении, позволяющие решать задачи фильтрации, восстановления пропущенных данных, редактирования аномальных значений, сглаживания, очистки от шумов, обнаружения дубликатов/противоречий и множество задач очистки. Обобщенная схема системы подготовки данных к анализу представлена на рисунке 3. Блок сбора и первичной подготовки данных осуществляет связывание с оперативными источниками данных, чтение информации из них и выполняет первичные операции по очистке данных: − расщепление атрибутов; − проверку допустимости и исправления; − стандартизацию; − сопоставление данных, относящихся к одному элементу; − слияние записей; − исключение дублирующих записей. Собранные и прошедшие первичную очистку данные поступают в блок, выполняющий их профайлинг. Результаты предварительного анализа собранного набора данных передаются менеджеру подготовки и блокам определения правил подготовки данных и их тестирования. Сформированные и проверенные этими модулями правила подготовки данных передаются менеджеру, осуществляющему управление процедурами, выполняемыми в ходе подготовки данных к анализу. Поток данных, поступивших в систему, последовательно проходит модули удаления выбросов, заполнения пропущенных значений, фильтрации и сглаживания и подсистему прореживания. Подсистема прореживания данных осуществляет их децимацию, агрегацию и обработку. Выходные потоки исходных данных, прошедших подготовку, поступают в хранилище, витрину или базу данных системы 14 PDF created with pdfFactory Pro trial version www.pdffactory.com аналитической обработки, разделяясь на потоки прошедшие и не прошедшие прореживание. Рис. 3. Структура системы подготовки данных к анализу 2.2. Этапы и методы подготовки данных Процесс подготовки данных включает в себя несколько этапов: − выявление проблем в данных (профайлинг). Профайлинг ориентирован на грубый анализ отдельных атрибутов для получения общей информации об исходном наборе данных, такой как тип, длина, спектр значений, частота, изменение, уникальность, наличие неопределенных значений и т.д., что позволяет обеспечить точное представление различных аспектов качества атрибута; − определение правил подготовки данных. На этом этапе необходимо выработать правила преобразования, часть из которых должна быть представлена программными инструментами системы подготовки данных; − тестирование правил подготовки данных. Корректность и эффективность правил подготовки данных должны тестироваться и оцениваться, например, на копиях данных источников. Это необходимо для выяснения необходимости корректировки правил с целью их улучшения или исправления ошибок; 15 PDF created with pdfFactory Pro trial version www.pdffactory.com − непосредственная подготовка данных. На этом этапе выполняются преобразования в соответствии с определенными ранее правилами. Над отдельными оперативными источниками данных выполняются следующие процедуры: − расщепление атрибутов – извлечение значений из атрибутов свободного формата для повышения точности представления и поддержки соответствующих этапов подготовки данных; − проверка допустимости и исправления – исследование каждого элемента данных на наличие ошибок. Обнаруженные ошибки исправляются по возможности автоматически; − стандартизация – преобразование данных в согласованный и унифицированный формат, что необходимо для дальнейшего их согласования и интеграции; − сопоставление данных, относящихся к одному элементу – устранение противоречивости и дублирования данных, полученных из различных источников; − слияние записей – объединение интегрированных записей, относящихся к одному объекту, выполняемое, если информация из разных записей дополняет или корректирует друг друга; − исключение дубликатов – удаление дублирующихся записей. Особое внимание в процессе подготовки данных к анализу следует уделить процедурам прореживания данных. Это вызвано тем, что в современных базах данных накапливаются огромные объемы информации, характеризующей некоторый объект, процесс или явление. Проведение анализа для большого массива данных с использованием сложных математических методов и алгоритмов приводит к большим вычислительным затратам на анализ, требует значительных вычислительных ресурсов и времени, что сказывается на оперативности проведения анализа. В ряде случаев, при аналитической обработке временных и аналогичных им последовательностных наборов данных в качестве прореживающей процедуры может быть применена агрегация – процедура слияния нескольких, связанных временными границами, значений в одно, например, ежесуточный набор данных может быть преобразован в еженедельный, ежемесячный и т.д. Необходимость предварительной обработки при анализе данных возникает независимо от того, какие технологии и алгоритмы используются. При использовании механизмов анализа, в основе которых лежат самообучающиеся алгоритмы, такие как нейронные сети, деревья решений и прочее, хорошее качество данных является ключевым требованием. Стандартные методы спектрального оценивания с использованием быстрого вычислительного алгоритма, именуемого быстрое преобразование Фурье, основаны на модели представления данных с помощью рядов Фурье, то есть анализируемый процесс полагается состоящим из некоторого набора гармонически связанных синусоид. В нетехнических областях в течение многих лет используются модели на основе других временных рядов. 16 PDF created with pdfFactory Pro trial version www.pdffactory.com Система подготовки данных к анализу предназначена для проведения процедур очистки, прореживания и экспресс-анализа данных. К ним относятся: − профайлинг; − определение правил очистки и подготовки данных; − тестирование правил очистки данных; − восстановление пропущенных значений; − редактирование аномальных значений; − обнаружение и редактирование дубликатов и противоречий; − вычитание шума; − проведение сглаживания; − фильтрация; − прореживание, включающее децимацию, агрегацию и другие методы прореживания; − оценка значимости факторов поведения результирующей величины. Большинство систем сбора информации вносит в данные ложные значения. Это может происходить по многим причинам, например, в результате технических сбоев или ошибки оператора. Неправдоподобные значения, возникающие в результате этих сбоев, могут вызвать значительные трудности при последующем анализе или сделать его совсем невозможным. Алгоритмы подавления неправдоподобных выбросов основываются на робастной (устойчивой) оценке средней скорости изменения временного ряда. В режиме фильтрации нижних частот можно ограничить верхнюю частоту спектра. При этом, из исходного сигнала удаляются высокочастотные составляющие, и меняется степень сглаживания исходного процесса. В процессе вычитания шума оценивается распределение спектральных составляющих по амплитуде и, полагая, что шумовые составляющие распределены по релеевскому закону, вычисляется порог, при превышении которого составляющая проходит на выход фильтра, в противном случае – отбрасывается. 2.3. Децимация, фильтрация Децимация В отличие от процедуры интерполяции преобразование выборочных значений сигнала к более низкой частоте дискретизации может являться источником специфической ошибки, которую часто называют подменой частот. Эффект подмены частот проявляется при выборе слишком низкой частоты дискретизации сигнала, т. е. ниже удвоенной максимальной частоты Фурье-спектра сигнала. В этом случае нарушаются условия теоремы Котельникова и высокочастотные гармоники сигнала или гармоники, частота которых выше половины выбранной частоты дискретизации, воспринимаются в полученной выборке как низкочастотные гармоники, т. е. гармоники, частота которых ниже половины частоты дискретизации. Чтобы избежать этого стробоскопического эффекта требуется подавить высокочастотные гармоники сигнала, частота которых выше половины выбранной 17 PDF created with pdfFactory Pro trial version www.pdffactory.com частоты дискретизации сигнала. Для этого используются линейные цифровые фильтры низких частот. Децимацию с нецелым коэффициентом сжатия частоты дискретизации аппроксимируют дробью, числитель которой определяет интерполяцию сигнала в целое число раз, а знаменатель – децимацию сигнала также в целое число раз. Интерполяция сигнала была рассмотрена выше, поэтому достаточно рассмотреть децимацию сигнала с целочисленным коэффициентом сжатия частоты дискретизации. Реализация децимации сигнала с целым коэффициентом очевидна: выходная выборка должна содержать лишь каждый p-тый элемент исходной выборки, подвергнутой соответствующей цифровой фильтрации. При этом какого-либо определенного правила выбора типа фильтра не существует, так как помимо индекса децимации выбор типа фильтра диктуется многими факторами, в частности, используемым программным и аппаратным обеспечением. Более широко используются не рекурсивные цифровые фильтры или фильтры с конечной импульсной характеристикой (КИХ-фильтры), так как в этом случае требуется вычислять только каждый p-тый элемент исходной выборки. В этом состоит некоторое преимущество использования нерекурсивных цифровых фильтров при выполнении процедуры децимации цифровых сигналов. Фильтрация Необходимость в фильтрации данных возникает каждый раз, когда нужно отделить передаваемое сообщение от искажающего его шума. Цель процесса фильтрации данных, а это могут быть не только результаты физических измерений, но и экономические показатели деятельности фирмы, и результаты социологических исследований, и т. д. – наилучшее восстановление первоначального сигнала на фоне помехи, или определение наличия полезного сигнала, или разрешение (различение) нескольких сигналов, присутствующих во входной последовательности. Фильтр нижних частот Пусть на вход фильтра поступает сигнал, изображенный на рисунке 4а. Этот сигнал получен сложением двух синусоид разной частоты (рис.4б и 4в), при этом частота помехи выше максимальной частоты, пропускаемой фильтром. При этом получаем спектр входных данных (рис.4г). Обнулив все составляющие, превышающие граничную частоту фильтра, получаем выходной спектр (рис.4д). Выходной сигнал представлен на рисунке 4е. Таким образом, реализуется алгоритм фильтра нижних частот. То есть из всего многообразия гармонических составляющих входной последовательности отбираются лишь те, которые не превышают некоторую верхнюю частоту. Понятно, что таким же образом можно было выделить любую часть спектра, это был бы уже полосовой фильтр. Фильтр нижних частот можно использовать еще и для сглаживания данных. Представим, что есть ряд данных, изображенный на рисунке 5а. На выходе фильтра увидим следующее изображение (рис.5б). Физический смысл этого прост. Есть сравнительно медленно меняющийся полезный сигнал, и есть быстро флюктуирующая шумовая составляющая. 18 PDF created with pdfFactory Pro trial version www.pdffactory.com Рис. 4. Низкочастотная фильтрация Медленно меняющейся составляющей соответствует низкочастотная часть спектра, шуму – высокочастотные составляющие спектра. Отбрасывая последние, мы выделяем полезную составляющую. Остается решить вопрос, какие частоты пропускать и какие отбрасывать. Было бы хорошо, если бы мы знали спектр полезного сигнала. В этом случае можно было не просто отбрасывать шумовые составляющие спектра, но и (чтобы еще больше уменьшить шум на выходе) полезные брать с соответствующими весами (дело в том, что полезный спектр и шумовой перекрываются). К сожалению, часто неизвестны не только параметры полезного сигнала, но и статистические свойства помехи. Остается надежда на здравый смысл, опыт и интуицию. Рис. 5. Сглаживание данных с использованием ФНЧ 19 PDF created with pdfFactory Pro trial version www.pdffactory.com Предсказание поведения некоего процесса на заданный интервал времени возможно, только тогда, когда его автокорреляционная функция достаточно медленно стремиться к нулю и для заданного интервала еще не достигла его. С другой стороны, автокорреляционная функция и квадрат модуля спектра процесса связаны тем же преобразованием Фурье, одно из свойств которого – чем шире спектр, тем быстрее изменение во времени, и наоборот, медленно меняющиеся во времени процессы имеют узкий спектр. Вывод: прогноз тем точнее, чем уже спектр прогнозируемого процесса. И наоборот, всякий прогноз – неявное выделение низкочастотных составляющих исследуемого процесса, сужение спектра. Калмановская фильтрация В настоящее время широкое распространение получили адаптивные фильтры, в которых поступающая новая информация используется для непрерывной корректировки ранее сделанной оценки сигнала (сопровождение цели в радиолокации, системы автоматического регулирования в управлении и т.д.). Особенный интерес представляют адаптивные фильтры рекурсивного типа, известные как фильтры Калмана. Эти фильтры широко используются в контурах управления в системах автоматического регулирования и управления. Именно оттуда они и появились, подтверждением чему служит столь специфическая терминология, используемая при описании их работы, как пространство состояний. Одна из основных задач, требующих своего решения в практике нейронных вычислений – получение быстрых и надежных алгоритмов обучения НС. В этой связи может оказаться полезным использование в контуре обратной связи обучающего алгоритма линейных фильтров. Так как обучающие алгоритмы имеют итеративную природу, такой фильтр должен представлять собой последовательное рекурсивное устройство оценки. В задаче калмановской фильтрации требуется оценивать процессы, то есть находить текущие оценки изменяющегося во времени сигнала, искаженного помехой, и, в силу этого, недоступного непосредственному измерению. В общем случае вид алгоритмов фильтрации зависит от статистических свойств сигнала и помехи. Будем предполагать, что полезный сигнал – медленно меняющаяся функция времени, а помеха – некоррелированный шум. Будем использовать метод наименьших квадратов, опять же по причине отсутствия априорных сведений о вероятностных характеристиках сигнала и помехи. Вначале получим оценку текущего значения xn по имеющимся «k» последним . значениям временного ряда Z , Z ,Z ...Z n n −1 n−2 n − ( k − 1) Модель наблюдения определяется как: Z = HX + V , (1) где Z – это вектор–столбец, состоящий из наблюдаемых значений временного ряда ; Z ,Z ,Z ...Z n n −1 n−2 n − ( k − 1) V – вектор–столбец помехи ξ , ξ , искажающий истинный ,ξ ...ξ n n − 1 n − 2 n − (k − 1) сигнал. 20 PDF created with pdfFactory Pro trial version www.pdffactory.com Необходима некоторая модель исходного сигнала. При отсутствии априорной информации о вероятностных характеристиках сигнала и помехи остается только строить предположения. На языке специалистов это называется параметрическая модель. В данном случае оцениваются параметры именно этой модели. При выборе подходящей модели генерации сигнала вспомним о том, что любую аналитическую функцию можно разложить в ряд Тейлора. Поразительное свойство ряда Тейлора заключается в том, что форма функции на любом конечном расстоянии t от некой точки x=a однозначно определяется поведением функции в бесконечно малой окрестности точки x=a (речь идет о ее производных первого и высшего порядков). Таким образом, существование рядов Тейлора означает, что аналитическая функция обладает внутренней структурой с очень сильной связью. Если, например, ограничиться тремя членами ряда Тейлора, то модель генерации сигнала будет выглядеть как: (2) X n − i = F− i × X n , где: i2 1 −i xn 2 X n = x′n ; F− i = 0 1 − i . xn′′ 0 0 1 (3) При заданном порядке полинома (в примере он равен 2) устанавливает связь между n-ым значением сигнала во временной последовательности и (ni)-ым. Таким образом, оцениваемый вектор состояния в данном случае включает в себя, помимо собственно оцениваемого значения, первую и вторую производную сигнала. В теории автоматического управления такой фильтр назвали бы фильтром с астатизмом 2-го порядка. Матрица преобразования H для данного случая (оценка осуществляется по текущему и k-1 предшествующим выборкам) выглядит как: 1 −k H= − − 1 −2 1 1 k2 2 − . 2 (4) − 1 0 ,5 Все эти числа получаются из ряда Тейлора в предположении, что временной интервал между соседними наблюдаемыми значениями постоянный и равен 1. Задача фильтрации при принятых предположениях свелась к задаче оценки параметров, в данном случае оцениваются параметры принятой нами модели генерации сигнала. И оценка значений вектора состояния X осуществляется по следующей формуле: X оц = ( H T × H )−1 × H T Z . Так реализуется процесс параметрического оценивания, основанный авторегрессионной модели процесса генерации сигнала. 21 PDF created with pdfFactory Pro trial version www.pdffactory.com (5) на Рассматриваемый фильтр реализуется программно, нужно заполнить матрицу H и вектор столбец наблюдений Z. Такие фильтры называются фильтрами с конечной памятью, так как для получения текущей оценки они используют последние k наблюдений. На каждом новом такте наблюдения к текущей совокупности наблюдений прибавляется новое и отбрасывается старое. Такой процесс получения оценок получил название скользящего окна. Фильтры с конечной памятью обладают тем основным недостатком, что после каждого нового наблюдения необходимо заново производить полный пересчет по всем хранящимся в памяти данным. Кроме того, вычисление оценок можно начинать только после того, как накоплены результаты первых k наблюдений. То есть эти фильтры обладают большой длительностью переходного процесса. Чтобы бороться с этим недостатком, необходимо перейти от фильтра с постоянной памятью к фильтру с растущей памятью. В таком фильтре число наблюдаемых значений, по которым производится оценка, должно совпадать с номером n текущего наблюдения. Это позволяет получать оценки, начиная с числа наблюдений, равного числу компонент оцениваемого вектора X. А это определяется порядком принятой модели, то есть, сколько членов из ряда Тейлора используется в модели. При этом с ростом n улучшаются сглаживающие свойства фильтра, то есть повышается точность оценок. Однако непосредственная реализация этого подхода связана с возрастанием вычислительных затрат. Поэтому фильтры с растущей памятью реализуются как рекуррентные. 3. Хранилища данных. Data Warehouse Стремление объединить в одной архитектуре СППР возможности OLTP-систем и систем анализа, требования к которым во многом противоречивы, привело к появлению концепции хранилищ данных. 3.1. Концепция хранилища данных Концепция хранилища данных (ХД), так или иначе, обсуждалась специалистами в области информационных систем достаточно давно. Первые статьи, посвященные именно ХД, появились в 1988 г., их авторами были Девлин и Мэрфи. В 1992 г. Уильман Г. Инмон подробно описал данную концепцию в своей монографии «Построение хранилищ данных». В основе концепции ХД лежит идея разделения данных, используемых для оперативной обработки и для решения задач анализа. Это позволяет применять структуры данных, которые удовлетворяют требованиям их хранения с учетом использования в OLTP – системах и системах анализа. Такое разделение позволяет оптимизировать как структуры данных оперативного хранения (оперативные БД, файлы, электронные таблицы) для выполнения операций ввода, модификации, удаления и поиска, так и структуры данных, используемые для анализа (для выполнения аналитических запросов). В СППР эти два типа данных называются соответственно оперативными источниками данных (ОИД) и хранилищем данных. Определение ХД по Инмону: Хранилище данных – предметно-ориентированный, интегрированный, неизменчивый, поддерживающий хронологию набор данных, организованный для целей поддержки принятия решений. 22 PDF created with pdfFactory Pro trial version www.pdffactory.com 3.2. ХД – многомерные кубы OLAP-технология представляет для анализа данные в виде многомерных (и, следовательно, нереляционных) наборов данных, называемых многомерными кубами (гиперкуб, метакуб, кубом фактов), оси которого содержат параметры, а ячейки – зависящие от них агрегатные данные. При том, гиперкуб является концептуальной логической моделью организации данных, а не физической реализацией их хранения, поскольку храниться такие данные могут и в реляционных таблицах ("реляционные БД были, есть и будут наиболее подходящей технологией для хранения корпорационных данных" – E.Codd). По Кодду, многомерное концептуальное представление (multi-dimensional conceptual view) представляет собой множественную перспективу, состоящую из нескольких независимых измерений, вдоль которых могут быть проанализированы определенные совокупности данных. Одновременный анализ по нескольким измерениям определяется как многомерный анализ. Осями многомерной системы координат служат основные атрибуты анализируемого бизнес-процесса (то, по чему ведется анализ). Например, для продаж это могут быть тип товара, регион, тип покупателя. В качестве одного из измерений используется время. На пересечениях осей-измерений (dimensions) – находятся данные, количественно характеризующие процесс – меры (measures): суммы и иные агрегатные функции (min, max, avg, дисперсия, ср. отклонение и пр.). Каждое измерение включает направления консолидации данных, состоящие из серии последовательных уровней обобщения (уровней иерархии), где каждый вышестоящий уровень соответствует большей степени агрегации данных по соответствующему измерению (различные уровни их детализации). В этом случае становится возможным произвольный выбор желаемого уровня детализации информации по каждому из измерений. Благодаря такой модели данных пользователи могут формулировать сложные запросы, генерировать отчеты, получать подмножества данных. П р и м е р 1 . Трехмерный куб, представленный на рисунке 6, где в качестве фактов использованы суммы продаж, а в качестве измерений – время, товар и магазин, определенных на разных уровнях группировки: товары группируются по категориям, магазины – по странам, а данные о времени совершения операций – по месяцам. Значения, «откладываемые» вдоль измерений, называются членами или метками (members). Метки используются в операциях манипулирования измерениями. Метки могут объединяться в иерархии, состоящие из одного или нескольких уровней детализации (levels). Например, метки измерения "Магазин" (Store) естественно объединяются в иерархию с уровнями: All (мир) Country (страна) State (штат) City (город) Store (магазин) 23 PDF created with pdfFactory Pro trial version www.pdffactory.com Рис. 6. Трехмерный куб В соответствии с уровнями иерархии вычисляются агрегатные значения, например, объем продаж для USA (уровень "Country") или для штата California (уровень "State"). В одном измерении можно реализовать более одной иерархии, скажем, для времени: {Год, Квартал, Месяц, День} и {Год, Неделя, День}. Поскольку в рассмотренном примере в общем случае в каждой стране может быть несколько городов, а в городе – несколько клиентов, можно говорить об иерархиях значений в измерении – регион. В этом случае на первом уровне иерархии располагаются страны, на втором – города, а на третьем – клиенты. Рис. 7. Сбалансированность иерархии Иерархии могут быть: − сбалансированными (balanced), как, например, иерархия, представленная на рисунке 7 (таковы же иерархии, основанные на данных типа "дата-время"); 24 PDF created with pdfFactory Pro trial version www.pdffactory.com − несбалансированными (unbalanced). Типичный пример несбалансированной иерархии – иерархия типа "начальникподчиненный", изображенный на рисунке 8. Иногда для таких иерархий используется термин Parent-child hierarchy. Рис. 8. Несбалансированность иерархий Существуют также иерархии, занимающие промежуточное положение между сбалансированными и несбалансированными (они обозначаются термином ragged – "неровный"). Обычно они содержат такие члены, логические "родители" которых находятся не на непосредственно вышестоящем уровне (например, в географической иерархии есть уровни Country, City и State, но при этом в наборе данных имеются страны, не имеющие штатов или регионов между уровнями Country и City). Такой тип иерархий представлен на рисунке 9. Рис. 9. Неровность иерархий Данные для аналитических систем не набиваются вручную пользователем и не перекачиваются непосредственно из OLTP-систем, т. е. баз данных оперативной обработки. Аналитик должен располагать проверенными данными, отражающими реальную ситуацию в бизнесе. Для создания достоверной картины и предназначены хранилища данных (Data Warehouses) – непротиворечивые интегрированные источники данных, собранные из многих других источников и внешних словарей и 25 PDF created with pdfFactory Pro trial version www.pdffactory.com зачастую представленных в специальных, удобных для анализа структурах. В рамках одной системы предполагается наличие избыточности данных для повышения скорости выполнения аналитических запросов. 3.3. Неудачи проектов по созданию ХД Бум развития хранилищ данных (ХД) пришелся на конец 90-х годов. Сегодня для многих технология хранилищ данных олицетворяет огромные массивы собранной информации, на создание которых затрачены масса времени и колоссальные средства, не окупившиеся и на сегодняшний день. Многие проекты по созданию хранилищ данных действительно заканчивались провалом, однако не стоит преждевременно хоронить идеи, разумное применение которых уже неоднократно приносило огромные прибыли. Неудачи проектов по созданию ХД зачастую объясняются желанием интегрировать «всё и вся» и в результате получить единый источник информации для всех подразделений компании. Чем больше источников данных было вовлечено в этот процесс, тем сложнее становилось получить работающую высокопроизводительную систему. ХД по определению ориентировано на потребности конечных пользователей – аналитиков, а не на функциональность какого-либо приложения. В этой связи логично и разумно ограничиваться требованиями отдельной группы аналитиков, работающих в рамках одной тематики. Практически одновременно с понятием хранилищ данных появился термин "витрины данных" (Data Marts), означающий по сути ХД для отдельной группы пользователей. 3.4. Витрины данных. Data Marts Изначально предлагалось использовать витрины данных над хранилищем как его подмножества на уровне детальных данных с необходимыми собственными агрегациями. В современной литературе довольно редко встречается термин "витрины данных", а под хранилищами теперь понимают массивы информации, пригодные и специально подготовленные для аналитической обработки. Все компоненты системы, от источников данных, до пользовательских мест, могут быть, как физически распределены, так и локализованы на одном компьютере. Витрина данных (ВД) – это упрощенный вариант ХД, содержащий только тематически объединенные данные. ВД максимально приближена к конечному пользователю и содержит данные, тематически ориентированные на него. ВД существенно меньше по объему, чем ХД, и для ее реализации не требуется больших затрат. Они могут быть реализованы как самостоятельно, так и вместе с ХД. Достоинства самостоятельных ВД: − проектирование ВД для ответов на определенный круг вопросов; − быстрое внедрение автономных ВД и получение отдачи; − упрощение процедур заполнения ВД и повышение их производительности за счет учета потребностей определенного круга пользователей. 26 PDF created with pdfFactory Pro trial version www.pdffactory.com Недостатки: − многократное хранение данных в разных ВД, что приводит к увеличению расходов на их хранение и потенциальным проблемам, связанным с необходимостью поддержания непротиворечивости данных; − отсутствие консолидированности данных на уровне предметной области, а, следовательно – отсутствие единой картины. В случае совместимости ХД и ВД в одной системе, ХД используется в качестве единственного источника интегрированных данных для всех ВД. Достоинства: − простота создания и наполнения ВД, поскольку наполнение происходит из единого стандартизованного надежного источника очищенных данных – из ХД; − простота расширения СППР за счет добавления новых ВД; − снижение нагрузки на основное ХД. Недостатки: − избыточность (данные хранятся как в ХД, так и в ВД); − дополнительные затраты на разработку СППР с ХД и ВД. 3.5. Эффективность архитектур ХД StatSoft определяет понятие хранилища данных как способ хранения больших многомерных массивов данных, который позволяет легко извлекать и использовать информацию в процедурах анализа. Эффективная архитектура хранилища данных должна быть организована таким образом, чтобы быть составной частью информационной системы управления предприятием (или, по крайней мере, иметь связь со всеми доступными данными). При этом необходимо использовать специальные технологии работы с корпоративными базами данных (например, Oracle, Sybase, MS SQL Server). Высокопроизводительная технология хранилищ данных, позволяющая пользователям организовать и эффективно использовать базу данных предприятия практически неограниченной сложности, разработана компанией StatSoft enterprise Systems и называется SENS [STATISTICA Enterprise System] и SEWSS [STATISTICA Enterprise-Wide SPC System]. Большинство хранилищ используют технологию реляционных баз данных, поскольку она предлагает надежные, проверенные и эффективные средства хранения и управления большими объемами данных. Важнейший вопрос, связанный с конструированием хранилищ данных – архитектура базы данных, как логическая, так и физическая. Создание логической схемы корпоративного хранилища данных требует всеобъемлющего моделирования бизнеса. Архитектура ХД приведена на рисунке 10. Менеджер загрузки (load manager) выполняет операции, связанные с извлечением и загрузкой данных в хранилище. Менеджер хранилища (warehouse manager) выполняет операции, связанные с управлением информацией, помещенной в хранилище данных. Это операции анализа непротиворечивости данных; создания индексов и представлений для базовых таблиц; денормализации данных; обобщения данных; резервного хранения и архивирования. 27 PDF created with pdfFactory Pro trial version www.pdffactory.com Рис. 10. Типичная архитектура хранилища данных Менеджер запросов (query manager) выполняет операции, связанные с управлением пользовательскими запросами. Создание хранилища данных из независимых источников данных — многоэтапный процесс, который предусматривает извлечение данных из каждого источника, преобразование их в соответствии со схемой хранилища данных, очистку, а затем загрузку в хранилище. 3.6. Основные свойства ХД Предметная ориентация – является фундаментальным отличием ХД от ОИД (оперативный источник данных). Разные ОИД могут содержать данные, описывающие одну и ту же предметную область с разных точек зрения. Решение, принятое на основе одной точки зрения, может быть неэффективным или даже неверным. ХД позволяют интегрировать информацию, отражающую разные точки зрения на одну предметную область. Предметная ориентация позволяет также хранить в ХД только те данные, которые нужны для их анализа (например, для анализа нет необходимости хранить информацию о номерах документов купли-продажи, в то время как их содержимое – количество, цена проданного товара просто необходимо). Это существенно сокращает затраты на носители информации и повышает безопасность доступа к данным. Интеграция – ОИД, как правило, разрабатывается в разное время несколькими коллективами с собственным инструментарием. Это приводит к тому, что данные, отражающие один и тот же объект реального мира в разных системах, описывают 28 PDF created with pdfFactory Pro trial version www.pdffactory.com его по-разному. Обязательная интеграция данных в ХД позволяет решить эту проблему, приведя данные к единому формату. Поддержка хронологии – данные в ОИД необходимы для выполнения над ними операций в текущий момент времени, поэтому они могут не иметь привязки ко времени. Для анализа данных часто важно иметь возможность отслеживать хронологию изменений показателей предметной области. Поэтому все данные, хранящиеся в ХД, должны соответствовать последовательным интервалам времени. Неизменяемость – требования к ОИД накладывают ограничения на время хранения в них данных. Те данные, которые не нужны для оперативной обработки, как правило, удаляются из ОИД для уменьшения занимаемых ресурсов. Для анализа, наоборот, требуются данные за максимально больший период времени. Поэтому, в отличии от ОИД, данные в ХД после загрузки только читаются. Это позволяет существенно повысить скорость доступа к данным, как за счет возможной избыточности хранящейся информации, так и за счет исключения операций модификации. При реализации в СППР концепции ХД данные из разных ОИД копируются в единое хранилище. Собранные данные приводятся к единому формату, согласовываются и обобщаются. Аналитические запросы адресуются к ХД (рис.11). Такая модель неизбежно приводит к дублированию информации в ОИД и в ХД. При загрузке информации из ОИД в ХД данные фильтруются. Многие из них не попадают в ХД, поскольку лишены смысла с точки зрения использования в процедурах анализа. Информация в ОИД носит, как правило, оперативный характер, и данные, потеряв актуальность, удаляются. В ХД, напротив, хранится историческая информация. Таким образом, дублирование содержимого ХД данными ОИД оказывается весьма незначительным. В ХД хранится обобщенная информация, которая в ОИД отсутствует. Во время загрузки в ХД данные очищаются и приводятся к единому формату. После такой обработки данные занимают гораздо меньший объем. Избыточность информации можно свести к нулю, используя виртуальное ХД. В данном случае в отличие от классического ХД, данные из ОИД не копируются в единое хранилище. Они извлекаются, преобразуются и интегрируются непосредственно при выполнении аналитических запросов в оперативной памяти компьютера. Фактически такие запросы напрямую адресуются к ОИД. Основными достоинствами виртуального ХД являются: − минимизация объема памяти, занимаемой на носителе информацией; − работа с текущими, детализированными данными. Однако такой подход обладает многими недостатками. Время обработки запросов к виртуальному ХД значительно превышает соответствующие показатели для физического хранилища. Кроме того, структуры оперативных БД, рассчитанные на интенсивное обновление одиночных записей, в высокой степени нормализованы. Для выполнения же аналитического запроса требуется объединение большого числа таблиц, что также приводит к снижению быстродействия. 29 PDF created with pdfFactory Pro trial version www.pdffactory.com Рис. 11. Структура СППР с физическим ХД Интегрированный взгляд на виртуальное хранилище возможен только при выполнении условия постоянной доступности всех ОИД. Таким образом, временная недоступность хотя бы одного из источников может привести либо к невыполнению аналитических запросов, либо к неверным результатам. Выполнение сложных аналитических запросов над ОИД занимает большой объем ресурсов компьютеров, на которых они работают. Это приводит к снижению быстродействия OLTP-систем, что недопустимо, т.к. время выполнения операций в таких системах часто весьма критично. Различные ОИД могут поддерживать разные форматы и кодировки данных. Часто на один и тот же вопрос может быть получено несколько вариантов ответа. Это может быть связано с несинхронностью моментов обновления данных в разных ОИД, отличиями в описании одинаковых объектов и событий предметной области, ошибками при вводе, утерей фрагментов архивов и т.д. В таком случае цель – формирование единого непротиворечивого взгляда на объект управления – может быть не достигнута. Главным же недостатком виртуального хранилища следует признать практическую невозможность получения данных за долгий период времени. При отсутствии физического хранилища доступны только те данные, которые на момент 30 PDF created with pdfFactory Pro trial version www.pdffactory.com запроса есть в ОИД. Основное назначение OLTP-систем – оперативная обработка текущих данных, поэтому они не ориентированны на хранение данных за длительный период времени. По мере устаревания данные выгружаются в архив и удаляются из оперативной БД. Несмотря на преимущества физического ХД перед виртуальным, необходимо признать, что его реализация представляет собой достаточно трудоемкий процесс. 3.7. Основные проблемы создания ХД Необходимость интеграции данных из неоднородных источников в распределенной среде – хранилища данных создаются для интегрирования данных, которые могут поступать из разнородных ОИД, физически размещающихся на разных компьютерах: БД, электронных архивов, публичных и коммерческих электронных каталогов, справочников, статистических сборников. При создании ХД приходится решать задачу построения системы, согласованно функционирующей с неоднородными программными средствами и решениями. Потребность в эффективном хранении и обработке очень больших объемов информации – свойство неизменности ХД предполагает накопление в нем информации за долгий период времени, что должно поддерживаться постоянным ростом объемов дисковой памяти. Необходимость многоуровневых справочников метаданных – для систем анализа наличие развитых метаданных (данных о данных) и средств их предоставления конечным пользователям является одним из основных условий успешной реализации ХД. Метаданные необходимы пользователям СППР для понимания структуры информации, на основании которой принимается решение. При создании ХД необходимо решать задачи хранения и удобного представления метаданных пользователям. Повышение требований к безопасности данных – собранная вместе и согласованная информация об истории развития корпорации, ее успехах и неудачах, о взаимоотношениях с поставщиками и заказчиками, об истории и состоянии рынка дает возможность анализа прошлой и текущей деятельности корпорации и построения прогнозов для будущего. Очевидно, что такая информация является конфиденциальной и доступ к ней ограничен в пределах самой компании, не говоря уже о других компаниях. Для обеспечения безопасности данных приходится решать вопросы аутентификации пользователей, защиты данных при их перемещении в хранилище данных из оперативных баз данных и внешних источников, защиты данных при их передаче по сети и т.д. Снижение затрат на создание ХД можно добиться, создавая его упрощенный вариант – витрину данных. 3.8. Организация ХД Все данные в ХД делятся на три основные категории (рис.12): − Детальные данные. − Агрегированные данные. − Метаданные. 31 PDF created with pdfFactory Pro trial version www.pdffactory.com Рис. 12. Архитектура ХД Детальными являются данные, переносимые непосредственно из ОИД. Они соответствуют элементарным событиям, фиксируемым OLTP-системами. Принято разделять все данные на измерения и факты. Измерениями называются наборы данных, необходимые для описания событий. Фактами называются данные, отражающие сущность события. Фактические данные могут быть представлены в виде числовых или категориальных значений. В процессе эксплуатации ХД необходимость в ряде детальных данных может снизиться. Ненужные детальные данные могут храниться в архивах в сжатом виде на более емких накопителях с более медленным доступом. Данные в архиве остаются доступными для обработки и анализа. Регулярно используемые для анализа данные должны храниться на накопителях с быстрым доступом. На основании детальных данных могут быть получены агрегированные (обобщенные) данные. Агрегирование происходит путем суммирования числовых фактических данных по определенным измерениям. В зависимости от возможности агрегировать данные они подразделяются на следующие типы: − аддитивные – числовые фактические данные, которые могут быть просуммированы по всем измерениям; 32 PDF created with pdfFactory Pro trial version www.pdffactory.com − полуаддитивные – числовые фактические данные, которые могут быть просуммированы только по определенным измерениям; − неаддитивные – фактические данные, которые не могут быть просуммированы ни по одному измерению. Те данные, к которым редко обращаются пользователи, могут вычисляться в процессе выполнения аналитических запросов. Данные, которые требуются более часто, должны храниться в ХД. Для удобства работы с ХД необходима информация о содержащихся в нем данных. Такая информация называется метаданными. Они должны отвечать на вопросы – что (описание объекта), кто (описание пользователей), где (описание места хранения), как (описание действий), когда (описание времени) и почему (описание причин). Так как метаданные играют важную роль в процессе работы с ХД, то к ним должен быть обеспечен удобный доступ. Для этого они сохраняются в репозитории метаданных с удобным для пользователя интерфейсом. 3.9. Информационные потоки Данные, поступающие из ОИД в ХД, перемещаемые внутри ХД и поступающие из ХД к аналитикам, образуют следующие информационные потоки: − входной поток (Inflow) – образуется данными, копируемыми в ХД из ОИД; − поток обобщений (Up flow) – образуется агрегированием детальных данных и их сохранением в ХД; − архивный поток (Down Flow) – перемещение детальных данных, обращение к которым снизилось; − поток метаданных (Meta flow) – перемещение информации о данных в репозиторий данных; − выходной поток (Out flow) – образуется данными, извлекаемыми пользователями; − обратный поток (Feedback Flow) – образуется очищенными данными, записываемыми обратно в ОИД. Самый мощный из информационных потоков – входной – связан с переносом данных из ОИД. При разработке ХД не менее 60 % всех затрат связано с переносом данных. 3.10. Перенос данных Процесс переноса, включающий в себя этапы извлечения, преобразования и загрузки, называется ETL-процессом (E – extraction, T – transformation, L – loading: извлечение, преобразование и загрузка, соответственно). Программные средства, обеспечивающие его выполнение, называются ETL-системами. Традиционно ETLсистемы использовались для переноса информации из устаревших версий информационных систем в новые. В настоящее время ETL-процесс находит все большее применение для переноса данных из ОИД в ХД и ВД. 33 PDF created with pdfFactory Pro trial version www.pdffactory.com Этапы ETL-процесса: Извлечение данных – чтобы начать ETL-процесс, необходимо извлечь данные из одного или нескольких источников и подготовить их к этапу преобразования. Можно выделить два способа извлечения данных: 1) Извлечение данных вспомогательными программными средствами непосредственно из структур хранения информации (файлов, электронных таблиц). Достоинством такого способа извлечения данных являются: − отсутствие необходимости расширять OLTP-систему; − данные могут извлекаться с учетом потребностей процесса переноса. 2) Выгрузка данных средствами OLTP-систем в промежуточные структуры. Достоинствами такого подхода являются: − возможность использовать средства OLTP-систем, адаптированные к структурам данных; − средства выгрузки изменяются вместе с изменениями OLTP-систем и ОИД; − возможность выполнения первого шага преобразования данных за счет определенного формата промежуточной структуры хранения данных. Преобразование данных – после того как сбор данных завершен, необходимо преобразовать их для размещения на новом месте. На этом этапе выполняются следующие процедуры: − обобщение данных; − перевод значений; − создание полей; − очистка данных. Наиболее важной задачей при переносе данных является их очистка. Основные проблемы очистки данных можно классифицировать по следующим уровням: − уровень ячейки таблицы; − уровень записи; − уровень таблицы БД; − уровень одиночной БД; − уровень множества БД. Очистка данных включает следующие этапы: выявление проблем в данных, определение правил очистки, тестирование правил очистки, непосредственно очистка данных. После исправления ошибок отдельных источников очищенные данные должны заменить загрязненные данные в исходных ОИД. Очищенные данные сохраняются в ХД и могут использоваться для анализа и принятия на их основе решений. За формирование аналитических запросов к данным и представление результатов их выполнения в СППР отвечают подсистемы анализа. От вида анализа также зависит и непосредственная реализация структур хранения данных в ХД. Загрузка данных – после того как данные преобразованы для размещения в ХД, осуществляется этап их загрузки. При загрузке выполняется запись преобразованных детальных и агрегированных данных. Кроме того, при записи новых детальных данных часть старых может переноситься в архив. Функции модулей, осуществляющих перенос данных: 34 PDF created with pdfFactory Pro trial version www.pdffactory.com − Менеджер загрузки (load manager) выполняет операции, связанные с извлечением и загрузкой данных в хранилище. − Менеджер хранилища (warehouse manager) выполняет операции, связанные с управлением информацией, помещенной в хранилище данных: анализ непротиворечивости данных; создание индексов и представлений для базовых таблиц; денормализация данных; обобщение данных; резервное хранение и архивирование. − Менеджер запросов (query manager) выполняет операции, связанные с управлением пользовательскими запросами. 3.11. Инструментарий хранилищ данных Создание хранилища данных из независимых источников данных – многоэтапный процесс, который предусматривает извлечение данных из каждого источника, преобразование их в соответствии со схемой хранилища данных, очистку, а затем загрузку в хранилище. Data Warehousing Information Center опубликовал обширный список инструментальных средств ETL (extract, transform, load – «извлечение, преобразование, загрузка»), выполняющих эту последовательность операций: − извлечение и преобразование; − очистка данных; − загрузка; − обновление; − управление метаданными. Цель этапа извлечения данных — перенести данные из разнородных источников в базу данных, где их можно модифицировать и добавить в хранилище. Цель последующего этапа преобразования данных — устранить несоответствия в схеме и соглашениях о значениях атрибутов. Набор правил и скриптов, как правило, выполняет преобразование данных из исходной схемы в итоговую схему. Дистрибьютор, к примеру, может разделить имя каждого клиента на три части: имя, отчество (или инициалы) и фамилия. Чтобы добавить предоставленную дистрибьютором информацию о продажах в хранилище, аналитик сначала должен извлечь записи, а затем, для каждой записи, преобразовать все столбцы с соответствующими тремя частями имени, чтобы получить значение для атрибута «Имя клиента». Ошибки при вводе данных и различия в схемах могут привести к тому, что таблица измерений «Клиент» будет иметь несколько соответствующих кортежей для одного клиента, что приводит к неточным ответам на запросы и некорректным моделям добычи данных. К примеру, если таблица клиентов содержит по несколько кортежей для некоторых клиентов в Нью-Йорке, то Нью-Йорк может ошибочно попасть в список первых 50 стран с самым большим числом индивидуальных клиентов. Инструменты, которые помогают определить и исправить аномалии данных, могут иметь высокую отдачу; значительное число исследований посвящено проблемам устранения дублирования и инструментам очистки данных. После того, как данные извлечены и преобразованы, возможно, что их еще необходимо дополнительно обработать перед тем, как добавить в хранилище. 35 PDF created with pdfFactory Pro trial version www.pdffactory.com Как правило, утилиты фоновой загрузки поддерживают такие функции, как проверка ограничений целостности; сортировка; суммирование, агрегирование и выполнение других вычислений для создания производных таблиц, размещаемых в хранилище; создание индексов и других способов доступа. Помимо наполнения хранилища, утилита загрузки должна позволять системным администраторам проверять статус; отменять, приостанавливать и возобновлять загрузку; возобновлять работу после ошибки без потери целостности данных. Поскольку утилиты загрузки для хранилищ данных обрабатывают значительно больше данных, чем содержится в транзакционных системах, они используют разного рода алгоритмы распараллеливания. Обновление хранилища данных состоит в распространении обновлений на исходные данные, которые соответственным образом пополняют базовые таблицы и производные данные, материализованные представления и индексы, размещенные в хранилище. Должны быть рассмотрены два основных вопроса: когда обновлять и как обновлять. Обычно хранилища данных обновляются периодически в соответствии с заранее установленным расписанием, например, ежедневно или еженедельно. Распространять каждое обновление необходимо только в том случае, если для выполнения OLAP-запросов требуются текущие данные. Администраторы хранилища данных определяют правила обновления в зависимости от требований пользователей и трафика. Расписание обновлений может быть различным для разных источников данных. Администратор должен выбрать циклы обновления таким образом, чтобы накладные расходы, вызванные обработкой больших объемов данных, не превысили расходы на выполнение утилиты инкрементальной загрузки. Большинство коммерческих инструментов используют инкрементальную загрузку при обновлении с тем, чтобы сократить объем данных, добавляя только измененные кортежи, если, конечно, источники данных позволяют извлекать соответствующие фрагменты данных. Метаданные – информация любого рода, которая требуется для управления хранилищем данных, а управление метаданными – существенный компонент архитектуры хранения. К административным метаданным относится вся информация, которая требуется для настройки и использования хранилища данных. Бизнес-метаданные включают в себя бизнес-термины и определения, принадлежность данных и правила оплаты услуг хранилища. Оперативные метаданные – это информация, собранная во время работы хранилища данных, такая как происхождение перенесенных и преобразованных данных; статус использования данных (активные, архивированные или удаленные); данные мониторинга, такие как статистика использования, сообщения об ошибках и результаты аудита. Метаданные хранилища часто размещаются в репозиторий, который позволяет совместно использовать метаданные различным инструментам и процессам при проектировании, установке, использовании, эксплуатации и администрировании хранилища. 36 PDF created with pdfFactory Pro trial version www.pdffactory.com 4. Оперативный анализ данных OLAP С концепцией многомерного анализа данных тесно связывают оперативный анализ, который выполняется средствами OLAP-систем. 4.1. Определение, назначение, общий принцип работы OLAP (On-Line Analytical Processing) – технология оперативной аналитической обработки данных, использующая методы и средства для сбора, хранения и анализа многомерных данных в целях поддержки процессов принятия решений. Основное назначение OLAP-систем – поддержка аналитической деятельности, произвольных запросов пользователей-аналитиков. Цель OLAP-анализа – проверка возникающих гипотез. Эдвард Кодд сформулировал 12 принципов OLAP, которые позже были переработаны в так называемый тест FASMI. Эти принципы будут рассмотрены в п.4.2. Если системы регламентированной отчетности отвечают на вопросы типа «сколько было продано товара?» или «какова прибыль за последний месяц», то OLAP призван дать ответы, скажем, на вопросы «насколько надо увеличить расходы на рекламу, чтобы прибыль выросла на 15%?» или «какие продукты будут в пятерке лучших по показателю прибыльности из наиболее продаваемых в Нижнем Новгороде?». Выражаясь математически, аналитик мыслит многомерными представлениями. Анализируя некоторый показатель, например, объем продаж, он отдает себе отчет, что определяются продажи, собственно, тем, каков интерес к конкретному товару, какой регион рассматривается и в какой момент времени. Таким образом, объем продаж может быть представлен в виде трехмерного (в нашем упрощенном примере) куба, гранями которого изображаются массивы данных по товарам, регионам и времени, а внутри куба находятся значения объема продаж. Выбирая конкретный товар, регион и временную точку, мы получаем соответствующий показатель объема продаж. Такое, простое, на первый взгляд, представление данных обеспечивает мощный механизм для аналитических запросов. Каждый из массивов данных (граней куба, или, как их называют, размерностей) может содержать не просто перечень значений, а набор деревьев, или иерархию значений, где верхнее значение иерархии раскрывается стоящими ниже и т. д. В каждом кубе обязательно присутствует иерархия времени. На верхнем уровне расположены годы (десятилетия), ниже – кварталы, затем месяцы, недели, дни. Уровень детализации, следующий ниже уровня дней, вряд ли будет интересовать пользователя в силу особенности аналитических задач – один час не меняет общей картины за месяц или квартал, т.е. не влияет на данные, интересующие аналитика. Для каждой размерности можно задать более одной иерархии и обобщать их с различных точек зрения. Что важно – все значения вычисляемого показателя будут физически храниться в иерархиях размерностей, т.е. вычислений «на лету» производиться не будет. В этом и состоит секрет эффективности выполнения операций аналитических запросов над многомерными представлениями, ведь аналитик должен получать ответ на одну из многих своих гипотез практически мгновенно. 37 PDF created with pdfFactory Pro trial version www.pdffactory.com Производители OLAP-систем обеспечивают скорость выполнения запросов в пределах одной секунды, максимум пяти. Однако не стоит уповать на эти цифры – эффективность работы конкретного приложения очень во многом определяется правильностью построения куба данных, сочетания числа размерностей с числом иерархий и уровнем детализации данных и даже порядком создания этих размерностей разработчиком. Например, в одном кубе не следует допускать более шести-семи размерностей, иначе затрудняется восприятие зависимостей самим аналитиком и существенно снижается производительность всей системы. В одном аналитическом приложении, как правило, существует несколько кубов данных, каждый из которых представляет анализируемый показатель. Для разных кубов может использоваться одна и та же размерность, причем фактически она будет не дублироваться, а разделяться. После наполнения куба данными возможно как дополнение, так и обновление значений размерностей. Значения на более высоких уровнях иерархии и значения внутри куба будут вычисляться автоматически. Такие обновления производятся не постоянно, а пакетным образом – раз в несколько дней, в зависимости от требований аналитических задач. Кубы данных могут быть как физически хранимыми, так и виртуальными, в терминологии это отражается в названиях "переменная" и "формула" соответственно. Можно создавать связи (отношения) между размерностями, например, различные категории товаров, хранящихся в одной размерности, связаны с различными подразделениями компании, эти товары производящими и выделенными в отдельную компанию. Все самое интересное с точки зрения OLAP-анализа начинается с применения этих немногих физических сущностей и функциональности, поддерживаемой клиентскими средствами. Простая, но достаточно важная операция над кубом данных – срез и вращение куба, т. е. фиксация одного или нескольких значений размерностей и просмотр показателя по другим. Современные интерфейсы позволяют пользователю реализовывать срезы и вращения на уровне drag-and-drop – с помощью мышки менять на экране местами размерности, столбцы со строками и т. д. Тем самым пользователь получает возможность анализировать показатель с различных точек зрения – товара или региона. Данные размерностей можно просматривать по различным уровням иерархии (например, время по кварталам и месяцам), а можно задавать и более сложные условия выборки или даже отдельные значения. Многие программные средства позволяют накладывать условия на анализируемый показатель, т.е. выбирать только значения показателя выше заданного (например, объем продаж более $150 000), или же минимальные и максимальные значения в каждом регионе отмечать отдельным цветом. Безусловно, наряду с табличным представлением поддерживается и графическое представление, со всеми возможными видами графиков – столбчатых, диаграмм, точками и линиями на координатной оси, двух и трехмерных. Любая операция вращения и среза данных выполняется моментально, перепостроение графика занимает доли секунды. Наиболее интересные и сложные возможности анализа данных заключаются в прогнозировании и выявлении тенденций. Подобные вычисления основаны на 38 PDF created with pdfFactory Pro trial version www.pdffactory.com построении функции экстраполяции на базе имеющегося (определяемого пользователем) набора исходных данных. Прогнозирование всегда существенно зависит от особенностей предметной области, поэтому универсальных алгоритмов экстраполяции не существует. Различные инструменты создания аналитических приложений содержат несколько алгоритмов, основанных на линейном, экспоненциальном тренде и учете сезонных колебаний. В ряде систем (например, Oracle Express) помимо этого предлагается мощный математический аппарат, позволяющий создавать собственные алгоритмы на основе известных законов, но не более того. Таким образом, точность прогноза реально определяется разработчиком системы. На практике использование прогнозирования максимально просто – пользователь задает интервал времени, на которое производится расчет. В виде таблицы или диаграммы отображается значение анализируемого показателя, известное для заданного интервала времени, и нажатием кнопки или вызовом функции меню вычисляются значения этого показателя на будущее. Другая интересная возможность OLAP-систем заключается в определении начальных условий по заданному желаемому результату. Примером такого запроса может служить приведенный в начале данного раздела вопрос: «на сколько надо увеличить расходы на рекламу, чтобы объем продаж увеличился на 15%?». Другим не менее распространенным видом аналитических запросов является анализ по принципу «что, если?». В этом случае аналитик имеет возможность менять значения показателей или размерностей, чтобы проследить зависимость от них результата. Современные OLAP-системы поддерживают многопользовательскую работу. Что же будет, если все вдруг начнут менять исходные данные? На самом деле изменения выполняются в отдельном адресном пространстве пользовательского приложения; реально исходные данные при этом не меняются. Для того чтобы внести изменения, пользователь должен обладать эксклюзивными правами. На это есть определенные технологические причины, зависящие от архитектуры аналитических систем и их взаимосвязи с хранилищами данных. П р и м е р 2 . Давайте вначале представим себе отчет в виде куба (рис.13), и данные, представляемые в кубе (рис.14). Рис. 13. Отчет 1 39 PDF created with pdfFactory Pro trial version www.pdffactory.com Рис. 14. Данные куба Теперь, если мы сложим значения во всех ячейках по вертикали, то получим следующий отчет (рис.15). Рис. 15. Отчет 2 Вся работа с кубом, собственно, и сводится к различным его поворотам, группировкам. Можно менять количество измерений, способы группировки, но это не имеет значение. Принципы совершенно одинаковы. И эти самые принципы порождают определенные проблемы. Дело в том, что при таком представлении данных работать с информацией легко и удобно, но куб очень быстро увеличивается в размерах. И для того, чтобы получить хороший результат, необходимо, чтобы на экран выводился не весь куб, а только нужная его часть. Для этого необходимо: − Во-первых, иметь возможность выбирать только те измерения, которые нас интересуют. Если вам все равно, в какой город продавался товар, то нужно с самого начала убрать измерение «город». − Во-вторых, иметь возможность выбрать/отсечь ненужные значения. Например, если из всей номенклатуры интересуют только утюги и холодильники, нужно строить куб только для них. 40 PDF created with pdfFactory Pro trial version www.pdffactory.com Работа с OLAP-системой должна быть простой и очевидной для пользователя. На это почему-то обращают мало внимания. Зачем нужен мощный инструмент, если им трудно пользоваться. Современные OLAP-системы поддерживают многопользовательскую работу. Изменения выполняются в отдельном адресном пространстве пользовательского приложения; реально исходные данные при этом не меняются. Для того чтобы внести изменения, пользователь должен обладать эксклюзивными правами. В целом, OLAP очень красивая, полезная и интересная технология. Если грамотно подходить к ее применению, то она принесет огромную пользу в вашей ежедневной работе. А пользователи, привыкнув к ней, вообще не понимают, как они могли до этого работать без нее. Быстро и легко получить из базы данных нужную информацию в нужном виде – все, что необходимо пользователю. 4.2. 12 правил Кодда – принципы OLAP Ниже перечислены 12 правил, изложенных Коддом и определяющих OLAP. 1) Многомерность – OLAP-система на концептуальном уровне должна представлять данные в виде многомерной модели, что упрощает процессы анализа и восприятия информации. 2) Прозрачность – OLAP-система должна скрывать от пользователя реальную реализацию многомерной модели, способ организации, источники, средства обработки и хранения. 3) Доступность – OLAP-система должна предоставлять пользователю единую, согласованную и целостную модель данных, обеспечивая доступ к данным независимо от того, как и где они хранятся. 4)Постоянная производительность при разработке отчетов – производительность OLAP-систем не должна значительно уменьшаться при увеличении количества измерений, по которым выполняется анализ. 5) Клиент-серверная архитектура – OLAP-система должна быть способна работать в среде «клиент-сервер», т.к. большинство данных, которые сегодня требуется подвергать оперативной аналитической обработке, хранятся распределено. 6) Равноправие измерений – OLAP-система должна поддерживать многомерную модель, в которой все изменения равноправны. 7) Динамическое управление разреженными матрицами – OLAP-система должна обеспечивать оптимальную обработку разреженных матриц. Скорость доступа должна сохраняться вне зависимости от расположения ячеек данных и быть постоянной величиной для моделей, имеющих разное число измерений и различную степень разреженности данных. 8) Поддержка многопользовательского режима – OLAP-система должна предоставлять возможность работать нескольким пользователям совместно с одной аналитической моделью или создавать для них различные модели из единых данных. При этом возможны как чтение, так и запись данных, поэтому система должна обеспечивать их целостность и безопасность. 9) Неограниченные перекрестные операции – OLAP-система должна обеспечивать сохранение функциональных отношений, описанных с помощью 41 PDF created with pdfFactory Pro trial version www.pdffactory.com определенного формального языка между ячейками гиперкуба при выполнении любых операций среза, вращения, консолидации или детализации. 10) Интуитивная манипуляция данными – OLAP-система должна предоставлять способ выполнения операций среза, вращения, консолидации и детализации над гиперкубом без необходимости пользователю совершать множество действий с интерфейсом. 11) Гибкие возможности получения отчетов – OLAP-система должна поддерживать различные способы визуализации данных. 12) Неограниченная размерность и число уровней агрегации – исследование о возможном числе необходимых измерений, требующихся в аналитической модели, показало, что одновременно может использоваться до 19 измерений. Отсюда вытекает настоятельная рекомендация, чтобы аналитический инструмент мог одновременно предоставить хотя бы 15, а предпочтительно – 20 измерений. Более того, каждое из общих измерений не должно быть ограничено по числу определяемых пользователем-аналитиком уровней агрегации и путей консолидации. Набор этих требований, достаточно часто вызывает различные нарекания и перечисленные 12 требований Кодда не позволяют точно определить OLAP. В 1995 г. Кодд к приведенному перечню добавил следующие шесть правил: 1) Пакетное извлечение против интерпретации – OLAP-система должна одинаково эффективно обеспечивать доступ, как к собственным, так и внешним данным. 2) Поддержка всех моделей OLAP анализа – OLAP-система должна поддерживать все четыре модели анализа данных: категориальную, толковательную, умозрительную, стереотипную. 3) Обработка ненормализованных данных – OLAP-система должна быть интегрирована с ненормализованными источниками данных. Модификации не должны приводить к изменениям данных, хранимых в исходных внешних системах. 4) Сохранение результатов OLAP анализа: хранение их отдельно от исходных данных – OLAP-система, работающая в режиме чтения – записи, после модификации исходных данных должна результаты сохранять отдельно, обеспечивая безопасность исходных данных. 5) Исключение отсутствующих значений – OLAP-система, представляя данные пользователю, должна отбрасывать все отсутствующие значения, и они должны отличаться от нулевых значений. 6) Обработка отсутствующих значений – OLAP-система должна игнорировать все отсутствующие значения без учета их источника. Более известен тест FASMI (Fast of Shared Multidimensional Information), созданный в 1995 году Найджелом Пендсом и Ричардом Критом на основе анализа правил Кодда. Они определили OLAP следующими пятью ключевыми словами: − Fast (быстрый) – предоставление пользователю результатов анализа за приемлемое время (обычно не более 5 с), пусть даже ценой менее детального анализа; − Analysis (анализ) – возможность осуществления любого логического и статистического анализа, характерного для данного приложения, и его сохранения в доступном для конечного пользователя виде; 42 PDF created with pdfFactory Pro trial version www.pdffactory.com − Shared (разделяемой) – многопользовательский доступ к данным с поддержкой соответствующих механизмов блокировок и средств авторизованного доступа; − Multidimensional (многомерной) – многомерное концептуальное представление данных, включая полную поддержку для иерархий и множественных иерархий (ключевое требование OLAP); − Information (информации) – возможность обращаться к любой нужной информации независимо от ее объема и места хранения. 4.3. Архитектура OLAP-систем OLAP-технология представляет для анализа данные в виде многомерных (и, следовательно, нереляционных) наборов данных, называемых многомерными кубами (гиперкуб, метакуб, кубом фактов), оси которого содержат параметры, а ячейки — зависящие от них агрегатные данные. При том гиперкуб является концептуальной логической моделью организации данных, а не физической реализацией их хранения, поскольку храниться такие данные могут и в реляционных таблицах. OLAP-система включает в себя два основных компонента: − OLAP-сервер – обеспечивает хранение данных, выполнение над ними необходимых операций и формирование многомерной модели на концептуальном уровне. OLAP-серверы обычно объединяют с ХД или ВД. − OLAP-клиент – представляет пользователю интерфейс к многомерной модели данных, обеспечивая его возможностью удобно манипулировать данными для выполнения задач анализа. OLAP-серверы скрывают от конечного пользователя способ реализации многомерной модели. Они формируют гиперкуб, с которым пользователи посредством OLAP-клиента выполняет все необходимые манипуляции, анализируя данные. Выделяют 3 основных способа реализации OLAP-серверов: − MOLAP – используют многомерные БД; − ROLAP – используют реляционные БД; − HOLAP – используют и многомерные и реляционные БД. Серверы MOLAP. Данные хранятся в виде упорядоченных многомерных массивов. Такие массивы подразделяются на гиперкубы и поликубы. Серверная архитектура, которая не опирается на функциональность основных реляционных систем, но напрямую поддерживает многомерные представления данных с помощью многомерного механизма хранения. MOLAP позволяет реализовывать многомерные запросы на уровне хранения путем установки прямого соответствия. Основное преимущество MOLAP заключается в превосходных свойствах индексации; ее недостаток — низкий коэффициент использования дискового пространства, особенно в случае разреженных данных. Многие серверы MOLAP при работе с разреженными множествами данных используют двухуровневую организацию памяти и сжатие. При двухуровневой организации пользователь либо непосредственно, либо с помощью специальных инструментов проектирования, идентифицирует набор подмассивов, которые, скорее всего, будут плотными, и 43 PDF created with pdfFactory Pro trial version www.pdffactory.com представляет их в виде массива. Индексировать эти массивы меньшего размера можно с помощью традиционных индексных структур. Многие из методик, разработанных для статистических баз данных, подходят и для MOLAP. Серверы MOLAP обладают хорошей производительностью и функциональностью, но не в состоянии должным образом масштабироваться в случае очень больших баз данных. Примеры OLAP-серверов, использующих MOLAP-архитектуру: Oracle Express Server фирмы Oracle, IBM Informix MetaCube, IBM DB2 OLAP, Arbor Essbase. Серверы ROLAP. Размещаются между основным реляционным сервером, где находится хранилище данных и клиентским инструментарием переднего плана. Серверы ROLAP поддерживают многомерные OLAP-запросы и, как правило, оптимизированы для конкретных реляционных серверов. Они указывают, какие представления должны быть материализованы, возможные запросы пользователей в терминах соответствующих материализованных представлений, и генерируют сложные SQL-серверы для основного сервера. Они также предусматривают дополнительные службы, такие как планирование запросов и распределение ресурсов. Серверы ROLAP наследуют возможности масштабирования и работы с транзакциями реляционных систем, однако существенные различия между запросами в стиле OLAP и SQL могут стать причиной низкой производительности. Нехватка производительности становится менее острой, благодаря ориентированным на задачи OLAP расширениям SQL, реализованным в серверах реляционных баз данных наподобие Oracle, IBM DB2 и Microsoft SQL Server. Примеры OLAP-серверов, использующих ROLAP-архитектуру: IBM Informix Red Brick, HighGate Project фирмы Sybase, Microsoft SQL Server 2000 Analysis Services фирмы Microsoft. Серверы HOLAP. Гибридная архитектура, которая объединяет технологии ROLAP и MOLAP. В отличие от MOLAP, которая работает лучше, когда данные более менее плотные, серверы ROLAP лучше в тех случаях, когда данные довольно разрежены. Серверы HOLAP применяют подход ROLAP для разреженных областей многомерного пространства и подход MOLAP – для плотных областей. Серверы HOLAP разделяют запрос на несколько подзапросов, направляют их к соответствующим фрагментам данных, комбинируют результаты, а затем предоставляют результат пользователю. Материализация выборочных представлений в HOLAP, выборочное построение индексов, а также планирование запросов и ресурсов аналогично тому, как это реализовано в серверах MOLAP и ROLAP. Примеры OLAP-серверов, использующих HOLAP-архитектуру: Microsoft SQL Server 2000 Analysis Services фирмы Microsoft, SAS Institute. 4.4. Аналитические OLAP-операции Над гиперкубом могут выполняться следующие операции: Срез (Slice), Вращение (Rotation), Консолидация (Drill Up), Детализация (Drill Down), Разбиение с поворотом (Slice and Dice). Операция СРЕЗА (СЕЧЕНИЯ). При выполнении операции сечения формируется подмножество гиперкуба, в котором значение одного или более измерений фиксировано (значение параметров для фиксированного, например, 44 PDF created with pdfFactory Pro trial version www.pdffactory.com месяца). Если рассматривать срез с позиции конечного пользователя, то наиболее часто его роль играет двумерная проекция куба. Операция ВРАЩЕНИЕ. Операция вращения изменяет порядок представления измерений, обеспечивая представление гиперкуба в более удобной для восприятия форме. Вращение – это изменение расположения измерений, представленных в отчете или на отображаемой странице. Операция КОНСОЛИДАЦИЯ. Включает такие обобщающие операции, как простое суммирование значений (свертка) или расчет с использованием сложных вычислений, включающих другие связанные данные. Например, показатели для отдельных компаний могут быть просто просуммированы с целью получения показателей для каждого города, а показатели для городов могут быть "свернуты" до показателей по отдельным странам. Операция ДЕТАЛИЗАЦИЯ. Операция, обратная консолидации, которая включает отображение подробных сведений для рассматриваемых консолидированных данных. Направление детализации может быть задано как по иерархии отдельных измерений, так и согласно прочим отношениям, установленным в рамках измерений или между измерениями. Операция РАЗБИЕНИЕ С ПОВОРОТОМ. Позволяет получить представление данных с разных точек зрения. Например, один срез данных о доходах может содержать все сведения о доходах от продаж товаров указанного типа по каждому городу. Другой срез может представлять данные о доходах отдельной компании в каждом из городов. На рисунке 16 приведен пример гиперкуба. Рис. 16. Представление данных в виде куба Измерение – это последовательность значений одного из анализируемых параметров. Например, для параметра «время» это последовательность календарных дней, для параметра «регион» это список городов. 45 PDF created with pdfFactory Pro trial version www.pdffactory.com Множественность измерения предполагает представление данных в виде многомерной модели. По измерениям в многомерной модели откладывают параметры, относящиеся к анализируемой предметной области. Каждое измерение может быть представлено в виде иерархической структуры. Например, измерение «Исполнитель» может иметь следующие иерархические уровни: «предприятие – подразделение – отдел – служащий». Более того, некоторые измерения могут иметь несколько видов иерархического представления. Например, измерение «время» может включать две иерархии со следующими уровнями: «год – квартал – месяц – день» и «неделя – день». На пересечениях осей измерений располагаются данные, количественно характеризующие анализируемые факты – меры. Это могут быть объемы продаж, выраженные в единицах продукции или в денежном выражении, остатки на складе, издержки и т.д. Таким образом, ребра такого гиперкуба являются измерениями, а ячейки – мерами. На рисунке 17 приведен пример операции среза. Данные, что не вошли в сформированный срез, связаны с теми элементами измерения, которые не были указаны в качестве определяющих элементов. Рис. 17. Операция среза На рисунке 18 приведен пример операции вращения, что позволяет придавать желаемый вид отчету, например перестановка местами строк и столбцов. Кроме того, вращением куба данных является перемещение внетабличных измерений на место измерений, представленных на отображаемой странице, и, наоборот (при этом внетабличное измерение становится новым измерением строки или измерением столбца). На рисунке 19 представлена операция консолидации и детализации. При этом направление детализации может быть задано как по иерархии отдельных измерений, так и согласно прочим отношениям, установленным в рамках измерений или между измерениями. 46 PDF created with pdfFactory Pro trial version www.pdffactory.com Рис. 18. Операция вращения Рис. 19. Операции консолидации и детализации 47 PDF created with pdfFactory Pro trial version www.pdffactory.com 5. Интеллектуальный анализ данных. Data Mining OLAP – системы предоставляют аналитику средства проверки гипотез при анализе данных. При этом основной задачей аналитика является генерация гипотез. Он решает ее, основываясь на основе своих знаний и опыте. Однако знания есть не только у человека, но и в накопленных данных, которые подвергаются анализу. Такие знания часто называют «скрытыми», т.к. они содержатся в гигабайтах и терабайтах информации, которые человек не в состоянии исследовать самостоятельно. В связи с этим существует высокая вероятность пропустить гипотезы, которые могут принести значительную выгоду. Очевидно, что для обнаружения скрытых знаний необходимо применять специальные методы автоматического анализа, при помощи которых приходится практически добывать знания из «завалов» информации. За этим направлением прочно закрепился термин добыча данных или Data Mining. Классическое определение этого термина дал в 1996 году один из основателей этого направления Пятецкий – Шапиро. 5.1. Добыча данных. Data Mining Исторически направление Data Mining направлено на обеспечение эффективных способов обнаружения моделей существующих наборов данных. Эти модели должны раскрывать некоторые полезные аспекты данных, скрывая детали, не являющиеся полезными для приложения. В разных исследовательских сообществах разработаны алгоритмы классификации, кластеризации, выявления ассоциативных правил и обобщения. Проблемой Data Mining в области баз данных является разработка алгоритмов и структур данных для просеивания базы данных в поисках «жемчужин». Такая обработка должна вестись в фоновом режиме с потреблением остаточных системных ресурсов. Другой важной проблемой является интеграция Data Mining с подсистемой поддержки запросов, оптимизацией и другими средствами базы данных, такими как триггеры. Data Mining, или, в устоявшемся переводе, извлечение знаний, стоит несколько обособленно в среде аналитических систем. Системы класса Data Mining наиболее сложны в реализации и решают широкий класс задач, связанных с выявлением скрытых взаимосвязей в данных. Если OLAP занимается проверкой возникающих у аналитика гипотез, то Data Mining помогает формулировать эти гипотезы в том случае, когда аналитик не до конца представляет цель своего запроса и, соответственно, не может четко определить его. Класс прикладных задач для Data Mining потенциально очень широк – от маркетинговых исследований и оценки надежности клиентов (например, для биллинговых систем) до проверки существования связей между физическими и юридическими лицами. В основе систем Data Mining лежит математический аппарат, базирующийся на алгоритмах систем искусственного интеллекта. Создание приложений начинается с оценки предметной области и выявления алгоритмов, дающих наиболее точные результаты для рассматриваемой задачи. Затем следует настройка и «обучение» алгоритмов, т.е. их прогонка на каком-то количестве (иногда на сотнях и тысячах) наборов исходных данных с заранее известными результатами. Прогонка, как правило, проводится в несколько этапов, с дальнейшей настройкой алгоритмов до 48 PDF created with pdfFactory Pro trial version www.pdffactory.com достижения требуемой точности. Существенную роль играет анализ и интерпретация полученных результатов. Современные системы Data Mining обладают полнофункциональным графическим интерфейсом, поддерживающим все стадии разработки приложения и развитым пользовательским интерфейсом, упрощающим применение системы и интерпретацию результатов. Однако от аналитиков, использующих Data Mining, требуется глубокое знание предметной области, владение математическим аппаратом и высокая квалификация пользователей программного обеспечения. Среди подобных инструментов наиболее известны Darwin компании Thinking Machines, ныне входящей в Oracle Corporation, и Intelligent Miner for Data корпорации IBM. В последнее время намечается тенденция к интеграции возможностей Data Mining в серверы баз данных. Так, например, корпорация Microsoft реализовала некоторые алгоритмы в версии своей СУБД SQL Server 2000. Data Mining – исследование и обнаружение «машиной» (алгоритмами, средствами искусственного интеллекта) в сырых данных скрытых знаний, которые ранее не были известны, нетривиальны, практически полезны, доступны для интерпретации человеком. Рассмотрим свойства обнаруживаемых знаний: − Знания должны быть новые, ранее неизвестные. Ценность представляют именно новые, ранее неизвестные знания, т.к. затраченные усилия на открытие знаний, которые уже известны пользователю, не окупаются. − Знания должны быть нетривиальны. Результаты анализа должны отражать неочевидные, неожиданные закономерности в данных, составляющие так называемые скрытые знания. − Знания должны быть практически полезны. Найденные знания должны быть применимы, в том числе и на новых данных, с достаточно высокой степенью достоверности. Полезность заключается в том, чтобы эти знания могли принести определенную выгоду при их применении. − Знания должны быть доступны для понимания человеку. Найденные закономерности должны быть логически объяснимы, в противном случае существует вероятность, что они являются случайными. Кроме того, знания должны быть представлены в понятном для человека виде. В Data Mining для представления полученных знаний служат модели. Виды моделей зависят от методов их создания. Наиболее распространенными являются: правила, деревья решений, кластеры и математические функции. Понятие «добыча данных» как процесс аналитического исследования больших массивов информации (обычно экономического характера) с целью выявления определенных закономерностей и систематических взаимосвязей между переменными, которые затем можно применить к новым совокупностям данных. Этот процесс включает три основных этапа: исследование, построение модели или структуры и проверка. В идеальном случае, при достаточном количестве данных можно организовать итеративную процедуру для построения устойчивой (робастной) модели. В то же время, в реальной ситуации практически невозможно проверить экономическую модель на стадии анализа и поэтому начальные результаты имеют характер эвристик, которые можно использовать в процессе 49 PDF created with pdfFactory Pro trial version www.pdffactory.com принятия решения (например, «Имеющиеся данные свидетельствуют о том, что у женщин частота приема снотворных средств увеличивается с возрастом быстрее, чем у мужчин»). Методы Data Mining помогают решать многие задачи, с которыми сталкивается аналитик. Из них основными являются классификация, регрессия, поиск ассоциативных правил и кластеризация. Задача классификации сводится к определению класса объекта по его характеристикам. Необходимо заметить, что в этой задаче множество классов, к которым может быть отнесен объект, заранее известно. Задача регрессии, подобно задаче классификации, позволяет определить по известным характеристикам объекта значение некоторого его параметра. В отличие от задачи классификации значением параметра является не конечное множество классов, а множество действительных чисел. При поиске ассоциативных правил целью является нахождение частных зависимостей между объектами или событиями. Найденные зависимости представляются в виде правил и могут быть использованы как для лучшего понимания природы анализируемых данных, так и для предсказания появления событий. Задача кластеризации заключается в поиске независимых групп и их характеристик во всем множестве анализируемых данных. Решение этой задачи помогает лучше понять данные. Кроме того, группировка однородных объектов позволяет сократить их число, а, следовательно, и облегчить анализ. Перечисленные задачи по назначению делятся на описательные и предсказательные. Описательные задачи уделяют внимание улучшению понимания анализируемых данных. К ним относятся задачи кластеризации и поиска, ассоциативных правил. Предсказательные задачи выполняются в два этапа: на первом этапе на основании набора данных с известными результатами строится модель, на втором этапе она используется для предсказания результатов на основании новых наборов данных. К таким задачам относят задачи классификации и регрессии По способам решения задачи разделяют на supervised learning (обучение с учителем) и unsupervised learning (обучение без учителя). Обучение с учителем (supervised learning) – проводится в несколько этапов. Сначала строится модель анализируемых данных – классификатор. Затем классификатор подвергается обучению, т.е. проверяется качество его работы и, если оно неудовлетворительное, происходит дополнительное обучение классификатора. Так продолжается до тех пор, пока не будет достигнут требуемый уровень точности. Обучение без учителя (unsupervised learning) работает с описательными моделями, представляющими некоторые закономерности, решение которых не требует предварительных знаний об анализируемых данных. 50 PDF created with pdfFactory Pro trial version www.pdffactory.com 5.2. Модели Data Mining Цель технологии Data Mining – нахождение в данных таких моделей, которые не могут быть найдены обычными методами. Существуют два вида моделей: предсказательные и описательные. Предсказательные (predictive) модели. Эти модели строятся на основании набора данных с известными результатами. Они используются для предсказания результатов на основании других наборов данных. При этом, естественно, требуется, чтобы модель работала максимально точно, была статистически значима и оправдана. К ним относятся следующие модели: − классификации – описывают правила или набор правил, в соответствии с которыми можно отнести описание любого нового объекта к одному из классов. Такие правила строятся на основании информации о существующих объектах путем разбиения их на классы; − последовательностей – описывают функции, позволяющие прогнозировать изменение непрерывных числовых параметров. Они строятся на основании данных об изменении некоторого параметра за прошедший период времени. Описательные (descriptive) модели. Эти модели уделяют внимание сути зависимостей в наборе данных, взаимному влиянию различных факторов. Ключевой момент в таких моделях – легкость и прозрачность для восприятия человеком. К ним относятся следующие виды моделей: − регрессионные – описывают функциональные зависимости между зависимыми и независимыми показателями и переменными в понятной человеку форме; − кластеризации – описывают группы, на которые можно разделить объекты, данные о которых подвергаются анализу. Группируются объекты на основе данных, описывающих сущность объектов. Объекты внутри кластера должны быть «похожими» друг на друга и отличаться от объектов, вошедших в другие кластеры. Чем больше похожи объекты внутри кластера и чем больше отличий между кластерами, тем точнее кластеризация; − исключений – описывают исключительные ситуации в записях, которые резко отличаются чем-либо от основного множества записей; − итоговые – выявление ограничений на данные анализируемого массива; − ассоциации – выявление закономерностей между связанными событиями. Для построения рассмотренных моделей используются различные методы и алгоритмы Data Mining. 5.3. Методы Data Mining Методы добычи данных приобретают все большую популярность в качестве инструмента для анализа экономической информации, особенно в тех случаях, когда предполагается, что из имеющихся данных можно будет извлечь знания для принятия решений в условиях неопределенности. Базовые методы. К базовым методам Data Mining принято относить, прежде всего, алгоритмы, основанные на переборе. Объем вычислений при этом растет экспоненциально с увеличением количества данных. Основным достоинством 51 PDF created with pdfFactory Pro trial version www.pdffactory.com является простота, как с точки зрения понимания, так и реализации. К недостаткам можно отнести отсутствие формальной теории, на основании которой строятся такие алгоритмы, а следовательно, сложности, связанные с их исследованием и развитием. К базовым методам Data Mining можно отнести также и подходы, использующие элементы теории статистики. Основная их идея сводится к корреляционному, регрессионному и другим видам статистического анализа. Основным недостатком является усреднение значений, что приводит к потере информативности данных. Это в свою очередь приводит к уменьшению количества добываемых знаний. Статистические методы: Корреляционный анализ, Регрессионный анализ, Ковариационный анализ. Нечеткая логика. Основным способом исследования задач анализа данных является их отображение на формализованный язык и последующий анализ полученной модели. Неопределенность по объему отсутствующей информации у системного аналитика можно разделить на три большие группы: неизвестность, неполнота (недостаточность, неадекватность), недостоверность. Недостоверность бывает физической и лингвистической. Выделяют два вида физической неопределенности: неточность, случайность. Выделяют два вида лингвистической неопределенности: неопределенность значений слов, неоднозначность смысла фраз. Для обработки физических неопределенностей успешно используются методы теории вероятностей и классическая теория множеств. Основной сферой применения нечеткой логики было и во многом остается управление. В общем случае можно предложить следующую схему реализации процесса управления: 1) распознавание; 2) предсказание; 3) идентификация; 4) принятие решения; 5) управление. Генетические алгоритмы. ГА относятся к числу универсальных методов оптимизации, позволяющих решать задачи различных типов и различной степени сложности. При этом ГА характеризуются возможностью как однокритериального, так и многокритериального поиска в большом пространстве. Одним из наиболее востребованных приложений ГА в области Data Mining является поиск наиболее оптимальной модели. Генетическими алгоритмами называют алгоритмы поиска, которые моделируют парную репродукцию. Парная репродукция характеризуется рекомбинацией двух родительских строк для создания потомков. Эта рекомбинация называется скрещиванием. Нейронные сети. Это класс моделей, основанных на биологической аналогии с мозгом человека и предназначенных после прохождения этапа так называемого обучения на имеющихся данных для решения разнообразных задач анализа данных. Размер и структура сети должны соответствовать сущности исследуемого явления. На этапе обучения нейроны сети итеративно обрабатывают входные данные и корректируют свои веса так, чтобы сеть наилучшим образом прогнозировала данные, на которых выполняется обучение. После обучения сеть готова к работе и может использоваться для построения прогнозов. Таким образом, нейронная сеть, прошедшая обучение, выражает закономерности, присутствующие в данных. Одно 52 PDF created with pdfFactory Pro trial version www.pdffactory.com из главных преимуществ нейронных сетей состоит в том, что они, по крайней мере, теоретически, могут аппроксимировать любую непрерывную функцию, и поэтому исследователю нет необходимости заранее принимать какие-либо гипотезы относительно модели и даже, в ряде случаев, о том, какие переменные действительно важны. Однако существенным недостатком нейронных сетей является то обстоятельство, что окончательное решение зависит от начальных установок сети и его практически невозможно интерпретировать в традиционных аналитических терминах, которые обычно применяются при построении теории явления. Хотя в последнее время возрос интерес к разработке новых методов анализа данных, специально предназначенных для сферы бизнеса (например, Деревья классификации), в целом системы добычи данных по-прежнему основываются на классических принципах разведочного анализа данных (РАД) и построения моделей и используют те же подходы и методы. Общая схема использования методов Data Mining приведена на рисунке 20. Рис.20. Схема использования методов Data Mining 5.4. Процесс поддержки принятия решений Интеллектуальный анализ данных (ИАД — Data Mining) — это процесс поддержки принятия решений, основанный на поиске в данных скрытых закономерностей. При этом накопленные сведения автоматически обобщаются до информации, которая может быть охарактеризована как знания. Стадии ИАД. В общем случае процесс ИАД состоит из трёх стадий: выявление закономерностей (свободный поиск); использование выявленных закономерностей для предсказания неизвестных значений (прогностическое моделирование); анализ исключений, предназначенный для выявления и толкования аномалий в найденных 53 PDF created with pdfFactory Pro trial version www.pdffactory.com закономерностях. Иногда в явном виде выделяют промежуточную стадию проверки достоверности найденных закономерностей между их нахождением и использованием (стадия валидации). Содержание основных стадий ИАД представлено на рисунке 21. Рис. 21. Основные стадии ИАД Группы методов ИАД. Все методы интеллектуального анализа данных подразделяются на две большие группы по принципу работы с исходными обучающими данными. В первом случае исходные данные могут храниться в явном детализированном виде и непосредственно использоваться для прогностического моделирования и/или анализа исключений; это так называемые методы рассуждений на основе анализа прецедентов. Главной проблемой этой группы методов является затрудненность их использования на больших объемах данных, хотя именно при анализе больших хранилищ данных методы интеллектуального анализа данных приносят наибольшую пользу. Во втором случае информация вначале извлекается из первичных данных и преобразуется в некоторые формальные конструкции (их вид зависит от конкретного метода). Согласно классификации, этот этап выполняется на стадии свободного поиска, которая у методов первой группы в принципе отсутствует. Таким образом, для прогностического моделирования и анализа исключений используются результаты этой стадии, которые гораздо более компактны, чем сами массивы исходных данных. При этом полученные конструкции могут быть либо «прозрачными» (интерпретируемыми), либо «черными ящиками» (не трактуемыми). 54 PDF created with pdfFactory Pro trial version www.pdffactory.com Суть методов ИАД представлена на рисунке 22. Рис. 22. Методы интеллектуального анализа данных 5.5. Процесс обнаружения знаний Для обнаружения знаний в данных недостаточно просто применить методы Data Mining, хотя, безусловно, этот этап является основным в процессе интеллектуального анализа. Весь процесс состоит из нескольких этапов. Обнаружение знаний (knowledge discovery) – процесс определения и достижения цели посредством итеративной добычи данных. Весь процесс можно разбить на следующие этапы, изображенные на рисунке 23: − понимание и формулировка задачи анализа; − подготовка данных для автоматизированного анализа; − применение методов Data Mining и построение моделей; − проверка построенных моделей; − интерпретация моделей человеком. На первом этапе выполняется осмысление поставленной задачи и уточнение целей, которые должны быть достигнуты методами Data Mining. Важно правильно сформулировать цели и выбрать необходимые для их достижения методы, т.к. от этого зависит дальнейшая эффективность всего процесса. Второй этап состоит в приведении данных к форме, пригодной для применения конкретных методов Data Mining. На этапе подготовки данных аналитик готовит набор данных, содержащий достаточно информации, для того чтобы создать точные модели на последующих этапах. Подготовка данных может включать в себя сложные запросы с объемными результатами. 55 PDF created with pdfFactory Pro trial version www.pdffactory.com Рис.23. Этапы ИАД Фактически, платформы добычи данных используют реляционные серверы или серверы OLAP для решения своих задач по подготовке данных. Как правило, добыча данных включает в себя итеративно создаваемые модели на основе подготовленного множества данных, а затем применение одной или нескольких моделей. Поскольку создание моделей на больших множествах данных может оказаться весьма дорогостоящим, аналитики часто сначала работают с несколькими выборками множества данных. Платформы добычи данных, таким образом, должны поддерживать вычисления на случайно выбранных экземплярах данных в сложных запросах. После выбора описывающих параметров изучаемые данные могут быть представлены в виде прямоугольной таблицы, где каждая строка представляет собой отдельный случай, объект или состояние изучаемого объекта, а каждая колонка – параметры, свойства или признаки всех исследуемых объектов. Большинство методов Data Mining работают только с подобными прямоугольными таблицами. Входящие в таблицу данные, необходимо предварительно обработать. Необходимо исключить из анализа параметры, имеющие одинаковые значения для всей колонки. Исключается также категориальный признак, значения которого во всех записях различны. Необходимо выделить то множество признаков, которые наиболее важны в контексте данного исследования, отбросить явно неприменимые и выделить те, которые наиболее вероятно войдут в искомую зависимость. Для этого используются статистические методы. После очистки данных по столбцам таблицы, необходимо провести предварительную очистку данных по строкам таблицы. Необходимо отбросить ошибки, очень неточно определенные значения, записи, соответствующие каким – то редким, исключительным ситуациям, и другие дефекты, которые могут резко понизить эффективность методов Data Mining, применяемых на следующих этапах анализа. 56 PDF created with pdfFactory Pro trial version www.pdffactory.com Третий этап – это собственно применение методов Data Mining. Только после того, как принято решение о том, какую модель применять, аналитик создает модель на всем подготовленном множестве данных. Цель этого этапа создания модели — указать шаблоны, которые определяют целевой атрибут (target attribute). Предсказать как точно указанные, так и скрытые атрибуты помогают несколько классов моделей добычи данных. На выбор модели влияют два важных фактора: точность модели и эффективность алгоритма для создания модели на больших множествах данных. С точки зрения статистики, точность большинства моделей увеличивается с ростом объема используемых данных, поэтому алгоритмы, на основе которых строятся модели добычи данных, должны быть эффективными и приемлемым образом масштабироваться при росте наборов обрабатываемых данных. Четвертый этап – проверка построенных моделей. Очень простой и часто используемый способ заключается в том, что все имеющиеся данные, которые необходимо анализировать, разбиваются на две группы. Как правило, одна из них большего размера, другая – меньшего. На большей группе, применяя те или иные методы Data Mining, получают модели, а на меньшей – проверяют их. По разности в точности между тестовой и обучающей группами можно судить об адекватности построенной модели. Последний пятый этап – интерпретация полученных моделей человеком в целях их использования для принятия решений, добавление получившихся правил и зависимостей в базы знаний и т.д. От того, насколько эффективным он будет, в значительной степени зависит успех решения поставленной задачи. Окончательная оценка ценности добытого нового знания выходит за рамки анализа, автоматизированного или традиционного, и может быть проведена только после претворения в жизнь решения, принятого на основе добытого знания, после проверки нового знания практикой. Исследование достигнутых практических результатов завершает оценку ценности добытого средствами Data Mining нового знания. 6. Классификация и регрессия Классификация является наиболее распространенной задачей интеллектуального анализа данных (ИАД). Она позволяет выявить признаки, характеризующие однотипные группы объектов – классы, для того чтобы по известным значениям этих характеристик можно было отнести новый объект к тому или иному классу. Ключевым моментом выполнения этой задачи является анализ множества классифицированных объектов. Наиболее типичный пример использования классификации – конкурентная борьба между поставщиками товаров и услуг за определенные группы клиентов. Классификация способна помочь определить характеристики неустойчивых клиентов, склонных перейти к другому поставщику, что позволяет найти оптимальную стратегию их удержания от этого шага (например, посредством предоставления скидок, льгот или даже с помощью индивидуальной работы с представителями "групп риска"). 57 PDF created with pdfFactory Pro trial version www.pdffactory.com Функцию f(x), описывающую зависимость условного среднего значения y(x) выходной переменной Y от заданных фиксированных значений входных переменных X1, ..., Хр, называют функцией регрессии. 6.1. Постановка задачи. Представление результатов В задаче классификации и регрессии требуется определить значение зависимой переменной объекта на основании значений других переменных, характеризующих данный объект. Формально задачу классификации и регрессии можно описать следующим образом. Пусть некоторый объект характеризуется набором переменных (6) I = {x1 , x 2 ,.., x n , y} = {X , y} , где x1, x2,.., xn – независимые переменные, значения которых известны; y – зависимая переменная, определяемая вектором X. Каждая переменная x i может принимать значения C i = {C i 1 , C i 2 ,.., C in }. (7) Если значениями переменной являются элементы конечного множества, то говорят, что они имеют категориальный тип. Если множество значений С зависимой переменной Y – конечное, то задача называется задачей классификации. Если переменная Y принимает значения из множества действительных чисел R, то задача называется задачей регрессии. Несмотря на то, что был назван способ определения значения зависимой переменной функцией классификации или регрессии, он необязательно может быть выражен математической функцией. Классификации и регрессии могут быть представлены следующими способами: − классификационные правила; − деревья решений; − математические функции. Математические функции чаще используются для представления регрессий, правила и деревья решений для классификаций. Классификационное правило состоит из двух частей: условия и заключения: Если <условие> то < заключение>. Условием является проверка одной или нескольких независимых переменных, оно может объединяться логическими операциями «И», «ИЛИ», «НЕ». Заключением является значение зависимой переменной или распределение ее вероятности по классам. При мер 3. если (лабораторные_ работы = сданы и РГР = сдана), то (допуск_к_экзамену = есть). Основным достоинством правил является легкость их восприятия и запись на естественном языке. Другое преимущество – относительная их независимость. В набор правил легко добавить новое, без необходимости изменять уже существующие. Относительность независимости правил связана с возможной их противоречивостью друг другу. 58 PDF created with pdfFactory Pro trial version www.pdffactory.com Деревья решений – это способ представления правил в иерархической, последовательной структуре. Обычно каждый узел дерева включает в себя проверку определенной независимой переменной. Если переменная категориальная, то количество ветвей, выходящих от узла соответствует количеству категориальных значений переменной. Если значением является число, то количество выходящих ветвей определяется количеством интервалов, на которое разбивается весь диапазон возможных значений. При этом выполняется проверка на попадание значение в один из этих интервалов. Листья деревьев соответствуют значениям зависимой переменной, т.е. классам. Деревья решений легко преобразуются в правила, но обратное преобразование не всегда возможно. Пример дерева решений изображен на рисунке 24. Рис. 24. Пример дерева решений Математическая функция выражает отношение зависимой переменной от независимых. При построении математической функции регрессии основная задача сводится к выбору наилучшей функции (аппроксимации) из множества доступных вариантов функций. Формально задачу построения функций классификации и регрессии можно описать как задачу выбора функции с минимальной степенью ошибки R(f): (8) min (R( f )) = min (∑ c( y, f ( X i ))) , где F – множество всех возможных функций; c( y, f ( X i )) – функция потерь. Для метода наименьших квадратов ci = ( y i − f ( X i ))2 . Для наилучшего равномерного приближения ci = ( y i − f ( X i )) . 6.2. Построение правил классификации Алгоритм построения 1R – правил Рассмотрим простейший алгоритм формирования элементарных правил для классификации объекта. Алгоритм 1R строит правила по значению одной независимой переменной. Идея: для любого возможного значения независимой переменной формируется правило, которое классифицирует объекты по обучающей 59 PDF created with pdfFactory Pro trial version www.pdffactory.com выборке. При этом в заключительной части правила указывается значение зависимой переменной, которое встречается наиболее часто. При этом ошибкой правила считается количество объектов, имеющих то же значение независимой переменной, но не относящихся к выбранному правилу. Таким образом, для каждого значения будет получен набор правил с оценкой ошибок их выполнения. Из них выбирается правило с наименьшей ошибкой. Если в обучающей выборке есть объекты с пропущенными значениями независимой переменной, то подсчитываются такие объекты для каждого возможного значения этой переменной. Если переменная имеет численные значения, то весь диапазон возможных значений разбивается на интервалы, так чтобы каждый из них соответствовал определенному классу в обучающей выборке. Алгоритм 1R, несмотря на свою простоту, во многих случаях на практике оказывается достаточно эффективным. Это объясняется тем, что многие объекты действительно можно классифицировать лишь по одному атрибуту. Кроме того, немногочисленность формируемых правил позволяет легко понять и использовать полученные результаты. Метод Naive Bayes Рассмотренный ранее 1R алгоритм формирует правила для принятия решений лишь по одной переменной объекта. Однако это не всегда приемлемо. Нередко для классификации необходимо рассмотреть несколько независимых переменных. Такую классификацию позволяет выполнить алгоритм Naive Bayes. Метод Naive Bayes позволяет выполнять классификацию по нескольким независимым переменным, используя формулу Байеса для расчета вероятности. Введем вероятность того, что некоторый объект относится к классу c r ( y = c r ) − P( y = c r ). Событие, соответствующее равенству независимых переменных определенным значениям, обозначим как Е, а вероятность его наступления Р(Е). Идея алгоритма заключается в расчете условной вероятности принадлежности объекта к классу cr при равенстве его независимых переменных определенным значениям: (9) P( y = c r E ) = P(E y = c r ) ∗ P( y − cr ) / P(E ) . Формируются правила, в условных частях которых сравниваются все независимые переменные со своими возможными значениями, а в заключительной части присутствуют все возможные значения зависимой переменной вида: если x1 = c 1h и x 2 = c a2 и … x m = c dm , тогда y = c r . Для каждого из этих правил по формуле Байеса определяется его вероятность. Полагая, что переменные независимы, выразим вероятность P(E y = cr ) через произведение вероятностей для каждой независимой переменной: (10) P(E y = cr ) = P (x1 = ch1 y = cr ) ∗ P (x 2 = ca2 y = c r ) ∗ ... ∗ P (x m = c dm y = c r ) . Тогда вероятность всего правила: P( y = c r E ) = P (x1 = c1h y = c r ) ∗ P(x2 = ca2 y = c r ) ∗ ... ∗ P(xm = c dm y = c r ) ∗ P( y = c r ) / P(E ) . (11) Вероятность принадлежности объекта к классу cr при условии равенства его переменной xi некоторому значению c di определяется по формуле: P(xi = c di y = cr ) = P(xi = c di и y = cr ) / P( y = cr ) , 60 PDF created with pdfFactory Pro trial version www.pdffactory.com (12) т.е. равно отношению количества объектов в обучающей выборке, у которых xi = cdi и y = c r , к количеству объектов, относящихся к классу cr. Таким образом, можно определять вероятности произвольного события Е. Одним из действительных преимуществ данного метода является то, что пропущенные значения не создают никакой проблемы. При подсчете вероятности они просто пропускаются для всех правил, и это не влияет на соотношение вероятностей. 6.3. Построение деревьев решений Методика «разделяй и властвуй» Метод «разделяй и властвуй» заключается в рекурсивном разбиении множества объектов из обучающей выборки на подмножества, содержащие объекты, относящиеся к одинаковым классам. Относительно обучающей выборки Т и множества классов С возможны три ситуации: − множество Т содержит один или более объектов, относящихся к одному классу сr. Тогда дерево решений для Т – это лист, определяющий класс сr ; − множество Т не содержит ни одного объекта (пустое множество). Тогда это снова лист, и класс, ассоциированный с листом, выбирается из другого множества, отличного от Т, например, из множества, ассоциированного с родителем; − множество Т обучающей выборки содержит объекты, относящиеся к разным классам. В этом случае множество Т разбивается на подмножества. Для этого выбирается одна из независимых переменных, имеющая два более отличных друг от друга значений с1,с2, .., сm; множество Т разбивается на подмножества Т1,Т2,..,Тm, каждое из которых содержит все объекты, имеющие значение сi для выбранного признака. Эта процедура рекурсивно продолжается до тех пор, пока в конечном множестве не окажутся объекты только одного класса. Использование данной методики предполагает построение дерева сверху вниз. Метод относится к «жадным» алгоритмам, не предполагающим возврата назад для выбора другой переменной, поэтому на этапе построения нельзя сказать, даст ли выбранная переменная оптимальное разбиение. При построении деревьев решений особое внимание уделяется выбору переменной, по которой будет выполняться разбиение. Общее правило для выбора: выбранная переменная должна разбить множество так, чтобы получаемые в итоге подмножества состояли из объектов, принадлежащих к одному классу, или были максимально приближены к этому, т.е. количество объектов из других классов в каждом из этих множеств было минимальным. Другой проблемой при построении дерева является проблема остановки его разбиения. К данной проблеме можно применить следующие правила: − использование статистических методов для оценки целесообразности дальнейшего разбиения, так называемая ранняя остановка. Но этот подход строит менее точные классификационные модели; − ограничение глубины дерева. Остановит дальнейшее построение, если разбиение ведет к дереву с глубиной, превышающей заданное значение; 61 PDF created with pdfFactory Pro trial version www.pdffactory.com − разбиение должно быть нетривиальным, т.е. получившиеся в результате узлы должны содержать не менее заданного количества объектов. Очень часто алгоритмы построения деревьев решений дают сложные деревья, которые «переполнены данными», имеют много узлов и ветвей. Для решения данной проблемы часто применяется так называемое отсечение ветвей (pruning). В отличии от процесса построения, отсечение ветвей происходит снизу вверх, двигаясь с листьев дерева, отмечая узлы как листья либо заменяя их поддеревом. Алгоритм ID3 Алгоритм ID3 производит выбор независимой переменной на каждом шаге на основании информации о том, каким образом классы распределены в множестве Т и его подмножествах, получаемых при разбиении. Пусть frec(cr,I) – количество объектов из множества I, относящихся к одному и тому же классу cr. Тогда вероятность того, что случайно выбранный объект будет принадлежать этому классу, равна P = frec(c r , I ) / I . Согласно теории информации произведем оценку среднего количества информации, необходимого для определения класса объекта из множества Т: Info(T ) = −∑ frec(c r , T ) / T ∗ log 2( frec(c r , I ) / T ) . (13) Это выражение дает количественную оценку в битах. Такую же оценку можно найти после разбиения множества Т на подмножества: (14) Infoxi (T ) = ∑ T j / T Info(T j ) . Критерием для выбора атрибута является следующая формула: Gain(xi ) = Info(T ) − Infoxi (T ) . (15) Выбирается переменная с максимальным значением Gain(). Она и будет являться проверкой в текущем узле дерева, а затем по ней производится дальнейшее построение дерева. Алгоритм C 4.5 Рассмотренный алгоритм ID3 подвержен сверхчувствительности, т.е. предпочитает переменные, которые имеют много значений. В алгоритме С 4.5 проблема решается введением некоторой нормализации. Пусть суть информации, относящейся к объекту, указывает не на класс, а на выход. Тогда, по аналогии с определением Info(T) определим: split Info(xi ) = −∑ T j / T ∗ log 2(T j / T ). (16) Это выражение оценивает потенциальную информацию, получаемую при разбиении множества Т на подмножества. Критерием выбора является следующее выражение: (17) Gain ratio(xi ) = Gain(xi ) / split Info(xi ) . Это улучшенный критерий выбора. Алгоритм покрытия Рассмотренные методы работают сверху вниз, разбивая на каждом шаге всю обучающую выборку на подмножества. Целью такого разбиения является получение подмножеств, соответствующих всем классам. Альтернативным является подход, когда дерево строится для каждого класса по отдельности. Алгоритм покрытия: на 62 PDF created with pdfFactory Pro trial version www.pdffactory.com каждом этапе генерируется проверка узла дерева, который покрывает несколько объектов обучающей выборки. На каждом шаге алгоритма выбирается значение переменной, которое разделяет все множество на два подмножества. Разделение выполняется так, чтобы все объекты класса, для которого строится дерево, принадлежали одному подмножеству. Такое разбиение производится до тех пор, пока не будет построено подмножество, содержащее объекты только одного класса. После построения дерева для одного класса таким же образом строятся деревья для других классов. Идею алгоритма можно представить графически (рис.25). Рис. 25. Геометрическая интерпретация идеи алгоритма покрытия Методы, рассмотренные для правил и деревьев решений, работают наиболее естественно с категориальными переменными. Их можно адаптировать для работы с числовыми переменными, однако существуют методы, которые наиболее естественно работают с ними. Это методы построения математических функций: линейные методы, метод наименьших квадратов, нелинейные методы, метод SVM (Support Vector Machines) – в теории распознавания образов, карта Кохонена. 7. Поиск ассоциативных правил Одной из наиболее распространенных задач анализа данных является определение наиболее часто встречающихся наборов объектов в большом множестве наборов. 7.1. Формальная постановка задачи Обозначим множеством: объекты, составляющие исследуемые I = {i1 , i2 ,..., in } , где ij – объекты, входящие в анализируемые наборы; n – общее количество наборов. 63 PDF created with pdfFactory Pro trial version www.pdffactory.com наборы следующим (18) В сфере торговли, например, такими объектами являются товары, представленные в прайс-листе. Наборы объектов из множества I, хранящиеся в БД и подвергаемые анализу, называются транзакциями. Транзакцию можно описать как подмножество множества I: T = {i j i j ∈ I }. (19) Такие транзакции в магазине соответствуют наборам товаров, покупаемых потребителем и сохраненных в БД в виде чека. Набор транзакций, информация о которых доступна для анализа, обозначим следующим множеством: (20) D = {T1 , T2 ,...,Tm }, где m – количество доступных для анализа транзакций. Множество транзакций, в который входит объект ij , обозначим Dij. Di = {Tr i j ∈ Tr ; j = 1..n; r = 1..m} ⊆ D . j (21) Некоторый произвольный набор объектов обозначим F, а множество транзакций, в который входит набор F, обозначим DF. (22) DF = {Tr F ∈ Tr ; r = 1..m} ⊆ D . Отношение количества транзакций, в который входит набор F, к общему количеству транзакций называется поддержкой (support) набора F: Supp(F ) = DF D . (23) Если аналитиком указано минимальное значение поддержки Suppmin, то частым набором, называется набор со значением поддержки, большим Suppmin. Supp(F) > Suppmin. (24) При поиске ассоциативных правил требуется найти множество всех частых наборов: L = {F Supp(F ) > Suppmin }. (25) 7.2. Ассоциативные правила После нахождения всех частых наборов объектов следует генерация ассоциативных правил из найденных частых наборов. Ассоциативное правило имеет вид: Если (условие), то (результат), где условие – обычно не логическое выражение, а набор объектов из множества I, с которыми связаны (ассоциированы) объекты, включенные в результат данного правила. П р и м е р 4 . Если (хлеб, молоко), то (колбаса). Основным достоинством ассоциативных правил является их легкое восприятие человеком и простая интерпретация языками программирования. Выделяют три вида ассоциативных правил: 64 PDF created with pdfFactory Pro trial version www.pdffactory.com − полезные правила – содержат ранее неизвестную информацию, имеющую логическое объяснение и могут использоваться для принятия решений; − тривиальные правила – содержат известную и легко объяснимую информацию, как правило, не приносят никакой пользы; − непонятные правила – содержат информацию, которая не может быть объяснена. Они требуют дополнительного анализа, и не могут быть применены для принятия решений. Оценка полезности ассоциативных правил Для оценки полезности ассоциативных правил используют следующие величины: Поддержка – показывает, какой процент транзакций поддерживает данное правило. Так как правило, строится на основании набора, то, значит, правило X=>Y имеет поддержку, равную поддержке набора F, который составляют X и Y: Supp X ⇒Y = Supp F = D F = X ∪Y D . (26) Достоверность – показывает вероятность того, что из наличия в транзакции набора X следует наличие в ней набора Y. Определяется отношением числа транзакций, содержащих наборы X и Y, к числу транзакций, содержащих набор X: Conf X ⇒Y = D F = X ∪Y DX = Supp X ∪Y . Supp X (27) Улучшение – показывает, полезнее ли правило случайного угадывания. Определяется отношением числа транзакций, содержащих наборы X и Y, к произведению количества транзакций с наборами X и Y: imprX ⇒Y = D F = X ∪Y D X DY = Supp X ∪Y . Supp X ∗ SuppY (28) Если улучшение больше 1, то это значит, что с помощью правила предсказать наличие набора Y вероятнее, чем случайное угадывание, если меньше единицы, то наоборот. 7.3. Алгоритм Apriori Выявление частых наборов объектов – операция, требующая большого количества вычислений, а, следовательно, и времени. Алгоритм Apriori использует одно из свойств поддержки: поддержка любого набора объектов не может превышать минимальной поддержки любого его подмножества. Алгоритм Apriori определяет часто встречающиеся наборы за несколько этапов. На некотором i-ом этапе определяются все часто встречающиеся i-элементные наборы. Каждый этап состоит из двух шагов: формирование кандидатов и подсчет поддержки кандидатов. На шаге формирования кандидатов алгоритм создает множество кандидатов из i-элементных наборов, чья поддержка пока не вычисляется. На шаге подсчета поддержки кандидатов алгоритм сканирует множество транзакций, вычисляя поддержку наборов-кандидатов. После сканирования отбрасываются кандидаты, поддержка которых меньше определенного пользовательского минимума и сохраняет только часто встречающиеся i-элементные наборы. Для 65 PDF created with pdfFactory Pro trial version www.pdffactory.com следующего за i-тым этапа, формирование кандидатов производится путем добавления к (i-1)-элементному частому набору элемента из другого частого набора. Разновидностью алгоритма Apriori являются алгоритм Apriori Tid. Отличительной чертой его является подсчет значения поддержки кандидатов не при сканировании множества D, а с помощью множества, являющегося множеством кандидатов (k – элементных наборов) потенциально частых, в соответствие которым ставится идентификатор TID транзакций, в которых они содержатся. Другой разновидностью является алгоритм MSAP, специально разработанный для выполнения сиквенциального анализа (предсказание появления события в будущем) сбоев телекоммуникационной сети. Алгоритм для поиска событий, следующих друг за другом, использует понятие «срочного окна». Это позволяет выявлять не просто одинаковые последовательности событий, а следующие друг за другом. 8. Кластеризация Первые публикации по кластерному анализу появились в конце 30-х годов прошлого столетия, но активное развитие этих методов и их широкое использование началось в конце 60-х – начале 70-х годов. Особенно расширилось их использование в связи с появлением и развитием ЭВМ и, в частности, персональных компьютеров. Это связано, прежде всего, с трудоемкостью обработки больших массивов информации. 8.1. Постановка задачи. Формальная постановка задачи Кластеризация отличается от классификации тем, что для проведения анализа не требуется иметь выделенную целевую переменную. Эта задача решается на начальных этапах исследования, когда о данных мало что известно. С этой точки зрения задача кластеризации является описательной задачей. Кластеризация – это поиск групп наиболее близких, похожих записей. После разбиения на кластеры начинается анализ с использованием других методов Data Mining. Кластерный анализ позволяет рассматривать достаточно большой объем информации, делая его более компактным и наглядным. Задача кластеризации состоит в разделении исследуемого множества объектов на группы «похожих» объектов, кластеры. Разбиение объектов осуществляется при одновременном их формировании. Определение кластеров выражается в итоговой модели данных, которая является решением задачи кластеризации. Решение задачи кластеризации зависит от природы объектов данных, от представления классов (кластеров), от предполагаемых отношений между объектами и кластерами. Формальная постановка задачи Дано: набор данных со следующими свойствами: − каждый экземпляр данных выражается четкими числовыми значениями; − класс для каждого конкретного экземпляра данных неизвестен. Найти: − способ сравнения данных между собой; − способ кластеризации; 66 PDF created with pdfFactory Pro trial version www.pdffactory.com − разбиение данных по кластерам. Формально задача кластеризации описывается следующим образом: Дано множество объектов данных I = {i1 , i2 ,..., in }, каждый из которых характеризуется набором параметров i j = {x1 , x 2 ,..., xm }, каждый из которых может принимать значения из некоторого множества. Требуется построить множество кластеров C = {c1 , c 2 ,..., c g }, каждый из которых содержит похожие друг на друга объекты из множества I. Требуется также найти отображение – F множества I на множество C: F : I → C , которое задает модель данных, являющуюся решением задачи. Кластер ck, входящий во множество C, содержит похожие друг на друга объекты из множества I: c k = {i j , i p i j ∈ I и d (i j , i p ) < σ }, (29) где σ – величина, определяющая меру близости для включения объектов в один кластер; d(ij, ip) – мера близости между объектами, называемая расстоянием. Если расстояние d(ij, ip) меньше некоторого значения σ, то говорят, что элементы близки и помещаются в один кластер. В противном случае элементы отличны друг от друга и помещаются в разные кластеры. Матрица отличия D есть матрица расстояний между всеми элементами множества I. Элементами матрицы являются значения d(ij, ip) в строке j и столбце p. Очевидно, что на главной диагонали значения будут равны нулю: d (e1 , e2 ) d (e1 ,en )     D =  d (e2 , e1 ) d (e2 ,en ) .  d (e , e ) d (e , e )  n 2  n 1  (30) Большинство алгоритмов работают с симметричными матрицами. Если матрица несимметрична, то ее можно привести к симметричному виду, путем преобразования (D + D m )/ 2 . 8.2. Меры близости, используемые при кластеризации Расстояния между объектами (рис.26) предполагают их представление в виде точек m-мерного пространства Rm. В этом случае могут быть использованы различные подходы к вычислению расстояний. Меры определяют расстояния между двумя точками, принадлежащие пространству входных переменных. Любую из приведенных мер расстояния можно выбирать с уверенностью лишь в том случае, если имеется информация о характере данных, подвергаемых кластеризации. Результатом кластерного анализа является набор кластеров, содержащих элементы исходного множества. Кластерная модель должна описывать как сами кластеры, так и принадлежность каждого объекта к одному из них. 67 PDF created with pdfFactory Pro trial version www.pdffactory.com Рис. 26. Меры близости, основанные на расстояниях Для небольшого числа объектов, характеризующихся двумя переменными, результаты кластерного анализа изображают графически. Элементы представляются точками, кластеры разделяются прямыми, которые описываются линейными функциями. Пример результата кластеризации в виде диаграммы представлен на рисунке 27. Рис. 27. Разделение на кластеры линиями Если кластеры нельзя разделить прямыми, то рисуются ломаные линии, которые описываются нелинейными функциями. В случае если элемент может принадлежать нескольким кластерам, то можно использовать Венские диаграммы, представленные на рисунке 28. Некоторые алгоритмы не просто относят элемент к одному из кластеров, а определяют вероятность его принадлежности. В этом случае удобнее представлять результат их работы в виде таблицы. В ней строки соответствуют элементам 68 PDF created with pdfFactory Pro trial version www.pdffactory.com исходного множества, столбцы – кластерам, а в ячейках указывается вероятность принадлежности элемента к кластеру. Рис. 28. Разделение на кластеры с использованием Венских диаграмм Ряд алгоритмов кластеризации строят иерархические структуры кластеров. В таких структурах самый верхний уровень соответствует всему множеству объектов. На следующем уровне он делится на несколько подкластеров. Каждый из них делится еще на несколько и т.д. Построение такой иерархии может происходить до тех пор, пока кластеры не будут соответствовать отдельным объектам. Такие диаграммы называются дендограммами. 8.3. Классификации и виды алгоритмов кластеризации При выполнении кластеризации важно, сколько в результате должно быть построено кластеров. Предполагается, что кластеризация должна выявить естественные локальные сгущения объектов. Поэтому число кластеров является параметром, часто существенно усложняющим вид алгоритма, если предполагается неизвестным, и существенно влияющим на качество результата, если оно известно. Проблема выбора числа кластеров весьма нетривиальна. Число методов разбиения на кластеры довольно велико. Все их можно разделить на методы: иерархические и неиерархические. В неиерархических алгоритмах требуется заранее регламентировать характер их работы и условие остановки довольно большим числом параметров, но в них достигается большая гибкость в варьировании кластеризации и обычно определяется число кластеров. В иерархических алгоритмах фактически отказываются от определения числа кластеров, строя полное дерево вложенных кластеров (дендрограмму). Они делятся на агломеративные и дивизимные. Агломеративные – Используется построение кластеров снизу вверх. Сначала все множество I представляется как множество кластеров, состоящих из одного 69 PDF created with pdfFactory Pro trial version www.pdffactory.com элемента. На следующем шаге выбираются два наиболее близких кластера и объединяются в один общий кластер. Дивизимные – Используют построение кластеров сверху вниз. Сначала все множество элементов I представляют как единственный кластер. На каждом шаге алгоритма один из существующих кластеров рекурсивно делится на два дочерних. К неиерархическим алгоритмам относят: − Алгоритм k-means – объекты отражаются в точке многомерного пространства, этот метод хорошо работает, если данные по своей естественной природе делятся на компактные, примерно сферические группы. Основной недостаток алгоритма – в силу дискретного характера элементов матрицы разбиения – большой размер пространства разбиения. − Алгоритм Fuzzy C-Means – является обобщением предыдущего алгоритма, с тем отличием, что кластеры теперь являются нечеткими множествами и каждая точка принадлежит различным кластерам с различной степенью принадлежности. Точка относится к тому или иному кластеру по критерию максимума принадлежности данному кластеру. Недостаток – ищет кластеры сферической формы. − Кластеризация по Гюстафсону-Кесселю – ищет кластеры в форме эллипсоидов, что делает его более гибким при решении различных задач. Кластеризация данных возможна также при помощи нечетких отношений (нечетких бинарных отношений), отношений α-квазиэквивалентности, которые можно применить из классической теории множеств. 9. Практическое применение некоторых методов и алгоритмов 9.1. Алгоритмы фильтрации, сглаживание данных При построении информационных технологий обработки данных приходится сталкиваться с решением задачи измерения параметров сигналов, которые характеризуют форму отдельных информативных фрагментов обрабатываемого сигнала. При анализе данных часто возникает задача их фильтрации, заключающаяся в устранении одной из составляющих зависимости y(xi). Наиболее часто целью фильтрации является подавление быстрых вариаций y(xt), которые чаще всего обусловлены шумом. В результате из быстро осциллирующей зависимости y(xi) получается другая, сглаженная зависимость, в которой доминирует более низкочастотная составляющая. Наиболее простыми и эффективными рецептами сглаживания (smoothing) можно считать регрессию различного вида. Однако регрессия часто уничтожает информативную составляющую данных, оставляя лишь наперед заданную пользователем зависимость. В связи с этим актуальной является задача построения эффективных алгоритмов сглаживания данных, которые в минимальной степени искажают форму информативных фрагментов сигналов. Проблемы подавления шума Компьютерная графика разделяется на три основных направления: визуализация, обработка изображений и распознавание образов. 70 PDF created with pdfFactory Pro trial version www.pdffactory.com Визуализация – это создание изображения на основе некоего описания (модели). К примеру, это может быть отображение графика, схемы, имитация трехмерной виртуальной реальности в компьютерных играх, в системах архитектурного проектирования и т.д. Основная задача распознавания образов – получение семантического описания изображенных объектов. Цели распознавания могут быть разными: как выделение отдельных элементов на изображении, так и классификация изображения в целом. В какой-то степени задача распознавания является обратной по отношению к задаче визуализации. Области применения – системы распознавания текстов, создание трехмерных моделей человека по фотографиям и т.д. Обработка изображений отвечает за преобразование (фильтрацию) изображений. Примерами могут служить повышение контраста, резкости, коррекция цветов, сглаживание. Задачей обработки изображения может быть как улучшение (восстановление, реставрация) изображения по какому-то определенному критерию, так и специальное преобразование, кардинально меняющее изображение. В последнем случае обработка изображений может быть промежуточным этапом для дальнейшего распознавания изображения (например, для выделения контура объекта). Методы обработки изображения могут существенно различаться в зависимости от того, каким путем изображение было получено – синтезировано системой машинной графики, либо путем оцифровки черно-белой или цветной фотографии или видео. В том случае, если изображение или видеопоследовательность были получены с помощью оцифровки, на них, как правило, присутствует шум. Проблема шумоподавления является одной из самых актуальных и распространенных проблем в области обработки как статичных изображений, так и видео. Чаще всего шумоподавление служит для улучшения визуального восприятия, но может также использоваться для каких-то специализированных целей – например, в медицине для увеличения четкости изображения на рентгеновских снимках, в качестве предобработки для последующего распознавания и т.д. Источники шума могут быть различными: − неидеальное оборудование для захвата изображения – видеокамера, сканер и т.д.; − плохие условия съемки – например, сильные шумы, возникающие при ночной фото/видеосъемке; − помехи при передаче по аналоговым каналам – наводки от источников электромагнитных полей, собственные шумы активных компонентов (усилителей) линии передачи (пример – телевизионный сигнал); − неточности (плохие фильтры) при выделении яркостного и цветоразностных сигналов из аналогового композитного сигнала и т. д. Соответственно, шумы тоже бывают разных видов. Самые распространенные: − белый шум – сигнал, отсчеты которого не коррелируют друг с другом, и его разновидность – белый гауссовский шум, который возникает, в частности, при плохих условиях приема сигнала и описывается следующей функцией плотности распределения амплитуд: 71 PDF created with pdfFactory Pro trial version www.pdffactory.com p(d ) = − 1 2πσ e d2 2σ 2 , где (31) d – амплитуда шума; σ – параметр распределения. − импульсный шум – случайные изолированные точки на изображении, значение которых значительно отличается от значений окружающих их точек (обычно возникает при передаче по аналоговым каналам); − цветные пятна – характерны для аналогового сигнала (к примеру, присутствуют в видеоизображении, оцифрованном с видеокассет VHS). Алгоритмы шумоподавления обычно специализируются на подавлении какогото конкретного вида шума. Не существует пока универсальных фильтров, детектирующих и подавляющих все виды шумов. Однако многие шумы можно довольно хорошо приблизить моделью белого гауссовского шума, поэтому большинство алгоритмов ориентировано на подавление именно этого вида шума. Основная проблема при пространственном шумоподавлении заключается в том, чтобы не испортить четкость краев предметов на изображении, а также мелкие детали, соизмеримые по амплитуде с шумом. Методы подавления шума Можно выделить следующие базовые подходы к пространственному шумоподавлению: 1) Линейное усреднение пикселей по соседям. 2) Медианная фильтрация. 3) Математическая морфология. 4) Гауссовское размытие. 5) Методы на основе Вейвлет-преобразования. 6) Метод главных компонент. 7) Анизотропная диффузия. 8) Фильтры Винера. Некоторые из этих методов применимы с небольшими модификациями также и во временной области. Заметим, что алгоритмы на основе Вейвлет-преобразования и метода главных компонент применяются, в основном, для обработки статичных изображений, хотя и обеспечивают наилучшее качество среди всех вышеперечисленных методов. Дело в том, что эти алгоритмы работают очень медленно и даже при хорошей оптимизации не могут обеспечить обработку в реальном времени, а при обработке видео скорость играет очень важную роль. Остановимся лишь на некоторых методах, т.к. цель данного раздела – сделать обзор о возможности применения в СППР некоторых методов и алгоритмов. Медианная фильтрация – это стандартный способ подавления импульсного шума. Однако в чистом виде медианный фильтр размывает мелкие детали, величина которых меньше размера окна для поиска медианы, поэтому на практике практически не используется. 72 PDF created with pdfFactory Pro trial version www.pdffactory.com Математическая морфология. Шумоподавление можно осуществлять с использованием двух основных морфологических операций: сужения (erosion) и расширения (dilation), а также их комбинаций – закрытия (closing) и раскрытия (opening). Раскрытие (сначала сужение, потом расширение) убирает выступы на границах объектов, а закрытие (сначала расширение, потом сужение) заполняет отверстия внутри и на границах. Изображения, обработанные этим методом, выглядят несколько искусственно, поэтому для обработки фотореалистичных изображений он не подходит. Вейвлет-преобразование – это инструмент многомасштабного анализа. Применительно к области шумоподавления оно позволяет удалять шум с изображения, не затрагивая значительно границы и детали. Также оно позволяет эффективно подавлять шумы со спектрами, отличными от белого. Метод главных компонент (МГК) позволяет выделить структуру в многомерном массиве данных и применяется в основном для распознавания или для сжатия изображений. В области шумоподавления этот подход является довольно новым и мало исследованным. Работает он лучше всего для изображений с белым гауссовским шумом. Фильтры Винера основаны на преобразовании Фурье и применяются, в основном, для подавления шума в аудио. На рисунке 29 можно увидеть реализацию метода линейного усреднения пикселей, как простейшую идею удаления шума – усреднять значения пикселей в пространственной окрестности. Рис. 29. Программное применение метода линейного усреднения пикселей Для каждого пикселя анализируются соседние для него пиксели, которые располагаются в некотором прямоугольном окне вокруг этого пикселя. Чем больше взят размер окна, тем сильнее происходит усреднение. Самый простой вариант фильтрации – в качестве нового значения центрального пикселя брать среднее арифметическое всех тех его соседей, значение которых отличается от значения центрального не более чем на некоторый порог. Чем больше величина этого порога, тем сильнее происходит усреднение. Вместо среднего арифметического соседей можно брать их взвешенную сумму, где весовой коэффициент каждого соседнего пикселя зависит либо от расстояния в пикселях от него до центрально пикселя, либо от разницы их значений. Эти алгоритмы очень простые, но они не дают хорошего результата. 73 PDF created with pdfFactory Pro trial version www.pdffactory.com 9.2. Алгоритм CART CART, сокращение от Classification And Regression Tree, переводится как «Дерево Классификации и Регрессии» – алгоритм бинарного дерева решений, впервые опубликованный Браманом и др. в 1984 году. Алгоритм предназначен для решения задач классификации и регрессии. Существует также несколько модифицированных версий – алгоритмы IndCART и DB-CART. Алгоритм IndCART, является частью пакета Ind и отличается от CART использованием иного способа обработки пропущенных значений, не осуществляет регрессионную часть алгоритма CART и имеет иные параметры отсечения. Алгоритм DB-CART базируется на следующей идее: вместо того чтобы использовать обучающий набор данных для определения разбиений, используем его для оценки распределения входных и выходных значений и затем используем эту оценку, чтобы определить разбиения. DB, соответственно, означает – «distribution based». Утверждается, что эта идея дает значительное уменьшение ошибки классификации, по сравнению со стандартными методами построения дерева. Основными отличиями алгоритма CART от алгоритмов семейства ID3 являются: бинарное представление дерева решений, функция, оценки качества разбиения, механизм отсечения дерева, алгоритм обработки пропущенных значений, построение деревьев регрессии. В алгоритме CART каждый узел дерева решений имеет двух потомков. На каждом шаге построения дерева правило, формируемое в узле, делит заданное множество примеров (обучающую выборку) на две части – часть, в которой выполняется правило (потомок – right) и часть, в которой правило не выполняется (потомок – left). Для выбора оптимального правила используется функция оценки качества разбиения. Функция оценки качества разбиения Оценочная функция, используемая алгоритмом CART, базируется на интуитивной идее уменьшения нечистоты (неопределённости) в узле. П р и м е р 5 . Рассмотрим задачу с двумя классами и узлом, имеющим по 50 примеров одного класса. Узел имеет максимальную «нечистоту». Если будет найдено разбиение, которое делит данные на две подгруппы 40:5 примеров в одной и 10:45 в другой, то интуитивно «нечистота» уменьшится. Она полностью исчезнет, когда будет найдено разбиение, которое создаст подгруппы 50:0 и 0:50. В алгоритме CART идея «нечистоты» формализована в индексе Gini. Если набор данных Т содержит данные n классов, тогда индекс Gini определяется как: n Gini(T) = 1 - ∑ pi2 , i =1 (32) где pi – вероятность (относительная частота) класса i в T. Если набор Т разбивается на две части Т1 и Т2 с числом примеров в каждом N1 и N2 соответственно, тогда показатель качества разбиения будет равен: Ginisplit ( T ) = N1 N Gini( T1 ) + 2 Gini( T2 ) . N N (33) Наилучшим считается то разбиение, для которого Ginisplit(T) минимально. Обозначим N – число примеров в узле-предке, L, R – число примеров соответственно в левом и правом потомке, li и ri – число экземпляров i-го класса в 74 PDF created with pdfFactory Pro trial version www.pdffactory.com левом/правом потомке. Тогда качество разбиения оценивается по следующей формуле: Ginisplit = n l  L  1− ∑  l  N  i =1  L   2  n  + R  1 − ∑  rl   → min .  N  i =1 R      2 (34) Чтобы уменьшить объем вычислений формулу можно преобразовать: 2  2  1   1 n 1 n    Ginisplit = L 1− ∑ (ll ) + R 1 − 2 ∑ (rl )   → min .  2     N L i =1 R i =1      (35) Так как умножение на константу не играет роли при минимизации, то: 2 2 1 n 1 n Ginisplit = L − ∑ (ll ) + R − ∑ (rl ) → min L i =1 R i =1 2 2 1 n 1 n Ginisplit = N −  ∑ (ll ) + ∑ (rl )  → min  L i =1  R i =1   (36) 2 2 1 n 1 n ~ Gini split = ∑ (ll ) + ∑ (rl ) → max L i =1 R i =1 ~ максимальна. В итоге, лучшим будет то разбиение, для которого величина G split Реже в алгоритме CART используются другие критерии разбиения Twoing, Symmetric Gini и др. Правила разбиения Каждый шаг построения дерева фактически состоит из совокупности трех трудоемких операций. Первое – сортировка источника данных по столбцу. Необходимо для вычисления порога, когда рассматриваемый в текущий момент времени атрибут имеет числовой тип. На каждом шаге построения дерева число сортировок будет как минимум равно количеству атрибутов числового типа. Второе – разделение источника данных. После того, как найдено наилучшее разбиение, необходимо разделить источник данных в соответствии с правилом формируемого узла и рекурсивно вызвать процедуру построения для двух половинок источника данных. Обе этих операции связаны (если действовать напрямую) с перемещением значительных объемов памяти. Здесь намеренно источник данных не называется таблицей, так как можно существенно снизить временные затраты на построение дерева, если использовать индексированный источник данных. Обращение к данным в таком источнике происходит не напрямую, а посредством логических индексов строк данных. Сортировать и разделять такой источник можно с минимальной потерей производительности. Третья операция, занимающая 60–80 % времени выполнения программы – ~ для всех возможных разбиений. Если у Вас n – числовых вычисление индексов G split атрибутов и m – примеров в выборке, то получается таблица n(m-1) – индексов, которая занимает большой объем памяти. Этого можно избежать, если использовать 75 PDF created with pdfFactory Pro trial version www.pdffactory.com один столбец для текущего атрибута и одну строку для лучших (максимальных) индексов для всех атрибутов. Можно и вовсе использовать только несколько числовых значений, получив быстрый, однако плохо читаемый код. Механизм отсечения дерева Механизм отсечения дерева, оригинальное название minimal cost-complexity tree pruning, – наиболее серьезное отличие алгоритма CART от других алгоритмов построения дерева. CART рассматривает отсечение как получение компромисса между двумя проблемами: получение дерева оптимального размера и получение точной оценки вероятности ошибочной классификации. Основная проблема отсечения – большое количество всех возможных отсеченных поддеревьев для одного дерева. Более точно, если бинарное дерево имеет |T| – листов, тогда существует ~[1.5028369|T|] отсечённых поддеревьев. И если дерево имеет хотя бы 1000 листов, тогда число отсечённых поддеревьев становится просто огромным. Базовая идея метода – не рассматривать все возможные поддеревья, ограничившись только «лучшими представителями». Чтобы определить качество разбиения CART просто игнорирует пропущенные значения. На рисунке 30 представлены две обучающие выборки, которые для наглядности представлены в декартовой системе координат. Рис. 30. Представление обучающей выборки на плоскости На рисунке 31 приведено дерево решений, построенное программой по обучающей выборке, используя выше рассказанный метод. Рис.31. Результаты построения деревьев решений методом CART 76 PDF created with pdfFactory Pro trial version www.pdffactory.com Алгоритм CART успешно сочетает в себе качество построенных моделей и, при удачной реализации, высокую скорость их построения. Включает в себя уникальные методики обработки пропущенных значений и построения оптимального дерева совокупностью алгоритмов cost-complexity pruning и V-fold cross-validation. 9.3. Алгоритм HITS Алгоритмы HITS (Kleinberg, 1999) и PageRank (реализован в Google) предназначены для поиска Интернет страниц, соответствующих запросу. Эти же алгоритмы позволяют искать похожие страницы (similar pages). Разработанные алгоритмы используют структуру ссылок в текстах, поэтому могут применяться к текстам на любом языке. Ссылки, связывающие страницы друг с другом, указываются экспертом. Предлагаемые алгоритмы применимы к корпусам текстов с гиперссылками и категориями. Эти тексты должны отвечать следующим условиям: − Каждому текстовому документу (статье) соответствует одно или несколько ключевых слов, отражающих содержание статьи. Например, в случае энциклопедии – энциклопедической статье соответствует одно слово – название статьи. − Статьи связаны ссылками. Для каждой статьи определены: набор исходящих ссылок (на статьи, которые упоминаются в данной статье) и входящих ссылок (на статьи, которые сами ссылаются на данную статью). − Каждая статья соотнесена одной или нескольким категориям (тематика статьи). Категории образуют дерево таким образом, что для каждой категории есть родитель-категория (кроме корня) и один или несколько детей-категорий (кроме листьев). Данная структура не является абстрактным измышлением. Она имеет конкретное воплощение в структурах типа вики (wiki), получивших широкое распространение в последнее время в Интернете, например, в виде электронной энциклопедии Википедия (на русском, английском и других языках). Задачу поиска похожих Интернет страниц Kleinberg сводит к задаче поиска похожих вершин в графе на основе вычисления весов вершин. Граф представляет взаимосвязь страниц, посредством ссылок, т.е. одни вершины будут ссылаться на другие, что отображено на рисунке 32. Рис.32. Граф ссылок 77 PDF created with pdfFactory Pro trial version www.pdffactory.com В связи с алгоритмом HITS возникают следующие проблемы: Поскольку рассматривается относительно небольшая часть графа, добавление ребер к нескольким узлам может серьезно изменить показатели концентраторов и авторитетов. В силу чего манипулировать этими показателями достаточно просто. Манипуляция ранжированием механизма поиска — серьезная проблема для Web. Если большая часть страниц в графе соседей относится к теме, которая отличается от темы запроса, авторитеты и концентраторы, получившие высокий рейтинг, могут относиться к другой теме. Эта проблема называется «смещением темы». Добавление весов к ребрам с учетом текста документов или их тезисов значительно смягчает негативный эффект этой проблемы. 9.4. Алгоритм Гюстафсона – Кесселя Кластеризация – это объединение объектов в группы (кластеры) на основе схожести признаков для объектов одной группы и отличий между группами. Большинство алгоритмов кластеризации не опираются на традиционные для статистических методов допущения; они могут использоваться в условиях почти полного отсутствия информации о законах распределения данных. Кластеризацию проводят для объектов с количественными (числовыми), качественными или смешанными признаками. Алгоритм включает в себя следующие шаги Шаг 1. Установить параметры алгоритма: С – количество кластеров; M – экспоненциальный вес; ε – параметр останова алгоритма. Шаг 2. Случайным образом сгенерировать матрицу нечеткого разбиения F, удовлетворяющую условиям (37) ∑ µ ki = 1,k = 1, M i = 1,C 0< ∑ µ ki < N ,i = 1,C k = 1, M (38) Шаг 3. Рассчитать центры кластеров m ∑ ( µ ki ) ⋅ X k Vi = k =1,N m ∑ ( µ ki ) i = 1,C (39) k =1,N Шаг 4. Рассчитать расстояния между объектами из X и центрами кластеров: Dki = X k − Vi 2 , k = 1, M , i = 1,C (40) Шаг 5. Пересчитать элементы матрицы нечеткого разбиения ( k = 1, M , i = 1,C ): если Dki > 0 , то µ ki = 1 1  ( m −1 )   2 1   Dik ⋅ ∑ 2   j =1,C D  jk   если Dki = 0 , то 78 PDF created with pdfFactory Pro trial version www.pdffactory.com ; (41) 1, j = i и j = 1,C (42) µ kj =  0 , j ≠ i 2 Шаг 6. Проверить условие F − F* < ε , где F * – матрица нечеткого разбиения на предыдущей итерации алгоритма. Если «да», то конец алгоритма, иначе – переход к шагу 3. Алгоритм Гюстафсона – Кесселя работает по такому же принципу, но расстояния между наборами из X и центрами кластеров высчитываются по следующей функции: 2 X − V B = ( X − V ) ⋅ B ⋅ ( X − V )T , (43) где B – матрица адаптивной нормы. При кластеризации оптимизируются не только координаты центров кластеров и матрица нечеткого разбиения, но также и норм-порождающие матрицы для всех кластеров. Это позволяет выделять кластера различной геометрической формы. Критерий оптимальности линеен относительно Вi, поэтому для получения ненулевых решений, вводят некоторые ограничения на норм-порождающие матрицы. В алгоритме Гюстафсона - Кесселя это ограничение на значение определителя норм - порождающих матриц: (44) Bi = β i , β i > 0 ,i = 1,C Оптимальное решение находится посредством метода неопределенных множителей Лагранжа. Алгоритм Гюстафсона – Кесселя, по сравнению с алгоритмом нечетких С-средних, обладает значительно большей вычислительной трудоемкостью. 9.5. Агломеративные алгоритмы Формально задача кластеризации описывается следующим образом. Пусть дан набор данных, обладающих следующими свойствами: − каждый экземпляр данных выражается четкими числовыми значениями; − класс для каждого конкретного экземпляра данных неизвестен. Требуется найти способ сравнения данных между собой, способ кластеризации, а также разбиение данных по кластерам. Эта задача может быть решена с помощью иерархических кластер – процедур. Иерархические (древообразные) процедуры являются наиболее распространенными алгоритмами кластерного анализа по их реализации на ЭВМ. Они бывают двух типов: агломеративные и дивизимные. Принцип работы иерархических агломеративных процедур состоит в последовательном объединении групп элементов сначала самых близких, а затем все более отдаленных друг от друга. Большинство этих алгоритмов исходит их матрицы расстояний (сходства). Матрица расстояний и меры близости Матрица сходства R есть квадратная матрица расстояний между всеми элементами множества исходных данных. Элементами матрицы являются значения 79 PDF created with pdfFactory Pro trial version www.pdffactory.com rij в строке i и столбце j, который определяет меру близости i-го элемента к j-му. Матрица расстояний имеет вид:  0  R =  r21 r  n1 r12 rn 2 r1n   r2 n  0  (45) Расстояния между объектами предполагают их представление в виде точек m-мерного пространства Rm. В этом случае могут быть использованы различные подходы к вычислению расстояний. Выбор способа вычисления элемента rij матрицы расстояний R является узловым моментом исследования, от которого в основном зависит окончательный вариант разбиения объектов на классы при данном алгоритме разбиения. Выбор способа определения расстояния определяется структурой признакового пространства и целью кластеризации. Рассмотрим меру близости, называемую обычное Евклидово расстояние. Данное расстояние используется для составления матрицы расстояний. Обычное Евклидово расстояние описывается формулой: pE = ( X i , X j ) = k ∑ (x l =1 il − x jl ) 2 , (46) где xij , x jl – величина l-ой компоненты у i-го (j-го) объекта (l=1,2..k; i, j=1,2..n). Использование этого расстояния оправданно в тех случаях, если: − Наблюдения берутся из генеральных совокупностей, имеющих многомерное нормальное распределение, т.е. компоненты множества исходных данных взаимно независимы и имеют одну и ту же дисперсию. − Компоненту вектора наблюдений однородны по физическому смыслу и одинаково важны для классификации. − Признаковое пространство совпадает с геометрическим пространством. В агломеративных иерархических процедурах особенно важно расстояние между группами элементов. Пусть Si – i-я группа (класс, кластер), состоящая из ni объектов; p( S , S ) – l m расстояние между группами S l и Sm. При этом расстоянии между классами Sl и S(m,q), являющимся объединением двух других кластеров Sm и Sq, можно определить по формуле: p( S i , S( m , q ) ) = αplm + βplq + γp mq − δ plm − plq , где (47) pim, piq, pmq – расстояния между кластерами Sl, Sm и Sq; α, β, γ, δ – числовые коэффициенты, значение которых определяет специфику процедуры, ее алгоритм. При α = β = - δ = 0,5, γ = 0 приходим к формуле «ближайшего соседа», а при α = β = δ = 0,5 и γ = 0 расстояние между классами определяется по принципу «дальнего соседа». Иерархические алгоритмы связаны с построением дендрограмм (от греческого dendron – «дерево»), которые являются результатом иерархического кластерного анализа. Дендрограмма описывает близость отдельных точек и кластеров друг к 80 PDF created with pdfFactory Pro trial version www.pdffactory.com другу, представляет в графическом виде последовательность объединения (разделения) кластеров. Дендрограмма (dendrogram) – древовидная диаграмма, содержащая n уровней, каждый из которых соответствует одному из шагов процесса последовательного укрупнения кластеров. Дендрограмму также называют древовидной схемой, деревом объединения кластеров, деревом иерархической структуры. Дендрограмма представляет собой вложенную группировку объектов, которая изменяется на различных уровнях иерархии. Существует много способов построения дендрограмм. В дендрограмме объекты могут располагаться вертикально или горизонтально. Пример вертикальной дендрограммы приведен на рисунке 33. Здесь по оси абсцисс откладываются номера точек, которые объединяются в кластеры. Рис.33. Вертикальная дендрограмма Агломеративные алгоритмы имеют свои преимущества и недостатки. Достоинствами данных алгоритмов можно считать простоту метода, прозрачность, возможность реализации на ЭВМ. К недостаткам агломеративных алгоритмов следует отнести громоздкость их вычислительной реализации. Алгоритмы требуют на каждом шаге вычисления матрицы расстояний, следовательно, емкости машинной памяти и большого количества времени. В этой связи реализация таких алгоритмов при числе наблюдений, большем нескольких сотен, нецелесообразна, а ряде случаев и невозможна. 9.6. Алгоритм K-MEANS Наиболее распространен среди неиерархических методов алгоритм k-средних, также называемый быстрым кластерным анализом. Полное описание алгоритма можно найти в работе Хартигана и Вонга (Hartigan and Wong, 1978). В отличие от иерархических методов, которые не требуют предварительных предположений относительно числа кластеров, для возможности использования этого метода необходимо иметь гипотезу о наиболее вероятном количестве кластеров. Алгоритм k-средних строит k кластеров, расположенных на возможно больших расстояниях друг от друга. Основной тип задач, которые решает алгоритм kсредних, это наличие предположений (гипотез) относительно числа кластеров, при этом они должны быть различны настолько, насколько это возможно. Выбор числа k может базироваться на результатах предшествующих исследований, теоретических соображениях или интуиции. Общая идея алгоритма: заданное фиксированное число k кластеров наблюдения сопоставляются кластерам так, что средние в кластере (для всех переменных) максимально возможно отличаются друг от друга. 81 PDF created with pdfFactory Pro trial version www.pdffactory.com Начальный шаг Выбирается число k, и на первом шаге эти точки считаются "центрами" кластеров. Каждому кластеру соответствует один центр. Выбор начальных центроидов может осуществляться следующим образом: − выбор k-наблюдений для максимизации начального расстояния; − случайный выбор k-наблюдений; − выбор первых k-наблюдений. В результате каждый объект назначен определенному кластеру. Итерации Вычисляются центры кластеров, которыми затем и далее считаются покоординатные средние кластеров. Объекты опять перераспределяются. Завершение процесса Процесс вычисления центров и перераспределения объектов продолжается до тех пор, пока не выполнено одно из условий: − кластерные центры стабилизировались, т.е. все наблюдения принадлежат кластеру, которому принадлежали до текущей итерации; − число итераций равно максимальному числу итераций. Выбор числа кластеров является сложным вопросом. Если нет предположений относительно этого числа, рекомендуют создать 2 кластера, затем 3, 4, 5 и т.д., сравнивая полученные результаты. После получений результатов кластерного анализа методом k-средних следует проверить правильность кластеризации (т.е. оценить, насколько кластеры отличаются друг от друга). Для этого рассчитываются средние значения для каждого кластера. При хорошей кластеризации должны быть получены сильно отличающиеся средние для всех измерений или хотя бы большей их части. Достоинства алгоритма: − простота использования; − быстрота использования; − понятность и прозрачность алгоритма. Недостатки алгоритма: − для работы с наборами данных, представленных в разных шкалах, необходимо привести данные к одной шкале либо вводить весовые коэффициенты; − необходимо заранее знать число кластеров, что на практике не всегда возможно; − алгоритм слишком чувствителен к выбросам, которые могут искажать значение среднего. Возможным решением этой проблемы является использование модификации алгоритма – алгоритм k-медианы; − алгоритм может медленно работать на больших базах данных. Возможным решением данной проблемы является использование выборки данных; − алгоритм работает только с числовыми данными. 82 PDF created with pdfFactory Pro trial version www.pdffactory.com 9.7. Генетические алгоритмы Одним из методов нахождения экстремумов сложных функций сегодня являются генетические алгоритмы. Генетический алгоритм – это одна из составляющих эволюционного моделирования как научного направления, базирующегося на принципах природного отбора по Ч. Дарвину. Основываясь на моделях, используемых в биологии и экономике, математик и психолог Джон Холланд (John Holland) разработал алгоритм генетической оптимизации, который впервые был предложен в 1975 г. в Мичиганском университете. Основной механизм эволюции – это естественный отбор. Его суть состоит в том, что более приспособленные особи имеют больше возможностей для выживания и размножения и, следовательно, приносят больше потомства, чем плохо приспособленные особи. При этом благодаря передаче генетической информации (генетическому наследованию) потомки наследуют от родителей основные их качества. Таким образом, потомки сильных индивидуумов также будут относительно хорошо приспособленными, а их доля в общей массе особей будет возрастать. После смены нескольких десятков или сотен поколений средняя приспособленность особей данного вида заметно возрастает. Генетический алгоритм – это простая модель эволюции в природе, реализованная в виде определенной последовательности действий. В нем используются как аналог механизма генетического наследования, так и аналог естественного отбора. При этом сохраняется биологическая терминология в упрощенном виде. При моделировании генетического наследования широко используются аналогии с биологическими понятиями (см. табл. 1). Таблица 1 Базовая терминология эволюционного моделирования Вектор (последовательность) из нулей и единиц. Хромосома Каждая позиция (бит) называется геном. Индивидуум = генетический код Набор хромосом = вариант решения задачи. Кроссовер Операция, при которой две хромосомы обмениваются своими частями. Мутация Случайное изменение одной или нескольких позиций в хромосоме. Приспособленность Значение целевой функции на данном индивидууме. индивидуума Выживание наиболее приспособленных Популяция следующего поколения формируется в соответствии с целевой функцией. Чем более приспособлен индивидуум, тем больше вероятность его участия в кроссовере. 83 PDF created with pdfFactory Pro trial version www.pdffactory.com Чтобы смоделировать эволюционный процесс, необходимо сгенерировать вначале случайную популяцию – несколько индивидуумов со случайным набором хромосом (числовых векторов). Генетический алгоритм имитирует эволюцию этой популяции как циклический процесс скрещивания индивидуумов и смены поколений. Жизненный цикл популяции – это несколько случайных скрещиваний (посредством кроссовера) и мутаций, в результате которых к популяции добавляется какое-то количество новых индивидуумов. Отбор в генетическом алгоритме – это процесс формирования новой популяции из старой, после чего старая популяция погибает. После отбора к новой популяции опять применяются операции кроссовера и мутации, затем опять происходит отбор, и так далее. Модель отбора определяет, каким образом следует строить популяцию следующего поколения. Как правило, вероятность участия индивидуума в скрещивании берется пропорциональной его приспособленности. Часто используется так называемая стратегия элитизма, при которой несколько лучших индивидуумов переходят в следующее поколение без изменений, не участвуя в кроссовере и отборе. В любом случае каждое следующее поколение будет в среднем лучше предыдущего. Когда приспособленность индивидуумов перестает заметно увеличиваться, процесс останавливают и в качестве решения задачи оптимизации берут наилучшего из найденных индивидуумов. Базовый генетический алгоритм 1) Инициировать начальный момент времени t=0. 2) Случайным образом сформировать начальную популяцию, состоящую из k особей, B0 = {A1,A2,…,Ak}. 3) Вычислить приспособленность каждой особи FAi = fit(Ai) , i=1..k и популяции в целом Ft = fit(Bt) (также иногда называемую термином фитнес). Значение этой функции определяет насколько хорошо подходит особь, описанная данной хромосомой, для решения задачи. 4) Выбрать особь Ac из популяции Ac = Get(Bt). 5) С определенной вероятностью (вероятностью кроссовера Pc) выбрать вторую особь из популяции Аc1 = Get(Bt) и произвести оператор кроссовера Ac=Crossing(Ac,Ac1). 6) С определенной вероятностью (вероятностью мутации Pm) выполнить оператор мутации Ac = mutation(Ac). 7) С определенной вероятностью (вероятностью инверсии Pi) выполнить оператор инверсии Ac = inversion(Ac). 8) Поместить полученную хромосому в новую популяцию insert(Bt+1,Ac). 9) Выполнить операции, начиная с пункта 3, k раз. 10) Увеличить номер текущей эпохи t=t+1. 11) Если выполнилось условие останова, то завершить работу, иначе переход на шаг 2. Принцип работы алгоритма отражен на рисунке 34. 84 PDF created with pdfFactory Pro trial version www.pdffactory.com Рис.34. Генетический алгоритм 85 PDF created with pdfFactory Pro trial version www.pdffactory.com Обычно оператор кроссовера оперирует двумя хромосомами. Существует много вариантов работы этого оператора, в частности, например, многоточечная рекомбинация – выбираются две и более точек разрыва, и родительские хромосомы обмениваются сегментами, которые находятся между этими точками. Мутация базируется на случайности. Оператор мутации M(x) = x' в каждой позиции аргумента с заданной вероятностью m заменяет ее содержимое элементом алфавита, выбор которого происходит в соответствии с равномерным распределением. Инверсия – изменение порядка следования частей хромосомы. Вероятности выбора родительских пар тоже могут определяться по-разному. Известны следующие способы: − панмиксия, когда родители выбираются из популяции случайным образом, так что один родитель может составлять пару с самим собой или участвовать в нескольких парах; − селекция, когда значения функции приспособленности родителей выше среднего значения по популяции; − инбридинг, когда первый родитель выбирается случайным образом, а вторым родителем с большей вероятностью является член популяции, ближайший к первому; − аутбридинг, когда первый родитель выбирается случайным образом, а вторым родителем с большей вероятностью является член популяции наиболее далекий от первого; − пропорциональный, когда родители выбираются с вероятностями, пропорциональными их значениям функции приспособленности. Существует также два механизма отбора членов новой популяции: элитный и отбор с вытеснением. В первом случае новая популяция состоит из наилучших членов репродукционной группы, которая объединяет в себе родителей, детей и мутантов. При отборе с вытеснением то что, будет ли член репродукционной группы вноситься в новую популяцию, определяется не только величиной ее приспособленности, но и тем, есть ли в новой популяции особь с аналогичным набором хромосом. Генетические алгоритмы ищут в чрезвычайно большом множестве решений наилучшее. Без использования генетического алгоритма во многих случаях массированный поиск решений был бы практически невозможен или неразумен. Генетические алгоритмы обеспечивают эффективный способ выполнения очень больших поисков, особенно когда нет простых эвристических методов решения поставленной задачи. Генетические алгоритмы представляют собой сравнительно новое направление. Они способны не только находить приемлемое решение и сокращать перебор в сложных задачах, но и легко адаптироваться к изменению проблемы. На сегодняшний день ведущие разработчики специализированных программных пакетов для ведения операций на фондовом рынке, моделирования распределенных компьютерных сетей, планирования бизнес-процессов уже используют решения, базирующиеся на использовании генетических алгоритмов (Например, TradeStation от Scientific Consultant Services). 86 PDF created with pdfFactory Pro trial version www.pdffactory.com Актуальность изучения генетических алгоритмов обусловлена их практической значимостью в различных областях человеческой деятельность. При профессиональном использовании генетические алгоритмы значительно расширяют области применения прогностических моделей. 9.8. Алгоритм метода скользящего окна Прогнозирование – установление функциональной зависимости между зависимыми и независимыми переменными. Прогнозирование направлено на определение тенденций динамики конкретного объекта или события на основе ретроспективных данных, т.е. анализа его состояния в прошлом и настоящем. Таким образом, решение задачи прогнозирования требует некоторой обучающей выборки данных. В самых общих чертах решение задачи прогнозирования сводится к решению таких подзадач: − выбор модели прогнозирования; − анализ адекватности и точности построенного прогноза. Временной ряд (time series) представляет собой упорядоченные во времени наблюдения (через равные интервалы времени). На основе анализа временных рядов можно строить прогнозы потребления на будущие периоды. Временной ряд состоит из нескольких компонент: тренд, сезонная компонента, циклическая компонента (стационарный случайный процесс) и случайная компонента. Под трендом понимается устойчивое систематическое изменение процесса в течение продолжительного времени. Оценка тренда осуществляется параметрическим и непараметрическим методами. Параметрический метод заключается в подборе гладкой функции, которая описывала бы тенденцию ряда: линейный тренд, полином и т.д. Непараметрический метод используется, когда нельзя подобрать гладкую функцию и заключается в механическом сглаживании временных рядов методом скользящей средней. Во временных рядах экономических процессов могут иметь место более или менее регулярные колебания. Если они имеют строго периодический или близкий к нему характер и завершаются в течение одного года, то их называют сезонными колебаниями. Оценка сезонной компоненты осуществляется двумя способами: с помощью тригонометрических функций и методом сезонных индексов. В тех случаях, когда период колебаний составляет несколько лет, то говорят, что во временном ряде присутствует циклическая компонента или стационарный случайный процесс. Существуют различные методы прогнозирования, основанные на анализе временных рядов, таких как: метод декомпозиции, скользящее среднее, экспоненциальное сглаживание, авторегрессионные модели, метод БоксаДженкинса, нейронные сети и др. Скользящее среднее значение – один из старейших и наиболее распространенных инструментов технического анализа. Сущность метода скользящих средних, заключающаяся в сглаживании рядов данных путем усреднения их значений в заданном периоде времени (математическое усреднение). 87 PDF created with pdfFactory Pro trial version www.pdffactory.com Существует несколько типов скользящих средних. Единственное, чем скользящие средние разных типов отличаются друг от друга, это разные весовые коэффициенты, которые присваиваются последним данным. Классификация скользящих средних по способу сглаживания − простые скользящие средние; − линейно взвешенные скользящие средние; − экспоненциально сглаженные скользящие средние. В случае простого скользящего среднего (SMA) все цены рассматриваемого периода имеют равный вес. В техническом анализе используются не только простые средние, но и взвешенные скользящие средние (WMA). Цене, по которой прошел больший объем при расчете средней цены за период придается соответственный больший вес. Но некоторые аналитики считали, последние цены имели большее значение. Экспоненциальные скользящие средние (EMA) – последние данные имеют больший вес. Их отличие как раз и заключается в том, что больший вес при расчете среднего значения за период придается недавним данным, а вес старых данных уменьшен. Следует отметить, что в результате применения различных методов прогнозирования могут быть получены различные прогнозы – это нормально и является особенностью работы того или иного метода. Методы прогнозирования чувствительны к шумам или выбросам, поэтому желательно перед прогнозированием провести предобработку данных. После прогнозирования мы проверяем полученную модель на адекватность, т.е. соответствие модели исследуемому объекту или процессу. Так как полного соответствия модели реальному процессу или объекту быть не может, адекватность – в какой-то мере – условное понятие. Модель временного ряда считается адекватной, если правильно отражает систематические компоненты временного ряда. Прогнозирование является распространенной и востребованной задачей во многих областях человеческой деятельности. В результате прогнозирования уменьшается риск принятия неверных, необоснованных или субъективных решений. Этапы прогнозирования Прогнозирование временного ряда заключает в себе следующие этапы: − Выдвижение гипотез (выдвижение гипотез производится экспертом, полагающимся, в значительной степени, на свой опыт и интуицию). − Сбор данных (очистка данных, поскольку в реальных данных почти всегда присутствуют пропуски, аномалии и т.д., что значительно ухудшает качество выборки). − Трансформация данных (является последним шагом перед построением прогностической модели, на этом шаге данные приводятся к виду, пригодному для использования различных способов построения моделей). − Построение моделей (в случае прогнозирования необходимо решать задачу регрессии: линейные модели – линейная регрессия, нелинейные – нейронные сети). 88 PDF created with pdfFactory Pro trial version www.pdffactory.com − Прогнозирование – после получения прогностической модели можно получить, собственно, сам прогноз. Описание метода Прогноз на основе скользящего среднего значения. При составлении прогноза этим методом используется значение средней арифметической величины потребления за последние периоды наблюдений. Скользящая средняя рассчитывается по следующей формуле: MA(n, k ) = n 1 ⋅ ∑ t( j) k j =n −k +1 , где (48) МА – скользящее среднее; n – число данных, используемых для прогноза; k – размер (длина) окна; t – значение показателя в j-ый момент времени. Для составления прогноза на основе скользящего среднего требуется определиться с количеством данных наблюдений n, которые будут использоваться в расчете. При этом необходимо учитывать особенности имеющегося временного ряда. Чем большее количество точек наблюдения берется в расчет, тем скользящая средняя менее чувствительна к изменениям значений в прошлые периоды. Преимущество метода прогнозирования по скользящей средней заключается в его простоте. Основным недостатком же является то, что значимость значений прошлых периодов при прогнозировании будущих значений одинакова. Между тем очевидно, что значимость статистики последнего из предшествующих периодов более велика, чем предыдущих. Метод скользящего среднего применять достаточно несложно, однако он слишком прост для создания точного прогноза. При использовании этого метода прогноз любого периода представляет собой не что иное, как получение среднего показателя нескольких результатов наблюдений временного ряда. Вычисления с помощью этого метода довольно просты и достаточно точно отражают изменения основных показателей предыдущего периода. Если для прогнозирования значений в будущем воспользоваться средним значением показателя за все периоды, вероятно, можно получить результат, несколько завышенный по сравнению с фактическим. Но если прогноз будет составлен на основании данных всего лишь за несколько последних периодов, то он намного точнее отразит тенденцию. Таким образом, чем меньше число результатов наблюдений, на основании которых вычислено скользящее среднее, тем точнее оно отражает изменения в уровне базовой линии. Достоинства метода: − простота и быстрота использования; − понятность и прозрачность метода; − подходит к любым количественным данным; − используется для сглаживания данных; − позволяет уловить тенденцию в динамике данных. 89 PDF created with pdfFactory Pro trial version www.pdffactory.com Недостатки метода: − алгоритм работает только с числовыми данными; − чувствительность среднего зависит от числа используемых данных; − не дает точного прогноза из-за одинакового веса (значимости) прошлых и будущих отчетов. 10. Стандарты Data Mining Стандарты затрагивают три основных аспекта Data Mining, которые и будут нами рассмотрены ниже. 10.1. Стандартизация Data Mining. Основные аспекты К аспектам относят, во-первых, унификацию интерфейсов, посредством которых любое приложение может получить доступ к функциональности Data Mining. Здесь сложилось два направления. Это стандартизация интерфейсов для объектных языков программирования (CWM Data Mining, JDM, OLE DB for Data Mining) и попытки разработки надстройки для языка SQL, которая позволяла бы обращаться к инструментарию Data Mining, встроенному непосредственно в реляционную базу данных. Второй аспект стандартизации – это выработка единого соглашения по хранению и передаче моделей Data Mining. Основой для подобного стандарта является язык XML. Сам стандарт носит название PMML (Predicted Model Markup Language). И третьим является, существующий стандарт CRISP, который дает рекомендации по организации процесса Data Mining в целом. Отношения между стандартами представлены на рисунке 35. Рис. 35. Отношения между основными стандартами Data Mining 10.2. Стандарт CWM Стандарт CWM(Common Warehouse Metamodel) – это стандарт, разработанный консорциумом OMG для обмена метаданными между различными программными продуктами и репозиториями, участвующими в создании корпоративных СППР. Он основан на открытых объектно-ориентированных технологиях и стандартах, использует UML (Unified Modeling Language) в качестве языка моделирования, XML и XMI для обмена метаданными и язык программирования JAVA для реализации моделей и спецификаций. 90 PDF created with pdfFactory Pro trial version www.pdffactory.com Для представления всевозможных метаданных, используемых в области хранилищ данных и аналитических систем, необходимы общие и достаточно универсальные стандарты. В настоящее время существует единый официально признанный стандарт CWM 1.0. В основе CWM лежит модельно-ориентированный подход к обмену метаданными, согласно которому объектные модели, представляющие специфические для конкретного продукта метаданные, строятся в соответствии с синтаксическим и семантическими спецификациями некоторой общей метамодели. CWM имеет модульную структуру, что позволяет минимизировать зависимости между различными компонентами, уменьшить сложность и повысить наглядность модели. Под модулем в данном случае понимается отдельная метамодель, предназначенная для представления определенного типа метаданных хранилища. Каждая метамодель реализована в виде пакета, содержащего набор описанных на UML базовых классов. Все пакеты структурированы и распределены по четырем слоям. Объектное ядро (Object Model) включает четыре пакета: − Сore (ядро) – содержит классы и ассоциации, которые формируют ядро объектной модели CWM и используется всеми другими пакетами, включая пакеты Object Model; − Behavior (поведение) – содержит классы и ассоциации, которые описывают поведение CWM-объектов и обеспечивают основу для описания вызовов, определенных поведением; − Relationships (отношения) – содержит классы и ассоциации, которые описывают отношения между CWM-объектами; − Instance (экземпляр) – содержит классы и ассоциации, которые представляют классификаторы CWM. Самый нижний слой метамодели CWM – Foundation (основа) – состоит из пакетов, которые поддерживают спецификацию базовых структурных элементов, таких как выражения, типы данных, типы отображений и др. Все они совместно используются пакетами верхних уровней. В него входят следующие пакеты: − бизнес-информация – содержит классы и ассоциации, которые представляют бизнес – информацию об элементах модели; − типы данных – содержит классы и ассоциации, которые представляют конструкторы, используемые при необходимости для создания специфичных типов данных; − выражения – содержит классы и ассоциации, которые представляют деревья выражений; − ключи и индексы – содержит классы и ассоциации, которые представляют ключи и индексы; − отображение типов – содержит классы и ассоциации, которые представляют отображение типов данных между разными системами; − размещение программ – содержит классы и ассоциации, которые описывают способ размещения программного обеспечения в хранилище данных. 91 PDF created with pdfFactory Pro trial version www.pdffactory.com Второй слой – Resource (ресурс) – содержит пакеты, используемые для описания информационных источников и целевых баз данных: − реляционный – представляют метаданные реляционных источников данных; − запись – представляют отдельные записи источников данных; − многомерный – представляют метаданные многомерных источников данных; − XML – описывают метаданные источников данных, представленных в формате XML. Третий слой называется Analysis (анализ) и содержит моделирования процессов или служб информационного анализа, включая визуализацию и распространение данных, многомерный анализ, извлечение знаний и др. Он содержит пакеты: − преобразование – представляют инструментарий преобразования данных; − OLAP – представляют метаданные инструментов оперативного анализа данных; − Data Mining – представляют метаданные инструментов Data Mining; Данный пакет разделен на три концептуальные области: Model – описание метаданных моделей, получаемых в результате работы методов Data Mining; Settings – описание метаданных настроек процесса построения моделей; Attributes – описание метаданных для атрибутов данных. Метамодель Model – состоит из общего представления моделей Data Mining. Она представляет собой структуру, описывающую результат работы алгоритмов Data Mining. Метамодель Settings – конкретизирует настройки процесса построения моделей и их отношения с атрибутами входной спецификации. Метамодель Attributes – описывает два подкласса для разных типов атрибутов. Таким образом, в пакете Data Mining стандарта CWM описаны все основные метаданные, необходимые для реализации соответствующих методов в СППР. Описанные классы могут быть расширены в зависимости от конкретных задач, но их использование гарантирует, что такая реализация будет совместима с другими системами, поддерживающими стандарт CWM. − информационная визуализация – содержит классы и ассоциации, которые представляют метаданные инструментов визуализации информации; − бизнес-номенклатура – представляют метаданные таксономии и глоссарии бизнеса. Четвертый слой – Management (управление) – состоит из пакетов, относящихся к особенностям функционирования хранилища. Эти средства позволяют моделировать процедуры по управлению хранилищем, устанавливать регламент их выполнения, специфицировать процессы контроля и протоколирования для загрузки информации и произведенных корректировок данных хранилища. В его состав входят два пакета: − процессы хранилища данных – представляют метаданные процессов хранилищ данных; − операции хранилища данных – представляют метаданные результатов операций хранилищ данных. 92 PDF created with pdfFactory Pro trial version www.pdffactory.com 10.3. Стандарт CRISP С ростом интереса к Data Mining возрастала и необходимость в разработке методологии создания таких систем. Эти потребности призван удовлетворить стандарт CRISP-DM (Cross-Industry Standard Process for Data Mining) – непатентованная, документированная и свободно доступная модель, описывающая основные фазы, выполнение которых позволяет организациям получать максимальную выгоду от использования методов Data Mining. Стандарт CRISP-DM описывается в терминах, иерархической модели процесса. Модель состоит из набора задач, описанных на четырех уровнях абстракции: фазы, общие задачи, специализированные задачи и примеры процессов. На верхнем уровне выделяется несколько фаз разработки. Каждая из них включает в себя несколько общих задач, относящихся ко второму уровню иерархии. Второй уровень называется общим ввиду того, что задачи, составляющие его, не учитывают особенностей прикладной области, для которой они решаются. Предполагается, что они являются законченными и неизменными. Законченность означает покрытие, как всего процесса, так и возможных приложений Data Mining. Неизменность означает, что модель должна быть актуальной и для неизвестных до сих пор методов Data Mining. Третий уровень специализированных задач включает описание шагов, необходимых для адаптации общих задач к решению специализированных проблем. На четвертом уровне представлены действия, решения и результаты реально встречающиеся в Data Mining. Данный уровень организован в соответствии с задачами верхнего уровня, но в то же время представляет собой конкретные практические задачи. CRISP-DM делит жизненный цикл проекта Data Mining на шесть фаз: − понимание бизнес-процессов; − понимание данных; − подготовка данных; − моделирование; − оценка; − размещение. Перечисленные фазы и взаимоотношения между ними представлены на рисунке 36, где стрелками изображены более важные и частые зависимости между фазами. Внешние стрелки, имеющие циклическую природу, иллюстрируют спиралеобразный процесс разработки проектов Data Mining. Фаза понимания бизнес-процессов В этой фазе должно быть уделено достаточно внимания целям проекта с точки зрения перспективности бизнеса, определения знаний в формулировке Data Mining проблемы и дальнейшей разработки первичного плана достижения целей. Чтобы понять, какие данные и как в дальнейшем они должны быть проанализированы, важным является полностью понять бизнес, для которого происходит поиск решения. Эта фаза включает следующие задачи: определение бизнес – целей, определение ситуации, определение целей Data Mining, создание плана проекта. 93 PDF created with pdfFactory Pro trial version www.pdffactory.com Фаза понимания данных Начинается фаза с первоначального сбора данных. Затем более близкое знакомство с ними с целью идентифицировать проблемы качества данных, исследовать их суть и выявить интересные поднаборы для формирования гипотез о скрытых знаниях. В этой фазе выполняются четыре общие задачи: первичный сбор данных, описание данных, изучение данных, проверка качества данных. Рис. 36. Жизненный цикл процесса Data Mining Фаза подготовки данных Включает в себя все действия, связанные с окончательным формированием набора данных для анализа. При этом выполняется пять задач: выбор данных, очистка данных, конструирование данных, интеграция данных, форматирование данных. Фаза моделирования Предназначена для выбора оптимального метода построения моделей и настройки его параметров для получения оптимальных решений. Обычно для одних и тех же проблем Data Mining существуют несколько методов решения. Некоторые из них накладывают определенные требования на данные, поэтому может понадобиться возврат на предыдущую фазу. В данной фазе решаются следующие задачи: выбор метода моделирования, генерация текстового проекта, создание моделей, оценка моделей. Фаза оценки На этой фазе более основательно оценивается модель до процесса ее окончательного размещения, чтобы убедиться в достижимости поставленных бизнес-целей. В конце этой фазы руководитель проекта должен решить, как дальше использовать результаты Data Mining. Фаза включает следующие задачи: оценка результатов, пересмотр процесса, определение дальнейших действий. Фаза размещения Служит для организации знаний и их представления в удобном для пользователя виде. В зависимости от требований фаза размещения может быть как простой, так и 94 PDF created with pdfFactory Pro trial version www.pdffactory.com сложной. На этой фазе решаются следующие задачи: планирование размещения, планирование наблюдения и сохранения, производство конечных отчетов. 10.4. Стандарт PMML Стандарт PMML (Predicted Model Markup Language) предназначен для обмена построенными mining-моделями между системами Data Mining. Данный стандарт описывает форму представления моделей в виде XML-документа. PMML – достаточно молодой стандарт, и нуждается в дальнейшем совершенствовании. Однако можно смело утверждать, что в настоящее время он имеет наибольшее практическое значение из всех стандартов Data Mining. Он активно используется разработчиками, т.к. позволяет системам обмениваться знаниями в унифицированном виде. Структура моделей описывается с помощью DTD-файла, который называется PMML DTD. Корневым элементом PMML-документа является тег . Первым элементом PMML-документа является заголовок – Header. Он содержит информацию о приложении, сформировавшем описываемую модель: название, версию, описание и т.п. В зависимости от операции, над описываемыми полями, их типы разделяют на три вида: категориальные – выполняется операция сравнения на равенство; упорядоченные – могут выполняться операции сравнения на больше или меньше; непрерывные – могут выполняться арифметические операции. PMML описывает разные виды простых преобразований данных: нормализация – отображает непрерывные или дискретные значения в числовые, дискретизация – отображает непрерывные значения в дискретные, отображения – отображает одни дискретные значения в другие, агрегация – суммирует или собирает группы значений. В PMML-документе могут описываться несколько моделей. Кроме того, список моделей в PMML-документе может быть пуст. Такой документ можно использовать не для передачи моделей, а для передачи первоначальных метаданных до построения модели. PMML 2.0 поддерживает следующие типы моделей: − ассоциативные правила – модель представляет правила, где некоторый набор элементов ассоциируется с другим набором элементов; − деревья решений – позволяют описать классификационные или предсказательные структуры. Каждый узел содержит логическое выражение, которое описывает правило выбора узла или ветви; − кластеры – различают два вида кластерных моделей: основанных на центрах и на расстояниях. Для моделей, основанных на центре, кластер описывается вектором координат центра. Для моделей, основанных на расстояниях, кластеры описываются их статистикой; − регрессия – функции регрессии используются, чтобы определить отношение между зависимой переменной и одной или несколькими независимыми переменными; − нейронные сети – имеют один или более входных узлов и один или более нейронов. Некоторые выходы нейронов являются выходами сети. Сеть описывается нейронами и их соединениями. Все нейроны организуются в уровни, последовательность уровней описывает порядок выполнения 95 PDF created with pdfFactory Pro trial version www.pdffactory.com вычислений. Модель не описывает процесс эволюции нейронной сети, представляя только конечный результат; − результат метода Naive Bayes – данная модель по существу описывает набор матриц. Для каждой независимой переменной описывается матрица, которая содержит частоту его значений относительно значений зависимой переменной; − последовательность – данная модель состоит из последовательности объектов, идентифицируемых первичным ключом, некоторые результаты которых описываются вторичным ключом. Каждый результат состоит из набора упорядоченных элементов. Поле «порядок» описывает порядок элементов в результате. 10.5. Библиотеки Data Mining Xelopes – свободно распространяемая библиотека, разработанная компанией Prudsys в тесном сотрудничестве со специалистами российской фирмы ZSoft. Архитектура библиотеки соответствует стандарту MDA от консорциума OMG, что позволило реализовать ее на языках Java, C# и С++. Основная идея стандарта MDA заключается в разработке базовой платформонезависимой модели, которая отображается в одну или более платформозависимых моделей. В данном случае под платформой понимается реализация на конкретном языке программирования. В основу PIM-библиотеки легли UML-диаграммы пакета Data Mining стандарта CWM. Были использованы диаграммы: − Model – диаграмма, представляющая Data Mining модель в целом; − Settings – диаграмма, представляющая настройки процесса Data Mining; − Attribute – диаграмма, представляющая описание атрибутов Data Mining. В Xelopes эти диаграммы расширены новыми классами, методами и интерфейсами. Классы пакета Model расширяют классы из одноименного пакета стандарта CWM и описывают различные модели. Например, статическая модель, модель ассоциированных правил, деревья решений, кластерная модель, модель сиквенциального анализа и др. Классы пакета Settings расширяют классы из одноименного пакета стандарта CWM и описывают классы настроек. Например, настройки для создания статической модели, модели ассоциативных правил, деревьев решений, кластерной модели, модели сиквенциального анализа и др. Классы пакета Attribute расширяют классы из одноименного пакета стандарта CWM и описывают различные типы атрибутов данных: числовые, категориальные, категориально – иерархические и др. Библиотека Xelopes предназначена для использования во всем процессе Data Mining, поэтому дополнительно были добавлены четыре UML-диаграммы, представляющие следующие концептуальные области: − Data Access – диаграмма, описывающая доступ к Data Mining алгоритмам; − Algorithms – диаграмма, описывающая процесс создания Data Mining моделей; − Automation – диаграмма, описывающая автоматический выбор параметров Data Mining алгоритмов; 96 PDF created with pdfFactory Pro trial version www.pdffactory.com − Transformation – диаграмма, описывающая процесс преобразования данных для моделирования Data Mining. Пакет Algorithms включает классы, реализующие алгоритмы построения различных моделей. Например, статистической модели, модели ассоциативных правил, деревья решений, кластерной модели, модели сиквенциального анализа и др. Пакет Data Access включает классы, реализующие унифицированный доступ к различным источникам информации. Например, таким как файлы формата ARFF, файлы протоколов Web-серверов, базы данных и др. Пакет Transformation содержит классы для реализации пошаговой концепции преобразования данных. Они опираются на стандарт CWM. К основным достоинствам библиотеки относится следующее: − свободно распространяемая – библиотека доступна для свободного использования. Кроме того, разработчики могут самостоятельно добавлять в нее новые алгоритмы; − независимость от платформы – так как базовое ядро сформировано в UML, то могут быть получены реализации практически на любом объектноориентированном языке; − независимость от исходных данных; − поддержка всех стандартов Data Mining. Также в библиотеке реализованы адаптеры к популярной библиотеке Weka. Основной подход решения задач Data Mining с помощью библиотеки Xelopes не зависит от вида или используемого метода и включает в себя выполнение следующих шагов: 1) Загрузка исходных данных. 2) Настройка процесса построения моделей: − общих для модели; − специфичных для алгоритма. 3) Инициализация алгоритма. 4) Построение модели. 5) Применение построенной модели для задач с учителем. При решении задач с учителем построенная модель может применяться к новым данным. В заключении приведем схему реализации ядра библиотеки Xelopes на трех языках (рис.37). Рис. 37. Ядро библиотеки Xelopes 97 PDF created with pdfFactory Pro trial version www.pdffactory.com Список литературы 1. Алиев, Т. М. Системы отображения информации: учеб. пособие для вузов по спец. «Автом. сист. обр. информ. и упр.» / Т. М. Алиев, Д. И. Вигдоров, В. П. Кривошеев – М.: Высш. шк., 1988. – 201 с. 2. Андон, А. И. Логические модели интеллектуальных информационных систем / А. И. Андон, А. Е. Яшунин, А. А. Резниченко – Киев: Наук. думка, 1999. – 396 с. 3. Базы данных. Интеллектуальная обработка информации / В. В. Корнеев, [и др.] – М.: Нолидж, 2003. – 352 с. 4. Дьяконов, В. П. Компьютерная математика. Теория и практика / В. П. Дьяконов – М.: Нолидж, 2001. – 1294 с. 5. Карташев, В. Г. Основы теории дискретных сигналов и цифровых фильтров / В. Г. Карташев – М.: Высш.шк., 1982. – 109 с. 6. Куприянов, М. С. Использование таблиц решений для проектирования быстродействующих микропроцессорных систем / М. С. Куприянов, У. Неддермайер, А. А. Баргесян // Микропроцессорные системы. – Л., 1981. – С. 63 – 79. 7. Методы и модели анализа данных: OLAP и Data Mining / А. А. Барсегян, [и др.] – СПб.: БХВ – Петербург, 2004. – 336 с. 8. Подход к организации терминальных процессоров для человеко-машинного управления / А. А. Баргесян, [и др.] // Диалог «Человек – ЭВМ». – Л., 1982. – C. 83 – 86. 9. Сергиенко, А. Б. Цифровая обработка сигналов: учебник для вузов / А. Б. Сергиенко – 2-е изд. – СПб.: Питер, 2006. – 751 с. 10. Соммервилл, И. Инженерия программного обеспечения / И. Соммервилл – 6е изд.; пер. с англ. – М.: Вильямс, 2002. – 624 с. 11. Трахтенгерц, Э. А. Компьютерная поддержка принятия решений / Э. А. Трахтенгерц – М., 1998. – С. 49 – 56. 12. Финк, Л. М. Сигналы, помехи, ошибки. Заметки о некоторых неожиданностях, парадоксах и заблуждениях в теории связи / Л. М. Финк – 2-е изд., перераб. и доп. – М.: Радио и связь, 1984. – 246 с. 13. Цыганенко, В. Н. Предальтернансное прореживание временных рядов при подготовке данных к анализу наилучшим равномерным приближением // Молодежь и современные информационные технологии: сб. трудов IV Всерос. науч. практ. конф. / В. Н. Цыганенко, А. Г. Белик – Томск, 2006. – С. 162-164. 14. Berson, А. Data Warehousing, Data Mining & OLAP / А. Berson, S. J. Smith McGraw – Hill, 1997. – 640 p. 98 PDF created with pdfFactory Pro trial version www.pdffactory.com 99 PDF created with pdfFactory Pro trial version www.pdffactory.com 100 PDF created with pdfFactory Pro trial version www.pdffactory.com