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

Предложен улучшенный алгоритм синтеза вторичной структуры алгебраических байесовских сетей, представленной в виде минимального графа смежности. Алгоритм отличается от предложенных ранее тем, что основывается на принципе инкрементализации, использует лишь особым образом отобранные ребра, исходящие из новой вершины, исключает оставшиеся избыточные ребра с помощью жадного алгоритма. Корректность работы инкрементального алгоритма обоснована математическим доказательством. Сравнение вычислительной сложности нового (инкрементального) алгоритма и двух известных (жадного и прямого) произведено с помощью статистических оценок сложности, построенных на основе выборки значений отношения времени работы программных реализаций двух сравниваемых алгоритмов. Теоретические оценки сложности жадного и прямого алгоритмов были получены ранее, но непригодны для осуществления компаративного анализа, поскольку опираются на скрытые характеристики вторичной структуры, которые можно вычислить лишь при ее построении. Для минимизации влияния случайных факторов при вычислении отношений использовано усредненное время работы программной реализации, полученное за счет K ее запусков на одном и том же наборе нагрузок. Выборка значений отношений сформирована для M таких наборов одинаковой мощности N. По выборке вычислены среднее геометрическое со статистиками, характеризующими разброс: границы 97% доверительного интервала, а также первый и третий квартили. Приведено описание алгоритмов стохастической генерации набора нагрузок заданной мощности, а также сбора статистических данных и вычисления статистических оценок отношения времени работы прямого и жадного алгоритма ко времени работы инкрементального алгоритма. Выполнена серия экспериментов, в которых N изменяется в диапазоне 1, 2…9, 10, 26, 42… 170. Результаты серии экспериментов, визуализированные с помощью графиков с использованием библиотеки Highcharts, показали, что инкрементальных алгоритм по скорости превзошел прямой и жадный алгоритмы, причем на диапазоне мощностей наборов нагрузок 10–170 этот вывод статистически достоверен (уровень 97%). Разработанный инкрементальный алгоритм предназначен для использования в решении задач машинного обучения алгебраических байесовских сетей.

