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.
