🔍 Поиск готовых работ

🔍 Поиск работ

АЛГЕБРАИЧЕСКИЕ БАЙЕСОВСКИЕ СЕТИ: СИСТЕМА АНАЛИЗА И СИНТЕЗА ВТОРИЧНОЙ СТРУКТУРЫ

Работа №66501

Тип работы

Бакалаврская работа

Предмет

информатика

Объем работы49
Год сдачи2016
Стоимость3800 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено
186
Не подходит работа?

Узнай цену на написание


Введение 5
1 Обзор существующих алгоритмов синтеза
вторичной структуры АБС 7
1.1 Существующие решения 7
1.2 Актуальность работы 8
2 Определения и обозначения 9
2.1 Теоретическая часть 9
2.2 Технологическая часть 11
3 Инкрементальный алгоритм добавления
вершины в минимальный граф смежности 12
3.1 Описание алгоритма 13
3.2 Корректность алгоритма 15
4 Улучшенный инкрементальный алгоритм
добавления вершины в минимальный граф смежности 19
4.1 Описание алгоритма 19
4.2 Корректность алгоритма 24
5 Декрементальный алгоритм удаления вершины 26
5.1 Описание алгоритма 26
5.2 Корректность алгоритма 28
6 Система анализа и синтеза 29
6.1 Общие интерфейсы 30
6.2 Визуализация графа 31
6.3 Графический пользовательский интерфейс 33
Заключение 43
Список литературы 44

Графы смежности интенсивно используются в алгебраических байесов-ских сетях (далее АБС) в качестве вторичной структуры [9,11,16,30,33]. Такой объект оказался необходим потому, что ряд алгоритмов локального и глобального вывода, использующие рекуррентный подход, требуют, что¬бы вторичной структурой был ациклический минимальный граф смеж¬ности [1, 8, 10, 12-14]. Однако предложенная стуктура сложна в построе¬нии, что заметно усложняет работу с динамически изменяющимися дан¬ными. Инкрементальный, а также использующий подобные методы декре- ментальный алгоритмы, рассматриваемые в данной работе, применяются для перестроения вторичной структуры АБС, что позволяет динамически изменять структуру графа смежности, не прибегая к полному перестро¬ению графа. Это существенно сказывается на времени работы подобных алгоритмов вывода [2,5]. Кроме того, минимальный граф смежности легче визуализировать, равно как и легче выявлять скрытые закономерности, им представленные.
При сложившейся практике обмена данными [15,32] между программ-ным компонентом, реализующим графический пользовательский интер¬фейс, и «блоком вычислений» — программным компонентом, обеспечива¬ющим построение сложной системы из заданных составляющих, — типич¬ный сценарий работы предполагает формирование набора составляющих, отправку набора в блок вычислений, формирование сложной системы, от-правку данных в графический пользовательский интерфейс для визуаль¬ного представления сформированной системы. Особенно это справедливо для клиент-серверных систем с так называемым «тонким» клиентом.
Однако этот типичный сценарий ведёт ко всё более длительному ожи-данию оператора, когда набор составляющих растёт, поскольку зачастую вычислительная сложность алгоритмов синтеза экспоненциально зависит от объема исходных данных или оказывается ещё большей.
Одним из возможных путей решения или, по крайней мере, смягче¬ния обозначенной проблемы является инкрементализация и дектремента- лизация алгоритмов, которая нацелена на использование того, что было построено на предшествующих шагах работы с программой.
Иначе говоря, на практике при работе с большим набором данных, в котором имеются связи, зависимости и отношения, часто ставится зада¬ча изменения подобного набора данных таким образом, чтобы имеющиеся ранее связи, зависимости и отношения либо сохранялись прежними, либо время, затрачиваемое на их перестроение, было бы близким к минимально-му [24,31,34,35,37]. Трудозатраты на выполнение таких операций играют важную, а порой и критическую роль, когда речь идет о real-time-системах или о системах, для которых важна высокая степень доступности. Таким образом, возникает вопрос, как избежать полного перестроения системы после каждого небольшого изменения исходного набора данных.
В рассматриваемом случае — примере минимального графа смежно¬сти как сложной системы — осуществляется попытка использовать уже построенный минимальный граф смежности и либо дополнить его новой вершиной, либо обеднить одной из существующих вершин с соблюдением требований структуры, подробно описанных во 2-м разделе.
Таким образом, теоретической целью данной работы является разработ-ка инкрементальных и декрементальных алгоритмов, ускоряющих постро-ение глобальных структур алгебраических байесовских сетей при работе с динамически изменяющимися данными.
Таже в данной работе есть технологическая цель: создание системы ана-лиза и синтеза вторичной структуры алгебраических байесовских сетей в виде комплекса программ, который позволял бы пользователям нагляд¬но изучать поведение глобальных структур АБС при поступлении в сеть новых данных, а также проводить различного рода вычисления, важные в контексте вероятностных графических моделей. Такая система могла бы пригодиться при изучении и преподавании теории алгебраических байесов-ских сетей. Пользователи системы получат возможность быстро и удобно работать с такой сложной структурой, как граф смежности, и для этого им не понадобится изучать особенности программной реализации подобных алгебраических структур. Также необходимо отметить, что настоящая вы-пускная квалификационная работа бакалавра является проектной, то есть выполняется совместно с коллегами (Романовым Артемом Витальевичем, Березиным Алексеем Ивановичем), кроме того, тесно связана с выпускной квалификационной работой бакалавра Мальчевской Екатерины Андреев¬ны.
Для удобства изложения сначала раскрывается теоретическая часть данной работы (главы 3-5), а затем практическая (глава 6), при этом все используемые определения вынесены в главу 2.


