Рубан А.И. Методы анализа данных. Практикум

Подождите немного. Документ загружается.

Методы анализа данных

Учебное пособие по циклу расчетно-графических работ

по курсу «Методы анализа данных»

Красноярск 2007 г.

Учебное пособие содержит описание ряда расчетно-графических ра-

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

анализа данных в виде программных стендов и тем самым получить реаль-

ный практический опыт в анализе данных и закрепить полученные на лекци-

ях теоретические сведения. Теоретический материал сопровождается при-

мерами.

Предназначено для студентов укрупненной группы подготовки направ-

ления 230100 — «Информатика и вычислительная техника» и преподавате-

лей дисциплины «Методы анализа данных».

ВВЕДЕНИЕ

Все методы анализа данных, рассматриваемые в теоретической части

курса не могут быть использованы «сами по себе». Для их применения на

практике их требуется реализовать в виде программы для ЭВМ.

Следует отметить, что на текущий момент уже существует множество

математических пакетов общего назначения, таких как MathCAD, MatLab и

может возникнуть закономерный вопрос «Зачем еще раз реализовывать тот

или иной метод для обработки и анализа данных?». Ответ очень прост – что-

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

математические пакеты (в своем подавляющем большинстве) реализованы по

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

получает на выходе, без малейшего представления о том, что же происходит

внутри.

Выполнив расчетно-графические работы, представленные в пособии,

студент получит реальный опыт работы со средними и большими массивами

данных, научится визуализировать обрабатываемую информацию и очень

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

невозможно корректно запрограммировать, не разобравшись в их устройстве.

В данной работе представлены наиболее часто встречающиеся на прак-

тике современные методы анализа данных ориентированные на использова-

ние современных ЭВМ, позволяющих быстро обрабатывать большие объемы

данных.

Основная идея, заложенная в данной работе – как можно доступнее по-

дать учебный материал, но в то же время оставить студенту большую степень

свободы в плане конкретной реализации рассматриваемых методов. С целью

более легкого усваивания информации в указаниях приведено множество

блок схем и пояснений практического характера, иллюстрирующих работу

рассматриваемых методов анализа данных.

1. ОБЩИЕ ТРЕБОВАНИЯ

Перечислим общие требования, предъявляемые к выполняемым рабо-

там.

1.1. Требования по оформлению

Отчет о выполненной работе должен содержать следующие части:

• Титульный лист. Оформляется в соответствии с текущими требо-

ваниями, принятыми в ВУЗе.

• Оформление текста согласно текущим требованиям принятым в

ВУЗе для оформления отчетов расчетно-графических работ.

• Постановка задачи. Содержимое этого раздела должно быть кон-

кретизировано под выполняемый вариант работы.

• Краткие теоретические сведения. Теоретические сведения долж-

ны быть конкретизированы под выполняемый вариант работы.

• Описание программной реализации метода. В этом разделе при-

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

ритмов и методов анализа данных.

• Тестирование реализованного метода. В этом разделе приводятся

результаты работы реализованного в виде программы метода

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

таблиц, графиков или снимков экрана.

• Выводы. В этом разделе должны быть представлены выводы об

обнаруженных свойствах и закономерностях реализованного ме-

тода анализа данных.

• Список литературы. Приводится список литературы, оформлен-

ный в соответствии с текущими требованиями, принятыми в ВУ-

Зе.

Примечание. Исходные тексты программы не надо включать в отчет.

Они должны быть предоставлены в электронном виде вместе с исполняемым

файлом программы реализующей выданный вариант работы.

1.2. Требования к реализации

• Используемый язык программирования. Любой на выбор студен-

та. Желательно использовать современные языки и платформы

программирования: C++, Delphi, Java, C# и т.д.

• Интерфейс пользователя. Желательно реализовывать дружест-

венный визуальный интерфейс пользователя в виде диалоговых

окон. Это ускоряет и упрощает процедуру тестирования про-

граммы при ее приемке преподавателем. Консольный вариант

интерфейса программы так же допустим, хотя и не желателен,

так как на сегодняшний день современные инструментальные

средства разработки (такие как Borland Delphi, Visual Studio, Ec-

lipse и т.д.) позволяют разрабатывать удобные визуальные диало-

говые окна «в несколько щелчков мышкой».

• При сдаче программы преподавателю во время контрольного за-

пуска программы она не должна выдавать сообщений об ошиб-

ках типа «Деление на ноль», «Переполнение» и т.п. Такие про-

граммы будут отправляться на доработку.

• Для сдачи программа должна быть предоставлена в виде испол-

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

нужными внешними библиотеками, так как на компьютере пре-

подавателя может не быть той инструментальной среды, которую

выбрал студент для реализации работы.

• Исходные тексты программы должны быть отформатированы и

содержать достаточное для понимания логики программы коли-

чество комментариев. Исходный текст программы обычно ис-

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

• Исполняемый модуль и носитель (дискета, флэшка, CD диск и

т.п.) на котором он предоставляется для проверки преподавате-

лю, должны быть предварительно проверены на вирусы. Это тре-

бование появилось в связи с частыми случаями заражения сда-

ваемых работ вирусами.

1.3 Пример интерфейса пользователя

На рисунке 1.1 приведен примерный интерфейс пользователя. Реко-

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

интерфейс, так как в таком случае удобно и наглядно представлена вся вход-

ная и вся выходная информация.

Рисунок 1.1. Примерный вид интерфейса пользователя.

Программа должна выполнять элементарные проверки на корректность

вводимых данных, например, ввод строковых данных вместо числовых и т.п.

1.4 Выдача и прием заданий

Темы расчетно-графических работ даются в рамках изложенного мате-

риала. Студент должен реализовать методы анализа данных, изложенные в

рамках лекций в виде программы на любом языке программирования (по вы-

бору студента).

Выдача заданий производится преподавателем во время проведения

практических занятий.

Так как в течение семестра невозможно выполнить все представленные

в пособии расчетно-графические работы рекомендуется в качестве основных

работ использовать следующие работы:

• Исследование байесовского правила классификации в распозна-

вании образов при непрерывных информативных признаках (ус-

ловные плотности известны с точностью до параметров).

• Исследование алгоритмов построения степенных моделей с ис-

пользованием ортогональных планов первого и второго поряд-

ков.

• Исследование непараметрической оценки прямой регрессии

• Исследование простейшего алгоритма адаптивной идентифика-

ции параметров статических (линейных и нелинейных относи-

тельно параметров) моделей объектов.

Состав и полнота реализации работ может варьироваться по желанию

преподавателя исходя из текущей ситуации в учебном процесс и уровня под-

готовки студентов.

Требования к выполнению расчетно-графических работ:

1. Строгое соответствие программы и результатов ее работы с полу-

ченным заданием.

2. Самостоятельные тестирование и отладка программы.

3. Устойчивость работы программы при любых значениях параметров,

задаваемых пользователем через интерфейс программы.

4. Предоставление демонстрационного примера и исходного текста

программы для защиты расчетно-графических работ.

5. Предоставление отчета, содержащего описание реализованного ме-

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

программы с различными входными параметрами.

Условия сдачи расчетно-графических работ:

Знание теории по сдаваемому методу анализа данных. Умение объяс-

нить полученные результаты. Способность быстро продемонстрировать вла-

дение предметной областью.

2. ОБЩАЯ СХЕМА ПОСТРОЕНИЯ РАБОТЫ

Каждая работа состоит из двух частей. Первая часть это моделирование

объекта. Вторая часть – реализация заданного метода.

Моделирование объекта приходится проводить по той причине, что нет

возможности предоставить студентам для исследования реальные объекты.

Модель объекта обычно задается как некоторая случайная величина или как

аналитическая функция, к которой добавлена помеха, имеющая нормальное

распределение с нулевым математическим ожиданием и некоторой диспер-

сией помехи (уровень помехи обычно вводится во время работы программы).

Отметим, что все современные языки программирования содержат реа-

лизацию генератора случайных чисел по равномерному закону, но для целей

моделирования этого мало – требуется генерировать и другие законы. Рас-

смотрим, как это можно сделать.

2.1. Общий метод генерации непрерывных распределений

