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

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

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»

Факультет бизнеса и менеджмента

Выпускная квалификационная работа

по направлению подготовки бизнес-информатика

образовательная программа «бизнес-информатика»

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

Канаев Павел Дмитриевич

Москва 2018



Введение

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

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

Объект исследования дипломной работы - студенты британских школ, которые проводили обучение в 2004-2006 годах.

Предмет исследования - успеваемость студента, финальная оценка за экзамен.

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

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

· Изучение предметной области исследования

· Теоретический анализ моделей обработки данных

· Теоретический анализ алгоритмов регрессии и кластеризации

· Проведение регрессионного анализа

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

· Разработка программного продукта

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

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

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

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



Глава 1. Теоретические аспекты анализа данных

1.1 Алгоритмы предобработки данных

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

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

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

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

· Label Encoding

· One-Hot Encoding

· Hashing trick

Label Encoding - вид кодирования категориальных признаков, при котором каждому уникальному значению признака ставится в соответствие некоторое число от 0 до n-1, где n - количество уникальных значений. Например, если имеется следующая таблица, в которой «Cat» - категориальный признак (Таб1), то после преобразования Label Encoding текущая таблица будет иметь вид (Таб2)

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

One-Hot Encoding - вид кодирования, при котором для каждого уникального значения искомого признака создаётся новый бинарный признак, так что значения всех новых равно нулю, за исключением одного, который является связанным с исходной категорией. Иными словами, для признаков, которые имеют n уникальных значений, создаются n новых переменных. Например, если имеется следующая таблица, в которой «Cat» - категориальный признак (Таб1), то после преобразования One-Hot Encoding текущая таблица будет иметь вид (Таб3)

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

Хэшировние признаков (Hashing trick) - вид кодирования, при котором исходные данные (k) преобразовываются по определённому правилу (f) в битовую строку (u). То есть

Преимуществом этого вида по сравнению с Label Encoding является отсутствие необходимости предварительного анализа данных и скорость обработки. Недостатком можно считать коллизию хэш-функций. Коллизией функции F будем называть такой случай, когда F(x) = F(y), где x и y -два разных исходных признака. Например, если имеется следующая таблица, в которой «Cat» - категориальный признак (Таб1), то после хеширования текущая таблица может иметь вид (Таб4)

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

Нормированием непрерывных значений некоторого признака A={,…,} назовём процедуру f такую что . Один из способов создать такое нормирование - воспользоваться формулой , где и - соответственно минимальный и максимальный элемент признака . Например, если имеется следующая таблица, в которой «Score» - непрерывный признак (Таб5), то после нормирования текущая таблица может иметь вид (Таб6)

Снижение размерности данных осуществляется за счёт исключения малозначащих признаков. Для их выявления в рамках регрессионного анализа используется корреляция и t-test.

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



, где , и

В качестве проверки значимости коэффициентов регрессии можно использовать критерий Фишера. Для линейной регрессии рассмотрим отдельно в следующей главе.

1.2 Регрессионные алгоритмы

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

После предобработки данных логичным было бы их применение, используя машинное обучение. Одним из самых распространённых способов использования таковых является регрессия. Регрессионным анализом назовём такой метод исследования влияния независимых переменных на зависимую, которая в общем случае является непрерывной величиной. В данном разделе рассмотрим самую базовую и простую часть такого типа моделирования - линейную регрессию. Линейной регрессией будем называть такую модель, в которой описывается зависимость между переменной y от вектора переменных x и для которой выполняется условие , где - коэффициенты регрессии, а - случайная ошибка регрессии. В одномерном случае регрессия будет иметь вид обыкновенной линейной функции . В таком случае график такой функции будет иметь вид (Рис1):



Рис 1. Линейная регрессия.

Линейная регрессия имеет следующие предположения:

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

· Остатки линейной регрессии имеют постоянную дисперсию. То есть

Одним из главных методов создания линейной регрессии является метод наименьших квадратов (МНК). МНК сводится к поиску минимума суммы квадратов ошибок регрессии. Ошибкой регрессии будем называть разницу между истинным значением целевой переменной и значением соответственного элемента оценки.

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

