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


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
Санкт
-
Петербургский политехнический университет
Петра Великого

Институт компьютерных наук и технологий

Высшая школа программной инженерии


Работа допущена к защите

И. о
. директора ВШ ПИ

П.Д. Дробинцев

«_____»________
__

2017 г.


ВЫПУСКНАЯ РАБОТА БАКАЛАВРА


Тема:
Программная система восполнения недостающей информации об объекте

Направление
:
09.03.01



Информатика и вычислительная техника








Выполнил
студент г
р. 43504/21







С.А. Чижов



Руководитель
к т.н. доцент







И
.
В
.
Никифоров





Санкт
-
Петербург

2017 г
Санкт
-
Петербургский политехнический университет
Петра Великого

Институт компьютерных наук и технологий

Высшая школа программной инженерии



УТВЕРЖДАЮ



И. о. д
иректор
а

ВШ ПИ




П.Д Дробинцев




«_____»__________ 2017

г.

З А Д А Н И Е

к работе на соискание степени бакалавра


Студента

Чижова Сергея Александровича

1.

Тема проекта (работы)

Программная

система восполнения недостающей
информации


(утверждена распоряжением по ИКНТ от
________________________№_________ )

2. Срок сдачи студентом оконченного проекта (работы) 1 июня 2017г.

3. Исходные данные к проекту (работе)


Разработать приложение по в
осполнению недостающей информации.

4.

Содержание расчетно
-
пояснительной записки (перечень подлежащих разработке
вопросов)

1. Обзор существующих решений

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

3. Концепция системы восполнения

4. Реализация



5. Применение

6.
Выводы и
заключение

5. Перечень графического материала (с точным указанием обязательных
чертежей)____________________________________________________________________
_____________________________________________________________________________
_
____________________________________________________________________________
_____________________________________________________________________________
_____________________________________________________________________________
_______________________
6.

Консультанты по проекту (с указанием соответствующих разделов)
_____________________________________________________________________________
_____________________________________________________________________________
______________________________________
_______________________________________
_____________________________________________________________________________
_____________________________________________________________________________
_______________________

7. Дата выдачи задания_________________
_____________________________





Руководитель _________________ (______________________)


(подпись руководителя)


(Фамилия и инициалы)




Задание принял к исполнению “__”___________20 г.


_________________ ( _______________________ )


(подпись студента)




(Фамилия и инициалы)

Реферат

С. 45. Рис. 25. Табл.2

ВОСПОЛНЕНИЕ НЕДОСТАЮЩЕЙ ИНФОРМАЦИИ
,

МАШИННОЕ
ОБУЧЕНИЕ
,

ЗАПОЛНЕНИЕ ПРОПУСКОВ
,

БОЛЬШИЕ ДАННЫЕ

Работа посвящена

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

и

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

реализующей заполнение для любых типов данных
,

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

формата

CSV
,

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


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

а также
библиотека
Swing

для графического интерфейса пользователя.
Для создания
системы используется
IntelliJ IDEA Commu
nity Edition
.

Результатом
данной
работы
является
разработка

прототипа

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

как качественных
,

так и
количественных
,

с минимальной настройкой конфигурации от пользователя.
.

Созданный прототип

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


Содержание


Введение

................................
................................
................................
..........

8

1.

Обзор литературы

................................
................................
................

10

1.1 Существующие решения

................................
................................
..

10

1.1.1
IBM

SPSS

................................
................................
.......................

10

1.1.3
Statsoft

STATICTICA

................................
................................
...

12

1.1.4
SAS

Enterprise

Miner

................................
................................
...

12

1.2 Обзор применяющихся алгоритмов

................................
..............

13

1.2.1 Метод
k
-
ближайших соседей

................................
....................

13

1.2.2
Линейная

регрессия

................................
................................
......

14

1.2.3 Л
огистическая

регрессия

................................
............................

16

1.2.4

Деревья

решений.

Алгоритм

CART

................................
...........

17

1.3 Сравнение алгоритмов

................................
................................
.....

17

1.4 Выводы и постановка задачи

................................
.........................

19

2. Система восполнения информации

................................
....................

21

2.1 Концепция

................................
................................
...........................

21

2.2 Требования на проектируемую систему

................................
.......

