V005344 Дипломная работа Разработка программного обеспечения для анализа данных

АННОТАЦИЯ 3

ABSTRACT 4

ВВЕДЕНИЕ 5

ГЛАВА 1. ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ ПРИМЕНЕНИЯ ПО ДЛЯ АНАЛИЗА ДАННЫХ 6

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

1.2Исторические предпосылки для использования ПО анализа данных 7

1.3Виды ПО для анализа данных 7

1.4Задачи, решаемые Data Maining и их использование 10

ГЛАВА 2. ИССЛЕДОВАНИЕ АЛГОРИТМОВ ДЛЯ АНАЛИЗА ДАННЫХ 13

2.1Постановка задачи для проектируемого ПО 13

2.2Анализ структуры Classification Tree 14

2.2.2.Комбинаторная энтропия 14

2.2.3.Энтропия Шенона 16

2.2.4.Примеры из термодинамики 18

2.2.5.Демон Максвелла 19

2.2.6.Решение парадокса Демона Максвелла 19

2.3Анализ структуры Naive Bayes 23

2.3.1.Теорема Бейеса 24

2.3.2.Предположение условной независимости 25

2.3.3.Проблема арифметического переполнения 26

2.3.4.Оценка Бейесовской модели 26

2.3.5.Проблема неизвестных слов 27

2.4Анализ структуры SVM 29

2.4.1.Постановка задачи 30

2.4.2.Классификация данных методом опорных векторов 30

2.4.5.Метод опорных векторов 31

2.4.6.Математическая формулировка 33

2.4.7.Линейная неразделимость 35

2.5Анализ структур кластеризации 36

2.5.1.Иерархическая кластеризация 37

2.5.2.Дендограмма кластеризации 38

ГЛАВА 3. ПРАКТИЧЕСКАЯ ЧАСТЬ РАЗРАБОТКИ АВТОМАТИЗИРОВАННОЙ СИСТЕМЫ 41

3.1Постановка задачи 41

3.2Требования к разрабатываемой системе 41

3.3Обоснование выбора программной среды и инструментов разработки 42

3.4Описание входной и выходной информации 43

3.5Архитектура и модульность программного средства 43

3.5.1.Модуль импорта данных из файла 43

3.5.2.Визуализации данных 43

3.5.3.Реализация алгоритма Classification Tree 43

3.5.4.Реализация алгоритма Naive Bayes 47

3.5.5.Реализация алгоритма SVM 51

3.5.6.Реализация алгоритма Cluster analysis 53

3.5.7.Модуль экспорта данных в PDF 55

3.10.Разработка интерфейса программы 57

3.11.Ресурсы, отображаемые на экране 58

ГЛАВА 4. ТЕСТИРОВАНИЕ ПРИЛОЖЕНИЯ 60

4.1.Работа с программным обеспечением 60

4.2.Описание тестовых заданий 61

ГЛАВА 5. ЭКОНОМИЧЕСКАЯ ЧАСТЬ 64

5.1 Анализ конкуренции разработанного ПО 64

5.2 Производственный план 64

ЗАКЛЮЧЕНИЕ 71

СПИСОК ЛИТЕРАТУРЫ 72

ПРИЛОЖЕНИЕ 1 74

ПРИЛОЖЕНИЕ 2 79

ПРИЛОЖЕНИЕ 3 85

ПРИЛОЖЕНИЕ 4 92

АННОТАЦИЯ

Тема дипломного проекта – «Разработка программного обеспечения для анализа данных».

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

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

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

• Classification Tree – дерево принятия решений;

• Naive Bayes – Байесовская наивная модель;

• SVM – метод опорных векторов;

• Cluster analysis – кластерный анализ.

Дипломный проект содержит пояснительную записку объемом 96 страниц, включая 28 иллюстраций, 2 таблиц, список литературы из 13 наименований, 4 приложений, и 0 листов графической части.

ABSTRACT

The theme of the degree project - "Development of software for data analysis."

The diploma project is considered designing software for analyzing data that are downloaded from the source data file format XLS, and the report notes in the file of PDF.

