Chương 1: Giới thiệu Chương 2: Hướng giải quyết Chương 3: Mô hình, thuật toán Chương 4: Thực nghiệm Chương 5: Xây dựng ứng dụng Chương 6: Kết luận, hướng phát triển Tài liệu tham khảo Phụ lục: Thuật toán gom nhóm truyền thống: K-Means, spectral clustering, DBSCAN Tìm kiếm láng giềng gần nhất: giải thuật Brute Force, K-D Tree Độ do NMI, BCube-F CHƯƠNG 2. HƯỚNG GIẢI QUYẾT 2.1 Giới thiệu Bài toán gom nhóm dữ liệu khuôn mặt đối mặt một số thách thức, như trong trường hợp ảnh được chụp ở nhiều góc độ khác nhau, thay đổi độ sáng, bị che khuất, sự phân bố phức tạp của các biểu diễn khuôn mặt khiến cho việc áp dụng các phương phương pháp truyền thống như K-Means [1], Spectral Clustering [2], gặp khó khăn vì các phương pháp này thường đưa ra các giả định cứng nhắc về phân bố dữ liệu. Một số công trình nghiên cứu sau đó được phát triển có thé đạt hiệu quả tốt trên dir liệu có phân bố phức tạp như gom nhóm dữ liệu phân cấp Agglomerative Hierarchical Clustering (AHC) [3, 4, 5], phương pháp này mang lại hiệu suất tốt trên gom nhóm khuôn mặt, nhưng độ phức tạp tính toán của nó là một van dé, hạn chế khi ứng dụng trong gom nhóm quy mô lớn. Trong khi đó, các phương pháp gom nhóm dựa trên liên kết không đặt ra bat kỳ giả định nào về phân phối dữ liệu va đạt được độ chính xác cao hơn.
Luận văn sẽ trình bay một số phương pháp đặc trưng của các hướng tiếp cận gồm K-means, DBSCAN, phương pháp gom nhóm dựa trên liên kết. Từ đó, ta có cái nhìn tổng quan về các hướng tiếp cận hiện nay trong bài toán gom nhóm khuôn mặt.2 Các giải thuật gom nhóm truyền thống 2.1 Thuật toán K-Means Là một thuật toán gom nhóm phổ biến trong machine learning và data mining. Thuật toán này thường được sử dung để phân nhóm các điểm dữ liệu vào các nhóm dựa trên sự tương đồng giữa chúng. Thuật toán K-Means hoạt động như sau: - Bước 1: Chọn số lượng nhóm (K) cần tạo.
- Bước 2: Chọn ngẫu nhiên K điểm làm các điểm tâm ban đầu của các nhóm. - Bước 3: Gán từng điểm dữ liệu vào nhóm gần nhất bằng cách tính toán khoảng cách giữa điểm dữ liệu và các điểm tâm của các nhóm. 8 - Bước 4: Cập nhật lại vi trí của các điểm tâm bằng cách tính toán trung bình của các điểm dữ liệu thuộc cùng một nhóm. - Bước 5: Lặp lại bước 3 và 4 cho đến khi các điểm tâm không thay đổi hoặc đạt đến điều kiện đừng được xác định trước (ví dụ: số lần lặp tối đa).
Kết quả cuối cùng của thuật toán K-Means là các nhóm dữ liệu, mỗi nhóm được đại điện bởi một điểm tâm. Thuật toán K-Means tìm cách tối thiểu hóa tổng bình phương khoảng cách giữa mỗi điểm dữ liệu và điểm tâm của nhóm mà nó thuộc về. Tuy K-Means là một thuật toán gom nhóm đơn giản và hiệu quả, nhưng nó có nhược điểm là dựa trên giả định về hình dang nhóm là hình cầu và không thé xử lý tốt với các dạng nhóm phi tuyến. Điều này làm cho K-Means không phù hợp với các dữ liệu có phân phối phức tạp.2 Phân nhóm phố Phân nhóm phổ (Spectral clustering) là một phương pháp phân nhóm dựa trên phân tích phổ của ma trận liên kết (affinity matrix).
Phương pháp này thường được sử dụng để phân nhóm dữ liệu có độ phức tạp cao. Các bước thực hiện gồm: - Chuan bị dữ liệu: cần xây dựng ma trận liên kết (affinity matrix) từ dữ liệu ban đầu. Ma trận này thường được xây dựng bằng cách tính độ tương đồng hoặc độ tương tự giữa các điểm dữ liệu trong không gian đặc trưng. - Xây dựng ma trận Laplacian: từ ma trận liên kết, ta xây dựng ma trận Laplacian.
Ma tran Laplacian được tính bằng cách lấy ma trận liên kết trừ ma trận bậc (degree matrix). - Phan tích phổ: thực hiện phân tích phổ trên ma tran Laplacian dé thu được các vector riêng và giá trị riêng của nó. Các vector riêng tương ứng với giá trị riêng nhỏ nhất thường chứa thông tin về phân nhóm. - Phan nhóm: sử dung các vector riêng dé phân nhóm dữ liệu.
Một phương pháp đơn giản là sử dung giá trị ngưỡng (thresholding) trên các giá trị riêng dé phan tách các nhóm. Phương pháp phân nhóm phô thường hiệu quả cho việc phân nhóm các dữ liệu có cấu trúc phức tạp, không phụ thuộc vào hình dạng và kích thước của nhóm, được áp dụng rộng rãi trong nhiều lĩnh vực, bao gồm phân nhóm hình ảnh, phân tích dữ liệu xã hội, nhận dạng nhóm từ vựng trong xử lý ngôn ngữ tự nhiên và nhiều lĩnh vực khác. Phương pháp phân nhóm phé thường cho kết quả tốt trong việc xử lý các bài toán phân nhóm có tính chất phi tuyến. Tuy nhiên, nhược điểm của phương pháp này là yêu cầu tính toán ma trận Laplacian và giải bài toán trị riêng, đòi hỏi tài nguyên tính toán cao và có thể không thích hợp cho các tập dữ liệu lớn.3 Phân nhóm dựa trên mật độ DBSCAN Thuật toán phân nhóm dựa trên mật độ (Density-Based Spatial Clustering of Applications with Noise) được sử dụng để nhóm các điểm dữ liệu trong một tập dữ liệu dựa trên mật độ và khoảng cách giữa chúng.
Đây là một thuật toán phân nhóm không cần chỉ định số lượng nhóm trước và có khả năng phát hiện các nhóm có hình dạng và kích thước đa dạng. Các bước chính của thuật toán DBSCAN là: - Xác định các điểm hàng xóm: cho một điểm cho trước, các điểm trong tập dữ liệu, có khoảng cách nhỏ hơn epsilon từ điểm cho trước, được coi là hàng xóm của điểm đó. -_ Xác định điểm cốt lõi (core points): Nếu số lượng điểm hàng xóm của một điểm vượt qua một ngưỡng nhất định (MinPts), điểm đó được xem là điểm cốt lõi. - Xác định các nhóm: Nếu một điểm là điểm cốt lõi, tất cả các điểm hàng xóm của nó (và hàng xóm của hàng xóm) thuộc cùng một nhóm.
Tiếp tục quá trình này cho tới khi không còn điểm cốt lõi nào được tìm thấy. 10 - _ Xử lý điểm biên (border points): Các điểm không phải là điểm cốt lõi nhưng vẫn có hàng xóm thuộc cùng một nhóm được coi là điểm biên. Chúng được gán vào nhóm tương ứng. - _ Xử lý điểm nhiễu (noise points): Các điểm không thuộc vào bat kỳ nhóm nao được xem là điểm nhiễu hoặc ngoại lệ.
Các tham số quan trọng trong DBSCAN bao gồm: Epsilon (e): là bán kính xung quanh mỗi điểm, được sử dụng dé xác định xem một điểm có được coi là láng giềng của một điểm khác hay không MinPts: Đây là số lượng tối thiểu của các điểm láng giềng cần thiết để một điểm được xem là một điểm cốt lõi. So với K-Means, DBSCAN có những ưu điểm : Khả năng xử lý các nhóm có hình dạng và kích thước không đồng nhất: DBSCAN có khả năng xác định các nhóm có hình dạng phức tạp và không yêu cầu các nhóm có kích thước tương đồng. Trong khi đó, K-means tạo ra các nhóm có hình dạng hình cầu và có kích thước tương đồng. Khả năng xử lý nhiễu và ngoại lệ: DBSCAN có khả năng xử lý nhiễu và ngoại lệ.
Nó có thé xác định các điểm nhiễu và không gan chúng vào bất kỳ nhóm nao. Trong khi đó, K-means không có cơ chế xử lý nhiễu và ngoại lệ, nó phân nhóm tat cả các điểm dit liệu, kê cả nhiêu và ngoại lệ. Không yêu cầu số lượng nhóm được xác định trước: DBSCAN không đòi hỏi người dùng chỉ định số lượng nhóm trước. Nó tự động xác định số lượng nhóm dựa trên dữ liệu và tham số của thuật toán.
Trong khi đó, K-means yêu cầu số lượng nhóm cần phân chia được xác định trước. Khả năng xác định các vùng dày đặc dựa trên mật độ: DBSCAN phân nhóm dựa trên mật độ và tìm các vùng dày đặc của điểm dữ liệu. Điều này giúp DBSCAN phát hiện các nhóm dữ liệu có mật độ cao và có thê làm việc tôt trên các tập dữ liệu có mật II độ đồng nhất. Trong khi đó, K-means chỉ tập trung vào việc tối thiểu hóa tông bình phương khoảng cách giữa các điểm và điểm tâm (centroid) tương ứng.
Tuy nhiên thuật toán này cũng ton tại một số nhược điềm: Thuật toán này cần đặt các tham số như epsilon va MinPts một cách hợp lý dé đạt được kết quả tốt. Không hiệu quả với các tập dữ liệu có mật độ không đồng nhất. Không thê xác định các nhóm có hình dạng phức tạp.3 Hướng tiếp cận mới, phân nhóm dựa trên liên kết Các phương pháp phân nhóm dựa trên liên kết (linkage-based) không đặt giả thiết về phân bé dữ liệu và đạt độ chính xác cao hơn. Phương pháp đơn giản nhất dé dự đoán liên kết là tính độ đo khoảng cách L, từng cặp điểm, nếu L; nhỏ hơn hoặc băng một ngưỡng xác định T, ta dự đoán rằng các điểm có khả năng liên kết; ngược lại, chúng không liên kết.
Khi mật độ của các nhóm biến đổi, việc sử dụng một ngưỡng cé định có thé không phù hợp. Trong thực tế, dữ liệu có phân bố tương đối phức tạp, các phần tử dữ liệu có liên kết với nhiều phần tử khác theo một mối quan hệ chồng chéo, phức tạp. Người ta thường biểu diễn dit liệu dạng đồ thị, các phan tử là các đỉnh, các mối quan hệ giữa chúng là các cạnh của đồ thị. Để ước lượng khả năng kết liên kết của 02 phần tử, nhiều công trình nghiên cứu trước đây như PageRank [6] SimRank [7], phân tích toàn bộ đồ thị.
Năm 2017, 2018 Zhang và Chen [8, 9] chứng minh rằng việc dự đoán liên kết chỉ cần xét đến hàng xóm của cặp nút là đủ. Qua tìm hiểu bai báo [10] tác giả dé xuất sử dụng Weisfeiler- Lehman Neural Machine [8], mạng neural đồ thị [9], dé học các đặc trưng tông quát về cấu trúc đồ thị từ các đồ thị con, việc dự đoán liên kết giữa 02 phần tử đạt hiệu suất, và tính ôn định cao.4 Kết luận Chính những ưu điểm của hướng tiếp cận phân nhóm dựa trên liên kết so với các giải pháp truyền thống, đồng thời việc ứng dụng phương pháp này vào thực tế là khả thi. Vì vậy luận văn tập trung nghiên cứu phương pháp phân nhóm dựa vào liên kết bằng cach sử dụng mạng tích chập đồ thị trong việc dự đoán liên kết. Chi tiết mô hình và thuật toán sẽ được giới thiệu chi tiết trong chương 03.
NGHIÊN CỨU MÔ HÌNH, THUẬT TOÁN 3.1 Định nghĩa vấn đề bài toán Cho tập ảnh khuôn mặt, sau khi trích xuất đặc trưng, ta có một tập dữ liệu tập các đặc trưng ảnh khuôn mặt X = [x¡,.,xy]” € R**?