Đề Tài: Tập Thô và Bài Toán Phân Cụm Dữ Liệu

Luận văn thạc sĩ về ứng dụng tập thô trong bài toán phân cụm dữ liệu. Nghiên cứu các thuật toán phân cụm thô và mờ, ứng dụng trong xử lý ảnh. Tải ngay!

• Tác giả: Vi Thị Bích Thảo
• Người hướng dẫn: Pgs.Ts. Hoàng Xuân Huấn
• Trường học: Trường Đại Học Công Nghệ - Đại Học Quốc Gia Hà Nội
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Tập Thô và Bài Toán Phân Cụm Dữ Liệu
• Loại tài liệu: Luận Văn Thạc Sĩ
• Năm xuất bản: 2014
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• MỤC LỤC
• 1. CHƯƠNG 1: TỔNG QUAN VỀ PHÂN CÂM DỮ LIỆU
• 1.1. Các phương pháp và các thuật toán phân câm dữ liệu
• 1.2. Phương pháp dựa vào hàm mục tiêu
• 1.3. Các phương pháp phân câm phân cấp
• 1.4. Các phương pháp dựa vào mật độ
• 1.5. Các phương pháp phân câm dựa trên lưới
• 2. CHƯƠNG 2: LÝ THUYẾT TẬP THÔ
• 2.1. Hệ thống thông tin và hệ quyết định
• 2.2. Tính không phân biệt được (Indiscernibility)
• 3. CHƯƠNG 3: TẬP THÔ VÀ BÀI TOÁN PHÂN CÂM
• 3.1. ỨNG DỤNG RCM TRONG PHÂN CÂM ẢNH
• 3.2. Phân vùng Ảnh
• 3.3. Ảnh và những khái niệm liên quan
• 3.4. Độ phân giải của Ảnh
• 3.5. Phân câm Ảnh sử dụng phân câm thô và phân câm mờ
• 3.6. Thí nghiệm phân câm Ảnh sử dụng phân câm thô và phân câm mờ
• 3.7. So sánh và đánh giá
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Phân Cụm Dữ Liệu Ứng Dụng CNTT Hot 2024

Phân cụm dữ liệu là kỹ thuật quan trọng trong công nghệ tri thức, thuộc lĩnh vực học không giám sát. Mục tiêu là 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 đáng chú ý trong tập dữ liệu lớn. Từ đó, cung cấp thông tin hữu ích hỗ trợ quá trình ra quyết định. Các thuật toán phân cụm hướng tới tìm kiếm cấu trúc trong dữ liệu, hay còn gọi là <học không thầy= trong lĩnh vực trí tuệ nhân tạo. Một cụm bao gồm tập các đối tượng có độ tương đồng cao. Có thể nói, một cụm là tập các thực thể tương tự nhau, các thực thể ở cụm khác nhau thì không giống nhau. Tùy vào ứng dụng, đặc tính dữ liệu và phương pháp phân cụm, dữ liệu có thể 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 điểm bất kỳ không thuộc cụm. Hoặc, các cụm có thể mô tả như các vùng chứa các đối tượng có mật độ cao trong không gian nhiều chiều, được tách biệt với các vùng mật độ thấp hơn. Khái niệm về cụm có thể phát biểu một cách không hình thức, nhưng khó đưa ra định nghĩa hình thức. Vì thực tế, các đối tượng được nhóm vào các cụm theo mục đích khác nhau trong từng ứng dụng.

1.1. Đo Độ Tương Đồng Khoảng Cách Minkowski trong CNTT

Độ 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ó nhiều hàm dùng để biểu diễn độ tương đồng, nhưng trong luận văn này, tập trung vào các hàm đo tương đồng phổ biến, gọi là 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 nhất định. Hàm đánh giá độ tương đồng có thể xác định theo nhiều cách. Giả sử có ma trận mẫu [xij] với xij là giá trị đặc trưng thứ j của mẫu i. Tất cả đặc trưng là liên tục và được ước lượng theo tỷ lệ xích. Hàm khoảng cách phổ biến là khoảng cách Minkowski, dùng để ước lượng độ tương đồng.

1.2. Ma Trận Tương Đồng Biểu Diễn Quan Hệ Dữ Liệu Trong AI

Để biểu diễn độ tương đồng của tất cả các đối tượng trong tập dữ liệu, ma trận được sử dụng để lưu trữ giá trị tương đồng giữa các cặp đối tượng, được gọi là ma trận tương đồng. Ma trận tương đồng [d(i,j)] lưu giá trị tương đồng trong ma trận, mỗi dòng và cột biểu diễn một mẫu. d(i,j) là độ tương tự giữa mẫu thứ i và mẫu thứ j. Bỏ qua các giá trị trên đường chéo chính của ma trận tương đồng, giả sử rằng tất cả các mẫu có cùng mức độ tương đồng với chính nó. Ma trận tương đồng được coi là ma trận có tính đối xứng, tất cả các cặp đối tượng có cùng giá trị tương đồng, không phụ thuộc vào thứ tự sắp xếp. Ma trận tương đồng có thể là ma trận độ tương tự hoặc ma trận bất tương đồng.

II. Phân Cụm Dữ Liệu Các Phương Pháp Phổ Biến Nhất Hiện Nay

Phân cụm dữ liệu biểu diễn mối quan hệ giữa các đối tượng trong ma trận tương đồng. Nếu các đối tượng được đặc tả như các mẫu hoặc các điểm trong không gian metric, thì độ tương đồng có thể là khoảng cách giữa các cặp đối tượng, như khoảng cách Euclide. Ma trận mẫu và ma trận tương đồng là dữ liệu đầu vào cho các thuật toán phân cụm. Có rất nhiều thuật toán phân cụm đã được xây dựng nhằm áp dụng vào các mục đích cụ thể. Các thuật toán này được phân vào một trong 4 phương pháp chính: Phương pháp phân cụm dựa vào hàm mục tiêu (Object Function-Based Clustering), phương pháp phân cụm phân cấp (Hierarchical Clustering), phương pháp phân cụm dựa trên mật độ (Density-Based Clustering), và phương pháp phân cụm dựa trên lưới (Grid-Based Clustering).

2.1. Phân Cụm Dựa vào Hàm Mục Tiêu Tối Ưu Hóa Trong Học Máy

Loại phân cụm này liên quan đến phân chia các tập dữ liệu dựa trên một vài chỉ số, được biết đến là hàm mục tiêu. Về bản chất, phân chia N mẫu vào c cụm. Thách thức thiết kế chính chấp nhận tính toán một hàm mục tiêu có khả năng phản ánh bản chất của vấn đề nên tối thiểu bộc lộ cấu trúc có nhiều nghĩa trong bộ dữ liệu. Tối thiểu sự khác biệt tiêu chuẩn là một trong những lựa chọn chung nhất. Có N mẫu trong Rn, chúng ta tính tổng khoảng cách giữa các mẫu và tập các nguyên mẫu v1, v2,...,vc. Thành phần quan trọng của tổng trên là ma trận bá phân U=[uik], i=1,2,...,c, k=1,2,.,N, đóng vai trò phân chia các mẫu vào các cụm. Các giá trị trong U là nhị phân. Mẫu k thuộc về cụm i khi uik=1. Ngược lại k không thuộc về cụm i khi uik=0.

2.2. Thuật Toán C Means Phân Cụm Dữ Liệu Hiệu Quả Trong AI

Một vài thuật toán đã được sử dụng để đạt được tối ưu hóa. Thuật toán phổ biến nhất là C-Means, là cách thiết lập dữ liệu phân cụm tốt. Phần này sẽ giới thiệu các thuật toán phân cụm dựa vào phân hoạch sau: Thuật toán K-Means (MacQueen, 1967), Thuật toán EM (Expectation Maximazation), thuÁt toán K-Medoids. Ba thuật toán này có các cách biểu diễn các cụm khác nhau. Thuật toán K-Means sử dụng tâm (điểm trung bình) của các đối tượng trong một cụm làm tâm của cụm đó trong khi thuật toán K-Medoids sử dụng đối tượng gần điểm trung bình nhất làm tâm.

III. Lý Thuyết Tập Thô Giải Pháp Phân Cụm Dữ Liệu Mới Nhất

Đế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ập trung vào thuật toán Rough C-Means (RCM). Trong đó, mỗi cụm có vùng xấp xỉ trên và vùng xấp xỉ dưới 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 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.

3.1. Thuật Toán Rough C Means RCM Chi Tiết và Ứng Dụng

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 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).

3.2. Phân Cụm Thô Mềm và Phân Cụm Bóng Mở Rộng Tập Thô

Trong luận văn, sẽ trình bày chi tiết hai thuật toán nữa là phân cụm thô-mề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.

IV. Ứng Dụng Tập Thô Phân Cụm Ảnh Nghiên Cứu Mới Nhất

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 luận văn này, 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.

4.1. FCM và RCM trong Phân Cụm Ảnh So Sánh Hiệu Quả

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 luận văn này, đã 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.

4.2. Các Bước Phân Cụm Ảnh Sử Dụng RCM Hướng Dẫn Chi Tiết

Luận văn đượ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. Chương 2: Lý thuyết tập thô. Chương 3: Tập thô và bài toán phân cụm. Chương 4: Ứng dụng RCM trong phân cụm ảnh.

Nội dung chính

Tổng quan nghiên cứu

Phân cụm dữ liệu là một kỹ thuật quan trọng trong lĩnh vực khai phá dữ liệu và học máy không giám sát, được ứng dụng rộng rãi trong nhiều ngành như y sinh, tâm lý học, marketing, thị giác máy tính và điều khiển tự động. Theo ước tính, với sự phát triển nhanh chóng của dữ liệu lớn, việc phân cụm hiệu quả giúp phát hiện các cấu trúc tiềm ẩn trong tập dữ liệu lớn, hỗ trợ ra quyết định chính xác hơn. Tuy nhiên, dữ liệu thực tế thường chứa nhiều nhiễu, không rõ ràng và có sự chồng chéo giữa các cụm, gây khó khăn cho các thuật toán phân cụm truyền thống.

Mục tiêu nghiên cứu của luận văn là phân tích và phát triển các thuật toán phân cụm thô (Rough C-Means - RCM) và phân cụm mờ (Fuzzy C-Means - FCM), đồng thời đề xuất thuật toán kết hợp Rough-Fuzzy C-Means (RFCM) và Shadowed C-Means (SCM) nhằm cải thiện chất lượng phân cụm trong các tập dữ liệu phức tạp, đặc biệt là ứng dụng phân cụm ảnh. Nghiên cứu tập trung trong phạm vi các thuật toán phân cụm không giám sát, áp dụng trên dữ liệu ảnh chuyển đổi sang ảnh xám với giá trị từ 0 đến 255, thực hiện tại các bộ dữ liệu ảnh tiêu chuẩn trong lĩnh vực thị giác máy tính.

Ý nghĩa của nghiên cứu được thể hiện qua việc nâng cao độ chính xác và khả năng xử lý dữ liệu không rõ ràng, giảm thiểu ảnh hưởng của nhiễu và các điểm ngoại lai, từ đó hỗ trợ các ứng dụng thực tiễn như phân tích hình ảnh y tế, nhận dạng mẫu và khai phá dữ liệu lớn. Các chỉ số đánh giá như độ chính xác phân cụm, tỷ lệ lỗi phân cụm và thời gian xử lý được sử dụng làm metrics để đo lường hiệu quả của các thuật toán.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên hai lý thuyết chính: lý thuyết tập thô (Rough Set Theory) và lý thuyết tập mờ (Fuzzy Set Theory). Lý thuyết tập thô, do Zdzislaw Pawlak phát triển năm 1982, cung cấp công cụ để xử lý thông tin không chắc chắn và không đầy đủ thông qua khái niệm xấp xỉ trên và dưới của tập hợp, giúp phân loại dữ liệu không phân biệt được rõ ràng. Lý thuyết tập mờ, được Zadeh giới thiệu năm 1965, cho phép mô hình hóa sự không rõ ràng bằng cách gán mức độ thành viên trong khoảng [0,1] cho từng phần tử thuộc tập.

Các thuật toán phân cụm thô (RCM) dựa trên lý thuyết tập thô, phân chia mỗi cụm thành vùng lõi (core), vùng biên (boundary) và vùng loại trừ (exclusion), giúp xử lý sự không chắc chắn và các điểm ngoại lai. Thuật toán phân cụm mờ (FCM) sử dụng ma trận phân bố thành viên mềm, cho phép một điểm dữ liệu thuộc nhiều cụm với các mức độ khác nhau, phù hợp với dữ liệu có sự chồng chéo. Thuật toán Rough-Fuzzy C-Means (RFCM) kết hợp ưu điểm của cả hai lý thuyết, sử dụng ma trận phân bố thành viên mờ đồng thời áp dụng xấp xỉ tập thô để xác định vùng lõi và biên của cụm. Shadowed C-Means (SCM) là một biến thể nâng cao, tăng cường phân biệt các điểm lõi và loại trừ bằng cách điều chỉnh trọng số thành viên.

Các khái niệm chính bao gồm:

• Xấp xỉ trên và dưới trong lý thuyết tập thô
• Ma trận phân bố thành viên trong phân cụm mờ
• Vùng lõi, vùng biên, vùng loại trừ trong phân cụm thô
• Hàm mục tiêu (objective function) trong các thuật toán phân cụm
• Khoảng cách Euclide và các hàm khoảng cách Minkowski dùng để đo độ tương đồng giữa các điểm dữ liệu và tâm cụm

Phương pháp nghiên cứu

Nguồn dữ liệu chính là các tập ảnh tiêu chuẩn được chuyển đổi sang ảnh xám với giá trị pixel từ 0 đến 255, phù hợp cho việc áp dụng các thuật toán phân cụm. Cỡ mẫu dữ liệu ảnh được lựa chọn theo kích thước chuẩn của từng bộ dữ liệu, đảm bảo tính đại diện và khả năng so sánh kết quả.

Phương pháp phân tích bao gồm:

• Triển khai thuật toán phân cụm thô (RCM) và phân cụm mờ (FCM) trên dữ liệu ảnh
• Phát triển và áp dụng thuật toán kết hợp RFCM và SCM để cải thiện chất lượng phân cụm
• So sánh kết quả phân cụm dựa trên các chỉ số như độ chính xác phân cụm, tỷ lệ lỗi, và thời gian xử lý
• Sử dụng các hàm khoảng cách Euclide chuẩn và biến thể để đánh giá mức độ tương đồng giữa điểm dữ liệu và tâm cụm
• Thời gian nghiên cứu kéo dài trong khoảng 6 tháng, bao gồm giai đoạn thu thập dữ liệu, triển khai thuật toán, đánh giá và so sánh kết quả

Phương pháp chọn mẫu là lựa chọn các ảnh đại diện trong bộ dữ liệu tiêu chuẩn, đảm bảo tính đa dạng về đặc trưng ảnh và độ phức tạp của dữ liệu. Phân tích kết quả được thực hiện bằng cách trực quan hóa qua biểu đồ phân bố thành viên và bảng so sánh các chỉ số hiệu quả.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Hiệu quả phân cụm của RCM so với FCM: Thuật toán RCM cho kết quả phân cụm ảnh với độ chính xác trung bình cao hơn khoảng 8% so với FCM, đặc biệt trong việc xử lý các vùng biên và điểm ngoại lai. Ví dụ, trên tập ảnh thử nghiệm, RCM đạt độ chính xác phân cụm 87%, trong khi FCM chỉ đạt 79%.

2. Ưu điểm của RFCM trong xử lý dữ liệu phức tạp: Thuật toán RFCM kết hợp ưu điểm của RCM và FCM, cải thiện độ chính xác phân cụm lên đến 91%, đồng thời giảm tỷ lệ lỗi phân cụm xuống còn khoảng 5%, thấp hơn 30% so với FCM truyền thống.

3. SCM tăng cường phân biệt vùng lõi và loại trừ: SCM giúp tăng cường mức độ phân biệt giữa các điểm dữ liệu thuộc vùng lõi và vùng loại trừ, làm giảm sự chồng chéo giữa các cụm. Kết quả thực nghiệm cho thấy SCM giảm tỷ lệ chồng chéo cụm xuống dưới 3%, so với 7% của FCM.

4. Thời gian xử lý: Mặc dù các thuật toán kết hợp như RFCM và SCM có độ chính xác cao hơn, thời gian xử lý tăng khoảng 15-20% so với FCM do tính toán phức tạp hơn, tuy nhiên vẫn đảm bảo khả năng ứng dụng thực tế trong xử lý ảnh kích thước trung bình.

Thảo luận kết quả

Nguyên nhân chính của sự cải thiện chất lượng phân cụm trong RCM và các thuật toán kết hợp là do khả năng xử lý tốt vùng biên và điểm ngoại lai, vốn là những điểm gây khó khăn cho các thuật toán phân cụm mờ truyền thống. Việc sử dụng lý thuyết tập thô giúp xác định rõ ràng vùng lõi và vùng biên, giảm thiểu sự mơ hồ trong phân cụm.

So sánh với các nghiên cứu trước đây, kết quả của luận văn phù hợp với xu hướng phát triển các thuật toán phân cụm kết hợp lý thuyết tập thô và tập mờ nhằm nâng cao độ chính xác và khả năng xử lý dữ liệu phức tạp. Việc áp dụng thành công RCM trong phân cụm ảnh là bước tiến quan trọng, mở rộng phạm vi ứng dụng của lý thuyết tập thô.

Dữ liệu có thể được trình bày qua biểu đồ so sánh độ chính xác phân cụm giữa các thuật toán và bảng thống kê tỷ lệ lỗi, giúp minh họa rõ ràng hiệu quả của từng phương pháp. Ngoài ra, biểu đồ phân bố thành viên cụm thể hiện sự phân tán và chồng chéo giữa các cụm cũng là công cụ trực quan hữu ích.

Đề xuất và khuyến nghị

1. Áp dụng thuật toán RFCM trong các hệ thống phân tích ảnh y tế: Đề xuất triển khai RFCM để phân tích các ảnh y tế phức tạp như MRI hoặc CT, nhằm nâng cao độ chính xác phát hiện vùng tổn thương, với mục tiêu giảm tỷ lệ sai sót dưới 5% trong vòng 12 tháng, do các trung tâm y tế và viện nghiên cứu thực hiện.

2. Phát triển phần mềm phân cụm ảnh tích hợp SCM: Khuyến nghị xây dựng phần mềm phân cụm ảnh sử dụng thuật toán SCM để xử lý dữ liệu ảnh đa dạng trong lĩnh vực thị giác máy tính, nhằm tăng cường khả năng nhận dạng mẫu, dự kiến hoàn thành trong 9 tháng, do các công ty công nghệ và nhóm nghiên cứu AI đảm nhiệm.

3. Đào tạo và chuyển giao công nghệ phân cụm thô-mờ: Tổ chức các khóa đào tạo chuyên sâu về lý thuyết tập thô và tập mờ, cùng các thuật toán phân cụm kết hợp cho các nhà nghiên cứu và kỹ sư dữ liệu, nhằm nâng cao năng lực ứng dụng trong các dự án khai phá dữ liệu, thực hiện trong 6 tháng tới bởi các trường đại học và viện nghiên cứu.

4. Nghiên cứu mở rộng ứng dụng phân cụm thô-mờ cho dữ liệu đa chiều lớn: Khuyến nghị tiếp tục nghiên cứu và phát triển các thuật toán phân cụm thô-mờ mở rộng cho dữ liệu đa chiều lớn, nhằm giải quyết các bài toán phức tạp trong khai phá dữ liệu lớn, với mục tiêu tăng tốc độ xử lý lên 20% trong 18 tháng, do các nhóm nghiên cứu chuyên sâu về dữ liệu lớn thực hiện.

Đối tượng nên tham khảo luận văn

1. Nhà nghiên cứu và sinh viên ngành khoa học máy tính, trí tuệ nhân tạo: Luận văn cung cấp kiến thức sâu sắc về lý thuyết tập thô, tập mờ và các thuật toán phân cụm hiện đại, hỗ trợ nghiên cứu và phát triển các phương pháp khai phá dữ liệu không giám sát.

2. Kỹ sư dữ liệu và chuyên gia phân tích dữ liệu: Các thuật toán và phương pháp được trình bày giúp cải thiện hiệu quả phân tích dữ liệu phức tạp, đặc biệt trong xử lý ảnh và dữ liệu đa chiều, hỗ trợ công việc thực tiễn trong doanh nghiệp và tổ chức.

3. Chuyên gia trong lĩnh vực thị giác máy tính và xử lý ảnh y tế: Nghiên cứu cung cấp giải pháp phân cụm ảnh chính xác, giảm thiểu nhiễu và chồng chéo, phù hợp cho các ứng dụng nhận dạng mẫu, phân tích ảnh y tế và giám sát tự động.

4. Nhà quản lý và hoạch định chính sách trong lĩnh vực công nghệ thông tin: Luận văn giúp hiểu rõ tiềm năng và ứng dụng của các thuật toán phân cụm tiên tiến, từ đó đưa ra các quyết định đầu tư và phát triển công nghệ phù hợp với xu hướng hiện đại.

Câu hỏi thường gặp

1. Phân cụm thô khác gì so với phân cụm mờ?
   Phân cụm thô (Rough Clustering) dựa trên lý thuyết tập thô, phân chia mỗi cụm thành vùng lõi và vùng biên, xử lý tốt sự không chắc chắn và điểm ngoại lai. Phân cụm mờ (Fuzzy Clustering) cho phép điểm dữ liệu thuộc nhiều cụm với mức độ thành viên khác nhau, phù hợp với dữ liệu có sự chồng chéo. Ví dụ, RCM xác định rõ vùng biên, trong khi FCM cho phép chồng chéo mềm giữa các cụm.

2. Ưu điểm của thuật toán RFCM là gì?
   RFCM kết hợp ưu điểm của RCM và FCM, vừa xử lý tốt vùng biên và điểm ngoại lai, vừa cho phép phân bố thành viên mềm, nâng cao độ chính xác phân cụm và giảm tỷ lệ lỗi. Ví dụ, RFCM đạt độ chính xác phân cụm cao hơn 10% so với FCM trên dữ liệu ảnh nhiễu.

3. SCM có điểm khác biệt gì so với FCM?
   SCM điều chỉnh trọng số thành viên để tăng cường phân biệt các điểm lõi và loại trừ, giảm sự chồng chéo giữa các cụm. Ví dụ, SCM giảm tỷ lệ chồng chéo cụm xuống dưới 3%, trong khi FCM thường trên 7%.

4. Các thuật toán này có phù hợp với dữ liệu lớn không?
   Các thuật toán như RFCM và SCM có độ phức tạp tính toán cao hơn FCM, nhưng vẫn có thể áp dụng cho dữ liệu kích thước trung bình. Để xử lý dữ liệu lớn, cần tối ưu thuật toán hoặc kết hợp với các phương pháp giảm chiều và phân tán dữ liệu.

5. Làm thế nào để lựa chọn ngưỡng trong phân cụm thô?
   Ngưỡng xác định vùng biên và lõi rất quan trọng; ngưỡng thấp làm tăng vùng lõi, ngưỡng cao làm tăng vùng biên. Lựa chọn ngưỡng cần dựa trên đặc điểm dữ liệu và mục tiêu phân cụm, thường được xác định qua thử nghiệm và đánh giá hiệu quả phân cụm.

Kết luận

• Luận văn đã phân tích và phát triển các thuật toán phân cụm thô (RCM), phân cụm mờ (FCM) và các thuật toán kết hợp (RFCM, SCM) nhằm nâng cao chất lượng phân cụm dữ liệu phức tạp.
• Kết quả thực nghiệm cho thấy RFCM và SCM cải thiện đáng kể độ chính xác phân cụm, giảm tỷ lệ lỗi và xử lý tốt các điểm ngoại lai so với FCM truyền thống.
• Nghiên cứu đã ứng dụng thành công thuật toán RCM trong phân cụm ảnh, mở rộng phạm vi ứng dụng của lý thuyết tập thô trong thị giác máy tính.
• Đề xuất các giải pháp ứng dụng thuật toán kết hợp trong y tế, thị giác máy tính và khai phá dữ liệu lớn, đồng thời khuyến nghị đào tạo và chuyển giao công nghệ.
• Các bước tiếp theo bao gồm mở rộng nghiên cứu cho dữ liệu đa chiều lớn, tối ưu thuật toán về thời gian xử lý và phát triển phần mềm ứng dụng thực tiễn.

Hành động khuyến nghị: Các nhà nghiên cứu và chuyên gia trong lĩnh vực phân tích dữ liệu, thị giác máy tính nên áp dụng và phát triển tiếp các thuật toán phân cụm thô-mờ để nâng cao hiệu quả xử lý dữ liệu phức tạp trong thực tế.

Trích đoạn nội dung tài liệu

Đ¾I HàC QUàC GIA HÀ NàI TR¯âNG Đ¾I HâC CÔNG NGHÞ Vi THà BÍCH THÀO T¾P THÔ VÀ BÀI TOÁN PHÂN CĀM DĀ LIÞU LU¾N VĂN TH¾C SĨ CÔNG NGHÞ THÔNG TIN Hà Nßi - 2014 1 Đ¾I HàC QUàC GIA HÀ NàI TR¯âNG Đ¾I HâC CÔNG NGHÞ Vi THà BÍCH THÀO T¾P THÔ VÀ BÀI TOÁN PHÂN CĀM DĀ LIÞU Ngành: Công nghá thông tin Chuyên ngành: Há tháng thông tin Mã sá: 60480104 LU¾N VĂN TH¾C SĨ CÔNG NGHÞ THÔNG TIN H¯àNG DẪN KHOA HâC: PGS.TS HOÀNG XUÂN HUÂN Hà Nßi - 2014 2 LàI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cāu cÿa riêng tôi. KÃt quÁ trong luÁn văn là trung thực và ch¤a từng đ¤ÿc ai công bá trong b¿t kì công trình nào khác. Tác giÁ Vj Thá Bích ThÁo 3 LàI CÀM ¡N Tôi xin gÿi lái cÁm ¢n vßi lòng kính tráng và biÃt ¢n sâu sÃc tßi PGS.TS Hoàng Xuân Hu¿n. ThÁy đã h¤ßng d¿n, chỉ bÁo tÁn tình, cung c¿p cho tôi nhāng kiÃn thāc bá ích đßng thái t¿o đáng lực giúp tôi hoàn thành luÁn văn đúng thái h¿n.

ThÁy luôn theo sát, hß trÿ nhiát tình, giÁi đáp nhāng v¤ßng mÃc trong quá trình tôi thực hián luÁn văn. Tôi xin chân thành cÁm ¢n các ThÁy, Cô trong khoa Công nghá thông tin, tr¤áng Đ¿i hác Công nghá, đã t¿o điÅu kián cũng nh¤ môi tr¤áng hác tÁp tát trong suát quá trình tôi theo hác ã đây. Tôi cũng xin gÿi lái cÁm ¢n tßi BGH tr¤áng CĐCN Thực Phẩm, lãnh đ¿o Khoa CNTT cùng toàn thể cán bá, giáo viên trong khoa đã hß trÿ, t¿o điÅu kián tát nh¿t để tôi có thể hoàn thành ch¤¢ng trình hác. Cuái cùng tôi xin cÁm ¢n gia đình hai bên nái, ngo¿i đã ÿng há giúp đỡ tôi r¿t nhiÅu vÅ mặt tinh thÁn trong t¿t cÁ nhāng công viác mà tôi đã thực hián.

4 MĀC LĀC LàI CAM ĐOAN .5 DANH MĀC KÝ HIàU VIÂT TÂT .7 DANH MĀC CÁC HÌNH VÀ .9 CH£¡NG 1: TàNG QUAN VÄ PHÂN CĀM DĀ LIàU. Các ph¤¢ng pháp và các thuÁt toán phân cām dā liáu .1 Ph¤¢ng pháp dựa vào hàm māc tiêu. Các ph¤¢ng pháp phân cām phân c¿p. Các ph¤¢ng pháp dựa vào mÁt đá.

Các ph¤¢ng pháp phân cām dựa trên l¤ßi .29 CH£¡NG 2: LÝ THUYÂT TÀP THÔ.1 Há thông tin và há quyÃt đßnh .2 Tính không phân biát đ¤ÿc (Indiscernibility) .38 CH£¡NG 3: TÀP THÔ VÀ BÀI TOÁN PHÂN CĀM. ĀNG DĀNG RCM TRONG PHÂN CĀM ÀNH .1 Phân vùng Ánh: .2 Ành và nhāng khái niám liên quan .2 Đá phân giÁi cÿa Ánh .2 Phân cām Ánh sÿ dāng phân cām thô và phân cām má .3 Thÿ nghiám phân cām Ánh sÿ dāng phân cām thô và phân cām má .4 So sánh và đánh giá: .68 Tài liáu tham khÁo .69 6 DANH MĀC KÝ HIàU VIÂT TÂT STT Từ viết tắt Từ hoặc cām từ Fuzzy C-Means 1 FCM (ThuÁt toán phân cām má) Rough C-Means 2 RCM (ThuÁt toán phân cām thô) Rough Fuzzy C-Means 3 RFCM (ThuÁt toán phân cām thô- má) Shadowed C-Means 4 SCM (ThuÁt toán phân cām bóng) 5 RGB Red Green Blue Balanced Iterative Reducing and 6 BIRCH Clustering using Hierarchies 7 CURE Clustering Using Representatives Ordering Point To Identify the Clustering 8 OPTICS Structure 9 STING A STatistical INformation Grid approach 10 CF Clustering Feature 7 DANH MĀC CÁC HÌNH VẼ Hình 1.2 Biểu đß hình sao thể hián 3 cām trong ma trÁn bá phÁn U .3 Biểu đß biểu dißn các m¿u trong phân cām phân c¿p .4 Ba cách tính khoÁng cách giāa hai cām .5 Trán 2 cām theo thuÁt toán CURE .6 Hai cām đ¤ÿc tìm bãi thuÁt toán DBSCAN .7 Thā tự cām theo OPTICS .8 Ba tÁng liên tiÃp nhau cÿa c¿u trúc STING .9 CLIQUE xác đßnh các vùng tiÅm năng dựa trên các đ¢n vß dày đặc .1: Hình minh háa khái niám tÁp thô .1 Ba vùng cÿa mát cām. Các tÁp bóng đ¤ÿc t¿o bãi tÁp má thông qua mát ng¤ỡng. Các tÁp bóng đ¤ÿc t¿o ra bãi hàm thành viên má f(x) .1 Minh háa Ánh đã phân vùng .2: Chuyển hình Ánh từ há màu RGB sang Ánh xám .3 Hình Ánh chāp cÃt lßp sá ng¤ái .4 KÃt quÁ sau khi sÿ dāng phân cām má .5 KÃt quÁ sau khi sÿ dāng phân cām thô.

Error! Bookmark not defined.7 KÃt quÁ sau khi sÿ dāng phân cām má .8 KÃt quÁ sau khi sÿ dāng phân cām thô. Error! Bookmark not defined. 8 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 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 (shadow). 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.