Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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



ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Предметом исследования является кластеризация данных дистанционного практикума с использованием методов 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]:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

Найти:

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

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

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

Формально задача кластеризации описывается следующим образом. Дано множество объектов данных 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)

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

. (1.7)

Используются также такие метрики, как манхэттенское расстояние (расстояние городских кварталов), «расстояние Чебышева», метрика «доминирования».

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

Информационной основой практикума является база данных. В настоящее время в ней размещено более 1500 задач различной тематики, для каждой из них подготовлены средства автоматической проверки и выполнена экспертная оценка сложности в баллах (1-200 баллов) [1].

За десять лет эксплуатации практикума зафиксировано около 168 000 попыток, из них 49 000 успешных (т.е., в среднем, задача решается студентом за три попытки, но разброс количества попыток, затраченных для решения задачи, велик).

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

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

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

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

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

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

При иерархической кластеризации выполняется объединение маленьких кластеров в большие или разделение больших кластеров на маленькие. Иерархические алгоритмы в свою очередь делятся на агломеративные и дивизимные. [16]

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

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

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

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

1) методы:

a. агломеративные методы (CURE, ROCK, CHAMELEON и др.)

b. дивизимные методы (BIRCH, MST и др.)

2) неиерархические методы (К-средних (k-means), PAM (k-means +
k-medoids), CLOPE и др.).

Существует еще несколько критериев для классификации методов кластеризации[17]:

1) по способу анализа данных:

1.1 четкие;

1.2 нечеткие

2) по количеству применений алгоритмов кластеризации:

2.1 с одноэтапной кластеризацией;

2.2 с многоэтапной кластеризацией

3) по возможности расширения объема обрабатываемых данных:

3.1 масштабируемые;

3.2 немасштабируемые.

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

На основании полученной информации для проведения эксперимента были выбраны алгоритмы COBWEB, DBSCAN, алгоритм иерархической кластеризации, XMEANS и EM-алгоритм.

Таблица 1 - Результаты анализа существующих алгоритмов кластеризации

Критерий отбора	k-средних	CURE	BIRCH	COBWEB	DBSCAN	XMEANS	EM	Иерарх. класт-ция	FOREL
Число настраиваемых параметров	1	4	1	1	2	2	1	3	3
Не требуется задание числа кластеров	-	-	-	+	+	+	+	+	-
Легкость реализации, вычислительная простота	+	-	+	+	+	+	+	+	+
Работа с большим объемом данных	+	-	-	+	+	+	+	-	-
Возможность выделять кластеры сложной структуры	-	+	-	+	+	-	+	+	-
Возможность выделять кластеры в присутствии «шума» и выбросов	-	+	-	+	-	+	+	+	+
Работа с любым типом данных	-	-	-	+	-	+	-	+	+

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

Ниже представлено математическое описание выбранных алгоритмов.

Алгоритм DBSCAN - это плотностный алгоритм для кластеризации пространственных данных с присутствием шума, был предложен Мартином Эстер, Гансом-Питером Кригель и коллегами в 1996 году как решение проблемы разбиения данных на кластеры произвольной формы. [16]

Авторы DBSCAN экспериментально показали, что алгоритм способен распознать кластеры различной формы, например, как на рисунке 2.1.

Рисунок 2.1 - Примеры кластеров произвольной формы

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

Алгоритм DBSCAN для заданных значений параметров исследует кластер следующим образом: сначала в качестве затравки выбирает случайную точку, являющуюся ядровой, затем помещает в кластер саму затравку и все точки, плотно-достижимые из неё.



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

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

EM-алгоритм является итеративным алгоритмом, каждая итерация которого состоит из двух шагов: шага математического ожидания (expectation step, E-шаг) и шага максимизации (maximization step, M-шаг).

На E-шаге вычисляется ожидаемое значение функции правдоподобия, при этом скрытые переменные рассматриваются как наблюдаемые. На M-шаге вычисляется оценка максимального правдоподобия, таким образом, увеличивается ожидаемое правдоподобие, вычисляемое на E-шаге. Затем это значение используется для E-шага на следующей итерации. Алгоритм выполняется до сходимости. Опишем эти шаги с математической точки. Для этого рассмотрим функцию:

(2.1)

где q -- распределение вероятностей ненаблюдаемых переменных Z;

p_Z|X ( · | x;и) -- условное распределение ненаблюдаемых переменных при фиксированных наблюдаемых и параметрах ;

