Аннотация.

В работе приведены результаты реализации модуля определения параметров сложной нагрузки на самоадаптирующиеся контейнеры данных. Представлено обоснование выбора модификации алгоритма ЕМ и алгоритма инициализации kmeans++, дано краткое описание работы программы. Помимо этого, проведен анализ качества кластеризации (для одного и нескольких кластеров, смещения и устаревания данных) и времени работы модуля. Исходя из результатов тестирования, можно сказать, что модуль хорошо справляется с задачей определения параметров сложной нагрузки и может быть эффективно использован в самоадаптирующихся контейнерах данных.

Ключевые слова:

хранение данных, эффективность кэша, самоадаптирующийся контейнер данных, нагрузка на контейнер, смесь нормальных распределений, кластеризация, ЕМ алгоритм, алгоритм k-средних.

Стр. 87-95.

DOI 10.14357/20718632190108

Полная версия статьи в формате pdf. 

Литература

1. Потапов Д. Р., Артемов М.А., Барановский Е.С. Обзор условий адаптации самоадаптирующихся ассоциативных контейнеров данных // Вестник вгу, серия: системный анализ и информационные технологии. Воронеж, 2017. №1. С. 112-119.
2. Зобов В. В., Селезнев К.Е. Инструмент для моделирования нагрузки на контейнеры данных // Материалы четырнадцатой научно-методической конференции «Информатика: проблемы, методология, технологии». — Воронеж, 2014. – Т. 3. – С. 154–161.
3. Потапов Д. Р. Обзор методов построения многомерных контейнеров данных «ключ-значение» для использования в самоадаптирующихся контейнерах данных // Прикладная информатика, 2018. №2(74). С. 69-82.
4. Потапов Д. Р., Артемов М.А., Барановский Е.С., Селезнев К.Е. Обзор методов построения контейнеров данных «ключ-значение» для использования в самоадаптирующихся контейнерах данных // Кибернетика и программирование, 2017. №5. С. 14-45.
5. Потапов Д. Р. Исследование эффективности применения кеша для использования в самоадаптирующихся контейнерах данных // ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ // Принято к печати.
6. Bishop C. Pattern Recognition and Machine Learning. — Heidelberg: Springer, 2006. 738 p.
7. McLachlan G., Peel D. Finite Mixture Models. — NY: John Wiley & Sons, 2004. 419 p.
8. Королёв В.Ю. ЕМ-алгоритм, его модификации и их применение к задаче разделения смесей вероятностных распределений. Теоретический обзор. — М.: Изд-во ИПИ РАН, 2007. 102 с.
9. McLachlan G., Krishnan T. The EM algorithm and extensions. Wiley series in probability and statistics. — NY: John Wiley & Sons, 1997. 400 p.
10. Blomer J., Bujna K. Simple methods for initializing the EM algorithm for Gaussian mixture models. // Computing Research Repository, 2013. http://arxiv.org/abs/1312.5946
11. Baudry J.-P., G. Celeux. EM for Mixtures. // Statistics and Computing, 2015. Vol. 25. No. 4. P. 713–726.
12. Melnykov V., Melnykov I. Initializing the EM algorithm in Gaussian mixture models with an unknown number of components. // Computational Statistics & Data Analysis, 2012. Vol. 56. No.6. P. 1381-1395.
13. Biernacki C., Celeux G., Govaert G. Choosing starting values for the EM algorithm for getting the highest likelihood in multivariate Gaussian mixture models. // Computational Statistics & Data Analysis, 2003. Vol. 41. No. 3-4. P. 561–575.
14. Meila M., Heckerman D. An Experimental Comparison of Several Clustering and Initialization Methods. // Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence, 1998. P. 386–395.
15. Arthur D., Vassilvitskii S. K-means++: The Advantages of Careful Seeding. // Proceedings of the 8th Annual ACMSIAM Symposium on Discrete Algorithms, 2007. P. 1027–1035.
16. Bahmani B., Moseley B., Vattani A., Kumar R., Vassilvitskii S. Scalable k-means++. // Proceedings of the VLDB Endowment, 2012. Vol.5. No.7. P.622-633.
17. Zhao W., Ma H., He Q. Parallel K-means clustering based on mapReduce. // Proceedings of the 1st International Conference on Cloud Computing, 2009. Vol. 5931. P. 674–679.
18. Xu Y., Qu W., Li Z., Ji C., Li Y., Wu Y. Fast Scalable kmeans++Algorithm with MapReduce. // Algorithms and Architectures for Parallel Processing. ICA3PP 2014, 2014. Vol. 8631. P. 15-28.
19. Aggarwal C.C., Han J., Wang J., Yu P.S. A framework for clustering evolving data streams. // Proceedings of the 29th international conference on Very large data bases, 2003. P. 81-92.
20. Liang P., Klein D. Online EM for unsupervised models //Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, 2009. P. 611-619.
21. Unsupervised machine learning with multivariate Gaussian mixture model which supports both offline data and real-time data stream. https://github.com/lukapopijac/gaussian-mixture-model
22. Круглов В. М., Королев В. Ю. Предельные теоремы для случайных сумм. М.: Изд-во Моск. ун-та, 1990. 269 с.
23. Гмурман В. Е. Теория вероятностей и математическая статистика: учебник для прикладного бакалавриат. М.: Издательство Юрайт, 2014. 479 с.
24. Bradley P.S., Fayyad U. M., Reina C. A. Scaling EM (Expectation-Maximization) Clustering to Large Databases. Microsoft Research Technical Report MSR-TR-98-35, 1999.