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

in 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 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 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 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 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 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 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 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]. 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]. 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 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 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) 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 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à 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 độ: 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