Control Systems and Computers, N3, 2023, Стаття 2
https://doi.org/10.15407/csc.2023.03.015
Marchenko O.O., Nasirov E.M. Methods of Dimensions Reduction in Text Processing Algorithms. Control Systems and Computers. 2023. № 3. С. 15-23
УДК 681.3.062
O.O. Marchenko, Doctor (physical and math.), professor, head of the department,
International Research and Training Center for Information Technologies and Systems of the NAS and MES of Ukraine, Acad. Glushkov ave., 40, Kyiv, 03187, Ukraine, ORCID: https://orcid.org/ 0000-0002-5408-5279, omarchenko@univ.kiev.ua
E.M. Nasirov, PhD (physical and math.), Senior Research Associate, International Research and Training Center for Information Technologies and Systems of the NAS and MES of Ukraine, Acad. Glushkov ave., 40, Kyiv, 03187, Ukraine, ORCID: https://orcid.org/0009-0006-9016-2602, enasirov@gmail.com
МЕТОДИ ЗМЕНШЕННЯ РОЗМІРНОСТІ В АЛГОРИТМАХ ОБРОБКИ ТЕКСТІВ
Вступ. Методи зменшення розмірності є дуже важливим кроком у процесі кластеризації текстів. Вирішення такої задачі є складним через велику розмірність даних. Такий простір з великими розмірами знижує ефективність процесу загалом. Ідея цих методів полягає в тому, щоб зменшити розміри наявних об’єктів, перетворивши їх в новий простір з низькорозмірними об’єктами. Сучасними та широко вживаними методами зменшення розмірності є такі методи, як NMF та SVD.
Мета статті. Дослідити переваги та недоліки методів зменшення розмірності для застосування в алгоритмах обробки текстів, порівняти обчислювальну складність та швидкодію доліджуваних методів.
Методи. Системний підхід, аналіз, теорія складності обчислень.
Результати. Проведено порівняння швидкодії усіченого сингулярного розкладу та невід’ємної матричної факторизації на щільних та розріджених матрицях різних розмірів. За результатами проведених тестувань визначено, що невід’ємна матрична факторизація потребує менше часу для розкладу щільних квадратних матриць. Проте при розкладі розріджених матриць сингулярний розклад виявився швидшим ніж базовий алгоритм невід’ємної матричної факторизації.
Висновки. Невід’ємна факторизація матриць та сингулярний розклад матриць насправді об’єднують групами алгоритмів. Обидва зазвичай використовуються для факторизації нижчого рангу, при цьому мінімізують помилку найменших квадратів порівняно з вхідними даними. Основна відмінність полягає в тому, який базис будує кожен алгоритм.
Завантажити повний текст! (англійською)
Ключові слова: штучний інтелект, комп’ютерна лінгвістика, паралельні обчислення.
- Allab, K., Labiod, L., Nadif, M., 2016. “A semi-NMF-PCA unified framework for data clustering”. IEEE Transactions on Knowledge and Data Engineering, 29(1), pp. 2-16.
https://doi.org/10.1109/TKDE.2016.2606098 - Kuang, D., Choo, J., Park, H., 2015. “Nonnegative matrix factorization for interactive topic modeling and document clustering”. Partitional clustering algorithms, pp. 215-243.
https://doi.org/10.1007/978-3-319-09259-1_7 - Alghamdi, H., Selamat, A., 2015. “Topic modelling used to improve Arabic web pages clustering”. In 2015 International Conference on Cloud Computing (ICCC, IEEE). pp. 1-6.
https://doi.org/10.1109/CLOUDCOMP.2015.7149662 - Hosseini-Asl, E., Zurada, J.M., 2014. “Nonnegative matrix factorization for document clustering: A survey”. In Artificial Intelligence and Soft Computing: 13th International Conference, ICAISC 2014, Zakopane, Poland, June 1-5, 2014, Proceedings, Part II, LNAI 8468,, Springer International Publishing, pp. 726-737.
https://doi.org/10.1007/978-3-319-07176-3_63 - Klinczak, M.N., Kaestner, C.A., 2015. “A study on topics identification on Twitter using clustering algo-rithms”. In 2015 Latin America Congress on Computational Intelligence (LA-CCI), pp. 1-6. IEEE. https://doi.org/10.1109/LA-CCI.2015.7435965
- Deerwester, S., Dumais, S. T., Furnas, G. W., Landauer, T. K., Harshman, R., 1990. “Indexing by latent se-mantic analysis”. Journal of the American society for information science, 41(6), pp. 391-407.
https://doi.org/10.1002/(SICI)1097-4571(199009)41:6<391::AID-ASI1>3.0.CO;2-9 - Dumais, S. T. (1991). “Improving the retrieval of information from external sources”. Behavior research methods, instruments, & computers, 23(2), pp. 229-236.
https://doi.org/10.3758/BF03203370 - Xu, W., Liu, X., Gong, Y., 2003. “Document clustering based on non-negative matrix factorization”. In Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, pp. 267-273.
https://doi.org/10.1145/860435.860485 - Shahnaz, F., Berry, M. W., Pauca, V.P., Plemmons, R.J., 2006. “Document clustering using nonnegative matrix factorization”. Information Processing & Management, 42(2), pp. 373-386. DOI: https://doi.org/10.1016/j.ipm.2004.11.005
- Van De Cruys, T., 2010. A Non-negative Tensor Factorization Model for Selectional Preference Induction. Journal of Natural Language Engineering, T. 16(4), pp. 417-437.
https://doi.org/10.1017/S1351324910000148 - Van de Cruys, T., Rimell, L., Poibeau, T., Korhonen, A., 2012. “Multi-way Tensor Factorization for Unsupervised Lexical Acquisition”. Proceedings of COLING-2012, pp. 2703-2720.
- Lee, D.D., Seung, H.S., 2000. “Algorithms for non-negative matrix factorization”. In NIPS, MIT Press, pp. 556-562.
- Li, X., Wang, S., Cai, Y., 2019. Tutorial: Complexity analysis of singular value decomposition and its variants. https://arxiv.org/abs/1906.12085.
- Golub, Gene H.; Van Loan, Charles F. “Lanczos Methods”. Matrix Computations. Baltimore: Johns Hopkins University Press. 1996, pp. 470-507.
- Marchenko, O.O., Nasirov, E.M., 2021. “Block-Diagonal approach for non-negative factorization of huge sparse linguistic matrices” Proceedings Actual problems of theory of control systems in compures sciences, pp. 72-78 (In Ukrainian).
- Phan, A.H., Cichocki, A., 2008. “Multi-way Nonnegative Tensor Factorization Using Fast Hierarchical Alternating Least Squares Algorithm (HALS)”. In Proceedings 2008 International Symposium on Nonlinear Theory and its Applications, pp.41-44.
Надійшла 06.09.2023