The first chapter of the diploma project the basic points for the theoretical analysis of the aspects that relate to program data analysis. Considered historical moments, the spectrum market for such programs both in Russia and abroad.

In the second chapter of this thesis provides a general analysis of all that will be used in future design software. This chapter deals with aspects relating to the areas of analysis that will be used in the form of algorithms:

• Classification Tree - a decision tree;

• Naive Bayes - naive Bayesian model;

• SVM - support vector;

• Cluster analysis - cluster analysis.

Graduation project contains an explanatory note volume 96 pages, including illustrations 28, 2 tables, bibliography of items 13 applications 4 and 0sheets and graphical part.

ВВЕДЕНИЕ

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

Данная программа призвана визуализировать данные из файла на экране компьютера в графическом виде, на основании того или иного алгоритма, которые встроены в программу. В программе используются 4 вида алгоритма:

• Classification Tree – дерево принятия решений;

• Naive Bayes – бейесовская наивная модель;

• SVM – метод опорных векторов;

• Cluster analysis – кластерный анализ.

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

При проектировании данного программного обеспечения использовались такой язык программирования  как Python. Использовались также следующие библиотеки matplotlib, numpy, PyQt, PySide, scikit_learn, scipy, xlrd.

ГЛАВА 1. ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ ПРИМЕНЕНИЯ ПО ДЛЯ АНАЛИЗА ДАННЫХ

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

Data Mining (рус. добыча данных, интеллектуальный анализ данных, глубинный анализ данных) — общее именование, которое используется для совокупности способов обнаружения в данных ранее неизвестных, нетривиальных, практически полезных и доступных интерпретации знаний, необходимых для принятия решений в различных сферах человеческой деятельности. Термин введён Григорием Пятецким-Шапиро в 1989 году[1].

Словосочетание «Data Mining» пока не имеет прямого точного перевода на русский язык. При переводе на русский язык используются следующие словосочетания: добыча данных, извлечение данных, просев информации, а также интеллектуальный анализ данных. Более полным и точным является словосочетание «обнаружение знаний в базах данных» (англ. knowledge discovery in databases, KDD).

Основу методов Data Mining составляют всевозможные методы классификации, моделирования и прогнозирования, основанные на применении деревьев решений, искусственных нейронных сетей, генетических алгоритмов, эволюционного программирования, ассоциативной памяти, нечёткой логики. К методам Data Mining нередко относят статистические методы (дескриптивный анализ, корреляционный и регрессионный анализ, факторный анализ, дисперсионный анализ, компонентный анализ, дискриминантный анализ, анализ временных рядов, анализ выживаемости, анализ связей). Такие методы, однако, предполагают некоторые априорные представления об анализируемых данных, что несколько расходится с целями Data Mining (обнаружение ранее неизвестных нетривиальных и практически полезных знаний)[1].

1.2 Исторические предпосылки для использования ПО анализа данных

Область Data Mining началась с семинара (англ. workshop), проведённого Григорием Пятецким-Шапиро в 1989 году.

Ранее, работая в компании GTE Labs, Григорий Пятецкий-Шапиро заинтересовался вопросом: можно ли автоматически находить определённые правила, чтобы ускорить некоторые запросы к крупным базам данных. Тогда же было предложено два термина — Data Mining («добыча данных») и Knowledge Discovery In Data (который следует переводить как «открытие знаний в базах данных»).

В 1993 году вышла первая рассылка «Knowledge Discovery Nuggets», а в 1994 году был создан один из первых сайтов по Data Mining[1].

1.3 Виды ПО для анализа данных

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

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

Существующая классификация статистических пакетов и предлагает делить их на четыре группы:

• интегрированные методо-ориентированные пакеты общего назначения;

• специализированные методо-ориентированные пакеты;

• предметно- (или проблемно-) ориентированные пакеты;

• обучающие программы.

Таблица 1.1 – Общие сведения об СПП.

Статистическая система Цена ОС Разработчки

 

1 3 4

SAS н/д W

SAS 850 D SAS Institute

Statgraphics+ 1048 W Manugistics

Statgraphics 995 D Manugistics

Statgraphics 995 D Manugistics

Minitab 695 W Minitab

