Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Государственное образовательное учреждение высшего профессионального образования
«ОМСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»
Конспект лекций
по дисциплине «Компьютерные технологии»
направление подготовки магистров
230100.68 Информатика и вычислительная техника
по профилю подготовки
«Компьютерный анализ и интерпретация данных»
Омск 2011 г.
Лекция 1.
Введение в анализ данных
Анализ данных — широкое понятие. Сегодня существуют десятки его определений. В самом общем смысле анализ данных — это исследования, связанные с обсчетом многомерной
системы данных, имеющей множество параметров. В процессе анализа данных исследователь
производит совокупность действий с целью формирования определенных представлений о
характере явления, описываемого этими данными. Как правило, для анализа данных
используются различные математические методы.
Анализ данных нельзя рассматривать только как обработку информации после ее сбора.
Анализ данных — это прежде всего средство проверки гипотез и решения задач
исследователя.
Известное противоречие между ограниченными познавательными способностями человека и бесконечностью Вселенной заставляет нас использовать модели и моделирование, тем самым упрощая изучение интересующих объектов, явлений и систем.
Слово «модель» (лат. modelium) означает «меру», «способ», «сходство с какой-то вещью». Построение моделей — универсальный способ изучения окружающего мира, позволяющий обнаруживать зависимости, прогнозировать_)Y__, разбивать на группы и решать множество других задач. Основная цель моделирования в том, что модель должна достаточно хорошо отображать функционирование моделируемой системы.
Модель — объект или описание объекта, системы для замещения (при определенных условиях, предположениях, гипотезах) одной системы (то есть оригинала) другой системой для лучшего изучения оригинала или воспроизведения каких-либо его свойств
Моделирование — универсальный метод получения, описания и использования
знаний. Применяется в любой профессиональной деятельности.
По виду моделирования модели делят:
§ на эмпирические — полученные на основе эмпирических фактов, зависимостей;
§ теоретические — полученные на основе математических описаний, законов;
§ смешанные, полуэмпирические — полученные на основе эмпирических зависимостей и математических описаний.
Нередко теоретические модели появляются из эмпирических, например, многие законы физики первоначально были получены из эмпирических данных.
Таким образом, анализ данных тесно связан с моделированием.
Отметим важные свойства любой модели.
§ Упрощенность. Модель отображает только существенные стороны объекта и, кроме того, должна быть проста для исследования или воспроизведения.
§ Конечность. Модель отображает оригинал лишь в конечном числе его отношений, и, кроме того, ресурсы моделирования конечны.
§ Приближенность. Действительность отображается моделью грубо или приближенно.
§ Адекватность. Модель должна успешно описывать моделируемую систему.
§ Целостность. Модель реализует некоторую систему (то есть целое).
§ Замкнутость. Модель учитывает и отображает замкнутую систему необходимых основных гипотез, связей и отношений.
§ Управляемость. Модель должна иметь хотя бы один параметр, изменениями которого можно имитировать поведение моделируемой системы в различных условиях.
Принципы анализа данных
Процесс анализа
В информационном подходе к анализу данных помимо модели присутствуют еще три важные
составляющие: эксперт, гипотеза и аналитик.
Эксперт — специалист в предметной области, профессионал, который за годы обучения и практической деятельности научился эффективно решать задачи, относящиеся к конкретной предметной области.
Эксперт — ключевая фигура в процессе анализа. По-настоящему эффективные аналитические решения можно получить не на основе одних лишь компьютерных программ, а в результате сочетания лучшего из того, что может человек и компьютер. Эксперт выдвигает гипотезы (предположения) и для проверки их достоверности либо просматривает некие выборки различными способами, либо строит те или иные модели.
Аналитик — специалист в области анализа и моделирования. Аналитик на достаточном уровне владеет какими-либо инструментальными и программными средствами анализа данных, например методами Data Mining. Кроме того, в обязанности аналитика входят функции систематизации данных, опроса мнений экспертов, координации действий всех участников проекта по анализу данных.
Аналитик играет роль «мостика» между экспертами, то есть является связующим звеном между специалистами разных уровней и областей. Он собирает у экспертов различные гипотезы, выдвигает требования к данным, проверяет гипотезы и вместе с экспертами анализирует полученные результаты. Аналитик должен обладать системными знаниями, так как помимо задач анализа на его плечи часто ложатся технические вопросы, связанные с базами данных, интеграцией с источниками данных и производительностью.
Поэтому в дальнейшем главным лицом в анализе данных мы будем считать аналитика,
предполагая, что он тесно сотрудничает с экспертами предметных областей.
Несмотря на то что существует множество аналитических задач, методы их решения можно разделить на две основные группы методов их решения (рисунок 1):
§ извлечение и визуализация данных;
§ построение и использование моделей.
Извлечение и визуализация данных
Чтобы получить новые знания об исследуемом объекте или явлении, не обязательно строить сложные модели. Часто достаточно «посмотреть» на данные в нужном виде, чтобы сделать определенные выводы или выдвинуть предположение о характере зависимостей в системе, получить ответ на интересующий вопрос. Это помогает сделать визуализация.
В случае визуализации аналитик некоторым образом формулирует запрос к информационной системе, извлекает нужную информацию из различных источников и просматривает полученные результаты. На их основе он делает выводы, которые и являются результатом анализа. Существует множество способов визуализации данных:
§ OLAP (кросс-таблицы и кросс-диаграммы);
§ таблицы;
§ диаграммы, гистограммы;
§ карты, проекции, срезы и т. п.
Лекция 2
Системы обработки данных (СОД)
СОД – это совокупность технических средств и программного обеспечения предназначенная для информационного обслуживания пользователей и технических объектов. В состав технических средств входит оборудование для ввода, хранения, преобразования и вывода данных, в том числе ЭВМ, устройства сопряжения с ЭВМ, аппаратура передачи.
Программное обеспечение (ПО) – это совокупность программ, реализующих возложенные на систему функции.
Функции СОД состоят в выполнении требуемых актов обработки данных: ввода, хранения, преобразования и вывода. Примером СОД являются вычислительные системы для решения научных, инженерно-технических, планово-экономических, и учебно-статистических задач. Основой СОД являются технические средства, т.к. их производительностью и надежностью в наибольшей степени определяется эффективность СОД.
Типы СОД:
Одномашинные СОД построены на базе единственной ЭВМ с однопроцессорной структурой. Создание их, включая разработку ПО не вызывает трудностей, однако имеет ограничения по производительности (до нескольких миллионов операций в секунду) и допускает простой системы в течение нескольких часов, из-за отказа оборудования. Быстродействие определяется быстродействием ИС и приближается к физическому пределу и производительности ЭВМ на уровне 10 миллионов операций в секунду. Из-за ограничения абсолютной надежности базы Одномашинные СОД частично удовлетворяют потребности в автоматизации обработки данных.
Для увеличения производительности СОД несколько ЭВМ (CPU) связываются между собой образуя многомашинный вычислительный комплекс (ММВК). ММВК различают с косвенной и прямой связью между ЭВМ.
Структурная схема ММВК с косвенной связью
ЭВМ
ЭВМ
НМЛ
НМД
НМЛ
НМД
НМД
Здесь связь осуществляется через общее запоминающее устройство, т.е. за счет доступа с общим набором данных. Связь называется косвенной и оказывается эффективной только в том случае, когда ЭВМ взаимодействует достаточно редко (при отказе одной ЭВМ или при начале и окончании обработки данных).
Более оперативное взаимодействие ЭВМ осуществляется при прямой связи через адаптер, обеспечивающий обмен данными между каналами ввода/вывода двух ЭВМ и передачу сигналов прерыванию.
Структурная схема ММВК с прямой связью
ЭВМ
ЭВМ
КВВ
КВВ
адаптер
НМД
НМЛ
НМД
НМЛ
В схеме создаются хорошие условия для координации процессов обработки данных, и увеличивается оперативность процессов обмена данными, что позволяет увеличить производительность СОД. Здесь все процессы имеют доступ ко всему объему данных, хранимых в ОЗУ, и могут взаимодействовать со всеми периферийными устройствами комплекса ММВК.
ММВК, содержащий несколько процессоров с общим ОЗУ и периферийными устройствами называется многопроцессорным.
Процессор
Процессор
Процессор
Средства коммутации
МП
МП
МП
КВВ
КВВ
…
ПУ
…
ПУ
ПУ
ПУ
МП – модуль памяти
ПУ – периферийное устройство
В структурной схеме процессоры через средства коммутации подключены к модулю памяти. Каналы ввода/вывода обслуживают периферийные устройства. Средства коммутации обеспечивают доступ каждого CPU к любому модулю ОП, каналам ввода/вывода, обеспечивают возможность передачи данных между последними. Отказы отдельных устройств в меньшей мере влияют на работоспособность ВК, т.к. каждый CPU имеет доступ ко всем данным, хранимым в общей ОП и ПУ, поэтому ВК может параллельно обработать не только независимые данные, но и блоки одной задачи.
ММВК и многопроцессорный ВК являются базовыми средствами для создания СОД различного назначения, поэтому в них включают общесистемное ПО.
СОД настроенная на решение задач конкретной области называется вычислительной системой (ВС). ВС включает в себя технические средства и ПО, ориентированное на решение определенных задач. ВС бывает двух типов:
В первом случае, ВС универсальны и используют прикладные программы. Во втором – ВС более быстродействующие и используются для решения задач векторной и матричной алгебры, распознавания образов. Широкое распространение получили адаптивные системы и системы с динамической структурой. При этом соединения между CPU, МП и ПУ устанавливается динамически в соответствие с требованиями задач в текущий момент времени. Это обеспечивает высокую производительность ВС, устойчивость к отказам.
Системы предназначены для обработки данных, передаваемых по каналам связи называют системами телеобработки.
Пользователи взаимодействуют с системой посредством терминалов (абонентских пунктов), подключаемых через каналы связи к средствам обработки данных ЭВМ или ВК. Данные передаются по каналам связи в форме сообщений, блоков данных, несущих в себе, кроме собственно данных, служебную информацию, необходимую для управления процессами передачи и защиту данных от искажений. ПО содержит специальные средства необходимые для управления техническими средствами управления связи между ЭВМ и абонентами, передачи данных между ними и организации взаимодействия пользователей с программами обработки данных. Телеобработка значительно увеличивает оперативность информационного обслуживания пользователей и расширяет их доступ к данным и процедурам их обработки.
Вычислительная сеть объединяет территориально разрозненный СОД в единый комплекс с помощью каналов передачи данных с единым ПО и обеспечивает доступ к данным и процедурам их обработки всех пользователей, связанных общей сферой деятельности.
Узлы связи (УС) принимают данные и передают их в направлении обеспечить доставку данных абонентам. Ядром сети является базовая сеть передачи данных (СПД), которая включает УС и каналы связи. ЭВМ подключают к узлам базовой сети передачи данных, что обеспечивает обмен данными между любыми каналами ЭВМ.
Совокупность ЭВМ, объединенных СПД образует сеть ЭВМ.К ЭВМ непосредственно или с помощью каналов связи подключены терминалы, через которые пользователи взаимодействуют с сетью. Совокупность терминалов и средств связи для подключения их к ЭВМ образуют терминальную сеть. Таким образом, вычислительная сеть представляет собой композицию СПД, сеть ЭВМ и терминальную сеть.
Вычислительные сети используют для объединения ЭВМ в пределах региона, страны или континента. Оснащены все ЭВМ специальными программными средствами для сетевой обработки данных. На сетевое ПО возлагают широкий комплекс функций:
- управление аппаратурой сопряжения и каналов связи,
- установление соединений между взаимодействующими процессами и ЭВМ,
- управление процессами передачи данных,
- ввод и выполнение заданий от удаленных терминалов,
- доступ программ к набору данных, размещенных в удаленных ЭВМ.
ЛВС – это совокупность близко расположенных ЭВМ, которые связаны последовательными интерфейсами и оснащены программными средствами, обеспечивающими информационное взаимодействие между процессами в различных ЭВМ.
Как видно из схемы, ЭВМ связываются с помощью моноканала, единого для всех ЭВМ сети. В моноканале наиболее часто используется витая пара, коаксиальный кабель или волоконно-оптический кабель. Длина моноканала не превышает нескольких сотен метров. Пропускная способность порядка 105-107 бит/сек, что достаточно для информационной связи между десятками ЭВМ.
Сетевые адаптеры (СА) – контроллеры, реализующие операции ввода-вывода через моноканал. Моноканал упрощает процедуру установления соединений и обмена данными между ЭВМ. Поэтому сетевое ПО оказывается более простым, чем в вычислительных сетях, содержащих сеть передачи данных, и легко встраивается даже в микро-ЭВМ.
ЛВС является эффективным средством построения сложных СОД на основе мини- и микро-ЭВМ, систем автоматизации проектирования, управления производством, транспортом и т.д.
Классификация СОД
СОД классифицируются в зависимости от способа их построения. СОД, построенные на основе отдельных ЭВМ, вычислительных комплексов и систем, образуют класс сосредоточенных (централизованных) систем, в которых вся обработка реализуется ЭВМ, вычислительным комплексом или специальный системой. Системы телеобработки и вычислительные сети относятся к классу распределенных систем, в которых процессы обработки данных рассредоточены по многим компонентам. При этом системы телеобработки считаются распределенными условно т.к. основные функции обработки данных здесь реализуются централизованно в одной ЭВМ или в вычислительном комплексе.
Интерфейсы СОД
Существенное влияние на организацию СОД оказывают интерфейсы. Все интерфейсы, используемые СОД, делятся на три класса:
Параллельный интерфейс состоит из большого числа линий, данные по которым передаются параллельно, в параллельном коде, в виде 8-128 разрядных слов со скоростью 106-108 бит/сек. Длина линий от нескольких метров до десятков (реже сотен) метров.
Последовательный интерфейс – одна линия. Данные передаются в последовательном коде со скоростью 105 – 107 бит/сек. Длина – от десятков метров до километров.
Связанные интерфейсы содержат каналы связи с ретранслятором. Скорость передачи данных порядка 103-105 бит/сек. Расстояние не ограничено.
В сосредоточенных системах используются параллельные интерфейсы и только для подключения периферийных устройств – последовательные. В распределенных системах из-за значительных расстояний используются только последовательные и связанные интерфейсы, что исключает возможность передачи сигналов прерывания между устройствами и требует представлении данных в виде сообщений, передаваемых с помощью операций ввода-вывода.
Лекция 3.
ПАРАЛЛЕЛЬНАЯ ОБРАБОТКА ДАННЫХ
Лекция 4.
Параллельные алгоритмы обработки данных
Алгоритм сортировки Бэтчера не является наиболее эффективным алгоритмом сортировки, однако он обладает одним важным компенсирующим качеством: все сравнения и/или обмены, определяемые данной итерацией алгоритма можно выполнять одновременно. С такими параллельными операциями сортировка осуществляется за .
Например, 1024 элемента можно рассортировать методом Бэтчера всего за 55 параллельных шагов. Схема сортировки Бэтчера несколько напоминает сортировку Шелла, но сравнения выполняются по-новому, а потому цепочки операций обмена записей не возникает. Поскольку в алгоритме Бэтчера, по существу, происходит слияние пар рассортированных подпоследовательностей, его можно назвать обменной сортировкой со слиянием.
Алгоритм Бэтчера (обменная сортировка со слиянием). Записи перекомпоновываются в пределах того же пространства в памяти. После завершения сортировки их ключи будут упорядочены: . Предполагается, что .
1)[начальная установка .] Установить , где — наименьшее целое число, такое, что . (Шаги 2-5 будут выполняться с .)
2)[начальная установка .] Установить .
3)[цикл по .] Для всех , таких, что и , выполнять шаг 4.
Затем перейти к шагу 5. (Здесь через обозначена операция "поразрядное логическое И" над представлениями целых чисел и ; все биты результата равны 0, кроме тех битов, для которых в соответствующих разрядах и находятся 1. Так . К этому моменту — нечётное кратное (т.е. частное от деления на нечётно), а — степень двойки, так что . Отсюда следует, что шаг 4 можно выполнять при всех нужных значениях в любом порядке или даже одновременно.)
4)[Сравнение/обмен .] Если , поменять местами записи .
5)[Цикл по .] Если , установить и возвратиться к шагу 3.
6)[Цикл по ] (К этому моменту перестановка будет -упорядочена.) Установить . Если , возвратиться к шагу 2.
2. Вычисление корня алгебраического или трансцендентного уравнения
Пусть дано уравнение . Требуется на отрезке найти корень при условии . Для построения алгоритма ветви используется метод хорд, заключающийся в следующем (рисунок N1). Кривая заменяется хордой , определяется
Рисунок 1. Метод хорд.
точка , после чего проводится хорда определяется и т. д., пока .
Для реализации задачи на процессоров, т.е. для построения параллельного алгоритма из ветвей, отрезок разбивается на подотрезков на границах которых вычисляется . Это определяет подотрезок длиной , содержащий корень . Точки и — соседние, в них значения функции имеют разные знаки (рисунок N1).
После отрезка рассматривается отрезок , где
(1)
Отрезок разбивается на частей, повторяется описанная процедура, получается отрезок и т. д., пока длина отрезка не станет меньше заданного значения. Параллельный счет оправдан, когда объём вычислений значения намного превосходит объём вычислений границ отрезка по (1).
Аналогичный результат получается и при использовании метода Ньютона.
3. Решение системы линейных алгебраических уравнений методом простой итерации
Система уравнений размерности записывается в виде , где — матрицы; и — векторы; — единичная матрица.
Последовательные приближения вычисляются по формуле , начиная с некоторого исходного приближения . Процесс завершается, если . Последовательность в методе простой итерации сходится, если для матрицы выполняется одно из неравенств
Применим к матрице и векторам и распределение горизонтальными полосами. Для нахождения в соответствующей ветви необходимы строка матрицы , вектор и значение . Поэтому можно обеспечить каждую ветвь всеми необходимыми данными для автономной работы. Отсюда
где — число строк матрицы и компонентов векторов и , обрабатываемых отдельной ветвью, — время обмена данными, — время выполнения сложения, — время выполнения умножения.
Лекция 5.
Термин OLAP - расшифровывается как OnLine Analytical Processing. То есть примерно можно перевести как “Обработка данных в реальном времени”. Это не упоминание какой то конкретной технологии или архитектуры, а как бы формулировка задачи.
OLAP также можно определить как особый способ анализа данных и получения отчетов. Сам термин OLAP появился уже гораздо позже появления промышленных серверов, которые называются сейчас OLAP-серверами. Термин был введен в употребление в 1993 году Эдгаром Коддом, “отцом” реляционных СУБД (система управления базами данных). Он также сформулировал 12 правил OLAP3, которым должна удовлетворять OLAP система. Они на экране.
Информационные системы масштаба предприятия, как правило, содержат приложения, предназначенные для комплексного многомерного анализа данных, их динамики, тенденций и т.п. Такой анализ в конечном итоге призван содействовать принятию решений. Нередко эти системы так и называются — системы поддержки принятия решений.
Принять любое управленческое решение невозможно не обладая необходимой для этого информацией, обычно количественной. Для этого необходимо создание хранилищ данных (Data warehouses), то есть процесс сбора, отсеивания и предварительной обработки данных с целью предоставления результирующей информации пользователям для статистического анализа (а нередко и создания аналитических отчетов). Основные требования к хранилищам данных на экране.
Конечной целью использования OLAP является анализ данных и представление результатов этого анализа в виде, удобном для восприятия и принятия решений. Основная идея OLAP заключается в построении многомерных кубов, которые будут доступны для пользовательских запросов. Однако исходные данные для построения OLAP-кубов обычно хранятся в реляционных базах данных. Нередко это специализированные реляционные базы данных, называемые также хранилищами данных (Data Warehouse). В отличие от так называемых оперативных баз данных, с которыми работают приложения, модифицирующие данные, хранилища данных предназначены исключительно для обработки и анализа информации, поэтому проектируются они таким образом, чтобы время выполнения запросов к ним было минимальным. Обычно данные копируются в хранилище из оперативных баз данных согласно определенному расписанию.
Типичная структура хранилища приведена на слайде.
Таблица фактов является основной таблицей хранилища данных. Как правило, она содержит сведения об объектах или событиях, совокупность которых будет в дальнейшем анализироваться. Обычно говорят о четырех наиболее часто встречающихся типах фактов. Они показаны на экране. Таблица фактов, как правило, содержит уникальный составной ключ, объединяющий первичные ключи таблиц измерений. Чаще всего это целочисленные значения либо значения типа «дата/время» — ведь таблица фактов может содержать сотни тысяч или даже миллионы записей, и хранить в ней повторяющиеся текстовые описания, как правило, невыгодно — лучше поместить их в меньшие по объему таблицы измерений. При этом как ключевые, так и некоторые не ключевые поля должны соответствовать будущим измерениям OLAP-куба. Помимо этого таблица фактов содержит одно или несколько числовых полей, на основании которых в дальнейшем будут получены агрегатные данные.
Таблицы измерений содержат неизменяемые либо редко изменяемые данные. В подавляющем большинстве случаев эти данные представляют собой по одной записи для каждого члена нижнего уровня иерархии в измерении. Таблицы измерений также содержат как минимум одно описательное поле (обычно с именем члена измерения) и, как правило, целочисленное ключевое поле (обычно это суррогатный ключ) для однозначной идентификации члена измерения. Если будущее измерение, основанное на данной таблице измерений, содержит иерархию, то таблица измерений также может содержать поля, указывающие на «родителя» данного члена в этой иерархии. Нередко (но не всегда) таблица измерений может содержать и поля, указывающие на «прародителей», и иных «предков» в данной иерархии (это обычно характерно для сбалансированных иерархий), а также дополнительные атрибуты членов измерений, содержавшиеся в исходной оперативной базе данных (например, адреса и телефоны клиентов).
Каждая таблица измерений должна находиться в отношении «один ко многим» с таблицей фактов. Пример на экране.
OLAP предоставляет удобные быстродействующие средства доступа, просмотра и анализа деловой информации. Пользователь получает естественную, интуитивно понятную модель данных, организуя их в виде многомерных кубов (Cubes). Осями многомерной системы координат служат основные атрибуты анализируемого бизнес-процесса. Например, для продаж это могут быть товар, регион, тип покупателя. В качестве одного из измерений используется время. На пересечениях осей - измерений (Dimensions) - находятся данные, количественно характеризующие процесс - меры (Measures). Это могут быть объемы продаж в штуках или в денежном выражении, остатки на складе, издержки и т. п. Пользователь, анализирующий информацию, может “разрезать” куб по разным направлениям, получать сводные (например, по годам) или, наоборот, детальные (по неделям) сведения и осуществлять прочие манипуляции, которые ему придут в голову в процессе анализа.
Даже трехмерный куб сложно отобразить на экране компьютера так, чтобы были видны значения интересующих мер. Что уж говорить о кубах с количеством измерений, большим трех? Для визуализации данных, хранящихся в кубе, применяются, как правило, привычные двумерные, т. е. табличные, представления, имеющие сложные иерархические заголовки строк и столбцов.
Двумерное представление куба можно получить, “разрезав” его поперек одной или нескольких осей (измерений): мы фиксируем значения всех измерений, кроме двух, - и получаем обычную двумерную таблицу. В горизонтальной оси таблицы (заголовки столбцов) представлено одно измерение, в вертикальной (заголовки строк) - другое, а в ячейках таблицы - значения мер. При этом набор мер фактически рассматривается как одно из измерений - мы либо выбираем для показа одну меру (и тогда можем разместить в заголовках строк и столбцов два измерения), либо показываем несколько мер (и тогда одну из осей таблицы займут названия мер, а другую - значения единственного “неразрезанного” измерения).
Значения, “откладываемые” вдоль измерений, называются членами или метками (members). Метки используются как для “разрезания” куба, так и для ограничения (фильтрации) выбираемых данных - когда в измерении, остающемся “неразрезанным”, нас интересуют не все значения, а их подмножество, например три города из нескольких десятков. Значения меток отображаются в двумерном представлении куба как заголовки строк и столбцов
Метки могут объединяться в иерархии, состоящие из одного или нескольких уровней (levels). Например, метки измерения “Магазин” (Store) естественно объединяются в иерархию с уровнями:
All (Мир)
Country (Страна)
State (Штат)
City (Город)
Store (Магазин).
В соответствии с уровнями иерархии вычисляются агрегатные значения, например объем продаж для USA (уровень “Country”) или для штата California (уровень “State”). В одном измерении можно реализовать более одной иерархии - скажем, для времени: {Год, Квартал, Месяц, День} и {Год, Неделя, День}.
Отметим, что иерархии могут быть сбалансированными (balanced), плюс иерархии, основанные на данных типа "дата—время", и несбалансированными (unbalanced). Типичный пример несбалансированной иерархии — иерархия типа "начальник—подчиненный".
Существуют также иерархии, занимающие промежуточное положение между сбалансированными и несбалансированными (они обозначаются термином ragged — "неровный"). Обычно они содержат такие члены, логические "родители" которых находятся не на непосредственно вышестоящем уровне (например, в географической иерархии есть уровни Country, City и State, но при этом в наборе данных имеются страны, не имеющие штатов или регионов между уровнями Country и City.
Как данные хранятся, грубо говоря, не волнует ни конечного пользователя, ни разработчиков инструмента, которым клиент пользуется.
Многомерность в OLAP-приложениях может быть разделена на три уровня:
Первые два уровня в обязательном порядке присутствуют во всех OLAP-средствах. Третий уровень, хотя и является широко распространенным, не обязателен, так как данные для многомерного представления могут извлекаться и из обычных реляционных структур.
В отличие от большинства предлагаемых сегодня на рынке решений, приобретение которых заранее предполагает использование какой-то определенной архитектуры хранилища, Microsoft OLAP Services не ограничивает выбор администратора, предлагая гибкую модель хранения. Если для нас являются критичными вопросы быстродействия, мы можем выбрать MOLAP, если мы не хотим забирать дополнительное место на диске за счет переноса детальных данных - можно выбрать ROLAP, если мы хотим взять лучшее из двух - то HOLAP. Более того, в Microsoft OLAP Services разные чаcти одного куба могут храниться в разных форматах, что позволяет более четко и аккуратно подстроиться под требования пользователя. Например, куб, содержащий данные о продажах, может быть разбит на несколько фрагментов, один из которых с данными за текущий год, запрашивается довольно часто, а остальные - не очень.
Лекция 6
Основную часть имеющихся статистических пакетов составляют специализированные пакеты и пакеты общего назначения.
Специализированные пакеты обычно содержат методы из одного-двух разделов статистики или методы, используемые в конкретной предметной области (контроль качества промышленной продукции, расчет страховых сумм и т.д.). Чаще всего встречаются пакеты для анализа временных рядов (например, Эвриста, МЕЗОЗАВР, ОЛИМП:СтатЭксперт, Forecast Expert), регрессионного и факторного анализа, кластерного анализа, многомерного шкалирования. Обычно такие пакеты содержат весьма полный набор традиционных методов в своей области, а иногда включают также и оригинальные методы и алгоритмы, созданные разработчиками пакета. Как правило, пакет и его документация ориентированы на специалистов, хорошо знакомых с соответствующими методами. Применять такие пакеты целесообразно в тех случаях, когда требуется систематически решать задачи из той области, для которой предназначен специализированный пакет, а возможностей пакетов общего назначения недостаточно.
Особое место на рынке занимают так называемые статистические пакеты общего назначения. Отсутствие прямой ориентации на специфическую предметную область, широкий диапазон статистических методов, дружелюбный интерфейс пользователя привлекает в них не только начинающих пользователей, но и специалистов. Универсальность этих пакетов особенно полезна:
- на начальных этапах обработки, когда речь идет о подборе статистической модели или метода анализа данных;
- когда поведение статистических данных выходит за рамки использовавшейся ранее модели;
- в процессе обучения основам статистики.
Именно пакеты общего назначения составляют большинство продаваемых на рынке статистических программ. К таким пакетам относятся системы STADIA и STATGRAPHICS, рассмотренные в этой книге, а также пакеты SPSS, SYSTAT, S-plus и др.
Неполные пакеты общего назначения. Некоторое хождение на рынке статистических программ (особенно в нашей стране) имеют пакеты, которые можно было бы назвать неполными пакетами общего назначения. Чаще всего они содержат простейшие методы описательной статистики и некоторые методы из двух-трех других разделов статистики. Как правило, это либо недоработанные первые версии вновь создаваемых пакетов, либо вынесенные на рынок программы для внутреннего, узкоспециализированного использования. Последние, кроме ограниченности статистических методов, обычно характеризуются недоработанными интерфейсами, скудностью сервисных возможностей. Отличительной чертой таких пакетов является отсутствие или слабая методическая проработка документации.
По-видимому, использование неполных пакетов общего назначения вряд ли может быть целесообразным, так как при практической работе почти наверняка (и, скорее всего, очень быстро) потребуются те методы, которые разработчики не смогли включить в пакет. Образно выражаясь, неполный пакет общего назначения похож на автомобиль, рассчитанный, скажем, на работу при температуре только от 15 до 20 градусов – иногда его можно использовать, а очень часто нельзя.
Компьютерные системы для анализа данных - пакеты статистических программ - считаются наукоемкими программными продуктами, но, пожалуй, наиболее широко применяются в практической и исследовательской работе в самых разнообразных областях.
На сегодняшний день Международный рынок насчитывает около тысячи (или даже более) пакетов, решающих задачи статистического анализа данных в среде операционных систем Windows, DOS, OS/2.
В настоящее время, по перечисленным выше причинам, число статистических пакетов, получивших распространение в России, достаточно велико и спрос на них продолжает возрастать.
Из зарубежных пакетов это STATGRAPHICS, SPSS, SYSTAT, BMDP,SAS, CSS, STATISTICA, S-plus, и т.п.
Из отечественных можно назвать такие пакеты, как STADIA, ЭВРИСТА, МИЗОЗАВР, ОЛИМП:Стат-Эксперт, Статистик-Консультант, САНИ, КЛАСС-МАСТЕР и т.д.
Виды статистических пакетов
Как уже отмечалось, международный рынок насчитывает > 1000 пакетов, решающих задачи статистического анализа данных в среде операционных систем Windows, DOS, OS/2. Как ориентироваться в этом многообразии, если даже справочники, содержащие только краткие описания пакетов, представляют из себя объёмные тома?
Большую часть статистических пакетов можно разбить на две группы — это статистические пакеты общего назначения и специализированные программные продукты.
Универсальные пакеты – отсутствие прямой ориентации на специфическую предметную область, предлагают широкий диапазон статистических методов. В них отсутствует ориентация на конкретную предметную область. Они обладают дружественным интерфейсом. Из зарубежных универсальных пакетов наиболее распространены BAS, SPSS, Systat, Minilab, Statgraphics, STATISTICA.
Специализированные пакеты - как правило, реализуют несколько статистических методов или методы, применяемые в конкретной предметной области. Чаще всего это системы, ориентированные на анализ временных рядов, корреляционно-регресионный, факторный или кластерный анализ. Применять такие пакеты целесообразно в тех случаях, когда требуется систематически решать задачи из этой области, для которой предназначен специализированный пакет, а возможностей пакетов общего назначения недостаточно. Из российских пакетов более известны STADIA, Олимп, Класс-Мастер, КВАЗАР, Статистик-Консультант; американские пакеты – ODA, WinSTAT, Statit и т.д.
Статистический пакет в идеале должен удовлетворять определенным требованиям:
· модульность;
· ассистирование при выборе способа обработки данных;
· использование простого проблемно-ориентированного языка для формулировки задания пользователя;
· автоматическая организация процесса обработки данных и связей с модулями пакета;
· ведение банка данных пользователя и составление отчета о результатах проделанного анализа;
· диалоговый режим работы пользователя с пакетом;
· совместимость с другим программным обеспечением.
Следует заметить, что развитие СПП обычно идет поэтапно, на каждом из них создается вариант пакета, все в большей степени удовлетворяющий перечисленным выше требованиям. При этом если создание есть результат разработки, то на каждом этапе пакет, с одной стороны, должен представлять собой готовую к использованию программную продукцию, а с другой - входить составной частью в более поздние стадии развития пакета.
Анализа однотипных зарубежных пакетов
Как выбрать подходящий статистический программный продукт (СПП)? Какими критериями следует руководствоваться при сравнении различных СПП? Можно ли оценить степень соответствия цены СПП его потребительским свойствам? Ниже излагается методика сравнительного, позволяющая такой продукт правильно выбрать и в дальнейшем эффективно использовать.
Существующая классификация статистических пакетов предлагает делить их на четыре группы:
· интегрированные методо-ориентированные пакеты общего назначения;
· специализированные методо-ориентированные пакеты;
· предметно- (или проблемно-) ориентированные пакеты;
· обучающие программы.
Рассмотрим пакеты первых двух групп поскольку именно они "обслуживают" весьма широкий спектр прикладных задач.
Список пакетов, составивших выборку для анализа, представлен в табл. 1.
Таблица 1.
Общие сведения об СПП.
Возможности западных статистических пакетов
Ввиду того, что в настоящее время стали очень популярны статистические методы обработки данных, соответствующие средства стали включаться в табличные процессоры общего назначения (например, в Еxcеl, Lоtus 1-2-3 и т.д.), а также в некоторые базы данных.
Западные статистические пакеты (SРSS,SAS,BMDР и т.д.) имеют следующие возможности:
· Позволяют обрабатывать гигантские объемы данных.
· Включают средства описания задач на встроенном языке.
· Дают возможность построения на их основе систем обработки информации для целых предприятий.
· Позволяют проводить узкоспециальные методы анализа.
Выбор статистического пакета для анализа данных зависит от характера решаемых задач, объема и специфики обрабатываемых данных, квалификации пользователей, имеющегося оборудования и т.д.
Возможности пакета SAS.
Для пользователей, имеющих дело со сверхбольшими объемами данных или узкоспециальными методами анализа, пока нет альтернативы использованию профессиональных западных пакетов. Среди пакетов такого рода наибольшими возможностями обладает пакет SAS.
Таблица: возможности пакета SAS:
|
Средство |
Возможности |
|
Программирование на 4GL (программном языке SAS System) |
Вызов различных статистических процедур SAS осуществляется из программ, написанных на программном языке SAS. Т.к этот программный язык имеет необходимые средства для управления данными, мощные макросредства, поэтому с его помощью могут быть реализованы сложные информационные технологии.
|
|
Программирование с помощью ASSIST |
Предназначен для пользователя, не имеющего специальной подготовки в области статистики и не программирующего на входном языке. Предоставляет не полный, но достаточный набор возможностей анализа данных. |
|
Консультативная помощь при анализе данных |
В SAS System имеется возможность получать консультативную помощь в выборе методов анализа и в интерпретации его результатов, а также рекомендации по дальнейшей работе с исходными данными.
|
|
Быстрая разработка приложений - аналитические возможности |
В SAS System имеется средство быстрой разработки приложений на основе объектной технологии - т.н. SAS/EIS. Среди возможностей объектов, предлагаемых для этих приложений, имеются и аналитические возможности: описательная статистика, расчеты обобщающих показателей, прогноз временных рядов, анализ "что-если". Все получаемые аналитические результаты обязательно наглядно представляются графически. |
|
Интерактивный матричный язык |
SAS System располагает, в дополнение к другим языковым средствам, специальный интерактивный матричный язык, который дает возможность осуществлять различные математические расчеты, в том числе и аналитико-статистические расчеты. |
|
Приложение ANALYST |
Это приложение, ориентированное на пользователя без специальной статистической подготовки, позволяет быстро осуществить статистический анализ данных, табличное и графическое представление результатов |
|
Аналитические методы в средствах разведки данных |
В SAS System разработано средство разведки данных (SAS Data Mining Solution), дающее пользователю возможность осуществить весь цикл работы с исходными данными, имеющими большие объемы и невыясненную статистическую структуру. |
Объемы обрабатываемых данных в пакете SРSS ограничиваются только величиной памяти вашего компьютера. Этот пакет также весьма удобен для работы с данными сложной структуры, когда необходимо делать их всевозможные срезы, как, например, в комплексном социологическом исследовании.
Недостатки западных статистических пакетов
Следует отметить, что продвижение западных продуктов в российской аудитории наталкивается на ряд ограничений в связи с неадекватностью культурно-исторической ситуации.
Большинство из таких статистических пакетов имеют следующие недостатки:
· Требуют наличие профессиональных навыков и высокой квалификации, широкого первоначального статистического образования, доступной литературы и консультационных служб. Поэтому они содержат мало экранных подсказок и требуют внимательного изучения документации на английском языке.
· Представляют сложности для быстрого освоения и использования.
· Отсутствие подробной документации, доступной для начинающих и информативной для специалистов-статистиков (исключение SPSS).
· Требуют больших финансовых затрат, так как немаловажное значение имеет цена пакета. Профессиональные западные статистические пакеты (SРSS,SAS,BMDР и т.д.) обычно стоят от 1 до 10 тыс. долларов и более. Мало кто готов заплатить такие деньги…
Лекция 8.
Системы DATA MINING в задачах анализа и интерпретации данных.
Data Mining - мультидисциплинарная область, возникшая и развивающаяся на базе таких наук как прикладная статистика, распознавание образов, искусственный интеллект, теория баз данных и др., см. рис. 1.1.
Рис. 1.1. Data Mining как мультидисциплинарная область
Приведем краткое описание некоторых дисциплин, на стыке которых появилась технология Data Mining.
Понятие Статистики
Статистика - это наука о методах сбора данных, их обработки и анализа для выявления закономерностей, присущих изучаемому явлению.
Статистика является совокупностью методов планирования эксперимента, сбора данных, их представления и обобщения, а также анализа и получения выводов на основании этих данных.
Статистика оперирует данными, полученными в результате наблюдений либо экспериментов. Одна из последующих глав будет посвящена понятию данных.
Понятие Машинного обучения
Единого определения машинного обучения на сегодняшний день нет.
Машинное обучение можно охарактеризовать как процесс получения программой новых знаний. Митчелл в 1996 году дал такое определение: "Машинное обучение - это наука, которая изучает компьютерные алгоритмы, автоматически улучшающиеся во время работы".
Одним из наиболее популярных примеров алгоритма машинного обучения являются нейронные сети.
Понятие Искусственного интеллекта
Искусственный интеллект - научное направление, в рамках которого ставятся и решаются задачи аппаратного или программного моделирования видов человеческой деятельности, традиционно считающихся интеллектуальными.
Термин интеллект (intelligence) происходит от латинского intellectus, что означает ум, рассудок, разум, мыслительные способности человека.
Соответственно, искусственный интеллект (AI, Artificial Intelligence) толкуется как свойство автоматических систем брать на себя отдельные функции интеллекта человека. Искусственным интеллектом называют свойство интеллектуальных систем выполнять творческие функции, которые традиционно считаются прерогативой человека.
Data Mining - мультидисциплинарная область, возникшая и развивающаяся на базе таких наук как прикладная статистика, распознавание образов, искусственный интеллект, теория баз данных и др., см. рис. 1.1.
Основная особенность Data Mining - это сочетание широкого математического инструментария (от классического статистического анализа до новых кибернетических методов) и последних достижений в сфере информационных технологий. В технологии Data Mining гармонично объединились строго формализованные методы и методы неформального анализа, т.е. количественный и качественный анализ данных.
К методам и алгоритмам Data Mining относятся следующие: искусственные нейронные сети, деревья решений, символьные правила, методы ближайшего соседа и k-ближайшего соседа, метод опорных векторов, байесовские сети, линейная регрессия, корреляционно-регрессионный анализ; иерархические методы кластерного анализа, неиерархические методы кластерного анализа, в том числе алгоритмы k-средних и k-медианы; методы поиска ассоциативных правил, в том числе алгоритм Apriori; метод ограниченного перебора, эволюционное программирование и генетические алгоритмы, разнообразные методы визуализации данных и множество других методов.
Большинство аналитических методов, используемые в технологии Data Mining - это известные математические алгоритмы и методы. Новым в их применении является возможность их использования при решении тех или иных конкретных проблем, обусловленная появившимися возможностями технических и программных средств. Следует отметить, что большинство методов Data Mining были разработаны в рамках теории искусственного интеллекта.
Метод (method) представляет собой норму или правило, определенный путь, способ, прием решений задачи теоретического, практического, познавательного, управленческого характера.
Понятие алгоритма появилось задолго до создания электронных вычислительных машин. Сейчас алгоритмы являются основой для решения многих прикладных и теоретических задач в различных сферах человеческой деятельности, в большинстве - это задачи, решение которых предусмотрено с использованием компьютера.
Алгоритм (algorithm) - точное предписание относительно последовательности действий (шагов), преобразующих исходные данные в искомый результат.
Классификация стадий Data Mining
Data Mining может состоять из двух [8] или трех стадий [9]:
Стадия 1. Выявление закономерностей (свободный поиск).
Стадия 2. Использование выявленных закономерностей для предсказания неизвестных значений (прогностическое моделирование).
В дополнение к этим стадиям иногда вводят стадию валидации [10], следующую за стадией свободного поиска. Цель валидации - проверка достоверности найденных закономерностей. Однако, мы будем считать валидацию частью первой стадии, поскольку в реализации многих методов, в частности, нейронных сетей и деревьев решений, предусмотрено деление общего множества данных на обучающее и проверочное, и последнее позволяет проверять достоверность полученных результатов.
Стадия 3. Анализ исключений - стадия предназначена для выявления и объяснения аномалий, найденных в закономерностях.
Итак, процесс Data Mining может быть представлен рядом таких последовательных стадий [11]:
СВОБОДНЫЙ ПОИСК (в том числе ВАЛИДАЦИЯ) ->
-> ПРОГНОСТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ->
-> АНАЛИЗ ИСКЛЮЧЕНИЙ
1. Свободный поиск (Discovery)
На стадии свободного поиска осуществляется исследование набора данных с целью поиска скрытых закономерностей. Предварительные гипотезы относительно вида закономерностей здесь не определяются.
Закономерность (law) - существенная и постоянно повторяющаяся взаимосвязь, определяющая этапы и формы процесса становления, развития различных явлений или процессов.
Система Data Mining на этой стадии определяет шаблоны, для получения которых в системах OLAP, например, аналитику необходимо обдумывать и создавать множество запросов. Здесь же аналитик освобождается от такой работы - шаблоны ищет за него система. Особенно полезно применение данного подхода в сверхбольших базах данных, где уловить закономерность путем создания запросов достаточно сложно, для этого требуется перепробовать множество разнообразных вариантов.
Свободный поиск представлен такими действиями:
Допустим, имеется база данных кадрового агентства с данными о профессии, стаже, возрасте и желаемом уровне вознаграждения. В случае самостоятельного задания запросов аналитик может получить приблизительно такие результаты: средний желаемый уровень вознаграждения специалистов в возрасте от 25 до 35 лет равен 1200 условных единиц. В случае свободного поиска система сама ищет закономерности, необходимо лишь задать целевую переменную. В результате поиска закономерностей система сформирует набор логических правил "если ..., то ...".
Могут быть найдены, например, такие закономерности "Если возраст < 20 лет и желаемый уровень вознаграждения > 700 условных единиц, то в 75% случаев соискатель ищет работу программиста" или "Если возраст >35 лет и желаемый уровень вознаграждения > 1200 условных единиц, то в 90% случаев соискатель ищет руководящую работу". Целевой переменной в описанных правилах выступает профессия.
При задании другой целевой переменной, например, возраста, получаем такие правила: "Если соискатель ищет руководящую работу и его стаж > 15 лет, то возраст соискателя > 35 лет в 65 % случаев".
Описанные действия, в рамках стадии свободного поиска, выполняются при помощи :
На стадии свободного поиска также должна осуществляться валидация закономерностей, т.е. проверка их достоверности на части данных, которые не принимали участие в формировании закономерностей. Такой прием разделения данных на обучающее и проверочное множество часто используется в методах нейронных сетей и деревьев решений и будет описан в соответствующих лекциях.
2. Прогностическое моделирование (Predictive Modeling)
Вторая стадия Data Mining - прогностическое моделирование - использует результаты работы первой стадии. Здесь обнаруженные закономерности используются непосредственно для прогнозирования.
Прогностическое моделирование включает такие действия:
В процессе прогностического моделирования решаются задачи классификации и прогнозирования.
При решении задачи классификации результаты работы первой стадии (индукции правил) используются для отнесения нового объекта, с определенной уверенностью, к одному из известных, предопределенных классов на основании известных значений.
При решении задачи прогнозирования результаты первой стадии (определение тренда или колебаний) используются для предсказания неизвестных (пропущенных или же будущих) значений целевой переменной (переменных).
Продолжая рассмотренный пример первой стадии, можем сделать следующий вывод.
Зная, что соискатель ищет руководящую работу и его стаж > 15 лет, на 65 % можно быть уверенным в том, что возраст соискателя > 35 лет. Или же, если возраст соискателя > 35 лет и желаемый уровень вознаграждения > 1200 условных единиц, на 90% можно быть уверенным в том, что соискатель ищет руководящую работу.
Сравнение свободного поиска и прогностического моделирования с точки зрения логики
Свободный поиск раскрывает общие закономерности. Он по своей природе индуктивен. Закономерности, полученные на этой стадии, формируются от частного к общему. В результате мы получаем некоторое общее знание о некотором классе объектов на основании исследования отдельных представителей этого класса.
Правило: "Если возраст соискателя < 20 лет и желаемый уровень вознаграждения > 700 условных единиц, то в 75% случаев соискатель ищет работу программиста"
На основании частного, т.е. информации о некоторых свойствах класса "возраст < 20 лет" и "желаемый уровень вознаграждения > 700 условных единиц", мы делаем вывод об общем, а именно: соискатели - программисты.
Прогностическое моделирование, напротив, дедуктивно. Закономерности, полученные на этой стадии, формируются от общего к частному и единичному. Здесь мы получаем новое знание о некотором объекте или же группе объектов на основании:
Знаем, что соискатель ищет руководящую работу и его стаж > 15 лет, на 65% можно быть уверенным в том, что возраст соискателя > 35 лет.
На основании некоторых общих правил, а именно: цель соискателя - руководящая работа и его стаж > 15 лет, мы делаем вывод о единичном - возраст соискателя > 35 лет.
Следует отметить, что полученные закономерности, а точнее, их конструкции, могут быть прозрачными, т.е. допускающими толкование аналитика (рассмотренные выше правила), и непрозрачными, так называемыми "черными ящиками". Типичный пример последней конструкции - нейронная сеть.
3. Анализ исключений (forensic analysis)
На третьей стадии Data Mining анализируются исключения или аномалии, выявленные в найденных закономерностях.
Действие, выполняемое на этой стадии, - выявление отклонений (deviation detection). Для выявления отклонений необходимо определить норму, которая рассчитывается на стадии свободного поиска.
Вернемся к одному из примеров, рассмотренному выше.
Найдено правило "Если возраст > 35 лет и желаемый уровень вознаграждения > 1200 условных единиц, то в 90 % случаев соискатель ищет руководящую работу". Возникает вопрос - к чему отнести оставшиеся 10 % случаев?
Здесь возможно два варианта. Первый из них - существует некоторое логическое объяснение, которое также может быть оформлено в виде правила. Второй вариант для оставшихся 10% - это ошибки исходных данных. В этом случае стадия анализа исключений может быть использована в качестве очистки данных.
3