So sánh các độ đo trong phân cụm văn bản tiếng Việt

Distance Number of clusters Number of noise points Cluster Object 4 Euclidean 1 9 574 2 12 3 4 4 1401 City-Block 1 7 1761 2 9 3 4 4 24 5 195 Cosine 0 2000 Jaccard 0 2000 Chebyshev 0 2000 Kết quả phân cụm với các tham số minpts = 4 được trình bày trong bảng 4 cho thấy rằng với tập dữ liệu đã sử dụng, phép đo Cosine, Jaccard và Chebyshev không phân cụm cho các đối tượng. Phép đo Euclidean mang lại cho chúng ta kết quả tốt hơn với ít các đối tượng gây nhiễu, trong khi City-Block không cho ra kết quả tốt khi cho 5 cụm nhưng các đối tượng ít phân cụm hơn và nhiều đối tượng gây nhiễu. VI. KẾT LUẬN Phân cụm văn bản đã được áp dụng rất nhiều trong các ứng dụng thực tế như phân tích gen, tìm kiếm thông tin, phân loại văn bản tự động hoặc trích xuất chủ đề văn bản tự động. Kết quả phân cụm văn bản phụ thuộc nhiều vào các quá trình như tiền xử lý văn bản (tách từ), lựa chọn các giải thuật phân cụm và độ đo khoảng cách giữa các băn bản. Đối với văn bản tiếng Việt, việc tách các từ trở nên khó khăn hơn so với ngôn ngữ tiếng Anh do bản chất của từ trong tiếng Việt được cấu tạo bởi một hoặc nhiều âm tiết. Hơn nữa, các từ ghép đã gây ra những trùng lặp nhập nhằng làm cho việc tách từ càng trở nên khó khăn hơn. Trong nghiên cứu này chúng tôi tập trung nghiên cứu các phương pháp, kỹ thuật phân cụm dữ liệu và so sánh các độ đo khoảng cách văn bản trên dữ liệu văn bản tiếng Việt. Nhờ đó, chúng ta có thể đánh giá, so sánh các độ đo khoảng cách văn bản sử dụng trong các thuật toán. Chúng tôi đã tiến hành thử nghiệm trên tập dữ liệu 2,000 bài báo được đăng tải trên các trang báo điện tử tiếng Việt. Tập dữ liệu trải qua bước tiền xử lý bao gồm các bước tách từ sử dụng công cụ vnTokenizer kết hợp mô hình BoW thu được kết quả ma trận tần suất xuất hiện các term có 32,185 cột. Trong nghiên cứu này chúng tôi chỉ tập trung vào các phương pháp phân cụm phổ biến như HC, Density-based và Partitioning. Kết quả thực nghiệm trên các thuật toán phổ biến cho thấy thuật toán HDBSCAN và các thuật toán HC cho kết quả phân cụm tốt đối với độ đo khoảng cách Euclidean. Giải thuật PAM kết hợp với độ đo Chebyshev với tham số k=3 cho ra kết quả tốt nhất so với các kết hợp còn lại. REFERENCE [1] A. K. Jain and R. C. Dubes, Algorithms for Clustering data. Prentice Hall, 1988. [2] R. Sharan and R. Shamir, “CLICK: a clustering algorithm with applications to gene expression analysis.,” Proceedings. Int. Conf. Intell. Syst. Mol. Biol., vol. 8, pp. 307-16, 2000. [3] N. Jardine and C. J. V. A. N. Rijsbergen, “The use of hierarchic clustering in Information retrieval,” vol. 7, pp. 217- 240, 1971. [4] A. GRIFFITHS, L. A. ROBINSON, and P. WILLETT, “Hierarchic agglomerative clustering methods for automatic document classification,” J. Doc., vol. 40, no. 3, pp. 175-205, 1993. [5] K. Wang, S. Zhou, and Y. He, “Classification of Real Life Documents,” Proc. 2001 SIAM Int. Conf. Data Min., pp. 1-16, 2001. [6] J. Silva, J. Mexia, A. Coelho, and G. Lopes, “Document clustering and cluster topic extraction in multilingual corpora,” pp. 513-520, 2002. [7] Fung, B. C. M., Wang, K., & Ester, M. (2011). Hierarchical Document Clustering. Encyclopedia of Data Warehousing and Mining, Second Edition, 970-975. https://doi.org/10.4018/978-1-60566-010-3.ch150 [8] Huang, A. (2008). Similarity measures for text document clustering. New Zealand Computer Science Research Student Conference (NZCSRSC), 49-56. [9] Dhillon, I., Kogan, J., & Nicholas, C. (2013). Feature Selection and Document Clustering. In Survey of Text Mining (pp. 73-100). https://doi.org/10.1007/978-1-4757-4305-0_4 422 SO SÁNH CÁC ĐỘ ĐO TRONG PHÂN CỤM VĂN BẢN TIẾNG VIỆT [10] Zamir, O., & Etzioni, O. (1998). Web Document Clustering: A Feasibility Demonstration. In Proceedings of ACM SIGIR conference on Research and Development in Information Retrieval (SIGIR) (pp. 46-54). https://doi.org/10.1145/290941.290956. [11] Shahnaz, F., Berry, M. W., Pauca, V. P., & Plemmons, R. J. (2006). Document clustering using nonnegative matrix factorization. Information Processing and Management, 42(2), 373-386. https://doi.org/10.1016/j.ipm.2004.11.005. [12] P. Berkhin, “A survey of clustering data mining techniques,” Group. Multidimens. Data Recent Adv. Clust., no. c, pp. 25-71, 2006. [13] S. Guha, R. Rastogi, and K. S. Cure, “An efficient clustering algorithm for large databases,” Proc. ACM SIGMOD Int. Conf. Manag. Data, vol. 2, no. 1, pp. 73-84, 1998. [14] S. Guha, R. Rastogi, and K. Shim, “Rock: a robust clustering algorithm for categorical attributes,” Inf. Syst., vol. 25, no. 5, pp. 345-366, 2000. [15] L. Kaufman and P. J. Rousseeuw, “Agglomerative Nesting (Program AGNES),” in Finding Groups in Data: An Introduction to Cluster Analysis, John Wiley & Sons, Inc, 1990, pp. 199-252. [16] L. Kaufman and P. J. Rousseeuw, “Divisive Analysis (Program DIANA),” in Finding Groups in Data: An Introduction to Cluster Analysis, John Wiley & Sons, Inc, 1990, pp. 253-279. [17] G. Karypis Eui-Hong Han Vipin Kumar, “CHAMELEON: A Hierarchical Clustering Algorithm Using Dynamic Modeling,” 1999. [18] J. MacQueen et al., “Some methods for classification and analysis of multivariate observations,” in Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, Oakland, CA., 1967 [19] L. Kaufman and P. J. Rousseeuw, “Partitioning Around Medoids (Program PAM),” in Finding Groups in Data: An Introduction to Cluster Analysis, John Wiley & Sons, Inc, 1990, pp. 68-125. [20] L. Kaufman and P. J. Rousseeuw, “Clustering Large Applications (Program CLARA),” in Finding Groups in Data: An Introduction to Cluster Analysis, John Wiley & Sons, Inc, 1990, pp. 126-163. [21] J. Han, M. Kamber, and J. Pei, Data mining Concepts and Techniques, 3rd ed. Morgan Kaufmann, 2012. [22] A. Huang, “Similarity measures for text document clustering,” New Zeal. Comput. Sci. Res. Student Conf., pp. 49- 56, 2008. [23] R. T. Ng and J. Han, “CLARANS: A method for clustering objects for spatial data mining,” IEEE Trans. Knowl. Data Eng., vol. 14, no. 5, pp. 1003-1016, 2002. [24] L. H. Phuong, N. T. M. Huyên, A. Roussanaly, and H. T. Vinh, “A hybrid approach to word segmentation of Vietnamese texts,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 5196 LNCS, pp. 240-249, 2008. [25] R. J. G. B. Campello, D. Moulavi, and J. Sander, “Density-based clustering based on hierarchical density estimates,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 7819 LNAI, no. PART 2, pp. 160-172, 2013. [26] Doan Mau Hien. Automatically assigning labels to books. Can Tho University, 2016. COMPARISON OF DIFFERENT MEASURES IN VIETNAMESE TEXT DOCUMENT CLUSTERING To Khanh Toan, Vo Hai Dang, Tran Thi Cam Tu, Truong Quoc Dinh, Huynh Xuan Hiep ABSTRACT: Document clustering is the process of grouping documents with similar features or attributes in a dataset into clusters so that the document in the same cluster are similar to each other. Document clustering plays an important role in several areas such as automatic text sorting, automatic text extracting, or searching and extraction of information. Many clustering algorithms have been proposed in the study of text clustering. Each algorithm using distance or similarity measurements to determine how a document similar to others. Therefore, choosing an inappropriate measurement would result in unexpected clusters. In this paper, we focused on comparing clustering measures used in prevalent algorithms such as HDBSCAN, PAM and Hierarchical Clustering in order to find a well-suite measurement for clustering algorithms. The study compared the clustering algorithms using the Euclidean, City-Block, Cosine, Jaccard and Chebyshev measurements on a dataset of 2,000 documents collected randomly from two online newspapers sites vietpress.net and vietnamnet.vn. The experimental results showed that the HDBSCAN algorithm combined with Euclidean measurement yielded the best results compared to the remaining combinations; The measurement of Chebyshev archived the best results on the PAM algorithm with k = 3.