Пусть y - вектор-столбец целевой переменной, х - матрица признаков

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

Тогда вектор оценок целевой переменной будет иметь вид

Вектор ошибок (остатков) регрессии будет равен

Соответственно, сумма квадратов ошибок в матричном виде будет иметь вид

Для поиска минимума функции RSS необходимо её продифференцировать и прировнять к нулю.

Отсюда получаем решение этой системы уравнений, которое называется нормальным уравнением:

Соответственно, элементы вектора являются искомыми коэффициентами линейной регрессии.

Для оценки значимости коэффициентов линейной регрессии можно применить критерий Фишера. Нулевая гипотеза этого критерия утверждает, что целевая переменная y не зависит от переменных x. Альтернативная говорит о зависимости целевой переменной от признаков х. Тогда фактический уровень F рассчитывается по формуле:

,

где n - объём выборки, m - количество признаков

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

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

1.2.2 Регуляризация линейной регрессии

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

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

· L1 - регуляризация (LASSO)

· L2 - регуляризация (RIDGE)

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

Рассмотрим L1- регуляризацию:

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

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

Эта система переходит в следующую задачу оптимизации:

Согласно теореме Куна-Таккера необходимым и достаточным условием существования минимума функции Лагранжа являются условия:

· Стационарности:

· Дополняющей нежёсткости:

Рассмотрим L2- регуляризацию:

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

По аналогии с LASSO регуляризацией составляется следующая задача оптимизации:

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

Параметры в большинстве случаев подбираются эмпирически вручную.

1.2.3 Меры точности линейной регрессии

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

·

· Adjusted

· MAE (Mean absolute error)

· MSE (Mean squared error)

· RMSE (Root mean squared error)

Рассмотрим коэффициент детерминации :

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

где - дисперсия случайной ошибки модели.



где - сумма квадратов ошибки регрессии

а - общая сумма квадратов

При рассмотрении линейной регрессии с константой, где , коэффициент детерминации

Соответственно, . Причём, чем выше , тем лучше модель.

Рассмотрим скорректированный (adjusted) коэффициент детерминации :

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

где n - количество объектов, а k - количество переменных.

Очевидно, что , так как количество параметров модели 1. Стоит заметить, что может быть и отрицательным, если k>n. Хотя, в таком случае не стоит говорить об информативности признаков.

Рассмотрим среднюю абсолютную ошибку (MAE).

Средняя абсолютная ошибка - метрика, отображающая разницу между истинными значениями целевой переменной и соответствующим значением регрессионной модели. Иными словами, это сумма ошибок в абсолютной мере, делённая на объём выборки.

Рассмотрим среднеквадратичную ошибку (MSE).

Mean squared error - метрика, которая выражается в сумме квадратов разницы между истинными значениями целевой переменной и соответствующим значением регрессионной модели. Другими словами, эту метрику можно выразить как

Рассмотрим среднеквадратичную ошибку (RMSE).

Root mean squared error - метрика, которая выражается в виде корня из суммы квадратов разницы между истинными значениями целевой переменной и соответствующим значением регрессионной модели. Другими словами, это корень квадратный из показателя MSE.

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

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

1.2.4 Полиноминальные регрессии

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

,

где J = (,,…,) - мультииндекс (набор из неотрицательных чисел).

В случае одной переменной такую функцию можно записать, как .

В одномерном случае полином степени 3 может выглядеть следующим образом (Рис 2):

Рис 2. Полиноминальная регрессия.



Степень полинома бывает очень тяжело подбирать, так как этот вид регрессии особенно склонен к переобучению. Например, известно, что через n+1 точек можно построить полином степени n. Для этого следует решить следующую СЛУ относительно параметров

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

Представим, что в рассматриваемой ранее функции первая и последняя точки являются «выбросами». В таком случае будет наблюдаться переобучение, и функция, скорее всего, является линейной (Рис 3).

Рис 3. Линейная регрессия.

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

Также, очевидным минусом полиноминальной регрессии может являться и скорость обучения. При достаточном большом количестве объектов при n признаках, линейная функция будет иметь всего n+1 слагаемых. Если же полином будет иметь хотя бы степень 2, то количество слагаемых в модели изменится на и будет равно , что уже существенно увеличит время выполнения при больших n.

