РАЗДЕЛ 2
МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ ГРУППИРОВКИ ПО ИНФОРМАЦИОННОМУ КРИТЕРИЮ СВЯЗИ
В предыдущем разделе был предложен эвристический подход к оценке информационной степени связи между изучаемыми дисциплинами. Центральным результатом следует считать возможность классификации выпускников исходя из успеваемости по отдельным, наиболее информативным дисциплинам, индикаторам успеваемости. Таким образом, проблема классификации выпускников высших учебных заведений может быть формализована на языка на языке кластерного анализа.
В настоящем разделе будет предложена и проанализирована математическая модель задачи группировки учебных дисциплин (параметров образовательного процесса) основанная на информационных связях.
2.1. Постановка и решение задачи группировки по информационному критерию связи
Рассмотрим множество дисциплин , (параметров), описывающих учебный процесс, в котором обучается m студентов. В ходе обучения фиксируются значения оценок , причем множества значений каждого из параметров дискретны. Необходимо построить разбиение множества на заданное число подмножеств таких, что степень связи между параметрами внутри каждого из подмножеств максимальна.
Результаты обучения представим в виде матрицы наблюдений . Элемент матрицы - оценка -го студента по -й дисциплине.
Если интерпретировать каждый из параметров как дискретную случайную величину, реализаций которой расположены в -м столбце матрицы наблюдений , то связь между любыми двумя из них , можно оценивать величиной взаимной информации, которая устанавливает, на сколько знание значения одного из параметров уменьшает неопределенность значения другого [37]:
, (2.1)
где - величина, оценивающая неопределенность значения параметра при отсутствии информации о значении ; - неопределенность случайной величины при известном значении параметра .
Оценивая величину неопределенности шенноновской энтропией [39] и пользуясь ее стандартными свойствами [104], получаем следующую формулу для определения величины взаимной информации
, (2.2)
где , - энтропии, а - совместная энтропия случайных величин , .
При этом статистические оценки энтропии вычисляются так:
, (2.3)
, (2.4)
где - количество наблюдений с одним и тем же r-м значение параметра , - количество наблюдений с одной и той t-й парой значений параметров , . Формула (2.2) более удобна для вычислений, по сравнению с выражением (2.1), в которое входит условная энтропия.
Величина взаимной информации обладает следующими свойствами:
а) она симметрична, т. e. в параметре содержится столько же информации о параметре , сколько ее содержится в об :
; (2.5)
б) , причем только в случае статистической независимости параметров и ;
в) имеет место неравенство
. (2.6)
Информация между всеми параметрами множества S определяется выражением
. (2.7)
Здесь - энтропия ; - совместная энтропия параметров , вычисляемая по формуле
, (2.8)
где - количество наблюдений с одним и тем же s-м набором значений параметров .
Утверждение 2.1. Для того чтобы параметры были независимыми, необходимо и достаточно выполнение условия
. (2.9)
Доказательство. Докажем сначала необходимое условие. Пусть параметры , независимы. Это означает, что для любого множества и любого параметра справедливо соотношение , где - условная энтропия параметра по всем элементам множества ?. Отсюда
(2.10)
. . . .. . . . . . . . . . . . . . . .
а так как
, (2.11)
то в случае независимости параметров
, (2.12)
откуда и из выражения (2.7) вытекает выполнение условия (2.9).
Перейдем к доказательству достаточности. Из соотношений (2.9) и (2.7) следует справедливость равенства (2.12). Подставляя в него вместо ее выражение, взятое из формулы (2.11), получаем
(2.13)
Поскольку в силу свойства энтропии каждый член в квадратных скобках неотрицателен, достижение последнего равенства возможно только в случае, когда выполняются соотношении (2.10). Аналогичные рассуждения можно провести для любой перестановки параметров , . Следовательно, любое подмножество множества S состоит из независимых элементов, что влечет за собой независимость всех параметров S. Утверждение доказано.
В процессе доказательства достаточности утверждения 2.1 установлена правомочность следующих положений.
Следствие 2.1. Если , то для любого подмножества множества имеет место равенство
. (2.14)
Следствие 2.2. Если , то для любой пары параметров , ,
. (2.15)
Пусть имеется разбиение множества S. Рассмотрим, как в этом случае распределяются связи между параметрами.
Введем предварительно обозначения:
- совместная энтропия параметров, образующих подмножество ;
- взаимная информация между параметрами, составляющими подмножество ;
- совместная энтропия разбиения;
- взаимная информация между всеми элементами разбиения множества S.
Утверждение 2.2. Если множество S разбито на К подмножеств , то
, (2.16)
Доказательство. В силу соотношения (2.7) имеем
, . (2.17)
Отсюда
. (2.18)
С другой стороны, согласно равенству (2.7)
(2.19)
Следовательно,
(2.20)
Утверждение доказано.
Таким образом, исходная задача отыскания разбиения, максимизирующего степень связи между элементами внутри подмножеств, эквивалентна задаче нахождения разбиения такого, что степень связи между подмножествами минимальна:
. (2.21)
Пусть - множество имен индексов, соответствующих параметров , , а - его подмножества, соответствующие подмножествам , . Обозначим также через - операцию суммирования по всем возможным значениям индексов, входящих во множество . Тогда в соответствии с [105]:
. (2.22)
Пусть и - два разбиения такие, что при и при , где - некоторое подмножество множества .
Утверждение 2.3. Разби