22

2.2.1
MSC
-
диаграммы взаимодействия

................................
................

23

2.2.2. Сценарии поведения системы

................................
..................

31

2.3 Содержание системы

................................
................................
........

33

2.3.1. Модуль выгрузки данных

................................
............................

33

2.3.2. Модуль восполнения
................................
................................
....

33

2.3.3. Модуль валидации результата

................................
.................

34

2.4. Математическая модель

................................
................................
.

34

Выводы

................................
................................
................................
......

35

3. Реализация

................................
................................
...............................

36

3.1 Пользовательский интерфейс

................................
.........................

36

3.1.1. Авторизация

................................
................................
................

36

3.1.2. Выб
ор файла

................................
................................
.................

38

7


3.1.3 Выбор места сохранения

................................
............................

38

3.1.4 Чтение атрибутов

................................
................................
......

39

3.1.5
Вызов процесса восполнения

................................
......................

39

3.2 Работа с логами системы

................................
................................
.

41

3.2.1 Случаи использования логов

................................
.......................

41

3.2.2 Реализация логов системы

................................
.........................

42

3.3 Многопоточность

................................
................................
..............

42

Выводы

................................
................................
................................
......

44

4. Результаты

................................
................................
...............................

45

Заключение

................................
................................
................................
....

46

Список литературы

................................
................................
.......................

47




8


Введение

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

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


Рис.1.
Объём зафиксированных данных в мире
.

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

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

0,8
1,76
4,4
7,9
2009
2011
2013
2015
9


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

что вы решили немного
“приукрасить” свою анкету, т.е., например, написать несвойственные вам
качества. Таким образом мы будем иметь дело уже с искаженными данными.

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

диплом будет
посвящен

проблем
е

неполноты данных.



10


1.

Обзор литературы

1.1
С
уществующи
е решения

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

обеспечения, которые используются для

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

1.1.1
IBM

SPSS

IBM

SPSS
[1]

-

это универсальная система для анализа данных. С ее
помощью можно работать с данными представленными в следующих
форматах. Несколько собственных форматов, таких как
sav,

zsav,

sys,

por,

а

также

общеизвестных,

такие

как

dat,

csv,

xls.


Данная

система

явл
яется

модульной.

Всего

в

ней

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

около

двух

десятков

различных

модулей,

заточенных

под

разные

обла
сти

статистического

анализа.

И

к
аждый

из

модулей

покупается

отдельно.

Относительно

нашего

исследования

будет

интересовать

модуль


Missing
Values
».


Для

импутации

пропущенных

значений

по

умолчанию

здесь

используется

для

количественных

переменных

метод

п
од

названием

линейная

регрессия
[2]
.

Для категориальных переменных всегда используется
логистическая регрессия
[3].


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

11


1.1.2
SAP

Predictive

Analytics

SAP Predictive Analysis
[4]



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

Однако
, функционал

замещения отсутствующих значений довольно скромен
.
И в

настоящее время предоставляется три метода. Отсутствующие значения
для определенного атрибута заменяются одним из следующих значений
(атрибута / столбца):



Мода
[5]
:

значение во множестве наблюдений,
которое встречается наиболее
часто.

• Среднее арифметическое
[6]
:

среднее арифметическое не нулевых значений
в данном столбце. Среднее значение рассчитывается следующим образом:

ݔ
=
1



ݔ


, где N
-

число не нулевых значений.

• Медиана
[7]
:

числовое значение, разделяющее верхнюю половину значений
из нижней половины. Среднее значение рассчитывается по:

Если N
-

нечетное число:

݉݁݀�ܽ݊
=
ܽ
[

2
]
;

