Xem mẫu
- Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XI về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 09-10/8/2018
DOI: 10.15625/vap.2018.00032
LỰA CHỌN CÁC RÀNG BUỘC CHO THUẬT TOÁN PHÂN CỤM NỬA
GIÁM SÁT
Vũ Việt Vũ1, Nguyễn Anh Tuấn2, Lê Thị Kiều Oanh3
1
Viện Công nghệ Thông tin, Đại học Quốc gia Hà Nội
2
Công ty Hệ thống Thông tin (FPT)
3
Trường Đại học Kinh tế Kỹ thuật Công Nghiệp
vuvietvu@vnu.edu.vn, tuanna2@fpt.com.vn, oanhlk2004@gmail.com
TÓM TẮT: Thuật toán phân cụm dựa trên các ràng buộc là một dạng của thuật toán phân cụm nửa giám sát nhằm tích hợp một tập
các ràng buộc để cải tiến quá trình phân cụm. Trên thực tế rất nhiều thuật toán phân cụm nửa giám sát đã được giới thiệu. Tuy
nhiên hầu hết các ràng buộc sử dụng được sinh ngẫu nhiên hoặc giả thiết rằng có sẵn từ ban đầu. Hơn nữa, một số tập ràng buộc
thậm chí có thể làm giảm chất lượng của quá trình phân cụm nếu chúng không được lựa chọn cẩn thận. Trong bài báo này, chúng
tôi đề xuất một thuật toán mới mở rộng từ thuật toán MMFFQS nhằm thu thập các ràng buộc từ người sử dụng, thuật toán mới
được đặt tên là KMMFFQS dựa trên K-Means và phương pháp Min-Max. Kết quả thực nghiệm với các tập dữ liệu thực từ UCI chỉ
ra tính hiệu quả của thuật toán đề xuất.
Từ khóa: Phân cụm nửa giám sát, ràng buộc, học tích cực, K-Means.
I. GIỚI THIỆU
Thuật toán phân cụm (clustering) nhằm phân tách một tập dữ liệu X có n phần tử trong không gian m chiều
thành các cụm sao cho các phần tử trong mỗi cụm thì tương tự nhau theo một độ đo nào đó. Thuật toán phân cụm đóng
vai trò quan trọng trong lĩnh vực khai phá dữ liệu và phát hiện tri thức từ dữ liệu. Mục đích của quá trình phân cụm là
phát hiện ra cấu trúc của tập dữ liệu đang xét, tìm ra mối liên hệ giữa các phần tử và thậm chí trong một số trường hợp
phát hiện ra các phần tử dị thường (outlier). Các thuật toán phân cụm được nghiên cứu và giới thiệu từ những năm 50
của thế kỷ XX. Các thuật toán điển hình có thể kể đến như K-Means, Fuzzy C-Means, thuật toán phân cụm dựa trên đồ
thị (GC), thuật toán phân cụm dựa trên mật độ (DBSCAN) [1],… Mặc dù đã có nhiều thuật toán phân cụm được đề
xuất, tuy nhiên hiện nay chủ đề phân cụm vẫn thu hút nhiều nhà nghiên cứu với mục đích cải tiến chất lượng phân cụm,
đáp ứng với các loại dữ liệu thực tế và phù hợp với các yêu cầu của người sử dụng.
Từ những năm 2000 trở lại đây, phương pháp phân cụm nửa giám sát (semi-supervised clustering) bắt đầu được
nghiên cứu và phát triển mạnh mẽ [2]. Một trong những dạng cơ bản của phân cụm nửa giám sát là các thuật toán sử
dụng ràng buộc. Các ràng buộc là các cặp dữ liệu có dạng must-link hoặc cannot-link trong đó must-link(u,v) với u, v là
các phần tử thuộc tập dữ liệu X thể hiện u và v nên nhóm vào cùng một cụm, trong khi cannot-link(u,v) cho biết u và v
nên thuộc về hai cụm khác nhau. Hình 1 minh họa ví dụ về dữ liệu với các ràng buộc. Một dạng khác của bài toán phân
cụm nửa giám sát cũng được quan tâm đó chính là bài toán phân cụm nửa giám sát sử dụng một số điểm hạt giống
(seed). Các seed ở đây chính là một số điểm đã được gán nhãn sẵn các nhãn của cụm.
Hình 1. Ví dụ về tập dữ liệu (bên trái) và dữ liệu với các ràng buộc (bên phải); các dữ liệu must-link được biểu diễn bằng các
đường nét liền, cannot-link được biểu diễn bằng các đường nét đứt.
Tính đến nay hầu hết các thuật toán phân cụm cơ bản đều đã có các thuật toán phân cụm nửa giám sát tương
ứng, các thuật toán này sử dụng một trong hai dạng hoặc thậm chí cả hai dạng là ràng buộc và seed vào trong cùng một
thuật toán. Chúng tôi có thể kể ra đây thuật toán phân cụm nửa giám sát cho K-Means [3], Fuzzy C-Means [4],
DBSCAN [5], GC [6],… Thuật toán có thể tích hợp cả hai dạng là ràng buộc và seed có thể kể đến như thuật toán
MCSSGC [7] và thuật toán MCSSDBS [8]. Phương pháp sử dụng các ràng buộc tích hợp vào bài toán phân cụm
thường có hai dạng là tích hợp trực tiếp vào quá trình tìm kiếm các cụm hoặc dùng các ràng buộc để huấn luyện một độ
đo khoảng cách sao cho khi chuyển sang không gian độ đo mới thì các điểm thuộc các ràng buộc must-link sẽ xích gần
nhau và các điểm thuộc các ràng buộc cannot-link sẽ xa nhau ra.
- 240 LỰA CHỌN CÁC RÀNG BUỘC CHO THUẬT TOÁN PHÂN CỤM NỬA GIÁM SÁT
Một vấn đề quan trọng phát sinh trong quá trình nghiên cứu các thuật toán phân cụm nửa giám sát là việc lựa
chọn các ràng buộc. Một số kết quả nghiên cứu đã chỉ ra rằng việc lựa chọn các ràng buộc tốt sẽ tăng đáng kể chất
lượng phân cụm tuy nhiên nếu tập các ràng buộc không lựa chọn tốt có thể làm giảm chất lượng phân cụm [9]. Việc lựa
chọn các cặp để gán nhãn nhằm thu thập các ràng buộc sao cho tốt nằm trong khuôn khổ của bài toán học tích cực
(active learning). Một số thuật toán học tích cực đã được phát triển như thuật toán FFQS [10], thuật toán MMFFQS
[11], thuật toán ASC [12], thuật toán AFCC [13], thuật toán dựa trên hàm hạt nhân [14],… Các nghiên cứu này đều cho
thấy việc lựa chọn tốt các ràng buộc không những làm tăng chất lượng của quá trình phân cụm mà còn giảm được số
lượng các ràng buộc cần thu thập. Trong bài báo này, chúng tôi đề xuất một thuật toán mới mở rộng từ thuật toán
MMFFQS nhằm thu thập các ràng buộc từ người sử dụng, thuật toán mới được đặt tên là KMMFFQS dựa trên K-
Means và phương pháp Min-Max. Kết quả thực nghiệm với các tập dữ liệu thực từ UCI [15] chỉ ra tính hiệu quả của
thuật toán đề xuất.
Phần tiếp theo của bài báo được cấu trúc như sau: Phần II sẽ trình bày các nghiên cứu liên quan; phần III giới
thiệu phương pháp đề xuất; phần IV là kết quả thực nghiệm và cuối cùng phần V là kết luận của bài báo.
II. MỘT SỐ NGHIÊN CỨU LIÊN QUAN
Với phương pháp Min-Max, đầu tiên sẽ chọn ngẫu nhiên một điểm trong tập dữ liệu X đem đi gán nhãn. Các
bước tiếp theo sẽ chọn điểm (ynew) nhằm cực đại hóa các khoảng cách nhỏ nhất từ các điểm chưa có nhãn đến các điểm
đã gán nhãn trong tập Y. Điểm ynew được xác định theo công thức sau:
ynew arg max x X min y Y d x, y
trong đó ynew biểu thị điểm mới sẽ cập nhật vào tập Y và d(.) là hàm khoảng cách (có thể là hàm tính khoảng cách theo
Euclid hay Mahananobis,…).
Dựa vào ý tưởng trên thuật toán FFQS đã được đề xuất năm 2004 cho việc thu thập các ràng buộc từ người sử
dụng. Thuật toán FFQS gồm hai bước cơ bản: Bước thứ nhất nhằm tìm ra tập xương sống trong đó mỗi cụm chứa ít
nhất một điểm nằm trong tập ràng buôc. Như vậy giữa các điểm của các cụm khác nhau sẽ tạo thành các ràng buộc
cannot-link. Sau khi tìm ra tập xương sống, phương pháp FFQS tiếp tục lấy ngẫu nhiên các điểm thuộc tập dữ liệu và
hình thành các cặp điểm với tập xương sống để truy vấn người sử dụng thu thập các must-link. Phương pháp FFQS đã
được kiểm thử với thuật toán MPCK-means và cho kết quả tốt khi so sánh với phương pháp lựa chọn ràng buộc bằng
phương pháp lấy ngẫu nhiên. Năm 2008, thuật toán MMFFQS được đề xuất dựa trên sự cải tiến của thuật toán FFQS.
Cụ thể tại bước 2 của thuật toán FFQS, thay vì lựa chọn các điểm ngẫu nhiên, thuật toán MMFFQS sẽ lựa chọn điểm
theo phương pháp Min-Max, điểm xa nhất của tập dữ liệu so với tập điểm đã xuất hiện trong các ràng buộc mà chưa
thuộc ràng buộc nào sẽ được lựa chọn để hình thành các cặp câu hỏi cho người sử dụng để gán nhãn là must-
link/cannot-link. Hình 2 minh họa một số ràng buộc thu thập được theo thuật toán MMFFQS. Phương pháp MMFFQS
áp dụng đối với thuật toán MPCK-means cho kết quả tốt hơn thuật toán FFQS. Tuy nhiên một hạn chế của hai thuật
toán trên là chúng ta phải biết số lượng các cụm ngay từ đầu và cả hai phương pháp chỉ phù hợp với tập dữ liệu các
cụm có dạng hình cầu cũng như kích thước các cụm là tương tự nhau. Và như vậy với các thuật toán phân cụm nửa
giám sát như MCSSDBS, MMSSGC, hay MCGC - đây là các thuật toán có thể tìm ra các cụm có hình dạng bất kỳ thì
khi sử dụng các ràng buộc thu thập được bởi thuật toán FFQS/MMFFQS sẽ cho kết quả cải tiến không cao.
Hình 2. Ví dụ về các ràng buộc thu thập bằng phương pháp MMFFQS
Trong một số nghiên cứu gần đây, chiến lược chia để trị tức là chia tập dữ liệu ra thành nhiều phần nhỏ để thực
hiện các công đoạn tiếp theo trên các phần nhỏ này tỏ ra hiệu quả trong nhiều trường hợp. Năm 2008, thuật toán phân
cụm SPARCL [16] được giới thiệu trong đó gồm hai bước cơ bản: Bước một sử dụng thuật toán K-Means chia tập dữ
liệu thành nhiều cụm rồi sau đó sử dụng độ đo giữa các cụm ghép các cụm nhỏ lại với nhau và thu được các cụm có
hình dạng bất kỳ. Thuật toán SPARCL có độ phức tạp tính toán nhỏ hơn các thuật toán cùng loại như DBSCAN. Năm
2009, thuật toán xấp xỉ Spectral clustering [17] được giới thiệu cũng dùng hai công đoạn như SPARCL, tuy nhiên thay
vì dùng các độ đo tương tự của hai cụm để ghép lại thì các tác giả đề xuất sử dụng trực tiếp thuật toán Spectral
- Vũ Việt Vũ, Nguyễn Anh Tuấn, Lê Thị Kiều Oanh 241
Clustering với các trọng tâm của các cụm thu được từ K-Means. Năm 2017, thuật toán COBRA [18] cũng sử dụng K-
Means để chia ra thành nhiều cụm nhỏ và đi thu thập các ràng buộc sử dụng cho các cặp cụm tương ứng. Kết quả thực
nghiệm đã chỉ ra tính hiệu quả của phương pháp đề xuất. Thậm chí thuật toán K-Means còn được áp dụng để tăng tốc
độ tính toán trong bài toán cây khung nhỏ nhất [19]. Trong phần tiếp theo của bái báo, chúng tôi sử dụng ý tưởng trên
và áp dụng vào việc thu thập các ràng buộc cải tiến cho thuật toán MMFFQS.
III. PHƯƠNG PHÁP ĐỀ XUẤT
Trong phần này, chúng tôi trình bày thuật toán KMMFFQS (K-Means based MMFFQS). Thuật toán
KMMFFQS tương đối đơn giản bao gồm hai bước như sau: Bước một sẽ áp dụng thuật toán K-Means nhằm chia tập
dữ liệu thành nhiều cụm khác nhau. Tập xương sống sẽ bao gồm tất cả các centroid của các cụm. Ở đây centroid của
một cụm là điểm thuộc tập dữ liệu và gần với trọng tâm của cụm đó nhất. Bước thứ hai sẽ áp dụng thuật toán
MMFFQS vào để thực hiện việc truy vấn các cặp dữ liệu nhằm thu thập các ràng buộc. Hai điểm quan trọng của thuật
toán KMMFFQS là:
Chúng ta không cần biết trước số cụm, việc sử dụng K-Means sẽ nhằm chia tập dữ liệu ban đầu ra thành
một lượng đủ lớn các cụm. Quá trình này sẽ biến các cụm có hình dạng bất kỳ thành hợp của các cụm có
hình dạng cầu theo thuật toán K-Means.
Với việc chia nhỏ tập dữ liệu, chúng ta sẽ thu thập được các ràng buộc phù hợp với các loại thuật toán phân
cụm nửa giám sát như MPCK-means, MCSSGC, MCSSDBS, MCGC,… Hình 3 minh họa các cặp điểm
dùng để truy vấn để gán nhãn (must-link/cannot-link) bởi người sử dụng khi sử dụng thuật toán
KMMFFQS. Tương tự như vậy hình 4 minh họa một số ràng buộc must-link và cannot-link thu thập được
cho tập dữ liệu gồm 4 cụm theo phân bố Gaussian.
Hình 3. Ví dụ về các câu hỏi truy vấn cho tập dữ liệu t4.8k.dat bằng phương pháp KMMFFQS
Việc lựa chọn số cụm trong bước một của thuật toán KMMFFQS là vấn đề đơn giản. Theo [19], giả sử n là số
lượng các điểm trong tập dữ liệu X, chúng ta có thể chọn số lượng cụm bằng hoặc nhỏ hơn n . Quá trình lựa chọn
các điểm để hình thành các cặp ứng viên gán nhãn bởi người sử dụng sẽ phụ thuộc vào tập điểm đang có trước đó.
Điểm mới được chọn theo phương pháp Min-Max sẽ luôn cách xa nhất có thể tập các điểm đã được thu thập trước đó.
Hình 4. Ví dụ về các ràng buộc thu thập bằng phương pháp KMMFFQS
- 242 LỰA CHỌN CÁC RÀNG BUỘC CHO THUẬT TOÁN PHÂN CỤM NỬA GIÁM SÁT
IV. KẾT QUẢ THỰC NGHIỆM
Để đánh giá hiệu quả của thuật toán, chúng tôi sử dụng 6 tập dữ liệu lấy từ trang website chứa các tập dữ liệu
thực UCI. Chi tiết về các tập dữ liệu được trình bày trong bảng 1. Độ đo Rand Index [20] sẽ được sử dụng để tính toán
chất lượng phân cụm cho các thuật toán. Độ đo Ran Index được tính bằng tỷ số giữa tổng số lượng các cặp nằm trong
cùng một cụm và số lượng các cặp nằm trong các cụm khác nhau đúng theo giá trị thực chia cho tổng số cặp của tập dữ
liệu đang xét.
Để đánh giá hiệu quả của thuật toán đề xuất, chúng tôi sử dụng thuật toán MCSSGC để tính toán kết quả.
Phương pháp KMMFFQS sẽ được so sánh với phương pháp lựa chọn ngẫu nhiên các cặp để gán nhãn bởi người sử
dụng. Ngoài ra kết quả phân cụm của thuật toán SSGC [21] (thuật toán phân cụm nửa giám sát chỉ sử dụng các seed)
cũng được trình bày trong hình 5.
Bảng 1. Dữ liệu dùng trong thực nghiệm từ UCI
ID Tên tập dữ liệu N M K
1 Ecoli 336 7 8
2 Iris 150 4 3
3 Protein 115 20 6
4 Soybean 47 35 4
5 Thyroid 215 5 3
6 Zoo 101 16 7
Từ kết quả trình bày ở hình 5 chúng ta có thể thấy với cùng số lượng ràng buộc chất lượng của thuật toán
MCSSGC tăng lên đáng kể khi sử dụng các ràng buộc thu thập được bởi phương pháp đề xuất. Chúng ta có thể giải
thích sự cải tiến này chính là nhờ sử dụng thuật toán K-Means vào pha thứ nhất của thuật toán đề xuất.
V. KẾT LUẬN
Trong bài báo này chúng tôi giới thiệu phương pháp KMMFFQS, một phương pháp mở rộng từ thuật toán
MMFFQS bằng cách sử dụng thuật toán K-Means vào chia nhỏ tập dữ liệu trước khi áp dụng chiến thuật Min-Max.
Bằng cách này thuật toán KMMFFQS thu thập được các ràng buộc đối với tập dữ liệu với hình dạng và kích thước cụm
bất kỳ. Kết quả thực nghiệm với tập dữ liệu từ UCI cho thấy hiệu quả của thuật toán đề xuất. Trong thời gian tới chúng
tôi sẽ tiếp tục tiến hành thực nghiệm để so sánh thuật toán đề xuất với các phương pháp khác cũng như áp dụng trên
các thuật toán phân cụm nửa giám sát khác.
Ecoli Iris
Protein Soybean
- Vũ Việt Vũ, Nguyễn Anh Tuấn, Lê Thị Kiều Oanh 243
Thyroid Zoo
Hình 5. Ví dụ về các ràng buộc thu thập bằng phương pháp KMMFFQS
VI. TÀI LIỆU THAM KHẢO
[1] Rui Xu, Donald C. Wunsch II. Survey of clustering algorithms. IEEE Trans. Neural Networks 16(3): 645-678
(2005).
[2] S. Basu, I. Davidson, and K. L. Wagstaff, Constrained Clustering. Advances in Algorithms, Theory, and
Applications, Chapman and Hall/CRC Data Mining and Knowledge Discovery Series, 1st edn., 2008.
[3] Sugato Basu, Mikhail Bilenko, Raymond J. Mooney. A probabilistic framework for semi-supervised
clustering. KDD 2004: 59-68.
[4] Nizar Grira, Michel Crucianu, Nozha Boujemaa. Semi-Supervised Fuzzy Clustering with Pairwise-Constrained
Competitive Agglomeration. FUZZ-IEEE 2005: 867-872
[5] Carlos Ruiz, Myra Spiliopoulou, Ernestina Menasalvas Ruiz. Density-based semi-supervised clustering. Data Min.
Knowl. Discov. 21(3): 345-370 (2010)
[6] Rajul Anand, Chandan K. Reddy. Graph-Based Clustering with Constraints. PAKDD (2) 2011: 51-62.
[7] Viet Vu Vu, Hong Quan Do. Graph-based Clustering with Background Knowledge. SoICT 2017: 167-172
[8] Viet Vu Vu, Hong Quan Do. Density-based clustering with side information and active learning. KSE 2017: 166-
171
[9] Ian Davidson, Kiri Wagstaff, Sugato Basu. Measuring Constraint-Set Utility for Partitional Clustering Algorithms.
PKDD 2006: 115-126
[10] Sugato Basu, Arindam Banerjee, Raymond J. Mooney. Active Semi-Supervision for Pairwise Constrained
Clustering. SDM 2004: 333-344
[11] Pavan Kumar Mallapragada, Rong Jin, Anil K. Jain. Active query selection for semi-supervised
clustering. ICPR 2008: 1-4
[12] Viet Vu Vu, Nicolas Labroche, Bernadette Bouchon-Meunier. Improving constrained clustering with active query
selection. Pattern Recognition 45(4): 1749-1758 (2012)
[13] Nizar Grira, Michel Crucianu, Nozha Boujemaa. Active semi-supervised fuzzy clustering. Pattern
Recognition 41(5): 1834-1844 (2008)
[14] Ahmad Ali Abin, Hamid Beigy. Active constrained fuzzy clustering: A multiple kernels learning approach.
Pattern Recognition 48(3): 953-967 (2015)
[15] M. Lichman, UCI Machine Learning Repository [http://archive.ics.uci.edu/ml]. Irvine, CA. University of
California, School of Information and Computer Science, 2013.
[16] Vineet Chaoji, Mohammad Al Hasan, Saeed Salem, Mohammed J. Zaki. SPARCL: an effective and efficient
algorithm for mining arbitrary shape-based clusters. Knowl. Inf. Syst. 21(2): 201-229 (2009)
[17] Donghui Yan, Ling Huang, Michael I. Jordan. Fast approximate spectral clustering. KDD, 2009, 907-916
[18] Toon van Craenendonck, Sebastijan Dumancic, Hendrik Blockeel:
[19] COBRA. A Fast and Simple Method for Active Clustering with Pairwise Constraints. IJCAI 2017: 2871-2877
[20] W. M. Rand. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical
Association, 66 (336): 846–850, 197, 1971.
- 244 LỰA CHỌN CÁC RÀNG BUỘC CHO THUẬT TOÁN PHÂN CỤM NỬA GIÁM SÁT
[21] Viet Vu Vu. An efficient semi-supervised graph based clustering. Intelligent Data Analysis, 22(2): 297-307
(2018).
SELECTING CONSTRAINTS FOR SEMI-SUPERVISED CLUSTERING
Vu Viet Vu, Nguyen Anh Tuan, Le Thi Kieu Oanh
ABSTRACT: Constraints based clustering is one kind of semi-supervised clustering that integrates a small set of constraints to the
clustering algorithms to improve the performances of clustering process. In fact, there are so many semi-supervised clustering
algorithms proposed in the literature. However, most of the time, constraints are generated at random or they are assumed to be
available for each cluster. Moreover, some constraint might actually decrease the performance of semi-supervised clustering
algorithms if they cannot be carefully chosen. In this paper, we introduce a new efficient algorithm extended from the MMFFQS
algorithm for active constraints selection which relies on K-Means clustering and Min-Max method, called KMMFFQS.
Experiments conducted on real datasets from UCI show the effectiveness of our new algorithm.
Keywords: semi-supervised clustering, constraint, active learning, K-Means.
nguon tai.lieu . vn