1.2.5 Метод опорных векторов

После стандартных представлений функций, следует рассмотреть один из алгоритмов машинного обучения - МОВ. Метод опорных векторов (SVM - Support vector Machine) - это особый класс алгоритмов, который характеризуется использованием ядер, отсутствием локальных минимумов, и используется для решения задач классификации и регрессии. В некоторой литературе для задач регрессии этот метод также может быть назван Опорный вектор регрессии (SVR).

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

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

где выражение типа

Геометрическая интерпретация данного метода может иметь следующий вид (Рис 4):



Рис 4. Интерпретация МОВ.

Дополнительные параметры C, и обозначим, как:

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

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



1.2.6 Решающие деревья

Следующим из рассматриваемых регрессионных алгоритмов - решающее дерево. Следует заметить, что этот изначально этот алгоритм является классификатором, но он может быть модифицирован в регрессию. Итак, дерево принятия решений (Decision tree) - метод построения модели, в листьях которого стоят значения целевой функции, а в узлах условия перехода для определения по какому из рёбер идти далее. Как правило, при истинном значении некоторого условия переход происходит в левую сторону, при отрицательном - в правую. Максимальная длинна пути одного алгоритма называется глубиной дерева. Деревом решений у данного метода является строго ориентированный граф без петель.

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

· CART (используется всего одно дерево)

· Random Forest (используется ансамбль деревьев)

· Stochastic Gradient Boosting (используется также несколько деревьев)

Далее рассмотрим каждый метод отдельно:

CART (Classification and regression trees - Классификационные и регрессионные деревья):

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



где - вероятность класса j в узле c.

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

RandomForest (Случайный лес):

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

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

Stochastic Gradient Boosting (Стохастическое градиентное добавление):

Стохастическое градиентное добавление является методом построения «слабых» предсказывающих деревьев принятия решений. На первом этапе строится фактически случайное дерево, на втором - вычисляется разность между предсказанием дерева, умноженные на коэффициент слабости и самой целевой переменной на конкретном шаге. Иными словами, выполняется равенство . Таким образом, каждый следующий шаг пытается исправить ошибки, которые были получены при построении предыдущего дерева. Как и для всех градиентных методов, операция будет производиться до тех пор, пока улучшение (разность) не будет стремиться к нулю.

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

1.2.7 XGBoost & CatBoost Regression

Одними из самых современных и эффективных алгоритмов на сегодняшний день являются методы экстремального градиентного бустинга. За реализацию таковых отвечают XGBoost и CatBoost. XGB и CB являются библиотеками Google и Yandex соответственно, в которых выполняются алгоритмыGradient Boosting Machine. Соответственно, в этой главе будет разбираться классический алгоритм функционального градиентного спуска Фридмана.

Как и во всех задачах машинного обучения, необходимо восстановить зависимость, между признаками x и целевыми переменными y. Задача приобретёт вид нахождения такой f, что. Для решения подобной задачи, как и в предыдущих главах, будет рассматриваться функция потерь:



Перепишем функцию , используя термины матожиданий:

Для ограничения решения пропараметризируем функцию

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

где приближение в M итераций описывается, как:

Далее выбирается самый простой итеративный алгоритм приближения - градиентный спуск, для которого выписывается градиент для каждой итерации t=1,..,M (для начала инициируется начальное приближение ):



После этого задаётся текущее итеративное приближение:

Добавляется к уже текущему:

Итоговое приближение:

Соответственно, получается функция:

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

После этого данная функция ограничивается некоторым семейством функций:



Получаем соответствующую задачу на шаге t:

где - некоторый оптимальный коэффициент

Для полученной задачи решаем МНК-регрессию:

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

И также обновляем приближение



Итоговая модель градиентного бустинга Фридмана:

1.3 Методы кластеризации

1.3.1 Кластеризация и её метрики

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

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

Наиболее часто используемые метрики кластеризации:

1. Евклидово расстояние.

Самое обычное расстояние в геометрическом плане. Рассчитывается как:



где n - размерности объектов

2. Квадрат евклидового расстояния.

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

3. Манхэттенское расстояние.

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

4. Расстояние Чебышева.

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



5. Степенное расстояние.

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

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

1.3.2 Алгоритмы кластеризации

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

1. Иерархические алгоритмы:

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

· Нисходящие

· Восходящие

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

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

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

2. Алгоритмы квадратичной ошибки:

В данном типе решения задачи кластеризации рассматривается минимизация суммы квадратов разности между каждым объектом и соответствующим центром масс кластера. Иными словами, существует проблема минимизации ошибки разбиения:

где центр масс каждого кластера, а определённая координата на плоскости, относящаяся к i-ому объекту и j-ому кластеру

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

Одним из самых распространённых алгоритмов этого типа является k-means, который будет подробнее рассмотрен в следующих главах.

3. Нечеткая кластеризация:

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

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

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

Одним из самых распространённых алгоритмов этого типа является c-means, который будет подробнее рассмотрен в следующих главах.

4. Выделение связных компонент:

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

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

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

5. Послойная кластеризация:

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

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

6. Минимальное покрывающее дерево:

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

Например, если минимальное покрывающее дерево объектов A,B,C,D,H,F выглядит следующим образом (Рис 5):

Рис 5. Минимальное покрывающее дерево.

То после первого шага данного алгоритма связь CG исчезнет, ввиду того, что у неё самый большой вес. Сформируются следующие два кластера (Рис 6):

Рис 6. Кластеризация.



На следующем этапе алгоритма станет ещё на один кластер больше (Рис 7):

Рис 7. Кластеризация.

В результате, при каждом следующем шаге, количество кластеров будет как минимум увеличиваться на 1 (за исключением тех случаев, когда рёбра будут иметь одинаковую длину).

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

1.3.3 Алгоритм кластеризации K-means

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

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

Наглядная демонстрация алгоритма:

Допустим, имеется 10 объектов и два кластера, к которым нужно эти объекты отнести (Рис 8).

Рис 8. Рассматриваемые объекты.

Два центра масс кластера определяются случайным образом (Рис 9).

Рис 9. Случайные центры масс.



Исходя из соответствующей метрики, объекты помечаются принадлежными к соответствующей группе (Рис 10).

Рис 10. Кластеризация.

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

Рис. 11. Пересчёт центра масс.

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

Рис 12. Переобозначение принадлежности к кластерам.



Вновь пересчитывается центр масс (Рис 13).

Рис 13. Пересчёт центра масс.

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

Рис 14. Графическая интерпретация результатов кластеризации.

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



1.3.4 Алгоритм нечёткой кластеризации C-means

Как уже писалось ранее, алгоритмы нечёткой кластеризации являются своеобразной модификацией алгоритмов квадратичной ошибки. Так что можно сказать, что c-means - это модификация k-means. Разница заключается в том, что в данном случае появляются величины U - матрица принадлежности и m - коэффициент неопределённости. Матрица принадлежности является искомым объектом, который требуется от задачи кластеризации данного типа. Элементпоказывает, как сильно объект i принадлежит кластеру j. Иными словами, является вероятностью принадлежности объекта i к кластеру j. Отсюда следует ограничение:

Целевая функция минимизации ошибки выглядит в отличной от метода квадратичной ошибки форме:

где центр масс рассчитывается по формуле:

Соответственно, алгоритм нечёткой кластеризации c-means выглядит следующим образом:

1. Формируется случайным образом матрица принадлежности U при выполнении условия:



2. Уточняется центр масс каждого кластера:

3. Выбирается нужная метрика. Чаще всего используется Евклидово расстояние:

4. Пересчитываются коэффициенты степеней принадлежности объектов к кластерам:

5. Алгоритм применяется до тех пор, пока изменение матрицы принадлежности U не станет незначительным:

где - значение, полученное на предыдущей итерации.

Итоговая матрицаявляется искомым выходным данным для алгоритма рассматриваемого типа.



1.4 Метод главных компонент