иначе
݉݁݀�ܽ݊
=
1
2
(
ܽ
[

2

1
]
+
ܽ
[

2
]





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


Данное решение также поддерживает интеграцию с языком
R
.



12


1.1.3
Statsoft

STATICTICA

STATISTICA
[8]



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

Данное программное обеспечение также как и
IBM

SPSS

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

тот
функционал, который ему необходим.

Интересующий нас функционал находится в модуле “
Data

Miner
”.
Для
импутации пропущенных значений по умолчанию используется метод

k
-
-
б
лижайших соседей
[9]

для кате
гориальных данных. З
начение
k

равно 3, но его
можно изменить, и выбрать от 1 до 500. Для непрерывных используется метод
расчета Медианы.

Также доступны более простые методы, такие как:

-

Мода (для категориальных данных)

-

Среднее арифметическое (для непрерывных данных)


Присутствует интеграция с языком
R
.

1.1.4
SAS

Enterprise

Miner

Программный

продукт

SAS

Enterprise

Miner
[10]


(разработчик

SAS

Instit
u
te Inc.)
-

это интегрированный

компонент

системы

SAS
, созданный
специально для выявления в огромных массивах данных

информации, которая
необходима для

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

Для импутации пропущенных значений п
о умолчанию используется
метод
ра
счета Медианы для непрерывных значений.
Эта статистика м
енее
чувствительна к экстремальным значениям, чем Среднее арифметическое,
и
поэтому полезна для вменения отсутствующих значений из искаженных
13


распределений. Также возможно построение моделей на основе дерева
решений
[11]
.


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

Также возможно использовать метод Мода.


Доступна интеграция с языком
R
.

1.2 Обзор применяющихся алгоритмов

1.2.1 Метод
k
-
ближайших соседей

Данный метод применяется для

решения задачи

классификации
,

который относит объект

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

пространстве признаков
.
При этом
параметр
k

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

k



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

k
=
4
, то каждый исс
ледуемый объект
сравнивается с 4
-
я

соседями.

Ниже проиллюстрирован пример при
k
=4.

В данном случае объект
X

будет отнесён к классу

, так

как к нему относится большинство ближайших
соседей.

14



Рис

2
. Классификация

при значении
k
=4.

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

можно
считать

высокую вычислительну
ю

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

1.2.2
Линейная

регрессия

Этот метод регрессионного анализа

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

линейной регрессии
,
которая строиться на основе
известных значениях набора

данных.

Итак, линейная

регрессия
-

это метод

аппроксимации

линейной
зависимости между входными и

выходными переменными
. Если ищется связь
м
ежду одной входной и одной выходной переменными, то имеет место
простая линейная регрессия. Для этого определяется уравнение регрессии
ݕ
=
15


ܽݔ
+
ܾ


и строится соответствующая прямая, известная как

линия
регрессии
[12]
. Коэффициенты

ܽ

и

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

Если ищется зависимость между несколькими входными и одной
выходной переменными, то имеет место множественная линейная регрессия.
Соответствую
щее уравнение имеет вид:

ݕ
=
ܾ
0
+
ܾ
1
ݔ
1
+
ܾ
2
ݔ
2
+

+
ܾ

ݔ


где

݊



число

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

гиперплоскостью
. Коэффициенты
ܾ
0

ܾ


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

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

Достоинства линейной регрессии:



Простота построения модели.



Скорость работы.



Модель является прозрачной, т.е. аналитик может оценить какой параметр
несет наибольшее значимость

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

16


Однако следует помнить, что данный метод работает только с
количественными величинами. Для работы с категориальными данными
применяется метод ло
гистической регрессии, который рассмотрен ниже.

1.2.3 Л
огистическая

регрессия

Логистическая регрессия является

разновидность
ю

множественной
регрессии,
которая применяется для анализа связей
между несколькими
предикторами
(
независимыми переменными
) и зависимой переменной.
Если
исследуемый критерий имеет только
два варианта,

например
,

да/
нет, то имеет
место б
инарная логистическая регрессия.

Во

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

ݕ
=
ܾ
0
+
ܾ
1
ݔ
1
+
ܾ
2
ݔ
2
+

+
ܾ

ݔ


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

Например, если
рассматривается
исход попытки поступления в ВУЗ, задается переменная
x

со
значениями 1 и 0, где 1 означает, что
человек поступ
ил в ВУЗ
, а 0



не
поступил.

Таким образом, с помощью логистической регрессии можно оценивать
вероятность того, что событие наступит для конкретного испытуемого
(поступит в ВУЗ или нет, долг будет погашен или нет и т.д.). Если же признак
не является бинарн
ым, то вместо предсказания бинарной переменной, мы
предсказываем непрерывную переменную со значениями на отрезке [0,1] при
любых значениях независимых переменных.



17


1.2.4

Деревья

решений.

Алгоритм

CART

CART, сокращение от Classification And Regression Tree
, переводится
как "Дерево Классификации и регрессии"


алгоритм бинарного дерева
решений, впервые опубликованный Бриманом и др. в 1984 году. Алгоритм
предназначен для решения задач классификации и регрессии.

В алгоритме CART каждый узел дерева решений имеет двух потомков.
На каждом шаге построения дерева правило, формируемое в узле, делит
заданное множество примеров (обучающую выборку) на две части


часть, в
которой выполняется правило (потомок


right) и час
ть, в которой правило не
выполняется (потомок


left). Для выбора оптимального правила используется
функция оценки качества разбиения.

А
чтобы справиться с пропущенными
значениями, алгоритм использует альтернативные или “суррогатные”
разбиения.


В итоге, плюсом данного алгоритма безусловно можно считать его
вычислительную сложность, а именно
O
(
log

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

1.3
Сравнен
ие алгоритмов

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

Итак,
метод
k
-
ближайших соседей

предназначен только для
классификации объектов,

и регрессию он не поддерживает. Кончено
теоретически этот метод можно распространить, и на использование с
18


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

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

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

Линейная регрессия

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

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

ближайших соседей.

Логистическая ре
грессия

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

Алгоритм
CART

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



19


Таблица 1. Сравнение алгоритмов


Классификация

Регрессия

Скорость

Качество

Простота
реализации

Метод
k

ближайших
соседей

+


-


-


-


+

Линейная

регрессия


-


+


+


+
/
-


+

Логистическая

регрессия


+


-


+


+
/
-


+
/
-

CART


+


+


+


+


-


1.4
Выводы и п
остановка задачи

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

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

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

денег.
Например,

стоимость подобных
решений иногда достигает 10

000 долларов, что недопустимо для частного
использования.

20



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

А также обеспечивать
достаточно высокий уровень восполнения пропущенных атрибутов.



21


2. Система восполнения информации

2.
1

Концепция

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

представленную на
рисунке
2
. Таким образом, изначально имеется массив неполных данных
которые трудно подвергать дальнейшему анализу и делать достато
чно точные
выводы об объектах. Задача разрабатываемой системы состоит в том, чтобы
на основании исходных данных, найти закономерности, построить модель
зависимости, и на её основе заполнить все возможные пропуски в данных.
Благодаря чему мы получим полный
набор данных, который более пригоден
для дальнейшего анализа, нежели исходные данные с пропусками.

Рис.

3
. Роль системы в анализе данных в целом.


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

3.


Рис .4
.
Концепция системы

22


2.2

Требования на проектируемую систему


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

необходимо сначала
сформулировать основные требования
.
Именно эти требования описаны
ниже в таблице 2.

Таблица 2. Требования на проектируемую систему.

Номер
требования

Описание

1.

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

1.1

Кнопка авторизации недоступна
,

пока не введены логин и
пароль

1.2

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

и нажата кнопка
авторизации
,

то выдать об этом сообщение.

2

При успешной авторизации окно должно свернуться
,

и
открыться основная форма работы с программой.

2.
1

В основном окне
,

при нажатии на кнопку выбора исходного
файла долж
ен

запуститься проводник
Windows

2.2

После выбор
исходного файла
,

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

2.3

При нажатии на кнопку выбора места сохранения

нового

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

2.4

После выбор места сохранения нового файла
,

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

23


2.5

После выбор исходного файла
,

должны быть считаны его
атрибуты и выведены на форму.

2.6

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

2
.7

При нажатии на кнопку запуска программы с выбранными
корректными данными
,

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

2.8

При нажатии на кнопку запуска программы с выбранными
корректными данными
,

после завершения работы алгоритма
восполнения выводится общая справочная информация.

2.9

При нажатии на кнопку прерывания расчетов
,

то все
вычисления завершаются
,

и выводится об этом сообщение.


Для того чтобы наглядно

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

и чтобы наглядно видеть
,

как будет происходить
взаимодействие пользователя с программой решено сделать
msc
-
диаграммы
[
15
],

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

2.2
.1
MSC
-
диаграммы взаимодействия


Данный подраздел посвящен проработке логики взаимодействия
пользователей с программой при помощи
MSC
-
диаграмм
,

для наглядного
,

и
более интуитивного понимания.

Итак
,

рассмотрим возможные взаимодействия
:

24



Рис.
5
.
При запуске
системы должно открываться окно авторизации


Рис.
6
.
Кнопка авторизации недоступна
,

пока не введены логин и пароль
.

25



Рис.
7
.
Если введен некорректный логин или пароль и нажата кнопка
авторизации
,

то выдать об этом сообщение.


Рис.
8
.
При успешной авторизации окно должно свернуться
,

и открыться
основная форма работы с программой.


26



Рис.
9
.
В основном окне
,

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


Рис.
10
.
После выбор исходного файла
,

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


27



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


Рис.
12
.
После выбор места сохранения нового файла
,

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


28



Рис. 1
3
.
После выбор исходного файла
,

должны быть считаны его атрибуты и
выведены на форму.


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


29



Рис. 1
5
.
При нажатии на кнопку запуска программы с выбранными
корректными данными
,

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


Рис.
16
.
При нажатии на кнопку запуска программы с выбранными
корректными данными
,

после завершения работы алгоритма восполнения
выводится общая справочная информация.

30



Рис.
17
.

При нажатии на кнопку прерывания расчетов
,

то все вычисления
завершаются
,

и выводится об этом сообщение.


С помощью
MSC
-
диаграмм были проработаны возможные
взаимодействия пользователя и программы. Что несомненно поможет при
разработке системы.



31


2.
2
.2. Сценарии поведения системы

Также
,

как в предыдущем подразделе
,

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

для наглядного
,

и более интуитивного
понимания.

Итак
,

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

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

т
ак и нет.


Рис.
18
. Не успешный сценарий взаимодействия

32


При успешном сценарии взаимодействие происходит успешно
,

и
пользователь получает файл с восполненными пропущенными значениями.


Рис.
1
9
.
Успешный сценарий взаимодействия

33


2.3 Содержание системы

2.
3
.1. М
од
уль выгрузки

данных


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

использует
закрытый
API
[1
4
], и бесплатно можно скачать лишь очень ограниченный круг
данн
ых, а точнее фото профиля пользователя, и его имя. В результате чего, для
проверки работоспособности разрабатываемой системы было принято
решение использовать подготовленные наборы данных в формате
CSV
.


Формат
CSV

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

2.
3
.2. Модуль восполнения

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

алгоритм
CART
[1
3
], т.к. он умеет работать как с непрерывными, так и с
категориальными атрибутами. Также алгоритм показывает неплохие
результаты восполнения.

Кроме того, алгоритм обладает хорошей
вычислительной сложностью
O
(
log

n
).


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

Условие
разбиения строится на основе уменьшения степени так называемой
“нечистоты” в узле. Таким образо
м, задается наиболее оптимальное условие
при котором в каждом узле содержится наибольшее количество объектов
принадлежащих одному классу.

В данном алгоритме важным элементом
является индекс
Gini
[
16
],
согласно которому и определяется условия
34


разбиения.
Разбиение останавливается на основе статистического
подхода
,

а именно применяется
ݔ�
2

критерий
[
17
]
.

Далее следует
укоротить дерево
,

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

чем просто недостроить
,

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


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

но и второе и
так далее. А

когда встречаем объект у которого неизвестен атрибут
,

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

2.
3
.3. Модуль валидации результата


Суть данного модуля заключается в
оценке уровня достоверности
восстановленных данных.

Такую оценку можно получить прибегнув
к
следующему

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

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

2.
4
. Математическая модель

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



В хранилище(наборе данных) содержится
N

объектов. У каждого
объекта есть одинаковые атрибуты. обозначим их следующим образом :
a
,
b
,
c
,
d
,
e
,
f
,
g
. Каждый атрибут может б
ыть представлен непрерывным значением,
35


например числом, либо категориальным.

У
M
-
объектов из
N

множества
неизвестны значения некоторых атрибутов. Однако у остальных объектов
содержащихся в
N
, известны все атрибуты, назовём это множество
F
. Таким
образом, объединение множеств
M

и
F

образует полное множество
N
.


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

буквой
O
.
Предположим у него отсутствует значение атрибута В, а в
се остальные
атрибуты известны. Н
еобходимо найти объекты в множестве
F

максимально
похожие на
объект
O
, на основе известных атрибутов. Далее вычислить
наиболее правдоподобное значение, согласно используемому алгоритму, и
присвоить это значение атрибуту
b

д
ля объекта
O
. Повторить данное действие
для остальных объектов множества
M
.

Выводы

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

которые описывают взаимодействие пользователя с программой.

С помощью
msc
-
диаграмм также созданы предполагаемые сценарии
взаимодействия пользователя с системой
,

как успешный
,

в результате
которого пользователь получает восполненные данные
,

так и неуспешный
,

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

Обозначены основные концепции разрабатываемой программы
,

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

восполнения
,

и

валидации результата. И в конце была
описана концепция системы с помощью математической модели.


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

и в
следующей главе будет описана её реализация.



36


3.
Реализация

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

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

3.1 Пользовательский интерфейс

Прототип п
ользовательс
кого

интерфейс
а

состоит из окна авторизации
пользователя
,

и главного окна
,

в котором происходит вся работа с
приложением.


3.1.1. Авторизация

При запуске приложения открывается окно авторизации.


Рис
. 20
.
Окно

авторизации

37


Оно

реализуется

следующим

кодом
:




super
(
"Authorization"
);


System.
arraycopy
length
);


new
GridBagLayout());