Minitab [ 4] D Minitab

Systat 995 W SPSS

Systat 995 D SPSS

SPSS 980 W SPSS

BMDP 695 D SPSS

Statistica 995 W StatSoft

Statistica 795 D StatSoft

IMSL-C (Num) 700 W Visual Numerics

Object Suite 700 W н/д

S-Plus 1450 W StatSci

S-Plus 1195 D StatSci

Класс-Мастер 320 W Изд-во "ТВП"

Класс-Мастер 300 D Изд-во "ТВП"

Мезозавр 520 W Изд-во "ТВП"

САНИ 300 D Изд-во "ТВП"

Stadia 500 W Информатика& Компьютеры

Stadia 250 D Информатика&Компьютеры

Stat-Media 250 D Полихимэкс

Starc н/д D ТОО Data-Center

Квазар н/д D ИММ УрО РАН

Palmoda 300 D ВЦ РАН

Лорег 350 W н/д

PolyAnalyst 1850 OS/2 ЗАО Megaputer

Олимп 500 W ЗАО CPS

Олимп 350 D ЗАО CPS

Статистик-Консультант н/д W ТОО "Тандем"

Ростан н/д D БГУ

Cтатэкс н/д D РМ и ПК Казахстан

Unistat 795 W Unistat

SOLO 695 W [4]

Multivariance 7 200 D [4]

ODA 499 D [4]

MVSP 100 D [4]

CART 795 W [4]

BMDP New System 795 W SPSS

BM-STAT 220 D International Software

Data Desk 450 н/д Computing Capability

SAM-86 350 н/д Open Training

Statmost 395 W DataMost Europe

Powerstat 395 н/д Multi-Health System

NCSS (вместе с Adv. Stat) 224 D [4]

NCSS (вместе с Adv. Stat и Graphs) 323 D [4]

SigmaStat 495 W Jandel Scientific

SigmaStat (вместе с SigmaPlot) 795 W Jandel Scientific

StatXact 495 W н/д

JMP 695 W SAS Institute

Statistix 495 D [4]

Statit 359 W [4]

STATlab 895 W SciTech International

WinSTAT 195 W [4]

TURBO Spring 469 W [4]

Stat Navigator 149 D [4]

Starex 90 н/д Far Communicat

Примечания. Цены приведены на момент публикации источников. Стоимость лицензионной копии СПП взята из каталогов [4]. Операционные системы: W - Windows, D – DOS.

1.4 Задачи, решаемые Data Maining и их использование

Задачи, решаемые методами Data Mining, принято разделять на описательные (англ. descriptive) и предсказательные (англ. predictive)[1].

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

К описательным задачам относятся:

• построение регрессионной модели.

• группировка объектов, кластерный анализ;

• поиск ассоциативных правил или паттернов (образцов);

К предсказательным задачам относятся:

• классификация объектов (для заранее заданных классов);

• регрессионный анализ, анализ временны́х рядов.

Ряд этапов решения задач методами Data Mining[1]:

1) Постановка задачи анализа;

2) Сбор данных;

3) Подготовка данных (фильтрация, дополнение, кодирование);

4) Выбор модели (алгоритма анализа данных);

5) Подбор параметров модели и алгоритма обучения;

6) Обучение модели (автоматический поиск остальных параметров модели);

7) Анализ качества обучения, если неудовлетворительный переход на п. 5 или п. 4;

8) Анализ выявленных закономерностей, если неудовлетворительный переход на п. 1, 4 или 5.

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

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

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

ГЛАВА 2. ИССЛЕДОВАНИЕ АЛГОРИТМОВ ДЛЯ АНАЛИЗА ДАННЫХ

2.1 Постановка задачи для проектируемого ПО

Сперва задача ставится таким образом:

• имеется достаточно крупная база данных;

• делается предположение, что в базе данных находятся некие «скрытые знания».

Нужно разрабатывать методы обнаружения знаний, которые скрыты в больших объёмах исходных «сырых» данных. В текущих условиях глобальной конкуренции именно найденные закономерности (знания) могут быть источником дополнительного конкурентного преимущества.