Возникли сложности?

Нужна помощь преподавателя?

Помощь в написании работ!
ДИПЛОМНЫЕ МАГИСТЕРСКИЕ ДИССЕРТАЦИИ
КУРСОВЫЕ СТАТЬИ ВКР

В данной работе рассмотрены три алгоритма, существенно ускоряющие синтез [2,5] нового минимального графа смежности при изменении первич-ной структуры исходного минимального графа смежности.
Вышеуказанные алгоритмы особенно удобны для интерактивных про-граммных систем, когда минимальный граф смежности строится в диалоге с пользователем. Последний ожидает от системы достаточного быстродей-ствия, полагая, что небольшое изменение в данных, в частности, при добав-лении или удалении вершины, влечет умеренное изменение минимального графа смежности.
Разработана система анализа и синтеза вторичной структуры АБС, ре-ализующая все предъявленные к ней требования.
Все задачи выполнены. Все цели достигнуты.



[1] Золотин А.А., Тулупьев А.Л., Сироткин А.В. Матрично-векторные ал-горитмы нормировки для локального апостериорного вывода в алгеб-раических байесовских сетях // Научно-технический вестник инфор-мационных технологий, механики и оптики. 2015. Том 15. № 1. С. 78-85.
[2] Зотов М.А., Левенец Д.Г., Тулупьев А.Л., Золотин А.А. Синтез вто-ричной структуры алгебраических байесовских сетей: инкременталь-ный алгоритм и статистическая оценка его сложности // Научно-технический вестник информационных технологий, механики и опти¬ки. 2016. № 1. С. 122-132.
[3] Зотов М.А., Тулупьев А. Л. Синтез вторичной структуры алгебраи-ческих байесовских сетей. // Компьютерные инструменты в образова- нии(2015. Выпуск 1).
[4] Зотов М.А., Тулупьев А.Л., Сироткин А.Л. Статистические оценки сложности прямого и жадного алгоритмов синтеза вторичной структу-ры алгебраических байесовских сетей // Нечеткие системы и мягкие вычисления. 2015. Т 10. №1. С. 75-91
[5] Левенец Д.Г., Зотов М.А., Тулупьев А.Л. Инкрементальный алгоритм синтеза минимального графа смежности. // Компьютерные инстру-менты в образовании. 2015. № 6. С. 3-18.
[6] Опарин В.В., Тулупьев А.Л. Синтез графа смежности с минимальным числом ребер: формализация алгоритма и анализ его корректности. // Тр. СПИИРАН. 2009. №11. C. 142-157.
[7] Опарин В.В., Фильченков А.А., Сироткин А.В., Тулупьев А.Л. Матро- идное представление семейства графов смежности над набором фраг-ментов знаний // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механи-ки и оптики. 2010. №4(68). С. 73-76.
[8] Тулупьев А.Л. Автоматическое обучение фрагментов знаний в алгеб-раических байесовских сетях // Интегрированные модели и мягкие вычисления в искусственном интеллекте. V-я Международная научно-практическая конференция. Сборник научных трудов. В 2-х т. Т. 1. С. 163-176.
[9] Тулупьев А.Л. Алгебраические байесовские сети: глобальный логико-вероятностный вывод в деревьях смежности: Учеб. пособие. СПб.: СПбГУ; ООО Издательство «Анатолия», 2007. С. 40. (Сер. Элементы мягких вычислений).
[10] Тулупьев А.Л. Алгебраические байесовские сети: локальный логико-вероятностный вывод: // Учеб. пособие. СПб.: СПбГУ; ООО Издатель-ство «Анатолия», 2007. С. 80. (Сер. Элементы мягких вычислений)
[11] Тулупьев А.Л. Алгебраические байесовские сети: открытые вопросы локального автоматического обучения // СПИСОК-2014: Материа¬лы всероссийской научной конференции по проблемам информатики. Санкт-Петербург, 2014. С. 569-577.
[12] Тулупьев А.Л. Вероятностная логика и вероятностные графические модели в базах фрагментов знаний с неопределенностью // Интегри-рованные модели, мягкие вычисления, вероятностные системы и ком-плексы программ в искусственном интеллекте. Научно-практическая конференция студентов, аспирантов, молодых ученых и специалистов (Коломна, 26-27 мая 2009 г.). Научные доклады. В 2-х т. Т. 1. М.: Физ- матлит, 2009. С. 26-46.
[13] Тулупьев А.Л. Дерево смежности с идеалами конъюнктов как ацик-лическая алгебраическая байесовская сеть // Тр. СПИИРАН. Вып. 3, т. 1. СПб.: Наука, 2006. С. 198-227.
[14] Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. С. 607.
[15] Тулупьев А.Л., Столяров Д.М., Ментюков М.В. Представление локаль-ной и глобальнойструктуры алгебраической байесовской сети в Java- приложениях // Труды СПИИРАН. 2007. Вып. 5. СПб.: Наука, 2007. С. 71-99.
[16] Тулупьев А.Л., Сироткин А.В., Николенко С.И. Байесовские сети дове-рия: логико-вероятностный вывод в ациклических направленных гра-фах. СПб.: Изд-во С.-Петерб. ун-та, 2009. С. 400.
[17] Фильченков А.А. Синтез графов смежности в машинном обучении глобальных структур алгебраических байесовских сетей. Дисс.... к-та физ.-мат. н. Самара, 2013. С. 339. (Самарск. гос. аэрокосм. ун-т им. ак. С.П. Королева (нац. исслед.))
[18] Фильченков А.А., Мусина В.Ф., Тулупьев А.Л. Алгоритм рандомизи-рованного синтеза минимального графа смежности // Тр. СПИИРАН.
2013. Вып. 2(35). С. 221-234. ун-т.
[19] Фильченков А.А., Тулупьев А.Л. Анализ циклов в минимальных гра-фах смежности алгебраических байесовских сетей // Тр. СПИИРАН. 2011. №17. С. 151-173.
[20] Фильченков А.А., Тулупьев А.Л. Структурный анализ систем мини-мальных графов смежности // Тр. СПИИРАН. 2009. №11. C. 104-129.
[21] Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Минимальные гра¬фы смежности алгебраической байесовской сети: нормализация основ синтеза и автоматического обучения // Нечеткие системы и мягкие вычисления. 2011. Т. 6. № 2. С. 145-163.
[22] Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Особенности анали¬за вторичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2010. № 1 (12). С. 97-118. (цит. 24, ИФ РИНЦ)
[23] Фильченков А.А., Фроленков К.В., Сироткин А.В., Тулупьев А.Л. Си-стема синтеза подмножеств минимальных графов смежности // Тр. СПИИРАН. 2013. Вып. 4(27). С. 200-244.
[24] Шинкаренко В.И. Зависимость временной эффективности алгоритмов и программ обработки больших объемов данных от их кэширования // Математические машины и системы. 2007. №2. С. 43-55.
[25] Обзор продуктов Visual Studio 2015 [Электронный ресурс]. Ре¬жим доступа: URL: https://www.visualstudio.com/ru-ru/products/vs- 2015-product-editions.aspx (дата обращения 07.05.2016).
[26] Руководство по программированию на C# [Электронный ре¬сурс]. Режим доступа: URL: https://msdn.microsoft.com/ru- ru/library/67ef8sbd.aspx (дата обращения 07.05.2016).
[27] Сайт компании Microsoft [Электронный ресурс]. Режим доступа: URL: https://www.microsoft.com/ru-ru/ (дата обращения 07.05.2016).
[28] Сайт проекта BitBucket [Электронный ресурс]. Режим доступа: URL: https://bitbucket.org/ (дата обращения 07.05.2016).
[29] Barrett C., Marathe A., Marathe M., Cook D., Hicks G., Faber V., Srinivasan A., Sussmann Y., Thornquist H. Statistical Analysis of Algorithms: A Case Study of Market-Clearing Mechanisms in the Power Industry. Journal of Graph Algorithms and Applications (JGAA). 2003. Vol. 7. P. 3-31.
[30] Jaynes E.T. Bayesian Methods: General Background // Maximum-Entropy and Bayesian Methods in Applied Statistics, by J. H. Justice (ed.). Cambridge: Cambridge Univ. Press, 1986. P. 1-19.
[31] Kas M., Wachs M., Carley K.M., Carley.L.R. Incremental Algorithm for Updating Betweenness Centrality in Dynamically Growing Networks. // Ozyer, T and Carrington, P, editor,2013 IEEE/ACM international conference on advances in social networks analysis and mining (ASONAM), p.39-46, 345 E 47TH ST, Newyork, NY 10017 USA, 2013. IEEE. IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), Niagara Falls, Canada, aug. 25-28, 2013.
[32] Maier D. Theory of Relational Databases. // Rockville, MD: Computer Science Press, 1983. P. 637
[33] Pearl J. Causality: Models, Reasoning, and Inference. Cambridge: Cambridge University Press, 2000. P. 400.
[34] Respondek J. S. Dynamic data structures in the incremental algorithms operating on a certain class of special matrices //Computational Science and Its Applications-ICCSA 2014. - Springer International Publishing,
2014. - С. 171-185.
[35] Song X., Yu L., Sun H. An Incremental Query Algorithm for Optimal Path Queries Under Traffic Jams. // Yu, F and Chen, W and Chen, Z and Yuan, J, editor, ISCSCT 2008: International Symposiumon Computer Science and Computational Technology, Proceedings, p.472-475, 10662 Los Vaqueros Circle, PO BOX3014, Los Alamitos, CA 90720-1264 USA, 2008. IEEE Computer SOC. International Symposium on Computer Science and Computational Technology, Shanghai, Peoples R China, dec.20-22, 2008.
[36] Graph# [Электронный ресурс]. Режим доступа: URL: https://graphsharp.codeplex.com/ (дата обращения 07.05.2016).
[37] Incremental algoritms [Электронный ресурс]. Режим доступа: URL: http://c2.com/cgi/wiki? IncrementalAlgorithms (дата обращения 01.11.2015).
[38] Microsoft Silverlight [Электронный ресурс]. Режим доступа: URL: https://www.microsoft.com/silverlight/ (дата обращения 07.05.2016).
[39] Introduction to Model/View/ViewModel pattern for building WPF apps [Электронный ресурс]. Режим доступа: URL: https://blogs.msdn.microsoft.com/johngossman/2005/10/08/introduction- to-modelviewviewmodel-pattern-for-building-wpf-apps/ (дата обращения 07.05.2016).
[40] MSDN: Windows Presentation Foundation [Электронный ресурс]. Режим доступа: URL: https://msdn.microsoft.com/ru-ru/library/ms754130.aspx (дата обращения 07.05.2016).
[41] QuickGraph, Graph Data Structures And Algorithms for .NET [Электрон-ный ресурс]. Режим доступа: URL: https://quickgraph.codeplex.com/ (дата обращения 07.05.2016).
[42] Wikipedia: Model-View-ViewModel [Электронный ресурс]. Режим до-ступа: URL: https://ru.wikipedia.org/wiki/Model-View-ViewModel (дата обращения 07.05.2016).
[43] Wikipedia: Windows Presentation Foundation
[Электронный ресурс]. Режим доступа: URL:
https://ru.wikipedia.org/wiki/Windows_Presentation_Foundation (дата обращения 07.05.2016).
[44] Wikipedia: XAML [Электронный ресурс]. Режим доступа: URL: https://ru.wikipedia.org/wiki/XAML (дата обращения 07.05.2016).
[45] .NET Framework [Электронный ресурс]. Режим доступа: URL: https://www.microsoft.com/net/default.aspx (дата обращения 07.05.2016).

Работу высылаем на протяжении 30 минут после оплаты.



Подобные работы


©2025 Cервис помощи студентам в выполнении работ
.