H -- энтропия;

D_KL -- расстояние Кульбака-Лейблера.

Тогда шаги EM-алгоритма можно представить как:

E-шаг: Выбираем q, чтобы максимизировать F:

(2.2)

M-шаг: Выбираем и, чтобы максимизировать F:

(2.3)

Алгоритм X-Means является одним из наиболее популярных методов кластеризации. Также он является некоторым обобщением алгоритма k-средних и использует его в своей реализации. Одним из главных отличий данного алгоритма можно назвать отсутствие требования точного количества искомых кластеров, задается лишь требуемый диапазон значений для количества кластеров. [18]

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

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

Данный алгоритм использует Байесовский критерий выбора модели. Он вытекает из принципа максимума правдоподобия. Этот критерий определяется формулой:



(2.4)

где ???? - логарифмическая функция правдоподобия для модели;

?? - длина вектора параметров;

?? - количество объектов в выборке.

Иерархическая кластеризация - это комплекс алгоритмов, использующих разделение крупных кластеров на более мелкие или объединение мелких в более крупные. Соответственно, выделяют дивизивную и агломеративную кластеризации. В данной работе использовалась агломеративная кластеризация Ланса-Уильямса.[17]

Алгоритм:

1. Cначала все кластеры одноэлементные:

(2.6)

2. Для всех (t -- номер итерации):

3. найти в два ближайших кластера:

(2.8)

4. Слить их в один кластер:

5.

;(2.10)



6. Для всех вычислить расстояние R(W, S) по формуле Ланса-Уильямса.

Расстояние между кластерами определяется как:

,(2.11)

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

Алгоритм COBWEB - классический метод инкрементальной концептуальной кластеризации, которая определяет кластеры как группы объектов, относящиеся к одному концепту - определённому набору пар атрибут-значение. Он создаёт иерархическую кластеризацию в виде дерева: каждый узел этого дерева ссылается на концепт и содержит вероятностное описание этого концепта, которое включает в себя вероятность принадлежности концепта к данному узлу и условные вероятности вида[10]:

(2.12)

где - пара атрибут-значение;

- класс концепта.

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

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

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

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

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

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

The Fuzzy Clustering and Data Analysis Toolbox

Программный комплекс для Matlab предоставляющий три категории функций [19]:

1) алгоритмы кластеризации, разбивающие данные на кластеры различными подходами: K-means и K-medoid - алгоритмы устойчивой кластеризации; FCMclust, GKclust и GGclust алгоритмы неустойчивой кластеризации;

2) функции анализа, оценивающие, каждое фиксированное разбиение, выполненное алгоритмом, основанные на индексах(Xie and Beni's, Dunn, Alternative Dunn, Partition index);

3) функции визуализации, реализующие модифицированный метод Sammon'а отображения данных в пространство меньшей размерности.

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

Cluster Validity Analysis Platform (CVAP)

Приложение является программным инструментом, реализовано также на Matlab. Основано на удобном графическом интерфейсе, включает в себя несколько алгоритмов кластерного анализа (K-means, hierarchical, SOM, PAM), а также наиболее широко используемые индексы оценки их работы. Работая в этом приложении, пользователь получает возможность не только загружать свои данные, а так же сохранять результаты работы. Несомненным достоинством является то, что графическая часть позволяет анализировать для одного индекса сразу несколько алгоритмов[20].

SPSS Statistics

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

RapidMiner

Данный программный комплекс является средой для машинного обучения и анализа данных, в которой пользователь ограждён от всей «черновой работы». [22] Вместо этого ему предлагается «нарисовать» весь желаемый процесс анализа данных в виде цепочки (графа) операторов и запустить его на выполнение. Цепочка операторов представляется в RapidMiner в виде интерактивного графа и в виде выражения на языке XML (основного языка системы).

Сейчас в системе реализовано более 400 операторов. Из них

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

2. Операторы предобработки (фильтрация, дискретизация, заполнение пропусков, уменьшение размерности и т.д.);

3. Операторы работы с признаками (селекция и генерация признаков);

4. Мета-операторы (например, оператор оптимизации по нескольким параметрам);

5. Операторы оценки качества (скользящий контроль и т.д.);

6. Операторы визуализации;

7. Операторы загрузки и сохранения данных (включая работу со специальными форматами: arff, C4.5, csv, bibtex, базы данных и т.д.).

WEKA