Исходя из того, что для графической иллюстрации кластеризации необходимы всего два или три компонента каждого объекта ввиду ограниченности мира трёхмерным пространством, необходимо выделить таковые из всех имеющихся признаков. Для этого следует использовать метод главных компонент. Метод главных компонент (Principal Component Analysis - PCA) -- один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Для анализа данного метода необходимо решить следующие задачи:

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

· Нахождение подпространства меньшей размерности, такого что в ортогональной проекции среднеквадратичное уклонение от среднего значения максимально

· Нахождение подпространства меньшей размерности, такого что в ортогональной проекции среднеквадратичное расстояние между точками максимально

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

Аппроксимация данных:

Даны объекты, где m - количество объектов, а n - количество признаков. Для каждых среди всех k-мерных линейных многообразий в найдём:



где

- ортонормированный набор векторов

, где

- скалярное произведение

Соответственно, векторы главных компонент определяются:

1.

2.

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

4. Аналогично делаем от 2 до k:

Так как планируется выделение всего двух компонент для иллюстрации графика, останавливаемся на этом шаге.

Поиск ортогональных проекций с наибольшим рассеянием:

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

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

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

Иными словами, нужно найти максимальное значение для k=1,2:



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

Все эти задачи сводятся к задаче диагонализации ковариационной матрицы С

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

где p - ранг матрицы X, а - вектор главных компонент.

Выводы

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



Глава 2. Постановка задачи оценки выбора методов успеваемости студентов

2.1 Формальное описание задач

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

· Выбор языка программирования для проведения анализа данных. Для качественного выполнения необходимо выбрать язык, в котором имеется относительно большое количество библиотек для работы с данными. Исходя из выбора языка, соответственно должен произвестись выбор среды (сред) программирования, в которой(-ых) будет производиться анализ данных и написание интерфейса программы.

· Предобработка данных. Используя выбранный язык программирования, выполнить все те требования, которые были описаны в разделе 1.1 «Алгоритмы предобработки данных». Необходимо представить данные в таком виде, которые подойдут под соответствующие методы тех библиотек, которые могут находиться в выбранной среде программирования.

· Выбор релевантной модели регрессии с подбором значимых параметров. Исходя из теоретических аспектов, описанных в разделе 1.2 необходимо выбрать модель, которая будет иметь наименьшую ошибку, наибольшую точность полученных результатов и относительно высокую скорость обучения. Для выбранной модели на основе статистических тестов (например, таких, как t-test или anova) выделить статистически значимые признаки регрессии.

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

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

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

· Выбор моделей интерпретации полученных кластеров. Необходимо изобрести универсальный способ описания полученных кластеров для модели нечёткой кластеризации.

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

2.2 Описание предметной области

Для реализации представленных подзадач необходимо изучить структуру рассматриваемого датасета с описанием полей и их возможных значений. Изучаемая таблица с данными состоит из информации об английской молодежи за 2004-2006 гг. В ней имеются 20 признаков по каждому ученику, всего которых насчитывается 8273 человека. Ключевым параметром всей выборки является поле ks4score, которое мы и будем изучать. Имеются следующие признаки:

· ks4score - это итоговая GCSE оценка, итоговый балл за среднее образование. Данный признак имеет непрерывные значения в диапазоне от 0 до 1000 баллов

· ks3score - оценка за предыдущую образовательную ступень. В российском понимании, это балл за неполное среднее образование (9 класс). Имеет непрерывные значения в диапазоне от 0 до 50 баллов.

· ethniс - национальность ученика, его раса. Имеет категориальные значения {'Bangladeshi', 'Black African', 'Black Caribbean', 'Indian', 'Mixed heritage', 'Other', 'Pakistani', 'White British'}

· gender - пол ученика. Бинарный признак, который имеет значения {Female, Male}

· sec - социально-экономический статус студента. Категориальный признак, имеющий значения {'Intermediate', 'Managerial.Professional', 'Semi.Routine.Unemployed', 'Small.Self.employed'}

· hiquamum - максимальный уровень образования, полученный матерью. Категориальный признак, имеющий значения {'Degree or equivalent', 'GCE A Level or equivalent', 'GCSE grades A-C or equiv', 'HE below degree level', 'No qualification', 'Other qualifications'}

