книги2 / 159

испытательный стенд для апробации и отладки программнотехническихрешенийприпроектированииивнедрениисистемаппаратнопрограммного комплекса «Безопасный город»;

предложения по нормативному правовому, организационнометодическому и нормативно-техническому сопровождению мероприятий по построению и развитию аппаратно-программного комплекса «Безопасный город», направленные на практическое применение результатов НИОКР.

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

Важно отметить, что использование методов Байеса (глава 1) при разработке специального программного обеспечения прогнозных ианалитических моделей в дальнейшем позволит интегрировать сценарии реагирования согласно анализируемым угрозам, при которых методами Байеса может обеспечиваться «выборка» оптимального набора действий и может быть приведена вероятностная оценка эффективности принимаемых решений.

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

а) среди природных угроз:

модель для прогнозирования лесных пожаров (глава 2); модель для прогнозирования последствий землетрясений (глава 3);

модельдляпрогнозированиянаводненийвследствиепаводков(глава4); б) среди техногенных угроз:

модель для прогнозирования последствий отключения теплоснабжения (глава 5);

модель для прогнозирования последствий отключения электроснабжения (глава 6);

модель для прогнозирования последствий разлива нефти и нефтепродуктов (глава 7);

модель для прогнозирования последствий сброса жидких технологических отходов в гидросферу (глава 8);

21

модель для прогнозирования последствий выброса опасных химических веществ в окружающую среду (глава 9);

в) среди биолого-социальных угроз:

модель для прогнозирования последствий массовых заболеваний людей (глава 10).

22

Глава 1.

Типовая прогнозная и аналитическая модель с использованием

метода Байеса

1.1. Метод Байеса и байесовские сети

Метод Байеса —статистический метод, использующий теорему Байеса для вычисления и обновления вероятностей после получения новых данных [7].

Теорема Байеса (или формула Байеса)—одна из основных теорем элементарной теории вероятностей, которая позволяет определить вероятность события при условии, что произошло другое статистически взаимозависимое сним событие. По формуле Байеса можно более точно пересчитать вероятность, взяв в расчет как ранее известную информацию, так и данные новых наблюдений. Особенность теоремы Байеса заключается в том, что для ее практического применения требуется большое количество расчетов, вычислений, поэтому байесовские оценки стали активно использовать только после революции в компьютерных и сетевых технологиях [8].

Формула Байеса позволяет «переставить причину и следствие»: по известному факту события вычислить вероятность того, что оно было вызвано данной причиной. При этом необходимо понимать, что для применения теоремы причинно-следственная связь междуAи B не является обязательной. События, отражающие действие «причин», в данном случае называют гипотезами, так как они—предполагаемые события, повлекшие данное. Безусловную вероятность справедливости гипотезы называют априорной (насколько вероятна причина вообще), аусловную—с учетом факта произошедшего события—апостериорной (насколько вероятной оказалась причина с учетом данных о событии).

Байесовская сеть—это графовая вероятностная модель, представляющая собой множество переменных и их вероятностных зависимостей по Байесу. Математический аппарат байесовских сетей был создан американским ученым Дж. Перлом [9]. Формально, байесовская сеть—это

23

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

1.2. Формализованное описание решаемой задачи

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

Байесовский классификатор—широкий класс алгоритмов классификации, основанный на принципе максимума апостериорной вероятности. Дляклассифицируемогообъектарассчитываются функции правдоподобия каждого из классов, по ним вычисляются апостериорные вероятности классов. Объект относится к тому классу, для которого апостериорная вероятность максимальна.

Вероятностная постановка задачи

Пусть X —множество описаний объектов, Y —конечное множество имен классов. Предполагается, что множество пар «объект, класс» X × Y является вероятностным пространством с плотностью распреде-

ления p(x, y) = P(y)p(x│y).

Имеется конечная обучающая выборка независимых наблюдений Xm = {(x1, y1), …, (xm, ym)}, полученных согласно плотности распределе-

ния p(x, y).

24

Требуется построить алгоритм классификации α: X → Y, которой способен отнести произвольный объект x X к классу y Y.

Задача классификации сводится к следующим подзадачам:

1.Восстановление плотностей классов по обучающей выборке.

2.Построение оптимального классификатора при известных плотностях классов.

Восстановление плотностей классов по обучающей выборке

По заданной обучающей выборке независимых наблюдений Xm = {(x1, y1), …, (xm, ym)}, полученных из неизвестного распределения p(x,y) =Py py(x), построить эмпирические оценки априорных вероятностей Py = P(y) того, что появится объект классаy, иплотностей распределения каждого из классов (функций правдоподобия классов) py(x) = p(x│y).

Построение оптимального классификатора при известных плотностях классов

Пусть для каждого класса y известна априорная вероятность Py и известны плотности распределения каждого из классов (функции правдоподобия классов) py(x).

Требуется построить алгоритм классификации a(x), доставляющий минимальное значение функционалу среднего риска, определяемого как математическое ожидание ошибки:

R a y Py P( x, y){a x s | y)},	(1)
y Y s Y

где λy —величина потерь за отнесение объекта класса y к классу s.

Решением указанной задачи при известных априорных вероятностях Py и функциях правдоподобия классов py(x) является алгоритм:

a x arg max		P p	y	(x) arg max P(y | x).		(2)
yε Y	y	y		y Yε	y

25

1.3.Генерация топологии байесовской сети

Воснове вероятностного вывода байесовской сети лежит теорема Байеса, в соответствии с которой:

	P H|e	P e|H P H	,	(3)
		P e

где:

H —гипотеза;

e —свидетельство;

P(H│e)—апостериорная вероятность; P(H)—априорная вероятность.

В соответствии с теоремой Байеса, степень доверия, которую мы можем присвоить гипотезе H при наступлении свидетельства e, может быть рассчитана путем умножения предыдущей степени доверия P(H) к гипотезе H на правдоподобие P(e│H), означающее наступление свидетельства e при условии, что гипотеза H истинна.

Под графом понимается параG =<V,B>, гдеV —множество вершин графа, V = {Vi}, i = 1, 2, …, n; B —множество связей, B = {Bj}, j = 1, 2, …, k. Каждая связь представляет собой пару вершин вида Bj = <VsVp>, где Vs, Vp V, а для графа без петель Vs ≠ Vp.

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

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

После построения граф байесовской сети проверяется на наличие двух свойств:

1)в графе отсутствуют ориентированные циклы;

2)множество значений любой случайной переменной-вершины

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

26

Если эти свойства выполняются, то построение графа завершается. В противном случае граф корректируется до тех пор, пока свойства 1) и

2)не окажутся истинными.

ВПАМ используется эвристический метод построения байесовских

сетей.

Входные данные.

Множество обучающих данных D = {d1, …, dn}, di = {x1i x2i…x(N)i}, где: нижний индекс —номер наблюдения; верхний индекс —номер переменной); n —количество наблюдений; N —количество вершин (входных и выходных параметров).

1. Первый этап.

Для всех пар вершин вычисляют значения обоюдной информации MI(xi, xj) по следующей зависимости:

i

j

i

j

P(xi , x j )

MI x

, x

P(x

, x

) log(

).

(4)

i

)P(x

j

)

xi , x j

P(x

Значение обоюдной информации—это оценка количества информации, содержащейся в переменной xi о переменной xj.

При MI(x i, x j) = 0 переменные x i и xj полностью независимы друг от друга.

После этого осуществляется упорядочивание элементов множества MI по убыванию:

MI MI xm1 , xm2 , MI xm3 , xm4 , MI xm5 , xm6 , .

(5)

2. Второй этап.

1 шаг. Из множества значений обоюдной информации MI осуществляется выбор первых двух максимальных значений MI(xm1, xm2) и

MI(xm3, xm4).

По полученным значениям MI(xm1, xm2) и MI(xm3, xm4) строится множество моделей G вида:

27

{(m1 → m2; m3 → m4), (m1 → m2; m3 ← m4), (m1 ← m2; m3 ← m4), (m1 ← m2; m3 → m4), (m1 ← m2; m3 не зависит от m4),

(m1 → m2; m3 не зависит от m4),(m1 не зависит от m2; m3 → m4), (m1 не зависит от m2; m3 ← m4),

(m1 не зависит от m2; m3 не зависит от m4)}.

Запись вида mi → mj означает, что вершина xmi является предком

вершины xmj.

2 шаг. Среди всех моделей множества G осуществляется перебор всех возможных нециклических сетевых структур. Вg* сохраняется оптимальная сетевая структура, у которой наименьшее значение функции L(g, xn)—описание минимальной длины (ОМД) при заданной последовательности из n наблюдений xn = d1d2…dn.

В общем виде определение ОМД осуществляется следующим образом.

Входные данные.

Множество обучающих данныхD = {d1, …,dn}, di = {x1i x2i…x (N)i}, где: нижний индекс—номер наблюдения; верхний индекс—номер переменной); n —количество наблюдений, состоит из N(N ≥ 2) переменных