Программа WEKA написана на языке Java в университете Вайкато (Новая Зеландия) и предоставляет пользователю возможность предобработки данных, решения задач кластеризации, классификации, регрессии и поиска ассоциативных правил, а также визуализации данных и результатов. [23] Программа очень проста в освоении (пожалуй, имеет самый интуитивный интерфейс среди всех программ такого типа), бесплатна и может быть дополнена новыми средствами предобработки и визуализации данных.

Исходные данные могут представлены в виде матрицы признаковых описаний объектов. Weka предоставляет доступ к SQL-базам через Java Database Connectivity (JDBC) и в качестве исходных данных может принимать результат SQL-запроса.

Weka имеет пользовательский интерфейс Explorer, но та же функциональность доступна через компонентный интерфейс Knowledge Flow и из командной строки. Имеется отдельное приложение Experimenter для сравнения предсказательной способности алгоритмов машинного обучения на заданном наборе задач.

Explorer имеет несколько панелей[24]:

1) панель предобработки Preprocess panel позволяет импортировать данные из базы, CSV файла и т.д., и применять к ним алгоритмы фильтрации, например, переводить количественные признаки в дискретные, удалять объекты и признаки по заданному критерию;

2) панель классификации Classify panel пoзволяет применять алгоритмы классификации и регрессии к выборке данных, оценивать предсказательную способность алгоритмов, визуализировать ошибочные предсказания, ROC-кривые, и сам алгоритм, если это возможно (в частности, деревья решений);

3) панель поиска ассоциативных правил Associate panel решает задачу выявления всех значимых взаимосвязей между признаками;

4) панель кластеризации Cluster panel даёт доступ к алгоритму k-средних, EM-алгоритму, COBWEB, DBSCAN и другим;

5) панель отбора признаков Select attributes panel даёт доступ к методам отбора признаков;

6) панель визуализации Visualize строит матрицу графиков разброса (scatter plot matrix), позволяет выбирать и увеличивать графики, и т.д.

Выбор программного средства для решения задачи кластеризации[25] Недостаток The Fuzzy Clustering and Data Analysis Toolbox и CVAP прежде всего заключается в их недоступности и невозможности анализа собственных алгоритмов. Данные некоммерческие приложения реализованы в основном на Matlab, который автоматически накладывает ряд ограничений:

1) приложения зависят от версии и поставленных дополнительных библиотек;

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

3) графическая и вычислительная реализации фиксированы;

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

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

Чтобы воспользоваться средствами The Fuzzy Clustering and Data Analysis Toolbox, необходимо написание дополнительных функций, связывающих алгоритм и функции анализа.

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

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

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

Свободные же программные комплексы (RapidMiner, WEKA) также накладывают ряд ограничений на процессы обработки данных. В данное ПО нет возможности встроить собственные алгоритмы, количество и разнообразие имеющихся алгоритмов кластеризации также незначительно.

RapidMiner имеет очень хорошие средства визуализации: способов визуализации достаточно много и все графики смотрятся очень эффектно. Но единственный минус, из-за которого пришлось отказаться от данного ПО, это отсутствие подключения к базе данных FireBird и отсутствие выбранных в начале исследования алгоритмов.

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

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

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

1) студенты (пользователи практикума);

2) задачи практикума;

3) пары «студент - задача».



Рис. 2.2 - Концептуальная схема базы данных

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

Для задач в базе данных хранятся следующие атрибуты:

? идентификатор задачи;

? предел использования процессорного времени и оперативной памяти для данной задачи;

? минимальный процент уникального кода при котором решение для данной задачи считается уникальным;

? экспертная сложность задачи;

? количество пользователей решивших данную задачу;

? количество пользователей пытавшихся решивших данную задачу;

? количество решений поступивших для данной задачи.

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

Каждая попытка решения задачи студентом фиксируется в базе данных, при этом сохраняются следующие сведения:

? идентификатор студента и номер задачи;

? дата и время получения решения задачи системой проверки;

? используемый компилятор;

? статус попытки (верное решение или код ошибки);

? характеристики верного решения - время исполнения программы (запроса, скрипта), размер используемой памяти, процент плагиата.

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

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

1) идентификатор пользователя;

2) - относительный показатель уровня подготовки студента;

3) среднее число попыток решения задач;

4) средняя сложность решаемых задач;

5) год обучения (1-5, студенты прошлых лет рассматриваются как один курс «-1»).

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

