Цепи Маркова

3.1 Марковские  случайные процессы

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

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

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

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

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

Итак, Марковский процесс удобно задавать графом переходов из состояния в состояние.

Рассмотрим два варианта описания Марковских процессов — с дискретным и непрерывным временем.

Случайный процесс называется процессом с дискретными состояниями, если возможны состояния системы  Si, S2, S3... можно перечислить одно за другим, а сам процесс состоит в том, что время от времени система S скачком переходит из одного состояния в другое.

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

Марковские процессы с  дискретными состояниями удобно иллюстрировать с помощью так  называемого графа состояний (рисунок  3.1), где кружками обозначены состояния S₁, S₂, S₃ ... системы S, а стрелками — возможные переходы из состояния в состояние. На графе отмечаются только непосредственные переходы, а не переходы через другие состояния. Возможные задержки в прежнем состоянии изображают «петлей», т. е. стрелкой, направленной из данного состояния в него же. Число состояний системы может быть как конечным, так и бесконечным (но счетным).

а - обычный; б - размеченный

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

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

Переходная матрица Р  образуется следующим образом. Исследуемый  ряд ранжируется в возрастающем порядке и в нём выделяются группы по состояниям: SI, S2, S3 …… Si ……. Sj ........ Sk.

Далее подсчитывают частоты  перехода от состояния к состоянию. Переход от состояния Si к состоянию Sj - это событие Si j, которое может совершиться (произойти) Vi j раз (таблица 3.1)

Таблица 3.1 - Матрица частот для К состояний процесса

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

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

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

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

На основании отчетов  по оценке и анализу результативности процессов СТУ 7.5.1-1.0.-2006 “Осуществление образовательного процесса” и СТУ 7.4.0.-1.0.-2007 “Управление приемом на обучение” был проведен анализ показателей  успеваемости студентов факультета «Автоматической электросвязи».

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

Таблица 3.2 - Результаты первых шести сессий в целом по факультету

Для визуального представления ежегодного изменения доли неудовлетворительных оценок представим данные таблицы 3.2 в виде графиков (рисунок 3.2).

Рисунок 3.3- Изменение доли неудовлетворительных оценок в 4-6 семестрах

Анализ рисунков показал, что студенты факультета испытывают трудности в 3-ем семестре. Исключение составляют:

- доля неудовлетворительных оценок в 6-м семестре, полученных студентами 2003 года набора составляет 46,4% (что на 16,7% выше, чем результаты 3-ей сессии);

- доля неудовлетворительных оценок в 5-м семестре, полученных студентами 2004 года составляет 47,5% (что является абсолютным максимумом по 6-ти сессиям за период наблюдения с 1996 года);

- доля неудовлетворительных оценок в 3-м семестре, полученных студентами 2005 года набора составляет 10,8% (что является минимальной величиной по результатам сдачи 3 -ей сессии за период наблюдения с 1996 года).

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

Далее проведем анализ изменения  доли неудовлетворительных оценок по результатам сдачи 6-ти сессий в пределах каждого потока (рисунок 3.4)

Рисунок 3.4 - Изменение доли неудовлетворительных оценок в пределах одного потока

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

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

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

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

2. Описание методики

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

Из определения матрицы  Р следует, что составляющие её элементы условных стохастических вероятностей перехода представляют состояние системы в какой-то фиксированный момент, отражающий поведение этой системы за определённый промежуток времени.

Введем следующие обозначения:

- высокий уровень неудовлетворительных оценок - В,

- средний - С,

- низкий - Н.

Тогда возможные состояния  успеваемости:

- S1 - высокий уровень неудовлетворительных оценок;

- S2 - средний уровень неудовлетворительных оценок;

- S3 - низкий уровень неудовлетворительных оценок.

Размеченный граф состояний  и переходов представлен на рисунке 3.5

Рисунок 3.5 - Размеченный  граф состояний и переходов.

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

- для каждого семестра (таблица 3.2) найдем максимальное и минимальное значение;

- учитывая, что в работе используем три уровня состояния успеваемости, рассчитаем величину интервала изменения группировочного признака;

- для каждого семестра рассчитываем интервалы изменения признака;

- для каждой пары семестров, с учетом состояния успеваемости,

рассчитываем число переходов;

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

Рассмотрим алгоритм формирования переходных матриц на примере перехода первый-второй семестры.

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

Таблица 3.3 - Интервалы изменения  успеваемости для каждого семестра,%

Рассмотрим алгоритм формирования переходных матриц на примере перехода первый-второй семестры.

Таблица 3.4 - Уровни успеваемости 1-2 семестры

По этим данным составлена таблица частот перехода от одного состояния к другому (таблица 3.5)

Таблица 3.5 – Частоты перехода от одного состояния к другому  

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

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

Таблица 3.6- Матрица переходных вероятностей 1-2 сессия

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

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

Аналогично построим матрицу  переходных вероятностей зависимости  результатов третьей сессии от успеваемости во вторую сессию и результатов четвертой сессии от успеваемости в третью сессию (таблицы 3.7 - 3.8)

Таблица 3.7 - Матрица переходных вероятностей 2-3 сессия

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

Таблица 3.8 - Матрица переходных вероятностей 3-4 сессия

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

Таблица 3.9 - Матрица переходных вероятностей 4-5 сессия

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

Таблица 3.10 - Матрица переходных вероятностей 5-6 сессия

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

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

 Таблица 3.11 - Матрица переходных вероятностей 1-6 сессия

Так, сохранение текущего уровня может оказаться равным:

- 0,5 для высокого уровня;

- 0,8 для среднего уровня;

- 0,25 для низкого уровня неудовлетворительных оценок.

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

Рисунок 3.6 наглядно демонстрирует  данные выводы.

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

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

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

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

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

Таблица 3.12 - Расчет предельного  состояния матрицы переходов 1-2 сессия