okButton
=
new
JButton(
"ok"
);


loginLabel
=
new
JLabel(
"login"
);


passwordLabel
=
new
JLabel(
"password"
);


loginField
=
new
JTextField(10);


passwordField
=
new
JPasswordField(10);

В случае провала валидации логина/пароля будет выведено
предупреждающее сообщение:


Рис
.
21
.
Сообщение об ошибке

Проверка корректности пароля реализуется следующей функцией
:


private boolean
checkValid(String log, String pass)
throws
NoSuchAlgorithmException {


boolean
flag =
false
;


String passwordHash =
(pass);


String dbPasswordHash;


try
{


ConnectionDB connect =
new
ConnectionDB(
[0],
[1],
[2]);


[3]);


connect.initProperties();


connect.init();


ResultSet rs =
"select hash_sum from dbusers where name= '"
+ log);


while
(rs.next()) {




if
(dbPasswordHash.trim().equals(passwordHash.trim())){


flag =
true
; } }


rs.close(); }
catch
(SQLException sqlEx) {


sqlEx.printStackTrace(); }


return
flag; }

38


Если валидация прошла успешно
,

то откроется

главная форма окно
программы.


Рис
.
22
.
Главное окно

3.1.2.
Выбор файла


Выбор файла происходит по нажатию кнопки

