Инкрементальный алгоритм синтеза минимального графа смежности

  • Даниил Григорьевич Левенец СПбГУ, Санкт-Петербург, Россия
  • Михаил Анатольевич Зотов СПбГУ, Санкт-Петербург, Россия
  • Александр Львович Тулупьев СПбГУ, Санкт-Петербург, Россия
Ключевые слова: граф смежности, вероятностные графические модели, инкрементальный алгоритм, статистическая оценка сложности, структурное обучение, машинное обучение

Аннотация

В статье предложен инкрементальный алгоритм, ускоряющий синтез минимального графа смежности по исходному минимальному графу смежности и новой вершине с заданной допустимой нагрузкой; доказана корректность работы такого алгоритма. Выполнен сравнительный анализ статистических оценок сложности реализаций предложенного алгоритма и двух известных алгоритмов синтеза минимального графа смежности: жадного и прямого; результаты вычислительных экспериментов представлены в виде графиков, снабжены комментариями и выводом. В целом, на наборах со средним и большим числом вершин инкрементальный алгоритм в 3-6 раз оказался быстрее, чем прямой, и в 10-50 раз быстрее, чем жадный. На наборах с небольшим числом вершин скорость алгоритмов отличается не сильно. Отмечено, что, чем больше в наборе вершин с нагрузкой 5-9 символов, тем более велик разброс отношения скоростей сравниваемых алгоритмов. В статье также достигнуты дидактические цели: в контексте синтеза минимальных графов смежности продемонстрировано обоснованное применение методов инкрементализации алгоритмов, статистического анализа скорости работы реализаций алгоритмов, визуализации данных, полученных в результате проведения вычислительных экспериментов.

Биографии авторов

Даниил Григорьевич Левенец, СПбГУ, Санкт-Петербург, Россия

Левенец Д. Г., cтудент 4 курса кафедры информатики математико-механического факультета СПбГУ

Михаил Анатольевич Зотов, СПбГУ, Санкт-Петербург, Россия

Зотов М. А., cтудент 5 курса кафедры системного программирования математико-механического факультета СПбГУ.

Александр Львович Тулупьев, СПбГУ, Санкт-Петербург, Россия

Тулупьев А. Л., доктор физико-математических наук, доцент, заведующий лаб. ТиМПИ СПИИРАН; профессор кафедры информатики СПбГУ.

Литература

