Xem mẫu
- 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.
nguon tai.lieu . vn