Выбрать файл
”.
Запускается процедура, которая вызывает стандартные средства
Windows
,

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

чтобы
наглядно

видеть его.

3.1.3

Выбор
места сохранения


Чтобы вызвать метод реализующий данный функционал
,

необходимо
нажать кнопку

Место сохранения

. При этом выбор пути очень схож с
предыдущим пунктом
,

т.е. происходит вызов проводника
Windows
,
далее
39


выбираем путь
,

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

3.1.
4

Чтение атрибутов


При нажатии на кнопку

Выбрать файл

помимо отображения пути
файла на форме
,

ещё одновременно происходит считывание атрибутов
объекта. Чтобы отобразить их на форме
,

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


Считанные атрибуты отображаются на форме
,

как показано на рисунке
22
.
Далее пользователь отмечает необходимые для восполнения атрибуты
галочками. Если необходимо восполнить все данные
,

то ну
жно выбрать поле

все

.


Рис. 23
. Отображение атрибутов на форме.

3.1.5
Вызов процесса восполнения


Внизу формы расположена текстовое поле
,

где выводятся информация о
работе системы
,

а также инструкции для пользователя
,

чтобы легче
ориентироваться. Такое поле изображено на рисунке
23.

40



Рис. 2
4
.
Текстовое поле для информации
.