1. Золотин А.А., Тулупьев А.Л., Сироткин А.В. Матрично-векторные алгоритмы нормировки для локального апостериорного вывода в алгебраических байесовских сетях // Научнотехнический вестник информационных технологий, механики и оптики, 2015. Т. 15. № 1. С. 78–85.
2. Зотов М.А., Тулупьев А.Л. Синтез вторичной структуры алгебраических байесовских сетей // Компьютерные инструменты в образовании, 2015. № 1. C. 3–16.
3. Зотов М.А., Тулупьев А.Л., Сироткин А.Л. Статистические оценки сложности прямого и жадного алгоритмов синтеза вторичной структуры алгебраических байесовских сетей // Нечеткие системы и мягкие вычисления, 2015. Т. 10. №1. С. 75–91.
4. Опарин В.В., Тулупьев А.Л. Синтез графа смежности с минимальным числом ребер: формализация алгоритма и анализ его корректности // Тр. СПИИРАН, 2009. № 11. C. 142–157.
5. Опарин В.В., Фильченков А.А., Сироткин А.В., Тулупьев А.Л. Матроидное представление семейства графов смежности над набором фрагментов знаний // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010. № 4(68). С. 73–76.
6. Тулупьев А.Л. Алгебраические байесовские сети: глобальный логико-вероятностный вывод в деревьях смежности: Учеб. пособие. СПб.: СПбГУ; ООО Издательство «Анатолия», 2007. С. 40. (Сер. Элементы мягких вычислений).
7. Тулупьев А.Л. Дерево смежности с идеалами конъюнктов как ациклическая алгебраическая байесовская сеть // Тр. СПИИРАН. Вып. 3, т. 1. СПб.: Наука, 2006. С. 198–227.
8. Тулупьев А.Л., Николенко С.И., Сироткин А.В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. С. 607.
9. Тулупьев А.Л., Сироткин А.В., Николенко С.И. Байесовские сети доверия: логиковероятностный вывод в ациклических направленных графах. СПб.: Изд-во С.-Петерб. ун-та, 2009. С. 400.
10. Тулупьев А.Л., Столяров Д.М., Ментюков М.В. Представление локальной и глобальной структуры алгебраической байесовской сети в Java-приложениях // Труды СПИИРАН. 2007. Вып. 5. СПб.: Наука, 2007. С. 71–99.
11. Фильченков А.А. Синтез графов смежности в машинном обучении глобальных структур алгебраических байесовских сетей. Дисс.... к-та физ.-мат. н. Самара, 2013. С. 339. (Самарск. гос. аэрокосм. ун-т им. ак. С.П. Королева (нац. исслед.))
12. Фильченков А.А., Мусина В.Ф., Тулупьев А.Л. Алгоритм рандомизированного синтеза минимального графа смежности // Тр. СПИИРАН. 2013. Вып. 2(35). С. 221–234. ун-т.
13. Фильченков А.А., Тулупьев А.Л. Структурный анализ систем минимальных графов смежности // Тр. СПИИРАН. 2009. № 11. C. 104–129.
14. Фильченков А.А., Тулупьев А.Л. Анализ циклов в минимальных графах смежности алгебраических байесовских сетей // Тр. СПИИРАН. 2011. № 17. С. 151–173.
15. Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Минимальные графы смежности алгебраической байесовской сети: формализация основ синтеза и автоматического обучения // Нечеткие системы и мягкие вычисления, 2011. Т. 6. № 2. С. 145–163.
16. Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Особенности анализа вторичной структуры алгебраической байесовской сети // Труды СПИИРАН. 2010. № 1 (12). С. 97–118.
17. Фильченков А.А., Фроленков К.В., Сироткин А.В., Тулупьев А.Л. Система алгоритмов синтеза подмножеств минимальных графов смежности // Труды СПИИРАН. 2013. № 4(27). С. 200–244.
18. Шинкаренко В.И. Зависимость временной эффективности алгоритмов и программ обработки больших объемов данных от их кэширования // Математические машины и системы. 2007. №2. С. 43–55.
19. 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.
20. Gonzalez-Diaz R., Ion A., Jimenez M.J., Poyatos.R. Incremental-Decremental Algorithm for Computing AT-Models and PersistentHomology // Real, P and DiazPernil, D and MolinaAbril, H and Berciano, A and Kropatsch, W, editor, Computer analysis of images and patterns:14th international conference, CAIP 2011, PT I, volume 6854 of LNCS, p.286–293, heidelberger platz3, D-14197 Berlin, Germany, 2011. springer-verlag berlin. 14thInternational Conference on Computer Analysis of Images and Patterns (CAIP),Seville, SPAIN, AUG 29-31, 2011.
21. Incremental algoritms [Электронный ресурс]. Режим доступа: URL: http://c2.com/cgi/wiki?IncrementalAlgorithms (дата обращения 01.11.2015).
22. 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.
23. Jerzy S. Respondek. Dynamic Data Structures in the Incremental Algorithms Operating on a Certain Class of Special Matrices. // Murgante, B and Misra, Sand Rocha, AMAC and Torre, C and Rocha, JG and Falcao, MI and Taniar,D and Apduhan, BO and Gervasi, O, editor, Computational scienceand its applications, part VI - ICCSA 2014, volume 8584 of Lecture Notes in Computer Science, p.171–185, Heidelberger platz 3, D-14197 Berlin, Germany, 2014. springer-verlag Berlin. 14-th International Conference on Computational Science and Its Applications (ICCSA), Guimaraes, Portugal, jun 30-jul 03, 2014.
24. 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.
25. Pearl J. Causality: Models, Reasoning, and Inference. Cambridge: Cambridge University Press, 2000. P. 400.
26. Sariyuce A.E., Kaya K., Saule E., Umit V. Catalyurek. Incremental Algorithms for Closeness Centrality. // Hu, X and Lin, TY and Raghavan, V and Wah, B and Yates, R and Fox, G and Shahabi, C and Smith, M and Yang, Q and Ghani, R and Fan, W and Lempel, R and Nambiar,R, editor,2013 IEEE International conference on big data, 345E 47-th st, Newyork, NY 10017 USA, 2013. IEEE. IEEE International Conference on Big Data (Big Data), Santa Clara, CA, oct. 06-09, 2013.
27. 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.
Опубликован
2015-12-30
Как цитировать
Левенец, Д. Г., Зотов, М. А., & Тулупьев, А. Л. (2015). Инкрементальный алгоритм синтеза минимального графа смежности. Компьютерные инструменты в образовании, (6), 3-18. извлечено от http://cte.eltech.ru/ojs/index.php/kio/article/view/1447
Выпуск
Раздел
Информатика

Наиболее читаемые статьи этого автора (авторов)