doi: 10.17586/2226-1494-2020-20-5-755-760


УДК 519.712.2

ПРИМЕНЕНИЕ МЕТОДА K-СРЕДНИХ В ЗАДАЧЕ ОЦЕНКИ ХАРАКТЕРИСТИК ПРОЦЕССА ДЛЯ ВЕБ-ПРИЛОЖЕНИЙ

Евстратов В.В., Ананьевский М.С.


Читать статью полностью 
Язык статьи - русский

Ссылка для цитирования:
Евстратов В.В., Ананьевский М.С. Применение метода K-средних в задаче оценки характеристик процесса для веб-приложений // Научно-технический вестник информационных технологий,механики и оптики. 2020.Т .20. № 5. С. 755–760. doi: 10.17586/2226-1494-2020-20-5-755-760


Аннотация
Предмет исследования. Исследованы подходы к решению задачи оценки характеристик процесса на примере задачи прогнозирования характеристик активности пользователей в компьютерных онлайн-играх. Рассмотрены методы машинного обучения и определены потенциальные преимущества алгоритмов кластеризации в применении к рассматриваемой задаче. Исследованы различные метрики качества алгоритмов кластеризации. Метод. На основе гипотезы, возникшей в ходе предварительного анализа данных о пользовательской активности, разработан подход к оценке характеристик процесса, использующий кластеризацию. Собраны данные об активности пользователей, для которых уже известны значения прогнозируемых характеристик. Каждый пользователь представлен в виде пары векторов: первый вектор составлен из его характеристик в первые дни активности, второй – из прогнозируемых характеристик. Векторы, представляющие пользователей в первые дни активности, используются в качестве обучающей выборки для алгоритма K-средних. За подбор параметра K отвечает специально разработанный функционал энтропийного вида, адекватный исследуемой задаче. Выделенным кластерам ставятся в соответствие усредненные по попавшим в них пользователям векторы прогнозируемых характеристик. Эти соответствия используются в качестве прогнозов характеристик для новых пользователей. Основные результаты. Предложен ориентированный на рассмотренный тип данных метод оценки качества кластеризации, позволяющий выбрать наиболее подходящее для целевой задачи число кластеров. Проведен численный эксперимент, демонстрирующий применимость разработанного метода. Практическая значимость. Применение предложенного подхода позволяет прогнозировать одновременно несколько характеристик пользователей компьютерных онлайн-игр, и, таким образом, решать различные прикладные задачи планирования и аналитики, возникающие в ходе разработки. Например, изложенный в статье метод был использован в задачах анализа окупаемости разработки новых игровых элементов и прогнозирования нагрузки на серверы с целью заблаговременного наращивания мощностей. Его преимуществами являются отсутствие необходимости экспертной разметки обучающей выборки и относительно невысокие требования к вычислительным мощностям – в силу низкой вычислительной сложности функционала качества для подбора гиперпараметра K.

Ключевые слова: кластеризация, K-Means, алгоритм K-средних, оценка качества кластеризации, энтропия, машинное обучение, алгоритмы, веб

Благодарности. Исследование выполнено при финансовой поддержке Российского фонда фундаментальных исследований в рамках научного проекта (грант № 19-08-00865 А).