X (1), X (2), …, X (N).

Каждая j-я переменная (j = 1, …, N) имеет A(j) = {0,1, …, a(j) –1} (a(j) > 2) состояний.

Каждая структура g (E) G представляется N множествами предков (П(1), …, П(N)), то есть для каждой вершиныj = 1, …, N, П(j) —множество

родительских вершин, такое что:
П( j ) {X 1 , , X N } \{X j }.	(6)

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

ОМД структуры g G при заданной последовательности из n наблюдений xn = d1d2… dn вычисляется по формуле:

L g, xn H g, xn	k(g)	log n ,	(7)
2

где:

k(g)—количество независимых условных вероятностей в сетевой структуре g;

28

H(g, xn)—эмпирическая энтропия, определяемая по формуле:

H g, xn H ( j, g, xn );			(8)
j J
k g k( j, g),			(9)
j J
где ОМД j-й вершины вычисляется по формуле:
L j, g, xn H j, g, xn	k( j, g)	log n .	(10)
2
Количество независимых условных вероятностейk(j,g)j-й вершины
определяется по формуле:
k j, g a j 1 a k ,			(11)
	k j

где θ(j) (cc) {1, …, j – 1, j + 1, …, N}—это такое множество, что П(j) = = {X(k): k (E) θ(j)}.

Эмпирическая энтропия j-й вершины вычисляется по формуле:

H j, g, xn n[q, s, j, g] log			n[q, s, j, g]	,	(12)
	s S ( j, g )q A( j )		n[s, j, g]
где:
	n
	n(s, j, g) I ( i j s),				(13)
	i 1
	n
n(q, s, j, g) I (xi q, i j		s),			(14)
	i 1
где:	= П( j) означает X ( k ) x( k ) , k j .
π( j)
i

Функция I(E) = 1, когда предикат E = true, в противном случае

I(E) = 0.

Для (0–2), если L(g, xn) < L(g*, xn), то тогда g*← g.

29

3. Третий этап.

После нахождения оптимальной структуры (структур) g* из G, из множества значений обоюдной информации MI выбирают следующее максимальное MI(x i_next, x j_next).

По полученному значению MI(x i_next, x j_next) и структуре (структурам) g* строится множество моделей G вида: {(g*; i_next → j_next), (g*; i_next ← j_next), (g*; i_next не зависит от j_next)}.

После этого осуществляется переход к 2 шагу этапа 2. Указанный цикл повторяется до тех пор, пока не будет проанали-

зировано определенное число элементов множества или все N(N – 1)/2 элементы множества MI.

Выходные данные—оптимальная структура (структуры) g*.

1.4.Определение априорных условных

имаргинальных вероятностных распределений

Для каждой переменной V, не имеющей родителей вграфе G, определяется вероятностное распределение над множеством ее значений (таблица безусловных вероятностей) на основе статистической информации об этой переменной (например, вероятностное распределение уже известно либо имеется информация о частотах выпадения тех или иных значений переменнойV), апри отсутствии такой информации—на основе мнения эксперта (задаются субъективные вероятности—степени доверия).

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

P(v)	Nv	,	(15)
где:	N

v —одно из значений переменной V;

Nv —число исходов, при которых наблюдалось событие {V = v}; N —общее число исходов.

30