1) идентификатор задачи;

2) - относительный показатель степени сложности задачи;

3) количество неуникальных решений;

4) количество частично верных решений;

5) среднее число попыток решения задачи.

Для кластеризации пар «студент-задача» были выбраны следующие атрибуты, которые позволят определить подходит задача студенту или нет:

1) сложность задачи;

2) - относительный показатель степени сложности задачи;

3) - относительный показатель уровня подготовки студента;

4) средняя сложность решенных студентом задач;

5) - относительный показатель с какой попытки решена задача;

6) Количество дней между первой и последней попыткой решения задачи.

В базе данных для каждой задачи выполнена экспертная оценка сложности в баллах (1-200 баллов). Но эмпирическая оценка сложности задачи, вычисленная на основе реальных данных о решении этой задачи множеством студентов, не всегда может совпадать с экспертной. Поэтому стоит обратить внимание, что во всех опытах в качестве атрибута использовалась именно эмпирическая оценка сложности задачи.



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

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

кластеризация data mining алгоритм

В настоящее время в базе данных дистанционного практикума накоплен достаточно большой объем информации: больше 168 000 решений отправлено студентами на проверку за всё время эксплуатации системы, более 1500 задач хранится в базе данных. Такой большой объем данных начал отрицательно сказываться на производительности системы. В связи с этим было создано хранилище данных (ХД), которое позволило разделить данные, используемые для оперативной обработки и для решения задач анализа. ХД было организовано на базе СУБД Oracle 11g, которая уже используется в практикуме для обучения студентов разработке SQL запросов.

Для анализа накопленных данных в ХД имеется таблица фактов, содержащая детальную информацию о каждой попытке решения конкретной задачи конкретным студентом. Кроме того, имеются агрегированные данные по каждой задаче и каждому студенту. Необходимые для кластеризации множества атрибутов были извлечены стандартными средствами выгрузки Oracle SQL Developer в файл формата .txt [26].

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

Перед тем, как начать процесс кластеризации, необходимо загрузить данные в пакет. WEKA поддерживает определенные форматы: .arff, .csv. Полученные данные их хранилища БД в формате .txt. Поэтому для проведения эксперимента необходим модуль подготовки данных, который будет преобразовывать данные из формата .txt в формат .csv, текстовые данные преобразовывать в цифровой код, так как некоторые алгоритмы работают только с числовыми типами. Таким образом, модуль подготовки данных проверяет входные данные на наличие строковых типов, если такие имеются, преобразует их в цифровой код. Затем полученные данные приводит к формату .csv, т.е. первая строка содержит название атрибутов, следующие строки представляют собой значения этих атрибутов, разделенные запятой. На выходе получаем файл формата .csv, готовый для загрузки в WEKA.

Обобщенный алгоритм работы модуля подготовки данных приведен на рисунке 3.1.

Моду ль подготовки данных реализован в соответствии с алгоритмом работы в среде разработки Microsoft Visual Studio 2008 на язык С++. [27, 28]

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

Кластеризация студентов - это первый опыт анализа данных с целью получения скрытых знаний с помощью выбранных алгоритмов. Алгоритмы изначально были опробованы на модельных данных, взятых из репозитория UCI, который является крупнейшим репозиторием реальных и модельных данных машинного обучения. Задачи (наборы данных, data set) именно этого репозитория чаще всего используются научным сообществом для эмпирического анализа алгоритмов машинного обучения[1].

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

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

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

- студенты, не отправившие ни одного решения;

- студенты, которым потребовалось для верного решения задач средней сложности (15 баллов) две попытки;

- студенты, которые решали легкие задачи (10 баллов) с первой попытки;

- студенты, у которых число отправленных решений для одной задачи больше десяти, средняя сложность задач 87 баллов (от 50 до 150 баллов);

- студенты, которым удалось получить верное решение сложных задач с первого раза (100 баллов);

- студенты, выбравшие сложные задачи и не сумевшие их решить (сложность задач 150 баллов).

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

Алгоритм DBSCAN выделил 5 кластеров:

1) студенты, хорошо решавшие задачи любой сложности;

2) студенты, решавшие задачи средней сложности;

3) студенты, выбравшие сложную задачу, но не сумевшие ее решить;

4) студенты, не отправившие не одного решения;

5) студенты, решавшие сложные задачи с 2-3 попыток.

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

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

Алгоритм COBWEB выделил 4 кластера:

1) студенты, решавшие легкие задачи с первой попытки;

2) студенты, решавшие задачи средней сложности с 1-2 попыток;

3) студенты, выбравшие сложные задачи, но так и не решившие их;

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

EM-алгоритм выделила 4 кластера:

1) студенты, не отправившие не одного решения;

2) студенты, решившие несложные задачи с первой попытки;

3) студенты, решившие задачи средней сложности за 2-3 попытки;

4) студенты, выбравшие сложные задачи, но не всегда решившие их.

Алгоритм X-MEANS выделил 6 кластеров:

1) студенты, решавшие легкие задачи с первой попытки;

2) студенты, решавшие легкие задачи за 2-3 попытки;

3) студенты, которые отправляли 1 - 2 решения задачи средней сложности, если оно оказывалось неверным, забрасывали задачу;

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

5) студенты, решившие задачи средней сложности за 1-2 попытки;

6) студенты, не отправившие ни одного решения.

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

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

Вторым этапом исследования накопленных данных в проверяющей системе была кластеризация задач. Ожиданием было получить кластеры задач разной сложности. Полученные в ходе эксперимента результаты представлены ниже[29].

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

- задачи, к которым не приступал ни один студент;

- задачи, у которых процент решивших студентов составляет 65-70%;

- задачи, у которых среднее количество попыток больше 5.

- задачи, которые решены с 1 попытки.

Алгоритм DBSCAN выделил 4 кластера:

1) задачи, к которым не приступал ни один студент;

2) задачи, которые решили два-три студента;

3) задачи, для которых количество пользователей пытавшихся решить превышает количество пользователей решивших данную задачу где-то в 2 раза;

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

Алгоритм COBWEB выделил 6 кластеров:

1) задачи, у которых количество отправленных и верных решений примерно одинаковое (относительный показатель числа решивших к числу решавших студентов от 0.8 до 1) и среднее число попыток - 4;

2) задачи, которые не решал ни один студент;

3) задачи, которые решили два-три студента с одной попытки;

4) задачи, которые были решены в среднем с 3 попыток;

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

6) задачи, у которых неверных решений больше, чем верных.

Алгоритм иерархической кластеризации выделил 5 кластеров:

1) задачи, у которых количество пользователей решивших и решавших примерно одинаковое (относительный показатель примерно 0.9, среднее число попыток - 3, количество пользователей при этом от 20 до 40 человек;

2) задачи, у которых процент решивших студентов составляет 65-70%;

3) задачи, к которым студенты приступали и решали их, а среднее количество попыток 2;

4) задачи, для решения которых понадобилось в среднем 6-7 попыток, при этом решило эти задачи не больше 20 человек;

5) задачи, к которым не приступал ни один студент.

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

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

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

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

Этот эксперимент проводился на обновленной версии статистического пакета WEKA, в которой появился новый алгоритм кластеризации - CANOPY. Это быстрый алгоритм кластеризации, используемый чаще всего для анализа данных большой размерности. Идея алгоритма заключается в том, чтобы разделить множество исходных объектов на несколько подмножеств, которые называются Canopy. Canopy - это такое множество элементов, у которого расстояние от центральной точки из этого множества до всех остальных точек в множестве не превышает некоторого значения. Данный алгоритм на входе не требует указания количества кластеров, поэтому он может использоваться в эксперименте. [30]

Обобщенные результаты кластеризации пар «студент-задача» представлены в таблице 3.5.

Таблица 3.5 - Обобщенные результаты кластеризации пар «студент-задача»

Алгоритм	Время выполнения, с	№ кластера	Количество объектов	% соотношение объектов
EM	175.84	1 кластер	18 717	43%
		2 кластер	24 885	57%
COBWEB	156.95	1 кластер	19 006	44%
		2 кластер	24 596	56%
CANOPY	0.05	1 кластер	14 077	32%
		2 кластер	29 525	68%
KMeans	0.63	1 кластер	19 949	46%
		2 кластер	23 653	54%
Иерархическая кластеризация	Алгоритм не смог кластеризовать исходную выборку из-за большого количества данных

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

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

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

Пример формирования кластеров ЕМ-алгоритмом в зависимости от атрибутов кластеризации представлен на рисунках 3.3, 3.4, 3.5, 3.6, 3.7.

Рис. 3.3 - Разбиение объектов на кластеры по признаку «степень сложности задачи»