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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:9

Thêm vào BST

Báo xấu

28
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết trình bày tập trung nghiên cứu so sánh các độ đo sử dụng trong các giải thuật phân cụm phổ biến như HDBSCAN, PAM và Hierarchical Clustering để tìm độ đo thích hợp cho các thuật toán. Nghiên cứu thực hiện so sánh các giải thuật phân cụm sử dụng các độ đo Euclidean, City-Block, Cosine, Jaccard Coefficient và Chebyshev trên tập dữ liệu gồm 2,000 văn bản được thu thập ngẫu nhiên từ hai trang báo điện tử vnexpress.net và vietnamnet.vn.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Huế, ngày 07-08/6/2019 DOI: 10.15625/vap.2019.00053 SO SÁNH CÁC ĐỘ ĐO TRONG PHÂN CỤM VĂN BẢN TIẾNG VIỆT Tô Khánh Toàn1, Võ Hải Đăng2, Trần Thị Cẩm Tú3, Trƣơng Quốc Định2, Huỳnh Xuân Hiệp2 1 Khoa Công nghệ thông tin, Trường Đại học Bạc Liêu 2 Khoa Công nghệ thông tin và Truyền thông, Trường Đại học Cần Thơ 3 Khoa Công nghệ thông tin, Trường Đại học Sư phạm Kỹ thuật Vĩnh Long tktoan@blu.edu.vn, vhdang@ctu.edu.vn, tuttc@vlute.edu.vn, tqdinh@ctu.edu.vn, hxhiep@ctu.edu.vn TÓM TẮT: Phân cụm văn bản là quá trình nhóm các tập văn bản có các tính chất tương tự nhau trong một tập dữ liệu vào các cụm sao cho các văn bản trong cùng một cụm có các tính chất tương đồng nhau. Phân cụm văn bản đóng vai trò quan trọng trong các lĩnh vực như phân loại văn bản tự động, trích xuất chủ đề văn bản tự động hay tìm kiếm và trích lọc thông tin. Có nhiều giải thuật phân cụm đã được đề xuất trong các nghiên cứu về phân cụm văn bản. Mỗi thuật toán sử dụng các độ đo tương tự hay độ đo khoảng cách để xác định một văn bản giống hay khác biệt với các văn bản khác. Do đó việc chọn độ đo không phù hợp sẽ cho ra kết quả phân cụm không mong muốn. Trong bài báo này chúng tôi tập trung nghiên cứu so sánh các độ đo sử dụng trong các giải thuật phân cụm phổ biến như HDBSCAN, PAM và Hierarchical Clustering để tìm độ đo thích hợp cho các thuật toán. Nghiên cứu thực hiện so sánh các giải thuật phân cụm sử dụng các độ đo Euclidean, City-Block, Cosine, Jaccard Coefficient và Chebyshev trên tập dữ liệu gồm 2,000 văn bản được thu thập ngẫu nhiên từ hai trang báo điện tử vnexpress.net và vietnamnet.vn. Kết quả thực nghiệm cho thấy giải thuật HDBSCAN kết hợp độ đo Euclidean cho ra kết quả tốt nhất so với các kết hợp còn lại; Độ đo Chebyshev cho ra kết quả tốt nhất trên giải thuật PAM với k=3. Từ khóa: HDBSCAN, PAM, Hierarchical Clustering, Euclidean, Jaccard Coefficient, Cosine, City-Block, Chebyshev, phân cụm văn bản tiếng Việt. I. PHÂN CỤM VĂN BẢN TIẾNG VIỆT Phân cụm (clustering) văn bản là một trong những bước quan trọng trong quá trình khai mỏ dữ liệu văn bản (text- mining). Theo Jain và Dubes [1], quá trình phân cụm văn bản là việc tự động nhóm các văn bản vào các cụm (clusters) sao cho các văn bản trong cùng một cụm có các đặc trưng (features) hoặc thuộc tính (attributes) giống nhau, các văn bản ở khác cụm có các đặc trưng khác nhau. Phân cụm và phân lớp (classification) là hai phương pháp phổ biến để phân loại văn bản tự động. Không giống như phân lớp, phân cụm văn bản không có dữ liệu học. Do đó, phương pháp phân cụm được gọi là học không giám sát (unsupervised learning), còn phương pháp phân lớp được gọi là học có giám sát (supervised learning). Trong phân loại văn bản, phương pháp phân cụm tỏ ra hiệu quả khi không có thông tin các nhóm trong dữ liệu văn bản được cho. Các giải thuật phân cụm sẽ thực hiện các bước học trên dữ liệu quan sát dựa vào các đặc trưng của dữ liệu để phân nhóm. Thuật toán phân cụm được ứng dụng rất nhiều vào trong các lĩnh vực như phân tích gen [2], tìm kiếm thông tin [3], phân loại văn bản tự động [4], [5] hoặc trích xuất chủ đề văn bản tự động [6]. Để phân cụm văn bản, trước tiên dữ liệu phải trải qua các bước tiền xử lý bao gồm loại bỏ các từ không quan trong (stop words), tách từ (word segmentation) và chuyển thể từ (stemming & lemmatization). Mỗi văn bản sau khi tiền xử lý sẽ được biểu diễn bởi một véc-tơ trong không gian nhiều chiều, mỗi chiều tương ứng với một từ hoặc cụm từ (term) xuất hiện trong văn bản. Bài toán phân cụm văn bản là một bài toán kinh điển, đã có nhiều công trình nghiên cứu được công bố [[8] - [11]]. Phần lớn các công trình nghiên cứu trên ngôn ngữ tiếng Anh. Quá trình phân cụm dữ liệu là một chuỗi các bước, trong đó bước đầu tiên là các đối tượng trong tập dữ liệu cần phải được trích xuất các đặc trưng hay các thuộc tính. Đối với văn bản, các đặc trưng này là các term xuất hiện trong tập dữ liệu văn bản. Thông thường đối với ngôn ngữ tiếng Anh, việc tách từ dựa vào khoảng trắng để xác định phạm vi của từ. Tuy nhiên đối với văn bản tiếng Việt, việc xác định ra giới của từ phức tạp hơn bởi đặc điểm của ngôn ngữ tiếng Việt từ được phân loại thành các từ đơn, từ phức, từ ghép. Công đoạn tách từ tiếng Việt gặp phải một số trở ngại như sự nhập nhằng trùng lặp. Lấy ví dụ, cụm từ “đĩa thịt bò” có thể được tách ra thành [“đĩa”, “thịt”, “bò”] hoặc là [“đĩa thịt”, “bò”] hay [“đĩa”, “thịt bò”] vì tất cả đều có nghĩa. Kỹ thuật phân cụm văn bản biểu diễn mỗi văn bản di như một vector m chiều, trong đó m chính là số lượng các term trong tập dữ liệu D={d1,…dn}. Do vậy, mô hình tính toán của các giải thuật là bài toán trong không gian nhiều chiều. Việc tính toán trên mô hình không gian có số chiều lớn trở nên khó khăn và mất rất nhiều thời gian. Trong kỹ thuật phân cụm, một văn bản di được gom vào một cụm Ci khi nó “tương tự” với các văn bản trong cụm đó. Để xác định di giống nhau hay khác biệt với dj người ta sử dụng các độ đo tương tự/khác biệt (similarity/dissimilarity) hay độ đo khoảng cách giữa các văn bản. Ví dụ giải thuật K-Means [18] dựa vào độ đo khoảng cách giữa các đối tượng để xác định tâm của cụm, hay thuật toán DBSCAN [21] tìm các láng giềng trong bán kính . Có nhiều phương pháp để xác định khoảng cách trong không gian, ví dụ khoảng cách Euclidean, khoảng cách Manhattan, hay khoảng cách Minkowski. Do đó, việc quyết định độ đo cũng sẽ ảnh hưởng đến kết quả phân cụm văn bản rất nhiều. Theo Berkhin [12], phương pháp phân cụm được chia thành các nhóm: Hierarchical Clustering (HC), Partitional Clustering, Density-based và Grid-based. Ứng với mỗi phương pháp phân cụm có nhiều giải thuật được đề xuất như
Tô Khánh Toàn, Võ Hải Đăng, Trần Thị Cẩm Tú, Trương Quốc Định, Huỳnh Xuân Hiệp 415 AGNES [15], DIANA [16], CURE [13], CHAMELEON [17], k-means [18], PAM [19], HDBSCAN [25], DBSCAN, STING, WaveCluster và CLIQUE [21]. Trong bài báo này chúng tôi tập trung nghiên cứu so sánh các độ đo sử dụng trong các phương pháp phân cụm phổ biến là HC, Partitional Clustering và Density-based trên giải thuật phân cụm tiêu biểu như HDBSCAN, PAM và AGNES để tìm độ đo thích hợp cho các thuật toán. Các độ đo được so sánh trên các kỹ thuật phân cụm gồm có Euclidean, City-Block, Cosine, Jaccard Coefficient và Chebyshev. II. PHƢƠNG PHÁP PHÂN CỤM VĂN BẢN Berkhin [12] chia các phương pháp phân cụm thành các nhóm: Hierarchical, Partitioning, Density và Grid-based. Với mỗi phương pháp phân cụm có nhiều giải thuật đã được đề xuất, trong phần này chúng tôi trình bày một số phương pháp và giải thuật phân cụm văn bản phổ biến thường được sử dụng. Phƣơng pháp Hierarchical clustering Phân cụm phân cấp (hierarchical clustering) là phương pháp phân cụm dữ liệu bằng cách gom các đối tượng thành các cụm có cấp bậc dựa trên độ tương đồng của các đối tượng trong dữ liệu. Thứ tự cấp bậc của các cụm này tạo thành một cấu trúc cây dendrogram. Có hai hướng tiếp cận đối với phương pháp phân cụm phân cấp: Agglomerative và Divisive [21]. Agglomerative clustering Đây là phương pháp tiếp cận từ dưới lên (bottom-up). Ban đầu mỗi đối tượng được xem như là một cluster riêng lẻ. Ở mỗi bước lặp, các đối tượng gần nhau sẽ được gộp lại thành một cluster. Quá trình này lặp lại cho đến khi tất cả các đối tượng được gộp lại thành một cluster duy nhất. Divisive clustering Ngược lại với agglomerative, đây là phương pháp tiếp cận từ trên xuống (top-down). Ban đầu tất cả các đối tượng được xem như thuộc cùng một cluster. Bước tiếp theo tiến hành phân chia thành hai cluster con dựa vào khoảng cách của các đối tượng. Tiếp tục đệ quy trên hai cluster con cho đến khi mỗi cluster chỉ còn lại một đối tượng. Hình 1. Phân cụm theo cách tiếp cận top-down/bottom-up và dendrogram biểu diễn cây phân cấp đối tượng {a,b,c,d,e} Để xác định khoảng cách giữa các cluster, các phương pháp xác định liên kết được sử dụng bao gồm: 1) khoảng cách gần nhất giữa 2 đối tượng thuộc 2 clusters (Single linkage); 2) khoảng cách xa nhất giữa hai đối tượng thuộc 2 cluster (Complete linkage); 3) khoảng cách trung bình giữa các đối tượng trong 2 clusters (Average linkage). Hình 2. Tiêu chí xác định khoảng cách cụm Các thuật toán điển hình cho phương pháp phân cụm phân cấp gồm có CURE (Clustering Using REpresentatives) [13], BIRCH (Balance Iterative Reducing and Clustering using Hierarchies), ROCK (Robust Clustering Algorithm for Categorical Attributes) [14], AGNES (Agglomerative Nesting) [15], DIANA (Divisive Analysis) [16] và Chameleon [17].
416 SO SÁNH CÁC ĐỘ ĐO TRONG PHÂN CỤM VĂN BẢN TIẾNG VIỆT Phƣơng pháp Partitional clustering Ý tưởng của phương pháp phân hoạch (partitional clustering) là chia tập hợp D gồm có n đối tượng thành k cụm C (k ≤ n) cho trước dựa vào độ đo thích hợp. Mỗi cụm được xác đinh bởi trọng tâm của cụm. Một đối tượng được gom vào cụm Ci nếu khoảng cách của đối tượng đó tới tâm của cụm Ci là nhỏ nhất. Sau mỗi bước tâm của cụm sẽ được cập nhật lại. Quá trình lặp lại cho đến khi hàm mục tiêu bé hơn một ngưỡng cho phép hoặc tâm của cụm không thay đổi. Hình 3. Ví dụ phân hoạch với k=3 Thuật toán được dùng phổ biến trong phương pháp phân hoạch là K-Means [18] do giải thuật đơn giản, cho ra kết quả dễ hiểu. Giải thuật K-Means được mô tả như sau: Input: k // số cụm mong muốn D = {x1, x2,…,xn} // tập hợp các đối tượng Output: C = {C1, C2,…,Ck} // tập hợp k cluster các đối tượng Begin Khởi tạo ngẫu nhiên k tâm cho k cluster Repeat Gán phần tử xi vào Cj nếu khoảng cách xi đến tâm Cj gần nhất Tính lại tâm của cluster dựa vào giá trị trung bình (mean) của các phân tử trong cluster Dừng nếu tâm cluster không thay đổi End Hình 4. Thuật toán K-Means Giải thuật K-Means có ưu điểm dễ cài đặt. Tuy nhiên nó lại có nhược điểm là khả năng chịu nhiễu không tốt, dễ bị ảnh hưởng bởi các phần tử nhiễu, kì dị. Thuật toán PAM (Partitioning Around Medoids) [19] giảm thiểu sự ảnh hưởng của nhiễu bằng cách chọn tâm của cluster là phần tử nằm giữa cụm (controid) thay vì dựa vào giá trị mean. Ngoài ra, các giải thuật như CLARA (Clustering Large Applications) [20], CLARANS (Clustering Large Applications based on RANdomized Search) [23] cũng cho ra kết quả phân cụm tốt. Phƣơng pháp Density-based clustering Đa số các giải thuật phân cụm theo phương pháp phân hoạch dựa vào khoảng cách giữa các đối tượng. Với cách tiếp cận này, giải thuật có thể phát hiện ra các cụm có hình cầu, nhưng lại gặp khó khăn trong việc khám phá các cụm có hình dạng bất kỳ [21]. Với phương pháp phân cụm dựa trên mật độ, mỗi cụm được xem như một vùng dày đặc (dense region) các đối tượng. Những đối tượng trong vùng thưa hơn được xem là nhiễu. Một đối tượng được phân cụm dựa vào hàm mật độ. Hàm mật độ xác định các đối tượng lân cận một đối tượng đang xét dựa vào tiêu chí xác định. Với phương pháp này, giải thuật phân cụm có thể xác định được các cụm có hình dạng bất kỳ và xử lý các đối tượng nhiễu và kì dị rất tốt. Tuy nhiên, việc xác định các tham số mật độ khá khó khăn vì nó ảnh hưởng đến kết quả phân cụm rất nhiều. Hình 5. Các cụm có hình dạng bất kỳ Các thuật toán điển hình cho phương pháp phân cụm này bao gồm DBSCAN (Density-Based Spatial Clustering of Applications with Noise), HDBSCAN (Hierarchical DBSCAN) [25], OPTICS (Ordering Points to Identify Clustering Structure), DENCLUE (DENsity-based CLUsting) [21].
Tô Khánh Toàn, Võ Hải Đăng, Trần Thị Cẩm Tú, Trương Quốc Định, Huỳnh Xuân Hiệp 417 III. ĐỘ ĐO KHOẢNG CÁCH VĂN BẢN Trong kỹ thuật phân cụm, một đối tượng Oi được gom vào một cụm Cj khi nó có các đặc trưng hay thuộc tính tương đồng với các đối tượng trong Cj và phải khác biệt với các đối tượng ở tất cả các cụm khác. Để xác định các đối tượng Oi “giống” hay “khác” với đối tượng Oj, người ta sử dụng các độ đo tương tự (similarity/disimilarity) hay độ đo khoảng cách giữa Oi và Oj trong không gian nhiều chiều. Cho D={d1, …,dn} là tập các văn bản và T={t1,…,tm} là tập các thuật ngữ (terms) duy nhất trong tập dữ liệu. Một văn bản sau đó được biểu diễn bởi một vector ⃗⃗⃗ trong không gian m chiều: (1) Trong đó tf(d,ti) là tần suất xuất hiện của thuật ngữ ti∈T trong văn bản d ∈ D. Khoảng cách Euclidean Khoảng cách giữa hai văn bản da và db được xác định theo khoảng cách Euclidean là khoảng cách giữa hai vector ⃗⃗⃗ và ⃗⃗⃗ được tính theo công thức: (2) Trong đó wt,a = tf(da,t) x idf(da,t) là trọng số của thuật ngữ t trong tập dữ liệu D. Độ đo khoảng cách Euclidean là trường hợp đặc biệt của độ đo khoảng cách Minkowski khi n = 2. Độ đo tƣơng tự Cosine Độ đo Cosine là độ đo sự tương quan giữa các vector trong không gian. Hai văn bản da và db được biểu diễn bởi hai vector ⃗⃗⃗ và ⃗⃗⃗ thì độ tương tự Cosine chính là cos của góc giữa hai vector được tính theo công thức: (3) Độ tương tự cosine giới hạn trong khoảng [0,1], trong đó nếu giá trị bằng 1 cho biết hai văn bản hoàn toàn giống nhau và ngược lại bằng 0 khi hai văn bản không có liên quan gì đến nhau. Độ đo Jaccard Coefficient Độ đo Jaccard Coefficient của hai văn bản là độ đo tương tự được xác định bằng tỷ số giữa các thuật ngữ giao nhau trên tổng số các thuật ngữ hợp nhau. (4) Độ tương tự Jaccard Coefficient có miền giá trị [0,1], bằng 1 nếu hai văn bản hoàn toàn giống nhau, ngược lại bằng 0 nếu cả hai khác nhau hoàn toàn. Khoảng cách City-Block Khoảng cách City-Block hay còn được gọi là khoảng cách Manhattan, là trường hợp đặc biệt của độ đo khoảng cách Minkowski khi n = 1 được tính theo công thức: (5) Khoảng cách Chebyshev Khoảng cách Chebyshev được biết đến như là khoảng cách bàn cờ vua trong không gian hai chiều được định nghĩa như là số bước ít nhất cần di chuyển quân vua từ một ô của bàn cờ tới ô khác. Cho hai vector p và q, khoảng cách giữa hai vector được tính theo công thức: (6) Trong đó pi và qi là toạ độ của p và q.
418 SO SÁNH CÁC ĐỘ ĐO TRONG PHÂN CỤM VĂN BẢN TIẾNG VIỆT IV. TIỀN XỬ LÝ VĂN BẢN TIẾNG VIỆT Tách từ Không giống như các ngôn ngữ khác, việc tách từ tiếng Việt không thể dựa vào khoảng trắng giữa các từ để phân tách. Trong tiếng Việt, đơn vị nhỏ nhất cấu tạo nên từ là âm tiết. Một từ được tạo bởi một âm tiết (từ đơn) hoặc nhiều âm tiết (từ phức, từ ghép). Theo [24], một cụm từ có thể được chia thành một chuỗi các âm tiết s1, s2,.. sn phân cách nhau bởi khoảng trắng. Thông thường các từ ghép tiếng Việt gồm hai âm tiết, một số trường hợp chúng ta gặp những từ ghép có đến ba âm tiết liên tiếp sisi + 1si + 2 trong đó cả hai phân đoạn (sisi + 1) (si + 2) và (si) (si + 1si + 2) tạo nên các từ có nghĩa tùy thuộc vào ngữ cảnh. Kiểu phân chia âm tiết này được gọi nhập nhằng chồng chéo. Hình 6. Sơ đồ biểu diễn một cụm từ [24] Để giải quyết sự nhập nhằng chồng chéo này, mô hình n-gram được sử dụng cho kết quả tách từ đạt độ chính xác hơn 95% [24]. Mô hình BoW Để phân cụm văn bản tiếng Việt, trước tiên cần chuyển văn bản sang dạng dữ liệu thích hợp. Phương pháp phổ biến được sử dụng để biểu diễn văn bản là mô hình BoW (Bag-of-Words)[26]. Trong mô hình này, tập dữ liệu D={d1, …,dm} và tập các term xuất hiện trong tập dữ liệu T={t1,…,tn} được biểu diễn dưới dạng ma trận Amxn. Trong đó văn bản di được biểu diễn là dòng thứ i và cột j là term thứ j xuất hiện trong tập dữ liệu, và ai,j là tần suất xuất hiện của term j trong văn bản di. Bảng 1. Mô hình BoW biểu diễn tập dữ liệu pin điện …. tn 1 1 0 …. 0 2 0 2 … 0 … … … … … m 4 1 … 1 V. THỰC NGHIỆM Để so sánh các độ đo trên các giải thuật phân cụm trên văn bản tiếng Việt, chúng tôi tiến hành các bước thu thập dữ liệu trên các tờ báo điện tử, tiền xử lý dữ liệu và cài đặt các giải thuật với các độ đo khoảng cách khác nhau. Hình 7. Kiến trúc tổng quan của hệ thống Dữ liệu Chúng tôi sử dụng tập dữ liệu gồm 2,000 bài viết được thu thập ngẫu nhiên từ các trang báo điện tử vnexpress.net và vietnamnet.vn cho mục đích thực nghiệm. Nội dung của các bài viết sau khi được thu thập bao gồm văn bản, hình ảnh và các đối tượng khác được trình bày theo cấu trúc ngôn ngữ HTML. Chỉ có nội dung văn bản được trích xuất để thực hiện phân cụm nội dung bao gồm tiêu đề, phần tóm tắt và nội dung bài viết. Dữ liệu được lưu trữ dưới dạng văn bản thuần
Tô Khánh Toàn, Võ Hải Đăng, Trần Thị Cẩm Tú, Trương Quốc Định, Huỳnh Xuân Hiệp 419 sau khi đã loại bỏ tất cả các thẻ HTML. Bước tiếp theo tập dữ liệu sẽ được xử lý trên mô hình BoW sau khi đã trải qua bước loại bỏ các từ không quan trọng, không mang ý nghĩa phân biệt các nội dung văn bản (stopwords). Kết quả thu được là tập dữ liệu gồm có 32,185 term được biểu diễn bởi ma trận có kích thước 2,000 x 32,185. Hình 8. Tập dữ liệu sau khi tiền xử lý Công cụ Để thực hiện tách từ trong tập dữ liệu, chúng tôi sử dụng công cụ vnTokenizer [24]. Công cụ cho độ chính xác cao lên đến 97% được nhóm tác giả kiểm nghiệm trên tập dữ liệu hai triệu âm tiết. Hình 9. Các từ được tách bởi công cụ vnTokenizer Kết quả thực nghiệm Trong thí nghiệm này, chúng tôi phân cụm nội dung tài liệu tiếng Việt với các giải thuật phân cụm: HBDSCAN, PAM và AGNES (HC) kết hợp lần lượt với các độ đo khoảng cách văn bản khác nhau: Euclidean, City-Block, Cosine, Jaccard, Chebyshev để đánh giá nhằm tìm ra độ đo thích hợp cho các phương pháp phân cụm. Phương pháp Partitional Clustering với giải thuật PAM Trong kỹ thuật phân hoạch với giải thuật PAM, chúng tôi thay đổi lần lượt giá trị K và ghi nhận kết quả như trong bảng 2. Bảng 2. Kết quả phân cụm với giải thuật PAM Euclidean City-Block Cosine Jaccard Chebyshev Clusters 3 3 3 3 3 Objective build 27.64682 267.661 0.848502 27.64682 11.8395 K=3 function swap 27.64682 267.661 0.8428233 27.64682 11.8395 Average silhouette 0.66 -0.25 0.02 0.66 0.74 Clusters 4 4 4 4 4 Objective build 27.36849 266.578 0.8290185 27.36849 11.544 K=4 function swap 27.34718 266.578 0.8290185 27.34718 11.491 Average silhouette 0.54 -0.25 0.03 0.54 0.34 Clusters 5 5 5 5 5 Objective build 27.18758 265.613 0.8140439 27.18758 11.339 K=5 function swap 27.16627 265.613 0.8101618 27.16627 11.2905 Average silhousette 0.25 -0.25 0.04 0.25 0.17
420 SO SÁNH CÁC ĐỘ ĐO TRONG PHÂN CỤM VĂN BẢN TIẾNG VIỆT Kết quả thử nghiệm ở trên cho thấy rằng khi K = 3 kết hợp với độ đo khoảng cách Chebyshev cho kết quả tốt nhất với Average silhouette 0.74. Hình 10. PAM sử dụng K=3 với khoảng cách Chebyshev Phương pháp Hierarchical Clustering Sử dụng kỹ thuật phân cụm HC trên các độ đo khách cách khác nhau chúng tôi thu được kết quả được trình bày như sau: Với kỹ thuật phân cụm Hierachical Clustering thì kết quả phân cụm phụ thuộc vào tham số đầu tương tự như giải thuật PAM. Trong thí nghiệm trên, với kết quả phân cụm kết hợp với phép đo Euclidean chúng tôi chọn khoảng cách bằng 200 (hình 14) với mong muốn có 5 cụm. Chúng tôi nhận được số lượng phần tử trong cụm như Bảng 3: Bảng 3. Số phần tử trong cụm 1 2 3 4 5 Objects 1993 4 1 1 1 Phương pháp Density-based Clustering Sử dụng kỹ thuật phân cụm dựa trên mật độ sử dung giải thuật HDBSCAN với giá trị minpts = 4 chúng tôi có kết quả được trình bày trong Bảng 4
Tô Khánh Toàn, Võ Hải Đăng, Trần Thị Cẩm Tú, Trương Quốc Định, Huỳnh Xuân Hiệp 421 Bảng 4. Kết quả thực nghiệm với minpts = 4 Number of clusters Number of noise points minpts Distance Cluster Object 4 1 9 2 12 574 Euclidean 3 4 4 1401 1 7 2 9 City-Block 3 4 1761 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.