Итак
,

чтобы начать процесс восполнения необходимо нажать кнопку
run
.

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

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

что и файл признакового описания
,

но при этом в
названии добавляется

new

. Поэтому не страшно
,

если пользователь не задаст
место сохранения самостоятельно. Также
,

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

то автоматически будут восстановлены все
атрибуты.

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

stop

.

После успешного восполнения данных
,

система выдаст об этом
сообщение. Кроме того
,

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

которое было описано немного ранее.

Таким образом
,

схематично упрощенный алгоритм изображен ниже

41



Рис. 25. Упрощенный алгоритм программы

3.2

Работа с логами системы

3
.2.1 Случаи использования логов


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

например
,

разработчик написал программу
,

запускает её
,

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

и в итоге с помощью такого
журнал
обнаружить причину нети
пичного поведения программы. Кроме того
,

логи также используются в процессе эксплуатации

программного
обеспечения
,

так как в действительности не все ошибки получается отловить
42


на этапе тестирования. И когда возникает сбой в программе
,

пользователь
может от
править отчет о сбое разработчикам
,

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

3.2.2

Реализация логов

системы


В сис
теме восполнения информации лог
ирование
реализуется

с
помощью java.util.logging
framework
[
19
]
.
Данный фреймворк выбран
,

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

и он
изначально поставляется с
JRE
[
20
]
, то есть в дополнительных скачиваниях нет
необходимости.