В общем случае распределение действительных чисел может быть вы-

ражено в терминах функции распределения

F(x)

, которая точно определяет

вероятность того, что случайная величина

не превысит значение

)

(

)

(

≤

Эта функция всегда монотонно возрастает от 0 до 1, т.е.

.1)(,0)(;),()(

2121

+∞

−∞

≤

FFxxåñëèxFxF

Если

F(x)

непрерывна и строго возрастающая (так что

2121

),()( xxêîãäàxFxF

), то она принимает все значения между 0 и 1 и

существует обратная функция

)(

−

, такая, что для

)(,)(

yFxêîãäàòîãäàòîëüêîèòîãäàxFy

−

В большинстве случаев, когда

F(x)

непрерывна и строго возрастаю-

щая, можно вычислить случайную величину

с распределением

F(x)

, по-

лагая

),(

UFX

−

где

– равномерно распределенная случайная величина. Действительно, ве-

роятность того что

≤

равна вероятности того, что

xUF ≤

−

)(

, а именно –

вероятности того, что

)

(

≤

, т.е.

F(x)

Теперь проблема сводится к решению задачи численного анализа – к

нахождению хороших методов вычисления

)(

−

с требуемой точностью.

Этот метод хорошо применять, когда существует однозначное преобра-

зование. Для нормального закона (который является одним из самых распро-

страненных) это не так.

Рассмотрим два основных способа генерации чисел имеющих нор-

мальное распределение.

2.2. Генерация чисел, по нормальному закону с использованием

центральной предельной теоремы

Центральная предельная теорема утверждает, что случайная величина

равная:

XXXY +++=

Имеет нормальное распределение с некоторым математическим ожи-

данием и дисперсией.

Как уже было сказано выше, в нашем распоряжении есть генератор

равномерно распределенных случайных чисел, мы можем воспользоваться

им для генерации случайных величин

Тогда для получения случайной величины

с нужными нам парамет-

рами можно воспользоваться следующей формулой:

mRND

Y +−σ=

∑

)5.0)1;0((

где

– количество слагаемых, при этом чем больше

, тем лучше качество

работы генератора, но тем больше время его работы. Оптимально брать

12 ≤

≤100.

m – желаемые параметры для случайной величины

2.3. Генерация чисел по нормальному закону методом полярных

координат

Этот алгоритм вычисляет две независимые нормально распределенные

случайные величины

Y и

Y .

Шаг 1. Генерируем две независимые случайные величины

U и

U ,

равномерно распределенных между 0 и 1. Присвоить

−

равномерно распределены между -1 и +1.

Шаг 2. Присвоить

VVS +=

Шаг 3. Если

≥

, возврат на Шаг 1.

Шаг 4. Присвоить

следующие значения:

ln2

−

ln2

−

Получим независимые нормально распределенные величины с нуле-

вым математическим ожиданием и единичной дисперсией.

Теперь что бы получить величины

Y и

Y с желаемыми параметрами

необходимо выполнить простейшее преобразование:

111

mXY

222

mXY

Для доказательства законности данного метода используем элементар-

ную аналитическую геометрию и вычисления: если на Шаге 3

, то точка

плоскости с декартовыми координатами (

) является случайной точкой,

равномерно распределенной внутри единичного круга. Перейдя к полярным

координатам

cos

RV ,

sin

RV , получим

, θ−= cosln2

SX , θ−= sinln2

SX .

Используя так же полярные координаты 'cos'

RX и 'sin'

RX ,

получим

SR ln2' −=

. Ясно, что

независимы, поскольку

независимы в единичном круге. К тому же

равномерно распределено

между 0 и

, и что

−

≥ . Эта вероятность равна

−

− , так как

равномерно распределено между 0 и 1. Вероятность того, что

лежит меж-

ду

, поэтому равна дифференциалу от

−

, т.е.

r 2/

−

. Анало-

гично вероятность того, что

≤

, равняется

























=θ

∫∫∫

∞−

−

∞−

−

≤θ≤θθ

−

dyedxerdrde

xrxrr

2/2/

}sin,cos|),{(

Это доказывает, что

независимы и нормально распределены.