Материал: Анализ данных дистанционного практикума по программирования с помощью методов Data Mining

Анализ данных дистанционного практикума по программирования с помощью методов Data Mining

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

. АНАЛИТИЧЕСКАЯ ОБЗОР

.1      Data Mining - способ «обнаружения знаний в базах данных»

.2      Кластеризация как одна из задач Data Mining

.3      Возможности анализа данных дистанционного практикума на основе задачи кластеризации

. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ДЛЯ ПРОВЕДЕНИЯ КЛАСТЕРИЗАЦИИ

.1      Выбор и описание алгоритмов кластеризации

.2      Выбор программного пакета для проведения эксперимента

.3      Выбор объектов для кластеризации данных дистанционного практикума и определение их признаков

. ХОД И РЕЗУЛЬТАТЫ ЭКСПЕРИМЕНТА

.1      Получение данных из хранилища базы данных дистанционного практикума

.2      Загрузка данных в программный пакет WEKA

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

.4      Кластеризация задач

.5      Кластеризация пар «студент - задача»

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ПРИЛОЖЕНИЕ 1. Реализация функций в модуле подготовки данных

ВВЕДЕНИЕ

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

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

В системах аналитической обработки данных различных предметных областей хорошо себя зарекомендовали методы Data Mining. В данной работе представлен опыт по применению методов Data Mining к данным дистанционного практикума по программированию, технологиям баз данных и смежным дисциплинам, разработанного в Вологодском государственном университете (), который активно используется при обучении специалистов в области ИКТ на протяжении десяти лет. Информационной основой практикума является база данных. За многие годы ее эксплуатации были накоплены большие объемы данных. На данный момент в базе данных хранится свыше 168 000 строк, содержащих информацию обо всех успешных и неуспешных попытках решения задач студентами. Основными сущностями для дальнейшего анализа данных нашей БД являются задачи и студенты, решающие эти задачи.Mining - это процесс обнаружения в сырых данных ранее неизвестных, нетривиальных, практически полезных и доступных интерпретации знаний, необходимых для принятия решений в различных сферах человеческой деятельности.

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

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

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

Исходя из поставленной цели, в ходе исследования решаются следующие задачи:

)        исследование и выбор подходящих алгоритмов кластеризации;

)        исследование и выбор программного пакета для проведения эксперимента;

)        подготовка данных для кластеризации;

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

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

В диссертации получены следующие новые научные и практические результаты:

1)      выбраны объекты кластеризации данных дистанционного практикума по программированию и определены множества их признаков;

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

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

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

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

Основные результаты диссертационной работы докладывались, обсуждались на научно-технических конференциях и получили положительную оценку на следующих конференциях: Международной научной конференции «Молодые исследователи - регионам» (Вологда, 2016), Международной научной конференции «Молодые исследователи - регионам» (Вологда, 2015), 5-й Международной научно-технической конференции «Перспективное развитие науки, техники и технологий» (Курск, 2015), Международной научно-практической конференции «Информатизация инженерного образования» - ИФОРИНО-2016 (Москва, 2016), Международной научной конференции студентов и молодых ученых «Молодежь и системная модернизация страны» (Курск, 2016), 4-й Международной молодежной научной конференции «Будущее науки - 2016» (Курск, 2016), Международной молодежной научной конференции «Современные тенденции развития науки и производства» (Курск, 2016). Кроме того, результаты диссертационной работы докладывались и обсуждались на ежегодных выступлениях магистрантов кафедры АВТ .

1. АНАЛИТИЧЕСКАЯ ОБЗОР

1.1    Data Mining - способ «обнаружения знаний в базах данных»

Развитие методов хранения данных привело к большому росту объемов накопленной и анализируемой информации. Объемы данных так внушительны, что человек не в силах самостоятельно их проанализировать, хотя необходимость проведения такого анализа вполне очевидна, в этих "сырых" данных могут заключаться знания, которые в дальнейшем могут быть использованы для принятия решений. Очевидно, что для обнаружения скрытых знаний необходимо применять специальные методы автоматического анализа, при помощи которых приходиться добывать знания из «завалов» информации. При проведении автоматического анализа данных активно используются методы Data Mining.