Что из себя представляют «скрытые знания»? Под ними подразумевают  обязательно знания:

• ранее неизвестные — то есть такие знания, которые должны быть новыми (а не подтверждающими какие-то ранее полученные сведения);

• нетривиальные — то есть такие, которые нельзя просто так увидеть (при непосредственном визуальном анализе данных или при вычислении простых статистических характеристик);

• практически полезные — то есть такие знания, которые представляют ценность для исследователя или потребителя;

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

Эти требования, которые, во многом, определяют суть методов Data mining и то, в каком виде и в каком соотношении в технологии Data mining используются системы управления базами данных, статистические методы анализа и методы искусственного интеллекта.

2.2 Анализ структуры Classification Tree

2.2.1. Энтропия и деревья принятия решений

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

Для полноты картины, рассмотрим природу энтропии и некоторые её свойства.

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

2.2.2. Комбинаторная энтропия

Для примера можно рассмотреть разноцветных шариков: 2 красных, 5 зеленых и 3 желтых. Перемешаем их и расположим в ряд. Назовём эту операцию перестановкой:

 

Рисунок 2.1 – Множество разноцветных шариков

Давайте посчитаем количество различных перестановок, учитывая, что шарики одного цвета — неразличимы. Если бы каждый шарик имел уникальный цвет, то количество перестановок было бы 10!, но если два шарика одинакового цвета поменять местами — новой перестановки не получится. Следовательно, нужно исключить 5! перестановок зеленых шариков между собой (а также, 3! желтых и 2! красных). Поэтому, в данном случае, решением будет[3]:

 

Мультиномиальний коэффициент позволяет рассчитать количество перестановок в общем случае данной задачи:

 

(Ni — количество одинаковых шариков каждого цвета). Все перестановки можно пронумеровать числами от 0 до (W — 1). Следовательно, строка из log2(W) бит однозначно кодирует каждую из перестановок. Так как перестановка состоит из N шариков, то среднее количество бит, которые приходятся на один элемент перестановки можно выразить следующим образом:

 

Эта величина именуется комбинаторной энтропией:

 

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

2.2.3. Энтропия Шенона

Теперь можно рассмотреть по подробнее описанное выше выражение для энтропии:

 

Учтя свойства логарифмов, эту формулу можно преобразовать следующим образом:

 

Предположим, что количество шариков достаточно велико для того чтобы воспользоваться формулой Стирлинга:

 

Применив формулу Стирлинга, получаем:

 

(где k — коэффициент перехода к натуральным логарифмам).

Учитывая, что

 

выражение можно преобразовать:

 

Так как общее число шариков равно N, а количество шариков i-го цвета — Ni, то вероятность того, что случайно выбранный шарик будет именно этого цвета является[3]:

 .

 Исходя из этого, формула для энтропии примет вид:

 

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

Сравнение 2-х энтропий представлено на следующем рисунке (2.2), который рассчитан для множеств, содержащих два типа объектов — А и В (суммарное количество элементов в каждом множестве — 100):

 

Рисунок 2.2. – Сравнительная иллюстрация энтропий

2.2.4. Примеры из термодинамики

Аналогичные выражения для энтропии можно получить в термодинамике:

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

• исходя из макроскопических свойств веществ: путем анализа работы тепловых машин.

Понятие энтропии играет фундаментальную роль в термодинамике, фигурируя в формулировке Второго начала термодинамики:

«если изолированная макроскопическая система находится в неравновесном состоянии, то наиболее вероятным является её самочинный переход в состояние с большим значением энтропии»:

2.2.5. Демон Максвелла

Для получения статистической природы Второго начала термодинамики в 1867 году Джеймс Максвелл предложил мысленный эксперимент: «Представим сосуд, заполненный газом определённой температуры, сосуд разделен перегородкой с заслонкой, которую демон открывает чтобы пропускать быстрые частицы в одну сторону, а медленные — в другую. Следовательно, спустя некоторое время, в одной части сосуда сконцентрируются быстрые частицы, а в другой — медленные. Таким образом, вопреки Второму началу термодинамики, демон Максвелла может уменьшать энтропию замкнутой системы»: