MỞ ĐẦU Phân cụm dữ liệu là một kỹ thuật quan trọng trong công nghệ tri thức, nó đƣợc ứng dụng rộng rãi và đa dạng trong các ngành khoa học nhƣ sinh học, tâm lý học, y học, ngành marketing, thị giác máy tính, và điều kiển học v. Phân cụm dữ liệu tổ chức dữ liệu bằng cách nhóm các đối tƣợng có độ tƣơng đồng cao vào một cụm, các đối tƣợng thuộc các cụm khác nhau có độ tƣơng đồng thấp hơn so với các đối tƣợng trong cùng một cụm. Tùy theo đặc điểm cấu trúc của tập dữ liệu và mục đích sử dụng, có các phƣơng pháp giải quyết khác nhau nhƣ: Phân cụm dựa vào hàm mục tiêu, phân cụm phân cấp, phân cụm dựa vào mật độ và phân cụm dựa vào lƣới. Thông thƣờng, thông tin về thế giới xung quanh là không chính xác, không đầy đủ, không chắc chắn hoặc chồng chéo.
Đó cũng là vấn đề gặp phải khi phân cụm dữ liệu. Phân cụm đƣợc chia làm hai loại phân cụm là phân cụm cứng và phân cụm mềm. Trong phân cụm cứng đối tƣợng đƣợc phân thành các cụm khác nhau, mỗi đối tƣợng thuộc về chính xác một cụm, ngƣợc lại ở phân cụm mềm các đối tƣợng có thể thuộc về nhiều hơn một cụm và mỗi đối tƣợng có độ thuộc với cụm. Cụ thể trong luận văn, tôi sẽ nghiên cứu các thuật toán phân cụm trong cả hai loại phân cụm này: Phân cụm thô (phân cụm cứng) và phân cụm mờ (phân cụm mềm).
Ngoài ra tôi cũng nghiên cứu thêm về 2 thuật toán kết hợp từ hai loại phân cụm trên là phân cụm thô mờ và phân cụm bóng. Zadeh (Đại học California ở Berkeley) đề xuất lý thuyết tập mờ (fuzzy set), là phần mở rộng của lý thuyết tập hợp truyền thống. Ý tƣởng chính của lý thuyết tập mờ là các phần tử của tập có độ thuộc trong khoảng [0,1] thay vì giá trị nhị phân. Nó là công cụ mô hình hóa sự không chắc chắn, không rõ ràng trong hệ thống phức tạp.
Trong phân cụm mờ, thuật toán thƣờng đƣợc sử dụng nhất là Fuzzy C-Means (FCM) đƣợc đề xuất vào năm 1973 bởi J.C Dunn và đƣợc cải tiến lại bởi Bezděk vào năm 1981. FCM thƣờng đƣợc sử dụng để xử lý trƣờng hợp các cụm chồng chéo nhau, tức là một số đối tƣợng có thể thuộc về nhiều hơn một cụm. Trong đó, mỗi một đối tƣợng có độ thuộc khác nhau đối với các cụm, chứ không hoàn toàn chỉ thuộc về một cụm đƣợc biểu diễn qua ma trận phân hoạch. FCM sử dụng giá trị trung bình (mean) độ thuộc của các đối tƣợng trong ma trận phân hoạch làm tâm cụm.
Các bƣớc 9 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com trong thuật toán là quá trình thực hiện cập nhật các đối tƣợng của cụm và ma trận phân hoạch. Thuật toán chi tiết sẽ đƣợc trình bày cụ thể trong luận văn. Đến năm 1982, Zdzislaw Pawlak đề xuất ra lý thuyết tập thô với mục đích là để phân loại thông tin và tri thức không chính xác hoặc không đầy đủ. Khái niệm cơ bản của lý thuyết tập thô là xấp xỉ trên và xấp xỉ dƣới của một tập dữ liệu.
Xấp xỉ dƣới bao gồm những đối tƣợng chắc chắn thuộc về cụm, trong khi xấp xỉ trên bao gồm những đối tƣợng có thể đƣợc phân lớp là thành viên không chắc chắn của cụm. Mỗi tập đƣợc xác định thông qua xấp xỉ trên và xấp xỉ dƣới đƣợc gọi là tập thô. Trong khuôn khổ luận văn, tôi tìm hiểu và trình bày cụ thể thuật toán Rough C-Means (RCM). Thuật toán RCM đƣợc Lingras và West đề xuất năm 2004 [4].
Trong đó, mỗi cụm có vùng xấp xỉ trên và vùng xấp xỉ dƣới của riêng mình. Việc xác định cụm phụ thuộc vào hai vùng xấp xỉ, không phải tất cả các đối tƣợng nhƣ trong FCM. Cụ thể, nếu nhƣ FCM xác định cụm dựa vào độ thuộc của đối tƣợng vào cụm thì RCM lựa chọn cụm bằng cách so sánh khoảng cách từ đối tƣợng tới tâm cụm so với một ngƣỡng mà ngƣời dùng tự chọn. Tất cả các đối tƣợng đƣợc chia vào ba vùng, cụ thể là, vùng lõi (Core level), vùng biên (Boundary level) và vùng loại trừ (Exclusion level).
Các đối tƣợng nằm ở vùng lõi chắc chắn thuộc về cụm. Các đối tƣợng ở vùng biên có thể thuộc về cụm. Các đối tƣợng khác thuộc phạm vi vùng loại trừ không thuộc cụm. Ngoài ra, trong luận văn tôi trình bày chi tiết hai thuật toán nữa là phân cụm thô-mờ, phân cụm bóng tƣơng ứng là Rough Fuzzy C-Means (RFCM) và Shadowed C –Means (SCM).
RFCM là thuật toán kết hợp từ FCM và RCM, trong đó cách xác định cụm của RFCM giống nhƣ RCM là dựa vào hai vùng xấp xỉ trên và xấp xỉ dƣới. Tuy nhiên cách xác định các vùng xấp xỉ này không dựa vào khoảng cách từ các đối tƣợng tới tâm mà dựa vào độ thuộc của phần tử đối với cụm giống nhƣ FCM. Thuật toán này giúp cho việc phân cụm mạnh hơn so với hai thuật toán phân cụm trƣớc. Đối với SCM, các đối tƣợng cũng đƣợc chia vào ba vùng tƣơng tự nhƣ trong RCM nhƣng tên gọi và cách xác định mỗi vùng là khác nhau.
Ba vùng lõi, vùng biên và vùng loại trừ trong lý thuyết tập thô tƣơng ứng với ba giá trị logic 0,1, và [0,1] trong tập bóng, cụ thể, lõi (Core), loại trừ (Exclusion), bóng 10 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Ngoài ra, SCM tạo ra sự khác biệt với FCM là nó tăng độ thuộc của một số phần tử tới 1 và giảm độ thuộc của một số phần tử khác về 0 để làm tăng sự tƣơng phản của các phần tử nhằm làm giảm sự chồng chéo không chắc chắn nhƣ ở trong FCM. Theo khía cạnh này, tập bóng có thể đƣợc coi là cầu nối giữa tập mờ và thô. Hiện nay phân cụm ảnh là một vấn đề đang nhận đƣợc nhiều sự quan tâm từ các nhà nghiên cứu.
Mục đích là để đơn giản hóa hoặc làm nổi bật một số đối tƣợng nhằm dễ dàng hơn trong việc phân tích hình ảnh. Để phân cụm ảnh, phải chuyển các điểm màu của ảnh sang hệ màu xám với giá trị từ 0 đến 255 sau đó áp dụng thuật toán phân cụm. Trƣớc đây, FCM đƣợc sử dụng nhiều trong phân cụm ảnh và nó đƣợc ứng dụng trong nhiều lĩnh vực khác nhau nhƣ phân tích hình ảnh y tế, phát hiện các đối tƣợng,… Trong cuốn luận văn này, tôi đã nghiên cứu và áp dụng RCM cho phân cụm ảnh, từ đó so sánh sự khác biệt so với phân cụm ảnh sử dụng FCM. Luận văn của tôi đƣợc chia làm 4 chƣơng với nội dung nhƣ sau: Chƣơng 1: Tổng quan về phân cụm dữ liệu.
Giới thiệu về phân cụm dữ liệu và các phƣơng pháp phân cụm với mỗi phƣơng pháp trình bày một thuật toán tƣơng ứng. Chƣơng 2: Lý thuyết tập thô. Trình bày tổng quan về lý thuyết tập thô bao gồm hệ thông tin, hệ quyết định, tính không phân biệt đƣợc và xấp xỉ tập hợp. Chƣơng 3: Tập thô và bài toán phân cụm.
Giới thiệu các thuật toán phân cụm: Phân cụm thô, phân cụm mờ, phân cụm thô-mờ, phân cụm bóng, các bƣớc phân cụm và công thức chi tiết của từng thuật toán. Chƣơng 4: Ứng dụng RCM trong phân cụm ảnh. Xây dựng phân cụm ảnh bằng RCM, đƣa ra kết quả phân cụm, đánh giá và so sánh với phân cụm ảnh bằng FCM. 11 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com CHƢƠNG 1: TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU Bài toán phân cụm dữ liệu là một kỹ thuật trong khai phá dữ liệu thuộc lĩnh vực học không giám sát, nhằm tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn đƣợc quan tâm trong tập dữ liệu lớn, từ đó cung cấp các thông tin hữu ích hỗ trợ cho việc ra quyết định.
Các thuật toán phân cụm hƣớng tới việc tìm kiếm cấu trúc trong dữ liệu. Phƣơng pháp này còn đƣợc gọi là “học không thầy” hay “học không có giám sát” (Unsupervised Learning) trong lĩnh vực nhận dạng mẫu (Pattern Recognition) nói riêng và trong trí tuệ nhân tạo nói chung. Một cụm bao gồm một tập các đối tƣợng có độ tƣơng đồng cao. Định nghĩa về cụm đƣợc phát biểu một cách không hình thức nhƣ sau: Một cụm là một tập các thực thể (các đối tƣợng) tƣơng tự nhau, và các thực thể ở các cụm khác nhau thì không giống nhau.1 Ví dụ về phân cụm Tùy vào từng ứng dụng, đặc tính của dữ liệu và từng phƣơng pháp phân cụm cụ thể, chúng ta có thể xem xét các dữ liệu nhƣ là các điểm trong không gian thỏa mãn điều kiện độ tƣơng đồng giữa hai điểm bất kỳ trong một cụm lớn hơn độ tƣơng đồng giữa một điểm bất kỳ trong cụm đó với một điểm bất kỳ không thuộc cụm hoặc các cụm có thể đƣợc mô tả nhƣ là các vùng chứa các đối 12 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com tƣợng có mật độ cao trong không gian nhiều chiều, đƣợc tách với các vùng chứa các đối tƣợng có mật độ thấp hơn.
Chúng ta có thể dễ dàng phát biểu không hình thức về một cụm, nhƣng lại rất khó để có thể đƣa ra một định nghĩa hình thức về cụm. Bởi vì thực tế thì các đối tƣợng đƣợc nhóm vào trong các cụm theo các mục đích khác nhau trong từng ứng dụng. Dữ liệu có thể cho thấy các cụm theo hình dạng và theo các kích thƣớc cụm. Các vấn đề liên quan tới bài toán phân cụm dữ liệu là vấn đề biểu diễn dữ liệu trong máy tính, xác định phƣơng pháp, từ đó đƣa ra thuật toán cụ thể để áp dụng, đồng thời xác định độ tƣơng đồng giữa các đối tƣợng.
Đối với các thuật toán trong phƣơng pháp dựa vào phân hoạch thì chúng ta còn phải xây dựng hàm đánh giá phù hợp để thuật toán cho ra kết quả phân cụm tốt. Độ tương đồng Độ tƣơng đồng giữa các đối tƣợng mô tả tính chất giống hoặc khác nhau giữa chúng theo một ý nghĩa nào đó. Có rất nhiều hàm đƣợc dùng để biểu diễn độ tƣơng đồng giữa các đối tƣợng. Tuy nhiên, trong khuôn khổ của luận văn chỉ trình bày một số các hàm đo tƣơng đồng phổ biến gọi là các hàm khoảng cách.
Khoảng cách giữa hai mẫu thứ i và mẫu thứ k ký hiệu là d(i,k) phải thỏa mãn các tính chất sau: 1. Hàm đánh giá độ tƣơng đồng có thể đƣợc xác định theo một số cách. Giả sử rằng chúng ta có một ma trận mẫu [xij] với xij là giá trị của đặc trƣng thứ j của mẫu i. Tất cả các đặc trƣng là liên tục và đƣợc ƣớc lƣợng theo tỷ lệ xích.