Математические методы и ЭВМ в историко-типологических исследованиях -
ISBN 5-02-009481-1
Скачать (прямая ссылка):
4 Сымонович Э. А., Кравченко Н. М. Указ. соч.
5 Там же. С. 72—117.
6 Там же С. 19.
7 Там же С. 14.
8 Айвазян С. А. и др. Указ. соч. С. 82.
9 Сымонович Э. А., Кравченко Н. М. Указ. соч. С. 19.
10 Никитина Г. Ф. Систематика погребального обряда племен Черняховской культуры. M., 1985.
9 Зак. № 2235
241 ПРИЛОЖЕНИЕ 1
ВЫВОД ФОРМУЛЫ РАСЧЕТА «УБЕДИТЕЛЬНОСТИ» КЛАССИФИКАЦИИ
Оценим вероятность получения классификации за счет чисто случайных причин. Допустим, что все объекты представляют собой выборку из однородной генеральной совокупности, а вероятность наличия у г'-го объекта /-го признака одинакова для всех объектов и не зависит от наличия или отсутствия других признаков. Обозначим эту вероятность Pj. Нетрудно видеть, что получение исследуемой классификации при этих предположениях обусловливается чисто случайными причинами. Определим вероятность такого события.
Дальнейшее изложение ведется для случая выделения двух классов, однако все подходы к оценке классификации и алгоритмам ее построения, приводимые здесь и во всех остальных Приложениях, могут быть получены для произвольного заранее заданного числа классов. Введем следующие обозначения: m.k — число объектов k-ro класса (k = l, 2); то — число переходных форм; Jk — множество номеров характеристических признаков k-й группы.
Пусть вероятность того, что объект не обладает ни одним признаком k-й группы, есть Pk. Тогда, очевидно,
Pk= П (1-P1). (III)
Вероятность того, что среди т исследуемых объектов найдется т і таких, что они обладают хотя бы одним признаком из Ji и не обладают ни одним из Jq, есть, согласно схеме Бернулли,
Rl = CT(P2Ql)mXl-P2Qifm', где Q1 = I-Pk.
Применяя ту же схему и формулу Байеса, оценим вероятность выбрать из оставшихся т — т і объектов ровно /лг таких, что они обладают хотя бы одним признаком из J2 и ни одним из /f.
• jr> ГШ (Pi<3i)m'(PiPi+Qi9i)"" R'-c-!— ^Г^г •
Отсюда искомая вероятность получения оцениваемой классификации в принятых предположениях Pj есть
р = molmLl (p^mXP1Q2)mXP1P2+ Q.Q,Г.
Оценкой максимального правдоподобия для Pj, входящих в формулу (III), является тj/m, где т,- — число объектов, обладающих у'-м признаком. Таким образом,
т — % і
Pk= П
/є/*
ПРИЛОЖЕНИЕ 2
ВВЕДЕНИЕ КРИТЕРИЕВ «ПРИЗНАННОЙ» И «ОБЩЕЙ» ИНФОРМАТИВНОСТИ КЛАССИФИКАЦИЙ
А. Признанная информативность
Положим энтропию, связанную с /-м признаком до проведения классификации, равной энтропии т независимых испытаний схемы Бернулли с вероятностью успеха, равной частоте наблюдения /-го признака на всей совокупности:
242 и / 1Z 1 т/ I —lZi —I/ N
Я/ = —/п(—In—H---In--).
mm т т
После проведения классификации энтропия, связанная с /-м признаком, уменьшается. Если признак отнесен к k-й группе, то на объектах других групп его энтропия равна нулю, так как по построению этот признак отсутствует у всех объектов, ВХОДЯЩИХ В 1-Ю группу при 1фк. Для k-й группы его энтропия есть
Hf= mk+Tik In mk~Tik),
mk mk mt mk
где Tjk — число объектов k-й группы, обладающих у'-м признаком, a mk — общее число объектов k-й группы. При k = О эта формула показывает энтропию у'-го признака на неклассифицированных объектах, т. е. переходных формах. Таким образом, снижение информативности по признаку, отнесенному к k-й группе, есть
Ij = Hi-Hf-Hl
Если в результате классификации /-й признак отнесен к общим, то положим Ij = O. Призначная информативность равна сумме снижения энтропии по всем признакам:
/=Z/у.
і
Б. Общая информативность
Положим энтропию, связанную с матрицей А до проведения классификации равной
• , т . т тп — т. тп — т. „
H(A) = —тп(-In----In-), т = У/Т/,
тп тп тп тп ' ^ '
или, если обозначить через р(А) долю единичных элементов («плотность» матрицы А),
H(A) =/тш(р(А)1пр(А) -}-(1-р(А)In (1— р(А)).
В результате классификации матрица разбивается на блоки Ab..As, A0, B0 (см. (I)), вне которых находятся только нулевые элементы, и поэтому энтропия вне этих блоков равна нулю. Вычислим энтропию каждого блока:
H(Ak) = -mknk( p(A*)lnp(A*)+(l -р(А*)1п(1 -р(А*)),
где mk и Пк — число строк и столбцов в k-м блоке; разность
S
I = H(A)- I H(Ak) H(B0) k = 0
показывает снижение энтропии в результате классификации и определяет ее общую информативность.
ПРИЛОЖЕНИЕ 3
АЛГОРИТМЫ «ВЕТВЕЙ И ГРАНИЦ» ДЛЯ ПОСТРОЕНИЯ КЛАССИФИКАЦИЙ, ОПТИМАЛЬНЫХ ПО ИНФОРМАТИВНОСТИ
Введем двудольный граф G = (X, Y), соответствующий матрице А: множество X соответствует множеству строк матрицы А; У — множеству столбцов. Наличие дуги (Xi, Yj), соединяющей вершины Xi^X и Yiе Y, соответствует наличию ненулевого элемента ац в матрице А. Классификация (при S = 2) задает разбиение A(G) вершин графа на три множества: в G1 входят строки и столбцы, относящиеся к первой группе, в G2 — ко второй, G3 содержит вершины графа, отвечающие окаймляющим строкам и столбцам матрицы А.
9*
243 Для подграфа G,<=G обозначим через Ai = (G), Gf, Gf) его разбиение, а через Я1 и Я2 — значение «призначной» и общей энтропии на матрице, соответствующей подграфу G1 и разбиению A1. Можно показать, что если G1c=G,-, то Я/^Я) и Я?< Hf.