Ниже приведен пример с использование реализации
логов
:


public


try
{


Statement stmt = mysqlConnection.createStatement();


return
stmt.executeQuery(query);


}
catch
(SQLException e) {

log
.
log
(Level.SEVERE,
"Except "
, e);



e.printStackTrace();


}
return null
;


}


public void
sqlQuery(String query) {
try
{


Statement stmr = mysqlConnection.createStatement();


stmr.executeUpdate(query);


}
catch
(SQLException

e) {


e.printStackTrace(); } }}


3.3 Многопоточность


В настоящее время развитие архитектуры процессоров идёт в сторону
увеличения количества ядер и потоков.
Поэтому
,

чтобы программа быстро
выполнялась на компьютере их необходимо задействовать. Это особенно
43


актуальн
о,

когда речь идет об обработке больших объемов данных. Итак
,

многопоточность это свойство некоторого процесса(программы)
,

который
состоит из нескольких потоков. Таким образом
,

происходит параллельное
выполнение программы
,

где каждый
поток выполняет свой набор инструкций.
В результате чего можно более эффективно использовать вычислительную
мощность современный компьютеров.
Бо
лее подробно об этом можно
почитать в научной статье
[21].


Изначально в
Java

запускается главный поток в методе
main
.
Далее в
определенных местах программы
,

которые задал программист
,

если это
необходимо
,

создаются

побочные потоки. Ниже приведен пример
,

как можно
запустить побочный поток
:

class

A


implements

Runnable


{


public

void

run
()



{

System
.
out
.
println
(
"
Побочный поток
"
);

}


}

public

class

prog


{

static

A

mA
;

static

void

main
(String[] args)


{

mA
=
new

A
();

Thread
new
Thready =
new

Thread(
mA
);

new
Thready.start();

System.out.println(
"
Основной

поток

завершился
"
);

}


}


В классе А реализуется интерфейс
Runnable
.
В
Runnable

находится
метод
run
()
.

Далее создаем объект класса
,

и в
main
()
запускаем новый поток
для объекта.



44


Выводы


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

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

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

а именно
,

реализовано
окно авторизации
,

и рассмотрен пример его использования.
Реализована

главная
форма системы
,

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

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

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

как логирование и многопоточность.



45


4.
Результаты

Результатами работы является
реализация

прототип
а

графического
интерфейса пользователя

системы восстановления
,

в числе которого такой
функционал
,

как

чтение
CSV
-
файлов признакового описания
,

выбор места
сохранения нового файла
,

возможность выбора пользователем

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

а такж
е авторизация пользователей.
Однако
,

анализ алгоритмов существующих систем
,

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

чем
предполагалось изначально
. Вследствие чего
,

на настоящий момент не
до
конца
реализован

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

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

Для тестирован
ия системы
,

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

открытый набор данных

c

сайта
UCI
[22].

Далее
будут проведены

тестовые запуски
,

и
оценка точности

восстановления

данных
,

полученной системы восстановления пропущенных значений
.


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

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

можно сослаться на
сторонние результаты тестирования алгоритма
CART

и некоторы
х других
[23]
.