Список литературы
1. Zhang Z., Lai Z., Xu Y., Shao L., Wu J., Xie G.-S. Discriminative elastic-net regularized linear regression // IEEE Transactions on Image Processing. 2017. V. 26. N 3. P. 1466–1481. doi: 10.1109/TIP.2017.2651396
2. Olive D.J. Linear Regression. Springer, 2017. IX, 494 p. doi: 10.1007/978-3-319-55252-1
3. Xu J., Xu C., Zou B., Tang Y.Y., Peng J., You X. New incremental learning algorithm with support vector machines // IEEE Transactions on Systems, Man, and Cybernetics: Systems. 2019. V. 49. N 11. P. 2230–2241. doi: 10.1109/TSMC.2018.2791511
4. Press S.J., Wilson S. Choosing between logistic regression and discriminant analysis // Journal of the American Statistical Association. 1978. V. 73. N 364. P. 699–705. doi: 10.1080/01621459.1978.10480080
5. Friedman J., Hastie T., Tibshirani R. Additive logistic regression: A statistical view of boosting // Annals of Statistics. 2000. V. 28. N 2. P. 337–407. doi: 10.1214/aos/1016218223
6. Subramaniyaswamy V., Logesh R. Adaptive KNN based recommender system through mining of user preferences // Wireless Personal Communications. 2017. V. 97. N 2. P. 2229–2247. doi: 10.1007/s11277-017-4605-5
7. Cheung D.W., Kao B., Lee J. Discovering user access patterns on the World Wide Web // Knowledge-Based Systems. 1998. V. 10. N 7. P. 463–470. doi: 10.1016/S0950-7051(98)00037-9
8. Liu D.-S., Fan S.-J. A modified decision tree algorithm based on genetic algorithm for mobile user classification problem // The Scientific World Journal. 2014. P. 468324.
9. Santra A., Jayasudha S. Classification of web log data to identify interested users using Naïve Bayesian classification // International Journal of Computer Science Issues (IJCSI). 2012. V. 9. N 1. P. 381.
10. Park S., Suresh N.C., Jeong B.-K. Sequence-based clustering for web usage mining: A new experimental framework and ann-enhanced k-means algorithm // Data & Knowledge Engineering. 2008. V. 65. N 3. P. 512–543. doi: 10.1016/j.datak.2008.01.002
11. Medina-Ortiz D., Contreras S., Quiroz C., Asenjo J.A., OliveraNappa Á. DMAKit: A user-friendly web platform for bringing stateof-the-art data analysis techniques to non-specific users // Information Systems. 2020. V. 93. P. 101557. doi: 10.1016/j.is.2020.101557
12. Meroño-Peñuela A. Refining Statistical Data on the Web. CreateSpace Independent Publishing Platform, 2016. 252 p.
 13. Nithya P., Sumathi P. Novel pre-processing technique for web log mining by removing global noise and web robots // Proc. of the National Conference on Computing and Communication Systems (NCCCS 2012). 2012. P. 41–45. doi: 10.1109/NCCCS.2012.6412976
14. Kanungo T., Mount D.M., Netanyahu N.S., Piatko C.D., Silverman R., Wu A.Y. An efficient k-means clustering algorithm: Analysis and implementation // IEEE Transactions on Pattern Analysis and Machine Intelligence. 2002. V. 24. N 7. P. 881–892. doi: 10.1109/TPAMI.2002.1017616
15. Yang S.-L., Li Y.-S., Hu X.-X., Pan R.-Y. Optimization study on k value of k-means algorithm // Xitong Gongcheng Lilun yu Shijian/ System Engineering Theory and Practice. 2006. V. 26. N 2. P. 97–101. (in Chinese)
16. Syakur M., Khotimah B., Rochman E.M.S., Satoto B.D. Integration k-means clustering method and elbow method for identification of the best customer profile cluster // IOP Conference Series: Materials Science and Engineering. 2018. V. 336. N 1. P. 012017. doi: 10.1088/1757-899X/336/1/012017
17. Thinsungnoen T., Kaoungku N., Durongdumronchai P., Kerdprasop K., Kerdprasop N. The clustering validity with silhouette and sum of squared errors // Proc. 3rd International Conference on Industrial Application Engineering (ICIAE 2015). 2015. P. 44–51. doi: 10.12792/iciae2015.012
18. Menardi G. Density-based Silhouette diagnostics for clustering methods // Statistics and Computing. 2011. V. 21. N 3. P. 295–308. doi: 10.1007/s11222-010-9169-0


Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Информация 2001-2024 ©
Научно-технический вестник информационных технологий, механики и оптики.
Все права защищены.

Яндекс.Метрика