Сравнительный анализ методов оценки взаимосвязи между вершинами при построении байесовских сетей
Проаналізовано методи оцінки взаємозв’язку між вершинами при побудові мереж Байєса з використанням евристичного алгоритму. Наведено теоретичне обґрунтування методів, розглянуто результати їх практичного використання при побудові класичних мереж, а також описано алгоритм проведення експериментів на о...
Saved in:
| Published in: | Проблемы управления и информатики |
|---|---|
| Date: | 2010 |
| Main Authors: | , , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/210848 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Сравнительный анализ методов оценки взаимосвязи между вершинами при построении байесовских сетей / П.И. Бидюк, В.И. Давиденко, Д.В. Трофименко, А.Н. Терентьев // Проблемы управления и информатики. — 2010. — № 6. — С. 64-73. — Бібліогр.: 12 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859575332431986688 |
|---|---|
| author | Бидюк, П.И. Давиденко, В.И. Трофименко, Д.В. Терентьев, А.Н. |
| author_facet | Бидюк, П.И. Давиденко, В.И. Трофименко, Д.В. Терентьев, А.Н. |
| citation_txt | Сравнительный анализ методов оценки взаимосвязи между вершинами при построении байесовских сетей / П.И. Бидюк, В.И. Давиденко, Д.В. Трофименко, А.Н. Терентьев // Проблемы управления и информатики. — 2010. — № 6. — С. 64-73. — Бібліогр.: 12 назв. — рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Проаналізовано методи оцінки взаємозв’язку між вершинами при побудові мереж Байєса з використанням евристичного алгоритму. Наведено теоретичне обґрунтування методів, розглянуто результати їх практичного використання при побудові класичних мереж, а також описано алгоритм проведення експериментів на основі псевдовипадкового генерування байєсових мереж. Отримані для кожного методу результати порівнювались. Зроблено висновки про можливість застосування розглянутих методів оцінки взаємозв’язку між вершинами при побудові байєсових мереж.
The estimation methods of nodes interrelation in Bayesian networks construction using heuristic algorithm are analysed. Theoretical justification of methods is given, results of practical use in construction of classic networks are considered and experiments implementation algorithm based on pseudorandom generation of Bayesian networks is described. Comparison of received results for each method is performed and conclusions are drawn about possibility of using the considered estimation methods of nodes correlation in Bayesian networks construction.
|
| first_indexed | 2026-03-13T19:13:53Z |
| format | Article |
| fulltext |
© П.И. БИДЮК, В.И. ДАВИДЕНКО, Д.В. ТРОФИМЕНКО, А.Н. ТЕРЕНТЬЕВ, 2010
64 ISSN 0572-2691
МЕТОДЫ ОБРАБОТКИ ИНФОРМАЦИИ
УДК 62-50
П.И. Бидюк, В.И. Давиденко, Д.В. Трофименко, А.Н. Терентьев
СРАВНИТЕЛЬНЫЙ АНАЛИЗ МЕТОДОВ
ОЦЕНКИ ВЗАИМОСВЯЗИ МЕЖДУ ВЕРШИНАМИ
ПРИ ПОСТРОЕНИИ БАЙЕСОВСКИХ СЕТЕЙ
Введение
Развитие и всестороннее применение вычислительной техники приводит
к широкому использованию средств цифровой обработки данных почти во всех
сферах деятельности человека. Полученная информация не может использоваться
в исходном виде и требует некоторой обработки. Именно поэтому популярны ме-
тоды интеллектуального анализа данных (data mining), которые позволяют нахо-
дить закономерности в данных, описывающих процессы различной природы.
Одной из технологий интеллектуального анализа данных являются байесовские
сети (БС) (Bayesian networks). Они дают возможность определять причинно-
следственные связи между факторами и получать вероятности возникновения той
или иной ситуации при изменении состояния любого узла сети.
Методика построения БС состоит из двух основных задач: построение опти-
мальной топологии БС, т.е. нахождение направленного ациклического графа, ко-
торый лучше всего соответствует эмпирическим обучающим данным; вычисление
значений таблиц условных вероятностей для всех вершин этого графа.
1. Постановка задачи
Данная статья посвящена сравнительному анализу методов оценки взаимо-
связи между вершинами при нахождении оптимальной структуры БС с использо-
ванием эвристического алгоритма.
Эвристический алгоритм построения БС [1] заключается в следующем:
1) построение упорядоченного множества вершин;
2) выполнение целенаправленного поиска с использованием оценочной функ-
ции на основе принципа описания минимальной длины;
3) повторение итераций до получения структуры сети заданного качества.
В данном алгоритме построение упорядоченного множества вершин — один
из ключевых моментов, поскольку наличие такого множества существенно
сокращает пространство возможных нециклических структур. Однако в этом
случае появляется новая нетривиальная задача: как по множеству обучающих
данных получить упорядоченное множество вершин сети. Самый очевидный
способ — привлечение экспертов. Однако может возникнуть необходимость
моделирования данных такой предметной области, в которой квалифицирован-
ных экспертов нет. Именно поэтому актуальна задача автоматического построе-
ния упорядоченного множества вершин и, как следствие, выбора эффективного
метода оценивания степени зависимости между факторами или произвольными
случайными переменными.
Международный научно-технический журнал
«Проблемы управления и информатики», 2010, № 6 65
2. Методы оценки взаимосвязи между факторами
Рассматриваются следующие методы оценивания: меры на основании стати-
стики 2 -квадрат (коэффициенты Пирсона, Крамера, Чупрова), значение обоюд-
ной информации и коэффициент Гудмана.
Коэффициенты связи, основанные на статистике 2. Поскольку крите-
рий 2 служит основой для проверки независимости, стоит рассмотреть возмож-
ность использования значений 2 как меру связи.
При рассмотрении коэффициентов связи, основанных на значении ,2 исхо-
дим из предпосылки о том, что чем больше объем выборки N, тем легче получить
статистически значимую величину критерия даже при очень слабой взаимосвязи
переменных (т.е. при больших объемах выборки даже слабые связи будут стати-
стически значимыми) [2]. Чтобы элиминировать влияние объема выборки N,
К. Пирсон предложил в качестве меры связи коэффициент среднеквадратической
сопряженности:
.
2
2
N
Значения 2 рассчитываются на основе таблицы частот взаимного сопряже-
ния переменных )1(X и )2(X (когда переменные сети имеют произвольное число
состояний m и n соответственно):
,1
1 1
11
2
m
i
n
j
n
j
ji
m
i
ji
ji
kk
k
N .nmN
В табл. 1 приведены значения частот взаимного сопряжения переменных
)1(X и ,)2(X где )( p
qx — q-е состояние p-й переменной; jik — частота взаимного
сопряжения j-го состояния переменной )1(X с i-м состоянием переменной .)2(X
Таблица 1
Переменные
)1(
1
)1( xX … )1()1(
nxX Сумма
)2(
1
)2( xX 11k … 1nk
n
j
jk
1
1
… … … … …
)2()2(
mxX mk1
… nmk
n
j
jmk
1
Сумма
m
i
ik
1
1
…
m
i
nik
1
m
i
n
j
jik
1 1
Стремясь нормировать меру связи к единому диапазону, С. Крамер видоиз-
менил формулу коэффициента среднеквадратической сопряженности для своего
коэффициента Крамера [3]: .
)1,1(min
2
2
mn
V
66 ISSN 0572-2691
А. Чупров [2] предложил похожую формулу — полихорический коэффици-
ент сопряженности (polychoric correlation coefficient) — коэффициент Чупрова:
.
)1)(1(
2
2
mn
T
Нетрудно заметить, что 2T и 2V эквивалентны, когда число столбцов равно
числу строк, в иных случаях 2V всегда больше .2T Для таблицы сопряженности
22 обе меры равны .2
Коэффициент контингенции Пирсона [4] имеет вид: .
1 2
2
2
C
Перечисленные коэффициенты, основанные на ,2 принимают область до-
пустимых значений от нуля до единицы. Значение ноль говорит о том, что пе-
ременные независимы, а единица означает, что значение одной переменной
можно точно спрогнозировать по другой, т.е. случай полной линейной зави-
симости.
Информационный подход к оценке связи. Традиционные меры связи, ос-
нованные на ,2 представляют собой сугубо эвристические конструкции. Но
интерпретация и математико-статистическое обоснование не являются совершен-
ными. Поэтому стоит также рассмотреть оценки мер связи, в основе которых
лежит теоретически-информационный подход к анализу таблиц частот.
Современная трактовка статистической связи между переменными A и B сво-
дится к оценке количества информации:
),()(),( ABHBHBAI
которое устраняет неопределенность того, какое значение примет B, если извест-
но значение A. Таким образом, мера сопряженности оценивается как доля сопря-
женного разнообразия величины B, включенной в систему ),,( BA по сравнению
с разнообразием (энтропией) B, рассматриваемой отдельно:
).(/),(| BHBAIR AB
Практическая трудность построения мер, относящихся к этому семейству, за-
ключается в сложности выбора конкретных дефиниций и формальных выражений
понятий «неопределенность» и «информация» из множества возможных
Л. Гудман и В. Крускал (L. Goodman, W. Kruscal) в своем принципе пропор-
циональной предикации [5] выразили мнение, что мерой связи должно служить
относительное уменьшение вероятности ошибки предсказания значения зависи-
мого признака по значению независимого. Если в рамках этой концепции оцени-
вать относительную ошибку, используя отношения правдоподобия и минимиза-
цию числа ошибочных предсказаний, получим меру связи, известную как коэф-
фициент Гудмана:
,
max1
maxmax |
|
j
j
j
ji
ij
j
i
AB
p
ppp
Международный научно-технический журнал
«Проблемы управления и информатики», 2010, № 6 67
где
j
jp max — вероятность, соответствующая модальной категории маргиналь-
ного распределения B;
j
ijp |max — вероятность модального значения B при i-м
значении A.
Значения лежат в пределах от 0 до 1: ноль означает невозможность пред-
сказания зависимого признака, а 1 означает, что по значению независимого при-
знака можно уверенно предсказать значение зависимого признака. Необходимо
отметить, что нулевое значение эквивалентно не состоянию статистической не-
зависимости, а тождеству модальных категорий переменных A и B.
Кроме несимметричных мер в [2] предложен симметричный коэффициент
Гудмана:
.
2maxmax1
2maxmaxmaxmax
/
/||
,
j
j
i
i
i
i
ji
i
j
j
j
j
ij
j
i
i
BA
pp
pppppp
Значение обоюдной информации (ЗОИ). Для оценки степени зависимости
двух произвольных переменных ix и jx в работе [6] Шоу и Лью в 1968 г. впервые
предложили использовать значение обоюдной информации (mutual information)
).,( jxxMI i
Для расчета они предложили следующее выражение:
,
)()(
),(
log),().,(
,
ji
ji
ji
xx
ji
xPxP
xxP
xxPxxMI
ji
где ),( ji xxP — значение совместной вероятности между ix и ,jx )( ixP
и )( jxP — значения вероятностей )( jxP соответственно.
По своей сути значение обоюдной информации — аналог корреляции, но по
своему содержанию это оценка количества информации о переменной ,jx со-
держащейся в переменной .ix Данный показатель измеряет, насколько знание
одной переменной уменьшает неопределенность другой. ЗОИ принимает неотри-
цательные значения .0),( j xxMI i
Если вершины ix и jx полностью незави-
симы одна от другой, ,0),( j xxMI i
так как ),()(),( jiji xPxPxxP следо-
вательно,
.0)1(log
)()(
)()(
log
)()(
),(
log
ji
ji
ji
ji
xPxP
xPxP
xPxP
xxP
3. Оценивание качества построения байесовских сетей
При проведении вычислительных экспериментов для оценивания качества
построения БС используется число лишних, отсутствующих и реверсивных дуг в
полученной БС сравнительно с оригинальной БС, а также структурная разница
или перекрестная энтропия между полученной и оригинальной БС.
Структурная разница. Для вычисления структурной разницы используют
формулу симметричной разницы структур [7]:
68 ISSN 0572-2691
))(Δ)((card )()(
11
AB ii
n
i
i
n
i
))),(\)(())(\)(((card )()()()(
1
BAAB iiii
n
i
где B — полученная БС; A — оригинальная БС; n — количество вершин сети;
)()( Bi — множество предков i-й вершины, полученной B; )()( Ai — мно-
жество предков i-й вершины оригинальной сети A; )(card — мощность конечно-
го множества , которое определяется как количество элементов, принадлежа-
щих множеству .
Перекрестная энтропия. Перекрестная энтропия — это расстояние между рас-
пределением построенной и оригинальной БС [8]. Пусть )(vp — совместное рас-
пределение оригинальной БС, )(vq — совместное распределение построенной БС.
Тогда перекрестная энтропия вычисляется так:
)(
)(
log)(),(
vq
vp
vpqpH
v
.
)(
)(
log)(
)()(
)()(
)()(
),( )( saXq
saXp
saXp
jj
jj
jj
AagjSsJj j
Интегральный показатель. Для оценивания качества построения БС разра-
ботан и реализован интегральный показатель, который учитывает число лишних,
отсутствующих и реверсивных дуг в построенной БС при сравнении с оригиналь-
ной БС.
Интегральный показатель вычисляется по формуле
,5,0 dirdeladd MMMR
где addM — количество добавленных связей; delM — количество удаленных
связей; dirM — количество связей с измененным направлением (в формуле
этот показатель имеет коэффициент 0,5, который указывает на меньшую кри-
тичность измененного направления по сравнению с отсутствием дуги или
наличием лишних).
4. Описание вычислительных экспериментов
Цель экспериментов — сравнение эффективности использования разных
метрик при построении БС эвристическим методом. Для проведения эксперимен-
тов применялось два метода: генерирование случайным образом выборки по за-
данной структуре исходной сети и непосредственное применение метрик при по-
строении БС по реальным эмпирическим данным. Также в рамках данных экспе-
риментов исследовались возможности использования способа псевдослучайной
генерации сетей для поиска взаимосвязей между размером выборки, количеством
вершин в сети, количеством состояний в каждой вершине и качеством восстанов-
ления сети.
Классические БС. Первый эксперимент заключался в использовании разных
методов оценки взаимосвязи между вершинами при построении БС по реальным
эмпирическим данным.
Международный научно-технический журнал
«Проблемы управления и информатики», 2010, № 6 69
Рассматривались следующие сети: Asia, CarStarts и Alarm. Они представляют
собой классические байесовские сети и используются исследователями для тести-
рования новых и существующих алгоритмов построения сетей. Данные сети вхо-
дят в стандартный набор примеров почти всех более-менее известных программ-
ных продуктов для работы с БС.
Сеть Asia состоит из 8 вершин и 8 дуг. Размер выборки 7200 обучающих
записей.
Сеть Car Starts имеет 18 вершин и 17 дуг. Размер выборки 10 тыс. обучающих
записей.
Сеть Alarm имеет 37 вершин и 46 дуг. Размер выборки 10 тыс. обучаю-
щих записей (выборка сгенерирована).
Значения разных метрик оценки взаимосвязи между вершинами при постро-
ении данных сетей приведены в табл. 2.
Таблица 2
Сеть Метрики addM
delM
dirM R
Car
Starts
ЗОИ 1 2 3 4,5 9
Метрика Пирсона 1 2 3 4,5 9
Метрика Чупрова 1 2 3 4,5 9
Метрика Крамера 1 2 3 4,5 9
Метрика Гудмана 1 2 3 4,5 9
Asia
ЗОИ 0 0 3 1,5 6
Метрика Пирсона 0 0 3 1,5 6
Метрика Чупрова 0 0 3 1,5 6
Метрика Крамера 0 0 3 1,5 6
Метрика Гудмана 0 1 3 2,5 7
Alarm
ЗОИ 12 2 22 25 58
Метрика Пирсона 12 2 13 20,5 40
Метрика Чупрова 14 3 14 24 45
Метрика Крамера 15 2 13 23,5 43
Метрика Гудмана 16 3 16 27 51
Псевдослучайная генерация байесовской сети . Второй эксперимент
заключался в генерировании по заданной структуре исходной сети псевдослучай-
ным образом.
Эксперимент можно разделить на четыре этапа:
1) генерация сети случайным образом;
2) генерация выборки;
3) построение структуры сети по выборке;
4) сравнение исходной и восстановленной сетей.
Генерация сети случайным образом. Для того чтобы исключить изолирован-
ные вершины, первым этапом было объединение всех вершин в цепь. При этом
направление дуги выбирается случайным образом. Количество связей, построен-
ных таким образом, равно .1N
Оставшиеся 1 NM связей строятся путем выбора случайным образом
родительской и дочерней вершин. При добавлении связи осуществляется провер-
ка на цикличность. Если новая связь образует цикл, то она отбрасывается и изби-
раются новые родительская и дочерняя вершины.
70 ISSN 0572-2691
Таблицы условных вероятностей задаются путем заполнения их случайными
числами в диапазоне от 0 до 1 со следующей нормализацией (приведение суммы
вероятностей по строке до 1).
Генерация выборки. Генерация выборки происходит следующим образом.
Сначала делается вероятностный вывод в сети без инстанциированных вершин
),( ijSP ;...,,1 Ni ,...,,1 Sj затем выбирается вершина i
N и инстанциирует-
ся одно из ее состояний ji
S с вероятностью этого состояния ).( ji
SP Пере-
считываются вероятности состояний вершин после инстанциирования
).( jiiij SSSP Далее выбирается следующая вершина. Эта операция повторя-
ется пока не останется неинстанциированных вершин. Инстанциированные состоя-
ния образуют запись в выборке ),...,,(
1 Nii SS )....,,1( Sik Алгоритм повторяется
до тех пор, пока не будет создано необходимое количества записей V в выборке.
Построение структуры сети по выборке. На основе полученной выборки
строится сеть с использованием выбранных метрик.
Сравнение исходной и восстановленной сетей. Вычисляются показатели, ха-
рактеризующие отличия восстановленной сети от исходной, а также оценивается
качество восстановления.
Проведение эксперимента: количество вершин (N): 10, количество свя-
зей (M) : 15, количество состояний вершины (S) : 2, размер выборки (V) : 1000,
количество итераций (I) : 100.
Для уменьшения статистической ошибки эксперимент был повторен I раз для
каждой метрики и были найдены средние значения показателей (табл. 3):
,,
,1
add
add
,1
I
M
M
I
R
R
Ii
i
Ii
i
,,,
,1,1
dir
dir
,1
del
del
II
M
M
I
M
M
Ii
i
Ii
i
Ii
i
где ,iR ,addiM ,deliM ,diriM i — значения показателей на i-й итерации.
Таблица 3
Метрики addM
delM
dirM R
ЗОИ 0,96 4,4 4,13 7,425 13,62
Метрика Пирсона 0,97 4,41 4,12 7,44 13,62
Метрика Чупрова 0,97 4,41 4,12 7,44 13,62
Метрика Крамера 0,97 4,41 4,12 7,44 13,62
Метрика Гудмана 1,15 6,25 3,51 9,155 14,42
Связь между параметрами байесовской сети и качеством ее восстанов-
ления. Цель эксперимента — определить характер зависимости качества восста-
новления сети от размера выборки. Для этого генерировалась сеть с заданными
параметрами (количество узлов, связей, состояний). На основании этой сети гене-
рировались выборки различного объема. С помощью сгенерированных данных
с использованием эвристического алгоритма с метрикой в виде обоюдной инфор-
мации сеть была восстановлена. Качество восстановления оценивалось инте-
Международный научно-технический журнал
«Проблемы управления и информатики», 2010, № 6 71
гральным показателем. Для получения более качественных результатов для за-
данного набора параметров сеть генерировалась несколько раз и рассчитывалось
среднее значение интегрального показателя.
На рис. 1–3 показаны результаты экспериментов для сетей с различными па-
раметрами. Количество повторений экспериментов для каждой ситуации, задан-
ной соответствующим набором параметров, равнялось 10. Для отдельных наборов
эксперимент был повторен 100 раз, ошибка по сравнению с экспериментами, со-
стоящими из 10 повторов моделирования ситуаций, не превысила 5 %.
И
н
те
гр
ал
ьн
ая
о
ш
и
б
к
а
График ошибки при количестве вершин 5, количество связей 6
0
1
2
3
4
5
6
Размер выборки
1
0
0
5
0
0
9
0
0
1
3
0
0
1
7
0
0
2
1
0
0
2
5
0
0
2
9
0
0
3
3
0
0
3
7
0
0
4
1
0
0
4
5
0
0
4
9
0
0
5
3
0
0
5
7
0
0
6
1
0
0
6
5
0
0
6
9
0
0
7
1
0
0
7
4
0
0
7
7
0
0
2 состояния 3 состояния 4 состояния
Рис. 1
И
н
те
гр
ал
ьн
ая
о
ш
и
б
к
а
График ошибки при количестве вершин 10, количество связей 12
0
2
4
6
8
10
12
Размер выборки
1
0
0
5
0
0
9
0
0
1
3
0
0
1
7
0
0
2
1
0
0
2
5
0
0
2
9
0
0
3
3
0
0
3
7
0
0
4
1
0
0
4
5
0
0
4
9
0
0
5
3
0
0
5
7
0
0
6
1
0
0
6
5
0
0
6
9
0
0
7
1
0
0
7
4
0
0
7
7
0
0
2 состояния 3 состояния 4 состояния
Рис. 2
И
н
те
гр
ал
ьн
ая
о
ш
и
б
к
а
График ошибки при количестве вершин 15, количество связей 18
0
5
10
15
20
Размер выборки
1
0
0
5
0
0
9
0
0
1
3
0
0
1
7
0
0
2
1
0
0
2
5
0
0
2
9
0
0
3
3
0
0
3
7
0
0
4
1
0
0
4
5
0
0
4
9
0
0
5
3
0
0
5
7
0
0
6
1
0
0
6
5
0
0
6
9
0
0
7
1
0
0
7
4
0
0
7
7
0
0
2 состояния 3 состояния 4 состояния
Рис. 3
72 ISSN 0572-2691
Исходя из графиков, можно сделать ряд выводов. Во-первых, зависимость
качества восстановления сети от размера выборки имеет характерную форму и
может быть представлена в виде функции. Параметры функции также будут зави-
сеть от параметров сети (количество вершин, состояний, связей и т.д.). Нужно от-
метить, что зависимость между ошибкой восстановления и размером выборки
имеет обратно пропорциональный характер, т.е. значение ошибки уменьшается
при увеличении выборки.
Во-вторых, видно, что при определенном объеме выборки дальнейшее ее
увеличение не несет заметного улучшения качества восстановления. Таким обра-
зом, существует некий порог размера выборки, превышение которого нецелесо-
образно. На основании полученных результатов проведенных 630 вычислитель-
ных экспериментов для определения размера обучающей выборки, обеспечиваю-
щей высокую точность построения топологии БС (состоящей не более чем из
50 вершин), авторы предлагают функцию вида
.100),,( MSNMSNV
Заключение
В настоящей статье рассмотрена проблема построения упорядоченного мно-
жества вершин как одного из этапов эвристического алгоритма построения БС.
Для решения поставленной задачи предложено использование разных методик
оценки взаимосвязей между вершинами.
Описанные методы оценки взаимосвязей можно разделить на две группы:
исключительно эвристические метрики, основанные на статистике 2 -квадрат,
и информационные метрики связи.
Из результатов проведенных вычислительных экспериментов видно, что ис-
пользование метрик обоюдной информации, Пирсона, Чупрова и Крамера дают
фактически идентичные результаты. Использование коэффициента Гудмана ведет
к ухудшению результата, в сравнении с вышеупомянутыми. Таким образом, в ка-
честве оценки связи в эвристическом алгоритме рекомендуется использовать зна-
чение обоюдной информации, коэффициенты Пирсона, Чупрова или Крамера.
Авторами предложена функция для определения размера обучающей выбор-
ки, необходимой для построения топологии БС.
В дальнейших исследованиях планируется разработать методы улучшения
качества алгоритмов построения БС, в частности, на основании полученных ре-
зультатов.
П.І. Бідюк, В.І. Давиденко, Д.В. Трофименко, О.М. Терентьєв
ПОРІВНЯЛЬНИЙ АНАЛІЗ МЕТОДІВ
ОЦІНКИ ВЗАЄМОЗВ’ЯЗКУ МІЖ ВЕРШИНАМИ
ПРИ ПОБУДОВІ МЕРЕЖ БАЙЄСА
Проаналізовано методи оцінки взаємозв’язку між вершинами при побудові
мереж Байєса з використанням евристичного алгоритму. Наведено теоретичне
обґрунтування методів, розглянуто результати їх практичного використання
при побудові класичних мереж, а також описано алгоритм проведення експе-
риментів на основі псевдовипадкового генерування байєсових мереж. Отримані
для кожного методу результати порівнювались. Зроблено висновки про можли-
вість застосування розглянутих методів оцінки взаємозв’язку між вершинами
при побудові байєсових мереж.
Международный научно-технический журнал
«Проблемы управления и информатики», 2010, № 6 73
P.I. Bidyuk, V.I. Davydenko, D.V. Trofymenko, A.N. Terentyev
COMPARATIVE ANALYSIS OF ESTIMATION
METHODS OF NODES CORRELATION
IN BAYESIAN NETWORKS CONSTRUCTION
The estimation methods of nodes interrelation in Bayesian networks construction
using heuristic algorithm are analysed. Theoretical justification of methods is given,
results of practical use in construction of classic networks are considered and exper-
iments implementation algorithm based on pseudorandom generation of Bayesian
networks is described. Comparison of received results for each method is performed
and conclusions are drawn about possibility of using the considered estimation meth-
ods of nodes correlation in Bayesian networks construction.
1. Терентьев А.Н., Бидюк П.И. Эвристический метод построения байесовских сетей // Мате-
матические машины и системы. — Киев : ТОВ «РВПК ЕКСЛИБРИС», 2006. — № 3. —
С. 12–23.
2. Елисеева И.И., Рукавишников В.О. Группировка, корреляция, распознавание образов (Ста-
тистические методы классификации и измерения связей). — М. : Статистика, 1977. —
144 с.
3. Cramer H. Mathematical methods of statistics. — Princeton. — NJ : Princeton U-t Press,
1946. — 575 p.
4. Liebetrau A.M. Measures of association. — Newbury Park, CA : Sage Publications // Quantitative
Appl. in the Social Sci., 1983, Ser. 32.
5. Goodman L.A., Kruskal W.H. Measures of association for cross-classifications // J. Amer. Statist.
Assoc. — 1954. — 49. — P. 732–764.
6. Chow C.K., Liu C.N. Approximating discrete probability distributions with dependence trees //
IEE Trans. on Inform. Theory. — 1968. — IT-14, N 3. — 6 p.
7. Zheng Y., Kwoh C.K. Improved MDL score for learning of Bayesian networks // Proc. of the
Intern. Conf. on Artificial Intell. in Sci. and Technology (AISAT 2004). — 2004. — P. 98–103.
8. Heckerman D., Geiger D., Chickering D.M. Learning Bayesian networks: the combination of
knowledge and statistical data // Machine Learning. — 1995. — 20, N 3. — P. 197–243.
9. Spiegel M.R., Stephens L.J. Schaum’s outline of theory and problems of statistics. — McGraw-
Hill Professional, 1999. — P. 345–349.
10. Терентьев А.Н., Бирюк П.И., Миронова А.В., Медин Н.Ю. Сравнение методов интеллекту-
ального анализа данных при оценивании кредитоспособности физических лиц // Проблемы
управления и информатики. — 2009. — № 5. — С. 141–149.
11. Терентьев А.Н., Бидюк П.И., Коршевнюк Л.А. Байесовская сеть — инструмент интеллекту-
ального анализа данных // Там же. — 2007. — № 4. — С. 83–92.
12. Афифи А., Эйзен С. Статистический анализ: Подход с использованием ЭВМ: Пер. с англ. —
М. : Мир, 1982. — 488 с.
Получено 13.05.2010
|
| id | nasplib_isofts_kiev_ua-123456789-210848 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2026-03-13T19:13:53Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Бидюк, П.И. Давиденко, В.И. Трофименко, Д.В. Терентьев, А.Н. 2025-12-18T10:00:32Z 2010 Сравнительный анализ методов оценки взаимосвязи между вершинами при построении байесовских сетей / П.И. Бидюк, В.И. Давиденко, Д.В. Трофименко, А.Н. Терентьев // Проблемы управления и информатики. — 2010. — № 6. — С. 64-73. — Бібліогр.: 12 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/210848 62-50 10.1615/JAutomatInfScien.v42.i11.40 Проаналізовано методи оцінки взаємозв’язку між вершинами при побудові мереж Байєса з використанням евристичного алгоритму. Наведено теоретичне обґрунтування методів, розглянуто результати їх практичного використання при побудові класичних мереж, а також описано алгоритм проведення експериментів на основі псевдовипадкового генерування байєсових мереж. Отримані для кожного методу результати порівнювались. Зроблено висновки про можливість застосування розглянутих методів оцінки взаємозв’язку між вершинами при побудові байєсових мереж. The estimation methods of nodes interrelation in Bayesian networks construction using heuristic algorithm are analysed. Theoretical justification of methods is given, results of practical use in construction of classic networks are considered and experiments implementation algorithm based on pseudorandom generation of Bayesian networks is described. Comparison of received results for each method is performed and conclusions are drawn about possibility of using the considered estimation methods of nodes correlation in Bayesian networks construction. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Методы обработки информации Сравнительный анализ методов оценки взаимосвязи между вершинами при построении байесовских сетей Порівняльний аналіз методів оцінки взаємозв’язку між вершинами при побудові мереж Байєса Comparative analysis of estimation methods of nodes correlation in Bayesian networks construction Article published earlier |
| spellingShingle | Сравнительный анализ методов оценки взаимосвязи между вершинами при построении байесовских сетей Бидюк, П.И. Давиденко, В.И. Трофименко, Д.В. Терентьев, А.Н. Методы обработки информации |
| title | Сравнительный анализ методов оценки взаимосвязи между вершинами при построении байесовских сетей |
| title_alt | Порівняльний аналіз методів оцінки взаємозв’язку між вершинами при побудові мереж Байєса Comparative analysis of estimation methods of nodes correlation in Bayesian networks construction |
| title_full | Сравнительный анализ методов оценки взаимосвязи между вершинами при построении байесовских сетей |
| title_fullStr | Сравнительный анализ методов оценки взаимосвязи между вершинами при построении байесовских сетей |
| title_full_unstemmed | Сравнительный анализ методов оценки взаимосвязи между вершинами при построении байесовских сетей |
| title_short | Сравнительный анализ методов оценки взаимосвязи между вершинами при построении байесовских сетей |
| title_sort | сравнительный анализ методов оценки взаимосвязи между вершинами при построении байесовских сетей |
| topic | Методы обработки информации |
| topic_facet | Методы обработки информации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/210848 |
| work_keys_str_mv | AT bidûkpi sravnitelʹnyianalizmetodovocenkivzaimosvâzimežduveršinamipripostroeniibaiesovskihsetei AT davidenkovi sravnitelʹnyianalizmetodovocenkivzaimosvâzimežduveršinamipripostroeniibaiesovskihsetei AT trofimenkodv sravnitelʹnyianalizmetodovocenkivzaimosvâzimežduveršinamipripostroeniibaiesovskihsetei AT terentʹevan sravnitelʹnyianalizmetodovocenkivzaimosvâzimežduveršinamipripostroeniibaiesovskihsetei AT bidûkpi porívnâlʹniianalízmetodívocínkivzaêmozvâzkumížveršinamipripobudovímerežbaiêsa AT davidenkovi porívnâlʹniianalízmetodívocínkivzaêmozvâzkumížveršinamipripobudovímerežbaiêsa AT trofimenkodv porívnâlʹniianalízmetodívocínkivzaêmozvâzkumížveršinamipripobudovímerežbaiêsa AT terentʹevan porívnâlʹniianalízmetodívocínkivzaêmozvâzkumížveršinamipripobudovímerežbaiêsa AT bidûkpi comparativeanalysisofestimationmethodsofnodescorrelationinbayesiannetworksconstruction AT davidenkovi comparativeanalysisofestimationmethodsofnodescorrelationinbayesiannetworksconstruction AT trofimenkodv comparativeanalysisofestimationmethodsofnodescorrelationinbayesiannetworksconstruction AT terentʹevan comparativeanalysisofestimationmethodsofnodescorrelationinbayesiannetworksconstruction |