В результате тестирования автор получил точность около 70%
,

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

что алгоритм имеет преимущества такие
как
,

быстрое обуче
ние модели
,

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

то можно считать выбор алгоритма вполне
успешным
.


46


Заключение

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

б
ыл
осуществлен обзор существующих решений, и выполнен сравнительный
анализ используемых алгоритмов. На основе этого, выбран наиболее
оптимальный

и универсальный

алгоритм

из рассмотренных

в качестве основы
реализуемой системы восполнения недостающей информа
ции.

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

использует закрытый
API
[
14], и бесплатно
можно скачать лишь очень ограниченный круг данных, а точнее фото профиля
пользователя, и его имя. В результате чего, для проверки работоспособности
разрабатываемой системы было принято решение использовать
подготовленные наборы данных в фо
рмате
CSV
.

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

диаграмм. Разработан прототип графического интерфейса пользователя
,

где реализована авторизация
,

чтение
CSV
-
файла признакового описания
,

и
работа с атрибутами пользователем
,

выбор места сохранения нового файла. А
также предложены и описаны сценарии тестирования системы в виде
msc
-
диаграмм.

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



47


Список литературы

1.

IBM

SPSS

Официальный сайт разработчика
https
://
www
.
ibm
.
com
/
analytics
/
ru
/
ru
/
technology
/
spss
/

2.

Линейная регрессия

Сайт

BaseGroup

Labs
https://basegroup.ru/community/articles/missing

3.

Логистическая регрессия

Сайт

BaseGroup Labs https://basegroup.ru/community/articles/logistic

4.

SAP Predictive Analysis

Официальный сайт раз
работчика

https://www.sap.com/products/predictive
-
analytics.html

5.

Мода

Сайт http://www.grandars.ru/student/statistika/strukturnye
-
srednie
-
velichiny.html

6.

Среднее арифметическое

Сайт
-
dannyx/62
-
srednee
-

7.

Медиана

Сайт
http://www.grandars.ru/student/statistika/strukturnye
-
srednie
-
velichiny.html

8.

Statsoft Statictica


Официальный сайт разработчика

http://statsoft.ru/

9.

Метод
k
-
ближайших соседей

Сайт
https
://
basegroup
.
ru
/
community
/
glossary
/
nearest
-
neighbor

10.

SAS Enterprise Miner


Официальный сайт разработчика

htt
ps://www.sas.com/en_us/software/enterprise
-
miner.html

11.

Деревья решений

Сайт
https://basegroup.ru/community/articles/description

12.

Линия регрессии


Сайт https://basegroup.ru/community/glossary/regression
-
line


48



13.

Алгоритм
CART


Сайт
https
://
basegroup
.
ru
/
com
munity
/
glossary
/
cart

14.


API

Сайт
https://habrahabr.ru/sandbox/52599/

15.

Msc
-
диаграммы

Сайт
https
://
en
.
wikipedia
.
org
/
wiki
/
Message
_
sequence
_
chart

16.

И
ндекс
Gini


Сайт https://basegroup.ru/community/glossary/gini
-
index

17.

ݔ�
2

критерий


https://basegroup.ru/community/glossary/chi
-
square
-
test

18.


Библиотека Swing


Сайт
http://darkraha.com/rus/java/swing/swing00.php

19.


java.util.logging framework


Сайт https://docs.oracle.com/javase/7/docs/api/java/util/logging/package
-
summary.html

20.


JRE

Сайт
https://ru.wikipedia.org/wiki/Java_Runtime_Environment

21.


Научная статья о многопоточности в приложениях. Гладышев Е.И.,
Мурыгин А.В.

Сайт
https://cyberleninka.ru/article/v/mnogopotochnost
-
v
-
prilozheniyah

22.


Библиотека открытых наборов данных для машинного обучения.

Сайт
https://archive.ics.uci.edu/ml/datasets.html

23.


Срав
ни
тельный анализ
алгоритмов машинного обучения

Сайт http://datareview.info/article/8
-
-
sravneniya
-
algoritmov
-
mashinnogo
-
obucheniya
-
na
-
r/



Приложенные файлы

  • pdf 34473530
    Размер файла: 1 MB Загрузок: 1

Добавить комментарий