Цепи Маркова

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 - Матрица частот для К состояний процесса

От состояния	К состоянию							Сумма по строке
	S1	S2	S3	…	Si	Sj	Sk
S1	V11	V12	V13		V1i	V1J	V1k	1
S2	V21	V22	V23		V2i	V2J	V2k	1
S3	V31	V32	V33		V3i	V3J	V3k	1
…	…	…	…	…	…	…	…	…
Si	Vi1	Vi2	Vi3		Vii	ViJ	Vik	1
Sj	Vj1	Vj2	Vj3		Vji	VjJ	Vjk	1
Sk	Vk1	Vk2	Vk3		Vki	VkJ	Vkk	1

 

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

 

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

 

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Год набора	1семестр		2семестр		3семестр		4семестр		5семестр		6 семестр
	Качественная  успеваемость, %	Количество неудов, %	Качественная  успеваемость, %	Количество неудов, %	Качественная  успеваемость, %	Количество неудов, %	Качественная  успеваемость, %	Количество неудов, %	Качественная  успеваемость, %	Количество неудов, %	Качественная  успеваемость, %	Количество неудов, %
1996	34,8	25,2	37,5	18,4	37,9	22	33,1	9,1	47,6	12,1	33,1	5,7
1997	22,2	25,7	28,1	20,9	20,8	24,2	31,5	9,9	49,4	20,1	43,9	24,7
1998	22,2	25	31,5	24,4	31,3	26,5	37,3	15,2	52,4	7,1	38,3	19,6
1999	18,3	29,8	24,5	31,4	25,9	34,7	29,5	33,7	40,3	24,7	34,7	23,3
2000	34,3	32,1	26,2	40	29,2	41,5	33,9	25,4	46,6	16,1	47	22,7
2001	20,1	39	28,7	30,1	22	40,4	29,9	13,4	28,3	14,8	40,6	21,3
2002	34,1	30,6	33,5	23,4	39	26,2	45,7	14,8	52,6	14,5	33,3	23,2
2003	18,4	39,5	28,9	31,1	17,4	38,9	24,5	30,1	47,4	24	15,7	46,4
2004	32,2	34,4	36,5	21	41,5	27	46,4	22,9	64,2	47,5	52,7	31,8
2005	25,2	19,5	25,8	20,8	37,8	10,8	20,5	29,5	55,8	21,7	38,4	24
2006	24,7	31,7	34,1	29,6	34,7	26,3	30,3	27,9	58	16	41	26,7
2007	14,2	20,3	22,7	27,6	20,1	40,2	18,3	28,5	48,3	25,6	30,5	33,3
2008	22,5	33,5	28,5	27,8	27,8	35,8	32,5	32,5	42,7	36,7	35	34,3

 

Для визуального представления ежегодного изменения доли неудовлетворительных оценок представим данные таблицы 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 - Интервалы изменения  успеваемости для каждого семестра,%

Семестр	Низкий уровень неудовлетворительных оценок		Средний уровень неудовлетворительных оценок		Высокий уровень неудовлетворительных оценок
	мин	мах	мин	мах	мин	мах
1	19,5	26,2	26,2	32,8	32,8	39,5
2	18,4	25,6	25,6	32,8	32,8	40,0
3	10,8	21,0	21,0	31,3	31,3	41,5
4	9,1	17,3	17,3	25,5	25,5	33,7
5	7,1	20,6	20,6	34,0	34,0	47,5
6	5,7	19,3	19,3	32,8	32,8	46,4