1. Wang X.D. Data mining in network engineering-Bayesian networks for data mining // Proc. Int. Conf. on Education, Management, Commerce and Society. Shenyang, China, 2015. V. 17. P. 412–417.
2. Benferhat S., Tabia K. Inference in possibilistic network classifiers under uncertain observations // Annals of Mathematics and Artificial Intelligence. 2012. V. 64. N 2–3. P. 269–309. doi: 10.1007/s10472-012-9290-1
3. Stratford D.S., Croft K.M., Pollino C.A. Knowledge representation using Bayesian networks and ontologies // Proc. 20th Int. Congress on Modelling and Simulation (ModSim 2013). Adelaide, Australia, 2013. P. 2980–2986.
4. Lockamy A., McCormack K. Modeling supplier risks using Bayesian networks // Industrial Management & Data Systems. 2012. V. 112. N 1–2. P. 313–333. doi: 10.1108/02635571211204317
5. Axelrad E.T., Sticha P.J., Brdiczka O., Shen J.Q. A Bayesian network model for predicting insider threats // Proc. 2nd IEEE CS Security and Privacy Workshops (SPW 2013). San Francisco, USA, 2013. P. 82–89. doi: 10.1109/SPW.2013.35
6. Hu Y., Zhang X.Z., Ngai E.W.T., Cai R.C., Liu M. Software project risk analysis using Bayesian networks with causality constraints // Decision Support Systems. 2013. V. 56. P. 439–449. doi: 10.1016/j.dss.2012.11.001
7. Xu C., Xu G.Q., Li X.H., Feng Z.Y., Meng Z.P. Approach to security attack pattern networks on the basis of Bayesian networks // Applied Mathematics & Information Sciences. 2013. V. 7. P. 233–241.
8. Wu X., Wen X.Y., Li J., Yao L. A new dynamic Bayesian network approach for determining effective con-nectivity from fMRI data // Neural Computing & Applications. 2014. V. 24. N 1. P. 91–97. doi: 10.1007/s00521-013-1465-0
9. Liu K.F.R., Lu C.F., Chen C.W., Shen Y.S. Applying Bayesian belief networks to health risk assessment // Stochastic Environmental Research and Risk Assessment. 2012. V. 26. N 3. P. 451–465. doi: 10.1007/s00477-011-0470-z
10. Forio M.A.E., Landuyt D., Bennetsen E., Lock K., Nguyen T.H.T., Ambarita M.N.D., Musonge P.L.S., Boets P., Everaert G., Dominguez-Granda L., Goethals P.L.M. Bayesian belief network models to analyse and pre-dict ecological water quality in rivers // Ecological Modelling. 2015. V. 312. P. 222–238. doi: 10.1016/j.ecolmodel.2015.05.025
11. Murray J.V., Stokes K.E., van Klinken R.D. Predicting the potential distribution of a riparian invasive plant: the effects of changing climate, flood regimes and land-use patterns // Global Change Biology. 2012. V. 18. N 5. P. 1738–1753. doi: 10.1111/j.1365-2486.2011.02621.x
12. Francis R.A., Guikema S.D., Henneman L. Bayesian belief networks for predicting drinking water distribution system pipe breaks // Reliability Engineering & System Safety. 2014. V. 130. P. 1–11. doi: 10.1016/j.ress.2014.04.024
13. Mittal S., Gopal K., Maskara S.L. A novel Bayesian belief network structure learning algorithm based on bio-inspired monkey search meta heuristic // Proc. 2014 7th Int. Conf. on Contemporary Computing (IC3). Noida, India, 2014. P. 141–147.
14. Li S.H., Zhang J., Sun B.L., Lei J. An incremental structure learning approach for Bayesian network // Proc. 26th Chinese Control and Decision Conference (2014 CCDC). Changsha, China, 2014. P. 4817–4822.
15. Samet S., Miri A., Granger E. Incremental learning of privacy-preserving Bayesian networks // Applied Soft Computing. 2013. V. 13. N 8. P. 3657–3667. doi: 10.1016/j.asoc.2013.03.011
16. Sharp A.M. Incremental Algorithms: Solving Problems in a Changing World. PhD Dissertation. Cornell Uni-versity, USA, 2007. 121 p. Available at: http://www.cs.cornell.edu/~asharp/papers/thesis.pdf.
17. Тулупьев А.Л. Алгебраические байесовские сети: глобальный логико-вероятностный вывод в деревь-ях смежности. СПб.: СПбГУ-Анатолия, 2007. 40 с.
18. Тулупьев А.Л., Сироткин А.В., Николенко С.И. Байесовские сети доверия: логико-вероятностный вывод в ациклических направленных графах. СПб.: СПбГУ, 2009. 400 с.
19. Тулупьев А.Л., Столяров Д.М., Ментюков М.В. Представление локальной и глобальной структуры алгебраической байесовской сети в Java-приложениях // Труды СПИИРАН. 2007. № 5. С. 71–99.
20. Опарин В.В., Тулупьев А.Л. Синтез графа смежности с минимальным числом ребер: формализация алгоритма и анализ его корректности // Труды СПИИРАН. 2009. № 11. C. 142–157.
21. Опарин В.В., Фильченков А.А., Сироткин А.В., Тулупьев А.Л. Матроидное представление семейства графов смежности над набором фрагментов знаний // Научно-технический вестник СПбГУ ИТМО. 2010. № 4 (68). С. 73–76.
22. Фильченков А.А. Синтез графов смежности в машинном обучении глобальных структур алгебраиче-ских байесовских сетей. Дис. ... канд. физ.-мат. наук. Самара, 2013. 339 с.
23. Фильченков А.А., Тулупьев А.Л., Сироткин А.В. Минимальные графы смежности алгебраической байесовской сети: формализация основ синтеза и автоматического обучения // Нечеткие системы и мягкие вычисления. 2011. Т. 6. № 2. С. 145–163.
24. Зотов М.А., Тулупьев А.Л. Синтез вторичной структуры алгебраических байесовских сетей: методика статистической оценки сложности и компаративный анализ прямого и жадного алгоритмов // Компь-ютерные инструменты в образовании. 2015. № 1. C. 3–18.
25. Зотов М.А., Тулупьев А.Л., Сироткин А.Л. Статистические оценки сложности прямого и жадного ал-горитмов синтеза вторичной структуры алгебраических байесовских сетей // Нечеткие системы и мяг-кие вычисления. 2015. Т. 10. № 1. С. 75–91.
26. Konstantinou N., Spanos D.E., Kouis D., Mitrou N. An approach for the incremental export of relational da-tabases into RDF graphs // International Journal on Artificial Intelligence Tools. 2015. V. 24. N 2. Art. 1540013. doi: 10.1142/S0218213015400138
27. Wycislik L., Warchal L. A performance comparison of several common computation tasks used in social network analysis performed on graph and relational databases // Man-Machine Interactions 3. 2014. V. 242. P. 651–659. doi: 10.1007/978-3-319-02309-0_70
28. Gao J., Zhou J.S., Yu J.X., Wang T.J. Shortest path computing in relational DBMSs // IEEE Transactions on Knowledge and Data Engineering. 2014. V. 26. N 4. P. 997–1011. doi: 10.1109/TKDE.2013.43
29. Chen R.W. Managing massive graphs in relational DBMS // Proc. IEEE Int. Conf. on Big Data. Santa Clara, 2013. P. 1–8.
30. Park J., Lee S.G. A graph-theoretic approach to optimize keyword queries in relational databases // Knowledge and Information Systems. 2014. V. 41. N 3. P. 843–870. doi: 10.1007/s10115-013-0690-2
 

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License