Data Mining - исследование и обнаружение "машиной" (алгоритмами, средствами искусственного интеллекта) в сырых данных скрытых знаний, которые не были известны, нетривиальны, практически полезны, доступны для интерпретации человеком.

Основными этапами решения задач методами Data Mining являются[3,4]:

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

)        сбор данных;

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

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

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

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

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

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

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

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

Основу методов Data Mining составляют методы классификации, моделирования и прогнозирования, основанные на применении искусственных нейронных сетей, нечёткой логики, деревьев решений, генетических алгоритмов, эволюционного программирования, ассоциативной памяти.

Задачи, решаемые методами Data Mining, принято разделять на описательные и предсказательные. Предназначение описательных задачах - это дать наглядное описание имеющихся скрытых закономерностей, а в предсказательных задачах на первом плане стоит вопрос о предсказании для тех случаев, для которых данных ещё нет [5, 6, 7].

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

К предсказательным задачам относятся: классификация объектов (для заранее заданных классов), регрессионный анализ, анализ временных рядов.

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

Для задач классификации характерно «обучение с учителем», при котором обучение модели производится на выборке, содержащей входные векторы.

Для задач ассоциации и кластеризации применяется «обучение без учителя», при котором построение модели производится по выборке, в которой нет выходного параметра. Значение выходного параметра подбирается автоматически в процессе обучения[8].

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

)        отсутствуют какие-либо предварительные знания об анализируемых данных, поскольку мы находимся на начальном этапе анализа;

)        заранее неизвестно количество групп, к которым будет отнесён каждый объект выборки;

)        разбиение объектов необходимо осуществить не по одному параметру, а по целому набору признаков.

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

.2      Кластеризация как одна из задач Data Mining

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

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

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

Задача кластеризации состоит в разделении исследуемого множества объектов на группы "похожих" объектов, называемых кластерами. Кластер (cluster) в переводе с английского означает сгусток, пучок, группа.

Решением задачи классификации является отнесение каждого из объектов данных к одному (или нескольким) из заранее определенных классов, а в задаче кластеризации отнесение каждого из объектов данных осуществляется к одному (или нескольким) из заранее не известных классов [9,10, 11].

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

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

Решение значительно зависит также и от представления кластеров и предполагаемых отношений объектов данных и кластеров, т.е. необходимо учитывать такие свойства, как возможность / невозможность принадлежности объектов нескольким кластерам. Также необходимо определить само понятие принадлежности кластеру: однозначная (принадлежит / не принадлежит), вероятностная (вероятность принадлежности), нечеткая (степень принадлежности).

Перейдем к математической постановке задачи кластеризации.[12, 13, 14]

Дано - набор данных со следующими свойствами:

)        каждый экземпляр данных выражается четким числовым значением;

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

Найти:

)        способ меру сходства;

)        метод кластеризации;

)        разбиение данных по кластерам.

Формально задача кластеризации описывается следующим образом. Дано множество объектов данных I, каждое из которых представлено набором атрибутов. Требуется построить множество кластеров C и отображение F множества I на множество C, т. е. F: I → C. Отображение F задает модель кластеризации данных, являющуюся решением задачи.

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

Множество I определим следующим образом:

,                    (1.1)

где i_j - исследуемый объект.

Каждый из объектов характеризуется набором параметров:

.              (1.2)

Каждая переменная x_h может принимать значения из некоторого множества:

.                            (1.3)

Задача кластеризации состоит в построении множества:

,                (1.4)

где c_k - кластер, содержащий похожие друг на друга объекты из множества I:

,  (1.5)

где d(i_j, i_p) - расстояние - мера близости между объектами;

σ - величина, определяющая меру близости для включения объектов в один кластер.

Понятие «расстояние между объектами» отражает меру сходства, близости объектов между собой по всей совокупности используемых признаков.

Расстоянием между объектами i_j и i_p называется величина d(i_j, i_p), которая удовлетворяет следующим аксиомам:

1.        , для всех i_j и i_p

2.        , тогда и только тогда, когда i_j = i_p

3.       

4.       

Наиболее известные меры близости:

Евклидово расстояние. Это расстояние вычисляется следующим образом:

.                                                     (1.6)

Расстояние по Хэммингу. Это расстояние - средняя разность по координатам. Вычисляется по формуле: