›

Luận văn Phân cụm dựa trên tri thức theo từng cặp

pdf 53 trang thiennha21 14/04/2022 5481
Download
Bạn đang xem 20 trang mẫu của tài liệu "Luận văn Phân cụm dựa trên tri thức theo từng cặp", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfluan_van_phan_cum_dua_tren_tri_thuc_theo_tung_cap.pdf

Nội dung text: Luận văn Phân cụm dựa trên tri thức theo từng cặp

  1. ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ ĐỖ VĂN VIỆT PHÂN CỤM DỰA TRÊN TRI THỨC THEO TỪNG CẶP Ngành: Hệ thống Thông tin Chuyên ngành: Hệ thống Thông tin Mã Số: 8480104.01 LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. HOÀNG XUÂN HUẤN Hà Nội – 09/2020
  2. i LỜI CAM ĐOAN Tôi Đỗ Văn Việt xin cam đoan những nội dung trình bày trong luận văn này là kết quả tìm hiểu, nghiên cứu của bản thân dưới sự hướng dẫn của PGS.TS. Hoàng Xuân Huấn. Mọi thông tin tham khảo sử dụng trong luận văn đều được trích dẫn đầy đủ và hợp pháp. Nếu có gì sai phạm, tôi xin hoàn toàn chịu trách nhiệm. Hà Nội, tháng 09 năm 2020 Đỗ Văn Việt
  3. ii LỜI CẢM ƠN Trong quá trình thực hiện luận văn, tôi đã gặp rất nhiều khó khăn. Nhưng tôi luôn nhận được sự ủng hộ, giúp đỡ từ các thầy cô, bạn bè và gia đình. Khi hoàn thành xong luận văn này, tôi thực sự rất biết ơn họ. Tôi xin gửi lời cảm ơn chân thành tới PGS.TS. Hoàng Xuân Huấn đã tận tình hướng dẫn và chỉ bảo tôi trong suốt quá trình thực hiện luận văn. Được nhận sự giúp đỡ của Thầy, với em là một món quà vô cùng quý giá trong cuộc đời này. Một lần nữa em gửi lời cảm ơn, lời biết ơn tới Thầy. Tôi xin chân thành cảm ơn các quý Thầy Cô trường Đại học Công nghệ – Đại học Quốc gia Hà Nội đã tận tình dạy bảo, truyền đạt những kiến thức quý báu giúp tôi hoàn thành nhiệm vụ học tập trong suốt thời gian theo học tại trường. Quý Thầy Cô đã giúp tôi có được những kiến thức nền tảng quý báu và quan trọng trong ngành nghề mà tôi đang theo đuổi. Tôi xin chân thành cảm ơn anh chị em đồng nghiệp đã giúp đỡ, ủng hộ tinh thần trong thời gian tôi tham gia học tập. Cuối cùng, tôi xin gửi lời cảm ơn, biết ơn tới những người thân yêu trong gia đình bé nhỏ của tôi. Những người đã phụ giúp tôi rất nhiều công việc, trách nhiệm trong gia đình để tôi có thể có thời gian, sức lực để học tập và hoàn thành luận văn. Hà Nội, tháng 09 năm 2020 Đỗ Văn Việt
  4. iii MỤC LỤC LỜI CAM ĐOAN i LỜI CẢM ƠN ii MỤC LỤC iii DANH MỤC KÝ HIỆU VÀ TỪ VIẾT TẮT v DANH SÁCH HÌNH VẼ vi LỜI NÓI ĐẦU 1 CHƯƠNG 1. PHÂN CỤM DỮ LIỆU 3 1.1. Phân cụm là gì 3 1.2. Một số phương pháp phân cụm dữ liệu cơ bản 4 1.2.1. Phương pháp phân hoạch 4 1.2.2. Phương pháp phân cấp 6 1.2.3. Phương pháp dựa trên mật độ 8 1.2.4. Phương pháp dựa trên lưới 10 CHƯƠNG 2. MẠNG NƠ-RON 13 2.1. Mạng nơ-ron 13 2.1.1. Nơ-ron sinh học 13 2.1.2. Perceptron 14 2.1.3. Mạng truyền tới nhiều tầng 16 2.2. Huấn luyện mạng nơ-ron 17 2.3. Hàm kích hoạt 19 2.4. Hàm mất mát 21 2.4.1. Hàm mất mát dùng cho hồi quy 21 2.4.2. Hàm mất mát dùng cho phân lớp 21 2.4.3. Hàm mất mát dùng cho tái tạo 22 CHƯƠNG 3. PHÂN CỤM DỰA TRÊN TRI THỨC THEO TỪNG CẶP . 24 3.1. Phân cụm dựa trên ràng buộc 24 3.1.1. Phân loại các ràng buộc 24 3.1.2. Các phương pháp phân cụm dựa trên ràng buộc 25 3.2. Phương pháp S3C2 27 3.2.1. Giới thiệu sơ lược 27 3.2.2 Chi tiết mô hình 28 3.3. Đánh giá mô hình 31 CHƯƠNG 4. THỬ NGHIỆM 33
  5. iv 4.1. Giới thiệu 33 4.2. Chương trình 33 4.2.1. Module dataset 33 4.2.2. Module labnet 33 4.2.3. Module clunet 34 4.3. Dữ liệu thử nghiệm 34 4.3.1. Dữ liệu hoa Iris 34 4.3.2. Dữ liệu chữ số viết tay MNIST 35 4.4. Thử nghiệm trên bộ dữ liệu hoa Iris 35 4.4.1. Kịch bản thử nghiệm 35 4.4.2. Kết quả thử nghiệm 37 4.4.3. Nhận xét 39 4.5. Thử nghiệm trên bộ dữ liệu MNIST 39 4.5.1. Kịch bản thử nghiệm 39 4.5.2. Kết quả thử nghiệm 41 4.5.3. Nhận xét 43 4.6. Nhận xét thử nghiệm 43 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 44 TÀI LIỆU THAM KHẢO 45
  6. v DANH MỤC KÝ HIỆU VÀ TỪ VIẾT TẮT STT Từ viết tắt Từ hoặc cụm từ 1 BI Business Intelligence 2 CRM Customer Relationship Management 3 MSE Mean Squared Error 4 SSC Semi-Supervised Clustering 5 S3C2 Semi-Supervised Siamese Classifiers for Clustering 6 LabNet Labeling Network 7 CluNet Clustering Network 8 SNN Siamese Neural Networks 9 DNNs Dense Deep Neural Networks 10 NMI Normalized Mutual Information 11 ARI Adjusted Rand Index 12 SSGC Semi-Supervised Graph-based Clustering
  7. vi DANH SÁCH HÌNH VẼ Hình 1.1 Phân cụm k-Means 6 Hình 1.2 Chameleon 7 Hình 1.3 Density-reachability và density-connectivity 10 Hình 1.4 Hierarchical structure for STING clustering 11 Hình 2.1 Nơ-ron sinh học 13 Hình 2.2 Single-layer perceptron 15 Hình 2.3 Artificial neuron for a multilayer perceptron 16 Hình 2.4 Multilayer neural network topology 17 Hình 2.5 Linear activation function 19 Hình 2.6 Sigmoid activation function 20 Hình 3.1 Mô hình S3C2 28 Hình 3.2 Cấu trúc mạng LabNet 29 Hình 3.3 Cấu trục mạng CluNet 30 Hình 3.4 NMI 32 Hình 4.1 Hoa Iris 35 Hình 4.2 Một mẫu chữ số 2 viết tay 35 Hình 4.3 Cấu trúc chi tiết mạng LabNet khi dữ liệu được sử dụng là Iris 36 Hình 4.4 Cấu trúc chi tiết mạng CluNet khi dữ liệu được sử dụng là Iris 37 Hình 4.5 Kết quả phân cụm trên bộ dữ liệu Iris 38 Hình 4.6 Kết quả phân cụm của một số phương pháp khác trên bộ dữ liệu Iris 38 Hình 4.7 Cấu trúc mạng LabNet khi dữ liệu được sử dụng là MNIST 40 Hình 4.8 Cấu trụng mạng nơ-ron được sử dụng trong CluNet 41 Hình 4.9 Kết quả phân cụm trên bộ dữ liệu MNIST 42 Hình 4.10 Biểu đồ kết quả phân cụm một số phương pháp trên MNIST 42
  8. 1 LỜI NÓI ĐẦU Thế kỉ 21, là kỉ nguyên mà nhân loại được chứng kiến sự thay đổi chóng mặt của công nghệ thông tin. Công nghệ thay đổi đã làm thay đổi mọi mặt trong đời sống của con người. Những sản phẩm công nghệ đã xuất hiện trên khắp mọi miền quê, khắp mọi nẻo đường, từ nông thôn đến thành thị. Công nghệ làm thay đổi thói quen sinh hoạt, vui chơi, giải trí của con người. Công nghệ làm thay đổi phương thức, quy trình sản xuất của các cá nhân, tập thể. Người ta sử dụng công nghệ cho mọi việc, ở mọi nơi, mọi lúc. Dẫn đến, một lượng dữ liệu khổng lồ được sinh ra hàng giờ, hàng phút, thẫm chí là hàng giây. Vì vậy mà lĩnh vực khai phá dữ liệu cũng như phát hiện tri thức ngày càng được quan tâm nhiều hơn, và cũng đang phát triển mạnh mẽ hơn bao giờ hết. Trong đó, phân cụm dữ liệu là một kĩ thuật quan trọng trong lĩnh vực này. Phân cụm (Clustering) là chia các tập dữ liệu thành các cụm sao cho các đối tượng trong cùng một cụm giống nhau hơn các đối tượng ở cụm khác. Bài toán phân cụm dữ liệu có được ứng dụng rộng rãi và đa dạng trong nhiều lĩnh vực, như kinh doanh thông minh (Business Intelligence: BI), nhận dạng mẫu, tìm kiếm web, sinh học, bảo mật và mạng xã hội, Bài toán này đã thu hút nhiều người nghiên cứu trong 5 thập kỷ qua, cùng với sự bùng nổ dữ liệu, càng ngày nó càng được quan tâm trong xử lý dữ liệu lớn (Big Data). Thoạt tiên, phân cụm dữ liệu được xét dưới dạng học không giám sát, việc phân cụm chỉ dựa vào tính tương tự của các đối tượng dữ liệu và kết quả phân cụm khó giải thích rõ ràng. Để tăng chất lượng phân cụm, trên thực tế, người dùng thường dùng thêm một số thông tin, tri thức nền tảng ban đầu nào đó về các đối tượng trong tập dữ liệu, chẳng hạn các đối tượng nên/không nên cùng một cụm. Hướng tiếp cận này được gọi là phân cụm bán giám sát. Hiện nay, các thông tin bổ trợ thường được cho dưới dạng tập giống (Seed) và ràng buộc (Constraint). Tập giống là tập gồm các đối tượng đã cho trước chúng thuộc cụm nào. Các ràng buộc có thể được gắn cho trên các cặp dữ liệu, như must-link hoặc cannot-link để cho biết chúng có thuộc cùng cụm hay không. Chúng cũng có thể là các ràng buộc trên các cụm, như ràng buộc về số lượng, kích thước hay hình dạng các cụm, Trong luận văn này, sau khi tìm hiểu hướng tiếp cận phân cụm dựa trên các ràng buộc theo từng cặp, chúng tôi tập trung vào phương pháp phân cụm dựa trên tri thức mới có tên là S3C2 [1], trong đó tri thức được cho dưới dạng ràng buộc theo từng cặp. Phương pháp này sử dụng mạng nơ-ron cùng với các thuật toán học sâu để phân cụm, cho hiệu quả cao. Chúng tôi thực hiện cài đặt thực nghiệm để so sánh với các thuật toán khác, kết quả cho thấy được các ưu
  9. 2 điểm nổi trội của thuật toán so với các thuật toán tiên tiến đã có, chẳng hạn như SSGC, SSDBSCAN, SSK-Means, MCSSGC [5,6]; kết quả cài đặt so sánh được với thực nghiệm trong bài báo vừa công bố. Ngoài phần kết luận, nội dung của luận văn bố cục như sau: - Chương 1. Giới thiệu bài toán phân cụm dữ liệu, các khái niệm và các tiếp cận cơ bản. - Chương 2. Giới thiệu kiến thức về mạng nơ-ron cần dùng để đi sâu vào tìm hiểu việc ứng dụng chúng cho bài toán phân cụm dựa trên tri thức được trình bày ở chương 3. - Chương 3. Trình bày phương pháp S3C2, một mô hình phân lớp sử dụng mạng nơ-ron cho bài toán phân cụm dựa trên ràng buộc theo từng cặp. - Chương 4. Trình bày kết quả cài đặt chương trình cho phương pháp S3C2, và chạy thử nghiệm trên tập dữ liệu hoa Iris, MNIST; đưa ra kết quả thực nghiệm của S3C2 đồng thời so sánh kết quả với các phương pháp khác: SSGC, SSDBSCAN, SSK-Means, MCSSGC [5,6].
  10. 3 CHƯƠNG 1. PHÂN CỤM DỮ LIỆU Trước khi đi sâu vào phân cụm bán giám sát dựa trên tri thức theo từng cặp, cũng như phương pháp S3C2 [1], chương này chúng tôi sẽ trình bày sơ lược về phân cụm dữ liệu, các phương pháp phân cụm dữ liệu. 1.1. Phân cụm là gì Phân cụm là quá trình phân tách một tập các đối tượng dữ liệu thành các tập con. Mỗi tập con là một cụm, sao cho các đối tượng trong cùng một cụm thì giống nhau, nhưng không giống so với các đối tượng ở các cụm khác [2]. Phân cụm được sử dụng rộng rãi trong nhiều lĩnh vực, như BI, nhận dạng mẫu, tìm kiếm web, sinh học và bảo mật, Trong BI, phân cụm có thể được sử dụng để sắp xếp một số lượng lớn các khách hàng vào các nhóm, trong đó các khách hàng trong cùng một nhóm sẽ có sự tương tự lớn về một số đặc điểm. Điều này tạo điều kiện cho phát triển các chiến lược kinh doanh để tăng cường quản lý quan hệ khách hàng (Customer Relationship Management: CRM) [2]. Trong nhận dạng mẫu, phân cụm cũng được sử dụng cho nhiều bài toán có tính ứng dụng cao, và rất thực tiễn, như nhận dạng chữ ký, nhận dạng chữ viết tay, nhận dạng vân tay, nhận diện khuôn mặt, Sản phẩm của phân cụm được triển khai trong rất nhiều hệ thống, và ngày càng trở nên phổ biến. Từ các ứng dụng của các cá nhân, tới các hệ thống lớn hơn của các doanh nghiệp, ngân hàng, các tập đoàn đa quốc gia, thậm chí là các hệ thống chính phủ, đều có sự hiện diện của phân cụm. Chẳng hạn như, ngày nay nhận dạng vân tay được sử dụng làm cơ chế xác thực cho hầu hết các thiết bị và ứng dụng. Phân cụm cũng được ứng dụng khá nhiều trong tìm kiếm web. Ví dụ như: một từ khóa tìm kiếm có thể cho ra một số lượng rất lớn các kết quả, do số lượng trang web là vô cùng lớn. Phân cụm có thể được sử dụng để sắp các kết quả đó vào các nhóm và trình bày các kết quả một cách ngắn gọn. Giúp người dùng có trải nghiệm tốt hơn, tìm kiếm dễ dàng và hiệu quả hơn. Hơn nữa, các kỹ thuật phân cụm cũng đã được phát triển để phân loại các tài liệu thành các chủ đề, kết quả của nó thường được sử dụng trong truy hồi thông tin. Trong khai phá dữ liệu, phân cụm được sử dụng như một công cụ độc lập để hiểu rõ hơn về phân phối của dữ liệu, để quan sát các đặc điểm của từng cụm và tập trung vào một nhóm cụ thể để phân tích thêm. Ngoài ra, nó cũng đóng vai trò là bước tiền xử lý cho các thuật toán khác như phân lớp, trích chọn đặc trưng, [2].
  11. 4 Bởi vì mỗi cụm là một tập các đối tượng tương tự nhau và không tương tự với các đối tượng thuộc lớp khác, nên mỗi cụm có thể được hiểu là một lớp ẩn. Theo nghĩa này, phân cụm đôi khi còn được gọi là phân lớp tự động. Trong một số ứng dụng, phân cụm còn được gọi là phân đoạn dữ liệu (Data Segmentation), bởi nó phân chia dữ liệu thành các nhóm dựa trên độ tương tự của chúng. Phân cụm cũng có thể được sử dụng để phát hiện ngoại lệ (các đối tượng cách xa bất kỳ cụm nào). Ví dụ như phát hiện gian lận thẻ tín dụng, giám sát các hoạt động tội phạm trong thương mại điện tử. Trong học máy, phân lớp được gọi là học có giám sát (Supervised Learning) vì thông tin nhãn lớp được sử dụng trong thuật toán học. Còn phân cụm được gọi là học không giám sát, do không sử dụng thông tin nhãn lớp. Vì lý do này, phân cụm là hình thức học tập dựa trên quan sát thay vì học qua các ví dụ [2]. 1.2. Một số phương pháp phân cụm dữ liệu cơ bản Tùy theo đặc điểm về tính tương đồng của các đối tượng trong các bài toán đang xét, có nhiều cách tiếp cận cho thuật toán phân cụm. J. Han và M. Kamber [2] phân các thuật toán này thành 4 loại chính: - Phương pháp phân hoạch (Partitioning methods) - Phương pháp phân cấp (Hierarchical methods) - Phương pháp dựa trên mật độ (Density-based methods) - Phương pháp dựa trên lưới (Grid-based methods) 1.2.1. Phương pháp phân hoạch Cho tập dữ liệu D gồm n đối tượng, phương pháp phân hoạch phân phối các đối tượng thuộc D thành k cụm, C1, C2, , Ck, sao cho Ci ∈ D và 푖 ∩ 푗 = ∅ với 1 ≤ 푖, 푗 ≤ . Một hàm mục tiêu được sử dụng để đánh giá chất lượng phân cụm sao cho các đối tượng trong cùng một cụm thì tương tự nhau nhưng khác so với các đối tượng ở các cụm khác. Ở đây, hàm mục tiêu sẽ nhắm đến việc làm tăng cao độ tương tự nội bộ (Intracluster Similarity) và giảm thấp độ tương tự liên kết (Intercluster Similarity). Hầu hết các phương pháp phân hoạch đều dựa trên khoảng cách (Distance-based). Ban đầu chúng khởi tạo một phân vùng. Sau đó, nó lặp đi lặp lại việc di chuyển các đối tượng từ nhóm này sang nhóm khác để cố gắng cải thiện chất lượng phân vùng. Phân cụm phân hoạch thường rất khó để đạt được tối ưu toàn cục mà thường thực hiện tối ưu cục bộ bằng các cách tiếp cận tham lam như thuật toán k-Means và k-medoids. Chúng thường hoạt động tốt khi được sử dụng để tìm
  12. 5 các cụm có hình cầu (Spherical Shaped Cluster) trong cơ sở dữ liệu có kích thước từ nhỏ đến trung bình [2]. Thuật toán k-Means [2] K-Means là một thuật toán phân cụm phân hoạch dựa trên trọng tâm. Chúng sử dụng trọng tâm của một cụm để đại diện cho cụm đó. Trọng tâm có thể được định nghĩa theo nhiều cách khác nhau, chẳng hạn như giá trị trung bình của các đối tượng trong cụm. Giả sử ta có cụm Ci với tâm ci. Gọi dist(p, ci) là khoảng cách giữa điểm p và tâm ci. Chất lượng của cụm Ci có thể được đo bằng tổng bình phương khoảng cách giữa tất các các đối tượng trong cụm và tâm ci, được định nghĩa như sau: 2 푖 = ∑ 푖푠푡( , 푖) ∈ 푖 푖 càng nhỏ thì chất lượng của cụm càng tốt. Từ đó, chất lượng của một kết quả phân cụm hay một bộ phân hoạch có thể được tính bởi công thức sau: 2 = ∑ ∑ 푖푠푡( , 푖) 푖=1 ∈ 푖 Tối ưu hóa E là một việc rất khó khăn. Trong trường hợp xấu nhất, chúng ta sẽ phải liệt kê một số lượng là lũy thừa của số cụm các phân hoạch có thể có. Bài toán là NP-hard trong không gian Euclide nói chung (chưa biết số chiều), thẫm chí ngay cả khi số cụm k=2. Trong trường hợp, các đối tượng dữ liệu là các vec-tơ trong không gian Euclide 2 chiều, nhưng chưa biết số cụm k, thì việc tối ưu E cũng là NP-hard. Để khắc phục điều này, k-Means sử dụng cách tiếp cận tham lam và thực hiện tối ưu cục bộ. Thuật toán k-Means định nghĩa trọng tâm của cụm là giá trị trung bình của các điểm trong cụm. Lược đồ giải thuật của thuật toán như sau: Input: . k: số lượng các cụm . D: tập dữ liệu gồm n đối tượng Output: Một tập gồm k cụm. Phương thức: (1) tùy chọn k đối tượng trong D làm tâm khởi tạo cho k cụm (2) lặp cho tới khi không có sự thay đổi nào nữa (2.1) gán (hoặc gán lại) mỗi đối tượng vào cụm mà nó gần tâm nhất (2.2)cập nhật lại tâm các cụm, bằng cách tính giá trị trung bình của các đối tượng trong cụm. Hình bên dưới mô phỏng giải thuật phân cụm k-Means
  13. 6 Hình 1.1 Phân cụm k-Means 1.2.2. Phương pháp phân cấp Phân cụm phân cấp còn được gọi là phân cụm cây, trong đó sắp xếp một tập dữ liệu đã cho thành một cấu trúc có dạng hình cây. Tùy theo cách xây dựng cây phân cấp, mà phân cụm phân cấp được chia thành hai phương pháp kết tụ (Agglomerative) hoặc phân tách (Divisive). Phương pháp kết tụ, còn được gọi là phương pháp từ dưới lên (Bottom-up), bắt đầu với mỗi đối tượng tạo thành một nhóm riêng biệt. Sau đó, nó liên tiếp trộn các đối tượng hoặc các nhóm gần nhau lại, cho tới khi tất cả các nhóm được trộn thành một, hoặc đạt tới một điều kiện kết thúc nào đó [2]. Phương pháp tách còn được gọi là phương pháp từ trên xuống (Top- down), bắt đầu với tất cả các đối tượng trong cùng một cụm. Trong mỗi lần lặp liên tiếp, một cụm lại được chia thành các cụm nhỏ hơn, kết thúc khi mỗi đối tượng nằm trong một cụm hoặc đạt tới điều kiện kết thúc nào đó. Phân cụm phân cấp có thể dựa trên khoảng cách hoặc dựa trên mật độ. Nó có mặt hạn chế bởi thực tế một khi một bước trộn (merge) hoặc tách (split) được thực hiện, nó không bao giờ có thể được hoàn tác và các bước tiếp theo của quá trình sẽ được thực hiện trên các cụm vừa mới được tạo. Do đó, nếu các quyết định trộn hoặc tách không được lựa chọn tốt sẽ dẫn đến chất lượng phân cụm không được tốt. Song sự cứng nhắc này cũng hữu ích ở chỗ nó dẫn đến chi phí tính toán nhỏ hơn bởi không phải lo lắng về tổ hợp của các lựa chọn khác nhau. Dù không thể sửa các quyết định sai lầm, tuy nhiên nhiều cách thức cải thiện chất lượng phân cụm phân cấp đã được đề xuất. Trong đó, một hướng đi đầy hứa hẹn là tích hợp phân cụm phân cấp với các kỹ thuật phân cụm khác, được gọi là phân cụm đa pha (Multiphase Clustering). Trong đoạn sau của tiểu mục này, chúng tôi sẽ giới thiệu một phương pháp như vậy, đó là Chameleon. Có một số cách để phân loại các phương pháp phân cụm phân cấp. Ví dụ, có thể phân chúng thành các loại: [2] - Phương pháp thuật toán (Algorithmic methods) - Phương pháp xác suất (Probabilistic methods)
  14. 7 - Phương pháp Bayes (Bayesian methods) Các phương pháp kết tụ, phân tách và multiphase thuộc nhóm các phương pháp thuật toán, chúng coi các đối tượng dữ liệu là xác định và tính toán các cụm thông qua việc xác định khoảng cách của các đối tượng. Các phương pháp xác suất sử dụng các mô hình xác suất để mô tả các cụm và đo lường chất lượng của các cụm bằng sự phù hợp của các mô hình. Thuật toán Chameleon [2] Nhiều thuật toán phân cụm như CURE, Rock, chỉ tìm thấy các cụm phù hợp với một số mô hình tĩnh. Mặc dù hiệu quả trong một số trường hợp, song các thuật toán này có thể cho kết quả phân cụm với chất lượng không tốt nếu người dùng lựa chọn các tham số mô hình tĩnh không thích hợp. Các thuật toán dễ bị hỏng khi dữ liệu chứa các cụm có hình dạng, mật độ và kích thước đa dạng. Chameleon là một thuật toán phân cụm phân cấp đa pha sử dụng mô hình động để xác định độ tương tự giữa các cặp cụm. Trong Chameleon, độ tương tự cụm được đánh giá dựa trên hai tiêu chí: - Mức độ kết nối của các đối tượng trong cụm - Mức độ gần gũi của các cụm Hai cụm được merge nếu mức độ kết nối của các đối tượng trong chúng cao và hai cụm đó gần gũi với nhau. Do đó, Chameleon không phụ thuộc vào một mô hình tĩnh, do người dùng cung cấp mà có thể tự động thích ứng với các đặc điểm bên trong của các cụm được trộn. Quá trình trộn tạo điều kiện phát hiện các cụm tự nhiên, đồng nhất và áp dụng cho tất cả các loại dữ liệu miễn là có thể chỉ định một hàm tương tự (similarity function). Hình bên dưới mô phỏng cách Chameleon hoạt động: Hình 1.2 Chameleon Ban đầu, Chameleon khởi tạo một đồ thị k-nearest-neighbor (knn graph), ở đó mỗi nút của đồ thị biểu thị cho một đối tượng dữ liệu, và tồn tại một cạnh giữa hai nút của đồ thị nếu một đối tượng nằm trong số k đối tượng tương tự nhất với đối tượng kia. Các cạnh được đánh trọng số (weight) để phản ảnh mức độ tương tự giữa các đối tượng. Chameleon sử dụng thuật toán phân hoạch đồ thị để phân tách knn graph thành một số lượng lớn các phân vùng, sao cho nó tối
  15. 8 thiểu edge cut. Nghĩa là, một cụm C được phân chia thành các cụm con Ci và Cj sao cho tối thiểu trọng số của các cạnh sẽ bị cắt để C được chia thành Ci và Cj, tương đương tối thiểu mức độ kết nối của hai cụm Ci, Cj. Sau đó, Chameleon sử dụng thuật toán phân cụm phân cấp kết tụ, lặp đi lặp lại việc trộn các cụm con. Để xác định các cặp tương tự nhau nhất, thuật toán tính cả mức độ kết nối và mức độ gần của các cụm. Cụ thể, để xác định sự tương tự của cặp cụm Ci và Cj, Chameleon dựa trên hai chỉ số: Relative interconnectivity, 푅 ( 푖, 푗), giữa hai cụm, Ci và Cj, được định nghĩa như sau: | { , }| 푅 ( , ) = 푖 푗 푖 푗 1 (| | + | | ) 2 푖 푗 trong đó, là tổng trọng số các edge cut của cụm cha, trước khi bị phân { 푖, 푗} tách thành hai cụm con Ci và Cj. Tương tự, 푖 (hoặc 푗) là cự tiểu tổng trọng số các edge cut nếu phân tách cụm Ci (hoặc Cj) thành hai phần. Relative closeness, 푅 ( 푖, 푗), giữa hai cụm, Ci và Cj, được định nghĩa như sau: ̅ 푆 { , } 푅 ( , ) = 푖 푗 푖 푗 | | | 푖| ̅ 푗 ̅ 푆 + 푆 | 푖| + | 푗| 푖 | 푖| + | 푗| 푗 trong đó, 푆̅ là trung bình trọng số của các cạnh nối các nút trong cụm Ci { 푖, 푗} và các nút trong cụm Cj, và 푆̅ (hoặc 푆̅ ) là trung bình trọng số của các 푖 푗 cạnh bị cắt nếu cụm Ci (hoặc Cj) bị phân tách làm hai phần. Chameleon đã được chứng minh có năng lực tốt hơn trong việc khám phá cám cụm có hình dạng tùy ý với chất lượng cao hơn so với các thuật toán điển hình khác như BIRCH hay DBSCAN. Tuy nhiên, chi phí cho xử lý dữ liệu có số chiều lớn có thể cần thời gian (푛2) trong trường hợp xấu nhất. 1.2.3. Phương pháp dựa trên mật độ Hầu hết các phương pháp phân hoạch dựa trên khoảng cách giữa các đối tượng, nên thường chỉ có thể tìm thấy các cụm có hình cầu và gặp khó khăn trong việc phát hiện các cụm có hình dạng tùy ý. Các phương pháp phân cụm dựa trên mật độ đã được phát triển để khắc phục các nhược điểm này. Để tìm được các cụm có hình dạng tùy ý, chúng mô hình hóa các cụm như các vùng có mật độ dày đặc trong không gian dữ liệu, được phân tách bởi các vùng thưa thớt. Ở đây, mật độ của một vùng được hiểu là
  16. 9 số lượng các đối tượng dữ liệu nằm trong vùng đó. Lược đồ chung của các phương pháp phân cụm dựa trên mật độ là từ một cụm cho trước, có thể là một điểm, chúng thực hiện mở rộng cụm đó cho tới khi mật độ trong vùng lân cận (neighborhood) vượt quá một ngưỡng nào đó. Không chỉ được dùng để khám phá các cụm có hình dạng tùy ý, phân cụm dựa trên mật độ còn được sử dụng để lọc nhiễu hoặc ngoại lệ [2]. Thuật toán DBSCAN [2] Để hiểu rõ hơn về DBSCAN, trước tiên chúng tôi sẽ trình bày các khái niệm được sử dụng trong thuật toán này. - Vùng lân cận của một đối tượng: Cho ɛ là một tham số do người dùng chỉ định, ɛ-lân cận của một đối tượng o là không gian với bán kính ɛ, tâm là o. - Mật độ của vùng ɛ-lân cận tâm o là số lượng các đối tượng nằm trong vùng đó, hay là số lượng các đối tượng có trong tập dữ liệu có khoảng cách tới o nhỏ hơn hoặc bằng ɛ. - Cho MinPts là một tham số người dùng, một vùng ɛ-lân cận tâm o được gọi là dày đặc nếu mật độ của nó lớn hơn hoặc bằng MinPts. - Đối tượng lõi (core object): Đối tượng o trong tập dữ liệu được gọi là đối tượng lõi nếu ɛ-lân cận của nó là một vùng có mật độ dày đặc. Ban đầu thuật toán tìm các đối tượng lõi, và các vùng dày đặc. Sau đó nó thực hiện tạo các vùng dày đặc lớn hơn từ các vùng dày đặc nhỏ tập trung quanh đối tượng lõi. Để thực hiện được điều này, DBSCAN đưa ra ba khái niệm: - directly density-reachable, được phát biểu như sau: đối tượng p directly density-reachable được từ q khi và chỉ khi q là đối tượng lõi và p thuộc ɛ- lân cận của q - density-reachable, được phát biểu như sau: đối tượng p density-reachable được từ q nếu có một chuỗi các đối tượng p1, , pn sao cho p1 = q, pn = p, và pi+1 directly density-reachable được từ pi với 1 ≤ 푖 ≤ 푛 - density-connectedness, được phát biểu như sau: hai đối tượng p1, p2 ∈ D được gọi là density-connected nếu có một đối tượng 푞 ∈ sao cho cả p1 và p2 đều density-reachable được từ q Tập con ∈ là một cụm nếu thỏa mãn hai điều kiện sau: - với mọi o1, o2 ∈ C, thì o1 và o2 density-connected với nhau - không tồn tại đối tượng o ∈ C và 표′ ∈ ( − ) sao cho o và 표′ là density- connected Hình dưới đây mô tả các mối quan hệ density-reachable và density- connectivity trong phân cụm dựa trên mật độ:
  17. 10 Hình 1.3 Density-reachability và density-connectivity Lược đồ giải thuật bên dưới sẽ giúp chúng ta hiểu một cách hoàn chỉnh về thuật toán DBSCAN: Input: - Tập hợp gồm n đối tượng cần phân cụm - ɛ: tham số bán kính - MinPts: ngưỡng mật độ dày đặc cho các lân cận Output: Tập các cụm Method: (1) đánh dấu mọi đối tượng với nhãn unvisited; (2) thực hiện (3) lựa chọn ngẫu nhiên một đối tượng unvisited p; (4) đánh dấu p là visited (5) nếu ɛ-lân cận của p có ít nhất MinPts đối tượng (6) tạo mới cụm C, và thêm p vào cụm C (7) gọi N là tập các đối tượng trong ɛ-lân cận của p (8) với mỗi đối tượng p’ trong N (9) nếu p' unvisited (10) đánh dấu p’ là visited (11) nếu ɛ-lân cận của p’ có ít nhất MinPts điểm (12) add toàn bộ các điểm thuộc ɛ-lân cận vào tập N (13) nếu p’ chưa thuộc bất kỳ cụm nào, thì thêm p’ vào cụm C (14) nhận được cụm C; (15) ngược lại thì đánh dấu p với nhãn noise; (16) cho tới khi không còn đối tượng nào có nhãn unvisited 1.2.4. Phương pháp dựa trên lưới Các phương pháp dựa trên lưới định lượng không gian các đối tượng thành một số hữu hạn các ô tạo thành cấu trúc lưới. Tất cả các hoạt động phân cụm được thực hiện trên cấu trúc lưới đó. Ưu điểm chính của phương pháp này là thời gian xử lý nhanh, thường không phụ thuộc vào số lượng dữ liệu và chỉ
  18. 11 phụ thuộc vào số lượng các ô của mỗi chiều trong không gian được lượng tử hóa [2]. Sử dụng lưới thường là một cách hiệu quả cho các bài toán khai phá dữ liệu không gian, bao gồm cả phân cụm. Do đó, các phương pháp dựa trên lưới có thể được tích hợp với các phương pháp phân cụm khác như phương pháp dựa trên mật độ và phương pháp phân cấp. Thuật toán STING (STatistical INformation Grid) [2] Không gian được chia thành các ô hình chữ nhật. Các ô có cấu trúc phân cấp, và các cấp bậc khác nhau của các ô tương ứng với độ phân giải (resolution) khác nhau. Các ô ở mức cao hơn, được phân hoạch thành một số ô ở mức thấp hơn. Các thông tin thống kê của mỗi ô được tính toán và lưu trữ trước và được sử dụng để trả lời các câu truy vấn. Hình bên dưới, mô tả cấu trúc phân cấp trong phân cụm STING: Hình 1.4 Hierarchical structure for STING clustering Mỗi cell có các tham số attribute-dependent và attribute-independent. Tham số attribute-independent là số lượng (count) các đối tượng trong một ô. Còn với tham số attribute-dependent, ta cần giả định rằng với mỗi đối tượng, thì các đặc trưng của nó có giá trị kiểu số. Với mỗi đặc trưng chúng ta có 5 tham số như sau: - mean: trung bình của tất các các giá trị trong ô đó, - stdev: độ lệch chuẩn (standard deviation) của tất các các giá trị trong ô đó, - min: giá trị cực tiểu của đặc trưng trong ô đó, - max: giá trị cực đại - kiểu phân phối mà các giá trị trong ô tuân theo, chẳng hạn như normal, uniform, exponential hoặc none (nếu không xác định được phân phối) Các tham số thống kê của các ô mức cao hơn có thể dễ dàng được tính từ các tham số của các ô ở mức thấp hơn. Khi dữ liệu được load vào cơ sở dữ liệu thì các tham số count, mean, stdev, min, max của các ô ở mức thấp nhất (bottom-level cell) được tính trực tiếp từ dữ liệu. Còn kiểu phân phối có thể
  19. 12 được chỉ định bởi người dùng (nếu đã biết trước) hoặc thu được từ các kĩ thuật trong thống kê. Nếu kiểu phân phối của các ô mức thấp không đồng nhất với nhau, thì kiểu phân phối của ô cấp cao được đặt là none. Tiếp theo chúng ta sẽ tìm hiểu việc truy vấn trên cấu trúc phân cấp để thực hiện phân cụm. Nếu cấu trúc phân cấp không thể trả lời được truy vấn, thì có thể sử dụng cơ sở dữ liệu ban đầu. SQL được sử dụng như là một ngôn ngữ để mô tả các truy vấn. Có hai kiểu truy vấn phổ biến: - truy vấn để tìm các vùng (region) thỏa mãn một số ràng buộc nào đó - truy vấn vào một vùng nào đó, và trả về các đặc trưng của vùng đó Ví dụ 1: Truy vấn tìm các vùng có mật độ nhà tối thiểu là 100, tối thiểu 70% số nhà có giá lớn hơn $400k và với tổng area tối thiểu 100 đơn vị độ tin cậy (confidence) tối thiểu là 0.9. select region from house-map where density in (100, ∞) and price range (40000, ∞) with percent (0.7, 1) and area (100, ∞) and with confidence 0.9 Ví dụ 2: Truy vấn lấy thông tin khoảng tuổi của các nhà trong region thỏa mãn các điều kiện: mật độ tối thiểu 100 nhà, tối thiểu 70% số nhà có giá trong khoảng từ $150k đến $300k với area tối thiểu 100 đơn vị trong California select range(age) from house-map where density in (100, ∞) and price range (150000, 30000) with percent (0.7, 1) and area (100, ∞) and location california
  20. 13 CHƯƠNG 2. MẠNG NƠ-RON Để dễ dàng hơn khi tiếp cận phương pháp S3C2, một lược đồ mạng nơ-ron nhân tạo xử lý tri thức theo từng cặp, chương này giới thiệu tóm tắt về mạng nơ- ron nhân tạo. 2.1. Mạng nơ-ron Mạng nơ-ron (neural network) là một mô hình tính toán có chung một số tính chất với bộ não động vật, ở đó nhiều đơn vị hoạt động một cách song song mà không cần một đơn vị điều khiển trung tâm. Trọng số giữa các đơn vị này là cách thức chính để lưu trữ thông tin dài hạn trên mạng nơ-ron. Việc cập nhật các trọng số này là cách thức chính mà mạng nơ-ron học các thông tin mới [3]. Cách hành xử của mạng nơ-ron được định hình bởi kiến trúc mạng của nó. Kiến trúc của mạng nơ-ron được xác định (một phần) bởi các yếu tố sau: - Số lượng nơ-ron - Số lượng các lớp (layer) - Kiểu kết nối giữa các lớp 2.1.1. Nơ-ron sinh học Nơ-ron sinh học là một tế bào thần kinh cung cấp đơn vị chức năng cơ bản cho hệ thần kinh của tất cả các loại động vật. Hình 2.1 Nơ-ron sinh học Các nơ-ron tồn tại để giao tiếp với nhau và truyền các xung điện hóa (electro- chemial impulse) qua các khớp thần kinh (synapse), từ tế bào này sang tế bào khác, miễn là các xung lực đủ mạnh để kích hoạt sự giải phóng các hóa chất (chemical) qua một khe sinap. Độ mạnh của xung lực phải vượt qua ngưỡng tối thiểu thì các hóa chất mới được giải phóng. Hình 2.2 trình bày các thành phần chính của tế bào thần kinh, bao gồm:
  21. 14 - Soma (Thân tế bào) - Dendrite (Sợi nhánh thần kinh) - Axon (Sợi trục thần kinh) - Synapse (Khớp thần kinh) Nơ-ron được tạo thành từ một tế bào thần kinh bao gồm một soma. Soma có nhiều dendrite nhưng chỉ có một axon. Tuy nhiên, axon có thể được phân ra làm hàng trăm nhánh. Synapses Synapse là điểm nối giữa axon và các dendrite. Phần lớn các synapse gửi tín hiệu từ axon của một nơ-ron tới các dendrite của các nơ-ron khác. Các trường hợp ngoại lệ là khi một nơ-ron có thể thiếu các dendrite, hoặc một nơ-ron thiếu axon hoặc là khi synapse nối một axon với một axon khác. Dendrites Dendrite gồm các sợi rẽ nhánh từ soma. Dendrite cho phép tế bào nhận tính hiệu từ các nơ-ron khác và mỗi dendrite thực hiện khuếch đại tín hiệu bằng trọng số của mình. Axons Axon là các sợi đơn, dài. Axon có điểm đầu bắt nguồn từ soma và kéo dài ra một đoạn thường là 1cm (gấp 100 lần đường kính của soma), điểm cuối phân ra nhiều nhánh và kết nối với các dendrite khác. Các nơ-ron có khả năng gửi các xung điện hóa thông qua thay đổi điện thế cross-membrane tạo ra action potential. Tín hiệu này truyền dọc theo sợi trục của tế bào và kích hoạt các kết nối sinap (synaptic connections) với các nơ-ron khác. 2.1.2. Perceptron Perceptron là một mô hình tuyến tính thường được sử dụng để phân lớp nhị phân. Trong lĩnh vực mạng nơ-ron, perceptron được coi là một nơ-ron nhân tạo (artificial neuron) sử dụng hàm bước Heaviside (Heaviside step function) cho chức năng kích hoạt. Tiền thân của perceptron là Threshold Logic Unit (TLU) được phát triển bởi McCulloch and Pitts năm 1943. Thuật toán huấn luyện perceptron là một thuật toán học có giám sát.
  22. 15 Hình bên dưới mô tả cách thức hoạt động của perceptron, với quan hệ đầu vào – đầu ra khá đơn giản: Hình 2.2 Single-layer perceptron Chúng tính tổng của n đầu vào x1, x2, , xn nhân với trọng số tương ứng của chúng, và sau đó gửi kết quả tới một hàm bước (step function) với ngưỡng xác định. Thông thường các perceptron sử dụng một hàm bước Heaviside với ngưỡng là 0.5. Hàm này sẽ cho đầu ra là 0 hoặc 1 tùy thuộc vào giá trị đầu vào. Phương trình biểu diễn hàm bước Heaviside có dạng: 0, < 0 ( ) = { 1, ≥ 0 Thuật toán học trong perceptron Việc huấn luyện perceptron học thực chất là một quá trình lặp đi lặp lại việc cập nhật các trọng số cho tới khi perceptron có khả năng phân loại đúng cho tất cả các dữ liệu hoặc thỏa mãn một điều kiện dừng nào đó. Ban đầu, thuật toán khởi tạo vec-tơ trọng số với các giá trị ngẫu nhiên nhỏ hoặc bằng 0. Nó sử dụng từng bản ghi đầu vào, tính toán được kết quả phân loại đầu ra và so sánh kết quả nhận được với nhãn phân loại được gán cho bản ghi đó. Nếu kết quả phân loại không chính xác, các trọng số sẽ được điều chỉnh phù hợp. Ngược lại, nếu kết quả chính xác thì trọng số được giữ nguyên. Thuật toán sẽ lặp lại nhiều lần trên dữ liệu huấn luyện, và chỉ dừng lại khi tất cả các dữ liệu mẫu đều được phân loại chính xác. Perceptron chỉ có khả năng giải các bài toán tuyến tính, khi đầu vào là bộ dữ liệu có thể phân tách tuyến tính, tức là ta có thể tìm thấy một siêu phẳng để phân tách bộ dữ liệu đó làm hai phần. Nó tỏ ra bất lực khi được sử dụng để giải quyết các vấn đề phi tuyến. Chẳng hạn như, nó không thể giải được bài toán mô hình hóa hàm logic XOR. Hình dưới biểu thị một tập dữ liệu không thể phân tách tuyến tính, hàm logic XOR.
  23. 16 x0 x1 y 0 0 0 0 1 1 1 0 1 1 1 0 Một perceptron cơ bản (một lớp) không thể giải được bài toán mô hình hóa hàm logic XOR, cho thấy một giới hạn ban đầu của mô hình perceptron. Sự bất lực ban đầu để giải quyết các vấn đề phi tuyến tính được coi là một thất bại đối với lĩnh vực mạng nơ-ron. Tuy nhiên, điều mà họ đã không nhận ra một cách rộng rãi rằng một perceptron đa lớp (multilayer perceptron) có thể giải quyết được bài toán XOR, cũng như nhiều bài toán phi tuyến tính khác. 2.1.3. Mạng truyền tới nhiều tầng Mạng truyền tới nhiều tầng (multilayer feed-forward networks) là một trong những kiến trúc mạng nơ-ron phổ biến. Mạng bao gồm một tầng vào (input layer), một hoặc nhiều tầng ẩn (hidden layer), và một tầng ra (output layer). Mỗi layer có một hoặc nhiều nơ-ron nhân tạo. Các nơ-ron nhân tạo của multilayer perceptron tương tự như tiền thân single-layer perceptron của nó, nhưng các layer có thể sử dụng các hàm kích hoạt một cách linh hoạt hơn, tùy thuộc vào kiểu đầu ra mà layer đó tạo ra. Hình bên dưới trình bày diagram của nơ-ron nhân tạo được update dựa trên diagram của perceptron. Hình 2.3 Artificial neuron for a multilayer perceptron Cũng giống như perceptron, “net input” là kết quả của tích vô hướng giữa các vec-tơ trọng số và input feature. Tuy nhiên, việc sử dụng hàm kích hoạt linh hoạt đã cho phép layer có khả năng tạo ra nhiều loại khác nhau cho giá trị đầu ra. Đây là một sử thay đổi lớn so với thiết kế của perceptron trước đây – luôn cố
  24. 17 định sử dụng hàm bước Heaviside. Nội dung chi tiết về hàm kích hoạt sẽ được chúng tôi trình bày ở mục sau của chương này. Mỗi layer kết nối hoàn toàn (đầy đủ) với layer liền kề. Kết nối giữa các nơ-ron trên các layer tạo thành một đồ thị không tuần hoàn (acyclic graph), như được minh họa trong hình bên dưới: Hình 2.4 Multilayer neural network topology Một mạng nơ-ron đa lớp truyền thẳng có thể biểu diễn cho bất kỳ hàm toán học nào, nếu cung cấp đủ các nơ-ron nhân tạo. Nó thường được huấn luyện bởi một thuật toán học được gọi là thuật toán lan truyền ngược (backpropagation learning). Thuật toán sử dụng phương pháp gradient descent (giảm gradient) trên trọng số của các kết nối trong mạng nơ-ron để tối thiểu lỗi của output. Trước đây, phương pháp lan truyền ngược từng được cho là chậm. Nhưng ngày nay, với những tiến bộ về năng lực tính toán thông qua tính toán song song và GPUs đã làm mới lại sự quan tâm đến các mạng nơ-ron. 2.2. Huấn luyện mạng nơ-ron Một mạng nơ-ron nhân tạo (artificial neural network) được huấn luyện tốt sẽ có trọng số làm được hai việc: khuếch đại tín hiệu (amplify signal) và làm giảm nhiễu (dampen noise). Trọng số lớn hơn là dấu hiệu của một mối tương quan chặt chẽ hơn giữa tín hiệu và đầu ra của mạng. Input được ghép cặp với các trọng số lớn hơn sẽ ảnh hưởng đến sự diễn dịch dữ liệu (data interpretation) của mạng nhiều hơn so với các input được ghép với các trong số nhỏ hơn. Quá trình học tập (cho bất kỳ thuật toán học nào sử dụng trọng số) là quá trình điều chỉnh lại weight và bias, làm cho một số phần (trong weight và bias) nhỏ hơn và một số khác thì lớn hơn. Từ đó phân bổ tầm quan trọng cho các phần nào đó của thông tin và cũng làm giảm thiểu tầm ảnh hưởng của một số phần khác [3]. Trong hầu hết các bộ dữ liệu, một số feature có tương quan mạnh với các nhãn (ví dụ: vị trí ảnh hưởng lớn đến giá bán của một ngôi nhà). Mạng nơ-ron
  25. 18 học các mối quan hệ này một cách mù quáng bằng cách dự đoán đầu ra dựa trên input và weight và sau đó đo đạc độ chính xác của kết quả. Các hàm mất mát trong các thuật toán tối ưu, chẳng hạn như stochastic gradient descent (SGD), thưởng (reward) cho mạng cho những dự đoán tốt và phạt (penalize) nó với những dữ đoán tồi. SGD dịch chuyển các tham số của mạng theo hướng tạo những dự đoán tốt và tránh những dự đoán tồi. Một cách nhìn khác về quá trình học là xem các nhãn như là các theory (giả định) và các đặc trưng (feature) như là các evidence (bằng chứng). Sau đó, mạng tìm cách thiết lập mối tương quan giữa theory và evidence. Mô hình sẽ cố gắng trả lời câu hỏi “which theory does the evidence support?”. Với những ý tưởng này, chúng ta hãy xem xét thuật toán học phổ biến cho mạng nơ-ron: thuật toán học lan truyền ngược (backpropagation). Backpropagation Learning [3] Backpropagation là một phần quan trọng của quá trình làm giảm lỗi trong mạng nơ-ron. Thuật toán học backpropagation tương tự như thuật toán học trên perceptron. Nó sẽ tính toán output bằng việc cho input forward qua mạng nơ- ron. Nếu output khớp với label tương ứng, thì thuật toán sẽ không làm gì và tiếp tục với những input tiếp theo. Ngược lại, nếu input không khớp với label tương ứng, thì thuật toán sẽ thực hiện update trọng số của các kết nối trong mạng nơ- ron. Dưới đây là pseudocode của thuật toán, nó sẽ giúp chúng ta hiểu rõ hơn về thuật toán này: function neural-network-learning(training-records) return network begin network ← initialize_weights(randomly) start loop for each example in training-records do network-output = neural-network-output(network, example) actual-output = observed outcome associated with example update weights in network based on {example, network-output, actual-output} end for end loop when all examples correctly predicted or hit stopping conditions return network end;
  26. 19 2.3. Hàm kích hoạt Hàm kích hoạt ánh xạ một input vô hướng và cho ra một output vô hướng (scalar-to-scalar function). Sử dụng các hàm kích hoạt giúp chúng ta đưa tính phi tuyến vào khả năng mô hình hóa của mạng nơ-ron. Bây giờ chúng ta sẽ thảo luận về một số hàm kích hoạt hữu ích trong mạng nơ-ron [3]. Linear Một biến đổi tuyến tính (linear transform) (hay còn gọi là toán tử tuyến tính hoặc là ánh xạ tuyến tính) là một hàm giữa hai không gian vec-tơ mà bảo toàn được các thao tác cộng và nhân vô hướng vec-tơ. Một cách hình thức, nếu V và W là các không gian vec-tơ trên cùng một trường, chúng ta nói rằng ánh xạ : → 푊 là một (phép) biến đổi tuyến tính nếu có bất kỳ hai vec-tơ x và y trong không gian V và bất kỳ vô hướng a trong K, chúng ta có: ( ± ) = ( ) ± ( ) (tính kết hợp) ( ) = ( ) (tính thuần nhất) Điều này có ý nghĩa tương đương với khẳng định f “bảo toàn tổ hợp tuyến tính”, có nghĩa là, cho bất kỳ các vec-tơ 1, . . . , và các vô hướng 1, . . . , chúng ta có: ( 1 1+. . . + ) = 1 ( 1)+. . . + ( ) Thực tế trong mạng nơ-ron, nó có ý nghĩa là hàm không làm thay đổi tín hiệu được truyền qua. Phương trình biểu diễn của một hàm kích hoạt tuyến tính có dạng: ( ) = trong đó kết quả là một giá trị số (numerical value) thuộc khoảng từ âm vô cùng đến dương vô cùng. Hàm có biểu diễn dưới dạng đồ thị như sau: Hình 2.5 Linear activation function Sigmoid Phương trình biểu diễn hàm sigmoid có dạng:
  27. 20 1 푠푖 표푖 ( ) = 1 + 푒− Hàm bị chặn trong khoảng (0, 1), cụ thể: lim 푠푖 표푖 ( ) = 0 → −∞ lim 푠푖 표푖 ( ) = 1 → +∞ Hàm có công thức đạo hàm khá đơn giản như sau: 휎( ) ∶= 푠푖 표푖 ( ) 푒− 휎′( ) = (1 + 푒− )2 1 푒− 휎′( ) = (1 + 푒− ) (1 + 푒− ) (1 + 푒− ) − 1 휎′( ) = 휎( ) (1 + 푒− ) 휎′( ) = 휎( )(1 − 휎( )) Hàm có đồ thị biểu diễn như sau: Hình 2.6 Sigmoid activation function Softmax Hàm có phương trình biểu diễn như sau: exp ( 푖) 푠표 푡 ( 푖) = 푛 ∑푗=1 exp ( 푗) trong đó kết quả là các giá trị thuộc khoảng (0, 1). Hàm trả về phân phối xác suất trên các lớp đầu ra (loại trừ lẫn nhau – tổng bằng 1). Hàm có tính chất đồng biến, bởi với các 푖 = 푊푖 càng lớn thì 푠표 푡 ( 푖) càng cao. Hàm thường được sử dụng trong các bài toán phân lớp đa lớp.
  28. 21 2.4. Hàm mất mát Hàm mất mát (loss function) giúp định lượng mức độ mà một mạng nơ- ron có trạng thái gần với trạng thái lý tưởng mà nó hướng tới học tập. Ý tưởng rất đơn giản. Mạng tính toán một số liệu dựa trên lỗi mà chúng quan sát được trên các dự đoán. Sau đó, chúng tổng hợp các lỗi này trên toàn bộ tập dữ liệu và tính trung bình. Kết quả nhận được chính là con số đại diện cho mức độ mà một mạng nơ-ron gần với trạng thái lý tưởng của nó [3]. Tìm kiếm trạng thái lý tưởng này tương đương với việc tìm kiếm các tham số (weight và bias) sao cho tối thiểu sự mất mát gây ra bởi các lỗi. Theo cách này, hàm mất mát giúp đặt việc huấn luyện mạng nơ-ron như một vấn đề tối ưu hóa. Trong hầu hết các trường hợp, các tham số này không thể tìm thấy được bằng cách phân tích, nhưng chúng có thể được xấp xỉ (approximated) tốt với các thuật toán tối ưu ví dụ như gradient descent. Phần sau đây cung cấp một cái nhìn sơ lược về các hàm mất mát phổ biến. 2.4.1. Hàm mất mát dùng cho hồi quy Mean squared error loss Hàm mất mát Mean squared error (MSE – Sai số bình phương trung bình) được sử dụng khi làm việc trên một mô hình hồi quy (regression model) đòi hỏi đầu ra là một số thực, cũng giống như Ordinary least squared error (Sai số bình phương tối thiểu) thường được sử dụng trong mô hồi quy tuyến tính (linear regression). Phương trình biểu diễn của hàm mất mát MSE có dạng như sau: 1 퐿(푊, ) = ∑(푌̂ − 푌 )2 푖 푖 푖 2.4.2. Hàm mất mát dùng cho phân lớp Hinge loss Hinge loss là hàm mất mát được sử dụng phổ biến nhất khi mạng được tối ưu hóa cho hard classification. Ví dụ: 0 → ℎô푛 ư , 1 → ó ư . Phương trình biểu diễn của Hinge loss có dạng như sau: 1 퐿(푊, ) = ∑ (0,1 − × ̂) 푖푗 푖푗 푖 Hinge loss được sử dụng chủ yếu để phân loại nhị phân (binary classification). Logistic loss Các hàm mất mát logistic được sử dụng khi probability classification được quan tâm nhiều hơn so với hard classification.
  29. 22 Giả sử ta có N điểm dữ liệu x1, x2, , xN trong tập huấn luyện, ta cũng giả sử các điểm dữ liệu này tuân theo một phân phối nào đó được mô tả bởi bộ tham số 휃 nào đó. Ta có: ( 1, 2, , | 휃) là xác suất đồng thời để xảy ra toàn bộ các sự kiện x1, x2, , xN, xác xuất này còn được gọi là likelihood. Việc huấn luyện bộ phân lớp lúc này chính là việc đi tìm bộ tham số ϴ sao cho xác suất ( 1, 2, , | ϴ) đạt cực đại: 휃 = max ( 1, 2, , | 휃) (1) 휃 Trong thực tế việc trực tiếp bài toán (1) khá phực tạp, nên người ta đưa ra một hàm sấp sỉ cho xác suất ( 1, 2, , | 휃), gọi là hàm ước lượng hợp lý. Với bài toán phân lớp nhị phân, hàm có phương trình biểu diễn như sau: 푖 1− 푖 퐿(푊, ) = ∏ ̂푖 × (1 − ̂푖) 푖 Sau đó, đi thực hiện cực đại hóa hàm ước lượng hợp lý 퐿(푊, ). Negative log likelihood Để thuận tiện về mặt toán học, người ta thường biến đổi hàm likelihood bằng cách chuyển xác suất thành log (logarit) của xác suất, tích của các xác suất thành tổng của các xác suất, đồng thời đặt phủ định cho biểu thức trên, để phương trình nhận được tương ứng với một hàm mất mát – thường được gọi là negative log likelihood. Hàm có phương trình biểu diễn như sau: 퐿(푊, ) = − ∑ 푖 × log( ̂푖) + (1 − 푖) × log(1 − ̂푖) 푖 Việc cực tiểu hóa negative log likelihood tương đương với cực đại hóa likelihood và tương đương với cực đại xác suất. Chú ý rằng, Cross-Entropy có nguồn gốc từ lý thuyết thông tin (information theory), trong khi negetive log likelihood có nguồn gốc từ mô hình thống kê (statistical modeling). Hai phương thức này giống nhau về mặt toán học. Nên dù không có vấn đề gì khi được sử dụng, nhưng nó thường gây nhầm lẫn cho mọi người. 2.4.3. Hàm mất mát dùng cho tái tạo Ý tưởng về recontruction rất đơn giản. Một mạng nơ-ron được huấn luyện để tái tạo đầu vào của nó sao cho càng giống càng tốt. Ví dụ cho các mạng nơ- ron thuộc loại này là restricted Boltmann machines, autoencoder, Các mạng nơ-ron này đều sử dụng các hàm mất mát có nguồn gốc từ lý thuyết thông tin.
  30. 23 Dưới đây là phương trình cho Kullback-Leibler divergence: 푌 (푌||푌̂) = − ∑ 푌 × log( 푖) 퐾퐿 푖 푌̂ 푖 푖
  31. 24 CHƯƠNG 3. PHÂN CỤM DỰA TRÊN TRI THỨC THEO TỪNG CẶP Trong chương này, chúng tôi sẽ trình bày vắn tắt về phân cụm dựa trên ràng buộc, sau đó đi chi tiết về một phương pháp phân cụm mới dựa trên tri thức theo từng cặp. Đó là phương pháp S3C2 sử dụng kỹ thuật phân lớp trên mạng nơ- ron nhân tạo do Śmieja, Marek & Struski, Łukasz & Figueiredo, Mário đề xuất [1]. 3.1. Phân cụm dựa trên ràng buộc Thông thường, phân cụm còn được gọi là học không giám sát, là hình thức học dựa trên quan sát, chứ không phải học thông qua các mẫu, các ví dụ. Do đó, kết quả phân cụm thường có độ chính xác không cao hoặc không đáp ứng được đầy đủ yêu cầu đặt ra của người dùng. Đặc biệt, đôi khi kết quả phân cụm còn mâu thuẫn với thông tin, đặc trưng được gắn trên đối tượng. Để tăng chất lượng cho phân cụm, một hướng tiếp cận mới là sử dụng thêm thông tin, tri thức nền tảng ban đầu của các đối tượng vào quá trình phân cụm. Các thông tin này có thể được mô hình hóa như là các ràng buộc phân cụm (clustering constraints). Hướng tiếp cận này được Jiawei Han và Micheline Kamber [2] gọi là phân cụm dựa trên ràng buộc. Cùng với phân cụm dựa trên seed, phân cụm dựa trên ràng buộc là một nhánh của phân cụm bán giám sát. 3.1.1. Phân loại các ràng buộc Jiawei Han và Micheline Kamber [2] đưa hai cách để phân loại các ràng buộc. Cách thứ nhất, phân loại dựa trên các khía cạnh của phân cụm (các đối tượng mẫu, các cụm, hay độ đo tương tự, ) mà các ràng buộc được gắn vào. Cách thứ hai, phân loại dựa trên mức độ mạnh hay yếu mà các ràng buộc sẽ tác động vào quá trình phân cụm. Theo cách thứ nhất, Jiawei Han và Micheline Kamber chia ràng buộc trong phân cụm thành ba loại: - Ràng buộc trên thể hiện (constraints on instances), - Ràng buộc trên cụm (constraints on clusters), - Ràng buộc trên thước đo độ tương tự (constraints on similarity measurement). Ràng buộc trên thể hiện: Một ràng buộc trên các thể hiện sẽ chỉ rõ cách mà một cặp hoặc một tập hợp các thể hiện nên được ở chung nhóm trong phân cụm. Hai loại phổ biến cho ràng buộc trên các thể hiện là: - must-link: hai đối tượng x và y có ràng buộc must-link thì chúng nên ở chung một cụm. Ràng buộc must-link có tính chất bắc cầu (transitive), nếu có must-link (x, y) và must-link (y, z) thì sẽ có must-link (x, z).
  32. 25 - cannot-link: ngược lại với ràng buộc must-link, nếu hai đối tượng x và y có ràng buộc cannot-link, thì x và y nên thuộc hai cụm khác nhau. Ràng buộc cannot-link có thể được entail. Nghĩa là, nếu có cannot-link (x, y), và must-link (x, x’), và must-link (y, y’) thì có cannot-link (x’, y’). Ràng buộc trên các thể hiện có thể có thể được đưa ra bằng các thể hiện cụ thể. Ngoài ra cũng có thể được định nghĩa dựa trên các thuộc tính của các đối tượng. Ví dụ: constraint (x, y) là must-link nếu dist(x, y) ≤ ɛ. Ràng buộc trên cụm Một ràng buộc trên cụm đưa ra một yêu cầu nào đó cho các cụm, có thể là sử dụng các thuộc tính của các cụm. Ví dụ: ràng buộc về số lượng các đối tượng tối thiểu cho một cụm, được kính tối đa của cụm, hay là hình dạng của cụm, Ràng buộc trên thước đo độ tương tự Thông thường, một thước đo độ tương tự, chẳng hạn như khoảng cách Euclide, được sử dụng để đo độ tương tự giữa các đối tượng. Nhưng trong một số trường hợp đặc biệt, người ta có thể bổ sung một số ràng buộc trên cách tính độ đo tương tự. Ví dụ như trong bài toán phân cụm các khách hàng, thông thường chúng ta có thể tính khoảng cách giữa hai khách hàng bằng khoảng cách theo đường bộ giữa hai vị trí của hai khách hàng. Tuy nhiên, nếu hai khách hàng sống ở hai quốc gia khác nhau, chúng ta phải tính khoảng cách theo đường chim bay. Đây là một ràng buộc trên thước đo độ tương tự. Theo cách thứ hai, Jiawei Han và Micheline Kamber chia ràng buộc trong phân cụm thành hai loại: - Ràng buộc cứng (hard constraints): là các ràng buộc sẽ có tác động mạnh trong quá trình phân cụm, cũng như kết quả phân cụm, - Ràng buộc mềm (soft constraints): là các ràng buộc có tác được ở mức yếu vào quá trình phân cụm. 3.1.2. Các phương pháp phân cụm dựa trên ràng buộc Với từng ứng dụng, hình thức cho các ràng buộc là rất khác nhau. Do đó, cần có các kỹ thuật khác nhau để xử lý cho các ràng buộc cụ thể. Trong mục này, chúng ta sẽ tìm hiểu về các nguyên tắc chung để xử lý các ràng buộc cứng và mềm trong quá trình phân cụm. Xử lý ràng buộc cứng Chiến lược chung để xử lý các ràng buộc cứng là tuân thủ nghiêm ngặt các ràng buộc trong quá trình gán cụm. Để minh họa cho ý tưởng này, chúng ta sẽ sử dụng một ví dụ về phân cụm phân hoạch. Cho trước một tập dữ liệu và một tập các ràng buộc trên các thể hiện (must-link hoặc cannot-link), thuật toán COP-k-Means được mở rộng từ k-
  33. 26 Means sao cho đáp ứng được các ràng buộc đó. Thuật toán COP-k-Means hoạt động như sau: Bước 1: Tạo các siêu thể hiện cho các ràng buộc must-link. Từ các ràng buộc must-link trên các thể hiện, sử dụng tính chất bắc cầu, thuật toán tính toán tạo ra được một số lượng các tập con, với các đối tượng trên cùng một tập con là các đối tượng có ràng buộc must-link với nhau. Để đảm bảo, tất cả các đối tượng trên cùng một tập con, sau khi thực hiện phân cụm (bước 2) được gán vào cùng một cụm, thuật toán tạo ra tương ứng với mỗi tập con một siêu thể hiện làm đại diện cho các tập con đó. Siêu thể hiện có giá trị là mean của các đối tượng trong cùng tập con tương ứng. Thực hiện các thay đổi sau trên tập D các đối tượng cần phân cụm: - Bổ sung thêm các siêu thể hiện vào tập D - Loại bỏ các đối tượng cùng tập con với siêu thể hiện tương ứng. Ta được tập D'. Bước 2: Thực hiện thuật toán phân cụm k-Means trên tập D', với yêu cầu bổ sung sau: - Trong quá trình gán (hoặc gán lại) cụm cho các đối tượng, luôn phải đảm bảo rằng đối tượng được gán vào cụm mà nó không có ràng buộc cannot- link với tâm cũng như bất kì đối tượng nào trong cụm đó. Bước 3: Kết quả phân cụm của các siêu thể hiện sẽ được lấy để gán cụm cho các đối tượng thuộc cùng tập con (từ bước 1) với nó. Chúng ta có thể dễ dàng thấy rằng COP-k-Means luôn đảm bảo tuân thủ tuyệt đối các ràng buộc must-link và cannot-link. Xử lý ràng buộc mềm Phân cụm với các ràng buộc mềm là một bài toán tối ưu hóa. Khi phân cụm vi phạm một ràng mềm, một hình phạt mềm được áp dụng cho phân cụm. Do đó, mục tiêu tối hóa của phân cụm gồm hai phần: tối ưu hóa chất lượng phân cụm và giảm thiểu hình phạt vi phạm ràng buộc. Hàm mục tiêu tổng thể là sự kết hợp giữa điểm chất lượng phân cụm và điểm phạt. Để minh họa, chúng ta sử dụng một ví dụ về phân cụm phân hoạch. Cho trước một tập dữ liệu cần phân cụm và tập các ràng buộc mềm trên các thể hiện, thuật toán CVQE (Constrained Vector Quantization Error) tiến hành phân cụm k-Means đồng thời thi hành các hình phạt cho các vi phạm ràng buộc. Hàm mục tiêu được sử dụng trong CVQE là tổng các khoảng cách được sử dụng trong k- Mean, được điều chỉnh bằng các hình phạt vi phạm, với cách tính như sau: - Hình phạt cho một vi phạm ràng buộc must-link: Nếu hai đối tượng x và y có ràng buộc must-link nhưng lại được gán cho hai cụm khác nhau có tâm
  34. 27 lần lượt c1 và c2, thì ràng buộc đó bị vi phạm. Dẫn đến dist (c1, c2) được cộng vào hàm mục tiêu như là một hình phạt. Hình phạt cho một vi phạm ràng buộc cannot-link: Nếu hai đối tượng x và y có ràng buộc cannot-link nhưng lại được gán cho cùng một cụm với tâm là c, thì ràng buộc đó bị vi phạm. Nên dist (c, c’) được cộng vào hàm mục tiêu để phạt. 3.2. Phương pháp S3C2 3.2.1. Giới thiệu sơ lược Hầu hết các cách tiếp cận SSC (Semi-Supervised Clustering) đều dựa vào việc điều chỉnh một phần nào đó của các phương pháp phân cụm không giám sát hiện có, để chuyển các tri thức nhãn lớp vào vào giải thuật phân cụm [7, 8, 9, 10, 11, 12]. Chẳng hạn như giải thuật COP-k-Means, dựa trên các ràng buộc must- link, đã tạo ra các siêu thể hiện, rồi sau đó thực hiện phân cụm giống như k- Means và bổ sung thêm việc xử lý ràng buộc cannot-link trong quá trình phân cụm. Gần đây, người ta đã chứng minh rằng các phương pháp phân cụm phân loại (discriminative clustering), phân cụm bằng cách sử dụng các công cụ phân lớp, thường hiệu quả hơn trong việc tận dụng các thông tin ràng buộc (nhãn lớp). Song, các phương pháp này lại có nhược điểm trong trường hợp số lượng cụm lớn mà số lượng các ràng buộc lại nhỏ, chúng thường cho chất lượng phân cụm kém. Śmieja, Marek & Struski, Łukasz & Figueiredo, Mário đã đưa ra một cải tiến so với các phương pháp phân cụm phân loại khác, giúp khắc phục nhược điểm này và tách SSC thành hai giai đoạn. Cụ thể: Giai đoạn 1: Xây dựng bộ phân lớp nhị phân dự đoán quan hệ theo cặp giữa các cặp điểm không gán nhãn (là must-link hay cannot-link). Từ đó cho phép gán nhãn quan hệ cho các cặp điểm không được gán nhãn lớp, do đó làm tăng số lượng các cặp được gán nhãn. Giai đoạn 2: Sử dụng các cặp được gán nhãn, bao gồm các cặp cho trước và được dự đoán thêm, vào phương pháp phân cụm bán giám sát. Phương pháp này được nhóm tác giả đặt tên là S3C2 (Semi-Supervised Siamese Classifiers for Clustering), và có mô hình tổng quan như hình bên dưới:
  35. 28 Hình 3.1 Mô hình S3C2 Trong đó, giai đoạn 1, bộ phân lớp nhị phân được xây dựng bằng một mạng nơ-ron Siamese, được các tác giả gọi là LabNet (labeling network). Mạng được sử dụng để phân loại các cặp điểm có ràng buộc là must-link hay cannot- link. Ở giai đoạn 2, các tác giả sử dụng thêm một mạng nơ-ron Siamese thứ hai, được gọi là CluNet (clustering network). Mạng được huấn luyện trên các cặp đối tượng đã được gán nhãn ràng buộc là must-link hay cannot-link để dự đoán cụm cho các đối tượng. 3.2.2 Chi tiết mô hình Kí hiệu và công thức Gọi X ∈ ℝ là tập dữ liệu, trong đó với mọi điểm x ∈ X thuộc về một trong K lớp. Mục tiêu của bài toán là phân tách Χ thành K cụm, tương thích với các lớp thực tế (chưa biết). Giả sử rằng, phần thông tin nhãn lớp được cho trước dưới dạng các ràng buộc theo cặp, cho biết hai đối tượng thuộc cùng một lớp (ràng buộc must-link) hay thuộc các lớp khác nhau (ràng buộc cannot-link). Một cách hình thức, thông tin nhãn lớp được thể hiện thông qua tập Լ ⊂ X × X, trong đó Լ = Ϻ ∪ Ϲ, và Ϻ = {( , ) ∈ X × X, với x và y thuộc cùng một lớp} Ϲ = {( , ) ∈ X × X, với x và y thuộc các lớp khác nhau} Bởi vì quan hệ nhị phân (binary relation) “thuộc cùng một lớp” là phản xạ (reflexive), nên ta có Ϻ chứa |Χ| cặp ( , ). Hơn nữa, các quan hệ nhị phân “thuộc cùng một lớp” và “thuộc các lớp khác nhau” là đối xứng (symmetric), nên ta lại có: ( , ) ∈ Ϻ → ( , ) ∈ Ϻ và ( , ) ∈ Ϲ → ( , ) ∈ Ϲ Cuối cùng, gọi U= Χ2 \ Լ là tập tất cả các cặp điểm chưa được gán nhãn.
  36. 29 Mô hình S3C2 bao gồm hai mạng nơ-ron phân lớp. Mạng LabNet được huấn luyện để gán nhãn (must-link hoặc cannot-link) cho các cặp đối tượng chưa được gán nhãn không thuộc Լ. Mạng CluNet học từ các cặp đã được gán nhãn để dự đoán cụm cho các đối tượng. Mạng gán nhãn: LabNet Thay vì thực hiện luôn SSC một cách trực tiếp, có thể là một bài toán đa lớp khó khăn, trước tiên phương pháp đi giải bài toán phân loại nhị phân đơn giản hơn rất nhiều: học để gán nhãn cho các cặp điểm không thuộc Լ là must- link (thuộc cùng một lớp) hay cannot-link (thuộc các lớp khác nhau). Bằng cách gán nhãn cho các cặp thuộc U và không thuộc Լ, S3C2 đã khắc phục được nhược điểm của các phương pháp SSC khác về chất lượng phân cụm khi số lượng các cặp được gán nhãn cho trước rất ít. Các cặp đối tượng được gán nhãn cho trước, và được gán nhãn bởi LabNet sẽ được sử dụng để huấn luyện CluNet học cách gán cụm cho các đối tượng. Mạng LabNet mà phương pháp sử dụng là một mạng SNN. Chức năng của mạng là từ mỗi cặp điểm ( , ) đầu vào, mạng sẽ trả ra cặp thể hiện (ℎ( ), ℎ( )). Dựa vào đó, phương pháp sẽ tính toán được x gần hay xa y, tương ứng( , ) ∈ Ϻ hay( , ) ∈ Ϲ, bằng cách tính khoảng cách Euclide giữa hai điểm h(x) và h(y): ( , ) = ‖ℎ( ) − ℎ( )‖, sau đó so sánh ( , ) với một ngưỡng cho trước Ƭ. Nếu ( , )2 < Ƭ thì cặp x và y sẽ được gán nhãn must-link, ngược lại thì nhãn được gán là cannot-link. Cấu trúc của mạng LabNet được mô tả như hình bên dưới: Hình 3.2 Cấu trúc mạng LabNet Mạng được huấn luyện bằng cách tối ưu hàm mất mát contrastive, hàm có công thức như sau:
  37. 30 1 퐿 표푛푡 (Ϻ, Ϲ) = ( ∑ ( , )2 + ∑ {1 − ( , ), 0}2) |Լ| ( , )∈Ϻ ( , )∈Ϲ Sau khi được huấn luyện, LabNet sẽ được sử dụng để gán nhãn cho tất cả các cặp điểm dữ liệu, ta có: Ϻ̃ = Ϻ ∪ {( , ) ∈ U, với ( , )2 < Ƭ} Ϲ̃ = Ϲ ∪ {( , ) ∈ U, với ( , )2 ≥ Ƭ} dẫn đến Ϻ̃ ∪ Ϲ̃ = Χ2. Mạng gán cụm: CluNet Bằng cách áp dụng LabNet cho các cặp không được gán nhãn nên tất cả các cặp trong tập dữ liệu đều được gán nhãn, cuối cùng việc phân cụm có thể được thực hiện theo cách hoàn toàn được giám sát. Thay vì sử dụng một phương pháp phân cụm không giám sát điển hình, phương pháp sử dụng một khung phân loại – vốn hiệu quả hơn với các bài toán học có giám sát. Cụ thể, phương pháp trực tiếp mô hình phép gán cụm bởi các xác suất có điều kiện: ( ) = ( | ), 푣ớ푖 = 1, , 퐾 Từ các ướng lượng các xác suất có điều kiện này, Χ có thể được phân hoạch bằng việc gán mỗi điểm ∈ 훸 cho cụm k thỏa mãn ( ) là đạt cực đại. Mạng CluNet mà phương pháp sử dụng mà một SNN, bao gồm một cặp hai mạng DNNs (Dense Deep Neural Networks) giống hệt nhau và chia sẻ trọng số. Ở đó, với mỗi cặp điểm( , ) được xử lý bởi cả hai mạng con này. Với softmax output layer, hai mạng con con sẽ mang lại tương ứng hai xác suất có điều kiện 1( ), , ( ) và 1( ), , ( ) cho mỗi cặp điểm ( , ). Cấu trúc của mạng CluNet được mô tả như hình bên dưới: Hình 3.3 Cấu trục mạng CluNet
  38. 31 Để hình thành các cụm phù hợp với các ràng buộc theo cặp, mục tiêu của phương pháp là giảm thiểu số lượng các cặp được phân loại sai. Lưu ý rằng, với các xác suất có điều kiện 1( ), , ( ) và 1( ), , ( ) cho mỗi cặp điểm ( , ), xác suất để x và y nằm trong cùng một cụm được phương pháp xác định bởi: 퐾 푠 ( , ) = ∑ ( ) × ( ) =1 và ( , ) = 1 − 푠( , ) là xác suất để x và y nằm ở các cụm khác nhau. Từ đó, phương pháp định nghĩa hàm mất mát misclassification trên tập các ràng buộc must-link Ϻ̃ và tập các ràng buộc cannot-link Ϲ̃ như sau: 1 퐿 푖푠 푙(Ϻ̃, Ϲ̃) = ( ∑ (1 − 푠( , )) + ∑ 푠( , )) |훸|2 ( , )∈Ϻ̃ ( , )∈Ϲ̃ Việc huấn luyện cho mạng CluNet được thực hiện bằng việc tối ưu hàm mất mát 퐿 푖푠 푙(Ϻ̃, Ϲ̃). 3.3. Đánh giá mô hình Chúng tôi sử dụng ba độ đo để đánh giá chất lượng mô hình phân cụm, đó là: - Normalized Mutual Information (NMI) [14] - Adjusted Rand Index (ARI) [13] - Rand Index (RI) [13] Normailized Mututal Information Giả sử hai phép gán nhãn (cho cùng N đối tượng), U và V. Entropy của chúng là lượng không chắc chắn của một phân hoạch, được xác định bởi: |푈| (푈) = − ∑ 푃(푖)log( 푃(푖)) 푖=1 trong đó, 푃(푖) = |푈푖|⟋ là xác suất để một đối tượng được chọn ngẫu nhiên từ U rơi vào lớp 푈푖. Tương tự như vậy đối với V: | | ( ) = − ∑ 푃′(푗)log( 푃′(푗)) 푗=1 với 푃′(푗) = | 푗|⟋ . Thông tin tương hỗ (Mutual Information: MI) giữa U và V được tính như sau: |푈| | | 푃(푖, 푗) (푈, ) = ∑ ∑ 푃(푖, 푗) log ( ) 푃(푖)푃′(푗) 푖=1 푗=1
  39. 32 trong đó 푃(푖, 푗) = |푈푖 ∩ 푗|⟋ là xác suất để một đối tượng được chọn ngẫu nhiên thuộc cả hai lớp 푈푖 và 푗. Khi đó, độ đo NMI được xác định như sau: (푈, ) (푈, ) = 푒 푛( (푈), ( )) Hình minh họa: Hình 3.4 NMI Adjusted Rand Index Giả sử C là phép gán nhãn chân thật của các đối tượng, còn K là bộ phân cụm, chúng ta định nghĩa a và b như sau: - a là số lượng các cặp điểm ở cùng một tập trên C và cùng một tập trên K - b là số lượng các cặp điểm ở các tập khác nhau trên C và ở các tập khác nhau trên K Chỉ số (unadjusted) Rand index được cho bởi: + 푅 = 푛푠 푙푒푠 2 푛푠 푙푒푠 trong đó, 2 là tổng số lượng các cặp có thể ghép trong tập dữ liệu (không phân biệt thứ tự) – tổ hợp chập 2 của n. Tuy nhiên, chỉ số RI không đảm bảo rằng các phép gãn nhãn ngẫu nhiên sẽ có giá trị gần bằng 0 (đặc biệt nếu số cụm có cùng độ lớn với số lượng mẫu). Để tránh được hạn chế này, ARI thực hiện chiết khấu RI dự kiến – E(RI) của các phép gãn nhãn ngẫu nhiên, cụ thể: 푅 − [푅 ] 푅 = (푅 ) − [푅 ]
  40. 33 CHƯƠNG 4. THỬ NGHIỆM 4.1. Giới thiệu Trong quá trình thực hiện luận văn, chúng tôi đã cài đặt chương trình cho phương pháp phân cụm S3C2 được trình bày trong chương 3. Chương trình thực hiện chạy thử nghiệm phân cụm trên bộ dữ liệu hoa Iris. Ngoài việc đưa ra các kết quả đạt được từ chương trình do chúng tôi tự cài đặt, luận văn còn đưa ra một số kết quả phân cụm của một số phương pháp khác của các tác giả khác thực hiện. Từ đó, chúng tôi làm rõ được những ưu điểm và nhược điểm của phương pháp được cài đặt trong luận văn. Ngoài việc thực hiện chạy thử nghiệm phân cụm trên bộ dữ liệu Iris – có kích thước khá nhỏ và số cụm chỉ là 3, chúng tôi tiến hành thử nghiệm thêm trên một bộ dữ liệu có kích thước lớn hơn, số cụm nhiều hơn, số chiều cũng lớn và phức tạp hơn. Đó là bộ dữ liệu chữ số viết tay MNIST. Từ đó, chúng ta có thể thấy phương pháp hoạt động tốt trên cả các loại dữ liệu phức tạp và có kích thước lớn, ngay cả khi với số lượng các cặp điểm được gán nhãn khá bé. Điều mà có thể khiến các phương pháp phân cụm khác gặp khá nhiều khó khăn. 4.2. Chương trình Chương trình cài đặt phương pháp phân cụm S3C2, bằng ngôn ngữ Python. Các thử nghiệm được chạy trên môi trường Python 3.7 với các thông số phần cứng như sau: - OS Name: Microsoft Windows 10 Pro - Processor: Intel(R) Core(TM) i5-8265U CPU @ 1.60GHz, 1800 Mhz, 4 Core(s), 8 Logical Processor(s) - System Type: x64-based PC Chương trình gồm 3 module chính: - dataset: có chức năng load và cung cấp dataset cho các module khác - labnet: xây dựng mô hình phân lớp nhị phân bằng mạng nơ-ron (cụ thể mạng Siamese), gán nhãn cho các cặp dữ liệu - clunet: xây dựng mạng gán cụm, thực hiện phân cụm trên tập dữ liệu, đánh giá chất lượng phân cụm, trực quan hóa mô hình phân cụm, kết quả phân cụm bằng các biểu đồ, hình ảnh. 4.2.1. Module dataset Module thực hiện load dữ liệu cần phân cụm từ các thư viện có sẵn của Python hoặc load từ file csv. Đầu ra gồm hai tập dữ liệu: dữ liệu huấn luyện và dữ liệu kiểm thử mô hình. Dữ liệu được biểu diễn dưới dạng các vector. 4.2.2. Module labnet Module labnet lại được chia thành các module con, cụ thể như sau:
  41. 34 - distances: định nghĩa các hàm là độ đo khoảng cách, được sử dụng trong mạng labnet - loss: định nghĩa hàm mất mát được sử dụng trong mạng labnet - signet: xây dựng kiến trúc cụ thể cho mạng SNN – Siamese Neural Networks, huấn luyện mạng như một bộ phân lớp nhị phân để có khả năng gán nhãn cho các cặp điểm dữ liệu - evaluation: cung cấp các hàm dùng để đánh giá mô hình phân lớp - visualization: trực quan hóa kết quả phân lớp, kiến trúc mạng dưới dạng các biểu đồ, hình ảnh. - pairgen: generate các cặp dữ liệu có gắn nhãn must-link hoặc cannot-link, bao gồm dữ liệu huấn luyện và dữ liệu kiểm thử 4.2.3. Module clunet Tương tự như module labnet, module clunet cũng được chia thành các module con, cụ thể như sau: - loss: định nghĩa hàm mất mát được sử dụng trong mạng clunet - visualization: trực quan hóa kết quả phân cụm dưới dạng các biểu đồ và hình ảnh - clunet: xây dựng kiến trúc cụ thể cho mạng clunet, thực hiện huấn luyện mạng để có khả năng gán cụm trên các đối tượng - pairgen: generate các cặp dữ liệu sử dụng cho việc huấn luyện mô hình, sử dụng mạng labnet để gán nhãn must-link, cannot-link cho các cặp dữ liệu chưa gán nhãn. 4.3. Dữ liệu thử nghiệm Hai bộ cơ sở dữ liệu được sử dụng để thử nghiệm trong chương trình gồm dữ liệu về hoa Iris và dữ liệu chữ số viết tay MNIST, được lấy lần lượt ở hai địa chỉ sau: - Iris: - MNIST: 4.3.1. Dữ liệu hoa Iris Bộ dữ liệu hoa Iris hay còn được gọi là Fisher’s Iris được giới thiệu bởi British và Ronald Fisher trong bài năm 1936 của họ. Bộ dữ liệu bao gồm 50 mẫu cho mỗi ba loài hoa Iris: Iris setosa, Iris virginica và Iris versicolor.
  42. 35 Hình 4.1 Hoa Iris Bốn thuộc tính được đo từ mỗi mẫu là: - Chiều dài đài hoa (sepal length), - Chiều rộng đài hoa (sepal width), - Chiều dài cánh hoa (petal length), - Chiều rộng cánh hoa (petal width) Cả bốn thuộc tính đều được tính trên đơn vị cm. 4.3.2. Dữ liệu chữ số viết tay MNIST MNIST là bộ cơ sỡ dữ liệu lớn nhất về chữ số viết tay, bao gồm một bộ huấn luyện gôm 60k mẫu và một bộ kiểm thử 10k mẫu. Mỗi mẫu là một bức ảnh đen trắng có kích thước 28 × 28 pixel. Dưới đây là một ví dụ về một mẫu chữ số viết tay trong MNIST: Hình 4.2 Một mẫu chữ số 2 viết tay 4.4. Thử nghiệm trên bộ dữ liệu hoa Iris 4.4.1. Kịch bản thử nghiệm Chúng tôi thực hiện chạy chương trình nhiều lần, dữ liệu huấn luyện được thay đổi cho các lần chạy lần lượt là 30, 60, 90, 120, 140, 160 cặp dữ liệu được gán nhãn must-link hoặc cannot-link. Ban đầu, chúng tôi thực hiện chạy chương trình với 30 cặp dữ liệu, và thực hiện chạy 20 lần, mỗi lần trong 20 lần chạy này, 30 cặp dữ liệu đều được
  43. 36 sinh ra ngẫu nhiên và khác nhau. Chúng tôi sử dụng các chỉ số NMI, ARI, RI để đánh giá chất lượng phân cụm. Các kết quả NMI, ARI, RI cuối cùng sẽ là NMI, ARI, RI trung bình của 20 lần chạy. Tương tự như vậy, chúng tôi lần lượt thực hiện chạy chương trình phân cụm với số cặp dữ liệu cho trước là 60, 90, 120, 140, 160 cặp, và với mỗi loại số cặp chúng tôi đều thực hiện 20 lần và lấy kết quả trung bình cho các lần chạy đó. Các tham số mô hình cũng như các siêu tham số được sử dụng cho các lần chạy đều giống nhau. Cụ thể, mạng LabNet được huấn luyện với thuật toán tối ưu RMSprop, learning rate 0.001, threshold Ƭ = 0.2, và max epoch 100. Thuật toán tối ưu Adam được sử dụng trong việc huấn luyện mạng CluNet, với các tham số như sau: learning rate 0.001, lặp lại 2000 lần. Với mỗi lần lặp chương trình sử dụng LabNet để generate ngẫu nhiên 100 cặp từ tập các điểm chưa được gán nhãn ràng buộc theo cặp, và generate ngẫu nhiên 10 cặp từ tập các cặp đã gán nhãn ràng buộc cho trước. Kiến trúc mạng LabNet đươc sử dụng cho các lần chạy đều giống nhau, và có mô tả như hình bên dưới: Hình 4.3 Cấu trúc chi tiết mạng LabNet khi dữ liệu được sử dụng là Iris Tương tự, mạng CluNet được sử dụng cho các lần chạy đều có kiến trúc như sau:
  44. 37 Hình 4.4 Cấu trúc chi tiết mạng CluNet khi dữ liệu được sử dụng là Iris 4.4.2. Kết quả thử nghiệm Dưới đây là các biểu đồ mô tả các kết quả nhận được, khi chạy chương trình phân cụm trên bộ dữ liệu Iris với tham số số lượng cặp gắn nhãn cho trước lần lượt là 30, 60, 90, 120, 140, 160 cặp:
  45. 38 Hình 4.5 Kết quả phân cụm trên bộ dữ liệu Iris Đường màu xanh lá cây biểu diễn cho chỉ số RI trung bình cho 20 lần chạy độc lập và khác nhau, đường màu xanh lam biểu diễn cho ARI trung bình, đường màu vàng biểu diễn cho NMI trung bình. Chúng tôi cũng thực hiện đo đạc thời gian chạy chương trình. Tổng số lần chạy là 6 × 20 = 120. Tổng thời gian chạy cho 120 lần là 3827 giây, khoảng 63.78 phút. Trung bình mỗi lần chạy khoảng 31.89 giây. Dưới đây chúng tôi sẽ trích dẫn một số biểu đồ về kết quả phân cụm của một số phương pháp khác: SSGC, SSDBSCAN, SSK-Means, MCSSGC [5,6] cũng trên bộ dữ liệu hoa Iris: Hình 4.6 Kết quả phân cụm của một số phương pháp khác trên bộ dữ liệu Iris
  46. 39 4.4.3. Nhận xét Biểu đồ trong hình 4.5 cho thấy kết quả phân cụm trên bộ dữ liệu hoa Iris do chúng tôi cài đặt và thực nghiệm theo phương pháp S3C2 qua các lần chạy với số lượng cặp dữ liệu khác nhau đều cho chỉ số RI trung bình trên 0.996. Còn các phương pháp SSGC, SSDBSCAN, SSK-Means, MCSSGC chỉ đạt RI khoảng 0.95 như hình 4.6. Do đó, chúng ta có thể khẳng định rằng, phương pháp do Marek Śmieja, Łukasz Struski, Mário A. T. Figueiredo [1] đề xuất, cho kết quả tốt hơn dù với số cặp dữ liệu cho trước là như nhau hoặc thậm chí ít hơn. 4.5. Thử nghiệm trên bộ dữ liệu MNIST 4.5.1. Kịch bản thử nghiệm Tương tự kịch bản thực nghiệm với bộ dữ liệu hoa Iris, chúng tôi cũng thực hiện chạy chương trình nhiều lần với số lượng cặp dữ liệu đầu vào thay đổi lần lượt là 100, 200, 500, 1000, 2000, 5000 cặp. Và với mới loại số cặp đầu vào, chúng tôi cũng thực hiện 5 lần độc lập với nhau, và lấy kết quả ARI, NMI, RI trung bình cho 5 lần chạy đó. Mạng LabNet vẫn được huấn luyện bằng thuật toán tối ưu RMSprop, với các tham số như sau: learning rate 0.001, threshold Ƭ = 0.5, và max epoch 100. Thuật toán tối ưu Adam cũng được sử dụng để huấn luyện mạng CluNet với bộ tham số: learning rate 0.001, lặp lại 2000 lần. Về mặt kiến trúc, các mạng LabNet và CluNet được sử dụng để phân cụm cho bộ dữ liệu MNIST là giống hệt so với khi phân cụm cho bộ dữ liệu Iris. Chỉ khác nhau về hình dạng của dữ liệu đầu vào, đầu ra, và số lượng các nơ-ron trên mỗi layer. Hình bên dưới mô tả chi tiết cho cấu trúc mạng LabNet:
  47. 40 Hình 4.7 Cấu trúc mạng LabNet khi dữ liệu được sử dụng là MNIST Và hình bên dưới tiếp theo sẽ mô tả cho cấu trúc mạng nơ-ron được sử dụng trong mạng CluNet:
  48. 41 Hình 4.8 Cấu trụng mạng nơ-ron được sử dụng trong CluNet 4.5.2. Kết quả thử nghiệm Dưới đây là các biểu đồ mô tả các kết quả nhận được, khi chạy chương trình phân cụm trên bộ dữ liệu MNIST với tham số số lượng cặp gắn nhãn cho trước lần lượt là 100, 200, 500, 1000, 2000, 5000:
  49. 42 Hình 4.9 Kết quả phân cụm trên bộ dữ liệu MNIST Chúng tôi thực hiện đo đạc thời gian chạy chương trình, kết quả như sau. Tổng số lần chạy là 30 lần, tổng thời gian chạy là 12362 giây. Trung bình một lần chạy mất khoảng 412 giây (khoảng 6.87 phút). Dưới đây chúng tôi sẽ trích dẫn biểu đồ kết quả phân cụm của một số phương pháp khác: d-graph [16], DCPR [15], IDEC [17] và S3C2 do nhóm tác giả [1] đạt được cũng trên dữ liệu MNIST: Hình 4.10 Biểu đồ kết quả phân cụm một số phương pháp trên MNIST Cột màu xanh là cây biểu thị cho kết quả phân cụm theo chỉ số NMI của phương pháp S3C2 do nhóm tác giả [1] cài đặt và thực nghiệm. Các cột màu xanh lam, cột màu vàng và cột màu đỏ lần lượt biểu thị chỉ số NMI của các phương pháp d-graph, DCPR, IDEC. Chỉ số NMI của S3C2 trong biểu đồ ở hình 4.10 là NMI trung bình của 5 lần phân cụm trên 5 tập huấn luyện khác nhau.
  50. 43 Qua hình 4.10, chúng ta dễ dàng thấy được với số link dữ liệu là 500, 1000, 2000, 5000 phương pháp S3C2 do nhóm tác giả [1] thực nghiệm đạt kết quả tốt nhất trong 4 phương pháp. 4.5.3. Nhận xét Các biểu đồ trong hình 4.9 và hình 4.10 cho thấy kết quả phân cụm do chúng tôi cài đặt và thực nghiệm có độ chính xác khá gần với kết quả thực nghiệm của nhóm tác giả trong [1]. 4.6. Nhận xét thử nghiệm Qua quan sát các kết quả mà luận văn này đã thực nghiệm nhiều lần, chúng tôi đưa ra một số nhận xét như sau: 1. Phương pháp S3C2 có xu hướng cho kết quả phân cụm tốt hơn với số lượng cặp dữ liệu cho trước lớn hơn. Đặc biệt khi dữ liệu có kích thước lớn hơn, có số chiều lớn hơn, điều này càng được thấy rõ ràng hơn. 2. Trước khi tiến hành phân cụm bằng lượng thông tin thường rất ít ỏi về dữ liệu (các ràng buộc theo cặp), phương pháp S3C2 thực hiện huấn luyện mạng LabNet có khả năng gán nhãn must-link hoặc cannot-link cho các cặp dữ liệu mới. Từ đó khắc phục được nhược điểm của nhiều phương pháp phân cụm phân loại khác, thường rất khó khăn khi đươc sử dụng để phân cụm dữ liệu có kích thước lớn, số cụm lớn, nhưng lượng thông tin tri thức ban đầu về dữ liệu lại rất ít. 3. Phương pháp S3C2 cho thấy khả năng phân cụm tốt hơn so với khá nhiều phương pháp phân cụm tiên tiến hiện có khác như SSGC, SSDBSCAN, SSK-Means, MCSSGC [5,6] và d-graph [16], DCPR [15], IDEC [17]. Dù lượng tri thức ban đầu về dữ liệu cần phân cụm như nhau, nhưng S3C2 đã cho kết quả thực nghiệm nổi trội hơn. 4. S3C2 là một mô hình phân cụm có tính linh hoạt cao. Như thực nghiệm cho thấy, dù là với dữ liệu có kích thước và độ phực tạp nhỏ, hay dữ liệu có kích thước và số chiều lớn hơn, chúng ta có thể dùng chung một model để phân cụm: cùng kiến trúc mạng LabNet, CluNet; cùng hàm kích hoạt, cùng hàm mất mát.
  51. 44 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN Kết luận Sau thời gian nghiên cứu, dưới sự hướng dẫn tận tình của Thầy giáo PGS.TS. Hoàng Xuân Huấn, tôi đã trình bày luận văn “Phân cụm bán dựa trên tri thức theo từng cặp”. Luận văn đã đạt được các kết quả chính như sau: 1. Nghiên cứu tài liệu và hệ thống lại các kiến thức có liên quan sau: - Phân cụm dữ liệu - Các phương pháp cơ bản trong phân cụm dữ liệu - Phân cụm dựa trên ràng buộc - Mạng nơ-ron nhân tạo - Trình bày phương pháp phân cụm bán giám sát sử dụng kĩ thuật phân lớp trên mạng nơ-ron, phương pháp có tên S3C2 2. Cài đặt chương trình cho phương pháp phân cụm S3C2. Thực hiện chạy thử nghiệm trên 2 bộ dữ liệu: dữ liệu về loài hoa Iris, dữ liệu chữ số viết tay MNIST. Đưa ra các kết quả thử nghiệm, đồng thời so sánh kết quả với các phương pháp phân cụm bán giám sát khác. Thực nghiệm cho thấy chất phương pháp S3C2 có nhiều ưu điểm nổi trội và chất lượng hơn các phương pháp như SSGC, SSDBSCAN, SSK-Means, MCSSGC [5,6]. Kết quả cài đặt so sánh được với thực nghiệm của nhóm tác giả trong [1]. Hướng nghiên cứu tiếp theo Trong thời gian tới, tôi định hướng tập trung nghiên cứu, và thực hiện các công việc sau đây: 1. Nghiên cứu nhiều hơn về các phương pháp phân cụm cũng như phân cụm bán giám sát, nghiên cứu thêm về mạng nơ-ron nhân tạo và các thuật toán học sâu. Từ đó, tôi sẽ cố gắng đề xuất các phương pháp mới tốt hơn. 2. Tìm hiểu các vấn đề trong thực tế, từ đó có thể ứng dụng luận văn vào nhiều bài toán thực tiễn. Do thời gian nghiên cứu có hạn, cùng với những hạn chế trong năng lực của bản thân, luận văn khó tránh khỏi những thiếu sót. Tôi rất mong nhận được sự đóng góp của các Thầy Cô, các bạn đồng nghiệp để tôi có thể hoàn thiện luận văn với chất lượng tốt hơn. Cuối cùng, tôi xin gửi lời cảm ơn chân thành nhất tới Thầy PGS.TS. Hoàng Xuân Huấn. Thầy đã tận tình chỉ bảo, hướng dẫn em hoàn thành từng bước, từng phần của luận văn. Nhận được sự giúp đỡ của Thầy với em là một điều vô cùng may mắn, và quý giá. Em cũng xin cảm ơn tất cả các Thầy Cô đã giảng dạy cho em trong suốt quá trình theo học tại Trường Đại học Công nghệ - Đại học Quốc Gia Hà Nội.
  52. 45 TÀI LIỆU THAM KHẢO [1] M. Śmieja, Ł. Struski, and M. Figueiredo (2020), A Classification-Based Approach to Semi-Supervised Clustering with Pairwise Constraints, Neural Networks, vol.127, pp.193-203. [2] Jiawei Han, Micheline Kamber and Jian Pei (2012), Data Mining. Concepts and Techniques, 3rd Edition, Elsevier, Waltham. [3] Josh Patterson, Adam Gibson (2017), Deep Learning: A Practitioner’s Approach, O’Reilly Media, Sevastopol. [4] Rajul Anand, Chandan K. Reddy (2011), Graph-Based Clustering with Constraints, Advances in Knowledge Discovery and Data Mining, vol.6635, pp.51-62. [5] Viet-Vu Vu (2018), An Efficient Semi-Supervised Graph Based Clustering, Intelligent Data Analysis, vol.22, pp.297-307. [6] Viet-Vu Vu, Hong-Quan Do (2017), Graph-based Clustering with Background Knowlegde, In Proceedings of the Eighth International Symposium on Information and Communication Technology (SoICT 2017), pp.167-172. [7] D. Cheng, V. Murino, M. Figueiredo (2007), Clustering under prior knowledge with application to image segmentation, in: Advances in Neural Information Processing Systems (NIPS), pp.401-408. [8] M. Law, A. Topchy, A. Jain (2005), Model-based clustering with probabilistic constraints, in: SIAM Conference on Data Mining (SDM), pp.641-645. [9] Z. Lu, T. Leen (2004), Semi-supervised learning with penalized probabilistic clustering., in: Advances in Neural Information Processing Systems (NIPS), pp.849-856. [10] V. Melnykov, I. Melnykov, S. Michael (2016), Semi-supervised model- based clustering with positive and negative constraints, Advances in data analysis and classification 10 (3), pp.327-349. [11] M. Bilenko, S. Basu, R. Mooney (2004), Integrating constraints and metric learning in semi-supervised clustering, in: International Conference on Machine Learning (ICML), p.11. [12] P. Qian, Y. Jiang, S. Wang, K. Su, J. Wang, L. Hu, R. Muzic (2017), Affinity and penalty jointly constrained spectral clustering with all- compatibility, flexibility, and robustness, IEEE Transactions on Neural Networks and Learning Systems 28 (5), pp.1123-1138.
  53. 46 [13] L. Hubert, P. Arabie (1985), Comparing partitions, Journal of Classification, vol.2, pp.193-218. [14] Strehl, Alexander, and Joydeep Ghosh (2002), Cluster ensembles – a knowledge reuse framework for combining multiple partitions, Journal of Machine Learning Research, vol.3, pp.583-617. [15] Y. Pei, X. Fern, T. Tjahja, R. Rosales (2016), Comparing clustering with pairwise and relative constraints: A unified framework, ACM Transactions on Knowledge Discovery from Data (TKDD) 11 (2). [16] M. Smieja, O. Myronov, J. Tabor (2018), Semi-supervised discriminative clustering with graph regularization, Knowledge-Based Systems 151, pp.24–36. [17] H. Zhang, S. Basu, I. Davidson (2019), Deep constrained clustering- algorithms and advances, in: Joint European Conference on Machine Learning and Knowledge Discovery in Databases (ECML-EKDD), p.17.