· singlepa - бинарный признак, определяющий, единственный ли ребенок в семье, имеющий значения {'no', 'yes'}

· house - бинарный признак, определяющий, состоит ли дом в аренде или в собственности. Имеет значения {'owned', 'rented'}

· fsm - бинарный признак, определяющий, получает ли ребенок дотацию от государства на бесплатное питание, имеющий значения {'no', 'yes'}

· parasp - бинарный признак, определяющий, хотят ли родители, чтобы ребенок продолжил образование. Имеет значения {'No', 'Yes'}

· computer - бинарный признак, определяющий, есть ли компьютер. Имеет значения {'No', 'Yes'}

· tuition - бинарный признак, определяющий, нанимали ли родители репетитора, имеющий значения {'No', 'Yes'}

· pupasp - бинарный признак, определяющий, хочет ли сам ребенок получать высшее образование, имеющий значения {'No', 'Yes'}

· absent - бинарный признак, определяющий, отсутствовал ли ребенок больше месяца за последний год. Имеет значения {'No', 'Yes'}

· homework - категориальный признак, определяющий, сколько ночей в неделю ребенок проводит за учебой. Имеет значения от 0 до 5 часов.

· asc - оценка, отражающая отношение ребенка к школе (чем больше, тем лучше). Является категориальным признаком со значениями {'high', 'low', 'very high', 'very low'}

· sen - бинарный признак, определяющий, нужны ли ребенку особые условия (например, если ученик колясочник, имеет низкое зрение, дислексию и прочее). Имеет значения {'No', 'Yes'}

· truancy - бинарный признак, определяющий, прогуливал ли ученик за последний год. Имеет значения {'No', 'Yes'}

· idaci_n - индекс ухода за ребенком. Определяет, насколько родители следят за ребенком. Имеет непрерывные значения в диапазоне от -4 до 4.

· fsmband - категорiиальный признак, определяющий, какой процент учеников школы получает бесплатное питание. Имеет значения {'13%-21%', '21%-35%', '35%+', '5%-9%', '9%-13%', '<5%'}

2.3 Обоснование выбора среды программирования

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

· Наличие библиотек анализа данных

· Простота использования

· Наличие доступных документаций

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

В связи с первым пунктом, выбор языка, а, соответстенно, и среды программирования свёлся к двум: Python и R. Остальные языки не имели достаточного количества библиотек, чтобы за относительно небольшое время построить необходимую модель. Разумеется, была возможность реализовать необходимые алгоритмы на языках группы C, но двойная работа не является оптимальным путём решения проблемы. Изучив реализацию алгоритмов, сопостояляя с теоретическими аспектами, было принято решение использовать язык программирования Python. Помимо прочего, было найдено необходимое количество информации по лаконичному внедрению соответствующего скрипта в интерфейс программы, в отличие от языка R.

Среди множества библиотек для создания графического интерфейса, были выделены два: Tkinter и Qt Disigner. Первый отличается своей простотой, а второй - удобством использования. Ввиду того, что потенциально установка программного обеспечания для QtDesigner заняла бы больше времени, было принято решение воспользоваться стандартной библиотекой Tkinter.

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

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

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

· SciPy

· XGBoost

· CatBoost

· SciKit learn

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

Выводы

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



Глава 3. Программная реализация оценки успеваемости студентов

3.1 Предобработка данных

Как уже писалось в предыдущей главе, чтобы преступать к обработке данных, для начала нужно выбрать язык и среду программирования. Один из главных критериев выбора языка программирования является наличие в нём соответствующих уже написанных библиотек для работы с данными. Под такой формат подходят всего два - Python или R. Выбор был сделан в пользу Python, ввиду того, что он более адаптивен под графический интерфейс, что будет необходимо в дальнейшем для реализации самой программы. В качестве программной среды было принято решение остановиться на Jupyter Notebook для проведения исследований и построения тестовых моделей (так как используемая тетрадка не требует запуск всего кода целиком, а имеет возможность воспроизводиться выделяемыми кусками) и JetBrains PyCharm для реализации front-end разработки и пользовательского интерфейса.

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